1 /*
2  * ngIRCd -- The Next Generation IRC Daemon
3  * Copyright (c)2001,2002 by Alexander Barton (alex@barton.de)
4  *
5  * This program is free software; you can redistribute it and/or modify
6  * it under the terms of the GNU General Public License as published by
7  * the Free Software Foundation; either version 2 of the License, or
8  * (at your option) any later version.
9  * Please read the file COPYING, README and AUTHORS for more information.
10  *
11  * Wildcard pattern matching
12  */
13 
14 
15 #include "portab.h"
16 
17 static char UNUSED id[] = "$Id: match.c,v 1.3 2005/03/19 18:43:49 fw Exp $";
18 
19 #include "imp.h"
20 #include <assert.h>
21 #include <string.h>
22 
23 #include "exp.h"
24 #include "match.h"
25 
26 
27 /*
28  * Die Pattern-Matching-Funkionen [Matche(), Matche_After_Star()] basieren
29  * auf Versionen von J. Kercheval. Die Version 1.1 wurde am 12.03.1991 als
30  * "public domain" freigegeben:
31  * <http://www.snippets.org/snippets/portable/MATCH+C.php3>
32  */
33 
34 
35 LOCAL int Matche PARAMS(( char *p, char *t ));
36 LOCAL int Matche_After_Star PARAMS(( char *p, char *t ));
37 
38 
39 #define MATCH_PATTERN	6	/* bad pattern */
40 #define MATCH_LITERAL	5	/* match failure on literal match */
41 #define MATCH_RANGE	4	/* match failure on [..] construct */
42 #define MATCH_ABORT	3	/* premature end of text string */
43 #define MATCH_END	2	/* premature end of pattern string */
44 #define MATCH_VALID	1	/* valid match */
45 
46 
47 GLOBAL bool
48 Match( char *Pattern, char *String )
49 {
50 	/* Pattern mit String vergleichen */
51 	if( Matche( Pattern, String ) == MATCH_VALID ) return true;
52 	else return false;
53 } /* Match */
54 
55 
56 LOCAL int
57 Matche( char *p, char *t )
58 {
59 	register char range_start, range_end;
60 	bool invert;
61 	bool member_match;
62 	bool loop;
63 
64 	for( ; *p; p++, t++ )
65 	{
66 		/* if this is the end of the text then this is the end of the match */
67 		if( ! *t )
68 		{
69 			return ( *p == '*' && *++p == '\0' ) ? MATCH_VALID : MATCH_ABORT;
70 		}
71 
72 		/* determine and react to pattern type */
73 		switch( *p )
74 		{
75 			case '?':	/* single any character match */
76 				break;
77 
78 			case '*':	/* multiple any character match */
79 				return Matche_After_Star( p, t );
80 
81 			case '[':	/* [..] construct, single member/exclusion character match */
82 				/* move to beginning of range */
83 				p++;
84 
85 				/* check if this is a member match or exclusion match */
86 				invert = false;
87 				if( *p == '!' || *p == '^' )
88 				{
89 					invert = true;
90 					p++;
91 				}
92 
93 				/* if closing bracket here or at range start then we have a malformed pattern */
94 				if ( *p == ']' ) return MATCH_PATTERN;
95 
96 				member_match = false;
97 				loop = true;
98 
99 				while( loop )
100 				{
101 					/* if end of construct then loop is done */
102 					if( *p == ']' )
103 					{
104 						loop = false;
105 						continue;
106 					}
107 
108 					/* matching a '!', '^', '-', '\' or a ']' */
109 					if( *p == '\\' ) range_start = range_end = *++p;
110 					else  range_start = range_end = *p;
111 
112 					/* if end of pattern then bad pattern (Missing ']') */
113 					if( ! *p ) return MATCH_PATTERN;
114 
115 					/* check for range bar */
116 					if( *++p == '-' )
117 					{
118 						/* get the range end */
119 						range_end = *++p;
120 
121 						/* if end of pattern or construct then bad pattern */
122 						if( range_end == '\0' || range_end == ']' ) return MATCH_PATTERN;
123 
124 						/* special character range end */
125 						if( range_end == '\\' )
126 						{
127 							range_end = *++p;
128 
129 							/* if end of text then we have a bad pattern */
130 							if ( ! range_end ) return MATCH_PATTERN;
131 						}
132 
133 						/* move just beyond this range */
134 						p++;
135 					}
136 
137 					/* if the text character is in range then match found. make sure the range
138 					 * letters have the proper relationship to one another before comparison */
139 					if( range_start < range_end )
140 					{
141 						if( *t >= range_start && *t <= range_end )
142 						{
143 							member_match = true;
144 							loop = false;
145 						}
146 					}
147 					else
148 					{
149 						if( *t >= range_end && *t <= range_start )
150 						{
151 							member_match = true;
152 							loop = false;
153 						}
154 					}
155 				}
156 
157 				/* if there was a match in an exclusion set then no match */
158 				/* if there was no match in a member set then no match */
159 				if(( invert && member_match ) || ! ( invert || member_match )) return MATCH_RANGE;
160 
161 				/* if this is not an exclusion then skip the rest of the [...]
162 				 * construct that already matched. */
163 				if( member_match )
164 				{
165 					while( *p != ']' )
166 					{
167 						/* bad pattern (Missing ']') */
168 						if( ! *p ) return MATCH_PATTERN;
169 
170 						/* skip exact match */
171 						if( *p == '\\' )
172 						{
173 							p++;
174 
175 							/* if end of text then we have a bad pattern */
176 							if( ! *p ) return MATCH_PATTERN;
177 						}
178 
179 						/* move to next pattern char */
180 						p++;
181 					}
182 				}
183 				break;
184 			case '\\':	/* next character is quoted and must match exactly */
185 				/* move pattern pointer to quoted char and fall through */
186 				p++;
187 
188 				/* if end of text then we have a bad pattern */
189 				if( ! *p ) return MATCH_PATTERN;
190 
191 				/* must match this character exactly */
192 			default:
193 				if( *p != *t ) return MATCH_LITERAL;
194 		}
195 	}
196 	/* if end of text not reached then the pattern fails */
197 
198 	if( *t ) return MATCH_END;
199 	else return MATCH_VALID;
200 } /* Matche */
201 
202 
203 LOCAL int
204 Matche_After_Star( char *p, char *t )
205 {
206 	register int nextp, match = 0;
207 
208 	/* pass over existing ? and * in pattern */
209 	while( *p == '?' || *p == '*' )
210 	{
211 		/* take one char for each ? and + */
212 		if (*p == '?')
213 		{
214 			/* if end of text then no match */
215 			if( ! *t++ ) return MATCH_ABORT;
216 		}
217 
218 		/* move to next char in pattern */
219 		p++;
220 	}
221 
222 	/* if end of pattern we have matched regardless of text left */
223 	if( ! *p ) return MATCH_VALID;
224 
225 	/* get the next character to match which must be a literal or '[' */
226 	nextp = *p;
227 	if( nextp == '\\' )
228 	{
229 		nextp = p[1];
230 
231 		/* if end of text then we have a bad pattern */
232 		if( ! nextp ) return MATCH_PATTERN;
233 	}
234 
235 	/* Continue until we run out of text or definite result seen */
236 	do
237 	{
238 		/* a precondition for matching is that the next character
239 		 * in the pattern match the next character in the text or that
240 		 * the next pattern char is the beginning of a range.  Increment
241 		 * text pointer as we go here */
242 		if( nextp == *t || nextp == '[' ) match = Matche( p, t );
243 
244 		/* if the end of text is reached then no match */
245 		if( ! *t++ ) match = MATCH_ABORT;
246 	} while( match != MATCH_VALID && match != MATCH_ABORT && match != MATCH_PATTERN );
247 
248 	/* return result */
249 	return match;
250 } /* Matche_After_Star */
251 
252 
253 /* -eof- */