xpcom/io/nsWildCard.cpp

   1 /* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 2 -*- */
   2 /* vim: set ts=8 sts=2 et sw=2 tw=80: */
   3 /* This Source Code Form is subject to the terms of the Mozilla Public
   4  * License, v. 2.0. If a copy of the MPL was not distributed with this
   5  * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
   6
   7 /* *
   8  *
   9  *
  10  * nsWildCard.cpp: shell-like wildcard match routines
  11  *
  12  * See nsIZipReader.findEntries documentation in nsIZipReader.idl for
  13  * a description of the syntax supported by the routines in this file.
  14  *
  15  * Rob McCool
  16  *
  17  */
  18
  19 #include "nsWildCard.h"
  20 #include "nsXPCOM.h"
  21 #include "nsCRTGlue.h"
  22 #include "nsCharTraits.h"
  23
  24 /* -------------------- ASCII-specific character methods ------------------- */
  25
  26 typedef int static_assert_character_code_arrangement['a' > 'A' ? 1 : -1];
  27
  28 template <class T>
  29 static int alpha(T aChar) {
  30   return ('a' <= aChar && aChar <= 'z') || ('A' <= aChar && aChar <= 'Z');
  31 }
  32
  33 template <class T>
  34 static int alphanumeric(T aChar) {
  35   return ('0' <= aChar && aChar <= '9') || ::alpha(aChar);
  36 }
  37
  38 template <class T>
  39 static int lower(T aChar) {
  40   return ('A' <= aChar && aChar <= 'Z') ? aChar + ('a' - 'A') : aChar;
  41 }
  42
  43 template <class T>
  44 static int upper(T aChar) {
  45   return ('a' <= aChar && aChar <= 'z') ? aChar - ('a' - 'A') : aChar;
  46 }
  47
  48 /* ----------------------------- _valid_subexp ---------------------------- */
  49
  50 template <class T>
  51 static int _valid_subexp(const T* aExpr, T aStop1, T aStop2) {
  52   int x;
  53   int nsc = 0; /* Number of special characters */
  54   int np;      /* Number of pipe characters in union */
  55   int tld = 0; /* Number of tilde characters */
  56
  57   for (x = 0; aExpr[x] && (aExpr[x] != aStop1) && (aExpr[x] != aStop2); ++x) {
  58     switch (aExpr[x]) {
  59       case '~':
  60         if (tld) { /* at most one exclusion */
  61           return INVALID_SXP;
  62         }
  63         if (aStop1) { /* no exclusions within unions */
  64           return INVALID_SXP;
  65         }
  66         if (!aExpr[x + 1]) { /* exclusion cannot be last character */
  67           return INVALID_SXP;
  68         }
  69         if (!x) { /* exclusion cannot be first character */
  70           return INVALID_SXP;
  71         }
  72         ++tld;
  73         [[fallthrough]];
  74       case '*':
  75       case '?':
  76       case '$':
  77         ++nsc;
  78         break;
  79       case '[':
  80         ++nsc;
  81         if ((!aExpr[++x]) || (aExpr[x] == ']')) {
  82           return INVALID_SXP;
  83         }
  84         for (; aExpr[x] && (aExpr[x] != ']'); ++x) {
  85           if (aExpr[x] == '\\' && !aExpr[++x]) {
  86             return INVALID_SXP;
  87           }
  88         }
  89         if (!aExpr[x]) {
  90           return INVALID_SXP;
  91         }
  92         break;
  93       case '(':
  94         ++nsc;
  95         if (aStop1) { /* no nested unions */
  96           return INVALID_SXP;
  97         }
  98         np = -1;
  99         do {
 100           int t = ::_valid_subexp(&aExpr[++x], T(')'), T('|'));
 101           if (t == 0 || t == INVALID_SXP) {
 102             return INVALID_SXP;
 103           }
 104           x += t;
 105           if (!aExpr[x]) {
 106             return INVALID_SXP;
 107           }
 108           ++np;
 109         } while (aExpr[x] == '|');
 110         if (np < 1) { /* must be at least one pipe */
 111           return INVALID_SXP;
 112         }
 113         break;
 114       case ')':
 115       case ']':
 116       case '|':
 117         return INVALID_SXP;
 118       case '\\':
 119         ++nsc;
 120         if (!aExpr[++x]) {
 121           return INVALID_SXP;
 122         }
 123         break;
 124       default:
 125         break;
 126     }
 127   }
 128   if (!aStop1 && !nsc) { /* must be at least one special character */
 129     return NON_SXP;
 130   }
 131   return ((aExpr[x] == aStop1 || aExpr[x] == aStop2) ? x : INVALID_SXP);
 132 }
 133
 134 template <class T>
 135 int NS_WildCardValid_(const T* aExpr) {
 136   int x = ::_valid_subexp(aExpr, T('\0'), T('\0'));
 137   return (x < 0 ? x : VALID_SXP);
 138 }
 139
 140 int NS_WildCardValid(const char* aExpr) { return NS_WildCardValid_(aExpr); }
 141
 142 int NS_WildCardValid(const char16_t* aExpr) { return NS_WildCardValid_(aExpr); }
 143
 144 /* ----------------------------- _shexp_match ----------------------------- */
 145
 146 #define MATCH 0
 147 #define NOMATCH 1
 148 #define ABORTED -1
 149
 150 template <class T>
 151 static int _shexp_match(const T* aStr, const T* aExpr, bool aCaseInsensitive,
 152                         unsigned int aLevel);
 153
 154 /**
 155  * Count characters until we reach a NUL character or either of the
 156  * two delimiter characters, stop1 or stop2.  If we encounter a bracketed
 157  * expression, look only for NUL or ']' inside it.  Do not look for stop1
 158  * or stop2 inside it. Return ABORTED if bracketed expression is unterminated.
 159  * Handle all escaping.
 160  * Return index in input string of first stop found, or ABORTED if not found.
 161  * If "dest" is non-nullptr, copy counted characters to it and null terminate.
 162  */
 163 template <class T>
 164 static int _scan_and_copy(const T* aExpr, T aStop1, T aStop2, T* aDest) {
 165   int sx; /* source index */
 166   T cc;
 167
 168   for (sx = 0; (cc = aExpr[sx]) && cc != aStop1 && cc != aStop2; ++sx) {
 169     if (cc == '\\') {
 170       if (!aExpr[++sx]) {
 171         return ABORTED; /* should be impossible */
 172       }
 173     } else if (cc == '[') {
 174       while ((cc = aExpr[++sx]) && cc != ']') {
 175         if (cc == '\\' && !aExpr[++sx]) {
 176           return ABORTED;
 177         }
 178       }
 179       if (!cc) {
 180         return ABORTED; /* should be impossible */
 181       }
 182     }
 183   }
 184   if (aDest && sx) {
 185     /* Copy all but the closing delimiter. */
 186     memcpy(aDest, aExpr, sx * sizeof(T));
 187     aDest[sx] = 0;
 188   }
 189   return cc ? sx : ABORTED; /* index of closing delimiter */
 190 }
 191
 192 /* On input, expr[0] is the opening parenthesis of a union.
 193  * See if any of the alternatives in the union matches as a pattern.
 194  * The strategy is to take each of the alternatives, in turn, and append
 195  * the rest of the expression (after the closing ')' that marks the end of
 196  * this union) to that alternative, and then see if the resultant expression
 197  * matches the input string.  Repeat this until some alternative matches,
 198  * or we have an abort.
 199  */
 200 template <class T>
 201 static int _handle_union(const T* aStr, const T* aExpr, bool aCaseInsensitive,
 202                          unsigned int aLevel) {
 203   int sx; /* source index */
 204   int cp; /* source index of closing parenthesis */
 205   int count;
 206   int ret = NOMATCH;
 207   T* e2;
 208
 209   /* Find the closing parenthesis that ends this union in the expression */
 210   cp = ::_scan_and_copy(aExpr, T(')'), T('\0'), static_cast<T*>(nullptr));
 211   if (cp == ABORTED || cp < 4) { /* must be at least "(a|b" before ')' */
 212     return ABORTED;
 213   }
 214   ++cp; /* now index of char after closing parenthesis */
 215   e2 = (T*)moz_xmalloc((1 + nsCharTraits<T>::length(aExpr)) * sizeof(T));
 216   for (sx = 1;; ++sx) {
 217     /* Here, aExpr[sx] is one character past the preceding '(' or '|'. */
 218     /* Copy everything up to the next delimiter to e2 */
 219     count = ::_scan_and_copy(aExpr + sx, T(')'), T('|'), e2);
 220     if (count == ABORTED || !count) {
 221       ret = ABORTED;
 222       break;
 223     }
 224     sx += count;
 225     /* Append everything after closing parenthesis to e2. This is safe. */
 226     nsCharTraits<T>::copy(e2 + count, aExpr + cp,
 227                           nsCharTraits<T>::length(aExpr + cp) + 1);
 228     ret = ::_shexp_match(aStr, e2, aCaseInsensitive, aLevel + 1);
 229     if (ret != NOMATCH || !aExpr[sx] || aExpr[sx] == ')') {
 230       break;
 231     }
 232   }
 233   free(e2);
 234   if (sx < 2) {
 235     ret = ABORTED;
 236   }
 237   return ret;
 238 }
 239
 240 /* returns 1 if val is in range from start..end, case insensitive. */
 241 static int _is_char_in_range(unsigned char aStart, unsigned char aEnd,
 242                              unsigned char aVal) {
 243   char map[256];
 244   memset(map, 0, sizeof(map));
 245   while (aStart <= aEnd) {
 246     map[lower(aStart++)] = 1;
 247   }
 248   return map[lower(aVal)];
 249 }
 250
 251 template <class T>
 252 static int _shexp_match(const T* aStr, const T* aExpr, bool aCaseInsensitive,
 253                         unsigned int aLevel) {
 254   int x; /* input string index */
 255   int y; /* expression index */
 256   int ret, neg;
 257
 258   if (aLevel > 20) { /* Don't let the stack get too deep. */
 259     return ABORTED;
 260   }
 261   for (x = 0, y = 0; aExpr[y]; ++y, ++x) {
 262     if (!aStr[x] && aExpr[y] != '$' && aExpr[y] != '*') {
 263       return NOMATCH;
 264     }
 265     switch (aExpr[y]) {
 266       case '$':
 267         if (aStr[x]) {
 268           return NOMATCH;
 269         }
 270         --x; /* we don't want loop to increment x */
 271         break;
 272       case '*':
 273         while (aExpr[++y] == '*') {
 274         }
 275         if (!aExpr[y]) {
 276           return MATCH;
 277         }
 278         while (aStr[x]) {
 279           ret = ::_shexp_match(&aStr[x++], &aExpr[y], aCaseInsensitive,
 280                                aLevel + 1);
 281           switch (ret) {
 282             case NOMATCH:
 283               continue;
 284             case ABORTED:
 285               return ABORTED;
 286             default:
 287               return MATCH;
 288           }
 289         }
 290         if (aExpr[y] == '$' && aExpr[y + 1] == '\0' && !aStr[x]) {
 291           return MATCH;
 292         } else {
 293           return NOMATCH;
 294         }
 295       case '[': {
 296         T start, end = 0;
 297         int i;
 298         ++y;
 299         neg = (aExpr[y] == '^' && aExpr[y + 1] != ']');
 300         if (neg) {
 301           ++y;
 302         }
 303         i = y;
 304         start = aExpr[i++];
 305         if (start == '\\') {
 306           start = aExpr[i++];
 307         }
 308         if (::alphanumeric(start) && aExpr[i++] == '-') {
 309           end = aExpr[i++];
 310           if (end == '\\') {
 311             end = aExpr[i++];
 312           }
 313         }
 314         if (::alphanumeric(end) && aExpr[i] == ']') {
 315           /* This is a range form: a-b */
 316           T val = aStr[x];
 317           if (end < start) { /* swap them */
 318             T tmp = end;
 319             end = start;
 320             start = tmp;
 321           }
 322           if (aCaseInsensitive && ::alpha(val)) {
 323             val = ::_is_char_in_range((unsigned char)start, (unsigned char)end,
 324                                       (unsigned char)val);
 325             if (neg == val) {
 326               return NOMATCH;
 327             }
 328           } else if (neg != (val < start || val > end)) {
 329             return NOMATCH;
 330           }
 331           y = i;
 332         } else {
 333           /* Not range form */
 334           int matched = 0;
 335           for (; aExpr[y] != ']'; ++y) {
 336             if (aExpr[y] == '\\') {
 337               ++y;
 338             }
 339             if (aCaseInsensitive) {
 340               matched |= (::upper(aStr[x]) == ::upper(aExpr[y]));
 341             } else {
 342               matched |= (aStr[x] == aExpr[y]);
 343             }
 344           }
 345           if (neg == matched) {
 346             return NOMATCH;
 347           }
 348         }
 349       } break;
 350       case '(':
 351         if (!aExpr[y + 1]) {
 352           return ABORTED;
 353         }
 354         return ::_handle_union(&aStr[x], &aExpr[y], aCaseInsensitive,
 355                                aLevel + 1);
 356       case '?':
 357         break;
 358       case ')':
 359       case ']':
 360       case '|':
 361         return ABORTED;
 362       case '\\':
 363         ++y;
 364         [[fallthrough]];
 365       default:
 366         if (aCaseInsensitive) {
 367           if (::upper(aStr[x]) != ::upper(aExpr[y])) {
 368             return NOMATCH;
 369           }
 370         } else {
 371           if (aStr[x] != aExpr[y]) {
 372             return NOMATCH;
 373           }
 374         }
 375         break;
 376     }
 377   }
 378   return (aStr[x] ? NOMATCH : MATCH);
 379 }
 380
 381 template <class T>
 382 static int ns_WildCardMatch(const T* aStr, const T* aXp,
 383                             bool aCaseInsensitive) {
 384   T* expr = nullptr;
 385   int ret = MATCH;
 386
 387   if (!nsCharTraits<T>::find(aXp, nsCharTraits<T>::length(aXp), T('~'))) {
 388     return ::_shexp_match(aStr, aXp, aCaseInsensitive, 0);
 389   }
 390
 391   expr = (T*)moz_xmalloc((nsCharTraits<T>::length(aXp) + 1) * sizeof(T));
 392   memcpy(expr, aXp, (nsCharTraits<T>::length(aXp) + 1) * sizeof(T));
 393
 394   int x = ::_scan_and_copy(expr, T('~'), T('\0'), static_cast<T*>(nullptr));
 395   if (x != ABORTED && expr[x] == '~') {
 396     expr[x++] = '\0';
 397     ret = ::_shexp_match(aStr, &expr[x], aCaseInsensitive, 0);
 398     switch (ret) {
 399       case NOMATCH:
 400         ret = MATCH;
 401         break;
 402       case MATCH:
 403         ret = NOMATCH;
 404         break;
 405       default:
 406         break;
 407     }
 408   }
 409   if (ret == MATCH) {
 410     ret = ::_shexp_match(aStr, expr, aCaseInsensitive, 0);
 411   }
 412
 413   free(expr);
 414   return ret;
 415 }
 416
 417 template <class T>
 418 int NS_WildCardMatch_(const T* aStr, const T* aExpr, bool aCaseInsensitive) {
 419   int is_valid = NS_WildCardValid(aExpr);
 420   switch (is_valid) {
 421     case INVALID_SXP:
 422       return -1;
 423     default:
 424       return ::ns_WildCardMatch(aStr, aExpr, aCaseInsensitive);
 425   }
 426 }
 427
 428 int NS_WildCardMatch(const char* aStr, const char* aXp, bool aCaseInsensitive) {
 429   return NS_WildCardMatch_(aStr, aXp, aCaseInsensitive);
 430 }
 431
 432 int NS_WildCardMatch(const char16_t* aStr, const char16_t* aXp,
 433                      bool aCaseInsensitive) {
 434   return NS_WildCardMatch_(aStr, aXp, aCaseInsensitive);
 435 }