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         return Match(pattern, ngt_LowerStr(haystack));
  65 } /* MatchCaseInsensitive */
  66
  67
  68 static int
  69 Matche( const char *p, const char *t )
  70 {
  71         register char range_start, range_end;
  72         bool invert;
  73         bool member_match;
  74         bool loop;
  75
  76         for( ; *p; p++, t++ )
  77         {
  78                 /* if this is the end of the text then this is the end of the match */
  79                 if( ! *t )
  80                 {
  81                         return ( *p == '*' && *++p == '\0' ) ? MATCH_VALID : MATCH_ABORT;
  82                 }
  83
  84                 /* determine and react to pattern type */
  85                 switch( *p )
  86                 {
  87                         case '?':       /* single any character match */
  88                                 break;
  89
  90                         case '*':       /* multiple any character match */
  91                                 return Matche_After_Star( p, t );
  92
  93                         case '[':       /* [..] construct, single member/exclusion character match */
  94                                 /* move to beginning of range */
  95                                 p++;
  96
  97                                 /* check if this is a member match or exclusion match */
  98                                 invert = false;
  99                                 if( *p == '!' || *p == '^' )
 100                                 {
 101                                         invert = true;
 102                                         p++;
 103                                 }
 104
 105                                 /* if closing bracket here or at range start then we have a malformed pattern */
 106                                 if ( *p == ']' ) return MATCH_PATTERN;
 107
 108                                 member_match = false;
 109                                 loop = true;
 110
 111                                 while( loop )
 112                                 {
 113                                         /* if end of construct then loop is done */
 114                                         if( *p == ']' )
 115                                         {
 116                                                 loop = false;
 117                                                 continue;
 118                                         }
 119
 120                                         /* matching a '!', '^', '-', '\' or a ']' */
 121                                         if( *p == '\\' ) range_start = range_end = *++p;
 122                                         else  range_start = range_end = *p;
 123
 124                                         /* if end of pattern then bad pattern (Missing ']') */
 125                                         if( ! *p ) return MATCH_PATTERN;
 126
 127                                         /* check for range bar */
 128                                         if( *++p == '-' )
 129                                         {
 130                                                 /* get the range end */
 131                                                 range_end = *++p;
 132
 133                                                 /* if end of pattern or construct then bad pattern */
 134                                                 if( range_end == '\0' || range_end == ']' ) return MATCH_PATTERN;
 135
 136                                                 /* special character range end */
 137                                                 if( range_end == '\\' )
 138                                                 {
 139                                                         range_end = *++p;
 140
 141                                                         /* if end of text then we have a bad pattern */
 142                                                         if ( ! range_end ) return MATCH_PATTERN;
 143                                                 }
 144
 145                                                 /* move just beyond this range */
 146                                                 p++;
 147                                         }
 148
 149                                         /* if the text character is in range then match found. make sure the range
 150                                          * letters have the proper relationship to one another before comparison */
 151                                         if( range_start < range_end )
 152                                         {
 153                                                 if( *t >= range_start && *t <= range_end )
 154                                                 {
 155                                                         member_match = true;
 156                                                         loop = false;
 157                                                 }
 158                                         }
 159                                         else
 160                                         {
 161                                                 if( *t >= range_end && *t <= range_start )
 162                                                 {
 163                                                         member_match = true;
 164                                                         loop = false;
 165                                                 }
 166                                         }
 167                                 }
 168
 169                                 /* if there was a match in an exclusion set then no match */
 170                                 /* if there was no match in a member set then no match */
 171                                 if(( invert && member_match ) || ! ( invert || member_match )) return MATCH_RANGE;
 172
 173                                 /* if this is not an exclusion then skip the rest of the [...]
 174                                  * construct that already matched. */
 175                                 if( member_match )
 176                                 {
 177                                         while( *p != ']' )
 178                                         {
 179                                                 /* bad pattern (Missing ']') */
 180                                                 if( ! *p ) return MATCH_PATTERN;
 181
 182                                                 /* skip exact match */
 183                                                 if( *p == '\\' )
 184                                                 {
 185                                                         p++;
 186
 187                                                         /* if end of text then we have a bad pattern */
 188                                                         if( ! *p ) return MATCH_PATTERN;
 189                                                 }
 190
 191                                                 /* move to next pattern char */
 192                                                 p++;
 193                                         }
 194                                 }
 195                                 break;
 196                         case '\\':      /* next character is quoted and must match exactly */
 197                                 /* move pattern pointer to quoted char and fall through */
 198                                 p++;
 199
 200                                 /* if end of text then we have a bad pattern */
 201                                 if( ! *p ) return MATCH_PATTERN;
 202
 203                                 /* must match this character exactly */
 204                         default:
 205                                 if( *p != *t ) return MATCH_LITERAL;
 206                 }
 207         }
 208         /* if end of text not reached then the pattern fails */
 209
 210         if( *t ) return MATCH_END;
 211         else return MATCH_VALID;
 212 } /* Matche */
 213
 214
 215 static int
 216 Matche_After_Star( const char *p, const char *t )
 217 {
 218         register int nextp, match = 0;
 219
 220         /* pass over existing ? and * in pattern */
 221         while( *p == '?' || *p == '*' )
 222         {
 223                 /* take one char for each ? and + */
 224                 if (*p == '?')
 225                 {
 226                         /* if end of text then no match */
 227                         if( ! *t++ ) return MATCH_ABORT;
 228                 }
 229
 230                 /* move to next char in pattern */
 231                 p++;
 232         }
 233
 234         /* if end of pattern we have matched regardless of text left */
 235         if( ! *p ) return MATCH_VALID;
 236
 237         /* get the next character to match which must be a literal or '[' */
 238         nextp = *p;
 239         if( nextp == '\\' )
 240         {
 241                 nextp = p[1];
 242
 243                 /* if end of text then we have a bad pattern */
 244                 if( ! nextp ) return MATCH_PATTERN;
 245         }
 246
 247         /* Continue until we run out of text or definite result seen */
 248         do
 249         {
 250                 /* a precondition for matching is that the next character
 251                  * in the pattern match the next character in the text or that
 252                  * the next pattern char is the beginning of a range.  Increment
 253                  * text pointer as we go here */
 254                 if( nextp == *t || nextp == '[' ) match = Matche( p, t );
 255
 256                 /* if the end of text is reached then no match */
 257                 if( ! *t++ ) match = MATCH_ABORT;
 258         } while( match != MATCH_VALID && match != MATCH_ABORT && match != MATCH_PATTERN );
 259
 260         /* return result */
 261         return match;
 262 } /* Matche_After_Star */
 263
 264
 265 /* -eof- */