PostgreSQL Source Code  git master
Macros | Functions
like_match.c File Reference
This graph shows which files directly or indirectly include this file:

Go to the source code of this file.

Macros

#define GETCHAR(t, locale)   (t)
 

Functions

static int MatchText (const char *t, int tlen, const char *p, int plen, pg_locale_t locale)
 

Macro Definition Documentation

◆ GETCHAR

#define GETCHAR (   t,
  locale 
)    (t)

Definition at line 76 of file like_match.c.

Function Documentation

◆ MatchText()

static int MatchText ( const char *  t,
int  tlen,
const char *  p,
int  plen,
pg_locale_t  locale 
)
static

Definition at line 80 of file like_match.c.

81 {
82  /* Fast path for match-everything pattern */
83  if (plen == 1 && *p == '%')
84  return LIKE_TRUE;
85 
86  /* Since this function recurses, it could be driven to stack overflow */
87  check_stack_depth();
88 
89  /*
90  * In this loop, we advance by char when matching wildcards (and thus on
91  * recursive entry to this function we are properly char-synced). On other
92  * occasions it is safe to advance by byte, as the text and pattern will
93  * be in lockstep. This allows us to perform all comparisons between the
94  * text and pattern on a byte by byte basis, even for multi-byte
95  * encodings.
96  */
97  while (tlen > 0 && plen > 0)
98  {
99  if (*p == '\\')
100  {
101  /* Next pattern byte must match literally, whatever it is */
102  NextByte(p, plen);
103  /* ... and there had better be one, per SQL standard */
104  if (plen <= 0)
105  ereport(ERROR,
106  (errcode(ERRCODE_INVALID_ESCAPE_SEQUENCE),
107  errmsg("LIKE pattern must not end with escape character")));
108  if (GETCHAR(*p, locale) != GETCHAR(*t, locale))
109  return LIKE_FALSE;
110  }
111  else if (*p == '%')
112  {
113  char firstpat;
114 
115  /*
116  * % processing is essentially a search for a text position at
117  * which the remainder of the text matches the remainder of the
118  * pattern, using a recursive call to check each potential match.
119  *
120  * If there are wildcards immediately following the %, we can skip
121  * over them first, using the idea that any sequence of N _'s and
122  * one or more %'s is equivalent to N _'s and one % (ie, it will
123  * match any sequence of at least N text characters). In this way
124  * we will always run the recursive search loop using a pattern
125  * fragment that begins with a literal character-to-match, thereby
126  * not recursing more than we have to.
127  */
128  NextByte(p, plen);
129 
130  while (plen > 0)
131  {
132  if (*p == '%')
133  NextByte(p, plen);
134  else if (*p == '_')
135  {
136  /* If not enough text left to match the pattern, ABORT */
137  if (tlen <= 0)
138  return LIKE_ABORT;
139  NextChar(t, tlen);
140  NextByte(p, plen);
141  }
142  else
143  break; /* Reached a non-wildcard pattern char */
144  }
145 
146  /*
147  * If we're at end of pattern, match: we have a trailing % which
148  * matches any remaining text string.
149  */
150  if (plen <= 0)
151  return LIKE_TRUE;
152 
153  /*
154  * Otherwise, scan for a text position at which we can match the
155  * rest of the pattern. The first remaining pattern char is known
156  * to be a regular or escaped literal character, so we can compare
157  * the first pattern byte to each text byte to avoid recursing
158  * more than we have to. This fact also guarantees that we don't
159  * have to consider a match to the zero-length substring at the
160  * end of the text. With a nondeterministic collation, we can't
161  * rely on the first bytes being equal, so we have to recurse in
162  * any case.
163  */
164  if (*p == '\\')
165  {
166  if (plen < 2)
167  ereport(ERROR,
168  (errcode(ERRCODE_INVALID_ESCAPE_SEQUENCE),
169  errmsg("LIKE pattern must not end with escape character")));
170  firstpat = GETCHAR(p[1], locale);
171  }
172  else
173  firstpat = GETCHAR(*p, locale);
174 
175  while (tlen > 0)
176  {
177  if (GETCHAR(*t, locale) == firstpat || (locale && !locale->deterministic))
178  {
179  int matched = MatchText(t, tlen, p, plen, locale);
180 
181  if (matched != LIKE_FALSE)
182  return matched; /* TRUE or ABORT */
183  }
184 
185  NextChar(t, tlen);
186  }
187 
188  /*
189  * End of text with no match, so no point in trying later places
190  * to start matching this pattern.
191  */
192  return LIKE_ABORT;
193  }
194  else if (*p == '_')
195  {
196  /* _ matches any single character, and we know there is one */
197  NextChar(t, tlen);
198  NextByte(p, plen);
199  continue;
200  }
201  else if (locale && !locale->deterministic)
202  {
203  /*
204  * For nondeterministic locales, we find the next substring of the
205  * pattern that does not contain wildcards and try to find a
206  * matching substring in the text. Crucially, we cannot do this
207  * character by character, as in the normal case, but must do it
208  * substring by substring, partitioned by the wildcard characters.
209  * (This is per SQL standard.)
210  */
211  const char *p1;
212  size_t p1len;
213  const char *t1;
214  size_t t1len;
215  bool found_escape;
216  const char *subpat;
217  size_t subpatlen;
218  char *buf = NULL;
219 
220  /*
221  * Determine next substring of pattern without wildcards. p is
222  * the start of the subpattern, p1 is one past the last byte. Also
223  * track if we found an escape character.
224  */
225  p1 = p;
226  p1len = plen;
227  found_escape = false;
228  while (p1len > 0)
229  {
230  if (*p1 == '\\')
231  {
232  found_escape = true;
233  NextByte(p1, p1len);
234  if (p1len == 0)
235  ereport(ERROR,
236  (errcode(ERRCODE_INVALID_ESCAPE_SEQUENCE),
237  errmsg("LIKE pattern must not end with escape character")));
238  }
239  else if (*p1 == '_' || *p1 == '%')
240  break;
241  NextByte(p1, p1len);
242  }
243 
244  /*
245  * If we found an escape character, then make an unescaped copy of
246  * the subpattern.
247  */
248  if (found_escape)
249  {
250  char *b;
251 
252  b = buf = palloc(p1 - p);
253  for (const char *c = p; c < p1; c++)
254  {
255  if (*c == '\\')
256  ;
257  else
258  *(b++) = *c;
259  }
260 
261  subpat = buf;
262  subpatlen = b - buf;
263  }
264  else
265  {
266  subpat = p;
267  subpatlen = p1 - p;
268  }
269 
270  /*
271  * Shortcut: If this is the end of the pattern, then the rest of
272  * the text has to match the rest of the pattern.
273  */
274  if (p1len == 0)
275  {
276  int cmp;
277 
278  cmp = pg_strncoll(subpat, subpatlen, t, tlen, locale);
279 
280  if (buf)
281  pfree(buf);
282  if (cmp == 0)
283  return LIKE_TRUE;
284  else
285  return LIKE_FALSE;
286  }
287 
288  /*
289  * Now build a substring of the text and try to match it against
290  * the subpattern. t is the start of the text, t1 is one past the
291  * last byte. We start with a zero-length string.
292  */
293  t1 = t;
294  t1len = tlen;
295  for (;;)
296  {
297  int cmp;
298 
299  CHECK_FOR_INTERRUPTS();
300 
301  cmp = pg_strncoll(subpat, subpatlen, t, (t1 - t), locale);
302 
303  /*
304  * If we found a match, we have to test if the rest of pattern
305  * can match against the rest of the string. Otherwise we
306  * have to continue here try matching with a longer substring.
307  * (This is similar to the recursion for the '%' wildcard
308  * above.)
309  *
310  * Note that we can't just wind forward p and t and continue
311  * with the main loop. This would fail for example with
312  *
313  * U&'\0061\0308bc' LIKE U&'\00E4_c' COLLATE ignore_accents
314  *
315  * You'd find that t=\0061 matches p=\00E4, but then the rest
316  * won't match; but t=\0061\0308 also matches p=\00E4, and
317  * then the rest will match.
318  */
319  if (cmp == 0)
320  {
321  int matched = MatchText(t1, t1len, p1, p1len, locale);
322 
323  if (matched == LIKE_TRUE)
324  {
325  if (buf)
326  pfree(buf);
327  return matched;
328  }
329  }
330 
331  /*
332  * Didn't match. If we used up the whole text, then the match
333  * fails. Otherwise, try again with a longer substring.
334  */
335  if (t1len == 0)
336  {
337  if (buf)
338  pfree(buf);
339  return LIKE_FALSE;
340  }
341  else
342  NextChar(t1, t1len);
343  }
344  }
345  else if (GETCHAR(*p, locale) != GETCHAR(*t, locale))
346  {
347  /* non-wildcard pattern char fails to match text char */
348  return LIKE_FALSE;
349  }
350 
351  /*
352  * Pattern and text match, so advance.
353  *
354  * It is safe to use NextByte instead of NextChar here, even for
355  * multi-byte character sets, because we are not following immediately
356  * after a wildcard character. If we are in the middle of a multibyte
357  * character, we must already have matched at least one byte of the
358  * character from both text and pattern; so we cannot get out-of-sync
359  * on character boundaries. And we know that no backend-legal
360  * encoding allows ASCII characters such as '%' to appear as non-first
361  * bytes of characters, so we won't mistakenly detect a new wildcard.
362  */
363  NextByte(t, tlen);
364  NextByte(p, plen);
365  }
366 
367  if (tlen > 0)
368  return LIKE_FALSE; /* end of pattern, but not of text */
369 
370  /*
371  * End of text, but perhaps not of pattern. Match iff the remaining
372  * pattern can match a zero-length string, ie, it's zero or more %'s.
373  */
374  while (plen > 0 && *p == '%')
375  NextByte(p, plen);
376  if (plen <= 0)
377  return LIKE_TRUE;
378 
379  /*
380  * End of text with no match, so no point in trying later places to start
381  * matching this pattern.
382  */
383  return LIKE_ABORT;
384 } /* MatchText() */
errcode
int errcode(int sqlerrcode)
Definition: elog.c:853
errmsg
int errmsg(const char *fmt,...)
Definition: elog.c:1070
ERROR
#define ERROR
Definition: elog.h:39
ereport
#define ereport(elevel,...)
Definition: elog.h:149
locale
static char * locale
Definition: initdb.c:140
b
int b
Definition: isn.c:69
LIKE_ABORT
#define LIKE_ABORT
Definition: like.c:32
LIKE_TRUE
#define LIKE_TRUE
Definition: like.c:30
LIKE_FALSE
#define LIKE_FALSE
Definition: like.c:31
NextByte
#define NextByte(p, plen)
Definition: like.c:105
NextChar
#define NextChar(p, plen)
Definition: like.c:142
MatchText
static int MatchText(const char *t, int tlen, const char *p, int plen, pg_locale_t locale)
Definition: like_match.c:80
GETCHAR
#define GETCHAR(t, locale)
Definition: like_match.c:76
pfree
void pfree(void *pointer)
Definition: mcxt.c:1521
palloc
void * palloc(Size size)
Definition: mcxt.c:1317
CHECK_FOR_INTERRUPTS
#define CHECK_FOR_INTERRUPTS()
Definition: miscadmin.h:122
pg_strncoll
int pg_strncoll(const char *arg1, ssize_t len1, const char *arg2, ssize_t len2, pg_locale_t locale)
Definition: pg_locale.c:1509
buf
static char * buf
Definition: pg_test_fsync.c:72
check_stack_depth
void check_stack_depth(void)
Definition: postgres.c:3572
c
char * c
Definition: preproc-cursor.c:31
cmp
static int cmp(const chr *x, const chr *y, size_t len)
Definition: regc_locale.c:743

References b, buf, CHECK_FOR_INTERRUPTS, check_stack_depth(), cmp(), ereport, errcode(), errmsg(), ERROR, GETCHAR, LIKE_ABORT, LIKE_FALSE, LIKE_TRUE, locale, NextByte, NextChar, palloc(), pfree(), and pg_strncoll().