Age Owner Branch data TLA Line data Source code
1 : : /*-------------------------------------------------------------------------
2 : : *
3 : : * tsquery_util.c
4 : : * Utilities for tsquery datatype
5 : : *
6 : : * Portions Copyright (c) 1996-2026, 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 *
6860 bruce@momjian.us 25 :CBC 6048 : QT2QTN(QueryItem *in, char *operand)
26 : : {
260 michael@paquier.xyz 27 : 6048 : QTNode *node = palloc0_object(QTNode);
28 : :
29 : : /* since this function recurses, it could be driven to stack overflow. */
6929 teodor@sigaev.ru 30 : 6048 : check_stack_depth();
31 : :
6946 tgl@sss.pgh.pa.us 32 : 6048 : node->valnode = in;
33 : :
6929 teodor@sigaev.ru 34 [ + + ]: 6048 : if (in->type == QI_OPR)
35 : : {
260 michael@paquier.xyz 36 : 2275 : node->child = palloc0_array(QTNode *, 2);
6946 tgl@sss.pgh.pa.us 37 : 2275 : node->child[0] = QT2QTN(in + 1, operand);
38 : 2275 : node->sign = node->child[0]->sign;
6251 peter_e@gmx.net 39 [ + + ]: 2275 : if (in->qoperator.oper == OP_NOT)
6946 tgl@sss.pgh.pa.us 40 : 34 : node->nchild = 1;
41 : : else
42 : : {
43 : 2241 : node->nchild = 2;
6251 peter_e@gmx.net 44 : 2241 : node->child[1] = QT2QTN(in + in->qoperator.left, operand);
6946 tgl@sss.pgh.pa.us 45 : 2241 : node->sign |= node->child[1]->sign;
46 : : }
47 : : }
48 [ + - ]: 3773 : else if (operand)
49 : : {
6251 peter_e@gmx.net 50 : 3773 : node->word = operand + in->qoperand.distance;
5868 tgl@sss.pgh.pa.us 51 : 3773 : node->sign = ((uint32) 1) << (((unsigned int) in->qoperand.valcrc) % 32);
52 : : }
53 : :
6946 54 : 6048 : return node;
55 : : }
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
6860 bruce@momjian.us 64 : 6719 : QTNFree(QTNode *in)
65 : : {
6946 tgl@sss.pgh.pa.us 66 [ + + ]: 6719 : if (!in)
67 : 8 : return;
68 : :
69 : : /* since this function recurses, it could be driven to stack overflow. */
6929 teodor@sigaev.ru 70 : 6711 : check_stack_depth();
71 : :
72 [ + + + - : 6711 : if (in->valnode->type == QI_VAL && in->word && (in->flags & QTN_WORDFREE) != 0)
+ + ]
6946 tgl@sss.pgh.pa.us 73 : 428 : pfree(in->word);
74 : :
3588 75 [ + + ]: 6711 : if (in->valnode->type == QI_OPR)
76 : : {
77 : : int i;
78 : :
79 [ + + ]: 7565 : for (i = 0; i < in->nchild; i++)
80 : 5055 : QTNFree(in->child[i]);
81 : : }
82 [ + + ]: 6711 : if (in->child)
83 : 2510 : pfree(in->child);
84 : :
85 [ + + ]: 6711 : if (in->flags & QTN_NEEDFREE)
86 : 822 : pfree(in->valnode);
87 : :
6946 88 : 6711 : pfree(in);
89 : : }
90 : :
91 : : /*
92 : : * Sort comparator for QTNodes.
93 : : *
94 : : * The sort order is somewhat arbitrary.
95 : : */
96 : : int
6860 bruce@momjian.us 97 : 2684 : QTNodeCompare(QTNode *an, QTNode *bn)
98 : : {
99 : : /* since this function recurses, it could be driven to stack overflow. */
6929 teodor@sigaev.ru 100 : 2684 : check_stack_depth();
101 : :
6946 tgl@sss.pgh.pa.us 102 [ + + ]: 2684 : if (an->valnode->type != bn->valnode->type)
103 [ + + ]: 795 : return (an->valnode->type > bn->valnode->type) ? -1 : 1;
104 : :
6929 teodor@sigaev.ru 105 [ + + ]: 1889 : if (an->valnode->type == QI_OPR)
106 : : {
6251 peter_e@gmx.net 107 : 363 : QueryOperator *ao = &an->valnode->qoperator;
108 : 363 : QueryOperator *bo = &bn->valnode->qoperator;
109 : :
6860 bruce@momjian.us 110 [ + + ]: 363 : if (ao->oper != bo->oper)
6929 teodor@sigaev.ru 111 [ + + ]: 34 : return (ao->oper > bo->oper) ? -1 : 1;
112 : :
113 [ + + ]: 329 : if (an->nchild != bn->nchild)
114 [ + - ]: 72 : return (an->nchild > bn->nchild) ? -1 : 1;
115 : :
116 : : {
117 : : int i,
118 : : res;
119 : :
120 [ + + ]: 427 : for (i = 0; i < an->nchild; i++)
121 [ + + ]: 342 : if ((res = QTNodeCompare(an->child[i], bn->child[i])) != 0)
122 : 172 : return res;
123 : : }
124 : :
3794 125 [ + + + + ]: 85 : if (ao->oper == OP_PHRASE && ao->distance != bo->distance)
126 [ + - ]: 4 : return (ao->distance > bo->distance) ? -1 : 1;
127 : :
6929 128 : 81 : return 0;
129 : : }
5868 tgl@sss.pgh.pa.us 130 [ + - ]: 1526 : else if (an->valnode->type == QI_VAL)
131 : : {
6251 peter_e@gmx.net 132 : 1526 : QueryOperand *ao = &an->valnode->qoperand;
133 : 1526 : QueryOperand *bo = &bn->valnode->qoperand;
134 : :
6929 teodor@sigaev.ru 135 [ + + ]: 1526 : if (ao->valcrc != bo->valcrc)
136 : : {
137 [ + + ]: 1182 : return (ao->valcrc > bo->valcrc) ? -1 : 1;
138 : : }
139 : :
6286 bruce@momjian.us 140 : 344 : return tsCompareString(an->word, ao->length, bn->word, bo->length, false);
141 : : }
142 : : else
143 : : {
5868 tgl@sss.pgh.pa.us 144 [ # # ]:UBC 0 : elog(ERROR, "unrecognized QueryItem type: %d", an->valnode->type);
145 : : return 0; /* keep compiler quiet */
146 : : }
147 : : }
148 : :
149 : : /*
150 : : * qsort comparator for QTNode pointers.
151 : : */
152 : : static int
6946 tgl@sss.pgh.pa.us 153 :CBC 2044 : cmpQTN(const void *a, const void *b)
154 : : {
5191 bruce@momjian.us 155 : 2044 : return QTNodeCompare(*(QTNode *const *) a, *(QTNode *const *) b);
156 : : }
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
6860 163 : 6103 : QTNSort(QTNode *in)
164 : : {
165 : : int i;
166 : :
167 : : /* since this function recurses, it could be driven to stack overflow. */
6929 teodor@sigaev.ru 168 : 6103 : check_stack_depth();
169 : :
170 [ + + ]: 6103 : if (in->valnode->type != QI_OPR)
6946 tgl@sss.pgh.pa.us 171 : 3975 : return;
172 : :
173 [ + + ]: 6982 : for (i = 0; i < in->nchild; i++)
174 : 4854 : QTNSort(in->child[i]);
3794 teodor@sigaev.ru 175 [ + + + + ]: 2128 : if (in->nchild > 1 && in->valnode->qoperator.oper != OP_PHRASE)
1297 peter@eisentraut.org 176 : 1242 : qsort(in->child, in->nchild, sizeof(QTNode *), cmpQTN);
177 : : }
178 : :
179 : : /*
180 : : * Are two QTNode trees equal according to QTNodeCompare?
181 : : */
182 : : bool
6860 bruce@momjian.us 183 : 140 : QTNEq(QTNode *a, QTNode *b)
184 : : {
6946 tgl@sss.pgh.pa.us 185 : 140 : uint32 sign = a->sign & b->sign;
186 : :
187 [ + + - + ]: 140 : if (!(sign == a->sign && sign == b->sign))
3588 188 : 4 : return false;
189 : :
1814 michael@paquier.xyz 190 : 136 : return (QTNodeCompare(a, b) == 0);
191 : : }
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
6860 bruce@momjian.us 201 : 5867 : QTNTernary(QTNode *in)
202 : : {
203 : : int i;
204 : :
205 : : /* since this function recurses, it could be driven to stack overflow. */
6929 teodor@sigaev.ru 206 : 5867 : check_stack_depth();
207 : :
208 [ + + ]: 5867 : if (in->valnode->type != QI_OPR)
6946 tgl@sss.pgh.pa.us 209 : 3714 : return;
210 : :
211 [ + + ]: 6800 : for (i = 0; i < in->nchild; i++)
212 : 4647 : QTNTernary(in->child[i]);
213 : :
214 : : /* Only AND and OR are associative, so don't flatten other node types */
3588 215 [ + + ]: 2153 : if (in->valnode->qoperator.oper != OP_AND &&
216 [ + + ]: 1350 : in->valnode->qoperator.oper != OP_OR)
217 : 838 : return;
218 : :
6946 219 [ + + ]: 4305 : for (i = 0; i < in->nchild; i++)
220 : : {
6929 teodor@sigaev.ru 221 : 2990 : QTNode *cc = in->child[i];
222 : :
3794 223 [ + + ]: 2990 : if (cc->valnode->type == QI_OPR &&
3588 tgl@sss.pgh.pa.us 224 [ + + ]: 1041 : in->valnode->qoperator.oper == cc->valnode->qoperator.oper)
225 : : {
6946 226 : 223 : int oldnchild = in->nchild;
227 : :
228 : 223 : in->nchild += cc->nchild - 1;
260 michael@paquier.xyz 229 : 223 : in->child = repalloc_array(in->child, QTNode *, in->nchild);
230 : :
6946 tgl@sss.pgh.pa.us 231 [ + + ]: 223 : if (i + 1 != oldnchild)
232 : 24 : memmove(in->child + i + cc->nchild, in->child + i + 1,
233 : 24 : (oldnchild - i - 1) * sizeof(QTNode *));
234 : :
235 : 223 : memcpy(in->child + i, cc->child, cc->nchild * sizeof(QTNode *));
236 : 223 : i += cc->nchild - 1;
237 : :
6860 bruce@momjian.us 238 [ + + ]: 223 : if (cc->flags & QTN_NEEDFREE)
6929 teodor@sigaev.ru 239 : 72 : pfree(cc->valnode);
6946 tgl@sss.pgh.pa.us 240 : 223 : pfree(cc);
241 : : }
242 : : }
243 : : }
244 : :
245 : : /*
246 : : * Convert a tree to binary tree by inserting intermediate nodes.
247 : : * (Opposite of QTNTernary)
248 : : */
249 : : void
6860 bruce@momjian.us 250 : 834 : QTNBinary(QTNode *in)
251 : : {
252 : : int i;
253 : :
254 : : /* since this function recurses, it could be driven to stack overflow. */
6929 teodor@sigaev.ru 255 : 834 : check_stack_depth();
256 : :
257 [ + + ]: 834 : if (in->valnode->type != QI_OPR)
6946 tgl@sss.pgh.pa.us 258 : 509 : return;
259 : :
260 [ + + ]: 1037 : for (i = 0; i < in->nchild; i++)
261 : 712 : QTNBinary(in->child[i]);
262 : :
263 [ + + ]: 407 : while (in->nchild > 2)
264 : : {
260 michael@paquier.xyz 265 : 82 : QTNode *nn = palloc0_object(QTNode);
266 : :
267 : 82 : nn->valnode = palloc0_object(QueryItem);
268 : 82 : nn->child = palloc0_array(QTNode *, 2);
269 : :
6946 tgl@sss.pgh.pa.us 270 : 82 : nn->nchild = 2;
271 : 82 : nn->flags = QTN_NEEDFREE;
272 : :
273 : 82 : nn->child[0] = in->child[0];
274 : 82 : nn->child[1] = in->child[1];
275 : 82 : nn->sign = nn->child[0]->sign | nn->child[1]->sign;
276 : :
277 : 82 : nn->valnode->type = in->valnode->type;
6251 peter_e@gmx.net 278 : 82 : nn->valnode->qoperator.oper = in->valnode->qoperator.oper;
279 : :
6946 tgl@sss.pgh.pa.us 280 : 82 : in->child[0] = nn;
281 : 82 : in->child[1] = in->child[in->nchild - 1];
282 : 82 : in->nchild--;
283 : : }
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
17 292 : 1486 : cntsize(QTNode *in, size_t *sumlen, size_t *nnode)
293 : : {
294 : : /* since this function recurses, it could be driven to stack overflow. */
6929 teodor@sigaev.ru 295 : 1486 : check_stack_depth();
296 : :
6946 tgl@sss.pgh.pa.us 297 : 1486 : *nnode += 1;
6929 teodor@sigaev.ru 298 [ + + ]: 1486 : if (in->valnode->type == QI_OPR)
299 : : {
300 : : int i;
301 : :
6946 tgl@sss.pgh.pa.us 302 [ + + ]: 1916 : for (i = 0; i < in->nchild; i++)
303 : 1264 : cntsize(in->child[i], sumlen, nnode);
304 : : }
305 : : else
306 : : {
6251 peter_e@gmx.net 307 : 834 : *sumlen += in->valnode->qoperand.length + 1;
308 : : }
6946 tgl@sss.pgh.pa.us 309 : 1486 : }
310 : :
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
6860 bruce@momjian.us 323 : 1486 : fillQT(QTN2QTState *state, QTNode *in)
324 : : {
325 : : /* since this function recurses, it could be driven to stack overflow. */
6929 teodor@sigaev.ru 326 : 1486 : check_stack_depth();
327 : :
328 [ + + ]: 1486 : if (in->valnode->type == QI_VAL)
329 : : {
330 : : size_t distance;
331 : :
332 : 834 : memcpy(state->curitem, in->valnode, sizeof(QueryOperand));
333 : :
6251 peter_e@gmx.net 334 : 834 : memcpy(state->curoperand, in->word, in->valnode->qoperand.length);
17 tgl@sss.pgh.pa.us 335 : 834 : distance = state->curoperand - state->operand;
336 [ - + ]: 834 : if (distance > MAXSTRPOS)
17 tgl@sss.pgh.pa.us 337 [ # # ]:UBC 0 : ereport(ERROR,
338 : : (errcode(ERRCODE_PROGRAM_LIMIT_EXCEEDED),
339 : : errmsg("tsquery is too large")));
17 tgl@sss.pgh.pa.us 340 :CBC 834 : state->curitem->qoperand.distance = distance;
6251 peter_e@gmx.net 341 : 834 : state->curoperand[in->valnode->qoperand.length] = '\0';
342 : 834 : state->curoperand += in->valnode->qoperand.length + 1;
6946 tgl@sss.pgh.pa.us 343 : 834 : state->curitem++;
344 : : }
345 : : else
346 : : {
347 : 652 : QueryItem *curitem = state->curitem;
348 : :
6929 teodor@sigaev.ru 349 [ - + ]: 652 : Assert(in->valnode->type == QI_OPR);
350 : :
351 : 652 : memcpy(state->curitem, in->valnode, sizeof(QueryOperator));
352 : :
6946 tgl@sss.pgh.pa.us 353 [ - + ]: 652 : Assert(in->nchild <= 2);
354 : 652 : state->curitem++;
355 : :
356 : 652 : fillQT(state, in->child[0]);
357 : :
358 [ + + ]: 652 : if (in->nchild == 2)
359 : : {
6251 peter_e@gmx.net 360 : 612 : curitem->qoperator.left = state->curitem - curitem;
6946 tgl@sss.pgh.pa.us 361 : 612 : fillQT(state, in->child[1]);
362 : : }
363 : : }
364 : 1486 : }
365 : :
366 : : /*
367 : : * Build flat tsquery from a QTNode tree.
368 : : */
369 : : TSQuery
6860 bruce@momjian.us 370 : 222 : QTN2QT(QTNode *in)
371 : : {
372 : : TSQuery out;
373 : : int len;
17 tgl@sss.pgh.pa.us 374 : 222 : size_t sumlen = 0,
6946 375 : 222 : nnode = 0;
376 : : QTN2QTState state;
377 : :
378 : 222 : cntsize(in, &sumlen, &nnode);
379 : :
4574 noah@leadboat.com 380 [ + - - + ]: 222 : if (TSQUERY_TOO_BIG(nnode, sumlen))
4574 noah@leadboat.com 381 [ # # ]:UBC 0 : ereport(ERROR,
382 : : (errcode(ERRCODE_PROGRAM_LIMIT_EXCEEDED),
383 : : errmsg("tsquery is too large")));
6946 tgl@sss.pgh.pa.us 384 :CBC 222 : len = COMPUTESIZE(nnode, sumlen);
385 : :
5574 386 : 222 : out = (TSQuery) palloc0(len);
6946 387 : 222 : SET_VARSIZE(out, len);
388 : 222 : out->size = nnode;
389 : :
390 : 222 : state.curitem = GETQUERY(out);
391 : 222 : state.operand = state.curoperand = GETOPERAND(out);
392 : :
393 : 222 : fillQT(&state, in);
394 : 222 : return out;
395 : : }
396 : :
397 : : /*
398 : : * Copy a QTNode tree.
399 : : *
400 : : * Modifiable copies of the words and valnodes are made, too.
401 : : */
402 : : QTNode *
6860 bruce@momjian.us 403 : 712 : QTNCopy(QTNode *in)
404 : : {
405 : : QTNode *out;
406 : :
407 : : /* since this function recurses, it could be driven to stack overflow. */
6929 teodor@sigaev.ru 408 : 712 : check_stack_depth();
409 : :
260 michael@paquier.xyz 410 : 712 : out = palloc_object(QTNode);
411 : :
6946 tgl@sss.pgh.pa.us 412 : 712 : *out = *in;
260 michael@paquier.xyz 413 : 712 : out->valnode = palloc_object(QueryItem);
6946 tgl@sss.pgh.pa.us 414 : 712 : *(out->valnode) = *(in->valnode);
415 : 712 : out->flags |= QTN_NEEDFREE;
416 : :
6929 teodor@sigaev.ru 417 [ + + ]: 712 : if (in->valnode->type == QI_VAL)
418 : : {
6251 peter_e@gmx.net 419 : 428 : out->word = palloc(in->valnode->qoperand.length + 1);
420 : 428 : memcpy(out->word, in->word, in->valnode->qoperand.length);
421 : 428 : out->word[in->valnode->qoperand.length] = '\0';
6946 tgl@sss.pgh.pa.us 422 : 428 : out->flags |= QTN_WORDFREE;
423 : : }
424 : : else
425 : : {
426 : : int i;
427 : :
260 michael@paquier.xyz 428 : 284 : out->child = palloc_array(QTNode *, in->nchild);
429 : :
6946 tgl@sss.pgh.pa.us 430 [ + + ]: 847 : for (i = 0; i < in->nchild; i++)
431 : 563 : out->child[i] = QTNCopy(in->child[i]);
432 : : }
433 : :
434 : 712 : return out;
435 : : }
436 : :
437 : : /*
438 : : * Clear the specified flag bit(s) in all nodes of a QTNode tree.
439 : : */
440 : : void
6860 bruce@momjian.us 441 : 3496 : QTNClearFlags(QTNode *in, uint32 flags)
442 : : {
443 : : /* since this function recurses, it could be driven to stack overflow. */
6883 tgl@sss.pgh.pa.us 444 : 3496 : check_stack_depth();
445 : :
446 : 3496 : in->flags &= ~flags;
447 : :
448 [ + + ]: 3496 : if (in->valnode->type != QI_VAL)
449 : : {
450 : : int i;
451 : :
452 [ + + ]: 4272 : for (i = 0; i < in->nchild; i++)
453 : 2968 : QTNClearFlags(in->child[i], flags);
454 : : }
455 : 3496 : }
|
