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  */
novc_test(const char * filename,struct utftpd_ctrl * flags)38 
39 /* modified by Uwe Ohse <uwe@ohse.de> for use in conflib
40  * and later for use elsewhere.
41  * I use this instead of fnmatch just because fnmatch is a compatibility
42  * problem, not because this one is more beautiful.
43  */
44 
45 #include "uocompiler.h"
46 #include "wildmat.h"
47 
48 #define TRUE			1
49 #define FALSE			0
50 #define ABORT			-1
51 
52 
53 	/* What character marks an inverted character class? */
54 #define NEGATE_CLASS		'^'
55 
56 
57 /*
58  **  Match text and p, return TRUE, FALSE, or ABORT.
59  **  tar(1) matching rules, which ignore a trailing slash? then set trailing_slash_ok != 0.
60  */
61 static int
62 DoMatch (const char *text, const char *p, int trailing_slash_ok)
63 {
64 	int last;
65 	int matched;
66 	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 (*text != *p)
78 				return FALSE;
79 			continue;
80 		case '?':
81 			/* Match anything. */
82 			continue;
83 		case '*':
84 			/* Consecutive stars act just like one. */
85 			while (*++p == '*')
86 				continue;
87 			/* Trailing star matches everything. */
88 			if (*p == '\0')
89 				return TRUE;
90 			while (*text)
91 				if ((matched = DoMatch (text++, p, trailing_slash_ok)) != FALSE)
92 					return matched;
93 			return ABORT;
94 		case '[':
95 			/* Inverted character class? */
96 			if (p[1]==NEGATE_CLASS) {
97 				reverse=1; p++;
98 			} else
99 				reverse=0;
100 			matched = FALSE;
101 			if (p[1] == ']' || p[1] == '-') {
102 				if (*++p == *text)
103 					matched = TRUE;
104 			}
105 			for (last = *p; *++p && *p != ']'; last = *p)
106 				/* This next line requires a good C compiler. */
107 				if (*p == '-' && p[1] != ']' && p[1]
108 					? *text <= *++p && *text >= last : *text == *p)
109 					matched = TRUE;
110 			if (matched == reverse)
111 				return FALSE;
112 			continue;
113 		}
114 	}
115 
116 	if (trailing_slash_ok && *text == '/')
117 		return TRUE;
118 	return *text == '\0';
119 }
120 
121 
122 /*
123  **  User-level routine.  Returns TRUE or FALSE.
124  */
125 int
126 wildmat (const char *text, const char *p)
127 {
128 	if (p[0] == '*' && p[1] == '\0') return TRUE; /* fast special case */
129 	return DoMatch (text, p,0) == TRUE;
130 }
131 /* almost the same, but accepts trailing slash plus whatever follows that:
132  * /var/tmp/xxx/yyy matches the pattern *tmp
133  */
134 int
135 dir_wildmat (const char *text, const char *p)
136 {
137 	if (p[0] == '*' && p[1] == '\0') return TRUE; /* fast special case */
138 	return DoMatch (text, p,1) == TRUE;
139 }
140 
141 
142 
143 #if	defined(TEST)
144 #include <stdio.h>
145 
146 /* Yes, we use gets not fgets.  Sue me. */
147 extern char *gets ();
148 
149 
150 int
151 main ()
152 {
153 	char p[80];
154 	char text[80];
155 
156 	printf ("Wildmat tester.  Enter pattern, then strings to test.\n");
157 	printf ("A blank line gets prompts for a new pattern; a blank pattern\n");
158 	printf ("exits the program.\n");
159 
160 	for (;;) {
161 		printf ("\nEnter pattern:  ");
162 		(void) fflush (stdout);
163 		if (gets (p) == NULL || p[0] == '\0')
164 			break;
165 		for (;;) {
166 			printf ("Enter text:  ");
167 			(void) fflush (stdout);
168 			if (gets (text) == NULL)
169 				exit (0);
170 			if (text[0] == '\0')
171 				/* Blank line; go back and get a new pattern. */
172 				break;
173 			printf ("      %s\n", wildmat (text, p) ? "YES" : "NO");
174 		}
175 	}
176 
177 	exit (0);
178 	/* NOTREACHED */
179 }
180 #endif							/* defined(TEST) */
181