1/* $Revision: 1.2 $
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
36 ** out on.
37 */
38
39#include "cs_config.h"
40
41#include <ctype.h>
42#include "neo_misc.h"
43
44#define ABORT -1
45
46
47 /* What character marks an inverted character class? */
48#define NEGATE_CLASS '^'
49 /* Is "*" a common pattern? */
50#define OPTIMIZE_JUST_STAR
51 /* Do tar(1) matching rules, which ignore a trailing slash? */
52#undef MATCH_TAR_PATTERN
53
54
55/*
56 ** Match text and p, return TRUE, FALSE, or ABORT.
57 */
58  static int
59DoMatch(register const char *text, register const 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	matched = FALSE;
97	if (p[1] == ']' || p[1] == '-')
98	  if (*++p == *text)
99	    matched = TRUE;
100	for (last = *p; *++p && *p != ']'; last = *p)
101	  /* This next line requires a good C compiler. */
102	  if (*p == '-' && p[1] != ']'
103	      ? *text <= *++p && *text >= last : *text == *p)
104	    matched = TRUE;
105	if (matched == reverse)
106	  return FALSE;
107	continue;
108    }
109  }
110
111#ifdef MATCH_TAR_PATTERN
112  if (*text == '/')
113    return TRUE;
114#endif /* MATCH_TAR_ATTERN */
115  return *text == '\0';
116}
117
118
119/*
120 ** Match text and p, return TRUE, FALSE, or ABORT.
121 */
122static int
123DoMatchCaseInsensitive(register const char *text, register const char *p)
124{
125  register int last;
126  register int matched;
127  register int reverse;
128
129  for ( ; *p; text++, p++) {
130    if (*text == '\0' && *p != '*')
131      return ABORT;
132    switch (*p) {
133      case '\\':
134	/* Literal match with following character. */
135	p++;
136	/* FALLTHROUGH */
137      default:
138	if (toupper(*text) != toupper(*p))
139	  return FALSE;
140	continue;
141      case '?':
142	/* Match anything. */
143	continue;
144      case '*':
145	while (*++p == '*')
146	  /* Consecutive stars act just like one. */
147	  continue;
148	if (*p == '\0')
149	  /* Trailing star matches everything. */
150	  return TRUE;
151	while (*text)
152	  if ((matched = DoMatchCaseInsensitive(text++, p)) != FALSE)
153	    return matched;
154	return ABORT;
155      case '[':
156	reverse = p[1] == NEGATE_CLASS ? TRUE : FALSE;
157	if (reverse)
158	  /* Inverted character class. */
159	  p++;
160	matched = FALSE;
161	if (p[1] == ']' || p[1] == '-')
162	  if (toupper(*++p) == toupper(*text))
163	    matched = TRUE;
164	for (last = toupper(*p); *++p && *p != ']'; last = toupper(*p))
165	  /* This next line requires a good C compiler. */
166	  if (*p == '-' && p[1] != ']'
167	      ? toupper(*text) <= toupper(*++p) && toupper(*text) >= last : toupper(*text) == toupper(*p))
168	    matched = TRUE;
169	if (matched == reverse)
170	  return FALSE;
171	continue;
172    }
173  }
174
175#ifdef MATCH_TAR_PATTERN
176  if (*text == '/')
177    return TRUE;
178#endif /* MATCH_TAR_ATTERN */
179  return *text == '\0';
180}
181
182
183/*
184 ** User-level routine. Returns TRUE or FALSE.
185 */
186int
187wildmat(const char *text, const char *p)
188{
189#ifdef OPTIMIZE_JUST_STAR
190  if (p[0] == '*' && p[1] == '\0')
191    return TRUE;
192#endif /* OPTIMIZE_JUST_STAR */
193  return DoMatch(text, p) == TRUE;
194}
195
196/*
197 ** User-level routine. Returns TRUE or FALSE.
198 */
199int
200wildmatcase(const char *text, const char *p)
201{
202#ifdef OPTIMIZE_JUST_STAR
203  if (p[0] == '*' && p[1] == '\0')
204    return TRUE;
205#endif /* OPTIMIZE_JUST_STAR */
206  return DoMatchCaseInsensitive(text, p) == TRUE;
207}
208