src/ngircd/match.c

   1 /*
   2  * ngIRCd -- The Next Generation IRC Daemon
   3  * Copyright (c)2001-2012 Alexander Barton (alex@barton.de) and Contributors.
   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 #include "portab.h"
  13
  14 /**
  15  * @file
  16  * Wildcard pattern matching
  17  */
  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  * The pattern matching functions [Matche(), Matche_After_Star()] are based
  31  * on code of J. Kercheval. Version 1.1 has been released on 1991-03-12 as
  32  * "public domain": <http://c.snippets.org/snip_lister.php?fname=match.c>
  33  */
  34
  35
  36 static int Matche PARAMS(( const char *p, const char *t ));
  37 static int Matche_After_Star PARAMS(( const char *p, const 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 /**
  49  * Match string with pattern.
  50  *
  51  * @param Pattern Pattern to match with
  52  * @param String Input string
  53  * @return true if pattern matches
  54  */
  55 GLOBAL bool
  56 Match( const char *Pattern, const char *String )
  57 {
  58         /* Pattern mit String vergleichen */
  59         if( Matche( Pattern, String ) == MATCH_VALID ) return true;
  60         else return false;
  61 } /* Match */
  62
  63
  64 /**
  65  * Match string with pattern case-insensitive.
  66  *
  67  * @param Pattern Pattern to match with
  68  * @param String Input string, at most COMMAND_LEN-1 characters long
  69  * @return true if pattern matches
  70  */
  71 GLOBAL bool
  72 MatchCaseInsensitive(const char *Pattern, const char *String)
  73 {
  74         char haystack[COMMAND_LEN];
  75
  76         strlcpy(haystack, String, sizeof(haystack));
  77         return Match(Pattern, ngt_LowerStr(haystack));
  78 } /* MatchCaseInsensitive */
  79
  80
  81 /**
  82  * Match string with pattern case-insensitive.
  83  *
  84  * @param pattern Pattern to match with
  85  * @param String Input string, at most COMMAND_LEN-1 characters long
  86  * @param Separator Character separating the individual patterns in the list
  87  * @return true if pattern matches
  88  */
  89 GLOBAL bool
  90 MatchCaseInsensitiveList(const char *Pattern, const char *String,
  91                      const char *Separator)
  92 {
  93         char tmp_pattern[COMMAND_LEN], haystack[COMMAND_LEN], *ptr;
  94
  95         strlcpy(tmp_pattern, Pattern, sizeof(tmp_pattern));
  96         strlcpy(haystack, String, sizeof(haystack));
  97         ngt_LowerStr(haystack);
  98
  99         ptr = strtok(tmp_pattern, Separator);
 100         while (ptr) {
 101                 ngt_TrimStr(ptr);
 102                 if (Match(ptr, haystack))
 103                         return true;
 104                 ptr = strtok(NULL, Separator);
 105         }
 106         return false;
 107 } /* MatchCaseInsensitive */
 108
 109
 110 static int
 111 Matche( const char *p, const char *t )
 112 {
 113         register char range_start, range_end;
 114         bool invert;
 115         bool member_match;
 116         bool loop;
 117
 118         for( ; *p; p++, t++ )
 119         {
 120                 /* if this is the end of the text then this is the end of the match */
 121                 if( ! *t )
 122                 {
 123                         return ( *p == '*' && *++p == '\0' ) ? MATCH_VALID : MATCH_ABORT;
 124                 }
 125
 126                 /* determine and react to pattern type */
 127                 switch( *p )
 128                 {
 129                         case '?':       /* single any character match */
 130                                 break;
 131
 132                         case '*':       /* multiple any character match */
 133                                 return Matche_After_Star( p, t );
 134
 135                         case '[':       /* [..] construct, single member/exclusion character match */
 136                                 /* move to beginning of range */
 137                                 p++;
 138
 139                                 /* check if this is a member match or exclusion match */
 140                                 invert = false;
 141                                 if( *p == '!' || *p == '^' )
 142                                 {
 143                                         invert = true;
 144                                         p++;
 145                                 }
 146
 147                                 /* if closing bracket here or at range start then we have a malformed pattern */
 148                                 if ( *p == ']' ) return MATCH_PATTERN;
 149
 150                                 member_match = false;
 151                                 loop = true;
 152
 153                                 while( loop )
 154                                 {
 155                                         /* if end of construct then loop is done */
 156                                         if( *p == ']' )
 157                                         {
 158                                                 loop = false;
 159                                                 continue;
 160                                         }
 161
 162                                         /* matching a '!', '^', '-', '\' or a ']' */
 163                                         if( *p == '\\' ) range_start = range_end = *++p;
 164                                         else  range_start = range_end = *p;
 165
 166                                         /* if end of pattern then bad pattern (Missing ']') */
 167                                         if( ! *p ) return MATCH_PATTERN;
 168
 169                                         /* check for range bar */
 170                                         if( *++p == '-' )
 171                                         {
 172                                                 /* get the range end */
 173                                                 range_end = *++p;
 174
 175                                                 /* if end of pattern or construct then bad pattern */
 176                                                 if( range_end == '\0' || range_end == ']' ) return MATCH_PATTERN;
 177
 178                                                 /* special character range end */
 179                                                 if( range_end == '\\' )
 180                                                 {
 181                                                         range_end = *++p;
 182
 183                                                         /* if end of text then we have a bad pattern */
 184                                                         if ( ! range_end ) return MATCH_PATTERN;
 185                                                 }
 186
 187                                                 /* move just beyond this range */
 188                                                 p++;
 189                                         }
 190
 191                                         /* if the text character is in range then match found. make sure the range
 192                                          * letters have the proper relationship to one another before comparison */
 193                                         if( range_start < range_end )
 194                                         {
 195                                                 if( *t >= range_start && *t <= range_end )
 196                                                 {
 197                                                         member_match = true;
 198                                                         loop = false;
 199                                                 }
 200                                         }
 201                                         else
 202                                         {
 203                                                 if( *t >= range_end && *t <= range_start )
 204                                                 {
 205                                                         member_match = true;
 206                                                         loop = false;
 207                                                 }
 208                                         }
 209                                 }
 210
 211                                 /* if there was a match in an exclusion set then no match */
 212                                 /* if there was no match in a member set then no match */
 213                                 if(( invert && member_match ) || ! ( invert || member_match )) return MATCH_RANGE;
 214
 215                                 /* if this is not an exclusion then skip the rest of the [...]
 216                                  * construct that already matched. */
 217                                 if( member_match )
 218                                 {
 219                                         while( *p != ']' )
 220                                         {
 221                                                 /* bad pattern (Missing ']') */
 222                                                 if( ! *p ) return MATCH_PATTERN;
 223
 224                                                 /* skip exact match */
 225                                                 if( *p == '\\' )
 226                                                 {
 227                                                         p++;
 228
 229                                                         /* if end of text then we have a bad pattern */
 230                                                         if( ! *p ) return MATCH_PATTERN;
 231                                                 }
 232
 233                                                 /* move to next pattern char */
 234                                                 p++;
 235                                         }
 236                                 }
 237                                 break;
 238                         case '\\':      /* next character is quoted and must match exactly */
 239                                 /* move pattern pointer to quoted char and fall through */
 240                                 p++;
 241
 242                                 /* if end of text then we have a bad pattern */
 243                                 if( ! *p ) return MATCH_PATTERN;
 244
 245                                 /* must match this character exactly */
 246                         default:
 247                                 if( *p != *t ) return MATCH_LITERAL;
 248                 }
 249         }
 250         /* if end of text not reached then the pattern fails */
 251
 252         if( *t ) return MATCH_END;
 253         else return MATCH_VALID;
 254 } /* Matche */
 255
 256
 257 static int
 258 Matche_After_Star( const char *p, const char *t )
 259 {
 260         register int nextp, match = 0;
 261
 262         /* pass over existing ? and * in pattern */
 263         while( *p == '?' || *p == '*' )
 264         {
 265                 /* take one char for each ? and + */
 266                 if (*p == '?')
 267                 {
 268                         /* if end of text then no match */
 269                         if( ! *t++ ) return MATCH_ABORT;
 270                 }
 271
 272                 /* move to next char in pattern */
 273                 p++;
 274         }
 275
 276         /* if end of pattern we have matched regardless of text left */
 277         if( ! *p ) return MATCH_VALID;
 278
 279         /* get the next character to match which must be a literal or '[' */
 280         nextp = *p;
 281         if( nextp == '\\' )
 282         {
 283                 nextp = p[1];
 284
 285                 /* if end of text then we have a bad pattern */
 286                 if( ! nextp ) return MATCH_PATTERN;
 287         }
 288
 289         /* Continue until we run out of text or definite result seen */
 290         do
 291         {
 292                 /* a precondition for matching is that the next character
 293                  * in the pattern match the next character in the text or that
 294                  * the next pattern char is the beginning of a range.  Increment
 295                  * text pointer as we go here */
 296                 if( nextp == *t || nextp == '[' ) match = Matche( p, t );
 297
 298                 /* if the end of text is reached then no match */
 299                 if( ! *t++ ) match = MATCH_ABORT;
 300         } while( match != MATCH_VALID && match != MATCH_ABORT && match != MATCH_PATTERN );
 301
 302         /* return result */
 303         return match;
 304 } /* Matche_After_Star */
 305
 306
 307 /* -eof- */