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-2014 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 #include <regex.h>
  38
  39 #include "exclude.h"
  40 #include "hash.h"
  41 #include "mbuiter.h"
  42 #include "fnmatch.h"
  43 #include "xalloc.h"
  44 #include "verify.h"
  45 #include "filename.h"
  46
  47 #if USE_UNLOCKED_IO
  48 # include "unlocked-io.h"
  49 #endif
  50
  51 /* Non-GNU systems lack these options, so we don't need to check them.  */
  52 #ifndef FNM_CASEFOLD
  53 # define FNM_CASEFOLD 0
  54 #endif
  55 #ifndef FNM_EXTMATCH
  56 # define FNM_EXTMATCH 0
  57 #endif
  58 #ifndef FNM_LEADING_DIR
  59 # define FNM_LEADING_DIR 0
  60 #endif
  61
  62 verify (((EXCLUDE_ANCHORED | EXCLUDE_INCLUDE | EXCLUDE_WILDCARDS)
  63          & (FNM_PATHNAME | FNM_NOESCAPE | FNM_PERIOD | FNM_LEADING_DIR
  64             | FNM_CASEFOLD | FNM_EXTMATCH))
  65         == 0);
  66
  67
  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. */
  73
  74
  75 /* An exclude pattern-options pair.  The options are fnmatch options
  76    ORed with EXCLUDE_* options.  */
  77
  78 struct patopts
  79   {
  80     int options;
  81     union
  82     {
  83       char const *pattern;
  84       regex_t re;
  85     } v;
  86   };
  87
  88 /* An array of pattern-options pairs.  */
  89
  90 struct exclude_pattern
  91   {
  92     struct patopts *exclude;
  93     size_t exclude_alloc;
  94     size_t exclude_count;
  95   };
  96
  97 enum exclude_type
  98   {
  99     exclude_hash,                    /* a hash table of excluded names */
 100     exclude_pattern                  /* an array of exclude patterns */
 101   };
 102
 103 struct exclude_segment
 104   {
 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 */
 108     union
 109     {
 110       Hash_table *table;             /* for type == exclude_hash */
 111       struct exclude_pattern pat;    /* for type == exclude_pattern */
 112     } v;
 113   };
 114
 115 struct pattern_buffer
 116   {
 117     struct pattern_buffer *next;
 118     char *base;
 119   };
 120
 121 /* The exclude structure keeps a singly-linked list of exclude segments,
 122    maintained in reverse order.  */
 123 struct exclude
 124   {
 125     struct exclude_segment *head;
 126     struct pattern_buffer *patbuf;
 127   };
 128
 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. */
 133 void
 134 exclude_add_pattern_buffer (struct exclude *ex, char *buf)
 135 {
 136   struct pattern_buffer *pbuf = xmalloc (sizeof *pbuf);
 137   pbuf->base = buf;
 138   pbuf->next = ex->patbuf;
 139   ex->patbuf = pbuf;
 140 }
 141
 142 /* Return true if STR has or may have wildcards, when matched with OPTIONS.
 143    Return false if STR definitely does not have wildcards.  */
 144 bool
 145 fnmatch_pattern_has_wildcards (const char *str, int options)
 146 {
 147   while (1)
 148     {
 149       switch (*str++)
 150         {
 151         case '.':
 152         case '{':
 153         case '}':
 154         case '(':
 155         case ')':
 156           if (options & EXCLUDE_REGEX)
 157             return true;
 158           break;
 159
 160         case '\\':
 161           if (options & EXCLUDE_REGEX)
 162             continue;
 163           else
 164             str += ! (options & FNM_NOESCAPE) && *str;
 165           break;
 166
 167         case '+': case '@': case '!':
 168           if (options & FNM_EXTMATCH && *str == '(')
 169             return true;
 170           break;
 171
 172         case '?': case '*': case '[':
 173           return true;
 174
 175         case '\0':
 176           return false;
 177         }
 178     }
 179 }
 180
 181 static void
 182 unescape_pattern (char *str)
 183 {
 184   char const *q = str;
 185   do
 186     q += *q == '\\' && q[1];
 187   while ((*str++ = *q++));
 188 }
 189
 190 /* Return a newly allocated and empty exclude list.  */
 191
 192 struct exclude *
 193 new_exclude (void)
 194 {
 195   return xzalloc (sizeof *new_exclude ());
 196 }
 197
 198 /* Calculate the hash of string.  */
 199 static size_t
 200 string_hasher (void const *data, size_t n_buckets)
 201 {
 202   char const *p = data;
 203   return hash_string (p, n_buckets);
 204 }
 205
 206 /* Ditto, for case-insensitive hashes */
 207 static size_t
 208 string_hasher_ci (void const *data, size_t n_buckets)
 209 {
 210   char const *p = data;
 211   mbui_iterator_t iter;
 212   size_t value = 0;
 213
 214   for (mbui_init (iter, p); mbui_avail (iter); mbui_advance (iter))
 215     {
 216       mbchar_t m = mbui_cur (iter);
 217       wchar_t wc;
 218
 219       if (m.wc_valid)
 220         wc = towlower (m.wc);
 221       else
 222         wc = *m.ptr;
 223
 224       value = (value * 31 + wc) % n_buckets;
 225     }
 226
 227   return value;
 228 }
 229
 230 /* compare two strings for equality */
 231 static bool
 232 string_compare (void const *data1, void const *data2)
 233 {
 234   char const *p1 = data1;
 235   char const *p2 = data2;
 236   return strcmp (p1, p2) == 0;
 237 }
 238
 239 /* compare two strings for equality, case-insensitive */
 240 static bool
 241 string_compare_ci (void const *data1, void const *data2)
 242 {
 243   char const *p1 = data1;
 244   char const *p2 = data2;
 245   return mbscasecmp (p1, p2) == 0;
 246 }
 247
 248 static void
 249 string_free (void *data)
 250 {
 251   free (data);
 252 }
 253
 254 /* Create new exclude segment of given TYPE and OPTIONS, and attach it
 255    to the head of EX.  */
 256 static void
 257 new_exclude_segment (struct exclude *ex, enum exclude_type type, int options)
 258 {
 259   struct exclude_segment *sp = xzalloc (sizeof (struct exclude_segment));
 260   sp->type = type;
 261   sp->options = options;
 262   switch (type)
 263     {
 264     case exclude_pattern:
 265       break;
 266
 267     case exclude_hash:
 268       sp->v.table = hash_initialize (0, NULL,
 269                                      (options & FNM_CASEFOLD) ?
 270                                        string_hasher_ci
 271                                        : string_hasher,
 272                                      (options & FNM_CASEFOLD) ?
 273                                        string_compare_ci
 274                                        : string_compare,
 275                                      string_free);
 276       break;
 277     }
 278   sp->next = ex->head;
 279   ex->head = sp;
 280 }
 281
 282 /* Free a single exclude segment */
 283 static void
 284 free_exclude_segment (struct exclude_segment *seg)
 285 {
 286   size_t i;
 287
 288   switch (seg->type)
 289     {
 290     case exclude_pattern:
 291       for (i = 0; i < seg->v.pat.exclude_count; i++)
 292         {
 293           if (seg->v.pat.exclude[i].options & EXCLUDE_REGEX)
 294             regfree (&seg->v.pat.exclude[i].v.re);
 295         }
 296       free (seg->v.pat.exclude);
 297       break;
 298
 299     case exclude_hash:
 300       hash_free (seg->v.table);
 301       break;
 302     }
 303   free (seg);
 304 }
 305
 306 /* Free the storage associated with an exclude list.  */
 307 void
 308 free_exclude (struct exclude *ex)
 309 {
 310   struct exclude_segment *seg;
 311   struct pattern_buffer *pbuf;
 312
 313   for (seg = ex->head; seg; )
 314     {
 315       struct exclude_segment *next = seg->next;
 316       free_exclude_segment (seg);
 317       seg = next;
 318     }
 319
 320   for (pbuf = ex->patbuf; pbuf; )
 321     {
 322       struct pattern_buffer *next = pbuf->next;
 323       free (pbuf->base);
 324       free (pbuf);
 325       pbuf = next;
 326     }
 327
 328   free (ex);
 329 }
 330
 331 /* Return zero if PATTERN matches F, obeying OPTIONS, except that
 332    (unlike fnmatch) wildcards are disabled in PATTERN.  */
 333
 334 static int
 335 fnmatch_no_wildcards (char const *pattern, char const *f, int options)
 336 {
 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))
 342     {
 343       size_t patlen = strlen (pattern);
 344       int r = strncmp (pattern, f, patlen);
 345       if (! r)
 346         {
 347           r = f[patlen];
 348           if (r == '/')
 349             r = 0;
 350         }
 351       return r;
 352     }
 353   else
 354     {
 355       /* Walk through a copy of F, seeing whether P matches any prefix
 356          of F.
 357
 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.  */
 361
 362       char *fcopy = xstrdup (f);
 363       char *p;
 364       int r;
 365       for (p = fcopy; ; *p++ = '/')
 366         {
 367           p = strchr (p, '/');
 368           if (p)
 369             *p = '\0';
 370           r = mbscasecmp (pattern, fcopy);
 371           if (!p || r <= 0)
 372             break;
 373         }
 374       free (fcopy);
 375       return r;
 376     }
 377 }
 378
 379 bool
 380 exclude_fnmatch (char const *pattern, char const *f, int options)
 381 {
 382   int (*matcher) (char const *, char const *, int) =
 383     (options & EXCLUDE_WILDCARDS
 384      ? fnmatch
 385      : fnmatch_no_wildcards);
 386   bool matched = ((*matcher) (pattern, f, options) == 0);
 387   char const *p;
 388
 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);
 393
 394   return matched;
 395 }
 396
 397 bool
 398 exclude_patopts (struct patopts const *opts, char const *f)
 399 {
 400   int options = opts->options;
 401
 402   return (options & EXCLUDE_REGEX)
 403           ? regexec (&opts->v.re, f, 0, NULL, 0) == 0
 404           : exclude_fnmatch (opts->v.pattern, f, options);
 405 }
 406
 407 /* Return true if the exclude_pattern segment SEG matches F.  */
 408
 409 static bool
 410 file_pattern_matches (struct exclude_segment const *seg, char const *f)
 411 {
 412   size_t exclude_count = seg->v.pat.exclude_count;
 413   struct patopts const *exclude = seg->v.pat.exclude;
 414   size_t i;
 415
 416   for (i = 0; i < exclude_count; i++)
 417     {
 418       if (exclude_patopts (exclude + i, f))
 419         return true;
 420     }
 421   return false;
 422 }
 423
 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) */
 427 static bool
 428 file_name_matches (struct exclude_segment const *seg, char const *f,
 429                    char *buffer)
 430 {
 431   int options = seg->options;
 432   Hash_table *table = seg->v.table;
 433
 434   do
 435     {
 436       /* initialize the pattern */
 437       strcpy (buffer, f);
 438
 439       while (1)
 440         {
 441           if (hash_lookup (table, buffer))
 442             return true;
 443           if (options & FNM_LEADING_DIR)
 444             {
 445               char *p = strrchr (buffer, '/');
 446               if (p)
 447                 {
 448                   *p = 0;
 449                   continue;
 450                 }
 451             }
 452           break;
 453         }
 454
 455       if (!(options & EXCLUDE_ANCHORED))
 456         {
 457           f = strchr (f, '/');
 458           if (f)
 459             f++;
 460         }
 461       else
 462         break;
 463     }
 464   while (f);
 465
 466   return false;
 467 }
 468
 469 /* Return true if EX excludes F.  */
 470
 471 bool
 472 excluded_file_name (struct exclude const *ex, char const *f)
 473 {
 474   struct exclude_segment *seg;
 475   bool invert = false;
 476   char *filename = NULL;
 477
 478   /* If no patterns are given, the default is to include.  */
 479   if (!ex->head)
 480     return false;
 481
 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)
 486     {
 487       if (seg->type == exclude_hash)
 488         {
 489           if (!filename)
 490             filename = xmalloc (strlen (f) + 1);
 491           if (file_name_matches (seg, f, filename))
 492             break;
 493         }
 494       else
 495         {
 496           if (file_pattern_matches (seg, f))
 497             break;
 498         }
 499
 500       if (! seg->next)
 501         {
 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.  */
 508           invert = true;
 509           break;
 510         }
 511     }
 512
 513   free (filename);
 514   return invert ^ ! (seg->options & EXCLUDE_INCLUDE);
 515 }
 516
 517 /* Append to EX the exclusion PATTERN with OPTIONS.  */
 518
 519 void
 520 add_exclude (struct exclude *ex, char const *pattern, int options)
 521 {
 522   struct exclude_segment *seg;
 523   struct exclude_pattern *pat;
 524   struct patopts *patopts;
 525
 526   if ((options & (EXCLUDE_REGEX|EXCLUDE_WILDCARDS))
 527       && fnmatch_pattern_has_wildcards (pattern, options))
 528     {
 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);
 533
 534       seg = ex->head;
 535
 536       pat = &seg->v.pat;
 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++];
 541
 542       patopts->options = options;
 543       if (options & EXCLUDE_REGEX)
 544         {
 545           int rc;
 546           int cflags = REG_NOSUB|REG_EXTENDED|
 547                        ((options & FNM_CASEFOLD) ? REG_ICASE : 0);
 548
 549           if (options & FNM_LEADING_DIR)
 550             {
 551               char *tmp;
 552               size_t len = strlen (pattern);
 553
 554               while (len > 0 && ISSLASH (pattern[len-1]))
 555                 --len;
 556
 557               if (len == 0)
 558                 rc = 1;
 559               else
 560                 {
 561                   tmp = xmalloc (len + 7);
 562                   memcpy (tmp, pattern, len);
 563                   strcpy (tmp + len, "(/.*)?");
 564                   rc = regcomp (&patopts->v.re, tmp, cflags);
 565                   free (tmp);
 566                 }
 567             }
 568           else
 569             rc = regcomp (&patopts->v.re, pattern, cflags);
 570
 571           if (rc)
 572             {
 573               pat->exclude_count--;
 574               return;
 575             }
 576         }
 577       else
 578         {
 579           if (options & EXCLUDE_ALLOC)
 580             {
 581               pattern = xstrdup (pattern);
 582               exclude_add_pattern_buffer (ex, (char*) pattern);
 583             }
 584           patopts->v.pattern = pattern;
 585         }
 586     }
 587   else
 588     {
 589       char *str, *p;
 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);
 596       seg = ex->head;
 597
 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);
 602       if (p != str)
 603         free (str);
 604     }
 605 }
 606
 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.  */
 611
 612 int
 613 add_exclude_fp (void (*add_func) (struct exclude *, char const *, int, void *),
 614                 struct exclude *ex, FILE *fp, int options,
 615                 char line_end,
 616                 void *data)
 617 {
 618   char *buf = NULL;
 619   char *p;
 620   char *pattern;
 621   char const *lim;
 622   size_t buf_alloc = 0;
 623   size_t buf_count = 0;
 624   int c;
 625   int e = 0;
 626
 627   while ((c = getc (fp)) != EOF)
 628     {
 629       if (buf_count == buf_alloc)
 630         buf = x2realloc (buf, &buf_alloc);
 631       buf[buf_count++] = c;
 632     }
 633
 634   if (ferror (fp))
 635     e = errno;
 636
 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);
 640
 641   exclude_add_pattern_buffer (ex, buf);
 642
 643   pattern = buf;
 644
 645   for (p = buf; p < lim; p++)
 646     if (*p == line_end)
 647       {
 648         char *pattern_end = p;
 649
 650         if (isspace ((unsigned char) line_end))
 651           {
 652             for (; ; pattern_end--)
 653               if (pattern_end == pattern)
 654                 goto next_pattern;
 655               else if (! isspace ((unsigned char) pattern_end[-1]))
 656                 break;
 657           }
 658
 659         *pattern_end = '\0';
 660         (*add_func) (ex, pattern, options, data);
 661
 662       next_pattern:
 663         pattern = p + 1;
 664       }
 665
 666   errno = e;
 667   return e ? -1 : 0;
 668 }
 669
 670 static void
 671 call_addfn (struct exclude *ex, char const *pattern, int options, void *data)
 672 {
 673   void (*addfn) (struct exclude *, char const *, int) = data;
 674   addfn (ex, pattern, options);
 675 }
 676
 677 int
 678 add_exclude_file (void (*add_func) (struct exclude *, char const *, int),
 679                   struct exclude *ex, char const *file_name, int options,
 680                   char line_end)
 681 {
 682   bool use_stdin = file_name[0] == '-' && !file_name[1];
 683   FILE *in;
 684   int rc = 0;
 685
 686   if (use_stdin)
 687     in = stdin;
 688   else if (! (in = fopen (file_name, "r")))
 689     return -1;
 690
 691   rc = add_exclude_fp (call_addfn, ex, in, options, line_end, add_func);
 692
 693   if (!use_stdin && fclose (in) != 0)
 694     rc = -1;
 695
 696   return rc;
 697 }