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__FBSDID("$FreeBSD$");
37
38/*
39 * Function fnmatch() as specified in POSIX 1003.2-1992, section B.6.
40 * Compares a filename or pathname to a pattern.
41 */
42
43#include <sys/param.h>
44#include <sys/ctype.h>
45#include <sys/libkern.h>
46
47#define	EOS	'\0'
48
49#define RANGE_MATCH     1
50#define RANGE_NOMATCH   0
51#define RANGE_ERROR     (-1)
52
53static int rangematch(const char *, char, int, char **);
54
55int
56fnmatch(const char *pattern, const char *string, 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					    strchr(string, '/') == NULL ?
95					    0 : FNM_NOMATCH);
96				else
97					return (0);
98			else if (c == '/' && flags & FNM_PATHNAME) {
99				if ((string = strchr(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
158static int
159rangematch(const char *pattern, char test, int flags, char **newp)
160{
161	int negate, ok;
162	char c, c2;
163
164	/*
165	 * A bracket expression starting with an unquoted circumflex
166	 * character produces unspecified results (IEEE 1003.2-1992,
167	 * 3.13.2).  This implementation treats it like '!', for
168	 * consistency with the regular expression syntax.
169	 * J.T. Conklin (conklin@ngai.kaleida.com)
170	 */
171	if ( (negate = (*pattern == '!' || *pattern == '^')) )
172		++pattern;
173
174	if (flags & FNM_CASEFOLD)
175		test = tolower((unsigned char)test);
176
177	/*
178	 * A right bracket shall lose its special meaning and represent
179	 * itself in a bracket expression if it occurs first in the list.
180	 * -- POSIX.2 2.8.3.2
181	 */
182	ok = 0;
183	c = *pattern++;
184	do {
185		if (c == '\\' && !(flags & FNM_NOESCAPE))
186			c = *pattern++;
187		if (c == EOS)
188			return (RANGE_ERROR);
189
190		if (c == '/' && (flags & FNM_PATHNAME))
191			return (RANGE_NOMATCH);
192
193		if (flags & FNM_CASEFOLD)
194			c = tolower((unsigned char)c);
195
196		if (*pattern == '-'
197		    && (c2 = *(pattern+1)) != EOS && c2 != ']') {
198			pattern += 2;
199			if (c2 == '\\' && !(flags & FNM_NOESCAPE))
200				c2 = *pattern++;
201			if (c2 == EOS)
202				return (RANGE_ERROR);
203
204			if (flags & FNM_CASEFOLD)
205				c2 = tolower((unsigned char)c2);
206
207			if (c <= test && test <= c2)
208				ok = 1;
209		} else if (c == test)
210			ok = 1;
211	} while ((c = *pattern++) != ']');
212
213	*newp = (char *)(uintptr_t)pattern;
214	return (ok == negate ? RANGE_NOMATCH : RANGE_MATCH);
215}
216