modules/libjar/nsWildCard.cpp

   1 /* -*- Mode: C; tab-width: 4; indent-tabs-mode: nil; c-basic-offset: 2 -*- */
   2 /* ***** BEGIN LICENSE BLOCK *****
   3  * Version: MPL 1.1/GPL 2.0/LGPL 2.1
   4  *
   5  * The contents of this file are subject to the Mozilla Public License Version
   6  * 1.1 (the "License"); you may not use this file except in compliance with
   7  * the License. You may obtain a copy of the License at
   8  * http://www.mozilla.org/MPL/
   9  *
  10  * Software distributed under the License is distributed on an "AS IS" basis,
  11  * WITHOUT WARRANTY OF ANY KIND, either express or implied. See the License
  12  * for the specific language governing rights and limitations under the
  13  * License.
  14  *
  15  * The Original Code is mozilla.org code.
  16  *
  17  * The Initial Developer of the Original Code is
  18  * Netscape Communications Corporation.
  19  * Portions created by the Initial Developer are Copyright (C) 1998
  20  * the Initial Developer. All Rights Reserved.
  21  *
  22  * Contributor(s):
  23  *
  24  * Alternatively, the contents of this file may be used under the terms of
  25  * either the GNU General Public License Version 2 or later (the "GPL"), or
  26  * the GNU Lesser General Public License Version 2.1 or later (the "LGPL"),
  27  * in which case the provisions of the GPL or the LGPL are applicable instead
  28  * of those above. If you wish to allow use of your version of this file only
  29  * under the terms of either the GPL or the LGPL, and not to allow others to
  30  * use your version of this file under the terms of the MPL, indicate your
  31  * decision by deleting the provisions above and replace them with the notice
  32  * and other provisions required by the GPL or the LGPL. If you do not delete
  33  * the provisions above, a recipient may use your version of this file under
  34  * the terms of any one of the MPL, the GPL or the LGPL.
  35  *
  36  * ***** END LICENSE BLOCK ***** */
  37
  38 /* *
  39  *
  40  *
  41  * nsWildCard.cpp: shell-like wildcard match routines
  42  *
  43  * See nsIZipReader.findEntries documentation in nsIZipReader.idl for
  44  * a description of the syntax supported by the routines in this file.
  45  *
  46  * Rob McCool
  47  *
  48  */
  49
  50 #include "nsWildCard.h"
  51 #include "plstr.h"
  52 #include "prmem.h"
  53
  54 /* ----------------------------- _valid_subexp ------------------------------ */
  55
  56
  57 static int
  58 _valid_subexp(char *expr, char stop)
  59 {
  60     register int x,y,t;
  61     int nsc,np,tld;
  62
  63     x=0;nsc=0;tld=0;
  64
  65     while(expr[x] && (expr[x] != stop)) {
  66         switch(expr[x]) {
  67           case '~':
  68             if(tld) return INVALID_SXP;
  69             else ++tld;
  70           case '*':
  71           case '?':
  72           case '^':
  73           case '$':
  74             ++nsc;
  75             break;
  76           case '[':
  77             ++nsc;
  78             if((!expr[++x]) || (expr[x] == ']'))
  79                 return INVALID_SXP;
  80             for(;expr[x] && (expr[x] != ']');++x)
  81                 if(expr[x] == '\\')
  82                     if(!expr[++x])
  83                         return INVALID_SXP;
  84             if(!expr[x])
  85                 return INVALID_SXP;
  86             break;
  87           case '(':
  88             ++nsc;np = 0;
  89             while(1) {
  90                 if(expr[++x] == ')')
  91                     return INVALID_SXP;
  92                 for(y=x;(expr[y]) && (expr[y] != '|') && (expr[y] != ')');++y)
  93                     if(expr[y] == '\\')
  94                         if(!expr[++y])
  95                             return INVALID_SXP;
  96                 if(!expr[y])
  97                     return INVALID_SXP;
  98                 if(expr[y] == '|')
  99                     ++np;
 100                 t = _valid_subexp(&expr[x],expr[y]);
 101                 if(t == INVALID_SXP)
 102                     return INVALID_SXP;
 103                 x+=t;
 104                 if(expr[x] == ')') {
 105                     if(!np)
 106                         return INVALID_SXP;
 107                     break;
 108                 }
 109             }
 110             break;
 111           case ')':
 112           case ']':
 113             return INVALID_SXP;
 114           case '\\':
 115             if(!expr[++x])
 116                 return INVALID_SXP;
 117           default:
 118             break;
 119         }
 120         ++x;
 121     }
 122     if((!stop) && (!nsc))
 123         return NON_SXP;
 124     return ((expr[x] == stop) ? x : INVALID_SXP);
 125 }
 126
 127 int
 128 NS_WildCardValid(char *expr)
 129 {
 130     int x;
 131
 132     x = _valid_subexp(expr, '\0');
 133     return (x < 0 ? x : VALID_SXP);
 134 }
 135
 136
 137 /* ----------------------------- _shexp_match ----------------------------- */
 138
 139
 140 #define MATCH 0
 141 #define NOMATCH 1
 142 #define ABORTED -1
 143
 144 static int _shexp_match(char *str, char *expr, PRBool case_insensitive);
 145
 146 static int
 147 _handle_union(char *str, char *expr, PRBool case_insensitive)
 148 {
 149     char *e2 = (char *) PR_Malloc(sizeof(char)*strlen(expr));
 150     register int t,p2,p1 = 1;
 151     int cp;
 152
 153     while(1) {
 154         for(cp=1;expr[cp] != ')';cp++)
 155             if(expr[cp] == '\\')
 156                 ++cp;
 157         for(p2 = 0;(expr[p1] != '|') && (p1 != cp);p1++,p2++) {
 158             if(expr[p1] == '\\')
 159                 e2[p2++] = expr[p1++];
 160             e2[p2] = expr[p1];
 161         }
 162         for (t=cp+1; ((e2[p2] = expr[t]) != 0); ++t,++p2) {}
 163         if(_shexp_match(str,e2, case_insensitive) == MATCH) {
 164             PR_Free(e2);
 165             return MATCH;
 166         }
 167         if(p1 == cp) {
 168             PR_Free(e2);
 169             return NOMATCH;
 170         }
 171         else ++p1;
 172     }
 173 }
 174
 175
 176 static int
 177 _shexp_match(char *str, char *expr, PRBool case_insensitive)
 178 {
 179     register int x,y;
 180     int ret,neg;
 181
 182     ret = 0;
 183     for(x=0,y=0;expr[y];++y,++x) {
 184         if((!str[x]) && (expr[y] != '(') && (expr[y] != '$') && (expr[y] != '*'))
 185             ret = ABORTED;
 186         else {
 187             switch(expr[y]) {
 188               case '$':
 189                 if( (str[x]) )
 190                     ret = NOMATCH;
 191                 else
 192                     --x;             /* we don't want loop to increment x */
 193                 break;
 194               case '*':
 195                 while(expr[++y] == '*'){}
 196                 if(!expr[y])
 197                     return MATCH;
 198                 while(str[x]) {
 199                     switch(_shexp_match(&str[x++],&expr[y], case_insensitive)) {
 200                     case NOMATCH:
 201                         continue;
 202                     case ABORTED:
 203                         ret = ABORTED;
 204                         break;
 205                     default:
 206                         return MATCH;
 207                     }
 208                     break;
 209                 }
 210                 if((expr[y] == '$') && (expr[y+1] == '\0') && (!str[x]))
 211                     return MATCH;
 212                 else
 213                     ret = ABORTED;
 214                 break;
 215               case '[':
 216                 neg = ((expr[++y] == '^') && (expr[y+1] != ']'));
 217                 if (neg)
 218                     ++y;
 219
 220                 if ((isalnum(expr[y])) && (expr[y+1] == '-') &&
 221                    (isalnum(expr[y+2])) && (expr[y+3] == ']'))
 222                     {
 223                         int start = expr[y], end = expr[y+2];
 224
 225                         /* Droolproofing for pinheads not included */
 226                         if(neg ^ ((str[x] < start) || (str[x] > end))) {
 227                             ret = NOMATCH;
 228                             break;
 229                         }
 230                         y+=3;
 231                     }
 232                 else {
 233                     int matched;
 234
 235                     for (matched=0;expr[y] != ']';y++) {
 236                         /* match an escaped ']' character */
 237                         if('\\' == expr[y] && ']' == expr[y+1]) {
 238                             if(']' == str[x])
 239                                 matched |= 1;
 240                             y++; /* move an extra char to compensate for '\\' */
 241                             continue;
 242                         }
 243                         matched |= (str[x] == expr[y]);
 244                     }
 245                     if (neg ^ (!matched))
 246                         ret = NOMATCH;
 247                 }
 248                 break;
 249               case '(':
 250                 return _handle_union(&str[x],&expr[y], case_insensitive);
 251                 break;
 252               case '?':
 253                 break;
 254               case '\\':
 255                 ++y;
 256               default:
 257                                 if(case_insensitive)
 258                                   {
 259                     if(toupper(str[x]) != toupper(expr[y]))
 260                         ret = NOMATCH;
 261                                   }
 262                                 else
 263                                   {
 264                     if(str[x] != expr[y])
 265                         ret = NOMATCH;
 266                                   }
 267                 break;
 268             }
 269         }
 270         if(ret)
 271             break;
 272     }
 273     return (ret ? ret : (str[x] ? NOMATCH : MATCH));
 274 }
 275
 276 int
 277 NS_WildCardMatch(char *str, char *xp, PRBool case_insensitive) {
 278     register int x;
 279     char *expr = PL_strdup(xp);
 280
 281         if(!expr)
 282                 return 1;
 283
 284     for(x=strlen(expr)-1;x;--x) {
 285         if((expr[x] == '~') && (expr[x-1] != '\\')) {
 286             expr[x] = '\0';
 287             if(_shexp_match(str,&expr[++x], case_insensitive) == MATCH)
 288                 goto punt;
 289             break;
 290         }
 291     }
 292     if(_shexp_match(str,expr, case_insensitive) == MATCH) {
 293         PR_Free(expr);
 294         return 0;
 295     }
 296
 297   punt:
 298     PR_Free(expr);
 299     return 1;
 300 }