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