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  * 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.5 2006/10/06 21:23:47 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 static int Matche PARAMS(( const char *p, const char *t ));
  36 static int Matche_After_Star PARAMS(( const char *p, const 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( const char *Pattern, const 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 static int
  57 Matche( const char *p, const 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 static int
 204 Matche_After_Star( const char *p, const 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- */