match.c 7.6 KB

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