dir: fix negative pathspecs in 'git ls-files' and 'git add'

From: Diogo Castro <[email protected]>

git ls-files calls common_prefix() / get_common_prefix_len() which calculate the length of the common prefix of all *positive* pathspecs, max_prefix_len.

max_prefix_len is then passed to match_pathspec() -> match_pathspec_with_flags() -> do_match_pathspec(), which strips max_prefix_len bytes off of *all* paths and match_pathspec_item() strips *all* pathspecs (positive or negative).

This causes the bug previously reported in [1].

As a result, when we run git ls-files -- sub/sub/sub/file ':(exclude)nonexistent':
* The common prefix of the positive pathspecs is sub/sub/sub, 11 bytes
* 11 bytes get stripped off both pathspecs:
* "sub/sub/sub/file" becomes "/file"
* "nonexistent" becomes ""
* Since the negative pathspec degenerated into "", it matches every file, and thus no results are returned.

When the common prefix is longer than the negative pathspec, we read out of bounds.

git add suffers from the same issue. It uses fill_directory(), which returns the common prefix length, but doesn't strip the trailing slash. Using the same pathspecs as in the example above, the common prefix would be sub/sub/sub/, 12 bytes.

Only git ls-files and git add are impacted. Other callers pass in 0 as the prefix.

Bug introduced in: ef79b1f870 (Support pathspec magic :(exclude) and its short form :!, 2013-12-06).

Solution: in do_match_pathspec(), only strip the prefix when handling positive pathspecs, not when handling negative pathspecs.

[1]: https://lore.kernel.org/git/[email protected]

---
dir: fix negative pathspecs in git ls-files and git add

Published-As: https://github.com/gitgitgadget/git/releases/tag/pr-git-2391%2Fdcastro%2Fdiogo.castro%2Ffix-pathspecs-common-prefix-v1
Fetch-It-Via: git fetch https://github.com/gitgitgadget/git pr-git-2391/dcastro/diogo.castro/fix-pathspecs-common-prefix-v1
Pull-Request: https://github.com/git/git/pull/2391

 dir.c                       | 11 ++++++++
 t/t6132-pathspec-exclude.sh | 52 +++++++++++++++++++++++++++++++++++++
 2 files changed, 63 insertions(+)

index 32430090dc..3fb2764efe 100644
@@ -539,6 +539,17 @@ static int do_match_pathspec(struct index_state *istate,
 			return 0;
 	}
 
+	/*
+	 * The `prefix`, calculated by `common_prefix_len()`, only takes
+	 * positive pathspecs into account. Negative pathspecs are not
+	 * considered.
+	 *
+	 * Therefore, the prefix can only be stripped from positive
+	 * pathspecs, not from negative pathspecs.
+	 */
+	if (exclude)
+		prefix = 0;
+
 	name += prefix;
 	namelen -= prefix;
 

base-commit: e9019fcafe0040228b8631c30f97ae1adb61bcdc

gitgitgadget

Hmph, if the command line were

	git ls-files -- a/b/c a/b/d !a/b/

shouldn't we strip a/b/ from all three? Would it make sense to leave the negative one relative to the full tree? I am wondering if the solution is to compute common prefix across both positive and negative ones instead.

I don't think so.

As far as I can tell, the "strip the common prefix" feature is a performance optimization aimed at avoiding walking the working directory needlessly.
So for git add -- a/b/c a/b/d, there's no need to look anywhere other than in a/b/.

But extending the "strip the common prefix" to negative pathspecs could end up negating the benefits we get from this perf optimization. E.g. in git add -- a/b/c a/b/d ':!*.md', there is no prefix common to *all* pathspecs, so we'd revert to walking the entire working directory, even though a/b/ would still suffice.

I was wondering more about case like this:

    $ git add -- a/b/c a/b/d ':!a/b/x

I agree that it is nonsense to compute the common prefix over only positive ones, and then to strip the common prefix from both positive and negative ones, and it needs to be corrected.

I think there's some misunderstanding, please allow me to take a step back and attempt to clarify.
My previous message was a reply to this:

As far as I can tell, this "common prefix" feature does not affect the semantics of "ls-files" or "add", it doesn't affect which files are reported.
It only affects the performance.

Your first example of "git ls-files -- a/b/c a/b/d :!a/b/" already works correctly, the pattern ":!a/b/" excludes everything from the first 2 pathspecs.

So the discussion to be had is purely about performance. My point was that computing the common prefix across both positive *and* negative pathspecs would not improve performance, and might actually make it worse.

The "common prefix" is mainly used to avoid walking the entire working directory.
A couple of examples to illustrate:

* "git add -- a/b/c a/b/d ':!a/b/x'"
* Under the current implementation, the common prefix is "a/b/",
so as a performance optimization, we can look only into the "a/b/" directory and ignore the others.
* Under your proposal of computing the "common prefix across both
positive and negative ones", the common prefix would still be "a/b/", so performance wouldn't be affected.
* "git add -- a/b/c a/b/d ':!a/**/x'"
* Under the current implementation, the common prefix is "a/b/",
like in the example above.
* Under your proposal, the common prefix would be "a/", so we'd
have to walk _more_ directories, which would hurt performance.

Does that answer your question? Or perhaps I misunderstood your point?

OK. Then that points at the right solution. Ignore negative ones when finding what the common prefix is, strip it only from positive ones to reduce the width of the traversal to come up with the list of possible match candidates, and match them as full paths against the negative ones to cull "within the positive set but is excluded" paths, and the posted patch looks good.

I still wonder if we need different implementation when we have many more negative patterns than the positive ones. In such a case, the stage to filter paths that matched one positive pattern by finding matches with a negative pattern among many of them, which may benefit from having a similar common prefix (among negative patterns) optimization, but that is a separate topic.

Thanks.

I see this work has been incorporated into [1]

I'm closing the PR on git/git.

[1]: https://lore.kernel.org/git/[email protected]/T/#t