dir.c: don't exclude whole dir prematurely if neg pattern may match

If there is a pattern "!foo/bar", this patch makes it not exclude "foo"
right away. This gives us a chance to examine "foo" and re-include
"foo/bar".

In order for it to detect that the directory under examination should
not be excluded right away, in other words it is a parent directory of a
negative pattern, the "directory path" of the negative pattern must be
literal. Patterns like "!f?o/bar" can't stop "foo" from being excluded.

Basename matching (i.e. "no slashes in the pattern") or must-be-dir
matching (i.e. "trailing slash in the pattern") does not work well with
this. For example, if we descend in "foo" and are examining "foo/abc",
current code for "foo/" pattern will check if path "foo/abc", not "foo",
is a directory. The same problem with basename matching. These may need
big code reorg to make it work.

Signed-off-by: Nguyễn Thái Ngọc Duy <pclouds@gmail.com>
Signed-off-by: Junio C Hamano <gitster@pobox.com>

3 files changed, 117 insertions, 5 deletions

diff --git a/Documentation/gitignore.txt b/Documentation/gitignore.txt
index 4fd04423e9..9cce703c5a 100644
--- a/Documentation/gitignore.txt
+++ b/Documentation/gitignore.txt
@@ -82,12 +82,12 @@ PATTERN FORMAT
 
  - An optional prefix "`!`" which negates the pattern; any
    matching file excluded by a previous pattern will become
-   included again. It is not possible to re-include a file if a parent
-   directory of that file is excluded. Git doesn't list excluded
-   directories for performance reasons, so any patterns on contained
-   files have no effect, no matter where they are defined.
+   included again.
    Put a backslash ("`\`") in front of the first "`!`" for patterns
    that begin with a literal "`!`", for example, "`\!important!.txt`".
+   It is possible to re-include a file if a parent directory of that
+   file is excluded if certain conditions are met. See section NOTES
+   for detail.
 
  - If the pattern ends with a slash, it is removed for the
    purpose of the following description, but it would only find
@@ -141,6 +141,21 @@ not tracked by Git remain untracked.
 To stop tracking a file that is currently tracked, use
 'git rm --cached'.
 
+To re-include files or directories when their parent directory is
+excluded, the following conditions must be met:
+
+ - The rules to exclude a directory and re-include a subset back must
+   be in the same .gitignore file.
+
+ - The directory part in the re-include rules must be literal (i.e. no
+   wildcards)
+
+ - The rules to exclude the parent directory must not end with a
+   trailing slash.
+
+ - The rules to exclude the parent directory must have at least one
+   slash.
+
 EXAMPLES
 --------
 
diff --git a/dir.c b/dir.c
index 4893181a0c..894027c0cd 100644
--- a/dir.c
+++ b/dir.c
@@ -733,6 +733,25 @@ int match_pathname(const char *pathname, int pathlen,
 		 */
 		if (!patternlen && !namelen)
 			return 1;
+		/*
+		 * This can happen when we ignore some exclude rules
+		 * on directories in other to see if negative rules
+		 * may match. E.g.
+		 *
+		 * /abc
+		 * !/abc/def/ghi
+		 *
+		 * The pattern of interest is "/abc". On the first
+		 * try, we should match path "abc" with this pattern
+		 * in the "if" statement right above, but the caller
+		 * ignores it.
+		 *
+		 * On the second try with paths within "abc",
+		 * e.g. "abc/xyz", we come here and try to match it
+		 * with "/abc".
+		 */
+		if (!patternlen && namelen && *name == '/')
+			return 1;
 	}
 
 	return fnmatch_icase_mem(pattern, patternlen,
@@ -741,6 +760,48 @@ int match_pathname(const char *pathname, int pathlen,
 }
 
 /*
+ * Return non-zero if pathname is a directory and an ancestor of the
+ * literal path in a (negative) pattern. This is used to keep
+ * descending in "foo" and "foo/bar" when the pattern is
+ * "!foo/bar/.gitignore". "foo/notbar" will not be descended however.
+ */
+static int match_neg_path(const char *pathname, int pathlen, int *dtype,
+			  const char *base, int baselen,
+			  const char *pattern, int prefix, int patternlen,
+			  int flags)
+{
+	assert((flags & EXC_FLAG_NEGATIVE) && !(flags & EXC_FLAG_NODIR));
+
+	if (*dtype == DT_UNKNOWN)
+		*dtype = get_dtype(NULL, pathname, pathlen);
+	if (*dtype != DT_DIR)
+		return 0;
+
+	if (*pattern == '/') {
+		pattern++;
+		patternlen--;
+		prefix--;
+	}
+
+	if (baselen) {
+		if (((pathlen < baselen && base[pathlen] == '/') ||
+		     pathlen == baselen) &&
+		    !strncmp_icase(pathname, base, pathlen))
+			return 1;
+		pathname += baselen + 1;
+		pathlen  -= baselen + 1;
+	}
+
+
+	if (prefix &&
+	    ((pathlen < prefix && pattern[pathlen] == '/') &&
+	     !strncmp_icase(pathname, pattern, pathlen)))
+		return 1;
+
+	return 0;
+}
+
+/*
  * Scan the given exclude list in reverse to see whether pathname
  * should be ignored.  The first match (i.e. the last on the list), if
  * any, determines the fate.  Returns the exclude_list element which
@@ -753,7 +814,7 @@ static struct exclude *last_exclude_matching_from_list(const char *pathname,
 						       struct exclude_list *el)
 {
 	struct exclude *exc = NULL; /* undecided */
-	int i;
+	int i, matched_negative_path = 0;
 
 	if (!el->nr)
 		return NULL;	/* undefined */
@@ -788,7 +849,18 @@ static struct exclude *last_exclude_matching_from_list(const char *pathname,
 			exc = x;
 			break;
 		}
+
+		if ((x->flags & EXC_FLAG_NEGATIVE) && !matched_negative_path &&
+		    match_neg_path(pathname, pathlen, dtype, x->base,
+				   x->baselen ? x->baselen - 1 : 0,
+				   exclude, prefix, x->patternlen, x->flags))
+			matched_negative_path = 1;
 	}
+	if (exc &&
+	    !(exc->flags & EXC_FLAG_NEGATIVE) &&
+	    !(exc->flags & EXC_FLAG_NODIR) &&
+	    matched_negative_path)
+		exc = NULL;
 	return exc;
 }
 
diff --git a/t/t3001-ls-files-others-exclude.sh b/t/t3001-ls-files-others-exclude.sh
index b2798feef7..2a13af1758 100755
--- a/t/t3001-ls-files-others-exclude.sh
+++ b/t/t3001-ls-files-others-exclude.sh
@@ -305,4 +305,29 @@ test_expect_success 'ls-files with "**" patterns and no slashes' '
 	test_cmp expect actual
 '
 
+test_expect_success 'negative patterns' '
+	git init reinclude &&
+	(
+		cd reinclude &&
+		cat >.gitignore <<-\EOF &&
+		/fooo
+		/foo
+		!foo/bar/bar
+		EOF
+		mkdir fooo &&
+		cat >fooo/.gitignore <<-\EOF &&
+		!/*
+		EOF
+		mkdir -p foo/bar &&
+		touch abc foo/def foo/bar/ghi foo/bar/bar &&
+		git ls-files -o --exclude-standard >../actual &&
+		cat >../expected <<-\EOF &&
+		.gitignore
+		abc
+		foo/bar/bar
+		EOF
+		test_cmp ../expected ../actual
+	)
+'
+
 test_done