cde/config/util/mkshadow/wildmat.c

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