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