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