src/ngircd/match.c

   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- */