src/backend/utils/adt/tsquery_cleanup.c

   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-2008, PostgreSQL Global Development Group
   8  *
   9  *
  10  * IDENTIFICATION
  11  *        $PostgreSQL$
  12  *
  13  *-------------------------------------------------------------------------
  14  */
  15
  16 #include "postgres.h"
  17
  18 #include "tsearch/ts_type.h"
  19 #include "tsearch/ts_utils.h"
  20 #include "miscadmin.h"
  21
  22 typedef struct NODE
  23 {
  24         struct NODE *left;
  25         struct NODE *right;
  26         QueryItem  *valnode;
  27 } NODE;
  28
  29 /*
  30  * make query tree from plain view of query
  31  */
  32 static NODE *
  33 maketree(QueryItem *in)
  34 {
  35         NODE       *node = (NODE *) palloc(sizeof(NODE));
  36
  37         node->valnode = in;
  38         node->right = node->left = NULL;
  39         if (in->type == QI_OPR)
  40         {
  41                 node->right = maketree(in + 1);
  42                 if (in->operator.oper != OP_NOT)
  43                         node->left = maketree(in + in->operator.left);
  44         }
  45         return node;
  46 }
  47
  48 /*
  49  * Internal state for plaintree and plainnode
  50  */
  51 typedef struct
  52 {
  53         QueryItem  *ptr;
  54         int                     len;                    /* allocated size of ptr */
  55         int                     cur;                    /* number of elements in ptr */
  56 } PLAINTREE;
  57
  58 static void
  59 plainnode(PLAINTREE *state, NODE *node)
  60 {
  61         /* since this function recurses, it could be driven to stack overflow. */
  62         check_stack_depth();
  63
  64         if (state->cur == state->len)
  65         {
  66                 state->len *= 2;
  67                 state->ptr = (QueryItem *) repalloc((void *) state->ptr, state->len * sizeof(QueryItem));
  68         }
  69         memcpy((void *) &(state->ptr[state->cur]), (void *) node->valnode, sizeof(QueryItem));
  70         if (node->valnode->type == QI_VAL)
  71                 state->cur++;
  72         else if (node->valnode->operator.oper == OP_NOT)
  73         {
  74                 state->ptr[state->cur].operator.left = 1;
  75                 state->cur++;
  76                 plainnode(state, node->right);
  77         }
  78         else
  79         {
  80                 int                     cur = state->cur;
  81
  82                 state->cur++;
  83                 plainnode(state, node->right);
  84                 state->ptr[cur].operator.left = state->cur - cur;
  85                 plainnode(state, node->left);
  86         }
  87         pfree(node);
  88 }
  89
  90 /*
  91  * make plain view of tree from a NODE-tree representation
  92  */
  93 static QueryItem *
  94 plaintree(NODE *root, int *len)
  95 {
  96         PLAINTREE       pl;
  97
  98         pl.cur = 0;
  99         pl.len = 16;
 100         if (root && (root->valnode->type == QI_VAL || root->valnode->type == QI_OPR))
 101         {
 102                 pl.ptr = (QueryItem *) palloc(pl.len * sizeof(QueryItem));
 103                 plainnode(&pl, root);
 104         }
 105         else
 106                 pl.ptr = NULL;
 107         *len = pl.cur;
 108         return pl.ptr;
 109 }
 110
 111 static void
 112 freetree(NODE *node)
 113 {
 114         /* since this function recurses, it could be driven to stack overflow. */
 115         check_stack_depth();
 116
 117         if (!node)
 118                 return;
 119         if (node->left)
 120                 freetree(node->left);
 121         if (node->right)
 122                 freetree(node->right);
 123         pfree(node);
 124 }
 125
 126 /*
 127  * clean tree for ! operator.
 128  * It's usefull for debug, but in
 129  * other case, such view is used with search in index.
 130  * Operator ! always return TRUE
 131  */
 132 static NODE *
 133 clean_NOT_intree(NODE *node)
 134 {
 135         /* since this function recurses, it could be driven to stack overflow. */
 136         check_stack_depth();
 137
 138         if (node->valnode->type == QI_VAL)
 139                 return node;
 140
 141         if (node->valnode->operator.oper == OP_NOT)
 142         {
 143                 freetree(node);
 144                 return NULL;
 145         }
 146
 147         /* operator & or | */
 148         if (node->valnode->operator.oper == OP_OR)
 149         {
 150                 if ((node->left = clean_NOT_intree(node->left)) == NULL ||
 151                         (node->right = clean_NOT_intree(node->right)) == NULL)
 152                 {
 153                         freetree(node);
 154                         return NULL;
 155                 }
 156         }
 157         else
 158         {
 159                 NODE       *res = node;
 160
 161                 Assert(node->valnode->operator.oper == OP_AND);
 162
 163                 node->left = clean_NOT_intree(node->left);
 164                 node->right = clean_NOT_intree(node->right);
 165                 if (node->left == NULL && node->right == NULL)
 166                 {
 167                         pfree(node);
 168                         res = NULL;
 169                 }
 170                 else if (node->left == NULL)
 171                 {
 172                         res = node->right;
 173                         pfree(node);
 174                 }
 175                 else if (node->right == NULL)
 176                 {
 177                         res = node->left;
 178                         pfree(node);
 179                 }
 180                 return res;
 181         }
 182         return node;
 183 }
 184
 185 QueryItem *
 186 clean_NOT(QueryItem *ptr, int *len)
 187 {
 188         NODE       *root = maketree(ptr);
 189
 190         return plaintree(clean_NOT_intree(root), len);
 191 }
 192
 193
 194 #ifdef V_UNKNOWN                                /* exists in Windows headers */
 195 #undef V_UNKNOWN
 196 #endif
 197 #ifdef V_FALSE                                  /* exists in Solaris headers */
 198 #undef V_FALSE
 199 #endif
 200
 201 /*
 202  * output values for result output parameter of clean_fakeval_intree
 203  */
 204 #define V_UNKNOWN       0                       /* the expression can't be evaluated
 205                                                                  * statically */
 206 #define V_TRUE          1                       /* the expression is always true (not
 207                                                                  * implemented) */
 208 #define V_FALSE         2                       /* the expression is always false (not
 209                                                                  * implemented) */
 210 #define V_STOP          3                       /* the expression is a stop word */
 211
 212 /*
 213  * Clean query tree from values which is always in
 214  * text (stopword)
 215  */
 216 static NODE *
 217 clean_fakeval_intree(NODE *node, char *result)
 218 {
 219         char            lresult = V_UNKNOWN,
 220                                 rresult = V_UNKNOWN;
 221
 222         /* since this function recurses, it could be driven to stack overflow. */
 223         check_stack_depth();
 224
 225         if (node->valnode->type == QI_VAL)
 226                 return node;
 227         else if (node->valnode->type == QI_VALSTOP)
 228         {
 229                 pfree(node);
 230                 *result = V_STOP;
 231                 return NULL;
 232         }
 233
 234         Assert(node->valnode->type == QI_OPR);
 235
 236         if (node->valnode->operator.oper == OP_NOT)
 237         {
 238                 node->right = clean_fakeval_intree(node->right, &rresult);
 239                 if (!node->right)
 240                 {
 241                         *result = V_STOP;
 242                         freetree(node);
 243                         return NULL;
 244                 }
 245         }
 246         else
 247         {
 248                 NODE       *res = node;
 249
 250                 node->left = clean_fakeval_intree(node->left, &lresult);
 251                 node->right = clean_fakeval_intree(node->right, &rresult);
 252
 253                 if (lresult == V_STOP && rresult == V_STOP)
 254                 {
 255                         freetree(node);
 256                         *result = V_STOP;
 257                         return NULL;
 258                 }
 259                 else if (lresult == V_STOP)
 260                 {
 261                         res = node->right;
 262                         pfree(node);
 263                 }
 264                 else if (rresult == V_STOP)
 265                 {
 266                         res = node->left;
 267                         pfree(node);
 268                 }
 269                 return res;
 270         }
 271         return node;
 272 }
 273
 274 QueryItem *
 275 clean_fakeval(QueryItem *ptr, int *len)
 276 {
 277         NODE       *root = maketree(ptr);
 278         char            result = V_UNKNOWN;
 279         NODE       *resroot;
 280
 281         resroot = clean_fakeval_intree(root, &result);
 282         if (result != V_UNKNOWN)
 283         {
 284                 ereport(NOTICE,
 285                                 (errmsg("text-search query contains only stop words or doesn't contain lexemes, ignored")));
 286                 *len = 0;
 287                 return NULL;
 288         }
 289
 290         return plaintree(resroot, len);
 291 }