Age Owner TLA Line data Source code
1 : /*-------------------------------------------------------------------------
2 : *
3 : * tsquery_util.c
4 : * Utilities for tsquery datatype
5 : *
6 : * Portions Copyright (c) 1996-2023, PostgreSQL Global Development Group
7 : *
8 : *
9 : * IDENTIFICATION
10 : * src/backend/utils/adt/tsquery_util.c
11 : *
12 : *-------------------------------------------------------------------------
13 : */
14 :
15 : #include "postgres.h"
16 :
17 : #include "miscadmin.h"
18 : #include "tsearch/ts_utils.h"
19 : #include "varatt.h"
20 :
21 : /*
22 : * Build QTNode tree for a tsquery given in QueryItem array format.
23 : */
24 : QTNode *
5624 bruce 25 GIC 4455 : QT2QTN(QueryItem *in, char *operand)
5710 tgl 26 ECB : {
5710 tgl 27 GIC 4455 : QTNode *node = (QTNode *) palloc0(sizeof(QTNode));
5710 tgl 28 ECB :
29 : /* since this function recurses, it could be driven to stack overflow. */
5693 teodor 30 GIC 4455 : check_stack_depth();
5693 teodor 31 ECB :
5710 tgl 32 GIC 4455 : node->valnode = in;
5710 tgl 33 ECB :
5693 teodor 34 GIC 4455 : if (in->type == QI_OPR)
5710 tgl 35 ECB : {
5710 tgl 36 GIC 1679 : node->child = (QTNode **) palloc0(sizeof(QTNode *) * 2);
5710 tgl 37 CBC 1679 : node->child[0] = QT2QTN(in + 1, operand);
38 1679 : node->sign = node->child[0]->sign;
5015 peter_e 39 1679 : if (in->qoperator.oper == OP_NOT)
5710 tgl 40 21 : node->nchild = 1;
5710 tgl 41 ECB : else
42 : {
5710 tgl 43 GIC 1658 : node->nchild = 2;
5015 peter_e 44 CBC 1658 : node->child[1] = QT2QTN(in + in->qoperator.left, operand);
5710 tgl 45 1658 : node->sign |= node->child[1]->sign;
5710 tgl 46 ECB : }
47 : }
5710 tgl 48 GIC 2776 : else if (operand)
5710 tgl 49 ECB : {
5015 peter_e 50 GIC 2776 : node->word = operand + in->qoperand.distance;
4632 tgl 51 CBC 2776 : node->sign = ((uint32) 1) << (((unsigned int) in->qoperand.valcrc) % 32);
5710 tgl 52 ECB : }
53 :
5710 tgl 54 GIC 4455 : return node;
5710 tgl 55 ECB : }
56 :
57 : /*
58 : * Free a QTNode tree.
59 : *
60 : * Referenced "word" and "valnode" items are freed if marked as transient
61 : * by flags.
62 : */
63 : void
5624 bruce 64 GIC 4920 : QTNFree(QTNode *in)
5710 tgl 65 ECB : {
5710 tgl 66 GIC 4920 : if (!in)
5710 tgl 67 CBC 6 : return;
5710 tgl 68 ECB :
69 : /* since this function recurses, it could be driven to stack overflow. */
5693 teodor 70 GIC 4914 : check_stack_depth();
5693 teodor 71 ECB :
5693 teodor 72 GIC 4914 : if (in->valnode->type == QI_VAL && in->word && (in->flags & QTN_WORDFREE) != 0)
5710 tgl 73 CBC 306 : pfree(in->word);
5710 tgl 74 ECB :
2352 tgl 75 GIC 4914 : if (in->valnode->type == QI_OPR)
5710 tgl 76 ECB : {
77 : int i;
78 :
2352 tgl 79 GIC 5529 : for (i = 0; i < in->nchild; i++)
2352 tgl 80 CBC 3697 : QTNFree(in->child[i]);
5710 tgl 81 ECB : }
2352 tgl 82 GIC 4914 : if (in->child)
2352 tgl 83 CBC 1832 : pfree(in->child);
2352 tgl 84 ECB :
2352 tgl 85 GIC 4914 : if (in->flags & QTN_NEEDFREE)
2352 tgl 86 CBC 576 : pfree(in->valnode);
5710 tgl 87 ECB :
5710 tgl 88 GIC 4914 : pfree(in);
5710 tgl 89 ECB : }
90 :
91 : /*
92 : * Sort comparator for QTNodes.
93 : *
94 : * The sort order is somewhat arbitrary.
95 : */
96 : int
5624 bruce 97 GIC 2007 : QTNodeCompare(QTNode *an, QTNode *bn)
5710 tgl 98 ECB : {
99 : /* since this function recurses, it could be driven to stack overflow. */
5693 teodor 100 GIC 2007 : check_stack_depth();
5693 teodor 101 ECB :
5710 tgl 102 GIC 2007 : if (an->valnode->type != bn->valnode->type)
5710 tgl 103 CBC 591 : return (an->valnode->type > bn->valnode->type) ? -1 : 1;
5624 bruce 104 ECB :
5693 teodor 105 GIC 1416 : if (an->valnode->type == QI_OPR)
5710 tgl 106 ECB : {
5015 peter_e 107 GIC 277 : QueryOperator *ao = &an->valnode->qoperator;
5015 peter_e 108 CBC 277 : QueryOperator *bo = &bn->valnode->qoperator;
5693 teodor 109 ECB :
5624 bruce 110 GIC 277 : if (ao->oper != bo->oper)
5693 teodor 111 CBC 24 : return (ao->oper > bo->oper) ? -1 : 1;
5693 teodor 112 ECB :
5693 teodor 113 GIC 253 : if (an->nchild != bn->nchild)
5693 teodor 114 CBC 54 : return (an->nchild > bn->nchild) ? -1 : 1;
5693 teodor 115 ECB :
116 : {
117 : int i,
118 : res;
119 :
5693 teodor 120 GIC 339 : for (i = 0; i < an->nchild; i++)
5693 teodor 121 CBC 269 : if ((res = QTNodeCompare(an->child[i], bn->child[i])) != 0)
122 129 : return res;
5693 teodor 123 ECB : }
124 :
2558 teodor 125 GIC 70 : if (ao->oper == OP_PHRASE && ao->distance != bo->distance)
2558 teodor 126 CBC 3 : return (ao->distance > bo->distance) ? -1 : 1;
2558 teodor 127 ECB :
5693 teodor 128 GIC 67 : return 0;
5710 tgl 129 ECB : }
4632 tgl 130 GIC 1139 : else if (an->valnode->type == QI_VAL)
5710 tgl 131 ECB : {
5015 peter_e 132 GIC 1139 : QueryOperand *ao = &an->valnode->qoperand;
5015 peter_e 133 CBC 1139 : QueryOperand *bo = &bn->valnode->qoperand;
5710 tgl 134 ECB :
5693 teodor 135 GIC 1139 : if (ao->valcrc != bo->valcrc)
5693 teodor 136 ECB : {
5693 teodor 137 GIC 876 : return (ao->valcrc > bo->valcrc) ? -1 : 1;
5693 teodor 138 ECB : }
139 :
5050 bruce 140 GIC 263 : return tsCompareString(an->word, ao->length, bn->word, bo->length, false);
5693 teodor 141 ECB : }
142 : else
143 : {
4632 tgl 144 UIC 0 : elog(ERROR, "unrecognized QueryItem type: %d", an->valnode->type);
4632 tgl 145 EUB : return 0; /* keep compiler quiet */
146 : }
147 : }
148 :
149 : /*
150 : * qsort comparator for QTNode pointers.
151 : */
152 : static int
5710 tgl 153 GIC 1518 : cmpQTN(const void *a, const void *b)
5710 tgl 154 ECB : {
3955 bruce 155 GIC 1518 : return QTNodeCompare(*(QTNode *const *) a, *(QTNode *const *) b);
5710 tgl 156 ECB : }
157 :
158 : /*
159 : * Canonicalize a QTNode tree by sorting the children of AND/OR nodes
160 : * into an arbitrary but well-defined order.
161 : */
162 : void
5624 bruce 163 GIC 4542 : QTNSort(QTNode *in)
5710 tgl 164 ECB : {
165 : int i;
166 :
167 : /* since this function recurses, it could be driven to stack overflow. */
5693 teodor 168 GIC 4542 : check_stack_depth();
5693 teodor 169 ECB :
5693 teodor 170 GIC 4542 : if (in->valnode->type != QI_OPR)
5710 tgl 171 CBC 2958 : return;
5710 tgl 172 ECB :
5710 tgl 173 GIC 5199 : for (i = 0; i < in->nchild; i++)
5710 tgl 174 CBC 3615 : QTNSort(in->child[i]);
2558 teodor 175 1584 : if (in->nchild > 1 && in->valnode->qoperator.oper != OP_PHRASE)
61 peter 176 GNC 924 : qsort(in->child, in->nchild, sizeof(QTNode *), cmpQTN);
5710 tgl 177 ECB : }
178 :
179 : /*
180 : * Are two QTNode trees equal according to QTNodeCompare?
181 : */
182 : bool
5624 bruce 183 GIC 99 : QTNEq(QTNode *a, QTNode *b)
5710 tgl 184 ECB : {
5710 tgl 185 GIC 99 : uint32 sign = a->sign & b->sign;
5710 tgl 186 ECB :
5710 tgl 187 GIC 99 : if (!(sign == a->sign && sign == b->sign))
2352 tgl 188 CBC 3 : return false;
5710 tgl 189 ECB :
578 michael 190 GIC 96 : return (QTNodeCompare(a, b) == 0);
5710 tgl 191 ECB : }
192 :
193 : /*
194 : * Remove unnecessary intermediate nodes. For example:
195 : *
196 : * OR OR
197 : * a OR -> a b c
198 : * b c
199 : */
200 : void
5624 bruce 201 GIC 4374 : QTNTernary(QTNode *in)
5710 tgl 202 ECB : {
203 : int i;
204 :
205 : /* since this function recurses, it could be driven to stack overflow. */
5693 teodor 206 GIC 4374 : check_stack_depth();
5693 teodor 207 ECB :
5693 teodor 208 GIC 4374 : if (in->valnode->type != QI_OPR)
5710 tgl 209 CBC 2769 : return;
5710 tgl 210 ECB :
5710 tgl 211 GIC 5073 : for (i = 0; i < in->nchild; i++)
5710 tgl 212 CBC 3468 : QTNTernary(in->child[i]);
5710 tgl 213 ECB :
214 : /* Only AND and OR are associative, so don't flatten other node types */
2352 tgl 215 GIC 1605 : if (in->valnode->qoperator.oper != OP_AND &&
2352 tgl 216 CBC 1008 : in->valnode->qoperator.oper != OP_OR)
217 624 : return;
2352 tgl 218 ECB :
5710 tgl 219 GIC 3213 : for (i = 0; i < in->nchild; i++)
5710 tgl 220 ECB : {
5693 teodor 221 GIC 2232 : QTNode *cc = in->child[i];
5693 teodor 222 ECB :
2558 teodor 223 GIC 2232 : if (cc->valnode->type == QI_OPR &&
2352 tgl 224 CBC 777 : in->valnode->qoperator.oper == cc->valnode->qoperator.oper)
5710 tgl 225 ECB : {
5710 tgl 226 GIC 165 : int oldnchild = in->nchild;
5710 tgl 227 ECB :
5710 tgl 228 GIC 165 : in->nchild += cc->nchild - 1;
5710 tgl 229 CBC 165 : in->child = (QTNode **) repalloc(in->child, in->nchild * sizeof(QTNode *));
5710 tgl 230 ECB :
5710 tgl 231 GIC 165 : if (i + 1 != oldnchild)
5710 tgl 232 CBC 18 : memmove(in->child + i + cc->nchild, in->child + i + 1,
233 18 : (oldnchild - i - 1) * sizeof(QTNode *));
5710 tgl 234 ECB :
5710 tgl 235 GIC 165 : memcpy(in->child + i, cc->child, cc->nchild * sizeof(QTNode *));
5710 tgl 236 CBC 165 : i += cc->nchild - 1;
5710 tgl 237 ECB :
5624 bruce 238 GIC 165 : if (cc->flags & QTN_NEEDFREE)
5693 teodor 239 CBC 54 : pfree(cc->valnode);
5710 tgl 240 165 : pfree(cc);
5710 tgl 241 ECB : }
242 : }
243 : }
244 :
245 : /*
246 : * Convert a tree to binary tree by inserting intermediate nodes.
247 : * (Opposite of QTNTernary)
248 : */
249 : void
5624 bruce 250 GIC 591 : QTNBinary(QTNode *in)
5710 tgl 251 ECB : {
252 : int i;
253 :
254 : /* since this function recurses, it could be driven to stack overflow. */
5693 teodor 255 GIC 591 : check_stack_depth();
5693 teodor 256 ECB :
5693 teodor 257 GIC 591 : if (in->valnode->type != QI_OPR)
5710 tgl 258 CBC 363 : return;
5710 tgl 259 ECB :
5710 tgl 260 GIC 732 : for (i = 0; i < in->nchild; i++)
5710 tgl 261 CBC 504 : QTNBinary(in->child[i]);
5710 tgl 262 ECB :
5710 tgl 263 GIC 288 : while (in->nchild > 2)
5710 tgl 264 ECB : {
5710 tgl 265 GIC 60 : QTNode *nn = (QTNode *) palloc0(sizeof(QTNode));
5710 tgl 266 ECB :
5710 tgl 267 GIC 60 : nn->valnode = (QueryItem *) palloc0(sizeof(QueryItem));
5710 tgl 268 CBC 60 : nn->child = (QTNode **) palloc0(sizeof(QTNode *) * 2);
5710 tgl 269 ECB :
5710 tgl 270 GIC 60 : nn->nchild = 2;
5710 tgl 271 CBC 60 : nn->flags = QTN_NEEDFREE;
5710 tgl 272 ECB :
5710 tgl 273 GIC 60 : nn->child[0] = in->child[0];
5710 tgl 274 CBC 60 : nn->child[1] = in->child[1];
275 60 : nn->sign = nn->child[0]->sign | nn->child[1]->sign;
5710 tgl 276 ECB :
5710 tgl 277 GIC 60 : nn->valnode->type = in->valnode->type;
5015 peter_e 278 CBC 60 : nn->valnode->qoperator.oper = in->valnode->qoperator.oper;
5710 tgl 279 ECB :
5710 tgl 280 GIC 60 : in->child[0] = nn;
5710 tgl 281 CBC 60 : in->child[1] = in->child[in->nchild - 1];
282 60 : in->nchild--;
5710 tgl 283 ECB : }
284 : }
285 :
286 : /*
287 : * Count the total length of operand strings in tree (including '\0'-
288 : * terminators) and the total number of nodes.
289 : * Caller must initialize *sumlen and *nnode to zeroes.
290 : */
291 : static void
5624 bruce 292 GIC 993 : cntsize(QTNode *in, int *sumlen, int *nnode)
5710 tgl 293 ECB : {
294 : /* since this function recurses, it could be driven to stack overflow. */
5693 teodor 295 GIC 993 : check_stack_depth();
5693 teodor 296 ECB :
5710 tgl 297 GIC 993 : *nnode += 1;
5693 teodor 298 CBC 993 : if (in->valnode->type == QI_OPR)
5710 tgl 299 ECB : {
300 : int i;
301 :
5710 tgl 302 GIC 1281 : for (i = 0; i < in->nchild; i++)
5710 tgl 303 CBC 846 : cntsize(in->child[i], sumlen, nnode);
5710 tgl 304 ECB : }
305 : else
306 : {
5015 peter_e 307 GIC 558 : *sumlen += in->valnode->qoperand.length + 1;
5710 tgl 308 ECB : }
5710 tgl 309 GIC 993 : }
5710 tgl 310 ECB :
311 : typedef struct
312 : {
313 : QueryItem *curitem;
314 : char *operand;
315 : char *curoperand;
316 : } QTN2QTState;
317 :
318 : /*
319 : * Recursively convert a QTNode tree into flat tsquery format.
320 : * Caller must have allocated arrays of the correct size.
321 : */
322 : static void
5624 bruce 323 GIC 993 : fillQT(QTN2QTState *state, QTNode *in)
5710 tgl 324 ECB : {
325 : /* since this function recurses, it could be driven to stack overflow. */
5693 teodor 326 GIC 993 : check_stack_depth();
5693 teodor 327 ECB :
5693 teodor 328 GIC 993 : if (in->valnode->type == QI_VAL)
5710 tgl 329 ECB : {
5693 teodor 330 GIC 558 : memcpy(state->curitem, in->valnode, sizeof(QueryOperand));
5693 teodor 331 ECB :
5015 peter_e 332 GIC 558 : memcpy(state->curoperand, in->word, in->valnode->qoperand.length);
5015 peter_e 333 CBC 558 : state->curitem->qoperand.distance = state->curoperand - state->operand;
334 558 : state->curoperand[in->valnode->qoperand.length] = '\0';
335 558 : state->curoperand += in->valnode->qoperand.length + 1;
5710 tgl 336 558 : state->curitem++;
5710 tgl 337 ECB : }
338 : else
339 : {
5710 tgl 340 GIC 435 : QueryItem *curitem = state->curitem;
5710 tgl 341 ECB :
5693 teodor 342 GIC 435 : Assert(in->valnode->type == QI_OPR);
5693 teodor 343 ECB :
5693 teodor 344 GIC 435 : memcpy(state->curitem, in->valnode, sizeof(QueryOperator));
5693 teodor 345 ECB :
5710 tgl 346 GIC 435 : Assert(in->nchild <= 2);
5710 tgl 347 CBC 435 : state->curitem++;
5710 tgl 348 ECB :
5710 tgl 349 GIC 435 : fillQT(state, in->child[0]);
5710 tgl 350 ECB :
5710 tgl 351 GIC 435 : if (in->nchild == 2)
5710 tgl 352 ECB : {
5015 peter_e 353 GIC 411 : curitem->qoperator.left = state->curitem - curitem;
5710 tgl 354 CBC 411 : fillQT(state, in->child[1]);
5710 tgl 355 ECB : }
356 : }
5710 tgl 357 GIC 993 : }
5710 tgl 358 ECB :
359 : /*
360 : * Build flat tsquery from a QTNode tree.
361 : */
362 : TSQuery
5624 bruce 363 GIC 147 : QTN2QT(QTNode *in)
5710 tgl 364 ECB : {
365 : TSQuery out;
366 : int len;
5710 tgl 367 GIC 147 : int sumlen = 0,
5710 tgl 368 CBC 147 : nnode = 0;
5710 tgl 369 ECB : QTN2QTState state;
370 :
5710 tgl 371 GIC 147 : cntsize(in, &sumlen, &nnode);
3338 noah 372 ECB :
3338 noah 373 GIC 147 : if (TSQUERY_TOO_BIG(nnode, sumlen))
3338 noah 374 LBC 0 : ereport(ERROR,
3338 noah 375 EUB : (errcode(ERRCODE_PROGRAM_LIMIT_EXCEEDED),
376 : errmsg("tsquery is too large")));
5710 tgl 377 GIC 147 : len = COMPUTESIZE(nnode, sumlen);
5710 tgl 378 ECB :
4338 tgl 379 GIC 147 : out = (TSQuery) palloc0(len);
5710 tgl 380 CBC 147 : SET_VARSIZE(out, len);
381 147 : out->size = nnode;
5710 tgl 382 ECB :
5710 tgl 383 GIC 147 : state.curitem = GETQUERY(out);
5710 tgl 384 CBC 147 : state.operand = state.curoperand = GETOPERAND(out);
5710 tgl 385 ECB :
5710 tgl 386 GIC 147 : fillQT(&state, in);
5710 tgl 387 CBC 147 : return out;
5710 tgl 388 ECB : }
389 :
390 : /*
391 : * Copy a QTNode tree.
392 : *
393 : * Modifiable copies of the words and valnodes are made, too.
394 : */
395 : QTNode *
5624 bruce 396 GIC 510 : QTNCopy(QTNode *in)
5710 tgl 397 ECB : {
398 : QTNode *out;
399 :
400 : /* since this function recurses, it could be driven to stack overflow. */
5693 teodor 401 GIC 510 : check_stack_depth();
5693 teodor 402 ECB :
5693 teodor 403 GIC 510 : out = (QTNode *) palloc(sizeof(QTNode));
5710 tgl 404 ECB :
5710 tgl 405 GIC 510 : *out = *in;
5710 tgl 406 CBC 510 : out->valnode = (QueryItem *) palloc(sizeof(QueryItem));
407 510 : *(out->valnode) = *(in->valnode);
408 510 : out->flags |= QTN_NEEDFREE;
5710 tgl 409 ECB :
5693 teodor 410 GIC 510 : if (in->valnode->type == QI_VAL)
5710 tgl 411 ECB : {
5015 peter_e 412 GIC 306 : out->word = palloc(in->valnode->qoperand.length + 1);
5015 peter_e 413 CBC 306 : memcpy(out->word, in->word, in->valnode->qoperand.length);
414 306 : out->word[in->valnode->qoperand.length] = '\0';
5710 tgl 415 306 : out->flags |= QTN_WORDFREE;
5710 tgl 416 ECB : }
417 : else
418 : {
419 : int i;
420 :
5710 tgl 421 GIC 204 : out->child = (QTNode **) palloc(sizeof(QTNode *) * in->nchild);
5710 tgl 422 ECB :
5710 tgl 423 GIC 609 : for (i = 0; i < in->nchild; i++)
5710 tgl 424 CBC 405 : out->child[i] = QTNCopy(in->child[i]);
5710 tgl 425 ECB : }
426 :
5710 tgl 427 GIC 510 : return out;
5710 tgl 428 ECB : }
429 :
430 : /*
431 : * Clear the specified flag bit(s) in all nodes of a QTNode tree.
432 : */
433 : void
5624 bruce 434 GIC 2622 : QTNClearFlags(QTNode *in, uint32 flags)
5647 tgl 435 ECB : {
436 : /* since this function recurses, it could be driven to stack overflow. */
5647 tgl 437 GIC 2622 : check_stack_depth();
5647 tgl 438 ECB :
5647 tgl 439 GIC 2622 : in->flags &= ~flags;
5647 tgl 440 ECB :
5647 tgl 441 GIC 2622 : if (in->valnode->type != QI_VAL)
5647 tgl 442 ECB : {
443 : int i;
444 :
5647 tgl 445 GIC 3204 : for (i = 0; i < in->nchild; i++)
5647 tgl 446 CBC 2226 : QTNClearFlags(in->child[i], flags);
5647 tgl 447 ECB : }
5647 tgl 448 GIC 2622 : }
|
