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 #include "defines.h"
  26 #include "tool.h"
  27
  28
  29 /*
  30  * Die Pattern-Matching-Funkionen [Matche(), Matche_After_Star()] basieren
  31  * auf Versionen von J. Kercheval. Die Version 1.1 wurde am 12.03.1991 als
  32  * "public domain" freigegeben:
  33  * <http://www.snippets.org/snippets/portable/MATCH+C.php3>
  34  */
  35
  36
  37 static int Matche PARAMS(( const char *p, const char *t ));
  38 static int Matche_After_Star PARAMS(( const char *p, const char *t ));
  39
  40
  41 #define MATCH_PATTERN   6       /* bad pattern */
  42 #define MATCH_LITERAL   5       /* match failure on literal match */
  43 #define MATCH_RANGE     4       /* match failure on [..] construct */
  44 #define MATCH_ABORT     3       /* premature end of text string */
  45 #define MATCH_END       2       /* premature end of pattern string */
  46 #define MATCH_VALID     1       /* valid match */
  47
  48
  49 GLOBAL bool
  50 Match( const char *Pattern, const char *String )
  51 {
  52         /* Pattern mit String vergleichen */
  53         if( Matche( Pattern, String ) == MATCH_VALID ) return true;
  54         else return false;
  55 } /* Match */
  56
  57
  58 GLOBAL bool
  59 MatchCaseInsensitive(const char *pattern, const char *searchme)
  60 {
  61         char haystack[COMMAND_LEN];
  62
  63         strlcpy(haystack, searchme, sizeof(haystack));
  64
  65         ngt_LowerStr(haystack);
  66
  67         return Match(pattern, haystack);
  68 } /* MatchCaseInsensitive */
  69
  70
  71 static int
  72 Matche( const char *p, const char *t )
  73 {
  74         register char range_start, range_end;
  75         bool invert;
  76         bool member_match;
  77         bool loop;
  78
  79         for( ; *p; p++, t++ )
  80         {
  81                 /* if this is the end of the text then this is the end of the match */
  82                 if( ! *t )
  83                 {
  84                         return ( *p == '*' && *++p == '\0' ) ? MATCH_VALID : MATCH_ABORT;
  85                 }
  86
  87                 /* determine and react to pattern type */
  88                 switch( *p )
  89                 {
  90                         case '?':       /* single any character match */
  91                                 break;
  92
  93                         case '*':       /* multiple any character match */
  94                                 return Matche_After_Star( p, t );
  95
  96                         case '[':       /* [..] construct, single member/exclusion character match */
  97                                 /* move to beginning of range */
  98                                 p++;
  99
 100                                 /* check if this is a member match or exclusion match */
 101                                 invert = false;
 102                                 if( *p == '!' || *p == '^' )
 103                                 {
 104                                         invert = true;
 105                                         p++;
 106                                 }
 107
 108                                 /* if closing bracket here or at range start then we have a malformed pattern */
 109                                 if ( *p == ']' ) return MATCH_PATTERN;
 110
 111                                 member_match = false;
 112                                 loop = true;
 113
 114                                 while( loop )
 115                                 {
 116                                         /* if end of construct then loop is done */
 117                                         if( *p == ']' )
 118                                         {
 119                                                 loop = false;
 120                                                 continue;
 121                                         }
 122
 123                                         /* matching a '!', '^', '-', '\' or a ']' */
 124                                         if( *p == '\\' ) range_start = range_end = *++p;
 125                                         else  range_start = range_end = *p;
 126
 127                                         /* if end of pattern then bad pattern (Missing ']') */
 128                                         if( ! *p ) return MATCH_PATTERN;
 129
 130                                         /* check for range bar */
 131                                         if( *++p == '-' )
 132                                         {
 133                                                 /* get the range end */
 134                                                 range_end = *++p;
 135
 136                                                 /* if end of pattern or construct then bad pattern */
 137                                                 if( range_end == '\0' || range_end == ']' ) return MATCH_PATTERN;
 138
 139                                                 /* special character range end */
 140                                                 if( range_end == '\\' )
 141                                                 {
 142                                                         range_end = *++p;
 143
 144                                                         /* if end of text then we have a bad pattern */
 145                                                         if ( ! range_end ) return MATCH_PATTERN;
 146                                                 }
 147
 148                                                 /* move just beyond this range */
 149                                                 p++;
 150                                         }
 151
 152                                         /* if the text character is in range then match found. make sure the range
 153                                          * letters have the proper relationship to one another before comparison */
 154                                         if( range_start < range_end )
 155                                         {
 156                                                 if( *t >= range_start && *t <= range_end )
 157                                                 {
 158                                                         member_match = true;
 159                                                         loop = false;
 160                                                 }
 161                                         }
 162                                         else
 163                                         {
 164                                                 if( *t >= range_end && *t <= range_start )
 165                                                 {
 166                                                         member_match = true;
 167                                                         loop = false;
 168                                                 }
 169                                         }
 170                                 }
 171
 172                                 /* if there was a match in an exclusion set then no match */
 173                                 /* if there was no match in a member set then no match */
 174                                 if(( invert && member_match ) || ! ( invert || member_match )) return MATCH_RANGE;
 175
 176                                 /* if this is not an exclusion then skip the rest of the [...]
 177                                  * construct that already matched. */
 178                                 if( member_match )
 179                                 {
 180                                         while( *p != ']' )
 181                                         {
 182                                                 /* bad pattern (Missing ']') */
 183                                                 if( ! *p ) return MATCH_PATTERN;
 184
 185                                                 /* skip exact match */
 186                                                 if( *p == '\\' )
 187                                                 {
 188                                                         p++;
 189
 190                                                         /* if end of text then we have a bad pattern */
 191                                                         if( ! *p ) return MATCH_PATTERN;
 192                                                 }
 193
 194                                                 /* move to next pattern char */
 195                                                 p++;
 196                                         }
 197                                 }
 198                                 break;
 199                         case '\\':      /* next character is quoted and must match exactly */
 200                                 /* move pattern pointer to quoted char and fall through */
 201                                 p++;
 202
 203                                 /* if end of text then we have a bad pattern */
 204                                 if( ! *p ) return MATCH_PATTERN;
 205
 206                                 /* must match this character exactly */
 207                         default:
 208                                 if( *p != *t ) return MATCH_LITERAL;
 209                 }
 210         }
 211         /* if end of text not reached then the pattern fails */
 212
 213         if( *t ) return MATCH_END;
 214         else return MATCH_VALID;
 215 } /* Matche */
 216
 217
 218 static int
 219 Matche_After_Star( const char *p, const char *t )
 220 {
 221         register int nextp, match = 0;
 222
 223         /* pass over existing ? and * in pattern */
 224         while( *p == '?' || *p == '*' )
 225         {
 226                 /* take one char for each ? and + */
 227                 if (*p == '?')
 228                 {
 229                         /* if end of text then no match */
 230                         if( ! *t++ ) return MATCH_ABORT;
 231                 }
 232
 233                 /* move to next char in pattern */
 234                 p++;
 235         }
 236
 237         /* if end of pattern we have matched regardless of text left */
 238         if( ! *p ) return MATCH_VALID;
 239
 240         /* get the next character to match which must be a literal or '[' */
 241         nextp = *p;
 242         if( nextp == '\\' )
 243         {
 244                 nextp = p[1];
 245
 246                 /* if end of text then we have a bad pattern */
 247                 if( ! nextp ) return MATCH_PATTERN;
 248         }
 249
 250         /* Continue until we run out of text or definite result seen */
 251         do
 252         {
 253                 /* a precondition for matching is that the next character
 254                  * in the pattern match the next character in the text or that
 255                  * the next pattern char is the beginning of a range.  Increment
 256                  * text pointer as we go here */
 257                 if( nextp == *t || nextp == '[' ) match = Matche( p, t );
 258
 259                 /* if the end of text is reached then no match */
 260                 if( ! *t++ ) match = MATCH_ABORT;
 261         } while( match != MATCH_VALID && match != MATCH_ABORT && match != MATCH_PATTERN );
 262
 263         /* return result */
 264         return match;
 265 } /* Matche_After_Star */
 266
 267
 268 /* -eof- */