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