[libgit2.git] / src / fnmatch.c

/*
 * Copyright (C) the libgit2 contributors. All rights reserved.
 *
 * This file is part of libgit2, distributed under the GNU GPL v2 with
 * a Linking Exception. For full terms see the included COPYING file.
 */

/*
 * 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.
 */

/*
 * Function fnmatch() as specified in POSIX 1003.2-1992, section B.6.
 * Compares a filename or pathname to a pattern.
 */

#include "fnmatch.h"

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

#define EOS		'\0'

#define RANGE_MATCH		1
#define RANGE_NOMATCH		0
#define RANGE_ERROR		(-1)

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

static int
p_fnmatchx(const char *pattern, const char *string, int flags, size_t recurs)
{
		const char *stringstart;
		char *newp;
		char c, test;
		int recurs_flags = flags & ~FNM_PERIOD;

		if (recurs-- == 0)
				return FNM_NORES;

		for (stringstart = string;;)
				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;

						/* Let '**' override PATHNAME match for this segment.
						 * It will be restored if/when we recurse below.
						 */
						if (c == '*') {
							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;
							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;
						}

						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) {
								int e;

								e = p_fnmatchx(pattern, string, recurs_flags, recurs);
								if (e != FNM_NOMATCH)
										return e;
								if (test == '/' && (flags & FNM_PATHNAME))
										break;
								++string;
						}
						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) &&
									(git__tolower((unsigned char)c) ==
									git__tolower((unsigned char)*string))))
								return (FNM_NOMATCH);
						++string;
						break;
				}
		/* NOTREACHED */
}

static int
rangematch(const char *pattern, char test, int flags, char **newp)
{
		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)
				test = (char)git__tolower((unsigned char)test);

		/*
			* 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))
						c = (char)git__tolower((unsigned char)c);
				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)
								c2 = (char)git__tolower((unsigned char)c2);
						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);
}

int
p_fnmatch(const char *pattern, const char *string, int flags)
{
		return p_fnmatchx(pattern, string, flags, 64);
}
Commit	Line	Data
e9c6571d	1	/*
359fc2d2	2	* Copyright (C) the libgit2 contributors. All rights reserved.
e9c6571d	3	*
bb742ede VM	4	* This file is part of libgit2, distributed under the GNU GPL v2 with
bb742ede VM	5	* a Linking Exception. For full terms see the included COPYING file.
e9c6571d VM	6	*/
e9c6571d VM	7
213a269a MW	8	/*
	9	* This file contains code originally derrived from OpenBSD fnmatch.c
	10	*
	11	* Copyright (c) 1989, 1993, 1994
	12	* The Regents of the University of California. All rights reserved.
	13	*
	14	* This code is derived from software contributed to Berkeley by
	15	* Guido van Rossum.
	16	*
	17	* Redistribution and use in source and binary forms, with or without
	18	* modification, are permitted provided that the following conditions
	19	* are met:
	20	* 1. Redistributions of source code must retain the above copyright
	21	* notice, this list of conditions and the following disclaimer.
	22	* 2. Redistributions in binary form must reproduce the above copyright
	23	* notice, this list of conditions and the following disclaimer in the
	24	* documentation and/or other materials provided with the distribution.
	25	* 3. Neither the name of the University nor the names of its contributors
	26	* may be used to endorse or promote products derived from this software
	27	* without specific prior written permission.
	28	*
	29	* THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
	30	* ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
	31	* IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
	32	* ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
	33	* FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
	34	* DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
	35	* OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
	36	* HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
	37	* LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
	38	* OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
	39	* SUCH DAMAGE.
	40	*/
	41
e9c6571d VM	42	/*
	43	* Function fnmatch() as specified in POSIX 1003.2-1992, section B.6.
	44	* Compares a filename or pathname to a pattern.
	45	*/
	46
eae0bfdc PP	47	#include "fnmatch.h"
eae0bfdc PP	48
e9c6571d VM	49	#include <ctype.h>
	50	#include <stdio.h>
	51	#include <string.h>
	52
87d9869f	53	#define EOS '\0'
e9c6571d	54
87d9869f VM	55	#define RANGE_MATCH 1
	56	#define RANGE_NOMATCH 0
	57	#define RANGE_ERROR (-1)
e9c6571d VM	58
	59	static int rangematch(const char , char, int, char *);
	60
d5a51910 RB	61	static int
d5a51910 RB	62	p_fnmatchx(const char pattern, const char string, int flags, size_t recurs)
e9c6571d	63	{
87d9869f VM	64	const char *stringstart;
	65	char *newp;
	66	char c, test;
2b6b85f1	67	int recurs_flags = flags & ~FNM_PERIOD;
87d9869f	68
d5a51910 RB	69	if (recurs-- == 0)
	70	return FNM_NORES;
	71
d45928cc	72	for (stringstart = string;;)
87d9869f VM	73	switch (c = *pattern++) {
	74	case EOS:
	75	if ((flags & FNM_LEADING_DIR) && *string == '/')
	76	return (0);
	77	return (*string == EOS ? 0 : FNM_NOMATCH);
	78	case '?':
	79	if (*string == EOS)
	80	return (FNM_NOMATCH);
	81	if (*string == '/' && (flags & FNM_PATHNAME))
	82	return (FNM_NOMATCH);
	83	if (*string == '.' && (flags & FNM_PERIOD) &&
	84	(string == stringstart \|\|
	85	((flags & FNM_PATHNAME) && *(string - 1) == '/')))
	86	return (FNM_NOMATCH);
	87	++string;
	88	break;
	89	case '*':
	90	c = *pattern;
2b6b85f1	91
c7d96060 RB	92	/* Let '**' override PATHNAME match for this segment.
	93	* It will be restored if/when we recurse below.
	94	*/
2b6b85f1	95	if (c == '*') {
1c3018eb CMN	96	c = *++pattern;
	97	/* star-star-slash is at the end, match by default */
	98	if (c == EOS)
	99	return 0;
	100	/* Double-star must be at end or between slashes */
	101	if (c != '/')
	102	return (FNM_NOMATCH);
	103
	104	c = *++pattern;
d45928cc CMN	105	do {
	106	int e = p_fnmatchx(pattern, string, recurs_flags, recurs);
	107	if (e != FNM_NOMATCH)
	108	return e;
	109	string = strchr(string, '/');
	110	} while (string++);
	111
	112	/* If we get here, we didn't find a match */
	113	return FNM_NOMATCH;
2b6b85f1	114	}
87d9869f VM	115
	116	if (*string == '.' && (flags & FNM_PERIOD) &&
	117	(string == stringstart \|\|
	118	((flags & FNM_PATHNAME) && *(string - 1) == '/')))
	119	return (FNM_NOMATCH);
	120
	121	/* Optimize for pattern with * at end or before /. */
	122	if (c == EOS) {
	123	if (flags & FNM_PATHNAME)
	124	return ((flags & FNM_LEADING_DIR) \|\|
	125	strchr(string, '/') == NULL ?
	126	0 : FNM_NOMATCH);
	127	else
	128	return (0);
	129	} else if (c == '/' && (flags & FNM_PATHNAME)) {
	130	if ((string = strchr(string, '/')) == NULL)
	131	return (FNM_NOMATCH);
	132	break;
	133	}
	134
	135	/* General case, use recursion. */
	136	while ((test = *string) != EOS) {
d5a51910 RB	137	int e;
d5a51910 RB	138
2b6b85f1	139	e = p_fnmatchx(pattern, string, recurs_flags, recurs);
d5a51910 RB	140	if (e != FNM_NOMATCH)
d5a51910 RB	141	return e;
87d9869f VM	142	if (test == '/' && (flags & FNM_PATHNAME))
87d9869f VM	143	break;
d45928cc	144	++string;
87d9869f VM	145	}
	146	return (FNM_NOMATCH);
	147	case '[':
	148	if (*string == EOS)
	149	return (FNM_NOMATCH);
	150	if (*string == '/' && (flags & FNM_PATHNAME))
	151	return (FNM_NOMATCH);
	152	if (*string == '.' && (flags & FNM_PERIOD) &&
	153	(string == stringstart \|\|
	154	((flags & FNM_PATHNAME) && *(string - 1) == '/')))
	155	return (FNM_NOMATCH);
	156
	157	switch (rangematch(pattern, *string, flags, &newp)) {
	158	case RANGE_ERROR:
	159	/* not a good range, treat as normal text */
	160	goto normal;
	161	case RANGE_MATCH:
	162	pattern = newp;
	163	break;
	164	case RANGE_NOMATCH:
	165	return (FNM_NOMATCH);
	166	}
	167	++string;
	168	break;
	169	case '\\':
	170	if (!(flags & FNM_NOESCAPE)) {
	171	if ((c = *pattern++) == EOS) {
	172	c = '\\';
	173	--pattern;
	174	}
	175	}
	176	/* FALLTHROUGH */
	177	default:
	178	normal:
	179	if (c != *string && !((flags & FNM_CASEFOLD) &&
75a4636f ET	180	(git__tolower((unsigned char)c) ==
75a4636f ET	181	git__tolower((unsigned char)*string))))
87d9869f VM	182	return (FNM_NOMATCH);
	183	++string;
	184	break;
	185	}
	186	/* NOTREACHED */
e9c6571d VM	187	}
	188
	189	static int
	190	rangematch(const char pattern, char test, int flags, char *newp)
	191	{
87d9869f VM	192	int negate, ok;
	193	char c, c2;
	194
	195	/*
	196	* A bracket expression starting with an unquoted circumflex
	197	* character produces unspecified results (IEEE 1003.2-1992,
	198	* 3.13.2). This implementation treats it like '!', for
	199	* consistency with the regular expression syntax.
	200	* J.T. Conklin (conklin@ngai.kaleida.com)
	201	*/
	202	if ((negate = (pattern == '!' \|\| pattern == '^')) != 0)
	203	++pattern;
	204
	205	if (flags & FNM_CASEFOLD)
75a4636f	206	test = (char)git__tolower((unsigned char)test);
87d9869f VM	207
	208	/*
	209	* A right bracket shall lose its special meaning and represent
	210	* itself in a bracket expression if it occurs first in the list.
	211	* -- POSIX.2 2.8.3.2
	212	*/
	213	ok = 0;
	214	c = *pattern++;
	215	do {
	216	if (c == '\\' && !(flags & FNM_NOESCAPE))
	217	c = *pattern++;
	218	if (c == EOS)
	219	return (RANGE_ERROR);
	220	if (c == '/' && (flags & FNM_PATHNAME))
	221	return (RANGE_NOMATCH);
	222	if ((flags & FNM_CASEFOLD))
75a4636f	223	c = (char)git__tolower((unsigned char)c);
87d9869f VM	224	if (*pattern == '-'
	225	&& (c2 = *(pattern+1)) != EOS && c2 != ']') {
	226	pattern += 2;
	227	if (c2 == '\\' && !(flags & FNM_NOESCAPE))
	228	c2 = *pattern++;
	229	if (c2 == EOS)
	230	return (RANGE_ERROR);
	231	if (flags & FNM_CASEFOLD)
75a4636f	232	c2 = (char)git__tolower((unsigned char)c2);
87d9869f VM	233	if (c <= test && test <= c2)
	234	ok = 1;
	235	} else if (c == test)
	236	ok = 1;
	237	} while ((c = *pattern++) != ']');
	238
	239	newp = (char )pattern;
	240	return (ok == negate ? RANGE_NOMATCH : RANGE_MATCH);
e9c6571d VM	241	}
e9c6571d VM	242
d5a51910 RB	243	int
	244	p_fnmatch(const char pattern, const char string, int flags)
	245	{
	246	return p_fnmatchx(pattern, string, flags, 64);
	247	}
	248