citadel/modules/nntp/wildmat.c

   1 /* wildmat.h - NNTP wildmat processing functions
   2  *
   3  * Copyright (c) 1994-2008 Carnegie Mellon University.  All rights reserved.
   4  *
   5  * Redistribution and use in source and binary forms, with or without
   6  * modification, are permitted provided that the following conditions
   7  * are met:
   8  *
   9  * 1. Redistributions of source code must retain the above copyright
  10  *    notice, this list of conditions and the following disclaimer.
  11  *
  12  * 2. Redistributions in binary form must reproduce the above copyright
  13  *    notice, this list of conditions and the following disclaimer in
  14  *    the documentation and/or other materials provided with the
  15  *    distribution.
  16  *
  17  * 3. The name "Carnegie Mellon University" must not be used to
  18  *    endorse or promote products derived from this software without
  19  *    prior written permission. For permission or any legal
  20  *    details, please contact
  21  *      Carnegie Mellon University
  22  *      Center for Technology Transfer and Enterprise Creation
  23  *      4615 Forbes Avenue
  24  *      Suite 302
  25  *      Pittsburgh, PA  15213
  26  *      (412) 268-7393, fax: (412) 268-7395
  27  *      innovation@andrew.cmu.edu
  28  *
  29  * 4. Redistributions of any form whatsoever must retain the following
  30  *    acknowledgment:
  31  *    "This product includes software developed by Computing Services
  32  *     at Carnegie Mellon University (http://www.cmu.edu/computing/)."
  33  *
  34  * CARNEGIE MELLON UNIVERSITY DISCLAIMS ALL WARRANTIES WITH REGARD TO
  35  * THIS SOFTWARE, INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY
  36  * AND FITNESS, IN NO EVENT SHALL CARNEGIE MELLON UNIVERSITY BE LIABLE
  37  * FOR ANY SPECIAL, INDIRECT OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
  38  * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN
  39  * AN ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING
  40  * OUT OF OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
  41  *
  42  * $Id: wildmat.c,v 1.4 2010/01/06 17:01:47 murch Exp $
  43  */
  44
  45 /*
  46 **
  47 **  Do shell-style pattern matching for ?, \, [], and * characters.
  48 **  Might not be robust in face of malformed patterns; e.g., "foo[a-"
  49 **  could cause a segmentation violation.  It is 8bit clean.
  50 **
  51 **  Written by Rich $alz, mirror!rs, Wed Nov 26 19:03:17 EST 1986.
  52 **  Rich $alz is now <rsalz@osf.org>.
  53 **  April, 1991:  Replaced mutually-recursive calls with in-line code
  54 **  for the star character.
  55 **
  56 **  Special thanks to Lars Mathiesen <thorinn@diku.dk> for the ABORT code.
  57 **  This can greatly speed up failing wildcard patterns.  For example:
  58 **      pattern: -*-*-*-*-*-*-12-*-*-*-m-*-*-*
  59 **      text 1:  -adobe-courier-bold-o-normal--12-120-75-75-m-70-iso8859-1
  60 **      text 2:  -adobe-courier-bold-o-normal--12-120-75-75-X-70-iso8859-1
  61 **  Text 1 matches with 51 calls, while text 2 fails with 54 calls.  Without
  62 **  the ABORT code, it takes 22310 calls to fail.  Ugh.  The following
  63 **  explanation is from Lars:
  64 **  The precondition that must be fulfilled is that DoMatch will consume
  65 **  at least one character in text.  This is true if *p is neither '*' nor
  66 **  '\0'.)  The last return has ABORT instead of FALSE to avoid quadratic
  67 **  behaviour in cases like pattern "*a*b*c*d" with text "abcxxxxx".  With
  68 **  FALSE, each star-loop has to run to the end of the text; with ABORT
  69 **  only the last one does.
  70 **
  71 **  Once the control of one instance of DoMatch enters the star-loop, that
  72 **  instance will return either TRUE or ABORT, and any calling instance
  73 **  will therefore return immediately after (without calling recursively
  74 **  again).  In effect, only one star-loop is ever active.  It would be
  75 **  possible to modify the code to maintain this context explicitly,
  76 **  eliminating all recursive calls at the cost of some complication and
  77 **  loss of clarity (and the ABORT stuff seems to be unclear enough by
  78 **  itself).  I think it would be unwise to try to get this into a
  79 **  released version unless you have a good test data base to try it out
  80 **  on.
  81 */
  82 #include <stdio.h>
  83 #include <sys/types.h>
  84
  85
  86
  87 #define TRUE                    1
  88 #define FALSE                   0
  89 #define ABORT                   -1
  90
  91
  92     /* What character marks an inverted character class? */
  93 #define NEGATE_CLASS            '^'
  94     /* Is "*" a common pattern? */
  95 #define OPTIMIZE_JUST_STAR
  96     /* Do tar(1) matching rules, which ignore a trailing slash? */
  97 #undef MATCH_TAR_PATTERN
  98
  99
 100 /*
 101 **  Match text and p, return TRUE, FALSE, or ABORT.
 102 */
 103 static int DoMatch(const char *text, const char *p)
 104 {
 105     int                 last;
 106     int                 matched;
 107     int                 reverse;
 108
 109     for ( ; *p; text++, p++) {
 110         if (*text == '\0' && *p != '*')
 111             return ABORT;
 112         switch (*p) {
 113         case '\\':
 114             /* Literal match with following character. */
 115             p++;
 116             /* FALLTHROUGH */
 117         default:
 118             if (*text != *p)
 119                 return FALSE;
 120             continue;
 121         case '?':
 122             /* Match anything. */
 123             continue;
 124         case '*':
 125             while (*++p == '*')
 126                 /* Consecutive stars act just like one. */
 127                 continue;
 128             if (*p == '\0')
 129                 /* Trailing star matches everything. */
 130                 return TRUE;
 131             while (*text)
 132                 if ((matched = DoMatch(text++, p)) != FALSE)
 133                     return matched;
 134             return ABORT;
 135         case '[':
 136             reverse = p[1] == NEGATE_CLASS ? TRUE : FALSE;
 137             if (reverse)
 138                 /* Inverted character class. */
 139                 p++;
 140             matched = FALSE;
 141             if (p[1] == ']' || p[1] == '-')
 142                 if (*++p == *text)
 143                     matched = TRUE;
 144             for (last = *p; *++p && *p != ']'; last = *p)
 145                 /* This next line requires a good C compiler. */
 146                 if (*p == '-' && p[1] != ']'
 147                     ? *text <= *++p && *text >= last : *text == *p)
 148                     matched = TRUE;
 149             if (matched == reverse)
 150                 return FALSE;
 151             continue;
 152         }
 153     }
 154
 155 #ifdef  MATCH_TAR_PATTERN
 156     if (*text == '/')
 157         return TRUE;
 158 #endif  /* MATCH_TAR_ATTERN */
 159     return *text == '\0';
 160 }
 161
 162
 163 /*
 164 **  User-level routine.  Returns TRUE or FALSE.
 165 */
 166 int wildmat(const char *text, const char *p)
 167 {
 168 #ifdef  OPTIMIZE_JUST_STAR
 169     if (p[0] == '*' && p[1] == '\0')
 170         return TRUE;
 171 #endif  /* OPTIMIZE_JUST_STAR */
 172     return DoMatch(text, p) == TRUE;
 173 }