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-2014 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. */
48 # include "unlocked-io.h"
51 /* Non-GNU systems lack these options, so we don't need to check them. */
53 # define FNM_CASEFOLD 0
56 # define FNM_EXTMATCH 0
58 #ifndef FNM_LEADING_DIR
59 # define FNM_LEADING_DIR 0
62 verify (((EXCLUDE_ANCHORED | EXCLUDE_INCLUDE | EXCLUDE_WILDCARDS)
63 & (FNM_PATHNAME | FNM_NOESCAPE | FNM_PERIOD | FNM_LEADING_DIR
64 | FNM_CASEFOLD | FNM_EXTMATCH))
68 /* Exclusion patterns are grouped into a singly-linked list of
69 "exclusion segments". Each segment represents a set of patterns
70 that can be matches using the same algorithm. Non-wildcard
71 patterns are kept in hash tables, to speed up searches. Wildcard
72 patterns are stored as arrays of patterns. */
75 /* An exclude pattern-options pair. The options are fnmatch options
76 ORed with EXCLUDE_* options. */
88 /* An array of pattern-options pairs. */
90 struct exclude_pattern
92 struct patopts *exclude;
99 exclude_hash, /* a hash table of excluded names */
100 exclude_pattern /* an array of exclude patterns */
103 struct exclude_segment
105 struct exclude_segment *next; /* next segment in list */
106 enum exclude_type type; /* type of this segment */
107 int options; /* common options for this segment */
110 Hash_table *table; /* for type == exclude_hash */
111 struct exclude_pattern pat; /* for type == exclude_pattern */
115 struct pattern_buffer
117 struct pattern_buffer *next;
121 /* The exclude structure keeps a singly-linked list of exclude segments,
122 maintained in reverse order. */
125 struct exclude_segment *head;
126 struct pattern_buffer *patbuf;
129 /* Register BUF in the pattern buffer list of EX. ADD_FUNC (see
130 add_exclude_file and add_exclude_fp below) can use this function
131 if it modifies the pattern, to ensure the allocated memory will be
132 properly reclaimed upon calling free_exclude. */
134 exclude_add_pattern_buffer (struct exclude *ex, char *buf)
136 struct pattern_buffer *pbuf = xmalloc (sizeof *pbuf);
138 pbuf->next = ex->patbuf;
142 /* Return true if STR has or may have wildcards, when matched with OPTIONS.
143 Return false if STR definitely does not have wildcards. */
145 fnmatch_pattern_has_wildcards (const char *str, int options)
156 if (options & EXCLUDE_REGEX)
161 if (options & EXCLUDE_REGEX)
164 str += ! (options & FNM_NOESCAPE) && *str;
167 case '+': case '@': case '!':
168 if (options & FNM_EXTMATCH && *str == '(')
172 case '?': case '*': case '[':
182 unescape_pattern (char *str)
186 q += *q == '\\' && q[1];
187 while ((*str++ = *q++));
190 /* Return a newly allocated and empty exclude list. */
195 return xzalloc (sizeof *new_exclude ());
198 /* Calculate the hash of string. */
200 string_hasher (void const *data, size_t n_buckets)
202 char const *p = data;
203 return hash_string (p, n_buckets);
206 /* Ditto, for case-insensitive hashes */
208 string_hasher_ci (void const *data, size_t n_buckets)
210 char const *p = data;
211 mbui_iterator_t iter;
214 for (mbui_init (iter, p); mbui_avail (iter); mbui_advance (iter))
216 mbchar_t m = mbui_cur (iter);
220 wc = towlower (m.wc);
224 value = (value * 31 + wc) % n_buckets;
230 /* compare two strings for equality */
232 string_compare (void const *data1, void const *data2)
234 char const *p1 = data1;
235 char const *p2 = data2;
236 return strcmp (p1, p2) == 0;
239 /* compare two strings for equality, case-insensitive */
241 string_compare_ci (void const *data1, void const *data2)
243 char const *p1 = data1;
244 char const *p2 = data2;
245 return mbscasecmp (p1, p2) == 0;
249 string_free (void *data)
254 /* Create new exclude segment of given TYPE and OPTIONS, and attach it
255 to the head of EX. */
257 new_exclude_segment (struct exclude *ex, enum exclude_type type, int options)
259 struct exclude_segment *sp = xzalloc (sizeof (struct exclude_segment));
261 sp->options = options;
264 case exclude_pattern:
268 sp->v.table = hash_initialize (0, NULL,
269 (options & FNM_CASEFOLD) ?
272 (options & FNM_CASEFOLD) ?
282 /* Free a single exclude segment */
284 free_exclude_segment (struct exclude_segment *seg)
290 case exclude_pattern:
291 for (i = 0; i < seg->v.pat.exclude_count; i++)
293 if (seg->v.pat.exclude[i].options & EXCLUDE_REGEX)
294 regfree (&seg->v.pat.exclude[i].v.re);
296 free (seg->v.pat.exclude);
300 hash_free (seg->v.table);
306 /* Free the storage associated with an exclude list. */
308 free_exclude (struct exclude *ex)
310 struct exclude_segment *seg;
311 struct pattern_buffer *pbuf;
313 for (seg = ex->head; seg; )
315 struct exclude_segment *next = seg->next;
316 free_exclude_segment (seg);
320 for (pbuf = ex->patbuf; pbuf; )
322 struct pattern_buffer *next = pbuf->next;
331 /* Return zero if PATTERN matches F, obeying OPTIONS, except that
332 (unlike fnmatch) wildcards are disabled in PATTERN. */
335 fnmatch_no_wildcards (char const *pattern, char const *f, int options)
337 if (! (options & FNM_LEADING_DIR))
338 return ((options & FNM_CASEFOLD)
339 ? mbscasecmp (pattern, f)
340 : strcmp (pattern, f));
341 else if (! (options & FNM_CASEFOLD))
343 size_t patlen = strlen (pattern);
344 int r = strncmp (pattern, f, patlen);
355 /* Walk through a copy of F, seeing whether P matches any prefix
358 FIXME: This is an O(N**2) algorithm; it should be O(N).
359 Also, the copy should not be necessary. However, fixing this
360 will probably involve a change to the mbs* API. */
362 char *fcopy = xstrdup (f);
365 for (p = fcopy; ; *p++ = '/')
370 r = mbscasecmp (pattern, fcopy);
380 exclude_fnmatch (char const *pattern, char const *f, int options)
382 int (*matcher) (char const *, char const *, int) =
383 (options & EXCLUDE_WILDCARDS
385 : fnmatch_no_wildcards);
386 bool matched = ((*matcher) (pattern, f, options) == 0);
389 if (! (options & EXCLUDE_ANCHORED))
390 for (p = f; *p && ! matched; p++)
391 if (*p == '/' && p[1] != '/')
392 matched = ((*matcher) (pattern, p + 1, options) == 0);
398 exclude_patopts (struct patopts const *opts, char const *f)
400 int options = opts->options;
402 return (options & EXCLUDE_REGEX)
403 ? regexec (&opts->v.re, f, 0, NULL, 0) == 0
404 : exclude_fnmatch (opts->v.pattern, f, options);
407 /* Return true if the exclude_pattern segment SEG matches F. */
410 file_pattern_matches (struct exclude_segment const *seg, char const *f)
412 size_t exclude_count = seg->v.pat.exclude_count;
413 struct patopts const *exclude = seg->v.pat.exclude;
416 for (i = 0; i < exclude_count; i++)
418 if (exclude_patopts (exclude + i, f))
424 /* Return true if the exclude_hash segment SEG matches F.
425 BUFFER is an auxiliary storage of the same length as F (with nul
426 terminator included) */
428 file_name_matches (struct exclude_segment const *seg, char const *f,
431 int options = seg->options;
432 Hash_table *table = seg->v.table;
436 /* initialize the pattern */
441 if (hash_lookup (table, buffer))
443 if (options & FNM_LEADING_DIR)
445 char *p = strrchr (buffer, '/');
455 if (!(options & EXCLUDE_ANCHORED))
469 /* Return true if EX excludes F. */
472 excluded_file_name (struct exclude const *ex, char const *f)
474 struct exclude_segment *seg;
476 char *filename = NULL;
478 /* If no patterns are given, the default is to include. */
482 /* Scan through the segments, reporting the status of the first match.
483 The segments are in reverse order, so this reports the status of
484 the last match in the original option list. */
485 for (seg = ex->head; ; seg = seg->next)
487 if (seg->type == exclude_hash)
490 filename = xmalloc (strlen (f) + 1);
491 if (file_name_matches (seg, f, filename))
496 if (file_pattern_matches (seg, f))
502 /* If patterns are given but none match, the default is the
503 opposite of the last segment (i.e., the first in the
504 original option list). For example, in the command
505 'grep -r --exclude="a*" --include="*b" pat dir', the
506 first option is --exclude so any file name matching
507 neither a* nor *b is included. */
514 return invert ^ ! (seg->options & EXCLUDE_INCLUDE);
517 /* Append to EX the exclusion PATTERN with OPTIONS. */
520 add_exclude (struct exclude *ex, char const *pattern, int options)
522 struct exclude_segment *seg;
523 struct exclude_pattern *pat;
524 struct patopts *patopts;
526 if ((options & (EXCLUDE_REGEX|EXCLUDE_WILDCARDS))
527 && fnmatch_pattern_has_wildcards (pattern, options))
529 if (! (ex->head && ex->head->type == exclude_pattern
530 && ((ex->head->options & EXCLUDE_INCLUDE)
531 == (options & EXCLUDE_INCLUDE))))
532 new_exclude_segment (ex, exclude_pattern, options);
537 if (pat->exclude_count == pat->exclude_alloc)
538 pat->exclude = x2nrealloc (pat->exclude, &pat->exclude_alloc,
539 sizeof *pat->exclude);
540 patopts = &pat->exclude[pat->exclude_count++];
542 patopts->options = options;
543 if (options & EXCLUDE_REGEX)
546 int cflags = REG_NOSUB|REG_EXTENDED|
547 ((options & FNM_CASEFOLD) ? REG_ICASE : 0);
549 if (options & FNM_LEADING_DIR)
552 size_t len = strlen (pattern);
554 while (len > 0 && ISSLASH (pattern[len-1]))
561 tmp = xmalloc (len + 7);
562 memcpy (tmp, pattern, len);
563 strcpy (tmp + len, "(/.*)?");
564 rc = regcomp (&patopts->v.re, tmp, cflags);
569 rc = regcomp (&patopts->v.re, pattern, cflags);
573 pat->exclude_count--;
579 if (options & EXCLUDE_ALLOC)
581 pattern = xstrdup (pattern);
582 exclude_add_pattern_buffer (ex, (char*) pattern);
584 patopts->v.pattern = pattern;
590 int exclude_hash_flags = (EXCLUDE_INCLUDE | EXCLUDE_ANCHORED
591 | FNM_LEADING_DIR | FNM_CASEFOLD);
592 if (! (ex->head && ex->head->type == exclude_hash
593 && ((ex->head->options & exclude_hash_flags)
594 == (options & exclude_hash_flags))))
595 new_exclude_segment (ex, exclude_hash, options);
598 str = xstrdup (pattern);
599 if ((options & (EXCLUDE_WILDCARDS | FNM_NOESCAPE)) == EXCLUDE_WILDCARDS)
600 unescape_pattern (str);
601 p = hash_insert (seg->v.table, str);
607 /* Use ADD_FUNC to append to EX the patterns in FILE_NAME, each with
608 OPTIONS. LINE_END terminates each pattern in the file. If
609 LINE_END is a space character, ignore trailing spaces and empty
610 lines in FP. Return -1 on failure, 0 on success. */
613 add_exclude_fp (void (*add_func) (struct exclude *, char const *, int, void *),
614 struct exclude *ex, FILE *fp, int options,
622 size_t buf_alloc = 0;
623 size_t buf_count = 0;
627 while ((c = getc (fp)) != EOF)
629 if (buf_count == buf_alloc)
630 buf = x2realloc (buf, &buf_alloc);
631 buf[buf_count++] = c;
637 buf = xrealloc (buf, buf_count + 1);
638 buf[buf_count] = line_end;
639 lim = buf + buf_count + ! (buf_count == 0 || buf[buf_count - 1] == line_end);
641 exclude_add_pattern_buffer (ex, buf);
645 for (p = buf; p < lim; p++)
648 char *pattern_end = p;
650 if (isspace ((unsigned char) line_end))
652 for (; ; pattern_end--)
653 if (pattern_end == pattern)
655 else if (! isspace ((unsigned char) pattern_end[-1]))
660 (*add_func) (ex, pattern, options, data);
671 call_addfn (struct exclude *ex, char const *pattern, int options, void *data)
673 void (*addfn) (struct exclude *, char const *, int) = data;
674 addfn (ex, pattern, options);
678 add_exclude_file (void (*add_func) (struct exclude *, char const *, int),
679 struct exclude *ex, char const *file_name, int options,
682 bool use_stdin = file_name[0] == '-' && !file_name[1];
688 else if (! (in = fopen (file_name, "r")))
691 rc = add_exclude_fp (call_addfn, ex, in, options, line_end, add_func);
693 if (!use_stdin && fclose (in) != 0)