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