src/nntp/uwildmat.cpp

   1 /*  $Id: uwildmat.c 6779 2004-05-17 07:25:28Z rra $\r
   2 **\r
   3 **  wildmat pattern matching with Unicode UTF-8 extensions.\r
   4 **\r
   5 **  Do shell-style pattern matching for ?, \, [], and * characters.  Might not\r
   6 **  be robust in face of malformed patterns; e.g., "foo[a-" could cause a\r
   7 **  segmentation violation.  It is 8-bit clean.  (Robustness hopefully fixed\r
   8 **  July 2000; all malformed patterns should now just fail to match anything.)\r
   9 **\r
  10 **  Original by Rich $alz, mirror!rs, Wed Nov 26 19:03:17 EST 1986.\r
  11 **  Rich $alz is now <rsalz@osf.org>.\r
  12 **\r
  13 **  April, 1991:  Replaced mutually-recursive calls with in-line code for the\r
  14 **  star character.\r
  15 **\r
  16 **  Special thanks to Lars Mathiesen <thorinn@diku.dk> for the ABORT code.\r
  17 **  This can greatly speed up failing wildcard patterns.  For example:\r
  18 **\r
  19 **      pattern: -*-*-*-*-*-*-12-*-*-*-m-*-*-*\r
  20 **      text 1:  -adobe-courier-bold-o-normal--12-120-75-75-m-70-iso8859-1\r
  21 **      text 2:  -adobe-courier-bold-o-normal--12-120-75-75-X-70-iso8859-1\r
  22 **\r
  23 **  Text 1 matches with 51 calls, while text 2 fails with 54 calls.  Without\r
  24 **  the ABORT code, it takes 22310 calls to fail.  Ugh.  The following\r
  25 **  explanation is from Lars:\r
  26 **\r
  27 **  The precondition that must be fulfilled is that DoMatch will consume at\r
  28 **  least one character in text.  This is true if *p is neither '*' nor '\0'.)\r
  29 **  The last return has ABORT instead of false to avoid quadratic behaviour in\r
  30 **  cases like pattern "*a*b*c*d" with text "abcxxxxx".  With false, each\r
  31 **  star-loop has to run to the end of the text; with ABORT only the last one\r
  32 **  does.\r
  33 **\r
  34 **  Once the control of one instance of DoMatch enters the star-loop, that\r
  35 **  instance will return either true or ABORT, and any calling instance will\r
  36 **  therefore return immediately after (without calling recursively again).\r
  37 **  In effect, only one star-loop is ever active.  It would be possible to\r
  38 **  modify the code to maintain this context explicitly, eliminating all\r
  39 **  recursive calls at the cost of some complication and loss of clarity (and\r
  40 **  the ABORT stuff seems to be unclear enough by itself).  I think it would\r
  41 **  be unwise to try to get this into a released version unless you have a\r
  42 **  good test data base to try it out on.\r
  43 **\r
  44 **  June, 1991:  Robert Elz <kre@munnari.oz.au> added minus and close bracket\r
  45 **  handling for character sets.\r
  46 **\r
  47 **  July, 2000:  Largely rewritten by Russ Allbery <rra@stanford.edu> to add\r
  48 **  support for ',', '!', and optionally '@' to the core wildmat routine.\r
  49 **  Broke the character class matching into a separate function for clarity\r
  50 **  since it's infrequently used in practice, and added some simple lookahead\r
  51 **  to significantly decrease the recursive calls in the '*' matching code.\r
  52 **  Added support for UTF-8 as the default character set for any high-bit\r
  53 **  characters.\r
  54 **\r
  55 **  For more information on UTF-8, see RFC 2279.\r
  56 **\r
  57 **  Please note that this file is intentionally written so that conditionally\r
  58 **  executed expressions are on separate lines from the condition to\r
  59 **  facilitate analysis of the coverage of the test suite using purecov.\r
  60 **  Please preserve this.  As of March 11, 2001, purecov reports that the\r
  61 **  accompanying test suite achieves 100% coverage of this file.\r
  62 */\r
  63 \r
  64 //#include "config.h"\r
  65 //#include "clibrary.h"\r
  66 //#include "libinn.h"\r
  67 #include "../../include/nntp/uwildmat.h"\r
  68 #include <string>\r
  69 #include <cstring>\r
  70 \r
  71 #define ABORT -1\r
  72 \r
  73 /* Whether or not an octet looks like the start of a UTF-8 character. */\r
  74 #define ISUTF8(c)       (((c) & 0xc0) == 0xc0)\r
  75 \r
  76 \r
  77 /*\r
  78 **  Determine the length of a non-ASCII character in octets (for advancing\r
  79 **  pointers when skipping over characters).  Takes a pointer to the start of\r
  80 **  the character and to the last octet of the string.  If end is NULL, expect\r
  81 **  the string pointed to by start to be nul-terminated.  If the character is\r
  82 **  malformed UTF-8, return 1 to treat it like an eight-bit local character.\r
  83 */\r
  84 static int\r
  85 utf8_length(const unsigned char *start, const unsigned char *end)\r
  86 {\r
  87     unsigned char mask = 0x80;\r
  88     const unsigned char *p;\r
  89     int length = 0;\r
  90     int left;\r
  91 \r
  92     for (; mask > 0 && (*start & mask) == mask; mask >>= 1)\r
  93         length++;\r
  94     if (length < 2 || length > 6)\r
  95         return 1;\r
  96     if (end != NULL && (end - start + 1) < length)\r
  97         return 1;\r
  98     left = length - 1;\r
  99     p = start + 1;\r
 100     for (p = start + 1; left > 0 && (*p & 0xc0) == 0x80; p++)\r
 101         left--;\r
 102     return (left == 0) ? length : 1;\r
 103 }\r
 104 \r
 105 \r
 106 /*\r
 107 **  Convert a UTF-8 character to UCS-4.  Takes a pointer to the start of the\r
 108 **  character and to the last octet of the string, and to a uint32_t into\r
 109 **  which to put the decoded UCS-4 value.  If end is NULL, expect the string\r
 110 **  pointed to by start to be nul-terminated.  Returns the number of octets in\r
 111 **  the UTF-8 encoding.  If the UTF-8 character is malformed, set result to\r
 112 **  the decimal value of the first octet; this is wrong, but it will generally\r
 113 **  cause the rest of the wildmat matching to do the right thing for non-UTF-8\r
 114 **  input.\r
 115 */\r
 116 static int\r
 117 utf8_decode(const unsigned char *start, const unsigned char *end,\r
 118             uint32_t *result)\r
 119 {\r
 120     uint32_t value = 0;\r
 121     int length, i;\r
 122     const unsigned char *p = start;\r
 123     unsigned char mask;\r
 124 \r
 125     length = utf8_length(start, end);\r
 126     if (length < 2) {\r
 127         *result = *start;\r
 128         return 1;\r
 129     }\r
 130     mask = (1 << (7 - length)) - 1;\r
 131     value = *p & mask;\r
 132     p++;\r
 133     for (i = length - 1; i > 0; i--) {\r
 134         value = (value << 6) | (*p & 0x3f);\r
 135         p++;\r
 136     }\r
 137     *result = value;\r
 138     return length;\r
 139 }\r
 140 \r
 141 \r
 142 /*\r
 143 **  Match a character class against text, a UCS-4 character.  start is a\r
 144 **  pointer to the first character of the character class, end a pointer to\r
 145 **  the last.  Returns whether the class matches that character.\r
 146 */\r
 147 static bool\r
 148 match_class(uint32_t text, const unsigned char *start,\r
 149             const unsigned char *end)\r
 150 {\r
 151     bool reversed, allowrange;\r
 152     const unsigned char *p = start;\r
 153     uint32_t first, last;\r
 154 \r
 155     /* Check for an inverted character class (starting with ^).  If the\r
 156        character matches the character class, we return !reversed; that way,\r
 157        we return true if it's a regular character class and false if it's a\r
 158        reversed one.  If the character doesn't match, we return reversed. */\r
 159     reversed = (*p == '^');\r
 160     if (reversed)\r
 161         p++;\r
 162 \r
 163     /* Walk through the character class until we reach the end or find a\r
 164        match, handling character ranges as we go.  Only permit a range to\r
 165        start when allowrange is true; this allows - to be treated like a\r
 166        normal character as the first character of the class and catches\r
 167        malformed ranges like a-e-n.  We treat the character at the beginning\r
 168        of a range as both a regular member of the class and the beginning of\r
 169        the range; this is harmless (although it means that malformed ranges\r
 170        like m-a will match m and nothing else). */\r
 171     allowrange = false;\r
 172     while (p <= end) {\r
 173         if (allowrange && *p == '-' && p < end) {\r
 174             p++;\r
 175             p += utf8_decode(p, end, &last);\r
 176             if (text >= first && text <= last)\r
 177                 return !reversed;\r
 178             allowrange = false;\r
 179         } else {\r
 180             p += utf8_decode(p, end, &first);\r
 181             if (text == first)\r
 182                 return !reversed;\r
 183             allowrange = true;\r
 184         }\r
 185     }\r
 186     return reversed;\r
 187 }\r
 188 \r
 189 \r
 190 /*\r
 191 **  Match the text against the pattern between start and end.  This is a\r
 192 **  single pattern; a leading ! or @ must already be taken care of, and\r
 193 **  commas must be dealt with outside of this routine.\r
 194 */\r
 195 static int\r
 196 match_pattern(const unsigned char *text, const unsigned char *start,\r
 197               const unsigned char *end)\r
 198 {\r
 199     const unsigned char *q, *endclass;\r
 200     const unsigned char *p = start;\r
 201     bool ismeta;\r
 202     int matched, width;\r
 203     uint32_t c;\r
 204 \r
 205     for (; p <= end; p++) {\r
 206         if (!*text && *p != '*')\r
 207             return ABORT;\r
 208 \r
 209         switch (*p) {\r
 210         case '\\':\r
 211             if (!*++p)\r
 212                 return ABORT;\r
 213             /* Fall through. */\r
 214 \r
 215         default:\r
 216             if (*text++ != *p)\r
 217                 return false;\r
 218             break;\r
 219 \r
 220         case '?':\r
 221             text += ISUTF8(*text) ? utf8_length(text, NULL) : 1;\r
 222             break;\r
 223 \r
 224         case '*':\r
 225             /* Consecutive stars are equivalent to one.  Advance pattern to\r
 226                the character after the star. */\r
 227             for (++p; *p == '*'; p++)\r
 228                 ;\r
 229 \r
 230             /* A trailing star will match anything. */\r
 231             if (p > end)\r
 232                 return true;\r
 233 \r
 234             /* Basic algorithm: Recurse at each point where the * could\r
 235                possibly match.  If the match succeeds or aborts, return\r
 236                immediately; otherwise, try the next position.\r
 237 \r
 238                Optimization: If the character after the * in the pattern\r
 239                isn't a metacharacter (the common case), then the * has to\r
 240                consume characters at least up to the next occurance of that\r
 241                character in the text.  Scan forward for those points rather\r
 242                than recursing at every possible point to save the extra\r
 243                function call overhead. */\r
 244             ismeta = (*p == '[' || *p == '?' || *p == '\\');\r
 245             while (*text) {\r
 246                 width = ISUTF8(*text) ? utf8_length(text, NULL) : 1;\r
 247                 if (ismeta) {\r
 248                     matched = match_pattern(text, p, end);\r
 249                     text += width;\r
 250                 } else {\r
 251                     while (*text && *text != *p) {\r
 252                         text += width;\r
 253                         width = ISUTF8(*text) ? utf8_length(text, NULL) : 1;\r
 254                     }\r
 255                     if (!*text)\r
 256                         return ABORT;\r
 257                     matched = match_pattern(++text, p + 1, end);\r
 258                 }\r
 259                 if (matched != false)\r
 260                     return matched;\r
 261             }\r
 262             return ABORT;\r
 263 \r
 264         case '[':\r
 265             /* Find the end of the character class, making sure not to pick\r
 266                up a close bracket at the beginning of the class. */\r
 267             p++;\r
 268             q = p + (*p == '^') + 1;\r
 269             if (q > end)\r
 270                 return ABORT;\r
 271             endclass = (unsigned char *)memchr(q, ']', (size_t) (end - q + 1));\r
 272             if (!endclass)\r
 273                 return ABORT;\r
 274 \r
 275             /* Do the heavy lifting in another function for clarity, since\r
 276                character classes are an uncommon case. */\r
 277             text += utf8_decode(text, NULL, &c);\r
 278             if (!match_class(c, p, endclass - 1))\r
 279                 return false;\r
 280             p = endclass;\r
 281             break;\r
 282         }\r
 283     }\r
 284 \r
 285     return (*text == '\0');\r
 286 }\r
 287 \r
 288 \r
 289 /*\r
 290 **  Takes text and a wildmat expression; a wildmat expression is a\r
 291 **  comma-separated list of wildmat patterns, optionally preceeded by ! to\r
 292 **  invert the sense of the expression.  Returns WILDMAT_MATCH if that\r
 293 **  expression matches the text, WILDMAT_FAIL otherwise.  If allowpoison is\r
 294 **  set, allow @ to introduce a poison expression (the same as !, but if it\r
 295 **  triggers the failed match the routine returns WILDMAT_POISON instead).\r
 296 */\r
 297 static enum uwildmat\r
 298 match_expression(const unsigned char *text, const unsigned char *start,\r
 299                  bool allowpoison)\r
 300 {\r
 301     const unsigned char *end, *split;\r
 302     const unsigned char *p = start;\r
 303     bool reverse, escaped;\r
 304     bool match = false;\r
 305     bool poison = false;\r
 306     bool poisoned = false;\r
 307 \r
 308     /* Handle the empty expression separately, since otherwise end will be\r
 309        set to an invalid pointer. */\r
 310     if (!*p)\r
 311         return !*text ? UWILDMAT_MATCH : UWILDMAT_FAIL;\r
 312     end = start + strlen((const char *) start) - 1;\r
 313 \r
 314     /* Main match loop.  Find each comma that separates patterns, and attempt \r
 315        to match the text with each pattern in order.  The last matching\r
 316        pattern determines whether the whole expression matches. */\r
 317     for (; p <= end + 1; p = split + 1) {\r
 318         if (allowpoison)\r
 319             poison = (*p == '@');\r
 320         reverse = (*p == '!') || poison;\r
 321         if (reverse)\r
 322             p++;\r
 323 \r
 324         /* Find the first unescaped comma, if any.  If there is none, split\r
 325            will be one greater than end and point at the nul at the end of\r
 326            the string. */\r
 327         for (escaped = false, split = p; split <= end; split++) {\r
 328             if (*split == '[') {\r
 329                 split++;\r
 330                 if (*split == ']')\r
 331                     split++;\r
 332                 while (split <= end && *split != ']')\r
 333                     split++;\r
 334             }\r
 335             if (*split == ',' && !escaped)\r
 336                 break;\r
 337             escaped = (*split == '\\') ? !escaped : false;\r
 338         }\r
 339 \r
 340         /* Optimization: If match == !reverse and poison == poisoned, this\r
 341            pattern can't change the result, so don't do any work. */\r
 342         if (match == !reverse && poison == poisoned)\r
 343             continue;\r
 344         if (match_pattern(text, p, split - 1) == true) {\r
 345             poisoned = poison;\r
 346             match = !reverse;\r
 347         }\r
 348     }\r
 349     if (poisoned)\r
 350         return UWILDMAT_POISON;\r
 351     return match ? UWILDMAT_MATCH : UWILDMAT_FAIL;\r
 352 }\r
 353 \r
 354 \r
 355 /*\r
 356 **  User-level routine used for wildmats where @ should be treated as a\r
 357 **  regular character.\r
 358 */\r
 359 bool\r
 360 uwildmat(const char *text, const char *pat)\r
 361 {\r
 362     const unsigned char *utext = (const unsigned char *) text;\r
 363     const unsigned char *upat = (const unsigned char *) pat;\r
 364 \r
 365     if (upat[0] == '*' && upat[1] == '\0')\r
 366         return true;\r
 367     else\r
 368         return (match_expression(utext, upat, false) == UWILDMAT_MATCH);\r
 369 }\r
 370 \r
 371 \r
 372 /*\r
 373 **  User-level routine used for wildmats that support poison matches.\r
 374 */\r
 375 enum uwildmat\r
 376 uwildmat_poison(const char *text, const char *pat)\r
 377 {\r
 378     const unsigned char *utext = (const unsigned char *) text;\r
 379     const unsigned char *upat = (const unsigned char *) pat;\r
 380 \r
 381     if (upat[0] == '*' && upat[1] == '\0')\r
 382         return UWILDMAT_MATCH;\r
 383     else\r
 384         return match_expression(utext, upat, true);\r
 385 }\r
 386 \r
 387 \r
 388 /*\r
 389 **  User-level routine for simple expressions (neither , nor ! are special).\r
 390 */\r
 391 bool\r
 392 uwildmat_simple(const char *text, const char *pat)\r
 393 {\r
 394     const unsigned char *utext = (const unsigned char *) text;\r
 395     const unsigned char *upat = (const unsigned char *) pat;\r
 396     size_t length;\r
 397 \r
 398     if (upat[0] == '*' && upat[1] == '\0')\r
 399         return true;\r
 400     else {\r
 401         length = strlen(pat);\r
 402         return (match_pattern(utext, upat, upat + length - 1) == true);\r
 403     }\r
 404 }\r