git.sesse.net Git - rdpsrv/blob - Xserver/config/util/mkshadow/wildmat.c

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