PostgreSQL Source Code  git master
_int_bool.c
Go to the documentation of this file.
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 
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 {
30  struct NODE *next;
31 } NODE;
32 
33 typedef struct
34 {
35  char *buf;
38  /* reverse polish notation in list (for temporary usage) */
40  /* number in str */
42 } WORKSTATE;
43 
44 /*
45  * get token from query string
46  */
47 static int32
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
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
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 */
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 {
229 } CHKVAL;
230 
231 /*
232  * is there value 'val' in (sorted) array or not ?
233  */
234 static bool
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
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
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 */
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
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,
305 }
306 
307 /* Array must be sorted! */
308 bool
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,
319 }
320 
321 typedef struct
322 {
325 } GinChkVal;
326 
327 static bool
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
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,
361 }
362 
363 static bool
365 {
366  /* since this function recurses, it could be driven to stack overflow */
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
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
411 {
412  /* just reverse the operands */
414  PG_GETARG_DATUM(1),
415  PG_GETARG_DATUM(0));
416 }
417 
418 Datum
420 {
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,
433  pfree(val);
434 
435  PG_FREE_IF_COPY(query, 1);
436  PG_RETURN_BOOL(result);
437 }
438 
439 static void
440 findoprnd(ITEM *ptr, int32 *pos)
441 {
442  /* since this function recurses, it could be driven to stack overflow. */
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
478 {
479  char *buf = (char *) PG_GETARG_POINTER(0);
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 {
551  char *buf;
552  char *cur;
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
564 infix(INFIX *in, bool first)
565 {
566  /* since this function recurses, it could be driven to stack overflow. */
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
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
665 {
666  elog(ERROR, "querytree is no longer implemented");
667  PG_RETURN_NULL();
668 }
#define PG_GETARG_QUERYTYPE_P(n)
Definition: _int.h:170
Definition: _int.h:140
#define PG_RETURN_POINTER(x)
Definition: fmgr.h:360
Datum boolop(PG_FUNCTION_ARGS)
Definition: _int_bool.c:419
Definition: _int_bool.c:26
#define ERR
Definition: _int.h:161
#define WAITOPERAND
Definition: _int_bool.c:18
ITEM * curpol
Definition: _int_bool.c:550
#define DEBUG3
Definition: elog.h:23
struct NODE * left
#define PG_GETARG_ARRAYTYPE_P_COPY(n)
Definition: array.h:252
static bool contains_required_value(ITEM *curitem)
Definition: _int_bool.c:364
int32 val
Definition: _int_bool.c:29
#define PG_GETARG_DATUM(n)
Definition: fmgr.h:268
#define CHECKARRVALID(x)
Definition: _int.h:30
#define WAITOPERATOR
Definition: _int_bool.c:20
#define PREPAREARR(x)
Definition: _int.h:49
static int32 gettoken(WORKSTATE *state, int32 *val)
Definition: _int_bool.c:48
static bool checkcondition_gin(void *checkval, ITEM *item, void *options)
Definition: _int_bool.c:328
int errcode(int sqlerrcode)
Definition: elog.c:610
#define PG_GETARG_POINTER(n)
Definition: fmgr.h:276
bool * mapped_check
Definition: _int_bool.c:324
#define GETQUERY(x)
Definition: _int.h:157
struct NODE * next
Definition: _int_bool.c:30
int32 count
Definition: _int_bool.c:37
int32 state
Definition: _int_bool.c:36
signed int int32
Definition: c.h:355
static void findoprnd(ITEM *ptr, int32 *pos)
Definition: _int_bool.c:440
PG_FUNCTION_INFO_V1(bqarr_in)
int16 type
Definition: _int.h:142
int32 * arrb
Definition: _int_bool.c:227
bool gin_bool_consistent(QUERYTYPE *query, bool *check)
Definition: _int_bool.c:336
#define sprintf
Definition: port.h:195
void pfree(void *pointer)
Definition: mcxt.c:1056
NODE * str
Definition: _int_bool.c:39
#define END
Definition: _int.h:160
void appendStringInfo(StringInfo str, const char *fmt,...)
Definition: stringinfo.c:91
#define GETBIT(x, i)
Definition: blutils.c:33
#define CLOSE
Definition: _int.h:165
#define ERROR
Definition: elog.h:43
Datum bqarr_in(PG_FUNCTION_ARGS)
Definition: _int_bool.c:477
char sign
Definition: informix.c:668
static char * buf
Definition: pg_test_fsync.c:67
void check_stack_depth(void)
Definition: postgres.c:3312
int32 val
Definition: _int.h:144
static bool checkcondition_arr(void *checkval, ITEM *item, void *options)
Definition: _int_bool.c:235
Datum bqarr_out(PG_FUNCTION_ARGS)
Definition: _int_bool.c:641
char * buf
Definition: _int_bool.c:35
#define OPEN
Definition: _int.h:164
static char ** options
void initStringInfo(StringInfo str)
Definition: stringinfo.c:59
static void infix(INFIX *in, bool first)
Definition: _int_bool.c:564
static bool execute(ITEM *curitem, void *checkval, void *options, bool calcnot, bool(*chkcond)(void *checkval, ITEM *item, void *options))
Definition: _int_bool.c:266
#define PG_RETURN_BOOL(x)
Definition: fmgr.h:358
uintptr_t Datum
Definition: postgres.h:367
#define COMPUTESIZE(size)
Definition: _int.h:155
bool query_has_required_values(QUERYTYPE *query)
Definition: _int_bool.c:399
int16 left
Definition: _int.h:143
#define ereport(elevel,...)
Definition: elog.h:144
bool signconsistent(QUERYTYPE *query, BITVECP sign, int siglen, bool calcnot)
Definition: _int_bool.c:300
#define VAL
Definition: _int.h:162
#define HASHVAL(val, siglen)
Definition: hstore_gist.c:44
#define WAITENDOPERAND
Definition: _int_bool.c:19
Datum rboolop(PG_FUNCTION_ARGS)
Definition: _int_bool.c:410
#define OPR
Definition: _int.h:163
Definition: regguts.h:298
int32 num
Definition: _int_bool.c:41
static int32 makepol(WORKSTATE *state)
Definition: _int_bool.c:153
#define PG_FREE_IF_COPY(ptr, n)
Definition: fmgr.h:260
#define ARRNELEMS(x)
Definition: cube.c:25
Datum querytree(PG_FUNCTION_ARGS)
Definition: _int_bool.c:664
#define RESIZEBUF(inf, addsize)
Definition: _int_bool.c:556
char * cur
Definition: _int_bool.c:552
static bool checkcondition_bit(void *checkval, ITEM *item, void *siglen)
Definition: _int_bool.c:257
void * palloc(Size size)
Definition: mcxt.c:949
int32 buflen
Definition: _int_bool.c:553
int errmsg(const char *fmt,...)
Definition: elog.c:824
int32 * arre
Definition: _int_bool.c:228
#define elog(elevel,...)
Definition: elog.h:214
int i
static void pushquery(WORKSTATE *state, int32 type, int32 val)
Definition: _int_bool.c:136
ITEM * first
Definition: _int_bool.c:323
#define PG_FUNCTION_ARGS
Definition: fmgr.h:193
#define SET_VARSIZE(PTR, len)
Definition: postgres.h:329
char * BITVECP
Definition: hstore_gist.c:30
#define ARRPTR(x)
Definition: cube.c:24
struct NODE NODE
bool execconsistent(QUERYTYPE *query, ArrayType *array, bool calcnot)
Definition: _int_bool.c:309
int32 size
Definition: _int.h:150
#define STACKDEPTH
Definition: _int_bool.c:147
#define QUERYTYPEMAXITEMS
Definition: _int.h:156
#define DirectFunctionCall2(func, arg1, arg2)
Definition: fmgr.h:626
#define PG_RETURN_NULL()
Definition: fmgr.h:344
int32 type
Definition: _int_bool.c:28
char * buf
Definition: _int_bool.c:551