Age Owner TLA Line data Source code
1 : /*-------------------------------------------------------------------------
2 : *
3 : * tsquery_rewrite.c
4 : * Utilities for reconstructing tsquery
5 : *
6 : * Portions Copyright (c) 1996-2023, PostgreSQL Global Development Group
7 : *
8 : *
9 : * IDENTIFICATION
10 : * src/backend/utils/adt/tsquery_rewrite.c
11 : *
12 : *-------------------------------------------------------------------------
13 : */
14 :
15 : #include "postgres.h"
16 :
17 : #include "catalog/pg_type.h"
18 : #include "executor/spi.h"
19 : #include "miscadmin.h"
20 : #include "tsearch/ts_utils.h"
21 : #include "utils/builtins.h"
22 :
23 :
24 : /*
25 : * If "node" is equal to "ex", return a copy of "subs" instead.
26 : * If "ex" matches a subset of node's children, return a modified version
27 : * of "node" in which those children are replaced with a copy of "subs".
28 : * Otherwise return "node" unmodified.
29 : *
30 : * The QTN_NOCHANGE bit is set in successfully modified nodes, so that
31 : * we won't uselessly recurse into them.
32 : * Also, set *isfind true if we make a replacement.
33 : */
34 : static QTNode *
5624 bruce 35 CBC 2376 : findeq(QTNode *node, QTNode *ex, QTNode *subs, bool *isfind)
36 : {
37 : /* Can't match unless signature matches and node type matches. */
38 2376 : if ((node->sign & ex->sign) != ex->sign ||
5693 teodor 39 213 : node->valnode->type != ex->valnode->type)
5710 tgl 40 2214 : return node;
41 :
42 : /* Ignore nodes marked NOCHANGE, too. */
43 162 : if (node->flags & QTN_NOCHANGE)
44 21 : return node;
45 :
5693 teodor 46 141 : if (node->valnode->type == QI_OPR)
47 : {
48 : /* Must be same operator. */
5015 peter_e 49 72 : if (node->valnode->qoperator.oper != ex->valnode->qoperator.oper)
5693 teodor 50 21 : return node;
51 :
5710 tgl 52 51 : if (node->nchild == ex->nchild)
53 : {
54 : /*
55 : * Simple case: when same number of children, match if equal.
56 : * (This is reliable when the children were sorted earlier.)
57 : */
58 30 : if (QTNEq(node, ex))
59 : {
60 : /* Match; delete node and return a copy of subs instead. */
61 24 : QTNFree(node);
62 24 : if (subs)
63 : {
64 24 : node = QTNCopy(subs);
65 24 : node->flags |= QTN_NOCHANGE;
66 : }
67 : else
5710 tgl 68 UBC 0 : node = NULL;
5710 tgl 69 CBC 24 : *isfind = true;
70 : }
71 : }
2352 72 21 : else if (node->nchild > ex->nchild && ex->nchild > 0)
73 : {
74 : /*
75 : * AND and OR are commutative/associative, so we should check if a
76 : * subset of the children match. For example, if node is A|B|C,
77 : * and ex is B|C, we have a match after we notionally convert node
78 : * to A|(B|C). This does not work for NOT or PHRASE nodes, but we
79 : * can't get here for those node types because they have a fixed
80 : * number of children.
81 : *
82 : * Because we expect that the children are sorted, it suffices to
83 : * make one pass through the two lists to find the matches.
84 : */
85 : bool *matched;
86 : int nmatched;
87 : int i,
88 : j;
89 :
90 : /* Assert that the subset rule is OK */
91 21 : Assert(node->valnode->qoperator.oper == OP_AND ||
92 : node->valnode->qoperator.oper == OP_OR);
93 :
94 : /* matched[] will record which children of node matched */
95 21 : matched = (bool *) palloc0(node->nchild * sizeof(bool));
96 21 : nmatched = 0;
97 21 : i = j = 0;
98 105 : while (i < node->nchild && j < ex->nchild)
99 : {
100 84 : int cmp = QTNodeCompare(node->child[i], ex->child[j]);
101 :
102 84 : if (cmp == 0)
103 : {
104 : /* match! */
105 60 : matched[i] = true;
106 60 : nmatched++;
107 60 : i++, j++;
108 : }
109 24 : else if (cmp < 0)
110 : {
111 : /* node->child[i] has no match, ignore it */
112 24 : i++;
113 : }
114 : else
115 : {
116 : /* ex->child[j] has no match; we can give up immediately */
2352 tgl 117 UBC 0 : break;
118 : }
119 : }
120 :
2352 tgl 121 CBC 21 : if (nmatched == ex->nchild)
122 : {
123 : /* collapse out the matched children of node */
124 21 : j = 0;
125 108 : for (i = 0; i < node->nchild; i++)
126 : {
127 87 : if (matched[i])
128 60 : QTNFree(node->child[i]);
129 : else
130 27 : node->child[j++] = node->child[i];
131 : }
132 :
133 : /* and instead insert a copy of subs */
134 21 : if (subs)
135 : {
136 21 : subs = QTNCopy(subs);
137 21 : subs->flags |= QTN_NOCHANGE;
138 21 : node->child[j++] = subs;
139 : }
140 :
141 21 : node->nchild = j;
142 :
143 : /*
144 : * At this point we might have a node with zero or one child,
145 : * which should be simplified. But we leave it to our caller
146 : * (dofindsubquery) to take care of that.
147 : */
148 :
149 : /*
150 : * Re-sort the node to put new child in the right place. This
151 : * is a bit bogus, because it won't matter for findsubquery's
152 : * remaining processing, and it's insufficient to prepare the
153 : * tree for another search (we would need to re-flatten as
154 : * well, and we don't want to do that because we'd lose the
155 : * QTN_NOCHANGE marking on the new child). But it's needed to
156 : * keep the results the same as the regression tests expect.
157 : */
158 21 : QTNSort(node);
159 :
160 21 : *isfind = true;
161 : }
162 :
163 21 : pfree(matched);
164 : }
165 : }
166 : else
167 : {
5693 teodor 168 69 : Assert(node->valnode->type == QI_VAL);
169 :
5015 peter_e 170 69 : if (node->valnode->qoperand.valcrc != ex->valnode->qoperand.valcrc)
5693 teodor 171 UBC 0 : return node;
5693 teodor 172 CBC 69 : else if (QTNEq(node, ex))
173 : {
174 69 : QTNFree(node);
175 69 : if (subs)
176 : {
177 60 : node = QTNCopy(subs);
178 60 : node->flags |= QTN_NOCHANGE;
179 : }
180 : else
181 : {
182 9 : node = NULL;
183 : }
184 69 : *isfind = true;
185 : }
186 : }
187 :
5710 tgl 188 120 : return node;
189 : }
190 :
191 : /*
192 : * Recursive guts of findsubquery(): attempt to replace "ex" with "subs"
193 : * at the root node, and if we failed to do so, recursively match against
194 : * child nodes.
195 : *
196 : * Delete any void subtrees resulting from the replacement.
197 : * In the following example '5' is replaced by empty operand:
198 : *
199 : * AND -> 6
200 : * / \
201 : * 5 OR
202 : * / \
203 : * 6 5
204 : */
205 : static QTNode *
5624 bruce 206 2376 : dofindsubquery(QTNode *root, QTNode *ex, QTNode *subs, bool *isfind)
207 : {
208 : /* since this function recurses, it could be driven to stack overflow. */
5693 teodor 209 2376 : check_stack_depth();
210 :
211 : /* also, since it's a bit expensive, let's check for query cancel. */
2352 tgl 212 2376 : CHECK_FOR_INTERRUPTS();
213 :
214 : /* match at the node itself */
5710 215 2376 : root = findeq(root, ex, subs, isfind);
216 :
217 : /* unless we matched here, consider matches at child nodes */
2310 218 2376 : if (root && (root->flags & QTN_NOCHANGE) == 0 &&
219 2262 : root->valnode->type == QI_OPR)
220 : {
221 : int i,
5710 222 846 : j = 0;
223 :
224 : /*
225 : * Any subtrees that are replaced by NULL must be dropped from the
226 : * tree.
227 : */
228 2802 : for (i = 0; i < root->nchild; i++)
229 : {
2310 230 1956 : root->child[j] = dofindsubquery(root->child[i], ex, subs, isfind);
231 1956 : if (root->child[j])
5710 232 1947 : j++;
233 : }
234 :
235 846 : root->nchild = j;
236 :
237 : /*
238 : * If we have just zero or one remaining child node, simplify out this
239 : * operator node.
240 : */
5003 teodor 241 846 : if (root->nchild == 0)
242 : {
5710 tgl 243 3 : QTNFree(root);
244 3 : root = NULL;
245 : }
5003 teodor 246 843 : else if (root->nchild == 1 && root->valnode->qoperator.oper != OP_NOT)
247 : {
5710 tgl 248 6 : QTNode *nroot = root->child[0];
249 :
250 6 : pfree(root);
251 6 : root = nroot;
252 : }
253 : }
254 :
255 2376 : return root;
256 : }
257 :
258 : /*
259 : * Substitute "subs" for "ex" throughout the QTNode tree at root.
260 : *
261 : * If isfind isn't NULL, set *isfind to show whether we made any substitution.
262 : *
263 : * Both "root" and "ex" must have been through QTNTernary and QTNSort
264 : * to ensure reliable matching.
265 : */
266 : QTNode *
5624 bruce 267 420 : findsubquery(QTNode *root, QTNode *ex, QTNode *subs, bool *isfind)
268 : {
5710 tgl 269 420 : bool DidFind = false;
270 :
271 420 : root = dofindsubquery(root, ex, subs, &DidFind);
272 :
273 420 : if (isfind)
5710 tgl 274 UBC 0 : *isfind = DidFind;
275 :
5710 tgl 276 CBC 420 : return root;
277 : }
278 :
279 : Datum
5646 280 66 : tsquery_rewrite_query(PG_FUNCTION_ARGS)
281 : {
5710 282 66 : TSQuery query = PG_GETARG_TSQUERY_COPY(0);
2219 noah 283 66 : text *in = PG_GETARG_TEXT_PP(1);
5710 tgl 284 66 : TSQuery rewrited = query;
285 66 : MemoryContext outercontext = CurrentMemoryContext;
286 : MemoryContext oldcontext;
287 : QTNode *tree;
288 : char *buf;
289 : SPIPlanPtr plan;
290 : Portal portal;
291 : bool isnull;
292 :
293 66 : if (query->size == 0)
294 : {
5710 tgl 295 UBC 0 : PG_FREE_IF_COPY(in, 1);
296 0 : PG_RETURN_POINTER(rewrited);
297 : }
298 :
5710 tgl 299 CBC 66 : tree = QT2QTN(GETQUERY(query), GETOPERAND(query));
300 66 : QTNTernary(tree);
301 66 : QTNSort(tree);
302 :
5493 303 66 : buf = text_to_cstring(in);
304 :
5710 305 66 : SPI_connect();
306 :
307 66 : if ((plan = SPI_prepare(buf, 0, NULL)) == NULL)
5710 tgl 308 UBC 0 : elog(ERROR, "SPI_prepare(\"%s\") failed", buf);
309 :
5646 tgl 310 CBC 66 : if ((portal = SPI_cursor_open(NULL, plan, NULL, NULL, true)) == NULL)
5710 tgl 311 UBC 0 : elog(ERROR, "SPI_cursor_open(\"%s\") failed", buf);
312 :
5710 tgl 313 CBC 66 : SPI_cursor_fetch(portal, true, 100);
314 :
5646 315 66 : if (SPI_tuptable == NULL ||
316 132 : SPI_tuptable->tupdesc->natts != 2 ||
5710 317 132 : SPI_gettypeid(SPI_tuptable->tupdesc, 1) != TSQUERYOID ||
318 66 : SPI_gettypeid(SPI_tuptable->tupdesc, 2) != TSQUERYOID)
5710 tgl 319 UBC 0 : ereport(ERROR,
320 : (errcode(ERRCODE_INVALID_PARAMETER_VALUE),
321 : errmsg("ts_rewrite query must return two tsquery columns")));
322 :
5710 tgl 323 CBC 132 : while (SPI_processed > 0 && tree)
324 : {
325 : uint64 i;
326 :
327 462 : for (i = 0; i < SPI_processed && tree; i++)
328 : {
329 396 : Datum qdata = SPI_getbinval(SPI_tuptable->vals[i], SPI_tuptable->tupdesc, 1, &isnull);
330 : Datum sdata;
331 :
332 396 : if (isnull)
5710 tgl 333 UBC 0 : continue;
334 :
5710 tgl 335 CBC 396 : sdata = SPI_getbinval(SPI_tuptable->vals[i], SPI_tuptable->tupdesc, 2, &isnull);
336 :
337 396 : if (!isnull)
338 : {
339 396 : TSQuery qtex = DatumGetTSQuery(qdata);
340 396 : TSQuery qtsubs = DatumGetTSQuery(sdata);
341 : QTNode *qex,
342 396 : *qsubs = NULL;
343 :
344 396 : if (qtex->size == 0)
345 : {
5710 tgl 346 UBC 0 : if (qtex != (TSQuery) DatumGetPointer(qdata))
347 0 : pfree(qtex);
348 0 : if (qtsubs != (TSQuery) DatumGetPointer(sdata))
349 0 : pfree(qtsubs);
350 0 : continue;
351 : }
352 :
5710 tgl 353 CBC 396 : qex = QT2QTN(GETQUERY(qtex), GETOPERAND(qtex));
354 :
355 396 : QTNTernary(qex);
356 396 : QTNSort(qex);
357 :
358 396 : if (qtsubs->size)
359 396 : qsubs = QT2QTN(GETQUERY(qtsubs), GETOPERAND(qtsubs));
360 :
361 396 : oldcontext = MemoryContextSwitchTo(outercontext);
362 396 : tree = findsubquery(tree, qex, qsubs, NULL);
363 396 : MemoryContextSwitchTo(oldcontext);
364 :
365 396 : QTNFree(qex);
366 396 : if (qtex != (TSQuery) DatumGetPointer(qdata))
5710 tgl 367 UBC 0 : pfree(qtex);
5710 tgl 368 CBC 396 : QTNFree(qsubs);
369 396 : if (qtsubs != (TSQuery) DatumGetPointer(sdata))
5710 tgl 370 UBC 0 : pfree(qtsubs);
371 :
5647 tgl 372 CBC 396 : if (tree)
373 : {
374 : /* ready the tree for another pass */
375 396 : QTNClearFlags(tree, QTN_NOCHANGE);
2352 376 396 : QTNTernary(tree);
5647 377 396 : QTNSort(tree);
378 : }
379 : }
380 : }
381 :
5710 382 66 : SPI_freetuptable(SPI_tuptable);
383 66 : SPI_cursor_fetch(portal, true, 100);
384 : }
385 :
386 66 : SPI_freetuptable(SPI_tuptable);
387 66 : SPI_cursor_close(portal);
388 66 : SPI_freeplan(plan);
389 66 : SPI_finish();
390 :
391 66 : if (tree)
392 : {
393 66 : QTNBinary(tree);
394 66 : rewrited = QTN2QT(tree);
395 66 : QTNFree(tree);
396 66 : PG_FREE_IF_COPY(query, 0);
397 : }
398 : else
399 : {
5710 tgl 400 UBC 0 : SET_VARSIZE(rewrited, HDRSIZETQ);
401 0 : rewrited->size = 0;
402 : }
403 :
5710 tgl 404 CBC 66 : pfree(buf);
405 66 : PG_FREE_IF_COPY(in, 1);
406 66 : PG_RETURN_POINTER(rewrited);
407 : }
408 :
409 : Datum
5646 410 24 : tsquery_rewrite(PG_FUNCTION_ARGS)
411 : {
5710 412 24 : TSQuery query = PG_GETARG_TSQUERY_COPY(0);
413 24 : TSQuery ex = PG_GETARG_TSQUERY(1);
414 24 : TSQuery subst = PG_GETARG_TSQUERY(2);
415 24 : TSQuery rewrited = query;
416 : QTNode *tree,
417 : *qex,
418 24 : *subs = NULL;
419 :
420 24 : if (query->size == 0 || ex->size == 0)
421 : {
5710 tgl 422 UBC 0 : PG_FREE_IF_COPY(ex, 1);
423 0 : PG_FREE_IF_COPY(subst, 2);
424 0 : PG_RETURN_POINTER(rewrited);
425 : }
426 :
5710 tgl 427 CBC 24 : tree = QT2QTN(GETQUERY(query), GETOPERAND(query));
428 24 : QTNTernary(tree);
429 24 : QTNSort(tree);
430 :
431 24 : qex = QT2QTN(GETQUERY(ex), GETOPERAND(ex));
432 24 : QTNTernary(qex);
433 24 : QTNSort(qex);
434 :
435 24 : if (subst->size)
436 18 : subs = QT2QTN(GETQUERY(subst), GETOPERAND(subst));
437 :
438 24 : tree = findsubquery(tree, qex, subs, NULL);
439 :
440 24 : QTNFree(qex);
441 24 : QTNFree(subs);
442 :
443 24 : if (!tree)
444 : {
445 3 : SET_VARSIZE(rewrited, HDRSIZETQ);
446 3 : rewrited->size = 0;
447 3 : PG_FREE_IF_COPY(ex, 1);
448 3 : PG_FREE_IF_COPY(subst, 2);
449 3 : PG_RETURN_POINTER(rewrited);
450 : }
451 : else
452 : {
453 21 : QTNBinary(tree);
454 21 : rewrited = QTN2QT(tree);
455 21 : QTNFree(tree);
456 : }
457 :
458 21 : PG_FREE_IF_COPY(query, 0);
459 21 : PG_FREE_IF_COPY(ex, 1);
460 21 : PG_FREE_IF_COPY(subst, 2);
461 21 : PG_RETURN_POINTER(rewrited);
462 : }
|
