LCOV - code coverage report
Current view: top level - src/backend/utils/adt - tsquery_util.c (source / functions) Hit Total Coverage
Test: PostgreSQL 12beta2 Lines: 174 176 98.9 %
Date: 2019-06-18 07:06:57 Functions: 13 13 100.0 %
Legend: Lines: hit not hit

          Line data    Source code
       1             : /*-------------------------------------------------------------------------
       2             :  *
       3             :  * tsquery_util.c
       4             :  *    Utilities for tsquery datatype
       5             :  *
       6             :  * Portions Copyright (c) 1996-2019, 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        5948 : QT2QTN(QueryItem *in, char *operand)
      25             : {
      26        5948 :     QTNode     *node = (QTNode *) palloc0(sizeof(QTNode));
      27             : 
      28             :     /* since this function recurses, it could be driven to stack overflow. */
      29        5948 :     check_stack_depth();
      30             : 
      31        5948 :     node->valnode = in;
      32             : 
      33        5948 :     if (in->type == QI_OPR)
      34             :     {
      35        2244 :         node->child = (QTNode **) palloc0(sizeof(QTNode *) * 2);
      36        2244 :         node->child[0] = QT2QTN(in + 1, operand);
      37        2244 :         node->sign = node->child[0]->sign;
      38        2244 :         if (in->qoperator.oper == OP_NOT)
      39          28 :             node->nchild = 1;
      40             :         else
      41             :         {
      42        2216 :             node->nchild = 2;
      43        2216 :             node->child[1] = QT2QTN(in + in->qoperator.left, operand);
      44        2216 :             node->sign |= node->child[1]->sign;
      45             :         }
      46             :     }
      47        3704 :     else if (operand)
      48             :     {
      49        3704 :         node->word = operand + in->qoperand.distance;
      50        3704 :         node->sign = ((uint32) 1) << (((unsigned int) in->qoperand.valcrc) % 32);
      51             :     }
      52             : 
      53        5948 :     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        6536 : QTNFree(QTNode *in)
      64             : {
      65        6536 :     if (!in)
      66           8 :         return;
      67             : 
      68             :     /* since this function recurses, it could be driven to stack overflow. */
      69        6528 :     check_stack_depth();
      70             : 
      71        6528 :     if (in->valnode->type == QI_VAL && in->word && (in->flags & QTN_WORDFREE) != 0)
      72         408 :         pfree(in->word);
      73             : 
      74        6528 :     if (in->valnode->type == QI_OPR)
      75             :     {
      76             :         int         i;
      77             : 
      78        7292 :         for (i = 0; i < in->nchild; i++)
      79        4876 :             QTNFree(in->child[i]);
      80             :     }
      81        6528 :     if (in->child)
      82        2416 :         pfree(in->child);
      83             : 
      84        6528 :     if (in->flags & QTN_NEEDFREE)
      85         760 :         pfree(in->valnode);
      86             : 
      87        6528 :     pfree(in);
      88             : }
      89             : 
      90             : /*
      91             :  * Sort comparator for QTNodes.
      92             :  *
      93             :  * The sort order is somewhat arbitrary.
      94             :  */
      95             : int
      96        3466 : QTNodeCompare(QTNode *an, QTNode *bn)
      97             : {
      98             :     /* since this function recurses, it could be driven to stack overflow. */
      99        3466 :     check_stack_depth();
     100             : 
     101        3466 :     if (an->valnode->type != bn->valnode->type)
     102         812 :         return (an->valnode->type > bn->valnode->type) ? -1 : 1;
     103             : 
     104        2654 :     if (an->valnode->type == QI_OPR)
     105             :     {
     106         376 :         QueryOperator *ao = &an->valnode->qoperator;
     107         376 :         QueryOperator *bo = &bn->valnode->qoperator;
     108             : 
     109         376 :         if (ao->oper != bo->oper)
     110          32 :             return (ao->oper > bo->oper) ? -1 : 1;
     111             : 
     112         344 :         if (an->nchild != bn->nchild)
     113          72 :             return (an->nchild > bn->nchild) ? -1 : 1;
     114             : 
     115             :         {
     116             :             int         i,
     117             :                         res;
     118             : 
     119         412 :             for (i = 0; i < an->nchild; i++)
     120         342 :                 if ((res = QTNodeCompare(an->child[i], bn->child[i])) != 0)
     121         202 :                     return res;
     122             :         }
     123             : 
     124          70 :         if (ao->oper == OP_PHRASE && ao->distance != bo->distance)
     125           4 :             return (ao->distance > bo->distance) ? -1 : 1;
     126             : 
     127          66 :         return 0;
     128             :     }
     129        2278 :     else if (an->valnode->type == QI_VAL)
     130             :     {
     131        2278 :         QueryOperand *ao = &an->valnode->qoperand;
     132        2278 :         QueryOperand *bo = &bn->valnode->qoperand;
     133             : 
     134        2278 :         if (ao->valcrc != bo->valcrc)
     135             :         {
     136        1926 :             return (ao->valcrc > bo->valcrc) ? -1 : 1;
     137             :         }
     138             : 
     139         352 :         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        2752 : cmpQTN(const void *a, const void *b)
     153             : {
     154        2752 :     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        6344 : QTNSort(QTNode *in)
     163             : {
     164             :     int         i;
     165             : 
     166             :     /* since this function recurses, it could be driven to stack overflow. */
     167        6344 :     check_stack_depth();
     168             : 
     169        6344 :     if (in->valnode->type != QI_OPR)
     170        4136 :         return;
     171             : 
     172        7292 :     for (i = 0; i < in->nchild; i++)
     173        5084 :         QTNSort(in->child[i]);
     174        2208 :     if (in->nchild > 1 && in->valnode->qoperator.oper != OP_PHRASE)
     175        1864 :         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         108 : QTNEq(QTNode *a, QTNode *b)
     183             : {
     184         108 :     uint32      sign = a->sign & b->sign;
     185             : 
     186         108 :     if (!(sign == a->sign && sign == b->sign))
     187           4 :         return false;
     188             : 
     189         104 :     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        5832 : QTNTernary(QTNode *in)
     201             : {
     202             :     int         i;
     203             : 
     204             :     /* since this function recurses, it could be driven to stack overflow. */
     205        5832 :     check_stack_depth();
     206             : 
     207        5832 :     if (in->valnode->type != QI_OPR)
     208        3692 :         return;
     209             : 
     210        6764 :     for (i = 0; i < in->nchild; i++)
     211        4624 :         QTNTernary(in->child[i]);
     212             : 
     213             :     /* Only AND and OR are associative, so don't flatten other node types */
     214        2996 :     if (in->valnode->qoperator.oper != OP_AND &&
     215         856 :         in->valnode->qoperator.oper != OP_OR)
     216         344 :         return;
     217             : 
     218        5748 :     for (i = 0; i < in->nchild; i++)
     219             :     {
     220        3952 :         QTNode     *cc = in->child[i];
     221             : 
     222        4988 :         if (cc->valnode->type == QI_OPR &&
     223        1036 :             in->valnode->qoperator.oper == cc->valnode->qoperator.oper)
     224             :         {
     225         244 :             int         oldnchild = in->nchild;
     226             : 
     227         244 :             in->nchild += cc->nchild - 1;
     228         244 :             in->child = (QTNode **) repalloc(in->child, in->nchild * sizeof(QTNode *));
     229             : 
     230         244 :             if (i + 1 != oldnchild)
     231          48 :                 memmove(in->child + i + cc->nchild, in->child + i + 1,
     232          48 :                         (oldnchild - i - 1) * sizeof(QTNode *));
     233             : 
     234         244 :             memcpy(in->child + i, cc->child, cc->nchild * sizeof(QTNode *));
     235         244 :             i += cc->nchild - 1;
     236             : 
     237         244 :             if (cc->flags & QTN_NEEDFREE)
     238          72 :                 pfree(cc->valnode);
     239         244 :             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         788 : QTNBinary(QTNode *in)
     250             : {
     251             :     int         i;
     252             : 
     253             :     /* since this function recurses, it could be driven to stack overflow. */
     254         788 :     check_stack_depth();
     255             : 
     256         788 :     if (in->valnode->type != QI_OPR)
     257         484 :         return;
     258             : 
     259         976 :     for (i = 0; i < in->nchild; i++)
     260         672 :         QTNBinary(in->child[i]);
     261             : 
     262         688 :     while (in->nchild > 2)
     263             :     {
     264          80 :         QTNode     *nn = (QTNode *) palloc0(sizeof(QTNode));
     265             : 
     266          80 :         nn->valnode = (QueryItem *) palloc0(sizeof(QueryItem));
     267          80 :         nn->child = (QTNode **) palloc0(sizeof(QTNode *) * 2);
     268             : 
     269          80 :         nn->nchild = 2;
     270          80 :         nn->flags = QTN_NEEDFREE;
     271             : 
     272          80 :         nn->child[0] = in->child[0];
     273          80 :         nn->child[1] = in->child[1];
     274          80 :         nn->sign = nn->child[0]->sign | nn->child[1]->sign;
     275             : 
     276          80 :         nn->valnode->type = in->valnode->type;
     277          80 :         nn->valnode->qoperator.oper = in->valnode->qoperator.oper;
     278             : 
     279          80 :         in->child[0] = nn;
     280          80 :         in->child[1] = in->child[in->nchild - 1];
     281          80 :         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        1284 : cntsize(QTNode *in, int *sumlen, int *nnode)
     292             : {
     293             :     /* since this function recurses, it could be driven to stack overflow. */
     294        1284 :     check_stack_depth();
     295             : 
     296        1284 :     *nnode += 1;
     297        1284 :     if (in->valnode->type == QI_OPR)
     298             :     {
     299             :         int         i;
     300             : 
     301        1660 :         for (i = 0; i < in->nchild; i++)
     302        1096 :             cntsize(in->child[i], sumlen, nnode);
     303             :     }
     304             :     else
     305             :     {
     306         720 :         *sumlen += in->valnode->qoperand.length + 1;
     307             :     }
     308        1284 : }
     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        1284 : fillQT(QTN2QTState *state, QTNode *in)
     323             : {
     324             :     /* since this function recurses, it could be driven to stack overflow. */
     325        1284 :     check_stack_depth();
     326             : 
     327        1284 :     if (in->valnode->type == QI_VAL)
     328             :     {
     329         720 :         memcpy(state->curitem, in->valnode, sizeof(QueryOperand));
     330             : 
     331         720 :         memcpy(state->curoperand, in->word, in->valnode->qoperand.length);
     332         720 :         state->curitem->qoperand.distance = state->curoperand - state->operand;
     333         720 :         state->curoperand[in->valnode->qoperand.length] = '\0';
     334         720 :         state->curoperand += in->valnode->qoperand.length + 1;
     335         720 :         state->curitem++;
     336             :     }
     337             :     else
     338             :     {
     339         564 :         QueryItem  *curitem = state->curitem;
     340             : 
     341             :         Assert(in->valnode->type == QI_OPR);
     342             : 
     343         564 :         memcpy(state->curitem, in->valnode, sizeof(QueryOperator));
     344             : 
     345             :         Assert(in->nchild <= 2);
     346         564 :         state->curitem++;
     347             : 
     348         564 :         fillQT(state, in->child[0]);
     349             : 
     350         564 :         if (in->nchild == 2)
     351             :         {
     352         532 :             curitem->qoperator.left = state->curitem - curitem;
     353         532 :             fillQT(state, in->child[1]);
     354             :         }
     355             :     }
     356        1284 : }
     357             : 
     358             : /*
     359             :  * Build flat tsquery from a QTNode tree.
     360             :  */
     361             : TSQuery
     362         188 : QTN2QT(QTNode *in)
     363             : {
     364             :     TSQuery     out;
     365             :     int         len;
     366         188 :     int         sumlen = 0,
     367         188 :                 nnode = 0;
     368             :     QTN2QTState state;
     369             : 
     370         188 :     cntsize(in, &sumlen, &nnode);
     371             : 
     372         188 :     if (TSQUERY_TOO_BIG(nnode, sumlen))
     373           0 :         ereport(ERROR,
     374             :                 (errcode(ERRCODE_PROGRAM_LIMIT_EXCEEDED),
     375             :                  errmsg("tsquery is too large")));
     376         188 :     len = COMPUTESIZE(nnode, sumlen);
     377             : 
     378         188 :     out = (TSQuery) palloc0(len);
     379         188 :     SET_VARSIZE(out, len);
     380         188 :     out->size = nnode;
     381             : 
     382         188 :     state.curitem = GETQUERY(out);
     383         188 :     state.operand = state.curoperand = GETOPERAND(out);
     384             : 
     385         188 :     fillQT(&state, in);
     386         188 :     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         680 : QTNCopy(QTNode *in)
     396             : {
     397             :     QTNode     *out;
     398             : 
     399             :     /* since this function recurses, it could be driven to stack overflow. */
     400         680 :     check_stack_depth();
     401             : 
     402         680 :     out = (QTNode *) palloc(sizeof(QTNode));
     403             : 
     404         680 :     *out = *in;
     405         680 :     out->valnode = (QueryItem *) palloc(sizeof(QueryItem));
     406         680 :     *(out->valnode) = *(in->valnode);
     407         680 :     out->flags |= QTN_NEEDFREE;
     408             : 
     409         680 :     if (in->valnode->type == QI_VAL)
     410             :     {
     411         408 :         out->word = palloc(in->valnode->qoperand.length + 1);
     412         408 :         memcpy(out->word, in->word, in->valnode->qoperand.length);
     413         408 :         out->word[in->valnode->qoperand.length] = '\0';
     414         408 :         out->flags |= QTN_WORDFREE;
     415             :     }
     416             :     else
     417             :     {
     418             :         int         i;
     419             : 
     420         272 :         out->child = (QTNode **) palloc(sizeof(QTNode *) * in->nchild);
     421             : 
     422         812 :         for (i = 0; i < in->nchild; i++)
     423         540 :             out->child[i] = QTNCopy(in->child[i]);
     424             :     }
     425             : 
     426         680 :     return out;
     427             : }
     428             : 
     429             : /*
     430             :  * Clear the specified flag bit(s) in all nodes of a QTNode tree.
     431             :  */
     432             : void
     433        3496 : QTNClearFlags(QTNode *in, uint32 flags)
     434             : {
     435             :     /* since this function recurses, it could be driven to stack overflow. */
     436        3496 :     check_stack_depth();
     437             : 
     438        3496 :     in->flags &= ~flags;
     439             : 
     440        3496 :     if (in->valnode->type != QI_VAL)
     441             :     {
     442             :         int         i;
     443             : 
     444        4272 :         for (i = 0; i < in->nchild; i++)
     445        2968 :             QTNClearFlags(in->child[i], flags);
     446             :     }
     447        3496 : }

Generated by: LCOV version 1.13