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 of the GNU General Public License Version 2 or later (the "GPL"),
00026  * or 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 "nsCRT.h"
00051 #include "plstr.h"
00052 #include "prmem.h"
00053 
00054 /* ----------------------------- shexp_valid ------------------------------ */
00055 
00056 
00057 static int 
00058 _valid_subexp(PRUnichar *expr, PRUnichar stop) 
00059 {
00060     register int x,y,t;
00061     int nsc,np,tld;
00062 
00063     x=0;nsc=0;tld=0;
00064 
00065     while(expr[x] && (expr[x] != stop)) {
00066         switch(expr[x]) {
00067           case '~':
00068             if(tld) return INVALID_SXP;
00069             else ++tld;
00070           case '*':
00071           case '?':
00072           case '^':
00073           case '$':
00074             ++nsc;
00075             break;
00076           case '[':
00077             ++nsc;
00078             if((!expr[++x]) || (expr[x] == ']'))
00079                 return INVALID_SXP;
00080             for(++x;expr[x] && (expr[x] != ']');++x)
00081                 if(expr[x] == '\\')
00082                     if(!expr[++x])
00083                         return INVALID_SXP;
00084             if(!expr[x])
00085                 return INVALID_SXP;
00086             break;
00087           case '(':
00088             ++nsc;np = 0;
00089             while(1) {
00090                 if(expr[++x] == ')')
00091                     return INVALID_SXP;
00092                 for(y=x;(expr[y]) && (expr[y] != '|') && (expr[y] != ')');++y)
00093                     if(expr[y] == '\\')
00094                         if(!expr[++y])
00095                             return INVALID_SXP;
00096                 if(!expr[y])
00097                     return INVALID_SXP;
00098                 if(expr[y] == '|')
00099                     ++np;
00100                 t = _valid_subexp(&expr[x],expr[y]);
00101                 if(t == INVALID_SXP)
00102                     return INVALID_SXP;
00103                 x+=t;
00104                 if(expr[x] == ')') {
00105                     if(!np)
00106                         return INVALID_SXP;
00107                     break;
00108                 }
00109             }
00110             break;
00111           case ')':
00112           case ']':
00113             return INVALID_SXP;
00114           case '\\':
00115             if(!expr[++x])
00116                 return INVALID_SXP;
00117           default:
00118             break;
00119         }
00120         ++x;
00121     }
00122     if((!stop) && (!nsc))
00123         return NON_SXP;
00124     return ((expr[x] == stop) ? x : INVALID_SXP);
00125 }
00126 
00127 int 
00128 NS_WildCardValid(PRUnichar *expr) 
00129 {
00130     int x;
00131 
00132     x = _valid_subexp(expr, '\0');
00133     return (x < 0 ? x : VALID_SXP);
00134 }
00135 
00136 
00137 /* ----------------------------- shexp_match ----------------------------- */
00138 
00139 
00140 #define MATCH 0
00141 #define NOMATCH 1
00142 #define ABORTED -1
00143 
00144 static int _shexp_match(const PRUnichar *str, const PRUnichar *expr,
00145                         PRBool case_insensitive);
00146 
00147 static int 
00148 _handle_union(const PRUnichar *str, const PRUnichar *expr,
00149               PRBool case_insensitive) 
00150 {
00151     PRUnichar *e2 = (PRUnichar *) PR_Malloc(sizeof(PRUnichar)*nsCRT::strlen(expr));
00152     register int t,p2,p1 = 1;
00153     int cp;
00154 
00155     while(1) {
00156         for(cp=1;expr[cp] != ')';cp++)
00157             if(expr[cp] == '\\')
00158                 ++cp;
00159         for(p2 = 0;(expr[p1] != '|') && (p1 != cp);p1++,p2++) {
00160             if(expr[p1] == '\\')
00161                 e2[p2++] = expr[p1++];
00162             e2[p2] = expr[p1];
00163         }
00164         for (t=cp+1; ((e2[p2] = expr[t]) != 0); ++t,++p2) {}
00165         if(_shexp_match(str,e2, case_insensitive) == MATCH) {
00166             PR_Free(e2);
00167             return MATCH;
00168         }
00169         if(p1 == cp) {
00170             PR_Free(e2);
00171             return NOMATCH;
00172         }
00173         else ++p1;
00174     }
00175 }
00176 
00177 
00178 static int 
00179 _shexp_match(const PRUnichar *str, const PRUnichar *expr,
00180              PRBool case_insensitive) 
00181 {
00182     register int x,y;
00183     int ret,neg;
00184 
00185     ret = 0;
00186     for(x=0,y=0;expr[y];++y,++x) {
00187         if((!str[x]) && (expr[y] != '(') && (expr[y] != '$') && (expr[y] != '*'))
00188             ret = ABORTED;
00189         else {
00190             switch(expr[y]) {
00191               case '$':
00192                 if( (str[x]) )
00193                     ret = NOMATCH;
00194                 else
00195                     --x;             /* we don't want loop to increment x */
00196                 break;
00197               case '*':
00198                 while(expr[++y] == '*'){}
00199                 if(!expr[y])
00200                     return MATCH;
00201                 while(str[x]) {
00202                     switch(_shexp_match(&str[x++],&expr[y], case_insensitive)) {
00203                     case NOMATCH:
00204                         continue;
00205                     case ABORTED:
00206                         ret = ABORTED;
00207                         break;
00208                     default:
00209                         return MATCH;
00210                     }
00211                     break;
00212                 }
00213                 if((expr[y] == '$') && (expr[y+1] == '\0') && (!str[x]))
00214                     return MATCH;
00215                 else
00216                     ret = ABORTED;
00217                 break;
00218               case '[':
00219                      neg = ((expr[++y] == '^') && (expr[y+1] != ']'));
00220                 if (neg)
00221                     ++y;
00222                 
00223                 if ((isalnum(expr[y])) && (expr[y+1] == '-') && 
00224                    (isalnum(expr[y+2])) && (expr[y+3] == ']'))
00225                     {
00226                         int start = expr[y], end = expr[y+2];
00227                         
00228                         /* Droolproofing for pinheads not included */
00229                         if(neg ^ ((str[x] < start) || (str[x] > end))) {
00230                             ret = NOMATCH;
00231                             break;
00232                         }
00233                         y+=3;
00234                     }
00235                 else {
00236                     int matched;
00237                     
00238                     for (matched=0;expr[y] != ']';y++)
00239                         matched |= (str[x] == expr[y]);
00240                     if (neg ^ (!matched))
00241                         ret = NOMATCH;
00242                 }
00243                 break;
00244               case '(':
00245                 return _handle_union(&str[x],&expr[y], case_insensitive);
00246                 break;
00247               case '?':
00248                 break;
00249               case '\\':
00250                 ++y;
00251               default:
00252                             if(case_insensitive)
00253                               {
00254                     if(toupper(str[x]) != toupper(expr[y]))
00255                         ret = NOMATCH;
00256                               }
00257                             else
00258                               {
00259                     if(str[x] != expr[y])
00260                         ret = NOMATCH;
00261                               }
00262                 break;
00263             }
00264         }
00265         if(ret)
00266             break;
00267     }
00268     return (ret ? ret : (str[x] ? NOMATCH : MATCH));
00269 }
00270 
00271 int 
00272 NS_WildCardMatch(const PRUnichar *str, const PRUnichar *xp,
00273                  PRBool case_insensitive) {
00274     register int x;
00275     PRUnichar *expr = nsCRT::strdup(xp);
00276 
00277        if(!expr)
00278               return 1;
00279 
00280     for(x=nsCRT::strlen(expr)-1;x;--x) {
00281         if((expr[x] == '~') && (expr[x-1] != '\\')) {
00282             expr[x] = '\0';
00283             if(_shexp_match(str,&expr[++x], case_insensitive) == MATCH)
00284                 goto punt;
00285             break;
00286         }
00287     }
00288     if(_shexp_match(str,expr, case_insensitive) == MATCH) {
00289         PR_Free(expr);
00290         return 0;
00291     }
00292 
00293   punt:
00294     PR_Free(expr);
00295     return 1;
00296 }