Sparse-index: integrate with status and add

From: Derrick Stolee <[email protected]>

It is difficult, but possible, to get into a state where we intend to add a directory that is outside of the sparse-checkout definition. Add a test to t1092-sparse-checkout-compatibility.sh that demonstrates this using a combination of 'git reset --mixed' and 'git checkout --orphan'.

This test failed before because the output of 'git status --porcelain=v2' would not match on the lines for folder1/:

* The sparse-checkout repo (with a full index) would output each path name that is intended to be added.

* The sparse-index repo would only output that "folder1/" is staged for addition.

The status should report the full list of files to be added, and so this sparse-directory entry should be expanded to a full list when reaching it inside the wt_status_collect_changes_initial() method. Use read_tree_at() to assist.

Somehow, this loop over the cache entries was not guarded by ensure_full_index() as intended.

---
 t/t1092-sparse-checkout-compatibility.sh | 33 ++++++++++++++++
 wt-status.c                              | 49 ++++++++++++++++++++++++
 2 files changed, 82 insertions(+)

index 1e9737cb4b7..ef918437908 100755
@@ -521,4 +521,37 @@ test_expect_success 'sparse-index is not expanded' '
 	test_region ! index ensure_full_index trace2.txt
 '
 
+test_expect_success 'reset mixed and checkout orphan' '
+	init_repos &&
+
+	test_all_match git checkout rename-out-to-in &&
+
+	# Sparse checkouts do not agree with full checkouts about
+	# how to report a directory/file conflict during a reset.
+	# This command would fail with test_all_match because the
+	# full checkout reports "T folder1/0/1" while a sparse
+	# checkout reports "D folder1/0/1". This matches because
+	# the sparse checkouts skip "adding" the other side of
+	# the conflict.
+	test_sparse_match git reset --mixed HEAD~1 &&
+	test_sparse_match test-tool read-cache --table --expand &&
+	test_sparse_match git status --porcelain=v2 &&
+
+	# At this point, sparse-checkouts behave differently
+	# from the full-checkout.
+	test_sparse_match git checkout --orphan new-branch &&
+	test_sparse_match test-tool read-cache --table --expand &&
+	test_sparse_match git status --porcelain=v2
+'
+
+test_expect_success 'add everything with deep new file' '
+	init_repos &&
+
+	run_on_sparse git sparse-checkout set deep/deeper1/deepest &&
+
+	run_on_all touch deep/deeper1/x &&
+	test_all_match git add . &&
+	test_all_match git status --porcelain=v2
+'
+
 test_done

gitgitgadget

From: Derrick Stolee <[email protected]>

If we need to expand a sparse-index into a full one, then the FS Monitor bitmap is going to be incorrect. Ensure that we start fresh at such an event.

While this is currently a performance drawback, the eventual hope of the sparse-index feature is that these expansions will be rare and hence we will be able to keep the FS Monitor data accurate across multiple Git commands.

These tests are added to demonstrate that the behavior is the same across a full index and a sparse index, but also that file modifications to a tracked directory outside of the sparse cone will trigger ensure_full_index().

---
 sparse-index.c              |  7 ++++++
 t/t7519-status-fsmonitor.sh | 48 +++++++++++++++++++++++++++++++++++++
 2 files changed, 55 insertions(+)

index ef53bd2198b..53c8f711ccc 100644
@@ -186,6 +186,10 @@ int convert_to_sparse(struct index_state *istate)
 	cache_tree_free(&istate->cache_tree);
 	cache_tree_update(istate, 0);
 
+	istate->fsmonitor_has_run_once = 0;
+	FREE_AND_NULL(istate->fsmonitor_dirty);
+	FREE_AND_NULL(istate->fsmonitor_last_update);
+
 	istate->sparse_index = 1;
 	trace2_region_leave("index", "convert_to_sparse", istate->repo);
 	return 0;

@@ -282,6 +286,9 @@ void ensure_full_index(struct index_state *istate)
 	istate->cache = full->cache;
 	istate->cache_nr = full->cache_nr;
 	istate->cache_alloc = full->cache_alloc;
+	istate->fsmonitor_has_run_once = 0;
+	FREE_AND_NULL(istate->fsmonitor_dirty);
+	FREE_AND_NULL(istate->fsmonitor_last_update);
 
 	strbuf_release(&base);
 	free(full);

gitgitgadget

On 6/28/2021 9:51 PM, Derrick Stolee via GitGitGadget wrote:
...

I'm very sorry for the noise. I was working on my cover letter and adjusting the patches relative to some nits I discovered, including the ordering of some patches in my larger topic on this subject, and forgot to push those before submitting the v6. Please ignore this version. A correct v7 is coming soon.

Again, sorry for the noise.

-Stolee

This is the first "payoff" series in the sparse-index work. It makes 'git status' very fast when a sparse-index is enabled on a repository with cone-mode sparse-checkout (and a small populated set).

This is based on ds/sparse-index-protections AND mt/add-rm-sparse-checkout. The latter branch is needed because it changes the behavior of 'git add' around sparse entries, which changes the expectations of a test added in patch 1.

The approach here is to audit the places where ensure_full_index() pops up while doing normal commands with pathspecs within the sparse-checkout definition. Each of these are checked and tested. In the end, the sparse-index is integrated with these features:

* git status
* FS Monitor index extension.

The performance tests in p2000-sparse-operations.sh improve by 95% or more, even when compared with the full-index cases, not just the sparse-index cases that previously had extra overhead.

Hopefully this is the first example of how ds/sparse-index-protections has done the basic work to do these conversions safely, making them look easier than they seemed when starting this adventure.

Thanks, -Stolee

Update in V7 (relative to v5)
=============================

APOLOGIES: As I was working on this cover letter, I was still organizing my big list of patches, including reordering some into this series. I forgot to actually include them in my v6 submission, so here is a re-submission. Please ignore v6.

I'm sorry that this revision took so long. Initially I was blocked on getting the directory/file conflict figured out (I did), but also my team was very busy with some things. Eventually, we reached an internal deadline to make an experimental release available [1] with initial sparse-index performance boosts. Creating that included some additional review by Jeff Hostetler and Johannes Schindelin which led to more changes in this version.

The good news is that this series has now created the basis for many Git commands to integrate with the sparse-index without much additional work. This effort was unfortunately overloaded on this series because the changes needed for things like 'git checkout' or 'git add' all intersect with the changes needed for 'git status'. Might as well get it right the first time.

Because the range-diff is a big difficult to read this time, I'll break the changes down on a patch-by-patch basis.

1. sparse-index: skip indexes with unmerged entries

(no change)

2. sparse-index: include EXTENDED flag when expanding

* Commit message better describes the purpose of the change.

3. t1092: replace incorrect 'echo' with 'cat'

* Typo fix

4. t1092: expand repository data shape

* some files are added that surround "folder1/" immediately before and after, based on the sorting with the trailing slash. This provides extra coverage.

5. t1092: add tests for status/add and sparse files

(no change)

6. unpack-trees: preserve cache_bottom

(no change)

7. unpack-trees: compare sparse directories correctly

* We were previosly not comparing the path lengths, which causes a problem (with later updates) when a sparse directory such as "folder1/0/" gets compared to a tree name "folder1".

8. unpack-trees: rename unpack_nondirectories()

* This new commit changes the name to make more sense with its new behavior that could modify a sparse directory entry. The point of the method is in contrast to recursing into trees.

9. unpack-trees: unpack sparse directory entries

* THIS is the biggest change from previous versions. There were a few things going on that were tricky to get right, especially with the directory/file conflict (handled in an update in the following, new patch).

* The changes to create_ce_entry() regarding alloc_len missed a spot that was critical to getting the length right in the allocated entry.

* Use '\0' over 0 to represent the terminating character.

* We don't need a "sparse_directory" parameter to unpack_nondirectories() (which was renamed to unpack_single_entry() by the previous new patch) because we can use dirmask to discover if src[0] (or any other value) should be a sparse directory entry.

* Similarly, we don't need to call the method twice from unpack_callback().

* The 'conflicts' variable is set to match the dirmask in the beginning, but it should depend on whether or not we have a sparse directory entry instead, and if all trees that have the path have a directory.

* The implementation of find_cache_entry() uses find_cache_pos() to find an insertion position for a path if it doesn't find an exact match. Before, we subtracted one to find the sparse directory entry, but there could be multiple paths between the sparse directory entry and the insertion point, so we need to walk backwards until we find it. This requires many paths having the same prefix, so hopefully is a rare case. Some of the test data changes were added to cover the need for this logic. This uses a helper method, sparse_dir_matches_path, which is also used by is_sparse_directory_entry.

10. unpack-trees: handle dir/file conflict of sparse entries

* This new logic inside twoway_merge handles the special case for dealing with a directory/file conflict during a 'git checkout'. The necessarily data and tests are also added here, though the logic will only take serious effect when we integrate with 'git checkout' later.

11. dir.c: accept a directory as part of cone-mode patterns

* The value slash_pos was previously a pointer within a strbuf, but in some cases we add to that strbuf and that could reallocate the pointer, making slash_pos be invalid. The replacement is to have slash_pos be an integer position within the string, so it is consistent even if the string is reallocated for an append.

12. diff-lib: handle index diffs with sparse dirs

* As recommended in the previous review, a simple diff_tree_oid() replaces the complicated use of read_tree_at() and traverse_trees() in the previous version.

13. status: skip sparse-checkout percentage with sparse-index

(no change)

14. status: use sparse-index throughout

(no change)

15. wt-status: expand added sparse directory entries

* Duplicate 'git status --porcelain=v2' lines are removed from tests.

* The pathspec is initialized using "= { 0 }" instead of memset().

16. fsmonitor: integrate with sparse index

* An extra test_region is added to ensure that the filesystem monitor hook is still being called, and we are not simply disabling the feature entirely.

Derrick Stolee (16):
sparse-index: skip indexes with unmerged entries
sparse-index: include EXTENDED flag when expanding
t1092: replace incorrect 'echo' with 'cat'
t1092: expand repository data shape
t1092: add tests for status/add and sparse files
unpack-trees: preserve cache_bottom
unpack-trees: compare sparse directories correctly
unpack-trees: rename unpack_nondirectories()
unpack-trees: unpack sparse directory entries
unpack-trees: handle dir/file conflict of sparse entries dir.c: accept a directory as part of cone-mode patterns
diff-lib: handle index diffs with sparse dirs
status: skip sparse-checkout percentage with sparse-index
status: use sparse-index throughout
wt-status: expand added sparse directory entries
fsmonitor: integrate with sparse index

 builtin/commit.c                         |   3 +
 diff-lib.c                               |  16 ++
 dir.c                                    |  24 ++-
 read-cache.c                             |  10 +-
 sparse-index.c                           |  27 +++-
 t/t1092-sparse-checkout-compatibility.sh | 181 ++++++++++++++++++++++-
 t/t7519-status-fsmonitor.sh              |  49 ++++++
 unpack-trees.c                           | 145 +++++++++++++++---
 wt-status.c                              |  65 +++++++-
 wt-status.h                              |   1 +
 10 files changed, 485 insertions(+), 36 deletions(-)

base-commit: ebf3c04b262aa27fbb97f8a0156c2347fecafafb
Published-As: https://github.com/gitgitgadget/git/releases/tag/pr-932%2Fderrickstolee%2Fsparse-index%2Fstatus-and-add-v7
Fetch-It-Via: git fetch https://github.com/gitgitgadget/git pr-932/derrickstolee/sparse-index/status-and-add-v7
Pull-Request: https://github.com/gitgitgadget/git/pull/932

Range-diff vs v6:

  1:  2a4a7256304 =  1:  2a4a7256304 sparse-index: skip indexes with unmerged entries
  2:  f5bae86014d =  2:  f5bae86014d sparse-index: include EXTENDED flag when expanding
  3:  d965669c766 =  3:  d965669c766 t1092: replace incorrect 'echo' with 'cat'
  4:  44a940211b2 !  4:  e10fa11cfdb t1092: expand repository data shape
     @@ Commit message
            one entry and are the first entry of a directory with multiple
            entries.
      
     +    * Add filenames adjacent to a sparse directory entry that sort before
     +      and after the trailing slash.
     +
          Later tests will take advantage of these shapes, but they also deepen
          the tests that already exist.
      
     @@ t/t1092-sparse-checkout-compatibility.sh: test_expect_success 'setup' '
      +		mkdir deep/deeper1/0/0 &&
      +		touch deep/deeper1/0/1 &&
      +		touch deep/deeper1/0/0/0 &&
     ++		>folder1- &&
     ++		>folder1.x &&
     ++		>folder10 &&
      +		cp -r deep/deeper1/0 folder1 &&
      +		cp -r deep/deeper1/0 folder2 &&
      +		echo >>folder1/0/0/0 &&
  5:  701ac0e8ff6 =  5:  e94ffa07d46 t1092: add tests for status/add and sparse files
  6:  587333f7c61 =  6:  a8dda933567 unpack-trees: preserve cache_bottom
  7:  6fc898ac23e !  7:  e52166f6e4c unpack-trees: compare sparse directories correctly

@@ Commit message
Within compare_entry(), it first calls do_compare_entry() to check the leading portion of the name. When the input path is a directory name, we could match exactly already. Thus, we should return 0 if we have an
- exact string match on a sparse directory entry.
+ exact string match on a sparse directory entry. The final check is a
+ length comparison between the strings.

@@ unpack-trees.c: static int compare_entry(const struct cache_entry *ce, const str
+ * works when the input name is a directory, since ce->name
+ * ends in a directory separator.
+ */
-+ if (S_ISSPARSEDIR(ce->ce_mode))
++ if (S_ISSPARSEDIR(ce->ce_mode) &&
++ ce->ce_namelen == traverse_path_len(info, tree_entry_len(n)) + 1)
+ return 0;
+
/*

  -:  ----------- >  8:  d04b62381b8 unpack-trees: rename unpack_nondirectories()
  8:  b676ef4925b !  9:  237ccf4e43d unpack-trees: unpack sparse directory entries
     @@ Commit message
          might want to perform a merge operation on the entry, such as during
          'git checkout <commit>' which wants to replace a sparse tree entry with
          the tree for that path at the target commit. We extend the logic within
     -    unpack_nondirectories() to create a sparse-directory entry in this case,
     -    and then that is sent to call_unpack_fn(). Since the name becomes
     -    confusing by handling directories, rename it to unpack_single_entry()
     -    since it handles a blob entry or a sparse directory entry without using
     -    traverse_trees_recursive().
     +    unpack_single_entry() to create a sparse-directory entry in this case,
     +    and then that is sent to call_unpack_fn().
      
          There are some subtleties in this process. For instance, we need to
          update find_cache_entry() to allow finding a sparse-directory entry that
          exactly matches a given path. Use the new helper method
     -    sparse_dir_matches_path() for this.
     +    sparse_dir_matches_path() for this. We also need to ignore conflict
     +    markers in the case that the entries correspond to directories and we
     +    already have a sparse directory entry.
      
          Signed-off-by: Derrick Stolee <[email protected]>
      
     @@ unpack-trees.c: static struct cache_entry *create_ce_entry(const struct traverse
       	return ce;
       }
       
     -@@ unpack-trees.c: static struct cache_entry *create_ce_entry(const struct traverse_info *info,
     -  * without actually calling it. If you change the logic here you may need to
     -  * check and change there as well.
     -  */
     --static int unpack_nondirectories(int n, unsigned long mask,
     --				 unsigned long dirmask,
     --				 struct cache_entry **src,
     --				 const struct name_entry *names,
     --				 const struct traverse_info *info)
     -+static int unpack_single_entry(int n, unsigned long mask,
     -+			       unsigned long dirmask,
     -+			       struct cache_entry **src,
     -+			       const struct name_entry *names,
     -+			       const struct traverse_info *info,
     -+			       int sparse_directory)
     - {
     - 	int i;
     +@@ unpack-trees.c: static int unpack_single_entry(int n, unsigned long mask,
       	struct unpack_trees_options *o = info->data;
       	unsigned long conflicts = info->df_conflicts | dirmask;
       
     @@ unpack-trees.c: static struct cache_entry *create_ce_entry(const struct traverse
       	if (mask == dirmask && !src[0])
       		return 0;
       
     -+	/* defer work if our cache entry doesn't match the expectations. */
     -+	if (sparse_directory) {
     -+		if (src[0] && !S_ISSPARSEDIR(src[0]->ce_mode))
     -+			BUG("expected sparse directory entry");
     -+	} else if (src[0] && S_ISSPARSEDIR(src[0]->ce_mode)) {
     -+		return 0;
     -+	}
     ++	/*
     ++	 * When we have a sparse directory entry for src[0],
     ++	 * then this isn't necessarily a directory-file conflict.
     ++	 */
     ++	if (mask == dirmask && src[0] &&
     ++	    S_ISSPARSEDIR(src[0]->ce_mode))
     ++		conflicts = 0;
      +
       	/*
       	 * Ok, we've filled in up to any potential index entry in src[0],
       	 * now do the rest.
     -@@ unpack-trees.c: static int unpack_nondirectories(int n, unsigned long mask,
     +@@ unpack-trees.c: static int unpack_single_entry(int n, unsigned long mask,
       		 * not stored in the index.  otherwise construct the
       		 * cache entry from the index aware logic.
       		 */
      -		src[i + o->merge] = create_ce_entry(info, names + i, stage, &o->result, o->merge);
      +		src[i + o->merge] = create_ce_entry(info, names + i, stage,
      +						    &o->result, o->merge,
     -+						    sparse_directory);
     ++						    bit & dirmask);
       	}
       
       	if (o->merge) {
     @@ unpack-trees.c: static int find_cache_pos(struct traverse_info *info,
      +	 * Check for a sparse-directory entry named "path/".
      +	 * Due to the input p->path not having a trailing
      +	 * slash, the negative 'pos' value overshoots the
     -+	 * expected position by one, hence "-2" here.
     ++	 * expected position by at least one, hence "-2" here.
      +	 */
      +	pos = -pos - 2;
      +
      +	if (pos < 0 || pos >= o->src_index->cache_nr)
       		return NULL;
      +
     -+	ce = o->src_index->cache[pos];
     ++	/*
     ++	 * We might have multiple entries between 'pos' and
     ++	 * the actual sparse-directory entry, so start walking
     ++	 * back until finding it or passing where it would be.
     ++	 */
     ++	while (pos >= 0) {
     ++		ce = o->src_index->cache[pos];
     ++
     ++		if (strncmp(ce->name, p->path, p->pathlen))
     ++			return NULL;
      +
     -+	if (!S_ISSPARSEDIR(ce->ce_mode))
     -+		return NULL;
     ++		if (S_ISSPARSEDIR(ce->ce_mode) &&
     ++		    sparse_dir_matches_path(ce, info, p))
     ++			return ce;
      +
     -+	if (sparse_dir_matches_path(ce, info, p))
     -+		return ce;
     ++		pos--;
     ++	}
      +
      +	return NULL;
       }
     @@ unpack-trees.c: static void debug_unpack_callback(int n,
       /*
        * 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
     -@@ unpack-trees.c: static int unpack_callback(int n, unsigned long mask, unsigned long dirmask, str
     - 		}
     - 	}
     - 
     --	if (unpack_nondirectories(n, mask, dirmask, src, names, info) < 0)
     -+	if (unpack_single_entry(n, mask, dirmask, src, names, info, 0) < 0)
     - 		return -1;
     - 
     - 	if (o->merge && src[0]) {
      @@ unpack-trees.c: static int unpack_callback(int n, unsigned long mask, unsigned long dirmask, str
       			}
       		}
       
      -		if (traverse_trees_recursive(n, dirmask, mask & ~dirmask,
      -					     names, info) < 0)
     -+		if (is_sparse_directory_entry(src[0], names, info)) {
     -+			if (unpack_single_entry(n, dirmask, mask & ~dirmask, src, names, info, 1) < 0)
     -+				return -1;
     -+		} else if (traverse_trees_recursive(n, dirmask, mask & ~dirmask,
     ++		if (!is_sparse_directory_entry(src[0], names, info) &&
     ++		    traverse_trees_recursive(n, dirmask, mask & ~dirmask,
      +						    names, info) < 0) {
       			return -1;
      +		}
  -:  ----------- > 10:  9f31c691af6 unpack-trees: handle dir/file conflict of sparse entries
  9:  d693f00d9a2 ! 11:  2a43287c47e dir.c: accept a directory as part of cone-mode patterns
     @@ Commit message
          Signed-off-by: Derrick Stolee <[email protected]>
      
       ## dir.c ##
     +@@ dir.c: enum pattern_match_result path_matches_pattern_list(
     + 	struct path_pattern *pattern;
     + 	struct strbuf parent_pathname = STRBUF_INIT;
     + 	int result = NOT_MATCHED;
     +-	const char *slash_pos;
     ++	size_t slash_pos;
     + 
     + 	if (!pl->use_cone_patterns) {
     + 		pattern = last_matching_pattern_from_list(pathname, pathlen, basename,
      @@ dir.c: enum pattern_match_result path_matches_pattern_list(
       	strbuf_addch(&parent_pathname, '/');
       	strbuf_add(&parent_pathname, pathname, pathlen);
     @@ dir.c: enum pattern_match_result path_matches_pattern_list(
      +	 * use the file-base matching logic in an equivalent way.
      +	 */
      +	if (parent_pathname.len > 0 &&
     -+	    parent_pathname.buf[parent_pathname.len - 1] == '/')
     ++	    parent_pathname.buf[parent_pathname.len - 1] == '/') {
     ++		slash_pos = parent_pathname.len - 1;
      +		strbuf_add(&parent_pathname, "-", 1);
     ++	} else {
     ++		const char *slash_ptr = strrchr(parent_pathname.buf, '/');
     ++		slash_pos = slash_ptr ? slash_ptr - parent_pathname.buf : 0;
     ++	}
      +
       	if (hashmap_contains_path(&pl->recursive_hashmap,
       				  &parent_pathname)) {
       		result = MATCHED_RECURSIVE;
     + 		goto done;
     + 	}
     + 
     +-	slash_pos = strrchr(parent_pathname.buf, '/');
     +-
     +-	if (slash_pos == parent_pathname.buf) {
     ++	if (!slash_pos) {
     + 		/* include every file in root */
     + 		result = MATCHED;
     + 		goto done;
     + 	}
     + 
     +-	strbuf_setlen(&parent_pathname, slash_pos - parent_pathname.buf);
     ++	strbuf_setlen(&parent_pathname, slash_pos);
     + 
     + 	if (hashmap_contains_path(&pl->parent_hashmap, &parent_pathname)) {
     + 		result = MATCHED;

10: ed11cfc791f ! 12: f83aa08ff6b diff-lib: handle index diffs with sparse dirs
@@ Commit message
identical to before: the lack of a cache entry is the same with a sparse index.

- Use diff_tree_oid() appropriately to appropriately compute the diff.
+ Use diff_tree_oid() appropriately to compute the diff.

 11:  48fd25aacbe = 13:  35063ffb8ed status: skip sparse-checkout percentage with sparse-index
 12:  3499105eb67 = 14:  b4033a9bf36 status: use sparse-index throughout
 13:  08225483d69 ! 15:  717a3f49f97 wt-status: expand added sparse directory entries
     @@ wt-status.c: static void wt_status_collect_changes_index(struct wt_status *s)
      +	struct string_list_item *it;
      +	struct wt_status_change_data *d;
      +	struct wt_status *s = context;
     -+	char *full_name;
     ++	struct strbuf full_name = STRBUF_INIT;
      +
      +	if (S_ISDIR(mode))
      +		return READ_TREE_RECURSIVE;
      +
     -+	full_name = xstrfmt("%s%s", base->buf, path);
     -+	it = string_list_insert(&s->change, full_name);
     ++	strbuf_add(&full_name, base->buf, base->len);
     ++	strbuf_addstr(&full_name, path);
     ++	it = string_list_insert(&s->change, full_name.buf);
      +	d = it->util;
      +	if (!d) {
      +		CALLOC_ARRAY(d, 1);
     @@ wt-status.c: static void wt_status_collect_changes_index(struct wt_status *s)
      +	d->mode_index = mode;
      +	oidcpy(&d->oid_index, oid);
      +	s->committable = 1;
     ++	strbuf_release(&full_name);
      +	return 0;
      +}
      +
 14:  711e403a63a ! 16:  1d744848ee6 fsmonitor: integrate with sparse index
     @@ t/t7519-status-fsmonitor.sh: test_expect_success 'status succeeds after staging/
      +	GIT_TRACE2_EVENT="$(pwd)/trace2.txt" GIT_TRACE2_EVENT_NESTING=10 \
      +		git status --porcelain=v2 >actual &&
      +	test_region $1 index ensure_full_index trace2.txt &&
     ++	test_region fsm_hook query trace2.txt &&
      +	test_cmp expect actual &&
      +	rm trace2.txt &&
      +	git sparse-checkout disable

gitgitgadget

From: Derrick Stolee <[email protected]>

The sparse-index format is designed to be compatible with merge conflicts, even those outside the sparse-checkout definition. The reason is that when converting a full index to a sparse one, a cache entry with nonzero stage will not be collapsed into a sparse directory entry.

However, this behavior was not tested, and a different behavior within convert_to_sparse() fails in this scenario. Specifically, cache_tree_update() will fail when unmerged entries exist. convert_to_sparse_rec() uses the cache-tree data to recursively walk the tree structure, but also to compute the OIDs used in the sparse-directory entries.

Add an index scan to convert_to_sparse() that will detect if these merge conflict entries exist and skip the conversion before trying to update the cache-tree. This is marked as NEEDSWORK because this can be removed with a suitable update to cache_tree_update() or a similar method that can construct a cache-tree with invalid nodes, but still allow creating the nodes necessary for creating sparse directory entries.

It is possible that in the future we will not need to make such an update, since if we do not expand a sparse-index into a full one, this conversion does not need to happen. Thus, this can be deferred until the merge machinery is made to integrate with the sparse-index.

---
 sparse-index.c                           | 18 ++++++++++++++++++
 t/t1092-sparse-checkout-compatibility.sh | 22 ++++++++++++++++++++++
 2 files changed, 40 insertions(+)

index affc4048f27..2c695930275 100644
@@ -116,6 +116,17 @@ int set_sparse_index_config(struct repository *repo, int enable)
 	return res;
 }
 
+static int index_has_unmerged_entries(struct index_state *istate)
+{
+	int i;
+	for (i = 0; i < istate->cache_nr; i++) {
+		if (ce_stage(istate->cache[i]))
+			return 1;
+	}
+
+	return 0;
+}
+
 int convert_to_sparse(struct index_state *istate)
 {
 	int test_env;

@@ -152,6 +163,13 @@ int convert_to_sparse(struct index_state *istate)
 		return -1;
 	}
 
+	/*
+	 * NEEDSWORK: If we have unmerged entries, then stay full.
+	 * Unmerged entries prevent the cache-tree extension from working.
+	 */
+	if (index_has_unmerged_entries(istate))
+		return 0;
+
 	if (cache_tree_update(istate, 0)) {
 		warning(_("unable to update cache-tree, staying full"));
 		return -1;

index e9a815ca7aa..ba2fd94adaf 100755
@@ -352,6 +352,28 @@ test_expect_success 'merge with outside renames' '
 	done
 '
 
+# Sparse-index fails to convert the index in the
+# final 'git cherry-pick' command.
+test_expect_success 'cherry-pick with conflicts' '
+	init_repos &&
+
+	write_script edit-conflict <<-\EOF &&
+	echo $1 >conflict
+	EOF
+
+	test_all_match git checkout -b to-cherry-pick &&
+	run_on_all ../edit-conflict ABC &&
+	test_all_match git add conflict &&
+	test_all_match git commit -m "conflict to pick" &&
+
+	test_all_match git checkout -B base HEAD~1 &&
+	run_on_all ../edit-conflict DEF &&
+	test_all_match git add conflict &&
+	test_all_match git commit -m "conflict in base" &&
+
+	test_all_match test_must_fail git cherry-pick to-cherry-pick
+'
+
 test_expect_success 'clean' '
 	init_repos &&
 

gitgitgadget

From: Derrick Stolee <[email protected]>

When creating a full index from a sparse one, we create cache entries for every blob within a given sparse directory entry. These are correctly marked with the CE_SKIP_WORKTREE flag, but the CE_EXTENDED flag is not included. The CE_EXTENDED flag would exist if we loaded a full index from disk with these entries marked with CE_SKIP_WORKTREE, so we can add the flag here to be consistent. This allows us to directly compare the flags present in cache entries when testing the sparse-index feature, but has no significance to its correctness in the user-facing functionality.

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

index 2c695930275..ef53bd2198b 100644
@@ -213,7 +213,7 @@ static int add_path_to_index(const struct object_id *oid,
 	strbuf_addstr(base, path);
 
 	ce = make_cache_entry(istate, mode, oid, base->buf, 0, 0);
-	ce->ce_flags |= CE_SKIP_WORKTREE;
+	ce->ce_flags |= CE_SKIP_WORKTREE | CE_EXTENDED;
 	set_index_entry(istate, istate->cache_nr++, ce);
 
 	strbuf_setlen(base, len);

gitgitgadget

From: Derrick Stolee <[email protected]>

This fixes the test data shape to be as expected, allowing rename detection to work properly now that the 'larger-content' file actually has meaningful lines.

---
 t/t1092-sparse-checkout-compatibility.sh | 2 +-
 1 file changed, 1 insertion(+), 1 deletion(-)

index ba2fd94adaf..ebbba044f77 100755
@@ -40,7 +40,7 @@ test_expect_success 'setup' '
 		done &&
 
 		git checkout -b rename-base base &&
-		echo >folder1/larger-content <<-\EOF &&
+		cat >folder1/larger-content <<-\EOF &&
 		matching
 		lines
 		help

gitgitgadget

From: Derrick Stolee <[email protected]>

As more features integrate with the sparse-index feature, more and more special cases arise that require different data shapes within the tree structure of the repository in order to demonstrate those cases.

Add several interesting special cases all at once instead of sprinkling them across several commits. The interesting cases being added here are:

* Add sparse-directory entries on both sides of directories within the sparse-checkout definition.

* Add directories outside the sparse-checkout definition who have only one entry and are the first entry of a directory with multiple entries.

* Add filenames adjacent to a sparse directory entry that sort before and after the trailing slash.

Later tests will take advantage of these shapes, but they also deepen the tests that already exist.

---
 t/t1092-sparse-checkout-compatibility.sh | 42 ++++++++++++++++++++++--
 1 file changed, 40 insertions(+), 2 deletions(-)

index ebbba044f77..363d605c209 100755
@@ -17,7 +17,7 @@ test_expect_success 'setup' '
 		echo "after folder1" >g &&
 		echo "after x" >z &&
 		mkdir folder1 folder2 deep x &&
-		mkdir deep/deeper1 deep/deeper2 &&
+		mkdir deep/deeper1 deep/deeper2 deep/before deep/later &&
 		mkdir deep/deeper1/deepest &&
 		echo "after deeper1" >deep/e &&
 		echo "after deepest" >deep/deeper1/e &&

@@ -25,10 +25,23 @@ test_expect_success 'setup' '
 		cp a folder2 &&
 		cp a x &&
 		cp a deep &&
+		cp a deep/before &&
 		cp a deep/deeper1 &&
 		cp a deep/deeper2 &&
+		cp a deep/later &&
 		cp a deep/deeper1/deepest &&
 		cp -r deep/deeper1/deepest deep/deeper2 &&
+		mkdir deep/deeper1/0 &&
+		mkdir deep/deeper1/0/0 &&
+		touch deep/deeper1/0/1 &&
+		touch deep/deeper1/0/0/0 &&
+		>folder1- &&
+		>folder1.x &&
+		>folder10 &&
+		cp -r deep/deeper1/0 folder1 &&
+		cp -r deep/deeper1/0 folder2 &&
+		echo >>folder1/0/0/0 &&
+		echo >>folder2/0/1 &&
 		git add . &&
 		git commit -m "initial commit" &&
 		git checkout -b base &&

@@ -56,11 +69,17 @@ test_expect_success 'setup' '
 		mv folder1/a folder2/b &&
 		mv folder1/larger-content folder2/edited-content &&
 		echo >>folder2/edited-content &&
+		echo >>folder2/0/1 &&
+		echo stuff >>deep/deeper1/a &&
 		git add . &&
 		git commit -m "rename folder1/... to folder2/..." &&
 
 		git checkout -b rename-out-to-in rename-base &&
 		mv folder1/a deep/deeper1/b &&
+		echo more stuff >>deep/deeper1/a &&
+		rm folder2/0/1 &&
+		mkdir folder2/0/1 &&
+		echo >>folder2/0/1/1 &&
 		mv folder1/larger-content deep/deeper1/edited-content &&
 		echo >>deep/deeper1/edited-content &&
 		git add . &&

@@ -68,6 +87,9 @@ test_expect_success 'setup' '
 
 		git checkout -b rename-in-to-out rename-base &&
 		mv deep/deeper1/a folder1/b &&
+		echo >>folder2/0/1 &&
+		rm -rf folder1/0/0 &&
+		echo >>folder1/0/0 &&
 		mv deep/deeper1/larger-content folder1/edited-content &&
 		echo >>folder1/edited-content &&
 		git add . &&

@@ -262,13 +284,29 @@ test_expect_success 'diff --staged' '
 	test_all_match git diff --staged
 '
 
-test_expect_success 'diff with renames' '
+test_expect_success 'diff with renames and conflicts' '
 	init_repos &&
 
 	for branch in rename-out-to-out rename-out-to-in rename-in-to-out
 	do
 		test_all_match git checkout rename-base &&
 		test_all_match git checkout $branch -- .&&
+		test_all_match git status --porcelain=v2 &&
+		test_all_match git diff --staged --no-renames &&
+		test_all_match git diff --staged --find-renames || return 1
+	done
+'
+
+test_expect_success 'diff with directory/file conflicts' '
+	init_repos &&
+
+	for branch in rename-out-to-out rename-out-to-in rename-in-to-out
+	do
+		git -C full-checkout reset --hard &&
+		test_sparse_match git reset --hard &&
+		test_all_match git checkout $branch &&
+		test_all_match git checkout rename-base -- . &&
+		test_all_match git status --porcelain=v2 &&
 		test_all_match git diff --staged --no-renames &&
 		test_all_match git diff --staged --find-renames || return 1
 	done

gitgitgadget

From: Derrick Stolee <[email protected]>

Before moving to update 'git status' and 'git add' to work with sparse indexes, add an explicit test that ensures the sparse-index works the same as a normal sparse-checkout when the worktree contains directories and files outside of the sparse cone.

Specifically, 'folder1/a' is a file in our test repo, but 'folder1' is not in the sparse cone. When 'folder1/a' is modified, the file is not shown as modified and adding it will fail. This is new behavior as of a20f704 (add: warn when asked to update SKIP_WORKTREE entries, 2021-04-08). Before that change, these adds would be silently ignored.

Untracked files are fine: adding new files both with 'git add .' and 'git add folder1/' works just as in a full checkout. This may not be entirely desirable, but we are not intending to change behavior at the moment, only document it. A future change could alter the behavior to be more sensible, and this test could be modified to satisfy the new expected behavior.

---
 t/t1092-sparse-checkout-compatibility.sh | 38 ++++++++++++++++++++++++
 1 file changed, 38 insertions(+)

index 363d605c209..3f61e5686b5 100755
@@ -254,6 +254,44 @@ test_expect_success 'add, commit, checkout' '
 	test_all_match git checkout -
 '
 
+test_expect_success 'status/add: outside sparse cone' '
+	init_repos &&
+
+	# adding a "missing" file outside the cone should fail
+	test_sparse_match test_must_fail git add folder1/a &&
+
+	# folder1 is at HEAD, but outside the sparse cone
+	run_on_sparse mkdir folder1 &&
+	cp initial-repo/folder1/a sparse-checkout/folder1/a &&
+	cp initial-repo/folder1/a sparse-index/folder1/a &&
+
+	test_sparse_match git status &&
+
+	write_script edit-contents <<-\EOF &&
+	echo text >>$1
+	EOF
+	run_on_sparse ../edit-contents folder1/a &&
+	run_on_all ../edit-contents folder1/new &&
+
+	test_sparse_match git status --porcelain=v2 &&
+
+	# This "git add folder1/a" fails with a warning
+	# in the sparse repos, differing from the full
+	# repo. This is intentional.
+	test_sparse_match test_must_fail git add folder1/a &&
+	test_sparse_match test_must_fail git add --refresh folder1/a &&
+	test_all_match git status --porcelain=v2 &&
+
+	test_all_match git add . &&
+	test_all_match git status --porcelain=v2 &&
+	test_all_match git commit -m folder1/new &&
+
+	run_on_all ../edit-contents folder1/newer &&
+	test_all_match git add folder1/ &&
+	test_all_match git status --porcelain=v2 &&
+	test_all_match git commit -m folder1/newer
+'
+
 test_expect_success 'checkout and reset --hard' '
 	init_repos &&
 

gitgitgadget

From: Derrick Stolee <[email protected]>

The cache_bottom member of 'struct unpack_trees_options' is used to track the range of index entries corresponding to a node of the cache tree. While recursing with traverse_by_cache_tree(), this value is preserved on the call stack using a local and then restored as that method returns.

The mark_ce_used() method normally modifies the cache_bottom member when it refers to the marked cache entry. However, sparse directory entries are stored as nodes in the cache-tree data structure as of 2de37c53 (cache-tree: integrate with sparse directory entries, 2021-03-30). Thus, the cache_bottom will be modified as the cache-tree walk advances. Do not update it as well within mark_ce_used().

---
 unpack-trees.c | 7 +++++++
 1 file changed, 7 insertions(+)

index f88a69f8e71..87c1ed204c8 100644
@@ -600,6 +600,13 @@ static void mark_ce_used(struct cache_entry *ce, struct unpack_trees_options *o)
 {
 	ce->ce_flags |= CE_UNPACKED;
 
+	/*
+	 * If this is a sparse directory, don't advance cache_bottom.
+	 * That will be advanced later using the cache-tree data.
+	 */
+	if (S_ISSPARSEDIR(ce->ce_mode))
+		return;
+
 	if (o->cache_bottom < o->src_index->cache_nr &&
 	    o->src_index->cache[o->cache_bottom] == ce) {
 		int bottom = o->cache_bottom;

gitgitgadget

From: Derrick Stolee <[email protected]>

As we further integrate the sparse-index into unpack-trees, we need to ensure that we compare sparse directory entries correctly with other entries. This affects searching for an exact path as well as sorting index entries.

Sparse directory entries contain the trailing directory separator. This is important for the sorting, in particular. Thus, within do_compare_entry() we stop using S_IFREG in all cases, since sparse directories should use S_IFDIR to indicate that the comparison should treat the entry name as a dirctory.

Within compare_entry(), it first calls do_compare_entry() to check the leading portion of the name. When the input path is a directory name, we could match exactly already. Thus, we should return 0 if we have an exact string match on a sparse directory entry. The final check is a length comparison between the strings.

---
 unpack-trees.c | 14 +++++++++++++-
 1 file changed, 13 insertions(+), 1 deletion(-)

index 87c1ed204c8..b113cc750f2 100644
@@ -983,6 +983,7 @@ static int do_compare_entry(const struct cache_entry *ce,
 	int pathlen, ce_len;
 	const char *ce_name;
 	int cmp;
+	unsigned ce_mode;
 
 	/*
 	 * If we have not precomputed the traverse path, it is quicker

@@ -1005,7 +1006,8 @@ static int do_compare_entry(const struct cache_entry *ce,
 	ce_len -= pathlen;
 	ce_name = ce->name + pathlen;
 
-	return df_name_compare(ce_name, ce_len, S_IFREG, name, namelen, mode);
+	ce_mode = S_ISSPARSEDIR(ce->ce_mode) ? S_IFDIR : S_IFREG;
+	return df_name_compare(ce_name, ce_len, ce_mode, name, namelen, mode);
 }
 
 static int compare_entry(const struct cache_entry *ce, const struct traverse_info *info, const struct name_entry *n)

@@ -1014,6 +1016,16 @@ static int compare_entry(const struct cache_entry *ce, const struct traverse_inf
 	if (cmp)
 		return cmp;
 
+	/*
+	 * At this point, we know that we have a prefix match. If ce
+	 * is a sparse directory, then allow an exact match. This only
+	 * works when the input name is a directory, since ce->name
+	 * ends in a directory separator.
+	 */
+	if (S_ISSPARSEDIR(ce->ce_mode) &&
+	    ce->ce_namelen == traverse_path_len(info, tree_entry_len(n)) + 1)
+		return 0;
+
 	/*
 	 * Even if the beginning compared identically, the ce should
 	 * compare as bigger than a directory leading up to it!

gitgitgadget

From: Derrick Stolee <[email protected]>

In the next change, we will use this method to unpack a sparse directory entry, so change the name to unpack_single_entry() so these entries apply. The new name reflects that we will not recurse into trees in order to resolve the conflicts.

---
 unpack-trees.c | 14 +++++++-------
 1 file changed, 7 insertions(+), 7 deletions(-)

index b113cc750f2..d26386ce8b2 100644
@@ -804,7 +804,7 @@ static int traverse_by_cache_tree(int pos, int nr_entries, int nr_names,
 		BUG("We need cache-tree to do this optimization");
 
 	/*
-	 * Do what unpack_callback() and unpack_nondirectories() normally
+	 * Do what unpack_callback() and unpack_single_entry() normally
 	 * do. But we walk all paths in an iterative loop instead.
 	 *
 	 * D/F conflicts and higher stage entries are not a concern

@@ -1075,11 +1075,11 @@ static struct cache_entry *create_ce_entry(const struct traverse_info *info,
  * without actually calling it. If you change the logic here you may need to
  * check and change there as well.
  */
-static int unpack_nondirectories(int n, unsigned long mask,
-				 unsigned long dirmask,
-				 struct cache_entry **src,
-				 const struct name_entry *names,
-				 const struct traverse_info *info)
+static int unpack_single_entry(int n, unsigned long mask,
+			       unsigned long dirmask,
+			       struct cache_entry **src,
+			       const struct name_entry *names,
+			       const struct traverse_info *info)
 {
 	int i;
 	struct unpack_trees_options *o = info->data;

@@ -1322,7 +1322,7 @@ static int unpack_callback(int n, unsigned long mask, unsigned long dirmask, str
 		}
 	}
 
-	if (unpack_nondirectories(n, mask, dirmask, src, names, info) < 0)
+	if (unpack_single_entry(n, mask, dirmask, src, names, info) < 0)
 		return -1;
 
 	if (o->merge && src[0]) {

gitgitgadget

From: Derrick Stolee <[email protected]>

During unpack_callback(), index entries are compared against tree entries. These are matched according to names and types. One goal is to decide if we should recurse into subtrees or simply operate on one index entry.

In the case of a sparse-directory entry, we do not want to recurse into that subtree and instead simply compare the trees. In some cases, we might want to perform a merge operation on the entry, such as during 'git checkout <commit>' which wants to replace a sparse tree entry with the tree for that path at the target commit. We extend the logic within unpack_single_entry() to create a sparse-directory entry in this case, and then that is sent to call_unpack_fn().

There are some subtleties in this process. For instance, we need to update find_cache_entry() to allow finding a sparse-directory entry that exactly matches a given path. Use the new helper method sparse_dir_matches_path() for this. We also need to ignore conflict markers in the case that the entries correspond to directories and we already have a sparse directory entry.

---
 unpack-trees.c | 105 +++++++++++++++++++++++++++++++++++++++++++++----
 1 file changed, 97 insertions(+), 8 deletions(-)

index d26386ce8b2..d141dffbd94 100644
@@ -1052,13 +1052,15 @@ static struct cache_entry *create_ce_entry(const struct traverse_info *info,
 	const struct name_entry *n,
 	int stage,
 	struct index_state *istate,
-	int is_transient)
+	int is_transient,
+	int is_sparse_directory)
 {
 	size_t len = traverse_path_len(info, tree_entry_len(n));
+	size_t alloc_len = is_sparse_directory ? len + 1 : len;
 	struct cache_entry *ce =
 		is_transient ?
-		make_empty_transient_cache_entry(len, NULL) :
-		make_empty_cache_entry(istate, len);
+		make_empty_transient_cache_entry(alloc_len, NULL) :
+		make_empty_cache_entry(istate, alloc_len);
 
 	ce->ce_mode = create_ce_mode(n->mode);
 	ce->ce_flags = create_ce_flags(stage);

@@ -1067,6 +1069,13 @@ static struct cache_entry *create_ce_entry(const struct traverse_info *info,
 	/* len+1 because the cache_entry allocates space for NUL */
 	make_traverse_path(ce->name, len + 1, info, n->path, n->pathlen);
 
+	if (is_sparse_directory) {
+		ce->name[len] = '/';
+		ce->name[len + 1] = '\0';
+		ce->ce_namelen++;
+		ce->ce_flags |= CE_SKIP_WORKTREE;
+	}
+
 	return ce;
 }
 

@@ -1085,10 +1094,17 @@ static int unpack_single_entry(int n, unsigned long mask,
 	struct unpack_trees_options *o = info->data;
 	unsigned long conflicts = info->df_conflicts | dirmask;
 
-	/* Do we have *only* directories? Nothing to do */
 	if (mask == dirmask && !src[0])
 		return 0;
 
+	/*
+	 * When we have a sparse directory entry for src[0],
+	 * then this isn't necessarily a directory-file conflict.
+	 */
+	if (mask == dirmask && src[0] &&
+	    S_ISSPARSEDIR(src[0]->ce_mode))
+		conflicts = 0;
+
 	/*
 	 * Ok, we've filled in up to any potential index entry in src[0],
 	 * now do the rest.

@@ -1118,7 +1134,9 @@ static int unpack_single_entry(int n, unsigned long mask,
 		 * not stored in the index.  otherwise construct the
 		 * cache entry from the index aware logic.
 		 */
-		src[i + o->merge] = create_ce_entry(info, names + i, stage, &o->result, o->merge);
+		src[i + o->merge] = create_ce_entry(info, names + i, stage,
+						    &o->result, o->merge,
+						    bit & dirmask);
 	}
 
 	if (o->merge) {

@@ -1222,16 +1240,69 @@ static int find_cache_pos(struct traverse_info *info,
 	return -1;
 }
 
+/*
+ * Given a sparse directory entry 'ce', compare ce->name to
+ * info->name + '/' + p->path + '/' if info->name is non-empty.
+ * Compare ce->name to p->path + '/' otherwise. Note that
+ * ce->name must end in a trailing '/' because it is a sparse
+ * directory entry.
+ */
+static int sparse_dir_matches_path(const struct cache_entry *ce,
+				   struct traverse_info *info,
+				   const struct name_entry *p)
+{
+	assert(S_ISSPARSEDIR(ce->ce_mode));
+	assert(ce->name[ce->ce_namelen - 1] == '/');
+
+	if (info->namelen)
+		return ce->ce_namelen == info->namelen + p->pathlen + 2 &&
+		       ce->name[info->namelen] == '/' &&
+		       !strncmp(ce->name, info->name, info->namelen) &&
+		       !strncmp(ce->name + info->namelen + 1, p->path, p->pathlen);
+	return ce->ce_namelen == p->pathlen + 1 &&
+	       !strncmp(ce->name, p->path, p->pathlen);
+}
+
 static struct cache_entry *find_cache_entry(struct traverse_info *info,
 					    const struct name_entry *p)
 {
+	struct cache_entry *ce;
 	int pos = find_cache_pos(info, p->path, p->pathlen);
 	struct unpack_trees_options *o = info->data;
 
 	if (0 <= pos)
 		return o->src_index->cache[pos];
-	else
+
+	/*
+	 * Check for a sparse-directory entry named "path/".
+	 * Due to the input p->path not having a trailing
+	 * slash, the negative 'pos' value overshoots the
+	 * expected position by at least one, hence "-2" here.
+	 */
+	pos = -pos - 2;
+
+	if (pos < 0 || pos >= o->src_index->cache_nr)
 		return NULL;
+
+	/*
+	 * We might have multiple entries between 'pos' and
+	 * the actual sparse-directory entry, so start walking
+	 * back until finding it or passing where it would be.
+	 */
+	while (pos >= 0) {
+		ce = o->src_index->cache[pos];
+
+		if (strncmp(ce->name, p->path, p->pathlen))
+			return NULL;
+
+		if (S_ISSPARSEDIR(ce->ce_mode) &&
+		    sparse_dir_matches_path(ce, info, p))
+			return ce;
+
+		pos--;
+	}
+
+	return NULL;
 }
 
 static void debug_path(struct traverse_info *info)

@@ -1266,6 +1337,21 @@ static void debug_unpack_callback(int n,
 		debug_name_entry(i, names + i);
 }
 
+/*
+ * Returns true if and only if the given cache_entry is a
+ * sparse-directory entry that matches the given name_entry
+ * from the tree walk at the given traverse_info.
+ */
+static int is_sparse_directory_entry(struct cache_entry *ce,
+				     struct name_entry *name,
+				     struct traverse_info *info)
+{
+	if (!ce || !name || !S_ISSPARSEDIR(ce->ce_mode))
+		return 0;
+
+	return sparse_dir_matches_path(ce, info, name);
+}
+
 /*
  * 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

@@ -1352,9 +1438,12 @@ static int unpack_callback(int n, unsigned long mask, unsigned long dirmask, str
 			}
 		}
 
-		if (traverse_trees_recursive(n, dirmask, mask & ~dirmask,
-					     names, info) < 0)
+		if (!is_sparse_directory_entry(src[0], names, info) &&
+		    traverse_trees_recursive(n, dirmask, mask & ~dirmask,
+						    names, info) < 0) {
 			return -1;
+		}
+
 		return mask;
 	}
 

gitgitgadget

From: Derrick Stolee <[email protected]>

---
 t/t1092-sparse-checkout-compatibility.sh | 25 ++++++++++++++++++++++--
 unpack-trees.c                           |  5 ++++-
 2 files changed, 27 insertions(+), 3 deletions(-)

index 3f61e5686b5..4e6446e7545 100755
@@ -95,6 +95,19 @@ test_expect_success 'setup' '
 		git add . &&
 		git commit -m "rename deep/deeper1/... to folder1/..." &&
 
+		git checkout -b df-conflict base &&
+		rm -rf folder1 &&
+		echo content >folder1 &&
+		git add . &&
+		git commit -m df &&
+
+		git checkout -b fd-conflict base &&
+		rm a &&
+		mkdir a &&
+		echo content >a/a &&
+		git add . &&
+		git commit -m fd &&
+
 		git checkout -b deepest base &&
 		echo "updated deepest" >deep/deeper1/deepest/a &&
 		git commit -a -m "update deepest" &&

@@ -325,7 +338,11 @@ test_expect_success 'diff --staged' '
 test_expect_success 'diff with renames and conflicts' '
 	init_repos &&
 
-	for branch in rename-out-to-out rename-out-to-in rename-in-to-out
+	for branch in rename-out-to-out \
+		      rename-out-to-in \
+		      rename-in-to-out \
+		      df-conflict \
+		      fd-conflict
 	do
 		test_all_match git checkout rename-base &&
 		test_all_match git checkout $branch -- .&&

@@ -338,7 +355,11 @@ test_expect_success 'diff with renames and conflicts' '
 test_expect_success 'diff with directory/file conflicts' '
 	init_repos &&
 
-	for branch in rename-out-to-out rename-out-to-in rename-in-to-out
+	for branch in rename-out-to-out \
+		      rename-out-to-in \
+		      rename-in-to-out \
+		      df-conflict \
+		      fd-conflict
 	do
 		git -C full-checkout reset --hard &&
 		test_sparse_match git reset --hard &&

index d141dffbd94..e63b2dcacbc 100644
@@ -2617,7 +2617,10 @@ int twoway_merge(const struct cache_entry * const *src,
 			 same(current, oldtree) && !same(current, newtree)) {
 			/* 20 or 21 */
 			return merged_entry(newtree, current, o);
-		} else
+		} else if (current && !oldtree && newtree &&
+			   S_ISSPARSEDIR(current->ce_mode) != S_ISSPARSEDIR(newtree->ce_mode))
+			return merged_entry(newtree, current, o);
+		else
 			return reject_merge(current, o);
 	}
 	else if (newtree) {

gitgitgadget

t1092 still passes if you replace the

    return merged_entry(newtree, current, o);
line with
    die("This line is never hit.");

Is it possible that you thought you needed this block but further refactoring removed the need? Or that it is only needed by the later ds/commit-and-checkout-with-sparse-index topic (which I haven't yet reviewed, because I was reviewing this topic first)? It seems this code change should either be dropped, or moved out to the relevant series that uses it.

It turns out that this testcase I provided still triggers the same fatal error if you omit the --sparse-index flag, so it's not a sparse-index-specific bug.

So, perhaps it shouldn't hold up this series, but given that a lot of your correctness verification in t1092 relies on comparisons between sparse checkouts and sparse indexes, it might be worth trying to get to the root of this.

...

I have been working with the whole stack of patches (including the ones that update 'git add') and trying to make the necessary changes in this series, especially when updating the test data shape or modifying methods that were necessary for 'git status'.

It is likely I was just overcautious thinking this was necessary so early. It might also have been necessary due to some strange case that is only exposed in a Scalar functional test. I'll try moving it to the next series and double check those tests.

The most important point is that 'current' and 'newtree' are both present but have different types (blob and tree) and the tree is necessarily at the edge of the sparse-checkout cone. In the cases where I was able to trigger this logic in the debugger, 'oldtree' was NULL, so I added as a condition to be extra cautious around unexpected initialization. It is possible that the '!oldtree' condition is unnecessary. I will investigate.

As for verify_uptodate(), it ignores the sparse directory unless o->skip_sparse_checkout is set. I wonder if it is possible to have that set and hit this case.

...

Thank you for finding an interesting test!

I have some upcoming thoughts on changing how sparse-checkout works for other complicated cases, so I will add this to that pile.

Thanks,
-Stolee

From: Derrick Stolee <[email protected]>

When we have sparse directory entries in the index, we want to compare that directory against sparse-checkout patterns. Those pattern matching algorithms are built expecting a file path, not a directory path. This is especially important in the "cone mode" patterns which will match files that exist within the "parent directories" as well as the recursive directory matches.

If path_matches_pattern_list() is given a directory, we can add a fake filename ("-") to the directory and get the same results as before, assuming we are in cone mode. Since sparse index requires cone mode patterns, this is an acceptable assumption.

---
 dir.c | 24 +++++++++++++++++++-----
 1 file changed, 19 insertions(+), 5 deletions(-)

index ebe5ec046e0..0c5264b3b20 100644
@@ -1376,7 +1376,7 @@ enum pattern_match_result path_matches_pattern_list(
 	struct path_pattern *pattern;
 	struct strbuf parent_pathname = STRBUF_INIT;
 	int result = NOT_MATCHED;
-	const char *slash_pos;
+	size_t slash_pos;
 
 	if (!pl->use_cone_patterns) {
 		pattern = last_matching_pattern_from_list(pathname, pathlen, basename,

@@ -1397,21 +1397,35 @@ enum pattern_match_result path_matches_pattern_list(
 	strbuf_addch(&parent_pathname, '/');
 	strbuf_add(&parent_pathname, pathname, pathlen);
 
+	/*
+	 * Directory entries are matched if and only if a file
+	 * contained immediately within them is matched. For the
+	 * case of a directory entry, modify the path to create
+	 * a fake filename within this directory, allowing us to
+	 * use the file-base matching logic in an equivalent way.
+	 */
+	if (parent_pathname.len > 0 &&
+	    parent_pathname.buf[parent_pathname.len - 1] == '/') {
+		slash_pos = parent_pathname.len - 1;
+		strbuf_add(&parent_pathname, "-", 1);
+	} else {
+		const char *slash_ptr = strrchr(parent_pathname.buf, '/');
+		slash_pos = slash_ptr ? slash_ptr - parent_pathname.buf : 0;
+	}
+
 	if (hashmap_contains_path(&pl->recursive_hashmap,
 				  &parent_pathname)) {
 		result = MATCHED_RECURSIVE;
 		goto done;
 	}
 
-	slash_pos = strrchr(parent_pathname.buf, '/');
-
-	if (slash_pos == parent_pathname.buf) {
+	if (!slash_pos) {
 		/* include every file in root */
 		result = MATCHED;
 		goto done;
 	}
 
-	strbuf_setlen(&parent_pathname, slash_pos - parent_pathname.buf);
+	strbuf_setlen(&parent_pathname, slash_pos);
 
 	if (hashmap_contains_path(&pl->parent_hashmap, &parent_pathname)) {
 		result = MATCHED;

gitgitgadget

From: Derrick Stolee <[email protected]>

While comparing an index to a tree, we may see a sparse directory entry. In this case, we should compare that portion of the tree to the tree represented by that entry. This could include a new tree which needs to be expanded to a full list of added files. It could also include an existing tree, in which case all of the changes inside are important to describe, including the modifications, additions, and deletions. Note that the case where the tree has a path and the index does not remains identical to before: the lack of a cache entry is the same with a sparse index.

Use diff_tree_oid() appropriately to compute the diff.

---
 diff-lib.c | 16 ++++++++++++++++
 1 file changed, 16 insertions(+)

index c2ac9250fe9..3f32f038371 100644
@@ -325,6 +325,11 @@ static void show_new_file(struct rev_info *revs,
 	unsigned dirty_submodule = 0;
 	struct index_state *istate = revs->diffopt.repo->index;
 
+	if (new_file && S_ISSPARSEDIR(new_file->ce_mode)) {
+		diff_tree_oid(NULL, &new_file->oid, new_file->name, &revs->diffopt);
+		return;
+	}
+
 	/*
 	 * New file in the index: it might actually be different in
 	 * the working tree.

@@ -347,6 +352,17 @@ static int show_modified(struct rev_info *revs,
 	unsigned dirty_submodule = 0;
 	struct index_state *istate = revs->diffopt.repo->index;
 
+	/*
+	 * If both are sparse directory entries, then expand the
+	 * modifications to the file level.
+	 */
+	if (old_entry && new_entry &&
+	    S_ISSPARSEDIR(old_entry->ce_mode) &&
+	    S_ISSPARSEDIR(new_entry->ce_mode)) {
+		diff_tree_oid(&old_entry->oid, &new_entry->oid, new_entry->name, &revs->diffopt);
+		return 0;
+	}
+
 	if (get_stat_data(istate, new_entry, &oid, &mode, cached, match_missing,
 			  &dirty_submodule, &revs->diffopt) < 0) {
 		if (report_missing)

gitgitgadget

Digging a little deeper, it appears that we could add this just before your new if-block:

    assert(S_ISSPARSEDIR(old_entry->ce_mode) ==
           S_ISSPARSEDIR(new_entry->ce_mode));

And the code still functions, while that also removes some of the surprise factor. I'm guessing that the difference between "folder1" and "folder1/" cause us to never try to directly compare a file to a directory...but if that's accurate, a comment of some effect might help make this code be a little clearer and make readers less likely to wonder why you need to check that both old and new are sparse directories.

...

I was surprised that this worked, because my patch conditioned on old_entry and new_entry being non-NULL. But of course show_modified() requires them to be non-NULL. That can be further simplified.

Adding the assert helps demonstrate this expectation, but also I will expand upon the comment.

Thanks,
-Stolee

From: Derrick Stolee <[email protected]>

'git status' began reporting a percentage of populated paths when sparse-checkout is enabled in 051df3cf (wt-status: show sparse checkout status as well, 2020-07-18). This percentage is incorrect when the index has sparse directories. It would also be expensive to calculate as we would need to parse trees to count the total number of possible paths.

Avoid the expensive computation by simplifying the output to only report that a sparse checkout exists, without the percentage.

This change is the reason we use 'git status --porcelain=v2' in t1092-sparse-checkout-compatibility.sh. We don't want to ensure that this message is equal across both modes, but instead just the important information about staged, modified, and untracked files are compared.

---
 t/t1092-sparse-checkout-compatibility.sh |  8 ++++++++
 wt-status.c                              | 14 +++++++++++---
 wt-status.h                              |  1 +
 3 files changed, 20 insertions(+), 3 deletions(-)

index 4e6446e7545..d372932cd12 100755
@@ -231,6 +231,14 @@ test_expect_success 'status with options' '
 	test_all_match git status --porcelain=v2 -uno
 '
 
+test_expect_success 'status reports sparse-checkout' '
+	init_repos &&
+	git -C sparse-checkout status >full &&
+	git -C sparse-index status >sparse &&
+	test_i18ngrep "You are in a sparse checkout with " full &&
+	test_i18ngrep "You are in a sparse checkout." sparse
+'
+
 test_expect_success 'add, commit, checkout' '
 	init_repos &&
 

index 42b67357169..96db3e74962 100644
@@ -1493,9 +1493,12 @@ static void show_sparse_checkout_in_use(struct wt_status *s,
 	if (s->state.sparse_checkout_percentage == SPARSE_CHECKOUT_DISABLED)
 		return;
 
-	status_printf_ln(s, color,
-			 _("You are in a sparse checkout with %d%% of tracked files present."),
-			 s->state.sparse_checkout_percentage);
+	if (s->state.sparse_checkout_percentage == SPARSE_CHECKOUT_SPARSE_INDEX)
+		status_printf_ln(s, color, _("You are in a sparse checkout."));
+	else
+		status_printf_ln(s, color,
+				_("You are in a sparse checkout with %d%% of tracked files present."),
+				s->state.sparse_checkout_percentage);
 	wt_longstatus_print_trailer(s);
 }
 

@@ -1653,6 +1656,11 @@ static void wt_status_check_sparse_checkout(struct repository *r,
 		return;
 	}
 
+	if (r->index->sparse_index) {
+		state->sparse_checkout_percentage = SPARSE_CHECKOUT_SPARSE_INDEX;
+		return;
+	}
+
 	for (i = 0; i < r->index->cache_nr; i++) {
 		struct cache_entry *ce = r->index->cache[i];
 		if (ce_skip_worktree(ce))

index 0d32799b28e..ab9cc9d8f03 100644
@@ -78,6 +78,7 @@ enum wt_status_format {
 };
 
 #define SPARSE_CHECKOUT_DISABLED -1
+#define SPARSE_CHECKOUT_SPARSE_INDEX -2
 
 struct wt_status_state {
 	int merge_in_progress;

gitgitgadget

From: Derrick Stolee <[email protected]>

By testing 'git -c core.fsmonitor= status -uno', we can check for the simplest index operations that can be made sparse-aware. The necessary implementation details are already integrated with sparse-checkout, so modify command_requires_full_index to be zero for cmd_status().

In refresh_index(), we loop through the index entries to refresh their stat() information. However, sparse directories have no stat() information to populate. Ignore these entries.

This allows 'git status' to no longer expand a sparse index to a full one. This is further tested by dropping the "-uno" option and adding an untracked file into the worktree.

The performance test p2000-sparse-checkout-operations.sh demonstrates these improvements:

Test HEAD~1 HEAD
-----------------------------------------------------------------------------

2000.2: git status (full-index-v3)    0.31(0.30+0.05)  0.31(0.29+0.06) +0.0%
2000.3: git status (full-index-v4)    0.31(0.29+0.07)  0.34(0.30+0.08) +9.7%
2000.4: git status (sparse-index-v3)  2.35(2.28+0.10)  0.04(0.04+0.05) -98.3%
2000.5: git status (sparse-index-v4)  2.35(2.24+0.15)  0.05(0.04+0.06) -97.9%

Note that since HEAD~1 was expanding the sparse index by parsing trees, it was artificially slower than the full index case. Thus, the 98% improvement is misleading, and instead we should celebrate the 0.34s to 0.05s improvement of 85%. This is more indicative of the peformance gains we are expecting by using a sparse index.

Note: we are dropping the assignment of core.fsmonitor here. This is not necessary for the test script as we are not altering the config any other way. Correct integration with FS Monitor will be validated in later changes.

---
 builtin/commit.c                         |  3 +++
 read-cache.c                             | 10 ++++++++--
 t/t1092-sparse-checkout-compatibility.sh | 13 +++++++++----
 3 files changed, 20 insertions(+), 6 deletions(-)

index 190d215d43b..12f51db158a 100644
@@ -1510,6 +1510,9 @@ int cmd_status(int argc, const char **argv, const char *prefix)
 	if (argc == 2 && !strcmp(argv[1], "-h"))
 		usage_with_options(builtin_status_usage, builtin_status_options);
 
+	prepare_repo_settings(the_repository);
+	the_repository->settings.command_requires_full_index = 0;
+
 	status_init_config(&s, git_status_config);
 	argc = parse_options(argc, argv, prefix,
 			     builtin_status_options,

index 1b3c2eb408b..277c2970a03 100644
@@ -1584,8 +1584,7 @@ int refresh_index(struct index_state *istate, unsigned int flags,
 	 */
 	preload_index(istate, pathspec, 0);
 	trace2_region_enter("index", "refresh", NULL);
-	/* TODO: audit for interaction with sparse-index. */
-	ensure_full_index(istate);
+
 	for (i = 0; i < istate->cache_nr; i++) {
 		struct cache_entry *ce, *new_entry;
 		int cache_errno = 0;

@@ -1600,6 +1599,13 @@ int refresh_index(struct index_state *istate, unsigned int flags,
 		if (ignore_skip_worktree && ce_skip_worktree(ce))
 			continue;
 
+		/*
+		 * If this entry is a sparse directory, then there isn't
+		 * any stat() information to update. Ignore the entry.
+		 */
+		if (S_ISSPARSEDIR(ce->ce_mode))
+			continue;
+
 		if (pathspec && !ce_path_match(istate, ce, pathspec, seen))
 			filtered = 1;
 

index d372932cd12..fed0440bafe 100755
@@ -532,12 +532,17 @@ test_expect_success 'sparse-index is expanded and converted back' '
 	GIT_TRACE2_EVENT="$(pwd)/trace2.txt" GIT_TRACE2_EVENT_NESTING=10 \
 		git -C sparse-index -c core.fsmonitor="" reset --hard &&
 	test_region index convert_to_sparse trace2.txt &&
-	test_region index ensure_full_index trace2.txt &&
+	test_region index ensure_full_index trace2.txt
+'
 
-	rm trace2.txt &&
+test_expect_success 'sparse-index is not expanded' '
+	init_repos &&
+
+	rm -f trace2.txt &&
+	echo >>sparse-index/untracked.txt &&
 	GIT_TRACE2_EVENT="$(pwd)/trace2.txt" GIT_TRACE2_EVENT_NESTING=10 \
-		git -C sparse-index -c core.fsmonitor="" status -uno &&
-	test_region index ensure_full_index trace2.txt
+		git -C sparse-index status &&
+	test_region ! index ensure_full_index trace2.txt
 '
 
 test_done

gitgitgadget

From: Derrick Stolee <[email protected]>

It is difficult, but possible, to get into a state where we intend to add a directory that is outside of the sparse-checkout definition. Add a test to t1092-sparse-checkout-compatibility.sh that demonstrates this using a combination of 'git reset --mixed' and 'git checkout --orphan'.

This test failed before because the output of 'git status --porcelain=v2' would not match on the lines for folder1/:

* The sparse-checkout repo (with a full index) would output each path name that is intended to be added.

* The sparse-index repo would only output that "folder1/" is staged for addition.

The status should report the full list of files to be added, and so this sparse-directory entry should be expanded to a full list when reaching it inside the wt_status_collect_changes_initial() method. Use read_tree_at() to assist.

Somehow, this loop over the cache entries was not guarded by ensure_full_index() as intended.

---
 t/t1092-sparse-checkout-compatibility.sh | 33 +++++++++++++++
 wt-status.c                              | 51 ++++++++++++++++++++++++
 2 files changed, 84 insertions(+)

index fed0440bafe..df217a2d10b 100755
@@ -545,4 +545,37 @@ test_expect_success 'sparse-index is not expanded' '
 	test_region ! index ensure_full_index trace2.txt
 '
 
+test_expect_success 'reset mixed and checkout orphan' '
+	init_repos &&
+
+	test_all_match git checkout rename-out-to-in &&
+
+	# Sparse checkouts do not agree with full checkouts about
+	# how to report a directory/file conflict during a reset.
+	# This command would fail with test_all_match because the
+	# full checkout reports "T folder1/0/1" while a sparse
+	# checkout reports "D folder1/0/1". This matches because
+	# the sparse checkouts skip "adding" the other side of
+	# the conflict.
+	test_sparse_match git reset --mixed HEAD~1 &&
+	test_sparse_match test-tool read-cache --table --expand &&
+	test_sparse_match git status --porcelain=v2 &&
+
+	# At this point, sparse-checkouts behave differently
+	# from the full-checkout.
+	test_sparse_match git checkout --orphan new-branch &&
+	test_sparse_match test-tool read-cache --table --expand &&
+	test_sparse_match git status --porcelain=v2
+'
+
+test_expect_success 'add everything with deep new file' '
+	init_repos &&
+
+	run_on_sparse git sparse-checkout set deep/deeper1/deepest &&
+
+	run_on_all touch deep/deeper1/x &&
+	test_all_match git add . &&
+	test_all_match git status --porcelain=v2
+'
+
 test_done

gitgitgadget

...

I'll add it to the pile, but I want to continue having this series focus on making the sparse-index work quickly without a change in behavior from a normal index. Changing the behavior of the sparse- checkout feature should be a separate series.

Thanks,
-Stolee

Hmm..perhaps there's some middle ground? I appreciate that you want to have this series focus on making the sparse-index work without worrying about behavioral changes to sparse-checkout. I'm concerned, though, that testcases tend to be treated as documentation of intended behavior, even when the tests are testing something else. These tests are clearly triggering buggy behavior, and I think your comments and subsequent command may be affected by it. I don't want to leave future folks (even ourselves) to have to try to explain away why the behavior expected in this test should not be expected.

Perhaps we can just add a comment that this testcase is triggering a bug in both sparse-checkout and sparse-index but we're only checking that the two match, and that once the bug is fix, the testcase itself may need tweaking?

I can get behind that approach: document the bug, but comment that it _is_ a bug and should be changed in the future.

Thanks,
-Stolee

From: Derrick Stolee <[email protected]>

If we need to expand a sparse-index into a full one, then the FS Monitor bitmap is going to be incorrect. Ensure that we start fresh at such an event.

While this is currently a performance drawback, the eventual hope of the sparse-index feature is that these expansions will be rare and hence we will be able to keep the FS Monitor data accurate across multiple Git commands.

These tests are added to demonstrate that the behavior is the same across a full index and a sparse index, but also that file modifications to a tracked directory outside of the sparse cone will trigger ensure_full_index().

---
 sparse-index.c              |  7 ++++++
 t/t7519-status-fsmonitor.sh | 49 +++++++++++++++++++++++++++++++++++++
 2 files changed, 56 insertions(+)

index ef53bd2198b..53c8f711ccc 100644
@@ -186,6 +186,10 @@ int convert_to_sparse(struct index_state *istate)
 	cache_tree_free(&istate->cache_tree);
 	cache_tree_update(istate, 0);
 
+	istate->fsmonitor_has_run_once = 0;
+	FREE_AND_NULL(istate->fsmonitor_dirty);
+	FREE_AND_NULL(istate->fsmonitor_last_update);
+
 	istate->sparse_index = 1;
 	trace2_region_leave("index", "convert_to_sparse", istate->repo);
 	return 0;

@@ -282,6 +286,9 @@ void ensure_full_index(struct index_state *istate)
 	istate->cache = full->cache;
 	istate->cache_nr = full->cache_nr;
 	istate->cache_alloc = full->cache_alloc;
+	istate->fsmonitor_has_run_once = 0;
+	FREE_AND_NULL(istate->fsmonitor_dirty);
+	FREE_AND_NULL(istate->fsmonitor_last_update);
 
 	strbuf_release(&base);
 	free(full);

gitgitgadget

On 6/28/2021 10:04 PM, Derrick Stolee via GitGitGadget wrote:
...

Since v6 was a mistake, here is the full range-diff of v5 versus v7:

 1:  5a2ed3d1d70 =  1:  2a4a7256304 sparse-index: skip indexes with unmerged entries
 2:  8aa41e74947 !  2:  f5bae86014d sparse-index: include EXTENDED flag when expanding

@@ Commit message

When creating a full index from a sparse one, we create cache entries for every blob within a given sparse directory entry. These are
- correctly marked with the CE_SKIP_WORKTREE flag, but they must also be
- marked with the CE_EXTENDED flag to ensure that the skip-worktree bit is
- correctly written to disk in the case that the index is not converted
- back down to a sparse-index.
+ correctly marked with the CE_SKIP_WORKTREE flag, but the CE_EXTENDED
+ flag is not included. The CE_EXTENDED flag would exist if we loaded a
+ full index from disk with these entries marked with CE_SKIP_WORKTREE, so
+ we can add the flag here to be consistent. This allows us to directly
+ compare the flags present in cache entries when testing the sparse-index
+ feature, but has no significance to its correctness in the user-facing
+ functionality.

3: b99371c7dd6 ! 3: d965669c766 t1092: replace incorrect 'echo' with 'cat'
@@ Commit message
t1092: replace incorrect 'echo' with 'cat'

This fixes the test data shape to be as expected, allowing rename
- detection to work properly now that the 'larger-conent' file actually
+ detection to work properly now that the 'larger-content' file actually
has meaningful lines.

4: f4dddac1859 ! 4: e10fa11cfdb t1092: expand repository data shape

    @@ Commit message
           one entry and are the first entry of a directory with multiple
           entries.
     
    +    * Add filenames adjacent to a sparse directory entry that sort before
    +      and after the trailing slash.
    +
         Later tests will take advantage of these shapes, but they also deepen
         the tests that already exist.
     
    @@ t/t1092-sparse-checkout-compatibility.sh: test_expect_success 'setup' '
     +		mkdir deep/deeper1/0/0 &&
     +		touch deep/deeper1/0/1 &&
     +		touch deep/deeper1/0/0/0 &&
    ++		>folder1- &&
    ++		>folder1.x &&
    ++		>folder10 &&
     +		cp -r deep/deeper1/0 folder1 &&
     +		cp -r deep/deeper1/0 folder2 &&
     +		echo >>folder1/0/0/0 &&
 5:  856346b72f7 =  5:  e94ffa07d46 t1092: add tests for status/add and sparse files
 6:  f3f6223e955 =  6:  a8dda933567 unpack-trees: preserve cache_bottom
 7:  45ae96adf28 !  7:  e52166f6e4c unpack-trees: compare sparse directories correctly

@@ Commit message
Within compare_entry(), it first calls do_compare_entry() to check the leading portion of the name. When the input path is a directory name, we could match exactly already. Thus, we should return 0 if we have an
- exact string match on a sparse directory entry.
+ exact string match on a sparse directory entry. The final check is a
+ length comparison between the strings.

@@ unpack-trees.c: static int compare_entry(const struct cache_entry *ce, const str
+ * works when the input name is a directory, since ce->name
+ * ends in a directory separator.
+ */
-+ if (S_ISSPARSEDIR(ce->ce_mode))
++ if (S_ISSPARSEDIR(ce->ce_mode) &&
++ ce->ce_namelen == traverse_path_len(info, tree_entry_len(n)) + 1)
+ return 0;
+
/*

 -:  ----------- >  8:  d04b62381b8 unpack-trees: rename unpack_nondirectories()
 8:  724194eef9f !  9:  237ccf4e43d unpack-trees: unpack sparse directory entries
    @@ Commit message
         might want to perform a merge operation on the entry, such as during
         'git checkout <commit>' which wants to replace a sparse tree entry with
         the tree for that path at the target commit. We extend the logic within
    -    unpack_nondirectories() to create a sparse-directory entry in this case,
    +    unpack_single_entry() to create a sparse-directory entry in this case,
         and then that is sent to call_unpack_fn().
     
         There are some subtleties in this process. For instance, we need to
         update find_cache_entry() to allow finding a sparse-directory entry that
    -    exactly matches a given path.
    +    exactly matches a given path. Use the new helper method
    +    sparse_dir_matches_path() for this. We also need to ignore conflict
    +    markers in the case that the entries correspond to directories and we
    +    already have a sparse directory entry.
     
         Signed-off-by: Derrick Stolee <[email protected]>
     
    @@ unpack-trees.c: static struct cache_entry *create_ce_entry(const struct traverse
     +	size_t alloc_len = is_sparse_directory ? len + 1 : len;
      	struct cache_entry *ce =
      		is_transient ?
    --		make_empty_transient_cache_entry(len) :
    +-		make_empty_transient_cache_entry(len, NULL) :
     -		make_empty_cache_entry(istate, len);
    -+		make_empty_transient_cache_entry(alloc_len) :
    ++		make_empty_transient_cache_entry(alloc_len, NULL) :
     +		make_empty_cache_entry(istate, alloc_len);
      
      	ce->ce_mode = create_ce_mode(n->mode);
    @@ unpack-trees.c: static struct cache_entry *create_ce_entry(const struct traverse
      
     +	if (is_sparse_directory) {
     +		ce->name[len] = '/';
    -+		ce->name[len + 1] = 0;
    ++		ce->name[len + 1] = '\0';
     +		ce->ce_namelen++;
     +		ce->ce_flags |= CE_SKIP_WORKTREE;
     +	}
    @@ unpack-trees.c: static struct cache_entry *create_ce_entry(const struct traverse
      	return ce;
      }
      
    -@@ unpack-trees.c: static int unpack_nondirectories(int n, unsigned long mask,
    - 				 unsigned long dirmask,
    - 				 struct cache_entry **src,
    - 				 const struct name_entry *names,
    --				 const struct traverse_info *info)
    -+				 const struct traverse_info *info,
    -+				 int sparse_directory)
    - {
    - 	int i;
    +@@ unpack-trees.c: static int unpack_single_entry(int n, unsigned long mask,
      	struct unpack_trees_options *o = info->data;
      	unsigned long conflicts = info->df_conflicts | dirmask;
      
    @@ unpack-trees.c: static int unpack_nondirectories(int n, unsigned long mask,
      	if (mask == dirmask && !src[0])
      		return 0;
      
    -+	/* no-op if our cache entry doesn't match the expectations. */
    -+	if (sparse_directory) {
    -+		if (src[0] && !S_ISSPARSEDIR(src[0]->ce_mode))
    -+			BUG("expected sparse directory entry");
    -+	} else if (src[0] && S_ISSPARSEDIR(src[0]->ce_mode)) {
    -+		return 0;
    -+	}
    ++	/*
    ++	 * When we have a sparse directory entry for src[0],
    ++	 * then this isn't necessarily a directory-file conflict.
    ++	 */
    ++	if (mask == dirmask && src[0] &&
    ++	    S_ISSPARSEDIR(src[0]->ce_mode))
    ++		conflicts = 0;
     +
      	/*
      	 * Ok, we've filled in up to any potential index entry in src[0],
      	 * now do the rest.
    -@@ unpack-trees.c: static int unpack_nondirectories(int n, unsigned long mask,
    +@@ unpack-trees.c: static int unpack_single_entry(int n, unsigned long mask,
      		 * not stored in the index.  otherwise construct the
      		 * cache entry from the index aware logic.
      		 */
     -		src[i + o->merge] = create_ce_entry(info, names + i, stage, &o->result, o->merge);
     +		src[i + o->merge] = create_ce_entry(info, names + i, stage,
     +						    &o->result, o->merge,
    -+						    sparse_directory);
    ++						    bit & dirmask);
      	}
      
      	if (o->merge) {
     @@ unpack-trees.c: static int find_cache_pos(struct traverse_info *info,
    + 	return -1;
    + }
    + 
    ++/*
    ++ * Given a sparse directory entry 'ce', compare ce->name to
    ++ * info->name + '/' + p->path + '/' if info->name is non-empty.
    ++ * Compare ce->name to p->path + '/' otherwise. Note that
    ++ * ce->name must end in a trailing '/' because it is a sparse
    ++ * directory entry.
    ++ */
    ++static int sparse_dir_matches_path(const struct cache_entry *ce,
    ++				   struct traverse_info *info,
    ++				   const struct name_entry *p)
    ++{
    ++	assert(S_ISSPARSEDIR(ce->ce_mode));
    ++	assert(ce->name[ce->ce_namelen - 1] == '/');
    ++
    ++	if (info->namelen)
    ++		return ce->ce_namelen == info->namelen + p->pathlen + 2 &&
    ++		       ce->name[info->namelen] == '/' &&
    ++		       !strncmp(ce->name, info->name, info->namelen) &&
    ++		       !strncmp(ce->name + info->namelen + 1, p->path, p->pathlen);
    ++	return ce->ce_namelen == p->pathlen + 1 &&
    ++	       !strncmp(ce->name, p->path, p->pathlen);
    ++}
    ++
      static struct cache_entry *find_cache_entry(struct traverse_info *info,
      					    const struct name_entry *p)
      {
    @@ unpack-trees.c: static int find_cache_pos(struct traverse_info *info,
     +	 * Check for a sparse-directory entry named "path/".
     +	 * Due to the input p->path not having a trailing
     +	 * slash, the negative 'pos' value overshoots the
    -+	 * expected position by one, hence "-2" here.
    ++	 * expected position by at least one, hence "-2" here.
     +	 */
     +	pos = -pos - 2;
     +
     +	if (pos < 0 || pos >= o->src_index->cache_nr)
    -+		return NULL;
    -+
    -+	ce = o->src_index->cache[pos];
    -+
    -+	if (!S_ISSPARSEDIR(ce->ce_mode))
      		return NULL;
     +
     +	/*
    -+	 * Compare ce->name to info->name + '/' + p->path + '/'
    -+	 * if info->name is non-empty. Compare ce->name to
    -+	 * p-.path + '/' otherwise.
    ++	 * We might have multiple entries between 'pos' and
    ++	 * the actual sparse-directory entry, so start walking
    ++	 * back until finding it or passing where it would be.
     +	 */
    -+	if (info->namelen) {
    -+		if (ce->ce_namelen == info->namelen + p->pathlen + 2 &&
    -+		    ce->name[info->namelen] == '/' &&
    -+		    !strncmp(ce->name, info->name, info->namelen) &&
    -+		    !strncmp(ce->name + info->namelen + 1, p->path, p->pathlen))
    ++	while (pos >= 0) {
    ++		ce = o->src_index->cache[pos];
    ++
    ++		if (strncmp(ce->name, p->path, p->pathlen))
    ++			return NULL;
    ++
    ++		if (S_ISSPARSEDIR(ce->ce_mode) &&
    ++		    sparse_dir_matches_path(ce, info, p))
     +			return ce;
    -+	} else if (ce->ce_namelen == p->pathlen + 1 &&
    -+		   !strncmp(ce->name, p->path, p->pathlen))
    -+		return ce;
    ++
    ++		pos--;
    ++	}
    ++
     +	return NULL;
      }
      
    @@ unpack-trees.c: static void debug_unpack_callback(int n,
     + * sparse-directory entry that matches the given name_entry
     + * from the tree walk at the given traverse_info.
     + */
    -+static int is_sparse_directory_entry(struct cache_entry *ce, struct name_entry *name, struct traverse_info *info)
    ++static int is_sparse_directory_entry(struct cache_entry *ce,
    ++				     struct name_entry *name,
    ++				     struct traverse_info *info)
     +{
    -+	size_t expected_len, name_start;
    -+
     +	if (!ce || !name || !S_ISSPARSEDIR(ce->ce_mode))
     +		return 0;
     +
    -+	if (info->namelen)
    -+		name_start = info->namelen + 1;
    -+	else
    -+		name_start = 0;
    -+	expected_len = name->pathlen + 1 + name_start;
    -+
    -+	if (ce->ce_namelen != expected_len ||
    -+	    strncmp(ce->name, info->name, info->namelen) ||
    -+	    strncmp(ce->name + name_start, name->path, name->pathlen))
    -+		return 0;
    -+
    -+	return 1;
    ++	return sparse_dir_matches_path(ce, info, name);
     +}
     +
      /*
       * 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
    -@@ unpack-trees.c: static int unpack_callback(int n, unsigned long mask, unsigned long dirmask, str
    - 		}
    - 	}
    - 
    --	if (unpack_nondirectories(n, mask, dirmask, src, names, info) < 0)
    -+	if (unpack_nondirectories(n, mask, dirmask, src, names, info, 0) < 0)
    - 		return -1;
    - 
    - 	if (o->merge && src[0]) {
     @@ unpack-trees.c: static int unpack_callback(int n, unsigned long mask, unsigned long dirmask, str
      			}
      		}
      
     -		if (traverse_trees_recursive(n, dirmask, mask & ~dirmask,
     -					     names, info) < 0)
    -+		if (is_sparse_directory_entry(src[0], names, info)) {
    -+			if (unpack_nondirectories(n, dirmask, mask & ~dirmask, src, names, info, 1) < 0)
    -+				return -1;
    -+		} else if (traverse_trees_recursive(n, dirmask, mask & ~dirmask,
    ++		if (!is_sparse_directory_entry(src[0], names, info) &&
    ++		    traverse_trees_recursive(n, dirmask, mask & ~dirmask,
     +						    names, info) < 0) {
      			return -1;
     +		}
 -:  ----------- > 10:  9f31c691af6 unpack-trees: handle dir/file conflict of sparse entries
 9:  b8ff179f43e ! 11:  2a43287c47e dir.c: accept a directory as part of cone-mode patterns
    @@ Commit message
         Signed-off-by: Derrick Stolee <[email protected]>
     
      ## dir.c ##
    +@@ dir.c: enum pattern_match_result path_matches_pattern_list(
    + 	struct path_pattern *pattern;
    + 	struct strbuf parent_pathname = STRBUF_INIT;
    + 	int result = NOT_MATCHED;
    +-	const char *slash_pos;
    ++	size_t slash_pos;
    + 
    + 	if (!pl->use_cone_patterns) {
    + 		pattern = last_matching_pattern_from_list(pathname, pathlen, basename,
     @@ dir.c: enum pattern_match_result path_matches_pattern_list(
      	strbuf_addch(&parent_pathname, '/');
      	strbuf_add(&parent_pathname, pathname, pathlen);
    @@ dir.c: enum pattern_match_result path_matches_pattern_list(
     +	 * use the file-base matching logic in an equivalent way.
     +	 */
     +	if (parent_pathname.len > 0 &&
    -+	    parent_pathname.buf[parent_pathname.len - 1] == '/')
    ++	    parent_pathname.buf[parent_pathname.len - 1] == '/') {
    ++		slash_pos = parent_pathname.len - 1;
     +		strbuf_add(&parent_pathname, "-", 1);
    ++	} else {
    ++		const char *slash_ptr = strrchr(parent_pathname.buf, '/');
    ++		slash_pos = slash_ptr ? slash_ptr - parent_pathname.buf : 0;
    ++	}
     +
      	if (hashmap_contains_path(&pl->recursive_hashmap,
      				  &parent_pathname)) {
      		result = MATCHED_RECURSIVE;
    + 		goto done;
    + 	}
    + 
    +-	slash_pos = strrchr(parent_pathname.buf, '/');
    +-
    +-	if (slash_pos == parent_pathname.buf) {
    ++	if (!slash_pos) {
    + 		/* include every file in root */
    + 		result = MATCHED;
    + 		goto done;
    + 	}
    + 
    +-	strbuf_setlen(&parent_pathname, slash_pos - parent_pathname.buf);
    ++	strbuf_setlen(&parent_pathname, slash_pos);
    + 
    + 	if (hashmap_contains_path(&pl->parent_hashmap, &parent_pathname)) {
    + 		result = MATCHED;
10:  b9b97e01129 ! 12:  f83aa08ff6b diff-lib: handle index diffs with sparse dirs
    @@ Commit message
         identical to before: the lack of a cache entry is the same with a sparse
         index.
     
    -    In the case where a tree is modified, we need to expand the tree
    -    recursively, and start comparing each contained entry as either an
    -    addition, deletion, or modification. This causes an interesting
    -    recursion that did not exist before.
    +    Use diff_tree_oid() appropriately to compute the diff.
     
         Signed-off-by: Derrick Stolee <[email protected]>
     
      ## diff-lib.c ##
    -@@ diff-lib.c: static int get_stat_data(const struct cache_entry *ce,
    - 	return 0;
    - }
    - 
    -+struct show_new_tree_context {
    -+	struct rev_info *revs;
    -+	unsigned added:1;
    -+};
    -+
    -+static int show_new_file_from_tree(const struct object_id *oid,
    -+				   struct strbuf *base, const char *path,
    -+				   unsigned int mode, void *context)
    -+{
    -+	struct show_new_tree_context *ctx = context;
    -+	struct cache_entry *new_file = make_transient_cache_entry(mode, oid, path, /* stage */ 0);
    -+
    -+	diff_index_show_file(ctx->revs, ctx->added ? "+" : "-", new_file, oid, !is_null_oid(oid), mode, 0);
    -+	discard_cache_entry(new_file);
    -+	return 0;
    -+}
    -+
    -+static void show_directory(struct rev_info *revs,
    -+			   const struct cache_entry *new_dir,
    -+			   int added)
    -+{
    -+	/*
    -+	 * new_dir is a sparse directory entry, so we want to collect all
    -+	 * of the new files within the tree. This requires recursively
    -+	 * expanding the trees.
    -+	 */
    -+	struct show_new_tree_context ctx = { revs, added };
    -+	struct repository *r = revs->repo;
    -+	struct strbuf base = STRBUF_INIT;
    -+	struct pathspec ps;
    -+	struct tree *tree = lookup_tree(r, &new_dir->oid);
    -+
    -+	memset(&ps, 0, sizeof(ps));
    -+	ps.recursive = 1;
    -+	ps.has_wildcard = 1;
    -+	ps.max_depth = -1;
    -+
    -+	strbuf_add(&base, new_dir->name, new_dir->ce_namelen);
    -+	read_tree_at(r, tree, &base, &ps,
    -+			show_new_file_from_tree, &ctx);
    -+}
    -+
    - static void show_new_file(struct rev_info *revs,
    - 			  const struct cache_entry *new_file,
    - 			  int cached, int match_missing)
     @@ diff-lib.c: static void show_new_file(struct rev_info *revs,
    - 	unsigned int mode;
      	unsigned dirty_submodule = 0;
    + 	struct index_state *istate = revs->diffopt.repo->index;
      
     +	if (new_file && S_ISSPARSEDIR(new_file->ce_mode)) {
    -+		show_directory(revs, new_file, /*added */ 1);
    ++		diff_tree_oid(NULL, &new_file->oid, new_file->name, &revs->diffopt);
     +		return;
     +	}
     +
      	/*
      	 * New file in the index: it might actually be different in
      	 * the working tree.
    -@@ diff-lib.c: static void show_new_file(struct rev_info *revs,
    - 	diff_index_show_file(revs, "+", new_file, oid, !is_null_oid(oid), mode, dirty_submodule);
    - }
    - 
    -+static int show_modified(struct rev_info *revs,
    -+			 const struct cache_entry *old_entry,
    -+			 const struct cache_entry *new_entry,
    -+			 int report_missing,
    -+			 int cached, int match_missing);
    -+
    -+static int compare_within_sparse_dir(int n, unsigned long mask,
    -+				     unsigned long dirmask, struct name_entry *entry,
    -+				     struct traverse_info *info)
    -+{
    -+	struct rev_info *revs = info->data;
    -+	struct object_id *oid0 = &entry[0].oid;
    -+	struct object_id *oid1 = &entry[1].oid;
    -+
    -+	if (oideq(oid0, oid1))
    -+		return mask;
    -+
    -+	/* Directory/file conflicts are handled earlier. */
    -+	if (S_ISDIR(entry[0].mode) && S_ISDIR(entry[1].mode)) {
    -+		struct tree_desc t[2];
    -+		void *buf[2];
    -+		struct traverse_info info_r = { NULL, };
    -+
    -+		info_r.name = xstrfmt("%s%s", info->traverse_path, entry[0].path);
    -+		info_r.namelen = strlen(info_r.name);
    -+		info_r.traverse_path = xstrfmt("%s/", info_r.name);
    -+		info_r.fn = compare_within_sparse_dir;
    -+		info_r.prev = info;
    -+		info_r.mode = entry[0].mode;
    -+		info_r.pathlen = entry[0].pathlen;
    -+		info_r.df_conflicts = 0;
    -+		info_r.data = revs;
    -+
    -+		buf[0] = fill_tree_descriptor(revs->repo, &t[0], oid0);
    -+		buf[1] = fill_tree_descriptor(revs->repo, &t[1], oid1);
    -+
    -+		traverse_trees(NULL, 2, t, &info_r);
    -+
    -+		free((char *)info_r.name);
    -+		free((char *)info_r.traverse_path);
    -+		free(buf[0]);
    -+		free(buf[1]);
    -+	} else {
    -+		char *old_path = NULL, *new_path = NULL;
    -+		struct cache_entry *old_entry = NULL, *new_entry = NULL;
    -+
    -+		if (entry[0].path) {
    -+			old_path = xstrfmt("%s%s", info->traverse_path, entry[0].path);
    -+			old_entry = make_transient_cache_entry(
    -+					entry[0].mode, &entry[0].oid,
    -+					old_path, /* stage */ 0);
    -+			old_entry->ce_flags |= CE_SKIP_WORKTREE;
    -+		}
    -+		if (entry[1].path) {
    -+			new_path = xstrfmt("%s%s", info->traverse_path, entry[1].path);
    -+			new_entry = make_transient_cache_entry(
    -+					entry[1].mode, &entry[1].oid,
    -+					new_path, /* stage */ 0);
    -+			new_entry->ce_flags |= CE_SKIP_WORKTREE;
    -+		}
    -+
    -+		if (entry[0].path && entry[1].path)
    -+			show_modified(revs, old_entry, new_entry, 0, 1, 0);
    -+		else if (entry[0].path)
    -+			diff_index_show_file(revs, revs->prefix,
    -+					     old_entry, &entry[0].oid,
    -+					     0, entry[0].mode, 0);
    -+		else if (entry[1].path)
    -+			show_new_file(revs, new_entry, 1, 0);
    -+
    -+		discard_cache_entry(old_entry);
    -+		discard_cache_entry(new_entry);
    -+		free(old_path);
    -+		free(new_path);
    -+	}
    -+
    -+	return mask;
    -+}
    -+
    -+static void show_modified_sparse_directory(struct rev_info *revs,
    -+			 const struct cache_entry *old_entry,
    -+			 const struct cache_entry *new_entry,
    -+			 int report_missing,
    -+			 int cached, int match_missing)
    -+{
    -+	struct tree_desc t[2];
    -+	void *buf[2];
    -+	struct traverse_info info = { NULL };
    -+	struct strbuf name = STRBUF_INIT;
    -+	struct strbuf parent_path = STRBUF_INIT;
    -+	char *last_dir_sep;
    -+
    -+	if (oideq(&old_entry->oid, &new_entry->oid))
    -+		return;
    -+
    -+	info.fn = compare_within_sparse_dir;
    -+	info.prev = &info;
    -+
    -+	strbuf_add(&name, new_entry->name, new_entry->ce_namelen - 1);
    -+	info.name = name.buf;
    -+	info.namelen = name.len;
    -+
    -+	strbuf_add(&parent_path, new_entry->name, new_entry->ce_namelen - 1);
    -+	if ((last_dir_sep = find_last_dir_sep(parent_path.buf)) > parent_path.buf)
    -+		strbuf_setlen(&parent_path, (last_dir_sep - parent_path.buf) - 1);
    -+	else
    -+		strbuf_setlen(&parent_path, 0);
    -+
    -+	info.pathlen = parent_path.len;
    -+
    -+	if (parent_path.len)
    -+		info.traverse_path = parent_path.buf;
    -+	else
    -+		info.traverse_path = "";
    -+
    -+	info.mode = new_entry->ce_mode;
    -+	info.df_conflicts = 0;
    -+	info.data = revs;
    -+
    -+	buf[0] = fill_tree_descriptor(revs->repo, &t[0], &old_entry->oid);
    -+	buf[1] = fill_tree_descriptor(revs->repo, &t[1], &new_entry->oid);
    -+
    -+	traverse_trees(NULL, 2, t, &info);
    -+
    -+	free(buf[0]);
    -+	free(buf[1]);
    -+	strbuf_release(&name);
    -+	strbuf_release(&parent_path);
    -+}
    -+
    - static int show_modified(struct rev_info *revs,
    - 			 const struct cache_entry *old_entry,
    - 			 const struct cache_entry *new_entry,
     @@ diff-lib.c: static int show_modified(struct rev_info *revs,
    - 	const struct object_id *oid;
      	unsigned dirty_submodule = 0;
    + 	struct index_state *istate = revs->diffopt.repo->index;
      
     +	/*
     +	 * If both are sparse directory entries, then expand the
    @@ diff-lib.c: static int show_modified(struct rev_info *revs,
     +	if (old_entry && new_entry &&
     +	    S_ISSPARSEDIR(old_entry->ce_mode) &&
     +	    S_ISSPARSEDIR(new_entry->ce_mode)) {
    -+		show_modified_sparse_directory(revs, old_entry, new_entry, report_missing, cached, match_missing);
    ++		diff_tree_oid(&old_entry->oid, &new_entry->oid, new_entry->name, &revs->diffopt);
     +		return 0;
     +	}
     +
    - 	if (get_stat_data(new_entry, &oid, &mode, cached, match_missing,
    + 	if (get_stat_data(istate, new_entry, &oid, &mode, cached, match_missing,
      			  &dirty_submodule, &revs->diffopt) < 0) {
      		if (report_missing)
11:  611b9f61fb2 = 13:  35063ffb8ed status: skip sparse-checkout percentage with sparse-index
12:  0c0a765dde8 = 14:  b4033a9bf36 status: use sparse-index throughout
13:  02f2c7b6398 ! 15:  717a3f49f97 wt-status: expand added sparse directory entries
    @@ t/t1092-sparse-checkout-compatibility.sh: test_expect_success 'sparse-index is n
     +	test_sparse_match git reset --mixed HEAD~1 &&
     +	test_sparse_match test-tool read-cache --table --expand &&
     +	test_sparse_match git status --porcelain=v2 &&
    -+	test_sparse_match git status --porcelain=v2 &&
     +
     +	# At this point, sparse-checkouts behave differently
     +	# from the full-checkout.
     +	test_sparse_match git checkout --orphan new-branch &&
     +	test_sparse_match test-tool read-cache --table --expand &&
    -+	test_sparse_match git status --porcelain=v2 &&
     +	test_sparse_match git status --porcelain=v2
     +'
     +
    @@ t/t1092-sparse-checkout-compatibility.sh: test_expect_success 'sparse-index is n
     +
     +	run_on_all touch deep/deeper1/x &&
     +	test_all_match git add . &&
    -+	test_all_match git status --porcelain=v2 &&
     +	test_all_match git status --porcelain=v2
     +'
     +
    @@ t/t1092-sparse-checkout-compatibility.sh: test_expect_success 'sparse-index is n
     
      ## wt-status.c ##
     @@ wt-status.c: static void wt_status_collect_changes_index(struct wt_status *s)
    - 	run_diff_index(&rev, 1);
    + 	clear_pathspec(&rev.prune_data);
      }
      
     +static int add_file_to_list(const struct object_id *oid,
    @@ wt-status.c: static void wt_status_collect_changes_index(struct wt_status *s)
     +	struct string_list_item *it;
     +	struct wt_status_change_data *d;
     +	struct wt_status *s = context;
    -+	char *full_name;
    ++	struct strbuf full_name = STRBUF_INIT;
     +
     +	if (S_ISDIR(mode))
     +		return READ_TREE_RECURSIVE;
     +
    -+	full_name = xstrfmt("%s%s", base->buf, path);
    -+	it = string_list_insert(&s->change, full_name);
    ++	strbuf_add(&full_name, base->buf, base->len);
    ++	strbuf_addstr(&full_name, path);
    ++	it = string_list_insert(&s->change, full_name.buf);
     +	d = it->util;
     +	if (!d) {
     +		CALLOC_ARRAY(d, 1);
    @@ wt-status.c: static void wt_status_collect_changes_index(struct wt_status *s)
     +	d->mode_index = mode;
     +	oidcpy(&d->oid_index, oid);
     +	s->committable = 1;
    ++	strbuf_release(&full_name);
     +	return 0;
     +}
     +
    @@ wt-status.c: static void wt_status_collect_changes_initial(struct wt_status *s)
     +			 * tree and marking them with DIFF_STATUS_ADDED.
     +			 */
     +			struct strbuf base = STRBUF_INIT;
    -+			struct pathspec ps;
    ++			struct pathspec ps = { 0 };
     +			struct tree *tree = lookup_tree(istate->repo, &ce->oid);
     +
    -+			memset(&ps, 0, sizeof(ps));
     +			ps.recursive = 1;
     +			ps.has_wildcard = 1;
     +			ps.max_depth = -1;
14:  46ca150c354 ! 16:  1d744848ee6 fsmonitor: integrate with sparse index
    @@ t/t7519-status-fsmonitor.sh: test_expect_success 'status succeeds after staging/
     +	GIT_TRACE2_EVENT="$(pwd)/trace2.txt" GIT_TRACE2_EVENT_NESTING=10 \
     +		git status --porcelain=v2 >actual &&
     +	test_region $1 index ensure_full_index trace2.txt &&
    ++	test_region fsm_hook query trace2.txt &&
     +	test_cmp expect actual &&
     +	rm trace2.txt &&
     +	git sparse-checkout disable

This is SUPER exciting. I've only read the cover letter, but it strongly suggests you've not only handled all my feedback in previous rounds, but got things pretty solidly nailed away. I'll try to make some time to go over it all soon.

...

Thanks for doing this; it was helpful.

You have indeed addressed nearly all my feedback in previous rounds, and I found few problems with all the new code in this round. Overall, this round is looking really good, though there are a couple things I called out in comments on individual patches that I'll summarize here:

Patch 9: a few minor suggestions for improving comments

Patch 10: the new code is never triggered and probably should either be dropped or made part of a later series if the later series needs it. Also, although it doesn't necessarily need to hold up this series, I found a bug affecting sparse-checkouts with or without sparse-index while trying to understand this patch.

Patch 12: the code was slightly confusing to me, but I found that there seems to be an invariant it is based upon. Adding an assert with a comment or just a comment about this invariant might help make the code more readable.

Patch 15: since the new tests in t1092 are written to compare sparse-checkout and sparse-index, it seems we should investigate a bug where the testsuite commands we invoke are giving incorrect behavior in both sparse-checkout and sparse-index.

This summary is nice. I will try to do a similar thing myself in the future.

Done.

I checked and this patch is not necessary until the next series, so I will move it to that one.

The assert() plus a better comment makes this patch cleaner.

I have made a note in an internal tracker to follow-up on this along with some other behavior things that currently exist in sparse-checkout as they should be pursued in a separate series.

I'm not ignoring your comments, but I would like to keep these patches that change the underlying data structure from being conflated with behavior changes. The fact that I am discovering (and documenting in tests) the changes is only highlighting that they already exist.

Thanks,
-Stolee

This is the first "payoff" series in the sparse-index work. It makes 'git status' very fast when a sparse-index is enabled on a repository with cone-mode sparse-checkout (and a small populated set).

This is based on ds/sparse-index-protections AND mt/add-rm-sparse-checkout. The latter branch is needed because it changes the behavior of 'git add' around sparse entries, which changes the expectations of a test added in patch 1.

The approach here is to audit the places where ensure_full_index() pops up while doing normal commands with pathspecs within the sparse-checkout definition. Each of these are checked and tested. In the end, the sparse-index is integrated with these features:

* git status
* FS Monitor index extension.

The performance tests in p2000-sparse-operations.sh improve by 95% or more, even when compared with the full-index cases, not just the sparse-index cases that previously had extra overhead.

Hopefully this is the first example of how ds/sparse-index-protections has done the basic work to do these conversions safely, making them look easier than they seemed when starting this adventure.

Thanks, -Stolee

Update in V8
============

* The directory/file conflict patch is removed and delayed to the next series where it will be required. (It will also be improved in that series.)

* Some comments have been improved, including a new assert() that helps document the situation.

Derrick Stolee (15):
sparse-index: skip indexes with unmerged entries
sparse-index: include EXTENDED flag when expanding
t1092: replace incorrect 'echo' with 'cat'
t1092: expand repository data shape
t1092: add tests for status/add and sparse files
unpack-trees: preserve cache_bottom
unpack-trees: compare sparse directories correctly
unpack-trees: rename unpack_nondirectories()
unpack-trees: unpack sparse directory entries dir.c: accept a directory as part of cone-mode patterns
diff-lib: handle index diffs with sparse dirs
status: skip sparse-checkout percentage with sparse-index
status: use sparse-index throughout
wt-status: expand added sparse directory entries
fsmonitor: integrate with sparse index

 builtin/commit.c                         |   3 +
 diff-lib.c                               |  19 +++
 dir.c                                    |  24 +++-
 read-cache.c                             |  10 +-
 sparse-index.c                           |  27 +++-
 t/t1092-sparse-checkout-compatibility.sh | 158 ++++++++++++++++++++++-
 t/t7519-status-fsmonitor.sh              |  49 +++++++
 unpack-trees.c                           | 142 +++++++++++++++++---
 wt-status.c                              |  65 +++++++++-
 wt-status.h                              |   1 +
 10 files changed, 464 insertions(+), 34 deletions(-)

base-commit: d486ca60a51c9cb1fe068803c3f540724e95e83a
Published-As: https://github.com/gitgitgadget/git/releases/tag/pr-932%2Fderrickstolee%2Fsparse-index%2Fstatus-and-add-v8
Fetch-It-Via: git fetch https://github.com/gitgitgadget/git pr-932/derrickstolee/sparse-index/status-and-add-v8
Pull-Request: https://github.com/gitgitgadget/git/pull/932

Range-diff vs v7:

  1:  2a4a7256304 =  1:  1815c148e8c sparse-index: skip indexes with unmerged entries
  2:  f5bae86014d =  2:  7bcde075d8d sparse-index: include EXTENDED flag when expanding
  3:  d965669c766 =  3:  05981e30b97 t1092: replace incorrect 'echo' with 'cat'
  4:  e10fa11cfdb !  4:  d38b66e9ee4 t1092: expand repository data shape
     @@ t/t1092-sparse-checkout-compatibility.sh: test_expect_success 'diff --staged' '
       	for branch in rename-out-to-out rename-out-to-in rename-in-to-out
       	do
       		test_all_match git checkout rename-base &&
     - 		test_all_match git checkout $branch -- .&&
     + 		test_all_match git checkout $branch -- . &&
      +		test_all_match git status --porcelain=v2 &&
      +		test_all_match git diff --staged --no-renames &&
      +		test_all_match git diff --staged --find-renames || return 1
  5:  e94ffa07d46 =  5:  95ddd3abe4e t1092: add tests for status/add and sparse files
  6:  a8dda933567 =  6:  b182b456613 unpack-trees: preserve cache_bottom
  7:  e52166f6e4c =  7:  988ddce4d45 unpack-trees: compare sparse directories correctly
  8:  d04b62381b8 =  8:  d67ad048b08 unpack-trees: rename unpack_nondirectories()
  9:  237ccf4e43d !  9:  c0b0b58584c unpack-trees: unpack sparse directory entries
     @@ unpack-trees.c: static int find_cache_pos(struct traverse_info *info,
      +	 * Check for a sparse-directory entry named "path/".
      +	 * Due to the input p->path not having a trailing
      +	 * slash, the negative 'pos' value overshoots the
     -+	 * expected position by at least one, hence "-2" here.
     ++	 * expected position, hence "-2" instead of "-1".
      +	 */
      +	pos = -pos - 2;
      +
     @@ unpack-trees.c: static int find_cache_pos(struct traverse_info *info,
       		return NULL;
      +
      +	/*
     -+	 * We might have multiple entries between 'pos' and
     -+	 * the actual sparse-directory entry, so start walking
     -+	 * back until finding it or passing where it would be.
     ++	 * Due to lexicographic sorting and sparse directory
     ++	 * entried ending with a trailing slash, our path as a
     ++	 * sparse directory (e.g "subdir/") and	our path as a
     ++	 * file (e.g. "subdir") might be separated by other
     ++	 * paths (e.g. "subdir-").
      +	 */
      +	while (pos >= 0) {
      +		ce = o->src_index->cache[pos];
 10:  9f31c691af6 <  -:  ----------- unpack-trees: handle dir/file conflict of sparse entries
 11:  2a43287c47e = 10:  76c7528f78f dir.c: accept a directory as part of cone-mode patterns
 12:  f83aa08ff6b ! 11:  d875a7f8585 diff-lib: handle index diffs with sparse dirs
     @@ diff-lib.c: static int show_modified(struct rev_info *revs,
       	unsigned dirty_submodule = 0;
       	struct index_state *istate = revs->diffopt.repo->index;
       
     ++	assert(S_ISSPARSEDIR(old_entry->ce_mode) ==
     ++	       S_ISSPARSEDIR(new_entry->ce_mode));
     ++
      +	/*
      +	 * If both are sparse directory entries, then expand the
     -+	 * modifications to the file level.
     ++	 * modifications to the file level. If only one was a sparse
     ++	 * directory, then they appear as an add and delete instead of
     ++	 * a modification.
      +	 */
     -+	if (old_entry && new_entry &&
     -+	    S_ISSPARSEDIR(old_entry->ce_mode) &&
     -+	    S_ISSPARSEDIR(new_entry->ce_mode)) {
     ++	if (S_ISSPARSEDIR(new_entry->ce_mode)) {
      +		diff_tree_oid(&old_entry->oid, &new_entry->oid, new_entry->name, &revs->diffopt);
      +		return 0;
      +	}
 13:  35063ffb8ed = 12:  2b72cc2d985 status: skip sparse-checkout percentage with sparse-index
 14:  b4033a9bf36 = 13:  1c1feef3733 status: use sparse-index throughout
 15:  717a3f49f97 = 14:  dada1b91bdc wt-status: expand added sparse directory entries
 16:  1d744848ee6 = 15:  bdc771cf373 fsmonitor: integrate with sparse index

gitgitgadget

From: Derrick Stolee <[email protected]>

The sparse-index format is designed to be compatible with merge conflicts, even those outside the sparse-checkout definition. The reason is that when converting a full index to a sparse one, a cache entry with nonzero stage will not be collapsed into a sparse directory entry.

However, this behavior was not tested, and a different behavior within convert_to_sparse() fails in this scenario. Specifically, cache_tree_update() will fail when unmerged entries exist. convert_to_sparse_rec() uses the cache-tree data to recursively walk the tree structure, but also to compute the OIDs used in the sparse-directory entries.

Add an index scan to convert_to_sparse() that will detect if these merge conflict entries exist and skip the conversion before trying to update the cache-tree. This is marked as NEEDSWORK because this can be removed with a suitable update to cache_tree_update() or a similar method that can construct a cache-tree with invalid nodes, but still allow creating the nodes necessary for creating sparse directory entries.

It is possible that in the future we will not need to make such an update, since if we do not expand a sparse-index into a full one, this conversion does not need to happen. Thus, this can be deferred until the merge machinery is made to integrate with the sparse-index.

---
 sparse-index.c                           | 18 ++++++++++++++++++
 t/t1092-sparse-checkout-compatibility.sh | 22 ++++++++++++++++++++++
 2 files changed, 40 insertions(+)

index affc4048f27..2c695930275 100644
@@ -116,6 +116,17 @@ int set_sparse_index_config(struct repository *repo, int enable)
 	return res;
 }
 
+static int index_has_unmerged_entries(struct index_state *istate)
+{
+	int i;
+	for (i = 0; i < istate->cache_nr; i++) {
+		if (ce_stage(istate->cache[i]))
+			return 1;
+	}
+
+	return 0;
+}
+
 int convert_to_sparse(struct index_state *istate)
 {
 	int test_env;

@@ -152,6 +163,13 @@ int convert_to_sparse(struct index_state *istate)
 		return -1;
 	}
 
+	/*
+	 * NEEDSWORK: If we have unmerged entries, then stay full.
+	 * Unmerged entries prevent the cache-tree extension from working.
+	 */
+	if (index_has_unmerged_entries(istate))
+		return 0;
+
 	if (cache_tree_update(istate, 0)) {
 		warning(_("unable to update cache-tree, staying full"));
 		return -1;

index d028b73eba1..b8617ceef71 100755
@@ -352,6 +352,28 @@ test_expect_success 'merge with outside renames' '
 	done
 '
 
+# Sparse-index fails to convert the index in the
+# final 'git cherry-pick' command.
+test_expect_success 'cherry-pick with conflicts' '
+	init_repos &&
+
+	write_script edit-conflict <<-\EOF &&
+	echo $1 >conflict
+	EOF
+
+	test_all_match git checkout -b to-cherry-pick &&
+	run_on_all ../edit-conflict ABC &&
+	test_all_match git add conflict &&
+	test_all_match git commit -m "conflict to pick" &&
+
+	test_all_match git checkout -B base HEAD~1 &&
+	run_on_all ../edit-conflict DEF &&
+	test_all_match git add conflict &&
+	test_all_match git commit -m "conflict in base" &&
+
+	test_all_match test_must_fail git cherry-pick to-cherry-pick
+'
+
 test_expect_success 'clean' '
 	init_repos &&
 

gitgitgadget

From: Derrick Stolee <[email protected]>

When creating a full index from a sparse one, we create cache entries for every blob within a given sparse directory entry. These are correctly marked with the CE_SKIP_WORKTREE flag, but the CE_EXTENDED flag is not included. The CE_EXTENDED flag would exist if we loaded a full index from disk with these entries marked with CE_SKIP_WORKTREE, so we can add the flag here to be consistent. This allows us to directly compare the flags present in cache entries when testing the sparse-index feature, but has no significance to its correctness in the user-facing functionality.

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

index 2c695930275..ef53bd2198b 100644
@@ -213,7 +213,7 @@ static int add_path_to_index(const struct object_id *oid,
 	strbuf_addstr(base, path);
 
 	ce = make_cache_entry(istate, mode, oid, base->buf, 0, 0);
-	ce->ce_flags |= CE_SKIP_WORKTREE;
+	ce->ce_flags |= CE_SKIP_WORKTREE | CE_EXTENDED;
 	set_index_entry(istate, istate->cache_nr++, ce);
 
 	strbuf_setlen(base, len);

gitgitgadget

From: Derrick Stolee <[email protected]>

This fixes the test data shape to be as expected, allowing rename detection to work properly now that the 'larger-content' file actually has meaningful lines.

---
 t/t1092-sparse-checkout-compatibility.sh | 2 +-
 1 file changed, 1 insertion(+), 1 deletion(-)

index b8617ceef71..87f1014a1c9 100755
@@ -40,7 +40,7 @@ test_expect_success 'setup' '
 		done &&
 
 		git checkout -b rename-base base &&
-		echo >folder1/larger-content <<-\EOF &&
+		cat >folder1/larger-content <<-\EOF &&
 		matching
 		lines
 		help

gitgitgadget

What's the connection with s/echo/cat/ ?

An old man doll... just what I always wanted! - Clara

From: Derrick Stolee <[email protected]>

As more features integrate with the sparse-index feature, more and more special cases arise that require different data shapes within the tree structure of the repository in order to demonstrate those cases.

Add several interesting special cases all at once instead of sprinkling them across several commits. The interesting cases being added here are:

* Add sparse-directory entries on both sides of directories within the sparse-checkout definition.

* Add directories outside the sparse-checkout definition who have only one entry and are the first entry of a directory with multiple entries.

* Add filenames adjacent to a sparse directory entry that sort before and after the trailing slash.

Later tests will take advantage of these shapes, but they also deepen the tests that already exist.

---
 t/t1092-sparse-checkout-compatibility.sh | 42 ++++++++++++++++++++++--
 1 file changed, 40 insertions(+), 2 deletions(-)

index 87f1014a1c9..0e71a623619 100755
@@ -17,7 +17,7 @@ test_expect_success 'setup' '
 		echo "after folder1" >g &&
 		echo "after x" >z &&
 		mkdir folder1 folder2 deep x &&
-		mkdir deep/deeper1 deep/deeper2 &&
+		mkdir deep/deeper1 deep/deeper2 deep/before deep/later &&
 		mkdir deep/deeper1/deepest &&
 		echo "after deeper1" >deep/e &&
 		echo "after deepest" >deep/deeper1/e &&

@@ -25,10 +25,23 @@ test_expect_success 'setup' '
 		cp a folder2 &&
 		cp a x &&
 		cp a deep &&
+		cp a deep/before &&
 		cp a deep/deeper1 &&
 		cp a deep/deeper2 &&
+		cp a deep/later &&
 		cp a deep/deeper1/deepest &&
 		cp -r deep/deeper1/deepest deep/deeper2 &&
+		mkdir deep/deeper1/0 &&
+		mkdir deep/deeper1/0/0 &&
+		touch deep/deeper1/0/1 &&
+		touch deep/deeper1/0/0/0 &&
+		>folder1- &&
+		>folder1.x &&
+		>folder10 &&
+		cp -r deep/deeper1/0 folder1 &&
+		cp -r deep/deeper1/0 folder2 &&
+		echo >>folder1/0/0/0 &&
+		echo >>folder2/0/1 &&
 		git add . &&
 		git commit -m "initial commit" &&
 		git checkout -b base &&

@@ -56,11 +69,17 @@ test_expect_success 'setup' '
 		mv folder1/a folder2/b &&
 		mv folder1/larger-content folder2/edited-content &&
 		echo >>folder2/edited-content &&
+		echo >>folder2/0/1 &&
+		echo stuff >>deep/deeper1/a &&
 		git add . &&
 		git commit -m "rename folder1/... to folder2/..." &&
 
 		git checkout -b rename-out-to-in rename-base &&
 		mv folder1/a deep/deeper1/b &&
+		echo more stuff >>deep/deeper1/a &&
+		rm folder2/0/1 &&
+		mkdir folder2/0/1 &&
+		echo >>folder2/0/1/1 &&
 		mv folder1/larger-content deep/deeper1/edited-content &&
 		echo >>deep/deeper1/edited-content &&
 		git add . &&

@@ -68,6 +87,9 @@ test_expect_success 'setup' '
 
 		git checkout -b rename-in-to-out rename-base &&
 		mv deep/deeper1/a folder1/b &&
+		echo >>folder2/0/1 &&
+		rm -rf folder1/0/0 &&
+		echo >>folder1/0/0 &&
 		mv deep/deeper1/larger-content folder1/edited-content &&
 		echo >>folder1/edited-content &&
 		git add . &&

@@ -262,13 +284,29 @@ test_expect_success 'diff --staged' '
 	test_all_match git diff --staged
 '
 
-test_expect_success 'diff with renames' '
+test_expect_success 'diff with renames and conflicts' '
 	init_repos &&
 
 	for branch in rename-out-to-out rename-out-to-in rename-in-to-out
 	do
 		test_all_match git checkout rename-base &&
 		test_all_match git checkout $branch -- . &&
+		test_all_match git status --porcelain=v2 &&
+		test_all_match git diff --staged --no-renames &&
+		test_all_match git diff --staged --find-renames || return 1
+	done
+'
+
+test_expect_success 'diff with directory/file conflicts' '
+	init_repos &&
+
+	for branch in rename-out-to-out rename-out-to-in rename-in-to-out
+	do
+		git -C full-checkout reset --hard &&
+		test_sparse_match git reset --hard &&
+		test_all_match git checkout $branch &&
+		test_all_match git checkout rename-base -- . &&
+		test_all_match git status --porcelain=v2 &&
 		test_all_match git diff --staged --no-renames &&
 		test_all_match git diff --staged --find-renames || return 1
 	done

gitgitgadget

From: Derrick Stolee <[email protected]>

Before moving to update 'git status' and 'git add' to work with sparse indexes, add an explicit test that ensures the sparse-index works the same as a normal sparse-checkout when the worktree contains directories and files outside of the sparse cone.

Specifically, 'folder1/a' is a file in our test repo, but 'folder1' is not in the sparse cone. When 'folder1/a' is modified, the file is not shown as modified and adding it will fail. This is new behavior as of a20f704 (add: warn when asked to update SKIP_WORKTREE entries, 2021-04-08). Before that change, these adds would be silently ignored.

Untracked files are fine: adding new files both with 'git add .' and 'git add folder1/' works just as in a full checkout. This may not be entirely desirable, but we are not intending to change behavior at the moment, only document it. A future change could alter the behavior to be more sensible, and this test could be modified to satisfy the new expected behavior.

---
 t/t1092-sparse-checkout-compatibility.sh | 38 ++++++++++++++++++++++++
 1 file changed, 38 insertions(+)

index 0e71a623619..2269f44e033 100755
@@ -254,6 +254,44 @@ test_expect_success 'add, commit, checkout' '
 	test_all_match git checkout -
 '
 
+test_expect_success 'status/add: outside sparse cone' '
+	init_repos &&
+
+	# adding a "missing" file outside the cone should fail
+	test_sparse_match test_must_fail git add folder1/a &&
+
+	# folder1 is at HEAD, but outside the sparse cone
+	run_on_sparse mkdir folder1 &&
+	cp initial-repo/folder1/a sparse-checkout/folder1/a &&
+	cp initial-repo/folder1/a sparse-index/folder1/a &&
+
+	test_sparse_match git status &&
+
+	write_script edit-contents <<-\EOF &&
+	echo text >>$1
+	EOF
+	run_on_sparse ../edit-contents folder1/a &&
+	run_on_all ../edit-contents folder1/new &&
+
+	test_sparse_match git status --porcelain=v2 &&
+
+	# This "git add folder1/a" fails with a warning
+	# in the sparse repos, differing from the full
+	# repo. This is intentional.
+	test_sparse_match test_must_fail git add folder1/a &&
+	test_sparse_match test_must_fail git add --refresh folder1/a &&
+	test_all_match git status --porcelain=v2 &&
+
+	test_all_match git add . &&
+	test_all_match git status --porcelain=v2 &&
+	test_all_match git commit -m folder1/new &&
+
+	run_on_all ../edit-contents folder1/newer &&
+	test_all_match git add folder1/ &&
+	test_all_match git status --porcelain=v2 &&
+	test_all_match git commit -m folder1/newer
+'
+
 test_expect_success 'checkout and reset --hard' '
 	init_repos &&
 

gitgitgadget

From: Derrick Stolee <[email protected]>

The cache_bottom member of 'struct unpack_trees_options' is used to track the range of index entries corresponding to a node of the cache tree. While recursing with traverse_by_cache_tree(), this value is preserved on the call stack using a local and then restored as that method returns.

The mark_ce_used() method normally modifies the cache_bottom member when it refers to the marked cache entry. However, sparse directory entries are stored as nodes in the cache-tree data structure as of 2de37c53 (cache-tree: integrate with sparse directory entries, 2021-03-30). Thus, the cache_bottom will be modified as the cache-tree walk advances. Do not update it as well within mark_ce_used().

---
 unpack-trees.c | 7 +++++++
 1 file changed, 7 insertions(+)

index f88a69f8e71..87c1ed204c8 100644
@@ -600,6 +600,13 @@ static void mark_ce_used(struct cache_entry *ce, struct unpack_trees_options *o)
 {
 	ce->ce_flags |= CE_UNPACKED;
 
+	/*
+	 * If this is a sparse directory, don't advance cache_bottom.
+	 * That will be advanced later using the cache-tree data.
+	 */
+	if (S_ISSPARSEDIR(ce->ce_mode))
+		return;
+
 	if (o->cache_bottom < o->src_index->cache_nr &&
 	    o->src_index->cache[o->cache_bottom] == ce) {
 		int bottom = o->cache_bottom;

gitgitgadget

From: Derrick Stolee <[email protected]>

As we further integrate the sparse-index into unpack-trees, we need to ensure that we compare sparse directory entries correctly with other entries. This affects searching for an exact path as well as sorting index entries.

Sparse directory entries contain the trailing directory separator. This is important for the sorting, in particular. Thus, within do_compare_entry() we stop using S_IFREG in all cases, since sparse directories should use S_IFDIR to indicate that the comparison should treat the entry name as a dirctory.

Within compare_entry(), it first calls do_compare_entry() to check the leading portion of the name. When the input path is a directory name, we could match exactly already. Thus, we should return 0 if we have an exact string match on a sparse directory entry. The final check is a length comparison between the strings.

---
 unpack-trees.c | 14 +++++++++++++-
 1 file changed, 13 insertions(+), 1 deletion(-)

index 87c1ed204c8..b113cc750f2 100644
@@ -983,6 +983,7 @@ static int do_compare_entry(const struct cache_entry *ce,
 	int pathlen, ce_len;
 	const char *ce_name;
 	int cmp;
+	unsigned ce_mode;
 
 	/*
 	 * If we have not precomputed the traverse path, it is quicker

@@ -1005,7 +1006,8 @@ static int do_compare_entry(const struct cache_entry *ce,
 	ce_len -= pathlen;
 	ce_name = ce->name + pathlen;
 
-	return df_name_compare(ce_name, ce_len, S_IFREG, name, namelen, mode);
+	ce_mode = S_ISSPARSEDIR(ce->ce_mode) ? S_IFDIR : S_IFREG;
+	return df_name_compare(ce_name, ce_len, ce_mode, name, namelen, mode);
 }
 
 static int compare_entry(const struct cache_entry *ce, const struct traverse_info *info, const struct name_entry *n)

@@ -1014,6 +1016,16 @@ static int compare_entry(const struct cache_entry *ce, const struct traverse_inf
 	if (cmp)
 		return cmp;
 
+	/*
+	 * At this point, we know that we have a prefix match. If ce
+	 * is a sparse directory, then allow an exact match. This only
+	 * works when the input name is a directory, since ce->name
+	 * ends in a directory separator.
+	 */
+	if (S_ISSPARSEDIR(ce->ce_mode) &&
+	    ce->ce_namelen == traverse_path_len(info, tree_entry_len(n)) + 1)
+		return 0;
+
 	/*
 	 * Even if the beginning compared identically, the ce should
 	 * compare as bigger than a directory leading up to it!

gitgitgadget

From: Derrick Stolee <[email protected]>

In the next change, we will use this method to unpack a sparse directory entry, so change the name to unpack_single_entry() so these entries apply. The new name reflects that we will not recurse into trees in order to resolve the conflicts.

---
 unpack-trees.c | 14 +++++++-------
 1 file changed, 7 insertions(+), 7 deletions(-)

index b113cc750f2..d26386ce8b2 100644
@@ -804,7 +804,7 @@ static int traverse_by_cache_tree(int pos, int nr_entries, int nr_names,
 		BUG("We need cache-tree to do this optimization");
 
 	/*
-	 * Do what unpack_callback() and unpack_nondirectories() normally
+	 * Do what unpack_callback() and unpack_single_entry() normally
 	 * do. But we walk all paths in an iterative loop instead.
 	 *
 	 * D/F conflicts and higher stage entries are not a concern

@@ -1075,11 +1075,11 @@ static struct cache_entry *create_ce_entry(const struct traverse_info *info,
  * without actually calling it. If you change the logic here you may need to
  * check and change there as well.
  */
-static int unpack_nondirectories(int n, unsigned long mask,
-				 unsigned long dirmask,
-				 struct cache_entry **src,
-				 const struct name_entry *names,
-				 const struct traverse_info *info)
+static int unpack_single_entry(int n, unsigned long mask,
+			       unsigned long dirmask,
+			       struct cache_entry **src,
+			       const struct name_entry *names,
+			       const struct traverse_info *info)
 {
 	int i;
 	struct unpack_trees_options *o = info->data;

@@ -1322,7 +1322,7 @@ static int unpack_callback(int n, unsigned long mask, unsigned long dirmask, str
 		}
 	}
 
-	if (unpack_nondirectories(n, mask, dirmask, src, names, info) < 0)
+	if (unpack_single_entry(n, mask, dirmask, src, names, info) < 0)
 		return -1;
 
 	if (o->merge && src[0]) {

gitgitgadget

From: Derrick Stolee <[email protected]>

During unpack_callback(), index entries are compared against tree entries. These are matched according to names and types. One goal is to decide if we should recurse into subtrees or simply operate on one index entry.

In the case of a sparse-directory entry, we do not want to recurse into that subtree and instead simply compare the trees. In some cases, we might want to perform a merge operation on the entry, such as during 'git checkout <commit>' which wants to replace a sparse tree entry with the tree for that path at the target commit. We extend the logic within unpack_single_entry() to create a sparse-directory entry in this case, and then that is sent to call_unpack_fn().

There are some subtleties in this process. For instance, we need to update find_cache_entry() to allow finding a sparse-directory entry that exactly matches a given path. Use the new helper method sparse_dir_matches_path() for this. We also need to ignore conflict markers in the case that the entries correspond to directories and we already have a sparse directory entry.

---
 unpack-trees.c | 107 +++++++++++++++++++++++++++++++++++++++++++++----
 1 file changed, 99 insertions(+), 8 deletions(-)

index d26386ce8b2..62ccd5a0ff6 100644
@@ -1052,13 +1052,15 @@ static struct cache_entry *create_ce_entry(const struct traverse_info *info,
 	const struct name_entry *n,
 	int stage,
 	struct index_state *istate,
-	int is_transient)
+	int is_transient,
+	int is_sparse_directory)
 {
 	size_t len = traverse_path_len(info, tree_entry_len(n));
+	size_t alloc_len = is_sparse_directory ? len + 1 : len;
 	struct cache_entry *ce =
 		is_transient ?
-		make_empty_transient_cache_entry(len, NULL) :
-		make_empty_cache_entry(istate, len);
+		make_empty_transient_cache_entry(alloc_len, NULL) :
+		make_empty_cache_entry(istate, alloc_len);
 
 	ce->ce_mode = create_ce_mode(n->mode);
 	ce->ce_flags = create_ce_flags(stage);

@@ -1067,6 +1069,13 @@ static struct cache_entry *create_ce_entry(const struct traverse_info *info,
 	/* len+1 because the cache_entry allocates space for NUL */
 	make_traverse_path(ce->name, len + 1, info, n->path, n->pathlen);
 
+	if (is_sparse_directory) {
+		ce->name[len] = '/';
+		ce->name[len + 1] = '\0';
+		ce->ce_namelen++;
+		ce->ce_flags |= CE_SKIP_WORKTREE;
+	}
+
 	return ce;
 }
 

@@ -1085,10 +1094,17 @@ static int unpack_single_entry(int n, unsigned long mask,
 	struct unpack_trees_options *o = info->data;
 	unsigned long conflicts = info->df_conflicts | dirmask;
 
-	/* Do we have *only* directories? Nothing to do */
 	if (mask == dirmask && !src[0])
 		return 0;
 
+	/*
+	 * When we have a sparse directory entry for src[0],
+	 * then this isn't necessarily a directory-file conflict.
+	 */
+	if (mask == dirmask && src[0] &&
+	    S_ISSPARSEDIR(src[0]->ce_mode))
+		conflicts = 0;
+
 	/*
 	 * Ok, we've filled in up to any potential index entry in src[0],
 	 * now do the rest.

@@ -1118,7 +1134,9 @@ static int unpack_single_entry(int n, unsigned long mask,
 		 * not stored in the index.  otherwise construct the
 		 * cache entry from the index aware logic.
 		 */
-		src[i + o->merge] = create_ce_entry(info, names + i, stage, &o->result, o->merge);
+		src[i + o->merge] = create_ce_entry(info, names + i, stage,
+						    &o->result, o->merge,
+						    bit & dirmask);
 	}
 
 	if (o->merge) {

@@ -1222,16 +1240,71 @@ static int find_cache_pos(struct traverse_info *info,
 	return -1;
 }
 
+/*
+ * Given a sparse directory entry 'ce', compare ce->name to
+ * info->name + '/' + p->path + '/' if info->name is non-empty.
+ * Compare ce->name to p->path + '/' otherwise. Note that
+ * ce->name must end in a trailing '/' because it is a sparse
+ * directory entry.
+ */
+static int sparse_dir_matches_path(const struct cache_entry *ce,
+				   struct traverse_info *info,
+				   const struct name_entry *p)
+{
+	assert(S_ISSPARSEDIR(ce->ce_mode));
+	assert(ce->name[ce->ce_namelen - 1] == '/');
+
+	if (info->namelen)
+		return ce->ce_namelen == info->namelen + p->pathlen + 2 &&
+		       ce->name[info->namelen] == '/' &&
+		       !strncmp(ce->name, info->name, info->namelen) &&
+		       !strncmp(ce->name + info->namelen + 1, p->path, p->pathlen);
+	return ce->ce_namelen == p->pathlen + 1 &&
+	       !strncmp(ce->name, p->path, p->pathlen);
+}
+
 static struct cache_entry *find_cache_entry(struct traverse_info *info,
 					    const struct name_entry *p)
 {
+	struct cache_entry *ce;
 	int pos = find_cache_pos(info, p->path, p->pathlen);
 	struct unpack_trees_options *o = info->data;
 
 	if (0 <= pos)
 		return o->src_index->cache[pos];
-	else
+
+	/*
+	 * Check for a sparse-directory entry named "path/".
+	 * Due to the input p->path not having a trailing
+	 * slash, the negative 'pos' value overshoots the
+	 * expected position, hence "-2" instead of "-1".
+	 */
+	pos = -pos - 2;
+
+	if (pos < 0 || pos >= o->src_index->cache_nr)
 		return NULL;
+
+	/*
+	 * Due to lexicographic sorting and sparse directory
+	 * entried ending with a trailing slash, our path as a
+	 * sparse directory (e.g "subdir/") and	our path as a
+	 * file (e.g. "subdir") might be separated by other
+	 * paths (e.g. "subdir-").
+	 */
+	while (pos >= 0) {
+		ce = o->src_index->cache[pos];
+
+		if (strncmp(ce->name, p->path, p->pathlen))
+			return NULL;
+
+		if (S_ISSPARSEDIR(ce->ce_mode) &&
+		    sparse_dir_matches_path(ce, info, p))
+			return ce;
+
+		pos--;
+	}
+
+	return NULL;
 }
 
 static void debug_path(struct traverse_info *info)

@@ -1266,6 +1339,21 @@ static void debug_unpack_callback(int n,
 		debug_name_entry(i, names + i);
 }
 
+/*
+ * Returns true if and only if the given cache_entry is a
+ * sparse-directory entry that matches the given name_entry
+ * from the tree walk at the given traverse_info.
+ */
+static int is_sparse_directory_entry(struct cache_entry *ce,
+				     struct name_entry *name,
+				     struct traverse_info *info)
+{
+	if (!ce || !name || !S_ISSPARSEDIR(ce->ce_mode))
+		return 0;
+
+	return sparse_dir_matches_path(ce, info, name);
+}
+
 /*
  * 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

@@ -1352,9 +1440,12 @@ static int unpack_callback(int n, unsigned long mask, unsigned long dirmask, str
 			}
 		}
 
-		if (traverse_trees_recursive(n, dirmask, mask & ~dirmask,
-					     names, info) < 0)
+		if (!is_sparse_directory_entry(src[0], names, info) &&
+		    traverse_trees_recursive(n, dirmask, mask & ~dirmask,
+						    names, info) < 0) {
 			return -1;
+		}
+
 		return mask;
 	}
 

gitgitgadget

From: Derrick Stolee <[email protected]>

When we have sparse directory entries in the index, we want to compare that directory against sparse-checkout patterns. Those pattern matching algorithms are built expecting a file path, not a directory path. This is especially important in the "cone mode" patterns which will match files that exist within the "parent directories" as well as the recursive directory matches.

If path_matches_pattern_list() is given a directory, we can add a fake filename ("-") to the directory and get the same results as before, assuming we are in cone mode. Since sparse index requires cone mode patterns, this is an acceptable assumption.

---
 dir.c | 24 +++++++++++++++++++-----
 1 file changed, 19 insertions(+), 5 deletions(-)

index ebe5ec046e0..0c5264b3b20 100644
@@ -1376,7 +1376,7 @@ enum pattern_match_result path_matches_pattern_list(
 	struct path_pattern *pattern;
 	struct strbuf parent_pathname = STRBUF_INIT;
 	int result = NOT_MATCHED;
-	const char *slash_pos;
+	size_t slash_pos;
 
 	if (!pl->use_cone_patterns) {
 		pattern = last_matching_pattern_from_list(pathname, pathlen, basename,

@@ -1397,21 +1397,35 @@ enum pattern_match_result path_matches_pattern_list(
 	strbuf_addch(&parent_pathname, '/');
 	strbuf_add(&parent_pathname, pathname, pathlen);
 
+	/*
+	 * Directory entries are matched if and only if a file
+	 * contained immediately within them is matched. For the
+	 * case of a directory entry, modify the path to create
+	 * a fake filename within this directory, allowing us to
+	 * use the file-base matching logic in an equivalent way.
+	 */
+	if (parent_pathname.len > 0 &&
+	    parent_pathname.buf[parent_pathname.len - 1] == '/') {
+		slash_pos = parent_pathname.len - 1;
+		strbuf_add(&parent_pathname, "-", 1);
+	} else {
+		const char *slash_ptr = strrchr(parent_pathname.buf, '/');
+		slash_pos = slash_ptr ? slash_ptr - parent_pathname.buf : 0;
+	}
+
 	if (hashmap_contains_path(&pl->recursive_hashmap,
 				  &parent_pathname)) {
 		result = MATCHED_RECURSIVE;
 		goto done;
 	}
 
-	slash_pos = strrchr(parent_pathname.buf, '/');
-
-	if (slash_pos == parent_pathname.buf) {
+	if (!slash_pos) {
 		/* include every file in root */
 		result = MATCHED;
 		goto done;
 	}
 
-	strbuf_setlen(&parent_pathname, slash_pos - parent_pathname.buf);
+	strbuf_setlen(&parent_pathname, slash_pos);
 
 	if (hashmap_contains_path(&pl->parent_hashmap, &parent_pathname)) {
 		result = MATCHED;

gitgitgadget

From: Derrick Stolee <[email protected]>

While comparing an index to a tree, we may see a sparse directory entry. In this case, we should compare that portion of the tree to the tree represented by that entry. This could include a new tree which needs to be expanded to a full list of added files. It could also include an existing tree, in which case all of the changes inside are important to describe, including the modifications, additions, and deletions. Note that the case where the tree has a path and the index does not remains identical to before: the lack of a cache entry is the same with a sparse index.

Use diff_tree_oid() appropriately to compute the diff.

---
 diff-lib.c | 19 +++++++++++++++++++
 1 file changed, 19 insertions(+)

index c2ac9250fe9..f9eadc4fc1a 100644
@@ -325,6 +325,11 @@ static void show_new_file(struct rev_info *revs,
 	unsigned dirty_submodule = 0;
 	struct index_state *istate = revs->diffopt.repo->index;
 
+	if (new_file && S_ISSPARSEDIR(new_file->ce_mode)) {
+		diff_tree_oid(NULL, &new_file->oid, new_file->name, &revs->diffopt);
+		return;
+	}
+
 	/*
 	 * New file in the index: it might actually be different in
 	 * the working tree.

@@ -347,6 +352,20 @@ static int show_modified(struct rev_info *revs,
 	unsigned dirty_submodule = 0;
 	struct index_state *istate = revs->diffopt.repo->index;
 
+	assert(S_ISSPARSEDIR(old_entry->ce_mode) ==
+	       S_ISSPARSEDIR(new_entry->ce_mode));
+
+	/*
+	 * If both are sparse directory entries, then expand the
+	 * modifications to the file level. If only one was a sparse
+	 * directory, then they appear as an add and delete instead of
+	 * a modification.
+	 */
+	if (S_ISSPARSEDIR(new_entry->ce_mode)) {
+		diff_tree_oid(&old_entry->oid, &new_entry->oid, new_entry->name, &revs->diffopt);
+		return 0;
+	}
+
 	if (get_stat_data(istate, new_entry, &oid, &mode, cached, match_missing,
 			  &dirty_submodule, &revs->diffopt) < 0) {
 		if (report_missing)

gitgitgadget

From: Derrick Stolee <[email protected]>

'git status' began reporting a percentage of populated paths when sparse-checkout is enabled in 051df3cf (wt-status: show sparse checkout status as well, 2020-07-18). This percentage is incorrect when the index has sparse directories. It would also be expensive to calculate as we would need to parse trees to count the total number of possible paths.

Avoid the expensive computation by simplifying the output to only report that a sparse checkout exists, without the percentage.

This change is the reason we use 'git status --porcelain=v2' in t1092-sparse-checkout-compatibility.sh. We don't want to ensure that this message is equal across both modes, but instead just the important information about staged, modified, and untracked files are compared.

---
 t/t1092-sparse-checkout-compatibility.sh |  8 ++++++++
 wt-status.c                              | 14 +++++++++++---
 wt-status.h                              |  1 +
 3 files changed, 20 insertions(+), 3 deletions(-)

index 2269f44e033..375b0d35565 100755
@@ -218,6 +218,14 @@ test_expect_success 'status with options' '
 	test_all_match git status --porcelain=v2 -uno
 '
 
+test_expect_success 'status reports sparse-checkout' '
+	init_repos &&
+	git -C sparse-checkout status >full &&
+	git -C sparse-index status >sparse &&
+	test_i18ngrep "You are in a sparse checkout with " full &&
+	test_i18ngrep "You are in a sparse checkout." sparse
+'
+
 test_expect_success 'add, commit, checkout' '
 	init_repos &&
 

index 42b67357169..96db3e74962 100644
@@ -1493,9 +1493,12 @@ static void show_sparse_checkout_in_use(struct wt_status *s,
 	if (s->state.sparse_checkout_percentage == SPARSE_CHECKOUT_DISABLED)
 		return;
 
-	status_printf_ln(s, color,
-			 _("You are in a sparse checkout with %d%% of tracked files present."),
-			 s->state.sparse_checkout_percentage);
+	if (s->state.sparse_checkout_percentage == SPARSE_CHECKOUT_SPARSE_INDEX)
+		status_printf_ln(s, color, _("You are in a sparse checkout."));
+	else
+		status_printf_ln(s, color,
+				_("You are in a sparse checkout with %d%% of tracked files present."),
+				s->state.sparse_checkout_percentage);
 	wt_longstatus_print_trailer(s);
 }
 

@@ -1653,6 +1656,11 @@ static void wt_status_check_sparse_checkout(struct repository *r,
 		return;
 	}
 
+	if (r->index->sparse_index) {
+		state->sparse_checkout_percentage = SPARSE_CHECKOUT_SPARSE_INDEX;
+		return;
+	}
+
 	for (i = 0; i < r->index->cache_nr; i++) {
 		struct cache_entry *ce = r->index->cache[i];
 		if (ce_skip_worktree(ce))

index 0d32799b28e..ab9cc9d8f03 100644
@@ -78,6 +78,7 @@ enum wt_status_format {
 };
 
 #define SPARSE_CHECKOUT_DISABLED -1
+#define SPARSE_CHECKOUT_SPARSE_INDEX -2
 
 struct wt_status_state {
 	int merge_in_progress;

gitgitgadget

From: Derrick Stolee <[email protected]>

By testing 'git -c core.fsmonitor= status -uno', we can check for the simplest index operations that can be made sparse-aware. The necessary implementation details are already integrated with sparse-checkout, so modify command_requires_full_index to be zero for cmd_status().

In refresh_index(), we loop through the index entries to refresh their stat() information. However, sparse directories have no stat() information to populate. Ignore these entries.

This allows 'git status' to no longer expand a sparse index to a full one. This is further tested by dropping the "-uno" option and adding an untracked file into the worktree.

The performance test p2000-sparse-checkout-operations.sh demonstrates these improvements:

Test HEAD~1 HEAD
-----------------------------------------------------------------------------

2000.2: git status (full-index-v3)    0.31(0.30+0.05)  0.31(0.29+0.06) +0.0%
2000.3: git status (full-index-v4)    0.31(0.29+0.07)  0.34(0.30+0.08) +9.7%
2000.4: git status (sparse-index-v3)  2.35(2.28+0.10)  0.04(0.04+0.05) -98.3%
2000.5: git status (sparse-index-v4)  2.35(2.24+0.15)  0.05(0.04+0.06) -97.9%

Note that since HEAD~1 was expanding the sparse index by parsing trees, it was artificially slower than the full index case. Thus, the 98% improvement is misleading, and instead we should celebrate the 0.34s to 0.05s improvement of 85%. This is more indicative of the peformance gains we are expecting by using a sparse index.

Note: we are dropping the assignment of core.fsmonitor here. This is not necessary for the test script as we are not altering the config any other way. Correct integration with FS Monitor will be validated in later changes.

---
 builtin/commit.c                         |  3 +++
 read-cache.c                             | 10 ++++++++--
 t/t1092-sparse-checkout-compatibility.sh | 13 +++++++++----
 3 files changed, 20 insertions(+), 6 deletions(-)

index 190d215d43b..12f51db158a 100644
@@ -1510,6 +1510,9 @@ int cmd_status(int argc, const char **argv, const char *prefix)
 	if (argc == 2 && !strcmp(argv[1], "-h"))
 		usage_with_options(builtin_status_usage, builtin_status_options);
 
+	prepare_repo_settings(the_repository);
+	the_repository->settings.command_requires_full_index = 0;
+
 	status_init_config(&s, git_status_config);
 	argc = parse_options(argc, argv, prefix,
 			     builtin_status_options,

index 0c3ac3cefc0..6a1337cc905 100644
@@ -1585,8 +1585,7 @@ int refresh_index(struct index_state *istate, unsigned int flags,
 	 */
 	preload_index(istate, pathspec, 0);
 	trace2_region_enter("index", "refresh", NULL);
-	/* TODO: audit for interaction with sparse-index. */
-	ensure_full_index(istate);
+
 	for (i = 0; i < istate->cache_nr; i++) {
 		struct cache_entry *ce, *new_entry;
 		int cache_errno = 0;

@@ -1601,6 +1600,13 @@ int refresh_index(struct index_state *istate, unsigned int flags,
 		if (ignore_skip_worktree && ce_skip_worktree(ce))
 			continue;
 
+		/*
+		 * If this entry is a sparse directory, then there isn't
+		 * any stat() information to update. Ignore the entry.
+		 */
+		if (S_ISSPARSEDIR(ce->ce_mode))
+			continue;
+
 		if (pathspec && !ce_path_match(istate, ce, pathspec, seen))
 			filtered = 1;
 

index 375b0d35565..751f397cc7f 100755
@@ -511,12 +511,17 @@ test_expect_success 'sparse-index is expanded and converted back' '
 	GIT_TRACE2_EVENT="$(pwd)/trace2.txt" GIT_TRACE2_EVENT_NESTING=10 \
 		git -C sparse-index -c core.fsmonitor="" reset --hard &&
 	test_region index convert_to_sparse trace2.txt &&
-	test_region index ensure_full_index trace2.txt &&
+	test_region index ensure_full_index trace2.txt
+'
 
-	rm trace2.txt &&
+test_expect_success 'sparse-index is not expanded' '
+	init_repos &&
+
+	rm -f trace2.txt &&
+	echo >>sparse-index/untracked.txt &&
 	GIT_TRACE2_EVENT="$(pwd)/trace2.txt" GIT_TRACE2_EVENT_NESTING=10 \
-		git -C sparse-index -c core.fsmonitor="" status -uno &&
-	test_region index ensure_full_index trace2.txt
+		git -C sparse-index status &&
+	test_region ! index ensure_full_index trace2.txt
 '
 
 test_done

gitgitgadget

From: Derrick Stolee <[email protected]>

It is difficult, but possible, to get into a state where we intend to add a directory that is outside of the sparse-checkout definition. Add a test to t1092-sparse-checkout-compatibility.sh that demonstrates this using a combination of 'git reset --mixed' and 'git checkout --orphan'.

This test failed before because the output of 'git status --porcelain=v2' would not match on the lines for folder1/:

* The sparse-checkout repo (with a full index) would output each path name that is intended to be added.

* The sparse-index repo would only output that "folder1/" is staged for addition.

The status should report the full list of files to be added, and so this sparse-directory entry should be expanded to a full list when reaching it inside the wt_status_collect_changes_initial() method. Use read_tree_at() to assist.

Somehow, this loop over the cache entries was not guarded by ensure_full_index() as intended.

---
 t/t1092-sparse-checkout-compatibility.sh | 33 +++++++++++++++
 wt-status.c                              | 51 ++++++++++++++++++++++++
 2 files changed, 84 insertions(+)

index 751f397cc7f..2394c36d881 100755
@@ -524,4 +524,37 @@ test_expect_success 'sparse-index is not expanded' '
 	test_region ! index ensure_full_index trace2.txt
 '
 
+test_expect_success 'reset mixed and checkout orphan' '
+	init_repos &&
+
+	test_all_match git checkout rename-out-to-in &&
+
+	# Sparse checkouts do not agree with full checkouts about
+	# how to report a directory/file conflict during a reset.
+	# This command would fail with test_all_match because the
+	# full checkout reports "T folder1/0/1" while a sparse
+	# checkout reports "D folder1/0/1". This matches because
+	# the sparse checkouts skip "adding" the other side of
+	# the conflict.
+	test_sparse_match git reset --mixed HEAD~1 &&
+	test_sparse_match test-tool read-cache --table --expand &&
+	test_sparse_match git status --porcelain=v2 &&
+
+	# At this point, sparse-checkouts behave differently
+	# from the full-checkout.
+	test_sparse_match git checkout --orphan new-branch &&
+	test_sparse_match test-tool read-cache --table --expand &&
+	test_sparse_match git status --porcelain=v2
+'
+
+test_expect_success 'add everything with deep new file' '
+	init_repos &&
+
+	run_on_sparse git sparse-checkout set deep/deeper1/deepest &&
+
+	run_on_all touch deep/deeper1/x &&
+	test_all_match git add . &&
+	test_all_match git status --porcelain=v2
+'
+
 test_done

gitgitgadget

From: Derrick Stolee <[email protected]>

If we need to expand a sparse-index into a full one, then the FS Monitor bitmap is going to be incorrect. Ensure that we start fresh at such an event.

While this is currently a performance drawback, the eventual hope of the sparse-index feature is that these expansions will be rare and hence we will be able to keep the FS Monitor data accurate across multiple Git commands.

These tests are added to demonstrate that the behavior is the same across a full index and a sparse index, but also that file modifications to a tracked directory outside of the sparse cone will trigger ensure_full_index().

---
 sparse-index.c              |  7 ++++++
 t/t7519-status-fsmonitor.sh | 49 +++++++++++++++++++++++++++++++++++++
 2 files changed, 56 insertions(+)

index ef53bd2198b..53c8f711ccc 100644
@@ -186,6 +186,10 @@ int convert_to_sparse(struct index_state *istate)
 	cache_tree_free(&istate->cache_tree);
 	cache_tree_update(istate, 0);
 
+	istate->fsmonitor_has_run_once = 0;
+	FREE_AND_NULL(istate->fsmonitor_dirty);
+	FREE_AND_NULL(istate->fsmonitor_last_update);
+
 	istate->sparse_index = 1;
 	trace2_region_leave("index", "convert_to_sparse", istate->repo);
 	return 0;

@@ -282,6 +286,9 @@ void ensure_full_index(struct index_state *istate)
 	istate->cache = full->cache;
 	istate->cache_nr = full->cache_nr;
 	istate->cache_alloc = full->cache_alloc;
+	istate->fsmonitor_has_run_once = 0;
+	FREE_AND_NULL(istate->fsmonitor_dirty);
+	FREE_AND_NULL(istate->fsmonitor_last_update);
 
 	strbuf_release(&base);
 	free(full);

gitgitgadget

...

This one looks really good. Just two minor comments:

...

s/entried/entries/ ?

...

As I commented over at [1], I would appreciate if we could at least add a comment in the testcase that we know this testcase triggers a bug for both sparse-index and sparse-checkout...and that fixing it might affect the other comments and commands within that testcase in the future...but for now, we're just testing as best we can that the two give the same behavior.

[1] https://lore.kernel.org/git/CABPp-BGJ+LTubgS=zvGJjk3kgyfW-7UFEa=qg-0mdyrY32j0pQ@mail.gmail.com/

If you agree and include the two fixups above, the entire series is:

If you disagree, then all patches other than 9 and 14 can have my Reviewed-by tag. :-)

Thanks for all the awesome work!

Oops! Yes, that would be a valuable fixup. Thanks for catching it.

How do you feel about a new patch that focuses on adding these comments, including an older test that had a similar documentation of the behavior change? A patch that could be queued on top of this series is pasted below the cutline.

Thanks,
-Stolee

-- >8 --

From 8e69def90f5844c117cc1e9efd673c92b85c9238 Mon Sep 17 00:00:00 2001
From: Derrick Stolee <[email protected]>
Date: Tue, 13 Jul 2021 08:50:24 -0400
Subject: [PATCH 16/15] t1092: document bad sparse-checkout behavior

There are several situations where a repository with sparse-checkout enabled will act differently than a normal repository, and in ways that are not intentional. The test t1092-sparse-checkout-compatibility.sh documents some of these deviations, but a casual reader might think these are intentional behavior changes.

Add comments on these tests that make it clear that these behaviors should be updated. Using 'NEEDSWORK' helps contributors find that these are potential areas for improvement.

---
 t/t1092-sparse-checkout-compatibility.sh | 10 ++++++----
 1 file changed, 6 insertions(+), 4 deletions(-)

index 2394c36d881..cabbd42e339 100755
@@ -392,8 +392,8 @@ test_expect_failure 'blame with pathspec outside sparse definition' '
 	test_all_match git blame deep/deeper2/deepest/a
 '
 
-# TODO: reset currently does not behave as expected when in a
-# sparse-checkout.
+# NEEDSWORK: a sparse-checkout behaves differently from a full checkout
+# in this scenario, but it shouldn't.
 test_expect_failure 'checkout and reset (mixed)' '
 	init_repos &&
 

@@ -403,8 +403,8 @@ test_expect_failure 'checkout and reset (mixed)' '
 	test_all_match git reset update-folder2
 '
 
-# Ensure that sparse-index behaves identically to
-# sparse-checkout with a full index.
+# 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 &&
 

@@ -524,6 +524,8 @@ test_expect_success 'sparse-index is not expanded' '
 	test_region ! index ensure_full_index trace2.txt
 '
 
+# NEEDSWORK: a sparse-checkout behaves differently from a full checkout
+# in this scenario, but it shouldn't.
 test_expect_success 'reset mixed and checkout orphan' '
 	init_repos &&
 

2.32.0.15.g108d1b86e21

Looks good to me. Re-roll with my Reviewed-by and let's get this series merged down to next. :-)

This is the first "payoff" series in the sparse-index work. It makes 'git status' very fast when a sparse-index is enabled on a repository with cone-mode sparse-checkout (and a small populated set).

This is based on ds/sparse-index-protections AND mt/add-rm-sparse-checkout. The latter branch is needed because it changes the behavior of 'git add' around sparse entries, which changes the expectations of a test added in patch 1.

The approach here is to audit the places where ensure_full_index() pops up while doing normal commands with pathspecs within the sparse-checkout definition. Each of these are checked and tested. In the end, the sparse-index is integrated with these features:

* git status
* FS Monitor index extension.

The performance tests in p2000-sparse-operations.sh improve by 95% or more, even when compared with the full-index cases, not just the sparse-index cases that previously had extra overhead.

Hopefully this is the first example of how ds/sparse-index-protections has done the basic work to do these conversions safely, making them look easier than they seemed when starting this adventure.

Thanks, -Stolee

Update in V9
============

* Fixed typo.

* All patches are marked as Reviewed-by Elijah. Thanks for the careful review!

Derrick Stolee (16):
sparse-index: skip indexes with unmerged entries
sparse-index: include EXTENDED flag when expanding
t1092: replace incorrect 'echo' with 'cat'
t1092: expand repository data shape
t1092: add tests for status/add and sparse files
unpack-trees: preserve cache_bottom
unpack-trees: compare sparse directories correctly
unpack-trees: rename unpack_nondirectories()
unpack-trees: unpack sparse directory entries dir.c: accept a directory as part of cone-mode patterns
diff-lib: handle index diffs with sparse dirs
status: skip sparse-checkout percentage with sparse-index
status: use sparse-index throughout
wt-status: expand added sparse directory entries
fsmonitor: integrate with sparse index
t1092: document bad sparse-checkout behavior

 builtin/commit.c                         |   3 +
 diff-lib.c                               |  19 +++
 dir.c                                    |  24 +++-
 read-cache.c                             |  10 +-
 sparse-index.c                           |  27 +++-
 t/t1092-sparse-checkout-compatibility.sh | 168 +++++++++++++++++++++--
 t/t7519-status-fsmonitor.sh              |  49 +++++++
 unpack-trees.c                           | 142 ++++++++++++++++---
 wt-status.c                              |  65 ++++++++-
 wt-status.h                              |   1 +
 10 files changed, 470 insertions(+), 38 deletions(-)

base-commit: d486ca60a51c9cb1fe068803c3f540724e95e83a
Published-As: https://github.com/gitgitgadget/git/releases/tag/pr-932%2Fderrickstolee%2Fsparse-index%2Fstatus-and-add-v9
Fetch-It-Via: git fetch https://github.com/gitgitgadget/git pr-932/derrickstolee/sparse-index/status-and-add-v9
Pull-Request: https://github.com/gitgitgadget/git/pull/932

Range-diff vs v8:

1: 1815c148e8c ! 1: ecab56fd57f sparse-index: skip indexes with unmerged entries
@@ Commit message
conversion does not need to happen. Thus, this can be deferred until the merge machinery is made to integrate with the sparse-index.

+ Reviewed-by: Elijah Newren <[email protected]>

## sparse-index.c ##
2: 7bcde075d8d ! 2: f3de9ce7baa sparse-index: include EXTENDED flag when expanding
@@ Commit message
feature, but has no significance to its correctness in the user-facing functionality.

+ Reviewed-by: Elijah Newren <[email protected]>

## sparse-index.c ##
3: 05981e30b97 ! 3: 5b59436011c t1092: replace incorrect 'echo' with 'cat'
@@ Commit message
detection to work properly now that the 'larger-content' file actually has meaningful lines.

+ Reviewed-by: Elijah Newren <[email protected]>

## t/t1092-sparse-checkout-compatibility.sh ##
4: d38b66e9ee4 ! 4: 4d06d972911 t1092: expand repository data shape
@@ Commit message
Later tests will take advantage of these shapes, but they also deepen the tests that already exist.

+ Reviewed-by: Elijah Newren <[email protected]>

## t/t1092-sparse-checkout-compatibility.sh ##
5: 95ddd3abe4e ! 5: cc83a0cd307 t1092: add tests for status/add and sparse files
@@ Commit message
be more sensible, and this test could be modified to satisfy the new expected behavior.

+ Reviewed-by: Elijah Newren <[email protected]>

## t/t1092-sparse-checkout-compatibility.sh ##
6: b182b456613 ! 6: 18cb1f6ea9b unpack-trees: preserve cache_bottom
@@ Commit message
the cache_bottom will be modified as the cache-tree walk advances. Do not update it as well within mark_ce_used().

+ Reviewed-by: Elijah Newren <[email protected]>

## unpack-trees.c ##
7: 988ddce4d45 ! 7: bdd47bd30e0 unpack-trees: compare sparse directories correctly
@@ Commit message
exact string match on a sparse directory entry. The final check is a length comparison between the strings.

+ Reviewed-by: Elijah Newren <[email protected]>

## unpack-trees.c ##
8: d67ad048b08 ! 8: 0e4b7390f47 unpack-trees: rename unpack_nondirectories()
@@ Commit message
apply. The new name reflects that we will not recurse into trees in order to resolve the conflicts.

+ Reviewed-by: Elijah Newren <[email protected]>

## unpack-trees.c ##
9: c0b0b58584c ! 9: 602525f5d71 unpack-trees: unpack sparse directory entries
@@ Commit message
markers in the case that the entries correspond to directories and we already have a sparse directory entry.

+ Reviewed-by: Elijah Newren <[email protected]>

## unpack-trees.c ##
@@ unpack-trees.c: static int find_cache_pos(struct traverse_info *info,
+
+ /*
+ * Due to lexicographic sorting and sparse directory
-+ * entried ending with a trailing slash, our path as a
++ * entries ending with a trailing slash, our path as a
+ * sparse directory (e.g "subdir/") and our path as a
+ * file (e.g. "subdir") might be separated by other
+ * paths (e.g. "subdir-").
10: 76c7528f78f ! 10: b051c0847a5 dir.c: accept a directory as part of cone-mode patterns
@@ Commit message
assuming we are in cone mode. Since sparse index requires cone mode patterns, this is an acceptable assumption.

+ Reviewed-by: Elijah Newren <[email protected]>

## dir.c ##
11: d875a7f8585 ! 11: e749fd41cda diff-lib: handle index diffs with sparse dirs
@@ Commit message

Use diff_tree_oid() appropriately to compute the diff.

+ Reviewed-by: Elijah Newren <[email protected]>

## diff-lib.c ##
12: 2b72cc2d985 ! 12: 7f782e3fe50 status: skip sparse-checkout percentage with sparse-index
@@ Commit message
this message is equal across both modes, but instead just the important information about staged, modified, and untracked files are compared.

+ Reviewed-by: Elijah Newren <[email protected]>

## t/t1092-sparse-checkout-compatibility.sh ##
13: 1c1feef3733 ! 13: ad1715e3319 status: use sparse-index throughout
@@ Commit message
other way. Correct integration with FS Monitor will be validated in later changes.

+ Reviewed-by: Elijah Newren <[email protected]>

## builtin/commit.c ##
14: dada1b91bdc ! 14: aa2258be302 wt-status: expand added sparse directory entries
@@ Commit message
Somehow, this loop over the cache entries was not guarded by ensure_full_index() as intended.

+ Reviewed-by: Elijah Newren <[email protected]>

## t/t1092-sparse-checkout-compatibility.sh ##
15: bdc771cf373 ! 15: 1d4b1f8aea0 fsmonitor: integrate with sparse index
@@ Commit message
to a tracked directory outside of the sparse cone will trigger ensure_full_index().

+ Reviewed-by: Elijah Newren <[email protected]>

## sparse-index.c ##
-: ----------- > 16: 45861118991 t1092: document bad sparse-checkout behavior

gitgitgadget

From: Derrick Stolee <[email protected]>

The sparse-index format is designed to be compatible with merge conflicts, even those outside the sparse-checkout definition. The reason is that when converting a full index to a sparse one, a cache entry with nonzero stage will not be collapsed into a sparse directory entry.

However, this behavior was not tested, and a different behavior within convert_to_sparse() fails in this scenario. Specifically, cache_tree_update() will fail when unmerged entries exist. convert_to_sparse_rec() uses the cache-tree data to recursively walk the tree structure, but also to compute the OIDs used in the sparse-directory entries.

Add an index scan to convert_to_sparse() that will detect if these merge conflict entries exist and skip the conversion before trying to update the cache-tree. This is marked as NEEDSWORK because this can be removed with a suitable update to cache_tree_update() or a similar method that can construct a cache-tree with invalid nodes, but still allow creating the nodes necessary for creating sparse directory entries.

It is possible that in the future we will not need to make such an update, since if we do not expand a sparse-index into a full one, this conversion does not need to happen. Thus, this can be deferred until the merge machinery is made to integrate with the sparse-index.

---
 sparse-index.c                           | 18 ++++++++++++++++++
 t/t1092-sparse-checkout-compatibility.sh | 22 ++++++++++++++++++++++
 2 files changed, 40 insertions(+)

index affc4048f27..2c695930275 100644
@@ -116,6 +116,17 @@ int set_sparse_index_config(struct repository *repo, int enable)
 	return res;
 }
 
+static int index_has_unmerged_entries(struct index_state *istate)
+{
+	int i;
+	for (i = 0; i < istate->cache_nr; i++) {
+		if (ce_stage(istate->cache[i]))
+			return 1;
+	}
+
+	return 0;
+}
+
 int convert_to_sparse(struct index_state *istate)
 {
 	int test_env;

@@ -152,6 +163,13 @@ int convert_to_sparse(struct index_state *istate)
 		return -1;
 	}
 
+	/*
+	 * NEEDSWORK: If we have unmerged entries, then stay full.
+	 * Unmerged entries prevent the cache-tree extension from working.
+	 */
+	if (index_has_unmerged_entries(istate))
+		return 0;
+
 	if (cache_tree_update(istate, 0)) {
 		warning(_("unable to update cache-tree, staying full"));
 		return -1;

index d028b73eba1..b8617ceef71 100755
@@ -352,6 +352,28 @@ test_expect_success 'merge with outside renames' '
 	done
 '
 
+# Sparse-index fails to convert the index in the
+# final 'git cherry-pick' command.
+test_expect_success 'cherry-pick with conflicts' '
+	init_repos &&
+
+	write_script edit-conflict <<-\EOF &&
+	echo $1 >conflict
+	EOF
+
+	test_all_match git checkout -b to-cherry-pick &&
+	run_on_all ../edit-conflict ABC &&
+	test_all_match git add conflict &&
+	test_all_match git commit -m "conflict to pick" &&
+
+	test_all_match git checkout -B base HEAD~1 &&
+	run_on_all ../edit-conflict DEF &&
+	test_all_match git add conflict &&
+	test_all_match git commit -m "conflict in base" &&
+
+	test_all_match test_must_fail git cherry-pick to-cherry-pick
+'
+
 test_expect_success 'clean' '
 	init_repos &&
 

gitgitgadget

From: Derrick Stolee <[email protected]>

When creating a full index from a sparse one, we create cache entries for every blob within a given sparse directory entry. These are correctly marked with the CE_SKIP_WORKTREE flag, but the CE_EXTENDED flag is not included. The CE_EXTENDED flag would exist if we loaded a full index from disk with these entries marked with CE_SKIP_WORKTREE, so we can add the flag here to be consistent. This allows us to directly compare the flags present in cache entries when testing the sparse-index feature, but has no significance to its correctness in the user-facing functionality.

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

index 2c695930275..ef53bd2198b 100644
@@ -213,7 +213,7 @@ static int add_path_to_index(const struct object_id *oid,
 	strbuf_addstr(base, path);
 
 	ce = make_cache_entry(istate, mode, oid, base->buf, 0, 0);
-	ce->ce_flags |= CE_SKIP_WORKTREE;
+	ce->ce_flags |= CE_SKIP_WORKTREE | CE_EXTENDED;
 	set_index_entry(istate, istate->cache_nr++, ce);
 
 	strbuf_setlen(base, len);

gitgitgadget

From: Derrick Stolee <[email protected]>

This fixes the test data shape to be as expected, allowing rename detection to work properly now that the 'larger-content' file actually has meaningful lines.

---
 t/t1092-sparse-checkout-compatibility.sh | 2 +-
 1 file changed, 1 insertion(+), 1 deletion(-)

index b8617ceef71..87f1014a1c9 100755
@@ -40,7 +40,7 @@ test_expect_success 'setup' '
 		done &&
 
 		git checkout -b rename-base base &&
-		echo >folder1/larger-content <<-\EOF &&
+		cat >folder1/larger-content <<-\EOF &&
 		matching
 		lines
 		help

gitgitgadget

From: Derrick Stolee <[email protected]>

As more features integrate with the sparse-index feature, more and more special cases arise that require different data shapes within the tree structure of the repository in order to demonstrate those cases.

Add several interesting special cases all at once instead of sprinkling them across several commits. The interesting cases being added here are:

* Add sparse-directory entries on both sides of directories within the sparse-checkout definition.

* Add directories outside the sparse-checkout definition who have only one entry and are the first entry of a directory with multiple entries.

* Add filenames adjacent to a sparse directory entry that sort before and after the trailing slash.

Later tests will take advantage of these shapes, but they also deepen the tests that already exist.

---
 t/t1092-sparse-checkout-compatibility.sh | 42 ++++++++++++++++++++++--
 1 file changed, 40 insertions(+), 2 deletions(-)

index 87f1014a1c9..0e71a623619 100755
@@ -17,7 +17,7 @@ test_expect_success 'setup' '
 		echo "after folder1" >g &&
 		echo "after x" >z &&
 		mkdir folder1 folder2 deep x &&
-		mkdir deep/deeper1 deep/deeper2 &&
+		mkdir deep/deeper1 deep/deeper2 deep/before deep/later &&
 		mkdir deep/deeper1/deepest &&
 		echo "after deeper1" >deep/e &&
 		echo "after deepest" >deep/deeper1/e &&

@@ -25,10 +25,23 @@ test_expect_success 'setup' '
 		cp a folder2 &&
 		cp a x &&
 		cp a deep &&
+		cp a deep/before &&
 		cp a deep/deeper1 &&
 		cp a deep/deeper2 &&
+		cp a deep/later &&
 		cp a deep/deeper1/deepest &&
 		cp -r deep/deeper1/deepest deep/deeper2 &&
+		mkdir deep/deeper1/0 &&
+		mkdir deep/deeper1/0/0 &&
+		touch deep/deeper1/0/1 &&
+		touch deep/deeper1/0/0/0 &&
+		>folder1- &&
+		>folder1.x &&
+		>folder10 &&
+		cp -r deep/deeper1/0 folder1 &&
+		cp -r deep/deeper1/0 folder2 &&
+		echo >>folder1/0/0/0 &&
+		echo >>folder2/0/1 &&
 		git add . &&
 		git commit -m "initial commit" &&
 		git checkout -b base &&

@@ -56,11 +69,17 @@ test_expect_success 'setup' '
 		mv folder1/a folder2/b &&
 		mv folder1/larger-content folder2/edited-content &&
 		echo >>folder2/edited-content &&
+		echo >>folder2/0/1 &&
+		echo stuff >>deep/deeper1/a &&
 		git add . &&
 		git commit -m "rename folder1/... to folder2/..." &&
 
 		git checkout -b rename-out-to-in rename-base &&
 		mv folder1/a deep/deeper1/b &&
+		echo more stuff >>deep/deeper1/a &&
+		rm folder2/0/1 &&
+		mkdir folder2/0/1 &&
+		echo >>folder2/0/1/1 &&
 		mv folder1/larger-content deep/deeper1/edited-content &&
 		echo >>deep/deeper1/edited-content &&
 		git add . &&

@@ -68,6 +87,9 @@ test_expect_success 'setup' '
 
 		git checkout -b rename-in-to-out rename-base &&
 		mv deep/deeper1/a folder1/b &&
+		echo >>folder2/0/1 &&
+		rm -rf folder1/0/0 &&
+		echo >>folder1/0/0 &&
 		mv deep/deeper1/larger-content folder1/edited-content &&
 		echo >>folder1/edited-content &&
 		git add . &&

@@ -262,13 +284,29 @@ test_expect_success 'diff --staged' '
 	test_all_match git diff --staged
 '
 
-test_expect_success 'diff with renames' '
+test_expect_success 'diff with renames and conflicts' '
 	init_repos &&
 
 	for branch in rename-out-to-out rename-out-to-in rename-in-to-out
 	do
 		test_all_match git checkout rename-base &&
 		test_all_match git checkout $branch -- . &&
+		test_all_match git status --porcelain=v2 &&
+		test_all_match git diff --staged --no-renames &&
+		test_all_match git diff --staged --find-renames || return 1
+	done
+'
+
+test_expect_success 'diff with directory/file conflicts' '
+	init_repos &&
+
+	for branch in rename-out-to-out rename-out-to-in rename-in-to-out
+	do
+		git -C full-checkout reset --hard &&
+		test_sparse_match git reset --hard &&
+		test_all_match git checkout $branch &&
+		test_all_match git checkout rename-base -- . &&
+		test_all_match git status --porcelain=v2 &&
 		test_all_match git diff --staged --no-renames &&
 		test_all_match git diff --staged --find-renames || return 1
 	done

gitgitgadget

From: Derrick Stolee <[email protected]>

Before moving to update 'git status' and 'git add' to work with sparse indexes, add an explicit test that ensures the sparse-index works the same as a normal sparse-checkout when the worktree contains directories and files outside of the sparse cone.

Specifically, 'folder1/a' is a file in our test repo, but 'folder1' is not in the sparse cone. When 'folder1/a' is modified, the file is not shown as modified and adding it will fail. This is new behavior as of a20f704 (add: warn when asked to update SKIP_WORKTREE entries, 2021-04-08). Before that change, these adds would be silently ignored.

Untracked files are fine: adding new files both with 'git add .' and 'git add folder1/' works just as in a full checkout. This may not be entirely desirable, but we are not intending to change behavior at the moment, only document it. A future change could alter the behavior to be more sensible, and this test could be modified to satisfy the new expected behavior.

---
 t/t1092-sparse-checkout-compatibility.sh | 38 ++++++++++++++++++++++++
 1 file changed, 38 insertions(+)

index 0e71a623619..2269f44e033 100755
@@ -254,6 +254,44 @@ test_expect_success 'add, commit, checkout' '
 	test_all_match git checkout -
 '
 
+test_expect_success 'status/add: outside sparse cone' '
+	init_repos &&
+
+	# adding a "missing" file outside the cone should fail
+	test_sparse_match test_must_fail git add folder1/a &&
+
+	# folder1 is at HEAD, but outside the sparse cone
+	run_on_sparse mkdir folder1 &&
+	cp initial-repo/folder1/a sparse-checkout/folder1/a &&
+	cp initial-repo/folder1/a sparse-index/folder1/a &&
+
+	test_sparse_match git status &&
+
+	write_script edit-contents <<-\EOF &&
+	echo text >>$1
+	EOF
+	run_on_sparse ../edit-contents folder1/a &&
+	run_on_all ../edit-contents folder1/new &&
+
+	test_sparse_match git status --porcelain=v2 &&
+
+	# This "git add folder1/a" fails with a warning
+	# in the sparse repos, differing from the full
+	# repo. This is intentional.
+	test_sparse_match test_must_fail git add folder1/a &&
+	test_sparse_match test_must_fail git add --refresh folder1/a &&
+	test_all_match git status --porcelain=v2 &&
+
+	test_all_match git add . &&
+	test_all_match git status --porcelain=v2 &&
+	test_all_match git commit -m folder1/new &&
+
+	run_on_all ../edit-contents folder1/newer &&
+	test_all_match git add folder1/ &&
+	test_all_match git status --porcelain=v2 &&
+	test_all_match git commit -m folder1/newer
+'
+
 test_expect_success 'checkout and reset --hard' '
 	init_repos &&
 

gitgitgadget

From: Derrick Stolee <[email protected]>

The cache_bottom member of 'struct unpack_trees_options' is used to track the range of index entries corresponding to a node of the cache tree. While recursing with traverse_by_cache_tree(), this value is preserved on the call stack using a local and then restored as that method returns.

The mark_ce_used() method normally modifies the cache_bottom member when it refers to the marked cache entry. However, sparse directory entries are stored as nodes in the cache-tree data structure as of 2de37c53 (cache-tree: integrate with sparse directory entries, 2021-03-30). Thus, the cache_bottom will be modified as the cache-tree walk advances. Do not update it as well within mark_ce_used().

---
 unpack-trees.c | 7 +++++++
 1 file changed, 7 insertions(+)

index f88a69f8e71..87c1ed204c8 100644
@@ -600,6 +600,13 @@ static void mark_ce_used(struct cache_entry *ce, struct unpack_trees_options *o)
 {
 	ce->ce_flags |= CE_UNPACKED;
 
+	/*
+	 * If this is a sparse directory, don't advance cache_bottom.
+	 * That will be advanced later using the cache-tree data.
+	 */
+	if (S_ISSPARSEDIR(ce->ce_mode))
+		return;
+
 	if (o->cache_bottom < o->src_index->cache_nr &&
 	    o->src_index->cache[o->cache_bottom] == ce) {
 		int bottom = o->cache_bottom;

gitgitgadget

From: Derrick Stolee <[email protected]>

As we further integrate the sparse-index into unpack-trees, we need to ensure that we compare sparse directory entries correctly with other entries. This affects searching for an exact path as well as sorting index entries.

Sparse directory entries contain the trailing directory separator. This is important for the sorting, in particular. Thus, within do_compare_entry() we stop using S_IFREG in all cases, since sparse directories should use S_IFDIR to indicate that the comparison should treat the entry name as a dirctory.

Within compare_entry(), it first calls do_compare_entry() to check the leading portion of the name. When the input path is a directory name, we could match exactly already. Thus, we should return 0 if we have an exact string match on a sparse directory entry. The final check is a length comparison between the strings.

---
 unpack-trees.c | 14 +++++++++++++-
 1 file changed, 13 insertions(+), 1 deletion(-)

index 87c1ed204c8..b113cc750f2 100644
@@ -983,6 +983,7 @@ static int do_compare_entry(const struct cache_entry *ce,
 	int pathlen, ce_len;
 	const char *ce_name;
 	int cmp;
+	unsigned ce_mode;
 
 	/*
 	 * If we have not precomputed the traverse path, it is quicker

@@ -1005,7 +1006,8 @@ static int do_compare_entry(const struct cache_entry *ce,
 	ce_len -= pathlen;
 	ce_name = ce->name + pathlen;
 
-	return df_name_compare(ce_name, ce_len, S_IFREG, name, namelen, mode);
+	ce_mode = S_ISSPARSEDIR(ce->ce_mode) ? S_IFDIR : S_IFREG;
+	return df_name_compare(ce_name, ce_len, ce_mode, name, namelen, mode);
 }
 
 static int compare_entry(const struct cache_entry *ce, const struct traverse_info *info, const struct name_entry *n)

@@ -1014,6 +1016,16 @@ static int compare_entry(const struct cache_entry *ce, const struct traverse_inf
 	if (cmp)
 		return cmp;
 
+	/*
+	 * At this point, we know that we have a prefix match. If ce
+	 * is a sparse directory, then allow an exact match. This only
+	 * works when the input name is a directory, since ce->name
+	 * ends in a directory separator.
+	 */
+	if (S_ISSPARSEDIR(ce->ce_mode) &&
+	    ce->ce_namelen == traverse_path_len(info, tree_entry_len(n)) + 1)
+		return 0;
+
 	/*
 	 * Even if the beginning compared identically, the ce should
 	 * compare as bigger than a directory leading up to it!

gitgitgadget

From: Derrick Stolee <[email protected]>

In the next change, we will use this method to unpack a sparse directory entry, so change the name to unpack_single_entry() so these entries apply. The new name reflects that we will not recurse into trees in order to resolve the conflicts.

---
 unpack-trees.c | 14 +++++++-------
 1 file changed, 7 insertions(+), 7 deletions(-)

index b113cc750f2..d26386ce8b2 100644
@@ -804,7 +804,7 @@ static int traverse_by_cache_tree(int pos, int nr_entries, int nr_names,
 		BUG("We need cache-tree to do this optimization");
 
 	/*
-	 * Do what unpack_callback() and unpack_nondirectories() normally
+	 * Do what unpack_callback() and unpack_single_entry() normally
 	 * do. But we walk all paths in an iterative loop instead.
 	 *
 	 * D/F conflicts and higher stage entries are not a concern

@@ -1075,11 +1075,11 @@ static struct cache_entry *create_ce_entry(const struct traverse_info *info,
  * without actually calling it. If you change the logic here you may need to
  * check and change there as well.
  */
-static int unpack_nondirectories(int n, unsigned long mask,
-				 unsigned long dirmask,
-				 struct cache_entry **src,
-				 const struct name_entry *names,
-				 const struct traverse_info *info)
+static int unpack_single_entry(int n, unsigned long mask,
+			       unsigned long dirmask,
+			       struct cache_entry **src,
+			       const struct name_entry *names,
+			       const struct traverse_info *info)
 {
 	int i;
 	struct unpack_trees_options *o = info->data;

@@ -1322,7 +1322,7 @@ static int unpack_callback(int n, unsigned long mask, unsigned long dirmask, str
 		}
 	}
 
-	if (unpack_nondirectories(n, mask, dirmask, src, names, info) < 0)
+	if (unpack_single_entry(n, mask, dirmask, src, names, info) < 0)
 		return -1;
 
 	if (o->merge && src[0]) {

gitgitgadget

From: Derrick Stolee <[email protected]>

During unpack_callback(), index entries are compared against tree entries. These are matched according to names and types. One goal is to decide if we should recurse into subtrees or simply operate on one index entry.

In the case of a sparse-directory entry, we do not want to recurse into that subtree and instead simply compare the trees. In some cases, we might want to perform a merge operation on the entry, such as during 'git checkout <commit>' which wants to replace a sparse tree entry with the tree for that path at the target commit. We extend the logic within unpack_single_entry() to create a sparse-directory entry in this case, and then that is sent to call_unpack_fn().

There are some subtleties in this process. For instance, we need to update find_cache_entry() to allow finding a sparse-directory entry that exactly matches a given path. Use the new helper method sparse_dir_matches_path() for this. We also need to ignore conflict markers in the case that the entries correspond to directories and we already have a sparse directory entry.

---
 unpack-trees.c | 107 +++++++++++++++++++++++++++++++++++++++++++++----
 1 file changed, 99 insertions(+), 8 deletions(-)

index d26386ce8b2..0a5135ab397 100644
@@ -1052,13 +1052,15 @@ static struct cache_entry *create_ce_entry(const struct traverse_info *info,
 	const struct name_entry *n,
 	int stage,
 	struct index_state *istate,
-	int is_transient)
+	int is_transient,
+	int is_sparse_directory)
 {
 	size_t len = traverse_path_len(info, tree_entry_len(n));
+	size_t alloc_len = is_sparse_directory ? len + 1 : len;
 	struct cache_entry *ce =
 		is_transient ?
-		make_empty_transient_cache_entry(len, NULL) :
-		make_empty_cache_entry(istate, len);
+		make_empty_transient_cache_entry(alloc_len, NULL) :
+		make_empty_cache_entry(istate, alloc_len);
 
 	ce->ce_mode = create_ce_mode(n->mode);
 	ce->ce_flags = create_ce_flags(stage);