contrib/ltree/lquery_op.c

   1 /*
   2  * op function for ltree and lquery
   3  * Teodor Sigaev <teodor@stack.net>
   4  * contrib/ltree/lquery_op.c
   5  */
   6 #include "postgres.h"
   7
   8 #include <ctype.h>
   9
  10 #include "catalog/pg_collation.h"
  11 #include "ltree.h"
  12 #include "miscadmin.h"
  13 #include "utils/array.h"
  14 #include "utils/formatting.h"
  15
  16 PG_FUNCTION_INFO_V1(ltq_regex);
  17 PG_FUNCTION_INFO_V1(ltq_rregex);
  18
  19 PG_FUNCTION_INFO_V1(lt_q_regex);
  20 PG_FUNCTION_INFO_V1(lt_q_rregex);
  21
  22 #define NEXTVAL(x) ( (lquery*)( (char*)(x) + INTALIGN( VARSIZE(x) ) ) )
  23
  24 static char *
  25 getlexeme(char *start, char *end, int *len)
  26 {
  27         char       *ptr;
  28         int                     charlen;
  29
  30         while (start < end && (charlen = pg_mblen(start)) == 1 && t_iseq(start, '_'))
  31                 start += charlen;
  32
  33         ptr = start;
  34         if (ptr >= end)
  35                 return NULL;
  36
  37         while (ptr < end && !((charlen = pg_mblen(ptr)) == 1 && t_iseq(ptr, '_')))
  38                 ptr += charlen;
  39
  40         *len = ptr - start;
  41         return start;
  42 }
  43
  44 bool
  45 compare_subnode(ltree_level *t, char *qn, int len, int (*cmpptr) (const char *, const char *, size_t), bool anyend)
  46 {
  47         char       *endt = t->name + t->len;
  48         char       *endq = qn + len;
  49         char       *tn;
  50         int                     lent,
  51                                 lenq;
  52         bool            isok;
  53
  54         while ((qn = getlexeme(qn, endq, &lenq)) != NULL)
  55         {
  56                 tn = t->name;
  57                 isok = false;
  58                 while ((tn = getlexeme(tn, endt, &lent)) != NULL)
  59                 {
  60                         if ((lent == lenq || (lent > lenq && anyend)) &&
  61                                 (*cmpptr) (qn, tn, lenq) == 0)
  62                         {
  63
  64                                 isok = true;
  65                                 break;
  66                         }
  67                         tn += lent;
  68                 }
  69
  70                 if (!isok)
  71                         return false;
  72                 qn += lenq;
  73         }
  74
  75         return true;
  76 }
  77
  78 int
  79 ltree_strncasecmp(const char *a, const char *b, size_t s)
  80 {
  81         char       *al = str_tolower(a, s, DEFAULT_COLLATION_OID);
  82         char       *bl = str_tolower(b, s, DEFAULT_COLLATION_OID);
  83         int                     res;
  84
  85         res = strncmp(al, bl, s);
  86
  87         pfree(al);
  88         pfree(bl);
  89
  90         return res;
  91 }
  92
  93 /*
  94  * See if an lquery_level matches an ltree_level
  95  *
  96  * This accounts for all flags including LQL_NOT, but does not
  97  * consider repetition counts.
  98  */
  99 static bool
 100 checkLevel(lquery_level *curq, ltree_level *curt)
 101 {
 102         lquery_variant *curvar = LQL_FIRST(curq);
 103         bool            success;
 104
 105         success = (curq->flag & LQL_NOT) ? false : true;
 106
 107         /* numvar == 0 means '*' which matches anything */
 108         if (curq->numvar == 0)
 109                 return success;
 110
 111         for (int i = 0; i < curq->numvar; i++)
 112         {
 113                 int                     (*cmpptr) (const char *, const char *, size_t);
 114
 115                 cmpptr = (curvar->flag & LVAR_INCASE) ? ltree_strncasecmp : strncmp;
 116
 117                 if (curvar->flag & LVAR_SUBLEXEME)
 118                 {
 119                         if (compare_subnode(curt, curvar->name, curvar->len, cmpptr,
 120                                                                 (curvar->flag & LVAR_ANYEND)))
 121                                 return success;
 122                 }
 123                 else if ((curvar->len == curt->len ||
 124                                   (curt->len > curvar->len && (curvar->flag & LVAR_ANYEND))) &&
 125                                  (*cmpptr) (curvar->name, curt->name, curvar->len) == 0)
 126                         return success;
 127
 128                 curvar = LVAR_NEXT(curvar);
 129         }
 130         return !success;
 131 }
 132
 133 /*
 134  * Try to match an lquery (of qlen items) to an ltree (of tlen items)
 135  */
 136 static bool
 137 checkCond(lquery_level *curq, int qlen,
 138                   ltree_level *curt, int tlen)
 139 {
 140         /* Since this function recurses, it could be driven to stack overflow */
 141         check_stack_depth();
 142
 143         /* Pathological patterns could take awhile, too */
 144         CHECK_FOR_INTERRUPTS();
 145
 146         /* Loop while we have query items to consider */
 147         while (qlen > 0)
 148         {
 149                 int                     low,
 150                                         high;
 151                 lquery_level *nextq;
 152
 153                 /*
 154                  * Get min and max repetition counts for this query item, dealing with
 155                  * the backwards-compatibility hack that the low/high fields aren't
 156                  * meaningful for non-'*' items unless LQL_COUNT is set.
 157                  */
 158                 if ((curq->flag & LQL_COUNT) || curq->numvar == 0)
 159                         low = curq->low, high = curq->high;
 160                 else
 161                         low = high = 1;
 162
 163                 /*
 164                  * We may limit "high" to the remaining text length; this avoids
 165                  * separate tests below.
 166                  */
 167                 if (high > tlen)
 168                         high = tlen;
 169
 170                 /* Fail if a match of required number of items is impossible */
 171                 if (high < low)
 172                         return false;
 173
 174                 /*
 175                  * Recursively check the rest of the pattern against each possible
 176                  * start point following some of this item's match(es).
 177                  */
 178                 nextq = LQL_NEXT(curq);
 179                 qlen--;
 180
 181                 for (int matchcnt = 0; matchcnt < high; matchcnt++)
 182                 {
 183                         /*
 184                          * If we've consumed an acceptable number of matches of this item,
 185                          * and the rest of the pattern matches beginning here, we're good.
 186                          */
 187                         if (matchcnt >= low && checkCond(nextq, qlen, curt, tlen))
 188                                 return true;
 189
 190                         /*
 191                          * Otherwise, try to match one more text item to this query item.
 192                          */
 193                         if (!checkLevel(curq, curt))
 194                                 return false;
 195
 196                         curt = LEVEL_NEXT(curt);
 197                         tlen--;
 198                 }
 199
 200                 /*
 201                  * Once we've consumed "high" matches, we can succeed only if the rest
 202                  * of the pattern matches beginning here.  Loop around (if you prefer,
 203                  * think of this as tail recursion).
 204                  */
 205                 curq = nextq;
 206         }
 207
 208         /*
 209          * Once we're out of query items, we match only if there's no remaining
 210          * text either.
 211          */
 212         return (tlen == 0);
 213 }
 214
 215 Datum
 216 ltq_regex(PG_FUNCTION_ARGS)
 217 {
 218         ltree      *tree = PG_GETARG_LTREE_P(0);
 219         lquery     *query = PG_GETARG_LQUERY_P(1);
 220         bool            res;
 221
 222         res = checkCond(LQUERY_FIRST(query), query->numlevel,
 223                                         LTREE_FIRST(tree), tree->numlevel);
 224
 225         PG_FREE_IF_COPY(tree, 0);
 226         PG_FREE_IF_COPY(query, 1);
 227         PG_RETURN_BOOL(res);
 228 }
 229
 230 Datum
 231 ltq_rregex(PG_FUNCTION_ARGS)
 232 {
 233         PG_RETURN_DATUM(DirectFunctionCall2(ltq_regex,
 234                                                                                 PG_GETARG_DATUM(1),
 235                                                                                 PG_GETARG_DATUM(0)
 236                                                                                 ));
 237 }
 238
 239 Datum
 240 lt_q_regex(PG_FUNCTION_ARGS)
 241 {
 242         ltree      *tree = PG_GETARG_LTREE_P(0);
 243         ArrayType  *_query = PG_GETARG_ARRAYTYPE_P(1);
 244         lquery     *query = (lquery *) ARR_DATA_PTR(_query);
 245         bool            res = false;
 246         int                     num = ArrayGetNItems(ARR_NDIM(_query), ARR_DIMS(_query));
 247
 248         if (ARR_NDIM(_query) > 1)
 249                 ereport(ERROR,
 250                                 (errcode(ERRCODE_ARRAY_SUBSCRIPT_ERROR),
 251                                  errmsg("array must be one-dimensional")));
 252         if (array_contains_nulls(_query))
 253                 ereport(ERROR,
 254                                 (errcode(ERRCODE_NULL_VALUE_NOT_ALLOWED),
 255                                  errmsg("array must not contain nulls")));
 256
 257         while (num > 0)
 258         {
 259                 if (DatumGetBool(DirectFunctionCall2(ltq_regex,
 260                                                                                          PointerGetDatum(tree), PointerGetDatum(query))))
 261                 {
 262
 263                         res = true;
 264                         break;
 265                 }
 266                 num--;
 267                 query = NEXTVAL(query);
 268         }
 269
 270         PG_FREE_IF_COPY(tree, 0);
 271         PG_FREE_IF_COPY(_query, 1);
 272         PG_RETURN_BOOL(res);
 273 }
 274
 275 Datum
 276 lt_q_rregex(PG_FUNCTION_ARGS)
 277 {
 278         PG_RETURN_DATUM(DirectFunctionCall2(lt_q_regex,
 279                                                                                 PG_GETARG_DATUM(1),
 280                                                                                 PG_GETARG_DATUM(0)
 281                                                                                 ));
 282 }