Initial revision
[nfs-utils.git] / 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 #include "config.h"
40
41 #include <ctype.h>
42
43 #define TRUE                    1
44 #define FALSE                   0
45 #define ABORT                   -1
46
47
48     /* What character marks an inverted character class? */
49 #define NEGATE_CLASS            '^'
50     /* Is "*" a common pattern? */
51 #define OPTIMIZE_JUST_STAR
52     /* Do tar(1) matching rules, which ignore a trailing slash? */
53 #undef MATCH_TAR_PATTERN
54
55
56 /*
57 **  Match text and p, return TRUE, FALSE, or ABORT.
58 */
59 static int
60 DoMatch(text, p)
61     register char       *text;
62     register char       *p;
63 {
64     register int        last;
65     register int        matched;
66     register int        reverse;
67
68     for ( ; *p; text++, p++) {
69         if (*text == '\0' && *p != '*')
70             return ABORT;
71         switch (*p) {
72         case '\\':
73             /* Literal match with following character. */
74             p++;
75             /* FALLTHROUGH */
76         default:
77             if (toupper (*text) != toupper (*p))
78                 return FALSE;
79             continue;
80         case '?':
81             /* Match anything. */
82             continue;
83         case '*':
84             while (*++p == '*')
85                 /* Consecutive stars act just like one. */
86                 continue;
87             if (*p == '\0')
88                 /* Trailing star matches everything. */
89                 return TRUE;
90             while (*text)
91                 if ((matched = DoMatch(text++, p)) != FALSE)
92                     return matched;
93             return ABORT;
94         case '[':
95             reverse = p[1] == NEGATE_CLASS ? TRUE : FALSE;
96             if (reverse)
97                 /* Inverted character class. */
98                 p++;
99             matched = FALSE;
100             if (p[1] == ']' || p[1] == '-')
101                 if (toupper (*++p) == toupper(*text))
102                     matched = TRUE;
103             for (last = *p; *++p && *p != ']'; last = *p)
104                 /* This next line requires a good C compiler. */
105                 if (*p == '-' && p[1] != ']'
106                     ? *text <= *++p && *text >= last
107                       : toupper (*text) == toupper (*p))
108                     matched = TRUE;
109             if (matched == reverse)
110                 return FALSE;
111             continue;
112         }
113     }
114
115 #ifdef  MATCH_TAR_PATTERN
116     if (*text == '/')
117         return TRUE;
118 #endif  /* MATCH_TAR_ATTERN */
119     return *text == '\0';
120 }
121
122
123 /*
124 **  User-level routine.  Returns TRUE or FALSE.
125 */
126 int
127 wildmat(text, p)
128     char        *text;
129     char        *p;
130 {
131 #ifdef  OPTIMIZE_JUST_STAR
132     if (p[0] == '*' && p[1] == '\0')
133         return TRUE;
134 #endif  /* OPTIMIZE_JUST_STAR */
135     return DoMatch(text, p) == TRUE;
136 }
137
138 \f
139
140 #if     defined(TEST)
141 #include <stdio.h>
142
143 /* Yes, we use gets not fgets.  Sue me. */
144 extern char     *gets();
145
146
147 int
148 main()
149 {
150     char         p[80];
151     char         text[80];
152
153     printf("Wildmat tester.  Enter pattern, then strings to test.\n");
154     printf("A blank line gets prompts for a new pattern; a blank pattern\n");
155     printf("exits the program.\n");
156
157     for ( ; ; ) {
158         printf("\nEnter pattern:  ");
159         (void)fflush(stdout);
160         if (gets(p) == NULL || p[0] == '\0')
161             break;
162         for ( ; ; ) {
163             printf("Enter text:  ");
164             (void)fflush(stdout);
165             if (gets(text) == NULL)
166                 exit(0);
167             if (text[0] == '\0')
168                 /* Blank line; go back and get a new pattern. */
169                 break;
170             printf("      %s\n", wildmat(text, p) ? "YES" : "NO");
171         }
172     }
173
174     exit(0);
175     /* NOTREACHED */
176 }
177 #endif  /* defined(TEST) */