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