Line data Source code
1 : /*
2 : * contrib/intarray/_int_bool.c
3 : */
4 : #include "postgres.h"
5 :
6 : #include "_int.h"
7 : #include "miscadmin.h"
8 :
9 4 : PG_FUNCTION_INFO_V1(bqarr_in);
10 4 : PG_FUNCTION_INFO_V1(bqarr_out);
11 4 : PG_FUNCTION_INFO_V1(boolop);
12 2 : PG_FUNCTION_INFO_V1(rboolop);
13 2 : PG_FUNCTION_INFO_V1(querytree);
14 :
15 :
16 : /* parser's states */
17 : #define WAITOPERAND 1
18 : #define WAITENDOPERAND 2
19 : #define WAITOPERATOR 3
20 :
21 : /*
22 : * node of query tree, also used
23 : * for storing polish notation in parser
24 : */
25 : typedef struct NODE
26 : {
27 : int32 type;
28 : int32 val;
29 : struct NODE *next;
30 : } NODE;
31 :
32 : typedef struct
33 : {
34 : char *buf;
35 : int32 state;
36 : int32 count;
37 : struct Node *escontext;
38 : /* reverse polish notation in list (for temporary usage) */
39 : NODE *str;
40 : /* number in str */
41 : int32 num;
42 : } WORKSTATE;
43 :
44 : /*
45 : * get token from query string
46 : */
47 : static int32
48 1100 : gettoken(WORKSTATE *state, int32 *val)
49 : {
50 : char nnn[16];
51 : int innn;
52 :
53 1100 : *val = 0; /* default result */
54 :
55 1100 : innn = 0;
56 : while (1)
57 : {
58 1776 : if (innn >= sizeof(nnn))
59 0 : return ERR; /* buffer overrun => syntax error */
60 1776 : switch (state->state)
61 : {
62 636 : case WAITOPERAND:
63 636 : innn = 0;
64 636 : if ((*(state->buf) >= '0' && *(state->buf) <= '9') ||
65 226 : *(state->buf) == '-')
66 : {
67 410 : state->state = WAITENDOPERAND;
68 410 : nnn[innn++] = *(state->buf);
69 : }
70 226 : else if (*(state->buf) == '!')
71 : {
72 96 : (state->buf)++;
73 96 : *val = (int32) '!';
74 96 : return OPR;
75 : }
76 130 : else if (*(state->buf) == '(')
77 : {
78 90 : state->count++;
79 90 : (state->buf)++;
80 90 : return OPEN;
81 : }
82 40 : else if (*(state->buf) != ' ')
83 4 : return ERR;
84 446 : break;
85 606 : case WAITENDOPERAND:
86 606 : if (*(state->buf) >= '0' && *(state->buf) <= '9')
87 : {
88 196 : nnn[innn++] = *(state->buf);
89 : }
90 : else
91 : {
92 : long lval;
93 :
94 410 : nnn[innn] = '\0';
95 410 : errno = 0;
96 410 : lval = strtol(nnn, NULL, 0);
97 410 : *val = (int32) lval;
98 410 : if (errno != 0 || (long) *val != lval)
99 0 : return ERR;
100 410 : state->state = WAITOPERATOR;
101 152 : return (state->count && *(state->buf) == '\0')
102 562 : ? ERR : VAL;
103 : }
104 196 : break;
105 534 : case WAITOPERATOR:
106 534 : if (*(state->buf) == '&' || *(state->buf) == '|')
107 : {
108 244 : state->state = WAITOPERAND;
109 244 : *val = (int32) *(state->buf);
110 244 : (state->buf)++;
111 244 : return OPR;
112 : }
113 290 : else if (*(state->buf) == ')')
114 : {
115 90 : (state->buf)++;
116 90 : state->count--;
117 90 : return (state->count < 0) ? ERR : CLOSE;
118 : }
119 200 : else if (*(state->buf) == '\0')
120 162 : return (state->count) ? ERR : END;
121 38 : else if (*(state->buf) != ' ')
122 4 : return ERR;
123 34 : break;
124 0 : default:
125 0 : return ERR;
126 : break;
127 : }
128 676 : (state->buf)++;
129 : }
130 : }
131 :
132 : /*
133 : * push new one in polish notation reverse view
134 : */
135 : static void
136 750 : pushquery(WORKSTATE *state, int32 type, int32 val)
137 : {
138 750 : NODE *tmp = (NODE *) palloc(sizeof(NODE));
139 :
140 750 : tmp->type = type;
141 750 : tmp->val = val;
142 750 : tmp->next = state->str;
143 750 : state->str = tmp;
144 750 : state->num++;
145 750 : }
146 :
147 : #define STACKDEPTH 16
148 :
149 : /*
150 : * make polish notation of query
151 : */
152 : static int32
153 260 : makepol(WORKSTATE *state)
154 : {
155 : int32 val,
156 : type;
157 : int32 stack[STACKDEPTH];
158 260 : int32 lenstack = 0;
159 :
160 : /* since this function recurses, it could be driven to stack overflow */
161 260 : check_stack_depth();
162 :
163 1100 : while ((type = gettoken(state, &val)) != END)
164 : {
165 938 : switch (type)
166 : {
167 410 : case VAL:
168 410 : pushquery(state, type, val);
169 604 : while (lenstack && (stack[lenstack - 1] == (int32) '&' ||
170 166 : stack[lenstack - 1] == (int32) '!'))
171 : {
172 194 : lenstack--;
173 194 : pushquery(state, OPR, stack[lenstack]);
174 : }
175 410 : break;
176 340 : case OPR:
177 340 : if (lenstack && val == (int32) '|')
178 6 : pushquery(state, OPR, val);
179 : else
180 : {
181 334 : if (lenstack == STACKDEPTH)
182 0 : ereturn(state->escontext, ERR,
183 : (errcode(ERRCODE_STATEMENT_TOO_COMPLEX),
184 : errmsg("statement too complex")));
185 334 : stack[lenstack] = val;
186 334 : lenstack++;
187 : }
188 340 : break;
189 90 : case OPEN:
190 90 : if (makepol(state) == ERR)
191 0 : return ERR;
192 136 : while (lenstack && (stack[lenstack - 1] == (int32) '&' ||
193 38 : stack[lenstack - 1] == (int32) '!'))
194 : {
195 46 : lenstack--;
196 46 : pushquery(state, OPR, stack[lenstack]);
197 : }
198 90 : break;
199 90 : case CLOSE:
200 118 : while (lenstack)
201 : {
202 28 : lenstack--;
203 28 : pushquery(state, OPR, stack[lenstack]);
204 : };
205 90 : return END;
206 : break;
207 8 : case ERR:
208 : default:
209 8 : ereturn(state->escontext, ERR,
210 : (errcode(ERRCODE_SYNTAX_ERROR),
211 : errmsg("syntax error")));
212 : }
213 : }
214 :
215 228 : while (lenstack)
216 : {
217 66 : lenstack--;
218 66 : pushquery(state, OPR, stack[lenstack]);
219 : };
220 162 : return END;
221 : }
222 :
223 : typedef struct
224 : {
225 : int32 *arrb;
226 : int32 *arre;
227 : } CHKVAL;
228 :
229 : /*
230 : * is there value 'val' in (sorted) array or not ?
231 : */
232 : static bool
233 539212 : checkcondition_arr(void *checkval, ITEM *item, void *options)
234 : {
235 539212 : int32 *StopLow = ((CHKVAL *) checkval)->arrb;
236 539212 : int32 *StopHigh = ((CHKVAL *) checkval)->arre;
237 : int32 *StopMiddle;
238 :
239 : /* Loop invariant: StopLow <= val < StopHigh */
240 :
241 2004868 : while (StopLow < StopHigh)
242 : {
243 1490510 : StopMiddle = StopLow + (StopHigh - StopLow) / 2;
244 1490510 : if (*StopMiddle == item->val)
245 24854 : return true;
246 1465656 : else if (*StopMiddle < item->val)
247 316316 : StopLow = StopMiddle + 1;
248 : else
249 1149340 : StopHigh = StopMiddle;
250 : }
251 514358 : return false;
252 : }
253 :
254 : static bool
255 88690 : checkcondition_bit(void *checkval, ITEM *item, void *siglen)
256 : {
257 88690 : return GETBIT(checkval, HASHVAL(item->val, (int) (intptr_t) siglen));
258 : }
259 :
260 : /*
261 : * evaluate boolean expression, using chkcond() to test the primitive cases
262 : */
263 : static bool
264 1586990 : execute(ITEM *curitem, void *checkval, void *options, bool calcnot,
265 : bool (*chkcond) (void *checkval, ITEM *item, void *options))
266 : {
267 : /* since this function recurses, it could be driven to stack overflow */
268 1586990 : check_stack_depth();
269 :
270 1586990 : if (curitem->type == VAL)
271 685890 : return (*chkcond) (checkval, curitem, options);
272 901100 : else if (curitem->val == (int32) '!')
273 : {
274 : return calcnot ?
275 277572 : ((execute(curitem - 1, checkval, options, calcnot, chkcond)) ? false : true)
276 663746 : : true;
277 : }
278 514926 : else if (curitem->val == (int32) '&')
279 : {
280 277520 : if (execute(curitem + curitem->left, checkval, options, calcnot, chkcond))
281 140570 : return execute(curitem - 1, checkval, options, calcnot, chkcond);
282 : else
283 136950 : return false;
284 : }
285 : else
286 : { /* |-operator */
287 237406 : if (execute(curitem + curitem->left, checkval, options, calcnot, chkcond))
288 13438 : return true;
289 : else
290 223968 : return execute(curitem - 1, checkval, options, calcnot, chkcond);
291 : }
292 : }
293 :
294 : /*
295 : * signconsistent & execconsistent called by *_consistent
296 : */
297 : bool
298 101776 : signconsistent(QUERYTYPE *query, BITVECP sign, int siglen, bool calcnot)
299 : {
300 203552 : return execute(GETQUERY(query) + query->size - 1,
301 101776 : (void *) sign, (void *) (intptr_t) siglen, calcnot,
302 : checkcondition_bit);
303 : }
304 :
305 : /* Array must be sorted! */
306 : bool
307 161452 : execconsistent(QUERYTYPE *query, ArrayType *array, bool calcnot)
308 : {
309 : CHKVAL chkval;
310 :
311 161452 : CHECKARRVALID(array);
312 161452 : chkval.arrb = ARRPTR(array);
313 161452 : chkval.arre = chkval.arrb + ARRNELEMS(array);
314 161452 : return execute(GETQUERY(query) + query->size - 1,
315 : (void *) &chkval, NULL, calcnot,
316 : checkcondition_arr);
317 : }
318 :
319 : typedef struct
320 : {
321 : ITEM *first;
322 : bool *mapped_check;
323 : } GinChkVal;
324 :
325 : static bool
326 57988 : checkcondition_gin(void *checkval, ITEM *item, void *options)
327 : {
328 57988 : GinChkVal *gcv = (GinChkVal *) checkval;
329 :
330 57988 : return gcv->mapped_check[item - gcv->first];
331 : }
332 :
333 : bool
334 29806 : gin_bool_consistent(QUERYTYPE *query, bool *check)
335 : {
336 : GinChkVal gcv;
337 29806 : ITEM *items = GETQUERY(query);
338 : int i,
339 29806 : j = 0;
340 :
341 29806 : if (query->size <= 0)
342 0 : return false;
343 :
344 : /*
345 : * Set up data for checkcondition_gin. This must agree with the query
346 : * extraction code in ginint4_queryextract.
347 : */
348 29806 : gcv.first = items;
349 29806 : gcv.mapped_check = (bool *) palloc(sizeof(bool) * query->size);
350 164442 : for (i = 0; i < query->size; i++)
351 : {
352 134636 : if (items[i].type == VAL)
353 61936 : gcv.mapped_check[i] = check[j++];
354 : }
355 :
356 29806 : return execute(GETQUERY(query) + query->size - 1,
357 : (void *) &gcv, NULL, true,
358 : checkcondition_gin);
359 : }
360 :
361 : static bool
362 72 : contains_required_value(ITEM *curitem)
363 : {
364 : /* since this function recurses, it could be driven to stack overflow */
365 72 : check_stack_depth();
366 :
367 72 : if (curitem->type == VAL)
368 28 : return true;
369 44 : else if (curitem->val == (int32) '!')
370 : {
371 : /*
372 : * Assume anything under a NOT is non-required. For some cases with
373 : * nested NOTs, we could prove there's a required value, but it seems
374 : * unlikely to be worth the trouble.
375 : */
376 12 : return false;
377 : }
378 32 : else if (curitem->val == (int32) '&')
379 : {
380 : /* If either side has a required value, we're good */
381 20 : if (contains_required_value(curitem + curitem->left))
382 16 : return true;
383 : else
384 4 : return contains_required_value(curitem - 1);
385 : }
386 : else
387 : { /* |-operator */
388 : /* Both sides must have required values */
389 12 : if (contains_required_value(curitem + curitem->left))
390 12 : return contains_required_value(curitem - 1);
391 : else
392 0 : return false;
393 : }
394 : }
395 :
396 : bool
397 24 : query_has_required_values(QUERYTYPE *query)
398 : {
399 24 : if (query->size <= 0)
400 0 : return false;
401 24 : return contains_required_value(GETQUERY(query) + query->size - 1);
402 : }
403 :
404 : /*
405 : * boolean operations
406 : */
407 : Datum
408 0 : rboolop(PG_FUNCTION_ARGS)
409 : {
410 : /* just reverse the operands */
411 0 : return DirectFunctionCall2(boolop,
412 : PG_GETARG_DATUM(1),
413 : PG_GETARG_DATUM(0));
414 : }
415 :
416 : Datum
417 136920 : boolop(PG_FUNCTION_ARGS)
418 : {
419 136920 : ArrayType *val = PG_GETARG_ARRAYTYPE_P_COPY(0);
420 136920 : QUERYTYPE *query = PG_GETARG_QUERYTYPE_P(1);
421 : CHKVAL chkval;
422 : bool result;
423 :
424 136920 : CHECKARRVALID(val);
425 136920 : PREPAREARR(val);
426 136920 : chkval.arrb = ARRPTR(val);
427 136920 : chkval.arre = chkval.arrb + ARRNELEMS(val);
428 136920 : result = execute(GETQUERY(query) + query->size - 1,
429 : &chkval, NULL, true,
430 : checkcondition_arr);
431 136920 : pfree(val);
432 :
433 136920 : PG_FREE_IF_COPY(query, 1);
434 136920 : PG_RETURN_BOOL(result);
435 : }
436 :
437 : static void
438 746 : findoprnd(ITEM *ptr, int32 *pos)
439 : {
440 : /* since this function recurses, it could be driven to stack overflow. */
441 746 : check_stack_depth();
442 :
443 : #ifdef BS_DEBUG
444 : elog(DEBUG3, (ptr[*pos].type == OPR) ?
445 : "%d %c" : "%d %d", *pos, ptr[*pos].val);
446 : #endif
447 746 : if (ptr[*pos].type == VAL)
448 : {
449 406 : ptr[*pos].left = 0;
450 406 : (*pos)--;
451 : }
452 340 : else if (ptr[*pos].val == (int32) '!')
453 : {
454 96 : ptr[*pos].left = -1;
455 96 : (*pos)--;
456 96 : findoprnd(ptr, pos);
457 : }
458 : else
459 : {
460 244 : ITEM *curitem = &ptr[*pos];
461 244 : int32 tmp = *pos;
462 :
463 244 : (*pos)--;
464 244 : findoprnd(ptr, pos);
465 244 : curitem->left = *pos - tmp;
466 244 : findoprnd(ptr, pos);
467 : }
468 746 : }
469 :
470 :
471 : /*
472 : * input
473 : */
474 : Datum
475 170 : bqarr_in(PG_FUNCTION_ARGS)
476 : {
477 170 : char *buf = (char *) PG_GETARG_POINTER(0);
478 : WORKSTATE state;
479 : int32 i;
480 : QUERYTYPE *query;
481 : int32 commonlen;
482 : ITEM *ptr;
483 : NODE *tmp;
484 170 : int32 pos = 0;
485 170 : struct Node *escontext = fcinfo->context;
486 :
487 : #ifdef BS_DEBUG
488 : StringInfoData pbuf;
489 : #endif
490 :
491 170 : state.buf = buf;
492 170 : state.state = WAITOPERAND;
493 170 : state.count = 0;
494 170 : state.num = 0;
495 170 : state.str = NULL;
496 170 : state.escontext = escontext;
497 :
498 : /* make polish notation (postfix, but in reverse order) */
499 170 : if (makepol(&state) == ERR)
500 8 : PG_RETURN_NULL();
501 162 : if (!state.num)
502 0 : ereturn(escontext, (Datum) 0,
503 : (errcode(ERRCODE_INVALID_PARAMETER_VALUE),
504 : errmsg("empty query")));
505 :
506 162 : if (state.num > QUERYTYPEMAXITEMS)
507 0 : ereturn(escontext, (Datum) 0,
508 : (errcode(ERRCODE_PROGRAM_LIMIT_EXCEEDED),
509 : errmsg("number of query items (%d) exceeds the maximum allowed (%d)",
510 : state.num, (int) QUERYTYPEMAXITEMS)));
511 162 : commonlen = COMPUTESIZE(state.num);
512 :
513 162 : query = (QUERYTYPE *) palloc(commonlen);
514 162 : SET_VARSIZE(query, commonlen);
515 162 : query->size = state.num;
516 162 : ptr = GETQUERY(query);
517 :
518 908 : for (i = state.num - 1; i >= 0; i--)
519 : {
520 746 : ptr[i].type = state.str->type;
521 746 : ptr[i].val = state.str->val;
522 746 : tmp = state.str->next;
523 746 : pfree(state.str);
524 746 : state.str = tmp;
525 : }
526 :
527 162 : pos = query->size - 1;
528 162 : findoprnd(ptr, &pos);
529 : #ifdef BS_DEBUG
530 : initStringInfo(&pbuf);
531 : for (i = 0; i < query->size; i++)
532 : {
533 : if (ptr[i].type == OPR)
534 : appendStringInfo(&pbuf, "%c(%d) ", ptr[i].val, ptr[i].left);
535 : else
536 : appendStringInfo(&pbuf, "%d ", ptr[i].val);
537 : }
538 : elog(DEBUG3, "POR: %s", pbuf.data);
539 : pfree(pbuf.data);
540 : #endif
541 :
542 162 : PG_RETURN_POINTER(query);
543 : }
544 :
545 :
546 : /*
547 : * out function
548 : */
549 : typedef struct
550 : {
551 : ITEM *curpol;
552 : char *buf;
553 : char *cur;
554 : int32 buflen;
555 : } INFIX;
556 :
557 : #define RESIZEBUF(inf,addsize) while( ( (inf)->cur - (inf)->buf ) + (addsize) + 1 >= (inf)->buflen ) { \
558 : int32 len = inf->cur - inf->buf; \
559 : inf->buflen *= 2; \
560 : inf->buf = (char*) repalloc( (void*)inf->buf, inf->buflen ); \
561 : inf->cur = inf->buf + len; \
562 : }
563 :
564 : static void
565 360 : infix(INFIX *in, bool first)
566 : {
567 : /* since this function recurses, it could be driven to stack overflow. */
568 360 : check_stack_depth();
569 :
570 360 : if (in->curpol->type == VAL)
571 : {
572 190 : RESIZEBUF(in, 11);
573 190 : sprintf(in->cur, "%d", in->curpol->val);
574 190 : in->cur = strchr(in->cur, '\0');
575 190 : in->curpol--;
576 : }
577 170 : else if (in->curpol->val == (int32) '!')
578 : {
579 54 : bool isopr = false;
580 :
581 54 : RESIZEBUF(in, 1);
582 54 : *(in->cur) = '!';
583 54 : in->cur++;
584 54 : *(in->cur) = '\0';
585 54 : in->curpol--;
586 54 : if (in->curpol->type == OPR)
587 : {
588 12 : isopr = true;
589 12 : RESIZEBUF(in, 2);
590 12 : sprintf(in->cur, "( ");
591 12 : in->cur = strchr(in->cur, '\0');
592 : }
593 54 : infix(in, isopr);
594 54 : if (isopr)
595 : {
596 12 : RESIZEBUF(in, 2);
597 12 : sprintf(in->cur, " )");
598 12 : in->cur = strchr(in->cur, '\0');
599 : }
600 : }
601 : else
602 : {
603 116 : int32 op = in->curpol->val;
604 : INFIX nrm;
605 :
606 116 : in->curpol--;
607 116 : if (op == (int32) '|' && !first)
608 : {
609 20 : RESIZEBUF(in, 2);
610 20 : sprintf(in->cur, "( ");
611 20 : in->cur = strchr(in->cur, '\0');
612 : }
613 :
614 116 : nrm.curpol = in->curpol;
615 116 : nrm.buflen = 16;
616 116 : nrm.cur = nrm.buf = (char *) palloc(sizeof(char) * nrm.buflen);
617 :
618 : /* get right operand */
619 116 : infix(&nrm, false);
620 :
621 : /* get & print left operand */
622 116 : in->curpol = nrm.curpol;
623 116 : infix(in, false);
624 :
625 : /* print operator & right operand */
626 124 : RESIZEBUF(in, 3 + (nrm.cur - nrm.buf));
627 116 : sprintf(in->cur, " %c %s", op, nrm.buf);
628 116 : in->cur = strchr(in->cur, '\0');
629 116 : pfree(nrm.buf);
630 :
631 116 : if (op == (int32) '|' && !first)
632 : {
633 20 : RESIZEBUF(in, 2);
634 20 : sprintf(in->cur, " )");
635 20 : in->cur = strchr(in->cur, '\0');
636 : }
637 : }
638 360 : }
639 :
640 :
641 : Datum
642 74 : bqarr_out(PG_FUNCTION_ARGS)
643 : {
644 74 : QUERYTYPE *query = PG_GETARG_QUERYTYPE_P(0);
645 : INFIX nrm;
646 :
647 74 : if (query->size == 0)
648 0 : ereport(ERROR,
649 : (errcode(ERRCODE_INVALID_PARAMETER_VALUE),
650 : errmsg("empty query")));
651 :
652 74 : nrm.curpol = GETQUERY(query) + query->size - 1;
653 74 : nrm.buflen = 32;
654 74 : nrm.cur = nrm.buf = (char *) palloc(sizeof(char) * nrm.buflen);
655 74 : *(nrm.cur) = '\0';
656 74 : infix(&nrm, true);
657 :
658 74 : PG_FREE_IF_COPY(query, 0);
659 74 : PG_RETURN_POINTER(nrm.buf);
660 : }
661 :
662 :
663 : /* Useless old "debugging" function for a fundamentally wrong algorithm */
664 : Datum
665 0 : querytree(PG_FUNCTION_ARGS)
666 : {
667 0 : elog(ERROR, "querytree is no longer implemented");
668 : PG_RETURN_NULL();
669 : }
|
