lib/exclude.c

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