]> granicus.if.org Git - postgresql/blobdiff - src/backend/utils/adt/tsquery_rewrite.c
Add support for EUI-64 MAC addresses as macaddr8
[postgresql] / src / backend / utils / adt / tsquery_rewrite.c
index c4d364a3871cf379ba8325d62717e50d3c43032f..1bd3deabd5605837e083c451e8343ee51f523111 100644 (file)
@@ -3,7 +3,7 @@
  * tsquery_rewrite.c
  *       Utilities for reconstructing tsquery
  *
- * Portions Copyright (c) 1996-2014, PostgreSQL Global Development Group
+ * Portions Copyright (c) 1996-2017, PostgreSQL Global Development Group
  *
  *
  * IDENTIFICATION
 #include "utils/builtins.h"
 
 
-static int
-addone(int *counters, int last, int total)
-{
-       /* since this function recurses, it could be driven to stack overflow. */
-       check_stack_depth();
-
-       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, replace it with subs. Replacement is actually done
- * by returning either node or a copy of subs.
+ * 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)
 {
+       /* 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 == 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)
                                {
@@ -73,79 +69,98 @@ findeq(QTNode *node, QTNode *ex, QTNode *subs, bool *isfind)
                                *isfind = true;
                        }
                }
-               else if (node->nchild > ex->nchild)
+               else if (node->nchild > ex->nchild && ex->nchild > 0)
                {
                        /*
-                        * AND and NOT are commutative, so we check if a subset of the
-                        * children match. For example, if tnode is A | B | C, and ex is B
-                        * | C, we have a match after we convert tnode to A | (B | C).
+                        * 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.
                         */
-                       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
+                       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
@@ -173,47 +188,56 @@ findeq(QTNode *node, QTNode *ex, QTNode *subs, bool *isfind)
        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)
 {
        /* since this function recurses, it could be driven to stack overflow. */
        check_stack_depth();
 
-       root = findeq(root, ex, subs, isfind);
-
-       if (root && (root->flags & QTN_NOCHANGE) == 0 && root->valnode->type == QI_OPR)
-       {
-               int                     i;
-
-               for (i = 0; i < root->nchild; i++)
-                       root->child[i] = dofindsubquery(root->child[i], ex, subs, isfind);
-       }
-
-       return root;
-}
+       /* also, since it's a bit expensive, let's check for query cancel. */
+       CHECK_FOR_INTERRUPTS();
 
-static QTNode *
-dropvoidsubtree(QTNode *root)
-{
-       if (!root)
-               return NULL;
+       /* match at the node itself */
+       root = findeq(root, ex, subs, isfind);
 
-       if (root->valnode->type == QI_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 we have just zero or one remaining child node, simplify out this
+                * operator node.
+                */
                if (root->nchild == 0)
                {
                        QTNFree(root);
@@ -231,6 +255,14 @@ dropvoidsubtree(QTNode *root)
        return root;
 }
 
+/*
+ * 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)
 {
@@ -238,9 +270,6 @@ findsubquery(QTNode *root, QTNode *ex, QTNode *subs, bool *isfind)
 
        root = dofindsubquery(root, ex, subs, &DidFind);
 
-       if (!subs && DidFind)
-               root = dropvoidsubtree(root);
-
        if (isfind)
                *isfind = DidFind;
 
@@ -251,7 +280,7 @@ Datum
 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;
@@ -260,7 +289,6 @@ tsquery_rewrite_query(PG_FUNCTION_ARGS)
        SPIPlanPtr      plan;
        Portal          portal;
        bool            isnull;
-       int                     i;
 
        if (query->size == 0)
        {
@@ -294,6 +322,8 @@ tsquery_rewrite_query(PG_FUNCTION_ARGS)
 
        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);
@@ -343,6 +373,7 @@ tsquery_rewrite_query(PG_FUNCTION_ARGS)
                                {
                                        /* ready the tree for another pass */
                                        QTNClearFlags(tree, QTN_NOCHANGE);
+                                       QTNTernary(tree);
                                        QTNSort(tree);
                                }
                        }