1 /* 2 * Copyright (c) 1989, 1993, 1994 3 * The Regents of the University of California. All rights reserved. 4 * 5 * This code is derived from software contributed to Berkeley by 6 * Guido van Rossum. 7 * 8 * Redistribution and use in source and binary forms, with or without 9 * modification, are permitted provided that the following conditions 10 * are met: 11 * 1. Redistributions of source code must retain the above copyright 12 * notice, this list of conditions and the following disclaimer. 13 * 2. Redistributions in binary form must reproduce the above copyright 14 * notice, this list of conditions and the following disclaimer in the 15 * documentation and/or other materials provided with the distribution. 16 * 3. Neither the name of the University nor the names of its contributors 17 * may be used to endorse or promote products derived from this software 18 * without specific prior written permission. 19 * 20 * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND 21 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 22 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 23 * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE 24 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 25 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 26 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 27 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 28 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 29 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 30 * SUCH DAMAGE. 31 * 32 * $FreeBSD: src/sys/libkern/fnmatch.c,v 1.17 2003/06/11 05:23:04 obrien Exp $ 33 * $DragonFly: src/sys/libkern/fnmatch.c,v 1.3 2006/12/13 21:58:51 dillon Exp $ 34 */ 35 36 /* 37 * Function fnmatch() as specified in POSIX 1003.2-1992, section B.6. 38 * Compares a filename or pathname to a pattern. 39 */ 40 41 #include <sys/param.h> 42 #include <sys/ctype.h> 43 #include <sys/libkern.h> 44 45 #define EOS '\0' 46 47 #define RANGE_MATCH 1 48 #define RANGE_NOMATCH 0 49 #define RANGE_ERROR (-1) 50 51 #define MAXNEST 20 52 53 static int rangematch(const char *, char, int, char **); 54 55 int 56 _kfnmatch(const char *pattern, const char *string, int flags, int nesting) 57 { 58 const char *stringstart; 59 char *newp; 60 char c, test; 61 62 if (nesting == MAXNEST) 63 return (FNM_NOMATCH); 64 65 for (stringstart = string;;) { 66 switch (c = *pattern++) { 67 case EOS: 68 if ((flags & FNM_LEADING_DIR) && *string == '/') 69 return (0); 70 return (*string == EOS ? 0 : FNM_NOMATCH); 71 case '?': 72 if (*string == EOS) 73 return (FNM_NOMATCH); 74 if (*string == '/' && (flags & FNM_PATHNAME)) 75 return (FNM_NOMATCH); 76 if (*string == '.' && (flags & FNM_PERIOD) && 77 (string == stringstart || 78 ((flags & FNM_PATHNAME) && *(string - 1) == '/'))) { 79 return (FNM_NOMATCH); 80 } 81 ++string; 82 break; 83 case '*': 84 c = *pattern; 85 /* Collapse multiple stars. */ 86 while (c == '*') 87 c = *++pattern; 88 89 if (*string == '.' && (flags & FNM_PERIOD) && 90 (string == stringstart || 91 ((flags & FNM_PATHNAME) && *(string - 1) == '/'))) { 92 return (FNM_NOMATCH); 93 } 94 95 /* Optimize for pattern with * at end or before /. */ 96 if (c == EOS) { 97 if (flags & FNM_PATHNAME) { 98 return ((flags & FNM_LEADING_DIR) || 99 index(string, '/') == NULL ? 100 0 : FNM_NOMATCH); 101 } else { 102 return (0); 103 } 104 } else if (c == '/' && flags & FNM_PATHNAME) { 105 if ((string = index(string, '/')) == NULL) 106 return (FNM_NOMATCH); 107 break; 108 } 109 110 /* General case, use recursion. */ 111 while ((test = *string) != EOS) { 112 if (!_kfnmatch(pattern, string, flags & ~FNM_PERIOD, nesting + 1)) 113 return (0); 114 if (test == '/' && flags & FNM_PATHNAME) 115 break; 116 ++string; 117 } 118 return (FNM_NOMATCH); 119 case '[': 120 if (*string == EOS) 121 return (FNM_NOMATCH); 122 if (*string == '/' && (flags & FNM_PATHNAME)) 123 return (FNM_NOMATCH); 124 if (*string == '.' && (flags & FNM_PERIOD) && 125 (string == stringstart || 126 ((flags & FNM_PATHNAME) && *(string - 1) == '/'))) 127 return (FNM_NOMATCH); 128 129 switch (rangematch(pattern, *string, flags, &newp)) { 130 case RANGE_ERROR: 131 goto norm; 132 case RANGE_MATCH: 133 pattern = newp; 134 break; 135 case RANGE_NOMATCH: 136 return (FNM_NOMATCH); 137 } 138 ++string; 139 break; 140 case '\\': 141 if (!(flags & FNM_NOESCAPE)) { 142 if ((c = *pattern++) == EOS) { 143 c = '\\'; 144 --pattern; 145 } 146 } 147 /* FALLTHROUGH */ 148 default: 149 norm: 150 if (c == *string) { 151 ; 152 } else if ((flags & FNM_CASEFOLD) && 153 (tolower((unsigned char)c) == 154 tolower((unsigned char)*string))) { 155 ; 156 } else { 157 return (FNM_NOMATCH); 158 } 159 string++; 160 break; 161 } 162 } 163 /* NOTREACHED */ 164 } 165 166 static int 167 rangematch(const char *pattern, char test, int flags, char **newp) 168 { 169 int negate, ok; 170 char c, c2; 171 172 /* 173 * A bracket expression starting with an unquoted circumflex 174 * character produces unspecified results (IEEE 1003.2-1992, 175 * 3.13.2). This implementation treats it like '!', for 176 * consistency with the regular expression syntax. 177 * J.T. Conklin (conklin@ngai.kaleida.com) 178 */ 179 if ((negate = (*pattern == '!' || *pattern == '^')) != 0) 180 ++pattern; 181 182 if (flags & FNM_CASEFOLD) 183 test = tolower((unsigned char)test); 184 185 /* 186 * A right bracket shall lose its special meaning and represent 187 * itself in a bracket expression if it occurs first in the list. 188 * -- POSIX.2 2.8.3.2 189 */ 190 ok = 0; 191 c = *pattern++; 192 do { 193 if (c == '\\' && !(flags & FNM_NOESCAPE)) 194 c = *pattern++; 195 if (c == EOS) 196 return (RANGE_ERROR); 197 198 if (c == '/' && (flags & FNM_PATHNAME)) 199 return (RANGE_NOMATCH); 200 201 if (flags & FNM_CASEFOLD) 202 c = tolower((unsigned char)c); 203 204 if (*pattern == '-' 205 && (c2 = *(pattern+1)) != EOS && c2 != ']') { 206 pattern += 2; 207 if (c2 == '\\' && !(flags & FNM_NOESCAPE)) 208 c2 = *pattern++; 209 if (c2 == EOS) 210 return (RANGE_ERROR); 211 212 if (flags & FNM_CASEFOLD) 213 c2 = tolower((unsigned char)c2); 214 215 if (c <= test && test <= c2) 216 ok = 1; 217 } else if (c == test) { 218 ok = 1; 219 } 220 } while ((c = *pattern++) != ']'); 221 222 *newp = (char *)(uintptr_t)pattern; 223 return (ok == negate ? RANGE_NOMATCH : RANGE_MATCH); 224 } 225 226