[PATCH] exclude: process exclude and include directives in order

[Paul Eggert]

This is part of a fix to a recently-reported grep bug.
I've tested this with tar and coreutils too -- it doesn't
affect them, since they never use EXCLUDE_INCLUDE.

---
 ChangeLog              |   18 ++++++++
 lib/exclude.c          |  111 +++++++++++++++++++++++-------------------------
 tests/test-exclude7.sh |    2 +-
 3 files changed, 72 insertions(+), 59 deletions(-)

diff --git a/ChangeLog b/ChangeLog
index ae5ca9e..1e384b3 100644
--- a/ChangeLog
+++ b/ChangeLog
@@ -1,5 +1,23 @@
 2012-04-29  Paul Eggert  <address@hidden>
 
+	exclude: process exclude and include directives in order
+       This restores the pre-2009 behavior, and is part of a fix of a
+       grep bug reported by Quentin Arce in
+       <http://lists.gnu.org/archive/html/bug-grep/2012-04/msg00056.html>.
+       * lib/exclude.c (struct exclude): Remove 'tail' member.
+       (new_exclude_segment): Prepend the new segment instead of appending.
+       Return void, since that's now more convenient.
+       (file_pattern_matches): Renamed from excluded_file_pattern_p.
+       (file_name_matches): Renamed from excluded_file_name_p.
+       (file_pattern_matches, file_name_matches):
+       Return true if the pattern matches, not if it excludes.
+       All callers changed.
+       (excluded_file_name): Process the list in reverse order;
+       since the list is now reversed this restores the pre-2009 behavior.
+       (add_exclude): Adjust to new reversed-order list.  Use local var
+       rather than macro, for clarity.
+       * tests/test-exclude7.sh: Adjust to corrected behavior.
+
        exclude: handle wildcards with FNM_NOESCAPE and with trailing \
        * lib/exclude.c (unescape_pattern): Don't worry about unescaped [;
        it's not possible here.  Handle the case of \ at end of pattern
diff --git a/lib/exclude.c b/lib/exclude.c
index 5aa6a7f..08a4829 100644
--- a/lib/exclude.c
+++ b/lib/exclude.c
@@ -104,10 +104,11 @@ struct exclude_segment
     } v;
   };
 
-/* The exclude structure keeps a singly-linked list of exclude segments */
+/* The exclude structure keeps a singly-linked list of exclude segments,
+   maintained in reverse order.  */
 struct exclude
   {
-    struct exclude_segment *head, *tail;
+    struct exclude_segment *head;
   };
 
 /* Return true if STR has or may have wildcards, when matched with OPTIONS.
@@ -211,8 +212,8 @@ string_free (void *data)
 }
 
 /* Create new exclude segment of given TYPE and OPTIONS, and attach it
-   to the tail of list in EX */
-static struct exclude_segment *
+   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));
@@ -234,12 +235,8 @@ new_exclude_segment (struct exclude *ex, enum exclude_type 
type, int options)
                                      string_free);
       break;
     }
-  if (ex->tail)
-    ex->tail->next = sp;
-  else
-    ex->head = sp;
-  ex->tail = sp;
-  return sp;
+  sp->next = ex->head;
+  ex->head = sp;
 }
 
 /* Free a single exclude segment */
@@ -339,36 +336,33 @@ exclude_fnmatch (char const *pattern, char const *f, int 
options)
   return matched;
 }
 
-/* Return true if the exclude_pattern segment SEG excludes F.  */
+/* Return true if the exclude_pattern segment SEG matches F.  */
 
 static bool
-excluded_file_pattern_p (struct exclude_segment const *seg, char const *f)
+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;
-  bool excluded = !! (exclude[0].options & EXCLUDE_INCLUDE);
 
-  /* Scan through the options, until they change excluded */
   for (i = 0; i < exclude_count; i++)
     {
       char const *pattern = exclude[i].pattern;
       int options = exclude[i].options;
       if (exclude_fnmatch (pattern, f, options))
-        return !excluded;
+        return true;
     }
-  return excluded;
+  return false;
 }
 
-/* Return true if the exclude_hash segment SEG excludes F.
+/* 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
-excluded_file_name_p (struct exclude_segment const *seg, char const *f,
-                      char *buffer)
+file_name_matches (struct exclude_segment const *seg, char const *f,
+                   char *buffer)
 {
   int options = seg->options;
-  bool excluded = !! (options & EXCLUDE_INCLUDE);
   Hash_table *table = seg->v.table;
 
   do
@@ -379,7 +373,7 @@ excluded_file_name_p (struct exclude_segment const *seg, 
char const *f,
       while (1)
         {
           if (hash_lookup (table, buffer))
-            return !excluded;
+            return true;
           if (options & FNM_LEADING_DIR)
             {
               char *p = strrchr (buffer, '/');
@@ -402,7 +396,8 @@ excluded_file_name_p (struct exclude_segment const *seg, 
char const *f,
         break;
     }
   while (f);
-  return excluded;
+
+  return false;
 }
 
 /* Return true if EX excludes F.  */
@@ -411,44 +406,46 @@ bool
 excluded_file_name (struct exclude const *ex, char const *f)
 {
   struct exclude_segment *seg;
-  bool excluded;
+  bool invert = false;
   char *filename = NULL;
 
   /* If no patterns are given, the default is to include.  */
   if (!ex->head)
     return false;
 
-  /* Otherwise, the default is the opposite of the first option.  */
-  excluded = !! (ex->head->options & EXCLUDE_INCLUDE);
-  /* Scan through the segments, seeing whether they change status from
-     excluded to included or vice versa.  */
-  for (seg = ex->head; seg; seg = seg->next)
+  /* 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)
     {
-      bool rc;
-
-      switch (seg->type)
+      if (seg->type == exclude_hash)
         {
-        case exclude_pattern:
-          rc = excluded_file_pattern_p (seg, f);
-          break;
-
-        case exclude_hash:
           if (!filename)
             filename = xmalloc (strlen (f) + 1);
-          rc = excluded_file_name_p (seg, f, filename);
-          break;
-
-        default:
-          abort ();
+          if (file_name_matches (seg, f, filename))
+            break;
         }
-      if (rc != excluded)
+      else
         {
-          excluded = rc;
+          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 excluded;
+  return invert ^ ! (seg->options & EXCLUDE_INCLUDE);
 }
 
 /* Append to EX the exclusion PATTERN with OPTIONS.  */
@@ -464,12 +461,11 @@ add_exclude (struct exclude *ex, char const *pattern, int 
options)
       struct exclude_pattern *pat;
       struct patopts *patopts;
 
-      if (ex->tail && ex->tail->type == exclude_pattern
-          && ((ex->tail->options & EXCLUDE_INCLUDE) ==
-              (options & EXCLUDE_INCLUDE)))
-        seg = ex->tail;
-      else
-        seg = new_exclude_segment (ex, exclude_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)
@@ -482,14 +478,13 @@ add_exclude (struct exclude *ex, char const *pattern, int 
options)
   else
     {
       char *str, *p;
-#define EXCLUDE_HASH_FLAGS (EXCLUDE_INCLUDE|EXCLUDE_ANCHORED|\
-                            FNM_LEADING_DIR|FNM_CASEFOLD)
-      if (ex->tail && ex->tail->type == exclude_hash
-          && ((ex->tail->options & EXCLUDE_HASH_FLAGS) ==
-              (options & EXCLUDE_HASH_FLAGS)))
-        seg = ex->tail;
-      else
-        seg = new_exclude_segment (ex, exclude_hash, options);
+      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)
diff --git a/tests/test-exclude7.sh b/tests/test-exclude7.sh
index a8ecf5b..2293eaf 100755
--- a/tests/test-exclude7.sh
+++ b/tests/test-exclude7.sh
@@ -28,8 +28,8 @@ Baz
 EOT
 
 cat > expected <<EOT
-bar: 1
 bar: 0
+bar: 1
 EOT
 
 test-exclude in -include in -- bar > out || exit $?
--
1.7.6.5