kc3-lang/gnulib/lib/exclude.c

• Show log

  Commit

• Hash : d7cf3b8d
  Author :
  Date : 2018-06-25T21:45:23
  

  Continue to use spaces for indentation, not tabs.
  

Download

• lib/exclude.c

• /* exclude.c -- exclude file names
  
     Copyright (C) 1992-1994, 1997, 1999-2007, 2009-2018 Free Software
     Foundation, Inc.
  
     This program is free software: you can redistribute it and/or modify
     it under the terms of the GNU General Public License as published by
     the Free Software Foundation; either version 3 of the License, or
     (at your option) any later version.
  
     This program is distributed in the hope that it will be useful,
     but WITHOUT ANY WARRANTY; without even the implied warranty of
     MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
     GNU General Public License for more details.
  
     You should have received a copy of the GNU General Public License
     along with this program.  If not, see <https://www.gnu.org/licenses/>.  */
  
  /* Written by Paul Eggert <eggert@twinsun.com>
     and Sergey Poznyakoff <gray@gnu.org>.
     Thanks to Phil Proudman <phil@proudman51.freeserve.co.uk>
     for improvement suggestions. */
  
  #include <config.h>
  
  #include <stdbool.h>
  
  #include <ctype.h>
  #include <errno.h>
  #include <stddef.h>
  #include <stdio.h>
  #include <stdlib.h>
  #include <string.h>
  #include <wctype.h>
  #include <regex.h>
  
  #include "exclude.h"
  #include "hash.h"
  #include "mbuiter.h"
  #include "fnmatch.h"
  #include "xalloc.h"
  #include "verify.h"
  #include "filename.h"
  
  #if USE_UNLOCKED_IO
  # include "unlocked-io.h"
  #endif
  
  /* Non-GNU systems lack these options, so we don't need to check them.  */
  #ifndef FNM_CASEFOLD
  # define FNM_CASEFOLD 0
  #endif
  #ifndef FNM_EXTMATCH
  # define FNM_EXTMATCH 0
  #endif
  #ifndef FNM_LEADING_DIR
  # define FNM_LEADING_DIR 0
  #endif
  
  verify (((EXCLUDE_ANCHORED | EXCLUDE_INCLUDE | EXCLUDE_WILDCARDS)
           & (FNM_PATHNAME | FNM_NOESCAPE | FNM_PERIOD | FNM_LEADING_DIR
              | FNM_CASEFOLD | FNM_EXTMATCH))
          == 0);
  
  
  /* Exclusion patterns are grouped into a singly-linked list of
     "exclusion segments".  Each segment represents a set of patterns
     that can be matches using the same algorithm.  Non-wildcard
     patterns are kept in hash tables, to speed up searches.  Wildcard
     patterns are stored as arrays of patterns. */
  
  
  /* An exclude pattern-options pair.  The options are fnmatch options
     ORed with EXCLUDE_* options.  */
  
  struct patopts
    {
      int options;
      union
      {
        char const *pattern;
        regex_t re;
      } v;
    };
  
  /* An array of pattern-options pairs.  */
  
  struct exclude_pattern
    {
      struct patopts *exclude;
      size_t exclude_alloc;
      size_t exclude_count;
    };
  
  enum exclude_type
    {
      exclude_hash,                    /* a hash table of excluded names */
      exclude_pattern                  /* an array of exclude patterns */
    };
  
  struct exclude_segment
    {
      struct exclude_segment *next;    /* next segment in list */
      enum exclude_type type;          /* type of this segment */
      int options;                     /* common options for this segment */
      union
      {
        Hash_table *table;             /* for type == exclude_hash */
        struct exclude_pattern pat;    /* for type == exclude_pattern */
      } v;
    };
  
  struct pattern_buffer
    {
      struct pattern_buffer *next;
      char *base;
    };
  
  /* The exclude structure keeps a singly-linked list of exclude segments,
     maintained in reverse order.  */
  struct exclude
    {
      struct exclude_segment *head;
      struct pattern_buffer *patbuf;
    };
  
  /* Register BUF in the pattern buffer list of EX.  ADD_FUNC (see
     add_exclude_file and add_exclude_fp below) can use this function
     if it modifies the pattern, to ensure the allocated memory will be
     properly reclaimed upon calling free_exclude. */
  void
  exclude_add_pattern_buffer (struct exclude *ex, char *buf)
  {
    struct pattern_buffer *pbuf = xmalloc (sizeof *pbuf);
    pbuf->base = buf;
    pbuf->next = ex->patbuf;
    ex->patbuf = pbuf;
  }
  
  /* Return true if STR has or may have wildcards, when matched with OPTIONS.
     Return false if STR definitely does not have wildcards.  */
  bool
  fnmatch_pattern_has_wildcards (const char *str, int options)
  {
    while (1)
      {
        switch (*str++)
          {
          case '.':
          case '{':
          case '}':
          case '(':
          case ')':
            if (options & EXCLUDE_REGEX)
              return true;
            break;
  
          case '\\':
            if (options & EXCLUDE_REGEX)
              continue;
            else
              str += ! (options & FNM_NOESCAPE) && *str;
            break;
  
          case '+': case '@': case '!':
            if (options & FNM_EXTMATCH && *str == '(')
              return true;
            break;
  
          case '?': case '*': case '[':
            return true;
  
          case '\0':
            return false;
          }
      }
  }
  
  static void
  unescape_pattern (char *str)
  {
    char const *q = str;
    do
      q += *q == '\\' && q[1];
    while ((*str++ = *q++));
  }
  
  /* Return a newly allocated and empty exclude list.  */
  
  struct exclude *
  new_exclude (void)
  {
    return xzalloc (sizeof *new_exclude ());
  }
  
  /* Calculate the hash of string.  */
  static size_t
  string_hasher (void const *data, size_t n_buckets)
  {
    char const *p = data;
    return hash_string (p, n_buckets);
  }
  
  /* Ditto, for case-insensitive hashes */
  static size_t
  string_hasher_ci (void const *data, size_t n_buckets)
  {
    char const *p = data;
    mbui_iterator_t iter;
    size_t value = 0;
  
    for (mbui_init (iter, p); mbui_avail (iter); mbui_advance (iter))
      {
        mbchar_t m = mbui_cur (iter);
        wchar_t wc;
  
        if (m.wc_valid)
          wc = towlower (m.wc);
        else
          wc = *m.ptr;
  
        value = (value * 31 + wc) % n_buckets;
      }
  
    return value;
  }
  
  /* compare two strings for equality */
  static bool
  string_compare (void const *data1, void const *data2)
  {
    char const *p1 = data1;
    char const *p2 = data2;
    return strcmp (p1, p2) == 0;
  }
  
  /* compare two strings for equality, case-insensitive */
  static bool
  string_compare_ci (void const *data1, void const *data2)
  {
    char const *p1 = data1;
    char const *p2 = data2;
    return mbscasecmp (p1, p2) == 0;
  }
  
  static void
  string_free (void *data)
  {
    free (data);
  }
  
  /* Create new exclude segment of given TYPE and OPTIONS, and attach it
     to the head of EX.  */
  static void
  new_exclude_segment (struct exclude *ex, enum exclude_type type, int options)
  {
    struct exclude_segment *sp = xzalloc (sizeof (struct exclude_segment));
    sp->type = type;
    sp->options = options;
    switch (type)
      {
      case exclude_pattern:
        break;
  
      case exclude_hash:
        sp->v.table = hash_initialize (0, NULL,
                                       (options & FNM_CASEFOLD) ?
                                         string_hasher_ci
                                         : string_hasher,
                                       (options & FNM_CASEFOLD) ?
                                         string_compare_ci
                                         : string_compare,
                                       string_free);
        break;
      }
    sp->next = ex->head;
    ex->head = sp;
  }
  
  /* Free a single exclude segment */
  static void
  free_exclude_segment (struct exclude_segment *seg)
  {
    size_t i;
  
    switch (seg->type)
      {
      case exclude_pattern:
        for (i = 0; i < seg->v.pat.exclude_count; i++)
          {
            if (seg->v.pat.exclude[i].options & EXCLUDE_REGEX)
              regfree (&seg->v.pat.exclude[i].v.re);
          }
        free (seg->v.pat.exclude);
        break;
  
      case exclude_hash:
        hash_free (seg->v.table);
        break;
      }
    free (seg);
  }
  
  /* Free the storage associated with an exclude list.  */
  void
  free_exclude (struct exclude *ex)
  {
    struct exclude_segment *seg;
    struct pattern_buffer *pbuf;
  
    for (seg = ex->head; seg; )
      {
        struct exclude_segment *next = seg->next;
        free_exclude_segment (seg);
        seg = next;
      }
  
    for (pbuf = ex->patbuf; pbuf; )
      {
        struct pattern_buffer *next = pbuf->next;
        free (pbuf->base);
        free (pbuf);
        pbuf = next;
      }
  
    free (ex);
  }
  
  /* Return zero if PATTERN matches F, obeying OPTIONS, except that
     (unlike fnmatch) wildcards are disabled in PATTERN.  */
  
  static int
  fnmatch_no_wildcards (char const *pattern, char const *f, int options)
  {
    if (! (options & FNM_LEADING_DIR))
      return ((options & FNM_CASEFOLD)
              ? mbscasecmp (pattern, f)
              : strcmp (pattern, f));
    else if (! (options & FNM_CASEFOLD))
      {
        size_t patlen = strlen (pattern);
        int r = strncmp (pattern, f, patlen);
        if (! r)
          {
            r = f[patlen];
            if (r == '/')
              r = 0;
          }
        return r;
      }
    else
      {
        /* Walk through a copy of F, seeing whether P matches any prefix
           of F.
  
           FIXME: This is an O(N**2) algorithm; it should be O(N).
           Also, the copy should not be necessary.  However, fixing this
           will probably involve a change to the mbs* API.  */
  
        char *fcopy = xstrdup (f);
        char *p;
        int r;
        for (p = fcopy; ; *p++ = '/')
          {
            p = strchr (p, '/');
            if (p)
              *p = '\0';
            r = mbscasecmp (pattern, fcopy);
            if (!p || r <= 0)
              break;
          }
        free (fcopy);
        return r;
      }
  }
  
  bool
  exclude_fnmatch (char const *pattern, char const *f, int options)
  {
    int (*matcher) (char const *, char const *, int) =
      (options & EXCLUDE_WILDCARDS
       ? fnmatch
       : fnmatch_no_wildcards);
    bool matched = ((*matcher) (pattern, f, options) == 0);
    char const *p;
  
    if (! (options & EXCLUDE_ANCHORED))
      for (p = f; *p && ! matched; p++)
        if (*p == '/' && p[1] != '/')
          matched = ((*matcher) (pattern, p + 1, options) == 0);
  
    return matched;
  }
  
  static bool
  exclude_patopts (struct patopts const *opts, char const *f)
  {
    int options = opts->options;
  
    return (options & EXCLUDE_REGEX)
            ? regexec (&opts->v.re, f, 0, NULL, 0) == 0
            : exclude_fnmatch (opts->v.pattern, f, options);
  }
  
  /* Return true if the exclude_pattern segment SEG matches F.  */
  
  static bool
  file_pattern_matches (struct exclude_segment const *seg, char const *f)
  {
    size_t exclude_count = seg->v.pat.exclude_count;
    struct patopts const *exclude = seg->v.pat.exclude;
    size_t i;
  
    for (i = 0; i < exclude_count; i++)
      {
        if (exclude_patopts (exclude + i, f))
          return true;
      }
    return false;
  }
  
  /* Return true if the exclude_hash segment SEG matches F.
     BUFFER is an auxiliary storage of the same length as F (with nul
     terminator included) */
  static bool
  file_name_matches (struct exclude_segment const *seg, char const *f,
                     char *buffer)
  {
    int options = seg->options;
    Hash_table *table = seg->v.table;
  
    do
      {
        /* initialize the pattern */
        strcpy (buffer, f);
  
        while (1)
          {
            if (hash_lookup (table, buffer))
              return true;
            if (options & FNM_LEADING_DIR)
              {
                char *p = strrchr (buffer, '/');
                if (p)
                  {
                    *p = 0;
                    continue;
                  }
              }
            break;
          }
  
        if (!(options & EXCLUDE_ANCHORED))
          {
            f = strchr (f, '/');
            if (f)
              f++;
          }
        else
          break;
      }
    while (f);
  
    return false;
  }
  
  /* Return true if EX excludes F.  */
  
  bool
  excluded_file_name (struct exclude const *ex, char const *f)
  {
    struct exclude_segment *seg;
    bool invert = false;
    char *filename = NULL;
  
    /* If no patterns are given, the default is to include.  */
    if (!ex->head)
      return false;
  
    /* Scan through the segments, reporting the status of the first match.
       The segments are in reverse order, so this reports the status of
       the last match in the original option list.  */
    for (seg = ex->head; ; seg = seg->next)
      {
        if (seg->type == exclude_hash)
          {
            if (!filename)
              filename = xmalloc (strlen (f) + 1);
            if (file_name_matches (seg, f, filename))
              break;
          }
        else
          {
            if (file_pattern_matches (seg, f))
              break;
          }
  
        if (! seg->next)
          {
            /* If patterns are given but none match, the default is the
               opposite of the last segment (i.e., the first in the
               original option list).  For example, in the command
               'grep -r --exclude="a*" --include="*b" pat dir', the
               first option is --exclude so any file name matching
               neither a* nor *b is included.  */
            invert = true;
            break;
          }
      }
  
    free (filename);
    return invert ^ ! (seg->options & EXCLUDE_INCLUDE);
  }
  
  /* Append to EX the exclusion PATTERN with OPTIONS.  */
  
  void
  add_exclude (struct exclude *ex, char const *pattern, int options)
  {
    struct exclude_segment *seg;
    struct exclude_pattern *pat;
    struct patopts *patopts;
  
    if ((options & (EXCLUDE_REGEX|EXCLUDE_WILDCARDS))
        && fnmatch_pattern_has_wildcards (pattern, options))
      {
        if (! (ex->head && ex->head->type == exclude_pattern
               && ((ex->head->options & EXCLUDE_INCLUDE)
                   == (options & EXCLUDE_INCLUDE))))
          new_exclude_segment (ex, exclude_pattern, options);
  
        seg = ex->head;
  
        pat = &seg->v.pat;
        if (pat->exclude_count == pat->exclude_alloc)
          pat->exclude = x2nrealloc (pat->exclude, &pat->exclude_alloc,
                                     sizeof *pat->exclude);
        patopts = &pat->exclude[pat->exclude_count++];
  
        patopts->options = options;
        if (options & EXCLUDE_REGEX)
          {
            int rc;
            int cflags = REG_NOSUB|REG_EXTENDED|
                         ((options & FNM_CASEFOLD) ? REG_ICASE : 0);
  
            if (options & FNM_LEADING_DIR)
              {
                char *tmp;
                size_t len = strlen (pattern);
  
                while (len > 0 && ISSLASH (pattern[len-1]))
                  --len;
  
                if (len == 0)
                  rc = 1;
                else
                  {
                    tmp = xmalloc (len + 7);
                    memcpy (tmp, pattern, len);
                    strcpy (tmp + len, "(/.*)?");
                    rc = regcomp (&patopts->v.re, tmp, cflags);
                    free (tmp);
                  }
              }
            else
              rc = regcomp (&patopts->v.re, pattern, cflags);
  
            if (rc)
              {
                pat->exclude_count--;
                return;
              }
          }
        else
          {
            if (options & EXCLUDE_ALLOC)
              {
                pattern = xstrdup (pattern);
                exclude_add_pattern_buffer (ex, (char*) pattern);
              }
            patopts->v.pattern = pattern;
          }
      }
    else
      {
        char *str, *p;
        int exclude_hash_flags = (EXCLUDE_INCLUDE | EXCLUDE_ANCHORED
                                  | FNM_LEADING_DIR | FNM_CASEFOLD);
        if (! (ex->head && ex->head->type == exclude_hash
               && ((ex->head->options & exclude_hash_flags)
                   == (options & exclude_hash_flags))))
          new_exclude_segment (ex, exclude_hash, options);
        seg = ex->head;
  
        str = xstrdup (pattern);
        if ((options & (EXCLUDE_WILDCARDS | FNM_NOESCAPE)) == EXCLUDE_WILDCARDS)
          unescape_pattern (str);
        p = hash_insert (seg->v.table, str);
        if (p != str)
          free (str);
      }
  }
  
  /* Use ADD_FUNC to append to EX the patterns in FILE_NAME, each with
     OPTIONS.  LINE_END terminates each pattern in the file.  If
     LINE_END is a space character, ignore trailing spaces and empty
     lines in FP.  Return -1 on failure, 0 on success.  */
  
  int
  add_exclude_fp (void (*add_func) (struct exclude *, char const *, int, void *),
                  struct exclude *ex, FILE *fp, int options,
                  char line_end,
                  void *data)
  {
    char *buf = NULL;
    char *p;
    char *pattern;
    char const *lim;
    size_t buf_alloc = 0;
    size_t buf_count = 0;
    int c;
    int e = 0;
  
    while ((c = getc (fp)) != EOF)
      {
        if (buf_count == buf_alloc)
          buf = x2realloc (buf, &buf_alloc);
        buf[buf_count++] = c;
      }
  
    if (ferror (fp))
      e = errno;
  
    buf = xrealloc (buf, buf_count + 1);
    buf[buf_count] = line_end;
    lim = buf + buf_count + ! (buf_count == 0 || buf[buf_count - 1] == line_end);
  
    exclude_add_pattern_buffer (ex, buf);
  
    pattern = buf;
  
    for (p = buf; p < lim; p++)
      if (*p == line_end)
        {
          char *pattern_end = p;
  
          if (isspace ((unsigned char) line_end))
            {
              for (; ; pattern_end--)
                if (pattern_end == pattern)
                  goto next_pattern;
                else if (! isspace ((unsigned char) pattern_end[-1]))
                  break;
            }
  
          *pattern_end = '\0';
          (*add_func) (ex, pattern, options, data);
  
        next_pattern:
          pattern = p + 1;
        }
  
    errno = e;
    return e ? -1 : 0;
  }
  
  static void
  call_addfn (struct exclude *ex, char const *pattern, int options, void *data)
  {
    void (**addfnptr) (struct exclude *, char const *, int) = data;
    (*addfnptr) (ex, pattern, options);
  }
  
  int
  add_exclude_file (void (*add_func) (struct exclude *, char const *, int),
                    struct exclude *ex, char const *file_name, int options,
                    char line_end)
  {
    bool use_stdin = file_name[0] == '-' && !file_name[1];
    FILE *in;
    int rc = 0;
  
    if (use_stdin)
      in = stdin;
    else if (! (in = fopen (file_name, "r")))
      return -1;
  
    rc = add_exclude_fp (call_addfn, ex, in, options, line_end, &add_func);
  
    if (!use_stdin && fclose (in) != 0)
      rc = -1;
  
    return rc;
  }
  

Download