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