pintos-os.org Git - pspp/blob - lib/exclude.c

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