[libgit2.git] / src / fnmatch.c

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

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

#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;

		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;
						/* Collapse multiple stars. */
						while (c == '*')
								c = *++pattern;

						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, flags & ~FNM_PERIOD, 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) &&
									(tolower((unsigned char)c) ==
									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)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)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)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	/*
5e0de328	2	* Copyright (C) 2009-2012 the libgit2 contributors
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	*/
	7
	8	/*
	9	* Function fnmatch() as specified in POSIX 1003.2-1992, section B.6.
	10	* Compares a filename or pathname to a pattern.
	11	*/
	12
	13	#include <ctype.h>
	14	#include <stdio.h>
	15	#include <string.h>
	16
	17	#include "fnmatch.h"
	18
87d9869f	19	#define EOS '\0'
e9c6571d	20
87d9869f VM	21	#define RANGE_MATCH 1
	22	#define RANGE_NOMATCH 0
	23	#define RANGE_ERROR (-1)
e9c6571d VM	24
	25	static int rangematch(const char , char, int, char *);
	26
d5a51910 RB	27	static int
d5a51910 RB	28	p_fnmatchx(const char pattern, const char string, int flags, size_t recurs)
e9c6571d	29	{
87d9869f VM	30	const char *stringstart;
	31	char *newp;
	32	char c, test;
	33
d5a51910 RB	34	if (recurs-- == 0)
	35	return FNM_NORES;
	36
87d9869f VM	37	for (stringstart = string;;)
	38	switch (c = *pattern++) {
	39	case EOS:
	40	if ((flags & FNM_LEADING_DIR) && *string == '/')
	41	return (0);
	42	return (*string == EOS ? 0 : FNM_NOMATCH);
	43	case '?':
	44	if (*string == EOS)
	45	return (FNM_NOMATCH);
	46	if (*string == '/' && (flags & FNM_PATHNAME))
	47	return (FNM_NOMATCH);
	48	if (*string == '.' && (flags & FNM_PERIOD) &&
	49	(string == stringstart \|\|
	50	((flags & FNM_PATHNAME) && *(string - 1) == '/')))
	51	return (FNM_NOMATCH);
	52	++string;
	53	break;
	54	case '*':
	55	c = *pattern;
	56	/* Collapse multiple stars. */
	57	while (c == '*')
	58	c = *++pattern;
	59
	60	if (*string == '.' && (flags & FNM_PERIOD) &&
	61	(string == stringstart \|\|
	62	((flags & FNM_PATHNAME) && *(string - 1) == '/')))
	63	return (FNM_NOMATCH);
	64
	65	/* Optimize for pattern with * at end or before /. */
	66	if (c == EOS) {
	67	if (flags & FNM_PATHNAME)
	68	return ((flags & FNM_LEADING_DIR) \|\|
	69	strchr(string, '/') == NULL ?
	70	0 : FNM_NOMATCH);
	71	else
	72	return (0);
	73	} else if (c == '/' && (flags & FNM_PATHNAME)) {
	74	if ((string = strchr(string, '/')) == NULL)
	75	return (FNM_NOMATCH);
	76	break;
	77	}
	78
	79	/* General case, use recursion. */
	80	while ((test = *string) != EOS) {
d5a51910 RB	81	int e;
	82
	83	e = p_fnmatchx(pattern, string, flags & ~FNM_PERIOD, recurs);
	84	if (e != FNM_NOMATCH)
	85	return e;
87d9869f VM	86	if (test == '/' && (flags & FNM_PATHNAME))
	87	break;
	88	++string;
	89	}
	90	return (FNM_NOMATCH);
	91	case '[':
	92	if (*string == EOS)
	93	return (FNM_NOMATCH);
	94	if (*string == '/' && (flags & FNM_PATHNAME))
	95	return (FNM_NOMATCH);
	96	if (*string == '.' && (flags & FNM_PERIOD) &&
	97	(string == stringstart \|\|
	98	((flags & FNM_PATHNAME) && *(string - 1) == '/')))
	99	return (FNM_NOMATCH);
	100
	101	switch (rangematch(pattern, *string, flags, &newp)) {
	102	case RANGE_ERROR:
	103	/* not a good range, treat as normal text */
	104	goto normal;
	105	case RANGE_MATCH:
	106	pattern = newp;
	107	break;
	108	case RANGE_NOMATCH:
	109	return (FNM_NOMATCH);
	110	}
	111	++string;
	112	break;
	113	case '\\':
	114	if (!(flags & FNM_NOESCAPE)) {
	115	if ((c = *pattern++) == EOS) {
	116	c = '\\';
	117	--pattern;
	118	}
	119	}
	120	/* FALLTHROUGH */
	121	default:
	122	normal:
	123	if (c != *string && !((flags & FNM_CASEFOLD) &&
	124	(tolower((unsigned char)c) ==
	125	tolower((unsigned char)*string))))
	126	return (FNM_NOMATCH);
	127	++string;
	128	break;
	129	}
	130	/* NOTREACHED */
e9c6571d VM	131	}
	132
	133	static int
	134	rangematch(const char pattern, char test, int flags, char *newp)
	135	{
87d9869f VM	136	int negate, ok;
	137	char c, c2;
	138
	139	/*
	140	* A bracket expression starting with an unquoted circumflex
	141	* character produces unspecified results (IEEE 1003.2-1992,
	142	* 3.13.2). This implementation treats it like '!', for
	143	* consistency with the regular expression syntax.
	144	* J.T. Conklin (conklin@ngai.kaleida.com)
	145	*/
	146	if ((negate = (pattern == '!' \|\| pattern == '^')) != 0)
	147	++pattern;
	148
	149	if (flags & FNM_CASEFOLD)
	150	test = (char)tolower((unsigned char)test);
	151
	152	/*
	153	* A right bracket shall lose its special meaning and represent
	154	* itself in a bracket expression if it occurs first in the list.
	155	* -- POSIX.2 2.8.3.2
	156	*/
	157	ok = 0;
	158	c = *pattern++;
	159	do {
	160	if (c == '\\' && !(flags & FNM_NOESCAPE))
	161	c = *pattern++;
	162	if (c == EOS)
	163	return (RANGE_ERROR);
	164	if (c == '/' && (flags & FNM_PATHNAME))
	165	return (RANGE_NOMATCH);
	166	if ((flags & FNM_CASEFOLD))
	167	c = (char)tolower((unsigned char)c);
	168	if (*pattern == '-'
	169	&& (c2 = *(pattern+1)) != EOS && c2 != ']') {
	170	pattern += 2;
	171	if (c2 == '\\' && !(flags & FNM_NOESCAPE))
	172	c2 = *pattern++;
	173	if (c2 == EOS)
	174	return (RANGE_ERROR);
	175	if (flags & FNM_CASEFOLD)
	176	c2 = (char)tolower((unsigned char)c2);
	177	if (c <= test && test <= c2)
	178	ok = 1;
	179	} else if (c == test)
	180	ok = 1;
	181	} while ((c = *pattern++) != ']');
	182
	183	newp = (char )pattern;
	184	return (ok == negate ? RANGE_NOMATCH : RANGE_MATCH);
e9c6571d VM	185	}
e9c6571d VM	186
d5a51910 RB	187	int
	188	p_fnmatch(const char pattern, const char string, int flags)
	189	{
	190	return p_fnmatchx(pattern, string, flags, 64);
	191	}
	192