Sparse index: integrate with 'read-tree'

From: Victoria Dye <[email protected]>

Prevent the repository root from being collapsed into a sparse directory by treating an empty path as "inside the sparse-checkout". When collapsing a sparse index (e.g. in 'git sparse-checkout reapply'), the root directory typically could not become a sparse directory due to the presence of in-cone root-level files and directories. However, if no such in-cone files or directories were present, there was no explicit check signaling that the "repository root path" (an empty string, in the case of 'convert_to_sparse(...)') was in-cone, and a sparse directory index entry would be created from the repository root directory.

The documentation in Documentation/git-sparse-checkout.txt explicitly states that the files in the root directory are expected to be in-cone for a cone-mode sparse-checkout. Collapsing the root into a sparse directory entry violates that assumption, as sparse directory entries are expected to be outside the sparse cone and have SKIP_WORKTREE enabled. This invalid state in turn causes issues with commands that interact with the index, e.g. 'git status'.

Treating an empty (root) path as in-cone prevents the creation of a root sparse directory in 'convert_to_sparse(...)'. Because the repository root is otherwise never compared with sparse patterns (in both cone-mode and non-cone sparse-checkouts), the new check does not cause additional changes to how sparse patterns are applied.

Quoted 1 line · Victoria Dye via GitGitGadget

From: Victoria Dye <[email protected]>

Aside: It looks like you have the same "mailto:" email addresses in the CC similar to a mistake I made. The root cause of my issue was that I copy-pasted from the rendered description of another PR instead of copying the plaintext available by clicking the "Edit" button. Perhaps this is worth extending GGG to prevent this issue in the future.

Quoted 18 lines

Prevent the repository root from being collapsed into a sparse directory by treating an empty path as "inside the sparse-checkout". When collapsing a sparse index (e.g. in 'git sparse-checkout reapply'), the root directory typically could not become a sparse directory due to the presence of in-cone root-level files and directories. However, if no such in-cone files or directories were present, there was no explicit check signaling that the "repository root path" (an empty string, in the case of 'convert_to_sparse(...)') was in-cone, and a sparse directory index entry would be created from the repository root directory.

The documentation in Documentation/git-sparse-checkout.txt explicitly states that the files in the root directory are expected to be in-cone for a cone-mode sparse-checkout. Collapsing the root into a sparse directory entry violates that assumption, as sparse directory entries are expected to be outside the sparse cone and have SKIP_WORKTREE enabled. This invalid state in turn causes issues with commands that interact with the index, e.g. 'git status'.

Quoted 5 lines

Treating an empty (root) path as in-cone prevents the creation of a root sparse directory in 'convert_to_sparse(...)'. Because the repository root is otherwise never compared with sparse patterns (in both cone-mode and non-cone sparse-checkouts), the new check does not cause additional changes to how sparse patterns are applied.

Good catch! I agree with everything said here.

dir.c static int path_in_sparse_checkout_1(const char *path, · line 1469

Quoted 1 line

dir.c +1 -0

+	if (!strlen(path) ||

Instead of a full strlen(), could we just check "if (!*path ||" to look for the nul byte?

Thanks,
-Stolee

From: Victoria Dye <[email protected]>

Enable two-way merge with 'git read-tree' without expanding the sparse index. When in a sparse index, a two-way merge will trivially succeed as long as there are not changes to the same sparse directory in multiple trees (i.e., sparse directory-level "edit-edit" conflicts). If there are such conflicts, the merge will fail despite the possibility that individual files could merge cleanly.

In order to resolve these "edit-edit" conflicts, "conflicted" sparse directories are - rather than rejected - merged by traversing their associated trees by OID. For each child of the sparse directory:

1. Files are merged as normal (see Documentation/git-read-tree.txt for details).
2. Subdirectories are treated as sparse directories and merged in 'twoway_merge'. If there are no conflicts, they are merged according to the rules in Documentation/git-read-tree.txt; otherwise, the subdirectory is recursively traversed and merged.

This process allows sparse directories to be individually merged at the necessary depth *without* expanding a full index.

Signed-off-by Victoria Dye <[email protected]>

---
 builtin/read-tree.c                      |  5 --
 t/t1092-sparse-checkout-compatibility.sh |  3 +-
 unpack-trees.c                           | 75 ++++++++++++++++++++++++
 3 files changed, 77 insertions(+), 6 deletions(-)

builtin/read-tree.c +0 -5

index a7b7f822281..5a421de2629 100644
@@ -225,11 +225,6 @@ int cmd_read_tree(int argc, const char **argv, const char *cmd_prefix)
                        opts.fn = opts.prefix ? bind_merge : oneway_merge;
                        break;
                case 2:
-                       /*
-                        * TODO: update twoway_merge to handle edit/edit conflicts in
-                        * sparse directories.
-                        */
-                       ensure_full_index(&the_index);
                        opts.fn = twoway_merge;
                        opts.initial_checkout = is_cache_unborn();
                        break;

t/t1092-sparse-checkout-compatibility.sh +2 -1

index a404be0a10f..d6f19682d65 100755
@@ -1411,7 +1411,8 @@ test_expect_success 'sparse index is not expanded: read-tree' '
        init_repos &&
 
        ensure_not_expanded checkout -b test-branch update-folder1 &&
-       for MERGE_TREES in "update-folder2"
+       for MERGE_TREES in "update-folder2" \
+                          "base update-folder2"
        do
                ensure_not_expanded read-tree -mu $MERGE_TREES &&
                ensure_not_expanded reset --hard HEAD || return 1

unpack-trees.c +19 -0

index dba122a02bb..a4ace53904e 100644
@@ -1360,6 +1360,42 @@ static int is_sparse_directory_entry(struct cache_entry *ce,
        return sparse_dir_matches_path(ce, info, name);
 }
 
+static int unpack_sparse_callback(int n, unsigned long mask, unsigned long dirmask, struct name_entry *names, struct traverse_info *info)
+{
+       struct cache_entry *src[MAX_UNPACK_TREES + 1] = { NULL, };
+       struct unpack_trees_options *o = info->data;
+       int ret;
+
+       assert(o->merge);
+
+       /*
+        * Unlike in 'unpack_callback', where src[0] is derived from the index when
+        * merging, src[0] is a transient cache entry derived from the first tree
+        * provided. Create the temporary entry as if it came from a non-sparse index.
+        */
+       if (!is_null_oid(&names[0].oid)) {
+               src[0] = create_ce_entry(info, &names[0], 0,
+                                       &o->result, 1,
+                                       dirmask & (1ul << 0));
+               src[0]->ce_flags |= (CE_SKIP_WORKTREE | CE_NEW_SKIP_WORKTREE);
+       }

unpack-trees.c +46 -1

+
+       if (src[0])
+               discard_cache_entry(src[0]);
+
+       return ret >= 0 ? mask : -1;
+}
+
 /*
  * Note that traverse_by_cache_tree() duplicates some logic in this function
  * without actually calling it. If you change the logic here you may need to

@@ -2464,6 +2500,37 @@ static int merged_entry(const struct cache_entry *ce,
        return 1;
 }
 
+static int merged_sparse_dir(const struct cache_entry * const *src, int n,
+                            struct unpack_trees_options *o)
+{
+       struct tree_desc t[MAX_UNPACK_TREES + 1];
+       void * tree_bufs[MAX_UNPACK_TREES + 1];
+       struct traverse_info info;
+       int i, ret;
+
+       /*
+        * Create the tree traversal information for traversing into *only* the
+        * sparse directory.
+        */
+       setup_traverse_info(&info, src[0]->name);
+       info.fn = unpack_sparse_callback;
+       info.data = o;
+       info.show_all_errors = o->show_all_errors;
+       info.pathspec = o->pathspec;
+
+       /* Get the tree descriptors of the sparse directory in each of the merging trees */
+       for (i = 0; i < n; i++)
+               tree_bufs[i] = fill_tree_descriptor(o->src_index->repo, &t[i],
+                                                   src[i] && !is_null_oid(&src[i]->oid) ? &src[i]->oid : NULL);
+
+       ret = traverse_trees(o->src_index, n, t, &info);
+
+       for (i = 0; i < n; i++)
+               free(tree_bufs[i]);
+
+       return ret;
+}
+
 static int deleted_entry(const struct cache_entry *ce,
                         const struct cache_entry *old,
                         struct unpack_trees_options *o)

@@ -2734,6 +2801,14 @@ int twoway_merge(const struct cache_entry * const *src,
                         * reject the merge instead.
                         */
                        return merged_entry(newtree, current, o);
+               } else if (S_ISSPARSEDIR(current->ce_mode)) {
+                       /*
+                        * The sparse directories differ, but we don't know whether that's
+                        * because of two different files in the directory being modified
+                        * (can be trivially merged) or if there is a real file conflict.
+                        * Merge the sparse directory by OID to compare file-by-file.
+                        */
+                       return merged_sparse_dir(src, 3, o);
                } else
                        return reject_merge(current, o);
        }
--

gitgitgadget

Quoted 21 lines · Victoria Dye via GitGitGadget

From: Victoria Dye <[email protected]>

Enable two-way merge with 'git read-tree' without expanding the sparse index. When in a sparse index, a two-way merge will trivially succeed as long as there are not changes to the same sparse directory in multiple trees (i.e., sparse directory-level "edit-edit" conflicts). If there are such conflicts, the merge will fail despite the possibility that individual files could merge cleanly.

In order to resolve these "edit-edit" conflicts, "conflicted" sparse directories are - rather than rejected - merged by traversing their associated trees by OID. For each child of the sparse directory:

1. Files are merged as normal (see Documentation/git-read-tree.txt for details).
2. Subdirectories are treated as sparse directories and merged in 'twoway_merge'. If there are no conflicts, they are merged according to the rules in Documentation/git-read-tree.txt; otherwise, the subdirectory is recursively traversed and merged.

Quoted 2 lines

This process allows sparse directories to be individually merged at the necessary depth *without* expanding a full index.

The idea of merging directory-level entries turns out to be problematic _if_ rename detection is involved, but read-tree-style merges are only trivial merges that ignore rename detection. As such, this idea is perfectly reasonable, and is a good way to go. Nicely done.

Mostly the patch looks good. There's one thing I'm wondering about, though...

Quoted 65 lines

Signed-off-by Victoria Dye <[email protected]>

---
 builtin/read-tree.c                      |  5 --
 t/t1092-sparse-checkout-compatibility.sh |  3 +-
 unpack-trees.c                           | 75 ++++++++++++++++++++++++
 3 files changed, 77 insertions(+), 6 deletions(-)

builtin/read-tree.c +0 -5

index a7b7f822281..5a421de2629 100644
@@ -225,11 +225,6 @@ int cmd_read_tree(int argc, const char **argv, const char *cmd_prefix)
                        opts.fn = opts.prefix ? bind_merge : oneway_merge;
                        break;
                case 2:
-                       /*
-                        * TODO: update twoway_merge to handle edit/edit conflicts in
-                        * sparse directories.
-                        */
-                       ensure_full_index(&the_index);
                        opts.fn = twoway_merge;
                        opts.initial_checkout = is_cache_unborn();
                        break;

t/t1092-sparse-checkout-compatibility.sh +2 -1

index a404be0a10f..d6f19682d65 100755
@@ -1411,7 +1411,8 @@ test_expect_success 'sparse index is not expanded: read-tree' '
        init_repos &&
 
        ensure_not_expanded checkout -b test-branch update-folder1 &&
-       for MERGE_TREES in "update-folder2"
+       for MERGE_TREES in "update-folder2" \
+                          "base update-folder2"
        do
                ensure_not_expanded read-tree -mu $MERGE_TREES &&
                ensure_not_expanded reset --hard HEAD || return 1

unpack-trees.c +19 -0

index dba122a02bb..a4ace53904e 100644
@@ -1360,6 +1360,42 @@ static int is_sparse_directory_entry(struct cache_entry *ce,
        return sparse_dir_matches_path(ce, info, name);
 }
 
+static int unpack_sparse_callback(int n, unsigned long mask, unsigned long dirmask, struct name_entry *names, struct traverse_info *info)
+{
+       struct cache_entry *src[MAX_UNPACK_TREES + 1] = { NULL, };
+       struct unpack_trees_options *o = info->data;
+       int ret;
+
+       assert(o->merge);
+
+       /*
+        * Unlike in 'unpack_callback', where src[0] is derived from the index when
+        * merging, src[0] is a transient cache entry derived from the first tree
+        * provided. Create the temporary entry as if it came from a non-sparse index.
+        */
+       if (!is_null_oid(&names[0].oid)) {
+               src[0] = create_ce_entry(info, &names[0], 0,
+                                       &o->result, 1,
+                                       dirmask & (1ul << 0));
+               src[0]->ce_flags |= (CE_SKIP_WORKTREE | CE_NEW_SKIP_WORKTREE);
+       }

unpack-trees.c static int is_sparse_directory_entry(struct cache_entry *ce, · line 1391

Quoted 10 lines

unpack-trees.c +10 -0

+
+       /*
+        * 'unpack_single_entry' assumes that src[0] is derived directly from
+        * the index, rather than from an entry in 'names'. This is *not* true when
+        * merging a sparse directory, in which case names[0] is the "index" source
+        * entry. To match the expectations of 'unpack_single_entry', shift past the
+        * "index" tree (i.e., names[0]) and adjust 'names', 'n', 'mask', and
+        * 'dirmask' accordingly.
+        */
+       ret = unpack_single_entry(n - 1, mask >> 1, dirmask >> 1, src, names + 1, info);

So, you're passing one less entry to unpack_single_entry() when you've

traversed into a sparse directory...won't the traversal at the next subdirectory deeper then also pass one less entry to unpack_single_entry(), so after recursing a directory or two, you only have one directory left and it won't conflict with anything so it just uses that remaining tree? (Or maybe it passes the wrong number of arguments into twoway_merge()?) Did I miss something in the logic somewhere that avoids that issue? It'd be nice to test it out, which brings me to...

Quoted 62 lines

unpack-trees.c +46 -0

+
+       if (src[0])
+               discard_cache_entry(src[0]);
+
+       return ret >= 0 ? mask : -1;
+}
+
 /*
  * Note that traverse_by_cache_tree() duplicates some logic in this function
  * without actually calling it. If you change the logic here you may need to

@@ -2464,6 +2500,37 @@ static int merged_entry(const struct cache_entry *ce,
        return 1;
 }
 
+static int merged_sparse_dir(const struct cache_entry * const *src, int n,
+                            struct unpack_trees_options *o)
+{
+       struct tree_desc t[MAX_UNPACK_TREES + 1];
+       void * tree_bufs[MAX_UNPACK_TREES + 1];
+       struct traverse_info info;
+       int i, ret;
+
+       /*
+        * Create the tree traversal information for traversing into *only* the
+        * sparse directory.
+        */
+       setup_traverse_info(&info, src[0]->name);
+       info.fn = unpack_sparse_callback;
+       info.data = o;
+       info.show_all_errors = o->show_all_errors;
+       info.pathspec = o->pathspec;
+
+       /* Get the tree descriptors of the sparse directory in each of the merging trees */
+       for (i = 0; i < n; i++)
+               tree_bufs[i] = fill_tree_descriptor(o->src_index->repo, &t[i],
+                                                   src[i] && !is_null_oid(&src[i]->oid) ? &src[i]->oid : NULL);
+
+       ret = traverse_trees(o->src_index, n, t, &info);
+
+       for (i = 0; i < n; i++)
+               free(tree_bufs[i]);
+
+       return ret;
+}
+
 static int deleted_entry(const struct cache_entry *ce,
                         const struct cache_entry *old,
                         struct unpack_trees_options *o)

@@ -2734,6 +2801,14 @@ int twoway_merge(const struct cache_entry * const *src,
                         * reject the merge instead.
                         */
                        return merged_entry(newtree, current, o);
+               } else if (S_ISSPARSEDIR(current->ce_mode)) {
+                       /*
+                        * The sparse directories differ, but we don't know whether that's
+                        * because of two different files in the directory being modified
+                        * (can be trivially merged) or if there is a real file conflict.
+                        * Merge the sparse directory by OID to compare file-by-file.
+                        */
+                       return merged_sparse_dir(src, 3, o);
                } else
                        return reject_merge(current, o);

Quoted 3 lines

unpack-trees.c +0 -1

        }
--

gitgitgadget

It would be nice to have a couple of tests. In particular, one designed to see what happens when we need to traverse into subdirectories of sparse directory entries and paths different between the two trees being merged.

Quoted 111 lines · Elijah Newren

Quoted 21 lines · Victoria Dye via GitGitGadget

From: Victoria Dye <[email protected]>

Enable two-way merge with 'git read-tree' without expanding the sparse index. When in a sparse index, a two-way merge will trivially succeed as long as there are not changes to the same sparse directory in multiple trees (i.e., sparse directory-level "edit-edit" conflicts). If there are such conflicts, the merge will fail despite the possibility that individual files could merge cleanly.

In order to resolve these "edit-edit" conflicts, "conflicted" sparse directories are - rather than rejected - merged by traversing their associated trees by OID. For each child of the sparse directory:

1. Files are merged as normal (see Documentation/git-read-tree.txt for details).
2. Subdirectories are treated as sparse directories and merged in 'twoway_merge'. If there are no conflicts, they are merged according to the rules in Documentation/git-read-tree.txt; otherwise, the subdirectory is recursively traversed and merged.

Quoted 2 lines

This process allows sparse directories to be individually merged at the necessary depth *without* expanding a full index.

The idea of merging directory-level entries turns out to be problematic _if_ rename detection is involved, but read-tree-style merges are only trivial merges that ignore rename detection. As such, this idea is perfectly reasonable, and is a good way to go. Nicely done.

Mostly the patch looks good. There's one thing I'm wondering about, though...

Quoted 65 lines

Signed-off-by Victoria Dye <[email protected]>

---
 builtin/read-tree.c                      |  5 --
 t/t1092-sparse-checkout-compatibility.sh |  3 +-
 unpack-trees.c                           | 75 ++++++++++++++++++++++++
 3 files changed, 77 insertions(+), 6 deletions(-)

builtin/read-tree.c +0 -5

index a7b7f822281..5a421de2629 100644
@@ -225,11 +225,6 @@ int cmd_read_tree(int argc, const char **argv, const char *cmd_prefix)
                        opts.fn = opts.prefix ? bind_merge : oneway_merge;
                        break;
                case 2:
-                       /*
-                        * TODO: update twoway_merge to handle edit/edit conflicts in
-                        * sparse directories.
-                        */
-                       ensure_full_index(&the_index);
                        opts.fn = twoway_merge;
                        opts.initial_checkout = is_cache_unborn();
                        break;

t/t1092-sparse-checkout-compatibility.sh +2 -1

index a404be0a10f..d6f19682d65 100755
@@ -1411,7 +1411,8 @@ test_expect_success 'sparse index is not expanded: read-tree' '
        init_repos &&
 
        ensure_not_expanded checkout -b test-branch update-folder1 &&
-       for MERGE_TREES in "update-folder2"
+       for MERGE_TREES in "update-folder2" \
+                          "base update-folder2"
        do
                ensure_not_expanded read-tree -mu $MERGE_TREES &&
                ensure_not_expanded reset --hard HEAD || return 1

unpack-trees.c +19 -0

index dba122a02bb..a4ace53904e 100644
@@ -1360,6 +1360,42 @@ static int is_sparse_directory_entry(struct cache_entry *ce,
        return sparse_dir_matches_path(ce, info, name);
 }
 
+static int unpack_sparse_callback(int n, unsigned long mask, unsigned long dirmask, struct name_entry *names, struct traverse_info *info)
+{
+       struct cache_entry *src[MAX_UNPACK_TREES + 1] = { NULL, };
+       struct unpack_trees_options *o = info->data;
+       int ret;
+
+       assert(o->merge);
+
+       /*
+        * Unlike in 'unpack_callback', where src[0] is derived from the index when
+        * merging, src[0] is a transient cache entry derived from the first tree
+        * provided. Create the temporary entry as if it came from a non-sparse index.
+        */
+       if (!is_null_oid(&names[0].oid)) {
+               src[0] = create_ce_entry(info, &names[0], 0,
+                                       &o->result, 1,
+                                       dirmask & (1ul << 0));
+               src[0]->ce_flags |= (CE_SKIP_WORKTREE | CE_NEW_SKIP_WORKTREE);
+       }

unpack-trees.c static int is_sparse_directory_entry(struct cache_entry *ce, · line 1391

Quoted 10 lines

unpack-trees.c +10 -0

+
+       /*
+        * 'unpack_single_entry' assumes that src[0] is derived directly from
+        * the index, rather than from an entry in 'names'. This is *not* true when
+        * merging a sparse directory, in which case names[0] is the "index" source
+        * entry. To match the expectations of 'unpack_single_entry', shift past the
+        * "index" tree (i.e., names[0]) and adjust 'names', 'n', 'mask', and
+        * 'dirmask' accordingly.
+        */
+       ret = unpack_single_entry(n - 1, mask >> 1, dirmask >> 1, src, names + 1, info);

So, you're passing one less entry to unpack_single_entry() when you've

Quoted 9 lines

traversed into a sparse directory...won't the traversal at the next subdirectory deeper then also pass one less entry to unpack_single_entry(), so after recursing a directory or two, you only have one directory left and it won't conflict with anything so it just uses that remaining tree? (Or maybe it passes the wrong number of arguments into twoway_merge()?) Did I miss something in the logic somewhere that avoids that issue? It'd be nice to test it out, which brings me to...

The answer itself is pretty straightforward (merged_sparse_dir(...) is called with n = 3, which is +1 to the n propagated throughout unpack_trees(...) for a two-way merge), but I'd like to take a more in-depth approach answering "why" in case it helps with review and/or anyone reading along.

Suppose you are performing a two-way merge, e.g. with the command git read-tree my-base other-commit. The repo contains the following files:

.

├── bar
│   └── f1
├── baz
│   ├── deep
│   │   └── a
│   └── f2
├── foo
└── foo1

Additionally:

1. 'other-commit' is identical to the index
2. 'baz/' is a sparse directory

With those assumptions in mind, below are excerpts of the execution path for merging a file, a non-sparse directory, and a sparse directory (with values for arguments indicated where appropriate):

MERGING FILE 'foo'
------------------
unpack_trees(len = 2, t = [my-base, other-commit], ...)
-> traverse_trees(..., n = 2, t = [my-base, other-commit], ...)
-> unpack_callback(n = 2, ..., names = [my-base:foo, other-commit:foo], ...)

    -> unpack_single_entry(n = 2, ..., src = [INDEX:foo, NULL, NULL],
                           names = [my-base:foo, other-commit:foo], ...)
      -> call_unpack_fn(src = [INDEX:foo, my-base:foo, other-commit:foo], ...)
        -> twoway_merge(src = [INDEX:foo, my-base:foo, other-commit:foo] ...)
  -> unpack_callback(n = 2, ..., names = [my-base:foo1, other-commit:foo1], ...)
    ...

MERGING NON-SPARSE DIRECTORY 'bar/'
----------------------------------
unpack_trees(len = 2, t = [my-base, other-commit], ...)
-> traverse_trees(..., n = 2, t = [my-base, other-commit], ...)
-> unpack_callback(n = 2, ..., names = [my-base:bar/, other-commit:bar/], ...)

    -> unpack_single_entry(n = 2, ..., src = [NULL, NULL, NULL],
                           names = [my-base:bar/, other-commit:bar/], ...)
    -> traverse_trees_recursive(n = 2, ..., names = [my-base:bar/, other-commit:bar/], ...)
      -> traverse_trees(..., n = 2, t = [my-base, other-commit], ...)
        -> unpack_callback(n = 2, ..., names = [my-base:bar/f1, other-commit:bar/f1], ...)
          ...

MERGING SPARSE DIRECTORY 'baz/'
------------------------------
unpack_trees(len = 2, t = [my-base, other-commit], ...)
-> traverse_trees(..., n = 2, t = [my-base, other-commit], ...)
-> unpack_callback(n = 2, ..., names = [my-base:baz/, other-commit:baz/], ...)

    -> unpack_single_entry(n = 2, ..., src = [INDEX:baz/, NULL, NULL],
                           names = [my-base:baz/, other-commit:baz/], ...)
      -> call_unpack_fn(src = [INDEX:baz/, my-base:baz/, other-commit:baz/], ...)
        -> twoway_merge(src = [INDEX:baz/, my-base:baz/, other-commit:baz/] ...)
  -> unpack_callback(n = 2, ..., names = [my-base:foo, other-commit:foo], ...)
    ...

Note that, throughout this process, n = 2 despite the fact that twoway_merge is actually called with *three* source entries, because src[0] is the traversed entry *as it appears in the index*. Additionally, because there are no differences between the index and 'other-commit', 'baz/' is merged without conflict in basically the same way as 'foo'.

Now suppose you update the the index to differ from 'other-commit':

1. 'baz/deep/a' is different between the index and 'my-base', same between 'my-base' and 'other-commit'
2. 'baz/f2' is different between 'my-base' and 'other-commit', same between the index and 'my-base'

Before this patch, twoway_merge would reject the merge entirely because the sparse directory 'baz/' has three different tree OIDs between the index, 'my-base' , and 'other-commit'. However, these changes *should* be mergeable as long as you merge 'baz/deep/' separately from 'baz/f2'.

The way we do this is by traversing the 'baz/' index entry the same way we traverse 'my-base' and 'other-commit' so we can circumvent populating src[0] from the index. The execution path looks something like this (when started at the sparse directory's twoway_merge):

MERGING CONFLICT IN SPARSE 'baz/'
---------------------------------
twoway_merge(src = [INDEX:baz/, my-base:baz/, other-commit:baz/] ...) -> merged_sparse_dir(src = [INDEX:baz/, my-base:baz/, other-commit:baz/], n = 3, ...)
-> traverse_trees(..., n = 3, t = [INDEX^{tree}, my-base, other-commit], ...)

    -> unpack_sparse_callback(n = 3, ...,
                              names = [INDEX^{tree}:baz/deep/, my-base:baz/deep/, other-commit:baz/deep/])
      -> unpack_single_entry(n = 2, ..., src = [INDEX^{tree}:baz/deep/, NULL, NULL],
                             names = [my-base:baz/deep/, other-commit:baz/deep/], ...)
        -> call_unpack_fn(src = [INDEX^{tree}:baz/deep/, my-base:baz/deep/, other-commit:baz/deep/], ...)
          -> twoway_merge(src = [INDEX^{tree}:baz/deep/, my-base:baz/deep/, other-commit:baz/deep/] ...)
    -> unpack_sparse_callback(n = 3, ...,
                              names = [INDEX^{tree}:baz/f2, my-base:baz/f2, other-commit:baz/f2])
      -> unpack_single_entry(n = 2, ..., src = [INDEX^{tree}:baz/f2, NULL, NULL],
                             names = [my-base:baz/f2, other-commit:baz/f2], ...)
        -> call_unpack_fn(src = [INDEX^{tree}:baz/f2, my-base:baz/f2, other-commit:baz/f2], ...)
          -> twoway_merge(src = [INDEX^{tree}:baz/f2, my-base:baz/f2, other-commit:baz/f2] ...)

Here, unpack_sparse_callback transforms its inputs (from traverse_trees) into the those needed by unpack_single_entry. Unlike unpack_callback, which extracts its src[0] from the index, unpack_sparse_callback creates src[0] from the first tree in names. Then, because unpack_single_entry expects n = 2 with a populated src[0] and the two remaining trees in names, it subtracts 1 from its value of n and shifts names (along with other arguments like mask and dirmask). As you can see, this could continue recursing without losing trees, since the first tree in the merged_sparse_dir path is basically storage for the index as the traversal continues.

Please let me know if I can clarify anything - this explanation more-or-less corresponds to how I understood the problem while solving it, but it's still pretty dense and there could be details I'm not conveying well or taking for granted.

Quoted 62 lines

Quoted 62 lines

unpack-trees.c +46 -0

+
+       if (src[0])
+               discard_cache_entry(src[0]);
+
+       return ret >= 0 ? mask : -1;
+}
+
 /*
  * Note that traverse_by_cache_tree() duplicates some logic in this function
  * without actually calling it. If you change the logic here you may need to

@@ -2464,6 +2500,37 @@ static int merged_entry(const struct cache_entry *ce,
        return 1;
 }
 
+static int merged_sparse_dir(const struct cache_entry * const *src, int n,
+                            struct unpack_trees_options *o)
+{
+       struct tree_desc t[MAX_UNPACK_TREES + 1];
+       void * tree_bufs[MAX_UNPACK_TREES + 1];
+       struct traverse_info info;
+       int i, ret;
+
+       /*
+        * Create the tree traversal information for traversing into *only* the
+        * sparse directory.
+        */
+       setup_traverse_info(&info, src[0]->name);
+       info.fn = unpack_sparse_callback;
+       info.data = o;
+       info.show_all_errors = o->show_all_errors;
+       info.pathspec = o->pathspec;
+
+       /* Get the tree descriptors of the sparse directory in each of the merging trees */
+       for (i = 0; i < n; i++)
+               tree_bufs[i] = fill_tree_descriptor(o->src_index->repo, &t[i],
+                                                   src[i] && !is_null_oid(&src[i]->oid) ? &src[i]->oid : NULL);
+
+       ret = traverse_trees(o->src_index, n, t, &info);
+
+       for (i = 0; i < n; i++)
+               free(tree_bufs[i]);
+
+       return ret;
+}
+
 static int deleted_entry(const struct cache_entry *ce,
                         const struct cache_entry *old,
                         struct unpack_trees_options *o)

@@ -2734,6 +2801,14 @@ int twoway_merge(const struct cache_entry * const *src,
                         * reject the merge instead.
                         */
                        return merged_entry(newtree, current, o);
+               } else if (S_ISSPARSEDIR(current->ce_mode)) {
+                       /*
+                        * The sparse directories differ, but we don't know whether that's
+                        * because of two different files in the directory being modified
+                        * (can be trivially merged) or if there is a real file conflict.
+                        * Merge the sparse directory by OID to compare file-by-file.
+                        */
+                       return merged_sparse_dir(src, 3, o);
                } else
                        return reject_merge(current, o);

Quoted 8 lines

Quoted 3 lines

unpack-trees.c +0 -1

        }
--

gitgitgadget

It would be nice to have a couple of tests. In particular, one designed to see what happens when we need to traverse into subdirectories of sparse directory entries and paths different between the two trees being merged.

There were supposed to be "ensure_not_expanded" tests added in this patch, but they ended up in [7/7] - I'll move them back in my next version.

Additionally, the 't1092' test 'read-tree --merge with edit/edit conflicts in sparse directories' contains examples of merges that require recursing into sparse directories (added back in [3/7] to establish expected behavior before changing read-tree).

Like previous integrations [1] [2], this series allows 'git read-tree' to operate using a sparse index.

The first two patches are bugfixes for issues found while implementing the 'read-tree' integration:

* The first (patch 1/7) fixes an edge case in which a repo with no in-cone files or directories would have its root collapsed into a sparse directory; the fix ensures the root directory is never collapsed into a sparse directory.
* The second (patch 2/7) corrects the 'git status' reporting of changes nested inside the subdirectory of a sparse directory, ensuring that the modified file (not the subdirectory) is correctly reported as having changes.

The remainder of the series focuses on utilizing the sparse index in 'git read-tree'. After some baseline behavior-establishing tests (patch 3/7), sparse index usage is trivially enabled (patch 4/7) for 'read-tree' except:

* usage with '--prefix'
* two- and three-way merge

These cases require additional changes in order to work as expected (i.e., outwardly matching non-sparse index sparse-checkout). For the former, the sparse index can be enabled as long as the index is expanded when the prefix is a directory outside the sparse cone (patch 5/7). For the latter, sparse directories that cannot be trivially merged must have their contents merged file-by-file, done by recursively traversing the trees represented by the sparse directories (patches 6/7 & 7/7).

From: Victoria Dye <[email protected]>

Add the 'recursive' flag to 'wt_status_collect_changes_index(...)'. Without

the 'recursive' flag, 'git status' could report index changes incorrectly when the following conditions were met:

* sparse index is enabled
* there is a difference between the index and HEAD in a file inside a *subdirectory* of a sparse directory
* the sparse directory index entry is *not* expanded in-core

In this scenario, 'git status' would not recurse into the sparse directory's subdirectories to identify which file contained the difference between the index and HEAD. Instead, it would report the immediate subdirectory itself as "modified".

Example:

$ git init
$ mkdir -p sparse/sub
$ echo test >sparse/sub/foo
$ git add .
$ git commit -m "commit 1"
$ echo somethingelse >sparse/sub/foo
$ git add .
$ git commit -a -m "commit 2"
$ git sparse-checkout set --cone --sparse-index 'sparse'
$ git reset --soft HEAD~1
$ git status
On branch master
You are in a sparse checkout.

Changes to be committed:
(use "git restore --staged <file>..." to unstage)
modified: sparse/sub

The 'recursive' diff option in 'wt_status_collect_changes_index' corrects this by indicating that 'git status' should recurse into sparse directories to find modified files. Given the same repository setup as the example above, the corrected result of git status is:

$ git status
On branch master
You are in a sparse checkout.

Changes to be committed:
(use "git restore --staged <file>..." to unstage)
modified: sparse/sub/foo

Signed-off-by Victoria Dye <[email protected]>

---
 t/t1092-sparse-checkout-compatibility.sh | 7 +++++++
 wt-status.c                              | 9 +++++++++
 2 files changed, 16 insertions(+)

t/t1092-sparse-checkout-compatibility.sh +7 -0

index 9ef7cd80885..b1dcaa0e642 100755
@@ -278,6 +278,13 @@ test_expect_success 'status with options' '
        test_all_match git status --porcelain=v2 -uno
 '
 
+test_expect_success 'status with diff in unexpanded sparse directory' '
+       init_repos &&
+       test_all_match git checkout rename-base &&
+       test_all_match git reset --soft rename-out-to-out &&
+       test_all_match git status --porcelain=v2
+'
+
 test_expect_success 'status reports sparse-checkout' '
        init_repos &&
        git -C sparse-checkout status >full &&

wt-status.c +0 -0

index 335e723a71e..4a5b9beeca1 100644
@@ -651,6 +651,15 @@ static void wt_status_collect_changes_index(struct wt_status *s)
        rev.diffopt.detect_rename = s->detect_rename >= 0 ? s->detect_rename : rev.diffopt.detect_rename;

wt-status.c +1 -1

+
        copy_pathspec(&rev.prune_data, &s->pathspec);
        run_diff_index(&rev, 1);
        object_array_clear(&rev.pending);
--

gitgitgadget

Quoted 4 lines · Victoria Dye via GitGitGadget

From: Victoria Dye <[email protected]>

Add the 'recursive' flag to 'wt_status_collect_changes_index(...)'. Without

Perhaps "Set the 'recursive' diff option flag in 'wt_status_collect_changes_index(...)'" ? There's no function argument named 'recursive' in wt_status_collect_changes_index() before or after your changes, which is what the wording led me to think of.

Quoted 76 lines

the 'recursive' flag, 'git status' could report index changes incorrectly when the following conditions were met:

* sparse index is enabled
* there is a difference between the index and HEAD in a file inside a *subdirectory* of a sparse directory
* the sparse directory index entry is *not* expanded in-core

In this scenario, 'git status' would not recurse into the sparse directory's subdirectories to identify which file contained the difference between the index and HEAD. Instead, it would report the immediate subdirectory itself as "modified".

Example:

$ git init
$ mkdir -p sparse/sub
$ echo test >sparse/sub/foo
$ git add .
$ git commit -m "commit 1"
$ echo somethingelse >sparse/sub/foo
$ git add .
$ git commit -a -m "commit 2"
$ git sparse-checkout set --cone --sparse-index 'sparse'
$ git reset --soft HEAD~1
$ git status
On branch master
You are in a sparse checkout.

Changes to be committed:
(use "git restore --staged <file>..." to unstage)
modified: sparse/sub

The 'recursive' diff option in 'wt_status_collect_changes_index' corrects this by indicating that 'git status' should recurse into sparse directories to find modified files. Given the same repository setup as the example above, the corrected result of git status is:

$ git status
On branch master
You are in a sparse checkout.

Changes to be committed:
(use "git restore --staged <file>..." to unstage)
modified: sparse/sub/foo

Signed-off-by Victoria Dye <[email protected]>

---
 t/t1092-sparse-checkout-compatibility.sh | 7 +++++++
 wt-status.c                              | 9 +++++++++
 2 files changed, 16 insertions(+)

t/t1092-sparse-checkout-compatibility.sh +7 -0

index 9ef7cd80885..b1dcaa0e642 100755
@@ -278,6 +278,13 @@ test_expect_success 'status with options' '
        test_all_match git status --porcelain=v2 -uno
 '
 
+test_expect_success 'status with diff in unexpanded sparse directory' '
+       init_repos &&
+       test_all_match git checkout rename-base &&
+       test_all_match git reset --soft rename-out-to-out &&
+       test_all_match git status --porcelain=v2
+'
+
 test_expect_success 'status reports sparse-checkout' '
        init_repos &&
        git -C sparse-checkout status >full &&

wt-status.c +0 -0

index 335e723a71e..4a5b9beeca1 100644
@@ -651,6 +651,15 @@ static void wt_status_collect_changes_index(struct wt_status *s)
        rev.diffopt.detect_rename = s->detect_rename >= 0 ? s->detect_rename : rev.diffopt.detect_rename;

wt-status.c static void wt_status_collect_changes_index(struct wt_status *s) · line 661

Quoted 10 lines

wt-status.c +8 -0

        rev.diffopt.rename_limit = s->rename_limit >= 0 ? s->rename_limit : rev.diffopt.rename_limit;
        rev.diffopt.rename_score = s->rename_score >= 0 ? s->rename_score : rev.diffopt.rename_score;
+
+       /*
+        * The `recursive` option must be enabled to show differences in files
+        * *more than* one level deep in a sparse directory index entry (e.g., given
+        * sparse directory 'sparse-dir/', reporting a difference in the file
+        * 'sparse-dir/another-dir/my-file').
+        */
+       rev.diffopt.flags.recursive = 1;

Kind of clever, and makes sense.

I'm wondering if there's an alternate wording that might be helpful here or in the commit message, that instead of just saying the 'recursive' option is necessary, perhaps says a little bit about why it helps. In particular, the diff machinery, by default, is not recursive and stops at comparing the first level of trees. (See e.g. the -r option in diff-tree, it's just that it's turned on by default in 'git diff' and by the -p option in 'git log'.) I'm guessing the recursive option never needed to be turned on previously within wt-status, due to something about the nature of the index only holding files previously. Now, however, the sparse index changes that. (And it also suggests that perhaps we should look to see if other commands run the diff machinery without the recursive flag, and see if they need it now due to sparse indices.)

Granted, I'm not totally sure how to work these facts in (in part because I don't know how comparison to the index normally avoids the need for the recursive flag), and maybe what you have is fine. Just thought I'd point it out since I wasn't aware of the non-recursive nature of the diff machinery until I started doing things with diff-tree.

Quoted 7 lines

wt-status.c +1 -1

+
        copy_pathspec(&rev.prune_data, &s->pathspec);
        run_diff_index(&rev, 1);
        object_array_clear(&rev.pending);
--

gitgitgadget

From: Victoria Dye <[email protected]>

Add tests focused on how 'git read-tree' behaves in sparse checkouts. Extra emphasis is placed on interactions with files outside the sparse cone, e.g. merges with out-of-cone conflicts.

Signed-off-by Victoria Dye <[email protected]>

---
 t/perf/p2000-sparse-operations.sh        |  1 +
 t/t1092-sparse-checkout-compatibility.sh | 85 ++++++++++++++++++++++++
 2 files changed, 86 insertions(+)

t/perf/p2000-sparse-operations.sh +1 -0

index 2a7106b9495..382716cfca9 100755
@@ -117,6 +117,7 @@ test_perf_on_all git diff
 test_perf_on_all git diff --cached
 test_perf_on_all git blame $SPARSE_CONE/a
 test_perf_on_all git blame $SPARSE_CONE/f3/a
+test_perf_on_all git read-tree -mu HEAD
 test_perf_on_all git checkout-index -f --all
 test_perf_on_all git update-index --add --remove $SPARSE_CONE/a
 

t/t1092-sparse-checkout-compatibility.sh +43 -0

index b1dcaa0e642..9d58da4e925 100755
@@ -819,6 +819,91 @@ test_expect_success 'update-index --cacheinfo' '
        test_cmp expect sparse-checkout-out
 '
 
+test_expect_success 'read-tree --merge with files outside sparse definition' '
+       init_repos &&
+
+       test_all_match git checkout -b test-branch update-folder1 &&
+       for MERGE_TREES in "base HEAD update-folder2" \
+                          "update-folder1 update-folder2" \
+                          "update-folder2"
+       do
+               # Clean up and remove on-disk files
+               test_all_match git reset --hard HEAD &&
+               test_sparse_match git sparse-checkout reapply &&
+
+               # Although the index matches, without --no-sparse-checkout, outside-of-
+               # definition files will not exist on disk for sparse checkouts
+               test_all_match git read-tree -mu $MERGE_TREES &&
+               test_all_match git status --porcelain=v2 &&
+               test_path_is_missing sparse-checkout/folder2 &&
+               test_path_is_missing sparse-index/folder2 &&
+
+               test_all_match git read-tree --reset -u HEAD &&
+               test_all_match git status --porcelain=v2 &&
+
+               test_all_match git read-tree -mu --no-sparse-checkout $MERGE_TREES &&
+               test_all_match git status --porcelain=v2 &&
+               test_cmp sparse-checkout/folder2/a sparse-index/folder2/a &&
+               test_cmp sparse-checkout/folder2/a full-checkout/folder2/a || return 1
+       done
+'
+
+test_expect_success 'read-tree --merge with edit/edit conflicts in sparse directories' '
+       init_repos &&
+
+       # Merge of multiple changes to same directory (but not same files) should
+       # succeed
+       test_all_match git read-tree -mu base rename-base update-folder1 &&
+       test_all_match git status --porcelain=v2 &&
+
+       test_all_match git reset --hard &&
+
+       test_all_match git read-tree -mu rename-base update-folder2 &&
+       test_all_match git status --porcelain=v2 &&
+
+       test_all_match git reset --hard &&

t/t1092-sparse-checkout-compatibility.sh +32 -1

+       test_all_match test_must_fail git read-tree --prefix=folder1/ -u update-folder1 &&
+
+       test_all_match git read-tree --prefix=folder2/0 -u rename-base &&
+       test_path_is_missing sparse-checkout/folder2 &&
+       test_path_is_missing sparse-index/folder2 &&
+
+       test_all_match git read-tree --reset -u HEAD &&
+       test_all_match git read-tree --prefix=folder2/0 -u --no-sparse-checkout rename-base &&
+       test_cmp sparse-checkout/folder2/0/a sparse-index/folder2/0/a &&
+       test_cmp sparse-checkout/folder2/0/a full-checkout/folder2/0/a
+'
+
+test_expect_success 'read-tree --merge with directory-file conflicts' '
+       init_repos &&
+
+       test_all_match git checkout -b test-branch rename-base &&
+
+       # Although the index matches, without --no-sparse-checkout, outside-of-
+       # definition files will not exist on disk for sparse checkouts
+       test_sparse_match git read-tree -mu rename-out-to-out &&
+       test_sparse_match git status --porcelain=v2 &&
+       test_path_is_missing sparse-checkout/folder2 &&
+       test_path_is_missing sparse-index/folder2 &&
+
+       test_sparse_match git read-tree --reset -u HEAD &&
+       test_sparse_match git status --porcelain=v2 &&
+
+       test_sparse_match git read-tree -mu --no-sparse-checkout rename-out-to-out &&
+       test_sparse_match git status --porcelain=v2 &&
+       test_cmp sparse-checkout/folder2/0/1 sparse-index/folder2/0/1
+'
+
 test_expect_success 'merge, cherry-pick, and rebase' '
        init_repos &&
 
--

gitgitgadget

Quoted 83 lines · Victoria Dye via GitGitGadget

From: Victoria Dye <[email protected]>

Add tests focused on how 'git read-tree' behaves in sparse checkouts. Extra emphasis is placed on interactions with files outside the sparse cone, e.g. merges with out-of-cone conflicts.

Signed-off-by Victoria Dye <[email protected]>

---
 t/perf/p2000-sparse-operations.sh        |  1 +
 t/t1092-sparse-checkout-compatibility.sh | 85 ++++++++++++++++++++++++
 2 files changed, 86 insertions(+)

t/perf/p2000-sparse-operations.sh +1 -0

index 2a7106b9495..382716cfca9 100755
@@ -117,6 +117,7 @@ test_perf_on_all git diff
 test_perf_on_all git diff --cached
 test_perf_on_all git blame $SPARSE_CONE/a
 test_perf_on_all git blame $SPARSE_CONE/f3/a
+test_perf_on_all git read-tree -mu HEAD
 test_perf_on_all git checkout-index -f --all
 test_perf_on_all git update-index --add --remove $SPARSE_CONE/a
 

t/t1092-sparse-checkout-compatibility.sh +50 -0

index b1dcaa0e642..9d58da4e925 100755
@@ -819,6 +819,91 @@ test_expect_success 'update-index --cacheinfo' '
        test_cmp expect sparse-checkout-out
 '
 
+test_expect_success 'read-tree --merge with files outside sparse definition' '
+       init_repos &&
+
+       test_all_match git checkout -b test-branch update-folder1 &&
+       for MERGE_TREES in "base HEAD update-folder2" \
+                          "update-folder1 update-folder2" \
+                          "update-folder2"
+       do
+               # Clean up and remove on-disk files
+               test_all_match git reset --hard HEAD &&
+               test_sparse_match git sparse-checkout reapply &&
+
+               # Although the index matches, without --no-sparse-checkout, outside-of-
+               # definition files will not exist on disk for sparse checkouts
+               test_all_match git read-tree -mu $MERGE_TREES &&
+               test_all_match git status --porcelain=v2 &&
+               test_path_is_missing sparse-checkout/folder2 &&
+               test_path_is_missing sparse-index/folder2 &&
+
+               test_all_match git read-tree --reset -u HEAD &&
+               test_all_match git status --porcelain=v2 &&
+
+               test_all_match git read-tree -mu --no-sparse-checkout $MERGE_TREES &&
+               test_all_match git status --porcelain=v2 &&
+               test_cmp sparse-checkout/folder2/a sparse-index/folder2/a &&
+               test_cmp sparse-checkout/folder2/a full-checkout/folder2/a || return 1
+       done
+'
+
+test_expect_success 'read-tree --merge with edit/edit conflicts in sparse directories' '
+       init_repos &&
+
+       # Merge of multiple changes to same directory (but not same files) should
+       # succeed
+       test_all_match git read-tree -mu base rename-base update-folder1 &&
+       test_all_match git status --porcelain=v2 &&
+
+       test_all_match git reset --hard &&
+
+       test_all_match git read-tree -mu rename-base update-folder2 &&
+       test_all_match git status --porcelain=v2 &&
+
+       test_all_match git reset --hard &&
+
+       test_all_match test_must_fail git read-tree -mu base update-folder1 rename-out-to-in &&
+       test_all_match test_must_fail git read-tree -mu rename-out-to-in update-folder1
+'
+
+test_expect_success 'read-tree --prefix outside sparse definition' '
+       init_repos &&

t/t1092-sparse-checkout-compatibility.sh test_expect_success 'update-index --cacheinfo' ' · line 874

Quoted 3 lines

t/t1092-sparse-checkout-compatibility.sh +3 -0

+
+       # Cannot read-tree --prefix with a single argument when files exist within
+       # prefix

Given the comments in the cover letter about --prefix needing special work, it's not clear to me whether the below is expected behavior or current-but-buggy behavior that you are testing and documenting. Could you clarify?

Quoted 38 lines

t/t1092-sparse-checkout-compatibility.sh +32 -1

+       test_all_match test_must_fail git read-tree --prefix=folder1/ -u update-folder1 &&
+
+       test_all_match git read-tree --prefix=folder2/0 -u rename-base &&
+       test_path_is_missing sparse-checkout/folder2 &&
+       test_path_is_missing sparse-index/folder2 &&
+
+       test_all_match git read-tree --reset -u HEAD &&
+       test_all_match git read-tree --prefix=folder2/0 -u --no-sparse-checkout rename-base &&
+       test_cmp sparse-checkout/folder2/0/a sparse-index/folder2/0/a &&
+       test_cmp sparse-checkout/folder2/0/a full-checkout/folder2/0/a
+'
+
+test_expect_success 'read-tree --merge with directory-file conflicts' '
+       init_repos &&
+
+       test_all_match git checkout -b test-branch rename-base &&
+
+       # Although the index matches, without --no-sparse-checkout, outside-of-
+       # definition files will not exist on disk for sparse checkouts
+       test_sparse_match git read-tree -mu rename-out-to-out &&
+       test_sparse_match git status --porcelain=v2 &&
+       test_path_is_missing sparse-checkout/folder2 &&
+       test_path_is_missing sparse-index/folder2 &&
+
+       test_sparse_match git read-tree --reset -u HEAD &&
+       test_sparse_match git status --porcelain=v2 &&
+
+       test_sparse_match git read-tree -mu --no-sparse-checkout rename-out-to-out &&
+       test_sparse_match git status --porcelain=v2 &&
+       test_cmp sparse-checkout/folder2/0/1 sparse-index/folder2/0/1
+'
+
 test_expect_success 'merge, cherry-pick, and rebase' '
        init_repos &&
 
--

gitgitgadget

From: Victoria Dye <[email protected]>

Add tests focused on how 'git read-tree' behaves in sparse checkouts. Extra emphasis is placed on interactions with files outside the sparse cone, e.g. merges with out-of-cone conflicts.

Signed-off-by Victoria Dye <[email protected]>

---
 t/perf/p2000-sparse-operations.sh        |  1 +
 t/t1092-sparse-checkout-compatibility.sh | 85 ++++++++++++++++++++++++
 2 files changed, 86 insertions(+)

t/perf/p2000-sparse-operations.sh +1 -0

index 2a7106b9495..382716cfca9 100755
@@ -117,6 +117,7 @@ test_perf_on_all git diff
 test_perf_on_all git diff --cached
 test_perf_on_all git blame $SPARSE_CONE/a
 test_perf_on_all git blame $SPARSE_CONE/f3/a
+test_perf_on_all git read-tree -mu HEAD
 test_perf_on_all git checkout-index -f --all
 test_perf_on_all git update-index --add --remove $SPARSE_CONE/a
 

t/t1092-sparse-checkout-compatibility.sh +18 -0

index b1dcaa0e642..9d58da4e925 100755
@@ -819,6 +819,91 @@ test_expect_success 'update-index --cacheinfo' '
 	test_cmp expect sparse-checkout-out
 '
 
+test_expect_success 'read-tree --merge with files outside sparse definition' '
+	init_repos &&
+
+	test_all_match git checkout -b test-branch update-folder1 &&
+	for MERGE_TREES in "base HEAD update-folder2" \
+			   "update-folder1 update-folder2" \
+			   "update-folder2"
+	do
+		# Clean up and remove on-disk files
+		test_all_match git reset --hard HEAD &&
+		test_sparse_match git sparse-checkout reapply &&
+
+		# Although the index matches, without --no-sparse-checkout, outside-of-
+		# definition files will not exist on disk for sparse checkouts
+		test_all_match git read-tree -mu $MERGE_TREES &&
+		test_all_match git status --porcelain=v2 &&
+		test_path_is_missing sparse-checkout/folder2 &&
+		test_path_is_missing sparse-index/folder2 &&

Quoted 50 lines · Victoria Dye via GitGitGadget

From: Victoria Dye <[email protected]>

Add tests focused on how 'git read-tree' behaves in sparse checkouts. Extra emphasis is placed on interactions with files outside the sparse cone, e.g. merges with out-of-cone conflicts.

Signed-off-by Victoria Dye <[email protected]>

---
 t/perf/p2000-sparse-operations.sh        |  1 +
 t/t1092-sparse-checkout-compatibility.sh | 85 ++++++++++++++++++++++++
 2 files changed, 86 insertions(+)

t/perf/p2000-sparse-operations.sh +1 -0

index 2a7106b9495..382716cfca9 100755
@@ -117,6 +117,7 @@ test_perf_on_all git diff
 test_perf_on_all git diff --cached
 test_perf_on_all git blame $SPARSE_CONE/a
 test_perf_on_all git blame $SPARSE_CONE/f3/a
+test_perf_on_all git read-tree -mu HEAD
 test_perf_on_all git checkout-index -f --all
 test_perf_on_all git update-index --add --remove $SPARSE_CONE/a
 

t/t1092-sparse-checkout-compatibility.sh +18 -0

index b1dcaa0e642..9d58da4e925 100755
@@ -819,6 +819,91 @@ test_expect_success 'update-index --cacheinfo' '
 	test_cmp expect sparse-checkout-out
 '
 
+test_expect_success 'read-tree --merge with files outside sparse definition' '
+	init_repos &&
+
+	test_all_match git checkout -b test-branch update-folder1 &&
+	for MERGE_TREES in "base HEAD update-folder2" \
+			   "update-folder1 update-folder2" \
+			   "update-folder2"
+	do
+		# Clean up and remove on-disk files
+		test_all_match git reset --hard HEAD &&
+		test_sparse_match git sparse-checkout reapply &&
+
+		# Although the index matches, without --no-sparse-checkout, outside-of-
+		# definition files will not exist on disk for sparse checkouts
+		test_all_match git read-tree -mu $MERGE_TREES &&
+		test_all_match git status --porcelain=v2 &&
+		test_path_is_missing sparse-checkout/folder2 &&
+		test_path_is_missing sparse-index/folder2 &&

t/t1092-sparse-checkout-compatibility.sh test_expect_success 'update-index --cacheinfo' ' · line 849

Quoted 10 lines

t/t1092-sparse-checkout-compatibility.sh +10 -0

+
+		test_all_match git read-tree --reset -u HEAD &&
+		test_all_match git status --porcelain=v2 &&
+
+		test_all_match git read-tree -mu --no-sparse-checkout $MERGE_TREES &&
+		test_all_match git status --porcelain=v2 &&
+		test_cmp sparse-checkout/folder2/a sparse-index/folder2/a &&
+		test_cmp sparse-checkout/folder2/a full-checkout/folder2/a || return 1
+	done
+'

Nit: Isn't this nicer/easier by unrolling the for-loop to the top-level, i.e.:

for MERGE_TREES in "base HEAD update-folder2" [...] do

	test_expect_success "'read-tree -mu $MERGE_TREES' with files outside sparse definition" '
		init_repos &&
		test_when_finished "test_all_match git reset --hard HEAD" &&
                ...
	'

done

It makes failures easier to reason about since you see which for-loop iteration you're in right away, and can e.g. pick one with --run.

And we can do the cleanup in test_when_finished instead of at the start of every loop.

Quoted 75 lines · Ævar Arnfjörð Bjarmason

Quoted 50 lines · Victoria Dye via GitGitGadget

From: Victoria Dye <[email protected]>

Add tests focused on how 'git read-tree' behaves in sparse checkouts. Extra emphasis is placed on interactions with files outside the sparse cone, e.g. merges with out-of-cone conflicts.

Signed-off-by Victoria Dye <[email protected]>

---
 t/perf/p2000-sparse-operations.sh        |  1 +
 t/t1092-sparse-checkout-compatibility.sh | 85 ++++++++++++++++++++++++
 2 files changed, 86 insertions(+)

t/perf/p2000-sparse-operations.sh +1 -0

index 2a7106b9495..382716cfca9 100755
@@ -117,6 +117,7 @@ test_perf_on_all git diff
 test_perf_on_all git diff --cached
 test_perf_on_all git blame $SPARSE_CONE/a
 test_perf_on_all git blame $SPARSE_CONE/f3/a
+test_perf_on_all git read-tree -mu HEAD
 test_perf_on_all git checkout-index -f --all
 test_perf_on_all git update-index --add --remove $SPARSE_CONE/a
 

t/t1092-sparse-checkout-compatibility.sh +18 -0

index b1dcaa0e642..9d58da4e925 100755
@@ -819,6 +819,91 @@ test_expect_success 'update-index --cacheinfo' '
 	test_cmp expect sparse-checkout-out
 '
 
+test_expect_success 'read-tree --merge with files outside sparse definition' '
+	init_repos &&
+
+	test_all_match git checkout -b test-branch update-folder1 &&
+	for MERGE_TREES in "base HEAD update-folder2" \
+			   "update-folder1 update-folder2" \
+			   "update-folder2"
+	do
+		# Clean up and remove on-disk files
+		test_all_match git reset --hard HEAD &&
+		test_sparse_match git sparse-checkout reapply &&
+
+		# Although the index matches, without --no-sparse-checkout, outside-of-
+		# definition files will not exist on disk for sparse checkouts
+		test_all_match git read-tree -mu $MERGE_TREES &&
+		test_all_match git status --porcelain=v2 &&
+		test_path_is_missing sparse-checkout/folder2 &&
+		test_path_is_missing sparse-index/folder2 &&

t/t1092-sparse-checkout-compatibility.sh test_expect_success 'update-index --cacheinfo' ' · line 849

Quoted 10 lines

t/t1092-sparse-checkout-compatibility.sh +10 -0

+
+		test_all_match git read-tree --reset -u HEAD &&
+		test_all_match git status --porcelain=v2 &&
+
+		test_all_match git read-tree -mu --no-sparse-checkout $MERGE_TREES &&
+		test_all_match git status --porcelain=v2 &&
+		test_cmp sparse-checkout/folder2/a sparse-index/folder2/a &&
+		test_cmp sparse-checkout/folder2/a full-checkout/folder2/a || return 1
+	done
+'

Nit: Isn't this nicer/easier by unrolling the for-loop to the top-level, i.e.:

for MERGE_TREES in "base HEAD update-folder2" [...] do

	test_expect_success "'read-tree -mu $MERGE_TREES' with files outside sparse definition" '
		init_repos &&
		test_when_finished "test_all_match git reset --hard HEAD" &&
                ...
	'

done

Quoted 3 lines

It makes failures easier to reason about since you see which for-loop iteration you're in right away, and can e.g. pick one with --run.

I like how this separates the test cases (while not adding any redundant/copied code). I'll update in the next version, thanks!

Quoted 2 lines

And we can do the cleanup in test_when_finished instead of at the start of every loop.

Because init_repos completely resets the test repos, this actually lets me remove the extra cleanup steps completely.

From: Victoria Dye <[email protected]>

When 'git read-tree' is provided with a prefix, expand the index only if the prefix is equivalent to a sparse directory or contained within one. If the index is not expanded in these cases, 'ce_in_traverse_path' will indicate that the relevant sparse directory is not in the prefix/traverse path, skipping past it and not unpacking the appropriate tree(s).

If the prefix is in-cone, its sparse subdirectories (if any) will be traversed correctly without index expansion.

Signed-off-by Victoria Dye <[email protected]>

---
 builtin/read-tree.c                      |  3 +--
 t/t1092-sparse-checkout-compatibility.sh |  8 ++++++-
 unpack-trees.c                           | 30 ++++++++++++++++++++++++
 3 files changed, 38 insertions(+), 3 deletions(-)

builtin/read-tree.c +1 -2

index c2fdbc2657f..a7b7f822281 100644
@@ -213,8 +213,7 @@ int cmd_read_tree(int argc, const char **argv, const char *cmd_prefix)
        if (opts.merge && !opts.index_only)
                setup_work_tree();
 
-       /* TODO: audit sparse index behavior in unpack_trees */
-       if (opts.skip_sparse_checkout || opts.prefix)
+       if (opts.skip_sparse_checkout)
                ensure_full_index(&the_index);
 
        if (opts.merge) {

t/t1092-sparse-checkout-compatibility.sh +7 -1

index ae44451a0a9..a404be0a10f 100755
@@ -1415,7 +1415,13 @@ test_expect_success 'sparse index is not expanded: read-tree' '
        do
                ensure_not_expanded read-tree -mu $MERGE_TREES &&
                ensure_not_expanded reset --hard HEAD || return 1
-       done
+       done &&
+
+       rm -rf sparse-index/deep/deeper2 &&
+       ensure_not_expanded add . &&
+       ensure_not_expanded commit -m "test" &&
+
+       ensure_not_expanded read-tree --prefix=deep/deeper2 -u deepest
 '
 
 test_expect_success 'ls-files' '

unpack-trees.c +1 -0

index 360844bda3a..dba122a02bb 100644
@@ -1739,6 +1739,36 @@ int unpack_trees(unsigned len, struct tree_desc *t, struct unpack_trees_options
                setup_standard_excludes(o->dir);
        }
 
+       /*

unpack-trees.c +6 -1

+                               ensure_full_index(o->src_index);
+
+                       strbuf_release(&ce_prefix);
+               }
+       }
+
        if (!core_apply_sparse_checkout || !o->update)
                o->skip_sparse_checkout = 1;
        if (!o->skip_sparse_checkout && !o->pl) {
--

gitgitgadget

Quoted 61 lines · Victoria Dye via GitGitGadget

From: Victoria Dye <[email protected]>

When 'git read-tree' is provided with a prefix, expand the index only if the prefix is equivalent to a sparse directory or contained within one. If the index is not expanded in these cases, 'ce_in_traverse_path' will indicate that the relevant sparse directory is not in the prefix/traverse path, skipping past it and not unpacking the appropriate tree(s).

If the prefix is in-cone, its sparse subdirectories (if any) will be traversed correctly without index expansion.

Signed-off-by Victoria Dye <[email protected]>

---
 builtin/read-tree.c                      |  3 +--
 t/t1092-sparse-checkout-compatibility.sh |  8 ++++++-
 unpack-trees.c                           | 30 ++++++++++++++++++++++++
 3 files changed, 38 insertions(+), 3 deletions(-)

builtin/read-tree.c +1 -2

index c2fdbc2657f..a7b7f822281 100644
@@ -213,8 +213,7 @@ int cmd_read_tree(int argc, const char **argv, const char *cmd_prefix)
        if (opts.merge && !opts.index_only)
                setup_work_tree();
 
-       /* TODO: audit sparse index behavior in unpack_trees */
-       if (opts.skip_sparse_checkout || opts.prefix)
+       if (opts.skip_sparse_checkout)
                ensure_full_index(&the_index);
 
        if (opts.merge) {

t/t1092-sparse-checkout-compatibility.sh +7 -1

index ae44451a0a9..a404be0a10f 100755
@@ -1415,7 +1415,13 @@ test_expect_success 'sparse index is not expanded: read-tree' '
        do
                ensure_not_expanded read-tree -mu $MERGE_TREES &&
                ensure_not_expanded reset --hard HEAD || return 1
-       done
+       done &&
+
+       rm -rf sparse-index/deep/deeper2 &&
+       ensure_not_expanded add . &&
+       ensure_not_expanded commit -m "test" &&
+
+       ensure_not_expanded read-tree --prefix=deep/deeper2 -u deepest
 '
 
 test_expect_success 'ls-files' '

unpack-trees.c +1 -0

index 360844bda3a..dba122a02bb 100644
@@ -1739,6 +1739,36 @@ int unpack_trees(unsigned len, struct tree_desc *t, struct unpack_trees_options
                setup_standard_excludes(o->dir);
        }
 
+       /*

unpack-trees.c int unpack_trees(unsigned len, struct tree_desc *t, struct unpack_trees_options · line 1752

Quoted 10 lines

unpack-trees.c +10 -0

+        * If the prefix is equal to or contained within a sparse directory, the
+        * index needs to be expanded to traverse with the specified prefix.
+        */
+       if (o->prefix && o->src_index->sparse_index) {
+               int prefix_len = strlen(o->prefix);
+
+               while (prefix_len > 0 && o->prefix[prefix_len - 1] == '/')
+                       prefix_len--;
+
+               if (prefix_len > 0) {

Is this condition check necessary? If we want some safety check here, could it instead be something like

   if (prefix_len <= 0)
       BUG("Broken prefix passed to unpack_trees");

and then dedent the following code? (Or are callers allowed to not sanitize their input before passing to unpack_trees(), meaning that we should use a die() rather than a BUG()?)

To test this idea, near the top of unpack_trees(), I added:

    if (o->prefix)
        assert(*o->prefix && *o->prefix != '/');

and reran all tests. They all ran without hitting that assertion. FWIW.

unpack-trees.c int unpack_trees(unsigned len, struct tree_desc *t, struct unpack_trees_options · line 1765

Quoted 13 lines

unpack-trees.c +13 -0

+                       struct strbuf ce_prefix = STRBUF_INIT;
+                       strbuf_grow(&ce_prefix, prefix_len + 1);
+                       strbuf_add(&ce_prefix, o->prefix, prefix_len);
+                       strbuf_addch(&ce_prefix, '/');
+
+                       /*
+                        * If the prefix is not inside the sparse cone, then the
+                        * index is explicitly expanded if it is found as a sparse
+                        * directory, or implicitly expanded (by 'index_name_pos')
+                        * if the path is inside a sparse directory.
+                        */
+                       if (!path_in_cone_mode_sparse_checkout(ce_prefix.buf, o->src_index) &&
+                           index_name_pos(o->src_index, ce_prefix.buf, ce_prefix.len) >= 0)

style nit: Can you rewrap both the comments and the code at 80 characters?

It took me a bit of playing and testing to understand these two lines. The comment helps, but it's still a bit dense to unpack; somehow I didn't understand that the comment was referring to index_name_pos()'s call to ensure_full_index(). Once I understood that, it all looks good.

Quoted 12 lines

unpack-trees.c +6 -1

+                               ensure_full_index(o->src_index);
+
+                       strbuf_release(&ce_prefix);
+               }
+       }
+
        if (!core_apply_sparse_checkout || !o->update)
                o->skip_sparse_checkout = 1;
        if (!o->skip_sparse_checkout && !o->pl) {
--

gitgitgadget

Quoted 77 lines · Elijah Newren

Quoted 61 lines · Victoria Dye via GitGitGadget

From: Victoria Dye <[email protected]>

When 'git read-tree' is provided with a prefix, expand the index only if the prefix is equivalent to a sparse directory or contained within one. If the index is not expanded in these cases, 'ce_in_traverse_path' will indicate that the relevant sparse directory is not in the prefix/traverse path, skipping past it and not unpacking the appropriate tree(s).

If the prefix is in-cone, its sparse subdirectories (if any) will be traversed correctly without index expansion.

Signed-off-by Victoria Dye <[email protected]>

---
 builtin/read-tree.c                      |  3 +--
 t/t1092-sparse-checkout-compatibility.sh |  8 ++++++-
 unpack-trees.c                           | 30 ++++++++++++++++++++++++
 3 files changed, 38 insertions(+), 3 deletions(-)

builtin/read-tree.c +1 -2

index c2fdbc2657f..a7b7f822281 100644
@@ -213,8 +213,7 @@ int cmd_read_tree(int argc, const char **argv, const char *cmd_prefix)
        if (opts.merge && !opts.index_only)
                setup_work_tree();
 
-       /* TODO: audit sparse index behavior in unpack_trees */
-       if (opts.skip_sparse_checkout || opts.prefix)
+       if (opts.skip_sparse_checkout)
                ensure_full_index(&the_index);
 
        if (opts.merge) {

t/t1092-sparse-checkout-compatibility.sh +7 -1

index ae44451a0a9..a404be0a10f 100755
@@ -1415,7 +1415,13 @@ test_expect_success 'sparse index is not expanded: read-tree' '
        do
                ensure_not_expanded read-tree -mu $MERGE_TREES &&
                ensure_not_expanded reset --hard HEAD || return 1
-       done
+       done &&
+
+       rm -rf sparse-index/deep/deeper2 &&
+       ensure_not_expanded add . &&
+       ensure_not_expanded commit -m "test" &&
+
+       ensure_not_expanded read-tree --prefix=deep/deeper2 -u deepest
 '
 
 test_expect_success 'ls-files' '

unpack-trees.c +1 -0

index 360844bda3a..dba122a02bb 100644
@@ -1739,6 +1739,36 @@ int unpack_trees(unsigned len, struct tree_desc *t, struct unpack_trees_options
                setup_standard_excludes(o->dir);
        }
 
+       /*

unpack-trees.c int unpack_trees(unsigned len, struct tree_desc *t, struct unpack_trees_options · line 1752

Quoted 10 lines

unpack-trees.c +10 -0

+        * If the prefix is equal to or contained within a sparse directory, the
+        * index needs to be expanded to traverse with the specified prefix.
+        */
+       if (o->prefix && o->src_index->sparse_index) {
+               int prefix_len = strlen(o->prefix);
+
+               while (prefix_len > 0 && o->prefix[prefix_len - 1] == '/')
+                       prefix_len--;
+
+               if (prefix_len > 0) {

Is this condition check necessary? If we want some safety check here, could it instead be something like

Quoted 3 lines

   if (prefix_len <= 0)
       BUG("Broken prefix passed to unpack_trees");

This condition was intended to skip unnecessary computation for the (probably unlikely, but still technically valid) case where the prefix is the repo root (e.g., '--prefix=/') - because the repo root is represented with only directory separator(s), prefix_len would be 0 after removing trailing '/'. In that scenario, the index won't need to be expanded, so we don't need to go looking in the index for that path.

None of that is particularly clear from reading the patch, though, so I'll add a comment & test covering it explicitly.

Quoted 23 lines

and then dedent the following code? (Or are callers allowed to not sanitize their input before passing to unpack_trees(), meaning that we should use a die() rather than a BUG()?)

To test this idea, near the top of unpack_trees(), I added:

    if (o->prefix)
        assert(*o->prefix && *o->prefix != '/');

and reran all tests. They all ran without hitting that assertion. FWIW.

unpack-trees.c int unpack_trees(unsigned len, struct tree_desc *t, struct unpack_trees_options · line 1765

Quoted 13 lines

unpack-trees.c +13 -0

+                       struct strbuf ce_prefix = STRBUF_INIT;
+                       strbuf_grow(&ce_prefix, prefix_len + 1);
+                       strbuf_add(&ce_prefix, o->prefix, prefix_len);
+                       strbuf_addch(&ce_prefix, '/');
+
+                       /*
+                        * If the prefix is not inside the sparse cone, then the
+                        * index is explicitly expanded if it is found as a sparse
+                        * directory, or implicitly expanded (by 'index_name_pos')
+                        * if the path is inside a sparse directory.
+                        */
+                       if (!path_in_cone_mode_sparse_checkout(ce_prefix.buf, o->src_index) &&
+                           index_name_pos(o->src_index, ce_prefix.buf, ce_prefix.len) >= 0)

Quoted 2 lines

style nit: Can you rewrap both the comments and the code at 80 characters?

I couldn't think of a way to wrap the condition that wouldn't make it more difficult to read. The best I could come up with was:

                        if (!path_in_cone_mode_sparse_checkout(ce_prefix.buf,
                                                               o->src_index) &&
                            index_name_pos(o->src_index,
                                           ce_prefix.buf,
                                           ce_prefix.len) >= 0)
                                ensure_full_index(o->src_index);

which, to me, is a bit hard to parse. Alternatively, though, I can move the prefix-checking logic into its own function (kind of like 'pathspec_needs_expanded_index(...)' in [1]), in which case I won't need to change the current wrapping to keep it under 80 characters.

[1] https://lore.kernel.org/git/822d7344587f698e73abba1ca726c3a905f7b403.1638201164.git.gitgitgadget@gmail.com/

Quoted 6 lines

It took me a bit of playing and testing to understand these two lines. The comment helps, but it's still a bit dense to unpack; somehow I didn't understand that the comment was referring to index_name_pos()'s call to ensure_full_index(). Once I understood that, it all looks good.

Sorry about that, I'll revise to make that clearer.

Quoted 12 lines

Quoted 12 lines

unpack-trees.c +6 -1

+                               ensure_full_index(o->src_index);
+
+                       strbuf_release(&ce_prefix);
+               }
+       }
+
        if (!core_apply_sparse_checkout || !o->update)
                o->skip_sparse_checkout = 1;
        if (!o->skip_sparse_checkout && !o->pl) {
--

gitgitgadget

Hi Victoria,

Quoted 83 lines · Victoria Dye

Quoted 77 lines · Elijah Newren

Quoted 61 lines · Victoria Dye via GitGitGadget

From: Victoria Dye <[email protected]>

When 'git read-tree' is provided with a prefix, expand the index only if the prefix is equivalent to a sparse directory or contained within one. If the index is not expanded in these cases, 'ce_in_traverse_path' will indicate that the relevant sparse directory is not in the prefix/traverse path, skipping past it and not unpacking the appropriate tree(s).

If the prefix is in-cone, its sparse subdirectories (if any) will be traversed correctly without index expansion.

Signed-off-by Victoria Dye <[email protected]>

---
 builtin/read-tree.c                      |  3 +--
 t/t1092-sparse-checkout-compatibility.sh |  8 ++++++-
 unpack-trees.c                           | 30 ++++++++++++++++++++++++
 3 files changed, 38 insertions(+), 3 deletions(-)

builtin/read-tree.c +1 -2

index c2fdbc2657f..a7b7f822281 100644
@@ -213,8 +213,7 @@ int cmd_read_tree(int argc, const char **argv, const char *cmd_prefix)
        if (opts.merge && !opts.index_only)
                setup_work_tree();
 
-       /* TODO: audit sparse index behavior in unpack_trees */
-       if (opts.skip_sparse_checkout || opts.prefix)
+       if (opts.skip_sparse_checkout)
                ensure_full_index(&the_index);
 
        if (opts.merge) {

t/t1092-sparse-checkout-compatibility.sh +7 -1

index ae44451a0a9..a404be0a10f 100755
@@ -1415,7 +1415,13 @@ test_expect_success 'sparse index is not expanded: read-tree' '
        do
                ensure_not_expanded read-tree -mu $MERGE_TREES &&
                ensure_not_expanded reset --hard HEAD || return 1
-       done
+       done &&
+
+       rm -rf sparse-index/deep/deeper2 &&
+       ensure_not_expanded add . &&
+       ensure_not_expanded commit -m "test" &&
+
+       ensure_not_expanded read-tree --prefix=deep/deeper2 -u deepest
 '
 
 test_expect_success 'ls-files' '

unpack-trees.c +1 -0

index 360844bda3a..dba122a02bb 100644
@@ -1739,6 +1739,36 @@ int unpack_trees(unsigned len, struct tree_desc *t, struct unpack_trees_options
                setup_standard_excludes(o->dir);
        }
 
+       /*

unpack-trees.c int unpack_trees(unsigned len, struct tree_desc *t, struct unpack_trees_options · line 1752

Quoted 10 lines

unpack-trees.c +10 -0

+        * If the prefix is equal to or contained within a sparse directory, the
+        * index needs to be expanded to traverse with the specified prefix.
+        */
+       if (o->prefix && o->src_index->sparse_index) {
+               int prefix_len = strlen(o->prefix);
+
+               while (prefix_len > 0 && o->prefix[prefix_len - 1] == '/')
+                       prefix_len--;
+
+               if (prefix_len > 0) {

Is this condition check necessary? If we want some safety check here, could it instead be something like

Quoted 3 lines

   if (prefix_len <= 0)
       BUG("Broken prefix passed to unpack_trees");

Quoted 6 lines

This condition was intended to skip unnecessary computation for the (probably unlikely, but still technically valid) case where the prefix is the repo root (e.g., '--prefix=/') - because the repo root is represented with only directory separator(s), prefix_len would be 0 after removing trailing '/'. In that scenario, the index won't need to be expanded, so we don't need to go looking in the index for that path.

Wow, that doesn't result in an error?!? That surprises me. I never even thought to test such a thing. Clearly, the following related command does give an error:

  git read-tree --prefix=/toplevel/ $TREE

(namely, "error: invalid path '/toplevel/subpath'")

whereas, the reason a single slash is accepted it because git is trying to be forgiving and treat the following two commands the same:

  git read-tree --prefix=subdir/ $TREE
  git read-tree --prefix=subdir $TREE

i.e. it tries to allow the trailing slash to be optional. And, by implementation quirk, making a trailing slash be optional turns out to mean that --prefix=/ is treated the same as no prefix at all, because empty string prefix just happens to give the same behavior as NULL prefix.

I think we should just throw an error if prefix starts with '/'. unpack_trees() can make it be a BUG() (and at the beginning of the function rather than down at this point and only inside some conditional). builtin/read-tree.c, the only thing that ever sets prefix in unpack_trees_options, should die() if it's passed something that starts with a '/'. Having paths start with a '/' is antithetical to how "prefix" is used throughout the codebase, though I guess I can see people making that mistake if they are used to gitignore-style patterns instead.

Quoted 47 lines

None of that is particularly clear from reading the patch, though, so I'll add a comment & test covering it explicitly.

Quoted 23 lines

and then dedent the following code? (Or are callers allowed to not sanitize their input before passing to unpack_trees(), meaning that we should use a die() rather than a BUG()?)

To test this idea, near the top of unpack_trees(), I added:

    if (o->prefix)
        assert(*o->prefix && *o->prefix != '/');

and reran all tests. They all ran without hitting that assertion. FWIW.

unpack-trees.c int unpack_trees(unsigned len, struct tree_desc *t, struct unpack_trees_options · line 1765

Quoted 13 lines

unpack-trees.c +13 -0

+                       struct strbuf ce_prefix = STRBUF_INIT;
+                       strbuf_grow(&ce_prefix, prefix_len + 1);
+                       strbuf_add(&ce_prefix, o->prefix, prefix_len);
+                       strbuf_addch(&ce_prefix, '/');
+
+                       /*
+                        * If the prefix is not inside the sparse cone, then the
+                        * index is explicitly expanded if it is found as a sparse
+                        * directory, or implicitly expanded (by 'index_name_pos')
+                        * if the path is inside a sparse directory.
+                        */
+                       if (!path_in_cone_mode_sparse_checkout(ce_prefix.buf, o->src_index) &&
+                           index_name_pos(o->src_index, ce_prefix.buf, ce_prefix.len) >= 0)

Quoted 2 lines

style nit: Can you rewrap both the comments and the code at 80 characters?

I couldn't think of a way to wrap the condition that wouldn't make it more difficult to read. The best I could come up with was:

                        if (!path_in_cone_mode_sparse_checkout(ce_prefix.buf,
                                                               o->src_index) &&
                            index_name_pos(o->src_index,
                                           ce_prefix.buf,
                                           ce_prefix.len) >= 0)
                                ensure_full_index(o->src_index);

which, to me, is a bit hard to parse. Alternatively, though, I can move the prefix-checking logic into its own function (kind of like 'pathspec_needs_expanded_index(...)' in [1]), in which case I won't need to change the current wrapping to keep it under 80 characters.

[1] https://lore.kernel.org/git/822d7344587f698e73abba1ca726c3a905f7b403.1638201164.git.gitgitgadget@gmail.com/

Quoted 8 lines

Quoted 6 lines

It took me a bit of playing and testing to understand these two lines. The comment helps, but it's still a bit dense to unpack; somehow I didn't understand that the comment was referring to index_name_pos()'s call to ensure_full_index(). Once I understood that, it all looks good.

Sorry about that, I'll revise to make that clearer.

Thanks. :-)

Quoted 12 lines

Quoted 12 lines

Quoted 12 lines

unpack-trees.c +6 -1

+                               ensure_full_index(o->src_index);
+
+                       strbuf_release(&ce_prefix);
+               }
+       }
+
        if (!core_apply_sparse_checkout || !o->update)
                o->skip_sparse_checkout = 1;
        if (!o->skip_sparse_checkout && !o->pl) {
--

gitgitgadget

Like previous integrations [1] [2], this series allows 'git read-tree' to operate using a sparse index.

The first two patches are bugfixes for issues found while implementing the 'read-tree' integration:

* The first (patch 1/7) fixes an edge case in which a repo with no in-cone files or directories would have its root collapsed into a sparse directory; the fix ensures the root directory is never collapsed into a sparse directory.
* The second (patch 2/7) corrects the 'git status' reporting of changes nested inside the subdirectory of a sparse directory, ensuring that the modified file (not the subdirectory) is correctly reported as having changes.

The remainder of the series focuses on utilizing the sparse index in 'git read-tree'. After some baseline behavior-establishing tests (patch 3/7), sparse index usage is trivially enabled (patch 4/7) for 'read-tree' except:

* usage with '--prefix'
* two- and three-way merge

These cases require additional changes in order to work as expected (i.e., outwardly matching non-sparse index sparse-checkout). For the former, the sparse index can be enabled as long as the index is expanded when the prefix is a directory outside the sparse cone (patch 5/7). For the latter, sparse directories that cannot be trivially merged must have their contents merged file-by-file, done by recursively traversing the trees represented by the sparse directories (patches 6/7 & 7/7).

Changes since V1
================

* switched an empty string check from '!strlen(path)' to the slightly-less-expensive '!*path'

Thanks!

* Victoria

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

Victoria Dye (7):
sparse-index: prevent repo root from becoming sparse
status: fix nested sparse directory diff in sparse index
read-tree: expand sparse checkout test coverage
read-tree: integrate with sparse index
read-tree: narrow scope of index expansion for '--prefix'
read-tree: make two-way merge sparse-aware
read-tree: make three-way merge sparse-aware

 builtin/read-tree.c                      |  10 +-
 dir.c                                    |   7 +-
 t/perf/p2000-sparse-operations.sh        |   1 +
 t/t1092-sparse-checkout-compatibility.sh | 129 +++++++++++++++++++++++
 unpack-trees.c                           | 121 ++++++++++++++++++++-
 wt-status.c                              |   9 ++
 6 files changed, 268 insertions(+), 9 deletions(-)

base-commit: e6ebfd0e8cbbd10878070c8a356b5ad1b3ca464e
Published-As: https://github.com/gitgitgadget/git/releases/tag/pr-1157%2Fvdye%2Fsparse%2Fread-tree-v2
Fetch-It-Via: git fetch https://github.com/gitgitgadget/git pr-1157/vdye/sparse/read-tree-v2
Pull-Request: https://github.com/gitgitgadget/git/pull/1157

Range-diff vs v1:

1: 90da1f9f33a ! 1: 744668eeece sparse-index: prevent repo root from becoming sparse
@@ Commit message
non-cone sparse-checkouts), the new check does not cause additional changes to how sparse patterns are applied.

+ Helped-by: Derrick Stolee <[email protected]>

Signed-off-by Victoria Dye <[email protected]>

## dir.c ##
@@ dir.c: static int path_in_sparse_checkout_1(const char *path,
+ * patterns, or the patterns are of the wrong type. */
- if (init_sparse_checkout_patterns(istate) ||
-+ if (!strlen(path) ||
++ if (!*path ||
+ init_sparse_checkout_patterns(istate) ||
(require_cone_mode &&
!istate->sparse_checkout_patterns->use_cone_patterns))

 2:  c21c9b9be34 = 2:  f0cff03b95d status: fix nested sparse directory diff in sparse index
 3:  ac42ae21d4a = 3:  ffe0b6aff2b read-tree: expand sparse checkout test coverage
 4:  5ee193bfa87 = 4:  cb7e0cf419c read-tree: integrate with sparse index
 5:  bea482b6b28 = 5:  4f05fa70209 read-tree: narrow scope of index expansion for '--prefix'
 6:  9fdcab038b2 = 6:  94c2aad2f93 read-tree: make two-way merge sparse-aware
 7:  1502e9acb32 = 7:  c4080e99d6e read-tree: make three-way merge sparse-aware

--
gitgitgadget

From: Victoria Dye <[email protected]>

(quoted diff) +25 -0

+static void update_sparsity_for_prefix(const char *prefix,
+				       struct index_state *istate)
+{
+	int prefix_len = strlen(prefix);
+	struct strbuf ce_prefix = STRBUF_INIT;
+
+	if (!istate->sparse_index)
+		return;
+
+	while (prefix_len > 0 && prefix[prefix_len - 1] == '/')
+		prefix_len--;
+
+	if (prefix_len <= 0)
+		BUG("Invalid prefix passed to update_sparsity_for_prefix");
+
+	strbuf_grow(&ce_prefix, prefix_len + 1);
+	strbuf_add(&ce_prefix, prefix, prefix_len);
+	strbuf_addch(&ce_prefix, '/');
+
+	/*
+	 * If the prefix points to a sparse directory or a path inside a sparse
+	 * directory, the index should be expanded. This is accomplished in one
+	 * of two ways:
+	 * - if the prefix is inside a sparse directory, it will be expanded by
+	 *   the 'ensure_full_index(...)' call in 'index_name_pos(...)'.

Quoted 26 lines · Victoria Dye via GitGitGadget

From: Victoria Dye <[email protected]>

(quoted diff) +25 -0

+static void update_sparsity_for_prefix(const char *prefix,
+				       struct index_state *istate)
+{
+	int prefix_len = strlen(prefix);
+	struct strbuf ce_prefix = STRBUF_INIT;
+
+	if (!istate->sparse_index)
+		return;
+
+	while (prefix_len > 0 && prefix[prefix_len - 1] == '/')
+		prefix_len--;
+
+	if (prefix_len <= 0)
+		BUG("Invalid prefix passed to update_sparsity_for_prefix");
+
+	strbuf_grow(&ce_prefix, prefix_len + 1);
+	strbuf_add(&ce_prefix, prefix, prefix_len);
+	strbuf_addch(&ce_prefix, '/');
+
+	/*
+	 * If the prefix points to a sparse directory or a path inside a sparse
+	 * directory, the index should be expanded. This is accomplished in one
+	 * of two ways:
+	 * - if the prefix is inside a sparse directory, it will be expanded by
+	 *   the 'ensure_full_index(...)' call in 'index_name_pos(...)'.

Review

Quoted 10 lines

(quoted diff) +10 -0

+	 * - if the prefix matches an existing sparse directory entry,
+	 *   'index_name_pos(...)' will return its index position, triggering
+	 *   the 'ensure_full_index(...)' below.
+	 */
+	if (!path_in_cone_mode_sparse_checkout(ce_prefix.buf, istate) &&
+	    index_name_pos(istate, ce_prefix.buf, ce_prefix.len) >= 0)
+		ensure_full_index(istate);
+
+	strbuf_release(&ce_prefix);
+}

Hm, I don't think I follow the rationale for having two different ways of expanding the index:

- If the prefix is inside a sparse directory, we should expand the index.
- If the prefix matches a sparse directory entry, we should expand the index.

So it seems like distinguishing between the two cases with index_name_pos(...) isn't necessary. I've attached a diff that does exactly this, and it passes t1092-sparse-checkout-compatibility.sh as far as I can tell. I've also amended the comment in a way that makes more sense to me, but I'm not 100% sure if it's accurate.

I'm also a little averse to using a side effect of index_name_pos() to achieve what we really want, so I'd prefer to get rid of the call if we can :)

----- >8 --------- >8 --------- >8 --------- >8 --------- >8 ----

unpack-trees.c +4 -10

index b876caca0d..5b07055605 100644
@@ -1749,17 +1749,11 @@ static void update_sparsity_for_prefix(const char *prefix,
 	strbuf_addch(&ce_prefix, '/');
 
 	/*
-	 * If the prefix points to a sparse directory or a path inside a sparse
-	 * directory, the index should be expanded. This is accomplished in one
-	 * of two ways:
-	 * - if the prefix is inside a sparse directory, it will be expanded by
-	 *   the 'ensure_full_index(...)' call in 'index_name_pos(...)'.
-	 * - if the prefix matches an existing sparse directory entry,
-	 *   'index_name_pos(...)' will return its index position, triggering
-	 *   the 'ensure_full_index(...)' below.
+	 * If the prefix points to a sparse directory or a path inside a
+	 * sparse directory (not within the sparse patterns), the index
+	 * should be expanded.
 	 */
-	if (!path_in_cone_mode_sparse_checkout(ce_prefix.buf, istate) &&
-	    index_name_pos(istate, ce_prefix.buf, ce_prefix.len) >= 0)
+	if (!path_in_cone_mode_sparse_checkout(ce_prefix.buf, istate))
 		ensure_full_index(istate);
 
 	strbuf_release(&ce_prefix);

There's an (admittedly subtle if you aren't familiar with sparse index) distinction between a "sparse directory" index entry and "a directory outside the sparse-checkout cone with SKIP_WORKTREE enabled on its entries". Ultimately, that's what necessitates the two checks but, as in [1], I want to use this as an opportunity to shed some light on what 'unpack_trees(...)' does.

Using our example above, suppose 'baz/' is partially expanded in the index, with the following index contents:

H bar/f1
S baz/deep/
S baz/f2
H foo
H foo1

If we use the prefix 'baz/' here, we actually traverse the trees properly:
'baz/deep/' and 'baz/f2' will be found and merged - no index expansion needed! But if we only checked '!path_in_cone_mode_sparse_checkout(...)', we would have expanded the index because 'baz/' is outside the sparse cone.

This presents a problem because index expansion is *extremely* expensive - we should avoid it whenever possible. That's where checking 'index_name_pos(...)' comes in: if the directory is in the index as a sparse directory, the position is '>= 0' and 'ensure_full_index(...)' is called; if the directory is inside an existing sparse directory, the position will be '< 0' but the index will be expanded implicitly. In every other case, we avoid expanding the index and proceed with the merge as normal.

Like previous integrations [1] [2], this series allows 'git read-tree' to operate using a sparse index.

The first three patches are bugfixes for issues found while implementing the 'read-tree' integration:

* The first (patch [1/8]) fixes an edge case in which a repo with no in-cone files or directories would have its root collapsed into a sparse directory; the fix ensures the root directory is never collapsed into a sparse directory.
* The second (patch [2/8]) corrects the 'git status' reporting of changes nested inside the subdirectory of a sparse directory, ensuring that the modified file (not the subdirectory) is correctly reported as having changes.
* The third (patch [3/8]) explicitly disallows the somewhat ambiguous case of using 'git read-tree --prefix=/' to represent the repo root (it could be interpreted as a leading slash - even though it's actually trailing slash - which is not allowed for prefixes). Now, an error specifying that prefixes cannot begin with '/' guides users more directly to the correct syntax. If a user does want to specify the repo root as their prefix, that can still be done with 'git read-tree --prefix='

The remainder of the series focuses on utilizing the sparse index in 'git read-tree'. After some baseline behavior-establishing tests (patch [4/8]), sparse index usage is trivially enabled (patch [5/8]) for 'read-tree' except:

* usage with '--prefix'
* two- and three-way merge

These cases require additional changes in order to work as expected (i.e., outwardly matching non-sparse index sparse-checkout). For the former, the sparse index can be enabled as long as the index is expanded when the prefix is a directory outside the sparse cone (patch [6/8]). For the latter, sparse directories that cannot be trivially merged must have their contents merged file-by-file, done by recursively traversing the trees represented by the sparse directories (patches [7/8] & [8/8]).

Changes since V2
================

* revised/clarified explanation for why the 'recursive' flag is necessary in 'git status' internal diff in both the commit message for [2/8] and the code comments
* added patch [3/8] to disallow '/' as a prefix
* moved the loop over different 'read-tree' scenarios outside the test in t1092 test 'read-tree --merge with files outside sparse definition', separating the tests into individually-runnable and traceable cases
* improved test case clarity and variety in 'read-tree --prefix' tests
* removed redundant arg to 'git reset' in 'sparse index is not expanded:
read-tree'
* pointed out pre-existing testing that covers '--prefix' in [6/8] commit message
* moved prefix-dependent index expansion logic into function 'update_sparsity_for_prefix', improved explanation for function behavior in comments

* pointed out pre-existing testing that covers two- and three-way merge in [7/8] & [8/8] commit messages, respectively
* added test cases for "ensure not expanded" tests of read-tree for both two- and three-way merge
* fixed issue with three-way merge implementation (if the "no merge" cases described in 't/t1000-read-tree-m-3way.sh' are reached, sparse directories should be recursively merged), testing added in the "ensure not expanded" cases

Changes since V1
================

* switched an empty string check from '!strlen(path)' to the slightly-less-expensive '!*path'

Thanks!

* Victoria

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

Victoria Dye (8):
sparse-index: prevent repo root from becoming sparse
status: fix nested sparse directory diff in sparse index
read-tree: explicitly disallow prefixes with a leading '/'
read-tree: expand sparse checkout test coverage
read-tree: integrate with sparse index
read-tree: narrow scope of index expansion for '--prefix'
read-tree: make two-way merge sparse-aware
read-tree: make three-way merge sparse-aware

 builtin/read-tree.c                      |  14 ++-
 dir.c                                    |   7 +-
 t/perf/p2000-sparse-operations.sh        |   1 +
 t/t1003-read-tree-prefix.sh              |  10 ++
 t/t1092-sparse-checkout-compatibility.sh | 133 ++++++++++++++++++++
 unpack-trees.c                           | 147 +++++++++++++++++++++--
 wt-status.c                              |   9 ++
 7 files changed, 308 insertions(+), 13 deletions(-)

base-commit: e6ebfd0e8cbbd10878070c8a356b5ad1b3ca464e
Published-As: https://github.com/gitgitgadget/git/releases/tag/pr-1157%2Fvdye%2Fsparse%2Fread-tree-v3
Fetch-It-Via: git fetch https://github.com/gitgitgadget/git pr-1157/vdye/sparse/read-tree-v3
Pull-Request: https://github.com/gitgitgadget/git/pull/1157

Range-diff vs v2:

 1:  744668eeece = 1:  744668eeece sparse-index: prevent repo root from becoming sparse
 2:  f0cff03b95d ! 2:  26f4d30bd95 status: fix nested sparse directory diff in sparse index

@@ Metadata
## Commit message ##
status: fix nested sparse directory diff in sparse index

- Add the 'recursive' flag to 'wt_status_collect_changes_index(...)'. Without
- the 'recursive' flag, 'git status' could report index changes incorrectly
- when the following conditions were met:
+ Enable the 'recursive' diff option for the diff executed as part of 'git
+ status'. Without the 'recursive' enabled, 'git status' reports index
+ changes incorrectly when the following conditions were met:

* sparse index is enabled
* there is a difference between the index and HEAD in a file inside a *subdirectory* of a sparse directory
* the sparse directory index entry is *not* expanded in-core

- In this scenario, 'git status' would not recurse into the sparse directory's
- subdirectories to identify which file contained the difference between the
- index and HEAD. Instead, it would report the immediate subdirectory itself
- as "modified".
+ Because it is not recursive by default, the diff in 'git status' reports
+ changes only at the level of files and directories that are immediate
+ children of a sparse directory, rather than recursing into directories with
+ changes to identify the modified file(s). As a result, 'git status' reports
+ the immediate subdirectory itself as "modified".

Example:

@@ Commit message
(use "git restore --staged <file>..." to unstage)
modified: sparse/sub

- The 'recursive' diff option in 'wt_status_collect_changes_index' corrects
- this by indicating that 'git status' should recurse into sparse directories
- to find modified files. Given the same repository setup as the example
- above, the corrected result of git status is:
+ Enabling the 'recursive' diff option in 'wt_status_collect_changes_index'
+ corrects this issue by allowing the diff to recurse into subdirectories of
+ sparse directories to find modified files. Given the same repository setup
+ as the example above, the corrected result of git status is:

$ git status
On branch master
@@ wt-status.c: static void wt_status_collect_changes_index(struct wt_status *s)
rev.diffopt.rename_score = s->rename_score >= 0 ? s->rename_score : rev.diffopt.rename_score;
+
+ /*
-+ * The recursive option must be enabled to show differences in files
-+ * *more than* one level deep in a sparse directory index entry (e.g., given -+ * sparse directory 'sparse-dir/', reporting a difference in the file
-+ * 'sparse-dir/another-dir/my-file').
++ * The recursive option must be enabled to allow the diff to recurse
++ * into subdirectories of sparse directory index entries. If it is not
++ * enabled, a subdirectory containing file(s) with changes is reported
++ * as "modified", rather than the modified files themselves.
+ */
+ rev.diffopt.flags.recursive = 1;
+

 -:  ----------- > 3:  e48a281a4d3 read-tree: explicitly disallow prefixes with a leading '/'
 3:  ffe0b6aff2b ! 4:  90ebcb7b8ff read-tree: expand sparse checkout test coverage
     @@ Commit message
          emphasis is placed on interactions with files outside the sparse cone, e.g.
          merges with out-of-cone conflicts.

     +    Helped-by: Ævar Arnfjörð Bjarmason <[email protected]>
          Signed-off-by: Victoria Dye <[email protected]>

       ## t/perf/p2000-sparse-operations.sh ##
     @@ t/t1092-sparse-checkout-compatibility.sh: test_expect_success 'update-index --ca
        test_cmp expect sparse-checkout-out
       '

     -+test_expect_success 'read-tree --merge with files outside sparse definition' '
     -+ init_repos &&
     -+
     -+ test_all_match git checkout -b test-branch update-folder1 &&
     -+ for MERGE_TREES in "base HEAD update-folder2" \
     -+                    "update-folder1 update-folder2" \
     -+                    "update-folder2"
     -+ do
     -+         # Clean up and remove on-disk files
     -+         test_all_match git reset --hard HEAD &&
     -+         test_sparse_match git sparse-checkout reapply &&
     ++for MERGE_TREES in "base HEAD update-folder2" \
     ++            "update-folder1 update-folder2" \
     ++            "update-folder2"
     ++do
     ++ test_expect_success "'read-tree -mu $MERGE_TREES' with files outside sparse definition" '
     ++         init_repos &&
      +
      +         # Although the index matches, without --no-sparse-checkout, outside-of-
      +         # definition files will not exist on disk for sparse checkouts
     @@ t/t1092-sparse-checkout-compatibility.sh: test_expect_success 'update-index --ca
      +         test_all_match git read-tree -mu --no-sparse-checkout $MERGE_TREES &&
      +         test_all_match git status --porcelain=v2 &&
      +         test_cmp sparse-checkout/folder2/a sparse-index/folder2/a &&
     -+         test_cmp sparse-checkout/folder2/a full-checkout/folder2/a || return 1
     -+ done
     -+'
     ++         test_cmp sparse-checkout/folder2/a full-checkout/folder2/a
     ++
     ++ '
     ++done
      +
      +test_expect_success 'read-tree --merge with edit/edit conflicts in sparse directories' '
      + init_repos &&
     @@ t/t1092-sparse-checkout-compatibility.sh: test_expect_success 'update-index --ca
      + test_all_match test_must_fail git read-tree -mu rename-out-to-in update-folder1
      +'
      +
     -+test_expect_success 'read-tree --prefix outside sparse definition' '
     ++test_expect_success 'read-tree --prefix' '
      + init_repos &&
      +
     -+ # Cannot read-tree --prefix with a single argument when files exist within
     -+ # prefix
     -+ test_all_match test_must_fail git read-tree --prefix=folder1/ -u update-folder1 &&
     ++ # If files differing between the index and target <commit-ish> exist
     ++ # inside the prefix, `read-tree --prefix` should fail
     ++ test_all_match test_must_fail git read-tree --prefix=deep/ deepest &&
     ++ test_all_match test_must_fail git read-tree --prefix=folder1/ update-folder1 &&
      +
     -+ test_all_match git read-tree --prefix=folder2/0 -u rename-base &&
     -+ test_path_is_missing sparse-checkout/folder2 &&
     -+ test_path_is_missing sparse-index/folder2 &&
     ++ # If no differing index entries exist matching the prefix,
     ++ # `read-tree --prefix` updates the index successfully
     ++ test_all_match git rm -rf deep/deeper1/deepest/ &&
     ++ test_all_match git read-tree --prefix=deep/deeper1/deepest -u deepest &&
     ++ test_all_match git status --porcelain=v2 &&
     ++
     ++ test_all_match git rm -rf --sparse folder1/ &&
     ++ test_all_match git read-tree --prefix=folder1/ -u update-folder1 &&
     ++ test_all_match git status --porcelain=v2 &&
      +
     -+ test_all_match git read-tree --reset -u HEAD &&
     -+ test_all_match git read-tree --prefix=folder2/0 -u --no-sparse-checkout rename-base &&
     -+ test_cmp sparse-checkout/folder2/0/a sparse-index/folder2/0/a &&
     -+ test_cmp sparse-checkout/folder2/0/a full-checkout/folder2/0/a
     ++ test_all_match git rm -rf --sparse folder2/0 &&
     ++ test_all_match git read-tree --prefix=folder2/0/ -u rename-out-to-out &&
     ++ test_all_match git status --porcelain=v2
      +'
      +
      +test_expect_success 'read-tree --merge with directory-file conflicts' '
 4:  cb7e0cf419c ! 5:  015618a9f29 read-tree: integrate with sparse index
     @@ t/t1092-sparse-checkout-compatibility.sh: test_expect_success 'sparse index is n
      + for MERGE_TREES in "update-folder2"
      + do
      +         ensure_not_expanded read-tree -mu $MERGE_TREES &&
     -+         ensure_not_expanded reset --hard HEAD || return 1
     ++         ensure_not_expanded reset --hard || return 1
      + done
      +'
      +
 5:  4f05fa70209 ! 6:  1a9365c3bc5 read-tree: narrow scope of index expansion for '--prefix'
     @@ Commit message
          If the prefix is in-cone, its sparse subdirectories (if any) will be
          traversed correctly without index expansion.

     +    The behavior of 'git read-tree' with prefixes 1) inside of cone, 2) equal to
     +    a sparse directory, and 3) inside a sparse directory are all tested as part
     +    of the 't/t1092-sparse-checkout-compatibility.sh' test 'read-tree --prefix',
     +    ensuring that the sparse index case works the way it did prior to this
     +    change as well as matching non-sparse index sparse-checkout.
     +
     +    Helped-by: Elijah Newren <[email protected]>
          Signed-off-by: Victoria Dye <[email protected]>

       ## builtin/read-tree.c ##
     @@ t/t1092-sparse-checkout-compatibility.sh
      @@ t/t1092-sparse-checkout-compatibility.sh: test_expect_success 'sparse index is not expanded: read-tree' '
        do
                ensure_not_expanded read-tree -mu $MERGE_TREES &&
     -          ensure_not_expanded reset --hard HEAD || return 1
     +          ensure_not_expanded reset --hard || return 1
      - done
      + done &&
      +
     @@ t/t1092-sparse-checkout-compatibility.sh: test_expect_success 'sparse index is n
       test_expect_success 'ls-files' '

       ## unpack-trees.c ##
     -@@ unpack-trees.c: int unpack_trees(unsigned len, struct tree_desc *t, struct unpack_trees_options
     -          setup_standard_excludes(o->dir);
     -  }
     +@@ unpack-trees.c: static void populate_from_existing_patterns(struct unpack_trees_options *o,
     +          o->pl = pl;
     + }

     -+ /*
     -+  * If the prefix is equal to or contained within a sparse directory, the
     -+  * index needs to be expanded to traverse with the specified prefix.
     -+  */
     -+ if (o->prefix && o->src_index->sparse_index) {
     -+         int prefix_len = strlen(o->prefix);
     ++static void update_sparsity_for_prefix(const char *prefix,
     ++                                struct index_state *istate)
     ++{
     ++ int prefix_len = strlen(prefix);
     ++ struct strbuf ce_prefix = STRBUF_INIT;
      +
     -+         while (prefix_len > 0 && o->prefix[prefix_len - 1] == '/')
     -+                 prefix_len--;
     ++ if (!istate->sparse_index)
     ++         return;
      +
     -+         if (prefix_len > 0) {
     -+                 struct strbuf ce_prefix = STRBUF_INIT;
     -+                 strbuf_grow(&ce_prefix, prefix_len + 1);
     -+                 strbuf_add(&ce_prefix, o->prefix, prefix_len);
     -+                 strbuf_addch(&ce_prefix, '/');
     ++ while (prefix_len > 0 && prefix[prefix_len - 1] == '/')
     ++         prefix_len--;
      +
     -+                 /*
     -+                  * If the prefix is not inside the sparse cone, then the
     -+                  * index is explicitly expanded if it is found as a sparse
     -+                  * directory, or implicitly expanded (by 'index_name_pos')
     -+                  * if the path is inside a sparse directory.
     -+                  */
     -+                 if (!path_in_cone_mode_sparse_checkout(ce_prefix.buf, o->src_index) &&
     -+                     index_name_pos(o->src_index, ce_prefix.buf, ce_prefix.len) >= 0)
     -+                         ensure_full_index(o->src_index);
     ++ if (prefix_len <= 0)
     ++         BUG("Invalid prefix passed to update_sparsity_for_prefix");
      +
     -+                 strbuf_release(&ce_prefix);
     -+         }
     -+ }
     ++ strbuf_grow(&ce_prefix, prefix_len + 1);
     ++ strbuf_add(&ce_prefix, prefix, prefix_len);
     ++ strbuf_addch(&ce_prefix, '/');
     ++
     ++ /*
     ++  * If the prefix points to a sparse directory or a path inside a sparse
     ++  * directory, the index should be expanded. This is accomplished in one
     ++  * of two ways:
     ++  * - if the prefix is inside a sparse directory, it will be expanded by
     ++  *   the 'ensure_full_index(...)' call in 'index_name_pos(...)'.
     ++  * - if the prefix matches an existing sparse directory entry,
     ++  *   'index_name_pos(...)' will return its index position, triggering
     ++  *   the 'ensure_full_index(...)' below.
     ++  */
     ++ if (!path_in_cone_mode_sparse_checkout(ce_prefix.buf, istate) &&
     ++     index_name_pos(istate, ce_prefix.buf, ce_prefix.len) >= 0)
     ++         ensure_full_index(istate);
     ++
     ++ strbuf_release(&ce_prefix);
     ++}
     +
     + static int verify_absent(const struct cache_entry *,
     +                   enum unpack_trees_error_types,
     +@@ unpack-trees.c: int unpack_trees(unsigned len, struct tree_desc *t, struct unpack_trees_options
     +          setup_standard_excludes(o->dir);
     +  }
     +
     ++ if (o->prefix)
     ++         update_sparsity_for_prefix(o->prefix, o->src_index);
      +
        if (!core_apply_sparse_checkout || !o->update)
                o->skip_sparse_checkout = 1;

6: 94c2aad2f93 ! 7: 71bec3ddad1 read-tree: make two-way merge sparse-aware
@@ Commit message
This process allows sparse directories to be individually merged at the necessary depth *without* expanding a full index.

+ The 't/t1092-sparse-checkout-compatibility.sh' test 'read-tree --merge with
+ edit/edit conflicts in sparse directories' tests two-way merges with 1)
+ changes inside sparse directories that do not conflict and 2) changes that
+ do conflict (with the correct file(s) reported in the error message).
+ Additionally, add two-way merge cases to 'sparse index is not expanded:
+ read-tree' to confirm that the index is not expanded regardless of whether
+ edit/edit conflicts are present in a sparse directory.
+

Signed-off-by Victoria Dye <[email protected]>

## builtin/read-tree.c ##
@@ t/t1092-sparse-checkout-compatibility.sh: test_expect_success 'sparse index is n

ensure_not_expanded checkout -b test-branch update-folder1 &&
- for MERGE_TREES in "update-folder2"
-+ for MERGE_TREES in "update-folder2" \
-+ "base update-folder2"
++ for MERGE_TREES in "base update-folder2" \
++ "base rename-base" \
++ "update-folder2"
do
ensure_not_expanded read-tree -mu $MERGE_TREES &&
- ensure_not_expanded reset --hard HEAD || return 1
+ ensure_not_expanded reset --hard || return 1

## unpack-trees.c ##
@@ unpack-trees.c: static int is_sparse_directory_entry(struct cache_entry *ce,
7: c4080e99d6e ! 8: 6bc11325dd1 read-tree: make three-way merge sparse-aware
@@ Commit message
merge, the contents of each conflicted sparse directory are merged without referencing the index, avoiding sparse index expansion.

+ As with two-way merge, the 't/t1092-sparse-checkout-compatibility.sh' test
+ 'read-tree --merge with edit/edit conflicts in sparse directories' confirms
+ that three-way merges with edit/edit changes (both with and without
+ conflicts) inside a sparse directory result in the correct index state or
+ error message. To ensure the index is not unnecessarily expanded, add
+ three-way merge cases to 'sparse index is not expanded: read-tree'.
+

Signed-off-by Victoria Dye <[email protected]>

## builtin/read-tree.c ##
@@ builtin/read-tree.c: int cmd_read_tree(int argc, const char **argv, const char *

## t/t1092-sparse-checkout-compatibility.sh ##
@@ t/t1092-sparse-checkout-compatibility.sh: test_expect_success 'sparse index is not expanded: read-tree' '
+ init_repos &&

ensure_not_expanded checkout -b test-branch update-folder1 &&
- for MERGE_TREES in "update-folder2" \
-- "base update-folder2"
+- for MERGE_TREES in "base update-folder2" \
++ for MERGE_TREES in "base HEAD update-folder2" \
++ "base HEAD rename-base" \
+ "base update-folder2" \
-+ "base HEAD update-folder2"
+ "base rename-base" \
+ "update-folder2"
do
- ensure_not_expanded read-tree -mu $MERGE_TREES &&
- ensure_not_expanded reset --hard HEAD || return 1

## unpack-trees.c ##
@@ unpack-trees.c: int threeway_merge(const struct cache_entry * const *stages,
@@ unpack-trees.c: int threeway_merge(const struct cache_entry * const *stages,

if (head) {
/* #5ALT, #15 */
+@@ unpack-trees.c: int threeway_merge(const struct cache_entry * const *stages, +
+ }
+
+- /* Below are "no merge" cases, which require that the index be +- * up-to-date to avoid the files getting overwritten with
+- * conflict resolution files.
+- */
++ /* Handle "no merge" cases (see t/t1000-read-tree-m-3way.sh) */
+ if (index) {
++ /*
++ * If we've reached the "no merge" cases and we're merging
++ * a sparse directory, we may have an "edit/edit" conflict that
++ * can be resolved by individually merging directory contents.
++ */
++ if (S_ISSPARSEDIR(index->ce_mode))
++ return merged_sparse_dir(stages, 4, o);
++
++ /*
++ * If we're not merging a sparse directory, ensure the index is
++ * up-to-date to avoid files getting overwritten with conflict
++ * resolution files
++ */
+ if (verify_uptodate(index, o))
+ return -1;
+ }

--
gitgitgadget

On Tue, Mar 1, 2022 at 12:24 PM Victoria Dye via GitGitGadget <[email protected]> wrote:

I've read through all of these. This round is:

Reviewed-by Elijah Newren <[email protected]>