1 /* exclude.c -- exclude file names
3 Copyright (C) 1992-1994, 1997, 1999-2007, 2009-2011 Free Software
6 This program is free software: you can redistribute it and/or modify
7 it under the terms of the GNU General Public License as published by
8 the Free Software Foundation; either version 3 of the License, or
9 (at your option) any later version.
11 This program is distributed in the hope that it will be useful,
12 but WITHOUT ANY WARRANTY; without even the implied warranty of
13 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14 GNU General Public License for more details.
16 You should have received a copy of the GNU General Public License
17 along with this program. If not, see <http://www.gnu.org/licenses/>. */
19 /* Written by Paul Eggert <eggert@twinsun.com>
20 and Sergey Poznyakoff <gray@gnu.org>.
21 Thanks to Phil Proudman <phil@proudman51.freeserve.co.uk>
22 for improvement suggestions. */
44 # include "unlocked-io.h"
47 /* Non-GNU systems lack these options, so we don't need to check them. */
49 # define FNM_CASEFOLD 0
52 # define FNM_EXTMATCH 0
54 #ifndef FNM_LEADING_DIR
55 # define FNM_LEADING_DIR 0
58 verify (((EXCLUDE_ANCHORED | EXCLUDE_INCLUDE | EXCLUDE_WILDCARDS)
59 & (FNM_PATHNAME | FNM_NOESCAPE | FNM_PERIOD | FNM_LEADING_DIR
60 | FNM_CASEFOLD | FNM_EXTMATCH))
63 /* The attribute __pure__ was added in gcc 2.96. */
64 #undef _GL_ATTRIBUTE_PURE
65 #if __GNUC__ > 2 || (__GNUC__ == 2 && __GNUC_MINOR__ >= 96)
66 # define _GL_ATTRIBUTE_PURE __attribute__ ((__pure__))
68 # define _GL_ATTRIBUTE_PURE /* empty */
72 /* Exclusion patterns are grouped into a singly-linked list of
73 "exclusion segments". Each segment represents a set of patterns
74 that can be matches using the same algorithm. Non-wildcard
75 patterns are kept in hash tables, to speed up searches. Wildcard
76 patterns are stored as arrays of patterns. */
79 /* An exclude pattern-options pair. The options are fnmatch options
80 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 /* The exclude structure keeps a singly-linked list of exclude segments */
118 struct exclude_segment *head, *tail;
121 /* Return true if str has wildcard characters */
122 bool _GL_ATTRIBUTE_PURE
123 fnmatch_pattern_has_wildcards (const char *str, int options)
125 const char *cset = "\\?*[]";
126 if (options & FNM_NOESCAPE)
130 size_t n = strcspn (str, cset);
133 else if (str[n] == '\\')
146 unescape_pattern (char *str)
162 while ((*str++ = *q++));
165 /* Return a newly allocated and empty exclude list. */
170 return xzalloc (sizeof *new_exclude ());
173 /* Calculate the hash of string. */
175 string_hasher (void const *data, size_t n_buckets)
177 char const *p = data;
178 return hash_string (p, n_buckets);
181 /* Ditto, for case-insensitive hashes */
183 string_hasher_ci (void const *data, size_t n_buckets)
185 char const *p = data;
186 mbui_iterator_t iter;
189 for (mbui_init (iter, p); mbui_avail (iter); mbui_advance (iter))
191 mbchar_t m = mbui_cur (iter);
195 wc = towlower (m.wc);
199 value = (value * 31 + wc) % n_buckets;
205 /* compare two strings for equality */
207 string_compare (void const *data1, void const *data2)
209 char const *p1 = data1;
210 char const *p2 = data2;
211 return strcmp (p1, p2) == 0;
214 /* compare two strings for equality, case-insensitive */
216 string_compare_ci (void const *data1, void const *data2)
218 char const *p1 = data1;
219 char const *p2 = data2;
220 return mbscasecmp (p1, p2) == 0;
224 string_free (void *data)
229 /* Create new exclude segment of given TYPE and OPTIONS, and attach it
230 to the tail of list in EX */
231 static struct exclude_segment *
232 new_exclude_segment (struct exclude *ex, enum exclude_type type, int options)
234 struct exclude_segment *sp = xzalloc (sizeof (struct exclude_segment));
236 sp->options = options;
239 case exclude_pattern:
243 sp->v.table = hash_initialize (0, NULL,
244 (options & FNM_CASEFOLD) ?
247 (options & FNM_CASEFOLD) ?
261 /* Free a single exclude segment */
263 free_exclude_segment (struct exclude_segment *seg)
267 case exclude_pattern:
268 free (seg->v.pat.exclude);
272 hash_free (seg->v.table);
278 /* Free the storage associated with an exclude list. */
280 free_exclude (struct exclude *ex)
282 struct exclude_segment *seg;
283 for (seg = ex->head; seg; )
285 struct exclude_segment *next = seg->next;
286 free_exclude_segment (seg);
292 /* Return zero if PATTERN matches F, obeying OPTIONS, except that
293 (unlike fnmatch) wildcards are disabled in PATTERN. */
296 fnmatch_no_wildcards (char const *pattern, char const *f, int options)
298 if (! (options & FNM_LEADING_DIR))
299 return ((options & FNM_CASEFOLD)
300 ? mbscasecmp (pattern, f)
301 : strcmp (pattern, f));
302 else if (! (options & FNM_CASEFOLD))
304 size_t patlen = strlen (pattern);
305 int r = strncmp (pattern, f, patlen);
316 /* Walk through a copy of F, seeing whether P matches any prefix
319 FIXME: This is an O(N**2) algorithm; it should be O(N).
320 Also, the copy should not be necessary. However, fixing this
321 will probably involve a change to the mbs* API. */
323 char *fcopy = xstrdup (f);
326 for (p = fcopy; ; *p++ = '/')
331 r = mbscasecmp (pattern, fcopy);
341 exclude_fnmatch (char const *pattern, char const *f, int options)
343 int (*matcher) (char const *, char const *, int) =
344 (options & EXCLUDE_WILDCARDS
346 : fnmatch_no_wildcards);
347 bool matched = ((*matcher) (pattern, f, options) == 0);
350 if (! (options & EXCLUDE_ANCHORED))
351 for (p = f; *p && ! matched; p++)
352 if (*p == '/' && p[1] != '/')
353 matched = ((*matcher) (pattern, p + 1, options) == 0);
358 /* Return true if the exclude_pattern segment SEG excludes F. */
361 excluded_file_pattern_p (struct exclude_segment const *seg, char const *f)
363 size_t exclude_count = seg->v.pat.exclude_count;
364 struct patopts const *exclude = seg->v.pat.exclude;
366 bool excluded = !! (exclude[0].options & EXCLUDE_INCLUDE);
368 /* Scan through the options, until they change excluded */
369 for (i = 0; i < exclude_count; i++)
371 char const *pattern = exclude[i].pattern;
372 int options = exclude[i].options;
373 if (exclude_fnmatch (pattern, f, options))
379 /* Return true if the exclude_hash segment SEG excludes F.
380 BUFFER is an auxiliary storage of the same length as F (with nul
381 terminator included) */
383 excluded_file_name_p (struct exclude_segment const *seg, char const *f,
386 int options = seg->options;
387 bool excluded = !! (options & EXCLUDE_INCLUDE);
388 Hash_table *table = seg->v.table;
392 /* initialize the pattern */
397 if (hash_lookup (table, buffer))
399 if (options & FNM_LEADING_DIR)
401 char *p = strrchr (buffer, '/');
411 if (!(options & EXCLUDE_ANCHORED))
424 /* Return true if EX excludes F. */
427 excluded_file_name (struct exclude const *ex, char const *f)
429 struct exclude_segment *seg;
431 char *filename = NULL;
433 /* If no patterns are given, the default is to include. */
437 /* Otherwise, the default is the opposite of the first option. */
438 excluded = !! (ex->head->options & EXCLUDE_INCLUDE);
439 /* Scan through the segments, seeing whether they change status from
440 excluded to included or vice versa. */
441 for (seg = ex->head; seg; seg = seg->next)
447 case exclude_pattern:
448 rc = excluded_file_pattern_p (seg, f);
453 filename = xmalloc (strlen (f) + 1);
454 rc = excluded_file_name_p (seg, f, filename);
470 /* Append to EX the exclusion PATTERN with OPTIONS. */
473 add_exclude (struct exclude *ex, char const *pattern, int options)
475 struct exclude_segment *seg;
477 if ((options & EXCLUDE_WILDCARDS)
478 && fnmatch_pattern_has_wildcards (pattern, options))
480 struct exclude_pattern *pat;
481 struct patopts *patopts;
483 if (ex->tail && ex->tail->type == exclude_pattern
484 && ((ex->tail->options & EXCLUDE_INCLUDE) ==
485 (options & EXCLUDE_INCLUDE)))
488 seg = new_exclude_segment (ex, exclude_pattern, options);
491 if (pat->exclude_count == pat->exclude_alloc)
492 pat->exclude = x2nrealloc (pat->exclude, &pat->exclude_alloc,
493 sizeof *pat->exclude);
494 patopts = &pat->exclude[pat->exclude_count++];
495 patopts->pattern = pattern;
496 patopts->options = options;
501 #define EXCLUDE_HASH_FLAGS (EXCLUDE_INCLUDE|EXCLUDE_ANCHORED|\
502 FNM_LEADING_DIR|FNM_CASEFOLD)
503 if (ex->tail && ex->tail->type == exclude_hash
504 && ((ex->tail->options & EXCLUDE_HASH_FLAGS) ==
505 (options & EXCLUDE_HASH_FLAGS)))
508 seg = new_exclude_segment (ex, exclude_hash, options);
510 str = xstrdup (pattern);
511 if (options & EXCLUDE_WILDCARDS)
512 unescape_pattern (str);
513 p = hash_insert (seg->v.table, str);
519 /* Use ADD_FUNC to append to EX the patterns in FILE_NAME, each with
520 OPTIONS. LINE_END terminates each pattern in the file. If
521 LINE_END is a space character, ignore trailing spaces and empty
522 lines in FILE. Return -1 on failure, 0 on success. */
525 add_exclude_file (void (*add_func) (struct exclude *, char const *, int),
526 struct exclude *ex, char const *file_name, int options,
529 bool use_stdin = file_name[0] == '-' && !file_name[1];
535 size_t buf_alloc = 0;
536 size_t buf_count = 0;
542 else if (! (in = fopen (file_name, "r")))
545 while ((c = getc (in)) != EOF)
547 if (buf_count == buf_alloc)
548 buf = x2realloc (buf, &buf_alloc);
549 buf[buf_count++] = c;
555 if (!use_stdin && fclose (in) != 0)
558 buf = xrealloc (buf, buf_count + 1);
559 buf[buf_count] = line_end;
560 lim = buf + buf_count + ! (buf_count == 0 || buf[buf_count - 1] == line_end);
563 for (p = buf; p < lim; p++)
566 char *pattern_end = p;
568 if (isspace ((unsigned char) line_end))
570 for (; ; pattern_end--)
571 if (pattern_end == pattern)
573 else if (! isspace ((unsigned char) pattern_end[-1]))
578 (*add_func) (ex, pattern, options);