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