LCOV - code coverage report
Current view: top level - src/backend/utils/adt - tsquery_cleanup.c (source / functions) Hit Total Coverage
Test: PostgreSQL 13devel Lines: 122 158 77.2 %
Date: 2019-09-19 02:07:14 Functions: 7 9 77.8 %
Legend: Lines: hit not hit

          Line data    Source code
       1             : /*-------------------------------------------------------------------------
       2             :  *
       3             :  * tsquery_cleanup.c
       4             :  *   Cleanup query from NOT values and/or stopword
       5             :  *   Utility functions to correct work.
       6             :  *
       7             :  * Portions Copyright (c) 1996-2019, PostgreSQL Global Development Group
       8             :  *
       9             :  *
      10             :  * IDENTIFICATION
      11             :  *    src/backend/utils/adt/tsquery_cleanup.c
      12             :  *
      13             :  *-------------------------------------------------------------------------
      14             :  */
      15             : 
      16             : #include "postgres.h"
      17             : 
      18             : #include "tsearch/ts_utils.h"
      19             : #include "miscadmin.h"
      20             : 
      21             : typedef struct NODE
      22             : {
      23             :     struct NODE *left;
      24             :     struct NODE *right;
      25             :     QueryItem  *valnode;
      26             : } NODE;
      27             : 
      28             : /*
      29             :  * make query tree from plain view of query
      30             :  */
      31             : static NODE *
      32        2152 : maketree(QueryItem *in)
      33             : {
      34        2152 :     NODE       *node = (NODE *) palloc(sizeof(NODE));
      35             : 
      36             :     /* since this function recurses, it could be driven to stack overflow. */
      37        2152 :     check_stack_depth();
      38             : 
      39        2152 :     node->valnode = in;
      40        2152 :     node->right = node->left = NULL;
      41        2152 :     if (in->type == QI_OPR)
      42             :     {
      43         952 :         node->right = maketree(in + 1);
      44         952 :         if (in->qoperator.oper != OP_NOT)
      45         896 :             node->left = maketree(in + in->qoperator.left);
      46             :     }
      47        2152 :     return node;
      48             : }
      49             : 
      50             : /*
      51             :  * Internal state for plaintree and plainnode
      52             :  */
      53             : typedef struct
      54             : {
      55             :     QueryItem  *ptr;
      56             :     int         len;            /* allocated size of ptr */
      57             :     int         cur;            /* number of elements in ptr */
      58             : } PLAINTREE;
      59             : 
      60             : static void
      61        1156 : plainnode(PLAINTREE *state, NODE *node)
      62             : {
      63             :     /* since this function recurses, it could be driven to stack overflow. */
      64        1156 :     check_stack_depth();
      65             : 
      66        1156 :     if (state->cur == state->len)
      67             :     {
      68           0 :         state->len *= 2;
      69           0 :         state->ptr = (QueryItem *) repalloc((void *) state->ptr, state->len * sizeof(QueryItem));
      70             :     }
      71        1156 :     memcpy((void *) &(state->ptr[state->cur]), (void *) node->valnode, sizeof(QueryItem));
      72        1156 :     if (node->valnode->type == QI_VAL)
      73         700 :         state->cur++;
      74         456 :     else if (node->valnode->qoperator.oper == OP_NOT)
      75             :     {
      76          44 :         state->ptr[state->cur].qoperator.left = 1;
      77          44 :         state->cur++;
      78          44 :         plainnode(state, node->right);
      79             :     }
      80             :     else
      81             :     {
      82         412 :         int         cur = state->cur;
      83             : 
      84         412 :         state->cur++;
      85         412 :         plainnode(state, node->right);
      86         412 :         state->ptr[cur].qoperator.left = state->cur - cur;
      87         412 :         plainnode(state, node->left);
      88             :     }
      89        1156 :     pfree(node);
      90        1156 : }
      91             : 
      92             : /*
      93             :  * make plain view of tree from a NODE-tree representation
      94             :  */
      95             : static QueryItem *
      96         288 : plaintree(NODE *root, int *len)
      97             : {
      98             :     PLAINTREE   pl;
      99             : 
     100         288 :     pl.cur = 0;
     101         288 :     pl.len = 16;
     102         288 :     if (root && (root->valnode->type == QI_VAL || root->valnode->type == QI_OPR))
     103             :     {
     104         288 :         pl.ptr = (QueryItem *) palloc(pl.len * sizeof(QueryItem));
     105         288 :         plainnode(&pl, root);
     106             :     }
     107             :     else
     108           0 :         pl.ptr = NULL;
     109         288 :     *len = pl.cur;
     110         288 :     return pl.ptr;
     111             : }
     112             : 
     113             : static void
     114          32 : freetree(NODE *node)
     115             : {
     116             :     /* since this function recurses, it could be driven to stack overflow. */
     117          32 :     check_stack_depth();
     118             : 
     119          32 :     if (!node)
     120           0 :         return;
     121          32 :     if (node->left)
     122           0 :         freetree(node->left);
     123          32 :     if (node->right)
     124           0 :         freetree(node->right);
     125          32 :     pfree(node);
     126             : }
     127             : 
     128             : /*
     129             :  * clean tree for ! operator.
     130             :  * It's useful for debug, but in
     131             :  * other case, such view is used with search in index.
     132             :  * Operator ! always return TRUE
     133             :  */
     134             : static NODE *
     135           0 : clean_NOT_intree(NODE *node)
     136             : {
     137             :     /* since this function recurses, it could be driven to stack overflow. */
     138           0 :     check_stack_depth();
     139             : 
     140           0 :     if (node->valnode->type == QI_VAL)
     141           0 :         return node;
     142             : 
     143           0 :     if (node->valnode->qoperator.oper == OP_NOT)
     144             :     {
     145           0 :         freetree(node);
     146           0 :         return NULL;
     147             :     }
     148             : 
     149             :     /* operator & or | */
     150           0 :     if (node->valnode->qoperator.oper == OP_OR)
     151             :     {
     152           0 :         if ((node->left = clean_NOT_intree(node->left)) == NULL ||
     153           0 :             (node->right = clean_NOT_intree(node->right)) == NULL)
     154             :         {
     155           0 :             freetree(node);
     156           0 :             return NULL;
     157             :         }
     158             :     }
     159             :     else
     160             :     {
     161           0 :         NODE       *res = node;
     162             : 
     163             :         Assert(node->valnode->qoperator.oper == OP_AND ||
     164             :                node->valnode->qoperator.oper == OP_PHRASE);
     165             : 
     166           0 :         node->left = clean_NOT_intree(node->left);
     167           0 :         node->right = clean_NOT_intree(node->right);
     168           0 :         if (node->left == NULL && node->right == NULL)
     169             :         {
     170           0 :             pfree(node);
     171           0 :             res = NULL;
     172             :         }
     173           0 :         else if (node->left == NULL)
     174             :         {
     175           0 :             res = node->right;
     176           0 :             pfree(node);
     177             :         }
     178           0 :         else if (node->right == NULL)
     179             :         {
     180           0 :             res = node->left;
     181           0 :             pfree(node);
     182             :         }
     183           0 :         return res;
     184             :     }
     185           0 :     return node;
     186             : }
     187             : 
     188             : QueryItem *
     189           0 : clean_NOT(QueryItem *ptr, int *len)
     190             : {
     191           0 :     NODE       *root = maketree(ptr);
     192             : 
     193           0 :     return plaintree(clean_NOT_intree(root), len);
     194             : }
     195             : 
     196             : 
     197             : /*
     198             :  * Remove QI_VALSTOP (stopword) nodes from query tree.
     199             :  *
     200             :  * Returns NULL if the query degenerates to nothing.  Input must not be NULL.
     201             :  *
     202             :  * When we remove a phrase operator due to removing one or both of its
     203             :  * arguments, we might need to adjust the distance of a parent phrase
     204             :  * operator.  For example, 'a' is a stopword, so:
     205             :  *      (b <-> a) <-> c  should become  b <2> c
     206             :  *      b <-> (a <-> c)  should become  b <2> c
     207             :  *      (b <-> (a <-> a)) <-> c  should become    b <3> c
     208             :  *      b <-> ((a <-> a) <-> c)  should become    b <3> c
     209             :  * To handle that, we define two output parameters:
     210             :  *      ladd: amount to add to a phrase distance to the left of this node
     211             :  *      radd: amount to add to a phrase distance to the right of this node
     212             :  * We need two outputs because we could need to bubble up adjustments to two
     213             :  * different parent phrase operators.  Consider
     214             :  *      w <-> (((a <-> x) <2> (y <3> a)) <-> z)
     215             :  * After we've removed the two a's and are considering the <2> node (which is
     216             :  * now just x <2> y), we have an ladd distance of 1 that needs to propagate
     217             :  * up to the topmost (leftmost) <->, and an radd distance of 3 that needs to
     218             :  * propagate to the rightmost <->, so that we'll end up with
     219             :  *      w <2> ((x <2> y) <4> z)
     220             :  * Near the bottom of the tree, we may have subtrees consisting only of
     221             :  * stopwords.  The distances of any phrase operators within such a subtree are
     222             :  * summed and propagated to both ladd and radd, since we don't know which side
     223             :  * of the lowest surviving phrase operator we are in.  The rule is that any
     224             :  * subtree that degenerates to NULL must return equal values of ladd and radd,
     225             :  * and the parent node dealing with it should incorporate only one of those.
     226             :  *
     227             :  * Currently, we only implement this adjustment for adjacent phrase operators.
     228             :  * Thus for example 'x <-> ((a <-> y) | z)' will become 'x <-> (y | z)', which
     229             :  * isn't ideal, but there is no way to represent the really desired semantics
     230             :  * without some redesign of the tsquery structure.  Certainly it would not be
     231             :  * any better to convert that to 'x <2> (y | z)'.  Since this is such a weird
     232             :  * corner case, let it go for now.  But we can fix it in cases where the
     233             :  * intervening non-phrase operator also gets removed, for example
     234             :  * '((x <-> a) | a) <-> y' will become 'x <2> y'.
     235             :  */
     236             : static NODE *
     237        2152 : clean_stopword_intree(NODE *node, int *ladd, int *radd)
     238             : {
     239             :     /* since this function recurses, it could be driven to stack overflow. */
     240        2152 :     check_stack_depth();
     241             : 
     242             :     /* default output parameters indicate no change in parent distance */
     243        2152 :     *ladd = *radd = 0;
     244             : 
     245        2152 :     if (node->valnode->type == QI_VAL)
     246         700 :         return node;
     247        1452 :     else if (node->valnode->type == QI_VALSTOP)
     248             :     {
     249         500 :         pfree(node);
     250         500 :         return NULL;
     251             :     }
     252             : 
     253             :     Assert(node->valnode->type == QI_OPR);
     254             : 
     255         952 :     if (node->valnode->qoperator.oper == OP_NOT)
     256             :     {
     257             :         /* NOT doesn't change pattern width, so just report child distances */
     258          56 :         node->right = clean_stopword_intree(node->right, ladd, radd);
     259          56 :         if (!node->right)
     260             :         {
     261          12 :             freetree(node);
     262          12 :             return NULL;
     263             :         }
     264             :     }
     265             :     else
     266             :     {
     267         896 :         NODE       *res = node;
     268             :         bool        isphrase;
     269             :         int         ndistance,
     270             :                     lladd,
     271             :                     lradd,
     272             :                     rladd,
     273             :                     rradd;
     274             : 
     275             :         /* First, recurse */
     276         896 :         node->left = clean_stopword_intree(node->left, &lladd, &lradd);
     277         896 :         node->right = clean_stopword_intree(node->right, &rladd, &rradd);
     278             : 
     279             :         /* Check if current node is OP_PHRASE, get its distance */
     280         896 :         isphrase = (node->valnode->qoperator.oper == OP_PHRASE);
     281         896 :         ndistance = isphrase ? node->valnode->qoperator.distance : 0;
     282             : 
     283         896 :         if (node->left == NULL && node->right == NULL)
     284             :         {
     285             :             /*
     286             :              * When we collapse out a phrase node entirely, propagate its own
     287             :              * distance into both *ladd and *radd; it is the responsibility of
     288             :              * the parent node to count it only once.  Also, for a phrase
     289             :              * node, distances coming from children are summed and propagated
     290             :              * up to parent (we assume lladd == lradd and rladd == rradd, else
     291             :              * rule was broken at a lower level).  But if this isn't a phrase
     292             :              * node, take the larger of the two child distances; that
     293             :              * corresponds to what TS_execute will do in non-stopword cases.
     294             :              */
     295          20 :             if (isphrase)
     296           4 :                 *ladd = *radd = lladd + ndistance + rladd;
     297             :             else
     298          16 :                 *ladd = *radd = Max(lladd, rladd);
     299          20 :             freetree(node);
     300          20 :             return NULL;
     301             :         }
     302         876 :         else if (node->left == NULL)
     303             :         {
     304             :             /* Removing this operator and left subnode */
     305             :             /* lladd and lradd are equal/redundant, don't count both */
     306         192 :             if (isphrase)
     307             :             {
     308             :                 /* operator's own distance must propagate to left */
     309         132 :                 *ladd = lladd + ndistance + rladd;
     310         132 :                 *radd = rradd;
     311             :             }
     312             :             else
     313             :             {
     314             :                 /* at non-phrase op, just forget the left subnode entirely */
     315          60 :                 *ladd = rladd;
     316          60 :                 *radd = rradd;
     317             :             }
     318         192 :             res = node->right;
     319         192 :             pfree(node);
     320             :         }
     321         684 :         else if (node->right == NULL)
     322             :         {
     323             :             /* Removing this operator and right subnode */
     324             :             /* rladd and rradd are equal/redundant, don't count both */
     325         272 :             if (isphrase)
     326             :             {
     327             :                 /* operator's own distance must propagate to right */
     328         152 :                 *ladd = lladd;
     329         152 :                 *radd = lradd + ndistance + rradd;
     330             :             }
     331             :             else
     332             :             {
     333             :                 /* at non-phrase op, just forget the right subnode entirely */
     334         120 :                 *ladd = lladd;
     335         120 :                 *radd = lradd;
     336             :             }
     337         272 :             res = node->left;
     338         272 :             pfree(node);
     339             :         }
     340         412 :         else if (isphrase)
     341             :         {
     342             :             /* Absorb appropriate corrections at this level */
     343         216 :             node->valnode->qoperator.distance += lradd + rladd;
     344             :             /* Propagate up any unaccounted-for corrections */
     345         216 :             *ladd = lladd;
     346         216 :             *radd = rradd;
     347             :         }
     348             :         else
     349             :         {
     350             :             /* We're keeping a non-phrase operator, so ladd/radd remain 0 */
     351             :         }
     352             : 
     353         876 :         return res;
     354             :     }
     355          44 :     return node;
     356             : }
     357             : 
     358             : /*
     359             :  * Number of elements in query tree
     360             :  */
     361             : static int32
     362        1156 : calcstrlen(NODE *node)
     363             : {
     364        1156 :     int32       size = 0;
     365             : 
     366        1156 :     if (node->valnode->type == QI_VAL)
     367             :     {
     368         700 :         size = node->valnode->qoperand.length + 1;
     369             :     }
     370             :     else
     371             :     {
     372             :         Assert(node->valnode->type == QI_OPR);
     373             : 
     374         456 :         size = calcstrlen(node->right);
     375         456 :         if (node->valnode->qoperator.oper != OP_NOT)
     376         412 :             size += calcstrlen(node->left);
     377             :     }
     378             : 
     379        1156 :     return size;
     380             : }
     381             : 
     382             : /*
     383             :  * Remove QI_VALSTOP (stopword) nodes from TSQuery.
     384             :  */
     385             : TSQuery
     386         304 : cleanup_tsquery_stopwords(TSQuery in)
     387             : {
     388             :     int32       len,
     389             :                 lenstr,
     390             :                 commonlen,
     391             :                 i;
     392             :     NODE       *root;
     393             :     int         ladd,
     394             :                 radd;
     395             :     TSQuery     out;
     396             :     QueryItem  *items;
     397             :     char       *operands;
     398             : 
     399         304 :     if (in->size == 0)
     400           0 :         return in;
     401             : 
     402             :     /* eliminate stop words */
     403         304 :     root = clean_stopword_intree(maketree(GETQUERY(in)), &ladd, &radd);
     404         304 :     if (root == NULL)
     405             :     {
     406          16 :         ereport(NOTICE,
     407             :                 (errmsg("text-search query contains only stop words or doesn't contain lexemes, ignored")));
     408          16 :         out = palloc(HDRSIZETQ);
     409          16 :         out->size = 0;
     410          16 :         SET_VARSIZE(out, HDRSIZETQ);
     411          16 :         return out;
     412             :     }
     413             : 
     414             :     /*
     415             :      * Build TSQuery from plain view
     416             :      */
     417             : 
     418         288 :     lenstr = calcstrlen(root);
     419         288 :     items = plaintree(root, &len);
     420         288 :     commonlen = COMPUTESIZE(len, lenstr);
     421             : 
     422         288 :     out = palloc(commonlen);
     423         288 :     SET_VARSIZE(out, commonlen);
     424         288 :     out->size = len;
     425             : 
     426         288 :     memcpy(GETQUERY(out), items, len * sizeof(QueryItem));
     427             : 
     428         288 :     items = GETQUERY(out);
     429         288 :     operands = GETOPERAND(out);
     430        1444 :     for (i = 0; i < out->size; i++)
     431             :     {
     432        1156 :         QueryOperand *op = (QueryOperand *) &items[i];
     433             : 
     434        1156 :         if (op->type != QI_VAL)
     435         456 :             continue;
     436             : 
     437         700 :         memcpy(operands, GETOPERAND(in) + op->distance, op->length);
     438         700 :         operands[op->length] = '\0';
     439         700 :         op->distance = operands - GETOPERAND(out);
     440         700 :         operands += op->length + 1;
     441             :     }
     442             : 
     443         288 :     return out;
     444             : }

Generated by: LCOV version 1.13