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,
45 : ltree_prefix_eq_func prefix_eq, bool anyend)
46 : {
47 16 : char *endt = t->name + t->len;
48 16 : char *endq = qn + len;
49 : char *tn;
50 : int lent,
51 : lenq;
52 : bool isok;
53 :
54 32 : while ((qn = getlexeme(qn, endq, &lenq)) != NULL)
55 : {
56 24 : tn = t->name;
57 24 : isok = false;
58 40 : while ((tn = getlexeme(tn, endt, &lent)) != NULL)
59 : {
60 64 : if ((lent == lenq || (lent > lenq && anyend)) &&
61 32 : (*prefix_eq) (qn, lenq, tn, lent))
62 : {
63 :
64 16 : isok = true;
65 16 : break;
66 : }
67 16 : tn += lent;
68 : }
69 :
70 24 : if (!isok)
71 8 : return false;
72 16 : qn += lenq;
73 : }
74 :
75 8 : return true;
76 : }
77 :
78 : /*
79 : * Check if 'a' is a prefix of 'b'.
80 : */
81 : bool
82 188244 : ltree_prefix_eq(const char *a, size_t a_sz, const char *b, size_t b_sz)
83 : {
84 188244 : if (a_sz > b_sz)
85 0 : return false;
86 : else
87 188244 : return (strncmp(a, b, a_sz) == 0);
88 : }
89 :
90 : /*
91 : * Case-insensitive check if 'a' is a prefix of 'b'.
92 : */
93 : bool
94 52 : ltree_prefix_eq_ci(const char *a, size_t a_sz, const char *b, size_t b_sz)
95 : {
96 : static pg_locale_t locale = NULL;
97 52 : size_t al_sz = a_sz + 1;
98 : size_t al_len;
99 52 : char *al = palloc(al_sz);
100 52 : size_t bl_sz = b_sz + 1;
101 : size_t bl_len;
102 52 : char *bl = palloc(bl_sz);
103 : bool res;
104 :
105 52 : if (!locale)
106 2 : locale = pg_database_locale();
107 :
108 : /* casefold both a and b */
109 :
110 52 : al_len = pg_strfold(al, al_sz, a, a_sz, locale);
111 52 : if (al_len + 1 > al_sz)
112 : {
113 : /* grow buffer if needed and retry */
114 0 : al_sz = al_len + 1;
115 0 : al = repalloc(al, al_sz);
116 0 : al_len = pg_strfold(al, al_sz, a, a_sz, locale);
117 : Assert(al_len + 1 <= al_sz);
118 : }
119 :
120 52 : bl_len = pg_strfold(bl, bl_sz, b, b_sz, locale);
121 52 : if (bl_len + 1 > bl_sz)
122 : {
123 : /* grow buffer if needed and retry */
124 0 : bl_sz = bl_len + 1;
125 0 : bl = repalloc(bl, bl_sz);
126 0 : bl_len = pg_strfold(bl, bl_sz, b, b_sz, locale);
127 : Assert(bl_len + 1 <= bl_sz);
128 : }
129 :
130 52 : if (al_len > bl_len)
131 0 : res = false;
132 : else
133 52 : res = (strncmp(al, bl, al_len) == 0);
134 :
135 52 : pfree(al);
136 52 : pfree(bl);
137 :
138 52 : return res;
139 : }
140 :
141 : /*
142 : * See if an lquery_level matches an ltree_level
143 : *
144 : * This accounts for all flags including LQL_NOT, but does not
145 : * consider repetition counts.
146 : */
147 : static bool
148 433726 : checkLevel(lquery_level *curq, ltree_level *curt)
149 : {
150 433726 : lquery_variant *curvar = LQL_FIRST(curq);
151 : bool success;
152 :
153 433726 : success = (curq->flag & LQL_NOT) ? false : true;
154 :
155 : /* numvar == 0 means '*' which matches anything */
156 433726 : if (curq->numvar == 0)
157 166390 : return success;
158 :
159 521574 : for (int i = 0; i < curq->numvar; i++)
160 : {
161 : ltree_prefix_eq_func prefix_eq;
162 :
163 267346 : prefix_eq = (curvar->flag & LVAR_INCASE) ? ltree_prefix_eq_ci : ltree_prefix_eq;
164 :
165 267346 : if (curvar->flag & LVAR_SUBLEXEME)
166 : {
167 8 : if (compare_subnode(curt, curvar->name, curvar->len, prefix_eq,
168 8 : (curvar->flag & LVAR_ANYEND)))
169 6 : return success;
170 : }
171 267338 : else if ((curvar->len == curt->len ||
172 267344 : (curt->len > curvar->len && (curvar->flag & LVAR_ANYEND))) &&
173 110052 : (*prefix_eq) (curvar->name, curvar->len, curt->name, curt->len))
174 13102 : return success;
175 :
176 254238 : curvar = LVAR_NEXT(curvar);
177 : }
178 254228 : return !success;
179 : }
180 :
181 : /*
182 : * Try to match an lquery (of qlen items) to an ltree (of tlen items)
183 : */
184 : static bool
185 287068 : checkCond(lquery_level *curq, int qlen,
186 : ltree_level *curt, int tlen)
187 : {
188 : /* Since this function recurses, it could be driven to stack overflow */
189 287068 : check_stack_depth();
190 :
191 : /* Pathological patterns could take awhile, too */
192 287068 : CHECK_FOR_INTERRUPTS();
193 :
194 : /* Loop while we have query items to consider */
195 325626 : while (qlen > 0)
196 : {
197 : int low,
198 : high;
199 : lquery_level *nextq;
200 :
201 : /*
202 : * Get min and max repetition counts for this query item, dealing with
203 : * the backwards-compatibility hack that the low/high fields aren't
204 : * meaningful for non-'*' items unless LQL_COUNT is set.
205 : */
206 318200 : if ((curq->flag & LQL_COUNT) || curq->numvar == 0)
207 26614 : low = curq->low, high = curq->high;
208 : else
209 291586 : low = high = 1;
210 :
211 : /*
212 : * We may limit "high" to the remaining text length; this avoids
213 : * separate tests below.
214 : */
215 318200 : if (high > tlen)
216 49976 : high = tlen;
217 :
218 : /* Fail if a match of required number of items is impossible */
219 318200 : if (high < low)
220 24346 : return false;
221 :
222 : /*
223 : * Recursively check the rest of the pattern against each possible
224 : * start point following some of this item's match(es).
225 : */
226 293854 : nextq = LQL_NEXT(curq);
227 293854 : qlen--;
228 :
229 473472 : for (int matchcnt = 0; matchcnt < high; matchcnt++)
230 : {
231 : /*
232 : * If we've consumed an acceptable number of matches of this item,
233 : * and the rest of the pattern matches beginning here, we're good.
234 : */
235 434914 : if (matchcnt >= low && checkCond(nextq, qlen, curt, tlen))
236 1188 : return true;
237 :
238 : /*
239 : * Otherwise, try to match one more text item to this query item.
240 : */
241 433726 : if (!checkLevel(curq, curt))
242 254108 : return false;
243 :
244 179618 : curt = LEVEL_NEXT(curt);
245 179618 : tlen--;
246 : }
247 :
248 : /*
249 : * Once we've consumed "high" matches, we can succeed only if the rest
250 : * of the pattern matches beginning here. Loop around (if you prefer,
251 : * think of this as tail recursion).
252 : */
253 38558 : curq = nextq;
254 : }
255 :
256 : /*
257 : * Once we're out of query items, we match only if there's no remaining
258 : * text either.
259 : */
260 7426 : return (tlen == 0);
261 : }
262 :
263 : Datum
264 120432 : ltq_regex(PG_FUNCTION_ARGS)
265 : {
266 120432 : ltree *tree = PG_GETARG_LTREE_P(0);
267 120432 : lquery *query = PG_GETARG_LQUERY_P(1);
268 : bool res;
269 :
270 120432 : res = checkCond(LQUERY_FIRST(query), query->numlevel,
271 120432 : LTREE_FIRST(tree), tree->numlevel);
272 :
273 120432 : PG_FREE_IF_COPY(tree, 0);
274 120432 : PG_FREE_IF_COPY(query, 1);
275 120432 : PG_RETURN_BOOL(res);
276 : }
277 :
278 : Datum
279 0 : ltq_rregex(PG_FUNCTION_ARGS)
280 : {
281 0 : PG_RETURN_DATUM(DirectFunctionCall2(ltq_regex,
282 : PG_GETARG_DATUM(1),
283 : PG_GETARG_DATUM(0)
284 : ));
285 : }
286 :
287 : Datum
288 3178 : lt_q_regex(PG_FUNCTION_ARGS)
289 : {
290 3178 : ltree *tree = PG_GETARG_LTREE_P(0);
291 3178 : ArrayType *_query = PG_GETARG_ARRAYTYPE_P(1);
292 3178 : lquery *query = (lquery *) ARR_DATA_PTR(_query);
293 3178 : bool res = false;
294 3178 : int num = ArrayGetNItems(ARR_NDIM(_query), ARR_DIMS(_query));
295 :
296 3178 : if (ARR_NDIM(_query) > 1)
297 0 : ereport(ERROR,
298 : (errcode(ERRCODE_ARRAY_SUBSCRIPT_ERROR),
299 : errmsg("array must be one-dimensional")));
300 3178 : if (array_contains_nulls(_query))
301 0 : ereport(ERROR,
302 : (errcode(ERRCODE_NULL_VALUE_NOT_ALLOWED),
303 : errmsg("array must not contain nulls")));
304 :
305 9484 : while (num > 0)
306 : {
307 6334 : if (DatumGetBool(DirectFunctionCall2(ltq_regex,
308 : PointerGetDatum(tree), PointerGetDatum(query))))
309 : {
310 :
311 28 : res = true;
312 28 : break;
313 : }
314 6306 : num--;
315 6306 : query = NEXTVAL(query);
316 : }
317 :
318 3178 : PG_FREE_IF_COPY(tree, 0);
319 3178 : PG_FREE_IF_COPY(_query, 1);
320 3178 : PG_RETURN_BOOL(res);
321 : }
322 :
323 : Datum
324 0 : lt_q_rregex(PG_FUNCTION_ARGS)
325 : {
326 0 : PG_RETURN_DATUM(DirectFunctionCall2(lt_q_regex,
327 : PG_GETARG_DATUM(1),
328 : PG_GETARG_DATUM(0)
329 : ));
330 : }
|
