TLA 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 CBC 2 : PG_FUNCTION_INFO_V1(bqarr_in);
11 2 : PG_FUNCTION_INFO_V1(bqarr_out);
12 2 : PG_FUNCTION_INFO_V1(boolop);
13 1 : PG_FUNCTION_INFO_V1(rboolop);
14 1 : 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 GIC 515 : gettoken(WORKSTATE *state, int32 *val)
50 ECB : {
51 : char nnn[16];
52 : int innn;
53 :
54 GIC 515 : *val = 0; /* default result */
55 ECB :
56 GIC 515 : innn = 0;
57 ECB : while (1)
58 : {
59 GIC 821 : if (innn >= sizeof(nnn))
60 LBC 0 : return ERR; /* buffer overrun => syntax error */
61 GBC 821 : switch (state->state)
62 ECB : {
63 GIC 297 : case WAITOPERAND:
64 CBC 297 : innn = 0;
65 297 : if ((*(state->buf) >= '0' && *(state->buf) <= '9') ||
66 106 : *(state->buf) == '-')
67 ECB : {
68 GIC 191 : state->state = WAITENDOPERAND;
69 CBC 191 : nnn[innn++] = *(state->buf);
70 ECB : }
71 GIC 106 : else if (*(state->buf) == '!')
72 ECB : {
73 GIC 45 : (state->buf)++;
74 CBC 45 : *val = (int32) '!';
75 45 : return OPR;
76 ECB : }
77 GIC 61 : else if (*(state->buf) == '(')
78 ECB : {
79 GIC 43 : state->count++;
80 CBC 43 : (state->buf)++;
81 43 : return OPEN;
82 ECB : }
83 GIC 18 : else if (*(state->buf) != ' ')
84 CBC 2 : return ERR;
85 207 : break;
86 275 : case WAITENDOPERAND:
87 275 : if (*(state->buf) >= '0' && *(state->buf) <= '9')
88 ECB : {
89 GIC 84 : nnn[innn++] = *(state->buf);
90 ECB : }
91 : else
92 : {
93 : long lval;
94 :
95 GIC 191 : nnn[innn] = '\0';
96 CBC 191 : errno = 0;
97 191 : lval = strtol(nnn, NULL, 0);
98 191 : *val = (int32) lval;
99 191 : if (errno != 0 || (long) *val != lval)
100 LBC 0 : return ERR;
101 GBC 191 : state->state = WAITOPERATOR;
102 CBC 72 : return (state->count && *(state->buf) == '\0')
103 263 : ? ERR : VAL;
104 ECB : }
105 GIC 84 : break;
106 CBC 249 : case WAITOPERATOR:
107 249 : if (*(state->buf) == '&' || *(state->buf) == '|')
108 ECB : {
109 GIC 114 : state->state = WAITOPERAND;
110 CBC 114 : *val = (int32) *(state->buf);
111 114 : (state->buf)++;
112 114 : return OPR;
113 ECB : }
114 GIC 135 : else if (*(state->buf) == ')')
115 ECB : {
116 GIC 43 : (state->buf)++;
117 CBC 43 : state->count--;
118 43 : return (state->count < 0) ? ERR : CLOSE;
119 ECB : }
120 GIC 92 : else if (*(state->buf) == '\0')
121 CBC 75 : return (state->count) ? ERR : END;
122 17 : else if (*(state->buf) != ' ')
123 2 : return ERR;
124 15 : break;
125 LBC 0 : default:
126 UBC 0 : return ERR;
127 EUB : break;
128 : }
129 GIC 306 : (state->buf)++;
130 ECB : }
131 : }
132 :
133 : /*
134 : * push new one in polish notation reverse view
135 : */
136 : static void
137 GIC 350 : pushquery(WORKSTATE *state, int32 type, int32 val)
138 ECB : {
139 GIC 350 : NODE *tmp = (NODE *) palloc(sizeof(NODE));
140 ECB :
141 GIC 350 : tmp->type = type;
142 CBC 350 : tmp->val = val;
143 350 : tmp->next = state->str;
144 350 : state->str = tmp;
145 350 : state->num++;
146 350 : }
147 ECB :
148 : #define STACKDEPTH 16
149 :
150 : /*
151 : * make polish notation of query
152 : */
153 : static int32
154 GIC 122 : makepol(WORKSTATE *state)
155 ECB : {
156 : int32 val,
157 : type;
158 : int32 stack[STACKDEPTH];
159 GIC 122 : int32 lenstack = 0;
160 ECB :
161 : /* since this function recurses, it could be driven to stack overflow */
162 GIC 122 : check_stack_depth();
163 ECB :
164 GIC 515 : while ((type = gettoken(state, &val)) != END)
165 ECB : {
166 GIC 440 : switch (type)
167 ECB : {
168 GIC 191 : case VAL:
169 CBC 191 : pushquery(state, type, val);
170 280 : while (lenstack && (stack[lenstack - 1] == (int32) '&' ||
171 78 : stack[lenstack - 1] == (int32) '!'))
172 ECB : {
173 GIC 89 : lenstack--;
174 CBC 89 : pushquery(state, OPR, stack[lenstack]);
175 ECB : }
176 GIC 191 : break;
177 CBC 159 : case OPR:
178 159 : if (lenstack && val == (int32) '|')
179 3 : pushquery(state, OPR, val);
180 ECB : else
181 : {
182 GIC 156 : if (lenstack == STACKDEPTH)
183 UNC 0 : ereturn(state->escontext, ERR,
184 EUB : (errcode(ERRCODE_STATEMENT_TOO_COMPLEX),
185 : errmsg("statement too complex")));
186 GIC 156 : stack[lenstack] = val;
187 CBC 156 : lenstack++;
188 ECB : }
189 GIC 159 : break;
190 CBC 43 : case OPEN:
191 43 : if (makepol(state) == ERR)
192 LBC 0 : return ERR;
193 GBC 66 : while (lenstack && (stack[lenstack - 1] == (int32) '&' ||
194 CBC 18 : stack[lenstack - 1] == (int32) '!'))
195 ECB : {
196 GIC 23 : lenstack--;
197 CBC 23 : pushquery(state, OPR, stack[lenstack]);
198 ECB : }
199 GIC 43 : break;
200 CBC 43 : case CLOSE:
201 57 : while (lenstack)
202 ECB : {
203 GIC 14 : lenstack--;
204 CBC 14 : pushquery(state, OPR, stack[lenstack]);
205 ECB : };
206 GIC 43 : return END;
207 ECB : break;
208 GIC 4 : case ERR:
209 ECB : default:
210 GNC 4 : ereturn(state->escontext, ERR,
211 ECB : (errcode(ERRCODE_SYNTAX_ERROR),
212 : errmsg("syntax error")));
213 : }
214 : }
215 :
216 CBC 105 : while (lenstack)
217 : {
218 30 : lenstack--;
219 30 : pushquery(state, OPR, stack[lenstack]);
220 : };
221 75 : 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 223162 : checkcondition_arr(void *checkval, ITEM *item, void *options)
235 : {
236 223162 : int32 *StopLow = ((CHKVAL *) checkval)->arrb;
237 223162 : int32 *StopHigh = ((CHKVAL *) checkval)->arre;
238 : int32 *StopMiddle;
239 :
240 : /* Loop invariant: StopLow <= val < StopHigh */
241 :
242 770743 : while (StopLow < StopHigh)
243 : {
244 556778 : StopMiddle = StopLow + (StopHigh - StopLow) / 2;
245 556778 : if (*StopMiddle == item->val)
246 9197 : return true;
247 547581 : else if (*StopMiddle < item->val)
248 129422 : StopLow = StopMiddle + 1;
249 : else
250 418159 : StopHigh = StopMiddle;
251 : }
252 213965 : return false;
253 : }
254 :
255 : static bool
256 43839 : checkcondition_bit(void *checkval, ITEM *item, void *siglen)
257 : {
258 43839 : 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 693384 : 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 693384 : check_stack_depth();
270 :
271 693384 : if (curitem->type == VAL)
272 295991 : return (*chkcond) (checkval, curitem, options);
273 397393 : else if (curitem->val == (int32) '!')
274 : {
275 : return calcnot ?
276 118943 : ((execute(curitem - 1, checkval, options, calcnot, chkcond)) ? false : true)
277 291288 : : true;
278 : }
279 225048 : else if (curitem->val == (int32) '&')
280 : {
281 121854 : if (execute(curitem + curitem->left, checkval, options, calcnot, chkcond))
282 62355 : return execute(curitem - 1, checkval, options, calcnot, chkcond);
283 : else
284 59499 : return false;
285 : }
286 : else
287 : { /* |-operator */
288 103194 : if (execute(curitem + curitem->left, checkval, options, calcnot, chkcond))
289 5706 : return true;
290 : else
291 97488 : return execute(curitem - 1, checkval, options, calcnot, chkcond);
292 : }
293 : }
294 :
295 : /*
296 : * signconsistent & execconsistent called by *_consistent
297 : */
298 : bool
299 50701 : signconsistent(QUERYTYPE *query, BITVECP sign, int siglen, bool calcnot)
300 : {
301 101402 : return execute(GETQUERY(query) + query->size - 1,
302 50701 : (void *) sign, (void *) (intptr_t) siglen, calcnot,
303 : checkcondition_bit);
304 : }
305 :
306 : /* Array must be sorted! */
307 : bool
308 55498 : execconsistent(QUERYTYPE *query, ArrayType *array, bool calcnot)
309 : {
310 : CHKVAL chkval;
311 :
312 55498 : CHECKARRVALID(array);
313 55498 : chkval.arrb = ARRPTR(array);
314 55498 : chkval.arre = chkval.arrb + ARRNELEMS(array);
315 55498 : 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 28990 : checkcondition_gin(void *checkval, ITEM *item, void *options)
328 : {
329 28990 : GinChkVal *gcv = (GinChkVal *) checkval;
330 :
331 28990 : return gcv->mapped_check[item - gcv->first];
332 : }
333 :
334 : bool
335 14901 : gin_bool_consistent(QUERYTYPE *query, bool *check)
336 : {
337 : GinChkVal gcv;
338 14901 : ITEM *items = GETQUERY(query);
339 : int i,
340 14901 : j = 0;
341 :
342 14901 : if (query->size <= 0)
343 UBC 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 CBC 14901 : gcv.first = items;
350 14901 : gcv.mapped_check = (bool *) palloc(sizeof(bool) * query->size);
351 82210 : for (i = 0; i < query->size; i++)
352 : {
353 67309 : if (items[i].type == VAL)
354 30964 : gcv.mapped_check[i] = check[j++];
355 : }
356 :
357 14901 : return execute(GETQUERY(query) + query->size - 1,
358 : (void *) &gcv, NULL, true,
359 : checkcondition_gin);
360 : }
361 :
362 : static bool
363 36 : contains_required_value(ITEM *curitem)
364 : {
365 : /* since this function recurses, it could be driven to stack overflow */
366 36 : check_stack_depth();
367 :
368 36 : if (curitem->type == VAL)
369 14 : return true;
370 22 : 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 6 : return false;
378 : }
379 16 : else if (curitem->val == (int32) '&')
380 : {
381 : /* If either side has a required value, we're good */
382 10 : if (contains_required_value(curitem + curitem->left))
383 8 : return true;
384 : else
385 2 : return contains_required_value(curitem - 1);
386 : }
387 : else
388 : { /* |-operator */
389 : /* Both sides must have required values */
390 6 : if (contains_required_value(curitem + curitem->left))
391 6 : return contains_required_value(curitem - 1);
392 : else
393 UBC 0 : return false;
394 : }
395 : }
396 :
397 : bool
398 CBC 12 : query_has_required_values(QUERYTYPE *query)
399 : {
400 12 : if (query->size <= 0)
401 UBC 0 : return false;
402 CBC 12 : return contains_required_value(GETQUERY(query) + query->size - 1);
403 : }
404 :
405 : /*
406 : * boolean operations
407 : */
408 : Datum
409 UBC 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 CBC 68450 : boolop(PG_FUNCTION_ARGS)
419 : {
420 68450 : ArrayType *val = PG_GETARG_ARRAYTYPE_P_COPY(0);
421 68450 : QUERYTYPE *query = PG_GETARG_QUERYTYPE_P(1);
422 : CHKVAL chkval;
423 : bool result;
424 :
425 68450 : CHECKARRVALID(val);
426 68450 : PREPAREARR(val);
427 68450 : chkval.arrb = ARRPTR(val);
428 68450 : chkval.arre = chkval.arrb + ARRNELEMS(val);
429 68450 : result = execute(GETQUERY(query) + query->size - 1,
430 : &chkval, NULL, true,
431 : checkcondition_arr);
432 68450 : pfree(val);
433 :
434 68450 : PG_FREE_IF_COPY(query, 1);
435 68450 : PG_RETURN_BOOL(result);
436 : }
437 :
438 : static void
439 348 : findoprnd(ITEM *ptr, int32 *pos)
440 : {
441 : /* since this function recurses, it could be driven to stack overflow. */
442 348 : 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 348 : if (ptr[*pos].type == VAL)
449 : {
450 189 : ptr[*pos].left = 0;
451 189 : (*pos)--;
452 : }
453 159 : else if (ptr[*pos].val == (int32) '!')
454 : {
455 45 : ptr[*pos].left = -1;
456 45 : (*pos)--;
457 45 : findoprnd(ptr, pos);
458 : }
459 : else
460 : {
461 114 : ITEM *curitem = &ptr[*pos];
462 114 : int32 tmp = *pos;
463 :
464 114 : (*pos)--;
465 114 : findoprnd(ptr, pos);
466 114 : curitem->left = *pos - tmp;
467 114 : findoprnd(ptr, pos);
468 : }
469 348 : }
470 :
471 :
472 : /*
473 : * input
474 : */
475 : Datum
476 79 : bqarr_in(PG_FUNCTION_ARGS)
477 : {
478 79 : 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 79 : int32 pos = 0;
486 GNC 79 : struct Node *escontext = fcinfo->context;
487 ECB :
488 : #ifdef BS_DEBUG
489 : StringInfoData pbuf;
490 : #endif
491 :
492 GIC 79 : state.buf = buf;
493 CBC 79 : state.state = WAITOPERAND;
494 79 : state.count = 0;
495 79 : state.num = 0;
496 79 : state.str = NULL;
497 GNC 79 : state.escontext = escontext;
498 ECB :
499 : /* make polish notation (postfix, but in reverse order) */
500 GNC 79 : if (makepol(&state) == ERR)
501 4 : PG_RETURN_NULL();
502 GIC 75 : if (!state.num)
503 UNC 0 : ereturn(escontext, (Datum) 0,
504 ECB : (errcode(ERRCODE_INVALID_PARAMETER_VALUE),
505 : errmsg("empty query")));
506 EUB :
507 GIC 75 : if (state.num > QUERYTYPEMAXITEMS)
508 UNC 0 : ereturn(escontext, (Datum) 0,
509 : (errcode(ERRCODE_PROGRAM_LIMIT_EXCEEDED),
510 ECB : errmsg("number of query items (%d) exceeds the maximum allowed (%d)",
511 EUB : state.num, (int) QUERYTYPEMAXITEMS)));
512 GIC 75 : commonlen = COMPUTESIZE(state.num);
513 :
514 75 : query = (QUERYTYPE *) palloc(commonlen);
515 CBC 75 : SET_VARSIZE(query, commonlen);
516 GIC 75 : query->size = state.num;
517 CBC 75 : ptr = GETQUERY(query);
518 ECB :
519 CBC 423 : for (i = state.num - 1; i >= 0; i--)
520 ECB : {
521 GIC 348 : ptr[i].type = state.str->type;
522 CBC 348 : ptr[i].val = state.str->val;
523 GIC 348 : tmp = state.str->next;
524 CBC 348 : pfree(state.str);
525 348 : state.str = tmp;
526 ECB : }
527 :
528 CBC 75 : pos = query->size - 1;
529 GIC 75 : findoprnd(ptr, &pos);
530 : #ifdef BS_DEBUG
531 ECB : 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 GIC 75 : PG_RETURN_POINTER(query);
544 : }
545 :
546 ECB :
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 GIC 180 : infix(INFIX *in, bool first)
567 : {
568 : /* since this function recurses, it could be driven to stack overflow. */
569 CBC 180 : check_stack_depth();
570 :
571 GIC 180 : if (in->curpol->type == VAL)
572 ECB : {
573 GIC 95 : RESIZEBUF(in, 11);
574 CBC 95 : sprintf(in->cur, "%d", in->curpol->val);
575 GIC 95 : in->cur = strchr(in->cur, '\0');
576 CBC 95 : in->curpol--;
577 ECB : }
578 CBC 85 : else if (in->curpol->val == (int32) '!')
579 ECB : {
580 GIC 27 : bool isopr = false;
581 ECB :
582 GIC 27 : RESIZEBUF(in, 1);
583 CBC 27 : *(in->cur) = '!';
584 GIC 27 : in->cur++;
585 CBC 27 : *(in->cur) = '\0';
586 27 : in->curpol--;
587 27 : if (in->curpol->type == OPR)
588 ECB : {
589 CBC 6 : isopr = true;
590 6 : RESIZEBUF(in, 2);
591 GIC 6 : sprintf(in->cur, "( ");
592 CBC 6 : in->cur = strchr(in->cur, '\0');
593 ECB : }
594 CBC 27 : infix(in, isopr);
595 27 : if (isopr)
596 : {
597 6 : RESIZEBUF(in, 2);
598 6 : sprintf(in->cur, " )");
599 GIC 6 : in->cur = strchr(in->cur, '\0');
600 ECB : }
601 : }
602 : else
603 : {
604 GIC 58 : int32 op = in->curpol->val;
605 : INFIX nrm;
606 :
607 CBC 58 : in->curpol--;
608 GIC 58 : if (op == (int32) '|' && !first)
609 : {
610 CBC 10 : RESIZEBUF(in, 2);
611 10 : sprintf(in->cur, "( ");
612 GIC 10 : in->cur = strchr(in->cur, '\0');
613 ECB : }
614 :
615 CBC 58 : nrm.curpol = in->curpol;
616 GIC 58 : nrm.buflen = 16;
617 58 : nrm.cur = nrm.buf = (char *) palloc(sizeof(char) * nrm.buflen);
618 ECB :
619 : /* get right operand */
620 CBC 58 : infix(&nrm, false);
621 :
622 : /* get & print left operand */
623 58 : in->curpol = nrm.curpol;
624 GIC 58 : infix(in, false);
625 :
626 ECB : /* print operator & right operand */
627 CBC 62 : RESIZEBUF(in, 3 + (nrm.cur - nrm.buf));
628 GIC 58 : sprintf(in->cur, " %c %s", op, nrm.buf);
629 58 : in->cur = strchr(in->cur, '\0');
630 CBC 58 : pfree(nrm.buf);
631 ECB :
632 CBC 58 : if (op == (int32) '|' && !first)
633 ECB : {
634 GIC 10 : RESIZEBUF(in, 2);
635 CBC 10 : sprintf(in->cur, " )");
636 GIC 10 : in->cur = strchr(in->cur, '\0');
637 ECB : }
638 : }
639 CBC 180 : }
640 :
641 :
642 ECB : Datum
643 GIC 37 : bqarr_out(PG_FUNCTION_ARGS)
644 : {
645 37 : QUERYTYPE *query = PG_GETARG_QUERYTYPE_P(0);
646 ECB : INFIX nrm;
647 :
648 CBC 37 : if (query->size == 0)
649 UIC 0 : ereport(ERROR,
650 : (errcode(ERRCODE_INVALID_PARAMETER_VALUE),
651 ECB : errmsg("empty query")));
652 EUB :
653 GIC 37 : nrm.curpol = GETQUERY(query) + query->size - 1;
654 37 : nrm.buflen = 32;
655 37 : nrm.cur = nrm.buf = (char *) palloc(sizeof(char) * nrm.buflen);
656 CBC 37 : *(nrm.cur) = '\0';
657 37 : infix(&nrm, true);
658 ECB :
659 CBC 37 : PG_FREE_IF_COPY(query, 0);
660 37 : PG_RETURN_POINTER(nrm.buf);
661 : }
662 ECB :
663 :
664 : /* Useless old "debugging" function for a fundamentally wrong algorithm */
665 : Datum
666 UIC 0 : querytree(PG_FUNCTION_ARGS)
667 : {
668 0 : elog(ERROR, "querytree is no longer implemented");
669 EUB : PG_RETURN_NULL();
670 : }
|
