* tsquery_rewrite.c
* Utilities for reconstructing tsquery
*
- * Portions Copyright (c) 1996-2007, PostgreSQL Global Development Group
+ * Portions Copyright (c) 1996-2017, PostgreSQL Global Development Group
*
*
* IDENTIFICATION
- * $PostgreSQL: pgsql/src/backend/utils/adt/tsquery_rewrite.c,v 1.1 2007/08/21 01:11:19 tgl Exp $
+ * src/backend/utils/adt/tsquery_rewrite.c
*
*-------------------------------------------------------------------------
*/
#include "postgres.h"
+#include "catalog/pg_type.h"
#include "executor/spi.h"
-#include "tsearch/ts_type.h"
+#include "miscadmin.h"
#include "tsearch/ts_utils.h"
+#include "utils/builtins.h"
-static int
-addone(int *counters, int last, int total)
-{
- counters[last]++;
- if (counters[last] >= total)
- {
- if (last == 0)
- return 0;
- if (addone(counters, last - 1, total - 1) == 0)
- return 0;
- counters[last] = counters[last - 1] + 1;
- }
- return 1;
-}
-
+/*
+ * If "node" is equal to "ex", return a copy of "subs" instead.
+ * If "ex" matches a subset of node's children, return a modified version
+ * of "node" in which those children are replaced with a copy of "subs".
+ * Otherwise return "node" unmodified.
+ *
+ * The QTN_NOCHANGE bit is set in successfully modified nodes, so that
+ * we won't uselessly recurse into them.
+ * Also, set *isfind true if we make a replacement.
+ */
static QTNode *
findeq(QTNode *node, QTNode *ex, QTNode *subs, bool *isfind)
{
-
- if ((node->sign & ex->sign) != ex->sign || node->valnode->type != ex->valnode->type || node->valnode->val != ex->valnode->val)
+ /* Can't match unless signature matches and node type matches. */
+ if ((node->sign & ex->sign) != ex->sign ||
+ node->valnode->type != ex->valnode->type)
return node;
+ /* Ignore nodes marked NOCHANGE, too. */
if (node->flags & QTN_NOCHANGE)
return node;
- if (node->valnode->type == OPR)
+ if (node->valnode->type == QI_OPR)
{
+ /* Must be same operator. */
+ if (node->valnode->qoperator.oper != ex->valnode->qoperator.oper)
+ return node;
+
if (node->nchild == ex->nchild)
{
+ /*
+ * Simple case: when same number of children, match if equal.
+ * (This is reliable when the children were sorted earlier.)
+ */
if (QTNEq(node, ex))
{
+ /* Match; delete node and return a copy of subs instead. */
QTNFree(node);
if (subs)
{
*isfind = true;
}
}
- else if (node->nchild > ex->nchild)
+ else if (node->nchild > ex->nchild && ex->nchild > 0)
{
- int *counters = (int *) palloc(sizeof(int) * node->nchild);
- int i;
- QTNode *tnode = (QTNode *) palloc(sizeof(QTNode));
-
- memset(tnode, 0, sizeof(QTNode));
- tnode->child = (QTNode **) palloc(sizeof(QTNode *) * ex->nchild);
- tnode->nchild = ex->nchild;
- tnode->valnode = (QueryItem *) palloc(sizeof(QueryItem));
- *(tnode->valnode) = *(ex->valnode);
-
- for (i = 0; i < ex->nchild; i++)
- counters[i] = i;
-
- do
+ /*
+ * AND and OR are commutative/associative, so we should check if a
+ * subset of the children match. For example, if node is A|B|C,
+ * and ex is B|C, we have a match after we notionally convert node
+ * to A|(B|C). This does not work for NOT or PHRASE nodes, but we
+ * can't get here for those node types because they have a fixed
+ * number of children.
+ *
+ * Because we expect that the children are sorted, it suffices to
+ * make one pass through the two lists to find the matches.
+ */
+ bool *matched;
+ int nmatched;
+ int i,
+ j;
+
+ /* Assert that the subset rule is OK */
+ Assert(node->valnode->qoperator.oper == OP_AND ||
+ node->valnode->qoperator.oper == OP_OR);
+
+ /* matched[] will record which children of node matched */
+ matched = (bool *) palloc0(node->nchild * sizeof(bool));
+ nmatched = 0;
+ i = j = 0;
+ while (i < node->nchild && j < ex->nchild)
{
- tnode->sign = 0;
- for (i = 0; i < ex->nchild; i++)
+ int cmp = QTNodeCompare(node->child[i], ex->child[j]);
+
+ if (cmp == 0)
{
- tnode->child[i] = node->child[counters[i]];
- tnode->sign |= tnode->child[i]->sign;
+ /* match! */
+ matched[i] = true;
+ nmatched++;
+ i++, j++;
}
+ else if (cmp < 0)
+ {
+ /* node->child[i] has no match, ignore it */
+ i++;
+ }
+ else
+ {
+ /* ex->child[j] has no match; we can give up immediately */
+ break;
+ }
+ }
- if (QTNEq(tnode, ex))
+ if (nmatched == ex->nchild)
+ {
+ /* collapse out the matched children of node */
+ j = 0;
+ for (i = 0; i < node->nchild; i++)
{
- int j = 0;
-
- pfree(tnode->valnode);
- pfree(tnode->child);
- pfree(tnode);
- if (subs)
- {
- tnode = QTNCopy(subs);
- tnode->flags = QTN_NOCHANGE | QTN_NEEDFREE;
- }
+ if (matched[i])
+ QTNFree(node->child[i]);
else
- tnode = NULL;
-
- node->child[counters[0]] = tnode;
-
- for (i = 1; i < ex->nchild; i++)
- node->child[counters[i]] = NULL;
- for (i = 0; i < node->nchild; i++)
- {
- if (node->child[i])
- {
- node->child[j] = node->child[i];
- j++;
- }
- }
+ node->child[j++] = node->child[i];
+ }
- node->nchild = j;
+ /* and instead insert a copy of subs */
+ if (subs)
+ {
+ subs = QTNCopy(subs);
+ subs->flags |= QTN_NOCHANGE;
+ node->child[j++] = subs;
+ }
- *isfind = true;
+ node->nchild = j;
+
+ /*
+ * At this point we might have a node with zero or one child,
+ * which should be simplified. But we leave it to our caller
+ * (dofindsubquery) to take care of that.
+ */
+
+ /*
+ * Re-sort the node to put new child in the right place. This
+ * is a bit bogus, because it won't matter for findsubquery's
+ * remaining processing, and it's insufficient to prepare the
+ * tree for another search (we would need to re-flatten as
+ * well, and we don't want to do that because we'd lose the
+ * QTN_NOCHANGE marking on the new child). But it's needed to
+ * keep the results the same as the regression tests expect.
+ */
+ QTNSort(node);
- break;
- }
- } while (addone(counters, ex->nchild - 1, node->nchild));
- if (tnode && (tnode->flags & QTN_NOCHANGE) == 0)
- {
- pfree(tnode->valnode);
- pfree(tnode->child);
- pfree(tnode);
+ *isfind = true;
}
- else
- QTNSort(node);
- pfree(counters);
+
+ pfree(matched);
}
}
- else if (QTNEq(node, ex))
+ else
{
- QTNFree(node);
- if (subs)
- {
- node = QTNCopy(subs);
- node->flags |= QTN_NOCHANGE;
- }
- else
+ Assert(node->valnode->type == QI_VAL);
+
+ if (node->valnode->qoperand.valcrc != ex->valnode->qoperand.valcrc)
+ return node;
+ else if (QTNEq(node, ex))
{
- node = NULL;
+ QTNFree(node);
+ if (subs)
+ {
+ node = QTNCopy(subs);
+ node->flags |= QTN_NOCHANGE;
+ }
+ else
+ {
+ node = NULL;
+ }
+ *isfind = true;
}
- *isfind = true;
}
return node;
}
+/*
+ * Recursive guts of findsubquery(): attempt to replace "ex" with "subs"
+ * at the root node, and if we failed to do so, recursively match against
+ * child nodes.
+ *
+ * Delete any void subtrees resulting from the replacement.
+ * In the following example '5' is replaced by empty operand:
+ *
+ * AND -> 6
+ * / \
+ * 5 OR
+ * / \
+ * 6 5
+ */
static QTNode *
dofindsubquery(QTNode *root, QTNode *ex, QTNode *subs, bool *isfind)
{
- root = findeq(root, ex, subs, isfind);
+ /* since this function recurses, it could be driven to stack overflow. */
+ check_stack_depth();
- if (root && (root->flags & QTN_NOCHANGE) == 0 && root->valnode->type == OPR)
- {
- int i;
+ /* also, since it's a bit expensive, let's check for query cancel. */
+ CHECK_FOR_INTERRUPTS();
- for (i = 0; i < root->nchild; i++)
- root->child[i] = dofindsubquery(root->child[i], ex, subs, isfind);
- }
-
- return root;
-}
-
-static QTNode *
-dropvoidsubtree(QTNode * root)
-{
-
- if (!root)
- return NULL;
+ /* match at the node itself */
+ root = findeq(root, ex, subs, isfind);
- if (root->valnode->type == OPR)
+ /* unless we matched here, consider matches at child nodes */
+ if (root && (root->flags & QTN_NOCHANGE) == 0 &&
+ root->valnode->type == QI_OPR)
{
int i,
j = 0;
+ /*
+ * Any subtrees that are replaced by NULL must be dropped from the
+ * tree.
+ */
for (i = 0; i < root->nchild; i++)
{
- if (root->child[i])
- {
- root->child[j] = root->child[i];
+ root->child[j] = dofindsubquery(root->child[i], ex, subs, isfind);
+ if (root->child[j])
j++;
- }
}
root->nchild = j;
- if (root->valnode->val == (int4) '!' && root->nchild == 0)
+ /*
+ * If we have just zero or one remaining child node, simplify out this
+ * operator node.
+ */
+ if (root->nchild == 0)
{
QTNFree(root);
root = NULL;
}
- else if (root->nchild == 1)
+ else if (root->nchild == 1 && root->valnode->qoperator.oper != OP_NOT)
{
QTNode *nroot = root->child[0];
return root;
}
-static QTNode *
+/*
+ * Substitute "subs" for "ex" throughout the QTNode tree at root.
+ *
+ * If isfind isn't NULL, set *isfind to show whether we made any substitution.
+ *
+ * Both "root" and "ex" must have been through QTNTernary and QTNSort
+ * to ensure reliable matching.
+ */
+QTNode *
findsubquery(QTNode *root, QTNode *ex, QTNode *subs, bool *isfind)
{
bool DidFind = false;
root = dofindsubquery(root, ex, subs, &DidFind);
- if (!subs && DidFind)
- root = dropvoidsubtree(root);
-
if (isfind)
*isfind = DidFind;
}
Datum
-ts_rewrite_accum(PG_FUNCTION_ARGS)
-{
- TSQuery acc;
- ArrayType *qa;
- TSQuery q;
- QTNode *qex = NULL,
- *subs = NULL,
- *acctree = NULL;
- bool isfind = false;
- Datum *elemsp;
- int nelemsp;
- MemoryContext aggcontext;
- MemoryContext oldcontext;
-
- aggcontext = ((AggState *) fcinfo->context)->aggcontext;
-
- if (PG_ARGISNULL(0) || PG_GETARG_POINTER(0) == NULL)
- {
- acc = (TSQuery) MemoryContextAlloc(aggcontext, HDRSIZETQ);
- SET_VARSIZE(acc, HDRSIZETQ);
- acc->size = 0;
- }
- else
- acc = PG_GETARG_TSQUERY(0);
-
- if (PG_ARGISNULL(1) || PG_GETARG_POINTER(1) == NULL)
- PG_RETURN_TSQUERY(acc);
- else
- qa = PG_GETARG_ARRAYTYPE_P_COPY(1);
-
- if (ARR_NDIM(qa) != 1)
- elog(ERROR, "array must be one-dimensional, not %d dimensions",
- ARR_NDIM(qa));
- if (ArrayGetNItems(ARR_NDIM(qa), ARR_DIMS(qa)) != 3)
- elog(ERROR, "array should have only three elements");
- if (ARR_ELEMTYPE(qa) != TSQUERYOID)
- elog(ERROR, "array should contain tsquery type");
-
- deconstruct_array(qa, TSQUERYOID, -1, false, 'i', &elemsp, NULL, &nelemsp);
-
- q = DatumGetTSQuery(elemsp[0]);
- if (q->size == 0)
- {
- pfree(elemsp);
- PG_RETURN_POINTER(acc);
- }
-
- if (!acc->size)
- {
- if (VARSIZE(acc) > HDRSIZETQ)
- {
- pfree(elemsp);
- PG_RETURN_POINTER(acc);
- }
- else
- acctree = QT2QTN(GETQUERY(q), GETOPERAND(q));
- }
- else
- acctree = QT2QTN(GETQUERY(acc), GETOPERAND(acc));
-
- QTNTernary(acctree);
- QTNSort(acctree);
-
- q = DatumGetTSQuery(elemsp[1]);
- if (q->size == 0)
- {
- pfree(elemsp);
- PG_RETURN_POINTER(acc);
- }
- qex = QT2QTN(GETQUERY(q), GETOPERAND(q));
- QTNTernary(qex);
- QTNSort(qex);
-
- q = DatumGetTSQuery(elemsp[2]);
- if (q->size)
- subs = QT2QTN(GETQUERY(q), GETOPERAND(q));
-
- acctree = findsubquery(acctree, qex, subs, &isfind);
-
- if (isfind || !acc->size)
- {
- /* pfree( acc ); do not pfree(p), because nodeAgg.c will */
- if (acctree)
- {
- QTNBinary(acctree);
- oldcontext = MemoryContextSwitchTo(aggcontext);
- acc = QTN2QT(acctree);
- MemoryContextSwitchTo(oldcontext);
- }
- else
- {
- acc = (TSQuery) MemoryContextAlloc(aggcontext, HDRSIZETQ);
- SET_VARSIZE(acc, HDRSIZETQ);
- acc->size = 0;
- }
- }
-
- pfree(elemsp);
- QTNFree(qex);
- QTNFree(subs);
- QTNFree(acctree);
-
- PG_RETURN_TSQUERY(acc);
-}
-
-Datum
-ts_rewrite_finish(PG_FUNCTION_ARGS)
-{
- TSQuery acc = PG_GETARG_TSQUERY(0);
- TSQuery rewrited;
-
- if (acc == NULL || PG_ARGISNULL(0) || acc->size == 0)
- {
- rewrited = (TSQuery) palloc(HDRSIZETQ);
- SET_VARSIZE(rewrited, HDRSIZETQ);
- rewrited->size = 0;
- }
- else
- {
- rewrited = (TSQuery) palloc(VARSIZE(acc));
- memcpy(rewrited, acc, VARSIZE(acc));
- pfree(acc);
- }
-
- PG_RETURN_POINTER(rewrited);
-}
-
-Datum
-tsquery_rewrite(PG_FUNCTION_ARGS)
+tsquery_rewrite_query(PG_FUNCTION_ARGS)
{
TSQuery query = PG_GETARG_TSQUERY_COPY(0);
- text *in = PG_GETARG_TEXT_P(1);
+ text *in = PG_GETARG_TEXT_PP(1);
TSQuery rewrited = query;
MemoryContext outercontext = CurrentMemoryContext;
MemoryContext oldcontext;
QTNode *tree;
char *buf;
- void *plan;
+ SPIPlanPtr plan;
Portal portal;
bool isnull;
- int i;
if (query->size == 0)
{
QTNTernary(tree);
QTNSort(tree);
- buf = TextPGetCString(in);
+ buf = text_to_cstring(in);
SPI_connect();
if ((plan = SPI_prepare(buf, 0, NULL)) == NULL)
elog(ERROR, "SPI_prepare(\"%s\") failed", buf);
- if ((portal = SPI_cursor_open(NULL, plan, NULL, NULL, false)) == NULL)
+ if ((portal = SPI_cursor_open(NULL, plan, NULL, NULL, true)) == NULL)
elog(ERROR, "SPI_cursor_open(\"%s\") failed", buf);
SPI_cursor_fetch(portal, true, 100);
- if (SPI_tuptable->tupdesc->natts != 2 ||
+ if (SPI_tuptable == NULL ||
+ SPI_tuptable->tupdesc->natts != 2 ||
SPI_gettypeid(SPI_tuptable->tupdesc, 1) != TSQUERYOID ||
SPI_gettypeid(SPI_tuptable->tupdesc, 2) != TSQUERYOID)
ereport(ERROR,
while (SPI_processed > 0 && tree)
{
+ uint64 i;
+
for (i = 0; i < SPI_processed && tree; i++)
{
Datum qdata = SPI_getbinval(SPI_tuptable->vals[i], SPI_tuptable->tupdesc, 1, &isnull);
QTNFree(qsubs);
if (qtsubs != (TSQuery) DatumGetPointer(sdata))
pfree(qtsubs);
+
+ if (tree)
+ {
+ /* ready the tree for another pass */
+ QTNClearFlags(tree, QTN_NOCHANGE);
+ QTNTernary(tree);
+ QTNSort(tree);
+ }
}
}
}
Datum
-tsquery_rewrite_query(PG_FUNCTION_ARGS)
+tsquery_rewrite(PG_FUNCTION_ARGS)
{
TSQuery query = PG_GETARG_TSQUERY_COPY(0);
TSQuery ex = PG_GETARG_TSQUERY(1);
subs = QT2QTN(GETQUERY(subst), GETOPERAND(subst));
tree = findsubquery(tree, qex, subs, NULL);
+
QTNFree(qex);
QTNFree(subs);