1 /* -*- buffer-read-only: t -*- vi: set ro: */
2 /* DO NOT EDIT! GENERATED AUTOMATICALLY! */
3 /* exclude.c -- exclude file names
5 Copyright (C) 1992-1994, 1997, 1999-2007, 2009-2013 Free Software
8 This program is free software: you can redistribute it and/or modify
9 it under the terms of the GNU General Public License as published by
10 the Free Software Foundation; either version 3 of the License, or
11 (at your option) any later version.
13 This program is distributed in the hope that it will be useful,
14 but WITHOUT ANY WARRANTY; without even the implied warranty of
15 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
16 GNU General Public License for more details.
18 You should have received a copy of the GNU General Public License
19 along with this program. If not, see <http://www.gnu.org/licenses/>. */
21 /* Written by Paul Eggert <eggert@twinsun.com>
22 and Sergey Poznyakoff <gray@gnu.org>.
23 Thanks to Phil Proudman <phil@proudman51.freeserve.co.uk>
24 for improvement suggestions. */
46 # include "unlocked-io.h"
49 /* Non-GNU systems lack these options, so we don't need to check them. */
51 # define FNM_CASEFOLD 0
54 # define FNM_EXTMATCH 0
56 #ifndef FNM_LEADING_DIR
57 # define FNM_LEADING_DIR 0
60 verify (((EXCLUDE_ANCHORED | EXCLUDE_INCLUDE | EXCLUDE_WILDCARDS)
61 & (FNM_PATHNAME | FNM_NOESCAPE | FNM_PERIOD | FNM_LEADING_DIR
62 | FNM_CASEFOLD | FNM_EXTMATCH))
66 /* Exclusion patterns are grouped into a singly-linked list of
67 "exclusion segments". Each segment represents a set of patterns
68 that can be matches using the same algorithm. Non-wildcard
69 patterns are kept in hash tables, to speed up searches. Wildcard
70 patterns are stored as arrays of patterns. */
73 /* An exclude pattern-options pair. The options are fnmatch options
74 ORed with EXCLUDE_* options. */
82 /* An array of pattern-options pairs. */
84 struct exclude_pattern
86 struct patopts *exclude;
93 exclude_hash, /* a hash table of excluded names */
94 exclude_pattern /* an array of exclude patterns */
97 struct exclude_segment
99 struct exclude_segment *next; /* next segment in list */
100 enum exclude_type type; /* type of this segment */
101 int options; /* common options for this segment */
104 Hash_table *table; /* for type == exclude_hash */
105 struct exclude_pattern pat; /* for type == exclude_pattern */
109 /* The exclude structure keeps a singly-linked list of exclude segments,
110 maintained in reverse order. */
113 struct exclude_segment *head;
116 /* Return true if STR has or may have wildcards, when matched with OPTIONS.
117 Return false if STR definitely does not have wildcards. */
119 fnmatch_pattern_has_wildcards (const char *str, int options)
126 str += ! (options & FNM_NOESCAPE) && *str;
129 case '+': case '@': case '!':
130 if (options & FNM_EXTMATCH && *str == '(')
134 case '?': case '*': case '[':
144 unescape_pattern (char *str)
148 q += *q == '\\' && q[1];
149 while ((*str++ = *q++));
152 /* Return a newly allocated and empty exclude list. */
157 return xzalloc (sizeof *new_exclude ());
160 /* Calculate the hash of string. */
162 string_hasher (void const *data, size_t n_buckets)
164 char const *p = data;
165 return hash_string (p, n_buckets);
168 /* Ditto, for case-insensitive hashes */
170 string_hasher_ci (void const *data, size_t n_buckets)
172 char const *p = data;
173 mbui_iterator_t iter;
176 for (mbui_init (iter, p); mbui_avail (iter); mbui_advance (iter))
178 mbchar_t m = mbui_cur (iter);
182 wc = towlower (m.wc);
186 value = (value * 31 + wc) % n_buckets;
192 /* compare two strings for equality */
194 string_compare (void const *data1, void const *data2)
196 char const *p1 = data1;
197 char const *p2 = data2;
198 return strcmp (p1, p2) == 0;
201 /* compare two strings for equality, case-insensitive */
203 string_compare_ci (void const *data1, void const *data2)
205 char const *p1 = data1;
206 char const *p2 = data2;
207 return mbscasecmp (p1, p2) == 0;
211 string_free (void *data)
216 /* Create new exclude segment of given TYPE and OPTIONS, and attach it
217 to the head of EX. */
219 new_exclude_segment (struct exclude *ex, enum exclude_type type, int options)
221 struct exclude_segment *sp = xzalloc (sizeof (struct exclude_segment));
223 sp->options = options;
226 case exclude_pattern:
230 sp->v.table = hash_initialize (0, NULL,
231 (options & FNM_CASEFOLD) ?
234 (options & FNM_CASEFOLD) ?
244 /* Free a single exclude segment */
246 free_exclude_segment (struct exclude_segment *seg)
250 case exclude_pattern:
251 free (seg->v.pat.exclude);
255 hash_free (seg->v.table);
261 /* Free the storage associated with an exclude list. */
263 free_exclude (struct exclude *ex)
265 struct exclude_segment *seg;
266 for (seg = ex->head; seg; )
268 struct exclude_segment *next = seg->next;
269 free_exclude_segment (seg);
275 /* Return zero if PATTERN matches F, obeying OPTIONS, except that
276 (unlike fnmatch) wildcards are disabled in PATTERN. */
279 fnmatch_no_wildcards (char const *pattern, char const *f, int options)
281 if (! (options & FNM_LEADING_DIR))
282 return ((options & FNM_CASEFOLD)
283 ? mbscasecmp (pattern, f)
284 : strcmp (pattern, f));
285 else if (! (options & FNM_CASEFOLD))
287 size_t patlen = strlen (pattern);
288 int r = strncmp (pattern, f, patlen);
299 /* Walk through a copy of F, seeing whether P matches any prefix
302 FIXME: This is an O(N**2) algorithm; it should be O(N).
303 Also, the copy should not be necessary. However, fixing this
304 will probably involve a change to the mbs* API. */
306 char *fcopy = xstrdup (f);
309 for (p = fcopy; ; *p++ = '/')
314 r = mbscasecmp (pattern, fcopy);
324 exclude_fnmatch (char const *pattern, char const *f, int options)
326 int (*matcher) (char const *, char const *, int) =
327 (options & EXCLUDE_WILDCARDS
329 : fnmatch_no_wildcards);
330 bool matched = ((*matcher) (pattern, f, options) == 0);
333 if (! (options & EXCLUDE_ANCHORED))
334 for (p = f; *p && ! matched; p++)
335 if (*p == '/' && p[1] != '/')
336 matched = ((*matcher) (pattern, p + 1, options) == 0);
341 /* Return true if the exclude_pattern segment SEG matches F. */
344 file_pattern_matches (struct exclude_segment const *seg, char const *f)
346 size_t exclude_count = seg->v.pat.exclude_count;
347 struct patopts const *exclude = seg->v.pat.exclude;
350 for (i = 0; i < exclude_count; i++)
352 char const *pattern = exclude[i].pattern;
353 int options = exclude[i].options;
354 if (exclude_fnmatch (pattern, f, options))
360 /* Return true if the exclude_hash segment SEG matches F.
361 BUFFER is an auxiliary storage of the same length as F (with nul
362 terminator included) */
364 file_name_matches (struct exclude_segment const *seg, char const *f,
367 int options = seg->options;
368 Hash_table *table = seg->v.table;
372 /* initialize the pattern */
377 if (hash_lookup (table, buffer))
379 if (options & FNM_LEADING_DIR)
381 char *p = strrchr (buffer, '/');
391 if (!(options & EXCLUDE_ANCHORED))
405 /* Return true if EX excludes F. */
408 excluded_file_name (struct exclude const *ex, char const *f)
410 struct exclude_segment *seg;
412 char *filename = NULL;
414 /* If no patterns are given, the default is to include. */
418 /* Scan through the segments, reporting the status of the first match.
419 The segments are in reverse order, so this reports the status of
420 the last match in the original option list. */
421 for (seg = ex->head; ; seg = seg->next)
423 if (seg->type == exclude_hash)
426 filename = xmalloc (strlen (f) + 1);
427 if (file_name_matches (seg, f, filename))
432 if (file_pattern_matches (seg, f))
438 /* If patterns are given but none match, the default is the
439 opposite of the last segment (i.e., the first in the
440 original option list). For example, in the command
441 'grep -r --exclude="a*" --include="*b" pat dir', the
442 first option is --exclude so any file name matching
443 neither a* nor *b is included. */
450 return invert ^ ! (seg->options & EXCLUDE_INCLUDE);
453 /* Append to EX the exclusion PATTERN with OPTIONS. */
456 add_exclude (struct exclude *ex, char const *pattern, int options)
458 struct exclude_segment *seg;
460 if ((options & EXCLUDE_WILDCARDS)
461 && fnmatch_pattern_has_wildcards (pattern, options))
463 struct exclude_pattern *pat;
464 struct patopts *patopts;
466 if (! (ex->head && ex->head->type == exclude_pattern
467 && ((ex->head->options & EXCLUDE_INCLUDE)
468 == (options & EXCLUDE_INCLUDE))))
469 new_exclude_segment (ex, exclude_pattern, options);
473 if (pat->exclude_count == pat->exclude_alloc)
474 pat->exclude = x2nrealloc (pat->exclude, &pat->exclude_alloc,
475 sizeof *pat->exclude);
476 patopts = &pat->exclude[pat->exclude_count++];
477 patopts->pattern = pattern;
478 patopts->options = options;
483 int exclude_hash_flags = (EXCLUDE_INCLUDE | EXCLUDE_ANCHORED
484 | FNM_LEADING_DIR | FNM_CASEFOLD);
485 if (! (ex->head && ex->head->type == exclude_hash
486 && ((ex->head->options & exclude_hash_flags)
487 == (options & exclude_hash_flags))))
488 new_exclude_segment (ex, exclude_hash, options);
491 str = xstrdup (pattern);
492 if ((options & (EXCLUDE_WILDCARDS | FNM_NOESCAPE)) == EXCLUDE_WILDCARDS)
493 unescape_pattern (str);
494 p = hash_insert (seg->v.table, str);
500 /* Use ADD_FUNC to append to EX the patterns in FILE_NAME, each with
501 OPTIONS. LINE_END terminates each pattern in the file. If
502 LINE_END is a space character, ignore trailing spaces and empty
503 lines in FILE. Return -1 on failure, 0 on success. */
506 add_exclude_file (void (*add_func) (struct exclude *, char const *, int),
507 struct exclude *ex, char const *file_name, int options,
510 bool use_stdin = file_name[0] == '-' && !file_name[1];
516 size_t buf_alloc = 0;
517 size_t buf_count = 0;
523 else if (! (in = fopen (file_name, "r")))
526 while ((c = getc (in)) != EOF)
528 if (buf_count == buf_alloc)
529 buf = x2realloc (buf, &buf_alloc);
530 buf[buf_count++] = c;
536 if (!use_stdin && fclose (in) != 0)
539 buf = xrealloc (buf, buf_count + 1);
540 buf[buf_count] = line_end;
541 lim = buf + buf_count + ! (buf_count == 0 || buf[buf_count - 1] == line_end);
544 for (p = buf; p < lim; p++)
547 char *pattern_end = p;
549 if (isspace ((unsigned char) line_end))
551 for (; ; pattern_end--)
552 if (pattern_end == pattern)
554 else if (! isspace ((unsigned char) pattern_end[-1]))
559 (*add_func) (ex, pattern, options);