git.cworth.org Git - tar/blob - gnu/exclude.c

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