Back to index

lightning-sunbird  0.9+nobinonly
nsWildCard.cpp
Go to the documentation of this file.
00001 /* -*- Mode: C; tab-width: 4; indent-tabs-mode: nil; c-basic-offset: 2 -*- */
00002 /* ***** BEGIN LICENSE BLOCK *****
00003  * Version: MPL 1.1/GPL 2.0/LGPL 2.1
00004  *
00005  * The contents of this file are subject to the Mozilla Public License Version
00006  * 1.1 (the "License"); you may not use this file except in compliance with
00007  * the License. You may obtain a copy of the License at
00008  * http://www.mozilla.org/MPL/
00009  *
00010  * Software distributed under the License is distributed on an "AS IS" basis,
00011  * WITHOUT WARRANTY OF ANY KIND, either express or implied. See the License
00012  * for the specific language governing rights and limitations under the
00013  * License.
00014  *
00015  * The Original Code is mozilla.org code.
00016  *
00017  * The Initial Developer of the Original Code is
00018  * Netscape Communications Corporation.
00019  * Portions created by the Initial Developer are Copyright (C) 1998
00020  * the Initial Developer. All Rights Reserved.
00021  *
00022  * Contributor(s):
00023  *
00024  * Alternatively, the contents of this file may be used under the terms of
00025  * either the GNU General Public License Version 2 or later (the "GPL"), or
00026  * the GNU Lesser General Public License Version 2.1 or later (the "LGPL"),
00027  * in which case the provisions of the GPL or the LGPL are applicable instead
00028  * of those above. If you wish to allow use of your version of this file only
00029  * under the terms of either the GPL or the LGPL, and not to allow others to
00030  * use your version of this file under the terms of the MPL, indicate your
00031  * decision by deleting the provisions above and replace them with the notice
00032  * and other provisions required by the GPL or the LGPL. If you do not delete
00033  * the provisions above, a recipient may use your version of this file under
00034  * the terms of any one of the MPL, the GPL or the LGPL.
00035  *
00036  * ***** END LICENSE BLOCK ***** */
00037 
00038 /* *
00039  * 
00040  *
00041  * shexp.c: shell-like wildcard match routines
00042  *
00043  * See shexp.h for public documentation.
00044  *
00045  * Rob McCool
00046  * 
00047  */
00048 
00049 #include "nsWildCard.h"
00050 #include "plstr.h"
00051 #include "prmem.h"
00052 
00053 /* ----------------------------- shexp_valid ------------------------------ */
00054 
00055 
00056 static int 
00057 _valid_subexp(char *expr, char stop) 
00058 {
00059     register int x,y,t;
00060     int nsc,np,tld;
00061 
00062     x=0;nsc=0;tld=0;
00063 
00064     while(expr[x] && (expr[x] != stop)) {
00065         switch(expr[x]) {
00066           case '~':
00067             if(tld) return INVALID_SXP;
00068             else ++tld;
00069           case '*':
00070           case '?':
00071           case '^':
00072           case '$':
00073             ++nsc;
00074             break;
00075           case '[':
00076             ++nsc;
00077             if((!expr[++x]) || (expr[x] == ']'))
00078                 return INVALID_SXP;
00079             for(++x;expr[x] && (expr[x] != ']');++x)
00080                 if(expr[x] == '\\')
00081                     if(!expr[++x])
00082                         return INVALID_SXP;
00083             if(!expr[x])
00084                 return INVALID_SXP;
00085             break;
00086           case '(':
00087             ++nsc;np = 0;
00088             while(1) {
00089                 if(expr[++x] == ')')
00090                     return INVALID_SXP;
00091                 for(y=x;(expr[y]) && (expr[y] != '|') && (expr[y] != ')');++y)
00092                     if(expr[y] == '\\')
00093                         if(!expr[++y])
00094                             return INVALID_SXP;
00095                 if(!expr[y])
00096                     return INVALID_SXP;
00097                 if(expr[y] == '|')
00098                     ++np;
00099                 t = _valid_subexp(&expr[x],expr[y]);
00100                 if(t == INVALID_SXP)
00101                     return INVALID_SXP;
00102                 x+=t;
00103                 if(expr[x] == ')') {
00104                     if(!np)
00105                         return INVALID_SXP;
00106                     break;
00107                 }
00108             }
00109             break;
00110           case ')':
00111           case ']':
00112             return INVALID_SXP;
00113           case '\\':
00114             if(!expr[++x])
00115                 return INVALID_SXP;
00116           default:
00117             break;
00118         }
00119         ++x;
00120     }
00121     if((!stop) && (!nsc))
00122         return NON_SXP;
00123     return ((expr[x] == stop) ? x : INVALID_SXP);
00124 }
00125 
00126 int 
00127 NS_WildCardValid(char *expr) 
00128 {
00129     int x;
00130 
00131     x = _valid_subexp(expr, '\0');
00132     return (x < 0 ? x : VALID_SXP);
00133 }
00134 
00135 
00136 /* ----------------------------- shexp_match ----------------------------- */
00137 
00138 
00139 #define MATCH 0
00140 #define NOMATCH 1
00141 #define ABORTED -1
00142 
00143 static int _shexp_match(char *str, char *expr, PRBool case_insensitive);
00144 
00145 static int 
00146 _handle_union(char *str, char *expr, PRBool case_insensitive) 
00147 {
00148     char *e2 = (char *) PR_Malloc(sizeof(char)*strlen(expr));
00149     register int t,p2,p1 = 1;
00150     int cp;
00151 
00152     while(1) {
00153         for(cp=1;expr[cp] != ')';cp++)
00154             if(expr[cp] == '\\')
00155                 ++cp;
00156         for(p2 = 0;(expr[p1] != '|') && (p1 != cp);p1++,p2++) {
00157             if(expr[p1] == '\\')
00158                 e2[p2++] = expr[p1++];
00159             e2[p2] = expr[p1];
00160         }
00161         for (t=cp+1; ((e2[p2] = expr[t]) != 0); ++t,++p2) {}
00162         if(_shexp_match(str,e2, case_insensitive) == MATCH) {
00163             PR_Free(e2);
00164             return MATCH;
00165         }
00166         if(p1 == cp) {
00167             PR_Free(e2);
00168             return NOMATCH;
00169         }
00170         else ++p1;
00171     }
00172 }
00173 
00174 
00175 static int 
00176 _shexp_match(char *str, char *expr, PRBool case_insensitive) 
00177 {
00178     register int x,y;
00179     int ret,neg;
00180 
00181     ret = 0;
00182     for(x=0,y=0;expr[y];++y,++x) {
00183         if((!str[x]) && (expr[y] != '(') && (expr[y] != '$') && (expr[y] != '*'))
00184             ret = ABORTED;
00185         else {
00186             switch(expr[y]) {
00187               case '$':
00188                 if( (str[x]) )
00189                     ret = NOMATCH;
00190                 else
00191                     --x;             /* we don't want loop to increment x */
00192                 break;
00193               case '*':
00194                 while(expr[++y] == '*'){}
00195                 if(!expr[y])
00196                     return MATCH;
00197                 while(str[x]) {
00198                     switch(_shexp_match(&str[x++],&expr[y], case_insensitive)) {
00199                     case NOMATCH:
00200                         continue;
00201                     case ABORTED:
00202                         ret = ABORTED;
00203                         break;
00204                     default:
00205                         return MATCH;
00206                     }
00207                     break;
00208                 }
00209                 if((expr[y] == '$') && (expr[y+1] == '\0') && (!str[x]))
00210                     return MATCH;
00211                 else
00212                     ret = ABORTED;
00213                 break;
00214               case '[':
00215                      neg = ((expr[++y] == '^') && (expr[y+1] != ']'));
00216                 if (neg)
00217                     ++y;
00218                 
00219                 if ((isalnum(expr[y])) && (expr[y+1] == '-') && 
00220                    (isalnum(expr[y+2])) && (expr[y+3] == ']'))
00221                     {
00222                         int start = expr[y], end = expr[y+2];
00223                         
00224                         /* Droolproofing for pinheads not included */
00225                         if(neg ^ ((str[x] < start) || (str[x] > end))) {
00226                             ret = NOMATCH;
00227                             break;
00228                         }
00229                         y+=3;
00230                     }
00231                 else {
00232                     int matched;
00233                     
00234                     for (matched=0;expr[y] != ']';y++)
00235                         matched |= (str[x] == expr[y]);
00236                     if (neg ^ (!matched))
00237                         ret = NOMATCH;
00238                 }
00239                 break;
00240               case '(':
00241                 return _handle_union(&str[x],&expr[y], case_insensitive);
00242                 break;
00243               case '?':
00244                 break;
00245               case '\\':
00246                 ++y;
00247               default:
00248                             if(case_insensitive)
00249                               {
00250                     if(toupper(str[x]) != toupper(expr[y]))
00251                         ret = NOMATCH;
00252                               }
00253                             else
00254                               {
00255                     if(str[x] != expr[y])
00256                         ret = NOMATCH;
00257                               }
00258                 break;
00259             }
00260         }
00261         if(ret)
00262             break;
00263     }
00264     return (ret ? ret : (str[x] ? NOMATCH : MATCH));
00265 }
00266 
00267 int 
00268 NS_WildCardMatch(char *str, char *xp, PRBool case_insensitive) {
00269     register int x;
00270     char *expr = PL_strdup(xp);
00271 
00272        if(!expr)
00273               return 1;
00274 
00275     for(x=strlen(expr)-1;x;--x) {
00276         if((expr[x] == '~') && (expr[x-1] != '\\')) {
00277             expr[x] = '\0';
00278             if(_shexp_match(str,&expr[++x], case_insensitive) == MATCH)
00279                 goto punt;
00280             break;
00281         }
00282     }
00283     if(_shexp_match(str,expr, case_insensitive) == MATCH) {
00284         PR_Free(expr);
00285         return 0;
00286     }
00287 
00288   punt:
00289     PR_Free(expr);
00290     return 1;
00291 }