1/*
2 * Copyright 1994 Christopher Seiwald.  All rights reserved.
3 *
4 * This file is part of Jam - see jam.c for Copyright information.
5 */
6
7/*
8 * glob.c - match a string against a simple pattern
9 *
10 * Understands the following patterns:
11 *
12 *	*	any number of characters
13 *	?	any single character
14 *	[a-z]	any single character in the range a-z
15 *	[^a-z]	any single character not in the range a-z
16 *	\x	match x
17 *
18 * External functions:
19 *
20 *	glob() - match a string against a simple pattern
21 *
22 * Internal functions:
23 *
24 *	globchars() - build a bitlist to check for character group match
25 *
26 * 11/04/02 (seiwald) - const-ing for string literals
27 */
28
29# include "jam.h"
30
31# define CHECK_BIT( tab, bit ) ( tab[ (bit)/8 ] & (1<<( (bit)%8 )) )
32# define BITLISTSIZE 16	/* bytes used for [chars] in compiled expr */
33
34static void globchars( const char *s, const char *e, char *b );
35
36/*
37 * glob() - match a string against a simple pattern
38 */
39
40int
41glob(
42	const char *c,
43	const char *s )
44{
45	char bitlist[ BITLISTSIZE ];
46	const char *here;
47
48	for( ;; )
49	    switch( *c++ )
50	{
51	case '\0':
52		return *s ? -1 : 0;
53
54	case '?':
55		if( !*s++ )
56		    return 1;
57		break;
58
59	case '[':
60		/* scan for matching ] */
61
62		here = c;
63		do if( !*c++ )
64			return 1;
65		while( here == c || *c != ']' );
66		c++;
67
68		/* build character class bitlist */
69
70		globchars( here, c, bitlist );
71
72		if( !CHECK_BIT( bitlist, *(unsigned char *)s ) )
73			return 1;
74		s++;
75		break;
76
77	case '*':
78		here = s;
79
80		while( *s )
81			s++;
82
83		/* Try to match the rest of the pattern in a recursive */
84		/* call.  If the match fails we'll back up chars, retrying. */
85
86		while( s != here )
87		{
88			int r;
89
90			/* A fast path for the last token in a pattern */
91
92			r = *c ? glob( c, s ) : *s ? -1 : 0;
93
94			if( !r )
95				return 0;
96			else if( r < 0 )
97				return 1;
98
99			--s;
100		}
101		break;
102
103	case '\\':
104		/* Force literal match of next char. */
105
106		if( !*c || *s++ != *c++ )
107		    return 1;
108		break;
109
110	default:
111		if( *s++ != c[-1] )
112		    return 1;
113		break;
114	}
115}
116
117/*
118 * globchars() - build a bitlist to check for character group match
119 */
120
121static void
122globchars(
123	const char *s,
124	const char *e,
125	char *b )
126{
127	int neg = 0;
128
129	memset( b, '\0', BITLISTSIZE  );
130
131	if( *s == '^')
132		neg++, s++;
133
134	while( s < e )
135	{
136		int c;
137
138		if( s+2 < e && s[1] == '-' )
139		{
140			for( c = s[0]; c <= s[2]; c++ )
141				b[ c/8 ] |= (1<<(c%8));
142			s += 3;
143		} else {
144			c = *s++;
145			b[ c/8 ] |= (1<<(c%8));
146		}
147	}
148
149	if( neg )
150	{
151		int i;
152		for( i = 0; i < BITLISTSIZE; i++ )
153			b[ i ] ^= 0377;
154	}
155
156	/* Don't include \0 in either $[chars] or $[^chars] */
157
158	b[0] &= 0376;
159}
160