[PATCH] ls-files: fix overeager pathspec optimization

Given pathspecs that share a common prefix, ls-files optimized its call
into recursive directory reader by starting at the common prefix
directory.

If you have a directory "t" with an untracked file "t/junk" in it, but the
top-level .gitignore file told us to ignore "t/", this resulted in an
unexpected behaviour:

    $ git ls-files -o --exclude-standard
    $ cd t && git ls-files -o --exclude-standard
    junk

Signed-off-by: Junio C Hamano <redacted>
---

Junio C Hamano [off-list ref] writes:

quoted

I think a proper fix should be in dir.c::read_directory() where it calls
read_directory_recursive() without first checking if the directory itself
should be ignored.  read_directory_recursive() itself has a logic to see
if the dirent it found is worth recursing into and a similar logic should
be in the toplevel caller.

So here it is.

 dir.c                              |   37 ++++++++++++++++++++++++++++++++++
 t/t3001-ls-files-others-exclude.sh |   39 ++++++++++++++++++++++++++++++++++++
 2 files changed, 76 insertions(+), 0 deletions(-)

diff --git a/dir.c b/dir.c
index f9ac454..9316eb6 100644
--- a/dir.c
+++ b/dir.c

@@ -787,6 +787,40 @@ static void free_simplify(struct path_simplify *simplify)
 	free(simplify);
 }
 
+static int has_leading_ignored_dir(struct dir_struct *dir,
+				   const char *path_, int len,
+				   const struct path_simplify *simplify)
+{
+	int at, dtype = DT_DIR;
+	char path[PATH_MAX];
+
+	at = 0;
+	memcpy(path, path_, len);
+	while (1) {
+		char *cp;
+		path[at] = '\0';
+		/*
+		 * NOTE! NOTE! NOTE!: we might want to actually lstat(2)
+		 * path[] to make sure it is a directory.
+		 */
+		if (excluded(dir, path, &dtype))
+			return 1;
+		if (at < len) {
+			path[at] = path_[at];
+			if (at < len && path[at] == '/')
+				at++;
+		}
+		if (len <= at)
+			break;
+		cp = memchr(path + at, '/', len - at);
+		if (!cp)
+			at = len;
+		else
+			at = cp - path;
+	}
+	return 0;
+}
+
 int read_directory(struct dir_struct *dir, const char *path, int len, const char **pathspec)
 {
 	struct path_simplify *simplify;

@@ -795,6 +829,9 @@ int read_directory(struct dir_struct *dir, const char *path, int len, const char
 		return dir->nr;
 
 	simplify = create_simplify(pathspec);
+	if (has_leading_ignored_dir(dir, path, len, simplify))
+		return dir->nr;
+
 	read_directory_recursive(dir, path, len, 0, simplify);
 	free_simplify(simplify);
 	qsort(dir->entries, dir->nr, sizeof(struct dir_entry *), cmp_name);

diff --git a/t/t3001-ls-files-others-exclude.sh b/t/t3001-ls-files-others-exclude.sh
index c65bca8..9e71260 100755
--- a/t/t3001-ls-files-others-exclude.sh
+++ b/t/t3001-ls-files-others-exclude.sh

@@ -153,4 +153,43 @@ test_expect_success 'negated exclude matches can override previous ones' '
 	grep "^a.1" output
 '
 
+test_expect_success 'subdirectory ignore (setup)' '
+	mkdir -p top/l1/l2 &&
+	(
+		cd top &&
+		git init &&
+		echo /.gitignore >.gitignore &&
+		echo l1 >>.gitignore &&
+		echo l2 >l1/.gitignore &&
+		>l1/l2/l1
+	)
+'
+
+test_expect_success 'subdirectory ignore (toplevel)' '
+	(
+		cd top &&
+		git ls-files -o --exclude-standard
+	) >actual &&
+	>expect &&
+	test_cmp expect actual
+'
+
+test_expect_success 'subdirectory ignore (l1/l2)' '
+	(
+		cd top/l1/l2 &&
+		git ls-files -o --exclude-standard
+	) >actual &&
+	>expect &&
+	test_cmp expect actual
+'
+
+test_expect_success 'subdirectory ignore (l1)' '
+	(
+		cd top/l1 &&
+		git ls-files -o --exclude-standard
+	) >actual &&
+	>expect &&
+	test_cmp expect actual
+'
+
 test_done

-- 
1.6.6.209.g52296.dirty

On Fri, 8 Jan 2010, Junio C Hamano wrote:

Given pathspecs that share a common prefix, ls-files optimized its call
into recursive directory reader by starting at the common prefix
directory.

If you have a directory "t" with an untracked file "t/junk" in it, but the
top-level .gitignore file told us to ignore "t/", this resulted in an
unexpected behaviour:

Ok, I'm not sure how "unexpected" this is, since arguably you are 
overriding the ignore file by _being_ in that directory (the same way 
index contents override ignore files), but I could go either way on that.

Your patch looks fine, although I think you did this in a very odd way.

+	at = 0;
+	memcpy(path, path_, len);
+	while (1) {
+		char *cp;
+		path[at] = '\0';
+		/*
+		 * NOTE! NOTE! NOTE!: we might want to actually lstat(2)
+		 * path[] to make sure it is a directory.
+		 */
+		if (excluded(dir, path, &dtype))
+			return 1;

The above starts by testing the empty string, and then after that test it 
goes on to the next directory component. That is just _odd_.

Wouldn't it be more natural to write the loop the other way around, ie 
_first_ look up the next directory component, and _then_ do the exclude 
processing for thoose components? 

Or is there some subtle reason I'm missing for actually checking the empty 
name?

				Linus