VirtualBox

source: kBuild/vendor/grep/2.12/lib/exclude.c

Last change on this file was 2595, checked in by bird, 12 years ago

gnu grep version 2.12 (grep-2.12.tar.xz, md5sum=8d2f0346d08b13c18afb81f0e8aa1e2f)

  • Property svn:eol-style set to native
File size: 14.0 KB
Line 
1/* exclude.c -- exclude file names
2
3 Copyright (C) 1992-1994, 1997, 1999-2007, 2009-2012 Free Software
4 Foundation, Inc.
5
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.
10
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.
15
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/>. */
18
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. */
23
24#include <config.h>
25
26#include <stdbool.h>
27
28#include <ctype.h>
29#include <errno.h>
30#include <stddef.h>
31#include <stdio.h>
32#include <stdlib.h>
33#include <string.h>
34#include <wctype.h>
35
36#include "exclude.h"
37#include "hash.h"
38#include "mbuiter.h"
39#include "fnmatch.h"
40#include "xalloc.h"
41#include "verify.h"
42
43#if USE_UNLOCKED_IO
44# include "unlocked-io.h"
45#endif
46
47/* Non-GNU systems lack these options, so we don't need to check them. */
48#ifndef FNM_CASEFOLD
49# define FNM_CASEFOLD 0
50#endif
51#ifndef FNM_EXTMATCH
52# define FNM_EXTMATCH 0
53#endif
54#ifndef FNM_LEADING_DIR
55# define FNM_LEADING_DIR 0
56#endif
57
58verify (((EXCLUDE_ANCHORED | EXCLUDE_INCLUDE | EXCLUDE_WILDCARDS)
59 & (FNM_PATHNAME | FNM_NOESCAPE | FNM_PERIOD | FNM_LEADING_DIR
60 | FNM_CASEFOLD | FNM_EXTMATCH))
61 == 0);
62
63
64/* Exclusion patterns are grouped into a singly-linked list of
65 "exclusion segments". Each segment represents a set of patterns
66 that can be matches using the same algorithm. Non-wildcard
67 patterns are kept in hash tables, to speed up searches. Wildcard
68 patterns are stored as arrays of patterns. */
69
70
71/* An exclude pattern-options pair. The options are fnmatch options
72 ORed with EXCLUDE_* options. */
73
74struct patopts
75 {
76 char const *pattern;
77 int options;
78 };
79
80/* An array of pattern-options pairs. */
81
82struct exclude_pattern
83 {
84 struct patopts *exclude;
85 size_t exclude_alloc;
86 size_t exclude_count;
87 };
88
89enum exclude_type
90 {
91 exclude_hash, /* a hash table of excluded names */
92 exclude_pattern /* an array of exclude patterns */
93 };
94
95struct exclude_segment
96 {
97 struct exclude_segment *next; /* next segment in list */
98 enum exclude_type type; /* type of this segment */
99 int options; /* common options for this segment */
100 union
101 {
102 Hash_table *table; /* for type == exclude_hash */
103 struct exclude_pattern pat; /* for type == exclude_pattern */
104 } v;
105 };
106
107/* The exclude structure keeps a singly-linked list of exclude segments */
108struct exclude
109 {
110 struct exclude_segment *head, *tail;
111 };
112
113/* Return true if str has wildcard characters */
114bool
115fnmatch_pattern_has_wildcards (const char *str, int options)
116{
117 const char *cset = "\\?*[]";
118 if (options & FNM_NOESCAPE)
119 cset++;
120 while (*str)
121 {
122 size_t n = strcspn (str, cset);
123 if (str[n] == 0)
124 break;
125 else if (str[n] == '\\')
126 {
127 str += n + 1;
128 if (*str)
129 str++;
130 }
131 else
132 return true;
133 }
134 return false;
135}
136
137static void
138unescape_pattern (char *str)
139{
140 int inset = 0;
141 char *q = str;
142 do
143 {
144 if (inset)
145 {
146 if (*q == ']')
147 inset = 0;
148 }
149 else if (*q == '[')
150 inset = 1;
151 else if (*q == '\\')
152 q++;
153 }
154 while ((*str++ = *q++));
155}
156
157/* Return a newly allocated and empty exclude list. */
158
159struct exclude *
160new_exclude (void)
161{
162 return xzalloc (sizeof *new_exclude ());
163}
164
165/* Calculate the hash of string. */
166static size_t
167string_hasher (void const *data, size_t n_buckets)
168{
169 char const *p = data;
170 return hash_string (p, n_buckets);
171}
172
173/* Ditto, for case-insensitive hashes */
174static size_t
175string_hasher_ci (void const *data, size_t n_buckets)
176{
177 char const *p = data;
178 mbui_iterator_t iter;
179 size_t value = 0;
180
181 for (mbui_init (iter, p); mbui_avail (iter); mbui_advance (iter))
182 {
183 mbchar_t m = mbui_cur (iter);
184 wchar_t wc;
185
186 if (m.wc_valid)
187 wc = towlower (m.wc);
188 else
189 wc = *m.ptr;
190
191 value = (value * 31 + wc) % n_buckets;
192 }
193
194 return value;
195}
196
197/* compare two strings for equality */
198static bool
199string_compare (void const *data1, void const *data2)
200{
201 char const *p1 = data1;
202 char const *p2 = data2;
203 return strcmp (p1, p2) == 0;
204}
205
206/* compare two strings for equality, case-insensitive */
207static bool
208string_compare_ci (void const *data1, void const *data2)
209{
210 char const *p1 = data1;
211 char const *p2 = data2;
212 return mbscasecmp (p1, p2) == 0;
213}
214
215static void
216string_free (void *data)
217{
218 free (data);
219}
220
221/* Create new exclude segment of given TYPE and OPTIONS, and attach it
222 to the tail of list in EX */
223static struct exclude_segment *
224new_exclude_segment (struct exclude *ex, enum exclude_type type, int options)
225{
226 struct exclude_segment *sp = xzalloc (sizeof (struct exclude_segment));
227 sp->type = type;
228 sp->options = options;
229 switch (type)
230 {
231 case exclude_pattern:
232 break;
233
234 case exclude_hash:
235 sp->v.table = hash_initialize (0, NULL,
236 (options & FNM_CASEFOLD) ?
237 string_hasher_ci
238 : string_hasher,
239 (options & FNM_CASEFOLD) ?
240 string_compare_ci
241 : string_compare,
242 string_free);
243 break;
244 }
245 if (ex->tail)
246 ex->tail->next = sp;
247 else
248 ex->head = sp;
249 ex->tail = sp;
250 return sp;
251}
252
253/* Free a single exclude segment */
254static void
255free_exclude_segment (struct exclude_segment *seg)
256{
257 switch (seg->type)
258 {
259 case exclude_pattern:
260 free (seg->v.pat.exclude);
261 break;
262
263 case exclude_hash:
264 hash_free (seg->v.table);
265 break;
266 }
267 free (seg);
268}
269
270/* Free the storage associated with an exclude list. */
271void
272free_exclude (struct exclude *ex)
273{
274 struct exclude_segment *seg;
275 for (seg = ex->head; seg; )
276 {
277 struct exclude_segment *next = seg->next;
278 free_exclude_segment (seg);
279 seg = next;
280 }
281 free (ex);
282}
283
284/* Return zero if PATTERN matches F, obeying OPTIONS, except that
285 (unlike fnmatch) wildcards are disabled in PATTERN. */
286
287static int
288fnmatch_no_wildcards (char const *pattern, char const *f, int options)
289{
290 if (! (options & FNM_LEADING_DIR))
291 return ((options & FNM_CASEFOLD)
292 ? mbscasecmp (pattern, f)
293 : strcmp (pattern, f));
294 else if (! (options & FNM_CASEFOLD))
295 {
296 size_t patlen = strlen (pattern);
297 int r = strncmp (pattern, f, patlen);
298 if (! r)
299 {
300 r = f[patlen];
301 if (r == '/')
302 r = 0;
303 }
304 return r;
305 }
306 else
307 {
308 /* Walk through a copy of F, seeing whether P matches any prefix
309 of F.
310
311 FIXME: This is an O(N**2) algorithm; it should be O(N).
312 Also, the copy should not be necessary. However, fixing this
313 will probably involve a change to the mbs* API. */
314
315 char *fcopy = xstrdup (f);
316 char *p;
317 int r;
318 for (p = fcopy; ; *p++ = '/')
319 {
320 p = strchr (p, '/');
321 if (p)
322 *p = '\0';
323 r = mbscasecmp (pattern, fcopy);
324 if (!p || r <= 0)
325 break;
326 }
327 free (fcopy);
328 return r;
329 }
330}
331
332bool
333exclude_fnmatch (char const *pattern, char const *f, int options)
334{
335 int (*matcher) (char const *, char const *, int) =
336 (options & EXCLUDE_WILDCARDS
337 ? fnmatch
338 : fnmatch_no_wildcards);
339 bool matched = ((*matcher) (pattern, f, options) == 0);
340 char const *p;
341
342 if (! (options & EXCLUDE_ANCHORED))
343 for (p = f; *p && ! matched; p++)
344 if (*p == '/' && p[1] != '/')
345 matched = ((*matcher) (pattern, p + 1, options) == 0);
346
347 return matched;
348}
349
350/* Return true if the exclude_pattern segment SEG excludes F. */
351
352static bool
353excluded_file_pattern_p (struct exclude_segment const *seg, char const *f)
354{
355 size_t exclude_count = seg->v.pat.exclude_count;
356 struct patopts const *exclude = seg->v.pat.exclude;
357 size_t i;
358 bool excluded = !! (exclude[0].options & EXCLUDE_INCLUDE);
359
360 /* Scan through the options, until they change excluded */
361 for (i = 0; i < exclude_count; i++)
362 {
363 char const *pattern = exclude[i].pattern;
364 int options = exclude[i].options;
365 if (exclude_fnmatch (pattern, f, options))
366 return !excluded;
367 }
368 return excluded;
369}
370
371/* Return true if the exclude_hash segment SEG excludes F.
372 BUFFER is an auxiliary storage of the same length as F (with nul
373 terminator included) */
374static bool
375excluded_file_name_p (struct exclude_segment const *seg, char const *f,
376 char *buffer)
377{
378 int options = seg->options;
379 bool excluded = !! (options & EXCLUDE_INCLUDE);
380 Hash_table *table = seg->v.table;
381
382 do
383 {
384 /* initialize the pattern */
385 strcpy (buffer, f);
386
387 while (1)
388 {
389 if (hash_lookup (table, buffer))
390 return !excluded;
391 if (options & FNM_LEADING_DIR)
392 {
393 char *p = strrchr (buffer, '/');
394 if (p)
395 {
396 *p = 0;
397 continue;
398 }
399 }
400 break;
401 }
402
403 if (!(options & EXCLUDE_ANCHORED))
404 {
405 f = strchr (f, '/');
406 if (f)
407 f++;
408 }
409 else
410 break;
411 }
412 while (f);
413 return excluded;
414}
415
416/* Return true if EX excludes F. */
417
418bool
419excluded_file_name (struct exclude const *ex, char const *f)
420{
421 struct exclude_segment *seg;
422 bool excluded;
423 char *filename = NULL;
424
425 /* If no patterns are given, the default is to include. */
426 if (!ex->head)
427 return false;
428
429 /* Otherwise, the default is the opposite of the first option. */
430 excluded = !! (ex->head->options & EXCLUDE_INCLUDE);
431 /* Scan through the segments, seeing whether they change status from
432 excluded to included or vice versa. */
433 for (seg = ex->head; seg; seg = seg->next)
434 {
435 bool rc;
436
437 switch (seg->type)
438 {
439 case exclude_pattern:
440 rc = excluded_file_pattern_p (seg, f);
441 break;
442
443 case exclude_hash:
444 if (!filename)
445 filename = xmalloc (strlen (f) + 1);
446 rc = excluded_file_name_p (seg, f, filename);
447 break;
448
449 default:
450 abort ();
451 }
452 if (rc != excluded)
453 {
454 excluded = rc;
455 break;
456 }
457 }
458 free (filename);
459 return excluded;
460}
461
462/* Append to EX the exclusion PATTERN with OPTIONS. */
463
464void
465add_exclude (struct exclude *ex, char const *pattern, int options)
466{
467 struct exclude_segment *seg;
468
469 if ((options & EXCLUDE_WILDCARDS)
470 && fnmatch_pattern_has_wildcards (pattern, options))
471 {
472 struct exclude_pattern *pat;
473 struct patopts *patopts;
474
475 if (ex->tail && ex->tail->type == exclude_pattern
476 && ((ex->tail->options & EXCLUDE_INCLUDE) ==
477 (options & EXCLUDE_INCLUDE)))
478 seg = ex->tail;
479 else
480 seg = new_exclude_segment (ex, exclude_pattern, options);
481
482 pat = &seg->v.pat;
483 if (pat->exclude_count == pat->exclude_alloc)
484 pat->exclude = x2nrealloc (pat->exclude, &pat->exclude_alloc,
485 sizeof *pat->exclude);
486 patopts = &pat->exclude[pat->exclude_count++];
487 patopts->pattern = pattern;
488 patopts->options = options;
489 }
490 else
491 {
492 char *str, *p;
493#define EXCLUDE_HASH_FLAGS (EXCLUDE_INCLUDE|EXCLUDE_ANCHORED|\
494 FNM_LEADING_DIR|FNM_CASEFOLD)
495 if (ex->tail && ex->tail->type == exclude_hash
496 && ((ex->tail->options & EXCLUDE_HASH_FLAGS) ==
497 (options & EXCLUDE_HASH_FLAGS)))
498 seg = ex->tail;
499 else
500 seg = new_exclude_segment (ex, exclude_hash, options);
501
502 str = xstrdup (pattern);
503 if (options & EXCLUDE_WILDCARDS)
504 unescape_pattern (str);
505 p = hash_insert (seg->v.table, str);
506 if (p != str)
507 free (str);
508 }
509}
510
511/* Use ADD_FUNC to append to EX the patterns in FILE_NAME, each with
512 OPTIONS. LINE_END terminates each pattern in the file. If
513 LINE_END is a space character, ignore trailing spaces and empty
514 lines in FILE. Return -1 on failure, 0 on success. */
515
516int
517add_exclude_file (void (*add_func) (struct exclude *, char const *, int),
518 struct exclude *ex, char const *file_name, int options,
519 char line_end)
520{
521 bool use_stdin = file_name[0] == '-' && !file_name[1];
522 FILE *in;
523 char *buf = NULL;
524 char *p;
525 char const *pattern;
526 char const *lim;
527 size_t buf_alloc = 0;
528 size_t buf_count = 0;
529 int c;
530 int e = 0;
531
532 if (use_stdin)
533 in = stdin;
534 else if (! (in = fopen (file_name, "r")))
535 return -1;
536
537 while ((c = getc (in)) != EOF)
538 {
539 if (buf_count == buf_alloc)
540 buf = x2realloc (buf, &buf_alloc);
541 buf[buf_count++] = c;
542 }
543
544 if (ferror (in))
545 e = errno;
546
547 if (!use_stdin && fclose (in) != 0)
548 e = errno;
549
550 buf = xrealloc (buf, buf_count + 1);
551 buf[buf_count] = line_end;
552 lim = buf + buf_count + ! (buf_count == 0 || buf[buf_count - 1] == line_end);
553 pattern = buf;
554
555 for (p = buf; p < lim; p++)
556 if (*p == line_end)
557 {
558 char *pattern_end = p;
559
560 if (isspace ((unsigned char) line_end))
561 {
562 for (; ; pattern_end--)
563 if (pattern_end == pattern)
564 goto next_pattern;
565 else if (! isspace ((unsigned char) pattern_end[-1]))
566 break;
567 }
568
569 *pattern_end = '\0';
570 (*add_func) (ex, pattern, options);
571
572 next_pattern:
573 pattern = p + 1;
574 }
575
576 errno = e;
577 return e ? -1 : 0;
578}
Note: See TracBrowser for help on using the repository browser.

© 2024 Oracle Support Privacy / Do Not Sell My Info Terms of Use Trademark Policy Automated Access Etiquette