Age Owner Branch data TLA 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 : :
8629 bruce@momjian.us 16 :CBC 3 : PG_FUNCTION_INFO_V1(ltq_regex);
17 : 2 : PG_FUNCTION_INFO_V1(ltq_rregex);
18 : :
8425 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 *
7319 neilc@samurai.com 25 : 36 : getlexeme(char *start, char *end, int *len)
26 : : {
27 : : char *ptr;
28 : :
1256 tgl@sss.pgh.pa.us 29 [ + + + + ]: 44 : while (start < end && t_iseq(start, '_'))
67 tmunro@postgresql.or 30 : 8 : start += pg_mblen_range(start, end);
31 : :
8629 bruce@momjian.us 32 : 36 : ptr = start;
6467 teodor@sigaev.ru 33 [ + + ]: 36 : if (ptr >= end)
8629 bruce@momjian.us 34 : 8 : return NULL;
35 : :
1256 tgl@sss.pgh.pa.us 36 [ + + + + ]: 114 : while (ptr < end && !t_iseq(ptr, '_'))
67 tmunro@postgresql.or 37 : 86 : ptr += pg_mblen_range(ptr, end);
38 : :
8629 bruce@momjian.us 39 : 28 : *len = ptr - start;
40 : 28 : return start;
41 : : }
42 : :
43 : : bool
17 jdavis@postgresql.or 44 : 8 : compare_subnode(ltree_level *t, char *qn, int len, bool prefix, bool ci)
45 : : {
8593 bruce@momjian.us 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 : :
7319 neilc@samurai.com 53 [ + + ]: 16 : while ((qn = getlexeme(qn, endq, &lenq)) != NULL)
54 : : {
8593 bruce@momjian.us 55 : 12 : tn = t->name;
8629 56 : 12 : isok = false;
7319 neilc@samurai.com 57 [ + + ]: 20 : while ((tn = getlexeme(tn, endt, &lent)) != NULL)
58 : : {
17 jdavis@postgresql.or 59 [ + + ]: 16 : if (ltree_label_match(qn, lenq, tn, lent, prefix, ci))
60 : : {
8593 bruce@momjian.us 61 : 8 : isok = true;
8629 62 : 8 : break;
63 : : }
64 : 8 : tn += lent;
65 : : }
66 : :
8593 67 [ + + ]: 12 : if (!isok)
8629 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
17 jdavis@postgresql.or 81 : 197863 : 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 : 197863 : size_t fpred_len = pred_len;
87 : : char *flabel; /* casefolded label */
88 : 197863 : 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 [ + + + + : 197863 : if ((pred_len == label_len || (prefix && pred_len < label_len)) &&
+ - ]
94 [ + + ]: 94223 : strncmp(pred, label, pred_len) == 0)
95 : 9195 : return true;
96 [ + + ]: 188668 : else if (!ci)
97 : 188638 : 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 : : */
89 jdavis@postgresql.or 104 [ + + ]:GNC 30 : if (!locale)
105 : 1 : locale = pg_database_locale();
106 : :
17 jdavis@postgresql.or 107 :CBC 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 */
17 jdavis@postgresql.or 112 :UBC 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 : : }
17 jdavis@postgresql.or 116 [ - + ]:CBC 30 : 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 */
17 jdavis@postgresql.or 124 :UBC 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 : : }
17 jdavis@postgresql.or 128 [ - + ]:CBC 30 : 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 : :
6467 teodor@sigaev.ru 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
6121 bruce@momjian.us 150 : 216853 : checkLevel(lquery_level *curq, ltree_level *curt)
151 : : {
8629 152 : 216853 : lquery_variant *curvar = LQL_FIRST(curq);
153 : : bool success;
154 : :
2175 tgl@sss.pgh.pa.us 155 : 216853 : success = (curq->flag & LQL_NOT) ? false : true;
156 : :
157 : : /* numvar == 0 means '*' which matches anything */
158 [ + + ]: 216853 : if (curq->numvar == 0)
159 : 83195 : return success;
160 : :
161 [ + + ]: 260767 : for (int i = 0; i < curq->numvar; i++)
162 : : {
17 jdavis@postgresql.or 163 : 133663 : bool prefix = (curvar->flag & LVAR_ANYEND);
164 : 133663 : bool ci = (curvar->flag & LVAR_INCASE);
165 : :
7319 neilc@samurai.com 166 [ + + ]: 133663 : if (curvar->flag & LVAR_SUBLEXEME)
167 : : {
17 jdavis@postgresql.or 168 [ + + ]: 4 : if (compare_subnode(curt, curvar->name, curvar->len, prefix, ci))
2175 tgl@sss.pgh.pa.us 169 : 3 : return success;
170 : : }
17 jdavis@postgresql.or 171 [ + + ]: 133659 : else if (ltree_label_match(curvar->name, curvar->len, curt->name,
172 : 133659 : curt->len, prefix, ci))
2175 tgl@sss.pgh.pa.us 173 : 6551 : return success;
174 : :
8593 bruce@momjian.us 175 : 127109 : curvar = LVAR_NEXT(curvar);
176 : : }
2175 tgl@sss.pgh.pa.us 177 : 127104 : 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 : 143524 : 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 : 143524 : check_stack_depth();
189 : :
190 : : /* Pathological patterns could take awhile, too */
191 [ - + ]: 143524 : CHECK_FOR_INTERRUPTS();
192 : :
193 : : /* Loop while we have query items to consider */
194 [ + + ]: 162803 : 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 [ + + + + ]: 159090 : if ((curq->flag & LQL_COUNT) || curq->numvar == 0)
206 : 13307 : low = curq->low, high = curq->high;
207 : : else
208 : 145783 : low = high = 1;
209 : :
210 : : /*
211 : : * We may limit "high" to the remaining text length; this avoids
212 : : * separate tests below.
213 : : */
214 [ + + ]: 159090 : if (high > tlen)
215 : 24988 : high = tlen;
216 : :
217 : : /* Fail if a match of required number of items is impossible */
218 [ + + ]: 159090 : 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 : 146917 : nextq = LQL_NEXT(curq);
8629 bruce@momjian.us 226 : 146917 : qlen--;
227 : :
2175 tgl@sss.pgh.pa.us 228 [ + + ]: 236726 : 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 [ + + + + ]: 217447 : 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 [ + + ]: 216853 : if (!checkLevel(curq, curt))
2178 241 : 127044 : return false;
242 : :
2175 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
8593 bruce@momjian.us 263 : 60206 : ltq_regex(PG_FUNCTION_ARGS)
264 : : {
3100 tgl@sss.pgh.pa.us 265 : 60206 : ltree *tree = PG_GETARG_LTREE_P(0);
266 : 60206 : lquery *query = PG_GETARG_LQUERY_P(1);
267 : : bool res;
268 : :
2175 269 : 60206 : res = checkCond(LQUERY_FIRST(query), query->numlevel,
270 : 60206 : LTREE_FIRST(tree), tree->numlevel);
271 : :
8593 bruce@momjian.us 272 [ + + ]: 60206 : PG_FREE_IF_COPY(tree, 0);
273 [ - + ]: 60206 : PG_FREE_IF_COPY(query, 1);
274 : 60206 : PG_RETURN_BOOL(res);
275 : : }
276 : :
277 : : Datum
8593 bruce@momjian.us 278 :UBC 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
8425 bruce@momjian.us 287 :CBC 1587 : lt_q_regex(PG_FUNCTION_ARGS)
288 : : {
3100 tgl@sss.pgh.pa.us 289 : 1587 : ltree *tree = PG_GETARG_LTREE_P(0);
8259 bruce@momjian.us 290 : 1587 : ArrayType *_query = PG_GETARG_ARRAYTYPE_P(1);
291 [ - + ]: 1587 : lquery *query = (lquery *) ARR_DATA_PTR(_query);
292 : 1587 : bool res = false;
293 : 1587 : int num = ArrayGetNItems(ARR_NDIM(_query), ARR_DIMS(_query));
294 : :
5863 tgl@sss.pgh.pa.us 295 [ - + ]: 1587 : if (ARR_NDIM(_query) > 1)
8259 bruce@momjian.us 296 [ # # ]:UBC 0 : ereport(ERROR,
297 : : (errcode(ERRCODE_ARRAY_SUBSCRIPT_ERROR),
298 : : errmsg("array must be one-dimensional")));
5544 tgl@sss.pgh.pa.us 299 [ - + ]:CBC 1587 : if (array_contains_nulls(_query))
7421 tgl@sss.pgh.pa.us 300 [ # # ]:UBC 0 : ereport(ERROR,
301 : : (errcode(ERRCODE_NULL_VALUE_NOT_ALLOWED),
302 : : errmsg("array must not contain nulls")));
303 : :
8259 bruce@momjian.us 304 [ + + ]:CBC 4736 : while (num > 0)
305 : : {
8425 306 [ + + ]: 3163 : if (DatumGetBool(DirectFunctionCall2(ltq_regex,
307 : : PointerGetDatum(tree), PointerGetDatum(query))))
308 : : {
309 : :
310 : 14 : res = true;
311 : 14 : break;
312 : : }
313 : 3149 : num--;
314 : 3149 : query = NEXTVAL(query);
315 : : }
316 : :
317 [ + + ]: 1587 : PG_FREE_IF_COPY(tree, 0);
318 [ - + ]: 1587 : PG_FREE_IF_COPY(_query, 1);
319 : 1587 : PG_RETURN_BOOL(res);
320 : : }
321 : :
322 : : Datum
8425 bruce@momjian.us 323 :UBC 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 : : }
|
