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 3 : PG_FUNCTION_INFO_V1(ltq_regex);
17 2 : PG_FUNCTION_INFO_V1(ltq_rregex);
18 :
19 3 : PG_FUNCTION_INFO_V1(lt_q_regex);
20 2 : PG_FUNCTION_INFO_V1(lt_q_rregex);
21 :
22 : #define NEXTVAL(x) ( (lquery*)( (char*)(x) + INTALIGN( VARSIZE(x) ) ) )
23 :
24 : static char *
25 36 : getlexeme(char *start, char *end, int *len)
26 : {
27 : char *ptr;
28 :
29 44 : while (start < end && t_iseq(start, '_'))
30 8 : start += pg_mblen_range(start, end);
31 :
32 36 : ptr = start;
33 36 : if (ptr >= end)
34 8 : return NULL;
35 :
36 114 : while (ptr < end && !t_iseq(ptr, '_'))
37 86 : ptr += pg_mblen_range(ptr, end);
38 :
39 28 : *len = ptr - start;
40 28 : return start;
41 : }
42 :
43 : bool
44 8 : compare_subnode(ltree_level *t, char *qn, int len, bool prefix, bool ci)
45 : {
46 8 : char *endt = t->name + t->len;
47 8 : char *endq = qn + len;
48 : char *tn;
49 : int lent,
50 : lenq;
51 : bool isok;
52 :
53 16 : while ((qn = getlexeme(qn, endq, &lenq)) != NULL)
54 : {
55 12 : tn = t->name;
56 12 : isok = false;
57 20 : while ((tn = getlexeme(tn, endt, &lent)) != NULL)
58 : {
59 16 : if (ltree_label_match(qn, lenq, tn, lent, prefix, ci))
60 : {
61 8 : isok = true;
62 8 : break;
63 : }
64 8 : tn += lent;
65 : }
66 :
67 12 : if (!isok)
68 4 : return false;
69 8 : qn += lenq;
70 : }
71 :
72 4 : return true;
73 : }
74 :
75 : /*
76 : * Check if the label matches the predicate string. If 'prefix' is true, then
77 : * the predicate string is treated as a prefix. If 'ci' is true, then the
78 : * predicate string is case-insensitive (and locale-aware).
79 : */
80 : bool
81 197718 : ltree_label_match(const char *pred, size_t pred_len, const char *label,
82 : size_t label_len, bool prefix, bool ci)
83 : {
84 : static pg_locale_t locale = NULL;
85 : char *fpred; /* casefolded predicate */
86 197718 : size_t fpred_len = pred_len;
87 : char *flabel; /* casefolded label */
88 197718 : size_t flabel_len = label_len;
89 : size_t len;
90 : bool res;
91 :
92 : /* fast path for binary match or binary prefix match */
93 197718 : if ((pred_len == label_len || (prefix && pred_len < label_len)) &&
94 94098 : strncmp(pred, label, pred_len) == 0)
95 9195 : return true;
96 188523 : else if (!ci)
97 188493 : return false;
98 :
99 : /*
100 : * Slow path for case-insensitive comparison: case fold and then compare.
101 : * This path is necessary even if pred_len > label_len, because the byte
102 : * lengths may change after casefolding.
103 : */
104 30 : if (!locale)
105 1 : locale = pg_database_locale();
106 :
107 30 : fpred = palloc(fpred_len + 1);
108 30 : len = pg_strfold(fpred, fpred_len + 1, pred, pred_len, locale);
109 30 : if (len > fpred_len)
110 : {
111 : /* grow buffer if needed and retry */
112 0 : fpred_len = len;
113 0 : fpred = repalloc(fpred, fpred_len + 1);
114 0 : len = pg_strfold(fpred, fpred_len + 1, pred, pred_len, locale);
115 : }
116 : Assert(len <= fpred_len);
117 30 : fpred_len = len;
118 :
119 30 : flabel = palloc(flabel_len + 1);
120 30 : len = pg_strfold(flabel, flabel_len + 1, label, label_len, locale);
121 30 : if (len > flabel_len)
122 : {
123 : /* grow buffer if needed and retry */
124 0 : flabel_len = len;
125 0 : flabel = repalloc(flabel, flabel_len + 1);
126 0 : len = pg_strfold(flabel, flabel_len + 1, label, label_len, locale);
127 : }
128 : Assert(len <= flabel_len);
129 30 : flabel_len = len;
130 :
131 30 : if ((fpred_len == flabel_len || (prefix && fpred_len < flabel_len)) &&
132 25 : strncmp(fpred, flabel, fpred_len) == 0)
133 13 : res = true;
134 : else
135 17 : res = false;
136 :
137 30 : pfree(fpred);
138 30 : pfree(flabel);
139 :
140 30 : return res;
141 : }
142 :
143 : /*
144 : * See if an lquery_level matches an ltree_level
145 : *
146 : * This accounts for all flags including LQL_NOT, but does not
147 : * consider repetition counts.
148 : */
149 : static bool
150 216708 : checkLevel(lquery_level *curq, ltree_level *curt)
151 : {
152 216708 : lquery_variant *curvar = LQL_FIRST(curq);
153 : bool success;
154 :
155 216708 : success = (curq->flag & LQL_NOT) ? false : true;
156 :
157 : /* numvar == 0 means '*' which matches anything */
158 216708 : if (curq->numvar == 0)
159 83195 : return success;
160 :
161 260477 : for (int i = 0; i < curq->numvar; i++)
162 : {
163 133518 : bool prefix = (curvar->flag & LVAR_ANYEND);
164 133518 : bool ci = (curvar->flag & LVAR_INCASE);
165 :
166 133518 : if (curvar->flag & LVAR_SUBLEXEME)
167 : {
168 4 : if (compare_subnode(curt, curvar->name, curvar->len, prefix, ci))
169 3 : return success;
170 : }
171 133514 : else if (ltree_label_match(curvar->name, curvar->len, curt->name,
172 133514 : curt->len, prefix, ci))
173 6551 : return success;
174 :
175 126964 : curvar = LVAR_NEXT(curvar);
176 : }
177 126959 : return !success;
178 : }
179 :
180 : /*
181 : * Try to match an lquery (of qlen items) to an ltree (of tlen items)
182 : */
183 : static bool
184 143379 : checkCond(lquery_level *curq, int qlen,
185 : ltree_level *curt, int tlen)
186 : {
187 : /* Since this function recurses, it could be driven to stack overflow */
188 143379 : check_stack_depth();
189 :
190 : /* Pathological patterns could take awhile, too */
191 143379 : CHECK_FOR_INTERRUPTS();
192 :
193 : /* Loop while we have query items to consider */
194 162658 : while (qlen > 0)
195 : {
196 : int low,
197 : high;
198 : lquery_level *nextq;
199 :
200 : /*
201 : * Get min and max repetition counts for this query item, dealing with
202 : * the backwards-compatibility hack that the low/high fields aren't
203 : * meaningful for non-'*' items unless LQL_COUNT is set.
204 : */
205 158945 : if ((curq->flag & LQL_COUNT) || curq->numvar == 0)
206 13307 : low = curq->low, high = curq->high;
207 : else
208 145638 : low = high = 1;
209 :
210 : /*
211 : * We may limit "high" to the remaining text length; this avoids
212 : * separate tests below.
213 : */
214 158945 : if (high > tlen)
215 24988 : high = tlen;
216 :
217 : /* Fail if a match of required number of items is impossible */
218 158945 : if (high < low)
219 12173 : return false;
220 :
221 : /*
222 : * Recursively check the rest of the pattern against each possible
223 : * start point following some of this item's match(es).
224 : */
225 146772 : nextq = LQL_NEXT(curq);
226 146772 : qlen--;
227 :
228 236581 : for (int matchcnt = 0; matchcnt < high; matchcnt++)
229 : {
230 : /*
231 : * If we've consumed an acceptable number of matches of this item,
232 : * and the rest of the pattern matches beginning here, we're good.
233 : */
234 217302 : if (matchcnt >= low && checkCond(nextq, qlen, curt, tlen))
235 594 : return true;
236 :
237 : /*
238 : * Otherwise, try to match one more text item to this query item.
239 : */
240 216708 : if (!checkLevel(curq, curt))
241 126899 : return false;
242 :
243 89809 : curt = LEVEL_NEXT(curt);
244 89809 : tlen--;
245 : }
246 :
247 : /*
248 : * Once we've consumed "high" matches, we can succeed only if the rest
249 : * of the pattern matches beginning here. Loop around (if you prefer,
250 : * think of this as tail recursion).
251 : */
252 19279 : curq = nextq;
253 : }
254 :
255 : /*
256 : * Once we're out of query items, we match only if there's no remaining
257 : * text either.
258 : */
259 3713 : return (tlen == 0);
260 : }
261 :
262 : Datum
263 60061 : ltq_regex(PG_FUNCTION_ARGS)
264 : {
265 60061 : ltree *tree = PG_GETARG_LTREE_P(0);
266 60061 : lquery *query = PG_GETARG_LQUERY_P(1);
267 : bool res;
268 :
269 60061 : res = checkCond(LQUERY_FIRST(query), query->numlevel,
270 60061 : LTREE_FIRST(tree), tree->numlevel);
271 :
272 60061 : PG_FREE_IF_COPY(tree, 0);
273 60061 : PG_FREE_IF_COPY(query, 1);
274 60061 : PG_RETURN_BOOL(res);
275 : }
276 :
277 : Datum
278 0 : ltq_rregex(PG_FUNCTION_ARGS)
279 : {
280 0 : PG_RETURN_DATUM(DirectFunctionCall2(ltq_regex,
281 : PG_GETARG_DATUM(1),
282 : PG_GETARG_DATUM(0)
283 : ));
284 : }
285 :
286 : Datum
287 1558 : lt_q_regex(PG_FUNCTION_ARGS)
288 : {
289 1558 : ltree *tree = PG_GETARG_LTREE_P(0);
290 1558 : ArrayType *_query = PG_GETARG_ARRAYTYPE_P(1);
291 1558 : lquery *query = (lquery *) ARR_DATA_PTR(_query);
292 1558 : bool res = false;
293 1558 : int num = ArrayGetNItems(ARR_NDIM(_query), ARR_DIMS(_query));
294 :
295 1558 : if (ARR_NDIM(_query) > 1)
296 0 : ereport(ERROR,
297 : (errcode(ERRCODE_ARRAY_SUBSCRIPT_ERROR),
298 : errmsg("array must be one-dimensional")));
299 1558 : if (array_contains_nulls(_query))
300 0 : ereport(ERROR,
301 : (errcode(ERRCODE_NULL_VALUE_NOT_ALLOWED),
302 : errmsg("array must not contain nulls")));
303 :
304 4649 : while (num > 0)
305 : {
306 3105 : if (DatumGetBool(DirectFunctionCall2(ltq_regex,
307 : PointerGetDatum(tree), PointerGetDatum(query))))
308 : {
309 :
310 14 : res = true;
311 14 : break;
312 : }
313 3091 : num--;
314 3091 : query = NEXTVAL(query);
315 : }
316 :
317 1558 : PG_FREE_IF_COPY(tree, 0);
318 1558 : PG_FREE_IF_COPY(_query, 1);
319 1558 : PG_RETURN_BOOL(res);
320 : }
321 :
322 : Datum
323 0 : lt_q_rregex(PG_FUNCTION_ARGS)
324 : {
325 0 : PG_RETURN_DATUM(DirectFunctionCall2(lt_q_regex,
326 : PG_GETARG_DATUM(1),
327 : PG_GETARG_DATUM(0)
328 : ));
329 : }
|
