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 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 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 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 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 */ 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 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 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 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, 360 checkcondition_gin); 361 } 362 363 static bool 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 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 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 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 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 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 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 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 664 querytree(PG_FUNCTION_ARGS) 665 { 666 elog(ERROR, "querytree is no longer implemented"); 667 PG_RETURN_NULL(); 668 } 669