BRL-CAD
fnmatch.c
Go to the documentation of this file.
1 /* F N M A T C H . C
2  * BRL-CAD
3  *
4  * Copyright (c) 1993-2014 United States Government as represented by
5  * the U.S. Army Research Laboratory.
6  *
7  * This library is free software; you can redistribute it and/or
8  * modify it under the terms of the GNU Lesser General Public License
9  * version 2.1 as published by the Free Software Foundation.
10  *
11  * This library is distributed in the hope that it will be useful, but
12  * WITHOUT ANY WARRANTY; without even the implied warranty of
13  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
14  * Lesser General Public License for more details.
15  *
16  * You should have received a copy of the GNU Lesser General Public
17  * License along with this file; see the file named COPYING for more
18  * information.
19  */
20 /*
21  * Based off of OpenBSD's fnmatch.c v 1.13 2006/03/31
22  *
23  * Copyright (c) 1989, 1993, 1994
24  * The Regents of the University of California. All rights reserved.
25  *
26  * This code is derived from software contributed to Berkeley by
27  * Guido van Rossum.
28  *
29  * Redistribution and use in source and binary forms, with or without
30  * modification, are permitted provided that the following conditions
31  * are met:
32  * 1. Redistributions of source code must retain the above copyright
33  * notice, this list of conditions and the following disclaimer.
34  * 2. Redistributions in binary form must reproduce the above copyright
35  * notice, this list of conditions and the following disclaimer in the
36  * documentation and/or other materials provided with the distribution.
37  * 3. Neither the name of the University nor the names of its contributors
38  * may be used to endorse or promote products derived from this software
39  * without specific prior written permission.
40  *
41  * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
42  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
43  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
44  * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
45  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
46  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
47  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
48  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
49  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
50  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
51  * SUCH DAMAGE.
52  *
53  */
54 
55 #include "common.h"
56 
57 #include <stdlib.h>
58 #include <ctype.h>
59 #include <string.h>
60 #include "bio.h"
61 
62 #include "bu/file.h"
63 #include "bu/log.h"
64 #include "bu/str.h"
65 #include "bu/vls.h"
66 
67 #define FNMATCH_IGNORECASE BU_FNMATCH_CASEFOLD
68 #define FNMATCH_FILE_NAME BU_FNMATCH_PATHNAME
69 
70 #define FNMATCH_EOS '\0'
71 
72 #define FNMATCH_RANGE_MATCH 1
73 #define FNMATCH_RANGE_NOMATCH 0
74 #define FNMATCH_RANGE_ERROR (-1)
75 
76 /* isblank appears to be obsolete in newer ctype.h files so use
77  * fnblank instead when looking for the "blank" character class.
78  */
79 static inline int
80 fnblank(int c)
81 {
82 #ifdef isblank
83  return isblank(c);
84 #else
85  return c == ' ' || c == '\t';
86 #endif
87 }
88 
89 
90 static inline int
91 fnalnum(int c)
92 {
93  return isalnum(c);
94 }
95 
96 
97 static inline int
98 fnalpha(int c)
99 {
100  return isalpha(c);
101 }
102 
103 
104 static inline int
105 fncntrl(int c)
106 {
107  return iscntrl(c);
108 }
109 
110 
111 static inline int
112 fndigit(int c)
113 {
114  return isdigit(c);
115 }
116 
117 
118 static inline int
119 fngraph(int c)
120 {
121  return isgraph(c);
122 }
123 
124 
125 static inline int
126 fnlower(int c)
127 {
128  return islower(c);
129 }
130 
131 
132 static inline int
133 fnprint(int c)
134 {
135  return isprint(c);
136 }
137 
138 
139 static inline int
140 fnpunct(int c)
141 {
142  return ispunct(c);
143 }
144 
145 
146 static inline int
147 fnspace(int c)
148 {
149  return isspace(c);
150 }
151 
152 
153 static inline int
154 fnupper(int c)
155 {
156  return isupper(c);
157 }
158 
159 
160 static inline int
161 fnxdigit(int c)
162 {
163  return isxdigit(c);
164 }
165 
166 
167 typedef struct _charclass {
168  const char *idstring; /* identifying string */
169  int (*checkfun)(int); /* testing function */
170 } CHARCLASS;
171 
172 static CHARCLASS charclasses[] = {
173  { "alnum", fnalnum },
174  { "alpha", fnalpha },
175  { "blank", fnblank },
176  { "cntrl", fncntrl },
177  { "digit", fndigit },
178  { "graph", fngraph },
179  { "lower", fnlower },
180  { "print", fnprint },
181  { "punct", fnpunct },
182  { "space", fnspace },
183  { "upper", fnupper },
184  { "xdigit", fnxdigit },
185 };
186 
187 
188 static int
189 classcompare(const void *a, const void *b)
190 {
191  return bu_strcmp(((CHARCLASS *)a)->idstring, ((CHARCLASS *)b)->idstring);
192 }
193 
194 
195 static CHARCLASS *
196 findclass(char *charclass)
197 {
198  CHARCLASS tmp;
199  tmp.idstring = charclass;
200  tmp.checkfun = NULL;
201  return (CHARCLASS *)bsearch(&tmp, charclasses, sizeof(charclasses)/sizeof(CHARCLASS), sizeof(CHARCLASS), classcompare);
202 }
203 
204 
205 static size_t
206 charclassmatch(const char *pattern, char test, size_t *s)
207 {
208  char c;
209  size_t counter = 0;
210  size_t resultholder = 0;
211  struct bu_vls classname = BU_VLS_INIT_ZERO;
212  CHARCLASS *ctclass;
213 
214  c = *pattern++;
215  while (c && (c != ':') && (resultholder != (size_t)-1)) {
216  if (c == FNMATCH_EOS)
217  resultholder = (size_t)-1;
218  counter++;
219 
220  c = *pattern++; /* next */
221  }
222  c = *pattern++;
223  bu_vls_strncpy(&classname, pattern-counter-2, counter);
224 
225  ctclass = findclass(bu_vls_addr(&classname));
226  if (ctclass == NULL) {
227  bu_log("Unknown character class type: %s\n", bu_vls_addr(&classname));
228  resultholder = (size_t)-1;
229  } else {
230  /*bu_log("classname: %s, test char = %c, (class->checkfun)=%d\n", bu_vls_addr(&classname), test, (ctclass->checkfun)(test));*/
231  if ((ctclass->checkfun)(test) != 0) {
232  resultholder = counter;
233  } else {
234  resultholder = 0;
235  }
236  }
237  *s = resultholder;
238  bu_vls_free(&classname);
239  return counter;
240 }
241 
242 
243 static int
244 _rangematch(const char *pattern, char test, int flags, char **newp)
245 {
246  size_t s;
247  int negate, ok, incpattern;
248  char c, c2;
249  /*
250  * A bracket expression starting with an unquoted circumflex
251  * character produces unspecified results (IEEE 1003.2-1992,
252  * 3.13.2). This implementation treats it like '!', for
253  * consistency with the regular expression syntax. J.T. Conklin
254  * (conklin@ngai.kaleida.com)
255  */
256  negate = (*pattern == '!' || *pattern == '^');
257  if (negate)
258  ++pattern;
259 
260 
261  if (flags & BU_FNMATCH_CASEFOLD)
262  test = (char)tolower((unsigned char)test);
263 
264  ok = 0;
265 
266  /*
267  * A right bracket shall lose its special meaning and represent
268  * itself in a bracket expression if it occurs first in the list.
269  * -- POSIX.2 2.8.3.2
270  */
271  c = *pattern++;
272  do {
273  if (c == '\\' && !(flags & BU_FNMATCH_NOESCAPE))
274  c = *pattern++;
275  if (c == FNMATCH_EOS)
276  return FNMATCH_RANGE_ERROR;
277  if (c == '/' && (flags & BU_FNMATCH_PATHNAME))
278  return FNMATCH_RANGE_NOMATCH;
279  if ((flags & BU_FNMATCH_CASEFOLD))
280  c = (char)tolower((unsigned char)c);
281  if (*pattern == '-'
282  && (c2 = *(pattern+1)) != FNMATCH_EOS && c2 != ']')
283  {
284  pattern += 2;
285  if (c2 == '\\' && !(flags & BU_FNMATCH_NOESCAPE))
286  c2 = *pattern++;
287  if (c2 == FNMATCH_EOS)
288  return FNMATCH_RANGE_ERROR;
289  if (flags & BU_FNMATCH_CASEFOLD)
290  c2 = (char)tolower((unsigned char)c2);
291  if (c <= test && test <= c2)
292  ok = 1;
293  } else if (c == test) {
294  ok = 1;
295  } else if ((c == '[') && (*pattern == ':')) {
296  incpattern = charclassmatch(pattern+1, test, &s);
297  if (s == (size_t)-1)
298  return FNMATCH_RANGE_ERROR;
299  if (s > 0)
300  ok = 1;
301  pattern = pattern + incpattern + 3;
302  }
303  } while ((c = *pattern++) != ']');
304 
305  *newp = (char *)pattern;
306  return ok == negate ? FNMATCH_RANGE_NOMATCH : FNMATCH_RANGE_MATCH;
307 }
308 
309 
310 int
311 bu_fnmatch(const char *pattern, const char *string, int flags)
312 {
313  const char *stringstart;
314  char *newp;
315  char c, test;
316  int limit = 10000;
317 
318  for (stringstart = string; limit > 0; limit--) {
319  switch (c = *pattern++) {
320  case FNMATCH_EOS:
321  if ((flags & BU_FNMATCH_LEADING_DIR) && *string == '/')
322  return 0;
323  return *string == FNMATCH_EOS ? 0 : BU_FNMATCH_NOMATCH;
324  case '?':
325  if (*string == FNMATCH_EOS)
326  return BU_FNMATCH_NOMATCH;
327  if (*string == '/' && (flags & BU_FNMATCH_PATHNAME))
328  return BU_FNMATCH_NOMATCH;
329  if (*string == '.' && (flags & BU_FNMATCH_PERIOD) &&
330  (string == stringstart ||
331  ((flags & BU_FNMATCH_PATHNAME) && *(string - 1) == '/')))
332  return BU_FNMATCH_NOMATCH;
333  ++string;
334  break;
335  case '*':
336  c = *pattern;
337  /* Collapse multiple stars. */
338  while (c == '*')
339  c = *++pattern;
340 
341  if (*string == '.' && (flags & BU_FNMATCH_PERIOD) &&
342  (string == stringstart ||
343  ((flags & BU_FNMATCH_PATHNAME) && *(string - 1) == '/')))
344  return BU_FNMATCH_NOMATCH;
345 
346  /* Optimize for pattern with * at end or before /. */
347  if (c == FNMATCH_EOS) {
348  if (flags & BU_FNMATCH_PATHNAME)
349  return ((flags & BU_FNMATCH_LEADING_DIR) ||
350  strchr(string, '/') == NULL ?
351  0 : BU_FNMATCH_NOMATCH);
352  else
353  return 0;
354  } else if (c == '/' && (flags & BU_FNMATCH_PATHNAME)) {
355  if ((string = strchr(string, '/')) == NULL)
356  return BU_FNMATCH_NOMATCH;
357  break;
358  }
359 
360  /* General case, use recursion. */
361  while ((test = *string) != FNMATCH_EOS) {
362  if (!bu_fnmatch(pattern, string, flags & ~BU_FNMATCH_PERIOD))
363  return 0;
364  if (test == '/' && (flags & BU_FNMATCH_PATHNAME))
365  break;
366  ++string;
367  }
368  return BU_FNMATCH_NOMATCH;
369  case '[':
370  if (*string == FNMATCH_EOS)
371  return BU_FNMATCH_NOMATCH;
372  if (*string == '/' && (flags & BU_FNMATCH_PATHNAME))
373  return BU_FNMATCH_NOMATCH;
374  if (*string == '.' && (flags & BU_FNMATCH_PERIOD) &&
375  (string == stringstart ||
376  ((flags & BU_FNMATCH_PATHNAME) && *(string - 1) == '/')))
377  return BU_FNMATCH_NOMATCH;
378 
379  switch (_rangematch(pattern, *string, flags, &newp)) {
380  case FNMATCH_RANGE_ERROR:
381  /* not a good range, treat as normal text */
382  goto normal;
383  case FNMATCH_RANGE_MATCH:
384  pattern = newp;
385  break;
387  return BU_FNMATCH_NOMATCH;
388  }
389  ++string;
390  break;
391  case '\\':
392  if (!(flags & BU_FNMATCH_NOESCAPE)) {
393  if ((c = *pattern++) == FNMATCH_EOS) {
394  c = '\\';
395  --pattern;
396  }
397  }
398  /* FALLTHROUGH */
399  default:
400  normal:
401  if (c != *string && !((flags & BU_FNMATCH_CASEFOLD) &&
402  (tolower((unsigned char)c) ==
403  tolower((unsigned char)*string))))
404  return BU_FNMATCH_NOMATCH;
405  ++string;
406  break;
407  }
408  }
409 
410  /* NOTREACHED (unless inf looping) */
411  return 0;
412 }
413 
414 
415 /*
416  * Local Variables:
417  * tab-width: 8
418  * mode: C
419  * indent-tabs-mode: t
420  * c-file-style: "stroustrup"
421  * End:
422  * ex: shiftwidth=4 tabstop=8
423  */
#define FNMATCH_RANGE_NOMATCH
Definition: fnmatch.c:73
void bu_log(const char *,...) _BU_ATTR_PRINTF12
Definition: log.c:176
#define BU_FNMATCH_NOMATCH
Definition: file.h:178
#define BU_FNMATCH_CASEFOLD
Definition: file.h:173
if lu s
Definition: nmg_mod.c:3860
void bu_vls_strncpy(struct bu_vls *vp, const char *s, size_t n)
Definition: vls.c:339
Header file for the BRL-CAD common definitions.
#define FNMATCH_RANGE_MATCH
Definition: fnmatch.c:72
size_t counter[MAX_PSW]
Definition: bu_parallel.c:42
#define FNMATCH_RANGE_ERROR
Definition: fnmatch.c:74
char * strchr(const char *sp, int c)
#define BU_FNMATCH_LEADING_DIR
Definition: file.h:172
void bu_vls_free(struct bu_vls *vp)
Definition: vls.c:248
struct _charclass CHARCLASS
#define BU_FNMATCH_NOESCAPE
Definition: file.h:169
#define BU_FNMATCH_PERIOD
Definition: file.h:171
int bu_fnmatch(const char *pattern, const char *string, int flags)
Definition: fnmatch.c:311
#define FNMATCH_EOS
Definition: fnmatch.c:70
int(* checkfun)(int)
Definition: fnmatch.c:169
#define BU_FNMATCH_PATHNAME
Definition: file.h:170
char * bu_vls_addr(const struct bu_vls *vp)
Definition: vls.c:111
int bu_strcmp(const char *string1, const char *string2)
Definition: str.c:171
#define BU_VLS_INIT_ZERO
Definition: vls.h:84
Definition: vls.h:56
const char * idstring
Definition: fnmatch.c:168