Debian Codegraph @

src/backend/utils/adt/tsquery_util.c

raw
1 /*-------------------------------------------------------------------------
2 *
3 * tsquery_util.c
4 * Utilities for tsquery datatype
5 *
6 * Portions Copyright (c) 1996-2025, 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 *
25 QT2QTN(QueryItem *in, char *operand)
26 {
27 QTNode *node = (QTNode *) palloc0(sizeof(QTNode));
28
29 /* since this function recurses, it could be driven to stack overflow. */
30 check_stack_depth();
31
32 node->valnode = in;
33
34 if (in->type == QI_OPR)
35 {
36 node->child = (QTNode **) palloc0(sizeof(QTNode *) * 2);
37 node->child[0] = QT2QTN(in + 1, operand);
38 node->sign = node->child[0]->sign;
39 if (in->qoperator.oper == OP_NOT)
40 node->nchild = 1;
41 else
42 {
43 node->nchild = 2;
44 node->child[1] = QT2QTN(in + in->qoperator.left, operand);
45 node->sign |= node->child[1]->sign;
46 }
47 }
48 else if (operand)
49 {
50 node->word = operand + in->qoperand.distance;
51 node->sign = ((uint32) 1) << (((unsigned int) in->qoperand.valcrc) % 32);
52 }
53
54 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
64 QTNFree(QTNode *in)
65 {
66 if (!in)
67 return;
68
69 /* since this function recurses, it could be driven to stack overflow. */
70 check_stack_depth();
71
72 if (in->valnode->type == QI_VAL && in->word && (in->flags & QTN_WORDFREE) != 0)
73 pfree(in->word);
74
75 if (in->valnode->type == QI_OPR)
76 {
77 int i;
78
79 for (i = 0; i < in->nchild; i++)
80 QTNFree(in->child[i]);
81 }
82 if (in->child)
83 pfree(in->child);
84
85 if (in->flags & QTN_NEEDFREE)
86 pfree(in->valnode);
87
88 pfree(in);
89 }
90
91 /*
92 * Sort comparator for QTNodes.
93 *
94 * The sort order is somewhat arbitrary.
95 */
96 int
97 QTNodeCompare(QTNode *an, QTNode *bn)
98 {
99 /* since this function recurses, it could be driven to stack overflow. */
100 check_stack_depth();
101
102 if (an->valnode->type != bn->valnode->type)
103 return (an->valnode->type > bn->valnode->type) ? -1 : 1;
104
105 if (an->valnode->type == QI_OPR)
106 {
107 QueryOperator *ao = &an->valnode->qoperator;
108 QueryOperator *bo = &bn->valnode->qoperator;
109
110 if (ao->oper != bo->oper)
111 return (ao->oper > bo->oper) ? -1 : 1;
112
113 if (an->nchild != bn->nchild)
114 return (an->nchild > bn->nchild) ? -1 : 1;
115
116 {
117 int i,
118 res;
119
120 for (i = 0; i < an->nchild; i++)
121 if ((res = QTNodeCompare(an->child[i], bn->child[i])) != 0)
122 return res;
123 }
124
125 if (ao->oper == OP_PHRASE && ao->distance != bo->distance)
126 return (ao->distance > bo->distance) ? -1 : 1;
127
128 return 0;
129 }
130 else if (an->valnode->type == QI_VAL)
131 {
132 QueryOperand *ao = &an->valnode->qoperand;
133 QueryOperand *bo = &bn->valnode->qoperand;
134
135 if (ao->valcrc != bo->valcrc)
136 {
137 return (ao->valcrc > bo->valcrc) ? -1 : 1;
138 }
139
140 return tsCompareString(an->word, ao->length, bn->word, bo->length, false);
141 }
142 else
143 {
144 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
153 cmpQTN(const void *a, const void *b)
154 {
155 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
163 QTNSort(QTNode *in)
164 {
165 int i;
166
167 /* since this function recurses, it could be driven to stack overflow. */
168 check_stack_depth();
169
170 if (in->valnode->type != QI_OPR)
171 return;
172
173 for (i = 0; i < in->nchild; i++)
174 QTNSort(in->child[i]);
175 if (in->nchild > 1 && in->valnode->qoperator.oper != OP_PHRASE)
176 qsort(in->child, in->nchild, sizeof(QTNode *), cmpQTN);
177 }
178
179 /*
180 * Are two QTNode trees equal according to QTNodeCompare?
181 */
182 bool
183 QTNEq(QTNode *a, QTNode *b)
184 {
185 uint32 sign = a->sign & b->sign;
186
187 if (!(sign == a->sign && sign == b->sign))
188 return false;
189
190 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
201 QTNTernary(QTNode *in)
202 {
203 int i;
204
205 /* since this function recurses, it could be driven to stack overflow. */
206 check_stack_depth();
207
208 if (in->valnode->type != QI_OPR)
209 return;
210
211 for (i = 0; i < in->nchild; i++)
212 QTNTernary(in->child[i]);
213
214 /* Only AND and OR are associative, so don't flatten other node types */
215 if (in->valnode->qoperator.oper != OP_AND &&
216 in->valnode->qoperator.oper != OP_OR)
217 return;
218
219 for (i = 0; i < in->nchild; i++)
220 {
221 QTNode *cc = in->child[i];
222
223 if (cc->valnode->type == QI_OPR &&
224 in->valnode->qoperator.oper == cc->valnode->qoperator.oper)
225 {
226 int oldnchild = in->nchild;
227
228 in->nchild += cc->nchild - 1;
229 in->child = (QTNode **) repalloc(in->child, in->nchild * sizeof(QTNode *));
230
231 if (i + 1 != oldnchild)
232 memmove(in->child + i + cc->nchild, in->child + i + 1,
233 (oldnchild - i - 1) * sizeof(QTNode *));
234
235 memcpy(in->child + i, cc->child, cc->nchild * sizeof(QTNode *));
236 i += cc->nchild - 1;
237
238 if (cc->flags & QTN_NEEDFREE)
239 pfree(cc->valnode);
240 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
250 QTNBinary(QTNode *in)
251 {
252 int i;
253
254 /* since this function recurses, it could be driven to stack overflow. */
255 check_stack_depth();
256
257 if (in->valnode->type != QI_OPR)
258 return;
259
260 for (i = 0; i < in->nchild; i++)
261 QTNBinary(in->child[i]);
262
263 while (in->nchild > 2)
264 {
265 QTNode *nn = (QTNode *) palloc0(sizeof(QTNode));
266
267 nn->valnode = (QueryItem *) palloc0(sizeof(QueryItem));
268 nn->child = (QTNode **) palloc0(sizeof(QTNode *) * 2);
269
270 nn->nchild = 2;
271 nn->flags = QTN_NEEDFREE;
272
273 nn->child[0] = in->child[0];
274 nn->child[1] = in->child[1];
275 nn->sign = nn->child[0]->sign | nn->child[1]->sign;
276
277 nn->valnode->type = in->valnode->type;
278 nn->valnode->qoperator.oper = in->valnode->qoperator.oper;
279
280 in->child[0] = nn;
281 in->child[1] = in->child[in->nchild - 1];
282 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
292 cntsize(QTNode *in, size_t *sumlen, size_t *nnode)
293 {
294 /* since this function recurses, it could be driven to stack overflow. */
295 check_stack_depth();
296
297 *nnode += 1;
298 if (in->valnode->type == QI_OPR)
299 {
300 int i;
301
302 for (i = 0; i < in->nchild; i++)
303 cntsize(in->child[i], sumlen, nnode);
304 }
305 else
306 {
307 *sumlen += in->valnode->qoperand.length + 1;
308 }
309 }
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
323 fillQT(QTN2QTState *state, QTNode *in)
324 {
325 /* since this function recurses, it could be driven to stack overflow. */
326 check_stack_depth();
327
328 if (in->valnode->type == QI_VAL)
329 {
330 size_t distance;
331
332 memcpy(state->curitem, in->valnode, sizeof(QueryOperand));
333
334 memcpy(state->curoperand, in->word, in->valnode->qoperand.length);
335 distance = state->curoperand - state->operand;
336 if (distance > MAXSTRPOS)
337 ereport(ERROR,
338 (errcode(ERRCODE_PROGRAM_LIMIT_EXCEEDED),
339 errmsg("tsquery is too large")));
340 state->curitem->qoperand.distance = distance;
341 state->curoperand[in->valnode->qoperand.length] = '\0';
342 state->curoperand += in->valnode->qoperand.length + 1;
343 state->curitem++;
344 }
345 else
346 {
347 QueryItem *curitem = state->curitem;
348
349 Assert(in->valnode->type == QI_OPR);
350
351 memcpy(state->curitem, in->valnode, sizeof(QueryOperator));
352
353 Assert(in->nchild <= 2);
354 state->curitem++;
355
356 fillQT(state, in->child[0]);
357
358 if (in->nchild == 2)
359 {
360 curitem->qoperator.left = state->curitem - curitem;
361 fillQT(state, in->child[1]);
362 }
363 }
364 }
365
366 /*
367 * Build flat tsquery from a QTNode tree.
368 */
369 TSQuery
370 QTN2QT(QTNode *in)
371 {
372 TSQuery out;
373 int len;
374 size_t sumlen = 0,
375 nnode = 0;
376 QTN2QTState state;
377
378 cntsize(in, &sumlen, &nnode);
379
380 if (TSQUERY_TOO_BIG(nnode, sumlen))
381 ereport(ERROR,
382 (errcode(ERRCODE_PROGRAM_LIMIT_EXCEEDED),
383 errmsg("tsquery is too large")));
384 len = COMPUTESIZE(nnode, sumlen);
385
386 out = (TSQuery) palloc0(len);
387 SET_VARSIZE(out, len);
388 out->size = nnode;
389
390 state.curitem = GETQUERY(out);
391 state.operand = state.curoperand = GETOPERAND(out);
392
393 fillQT(&state, in);
394 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 *
403 QTNCopy(QTNode *in)
404 {
405 QTNode *out;
406
407 /* since this function recurses, it could be driven to stack overflow. */
408 check_stack_depth();
409
410 out = (QTNode *) palloc(sizeof(QTNode));
411
412 *out = *in;
413 out->valnode = (QueryItem *) palloc(sizeof(QueryItem));
414 *(out->valnode) = *(in->valnode);
415 out->flags |= QTN_NEEDFREE;
416
417 if (in->valnode->type == QI_VAL)
418 {
419 out->word = palloc(in->valnode->qoperand.length + 1);
420 memcpy(out->word, in->word, in->valnode->qoperand.length);
421 out->word[in->valnode->qoperand.length] = '\0';
422 out->flags |= QTN_WORDFREE;
423 }
424 else
425 {
426 int i;
427
428 out->child = (QTNode **) palloc(sizeof(QTNode *) * in->nchild);
429
430 for (i = 0; i < in->nchild; i++)
431 out->child[i] = QTNCopy(in->child[i]);
432 }
433
434 return out;
435 }
436
437 /*
438 * Clear the specified flag bit(s) in all nodes of a QTNode tree.
439 */
440 void
441 QTNClearFlags(QTNode *in, uint32 flags)
442 {
443 /* since this function recurses, it could be driven to stack overflow. */
444 check_stack_depth();
445
446 in->flags &= ~flags;
447
448 if (in->valnode->type != QI_VAL)
449 {
450 int i;
451
452 for (i = 0; i < in->nchild; i++)
453 QTNClearFlags(in->child[i], flags);
454 }
455 }