| 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 |