git.gag.com Git - debian/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-1994, 1997, 1999-2007, 2009-2013 Free Software
   6    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    maintained in reverse order.  */
 111 struct exclude
 112   {
 113     struct exclude_segment *head;
 114   };
 115
 116 /* Return true if STR has or may have wildcards, when matched with OPTIONS.
 117    Return false if STR definitely does not have wildcards.  */
 118 bool
 119 fnmatch_pattern_has_wildcards (const char *str, int options)
 120 {
 121   while (1)
 122     {
 123       switch (*str++)
 124         {
 125         case '\\':
 126           str += ! (options & FNM_NOESCAPE) && *str;
 127           break;
 128
 129         case '+': case '@': case '!':
 130           if (options & FNM_EXTMATCH && *str == '(')
 131             return true;
 132           break;
 133
 134         case '?': case '*': case '[':
 135           return true;
 136
 137         case '\0':
 138           return false;
 139         }
 140     }
 141 }
 142
 143 static void
 144 unescape_pattern (char *str)
 145 {
 146   char const *q = str;
 147   do
 148     q += *q == '\\' && q[1];
 149   while ((*str++ = *q++));
 150 }
 151
 152 /* Return a newly allocated and empty exclude list.  */
 153
 154 struct exclude *
 155 new_exclude (void)
 156 {
 157   return xzalloc (sizeof *new_exclude ());
 158 }
 159
 160 /* Calculate the hash of string.  */
 161 static size_t
 162 string_hasher (void const *data, size_t n_buckets)
 163 {
 164   char const *p = data;
 165   return hash_string (p, n_buckets);
 166 }
 167
 168 /* Ditto, for case-insensitive hashes */
 169 static size_t
 170 string_hasher_ci (void const *data, size_t n_buckets)
 171 {
 172   char const *p = data;
 173   mbui_iterator_t iter;
 174   size_t value = 0;
 175
 176   for (mbui_init (iter, p); mbui_avail (iter); mbui_advance (iter))
 177     {
 178       mbchar_t m = mbui_cur (iter);
 179       wchar_t wc;
 180
 181       if (m.wc_valid)
 182         wc = towlower (m.wc);
 183       else
 184         wc = *m.ptr;
 185
 186       value = (value * 31 + wc) % n_buckets;
 187     }
 188
 189   return value;
 190 }
 191
 192 /* compare two strings for equality */
 193 static bool
 194 string_compare (void const *data1, void const *data2)
 195 {
 196   char const *p1 = data1;
 197   char const *p2 = data2;
 198   return strcmp (p1, p2) == 0;
 199 }
 200
 201 /* compare two strings for equality, case-insensitive */
 202 static bool
 203 string_compare_ci (void const *data1, void const *data2)
 204 {
 205   char const *p1 = data1;
 206   char const *p2 = data2;
 207   return mbscasecmp (p1, p2) == 0;
 208 }
 209
 210 static void
 211 string_free (void *data)
 212 {
 213   free (data);
 214 }
 215
 216 /* Create new exclude segment of given TYPE and OPTIONS, and attach it
 217    to the head of EX.  */
 218 static void
 219 new_exclude_segment (struct exclude *ex, enum exclude_type type, int options)
 220 {
 221   struct exclude_segment *sp = xzalloc (sizeof (struct exclude_segment));
 222   sp->type = type;
 223   sp->options = options;
 224   switch (type)
 225     {
 226     case exclude_pattern:
 227       break;
 228
 229     case exclude_hash:
 230       sp->v.table = hash_initialize (0, NULL,
 231                                      (options & FNM_CASEFOLD) ?
 232                                        string_hasher_ci
 233                                        : string_hasher,
 234                                      (options & FNM_CASEFOLD) ?
 235                                        string_compare_ci
 236                                        : string_compare,
 237                                      string_free);
 238       break;
 239     }
 240   sp->next = ex->head;
 241   ex->head = sp;
 242 }
 243
 244 /* Free a single exclude segment */
 245 static void
 246 free_exclude_segment (struct exclude_segment *seg)
 247 {
 248   switch (seg->type)
 249     {
 250     case exclude_pattern:
 251       free (seg->v.pat.exclude);
 252       break;
 253
 254     case exclude_hash:
 255       hash_free (seg->v.table);
 256       break;
 257     }
 258   free (seg);
 259 }
 260
 261 /* Free the storage associated with an exclude list.  */
 262 void
 263 free_exclude (struct exclude *ex)
 264 {
 265   struct exclude_segment *seg;
 266   for (seg = ex->head; seg; )
 267     {
 268       struct exclude_segment *next = seg->next;
 269       free_exclude_segment (seg);
 270       seg = next;
 271     }
 272   free (ex);
 273 }
 274
 275 /* Return zero if PATTERN matches F, obeying OPTIONS, except that
 276    (unlike fnmatch) wildcards are disabled in PATTERN.  */
 277
 278 static int
 279 fnmatch_no_wildcards (char const *pattern, char const *f, int options)
 280 {
 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))
 286     {
 287       size_t patlen = strlen (pattern);
 288       int r = strncmp (pattern, f, patlen);
 289       if (! r)
 290         {
 291           r = f[patlen];
 292           if (r == '/')
 293             r = 0;
 294         }
 295       return r;
 296     }
 297   else
 298     {
 299       /* Walk through a copy of F, seeing whether P matches any prefix
 300          of F.
 301
 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.  */
 305
 306       char *fcopy = xstrdup (f);
 307       char *p;
 308       int r;
 309       for (p = fcopy; ; *p++ = '/')
 310         {
 311           p = strchr (p, '/');
 312           if (p)
 313             *p = '\0';
 314           r = mbscasecmp (pattern, fcopy);
 315           if (!p || r <= 0)
 316             break;
 317         }
 318       free (fcopy);
 319       return r;
 320     }
 321 }
 322
 323 bool
 324 exclude_fnmatch (char const *pattern, char const *f, int options)
 325 {
 326   int (*matcher) (char const *, char const *, int) =
 327     (options & EXCLUDE_WILDCARDS
 328      ? fnmatch
 329      : fnmatch_no_wildcards);
 330   bool matched = ((*matcher) (pattern, f, options) == 0);
 331   char const *p;
 332
 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);
 337
 338   return matched;
 339 }
 340
 341 /* Return true if the exclude_pattern segment SEG matches F.  */
 342
 343 static bool
 344 file_pattern_matches (struct exclude_segment const *seg, char const *f)
 345 {
 346   size_t exclude_count = seg->v.pat.exclude_count;
 347   struct patopts const *exclude = seg->v.pat.exclude;
 348   size_t i;
 349
 350   for (i = 0; i < exclude_count; i++)
 351     {
 352       char const *pattern = exclude[i].pattern;
 353       int options = exclude[i].options;
 354       if (exclude_fnmatch (pattern, f, options))
 355         return true;
 356     }
 357   return false;
 358 }
 359
 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) */
 363 static bool
 364 file_name_matches (struct exclude_segment const *seg, char const *f,
 365                    char *buffer)
 366 {
 367   int options = seg->options;
 368   Hash_table *table = seg->v.table;
 369
 370   do
 371     {
 372       /* initialize the pattern */
 373       strcpy (buffer, f);
 374
 375       while (1)
 376         {
 377           if (hash_lookup (table, buffer))
 378             return true;
 379           if (options & FNM_LEADING_DIR)
 380             {
 381               char *p = strrchr (buffer, '/');
 382               if (p)
 383                 {
 384                   *p = 0;
 385                   continue;
 386                 }
 387             }
 388           break;
 389         }
 390
 391       if (!(options & EXCLUDE_ANCHORED))
 392         {
 393           f = strchr (f, '/');
 394           if (f)
 395             f++;
 396         }
 397       else
 398         break;
 399     }
 400   while (f);
 401
 402   return false;
 403 }
 404
 405 /* Return true if EX excludes F.  */
 406
 407 bool
 408 excluded_file_name (struct exclude const *ex, char const *f)
 409 {
 410   struct exclude_segment *seg;
 411   bool invert = false;
 412   char *filename = NULL;
 413
 414   /* If no patterns are given, the default is to include.  */
 415   if (!ex->head)
 416     return false;
 417
 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)
 422     {
 423       if (seg->type == exclude_hash)
 424         {
 425           if (!filename)
 426             filename = xmalloc (strlen (f) + 1);
 427           if (file_name_matches (seg, f, filename))
 428             break;
 429         }
 430       else
 431         {
 432           if (file_pattern_matches (seg, f))
 433             break;
 434         }
 435
 436       if (! seg->next)
 437         {
 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.  */
 444           invert = true;
 445           break;
 446         }
 447     }
 448
 449   free (filename);
 450   return invert ^ ! (seg->options & EXCLUDE_INCLUDE);
 451 }
 452
 453 /* Append to EX the exclusion PATTERN with OPTIONS.  */
 454
 455 void
 456 add_exclude (struct exclude *ex, char const *pattern, int options)
 457 {
 458   struct exclude_segment *seg;
 459
 460   if ((options & EXCLUDE_WILDCARDS)
 461       && fnmatch_pattern_has_wildcards (pattern, options))
 462     {
 463       struct exclude_pattern *pat;
 464       struct patopts *patopts;
 465
 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);
 470       seg = ex->head;
 471
 472       pat = &seg->v.pat;
 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;
 479     }
 480   else
 481     {
 482       char *str, *p;
 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);
 489       seg = ex->head;
 490
 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);
 495       if (p != str)
 496         free (str);
 497     }
 498 }
 499
 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.  */
 504
 505 int
 506 add_exclude_file (void (*add_func) (struct exclude *, char const *, int),
 507                   struct exclude *ex, char const *file_name, int options,
 508                   char line_end)
 509 {
 510   bool use_stdin = file_name[0] == '-' && !file_name[1];
 511   FILE *in;
 512   char *buf = NULL;
 513   char *p;
 514   char const *pattern;
 515   char const *lim;
 516   size_t buf_alloc = 0;
 517   size_t buf_count = 0;
 518   int c;
 519   int e = 0;
 520
 521   if (use_stdin)
 522     in = stdin;
 523   else if (! (in = fopen (file_name, "r")))
 524     return -1;
 525
 526   while ((c = getc (in)) != EOF)
 527     {
 528       if (buf_count == buf_alloc)
 529         buf = x2realloc (buf, &buf_alloc);
 530       buf[buf_count++] = c;
 531     }
 532
 533   if (ferror (in))
 534     e = errno;
 535
 536   if (!use_stdin && fclose (in) != 0)
 537     e = errno;
 538
 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);
 542   pattern = buf;
 543
 544   for (p = buf; p < lim; p++)
 545     if (*p == line_end)
 546       {
 547         char *pattern_end = p;
 548
 549         if (isspace ((unsigned char) line_end))
 550           {
 551             for (; ; pattern_end--)
 552               if (pattern_end == pattern)
 553                 goto next_pattern;
 554               else if (! isspace ((unsigned char) pattern_end[-1]))
 555                 break;
 556           }
 557
 558         *pattern_end = '\0';
 559         (*add_func) (ex, pattern, options);
 560
 561       next_pattern:
 562         pattern = p + 1;
 563       }
 564
 565   errno = e;
 566   return e ? -1 : 0;
 567 }