support/nfs/wildmat.c

   1 /*  $Revision: 0.2.18.1 $
   2 **
   3 **  Do shell-style pattern matching for ?, \, [], and * characters.
   4 **  Might not be robust in face of malformed patterns; e.g., "foo[a-"
   5 **  could cause a segmentation violation.  It is 8bit clean.
   6 **
   7 **  Written by Rich $alz, mirror!rs, Wed Nov 26 19:03:17 EST 1986.
   8 **  Rich $alz is now <rsalz@osf.org>.
   9 **  April, 1991:  Replaced mutually-recursive calls with in-line code
  10 **  for the star character.
  11 **
  12 **  Special thanks to Lars Mathiesen <thorinn@diku.dk> for the ABORT code.
  13 **  This can greatly speed up failing wildcard patterns.  For example:
  14 **      pattern: -*-*-*-*-*-*-12-*-*-*-m-*-*-*
  15 **      text 1:  -adobe-courier-bold-o-normal--12-120-75-75-m-70-iso8859-1
  16 **      text 2:  -adobe-courier-bold-o-normal--12-120-75-75-X-70-iso8859-1
  17 **  Text 1 matches with 51 calls, while text 2 fails with 54 calls.  Without
  18 **  the ABORT code, it takes 22310 calls to fail.  Ugh.  The following
  19 **  explanation is from Lars:
  20 **  The precondition that must be fulfilled is that DoMatch will consume
  21 **  at least one character in text.  This is true if *p is neither '*' nor
  22 **  '\0'.)  The last return has ABORT instead of FALSE to avoid quadratic
  23 **  behaviour in cases like pattern "*a*b*c*d" with text "abcxxxxx".  With
  24 **  FALSE, each star-loop has to run to the end of the text; with ABORT
  25 **  only the last one does.
  26 **
  27 **  Once the control of one instance of DoMatch enters the star-loop, that
  28 **  instance will return either TRUE or ABORT, and any calling instance
  29 **  will therefore return immediately after (without calling recursively
  30 **  again).  In effect, only one star-loop is ever active.  It would be
  31 **  possible to modify the code to maintain this context explicitly,
  32 **  eliminating all recursive calls at the cost of some complication and
  33 **  loss of clarity (and the ABORT stuff seems to be unclear enough by
  34 **  itself).  I think it would be unwise to try to get this into a
  35 **  released version unless you have a good test data base to try it out
  36 **  on.
  37 */
  38
  39 #ifdef HAVE_CONFIG_H
  40 #include <config.h>
  41 #endif
  42
  43 #include <ctype.h>
  44
  45 #define TRUE                    1
  46 #define FALSE                   0
  47 #define ABORT                   -1
  48
  49
  50     /* What character marks an inverted character class? */
  51 #define NEGATE_CLASS            '^'
  52     /* Is "*" a common pattern? */
  53 #define OPTIMIZE_JUST_STAR
  54     /* Do tar(1) matching rules, which ignore a trailing slash? */
  55 #undef MATCH_TAR_PATTERN
  56
  57
  58 /*
  59 **  Match text and p, return TRUE, FALSE, or ABORT.
  60 */
  61 static int
  62 DoMatch(text, p)
  63     register char       *text;
  64     register char       *p;
  65 {
  66     register int        last;
  67     register int        matched;
  68     register int        reverse;
  69
  70     for ( ; *p; text++, p++) {
  71         if (*text == '\0' && *p != '*')
  72             return ABORT;
  73         switch (*p) {
  74         case '\\':
  75             /* Literal match with following character. */
  76             p++;
  77             /* FALLTHROUGH */
  78         default:
  79             if (toupper (*text) != toupper (*p))
  80                 return FALSE;
  81             continue;
  82         case '?':
  83             /* Match anything. */
  84             continue;
  85         case '*':
  86             while (*++p == '*')
  87                 /* Consecutive stars act just like one. */
  88                 continue;
  89             if (*p == '\0')
  90                 /* Trailing star matches everything. */
  91                 return TRUE;
  92             while (*text)
  93                 if ((matched = DoMatch(text++, p)) != FALSE)
  94                     return matched;
  95             return ABORT;
  96         case '[':
  97             reverse = p[1] == NEGATE_CLASS ? TRUE : FALSE;
  98             if (reverse)
  99                 /* Inverted character class. */
 100                 p++;
 101             matched = FALSE;
 102             if (p[1] == ']' || p[1] == '-')
 103                 if (toupper (*++p) == toupper(*text))
 104                     matched = TRUE;
 105             for (last = *p; *++p && *p != ']'; last = *p)
 106                 /* This next line requires a good C compiler. */
 107                 if (*p == '-' && p[1] != ']'
 108                     ? *text <= *++p && *text >= last
 109                       : toupper (*text) == toupper (*p))
 110                     matched = TRUE;
 111             if (matched == reverse)
 112                 return FALSE;
 113             continue;
 114         }
 115     }
 116
 117 #ifdef  MATCH_TAR_PATTERN
 118     if (*text == '/')
 119         return TRUE;
 120 #endif  /* MATCH_TAR_ATTERN */
 121     return *text == '\0';
 122 }
 123
 124
 125 /*
 126 **  User-level routine.  Returns TRUE or FALSE.
 127 */
 128 int
 129 wildmat(text, p)
 130     char        *text;
 131     char        *p;
 132 {
 133 #ifdef  OPTIMIZE_JUST_STAR
 134     if (p[0] == '*' && p[1] == '\0')
 135         return TRUE;
 136 #endif  /* OPTIMIZE_JUST_STAR */
 137     return DoMatch(text, p) == TRUE;
 138 }
 139
 140 \f
 141
 142 #if     defined(TEST)
 143 #include <stdio.h>
 144
 145 /* Yes, we use gets not fgets.  Sue me. */
 146 extern char     *gets();
 147
 148
 149 int
 150 main()
 151 {
 152     char         p[80];
 153     char         text[80];
 154
 155     printf("Wildmat tester.  Enter pattern, then strings to test.\n");
 156     printf("A blank line gets prompts for a new pattern; a blank pattern\n");
 157     printf("exits the program.\n");
 158
 159     for ( ; ; ) {
 160         printf("\nEnter pattern:  ");
 161         (void)fflush(stdout);
 162         if (gets(p) == NULL || p[0] == '\0')
 163             break;
 164         for ( ; ; ) {
 165             printf("Enter text:  ");
 166             (void)fflush(stdout);
 167             if (gets(text) == NULL)
 168                 exit(0);
 169             if (text[0] == '\0')
 170                 /* Blank line; go back and get a new pattern. */
 171                 break;
 172             printf("      %s\n", wildmat(text, p) ? "YES" : "NO");
 173         }
 174     }
 175
 176     exit(0);
 177     /* NOTREACHED */
 178 }
 179 #endif  /* defined(TEST) */