granicus.if.org Git - postgresql/blob - src/backend/utils/adt/like_match.c

   1 /*-------------------------------------------------------------------------
   2  *
   3  * like_match.c
   4  *        like expression handling internal code.
   5  *
   6  * This file is included by like.c *twice* if multibyte is enabled.
   7  * This is for an optimization of single byte encodings.
   8  * Before the inclusion, we need to define following macros:
   9  *
  10  * CHAREQ
  11  * ICHAREQ
  12  * NextChar
  13  * CopyAdvChar
  14  * MatchText (MBMatchText)
  15  * MatchTextIC (MBMatchTextIC)
  16  * do_like_escape (MB_do_like_escape)
  17  *
  18  * Copyright (c) 1996-2002, PostgreSQL Global Development Group
  19  *
  20  * IDENTIFICATION
  21  *      $Header: /cvsroot/pgsql/src/backend/utils/adt/like_match.c,v 1.3 2002/06/20 20:29:37 momjian Exp $
  22  *
  23  *-------------------------------------------------------------------------
  24  */
  25
  26 /*
  27 **      Originally written by Rich $alz, mirror!rs, Wed Nov 26 19:03:17 EST 1986.
  28 **      Rich $alz is now <rsalz@bbn.com>.
  29 **      Special thanks to Lars Mathiesen <thorinn@diku.dk> for the LABORT code.
  30 **
  31 **      This code was shamelessly stolen from the "pql" code by myself and
  32 **      slightly modified :)
  33 **
  34 **      All references to the word "star" were replaced by "percent"
  35 **      All references to the word "wild" were replaced by "like"
  36 **
  37 **      All the nice shell RE matching stuff was replaced by just "_" and "%"
  38 **
  39 **      As I don't have a copy of the SQL standard handy I wasn't sure whether
  40 **      to leave in the '\' escape character handling.
  41 **
  42 **      Keith Parks. <keith@mtcc.demon.co.uk>
  43 **
  44 **      SQL92 lets you specify the escape character by saying
  45 **      LIKE <pattern> ESCAPE <escape character>. We are a small operation
  46 **      so we force you to use '\'. - ay 7/95
  47 **
  48 **      Now we have the like_escape() function that converts patterns with
  49 **      any specified escape character (or none at all) to the internal
  50 **      default escape character, which is still '\'. - tgl 9/2000
  51 **
  52 ** The code is rewritten to avoid requiring null-terminated strings,
  53 ** which in turn allows us to leave out some memcpy() operations.
  54 ** This code should be faster and take less memory, but no promises...
  55 ** - thomas 2000-08-06
  56 **
  57 */
  58
  59
  60 /*--------------------
  61  *      Match text and p, return LIKE_TRUE, LIKE_FALSE, or LIKE_ABORT.
  62  *
  63  *      LIKE_TRUE: they match
  64  *      LIKE_FALSE: they don't match
  65  *      LIKE_ABORT: not only don't they match, but the text is too short.
  66  *
  67  * If LIKE_ABORT is returned, then no suffix of the text can match the
  68  * pattern either, so an upper-level % scan can stop scanning now.
  69  *--------------------
  70  */
  71
  72 static int
  73 MatchText(unsigned char *t, int tlen, unsigned char *p, int plen)
  74 {
  75         /* Fast path for match-everything pattern */
  76         if ((plen == 1) && (*p == '%'))
  77                 return LIKE_TRUE;
  78
  79         while ((tlen > 0) && (plen > 0))
  80         {
  81                 if (*p == '\\')
  82                 {
  83                         /* Next pattern char must match literally, whatever it is */
  84                         NextChar(p, plen);
  85                         if ((plen <= 0) || !CHAREQ(t, p))
  86                                 return LIKE_FALSE;
  87                 }
  88                 else if (*p == '%')
  89                 {
  90                         /* %% is the same as % according to the SQL standard */
  91                         /* Advance past all %'s */
  92                         while ((plen > 0) && (*p == '%'))
  93                                 NextChar(p, plen);
  94                         /* Trailing percent matches everything. */
  95                         if (plen <= 0)
  96                                 return LIKE_TRUE;
  97
  98                         /*
  99                          * Otherwise, scan for a text position at which we can match
 100                          * the rest of the pattern.
 101                          */
 102                         while (tlen > 0)
 103                         {
 104                                 /*
 105                                  * Optimization to prevent most recursion: don't recurse
 106                                  * unless first pattern char might match this text char.
 107                                  */
 108                                 if (CHAREQ(t, p) || (*p == '\\') || (*p == '_'))
 109                                 {
 110                                         int                     matched = MatchText(t, tlen, p, plen);
 111
 112                                         if (matched != LIKE_FALSE)
 113                                                 return matched; /* TRUE or ABORT */
 114                                 }
 115
 116                                 NextChar(t, tlen);
 117                         }
 118
 119                         /*
 120                          * End of text with no match, so no point in trying later
 121                          * places to start matching this pattern.
 122                          */
 123                         return LIKE_ABORT;
 124                 }
 125                 else if ((*p != '_') && !CHAREQ(t, p))
 126                 {
 127                         /*
 128                          * Not the single-character wildcard and no explicit match?
 129                          * Then time to quit...
 130                          */
 131                         return LIKE_FALSE;
 132                 }
 133
 134                 NextChar(t, tlen);
 135                 NextChar(p, plen);
 136         }
 137
 138         if (tlen > 0)
 139                 return LIKE_FALSE;              /* end of pattern, but not of text */
 140
 141         /* End of input string.  Do we have matching pattern remaining? */
 142         while ((plen > 0) && (*p == '%'))       /* allow multiple %'s at end of
 143                                                                                  * pattern */
 144                 NextChar(p, plen);
 145         if (plen <= 0)
 146                 return LIKE_TRUE;
 147
 148         /*
 149          * End of text with no match, so no point in trying later places to
 150          * start matching this pattern.
 151          */
 152         return LIKE_ABORT;
 153 }       /* MatchText() */
 154
 155 /*
 156  * Same as above, but ignore case
 157  */
 158 static int
 159 MatchTextIC(unsigned char *t, int tlen, unsigned char *p, int plen)
 160 {
 161         /* Fast path for match-everything pattern */
 162         if ((plen == 1) && (*p == '%'))
 163                 return LIKE_TRUE;
 164
 165         while ((tlen > 0) && (plen > 0))
 166         {
 167                 if (*p == '\\')
 168                 {
 169                         /* Next pattern char must match literally, whatever it is */
 170                         NextChar(p, plen);
 171                         if ((plen <= 0) || !ICHAREQ(t, p))
 172                                 return LIKE_FALSE;
 173                 }
 174                 else if (*p == '%')
 175                 {
 176                         /* %% is the same as % according to the SQL standard */
 177                         /* Advance past all %'s */
 178                         while ((plen > 0) && (*p == '%'))
 179                                 NextChar(p, plen);
 180                         /* Trailing percent matches everything. */
 181                         if (plen <= 0)
 182                                 return LIKE_TRUE;
 183
 184                         /*
 185                          * Otherwise, scan for a text position at which we can match
 186                          * the rest of the pattern.
 187                          */
 188                         while (tlen > 0)
 189                         {
 190                                 /*
 191                                  * Optimization to prevent most recursion: don't recurse
 192                                  * unless first pattern char might match this text char.
 193                                  */
 194                                 if (ICHAREQ(t, p) || (*p == '\\') || (*p == '_'))
 195                                 {
 196                                         int                     matched = MatchTextIC(t, tlen, p, plen);
 197
 198                                         if (matched != LIKE_FALSE)
 199                                                 return matched; /* TRUE or ABORT */
 200                                 }
 201
 202                                 NextChar(t, tlen);
 203                         }
 204
 205                         /*
 206                          * End of text with no match, so no point in trying later
 207                          * places to start matching this pattern.
 208                          */
 209                         return LIKE_ABORT;
 210                 }
 211                 else if ((*p != '_') && !ICHAREQ(t, p))
 212                 {
 213                         /*
 214                          * Not the single-character wildcard and no explicit match?
 215                          * Then time to quit...
 216                          */
 217                         return LIKE_FALSE;
 218                 }
 219
 220                 NextChar(t, tlen);
 221                 NextChar(p, plen);
 222         }
 223
 224         if (tlen > 0)
 225                 return LIKE_FALSE;              /* end of pattern, but not of text */
 226
 227         /* End of input string.  Do we have matching pattern remaining? */
 228         while ((plen > 0) && (*p == '%'))       /* allow multiple %'s at end of
 229                                                                                  * pattern */
 230                 NextChar(p, plen);
 231         if (plen <= 0)
 232                 return LIKE_TRUE;
 233
 234         /*
 235          * End of text with no match, so no point in trying later places to
 236          * start matching this pattern.
 237          */
 238         return LIKE_ABORT;
 239 }       /* MatchTextIC() */
 240
 241 /*
 242  * like_escape() --- given a pattern and an ESCAPE string,
 243  * convert the pattern to use Postgres' standard backslash escape convention.
 244  */
 245 static text *
 246 do_like_escape(text *pat, text *esc)
 247 {
 248         text       *result;
 249         unsigned char *p,
 250                            *e,
 251                            *r;
 252         int                     plen,
 253                                 elen;
 254         bool            afterescape;
 255
 256         p = VARDATA(pat);
 257         plen = (VARSIZE(pat) - VARHDRSZ);
 258         e = VARDATA(esc);
 259         elen = (VARSIZE(esc) - VARHDRSZ);
 260
 261         /*
 262          * Worst-case pattern growth is 2x --- unlikely, but it's hardly worth
 263          * trying to calculate the size more accurately than that.
 264          */
 265         result = (text *) palloc(plen * 2 + VARHDRSZ);
 266         r = VARDATA(result);
 267
 268         if (elen == 0)
 269         {
 270                 /*
 271                  * No escape character is wanted.  Double any backslashes in the
 272                  * pattern to make them act like ordinary characters.
 273                  */
 274                 while (plen > 0)
 275                 {
 276                         if (*p == '\\')
 277                                 *r++ = '\\';
 278                         CopyAdvChar(r, p, plen);
 279                 }
 280         }
 281         else
 282         {
 283                 /*
 284                  * The specified escape must be only a single character.
 285                  */
 286                 NextChar(e, elen);
 287                 if (elen != 0)
 288                         elog(ERROR, "ESCAPE string must be empty or one character");
 289                 e = VARDATA(esc);
 290
 291                 /*
 292                  * If specified escape is '\', just copy the pattern as-is.
 293                  */
 294                 if (*e == '\\')
 295                 {
 296                         memcpy(result, pat, VARSIZE(pat));
 297                         return result;
 298                 }
 299
 300                 /*
 301                  * Otherwise, convert occurrences of the specified escape
 302                  * character to '\', and double occurrences of '\' --- unless they
 303                  * immediately follow an escape character!
 304                  */
 305                 afterescape = false;
 306                 while (plen > 0)
 307                 {
 308                         if (CHAREQ(p, e) && !afterescape)
 309                         {
 310                                 *r++ = '\\';
 311                                 NextChar(p, plen);
 312                                 afterescape = true;
 313                         }
 314                         else if (*p == '\\')
 315                         {
 316                                 *r++ = '\\';
 317                                 if (!afterescape)
 318                                         *r++ = '\\';
 319                                 NextChar(p, plen);
 320                                 afterescape = false;
 321                         }
 322                         else
 323                         {
 324                                 CopyAdvChar(r, p, plen);
 325                                 afterescape = false;
 326                         }
 327                 }
 328         }
 329
 330         VARATT_SIZEP(result) = r - ((unsigned char *) result);
 331
 332         return result;
 333 }