LCOV - code coverage report
Current view: top level - src/backend/utils/adt - like_match.c (source / functions) Hit Total Coverage
Test: PostgreSQL 14devel Lines: 137 311 44.1 %
Date: 2020-11-27 12:05:55 Functions: 2 6 33.3 %
Legend: Lines: hit not hit

          Line data    Source code
       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-2020, 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 <rsalz@bbn.com>.
      30             :  *  Special thanks to Lars Mathiesen <thorinn@diku.dk> 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. <keith@mtcc.demon.co.uk>
      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) MATCH_LOWER(t)
      75             : #else
      76             : #define GETCHAR(t) (t)
      77             : #endif
      78             : 
      79             : static int
      80     1660860 : MatchText(const char *t, int tlen, const char *p, int plen,
      81             :           pg_locale_t locale, bool locale_is_c)
      82             : {
      83             :     /* Fast path for match-everything pattern */
      84     1660860 :     if (plen == 1 && *p == '%')
      85           0 :         return LIKE_TRUE;
      86             : 
      87             :     /* Since this function recurses, it could be driven to stack overflow */
      88     1660860 :     check_stack_depth();
      89             : 
      90             :     /*
      91             :      * In this loop, we advance by char when matching wildcards (and thus on
      92             :      * recursive entry to this function we are properly char-synced). On other
      93             :      * occasions it is safe to advance by byte, as the text and pattern will
      94             :      * be in lockstep. This allows us to perform all comparisons between the
      95             :      * text and pattern on a byte by byte basis, even for multi-byte
      96             :      * encodings.
      97             :      */
      98     2035678 :     while (tlen > 0 && plen > 0)
      99             :     {
     100     2032374 :         if (*p == '\\')
     101             :         {
     102             :             /* Next pattern byte must match literally, whatever it is */
     103        5464 :             NextByte(p, plen);
     104             :             /* ... and there had better be one, per SQL standard */
     105        5464 :             if (plen <= 0)
     106           0 :                 ereport(ERROR,
     107             :                         (errcode(ERRCODE_INVALID_ESCAPE_SEQUENCE),
     108             :                          errmsg("LIKE pattern must not end with escape character")));
     109        5464 :             if (GETCHAR(*p) != GETCHAR(*t))
     110        1972 :                 return LIKE_FALSE;
     111             :         }
     112     2026910 :         else if (*p == '%')
     113             :         {
     114             :             char        firstpat;
     115             : 
     116             :             /*
     117             :              * % processing is essentially a search for a text position at
     118             :              * which the remainder of the text matches the remainder of the
     119             :              * pattern, using a recursive call to check each potential match.
     120             :              *
     121             :              * If there are wildcards immediately following the %, we can skip
     122             :              * over them first, using the idea that any sequence of N _'s and
     123             :              * one or more %'s is equivalent to N _'s and one % (ie, it will
     124             :              * match any sequence of at least N text characters).  In this way
     125             :              * we will always run the recursive search loop using a pattern
     126             :              * fragment that begins with a literal character-to-match, thereby
     127             :              * not recursing more than we have to.
     128             :              */
     129       74498 :             NextByte(p, plen);
     130             : 
     131       74690 :             while (plen > 0)
     132             :             {
     133       44632 :                 if (*p == '%')
     134           4 :                     NextByte(p, plen);
     135       44628 :                 else if (*p == '_')
     136             :                 {
     137             :                     /* If not enough text left to match the pattern, ABORT */
     138         192 :                     if (tlen <= 0)
     139           4 :                         return LIKE_ABORT;
     140         188 :                     NextChar(t, tlen);
     141         188 :                     NextByte(p, plen);
     142             :                 }
     143             :                 else
     144       44436 :                     break;      /* Reached a non-wildcard pattern char */
     145             :             }
     146             : 
     147             :             /*
     148             :              * If we're at end of pattern, match: we have a trailing % which
     149             :              * matches any remaining text string.
     150             :              */
     151       74494 :             if (plen <= 0)
     152       30058 :                 return LIKE_TRUE;
     153             : 
     154             :             /*
     155             :              * Otherwise, scan for a text position at which we can match the
     156             :              * rest of the pattern.  The first remaining pattern char is known
     157             :              * to be a regular or escaped literal character, so we can compare
     158             :              * the first pattern byte to each text byte to avoid recursing
     159             :              * more than we have to.  This fact also guarantees that we don't
     160             :              * have to consider a match to the zero-length substring at the
     161             :              * end of the text.
     162             :              */
     163       44436 :             if (*p == '\\')
     164             :             {
     165           4 :                 if (plen < 2)
     166           0 :                     ereport(ERROR,
     167             :                             (errcode(ERRCODE_INVALID_ESCAPE_SEQUENCE),
     168             :                              errmsg("LIKE pattern must not end with escape character")));
     169           4 :                 firstpat = GETCHAR(p[1]);
     170             :             }
     171             :             else
     172       44432 :                 firstpat = GETCHAR(*p);
     173             : 
     174     2620418 :             while (tlen > 0)
     175             :             {
     176     2600888 :                 if (GETCHAR(*t) == firstpat)
     177             :                 {
     178       32874 :                     int         matched = MatchText(t, tlen, p, plen,
     179             :                                                     locale, locale_is_c);
     180             : 
     181       32874 :                     if (matched != LIKE_FALSE)
     182       24906 :                         return matched; /* TRUE or ABORT */
     183             :                 }
     184             : 
     185     2575982 :                 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       19530 :             return LIKE_ABORT;
     193             :         }
     194     1952412 :         else if (*p == '_')
     195             :         {
     196             :             /* _ matches any single character, and we know there is one */
     197        3490 :             NextChar(t, tlen);
     198        3490 :             NextByte(p, plen);
     199        3490 :             continue;
     200             :         }
     201     1948922 :         else if (GETCHAR(*p) != GETCHAR(*t))
     202             :         {
     203             :             /* non-wildcard pattern char fails to match text char */
     204     1581086 :             return LIKE_FALSE;
     205             :         }
     206             : 
     207             :         /*
     208             :          * Pattern and text match, so advance.
     209             :          *
     210             :          * It is safe to use NextByte instead of NextChar here, even for
     211             :          * multi-byte character sets, because we are not following immediately
     212             :          * after a wildcard character. If we are in the middle of a multibyte
     213             :          * character, we must already have matched at least one byte of the
     214             :          * character from both text and pattern; so we cannot get out-of-sync
     215             :          * on character boundaries.  And we know that no backend-legal
     216             :          * encoding allows ASCII characters such as '%' to appear as non-first
     217             :          * bytes of characters, so we won't mistakenly detect a new wildcard.
     218             :          */
     219      371328 :         NextByte(t, tlen);
     220      371328 :         NextByte(p, plen);
     221             :     }
     222             : 
     223        3304 :     if (tlen > 0)
     224         104 :         return LIKE_FALSE;      /* end of pattern, but not of text */
     225             : 
     226             :     /*
     227             :      * End of text, but perhaps not of pattern.  Match iff the remaining
     228             :      * pattern can match a zero-length string, ie, it's zero or more %'s.
     229             :      */
     230        3538 :     while (plen > 0 && *p == '%')
     231         338 :         NextByte(p, plen);
     232        3200 :     if (plen <= 0)
     233        2200 :         return LIKE_TRUE;
     234             : 
     235             :     /*
     236             :      * End of text with no match, so no point in trying later places to start
     237             :      * matching this pattern.
     238             :      */
     239        1000 :     return LIKE_ABORT;
     240             : }                               /* MatchText() */
     241     1621320 : 
     242             : /*
     243             :  * like_escape() --- given a pattern and an ESCAPE string,
     244             :  * convert the pattern to use Postgres' standard backslash escape convention.
     245     1621320 :  */
     246           0 : #ifdef do_like_escape
     247             : 
     248             : static text *
     249     1621320 : do_like_escape(text *pat, text *esc)
     250             : {
     251             :     text       *result;
     252             :     char       *p,
     253             :                *e,
     254             :                *r;
     255             :     int         plen,
     256             :                 elen;
     257             :     bool        afterescape;
     258             : 
     259     1993606 :     p = VARDATA_ANY(pat);
     260           0 :     plen = VARSIZE_ANY_EXHDR(pat);
     261     1990302 :     e = VARDATA_ANY(esc);
     262           0 :     elen = VARSIZE_ANY_EXHDR(esc);
     263             : 
     264        5464 :     /*
     265             :      * Worst-case pattern growth is 2x --- unlikely, but it's hardly worth
     266        5464 :      * trying to calculate the size more accurately than that.
     267           0 :      */
     268           0 :     result = (text *) palloc(plen * 2 + VARHDRSZ);
     269           0 :     r = VARDATA(result);
     270        5464 : 
     271        1972 :     if (elen == 0)
     272             :     {
     273     1984838 :         /*
     274             :          * No escape character is wanted.  Double any backslashes in the
     275             :          * pattern to make them act like ordinary characters.
     276             :          */
     277           0 :         while (plen > 0)
     278             :         {
     279           0 :             if (*p == '\\')
     280           0 :                 *r++ = '\\';
     281           0 :             CopyAdvChar(r, p, plen);
     282             :         }
     283             :     }
     284             :     else
     285             :     {
     286             :         /*
     287             :          * The specified escape must be only a single character.
     288             :          */
     289           0 :         NextChar(e, elen);
     290       74390 :         if (elen != 0)
     291           0 :             ereport(ERROR,
     292       74582 :                     (errcode(ERRCODE_INVALID_ESCAPE_SEQUENCE),
     293             :                      errmsg("invalid escape string"),
     294       44632 :                      errhint("Escape string must be empty or one character.")));
     295           4 : 
     296       44628 :         e = VARDATA_ANY(esc);
     297             : 
     298             :         /*
     299         192 :          * If specified escape is '\', just copy the pattern as-is.
     300           4 :          */
     301         188 :         if (*e == '\\')
     302         188 :         {
     303           0 :             memcpy(result, pat, VARSIZE_ANY(pat));
     304           0 :             return result;
     305       44436 :         }
     306             : 
     307             :         /*
     308             :          * Otherwise, convert occurrences of the specified escape character to
     309             :          * '\', and double occurrences of '\' --- unless they immediately
     310             :          * follow an escape character!
     311             :          */
     312       74386 :         afterescape = false;
     313       29950 :         while (plen > 0)
     314             :         {
     315           0 :             if (CHAREQ(p, e) && !afterescape)
     316             :             {
     317           0 :                 *r++ = '\\';
     318           0 :                 NextChar(p, plen);
     319           0 :                 afterescape = true;
     320             :             }
     321           0 :             else if (*p == '\\')
     322             :             {
     323           0 :                 *r++ = '\\';
     324       44436 :                 if (!afterescape)
     325           0 :                     *r++ = '\\';
     326           4 :                 NextChar(p, plen);
     327           0 :                 afterescape = false;
     328             :             }
     329             :             else
     330           4 :             {
     331           0 :                 CopyAdvChar(r, p, plen);
     332           0 :                 afterescape = false;
     333       44432 :             }
     334             :         }
     335     2620418 :     }
     336             : 
     337     2600888 :     SET_VARSIZE(result, r - ((char *) result));
     338             : 
     339       32874 :     return result;
     340             : }
     341             : #endif                          /* do_like_escape */
     342       32874 : 
     343       24906 : #ifdef CHAREQ
     344             : #undef CHAREQ
     345             : #endif
     346     2575982 : 
     347             : #undef NextChar
     348             : #undef CopyAdvChar
     349             : #undef MatchText
     350             : 
     351             : #ifdef do_like_escape
     352             : #undef do_like_escape
     353       19530 : #endif
     354             : 
     355     1910448 : #undef GETCHAR
     356             : 
     357             : #ifdef MATCH_LOWER
     358        3490 : #undef MATCH_LOWER
     359        3490 : 
     360        3490 : #endif

Generated by: LCOV version 1.13