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       /* fall through */
  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*)NS_Alloc((1 + nsCharTraits<T>::length(aExpr)) * sizeof(T));
 244   if (!e2) {
 245     return ABORTED;
 246   }
 247   for (sx = 1; ; ++sx) {
 248     /* Here, aExpr[sx] is one character past the preceding '(' or '|'. */
 249     /* Copy everything up to the next delimiter to e2 */
 250     count = ::_scan_and_copy(aExpr + sx, T(')'), T('|'), e2);
 251     if (count == ABORTED || !count) {
 252       ret = ABORTED;
 253       break;
 254     }
 255     sx += count;
 256     /* Append everything after closing parenthesis to e2. This is safe. */
 257     nsCharTraits<T>::copy(e2 + count, aExpr + cp,
 258                           nsCharTraits<T>::length(aExpr + cp) + 1);
 259     ret = ::_shexp_match(aStr, e2, aCaseInsensitive, aLevel + 1);
 260     if (ret != NOMATCH || !aExpr[sx] || aExpr[sx] == ')') {
 261       break;
 262     }
 263   }
 264   NS_Free(e2);
 265   if (sx < 2) {
 266     ret = ABORTED;
 267   }
 268   return ret;
 269 }
 270
 271 /* returns 1 if val is in range from start..end, case insensitive. */
 272 static int
 273 _is_char_in_range(unsigned char aStart, unsigned char aEnd, unsigned char aVal)
 274 {
 275   char map[256];
 276   memset(map, 0, sizeof(map));
 277   while (aStart <= aEnd) {
 278     map[lower(aStart++)] = 1;
 279   }
 280   return map[lower(aVal)];
 281 }
 282
 283 template<class T>
 284 static int
 285 _shexp_match(const T* aStr, const T* aExpr, bool aCaseInsensitive,
 286              unsigned int aLevel)
 287 {
 288   int x;   /* input string index */
 289   int y;   /* expression index */
 290   int ret, neg;
 291
 292   if (aLevel > 20) {    /* Don't let the stack get too deep. */
 293     return ABORTED;
 294   }
 295   for (x = 0, y = 0; aExpr[y]; ++y, ++x) {
 296     if (!aStr[x] && aExpr[y] != '$' && aExpr[y] != '*') {
 297       return NOMATCH;
 298     }
 299     switch (aExpr[y]) {
 300       case '$':
 301         if (aStr[x]) {
 302           return NOMATCH;
 303         }
 304         --x;                 /* we don't want loop to increment x */
 305         break;
 306       case '*':
 307         while (aExpr[++y] == '*') {
 308         }
 309         if (!aExpr[y]) {
 310           return MATCH;
 311         }
 312         while (aStr[x]) {
 313           ret = ::_shexp_match(&aStr[x++], &aExpr[y], aCaseInsensitive,
 314                                aLevel + 1);
 315           switch (ret) {
 316             case NOMATCH:
 317               continue;
 318             case ABORTED:
 319               return ABORTED;
 320             default:
 321               return MATCH;
 322           }
 323         }
 324         if (aExpr[y] == '$' && aExpr[y + 1] == '\0' && !aStr[x]) {
 325           return MATCH;
 326         } else {
 327           return NOMATCH;
 328         }
 329       case '[': {
 330         T start, end = 0;
 331         int i;
 332         neg = (aExpr[++y] == '^' && aExpr[y + 1] != ']');
 333         if (neg) {
 334           ++y;
 335         }
 336         i = y;
 337         start = aExpr[i++];
 338         if (start == '\\') {
 339           start = aExpr[i++];
 340         }
 341         if (::alphanumeric(start) && aExpr[i++] == '-') {
 342           end = aExpr[i++];
 343           if (end == '\\') {
 344             end = aExpr[i++];
 345           }
 346         }
 347         if (::alphanumeric(end) && aExpr[i] == ']') {
 348           /* This is a range form: a-b */
 349           T val = aStr[x];
 350           if (end < start) { /* swap them */
 351             T tmp = end;
 352             end = start;
 353             start = tmp;
 354           }
 355           if (aCaseInsensitive && ::alpha(val)) {
 356             val = ::_is_char_in_range((unsigned char)start,
 357                                       (unsigned char)end,
 358                                       (unsigned char)val);
 359             if (neg == val) {
 360               return NOMATCH;
 361             }
 362           } else if (neg != (val < start || val > end)) {
 363             return NOMATCH;
 364           }
 365           y = i;
 366         } else {
 367           /* Not range form */
 368           int matched = 0;
 369           for (; aExpr[y] != ']'; ++y) {
 370             if (aExpr[y] == '\\') {
 371               ++y;
 372             }
 373             if (aCaseInsensitive) {
 374               matched |= (::upper(aStr[x]) == ::upper(aExpr[y]));
 375             } else {
 376               matched |= (aStr[x] == aExpr[y]);
 377             }
 378           }
 379           if (neg == matched) {
 380             return NOMATCH;
 381           }
 382         }
 383       }
 384       break;
 385       case '(':
 386         if (!aExpr[y + 1]) {
 387           return ABORTED;
 388         }
 389         return ::_handle_union(&aStr[x], &aExpr[y], aCaseInsensitive,
 390                                aLevel + 1);
 391       case '?':
 392         break;
 393       case ')':
 394       case ']':
 395       case '|':
 396         return ABORTED;
 397       case '\\':
 398         ++y;
 399       /* fall through */
 400       default:
 401         if (aCaseInsensitive) {
 402           if (::upper(aStr[x]) != ::upper(aExpr[y])) {
 403             return NOMATCH;
 404           }
 405         } else {
 406           if (aStr[x] != aExpr[y]) {
 407             return NOMATCH;
 408           }
 409         }
 410         break;
 411     }
 412   }
 413   return (aStr[x] ? NOMATCH : MATCH);
 414 }
 415
 416
 417 template<class T>
 418 static int
 419 ns_WildCardMatch(const T* aStr, const T* aXp, bool aCaseInsensitive)
 420 {
 421   T* expr = nullptr;
 422   int ret = MATCH;
 423
 424   if (!nsCharTraits<T>::find(aXp, nsCharTraits<T>::length(aXp), T('~'))) {
 425     return ::_shexp_match(aStr, aXp, aCaseInsensitive, 0);
 426   }
 427
 428   expr = (T*)NS_Alloc((nsCharTraits<T>::length(aXp) + 1) * sizeof(T));
 429   if (!expr) {
 430     return NOMATCH;
 431   }
 432   memcpy(expr, aXp, (nsCharTraits<T>::length(aXp) + 1) * sizeof(T));
 433
 434   int x = ::_scan_and_copy(expr, T('~'), T('\0'), static_cast<T*>(nullptr));
 435   if (x != ABORTED && expr[x] == '~') {
 436     expr[x++] = '\0';
 437     ret = ::_shexp_match(aStr, &expr[x], aCaseInsensitive, 0);
 438     switch (ret) {
 439       case NOMATCH:
 440         ret = MATCH;
 441         break;
 442       case MATCH:
 443         ret = NOMATCH;
 444         break;
 445       default:
 446         break;
 447     }
 448   }
 449   if (ret == MATCH) {
 450     ret = ::_shexp_match(aStr, expr, aCaseInsensitive, 0);
 451   }
 452
 453   NS_Free(expr);
 454   return ret;
 455 }
 456
 457 template<class T>
 458 int
 459 NS_WildCardMatch_(const T* aStr, const T* aExpr, bool aCaseInsensitive)
 460 {
 461   int is_valid = NS_WildCardValid(aExpr);
 462   switch (is_valid) {
 463     case INVALID_SXP:
 464       return -1;
 465     default:
 466       return ::ns_WildCardMatch(aStr, aExpr, aCaseInsensitive);
 467   }
 468 }
 469
 470 int
 471 NS_WildCardMatch(const char* aStr, const char* aXp, bool aCaseInsensitive)
 472 {
 473   return NS_WildCardMatch_(aStr, aXp, aCaseInsensitive);
 474 }
 475
 476 int
 477 NS_WildCardMatch(const char16_t* aStr, const char16_t* aXp,
 478                  bool aCaseInsensitive)
 479 {
 480   return NS_WildCardMatch_(aStr, aXp, aCaseInsensitive);
 481 }