2 8907c8dd 2002-06-26 alex * ngIRCd -- The Next Generation IRC Daemon
3 8907c8dd 2002-06-26 alex * Copyright (c)2001,2002 by Alexander Barton (alex@barton.de)
5 8907c8dd 2002-06-26 alex * Dieses Programm ist freie Software. Sie koennen es unter den Bedingungen
6 8907c8dd 2002-06-26 alex * der GNU General Public License (GPL), wie von der Free Software Foundation
7 8907c8dd 2002-06-26 alex * herausgegeben, weitergeben und/oder modifizieren, entweder unter Version 2
8 8907c8dd 2002-06-26 alex * der Lizenz oder (wenn Sie es wuenschen) jeder spaeteren Version.
9 8907c8dd 2002-06-26 alex * Naehere Informationen entnehmen Sie bitter der Datei COPYING. Eine Liste
10 8907c8dd 2002-06-26 alex * der an ngIRCd beteiligten Autoren finden Sie in der Datei AUTHORS.
12 8907c8dd 2002-06-26 alex * $Id: match.c,v 1.1 2002/06/26 15:42:58 alex Exp $
14 8907c8dd 2002-06-26 alex * match.c: Wildcard Pattern Matching
18 8907c8dd 2002-06-26 alex #include "portab.h"
20 8907c8dd 2002-06-26 alex #include "imp.h"
21 8907c8dd 2002-06-26 alex #include <assert.h>
22 8907c8dd 2002-06-26 alex #include <string.h>
24 8907c8dd 2002-06-26 alex #include "exp.h"
25 8907c8dd 2002-06-26 alex #include "match.h"
29 8907c8dd 2002-06-26 alex * Die Pattern-Matching-Funkionen [Matche(), Matche_After_Star()] basieren
30 8907c8dd 2002-06-26 alex * auf Versionen von J. Kercheval. Die Version 1.1 wurde am 12.03.1991 als
31 8907c8dd 2002-06-26 alex * "public domain" freigegeben:
32 8907c8dd 2002-06-26 alex * <http://www.snippets.org/snippets/portable/MATCH+C.php3>
36 8907c8dd 2002-06-26 alex LOCAL INT Matche PARAMS(( REGISTER CHAR *p, REGISTER CHAR *t ));
37 8907c8dd 2002-06-26 alex LOCAL INT Matche_After_Star PARAMS(( REGISTER CHAR *p, REGISTER CHAR *t ));
40 8907c8dd 2002-06-26 alex #define MATCH_PATTERN 6 /* bad pattern */
41 8907c8dd 2002-06-26 alex #define MATCH_LITERAL 5 /* match failure on literal match */
42 8907c8dd 2002-06-26 alex #define MATCH_RANGE 4 /* match failure on [..] construct */
43 8907c8dd 2002-06-26 alex #define MATCH_ABORT 3 /* premature end of text string */
44 8907c8dd 2002-06-26 alex #define MATCH_END 2 /* premature end of pattern string */
45 8907c8dd 2002-06-26 alex #define MATCH_VALID 1 /* valid match */
48 8907c8dd 2002-06-26 alex GLOBAL BOOLEAN
49 8907c8dd 2002-06-26 alex Match( CHAR *Pattern, CHAR *String )
51 8907c8dd 2002-06-26 alex /* Pattern mit String vergleichen */
52 8907c8dd 2002-06-26 alex if( Matche( Pattern, String ) == MATCH_VALID ) return TRUE;
53 8907c8dd 2002-06-26 alex else return FALSE;
54 8907c8dd 2002-06-26 alex } /* Match */
58 8907c8dd 2002-06-26 alex Matche( REGISTER CHAR *p, REGISTER CHAR *t )
60 8907c8dd 2002-06-26 alex REGISTER CHAR range_start, range_end;
61 8907c8dd 2002-06-26 alex BOOLEAN invert;
62 8907c8dd 2002-06-26 alex BOOLEAN member_match;
63 8907c8dd 2002-06-26 alex BOOLEAN loop;
65 8907c8dd 2002-06-26 alex for( ; *p; p++, t++ )
67 8907c8dd 2002-06-26 alex /* if this is the end of the text then this is the end of the match */
70 8907c8dd 2002-06-26 alex return ( *p == '*' && *++p == '\0' ) ? MATCH_VALID : MATCH_ABORT;
73 8907c8dd 2002-06-26 alex /* determine and react to pattern type */
74 8907c8dd 2002-06-26 alex switch( *p )
76 8907c8dd 2002-06-26 alex case '?': /* single any character match */
79 8907c8dd 2002-06-26 alex case '*': /* multiple any character match */
80 8907c8dd 2002-06-26 alex return Matche_After_Star( p, t );
82 8907c8dd 2002-06-26 alex case '[': /* [..] construct, single member/exclusion character match */
83 8907c8dd 2002-06-26 alex /* move to beginning of range */
86 8907c8dd 2002-06-26 alex /* check if this is a member match or exclusion match */
87 8907c8dd 2002-06-26 alex invert = FALSE;
88 8907c8dd 2002-06-26 alex if( *p == '!' || *p == '^' )
90 8907c8dd 2002-06-26 alex invert = TRUE;
94 8907c8dd 2002-06-26 alex /* if closing bracket here or at range start then we have a malformed pattern */
95 8907c8dd 2002-06-26 alex if ( *p == ']' ) return MATCH_PATTERN;
97 8907c8dd 2002-06-26 alex member_match = FALSE;
98 8907c8dd 2002-06-26 alex loop = TRUE;
100 8907c8dd 2002-06-26 alex while( loop )
102 8907c8dd 2002-06-26 alex /* if end of construct then loop is done */
103 8907c8dd 2002-06-26 alex if( *p == ']' )
105 8907c8dd 2002-06-26 alex loop = FALSE;
109 8907c8dd 2002-06-26 alex /* matching a '!', '^', '-', '\' or a ']' */
110 8907c8dd 2002-06-26 alex if( *p == '\\' ) range_start = range_end = *++p;
111 8907c8dd 2002-06-26 alex else range_start = range_end = *p;
113 8907c8dd 2002-06-26 alex /* if end of pattern then bad pattern (Missing ']') */
114 8907c8dd 2002-06-26 alex if( ! *p ) return MATCH_PATTERN;
116 8907c8dd 2002-06-26 alex /* check for range bar */
117 8907c8dd 2002-06-26 alex if( *++p == '-' )
119 8907c8dd 2002-06-26 alex /* get the range end */
120 8907c8dd 2002-06-26 alex range_end = *++p;
122 8907c8dd 2002-06-26 alex /* if end of pattern or construct then bad pattern */
123 8907c8dd 2002-06-26 alex if( range_end == '\0' || range_end == ']' ) return MATCH_PATTERN;
125 8907c8dd 2002-06-26 alex /* special character range end */
126 8907c8dd 2002-06-26 alex if( range_end == '\\' )
128 8907c8dd 2002-06-26 alex range_end = *++p;
130 8907c8dd 2002-06-26 alex /* if end of text then we have a bad pattern */
131 8907c8dd 2002-06-26 alex if ( ! range_end ) return MATCH_PATTERN;
134 8907c8dd 2002-06-26 alex /* move just beyond this range */
138 8907c8dd 2002-06-26 alex /* if the text character is in range then match found. make sure the range
139 8907c8dd 2002-06-26 alex * letters have the proper relationship to one another before comparison */
140 8907c8dd 2002-06-26 alex if( range_start < range_end )
142 8907c8dd 2002-06-26 alex if( *t >= range_start && *t <= range_end )
144 8907c8dd 2002-06-26 alex member_match = TRUE;
145 8907c8dd 2002-06-26 alex loop = FALSE;
150 8907c8dd 2002-06-26 alex if( *t >= range_end && *t <= range_start )
152 8907c8dd 2002-06-26 alex member_match = TRUE;
153 8907c8dd 2002-06-26 alex loop = FALSE;
158 8907c8dd 2002-06-26 alex /* if there was a match in an exclusion set then no match */
159 8907c8dd 2002-06-26 alex /* if there was no match in a member set then no match */
160 8907c8dd 2002-06-26 alex if(( invert && member_match ) || ! ( invert || member_match )) return MATCH_RANGE;
162 8907c8dd 2002-06-26 alex /* if this is not an exclusion then skip the rest of the [...]
163 8907c8dd 2002-06-26 alex * construct that already matched. */
164 8907c8dd 2002-06-26 alex if( member_match )
166 8907c8dd 2002-06-26 alex while( *p != ']' )
168 8907c8dd 2002-06-26 alex /* bad pattern (Missing ']') */
169 8907c8dd 2002-06-26 alex if( ! *p ) return MATCH_PATTERN;
171 8907c8dd 2002-06-26 alex /* skip exact match */
172 8907c8dd 2002-06-26 alex if( *p == '\\' )
176 8907c8dd 2002-06-26 alex /* if end of text then we have a bad pattern */
177 8907c8dd 2002-06-26 alex if( ! *p ) return MATCH_PATTERN;
180 8907c8dd 2002-06-26 alex /* move to next pattern char */
185 8907c8dd 2002-06-26 alex case '\\': /* next character is quoted and must match exactly */
186 8907c8dd 2002-06-26 alex /* move pattern pointer to quoted char and fall through */
189 8907c8dd 2002-06-26 alex /* if end of text then we have a bad pattern */
190 8907c8dd 2002-06-26 alex if( ! *p ) return MATCH_PATTERN;
192 8907c8dd 2002-06-26 alex /* must match this character exactly */
194 8907c8dd 2002-06-26 alex if( *p != *t ) return MATCH_LITERAL;
197 8907c8dd 2002-06-26 alex /* if end of text not reached then the pattern fails */
199 8907c8dd 2002-06-26 alex if( *t ) return MATCH_END;
200 8907c8dd 2002-06-26 alex else return MATCH_VALID;
201 8907c8dd 2002-06-26 alex } /* Matche */
205 8907c8dd 2002-06-26 alex Matche_After_Star( REGISTER CHAR *p, REGISTER CHAR *t )
207 8907c8dd 2002-06-26 alex REGISTER INT nextp, match = 0;
209 8907c8dd 2002-06-26 alex /* pass over existing ? and * in pattern */
210 8907c8dd 2002-06-26 alex while( *p == '?' || *p == '*' )
212 8907c8dd 2002-06-26 alex /* take one char for each ? and + */
213 8907c8dd 2002-06-26 alex if (*p == '?')
215 8907c8dd 2002-06-26 alex /* if end of text then no match */
216 8907c8dd 2002-06-26 alex if( ! *t++ ) return MATCH_ABORT;
219 8907c8dd 2002-06-26 alex /* move to next char in pattern */
223 8907c8dd 2002-06-26 alex /* if end of pattern we have matched regardless of text left */
224 8907c8dd 2002-06-26 alex if( ! *p ) return MATCH_VALID;
226 8907c8dd 2002-06-26 alex /* get the next character to match which must be a literal or '[' */
227 8907c8dd 2002-06-26 alex nextp = *p;
228 8907c8dd 2002-06-26 alex if( nextp == '\\' )
230 8907c8dd 2002-06-26 alex nextp = p[1];
232 8907c8dd 2002-06-26 alex /* if end of text then we have a bad pattern */
233 8907c8dd 2002-06-26 alex if( ! nextp ) return MATCH_PATTERN;
236 8907c8dd 2002-06-26 alex /* Continue until we run out of text or definite result seen */
239 8907c8dd 2002-06-26 alex /* a precondition for matching is that the next character
240 8907c8dd 2002-06-26 alex * in the pattern match the next character in the text or that
241 8907c8dd 2002-06-26 alex * the next pattern char is the beginning of a range. Increment
242 8907c8dd 2002-06-26 alex * text pointer as we go here */
243 8907c8dd 2002-06-26 alex if( nextp == *t || nextp == '[' ) match = Matche( p, t );
245 8907c8dd 2002-06-26 alex /* if the end of text is reached then no match */
246 8907c8dd 2002-06-26 alex if( ! *t++ ) match = MATCH_ABORT;
247 8907c8dd 2002-06-26 alex } while( match != MATCH_VALID && match != MATCH_ABORT && match != MATCH_PATTERN );
249 8907c8dd 2002-06-26 alex /* return result */
250 8907c8dd 2002-06-26 alex return match;
251 8907c8dd 2002-06-26 alex } /* Matche_After_Star */
254 8907c8dd 2002-06-26 alex /* -eof- */