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