fnmatch.c 7.36 KB
Newer Older
1
/*
Edward Thomson committed
2
 * Copyright (C) the libgit2 contributors. All rights reserved.
3
 *
Vicent Marti committed
4 5
 * This file is part of libgit2, distributed under the GNU GPL v2 with
 * a Linking Exception. For full terms see the included COPYING file.
6 7 8
 */

/*
9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42
 * This file contains code originally derrived from OpenBSD fnmatch.c 
 *
 * Copyright (c) 1989, 1993, 1994
 *      The Regents of the University of California.  All rights reserved.
 *
 * This code is derived from software contributed to Berkeley by
 * Guido van Rossum.
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions
 * are met:
 * 1. Redistributions of source code must retain the above copyright
 *    notice, this list of conditions and the following disclaimer.
 * 2. Redistributions in binary form must reproduce the above copyright
 *    notice, this list of conditions and the following disclaimer in the
 *    documentation and/or other materials provided with the distribution.
 * 3. Neither the name of the University nor the names of its contributors
 *    may be used to endorse or promote products derived from this software
 *    without specific prior written permission.
 *
 * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
 * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
 * SUCH DAMAGE.
 */

/*
43 44 45 46 47 48 49 50 51 52
 * Function fnmatch() as specified in POSIX 1003.2-1992, section B.6.
 * Compares a filename or pathname to a pattern.
 */

#include <ctype.h>
#include <stdio.h>
#include <string.h>

#include "fnmatch.h"

Vicent Marti committed
53
#define EOS		'\0'
54

Vicent Marti committed
55 56 57
#define RANGE_MATCH		1
#define RANGE_NOMATCH		0
#define RANGE_ERROR		(-1)
58 59 60

static int rangematch(const char *, char, int, char **);

61 62
static int
p_fnmatchx(const char *pattern, const char *string, int flags, size_t recurs)
63
{
Vicent Marti committed
64 65 66
		const char *stringstart;
		char *newp;
		char c, test;
67
		int recurs_flags = flags & ~FNM_PERIOD;
Vicent Marti committed
68

69 70 71
		if (recurs-- == 0)
				return FNM_NORES;

72
		for (stringstart = string;;)
Vicent Marti committed
73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90
				switch (c = *pattern++) {
				case EOS:
						if ((flags & FNM_LEADING_DIR) && *string == '/')
								return (0);
						return (*string == EOS ? 0 : FNM_NOMATCH);
				case '?':
						if (*string == EOS)
								return (FNM_NOMATCH);
						if (*string == '/' && (flags & FNM_PATHNAME))
								return (FNM_NOMATCH);
						if (*string == '.' && (flags & FNM_PERIOD) &&
							(string == stringstart ||
							((flags & FNM_PATHNAME) && *(string - 1) == '/')))
								return (FNM_NOMATCH);
						++string;
						break;
				case '*':
						c = *pattern;
91

92 93 94
						/* Let '**' override PATHNAME match for this segment.
						 * It will be restored if/when we recurse below.
						 */
95
						if (c == '*') {
96 97 98 99 100 101 102 103 104
							c = *++pattern;
							/* star-star-slash is at the end, match by default */
							if (c == EOS)
								return 0;
							/* Double-star must be at end or between slashes */
							if (c != '/')
								return (FNM_NOMATCH);

							c = *++pattern;
105 106 107 108 109 110 111 112 113
							do {
								int e = p_fnmatchx(pattern, string, recurs_flags, recurs);
								if (e != FNM_NOMATCH)
									return e;
								string = strchr(string, '/');
							} while (string++);

							/* If we get here, we didn't find a match */
							return FNM_NOMATCH;
114
						}
Vicent Marti committed
115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136

						if (*string == '.' && (flags & FNM_PERIOD) &&
							(string == stringstart ||
							((flags & FNM_PATHNAME) && *(string - 1) == '/')))
								return (FNM_NOMATCH);

						/* Optimize for pattern with * at end or before /. */
						if (c == EOS) {
								if (flags & FNM_PATHNAME)
										return ((flags & FNM_LEADING_DIR) ||
											strchr(string, '/') == NULL ?
											0 : FNM_NOMATCH);
								else
										return (0);
						} else if (c == '/' && (flags & FNM_PATHNAME)) {
								if ((string = strchr(string, '/')) == NULL)
										return (FNM_NOMATCH);
								break;
						}

						/* General case, use recursion. */
						while ((test = *string) != EOS) {
137 138
								int e;

139
								e = p_fnmatchx(pattern, string, recurs_flags, recurs);
140 141
								if (e != FNM_NOMATCH)
										return e;
Vicent Marti committed
142 143
								if (test == '/' && (flags & FNM_PATHNAME))
										break;
144
								++string;
Vicent Marti committed
145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179
						}
						return (FNM_NOMATCH);
				case '[':
						if (*string == EOS)
								return (FNM_NOMATCH);
						if (*string == '/' && (flags & FNM_PATHNAME))
								return (FNM_NOMATCH);
						if (*string == '.' && (flags & FNM_PERIOD) &&
							(string == stringstart ||
							((flags & FNM_PATHNAME) && *(string - 1) == '/')))
								return (FNM_NOMATCH);

						switch (rangematch(pattern, *string, flags, &newp)) {
						case RANGE_ERROR:
								/* not a good range, treat as normal text */
								goto normal;
						case RANGE_MATCH:
								pattern = newp;
								break;
						case RANGE_NOMATCH:
								return (FNM_NOMATCH);
						}
						++string;
						break;
				case '\\':
						if (!(flags & FNM_NOESCAPE)) {
								if ((c = *pattern++) == EOS) {
										c = '\\';
										--pattern;
								}
						}
						/* FALLTHROUGH */
				default:
				normal:
						if (c != *string && !((flags & FNM_CASEFOLD) &&
180 181
									(git__tolower((unsigned char)c) ==
									git__tolower((unsigned char)*string))))
Vicent Marti committed
182 183 184 185 186
								return (FNM_NOMATCH);
						++string;
						break;
				}
		/* NOTREACHED */
187 188 189 190 191
}

static int
rangematch(const char *pattern, char test, int flags, char **newp)
{
Vicent Marti committed
192 193 194 195 196 197 198 199 200 201 202 203 204 205
		int negate, ok;
		char c, c2;

		/*
			* A bracket expression starting with an unquoted circumflex
			* character produces unspecified results (IEEE 1003.2-1992,
			* 3.13.2). This implementation treats it like '!', for
			* consistency with the regular expression syntax.
			* J.T. Conklin (conklin@ngai.kaleida.com)
			*/
		if ((negate = (*pattern == '!' || *pattern == '^')) != 0)
				++pattern;

		if (flags & FNM_CASEFOLD)
206
				test = (char)git__tolower((unsigned char)test);
Vicent Marti committed
207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222

		/*
			* A right bracket shall lose its special meaning and represent
			* itself in a bracket expression if it occurs first in the list.
			* -- POSIX.2 2.8.3.2
			*/
		ok = 0;
		c = *pattern++;
		do {
				if (c == '\\' && !(flags & FNM_NOESCAPE))
						c = *pattern++;
				if (c == EOS)
						return (RANGE_ERROR);
				if (c == '/' && (flags & FNM_PATHNAME))
						return (RANGE_NOMATCH);
				if ((flags & FNM_CASEFOLD))
223
						c = (char)git__tolower((unsigned char)c);
Vicent Marti committed
224 225 226 227 228 229 230 231
				if (*pattern == '-'
					&& (c2 = *(pattern+1)) != EOS && c2 != ']') {
						pattern += 2;
						if (c2 == '\\' && !(flags & FNM_NOESCAPE))
								c2 = *pattern++;
						if (c2 == EOS)
								return (RANGE_ERROR);
						if (flags & FNM_CASEFOLD)
232
								c2 = (char)git__tolower((unsigned char)c2);
Vicent Marti committed
233 234 235 236 237 238 239 240
						if (c <= test && test <= c2)
								ok = 1;
				} else if (c == test)
						ok = 1;
		} while ((c = *pattern++) != ']');

		*newp = (char *)pattern;
		return (ok == negate ? RANGE_NOMATCH : RANGE_MATCH);
241 242
}

243 244 245 246 247 248
int
p_fnmatch(const char *pattern, const char *string, int flags)
{
		return p_fnmatchx(pattern, string, flags, 64);
}