.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 <pclo...@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

--
To unsubscribe from this list: send the line "unsubscribe git" in
the body of a message to majord...@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html

Reply via email to