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