xref: /freebsd/sys/libkern/fnmatch.c (revision 74bf4e164ba5851606a27d4feff27717452583e5)
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  * 4. 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 
33 #include <sys/cdefs.h>
34 __FBSDID("$FreeBSD$");
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 static int rangematch(const char *, char, int, char **);
52 
53 int
54 fnmatch(pattern, string, flags)
55 	const char *pattern, *string;
56 	int flags;
57 {
58 	const char *stringstart;
59 	char *newp;
60 	char c, test;
61 
62 	for (stringstart = string;;)
63 		switch (c = *pattern++) {
64 		case EOS:
65 			if ((flags & FNM_LEADING_DIR) && *string == '/')
66 				return (0);
67 			return (*string == EOS ? 0 : FNM_NOMATCH);
68 		case '?':
69 			if (*string == EOS)
70 				return (FNM_NOMATCH);
71 			if (*string == '/' && (flags & FNM_PATHNAME))
72 				return (FNM_NOMATCH);
73 			if (*string == '.' && (flags & FNM_PERIOD) &&
74 			    (string == stringstart ||
75 			    ((flags & FNM_PATHNAME) && *(string - 1) == '/')))
76 				return (FNM_NOMATCH);
77 			++string;
78 			break;
79 		case '*':
80 			c = *pattern;
81 			/* Collapse multiple stars. */
82 			while (c == '*')
83 				c = *++pattern;
84 
85 			if (*string == '.' && (flags & FNM_PERIOD) &&
86 			    (string == stringstart ||
87 			    ((flags & FNM_PATHNAME) && *(string - 1) == '/')))
88 				return (FNM_NOMATCH);
89 
90 			/* Optimize for pattern with * at end or before /. */
91 			if (c == EOS)
92 				if (flags & FNM_PATHNAME)
93 					return ((flags & FNM_LEADING_DIR) ||
94 					    index(string, '/') == NULL ?
95 					    0 : FNM_NOMATCH);
96 				else
97 					return (0);
98 			else if (c == '/' && flags & FNM_PATHNAME) {
99 				if ((string = index(string, '/')) == NULL)
100 					return (FNM_NOMATCH);
101 				break;
102 			}
103 
104 			/* General case, use recursion. */
105 			while ((test = *string) != EOS) {
106 				if (!fnmatch(pattern, string, flags & ~FNM_PERIOD))
107 					return (0);
108 				if (test == '/' && flags & FNM_PATHNAME)
109 					break;
110 				++string;
111 			}
112 			return (FNM_NOMATCH);
113 		case '[':
114 			if (*string == EOS)
115 				return (FNM_NOMATCH);
116 			if (*string == '/' && (flags & FNM_PATHNAME))
117 				return (FNM_NOMATCH);
118 			if (*string == '.' && (flags & FNM_PERIOD) &&
119 			    (string == stringstart ||
120 			    ((flags & FNM_PATHNAME) && *(string - 1) == '/')))
121 				return (FNM_NOMATCH);
122 
123 			switch (rangematch(pattern, *string, flags, &newp)) {
124 			case RANGE_ERROR:
125 				goto norm;
126 			case RANGE_MATCH:
127 				pattern = newp;
128 				break;
129 			case RANGE_NOMATCH:
130 				return (FNM_NOMATCH);
131 			}
132 			++string;
133 			break;
134 		case '\\':
135 			if (!(flags & FNM_NOESCAPE)) {
136 				if ((c = *pattern++) == EOS) {
137 					c = '\\';
138 					--pattern;
139 				}
140 			}
141 			/* FALLTHROUGH */
142 		default:
143 		norm:
144 			if (c == *string)
145 				;
146 			else if ((flags & FNM_CASEFOLD) &&
147 				 (tolower((unsigned char)c) ==
148 				  tolower((unsigned char)*string)))
149 				;
150 			else
151 				return (FNM_NOMATCH);
152 			string++;
153 			break;
154 		}
155 	/* NOTREACHED */
156 }
157 
158 static int
159 rangematch(pattern, test, flags, newp)
160 	const char *pattern;
161 	char test;
162 	int flags;
163 	char **newp;
164 {
165 	int negate, ok;
166 	char c, c2;
167 
168 	/*
169 	 * A bracket expression starting with an unquoted circumflex
170 	 * character produces unspecified results (IEEE 1003.2-1992,
171 	 * 3.13.2).  This implementation treats it like '!', for
172 	 * consistency with the regular expression syntax.
173 	 * J.T. Conklin (conklin@ngai.kaleida.com)
174 	 */
175 	if ( (negate = (*pattern == '!' || *pattern == '^')) )
176 		++pattern;
177 
178 	if (flags & FNM_CASEFOLD)
179 		test = tolower((unsigned char)test);
180 
181 	/*
182 	 * A right bracket shall lose its special meaning and represent
183 	 * itself in a bracket expression if it occurs first in the list.
184 	 * -- POSIX.2 2.8.3.2
185 	 */
186 	ok = 0;
187 	c = *pattern++;
188 	do {
189 		if (c == '\\' && !(flags & FNM_NOESCAPE))
190 			c = *pattern++;
191 		if (c == EOS)
192 			return (RANGE_ERROR);
193 
194 		if (c == '/' && (flags & FNM_PATHNAME))
195 			return (RANGE_NOMATCH);
196 
197 		if (flags & FNM_CASEFOLD)
198 			c = tolower((unsigned char)c);
199 
200 		if (*pattern == '-'
201 		    && (c2 = *(pattern+1)) != EOS && c2 != ']') {
202 			pattern += 2;
203 			if (c2 == '\\' && !(flags & FNM_NOESCAPE))
204 				c2 = *pattern++;
205 			if (c2 == EOS)
206 				return (RANGE_ERROR);
207 
208 			if (flags & FNM_CASEFOLD)
209 				c2 = tolower((unsigned char)c2);
210 
211 			if (c <= test && test <= c2)
212 				ok = 1;
213 		} else if (c == test)
214 			ok = 1;
215 	} while ((c = *pattern++) != ']');
216 
217 	*newp = (char *)(uintptr_t)pattern;
218 	return (ok == negate ? RANGE_NOMATCH : RANGE_MATCH);
219 }
220