[PATCH v3 09/13] exclude: filter out patterns not applicable to the current directory

["Nguyễn Thái Ngọc Duy" <pclouds@gmail.com>]

.gitignore files are spread over directories (*) so that when we check
for ignored files at foo, we are not bothered by foo/bar/.gitignore,
which contains ignore rules for foo/bar only.

This is not enough. foo/.gitignore can contain the pattern
"foo/bar/*.c". When we stay at foo, we know that the pattern cannot
match anything. Similarly, the pattern "/autom4te.cache" at root
directory cannot match anything in foo. This patch attempts to filter
out such patterns to drive down matching cost.

The algorithm implemented here is a naive one. Patterns can be either
active or passive:

 - When we enter a new directory (e.g. from root to foo), currently
   active patterns may no longer be applicable and can be turned to
   passive.

 - On the opposite, when we leave a directory (foo back to roo),
   passive patterns may come alive again.

We could do smarter things. But this implementation cuts a big portion
of cost already (and solves the "root .gitignore is evil" problem).
There's probably no need to be smart.

(*) this design forces us to try to find .gitignore at every
directory. On webkit.git that equals to 6k open syscalls. It feels
like ".svn on every directory" again. I suggest we add
~/.gitignore.master, containing the list .gitignore files in
worktree. If this file exists, we don't poke at every directory for
.gitignore.

treat_leading_path:   0.000  0.000
read_directory:       3.455  2.879
+treat_one_path:      2.203  1.620
++is_excluded:        2.000  1.416
+++prep_exclude:      0.171  0.198
+++matching:          1.509  0.904
++dir_exist:          0.036  0.035
++index_name_exists:  0.292  0.289
lazy_init_name_hash:  0.257  0.257
+simplify_away:       0.084  0.085
+dir_add_name:        0.446  0.446

Signed-off-by: Nguyễn Thái Ngọc Duy <pclouds@gmail.com>
---
 dir.c | 93 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++--
 dir.h |  1 +
 2 files changed, 92 insertions(+), 2 deletions(-)

diff --git a/dir.c b/dir.c
index 932fd2f..c57bf06 100644
--- a/dir.c
+++ b/dir.c
@@ -458,7 +458,7 @@ void add_exclude(const char *string, const char *base,
 	x->base = base;
 	x->baselen = baselen;
 	x->pattern_baselen = pattern_baselen;
-	x->flags = flags;
+	x->flags = flags | EXC_FLAG_ACTIVE;
 	x->srcpos = srcpos;
 	ALLOC_GROW(el->excludes, el->nr + 1, el->alloc);
 	el->excludes[el->nr++] = x;
@@ -591,6 +591,87 @@ void add_excludes_from_file(struct dir_struct *dir, const char *fname)
 		die("cannot use %s as an exclude file", fname);
 }
 
+static int pattern_match_base(struct dir_struct *dir,
+			      const char *base, int baselen,
+			      const struct exclude *exc)
+{
+	const char *pattern;
+
+	/*
+	 * TODO: if a patterns come from a .gitignore, exc->base would
+	 * be the same for all of them. We could compare once and
+	 * reuse the result, instead of perform the comparison per
+	 * pattern like this.
+	 */
+	if (exc->baselen) {
+		if (baselen < exc->baselen + 1)
+			return 0;
+
+		if (base[exc->baselen] != '/' ||
+		    memcmp(base, exc->base, exc->baselen))
+			return 0;
+
+		base += exc->baselen + 1;
+		baselen -= exc->baselen + 1;
+	}
+
+	if (baselen != exc->pattern_baselen)
+		return 0;
+
+	if (exc->pattern_baselen) {
+		pattern = exc->pattern;
+		if (*pattern == '/')
+			pattern++;
+		if (memcmp(base, pattern, exc->pattern_baselen))
+			return 0;
+	}
+
+	return 1;
+}
+
+/*
+ * If pushed is non-zero, we have entered a new directory. Some
+ * pathname patterns may no longer applicable. Go over all active
+ * patterns and disable them if so.
+ *
+ * If popped is non-zero, we have left a directory. Inactive patterns
+ * may be applicable again. Go over them and re-enable if so.
+ */
+static void scan_patterns(struct dir_struct *dir,
+			  const char *base, int baselen,
+			  int pushed, int popped)
+{
+	int i, j, k;
+
+	for (i = EXC_CMDL; i <= EXC_FILE; i++) {
+		struct exclude_list_group *group = &dir->exclude_list_group[i];
+		for (j = group->nr - 1; j >= 0; j--) {
+			struct exclude_list *list = &group->el[j];
+			for (k = 0; k < list->nr; k++) {
+				struct exclude *exc = list->excludes[k];
+
+				/*
+				 * No base (i.e. EXC_FLAG_NODIR) or
+				 * applicable to many bases ("**"
+				 * patterns)
+				 */
+				if (exc->pattern_baselen == -1)
+					continue;
+
+				if (exc->flags & EXC_FLAG_ACTIVE) {
+					if (pushed &&
+					    !pattern_match_base(dir, base, baselen, exc))
+						exc->flags &= ~EXC_FLAG_ACTIVE;
+				} else {
+					if (popped &&
+					    pattern_match_base(dir, base, baselen, exc))
+						exc->flags |= EXC_FLAG_ACTIVE;
+				}
+			}
+		}
+	}
+}
+
 /*
  * Loads the per-directory exclude list for the substring of base
  * which has a char length of baselen.
@@ -600,7 +681,7 @@ static void prep_exclude(struct dir_struct *dir, const char *base, int baselen)
 	struct exclude_list_group *group;
 	struct exclude_list *el;
 	struct exclude_stack *stk = NULL;
-	int current;
+	int current, popped = 0, pushed = 0;
 
 	if ((!dir->exclude_per_dir) ||
 	    (baselen + strlen(dir->exclude_per_dir) >= PATH_MAX))
@@ -621,6 +702,7 @@ static void prep_exclude(struct dir_struct *dir, const char *base, int baselen)
 		clear_exclude_list(el);
 		free(stk);
 		group->nr--;
+		popped++;
 	}
 
 	/* Read from the parent directories and push them down. */
@@ -659,8 +741,12 @@ static void prep_exclude(struct dir_struct *dir, const char *base, int baselen)
 					       el, 1);
 		dir->exclude_stack = stk;
 		current = stk->baselen;
+		pushed++;
 	}
 	dir->basebuf[baselen] = '\0';
+
+	if (pushed | popped)
+		scan_patterns(dir, base, baselen, pushed, popped);
 }
 
 int match_basename(const char *basename, int basenamelen,
@@ -755,6 +841,9 @@ static struct exclude *last_exclude_matching_from_list(const char *pathname,
 		const char *exclude = x->pattern;
 		int prefix = x->nowildcardlen;
 
+		if (!(x->flags & EXC_FLAG_ACTIVE))
+			continue;
+
 		if (x->flags & EXC_FLAG_MUSTBEDIR) {
 			if (*dtype == DT_UNKNOWN)
 				*dtype = get_dtype(NULL, pathname, pathlen);
diff --git a/dir.h b/dir.h
index cb50a85..247bfda 100644
--- a/dir.h
+++ b/dir.h
@@ -14,6 +14,7 @@ struct dir_entry {
 #define EXC_FLAG_ENDSWITH 4
 #define EXC_FLAG_MUSTBEDIR 8
 #define EXC_FLAG_NEGATIVE 16
+#define EXC_FLAG_ACTIVE 32
 
 /*
  * Each excludes file will be parsed into a fresh exclude_list which
-- 
1.8.1.2.536.gf441e6d