/*
 * @(#)wildmat.c 1.3 87/11/06   Public Domain.
 *
From: rs@mirror.TMC.COM (Rich Salz)
Newsgroups: net.sources
Subject: Small shell-style pattern matcher
Message-ID: <596@mirror.TMC.COM>
Date: 27 Nov 86 00:06:40 GMT

There have been several regular-expression subroutines and one or two
filename-globbing routines in mod.sources.  They handle lots of
complicated patterns.  This small piece of code handles the *?[]\
wildcard characters the way the standard Unix(tm) shells do, with the
addition that "[^.....]" is an inverse character class -- it matches
any character not in the range ".....".  Read the comments for more
info.

For my application, I had first ripped off a copy of the "glob" routine
from within the find(1) source, but that code is bad news:  it recurses
on every character in the pattern.  I'm putting this replacement in the
public domain.  It's small, tight, and iterative.  Compile with -DTEST
to get a test driver.  After you're convinced it works, install in
whatever way is appropriate for you.

I would like to hear of bugs, but am not interested in additions; if I
were, I'd use the code I mentioned above.
*/
/*
**  Do shell-style pattern matching for ?, \, [], and * characters.
**  Might not be robust in face of malformed patterns; e.g., "foo[a-"
**  could cause a segmentation violation.
**
**  Written by Rich $alz, mirror!rs, Wed Nov 26 19:03:17 EST 1986.
*/

/*
 * Modified 6Nov87 by John Gilmore (hoptoad!gnu) to return a "match"
 * if the pattern is immediately followed by a "/", as well as \0.
 * This matches what "tar" does for matching whole subdirectories.
 *
 * The "*" code could be sped up by only recursing one level instead
 * of two for each trial pattern, perhaps, and not recursing at all
 * if a literal match of the next 2 chars would fail.
 */

/* Modified by Anders Klemets to take an array of pointers as an optional
   argument. Each part of the string that matches '*' is returned as a
   null-terminated, malloced string in this array.
 */
#include "global.h"
#include "ctype.h"



#if !defined(_lint)
static char rcsid[] OPTIONAL = "$Id: wildmat.c,v 1.13 1997/08/19 01:19:22 root Exp $";
#endif

static int Star (const char *s, char *p, char **argv, int single);
static int haveDot (register const char *c, register int len);



static int
haveDot (register const char *s, register int len)
{
	if (s != NULLCHAR)	{
		while (len-- > 0)
			if (*s++ == '.')
				return TRUE;
	}
	return FALSE;
}



static int
Star (register const char *s, register char *p, register char **argv, int single)
{
char const *cp = s;

	if (cp == NULLCHAR || !*cp)
		return -1;

	while (wildmat(cp, p, argv) == FALSE)
		if(*++cp == '\0')
			return -1;
	if ((single == TRUE) && haveDot(s, cp - s))
		return -1;
	return cp - s;
}



int
wildmat (register const char *s, register char *p, register char **argv)
{
register int last;
register int matched;
register int reverse;
register int cnt;
int single;

	if (!s || !p)
		return FALSE;

	for(; *p; s++,p++){
		switch(*p){
		case '\\':
			/* Literal match with following character; fall through. */
			p++;
			/* fall through */
		default:
		     /*   if(*s != *p)   */
		     if (tolower(*s) != tolower(*p))
				return FALSE;
		     continue;
		case '?':
			/* Match anything. */
			if(*s == '\0')
				return FALSE;
			continue;
		case '*':
		case '+':
			single = (*p == '+');

			/* Trailing star matches everything. */
			if(argv == NULLCHARP)
				return *++p ? 1 + Star(s, p, NULLCHARP, single) : TRUE;
			if(*++p == '\0'){
				cnt = (int) strlen(s);
				if ((single == TRUE) && haveDot(s, cnt))
					return FALSE;
			} else {
				if((cnt = Star(s, p, argv+1, single)) == -1)
					return FALSE;
			}
#ifdef TEST
			*argv = malloc((unsigned)cnt+1);
#else
			*argv = mallocw((unsigned)cnt+1);
#endif
			strncpy(*argv,s,(size_t)cnt);
			*(*argv + cnt) = '\0';
			return TRUE;
		case '[':
			/* [^....] means inverse character class. */
			reverse = (p[1] == '^' || p[1] == '!') ? TRUE : FALSE;
			if(reverse)
				p++;
			for(last = 0400, matched = FALSE; *++p && *p != ']'; last = *p){
				/* This next line requires a good C compiler. */
				if(*p == '-' ? *s <= *++p && *s >= last : *s == *p)
					matched = TRUE;
			}
			if(matched == reverse)
				return FALSE;
			continue;
		}
	}
	/* For "tar" use, matches that end at a slash also work. --hoptoad!gnu */
	return *s == '\0' || *s == '/';
}




#ifdef  TEST
#include <stdio.h>

extern char *gets();

void
main (void)
{
char pattern[80];
char text[80];
char *argv[80], *cp;
int cnt;
    
	while (TRUE){
		printf("Enter pattern:  ");
		if(gets(pattern) == NULL)
			break;
		while (TRUE){
			memset(argv, 0, 80 * sizeof (char *));
			printf("Enter text:  ");
			if(gets(text) == NULL)
				exit(0);
			if(text[0] == '\0')
				/* Blank line; go back and get a new pattern. */
				break;
			printf("      %d\n", wildmat(text, pattern, argv));
			for(cnt = 0; argv[cnt] != NULLCHAR; ++cnt){
				printf("String %d is: '%s'\n",cnt,argv[cnt]);
				free(argv[cnt]);
			}
		}
	}
	exit(0);
}
#endif  /* TEST */
