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 static void
 140 unescape_pattern (char *str)
 141 {
 142   int inset = 0;
 143   char *q = str;
 144   do
 145     {
 146       if (inset)
 147         {
 148           if (*q == ']')
 149             inset = 0;
 150         }
 151       else if (*q == '[')
 152         inset = 1;
 153       else if (*q == '\\')
 154         q++;
 155     }
 156   while ((*str++ = *q++));
 157 }
 158
 159 /* Return a newly allocated and empty exclude list.  */
 160
 161 struct exclude *
 162 new_exclude (void)
 163 {
 164   return xzalloc (sizeof *new_exclude ());
 165 }
 166
 167 /* Calculate the hash of string.  */
 168 static size_t
 169 string_hasher (void const *data, size_t n_buckets)
 170 {
 171   char const *p = data;
 172   return hash_string (p, n_buckets);
 173 }
 174
 175 /* Ditto, for case-insensitive hashes */
 176 static size_t
 177 string_hasher_ci (void const *data, size_t n_buckets)
 178 {
 179   char const *p = data;
 180   mbui_iterator_t iter;
 181   size_t value = 0;
 182
 183   for (mbui_init (iter, p); mbui_avail (iter); mbui_advance (iter))
 184     {
 185       mbchar_t m = mbui_cur (iter);
 186       wchar_t wc;
 187
 188       if (m.wc_valid)
 189         wc = towlower (m.wc);
 190       else
 191         wc = *m.ptr;
 192
 193       value = (value * 31 + wc) % n_buckets;
 194     }
 195
 196   return value;
 197 }
 198
 199 /* compare two strings for equality */
 200 static bool
 201 string_compare (void const *data1, void const *data2)
 202 {
 203   char const *p1 = data1;
 204   char const *p2 = data2;
 205   return strcmp (p1, p2) == 0;
 206 }
 207
 208 /* compare two strings for equality, case-insensitive */
 209 static bool
 210 string_compare_ci (void const *data1, void const *data2)
 211 {
 212   char const *p1 = data1;
 213   char const *p2 = data2;
 214   return mbscasecmp (p1, p2) == 0;
 215 }
 216
 217 static void
 218 string_free (void *data)
 219 {
 220   free (data);
 221 }
 222
 223 /* Create new exclude segment of given TYPE and OPTIONS, and attach it
 224    to the tail of list in EX */
 225 static struct exclude_segment *
 226 new_exclude_segment (struct exclude *ex, enum exclude_type type, int options)
 227 {
 228   struct exclude_segment *sp = xzalloc (sizeof (struct exclude_segment));
 229   sp->type = type;
 230   sp->options = options;
 231   switch (type)
 232     {
 233     case exclude_pattern:
 234       break;
 235
 236     case exclude_hash:
 237       sp->v.table = hash_initialize (0, NULL,
 238                                      (options & FNM_CASEFOLD) ?
 239                                        string_hasher_ci
 240                                        : string_hasher,
 241                                      (options & FNM_CASEFOLD) ?
 242                                        string_compare_ci
 243                                        : string_compare,
 244                                      string_free);
 245       break;
 246     }
 247   if (ex->tail)
 248     ex->tail->next = sp;
 249   else
 250     ex->head = sp;
 251   ex->tail = sp;
 252   return sp;
 253 }
 254
 255 /* Free a single exclude segment */
 256 static void
 257 free_exclude_segment (struct exclude_segment *seg)
 258 {
 259   switch (seg->type)
 260     {
 261     case exclude_pattern:
 262       free (seg->v.pat.exclude);
 263       break;
 264
 265     case exclude_hash:
 266       hash_free (seg->v.table);
 267       break;
 268     }
 269   free (seg);
 270 }
 271
 272 /* Free the storage associated with an exclude list.  */
 273 void
 274 free_exclude (struct exclude *ex)
 275 {
 276   struct exclude_segment *seg;
 277   for (seg = ex->head; seg; )
 278     {
 279       struct exclude_segment *next = seg->next;
 280       free_exclude_segment (seg);
 281       seg = next;
 282     }
 283   free (ex);
 284 }
 285
 286 /* Return zero if PATTERN matches F, obeying OPTIONS, except that
 287    (unlike fnmatch) wildcards are disabled in PATTERN.  */
 288
 289 static int
 290 fnmatch_no_wildcards (char const *pattern, char const *f, int options)
 291 {
 292   if (! (options & FNM_LEADING_DIR))
 293     return ((options & FNM_CASEFOLD)
 294             ? mbscasecmp (pattern, f)
 295             : strcmp (pattern, f));
 296   else if (! (options & FNM_CASEFOLD))
 297     {
 298       size_t patlen = strlen (pattern);
 299       int r = strncmp (pattern, f, patlen);
 300       if (! r)
 301         {
 302           r = f[patlen];
 303           if (r == '/')
 304             r = 0;
 305         }
 306       return r;
 307     }
 308   else
 309     {
 310       /* Walk through a copy of F, seeing whether P matches any prefix
 311          of F.
 312
 313          FIXME: This is an O(N**2) algorithm; it should be O(N).
 314          Also, the copy should not be necessary.  However, fixing this
 315          will probably involve a change to the mbs* API.  */
 316
 317       char *fcopy = xstrdup (f);
 318       char *p;
 319       int r;
 320       for (p = fcopy; ; *p++ = '/')
 321         {
 322           p = strchr (p, '/');
 323           if (p)
 324             *p = '\0';
 325           r = mbscasecmp (pattern, fcopy);
 326           if (!p || r <= 0)
 327             break;
 328         }
 329       free (fcopy);
 330       return r;
 331     }
 332 }
 333
 334 bool
 335 exclude_fnmatch (char const *pattern, char const *f, int options)
 336 {
 337   int (*matcher) (char const *, char const *, int) =
 338     (options & EXCLUDE_WILDCARDS
 339      ? fnmatch
 340      : fnmatch_no_wildcards);
 341   bool matched = ((*matcher) (pattern, f, options) == 0);
 342   char const *p;
 343
 344   if (! (options & EXCLUDE_ANCHORED))
 345     for (p = f; *p && ! matched; p++)
 346       if (*p == '/' && p[1] != '/')
 347         matched = ((*matcher) (pattern, p + 1, options) == 0);
 348
 349   return matched;
 350 }
 351
 352 /* Return true if the exclude_pattern segment SEG excludes F.  */
 353
 354 static bool
 355 excluded_file_pattern_p (struct exclude_segment const *seg, char const *f)
 356 {
 357   size_t exclude_count = seg->v.pat.exclude_count;
 358   struct patopts const *exclude = seg->v.pat.exclude;
 359   size_t i;
 360   bool excluded = !! (exclude[0].options & EXCLUDE_INCLUDE);
 361
 362   /* Scan through the options, until they change excluded */
 363   for (i = 0; i < exclude_count; i++)
 364     {
 365       char const *pattern = exclude[i].pattern;
 366       int options = exclude[i].options;
 367       if (exclude_fnmatch (pattern, f, options))
 368         return !excluded;
 369     }
 370   return excluded;
 371 }
 372
 373 /* Return true if the exclude_hash segment SEG excludes F.
 374    BUFFER is an auxiliary storage of the same length as F (with nul
 375    terminator included) */
 376 static bool
 377 excluded_file_name_p (struct exclude_segment const *seg, char const *f,
 378                       char *buffer)
 379 {
 380   int options = seg->options;
 381   bool excluded = !! (options & EXCLUDE_INCLUDE);
 382   Hash_table *table = seg->v.table;
 383
 384   do
 385     {
 386       /* initialize the pattern */
 387       strcpy (buffer, f);
 388
 389       while (1)
 390         {
 391           if (hash_lookup (table, buffer))
 392             return !excluded;
 393           if (options & FNM_LEADING_DIR)
 394             {
 395               char *p = strrchr (buffer, '/');
 396               if (p)
 397                 {
 398                   *p = 0;
 399                   continue;
 400                 }
 401             }
 402           break;
 403         }
 404
 405       if (!(options & EXCLUDE_ANCHORED))
 406         {
 407           f = strchr (f, '/');
 408           if (f)
 409             f++;
 410         }
 411       else
 412         break;
 413     }
 414   while (f);
 415   return excluded;
 416 }
 417
 418 /* Return true if EX excludes F.  */
 419
 420 bool
 421 excluded_file_name (struct exclude const *ex, char const *f)
 422 {
 423   struct exclude_segment *seg;
 424   bool excluded;
 425   char *filename = NULL;
 426
 427   /* If no patterns are given, the default is to include.  */
 428   if (!ex->head)
 429     return false;
 430
 431   /* Otherwise, the default is the opposite of the first option.  */
 432   excluded = !! (ex->head->options & EXCLUDE_INCLUDE);
 433   /* Scan through the segments, seeing whether they change status from
 434      excluded to included or vice versa.  */
 435   for (seg = ex->head; seg; seg = seg->next)
 436     {
 437       bool rc;
 438
 439       switch (seg->type)
 440         {
 441         case exclude_pattern:
 442           rc = excluded_file_pattern_p (seg, f);
 443           break;
 444
 445         case exclude_hash:
 446           if (!filename)
 447             filename = xmalloc (strlen (f) + 1);
 448           rc = excluded_file_name_p (seg, f, filename);
 449           break;
 450
 451         default:
 452           abort ();
 453         }
 454       if (rc != excluded)
 455         {
 456           excluded = rc;
 457           break;
 458         }
 459     }
 460   free (filename);
 461   return excluded;
 462 }
 463
 464 /* Append to EX the exclusion PATTERN with OPTIONS.  */
 465
 466 void
 467 add_exclude (struct exclude *ex, char const *pattern, int options)
 468 {
 469   struct exclude_segment *seg;
 470
 471   if ((options & EXCLUDE_WILDCARDS)
 472       && fnmatch_pattern_has_wildcards (pattern, options))
 473     {
 474       struct exclude_pattern *pat;
 475       struct patopts *patopts;
 476
 477       if (ex->tail && ex->tail->type == exclude_pattern
 478           && ((ex->tail->options & EXCLUDE_INCLUDE) ==
 479               (options & EXCLUDE_INCLUDE)))
 480         seg = ex->tail;
 481       else
 482         seg = new_exclude_segment (ex, exclude_pattern, options);
 483
 484       pat = &seg->v.pat;
 485       if (pat->exclude_count == pat->exclude_alloc)
 486         pat->exclude = x2nrealloc (pat->exclude, &pat->exclude_alloc,
 487                                    sizeof *pat->exclude);
 488       patopts = &pat->exclude[pat->exclude_count++];
 489       patopts->pattern = pattern;
 490       patopts->options = options;
 491     }
 492   else
 493     {
 494       char *str, *p;
 495 #define EXCLUDE_HASH_FLAGS (EXCLUDE_INCLUDE|EXCLUDE_ANCHORED|\
 496                             FNM_LEADING_DIR|FNM_CASEFOLD)
 497       if (ex->tail && ex->tail->type == exclude_hash
 498           && ((ex->tail->options & EXCLUDE_HASH_FLAGS) ==
 499               (options & EXCLUDE_HASH_FLAGS)))
 500         seg = ex->tail;
 501       else
 502         seg = new_exclude_segment (ex, exclude_hash, options);
 503
 504       str = xstrdup (pattern);
 505       if (options & EXCLUDE_WILDCARDS)
 506         unescape_pattern (str);
 507       p = hash_insert (seg->v.table, str);
 508       if (p != str)
 509         free (str);
 510     }
 511 }
 512
 513 /* Use ADD_FUNC to append to EX the patterns in FILE_NAME, each with
 514    OPTIONS.  LINE_END terminates each pattern in the file.  If
 515    LINE_END is a space character, ignore trailing spaces and empty
 516    lines in FILE.  Return -1 on failure, 0 on success.  */
 517
 518 int
 519 add_exclude_file (void (*add_func) (struct exclude *, char const *, int),
 520                   struct exclude *ex, char const *file_name, int options,
 521                   char line_end)
 522 {
 523   bool use_stdin = file_name[0] == '-' && !file_name[1];
 524   FILE *in;
 525   char *buf = NULL;
 526   char *p;
 527   char const *pattern;
 528   char const *lim;
 529   size_t buf_alloc = 0;
 530   size_t buf_count = 0;
 531   int c;
 532   int e = 0;
 533
 534   if (use_stdin)
 535     in = stdin;
 536   else if (! (in = fopen (file_name, "r")))
 537     return -1;
 538
 539   while ((c = getc (in)) != EOF)
 540     {
 541       if (buf_count == buf_alloc)
 542         buf = x2realloc (buf, &buf_alloc);
 543       buf[buf_count++] = c;
 544     }
 545
 546   if (ferror (in))
 547     e = errno;
 548
 549   if (!use_stdin && fclose (in) != 0)
 550     e = errno;
 551
 552   buf = xrealloc (buf, buf_count + 1);
 553   buf[buf_count] = line_end;
 554   lim = buf + buf_count + ! (buf_count == 0 || buf[buf_count - 1] == line_end);
 555   pattern = buf;
 556
 557   for (p = buf; p < lim; p++)
 558     if (*p == line_end)
 559       {
 560         char *pattern_end = p;
 561
 562         if (isspace ((unsigned char) line_end))
 563           {
 564             for (; ; pattern_end--)
 565               if (pattern_end == pattern)
 566                 goto next_pattern;
 567               else if (! isspace ((unsigned char) pattern_end[-1]))
 568                 break;
 569           }
 570
 571         *pattern_end = '\0';
 572         (*add_func) (ex, pattern, options);
 573
 574       next_pattern:
 575         pattern = p + 1;
 576       }
 577
 578   errno = e;
 579   return e ? -1 : 0;
 580 }