Fix `git clean` with pathspecs

Sometimes, multiple git clean $ARGS invocations (with the exact same flags and parameters for each invocation) are needed to properly clean out the desired files. Sometimes, git clean $PATHS just refuses to clean the files it was explicitly told to clean. This patch series aims to address these (very old) problems.

I was made aware of the problems when a user brought to me the following testcase:

    mkdir d{1,2}
    touch d{1,2}/ut
    touch d1/t
    git add d1/t

With this setup, the user would need to run
git clean -ffd */ut
twice to delete both ut files. Digging further, I found multiple interesting variants.

However, I am still slightly unsure of what the correct behavior is supposed to be for one particular case, namely, if the clean command were instead:
git clean -f '*ut'
(note that the glob is quoted to protect from shell expansion, and that the -d option was removed), should the files still be cleaned? I assumed yes and implemented that in patches 5-6, but the commit message discusses this case, and patch 7 exists to change the implementation to answer this question with a 'no'. Patch 7 should NOT should not be accepted as-is -- it should either be dropped or squashed into earlier commits, but which depends on the desired behavior.

Patches 1-2 are almost independent one-line fixes that could be submitted independently. However, if we decide to keep the changes from patch 7, then this series does depend on patch 2 for the tests to pass.

Patch 3 adds four new testcases covering the variants I noticed.

Patch 4 fixes clean with explicit pathspecs and the -d option.

Patches 5-7 fixes clean with explicit pathspecs without the -d option.

Elijah Newren (7):
dir.c: Fix typo in comment
dir.c: fix off-by-one error in match_pathspec_item
t7300: Add some testcases showing failure to clean specified pathspecs
dir: Directories should be checked for matching pathspecs too
dir: Make the DO_MATCH_SUBMODULE code reusable for a non-submodule
case
dir: If our pathspec might match files under a dir, recurse into it If we do not want globs to recurse into subdirs without -d...

 dir.c            | 23 +++++++++++++++--------
 dir.h            |  5 +++--
 t/t7300-clean.sh | 32 ++++++++++++++++++++++++++++++++
 3 files changed, 50 insertions(+), 10 deletions(-)

2.17.0.7.g0b50f94d69

---
 dir.c | 2 +-
 1 file changed, 1 insertion(+), 1 deletion(-)

index dedbf5d476..19212129f0 100644
@@ -138,7 +138,7 @@ static size_t common_prefix_len(const struct pathspec *pathspec)
 	 * ":(icase)path" is treated as a pathspec full of
 	 * wildcard. In other words, only prefix is considered common
 	 * prefix. If the pathspec is abc/foo abc/bar, running in
-	 * subdir xyz, the common prefix is still xyz, not xuz/abc as
+	 * subdir xyz, the common prefix is still xyz, not xyz/abc as
 	 * in non-:(icase).
 	 */
 	GUARD_PATHSPEC(pathspec,

2.17.0.7.g0b50f94d69

For a pathspec like 'foo/bar' comparing against a path named "foo/", namelen will be 4, and match[namelen] will be 'b'. The correct location of the directory separator is namelen-1.

The reason the code worked anyway was that the following code immediately checked whether the first matchlen characters matched (which they do) and then bailed and return MATCHED_RECURSIVELY anyway since wildmatch doesn't have the ability to check if "name" can be matched as a directory (or prefix) against the pathspec.

---
 dir.c | 2 +-
 1 file changed, 1 insertion(+), 1 deletion(-)

index 19212129f0..c915a69385 100644
@@ -384,7 +384,7 @@ static int match_pathspec_item(const struct pathspec_item *item, int prefix,
 	if (flags & DO_MATCH_SUBMODULE) {
 		/* name is a literal prefix of the pathspec */
 		if ((namelen < matchlen) &&
-		    (match[namelen] == '/') &&
+		    (match[namelen-1] == '/') &&
 		    !ps_strncmp(item, match, name, namelen))
 			return MATCHED_RECURSIVELY;
 

2.17.0.7.g0b50f94d69

Technically, the tests pass anyway due to the fallback behavior mentioned in the commit message, but this is a really good point. It looks like the call to submodule_path_match() from builtin/grep.c is going to be passing name without the trailing '/', which is contrary to how read_directory_recursive() in dir.c builds up paths (namely with the trailing '/'). If we tried to force consistency (either always omit the trailing slash or always include it), then we'd probably want to do so for match_pathspec() calls as well, and there are lots of those throughout the code and auditing it all looks painful.

So I should probably make the check handle both cases:

@@ -383,8 +383,9 @@ static int match_pathspec_item(const struct pathspec_item *item, int prefix,

        /* Perform checks to see if "name" is a super set of the pathspec */
        if (flags & DO_MATCH_LEADING_PATHSPEC) {
                /* name is a literal prefix of the pathspec */
+               int offset = name[namelen-1] == '/' ? 1 : 0;
                if ((namelen < matchlen) &&

- (match[namelen] == '/') &&
+ (match[namelen-offset] == '/') &&
!ps_strncmp(item, match, name, namelen))
return MATCHED_RECURSIVELY_LEADING_PATHSPEC;

<snip>

Right, I don't see how an empty path would make sense.

If it'd only take you a few hours, then you're a lot faster than me. It took me a while to start wrapping my head around it.

The other trailing-slash matches in the function are all correct, according to the testsuite. (I'm not sure I like the DO_MATCH_DIRECTORY stuff, but it is encoded in tests and backward compatibility is important.) In particular, changing the earlier code to have the same offset trick would make it claim that e.g. either "a/b" or "a/b/" as names match unconditionally against "a/b/c" as a pathspec. We need it to be conditional: we only want that to be considered a match when checking whether we want to recurse into the directory for other matches, not when checking whether the directory itself matches the pathspec. Thus, it should be behind a separate flag, in a subsequent check, which is what this series does (namely with DO_MATCH_LEADING_PATHSPEC).

To be more precise, here is how a matrix of pathnames and pathspecs would be treated by match_pathspec_item(), where I am abbreviating names like MATCH_RECURSIVELY_LEADING_PATHSPEC to LEADING):

Pathspecs
| a/b | a/b/ | a/b/c
------+-----------+------------+-----------
a/b | EXACT | RECURSIVE | LEADING[3]

  Names   a/b/  |  EXACT[1] |  EXACT     |  LEADING[2]
          a/b/c | RECURSIVE | RECURSIVE  |  EXACT

[1] Only if DO_MATCH_DIRECTORY is passed. Otherwise, this is NOT a match at all.
[2] Only if DO_MATCH_LEADING_PATHSPEC is passed, after applying this series. Otherwise, not a match at all.
[3] Without the fix in this thread that you highlighted, and assuming we apply patch 7, this would actually mistakenly return RECURSIVE.

Now for a separate question: How much of the above would you like added to the commit message...or even as a comment in the code to make it clearer to other folks trying to make sense of it?

Elijah

OK, I was being overly optimistic. :)

OK, that makes some sense to me.

That table seems quite illuminating to me. It's hard to pick out all the special-cases from the code, or what they're _supposed_ to be doing. I think it makes sense as a code comment.

-Peff

PS I'm going to be on a 3-week vacation starting tomorrow, so apologies
in advance for ignoring any follow-ups.

Someone brought me a testcase where multiple git-clean invocations were required to clean out unwanted files:
mkdir d{1,2}
touch d{1,2}/ut
touch d1/t && git add d1/t
With this setup, the user would need to run
git clean -ffd */ut
twice to delete both ut files.

A little testing showed some interesting variants:
* If only one of those two ut files existed (either one), then only one clean command would be necessary.
* If both directories had tracked files, then only one git clean would be necessary to clean both files.
* If both directories had no tracked files then the clean command above would never clean either of the untracked files despite the pathspec explicitly calling both of them out.

A bisect showed that the failure to clean out the files started with commit cf424f5fd89b ("clean: respect pathspecs with "-d"", 2014-03-10). However, that pointed to a separate issue: while the "-d" flag was used by the original user who showed me this problem, that flag should have been irrelevant to this problem. Testing again without the "-d" flag showed that the same buggy behavior exists without using that flag, and has in fact existed since before cf424f5fd89b.

Add testcases showing that multiple untracked files within entirely untracked directories cannot be cleaned when specifying these files to git clean via pathspecs.

---
 t/t7300-clean.sh | 32 ++++++++++++++++++++++++++++++++
 1 file changed, 32 insertions(+)

index 7b36954d63..3d260e21ea 100755
@@ -669,4 +669,36 @@ test_expect_success 'git clean -d skips untracked dirs containing ignored files'
 	test_path_is_missing foo/b/bb
 '
 
+test_expect_failure 'git clean handles being told what to clean' '
+	mkdir -p d1 d2 &&
+	touch d1/ut d2/ut &&
+	git clean -f */ut &&
+	test_path_is_missing d1/ut &&
+	test_path_is_missing d2/ut
+'
+
+test_expect_failure 'git clean handles being told what to clean, with -d' '
+	mkdir -p d1 d2 &&
+	touch d1/ut d2/ut &&
+	git clean -ffd */ut &&
+	test_path_is_missing d1/ut &&
+	test_path_is_missing d2/ut
+'
+
+test_expect_failure 'git clean handles being told a glob to clean' '
+	mkdir -p d1 d2 &&
+	touch d1/ut d2/ut &&
+	git clean -f "*ut" &&
+	test_path_is_missing d1/ut &&
+	test_path_is_missing d2/ut
+'
+
+test_expect_failure 'git clean handles being told a glob to clean with -d' '
+	mkdir -p d1 d2 &&
+	touch d1/ut d2/ut &&
+	git clean -ffd "*ut" &&
+	test_path_is_missing d1/ut &&
+	test_path_is_missing d2/ut
+'
+
 test_done

2.17.0.7.g0b50f94d69

Even if a directory doesn't match a pathspec, it is possible, depending on the precise pathspecs, that some file underneath it might. So we special case and recurse into the directory for such situations. However, we previously always added any untracked directory that we recursed into to the list of untracked paths, regardless of whether the directory itself matched the pathspec.

For the case of git-clean and a set of pathspecs of "dir/file" and "more", this caused a problem because we'd end up with dir entries for both of
"dir"
"dir/file"
Then correct_untracked_entries() would try to helpfully prune duplicates for us by removing "dir/file" since it's under "dir", leaving us with
"dir"
Since the original pathspec only had "dir/file", the only entry left doesn't match and leaves nothing to be removed. (Note that if only one pathspec was specified, e.g. only "dir/file", then the common_prefix_len optimizations in fill_directory would cause us to bypass this problem, making it appear in simple tests that we could correctly remove manually specified pathspecs.)

Fix this by actually checking whether the directory we are about to add to the list of dir entries actually matches the pathspec; only do this matching check after we have already returned from recursing into the directory.

---
 dir.c            | 5 +++++
 t/t7300-clean.sh | 4 ++--
 2 files changed, 7 insertions(+), 2 deletions(-)

index c915a69385..e783431948 100644
@@ -1973,6 +1973,11 @@ static enum path_treatment read_directory_recursive(struct dir_struct *dir,
 							 check_only, stop_at_first_file, pathspec);
 			if (subdir_state > dir_state)
 				dir_state = subdir_state;
+
+			if (!match_pathspec(pathspec, path.buf, path.len,
+					    0 /* prefix */, NULL,
+					    0 /* do NOT special case dirs */))
+				state = path_none;
 		}
 
 		if (check_only) {

index 3d260e21ea..31f2d0d8ba 100755
@@ -677,7 +677,7 @@ test_expect_failure 'git clean handles being told what to clean' '
 	test_path_is_missing d2/ut
 '
 
-test_expect_failure 'git clean handles being told what to clean, with -d' '
+test_expect_success 'git clean handles being told what to clean, with -d' '
 	mkdir -p d1 d2 &&
 	touch d1/ut d2/ut &&
 	git clean -ffd */ut &&

@@ -693,7 +693,7 @@ test_expect_failure 'git clean handles being told a glob to clean' '
 	test_path_is_missing d2/ut
 '
 
-test_expect_failure 'git clean handles being told a glob to clean with -d' '
+test_expect_success 'git clean handles being told a glob to clean with -d' '
 	mkdir -p d1 d2 &&
 	touch d1/ut d2/ut &&
 	git clean -ffd "*ut" &&

2.17.0.7.g0b50f94d69

It sounds like correct_untracked_entries() is doing the wrong thing, and it should be aware of the pathspec-matching when culling entries. In other words, my understanding was that read_directory() does not necessarily promise to cull fully (which is what led to cf424f5fd in the first place), and callers are forced to apply their own pathspecs.

The distinction is academic for this particular bug, but it makes me wonder if there are other cases where "clean" needs to be more careful with what comes out of dir.c.

-Peff

Interesting, I read things very differently. Looking back at commit 6b1db43109ab ("clean: teach clean -d to preserve ignored paths", 2017-05-23), which introduced correct_untracked_entries(), I thought that correct_untracked_entries() wasn't there to correct pathspec issues with fill_directory(), but instead to special case the handling of files which are both untracked and ignored. Did I mis-read or were there other commits that changed the semantics?

Also, it would just seem odd to me that fill_directory() requires pathspecs, and it uses those pathspecs, but it doesn't guarantee that the files it returns matches them. That seems like an API ripe for mis-use, especially since I don't see any comment in the code about such an assumption. Is that really the expectation?

To be honest, I don't know. Most of dir.c predates me, and I've tried to avoid looking at it too hard. But I had a vague recollection of it being "best effort", and this bit from cf424f5fd89b reinforces that:

However, read_directory does not actually check against our pathspec. It uses a simplified version that may turn up false positives. As a result, we need to check that any hits match our pathspec.

So I don't know that correct_untracked_entries() is there to fix the pathspec handling. But I think that anybody who looks at the output of fill_directory() does need to be aware that they may get more entries than they expected, and has to apply the pathspecs themselves. And that's what that extra dir_path_match() call in cmd_clean() is there for (it used to be match_pathspec before some renaming).

I agree it's an error-prone interface. I don't know all the conditions under which dir.c might return extra entries, but it seems like it might be sane for it to do a final pathspec-matching pass so that callers don't have to. That would mean that correct_untracked_entries() sees the correctly culled list, and the extra check in cmd_clean() could be dropped.

Ideally, of course, we'd fix those individual cases, since that would be more efficient. And your patch may be the right first step in that direction. But since we don't know what all of them are, it seems ripe for regressions.

-Peff

At least the original design of the traversal was "try making use of pathspec during the traversal when we can cheaply filter out obvious non-hits and avoid recursing into an entire hierarchy---false negative is an absolute no-no, but forcing the consumer to post filter is OK".

That matches with my understanding of how "fill" thing worked from early days.

The specific checks done in match_pathspec_item for the DO_MATCH_SUBMODULE case are useful for other cases which have nothing to do with submodules. Rename this constant; a subsequent commit will make use of this change.

---
 dir.c | 6 +++---
 1 file changed, 3 insertions(+), 3 deletions(-)

index e783431948..b0bca179fd 100644
@@ -272,7 +272,7 @@ static int do_read_blob(const struct object_id *oid, struct oid_stat *oid_stat,
 
 #define DO_MATCH_EXCLUDE   (1<<0)
 #define DO_MATCH_DIRECTORY (1<<1)
-#define DO_MATCH_SUBMODULE (1<<2)
+#define DO_MATCH_LEADING_PATHSPEC (1<<2)
 
 static int match_attrs(const char *name, int namelen,
 		       const struct pathspec_item *item)

@@ -381,7 +381,7 @@ static int match_pathspec_item(const struct pathspec_item *item, int prefix,
 		return MATCHED_FNMATCH;
 
 	/* Perform checks to see if "name" is a super set of the pathspec */
-	if (flags & DO_MATCH_SUBMODULE) {
+	if (flags & DO_MATCH_LEADING_PATHSPEC) {
 		/* name is a literal prefix of the pathspec */
 		if ((namelen < matchlen) &&
 		    (match[namelen-1] == '/') &&

@@ -521,7 +521,7 @@ int submodule_path_match(const struct pathspec *ps,
 					strlen(submodule_name),
 					0, seen,
 					DO_MATCH_DIRECTORY |
-					DO_MATCH_SUBMODULE);
+					DO_MATCH_LEADING_PATHSPEC);
 	return matched;
 }
 

2.17.0.7.g0b50f94d69

For git clean, if a directory is entirely untracked and the user did not specify -d (corresponding to DIR_SHOW_IGNORED_TOO), then we usually do not want to remove that directory and thus do not recurse into it. However, if the user manually specified specific (or even globbed) paths somewhere under that directory to remove, then we need to recurse into the directory to make sure we remove the relevant paths under that directory as the user requested.

Note that this does not mean that the recursed-into directory will be added to dir->entries for later removal; as of a few commits earlier in this series, there is another more strict match check that is run after returning from a recursed-into directory before deciding to add it to the list of entries. Therefore, this will only result in files underneath the given directory which match one of the pathspecs being added to the entries list.

Two particular considerations for this patch:

* If we want to only recurse into a directory when it is specifically matched rather than matched-via-glob (e.g. '*.c'), then we could do so via making the final non-zero return in match_pathspec_item be MATCHED_RECURSIVELY instead of MATCHED_RECURSIVELY_LEADING_PATHSPEC. (See final patch of this RFC series for details; note that the relative order of MATCHED_RECURSIVELY_LEADING_PATHSPEC and MATCHED_RECURSIVELY are important for such a change.))

* There is a growing amount of logic in read_directory_recursive() for deciding whether to recurse into a subdirectory. However, there is a comment immediately preceding this logic that says to recurse if
instructed by treat_path(). It may be better for the logic in
read_directory_recursive() to be moved to treat_path() (or another function it calls, such as treat_directory()), but I did not feel strongly about this and just left the logic where it was while adding to it. Do others have strong opinions on this?

---
 dir.c            | 10 ++++++----
 dir.h            |  5 +++--
 t/t7300-clean.sh |  4 ++--
 3 files changed, 11 insertions(+), 8 deletions(-)

index b0bca179fd..f55e24f149 100644
@@ -386,7 +386,7 @@ static int match_pathspec_item(const struct pathspec_item *item, int prefix,
 		if ((namelen < matchlen) &&
 		    (match[namelen-1] == '/') &&
 		    !ps_strncmp(item, match, name, namelen))
-			return MATCHED_RECURSIVELY;
+			return MATCHED_RECURSIVELY_LEADING_PATHSPEC;
 
 		/* name" doesn't match up to the first wild character */
 		if (item->nowildcard_len < item->len &&

@@ -403,7 +403,7 @@ static int match_pathspec_item(const struct pathspec_item *item, int prefix,
 		 * The submodules themselves will be able to perform more
 		 * accurate matching to determine if the pathspec matches.
 		 */
-		return MATCHED_RECURSIVELY;
+		return MATCHED_RECURSIVELY_LEADING_PATHSPEC;
 	}
 
 	return 0;

@@ -1961,8 +1961,10 @@ static enum path_treatment read_directory_recursive(struct dir_struct *dir,
 		/* recurse into subdir if instructed by treat_path */
 		if ((state == path_recurse) ||
 			((state == path_untracked) &&
-			 (dir->flags & DIR_SHOW_IGNORED_TOO) &&
-			 (get_dtype(cdir.de, istate, path.buf, path.len) == DT_DIR))) {
+			 (get_dtype(cdir.de, istate, path.buf, path.len) == DT_DIR) &&
+			 ((dir->flags & DIR_SHOW_IGNORED_TOO) ||
+			  do_match_pathspec(pathspec, path.buf, path.len,
+					    baselen, NULL, DO_MATCH_LEADING_PATHSPEC) == MATCHED_RECURSIVELY_LEADING_PATHSPEC))) {
 			struct untracked_cache_dir *ud;
 			ud = lookup_untracked(dir->untracked, untracked,
 					      path.buf + baselen,

index b0758b82a2..0573f99ae0 100644
@@ -210,8 +210,9 @@ extern int count_slashes(const char *s);
  * when populating the seen[] array.
  */
 #define MATCHED_RECURSIVELY 1
-#define MATCHED_FNMATCH 2
-#define MATCHED_EXACTLY 3
+#define MATCHED_RECURSIVELY_LEADING_PATHSPEC 2
+#define MATCHED_FNMATCH 3
+#define MATCHED_EXACTLY 4
 extern int simple_length(const char *match);
 extern int no_wildcard(const char *string);
 extern char *common_prefix(const struct pathspec *pathspec);

index 31f2d0d8ba..889b3401e4 100755
@@ -669,7 +669,7 @@ test_expect_success 'git clean -d skips untracked dirs containing ignored files'
 	test_path_is_missing foo/b/bb
 '
 
-test_expect_failure 'git clean handles being told what to clean' '
+test_expect_success 'git clean handles being told what to clean' '
 	mkdir -p d1 d2 &&
 	touch d1/ut d2/ut &&
 	git clean -f */ut &&

@@ -685,7 +685,7 @@ test_expect_success 'git clean handles being told what to clean, with -d' '
 	test_path_is_missing d2/ut
 '
 
-test_expect_failure 'git clean handles being told a glob to clean' '
+test_expect_success 'git clean handles being told a glob to clean' '
 	mkdir -p d1 d2 &&
 	touch d1/ut d2/ut &&
 	git clean -f "*ut" &&

2.17.0.7.g0b50f94d69

If folks prefer this behavior, I'll squash this patch into the previous. Otherwise, I'll just drop this patch from the series.

---
 dir.c            | 2 +-
 t/t7300-clean.sh | 6 +++---
 2 files changed, 4 insertions(+), 4 deletions(-)

index f55e24f149..bad75e9fbd 100644
@@ -403,7 +403,7 @@ static int match_pathspec_item(const struct pathspec_item *item, int prefix,
 		 * The submodules themselves will be able to perform more
 		 * accurate matching to determine if the pathspec matches.
 		 */
-		return MATCHED_RECURSIVELY_LEADING_PATHSPEC;
+		return MATCHED_RECURSIVELY;
 	}
 
 	return 0;

index 889b3401e4..913ea6bda3 100755
@@ -685,12 +685,12 @@ test_expect_success 'git clean handles being told what to clean, with -d' '
 	test_path_is_missing d2/ut
 '
 
-test_expect_success 'git clean handles being told a glob to clean' '
+test_expect_success 'git clean will not recurse with globs without -d' '
 	mkdir -p d1 d2 &&
 	touch d1/ut d2/ut &&
 	git clean -f "*ut" &&
-	test_path_is_missing d1/ut &&
-	test_path_is_missing d2/ut
+	test_path_is_file d1/ut &&
+	test_path_is_file d2/ut
 '
 
 test_expect_success 'git clean handles being told a glob to clean with -d' '

2.17.0.7.g0b50f94d69