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 "miscadmin.h"
12 #include "utils/formatting.h"
13 #include "ltree.h"
14
15 PG_FUNCTION_INFO_V1(ltq_regex);
16 PG_FUNCTION_INFO_V1(ltq_rregex);
17
18 PG_FUNCTION_INFO_V1(lt_q_regex);
19 PG_FUNCTION_INFO_V1(lt_q_rregex);
20
21 #define NEXTVAL(x) ( (lquery*)( (char*)(x) + INTALIGN( VARSIZE(x) ) ) )
22
23 typedef struct
24 {
25 lquery_level *q;
26 int nq;
27 ltree_level *t;
28 int nt;
29 int posq;
30 int post;
31 } FieldNot;
32
33 static char *
getlexeme(char * start,char * end,int * len)34 getlexeme(char *start, char *end, int *len)
35 {
36 char *ptr;
37 int charlen;
38
39 while (start < end && (charlen = pg_mblen(start)) == 1 && t_iseq(start, '_'))
40 start += charlen;
41
42 ptr = start;
43 if (ptr >= end)
44 return NULL;
45
46 while (ptr < end && !((charlen = pg_mblen(ptr)) == 1 && t_iseq(ptr, '_')))
47 ptr += charlen;
48
49 *len = ptr - start;
50 return start;
51 }
52
53 bool
compare_subnode(ltree_level * t,char * qn,int len,int (* cmpptr)(const char *,const char *,size_t),bool anyend)54 compare_subnode(ltree_level *t, char *qn, int len, int (*cmpptr) (const char *, const char *, size_t), bool anyend)
55 {
56 char *endt = t->name + t->len;
57 char *endq = qn + len;
58 char *tn;
59 int lent,
60 lenq;
61 bool isok;
62
63 while ((qn = getlexeme(qn, endq, &lenq)) != NULL)
64 {
65 tn = t->name;
66 isok = false;
67 while ((tn = getlexeme(tn, endt, &lent)) != NULL)
68 {
69 if (
70 (
71 lent == lenq ||
72 (lent > lenq && anyend)
73 ) &&
74 (*cmpptr) (qn, tn, lenq) == 0)
75 {
76
77 isok = true;
78 break;
79 }
80 tn += lent;
81 }
82
83 if (!isok)
84 return false;
85 qn += lenq;
86 }
87
88 return true;
89 }
90
91 int
ltree_strncasecmp(const char * a,const char * b,size_t s)92 ltree_strncasecmp(const char *a, const char *b, size_t s)
93 {
94 char *al = str_tolower(a, s, DEFAULT_COLLATION_OID);
95 char *bl = str_tolower(b, s, DEFAULT_COLLATION_OID);
96 int res;
97
98 res = strncmp(al, bl, s);
99
100 pfree(al);
101 pfree(bl);
102
103 return res;
104 }
105
106 static bool
checkLevel(lquery_level * curq,ltree_level * curt)107 checkLevel(lquery_level *curq, ltree_level *curt)
108 {
109 int (*cmpptr) (const char *, const char *, size_t);
110 lquery_variant *curvar = LQL_FIRST(curq);
111 int i;
112
113 for (i = 0; i < curq->numvar; i++)
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, (curvar->flag & LVAR_ANYEND)))
120 return true;
121 }
122 else if (
123 (
124 curvar->len == curt->len ||
125 (curt->len > curvar->len && (curvar->flag & LVAR_ANYEND))
126 ) &&
127 (*cmpptr) (curvar->name, curt->name, curvar->len) == 0)
128 {
129
130 return true;
131 }
132 curvar = LVAR_NEXT(curvar);
133 }
134 return false;
135 }
136
137 /*
138 void
139 printFieldNot(FieldNot *fn ) {
140 while(fn->q) {
141 elog(NOTICE,"posQ:%d lenQ:%d posT:%d lenT:%d", fn->posq,fn->nq,fn->post,fn->nt);
142 fn++;
143 }
144 }
145 */
146
147 static struct
148 {
149 bool muse;
150 uint32 high_pos;
151 } SomeStack =
152
153 {
154 false, 0,
155 };
156
157 static bool
checkCond(lquery_level * curq,int query_numlevel,ltree_level * curt,int tree_numlevel,FieldNot * ptr)158 checkCond(lquery_level *curq, int query_numlevel, ltree_level *curt, int tree_numlevel, FieldNot *ptr)
159 {
160 uint32 low_pos = 0,
161 high_pos = 0,
162 cur_tpos = 0;
163 int tlen = tree_numlevel,
164 qlen = query_numlevel;
165 int isok;
166 lquery_level *prevq = NULL;
167 ltree_level *prevt = NULL;
168
169 /* Since this function recurses, it could be driven to stack overflow */
170 check_stack_depth();
171
172 /* Pathological patterns could take awhile, too */
173 CHECK_FOR_INTERRUPTS();
174
175 if (SomeStack.muse)
176 {
177 high_pos = SomeStack.high_pos;
178 qlen--;
179 prevq = curq;
180 curq = LQL_NEXT(curq);
181 SomeStack.muse = false;
182 }
183
184 while (tlen > 0 && qlen > 0)
185 {
186 if (curq->numvar)
187 {
188 prevt = curt;
189 while (cur_tpos < low_pos)
190 {
191 curt = LEVEL_NEXT(curt);
192 tlen--;
193 cur_tpos++;
194 if (tlen == 0)
195 return false;
196 if (ptr && ptr->q)
197 ptr->nt++;
198 }
199
200 if (ptr && curq->flag & LQL_NOT)
201 {
202 if (!(prevq && prevq->numvar == 0))
203 prevq = curq;
204 if (ptr->q == NULL)
205 {
206 ptr->t = prevt;
207 ptr->q = prevq;
208 ptr->nt = 1;
209 ptr->nq = 1 + ((prevq == curq) ? 0 : 1);
210 ptr->posq = query_numlevel - qlen - ((prevq == curq) ? 0 : 1);
211 ptr->post = cur_tpos;
212 }
213 else
214 {
215 ptr->nt++;
216 ptr->nq++;
217 }
218
219 if (qlen == 1 && ptr->q->numvar == 0)
220 ptr->nt = tree_numlevel - ptr->post;
221 curt = LEVEL_NEXT(curt);
222 tlen--;
223 cur_tpos++;
224 if (high_pos < cur_tpos)
225 high_pos++;
226 }
227 else
228 {
229 isok = false;
230 while (cur_tpos <= high_pos && tlen > 0 && !isok)
231 {
232 isok = checkLevel(curq, curt);
233 curt = LEVEL_NEXT(curt);
234 tlen--;
235 cur_tpos++;
236 if (isok && prevq && prevq->numvar == 0 && tlen > 0 && cur_tpos <= high_pos)
237 {
238 FieldNot tmpptr;
239
240 if (ptr)
241 memcpy(&tmpptr, ptr, sizeof(FieldNot));
242 SomeStack.high_pos = high_pos - cur_tpos;
243 SomeStack.muse = true;
244 if (checkCond(prevq, qlen + 1, curt, tlen, (ptr) ? &tmpptr : NULL))
245 return true;
246 }
247 if (!isok && ptr)
248 ptr->nt++;
249 }
250 if (!isok)
251 return false;
252
253 if (ptr && ptr->q)
254 {
255 if (checkCond(ptr->q, ptr->nq, ptr->t, ptr->nt, NULL))
256 return false;
257 ptr->q = NULL;
258 }
259 low_pos = cur_tpos;
260 high_pos = cur_tpos;
261 }
262 }
263 else
264 {
265 low_pos = cur_tpos + curq->low;
266 high_pos = cur_tpos + curq->high;
267 if (ptr && ptr->q)
268 {
269 ptr->nq++;
270 if (qlen == 1)
271 ptr->nt = tree_numlevel - ptr->post;
272 }
273 }
274
275 prevq = curq;
276 curq = LQL_NEXT(curq);
277 qlen--;
278 }
279
280 if (low_pos > tree_numlevel || tree_numlevel > high_pos)
281 return false;
282
283 while (qlen > 0)
284 {
285 if (curq->numvar)
286 {
287 if (!(curq->flag & LQL_NOT))
288 return false;
289 }
290 else
291 {
292 low_pos = cur_tpos + curq->low;
293 high_pos = cur_tpos + curq->high;
294 }
295
296 curq = LQL_NEXT(curq);
297 qlen--;
298 }
299
300 if (low_pos > tree_numlevel || tree_numlevel > high_pos)
301 return false;
302
303 if (ptr && ptr->q && checkCond(ptr->q, ptr->nq, ptr->t, ptr->nt, NULL))
304 return false;
305
306 return true;
307 }
308
309 Datum
ltq_regex(PG_FUNCTION_ARGS)310 ltq_regex(PG_FUNCTION_ARGS)
311 {
312 ltree *tree = PG_GETARG_LTREE(0);
313 lquery *query = PG_GETARG_LQUERY(1);
314 bool res = false;
315
316 if (query->flag & LQUERY_HASNOT)
317 {
318 FieldNot fn;
319
320 fn.q = NULL;
321
322 res = checkCond(LQUERY_FIRST(query), query->numlevel,
323 LTREE_FIRST(tree), tree->numlevel, &fn);
324 }
325 else
326 {
327 res = checkCond(LQUERY_FIRST(query), query->numlevel,
328 LTREE_FIRST(tree), tree->numlevel, NULL);
329 }
330
331 PG_FREE_IF_COPY(tree, 0);
332 PG_FREE_IF_COPY(query, 1);
333 PG_RETURN_BOOL(res);
334 }
335
336 Datum
ltq_rregex(PG_FUNCTION_ARGS)337 ltq_rregex(PG_FUNCTION_ARGS)
338 {
339 PG_RETURN_DATUM(DirectFunctionCall2(ltq_regex,
340 PG_GETARG_DATUM(1),
341 PG_GETARG_DATUM(0)
342 ));
343 }
344
345 Datum
lt_q_regex(PG_FUNCTION_ARGS)346 lt_q_regex(PG_FUNCTION_ARGS)
347 {
348 ltree *tree = PG_GETARG_LTREE(0);
349 ArrayType *_query = PG_GETARG_ARRAYTYPE_P(1);
350 lquery *query = (lquery *) ARR_DATA_PTR(_query);
351 bool res = false;
352 int num = ArrayGetNItems(ARR_NDIM(_query), ARR_DIMS(_query));
353
354 if (ARR_NDIM(_query) > 1)
355 ereport(ERROR,
356 (errcode(ERRCODE_ARRAY_SUBSCRIPT_ERROR),
357 errmsg("array must be one-dimensional")));
358 if (array_contains_nulls(_query))
359 ereport(ERROR,
360 (errcode(ERRCODE_NULL_VALUE_NOT_ALLOWED),
361 errmsg("array must not contain nulls")));
362
363 while (num > 0)
364 {
365 if (DatumGetBool(DirectFunctionCall2(ltq_regex,
366 PointerGetDatum(tree), PointerGetDatum(query))))
367 {
368
369 res = true;
370 break;
371 }
372 num--;
373 query = NEXTVAL(query);
374 }
375
376 PG_FREE_IF_COPY(tree, 0);
377 PG_FREE_IF_COPY(_query, 1);
378 PG_RETURN_BOOL(res);
379 }
380
381 Datum
lt_q_rregex(PG_FUNCTION_ARGS)382 lt_q_rregex(PG_FUNCTION_ARGS)
383 {
384 PG_RETURN_DATUM(DirectFunctionCall2(lt_q_regex,
385 PG_GETARG_DATUM(1),
386 PG_GETARG_DATUM(0)
387 ));
388 }
389