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