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