xref: /freebsd/sys/libkern/fnmatch.c (revision 64c2a712d661db9be31f02fe97c3b59710290ae3)
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  
53  static int rangematch(const char *, char, int, char **);
54  
55  int
56  fnmatch(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  
158  static int
159  rangematch(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