[PATCH 0/7] Sparse Index: integrate with reset

Sorry, one more thing...

On Wed, Oct 27, 2021 at 7:39 AM Victoria Dye via GitGitGadget
[off-list ref] wrote:

You've added two testcases where a wildcard results in no index
expansion; should there also be a test where a wildcard results in
index expansion for completeness?

Hi!

On Wed, Oct 27, 2021 at 7:39 AM Victoria Dye via GitGitGadget
[off-list ref] wrote:

This series integrates the sparse index with git reset and provides
miscellaneous fixes and improvements to the command in sparse checkouts.

...

Changes since V3
================

 * Replace git update-index --force-full-index with git reset update-folder1
   -- folder1/a, remove introduction of new --force-full-index option
   entirely, and add comment clarifying the intent of sparse-index is
   expanded and converted back test
 * Fix authorship on reset: preserve skip-worktree bit in mixed reset
   (current patch fully replaces original patch, but metadata of the
   original wasn't properly replaced)


Changes since V4
================

 * Update t1092 test 'checkout and reset (mixed)' to explicitly verify
   differences between sparse and full checkouts

I apologize for my tardiness in reviewing your updated series.  You
have addressed all my feedback from v2 and things look really good.  I
had a couple small questions on patch 7.

As with my previous review, I kinda skipped over the last patch
because I never figured out the cache_bottom stuff.  I read it to see
if there were any obvious mistakes to someone unfamiliar with that
mechanism (i.e. me) but didn't see anything.  I read over the earlier
patches much more carefully.

Anyway, other than patch 7 -- where I only had a minor nit on the
commit message plus two questions (which might result in no changes),
the series looks good.

Elijah Newren wrote:

On Thu, Oct 7, 2021 at 2:15 PM Victoria Dye via GitGitGadget
[off-list ref] wrote:

quoted

From: Victoria Dye <redacted>

Remove the `ensure_full_index` guard on `read_from_tree` and update `git
reset --mixed` to ensure it can use sparse directory index entries wherever
possible. Sparse directory entries are reset use `diff_tree_oid`, which

I am having trouble parsing this second sentence.  Was this meant to
be 'Sparse directory entries _which_ are reset use...'?

It should be "Sparse directory entries are reset _using_
`diff_tree_oid`...".

quoted

requires `change` and `add_remove` functions to process the internal
contents of the sparse directory. The `recursive` diff option handles cases
in which `reset --mixed` must diff/merge files that are nested multiple
levels deep in a sparse directory.

The use of pathspecs with `git reset --mixed` introduces scenarios in which
internal contents of sparse directories may be matched by the pathspec. In
order to reset *all* files in the repo that may match the pathspec, the
following conditions on the pathspec require index expansion before
performing the reset:

* "magic" pathspecs
* wildcard pathspecs that do not match only in-cone files or entire sparse
  directories
* literal pathspecs matching something outside the sparse checkout
  definition

Helped-by: Elijah Newren [off-list ref]
Signed-off-by: Victoria Dye <redacted>
---
 builtin/reset.c                          | 78 +++++++++++++++++++++++-
 t/t1092-sparse-checkout-compatibility.sh | 17 ++++++
 2 files changed, 93 insertions(+), 2 deletions(-)

diff --git a/builtin/reset.c b/builtin/reset.c
index 0ac0de7dc97..60517e7e1d6 100644
--- a/builtin/reset.c
+++ b/builtin/reset.c

@@ -148,7 +148,9 @@ static void update_index_from_diff(struct diff_queue_struct *q,
                 * If the file 1) corresponds to an existing index entry with
                 * skip-worktree set, or 2) does not exist in the index but is
                 * outside the sparse checkout definition, add a skip-worktree bit
-                * to the new index entry.
+                * to the new index entry. Note that a sparse index will be expanded
+                * if this entry is outside the sparse cone - this is necessary
+                * to properly construct the reset sparse directory.
                 */
                pos = cache_name_pos(one->path, strlen(one->path));
                if ((pos >= 0 && ce_skip_worktree(active_cache[pos])) ||

@@ -166,6 +168,73 @@ static void update_index_from_diff(struct diff_queue_struct *q,
        }
 }

+static int pathspec_needs_expanded_index(const struct pathspec *pathspec)
+{
+       unsigned int i, pos;
+       int res = 0;
+       char *skip_worktree_seen = NULL;
+
+       /*
+        * When using a magic pathspec, assume for the sake of simplicity that
+        * the index needs to be expanded to match all matchable files.
+        */
+       if (pathspec->magic)
+               return 1;
+
+       for (i = 0; i < pathspec->nr; i++) {
+               struct pathspec_item item = pathspec->items[i];
+
+               /*
+                * If the pathspec item has a wildcard, the index should be expanded
+                * if the pathspec has the possibility of matching a subset of entries inside
+                * of a sparse directory (but not the entire directory).
+                *
+                * If the pathspec item is a literal path, the index only needs to be expanded
+                * if a) the pathspec isn't in the sparse checkout cone (to make sure we don't
+                * expand for in-cone files) and b) it doesn't match any sparse directories
+                * (since we can reset whole sparse directories without expanding them).
+                */
+               if (item.nowildcard_len < item.len) {
+                       for (pos = 0; pos < active_nr; pos++) {
+                               struct cache_entry *ce = active_cache[pos];
+
+                               if (!S_ISSPARSEDIR(ce->ce_mode))
+                                       continue;

This double loop over all pathspecs and over all index entries reminds
me of the original non-cone mode sparsity patterns.  Stolee introduced
cone mode patterns specifically to avoid the expensiveness of such
double loops (cf.
https://lore.kernel.org/git/19d664a5dada87a9a8dcf18d7548582275593f10.1566313865.git.gitgitgadget@gmail.com/).
Can one of the functions he added allow us to avoid this double loop,
or are there complications that don't allow this (e.g. the actually
SKIP_WORKTREE paths don't quite match the requested sparsity paths in
some cases, or here we are faced with just a leading path of multiple
index entries)?

quoted

+                               /*
+                                * If the pre-wildcard length is longer than the sparse
+                                * directory name and the sparse directory is the first
+                                * component of the pathspec, need to expand the index.
+                                */
+                               if (item.nowildcard_len > ce_namelen(ce) &&
+                                   !strncmp(item.original, ce->name, ce_namelen(ce))) {
+                                       res = 1;
+                                       break;
+                               }
+
+                               /*
+                                * If the pre-wildcard length is shorter than the sparse
+                                * directory and the pathspec does not match the whole
+                                * directory, need to expand the index.
+                                */
+                               if (!strncmp(item.original, ce->name, item.nowildcard_len) &&
+                                   wildmatch(item.original, ce->name, 0)) {
+                                       res = 1;
+                                       break;
+                               }
+                       }
+               } else if (!path_in_cone_mode_sparse_checkout(item.original, &the_index) &&
+                          !matches_skip_worktree(pathspec, i, &skip_worktree_seen))

Oh, so you can at least generally avoid the double loop.  That's good.
So is this just a case of wildcards are special and there isn't a way,
even in cone-mode, to avoid the double loop?

The wildcard pathspecs are difficult to handle as "cleanly" as the
non-wildcard pathspecs, since the condition for expanding the index is
whether the pathspec has the potential to match some, but not all, contents
of any given sparse directory. Luckily, the double loop is constrained to
only sparse directories in the index and wildcard pathspecs, and exits as
soon as there is any indication that the index needs to be expanded.

(Given that I'm so tardy in reviewing this, even if the answer is that
the double loop is avoidable, or if we just don't know, I'd be totally
fine with a 'TODO: consider whether this double loop could be avoided
in cone mode using some kind of variant of
path_in_cone_mode_sparse_checkout()')

I had originally tried something like this, but even if a wildcard pathspec
is in-cone, it could match something outside of it. For example, '*.c' is
in-cone, but has the potential to match only some of the files in a sparse
directory containing both *.c and *.h files. 

Looking at it again, though, if you constrain
`path_in_cone_mode_sparse_checkout()` pathspecs further and require that the
only post-`nowildcard_len` characters are '*', there's no risk of matching
partial subsets of files in sparse directories. I'll add that in a re-roll.

quoted

+                       res = 1;
+
+               if (res > 0)
+                       break;
+       }
+
+       free(skip_worktree_seen);
+       return res;
+}
+
 static int read_from_tree(const struct pathspec *pathspec,
                          struct object_id *tree_oid,
                          int intent_to_add)

@@ -178,9 +247,14 @@ static int read_from_tree(const struct pathspec *pathspec,
        opt.format_callback = update_index_from_diff;
        opt.format_callback_data = &intent_to_add;
        opt.flags.override_submodule_config = 1;
+       opt.flags.recursive = 1;
        opt.repo = the_repository;
+       opt.change = diff_change;
+       opt.add_remove = diff_addremove;
+
+       if (pathspec->nr && the_index.sparse_index && pathspec_needs_expanded_index(pathspec))
+               ensure_full_index(&the_index);

-       ensure_full_index(&the_index);
        if (do_diff_cache(tree_oid, &opt))
                return 1;
        diffcore_std(&opt);

diff --git a/t/t1092-sparse-checkout-compatibility.sh b/t/t1092-sparse-checkout-compatibility.sh
index 4ac93874cb2..c9343ff5b9c 100755
--- a/t/t1092-sparse-checkout-compatibility.sh
+++ b/t/t1092-sparse-checkout-compatibility.sh

@@ -774,11 +774,28 @@ test_expect_success 'sparse-index is not expanded' '
                ensure_not_expanded reset --hard $ref || return 1
        done &&

+       ensure_not_expanded reset --mixed base &&
        ensure_not_expanded reset --hard update-deep &&
        ensure_not_expanded reset --keep base &&
        ensure_not_expanded reset --merge update-deep &&
        ensure_not_expanded reset --hard &&

+       ensure_not_expanded reset base -- deep/a &&
+       ensure_not_expanded reset base -- nonexistent-file &&
+       ensure_not_expanded reset deepest -- deep &&
+
+       # Although folder1 is outside the sparse definition, it exists as a
+       # directory entry in the index, so the pathspec will not force the
+       # index to be expanded.
+       ensure_not_expanded reset deepest -- folder1 &&
+       ensure_not_expanded reset deepest -- folder1/ &&
+
+       # Wildcard identifies only in-cone files, no index expansion
+       ensure_not_expanded reset deepest -- deep/\* &&
+
+       # Wildcard identifies only full sparse directories, no index expansion
+       ensure_not_expanded reset deepest -- folder\* &&
+
        ensure_not_expanded checkout -f update-deep &&
        test_config -C sparse-index pull.twohead ort &&
        (
--

gitgitgadget

Elijah Newren wrote:

Sorry, one more thing...

On Wed, Oct 27, 2021 at 7:39 AM Victoria Dye via GitGitGadget
[off-list ref] wrote:

quoted

From: Victoria Dye <redacted>

Remove the `ensure_full_index` guard on `read_from_tree` and update `git
reset --mixed` to ensure it can use sparse directory index entries wherever
possible. Sparse directory entries are reset use `diff_tree_oid`, which
requires `change` and `add_remove` functions to process the internal
contents of the sparse directory. The `recursive` diff option handles cases
in which `reset --mixed` must diff/merge files that are nested multiple
levels deep in a sparse directory.

The use of pathspecs with `git reset --mixed` introduces scenarios in which
internal contents of sparse directories may be matched by the pathspec. In
order to reset *all* files in the repo that may match the pathspec, the
following conditions on the pathspec require index expansion before
performing the reset:

* "magic" pathspecs
* wildcard pathspecs that do not match only in-cone files or entire sparse
  directories
* literal pathspecs matching something outside the sparse checkout
  definition

Helped-by: Elijah Newren [off-list ref]
Signed-off-by: Victoria Dye <redacted>
---
 builtin/reset.c                          | 78 +++++++++++++++++++++++-
 t/t1092-sparse-checkout-compatibility.sh | 17 ++++++
 2 files changed, 93 insertions(+), 2 deletions(-)

diff --git a/builtin/reset.c b/builtin/reset.c
index 0ac0de7dc97..60517e7e1d6 100644
--- a/builtin/reset.c
+++ b/builtin/reset.c

@@ -148,7 +148,9 @@ static void update_index_from_diff(struct diff_queue_struct *q,
                 * If the file 1) corresponds to an existing index entry with
                 * skip-worktree set, or 2) does not exist in the index but is
                 * outside the sparse checkout definition, add a skip-worktree bit
-                * to the new index entry.
+                * to the new index entry. Note that a sparse index will be expanded
+                * if this entry is outside the sparse cone - this is necessary
+                * to properly construct the reset sparse directory.
                 */
                pos = cache_name_pos(one->path, strlen(one->path));
                if ((pos >= 0 && ce_skip_worktree(active_cache[pos])) ||

@@ -166,6 +168,73 @@ static void update_index_from_diff(struct diff_queue_struct *q,
        }
 }

+static int pathspec_needs_expanded_index(const struct pathspec *pathspec)
+{
+       unsigned int i, pos;
+       int res = 0;
+       char *skip_worktree_seen = NULL;
+
+       /*
+        * When using a magic pathspec, assume for the sake of simplicity that
+        * the index needs to be expanded to match all matchable files.
+        */
+       if (pathspec->magic)
+               return 1;
+
+       for (i = 0; i < pathspec->nr; i++) {
+               struct pathspec_item item = pathspec->items[i];
+
+               /*
+                * If the pathspec item has a wildcard, the index should be expanded
+                * if the pathspec has the possibility of matching a subset of entries inside
+                * of a sparse directory (but not the entire directory).
+                *
+                * If the pathspec item is a literal path, the index only needs to be expanded
+                * if a) the pathspec isn't in the sparse checkout cone (to make sure we don't
+                * expand for in-cone files) and b) it doesn't match any sparse directories
+                * (since we can reset whole sparse directories without expanding them).
+                */
+               if (item.nowildcard_len < item.len) {
+                       for (pos = 0; pos < active_nr; pos++) {
+                               struct cache_entry *ce = active_cache[pos];
+
+                               if (!S_ISSPARSEDIR(ce->ce_mode))
+                                       continue;
+
+                               /*
+                                * If the pre-wildcard length is longer than the sparse
+                                * directory name and the sparse directory is the first
+                                * component of the pathspec, need to expand the index.
+                                */
+                               if (item.nowildcard_len > ce_namelen(ce) &&
+                                   !strncmp(item.original, ce->name, ce_namelen(ce))) {
+                                       res = 1;
+                                       break;
+                               }
+
+                               /*
+                                * If the pre-wildcard length is shorter than the sparse
+                                * directory and the pathspec does not match the whole
+                                * directory, need to expand the index.
+                                */
+                               if (!strncmp(item.original, ce->name, item.nowildcard_len) &&
+                                   wildmatch(item.original, ce->name, 0)) {
+                                       res = 1;
+                                       break;
+                               }
+                       }
+               } else if (!path_in_cone_mode_sparse_checkout(item.original, &the_index) &&
+                          !matches_skip_worktree(pathspec, i, &skip_worktree_seen))
+                       res = 1;
+
+               if (res > 0)
+                       break;
+       }
+
+       free(skip_worktree_seen);
+       return res;
+}
+
 static int read_from_tree(const struct pathspec *pathspec,
                          struct object_id *tree_oid,
                          int intent_to_add)

@@ -178,9 +247,14 @@ static int read_from_tree(const struct pathspec *pathspec,
        opt.format_callback = update_index_from_diff;
        opt.format_callback_data = &intent_to_add;
        opt.flags.override_submodule_config = 1;
+       opt.flags.recursive = 1;
        opt.repo = the_repository;
+       opt.change = diff_change;
+       opt.add_remove = diff_addremove;
+
+       if (pathspec->nr && the_index.sparse_index && pathspec_needs_expanded_index(pathspec))
+               ensure_full_index(&the_index);

-       ensure_full_index(&the_index);
        if (do_diff_cache(tree_oid, &opt))
                return 1;
        diffcore_std(&opt);

diff --git a/t/t1092-sparse-checkout-compatibility.sh b/t/t1092-sparse-checkout-compatibility.sh
index 5664ff8f039..44d5e11c762 100755
--- a/t/t1092-sparse-checkout-compatibility.sh
+++ b/t/t1092-sparse-checkout-compatibility.sh

@@ -781,11 +781,28 @@ test_expect_success 'sparse-index is not expanded' '
                ensure_not_expanded reset --hard $ref || return 1
        done &&

+       ensure_not_expanded reset --mixed base &&
        ensure_not_expanded reset --hard update-deep &&
        ensure_not_expanded reset --keep base &&
        ensure_not_expanded reset --merge update-deep &&
        ensure_not_expanded reset --hard &&

+       ensure_not_expanded reset base -- deep/a &&
+       ensure_not_expanded reset base -- nonexistent-file &&
+       ensure_not_expanded reset deepest -- deep &&
+
+       # Although folder1 is outside the sparse definition, it exists as a
+       # directory entry in the index, so the pathspec will not force the
+       # index to be expanded.
+       ensure_not_expanded reset deepest -- folder1 &&
+       ensure_not_expanded reset deepest -- folder1/ &&
+
+       # Wildcard identifies only in-cone files, no index expansion
+       ensure_not_expanded reset deepest -- deep/\* &&
+
+       # Wildcard identifies only full sparse directories, no index expansion
+       ensure_not_expanded reset deepest -- folder\* &&
+

You've added two testcases where a wildcard results in no index
expansion; should there also be a test where a wildcard results in
index expansion for completeness?

The tests haven't verified when the index *is* expanded for any of the
commands implemented so far (save for the one ensuring that, when the index
is expanded, the expansion is logged via trace2). I see the value in it
(e.g. using the tests to demonstrate what can trigger index expansion).
Conversely, if the tests are intended to confirm "successful" sparse index
support (where index expansion is equivalent to "the sparse index is not
supported"), then verifying index expansion doesn't necessarily fit that
purpose. 

I'm not sure which interpretation is "correct", but if it does make sense to
test expansion cases I'm happy to add them here (or, if not in this series,
add a TODO to include them in the future).

For what it's worth, the test 'reset with wildcard pathspec' in [4/8] is
intended to cover a broader set of wildcard scenarios (verifying
correctness, rather than index expansion). Given the other updates I intend
to make to wildcard handling, I'm planning on adding cases to that test in 
my next re-roll.

This series integrates the sparse index with git reset and provides
miscellaneous fixes and improvements to the command in sparse checkouts.
This includes:

 1. tests added to t1092 and p2000 to establish the baseline functionality
    of the command
 2. repository settings to enable the sparse index with ensure_full_index
    guarding any code paths that break tests without other compatibility
    updates.
 3. modifications to remove or reduce the scope in which ensure_full_index
    must be called.

The sparse index updates are predicated on a fix originating from the
microsoft/git fork [1], correcting how git reset --mixed handles resetting
entries outside the sparse checkout definition. Additionally, a performance
"bug" in next_cache_entry with sparse index is corrected, preventing
repeatedly looping over already-searched entries.

The p2000 tests demonstrate a ~70% execution time reduction in git reset
using a sparse index, and no change (within expected variability [2]) using
a full index. Results summarized below [3, 4]:

Test                           base              [5/8]                 
-----------------------------------------------------------------------
git reset --hard (full-v3)     1.00(0.50+0.39)   0.97(0.50+0.37) -3.0% 
git reset --hard (full-v4)     1.00(0.51+0.38)   0.96(0.50+0.36) -4.0% 
git reset --hard (sparse-v3)   1.68(1.17+0.39)   1.37(0.91+0.35) -18.5%
git reset --hard (sparse-v4)   1.70(1.18+0.40)   1.41(0.94+0.35) -17.1%

Test                           base              [6/8]   
-----------------------------------------------------------------------
git reset --hard (full-v3)     1.00(0.50+0.39)   0.94(0.48+0.34) -6.0% 
git reset --hard (full-v4)     1.00(0.51+0.38)   0.95(0.51+0.34) -5.0% 
git reset --hard (sparse-v3)   1.68(1.17+0.39)   0.46(0.05+0.29) -72.6%
git reset --hard (sparse-v4)   1.70(1.18+0.40)   0.46(0.06+0.29) -72.9%

Test                               base              [7/8]
---------------------------------------------------------------------------
git reset (full-v3)                0.77(0.27+0.37)   0.72(0.26+0.32) -6.5%
git reset (full-v4)                0.75(0.27+0.34)   0.73(0.26+0.32) -2.7%
git reset (sparse-v3)              1.44(0.96+0.36)   0.43(0.04+0.96) -70.1%
git reset (sparse-v4)              1.46(0.97+0.36)   0.43(0.05+0.79) -70.5%
git reset -- missing (full-v3)     0.72(0.26+0.32)   0.69(0.26+0.30) -4.2%
git reset -- missing (full-v4)     0.74(0.28+0.33)   0.71(0.27+0.32) -4.1% 
git reset -- missing (sparse-v3)   1.45(0.97+0.35)   0.81(0.42+0.90) -44.1%
git reset -- missing (sparse-v4)   1.41(0.94+0.34)   0.79(0.42+0.76) -44.0%

Test                               base              [8/8]            
---------------------------------------------------------------------------
git reset -- missing (full-v3)     0.72(0.26+0.32)   0.73(0.26+0.33) +1.4% 
git reset -- missing (full-v4)     0.74(0.28+0.33)   0.74(0.27+0.32) +0.0% 
git reset -- missing (sparse-v3)   1.45(0.97+0.35)   0.43(0.05+0.80) -70.3%
git reset -- missing (sparse-v4)   1.41(0.94+0.34)   0.44(0.05+0.76) -68.8%



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

 * Add --force-full-index option to update-index. The option is used
   circumvent changing command_requires_full_index from its default value -
   right now this is effectively a no-op, but will change once update-index
   is integrated with sparse index. By using this option in the t1092
   expand/collapse test, the command used to test will not need to be
   updated with subsequent sparse index integrations.
 * Update implementation of mixed reset for entries outside sparse checkout
   definition. The condition in which a file should be checked out before
   index reset is simplified to "if it has skip-worktree enabled and a reset
   would change the file, check it out".
   * After checking the behavior of update_index_from_diff with renames,
     found that the diff used by reset does not produce diff queue entries
     with different pathnames for one and two. Because of this, and that
     nothing in the implementation seems to rely on identical path names, no
     BUG check is added.
 * Correct a bug in the sparse index is not expanded tests in t1092 where
   failure of a git reset --mixed test was not being reported. Test now
   verifies an appropriate scenario with corrected failure-checking.


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

 * Replace patch adding checkouts for git reset --mixed with sparse checkout
   with preserving the skip-worktree flag (including a new test for git
   reset --mixed and update to t1092 - checkout and reset (mixed))
 * Move rename of is_missing into its own patch
 * Further extend t1092 tests and remove unnecessary commands/tests where
   possible
 * Refine logic determining which pathspecs require ensure_full_index in git
   reset --mixed, add related ensure_not_expanded tests
 * Add index_search_mode enum to index_name_stage_pos
 * Clean up variable usage & remove unnecessary subtree_path in
   prime_cache_tree_rec
 * Update cover letter performance data
 * More thoroughly explain changes in each commit message


Changes since V3
================

 * Replace git update-index --force-full-index with git reset update-folder1
   -- folder1/a, remove introduction of new --force-full-index option
   entirely, and add comment clarifying the intent of sparse-index is
   expanded and converted back test
 * Fix authorship on reset: preserve skip-worktree bit in mixed reset
   (current patch fully replaces original patch, but metadata of the
   original wasn't properly replaced)


Changes since V4
================

 * Update t1092 test 'checkout and reset (mixed)' to explicitly verify
   differences between sparse and full checkouts


Changes since V5
================

 * Update t1092 test 'reset with wildcard pathspec' with more cases and
   better checks
 * Add "special case" wildcard pathspec check when determining whether to
   expand the index (avoids double-loop over pathspecs & index entries)

Thanks! -Victoria

[1] microsoft@6b8a074 [2]
https://lore.kernel.org/git/8b9fe3f8-f0e3-4567-b20b-17c92bd1a5c5@github.com/
[3] If a test and/or commit is not mentioned, there is no significant change
to performance [4] Pathspec "does-not-exist" is changed to "missing" to save
space in performance report

Victoria Dye (8):
  reset: rename is_missing to !is_in_reset_tree
  reset: preserve skip-worktree bit in mixed reset
  sparse-index: update command for expand/collapse test
  reset: expand test coverage for sparse checkouts
  reset: integrate with sparse index
  reset: make sparse-aware (except --mixed)
  reset: make --mixed sparse-aware
  unpack-trees: improve performance of next_cache_entry

 builtin/reset.c                          | 113 ++++++++++++++++-
 cache-tree.c                             |  46 ++++++-
 cache.h                                  |  10 ++
 read-cache.c                             |  27 ++--
 t/perf/p2000-sparse-operations.sh        |   3 +
 t/t1092-sparse-checkout-compatibility.sh | 154 ++++++++++++++++++++---
 t/t7102-reset.sh                         |  17 +++
 unpack-trees.c                           |  23 +++-
 8 files changed, 356 insertions(+), 37 deletions(-)


base-commit: cefe983a320c03d7843ac78e73bd513a27806845
Published-As: https://github.com/gitgitgadget/git/releases/tag/pr-1048%2Fvdye%2Fvdye%2Fsparse-index-part1-v6
Fetch-It-Via: git fetch https://github.com/gitgitgadget/git pr-1048/vdye/vdye/sparse-index-part1-v6
Pull-Request: https://github.com/gitgitgadget/git/pull/1048

Range-diff vs v5:

 1:  ad7013a31aa = 1:  ad7013a31aa reset: rename is_missing to !is_in_reset_tree
 2:  b221b00b7e0 = 2:  b221b00b7e0 reset: preserve skip-worktree bit in mixed reset
 3:  1bb2ca92c60 = 3:  1bb2ca92c60 sparse-index: update command for expand/collapse test
 4:  cc76c694647 ! 4:  741a2c9ffaa reset: expand test coverage for sparse checkouts
     @@ t/t1092-sparse-checkout-compatibility.sh: test_expect_success 'checkout and rese
      +test_expect_success 'reset with wildcard pathspec' '
      +	init_repos &&
      +
     -+	test_all_match git checkout -b reset-test update-deep &&
     -+	test_all_match git reset base -- \*/a &&
     -+	test_all_match git status --porcelain=v2 &&
     -+	test_all_match git rev-parse HEAD:folder1/a &&
     ++	test_all_match git reset update-deep -- deep\* &&
     ++	test_all_match git ls-files -s -- deep &&
      +
     -+	test_all_match git reset base -- folder\* &&
     -+	test_all_match git status --porcelain=v2 &&
     -+	test_all_match git rev-parse HEAD:folder2
     ++	test_all_match git reset deepest -- deep\*\*\* &&
     ++	test_all_match git ls-files -s -- deep &&
     ++
     ++	# The following `git reset`s result in updating the index on files with
     ++	# `skip-worktree` enabled. To avoid failing due to discrepencies in reported
     ++	# "modified" files, `test_sparse_match` reset is performed separately from
     ++	# "full-checkout" reset, then the index contents of all repos are verified.
     ++
     ++	test_sparse_match git reset update-folder1 -- \*/a &&
     ++	git -C full-checkout reset update-folder1 -- \*/a &&
     ++	test_all_match git ls-files -s -- deep/a folder1/a &&
     ++
     ++	test_sparse_match git reset update-folder2 -- folder\* &&
     ++	git -C full-checkout reset update-folder2 -- folder\* &&
     ++	test_all_match git ls-files -s -- folder10 folder1 folder2 &&
     ++
     ++	test_sparse_match git reset base -- folder1/\* &&
     ++	git -C full-checkout reset base -- folder1/\* &&
     ++	test_all_match git ls-files -s -- folder1
      +'
      +
       test_expect_success 'merge, cherry-pick, and rebase' '
 5:  217ae445418 = 5:  65b0eafd27c reset: integrate with sparse index
 6:  a3e2fd59867 = 6:  908c84005b9 reset: make sparse-aware (except --mixed)
 7:  a9135a5ed64 ! 7:  822d7344587 reset: make --mixed sparse-aware
     @@ Commit message
      
          Remove the `ensure_full_index` guard on `read_from_tree` and update `git
          reset --mixed` to ensure it can use sparse directory index entries wherever
     -    possible. Sparse directory entries are reset use `diff_tree_oid`, which
     +    possible. Sparse directory entries are reset using `diff_tree_oid`, which
          requires `change` and `add_remove` functions to process the internal
          contents of the sparse directory. The `recursive` diff option handles cases
          in which `reset --mixed` must diff/merge files that are nested multiple
     @@ builtin/reset.c: static void update_index_from_diff(struct diff_queue_struct *q,
      +		 * (since we can reset whole sparse directories without expanding them).
      +		 */
      +		if (item.nowildcard_len < item.len) {
     ++			/*
     ++			 * Special case: if the pattern is a path inside the cone
     ++			 * followed by only wildcards, the pattern cannot match
     ++			 * partial sparse directories, so we don't expand the index.
     ++			 */
     ++			if (path_in_cone_mode_sparse_checkout(item.original, &the_index) &&
     ++			    strspn(item.original + item.nowildcard_len, "*") == item.len - item.nowildcard_len)
     ++				continue;
     ++
      +			for (pos = 0; pos < active_nr; pos++) {
      +				struct cache_entry *ce = active_cache[pos];
      +
 8:  f91d1dcf024 = 8:  ddd97fb2837 unpack-trees: improve performance of next_cache_entry

-- 
gitgitgadget

From: Victoria Dye <redacted>

Rename and invert value of `is_missing` to `is_in_reset_tree` to make the
variable more descriptive of what it represents.

Signed-off-by: Victoria Dye <redacted>
---
 builtin/reset.c | 6 +++---
 1 file changed, 3 insertions(+), 3 deletions(-)

diff --git a/builtin/reset.c b/builtin/reset.c
index 51c9e2f43ff..d3695ce43c4 100644
--- a/builtin/reset.c
+++ b/builtin/reset.c

@@ -131,10 +131,10 @@ static void update_index_from_diff(struct diff_queue_struct *q,
 
 	for (i = 0; i < q->nr; i++) {
 		struct diff_filespec *one = q->queue[i]->one;
-		int is_missing = !(one->mode && !is_null_oid(&one->oid));
+		int is_in_reset_tree = one->mode && !is_null_oid(&one->oid);
 		struct cache_entry *ce;
 
-		if (is_missing && !intent_to_add) {
+		if (!is_in_reset_tree && !intent_to_add) {
 			remove_file_from_cache(one->path);
 			continue;
 		}

@@ -144,7 +144,7 @@ static void update_index_from_diff(struct diff_queue_struct *q,
 		if (!ce)
 			die(_("make_cache_entry failed for path '%s'"),
 			    one->path);
-		if (is_missing) {
+		if (!is_in_reset_tree) {
 			ce->ce_flags |= CE_INTENT_TO_ADD;
 			set_object_name_for_intent_to_add_entry(ce);
 		}

-- 
gitgitgadget

From: Victoria Dye <redacted>

Change `update_index_from_diff` to set `skip-worktree` when applicable for
new index entries. When `git reset --mixed <tree-ish>` is run, entries in
the index with differences between the pre-reset HEAD and reset <tree-ish>
are identified and handled with `update_index_from_diff`. For each file, a
new cache entry in inserted into the index, created from the <tree-ish> side
of the reset (without changing the working tree). However, the newly-created
entry must have `skip-worktree` explicitly set in either of the following
scenarios:

1. the file is in the current index and has `skip-worktree` set
2. the file is not in the current index but is outside of a defined sparse
   checkout definition

Not setting the `skip-worktree` bit leads to likely-undesirable results for
a user. It causes `skip-worktree` settings to disappear on the
"diff"-containing files (but *only* the diff-containing files), leading to
those files now showing modifications in `git status`. For example, when
running `git reset --mixed` in a sparse checkout, some file entries outside
of sparse checkout could show up as deleted, despite the user never deleting
anything (and not wanting them on-disk anyway).

Additionally, add a test to `t7102` to ensure `skip-worktree` is preserved
in a basic `git reset --mixed` scenario and update a failure-documenting
test from 19a0acc (t1092: test interesting sparse-checkout scenarios,
2021-01-23) with new expected behavior.

Helped-by: Junio C Hamano [off-list ref]
Signed-off-by: Victoria Dye <redacted>
---
 builtin/reset.c                          | 14 ++++++++++++++
 t/t1092-sparse-checkout-compatibility.sh | 22 ++++++++--------------
 t/t7102-reset.sh                         | 17 +++++++++++++++++
 3 files changed, 39 insertions(+), 14 deletions(-)

diff --git a/builtin/reset.c b/builtin/reset.c
index d3695ce43c4..e441b6601b9 100644
--- a/builtin/reset.c
+++ b/builtin/reset.c

@@ -25,6 +25,7 @@
 #include "cache-tree.h"
 #include "submodule.h"
 #include "submodule-config.h"
+#include "dir.h"
 
 #define REFRESH_INDEX_DELAY_WARNING_IN_MS (2 * 1000)
 

@@ -130,6 +131,7 @@ static void update_index_from_diff(struct diff_queue_struct *q,
 	int intent_to_add = *(int *)data;
 
 	for (i = 0; i < q->nr; i++) {
+		int pos;
 		struct diff_filespec *one = q->queue[i]->one;
 		int is_in_reset_tree = one->mode && !is_null_oid(&one->oid);
 		struct cache_entry *ce;

@@ -141,6 +143,18 @@ static void update_index_from_diff(struct diff_queue_struct *q,
 
 		ce = make_cache_entry(&the_index, one->mode, &one->oid, one->path,
 				      0, 0);
+
+		/*
+		 * If the file 1) corresponds to an existing index entry with
+		 * skip-worktree set, or 2) does not exist in the index but is
+		 * outside the sparse checkout definition, add a skip-worktree bit
+		 * to the new index entry.
+		 */
+		pos = cache_name_pos(one->path, strlen(one->path));
+		if ((pos >= 0 && ce_skip_worktree(active_cache[pos])) ||
+		    (pos < 0 && !path_in_sparse_checkout(one->path, &the_index)))
+			ce->ce_flags |= CE_SKIP_WORKTREE;
+
 		if (!ce)
 			die(_("make_cache_entry failed for path '%s'"),
 			    one->path);

diff --git a/t/t1092-sparse-checkout-compatibility.sh b/t/t1092-sparse-checkout-compatibility.sh
index 886e78715fe..c7449afe965 100755
--- a/t/t1092-sparse-checkout-compatibility.sh
+++ b/t/t1092-sparse-checkout-compatibility.sh

@@ -459,26 +459,20 @@ test_expect_failure 'blame with pathspec outside sparse definition' '
 	test_all_match git blame deep/deeper2/deepest/a
 '
 
-# NEEDSWORK: a sparse-checkout behaves differently from a full checkout
-# in this scenario, but it shouldn't.
-test_expect_failure 'checkout and reset (mixed)' '
+test_expect_success 'checkout and reset (mixed)' '
 	init_repos &&
 
 	test_all_match git checkout -b reset-test update-deep &&
 	test_all_match git reset deepest &&
-	test_all_match git reset update-folder1 &&
-	test_all_match git reset update-folder2
-'
-
-# NEEDSWORK: a sparse-checkout behaves differently from a full checkout
-# in this scenario, but it shouldn't.
-test_expect_success 'checkout and reset (mixed) [sparse]' '
-	init_repos &&
 
-	test_sparse_match git checkout -b reset-test update-deep &&
-	test_sparse_match git reset deepest &&
+	# Because skip-worktree is preserved, resetting to update-folder1
+	# will show worktree changes for folder1/a in full-checkout, but not
+	# in sparse-checkout or sparse-index.
+	git -C full-checkout reset update-folder1 >full-checkout-out &&
 	test_sparse_match git reset update-folder1 &&
-	test_sparse_match git reset update-folder2
+	grep "M	folder1/a" full-checkout-out &&
+	! grep "M	folder1/a" sparse-checkout-out &&
+	run_on_sparse test_path_is_missing folder1
 '
 
 test_expect_success 'merge, cherry-pick, and rebase' '

diff --git a/t/t7102-reset.sh b/t/t7102-reset.sh
index 601b2bf97f0..d05426062ec 100755
--- a/t/t7102-reset.sh
+++ b/t/t7102-reset.sh

@@ -472,6 +472,23 @@ test_expect_success '--mixed refreshes the index' '
 	test_cmp expect output
 '
 
+test_expect_success '--mixed preserves skip-worktree' '
+	echo 123 >>file2 &&
+	git add file2 &&
+	git update-index --skip-worktree file2 &&
+	git reset --mixed HEAD >output &&
+	test_must_be_empty output &&
+
+	cat >expect <<-\EOF &&
+	Unstaged changes after reset:
+	M	file2
+	EOF
+	git update-index --no-skip-worktree file2 &&
+	git add file2 &&
+	git reset --mixed HEAD >output &&
+	test_cmp expect output
+'
+
 test_expect_success 'resetting specific path that is unmerged' '
 	git rm --cached file2 &&
 	F1=$(git rev-parse HEAD:file1) &&

-- 
gitgitgadget

From: Victoria Dye <redacted>

In anticipation of `git reset --hard` being able to use the sparse index
without expanding it, replace the command in `sparse-index is expanded and
converted back` with `git reset -- folder1/a`. This command will need to
expand the index to work properly, even after integrating the rest of
`reset` with sparse index.

Helped-by: Derrick Stolee [off-list ref]
Signed-off-by: Victoria Dye <redacted>
---
 t/t1092-sparse-checkout-compatibility.sh | 6 +++++-
 1 file changed, 5 insertions(+), 1 deletion(-)

diff --git a/t/t1092-sparse-checkout-compatibility.sh b/t/t1092-sparse-checkout-compatibility.sh
index c7449afe965..cab6340a9d0 100755
--- a/t/t1092-sparse-checkout-compatibility.sh
+++ b/t/t1092-sparse-checkout-compatibility.sh

@@ -634,11 +634,15 @@ test_expect_success 'submodule handling' '
 	grep "160000 commit $(git -C initial-repo rev-parse HEAD)	modules/sub" cache
 '
 
+# When working with a sparse index, some commands will need to expand the
+# index to operate properly. If those commands also write the index back
+# to disk, they need to convert the index to sparse before writing.
+# This test verifies that both of these events are logged in trace2 logs.
 test_expect_success 'sparse-index is expanded and converted back' '
 	init_repos &&
 
 	GIT_TRACE2_EVENT="$(pwd)/trace2.txt" GIT_TRACE2_EVENT_NESTING=10 \
-		git -C sparse-index -c core.fsmonitor="" reset --hard &&
+		git -C sparse-index reset -- folder1/a &&
 	test_region index convert_to_sparse trace2.txt &&
 	test_region index ensure_full_index trace2.txt
 '

-- 
gitgitgadget

From: Victoria Dye <redacted>

Add new tests for `--merge` and `--keep` modes, as well as mixed reset with
pathspecs. New performance test cases exercise various execution paths for
`reset`.

Co-authored-by: Derrick Stolee [off-list ref]
Signed-off-by: Derrick Stolee <redacted>
Signed-off-by: Victoria Dye <redacted>
---
 t/perf/p2000-sparse-operations.sh        |  3 +
 t/t1092-sparse-checkout-compatibility.sh | 98 ++++++++++++++++++++++++
 2 files changed, 101 insertions(+)

diff --git a/t/perf/p2000-sparse-operations.sh b/t/perf/p2000-sparse-operations.sh
index 597626276fb..bfd332120c8 100755
--- a/t/perf/p2000-sparse-operations.sh
+++ b/t/perf/p2000-sparse-operations.sh

@@ -110,5 +110,8 @@ test_perf_on_all git add -A
 test_perf_on_all git add .
 test_perf_on_all git commit -a -m A
 test_perf_on_all git checkout -f -
+test_perf_on_all git reset
+test_perf_on_all git reset --hard
+test_perf_on_all git reset -- does-not-exist
 
 test_done

diff --git a/t/t1092-sparse-checkout-compatibility.sh b/t/t1092-sparse-checkout-compatibility.sh
index cab6340a9d0..4125525ab86 100755
--- a/t/t1092-sparse-checkout-compatibility.sh
+++ b/t/t1092-sparse-checkout-compatibility.sh

@@ -475,6 +475,104 @@ test_expect_success 'checkout and reset (mixed)' '
 	run_on_sparse test_path_is_missing folder1
 '
 
+test_expect_success 'checkout and reset (merge)' '
+	init_repos &&
+
+	write_script edit-contents <<-\EOF &&
+	echo text >>$1
+	EOF
+
+	test_all_match git checkout -b reset-test update-deep &&
+	run_on_all ../edit-contents a &&
+	test_all_match git reset --merge deepest &&
+	test_all_match git status --porcelain=v2 &&
+
+	test_all_match git reset --hard update-deep &&
+	run_on_all ../edit-contents deep/a &&
+	test_all_match test_must_fail git reset --merge deepest
+'
+
+test_expect_success 'checkout and reset (keep)' '
+	init_repos &&
+
+	write_script edit-contents <<-\EOF &&
+	echo text >>$1
+	EOF
+
+	test_all_match git checkout -b reset-test update-deep &&
+	run_on_all ../edit-contents a &&
+	test_all_match git reset --keep deepest &&
+	test_all_match git status --porcelain=v2 &&
+
+	test_all_match git reset --hard update-deep &&
+	run_on_all ../edit-contents deep/a &&
+	test_all_match test_must_fail git reset --keep deepest
+'
+
+test_expect_success 'reset with pathspecs inside sparse definition' '
+	init_repos &&
+
+	write_script edit-contents <<-\EOF &&
+	echo text >>$1
+	EOF
+
+	test_all_match git checkout -b reset-test update-deep &&
+	run_on_all ../edit-contents deep/a &&
+
+	test_all_match git reset base -- deep/a &&
+	test_all_match git status --porcelain=v2 &&
+
+	test_all_match git reset base -- nonexistent-file &&
+	test_all_match git status --porcelain=v2 &&
+
+	test_all_match git reset deepest -- deep &&
+	test_all_match git status --porcelain=v2
+'
+
+# Although the working tree differs between full and sparse checkouts after
+# reset, the state of the index is the same.
+test_expect_success 'reset with pathspecs outside sparse definition' '
+	init_repos &&
+	test_all_match git checkout -b reset-test base &&
+
+	test_sparse_match git reset update-folder1 -- folder1 &&
+	git -C full-checkout reset update-folder1 -- folder1 &&
+	test_sparse_match git status --porcelain=v2 &&
+	test_all_match git rev-parse HEAD:folder1 &&
+
+	test_sparse_match git reset update-folder2 -- folder2/a &&
+	git -C full-checkout reset update-folder2 -- folder2/a &&
+	test_sparse_match git status --porcelain=v2 &&
+	test_all_match git rev-parse HEAD:folder2/a
+'
+
+test_expect_success 'reset with wildcard pathspec' '
+	init_repos &&
+
+	test_all_match git reset update-deep -- deep\* &&
+	test_all_match git ls-files -s -- deep &&
+
+	test_all_match git reset deepest -- deep\*\*\* &&
+	test_all_match git ls-files -s -- deep &&
+
+	# The following `git reset`s result in updating the index on files with
+	# `skip-worktree` enabled. To avoid failing due to discrepencies in reported
+	# "modified" files, `test_sparse_match` reset is performed separately from
+	# "full-checkout" reset, then the index contents of all repos are verified.
+
+	test_sparse_match git reset update-folder1 -- \*/a &&
+	git -C full-checkout reset update-folder1 -- \*/a &&
+	test_all_match git ls-files -s -- deep/a folder1/a &&
+
+	test_sparse_match git reset update-folder2 -- folder\* &&
+	git -C full-checkout reset update-folder2 -- folder\* &&
+	test_all_match git ls-files -s -- folder10 folder1 folder2 &&
+
+	test_sparse_match git reset base -- folder1/\* &&
+	git -C full-checkout reset base -- folder1/\* &&
+	test_all_match git ls-files -s -- folder1
+'
+
 test_expect_success 'merge, cherry-pick, and rebase' '
 	init_repos &&
 

-- 
gitgitgadget

From: Victoria Dye <redacted>

Disable `command_requires_full_index` repo setting and add
`ensure_full_index` guards around code paths that cannot yet use sparse
directory index entries. `reset --soft` does not modify the index, so no
compatibility changes are needed for it to function without expanding the
index. For all other reset modes (`--mixed`, `--hard`, `--keep`, `--merge`),
the full index is expanded to prevent cache tree corruption and invalid
variable accesses.

Additionally, the `read_cache()` check verifying an uncorrupted index is
moved after argument parsing and preparing the repo settings. The index is
not used by the preceding argument handling, but `read_cache()` must be run
*after* enabling sparse index for the command (so that the index is not
expanded unnecessarily) and *before* using the index for reset (so that it
is verified as uncorrupted).

Signed-off-by: Victoria Dye <redacted>
---
 builtin/reset.c | 10 +++++++---
 cache-tree.c    |  1 +
 2 files changed, 8 insertions(+), 3 deletions(-)

diff --git a/builtin/reset.c b/builtin/reset.c
index e441b6601b9..0ac0de7dc97 100644
--- a/builtin/reset.c
+++ b/builtin/reset.c

@@ -180,6 +180,7 @@ static int read_from_tree(const struct pathspec *pathspec,
 	opt.flags.override_submodule_config = 1;
 	opt.repo = the_repository;
 
+	ensure_full_index(&the_index);
 	if (do_diff_cache(tree_oid, &opt))
 		return 1;
 	diffcore_std(&opt);

@@ -257,9 +258,6 @@ static void parse_args(struct pathspec *pathspec,
 	}
 	*rev_ret = rev;
 
-	if (read_cache() < 0)
-		die(_("index file corrupt"));
-
 	parse_pathspec(pathspec, 0,
 		       PATHSPEC_PREFER_FULL |
 		       (patch_mode ? PATHSPEC_PREFIX_ORIGIN : 0),

@@ -405,6 +403,12 @@ int cmd_reset(int argc, const char **argv, const char *prefix)
 	if (intent_to_add && reset_type != MIXED)
 		die(_("-N can only be used with --mixed"));
 
+	prepare_repo_settings(the_repository);
+	the_repository->settings.command_requires_full_index = 0;
+
+	if (read_cache() < 0)
+		die(_("index file corrupt"));
+
 	/* Soft reset does not touch the index file nor the working tree
 	 * at all, but requires them in a good order.  Other resets reset
 	 * the index file to the tree object we are switching to. */

diff --git a/cache-tree.c b/cache-tree.c
index 90919f9e345..9be19c85b66 100644
--- a/cache-tree.c
+++ b/cache-tree.c

@@ -776,6 +776,7 @@ void prime_cache_tree(struct repository *r,
 	cache_tree_free(&istate->cache_tree);
 	istate->cache_tree = cache_tree();
 
+	ensure_full_index(istate);
 	prime_cache_tree_rec(r, istate->cache_tree, tree);
 	istate->cache_changed |= CACHE_TREE_CHANGED;
 	trace2_region_leave("cache-tree", "prime_cache_tree", the_repository);

-- 
gitgitgadget

From: Victoria Dye <redacted>

Remove `ensure_full_index` guard on `prime_cache_tree` and update
`prime_cache_tree_rec` to correctly reconstruct sparse directory entries in
the cache tree. While processing a tree's entries, `prime_cache_tree_rec`
must determine whether a directory entry is sparse or not by searching for
it in the index (*without* expanding the index). If a matching sparse
directory index entry is found, no subtrees are added to the cache tree
entry and the entry count is set to 1 (representing the sparse directory
itself). Otherwise, the tree is assumed to not be sparse and its subtrees
are recursively added to the cache tree.

Helped-by: Elijah Newren [off-list ref]
Signed-off-by: Victoria Dye <redacted>
---
 cache-tree.c                             | 47 ++++++++++++++++++++++--
 cache.h                                  | 10 +++++
 read-cache.c                             | 27 ++++++++++----
 t/t1092-sparse-checkout-compatibility.sh | 15 +++++++-
 4 files changed, 86 insertions(+), 13 deletions(-)

diff --git a/cache-tree.c b/cache-tree.c
index 9be19c85b66..2866101052c 100644
--- a/cache-tree.c
+++ b/cache-tree.c

@@ -740,15 +740,26 @@ out:
 	return ret;
 }
 
+static void prime_cache_tree_sparse_dir(struct cache_tree *it,
+					struct tree *tree)
+{
+
+	oidcpy(&it->oid, &tree->object.oid);
+	it->entry_count = 1;
+}
+
 static void prime_cache_tree_rec(struct repository *r,
 				 struct cache_tree *it,
-				 struct tree *tree)
+				 struct tree *tree,
+				 struct strbuf *tree_path)
 {
 	struct tree_desc desc;
 	struct name_entry entry;
 	int cnt;
+	int base_path_len = tree_path->len;
 
 	oidcpy(&it->oid, &tree->object.oid);
+
 	init_tree_desc(&desc, tree->buffer, tree->size);
 	cnt = 0;
 	while (tree_entry(&desc, &entry)) {

@@ -757,14 +768,40 @@ static void prime_cache_tree_rec(struct repository *r,
 		else {
 			struct cache_tree_sub *sub;
 			struct tree *subtree = lookup_tree(r, &entry.oid);
+
 			if (!subtree->object.parsed)
 				parse_tree(subtree);
 			sub = cache_tree_sub(it, entry.path);
 			sub->cache_tree = cache_tree();
-			prime_cache_tree_rec(r, sub->cache_tree, subtree);
+
+			/*
+			 * Recursively-constructed subtree path is only needed when working
+			 * in a sparse index (where it's used to determine whether the
+			 * subtree is a sparse directory in the index).
+			 */
+			if (r->index->sparse_index) {
+				strbuf_setlen(tree_path, base_path_len);
+				strbuf_grow(tree_path, base_path_len + entry.pathlen + 1);
+				strbuf_add(tree_path, entry.path, entry.pathlen);
+				strbuf_addch(tree_path, '/');
+			}
+
+			/*
+			 * If a sparse index is in use, the directory being processed may be
+			 * sparse. To confirm that, we can check whether an entry with that
+			 * exact name exists in the index. If it does, the created subtree
+			 * should be sparse. Otherwise, cache tree expansion should continue
+			 * as normal.
+			 */
+			if (r->index->sparse_index &&
+			    index_entry_exists(r->index, tree_path->buf, tree_path->len))
+				prime_cache_tree_sparse_dir(sub->cache_tree, subtree);
+			else
+				prime_cache_tree_rec(r, sub->cache_tree, subtree, tree_path);
 			cnt += sub->cache_tree->entry_count;
 		}
 	}
+
 	it->entry_count = cnt;
 }
 

@@ -772,12 +809,14 @@ void prime_cache_tree(struct repository *r,
 		      struct index_state *istate,
 		      struct tree *tree)
 {
+	struct strbuf tree_path = STRBUF_INIT;
+
 	trace2_region_enter("cache-tree", "prime_cache_tree", the_repository);
 	cache_tree_free(&istate->cache_tree);
 	istate->cache_tree = cache_tree();
 
-	ensure_full_index(istate);
-	prime_cache_tree_rec(r, istate->cache_tree, tree);
+	prime_cache_tree_rec(r, istate->cache_tree, tree, &tree_path);
+	strbuf_release(&tree_path);
 	istate->cache_changed |= CACHE_TREE_CHANGED;
 	trace2_region_leave("cache-tree", "prime_cache_tree", the_repository);
 }

diff --git a/cache.h b/cache.h
index f6295f3b048..1d3e4665562 100644
--- a/cache.h
+++ b/cache.h

@@ -816,6 +816,16 @@ struct cache_entry *index_file_exists(struct index_state *istate, const char *na
  */
 int index_name_pos(struct index_state *, const char *name, int namelen);
 
+/*
+ * Determines whether an entry with the given name exists within the
+ * given index. The return value is 1 if an exact match is found, otherwise
+ * it is 0. Note that, unlike index_name_pos, this function does not expand
+ * the index if it is sparse. If an item exists within the full index but it
+ * is contained within a sparse directory (and not in the sparse index), 0 is
+ * returned.
+ */
+int index_entry_exists(struct index_state *, const char *name, int namelen);
+
 /*
  * Some functions return the negative complement of an insert position when a
  * precise match was not found but a position was found where the entry would

diff --git a/read-cache.c b/read-cache.c
index f5d4385c408..c079ece981a 100644
--- a/read-cache.c
+++ b/read-cache.c

@@ -68,6 +68,11 @@
  */
 #define CACHE_ENTRY_PATH_LENGTH 80
 
+enum index_search_mode {
+	NO_EXPAND_SPARSE = 0,
+	EXPAND_SPARSE = 1
+};
+
 static inline struct cache_entry *mem_pool__ce_alloc(struct mem_pool *mem_pool, size_t len)
 {
 	struct cache_entry *ce;

@@ -551,7 +556,10 @@ int cache_name_stage_compare(const char *name1, int len1, int stage1, const char
 	return 0;
 }
 
-static int index_name_stage_pos(struct index_state *istate, const char *name, int namelen, int stage)
+static int index_name_stage_pos(struct index_state *istate,
+				const char *name, int namelen,
+				int stage,
+				enum index_search_mode search_mode)
 {
 	int first, last;
 

@@ -570,7 +578,7 @@ static int index_name_stage_pos(struct index_state *istate, const char *name, in
 		first = next+1;
 	}
 
-	if (istate->sparse_index &&
+	if (search_mode == EXPAND_SPARSE && istate->sparse_index &&
 	    first > 0) {
 		/* Note: first <= istate->cache_nr */
 		struct cache_entry *ce = istate->cache[first - 1];

@@ -586,7 +594,7 @@ static int index_name_stage_pos(struct index_state *istate, const char *name, in
 		    ce_namelen(ce) < namelen &&
 		    !strncmp(name, ce->name, ce_namelen(ce))) {
 			ensure_full_index(istate);
-			return index_name_stage_pos(istate, name, namelen, stage);
+			return index_name_stage_pos(istate, name, namelen, stage, search_mode);
 		}
 	}
 

@@ -595,7 +603,12 @@ static int index_name_stage_pos(struct index_state *istate, const char *name, in
 
 int index_name_pos(struct index_state *istate, const char *name, int namelen)
 {
-	return index_name_stage_pos(istate, name, namelen, 0);
+	return index_name_stage_pos(istate, name, namelen, 0, EXPAND_SPARSE);
+}
+
+int index_entry_exists(struct index_state *istate, const char *name, int namelen)
+{
+	return index_name_stage_pos(istate, name, namelen, 0, NO_EXPAND_SPARSE) >= 0;
 }
 
 int remove_index_entry_at(struct index_state *istate, int pos)

@@ -1222,7 +1235,7 @@ static int has_dir_name(struct index_state *istate,
 			 */
 		}
 
-		pos = index_name_stage_pos(istate, name, len, stage);
+		pos = index_name_stage_pos(istate, name, len, stage, EXPAND_SPARSE);
 		if (pos >= 0) {
 			/*
 			 * Found one, but not so fast.  This could

@@ -1322,7 +1335,7 @@ static int add_index_entry_with_check(struct index_state *istate, struct cache_e
 		strcmp(ce->name, istate->cache[istate->cache_nr - 1]->name) > 0)
 		pos = index_pos_to_insert_pos(istate->cache_nr);
 	else
-		pos = index_name_stage_pos(istate, ce->name, ce_namelen(ce), ce_stage(ce));
+		pos = index_name_stage_pos(istate, ce->name, ce_namelen(ce), ce_stage(ce), EXPAND_SPARSE);
 
 	/* existing match? Just replace it. */
 	if (pos >= 0) {

@@ -1357,7 +1370,7 @@ static int add_index_entry_with_check(struct index_state *istate, struct cache_e
 		if (!ok_to_replace)
 			return error(_("'%s' appears as both a file and as a directory"),
 				     ce->name);
-		pos = index_name_stage_pos(istate, ce->name, ce_namelen(ce), ce_stage(ce));
+		pos = index_name_stage_pos(istate, ce->name, ce_namelen(ce), ce_stage(ce), EXPAND_SPARSE);
 		pos = -pos-1;
 	}
 	return pos + 1;

diff --git a/t/t1092-sparse-checkout-compatibility.sh b/t/t1092-sparse-checkout-compatibility.sh
index 4125525ab86..871cc3fcb8d 100755
--- a/t/t1092-sparse-checkout-compatibility.sh
+++ b/t/t1092-sparse-checkout-compatibility.sh

@@ -777,9 +777,9 @@ test_expect_success 'sparse-index is not expanded' '
 	ensure_not_expanded checkout - &&
 	ensure_not_expanded switch rename-out-to-out &&
 	ensure_not_expanded switch - &&
-	git -C sparse-index reset --hard &&
+	ensure_not_expanded reset --hard &&
 	ensure_not_expanded checkout rename-out-to-out -- deep/deeper1 &&
-	git -C sparse-index reset --hard &&
+	ensure_not_expanded reset --hard &&
 	ensure_not_expanded restore -s rename-out-to-out -- deep/deeper1 &&
 
 	echo >>sparse-index/README.md &&