wildmat.c

早期freebsd实现

/*  $Revision: 4.0.1.1 $
**
**  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.  It is 8bit clean.
**
**  Written by Rich $alz, mirror!rs, Wed Nov 26 19:03:17 EST 1986.
**  Rich $alz is now <[e-mail]>.
**  April, 1991:  Replaced mutually-recursive calls with in-line code
**  for the star character.
**
**  Special thanks to Lars Mathiesen <[e-mail]> for the ABORT code.
**  This can greatly speed up failing wildcard patterns.  For example:
**	pattern: -*-*-*-*-*-*-12-*-*-*-m-*-*-*
**	text 1:	 -adobe-courier-bold-o-normal--12-120-75-75-m-70-iso8859-1
**	text 2:	 -adobe-courier-bold-o-normal--12-120-75-75-X-70-iso8859-1
**  Text 1 matches with 51 calls, while text 2 fails with 54 calls.  Without
**  the ABORT, then it takes 22310 calls to fail.  Ugh.  The following
**  explanation is from Lars:
**  The precondition that must be fulfilled is that DoMatch will consume
**  at least one character in text.  This is true if *p is neither '*' nor
**  '\0'.)  The last return has ABORT instead of FALSE to avoid quadratic
**  behaviour in cases like pattern "*a*b*c*d" with text "abcxxxxx".  With
**  FALSE, each star-loop has to run to the end of the text; with ABORT
**  only the last one does.
**
**  Once the control of one instance of DoMatch enters the star-loop, that
**  instance will return either TRUE or ABORT, and any calling instance
**  will therefore return immediately after (without calling recursively
**  again).  In effect, only one star-loop is ever active.  It would be
**  possible to modify the code to maintain this context explicitly,
**  eliminating all recursive calls at the cost of some complication and
**  loss of clarity (and the ABORT stuff seems to be unclear enough by
**  itself).  I think it would be unwise to try to get this into a
**  released version unless you have a good test data base to try it out
**  on.
*/

#define TRUE			1
#define FALSE			0
#define ABORT			-1


    /* What character marks an inverted character class? */
#define NEGATE_CLASS		'^'
    /* Is "*" a common pattern? */
#define OPTIMIZE_JUST_STAR
    /* Do tar(1) matching rules, which ignore a trailing slash? */
#undef MATCH_TAR_PATTERN


/*
**  Match text and p, return TRUE, FALSE, or ABORT.
*/
static int
DoMatch(text, p)
    char	*text;
    char	*p;
{
    int	last;
    int	matched;
    int	reverse;

    for ( ; *p; text++, p++) {
	if (*text == '\0' && *p != '*')
	    return ABORT;
	switch (*p) {
	case '\\':
	    /* Literal match with following character. */
	    p++;
	    /* FALLTHROUGH */
	default:
	    if (*text != *p)
		return FALSE;
	    continue;
	case '?':
	    /* Match anything. */
	    continue;
	case '*':
	    while (*++p == '*')
		/* Consecutive stars act just like one. */
		continue;
	    if (*p == '\0')
		/* Trailing star matches everything. */
		return TRUE;
	    while (*text)
		if ((matched = DoMatch(text++, p)) != FALSE)
		    return matched;
	    return ABORT;
	case '[':
	    reverse = p[1] == NEGATE_CLASS ? TRUE : FALSE;
	    if (reverse)
		/* Inverted character class. */
		p++;
	    for (last = 0400, matched = FALSE; *++p && *p != ']'; last = *p)
		/* This next line requires a good C compiler. */
		if (*p == '-' ? *text <= *++p && *text >= last : *text == *p)
		    matched = TRUE;
	    if (matched == reverse)
		return FALSE;
	    continue;
	}
    }

#ifdef	MATCH_TAR_PATTERN
    if (*text == '/')
	return TRUE;
#endif	/* MATCH_TAR_ATTERN */
    return *text == '\0';
}


/*
**  User-level routine.  Returns TRUE or FALSE.
*/
int
wildmat(text, p)
    char	*text;
    char	*p;
{
#ifdef	OPTIMIZE_JUST_STAR
    if (p[0] == '*' && p[1] == '\0')
	return TRUE;
#endif	/* OPTIMIZE_JUST_STAR */
    return DoMatch(text, p) == TRUE;
}

#include <stdio.h>
#include <sys/types.h>
#include <dirent.h>
#include <sys/stat.h>
#if __STDC__
#ifdef unix
#define _SIZE_T	/* unix defines size_t in sys/types.h */
#endif
#ifndef _COMPILER_H
#  include <compiler.h>
#endif
#include <stddef.h>
#include <stdlib.h>
#else
extern char *malloc(), *realloc();
extern char *rindex(),  *strdup();
#define __PROTO(x) ()
#endif
#include <string.h>

#define MAX_DIR	32	/* max depth of dir recursion */
static struct {
	char *dir, *patt;
} dir_stack[MAX_DIR];
static int stack_p;
static char **matches;
static int nmatches;

static void *ck_memalloc __PROTO((void *));
#define ck_strdup(p) ck_memalloc(strdup(p))
#define ck_malloc(s) ck_memalloc(malloc(s))
#define ck_realloc(p, s) ck_memalloc(realloc(p, s))


#define DEBUGX(x) 

/*
 * return true if patt contains a wildcard char
 */
int contains_wild(patt)
char *patt;
{
    char c;
    char *p;

    /* only check for wilds in the basename part of the pathname only */
    if((p = rindex(patt, '/')) == NULL)
	p = rindex(patt, '\\');
    if(!p)
	p = patt;

    while((c = *p++))
	if((c == '*') || (c == '?') || (c == '['))
	    return 1;
    return 0;
}

#ifndef ZOO
void free_all()
{
    char **p;

    if(!matches)
	return;

    for(p = matches; *p; p++)
	free(*p);
    free(matches);
    matches = NULL;
}
#endif

static void push(dir, patt)
char *dir;
char *patt;
{
    if(stack_p < (MAX_DIR - 2))
	stack_p++;
    else
    {
	fprintf(stderr,"directory stack overflow\n");
	exit(99);
    }
    dir_stack[stack_p].dir = dir;
    dir_stack[stack_p].patt = patt;
}

/*
 * glob patt
 * if decend_dir is true, recursively decend any directories encountered.
 * returns pointer to all matches encountered.
 * if the initial patt is a directory, and decend_dir is true, it is
 * equivalent to specifying the pattern "patt\*"
 *
 * Restrictions:
 *  - handles wildcards only in the base part of a pathname
 *    ie: will not handle \foo\*\bar\ (wildcard in the middle of pathname)
 *
 *  - max dir recursion is MAX_DIR
 *
 *  - on certain failures it will just skip potential matches as if they
 *    were not present.
 *
 *  ++jrb	[e-mail]
 */
static char **do_match __PROTO((int decend_dir));

char **glob(patt, decend_dir)
char *patt;
int decend_dir;
{
    char *dir, *basepatt, *p;
    struct stat s;

    DEBUGX((fprintf(stderr,"glob(%s, %d)\n", patt, decend_dir)));
    matches = NULL;
    nmatches = 0;
    stack_p = -1;

    /* first check for wildcards */
    if(contains_wild(patt))
    {
	/* break it up into dir and base patt, do_matches and return */
	p = ck_strdup(patt);
	if((basepatt = rindex(p, '/')) == NULL)
	    basepatt = rindex(p, '\\');
        if(basepatt)
        {
	    dir = p;
	    *basepatt++ = '\0';
	    basepatt = ck_strdup(basepatt);
        }
        else
        {
	    dir = ck_strdup(".");
	    basepatt = p;
        }

        if(strcmp(basepatt, "*.*") == 0)
        {
            /* the desktop, and other braindead shells strike again */
            basepatt[1] = '\0';
        }
	push(dir, basepatt);
	DEBUGX((fprintf(stderr, "calling %s, %s\n", dir, basepatt)));
	return do_match(decend_dir);
    }

    /* if no wilds, check for dir */
    if(decend_dir && (!stat(patt, &s)))
    {
	if((s.st_mode & S_IFMT) == S_IFDIR)
	{   /* is a dir */
	    size_t len = strlen(patt);
	    
	    dir = ck_strdup(patt);
	    --len;
	    if(len && ((dir[len] == '/') 
#ifdef atarist
	       || (dir[len] == '\\')
#endif
	     ))
		dir[len] = '\0';
	    basepatt = ck_strdup("*");
	    push(dir, basepatt);
	    DEBUGX((fprintf(stderr, "calling %s, %s\n", dir, basepatt)));
	    return do_match(decend_dir);
        }
    }
    return NULL;
}

static char **do_match(decend_dir)
int decend_dir;
{
    DIR *dirp;
    struct dirent *d;
    struct stat s;
    char *dir, *basepatt;

    while(stack_p >= 0)
    {
	dir = ck_strdup(dir_stack[stack_p].dir); 
	free(dir_stack[stack_p].dir);
        basepatt = ck_strdup(dir_stack[stack_p].patt);
	free(dir_stack[stack_p--].patt);
	
        DEBUGX((fprintf(stderr,"dir %s patt %s stack %d\n", dir, basepatt, stack_p)));

    	dirp = opendir(dir);
	if(!dirp)
	{
	    free(dir);
	    DEBUGX((fprintf(stderr,"no dir\n")));
	    continue;
        }
	
        while((d = readdir(dirp)))
        {
	    char *p = ck_malloc(strlen(dir) + strlen(d->d_name) + 2L);
            if(strcmp(dir, "."))
                                     /* If we have a full pathname then */
	    {			     /* let's append the directory info */
		strcpy(p, dir);
#ifndef unix
		strcat(p, "\\");
#else
		strcat(p, "/");
#endif
		strcat(p, d->d_name);
	    }
	    else		      /* Otherwise, the name is just fine, */
		strcpy(p, d->d_name); /* there's no need for './' -- bjsjr */

	    DEBUGX((fprintf(stderr, "Testing %s\n", p)));
	    if(!stat(p, &s))	/* if stat fails, ignore it */
            {
	        if( ((s.st_mode & S_IFMT) == S_IFREG) ||
		    ((s.st_mode & S_IFMT) == S_IFLNK) )
	        {  /* it is a file/symbolic link */
		    if(wildmat(d->d_name, basepatt))
		    {  /* it matches pattern */
			DEBUGX((fprintf(stderr,"File Matched\n")));
			if(matches == NULL)
			    matches = (char **)ck_malloc(sizeof(char *));
			else
			    matches = (char **)
			      ck_realloc(matches, (nmatches+1)*sizeof(char *)); 
			matches[nmatches++] = p;
		    } /* no match */
		    else
		    {
			DEBUGX((fprintf(stderr,"No File Match\n")));
		        free(p);
		    }
		} else if(decend_dir && ((s.st_mode & S_IFMT) == S_IFDIR))
		{
		    if(!((!strcmp(d->d_name,".")) || (!strcmp(d->d_name, "..")
#ifdef atarist
    		         || (!strcmp(d->d_name, ".dir"))
#endif
    		    )))
		    {
			char *push_p = ck_strdup("*");
			push(p, push_p);
			DEBUGX((fprintf(stderr,"Dir pushed\n")));
		    }
		    else
		    {
			DEBUGX((fprintf(stderr, "DIR skipped\n")));
			free(p);
		    }
	        }
		else
		{
		    DEBUGX((fprintf(stderr, "Not a dir/no decend\n")));
		    free(p);
		}
	    } /* stat */
	    else
	    {
		DEBUGX((fprintf(stderr, "Stat failed\n")));
		free(p);
	    }
        } /* while readdir */
        closedir(dirp);
	free(basepatt);
	free(dir);
	DEBUGX((fprintf(stderr, "Dir done\n\n")));
    } /* while dirs in stack */
    
    if(!nmatches)
    {
	DEBUGX((fprintf(stderr, "No matches\n")));
	return NULL;
    }
    
    matches = (char **)realloc(matches, (nmatches+1)*sizeof(char *));
    if(!matches)
    {  return NULL; }
    matches[nmatches] = NULL;
    DEBUGX((fprintf(stderr, "%d matches\n", nmatches)));    
    return matches;
}

#ifdef ZOO
#include "errors.i"
#endif

static void *ck_memalloc(p)
void *p;
{
    if(!p)
    {
#ifndef ZOO
        fprintf(stderr, "Out of memory\n");
	exit(98);
#else
        prterror('f', no_memory);
#endif
    }
    return p;
}

#ifdef TEST_GLOB
void test(path, dec)
char *path;
int dec;
{
    char **m;
    char **matches;

    printf("Testing %s %d\n", path, dec);
    matches = glob(path, dec);
    if(!matches)
    {
	printf("No matches\n");
    }
    else
    {
        for(m = matches; *m; m++)
	    printf("%s\n", *m);
	putchar('\n');
        free_all();
    }
}

int main()
{
#ifndef unix
    test("e:\\lib\\*.olb", 0);
    test("e:\\lib", 0);
    test("e:\\lib\\", 1);
#else
    test("/net/acae127/home/bammi/News/comp.sources.misc/*.c", 0);
    test("/net/acae127/home/bammi/News/comp.sources.misc", 0);
    test("/net/acae127/home/bammi/News/comp.sources.misc", 1);
    test("/net/acae127/home/bammi/atari/cross-gcc", 1);
#endif
    
    return 0;
}

#endif

#ifdef	TEST_WILDMAT
#include <stdio.h>

/* Yes, we use gets not fgets.  Sue me. */
extern char	*gets();


main()
{
    char	pattern[80];
    char	text[80];

    printf("Wildmat tester.  Enter pattern, then strings to test.\n");
    printf("A blank line gets prompts for a new pattern; a blank pattern\n");
    printf("exits the program.\n\n");

    for ( ; ; ) {
	printf("Enter pattern:  ");
	if (gets(pattern) == NULL)
	    break;
	for ( ; ; ) {
	    printf("Enter text:  ");
	    if (gets(text) == NULL)
		exit(0);
	    if (text[0] == '\0')
		/* Blank line; go back and get a new pattern. */
		break;
	    printf("      %s\n", wildmat(text, pattern) ? "YES" : "NO");
	}
    }

    exit(0);
    /* NOTREACHED */
}
#endif	/* TEST_WILDMAT */