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

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