patch, 2 partsSparse Index: fix a checkout bug with deep sparse-checkout patterns

This week, we rolled out the sparse index to a large internal monorepo. We got two very similar bug reports that dealt with a strange error that involved the same set of paths. One was during git pull (pull was a red herring) and the other was git checkout. The git checkout case gave enough of a reproduction to debug deep into unpack-trees.c and find the problem.

This bug dates back to 523506d (unpack-trees: unpack sparse directory entries, 2021-07-14). The reason we didn't hit this before is because it requires the following:

 1. The sparse-checkout definition needs to have recursive inclusion of deep
    folders (depth 3 or more).
 2. Adjacent to those deep folders, we need a deep sparse directory entry
    that receives changes.
 3. In this particular repo, deep directories are only added to the
    sparse-checkout in rare occasions and those adjacent folders are rarely
    updated. They happened to update this week and hit our sparse index
    dogfooders in surprising ways.

The first patch adds a test that fails without the fix. It requires modifying our test data to make adjacent, deep sparse directory entries possible. It's a rather simple test after we have that data change.

The second patch includes the actual fix. It's really just an error of not understanding the difference between the name and traverse_path members of the struct traverse_info structure. name only stores a single tree entry while traverse_path actually includes the full name from root. The method we are editing also has an additional struct name_entry that fills in the tree entry on top of the traverse_path, which explains how this worked to depth two, but not depth three.

Thanks, -Stolee

Derrick Stolee (2):
  t1092: add deeper changes during a checkout
  unpack-trees: use traverse_path instead of name

 t/t1092-sparse-checkout-compatibility.sh | 16 +++++++++++++++-
 unpack-trees.c                           | 10 +++++-----
 2 files changed, 20 insertions(+), 6 deletions(-)

base-commit: cd3e606211bb1cf8bc57f7d76bab98cc17a150bc
Published-As: https://github.com/gitgitgadget/git/releases/tag/pr-1092%2Fderrickstolee%2Fsparse-index%2Fcheckout-bug-v1
Fetch-It-Via: git fetch https://github.com/gitgitgadget/git pr-1092/derrickstolee/sparse-index/checkout-bug-v1
Pull-Request: https://github.com/gitgitgadget/git/pull/1092

From: Derrick Stolee <dstolee@microsoft.com>

The sparse_dir_matches_path() method compares a cache entry that is a sparse directory entry against a 'struct traverse_info *info' and a 'struct name_entry *p' to see if the cache entry has exactly the right name for those other inputs.

This method was introduced in 523506d (unpack-trees: unpack sparse directory entries, 2021-07-14), but included a significant mistake. The path comparisons used 'info->name' instead of 'info->traverse_path'. Since 'info->name' only stores a single tree entry name while 'info->traverse_path' stores the full path from root, this method does not work when 'info' is in a subdirectory of a directory. Replacing the right strings and their corresponding lengths make the method work properly.

The previous change included a failing test that exposes this issue. That test now passes. The critical detail is that as we go deep into unpack_trees(), the logic for merging a sparse directory entry with a tree entry during 'git checkout' relies on this sparse_dir_matches_path() in order to avoid calling traverse_trees_recursive() during unpack_callback() in this hunk:

	if (!is_sparse_directory_entry(src[0], names, info) &&
	    traverse_trees_recursive(n, dirmask, mask & ~dirmask,
					    names, info) < 0) {
		return -1;
	}

For deep paths, the short-circuit never occurred and traverse_trees_recursive() was being called incorrectly and that was causing other strange issues. Specifically, the error message from the now-passing test previously included this:

      error: Your local changes to the following files would be overwritten by checkout:
              deep/deeper1/deepest2/a
              deep/deeper1/deepest3/a
      Please commit your changes or stash them before you switch branches.
      Aborting

These messages occurred because the 'current' cache entry in twoway_merge() was showing as NULL because the index did not contain entries for the paths contained within the sparse directory entries. We instead had 'oldtree' given as the entry at HEAD and 'newtree' as the entry in the target tree. This led to reject_merge() listing these paths.

Now that sparse_dir_matches_path() works the same for deep paths as it does for shallow depths, the rest of the logic kicks in to properly handle modifying the sparse directory entries as designed.

Reported-by: Gustave Granroth <gus.gran@gmail.com>
Reported-by: Mike Marcelais <michmarc@exchange.microsoft.com>
Signed-off-by: Derrick Stolee <dstolee@microsoft.com>
---
 t/t1092-sparse-checkout-compatibility.sh |  2 +-
 unpack-trees.c                           | 10 +++++-----
 2 files changed, 6 insertions(+), 6 deletions(-)

On Fri, Dec 3, 2021 at 6:55 PM Derrick Stolee via GitGitGadget <gitgitgadget@gmail.com> wrote:

Eek, sorry for not catching this in my earlier review. Thanks for the detailed explanation; well analyzed.

The comment at the beginning of this function (not shown in this patch) is now stale and misleading; it should be corrected too.

On 12/4/2021 12:42 AM, Elijah Newren wrote:

 
Will do! Thanks for catching that.

Thanks, -Stolee

From: Derrick Stolee <dstolee@microsoft.com>

Extend the repository data in the setup of t1092 to include more directories within two parent directories. This reproduces a bug found by users of the sparse index feature with suitably-complicated sparse-checkout definitions.

Add a failing test that fails in its first 'git checkout deepest' run in the sparse index case with this error:

  error: Your local changes to the following files would be overwritten by checkout:
          deep/deeper1/deepest2/a
          deep/deeper1/deepest3/a
  Please commit your changes or stash them before you switch branches.
  Aborting

The next change will fix this error, and that fix will make it clear why the extra depth is necessary for revealing this bug. The assignment of the sparse-checkout definition to include deep/deeper1/deepest as a sibling directory is important to ensure that deep/deeper1 is not a sparse directory entry, but deep/deeper1/deepest2 is.

Signed-off-by: Derrick Stolee <dstolee@microsoft.com>
---
 t/t1092-sparse-checkout-compatibility.sh | 16 +++++++++++++++-
 1 file changed, 15 insertions(+), 1 deletion(-)

On Fri, Dec 3, 2021 at 6:55 PM Derrick Stolee via GitGitGadget <gitgitgadget@gmail.com> wrote:

Thanks for the detailed explanation. I looked around for similar potential problems elsewhere, but only noted that the comment at the top of the function is also wrong and should be updated (as I commented on Patch 2). After you fix the comment similarly, feel free to add my

Reviewed-by: Elijah Newren <newren@gmail.com>

This week, we rolled out the sparse index to a large internal monorepo. We got two very similar bug reports that dealt with a strange error that involved the same set of paths. One was during git pull (pull was a red herring) and the other was git checkout. The git checkout case gave enough of a reproduction to debug deep into unpack-trees.c and find the problem.

This bug dates back to 523506d (unpack-trees: unpack sparse directory entries, 2021-07-14). The reason we didn't hit this before is because it requires the following:

 1. The sparse-checkout definition needs to have recursive inclusion of deep
    folders (depth 3 or more).
 2. Adjacent to those deep folders, we need a deep sparse directory entry
    that receives changes.
 3. In this particular repo, deep directories are only added to the
    sparse-checkout in rare occasions and those adjacent folders are rarely
    updated. They happened to update this week and hit our sparse index
    dogfooders in surprising ways.

The first patch adds a test that fails without the fix. It requires modifying our test data to make adjacent, deep sparse directory entries possible. It's a rather simple test after we have that data change.

The second patch includes the actual fix. It's really just an error of not understanding the difference between the name and traverse_path members of the struct traverse_info structure. name only stores a single tree entry while traverse_path actually includes the full name from root. The method we are editing also has an additional struct name_entry that fills in the tree entry on top of the traverse_path, which explains how this worked to depth two, but not depth three.

Update in v2 ============

 * Fixed the comment describing the sparse_dir_matches_path() method.

Thanks, -Stolee

Derrick Stolee (2):
  t1092: add deeper changes during a checkout
  unpack-trees: use traverse_path instead of name

 t/t1092-sparse-checkout-compatibility.sh | 16 +++++++++++++++-
 unpack-trees.c                           | 14 ++++++++------
 2 files changed, 23 insertions(+), 7 deletions(-)

base-commit: cd3e606211bb1cf8bc57f7d76bab98cc17a150bc
Published-As: https://github.com/gitgitgadget/git/releases/tag/pr-1092%2Fderrickstolee%2Fsparse-index%2Fcheckout-bug-v2
Fetch-It-Via: git fetch https://github.com/gitgitgadget/git pr-1092/derrickstolee/sparse-index/checkout-bug-v2
Pull-Request: https://github.com/gitgitgadget/git/pull/1092

Range-diff vs v1:

 1:  ba05d7d4149 = 1:  ba05d7d4149 t1092: add deeper changes during a checkout
 2:  c9142199656 ! 2:  aa37168dcb4 unpack-trees: use traverse_path instead of name
     @@ t/t1092-sparse-checkout-compatibility.sh: test_expect_success 'add, commit, chec
       	test_sparse_match git sparse-checkout set deep/deeper1/deepest &&
      
       ## unpack-trees.c ##
     +@@ unpack-trees.c: static int find_cache_pos(struct traverse_info *info,
     + 
     + /*
     +  * Given a sparse directory entry 'ce', compare ce->name to
     +- * info->name + '/' + p->path + '/' if info->name is non-empty.
     ++ * info->traverse_path + p->path + '/' if info->traverse_path
     ++ * is non-empty.
     ++ *
     +  * Compare ce->name to p->path + '/' otherwise. Note that
     +  * ce->name must end in a trailing '/' because it is a sparse
     +  * directory entry.
      @@ unpack-trees.c: static int sparse_dir_matches_path(const struct cache_entry *ce,
       	assert(S_ISSPARSEDIR(ce->ce_mode));
       	assert(ce->name[ce->ce_namelen - 1] == '/');

From: Derrick Stolee <dstolee@microsoft.com>

Extend the repository data in the setup of t1092 to include more directories within two parent directories. This reproduces a bug found by users of the sparse index feature with suitably-complicated sparse-checkout definitions.

Add a failing test that fails in its first 'git checkout deepest' run in the sparse index case with this error:

  error: Your local changes to the following files would be overwritten by checkout:
          deep/deeper1/deepest2/a
          deep/deeper1/deepest3/a
  Please commit your changes or stash them before you switch branches.
  Aborting

The next change will fix this error, and that fix will make it clear why the extra depth is necessary for revealing this bug. The assignment of the sparse-checkout definition to include deep/deeper1/deepest as a sibling directory is important to ensure that deep/deeper1 is not a sparse directory entry, but deep/deeper1/deepest2 is.

Signed-off-by: Derrick Stolee <dstolee@microsoft.com>
---
 t/t1092-sparse-checkout-compatibility.sh | 16 +++++++++++++++-
 1 file changed, 15 insertions(+), 1 deletion(-)

From: Derrick Stolee <dstolee@microsoft.com>

The sparse_dir_matches_path() method compares a cache entry that is a sparse directory entry against a 'struct traverse_info *info' and a 'struct name_entry *p' to see if the cache entry has exactly the right name for those other inputs.

This method was introduced in 523506d (unpack-trees: unpack sparse directory entries, 2021-07-14), but included a significant mistake. The path comparisons used 'info->name' instead of 'info->traverse_path'. Since 'info->name' only stores a single tree entry name while 'info->traverse_path' stores the full path from root, this method does not work when 'info' is in a subdirectory of a directory. Replacing the right strings and their corresponding lengths make the method work properly.

The previous change included a failing test that exposes this issue. That test now passes. The critical detail is that as we go deep into unpack_trees(), the logic for merging a sparse directory entry with a tree entry during 'git checkout' relies on this sparse_dir_matches_path() in order to avoid calling traverse_trees_recursive() during unpack_callback() in this hunk:

	if (!is_sparse_directory_entry(src[0], names, info) &&
	    traverse_trees_recursive(n, dirmask, mask & ~dirmask,
					    names, info) < 0) {
		return -1;
	}

For deep paths, the short-circuit never occurred and traverse_trees_recursive() was being called incorrectly and that was causing other strange issues. Specifically, the error message from the now-passing test previously included this:

      error: Your local changes to the following files would be overwritten by checkout:
              deep/deeper1/deepest2/a
              deep/deeper1/deepest3/a
      Please commit your changes or stash them before you switch branches.
      Aborting

These messages occurred because the 'current' cache entry in twoway_merge() was showing as NULL because the index did not contain entries for the paths contained within the sparse directory entries. We instead had 'oldtree' given as the entry at HEAD and 'newtree' as the entry in the target tree. This led to reject_merge() listing these paths.

Now that sparse_dir_matches_path() works the same for deep paths as it does for shallow depths, the rest of the logic kicks in to properly handle modifying the sparse directory entries as designed.

Reported-by: Gustave Granroth <gus.gran@gmail.com>
Reported-by: Mike Marcelais <michmarc@exchange.microsoft.com>
Signed-off-by: Derrick Stolee <dstolee@microsoft.com>
---
 t/t1092-sparse-checkout-compatibility.sh |  2 +-
 unpack-trees.c                           | 14 ++++++++------
 2 files changed, 9 insertions(+), 7 deletions(-)