Debian Codegraph @

src/backend/utils/adt/like_match.c

raw
1 /*-------------------------------------------------------------------------
2 *
3 * like_match.c
4 * LIKE pattern matching internal code.
5 *
6 * This file is included by like.c four times, to provide matching code for
7 * (1) single-byte encodings, (2) UTF8, (3) other multi-byte encodings,
8 * and (4) case insensitive matches in single-byte encodings.
9 * (UTF8 is a special case because we can use a much more efficient version
10 * of NextChar than can be used for general multi-byte encodings.)
11 *
12 * Before the inclusion, we need to define the following macros:
13 *
14 * NextChar
15 * MatchText - to name of function wanted
16 * do_like_escape - name of function if wanted - needs CHAREQ and CopyAdvChar
17 * MATCH_LOWER - define for case (4) to specify case folding for 1-byte chars
18 *
19 * Copyright (c) 1996-2025, PostgreSQL Global Development Group
20 *
21 * IDENTIFICATION
22 * src/backend/utils/adt/like_match.c
23 *
24 *-------------------------------------------------------------------------
25 */
26
27 /*
28 * Originally written by Rich $alz, mirror!rs, Wed Nov 26 19:03:17 EST 1986.
29 * Rich $alz is now <[email protected]>.
30 * Special thanks to Lars Mathiesen <[email protected]> for the
31 * LIKE_ABORT code.
32 *
33 * This code was shamelessly stolen from the "pql" code by myself and
34 * slightly modified :)
35 *
36 * All references to the word "star" were replaced by "percent"
37 * All references to the word "wild" were replaced by "like"
38 *
39 * All the nice shell RE matching stuff was replaced by just "_" and "%"
40 *
41 * As I don't have a copy of the SQL standard handy I wasn't sure whether
42 * to leave in the '\' escape character handling.
43 *
44 * Keith Parks. <[email protected]>
45 *
46 * SQL lets you specify the escape character by saying
47 * LIKE <pattern> ESCAPE <escape character>. We are a small operation
48 * so we force you to use '\'. - ay 7/95
49 *
50 * Now we have the like_escape() function that converts patterns with
51 * any specified escape character (or none at all) to the internal
52 * default escape character, which is still '\'. - tgl 9/2000
53 *
54 * The code is rewritten to avoid requiring null-terminated strings,
55 * which in turn allows us to leave out some memcpy() operations.
56 * This code should be faster and take less memory, but no promises...
57 * - thomas 2000-08-06
58 */
59
60
61 /*--------------------
62 * Match text and pattern, return LIKE_TRUE, LIKE_FALSE, or LIKE_ABORT.
63 *
64 * LIKE_TRUE: they match
65 * LIKE_FALSE: they don't match
66 * LIKE_ABORT: not only don't they match, but the text is too short.
67 *
68 * If LIKE_ABORT is returned, then no suffix of the text can match the
69 * pattern either, so an upper-level % scan can stop scanning now.
70 *--------------------
71 */
72
73 #ifdef MATCH_LOWER
74 #define GETCHAR(t, locale) MATCH_LOWER(t, locale)
75 #else
76 #define GETCHAR(t, locale) (t)
77 #endif
78
79 static int
80 MatchText(const char *t, int tlen, const char *p, int plen, pg_locale_t locale)
81 {
82 bool nondeterministic = (locale && !locale->deterministic);
83
84 /* Fast path for match-everything pattern */
85 if (plen == 1 && *p == '%')
86 return LIKE_TRUE;
87
88 /* Since this function recurses, it could be driven to stack overflow */
89 check_stack_depth();
90
91 /*
92 * In this loop, we advance by char when matching wildcards (and thus on
93 * recursive entry to this function we are properly char-synced). On other
94 * occasions it is safe to advance by byte, as the text and pattern will
95 * be in lockstep. This allows us to perform all comparisons between the
96 * text and pattern on a byte by byte basis, even for multi-byte
97 * encodings. (But that doesn't work in a nondeterministic locale, so the
98 * nondeterministic case below has to advance the text by chars.)
99 */
100 while (tlen > 0 && plen > 0)
101 {
102 /*
103 * At the top of this loop, we are not positioned immediately after an
104 * escape, so we may take wildcards at face value.
105 */
106 if (*p == '%')
107 {
108 char firstpat;
109
110 /*
111 * % processing is essentially a search for a text position at
112 * which the remainder of the text matches the remainder of the
113 * pattern, using a recursive call to check each potential match.
114 *
115 * If there are wildcards immediately following the %, we can skip
116 * over them first, using the idea that any sequence of N _'s and
117 * one or more %'s is equivalent to N _'s and one % (ie, it will
118 * match any sequence of at least N text characters). In this way
119 * we will always run the recursive search loop using a pattern
120 * fragment that begins with a literal character-to-match, thereby
121 * not recursing more than we have to.
122 */
123 NextByte(p, plen);
124
125 while (plen > 0)
126 {
127 if (*p == '%')
128 NextByte(p, plen);
129 else if (*p == '_')
130 {
131 /* If not enough text left to match the pattern, ABORT */
132 if (tlen <= 0)
133 return LIKE_ABORT;
134 NextChar(t, tlen);
135 NextByte(p, plen);
136 }
137 else
138 break; /* Reached a non-wildcard pattern char */
139 }
140
141 /*
142 * If we're at end of pattern, match: we have a trailing % which
143 * matches any remaining text string.
144 */
145 if (plen <= 0)
146 return LIKE_TRUE;
147
148 /*
149 * Otherwise, scan for a text position at which we can match the
150 * rest of the pattern. The first remaining pattern char is known
151 * to be a regular or escaped literal character, so we can compare
152 * the first pattern byte to each text byte to avoid recursing
153 * more than we have to. This fact also guarantees that we don't
154 * have to consider a match to the zero-length substring at the
155 * end of the text. But with a nondeterministic locale, we can't
156 * rely on the first byte of a match being equal, so we have to
157 * recurse in any case.
158 */
159 if (*p == '\\')
160 {
161 if (plen < 2)
162 ereport(ERROR,
163 (errcode(ERRCODE_INVALID_ESCAPE_SEQUENCE),
164 errmsg("LIKE pattern must not end with escape character")));
165 firstpat = GETCHAR(p[1], locale);
166 }
167 else
168 firstpat = GETCHAR(*p, locale);
169
170 while (tlen > 0)
171 {
172 if (GETCHAR(*t, locale) == firstpat || nondeterministic)
173 {
174 int matched = MatchText(t, tlen, p, plen, locale);
175
176 if (matched != LIKE_FALSE)
177 return matched; /* TRUE or ABORT */
178 }
179
180 NextChar(t, tlen);
181 }
182
183 /*
184 * End of text with no match, so no point in trying later places
185 * to start matching this pattern.
186 */
187 return LIKE_ABORT;
188 }
189 else if (*p == '_')
190 {
191 /* _ matches any single character, and we know there is one */
192 NextChar(t, tlen);
193 NextByte(p, plen);
194 continue;
195 }
196 else if (nondeterministic)
197 {
198 /*
199 * For nondeterministic locales, we find the next substring of the
200 * pattern that does not contain wildcards and try to find a
201 * matching substring in the text. Crucially, we cannot do this
202 * character by character, as in the normal case, but must do it
203 * substring by substring, partitioned by the wildcard characters.
204 * (This is per SQL standard.)
205 */
206 const char *p1;
207 size_t p1len;
208 const char *t1;
209 size_t t1len;
210 bool found_escape;
211 const char *subpat;
212 size_t subpatlen;
213 char *buf = NULL;
214
215 /*
216 * Determine length of substring of pattern without wildcards. p
217 * is the start of the subpattern, p1 will advance to one past its
218 * last byte. Also track if we found an escape character.
219 */
220 p1 = p;
221 p1len = plen;
222 found_escape = false;
223 while (p1len > 0)
224 {
225 if (*p1 == '\\')
226 {
227 found_escape = true;
228 NextByte(p1, p1len);
229 if (p1len == 0)
230 ereport(ERROR,
231 (errcode(ERRCODE_INVALID_ESCAPE_SEQUENCE),
232 errmsg("LIKE pattern must not end with escape character")));
233 }
234 else if (*p1 == '_' || *p1 == '%')
235 break;
236 /* Advance over regular or escaped character */
237 NextByte(p1, p1len);
238 }
239
240 /*
241 * If we found an escape character, then make a de-escaped copy of
242 * the subpattern that we can use to match literally. Otherwise
243 * we can use the subpattern in-place. (buf holds the de-escaped
244 * copy; be sure to pfree it before returning.)
245 */
246 if (found_escape)
247 {
248 char *b;
249
250 b = buf = palloc(p1 - p);
251 for (const char *c = p; c < p1; c++)
252 {
253 if (*c == '\\')
254 c++; /* we already checked this isn't the end */
255 *(b++) = *c;
256 }
257
258 subpat = buf;
259 subpatlen = b - buf;
260 }
261 else
262 {
263 subpat = p;
264 subpatlen = p1 - p;
265 }
266
267 /*
268 * Shortcut: If this is the end of the pattern, then the rest of
269 * the text has to match the rest of the pattern.
270 */
271 if (p1len == 0)
272 {
273 int cmp;
274
275 cmp = pg_strncoll(subpat, subpatlen, t, tlen, locale);
276
277 if (buf)
278 pfree(buf);
279 if (cmp == 0)
280 return LIKE_TRUE;
281 else
282 return LIKE_FALSE;
283 }
284
285 /*
286 * Consider each successively-longer substring of the remaining
287 * text and try to match it against the subpattern. t is the
288 * start of the substring, t1 is one past its last byte. We start
289 * with a zero-length substring.
290 */
291 t1 = t;
292 t1len = tlen;
293 for (;;)
294 {
295 int cmp;
296
297 /* This could be slow, so allow interrupts */
298 CHECK_FOR_INTERRUPTS();
299
300 cmp = pg_strncoll(subpat, subpatlen, t, (t1 - t), locale);
301
302 /*
303 * If we found a match, we have to test if the rest of pattern
304 * can match against the rest of the text. If not, we have to
305 * continue and try the next longer substring. (This is
306 * similar to the recursion for the '%' wildcard above.)
307 *
308 * Note that we can't just wind forward p and t and continue
309 * with the main loop. This would fail for example with
310 *
311 * U&'\0061\0308bc' LIKE U&'\00E4_c' COLLATE ignore_accents
312 *
313 * You'd find that t=\0061 matches p=\00E4, but then the rest
314 * won't match; but t=\0061\0308 also matches p=\00E4, and
315 * then the rest will match.
316 */
317 if (cmp == 0)
318 {
319 int matched = MatchText(t1, t1len, p1, p1len, locale);
320
321 if (matched == LIKE_TRUE)
322 {
323 if (buf)
324 pfree(buf);
325 return matched;
326 }
327 }
328
329 /*
330 * Didn't match. If we used up the whole text, then the match
331 * fails. Otherwise, try again with a longer substring.
332 */
333 if (t1len == 0)
334 {
335 if (buf)
336 pfree(buf);
337 return LIKE_FALSE;
338 }
339 else
340 NextChar(t1, t1len);
341 } /* end loop over substrings starting at t */
342 }
343 /* the rest of this loop considers only deterministic cases */
344 else if (*p == '\\')
345 {
346 /* Next pattern byte must match literally, whatever it is */
347 NextByte(p, plen);
348 /* ... and there had better be one, per SQL standard */
349 if (plen <= 0)
350 ereport(ERROR,
351 (errcode(ERRCODE_INVALID_ESCAPE_SEQUENCE),
352 errmsg("LIKE pattern must not end with escape character")));
353 if (GETCHAR(*p, locale) != GETCHAR(*t, locale))
354 return LIKE_FALSE;
355 }
356 else if (GETCHAR(*p, locale) != GETCHAR(*t, locale))
357 {
358 /* non-wildcard pattern char fails to match text char */
359 return LIKE_FALSE;
360 }
361
362 /*
363 * Pattern and text match, so advance.
364 *
365 * It is safe to use NextByte instead of NextChar here, even for
366 * multi-byte character sets, because we are not following immediately
367 * after a wildcard character. If we are in the middle of a multibyte
368 * character, we must already have matched at least one byte of the
369 * character from both text and pattern; so we cannot get out-of-sync
370 * on character boundaries. And we know that no backend-legal
371 * encoding allows ASCII characters such as '%' to appear as non-first
372 * bytes of characters, so we won't mistakenly detect a new wildcard.
373 */
374 NextByte(t, tlen);
375 NextByte(p, plen);
376 }
377
378 if (tlen > 0)
379 return LIKE_FALSE; /* end of pattern, but not of text */
380
381 /*
382 * End of text, but perhaps not of pattern. Match iff the remaining
383 * pattern can match a zero-length string, ie, it's zero or more %'s.
384 */
385 while (plen > 0 && *p == '%')
386 NextByte(p, plen);
387 if (plen <= 0)
388 return LIKE_TRUE;
389
390 /*
391 * End of text with no match, so no point in trying later places to start
392 * matching this pattern.
393 */
394 return LIKE_ABORT;
395 } /* MatchText() */
396
397 /*
398 * like_escape() --- given a pattern and an ESCAPE string,
399 * convert the pattern to use Postgres' standard backslash escape convention.
400 */
401 #ifdef do_like_escape
402
403 static text *
404 do_like_escape(text *pat, text *esc)
405 {
406 text *result;
407 char *p,
408 *e,
409 *r;
410 int plen,
411 elen;
412 bool afterescape;
413
414 p = VARDATA_ANY(pat);
415 plen = VARSIZE_ANY_EXHDR(pat);
416 e = VARDATA_ANY(esc);
417 elen = VARSIZE_ANY_EXHDR(esc);
418
419 /*
420 * Worst-case pattern growth is 2x --- unlikely, but it's hardly worth
421 * trying to calculate the size more accurately than that.
422 */
423 result = (text *) palloc(plen * 2 + VARHDRSZ);
424 r = VARDATA(result);
425
426 if (elen == 0)
427 {
428 /*
429 * No escape character is wanted. Double any backslashes in the
430 * pattern to make them act like ordinary characters.
431 */
432 while (plen > 0)
433 {
434 if (*p == '\\')
435 *r++ = '\\';
436 CopyAdvChar(r, p, plen);
437 }
438 }
439 else
440 {
441 /*
442 * The specified escape must be only a single character.
443 */
444 NextChar(e, elen);
445 if (elen != 0)
446 ereport(ERROR,
447 (errcode(ERRCODE_INVALID_ESCAPE_SEQUENCE),
448 errmsg("invalid escape string"),
449 errhint("Escape string must be empty or one character.")));
450
451 e = VARDATA_ANY(esc);
452 elen = VARSIZE_ANY_EXHDR(esc);
453
454 /*
455 * If specified escape is '\', just copy the pattern as-is.
456 */
457 if (*e == '\\')
458 {
459 memcpy(result, pat, VARSIZE_ANY(pat));
460 return result;
461 }
462
463 /*
464 * Otherwise, convert occurrences of the specified escape character to
465 * '\', and double occurrences of '\' --- unless they immediately
466 * follow an escape character!
467 */
468 afterescape = false;
469 while (plen > 0)
470 {
471 if (CHAREQ(p, plen, e, elen) && !afterescape)
472 {
473 *r++ = '\\';
474 NextChar(p, plen);
475 afterescape = true;
476 }
477 else if (*p == '\\')
478 {
479 *r++ = '\\';
480 if (!afterescape)
481 *r++ = '\\';
482 NextChar(p, plen);
483 afterescape = false;
484 }
485 else
486 {
487 CopyAdvChar(r, p, plen);
488 afterescape = false;
489 }
490 }
491 }
492
493 SET_VARSIZE(result, r - ((char *) result));
494
495 return result;
496 }
497 #endif /* do_like_escape */
498
499 #ifdef CHAREQ
500 #undef CHAREQ
501 #endif
502
503 #undef NextChar
504 #undef CopyAdvChar
505 #undef MatchText
506
507 #ifdef do_like_escape
508 #undef do_like_escape
509 #endif
510
511 #undef GETCHAR
512
513 #ifdef MATCH_LOWER
514 #undef MATCH_LOWER
515
516 #endif