Sparse Index: Integrate with merge, cherry-pick, rebase, and revert

This series integrates the sparse index with commands that perform merges such as 'git merge', 'git cherry-pick', 'git revert' (free with cherry-pick), and 'git rebase'.

When the ORT merge strategy is enabled, this allows most merges to succeed without expanding the sparse index, leading to significant performance gains. I tested these changes against an internal monorepo with over 2 million paths at HEAD but with a sparse-checkout that only has ~60,000 files within the sparse-checkout cone. 'git merge' commands went from 5-6 seconds to 0.750-1.250s.

In the case of the recursive merge strategy, the sparse index is expanded before the recursive algorithm proceeds. We expect that this is as good as we can get with that strategy. When the strategy shifts to ORT as the default, then this will not be a problem except for users who decide to change the behavior.

Most of the hard work was done by previous series, such as ds/sparse-index-ignored-files (which this series is based on).

Thanks, -Stolee

Derrick Stolee (6):
t1092: use ORT merge strategy
diff: ignore sparse paths in diffstat
merge: make sparse-aware with ORT
merge-ort: expand only for out-of-cone conflicts
t1092: add cherry-pick, rebase tests
sparse-index: integrate with cherry-pick and rebase

 builtin/merge.c                          |  3 +
 builtin/rebase.c                         |  6 ++
 builtin/revert.c                         |  3 +
 diff.c                                   |  8 ++
 merge-ort.c                              | 16 ++++
 merge-recursive.c                        |  3 +
 t/t1092-sparse-checkout-compatibility.sh | 97 +++++++++++++++++++++---
 7 files changed, 124 insertions(+), 12 deletions(-)

base-commit: febef675f051eb08896751bb5661b6deb5579ead
Published-As: https://github.com/gitgitgadget/git/releases/tag/pr-1019%2Fderrickstolee%2Fsparse-index%2Fmerge-v1
Fetch-It-Via: git fetch https://github.com/gitgitgadget/git pr-1019/derrickstolee/sparse-index/merge-v1
Pull-Request: https://github.com/gitgitgadget/git/pull/1019

gitgitgadget

From: Derrick Stolee <[email protected]>

The sparse index will be compatible with the ORT merge strategy, so let's use it explicitly in our tests.

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

index ddc86bb4152..3e01e70fa0b 100755
@@ -7,6 +7,11 @@ GIT_TEST_SPARSE_INDEX=
 
 . ./test-lib.sh
 
+# Force the use of the ORT merge algorithm until testing with the
+# recursive strategy. We expect ORT to be used with sparse-index.
+GIT_TEST_MERGE_ALGORITHM=ort
+export GIT_TEST_MERGE_ALGORITHM
+
 test_expect_success 'setup' '
 	git init initial-repo &&
 	(

@@ -501,7 +506,7 @@ test_expect_success 'merge with conflict outside cone' '
 
 	test_all_match git checkout -b merge-tip merge-left &&
 	test_all_match git status --porcelain=v2 &&
-	test_all_match test_must_fail git merge -m merge merge-right &&
+	test_all_match test_must_fail git merge -sort -m merge merge-right &&
 	test_all_match git status --porcelain=v2 &&
 
 	# Resolve the conflict in different ways:

@@ -531,7 +536,7 @@ test_expect_success 'merge with outside renames' '
 	do
 		test_all_match git reset --hard &&
 		test_all_match git checkout -f -b merge-$type update-deep &&
-		test_all_match git merge -m "$type" rename-$type &&
+		test_all_match git merge -sort -m "$type" rename-$type &&
 		test_all_match git rev-parse HEAD^{tree} || return 1
 	done
 '

gitgitgadget

Unless you mean that the sparse index will only be compatible with ort, but will never be with recursive, I do not quite see why this is taking us into a good direction. Is this because we want to gain test coverage for ort early, before we flip the default to ort [*1*]?

[Footnote]

*1* If the answer is "no, it is because sparse index will not work
with recursive", the please disregard the rest, but just in case it is not...

It seems to me that it would let us live in the future in a more comprehensive way if we tweaked merge_recursive() and/or merge_recursive_generic() so that all internal callers, not just builtin/merge.c, would redirect to the ort machinery when say GIT_TEST_REPLACE_RECURSIVE_WITH_ORT environment exists, and doing it that way we do not need to sprinkle "-srecursive" and "-sort" everywhere in our tests at randomly chosen places to give test coverage to both strategies.

The sparse index will _work_ with the recursive merge strategy, it will just continue to be slow, and likely slower than if we had a full index. This is because the recursive merge algorithm will expand a sparse index into a full one before doing any of its logic (hence my confidence that it will work).

The main point why ORT is the focus is that the ORT strategy is required so the sparse index can get the intended performance gains (i.e. it does not expand in most cases). The ORT algorithm can resolve conflicts outside the sparse-checkout cone without needing the index as a data structure and instead the resulting tree is recorded in the correct sparse directory entry.

I could also change this patch to stop using ORT _all the time_ and instead let the GIT_TEST_MERGE_ALGORITHM decide which is tested.

That is, except for the final tests that check that the index is not expanded. Those tests must specify the ORT strategy explicitly.

I think I started playing with the GIT_TEST_MERGE_ALGORITHM because it appears to override the command-line option, but I will need to double-check that.

Thanks,
-Stolee

Ah, thanks for explanation. The tests being touched are not about correctness of the merge results but the damage the operation would make to the sparseness of the index, and because in the longer term the recursive backend is on its way out, we do want to focus on testing how ORT performs.

No, that's OK.

It was unclear from the proposed log message (hence my questions), but if it is made clear that we have a good reason why we want to see how the sparse-index works with ORT, explicitly testing with ORT like your patch does is the right thing to do, I would think.

With GIT_TEST_MERGE_ALGORITHM set to ort and exported, it is puzzling why some "git merge" invocations gets "-s ort" in the same patch, though.

Thanks.

GIT_TEST_MERGE_ALGORITHM already does this; the testsuite already had -s recursive sprinkled everywhere (due to contrast with -s resolve), but since I wanted to use all existing recursive tests as ort tests, then rather than tweaking all the test files and copying tests and whatnot, we decided to just have GIT_TEST_MERGE_ALGORITHM reinterpret "recursive" to whatever GIT_TEST_MERGE_ALGORITHM says.

Yes, GIT_TEST_MERGE_ALGORITHM=ort reinterprets "recursive" to mean "ort".

I somehow thought that direct calls to merge_recursive() and merge_recursive_generic() are not affected with that environment variable, so you cannot influence what happens during "git am -3" and "git stash apply" with that, but perhaps I was not reading the code correctly.

It seems that merge_recursive() and merge_ort_recursive() are interface compatible and the latter can serve as a drop-in replacement for the former?

Sorry for being unclear. I was responding to the "sprinkling" portion of the quote; GIT_TEST_MERGE_ALGORITHM allows us to avoid sprinkling -srecursive and -sort in various places.

You are correct that merge_recursive() and merge_recursive_generic() are unaffected by the environment variable; the environment variable operates at a higher level in the code to choose whether to call e.g. merge_recursive() vs. merge_incore_recursive().

Yes, merge_ort_recursive() and merge_ort_nonrecursive() were meant as interface compatible drop-in replacements for merge_recursive() and merge_trees(), to make it easy to switch callers over.

There is no such replacement for merge_recursive_generic(), though, and builtin/{am, merge-recursive, stash}.c will all need to be modified to work with merge-ort. IIRC, when last we discussed that interface, we realized that the three were using it a bit differently and it had some hardcoded am-specific assumptions that were not appropriate for the other two, so it's not clear to me we should port that interface.

But merge_recursive_generic() eveantually calls into merge_recursive(); as long as you hook into the latter, you're covered, no?

Okay, you caught me. merge_ort_recursive() has one API difference from merge_recursive(), namely, it does not allow opt->ancestor to be anything other than NULL, whereas merge_recursive() does. The only caller where that distinction matters is merge_recursive_generic()...but that does prevent merge_recursive_generic() from just calling merge_ort_recursive().

The original patches I sent in for merge_incore_recursive() would have provided for this same ability (and made merge_ort_recursive() actually be a drop in replacement), but you rightfully pointed out that the relevant opt->ancestor portion of the patches made no sense. At the time, I responded (at
https://lore.kernel.org/git/CABPp-BFr=1iVY739cfh-1Hp82x-Mny-k4y0f3zZ_YuP3PxiGfQ@mail.gmail.com/):

"""
Yeah, you're making me lean towards thinking that merge_recursive_generic() is just a broken API that I shouldn't port over (even as a wrapper), and that I further shouldn't support using the merge_ort_recursive() API in a fashion wanted by that function. """

The problem with opt->ancestor in merge_recursive_generic() is as follows:

* When there is only one merge base (and opt->ancestor is not set),
merge_ort_recursive() and merge_recursive() will both set opt->ancestor to the hash of the merge base commit.

* The hash of the merge base is great when the merge base is a real
commit, less so when fake commits are generated (as merge_recursive_generic() does) to pass along.

* Because of the above, merge_recursive_generic() overrides
opt->ancestor with the value "constructed merge base" when there is exactly one merge base tree. That was done with git-am in mind, and makes sense for am because it does create a fake or constructed merge base. It does not make sense to me for stash, which has a real commit. It also seems suboptimal or wrong for builtin/merge-recursive.c as well -- it's hard to be sure since builtin/merge-recursive simply takes an OID rather than actual branch names and thus those OIDs could correspond to fake or constructed commits, but builtin/merge-recursive does have the better_branch_name() function it uses for o.branch1 and o.branch2 and it seems like it should do the same on the merge base when it's unique.

Rather than porting this bug (these bugs?) over from merge-recursive, I'll just convert the merge_recursive_generic() callers over to the new API.

From: Derrick Stolee <[email protected]>

The diff_populate_filespec() method is used to describe the diff after a merge operation is complete, especially when a conflict appears. In order to avoid expanding a sparse index, the reuse_worktree_file() needs to be adapted to ignore files that are outside of the sparse-checkout cone. The file names and OIDs used for this check come from the merged tree in the case of the ORT strategy, not the index, hence the ability to look into these paths without having already expanded the index.

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

index a8113f17070..c457cfa0e59 100644
@@ -26,6 +26,7 @@
 #include "parse-options.h"
 #include "help.h"
 #include "promisor-remote.h"
+#include "dir.h"
 
 #ifdef NO_FAST_WORKING_DIRECTORY
 #define FAST_WORKING_DIRECTORY 0

@@ -3900,6 +3901,13 @@ static int reuse_worktree_file(struct index_state *istate,
 	if (!FAST_WORKING_DIRECTORY && !want_file && has_object_pack(oid))
 		return 0;
 
+	/*
+	 * If this path does not match our sparse-checkout definition,
+	 * then the file will not be in the working directory.
+	 */
+	if (!path_in_sparse_checkout(name, istate))
+		return 0;
+
 	/*
 	 * Similarly, if we'd have to convert the file contents anyway, that
 	 * makes the optimization not worthwhile.

gitgitgadget

I'm confused; I thought the diffstat was only shown if the merge was successful, in which case there would be no conflicts appearing.

Also, I'm not that familiar with the general diff machinery (just the rename detection parts), but...if the diffstat only shows when the merge is successful, wouldn't we be comparing two REVS (ORIG_HEAD to HEAD)? Why would we make use of the working tree at all in such a case? And, wouldn't using the working tree be dangerous...what if there was a merge performed with a dirty working tree?

On a bit of a tangent, I know diffcore-rename.c calls into diff_populate_filespec() as well, and I have some code doing merges in a bare repository (where there obviously is no index). It seemed to be working, but given this commit message, now I'm wondering if I've missed something fundamental either in that implementation or there's something amiss in this patch. Or both. Maybe I need to dig into diff_populate_filespec() more, but it seems you already have. Any pointers to orient me on why your changes are right here (and, if you know, why diffcore-rename.c should or shouldn't be using diff_populate_filespec() in a bare repo)?

That's my mistake. I'll edit the message accordingly.

I think the cases you are thinking about are covered by this condition before the one I'm inserting:

/* We want to avoid the working directory if our caller
* doesn't need the data in a normal file, this system
* is rather slow with its stat/open/mmap/close syscalls,
* and the object is contained in a pack file. The pack
* is probably already open and will be faster to obtain
* the data through than the working directory. Loose
* objects however would tend to be slower as they need
* to be individually opened and inflated.
*/
if (!FAST_WORKING_DIRECTORY && !want_file && has_object_pack(oid))
return 0;

or after:

	/*
	 * Similarly, if we'd have to convert the file contents anyway, that
	 * makes the optimization not worthwhile.
	 */
	if (!want_file && would_convert_to_git(istate, name))
		return 0;

(This makes me think that I should move my new condition further down so these two can be linked by context.)

Sounds like this is just an optimization, so it is fine to opt out of it if we think the optimization isn't necessary. Outside of the sparse-checkout cone qualifies.

Thanks,
-Stolee

Ah, this is very helpful. Thanks for digging up these details.

From: Derrick Stolee <[email protected]>

Allow 'git merge' to operate without expanding a sparse index, at least not immediately. The index still will be expanded in a few cases:

1. If the merge strategy is 'recursive', then we enable command_requires_full_index at the start of the merge_recursive() method. We expect sparse-index users to also have the 'ort' strategy enabled.

2. If the merge results in a conflicted file, then we expand the index before updating the working tree. The loop that iterates over the worktree replaces index entries and tracks 'origintal_cache_nr' which can become completely wrong if the index expands in the middle of the operation. This safety valve is important before that loop starts. A later change will focus this to only expand if we indeed have a conflict outside of the sparse-checkout cone.

Some test updates are required, including a mistaken 'git checkout -b' that did not specify the base branch, causing merges to be fast-forward merges.

---
 builtin/merge.c                          | 3 +++
 merge-ort.c                              | 8 ++++++++
 merge-recursive.c                        | 3 +++
 t/t1092-sparse-checkout-compatibility.sh | 8 ++++++--
 4 files changed, 20 insertions(+), 2 deletions(-)

index 22f23990b37..926de328fbb 100644
@@ -1276,6 +1276,9 @@ int cmd_merge(int argc, const char **argv, const char *prefix)
 	if (argc == 2 && !strcmp(argv[1], "-h"))
 		usage_with_options(builtin_merge_usage, builtin_merge_options);
 
+	prepare_repo_settings(the_repository);
+	the_repository->settings.command_requires_full_index = 0;
+
 	/*
 	 * Check if we are _not_ on a detached HEAD, i.e. if there is a
 	 * current branch.

index 6eb910d6f0c..8e754b769e1 100644
@@ -4058,6 +4058,14 @@ static int record_conflicted_index_entries(struct merge_options *opt)
 	if (strmap_empty(&opt->priv->conflicted))
 		return 0;
 
+	/*
+	 * We are in a conflicted state. These conflicts might be inside
+	 * sparse-directory entries, so expand the index preemtively.
+	 * Also, we set original_cache_nr below, but that might change if
+	 * index_name_pos() calls ask for paths within sparse directories.
+	 */
+	ensure_full_index(index);
+
 	/* If any entries have skip_worktree set, we'll have to check 'em out */
 	state.force = 1;
 	state.quiet = 1;

index 3355d50e8ad..1f563cd6874 100644
@@ -3750,6 +3750,9 @@ int merge_recursive(struct merge_options *opt,
 	assert(opt->ancestor == NULL ||
 	       !strcmp(opt->ancestor, "constructed merge base"));
 
+	prepare_repo_settings(opt->repo);
+	opt->repo->settings.command_requires_full_index = 1;
+
 	if (merge_start(opt, repo_get_commit_tree(opt->repo, h1)))
 		return -1;
 	clean = merge_recursive_internal(opt, h1, h2, merge_bases, result);

index 3e01e70fa0b..781ebd9a656 100755
@@ -52,7 +52,7 @@ test_expect_success 'setup' '
 		git checkout -b base &&
 		for dir in folder1 folder2 deep
 		do
-			git checkout -b update-$dir &&
+			git checkout -b update-$dir base &&
 			echo "updated $dir" >$dir/a &&
 			git commit -a -m "update $dir" || return 1
 		done &&

@@ -652,7 +652,11 @@ test_expect_success 'sparse-index is not expanded' '
 	echo >>sparse-index/extra.txt &&
 	ensure_not_expanded add extra.txt &&
 	echo >>sparse-index/untracked.txt &&
-	ensure_not_expanded add .
+	ensure_not_expanded add . &&
+
+	ensure_not_expanded checkout -f update-deep &&
+	ensure_not_expanded merge -s ort -m merge update-folder1 &&
+	ensure_not_expanded merge -s ort -m merge update-folder2
 '
 
 # NEEDSWORK: a sparse-checkout behaves differently from a full checkout

gitgitgadget

What about resolve, octopus, subtree (which technically could be implemented via either recursive or ort, such fun...) or a user-defined strategy?

resolve and octopus would absolutely need a full index. subtree would if implemented via merge-recursive, and not if implemented via merge-ort.

I'm not sure what to assume about user-defined strategies; I guess for safety reasons and backward compatibility, we should always expand? Or maybe there are no backward compatibility concerns since no one who uses a sparse-index will attempt to use any pre-existing external merge strategies (are there even any known ones in the wild or is this still a theoretical capability?), and we can assume they will only use ones written in the future? Hmm...

From reading the patch below, this is specific to ort, but that wasn't clear on reading the commit message.

From: Derrick Stolee <[email protected]>

Merge conflicts happen often enough to want to avoid expanding a sparse index when they happen, as long as those conflicts are within the sparse-checkout cone. If a conflict exists outside of the sparse-checkout cone, then we still need to expand before iterating over the index entries. This is critical to do in advance because of how the original_cache_nr is tracked to allow inserting and replacing cache entries.

Iterate over the conflicted files and check if any paths are outside of the sparse-checkout cone. If so, then expand the full index.

Add a test that demonstrates that we do not expand the index, even when we hit a conflict within the sparse-checkout cone.

---
 merge-ort.c                              | 14 ++++++++---
 t/t1092-sparse-checkout-compatibility.sh | 30 ++++++++++++++++++++++--
 2 files changed, 39 insertions(+), 5 deletions(-)

index 8e754b769e1..590e52058cf 100644
@@ -36,6 +36,7 @@
 #include "tree.h"
 #include "unpack-trees.h"
 #include "xdiff-interface.h"
+#include "dir.h"
 
 /*
  * We have many arrays of size 3.  Whenever we have such an array, the

@@ -4060,11 +4061,18 @@ static int record_conflicted_index_entries(struct merge_options *opt)
 
 	/*
 	 * We are in a conflicted state. These conflicts might be inside
-	 * sparse-directory entries, so expand the index preemtively.
-	 * Also, we set original_cache_nr below, but that might change if
+	 * sparse-directory entries, so check if any entries are outside
+	 * of the sparse-checkout cone preemptively.
+	 *
+	 * We set original_cache_nr below, but that might change if
 	 * index_name_pos() calls ask for paths within sparse directories.
 	 */
-	ensure_full_index(index);
+	strmap_for_each_entry(&opt->priv->conflicted, &iter, e) {
+		if (!path_in_sparse_checkout(e->key, index)) {
+			ensure_full_index(index);
+			break;
+		}
+	}
 
 	/* If any entries have skip_worktree set, we'll have to check 'em out */
 	state.force = 1;

index 781ebd9a656..a0ed2bec574 100755
@@ -622,8 +622,21 @@ test_expect_success 'sparse-index is expanded and converted back' '
 ensure_not_expanded () {
 	rm -f trace2.txt &&
 	echo >>sparse-index/untracked.txt &&
-	GIT_TRACE2_EVENT="$(pwd)/trace2.txt" GIT_TRACE2_EVENT_NESTING=10 \
-		git -C sparse-index "$@" &&
+
+	if test "$1" = "!"
+	then
+		shift &&
+		(
+			GIT_TRACE2_EVENT="$(pwd)/trace2.txt" &&
+			GIT_TRACE2_EVENT_NESTING=10 &&
+			export GIT_TRACE2_EVENT &&
+			export GIT_TRACE2_EVENT_NESTING &&
+			test_must_fail git -C sparse-index "$@" || return 1
+		)
+	else
+		GIT_TRACE2_EVENT="$(pwd)/trace2.txt" GIT_TRACE2_EVENT_NESTING=10 \
+			git -C sparse-index "$@" || return 1
+	fi &&
 	test_region ! index ensure_full_index trace2.txt
 }
 

@@ -659,6 +672,19 @@ test_expect_success 'sparse-index is not expanded' '
 	ensure_not_expanded merge -s ort -m merge update-folder2
 '
 
+test_expect_success 'sparse-index is not expanded: merge conflict in cone' '
+	init_repos &&
+
+	for side in right left
+	do
+		git -C sparse-index checkout -b expand-$side base &&
+		echo $side >sparse-index/deep/a &&
+		git -C sparse-index commit -a -m "$side" || return 1
+	done &&
+
+	ensure_not_expanded ! merge -m merged expand-right
+'
+
 # 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' '

gitgitgadget

If I had read ahead a little bit instead of responding as I went.... :-)

Awesome to see this.

          test_must_fail env \
                  GIT_TRACE2_EVENT="$(pwd)/trace2.txt"
GIT_TRACE2_EVENT_NESTING=10 \
                          git -C sparse-index "$@" || return 1

From: Derrick Stolee <[email protected]>

Add tests to check that cherry-pick and rebase behave the same in the sparse-index case as in the full index cases.

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

index a0ed2bec574..a52d2edda54 100755
@@ -486,14 +486,17 @@ test_expect_success 'checkout and reset (mixed) [sparse]' '
 	test_sparse_match git reset update-folder2
 '
 
-test_expect_success 'merge' '
+test_expect_success 'merge, cherry-pick, and rebase' '
 	init_repos &&
 
-	test_all_match git checkout -b merge update-deep &&
-	test_all_match git merge -m "folder1" update-folder1 &&
-	test_all_match git rev-parse HEAD^{tree} &&
-	test_all_match git merge -m "folder2" update-folder2 &&
-	test_all_match git rev-parse HEAD^{tree}
+	for OPERATION in "merge -s ort -m merge" cherry-pick rebase
+	do
+		test_all_match git checkout -B temp update-deep &&
+		test_all_match git $OPERATION update-folder1 &&
+		test_all_match git rev-parse HEAD^{tree} &&
+		test_all_match git $OPERATION update-folder2 &&
+		test_all_match git rev-parse HEAD^{tree} || return 1
+	done
 '
 
 # NEEDSWORK: This test is documenting current behavior, but that

gitgitgadget

From: Derrick Stolee <[email protected]>

The hard work was already done with 'git merge' and the ORT strategy. Just add extra tests to see that we get the expected results in the non-conflict cases.

---
 builtin/rebase.c                         |  6 ++++
 builtin/revert.c                         |  3 ++
 t/t1092-sparse-checkout-compatibility.sh | 41 ++++++++++++++++++++++--
 3 files changed, 47 insertions(+), 3 deletions(-)

index 33e09619005..27433d7c5a2 100644
@@ -559,6 +559,9 @@ int cmd_rebase__interactive(int argc, const char **argv, const char *prefix)
 	argc = parse_options(argc, argv, prefix, options,
 			builtin_rebase_interactive_usage, PARSE_OPT_KEEP_ARGV0);
 
+	prepare_repo_settings(the_repository);
+	the_repository->settings.command_requires_full_index = 0;
+
 	if (!is_null_oid(&squash_onto))
 		opts.squash_onto = &squash_onto;
 

@@ -1430,6 +1433,9 @@ int cmd_rebase(int argc, const char **argv, const char *prefix)
 		usage_with_options(builtin_rebase_usage,
 				   builtin_rebase_options);
 
+	prepare_repo_settings(the_repository);
+	the_repository->settings.command_requires_full_index = 0;
+
 	options.allow_empty_message = 1;
 	git_config(rebase_config, &options);
 	/* options.gpg_sign_opt will be either "-S" or NULL */

index 237f2f18d4c..6c4c22691bd 100644
@@ -136,6 +136,9 @@ static int run_sequencer(int argc, const char **argv, struct replay_opts *opts)
 			PARSE_OPT_KEEP_ARGV0 |
 			PARSE_OPT_KEEP_UNKNOWN);
 
+	prepare_repo_settings(the_repository);
+	the_repository->settings.command_requires_full_index = 0;
+
 	/* implies allow_empty */
 	if (opts->keep_redundant_commits)
 		opts->allow_empty = 1;

gitgitgadget

:-)

This series integrates the sparse index with commands that perform merges such as 'git merge', 'git cherry-pick', 'git revert' (free with cherry-pick), and 'git rebase'.

When the ORT merge strategy is enabled, this allows most merges to succeed without expanding the sparse index, leading to significant performance gains. I tested these changes against an internal monorepo with over 2 million paths at HEAD but with a sparse-checkout that only has ~60,000 files within the sparse-checkout cone. 'git merge' commands went from 5-6 seconds to 0.750-1.250s.

In the case of the recursive merge strategy, the sparse index is expanded before the recursive algorithm proceeds. We expect that this is as good as we can get with that strategy. When the strategy shifts to ORT as the default, then this will not be a problem except for users who decide to change the behavior.

Most of the hard work was done by previous series, such as ds/sparse-index-ignored-files (which this series is based on).

Updates in V2
=============

* The tests no longer specify GIT_TEST_MERGE_ALGORITHM or directly reference "-s ort". By relaxing this condition, I found an issue with 'git cherry-pick' and 'git rebase' when using the 'recursive' algorithm which is fixed in a new patch.

* Use the pul.twohead config to specify the ORT merge algorithm to avoid expanding the sparse index when that is what we are testing.

* Corrected some misstatements in my commit messages.

Thanks, -Stolee

Derrick Stolee (6):
diff: ignore sparse paths in diffstat
merge: make sparse-aware with ORT
merge-ort: expand only for out-of-cone conflicts
t1092: add cherry-pick, rebase tests
sequencer: ensure full index if not ORT strategy
sparse-index: integrate with cherry-pick and rebase

 builtin/merge.c                          |  3 +
 builtin/rebase.c                         |  6 ++
 builtin/revert.c                         |  3 +
 diff.c                                   |  8 +++
 merge-ort.c                              | 15 ++++
 merge-recursive.c                        |  3 +
 sequencer.c                              |  9 +++
 t/t1092-sparse-checkout-compatibility.sh | 92 +++++++++++++++++++++---
 8 files changed, 129 insertions(+), 10 deletions(-)

base-commit: 8d55a6ba2fdf64cee4eb51f3cb6f9808bd0b7505
Published-As: https://github.com/gitgitgadget/git/releases/tag/pr-1019%2Fderrickstolee%2Fsparse-index%2Fmerge-v2
Fetch-It-Via: git fetch https://github.com/gitgitgadget/git pr-1019/derrickstolee/sparse-index/merge-v2
Pull-Request: https://github.com/gitgitgadget/git/pull/1019

Range-diff vs v1:

 1:  7cad9eee90b < -:  ----------- t1092: use ORT merge strategy
 2:  9f50f11d394 ! 1:  c5ae705648c diff: ignore sparse paths in diffstat

@@ Commit message
diff: ignore sparse paths in diffstat

The diff_populate_filespec() method is used to describe the diff after a
- merge operation is complete, especially when a conflict appears. In
- order to avoid expanding a sparse index, the reuse_worktree_file() needs
- to be adapted to ignore files that are outside of the sparse-checkout
- cone. The file names and OIDs used for this check come from the merged
- tree in the case of the ORT strategy, not the index, hence the ability
- to look into these paths without having already expanded the index.
+ merge operation is complete. In order to avoid expanding a sparse index,
+ the reuse_worktree_file() needs to be adapted to ignore files that are
+ outside of the sparse-checkout cone. The file names and OIDs used for
+ this check come from the merged tree in the case of the ORT strategy,
+ not the index, hence the ability to look into these paths without having
+ already expanded the index.
+
+ The work done by reuse_worktree_file() is only an optimization, and
+ requires the file being on disk for it to be of any value. Thus, it is
+ safe to exit the method early if we do not expect the file on disk.

@@ diff.c
#ifdef NO_FAST_WORKING_DIRECTORY
#define FAST_WORKING_DIRECTORY 0
@@ diff.c: static int reuse_worktree_file(struct index_state *istate,
- if (!FAST_WORKING_DIRECTORY && !want_file && has_object_pack(oid))
+ if (!want_file && would_convert_to_git(istate, name))
return 0;

+ /*
@@ diff.c: static int reuse_worktree_file(struct index_state *istate,
+ if (!path_in_sparse_checkout(name, istate))
+ return 0;
+
- /*
- * Similarly, if we'd have to convert the file contents anyway, that
- * makes the optimization not worthwhile.
+ len = strlen(name);
+ pos = index_name_pos(istate, name, len);
+ if (pos < 0)
3: 4c1104a0dd3 ! 2: bb150483bcf merge: make sparse-aware with ORT
@@ Commit message
method. We expect sparse-index users to also have the 'ort' strategy enabled.

- 2. If the merge results in a conflicted file, then we expand the index
- before updating the working tree. The loop that iterates over the
- worktree replaces index entries and tracks 'origintal_cache_nr' which
- can become completely wrong if the index expands in the middle of the
- operation. This safety valve is important before that loop starts. A
- later change will focus this to only expand if we indeed have a
- conflict outside of the sparse-checkout cone.
+ 2. With the 'ort' strategy, if the merge results in a conflicted file,
+ then we expand the index before updating the working tree. The loop
+ that iterates over the worktree replaces index entries and tracks
+ 'origintal_cache_nr' which can become completely wrong if the index
+ expands in the middle of the operation. This safety valve is
+ important before that loop starts. A later change will focus this
+ to only expand if we indeed have a conflict outside of the
+ sparse-checkout cone.
+
+ 3. Other merge strategies are executed as a 'git merge-X' subcommand,
+ and those strategies are currently protected with the
+ 'command_requires_full_index' guard.

Some test updates are required, including a mistaken 'git checkout -b' that did not specify the base branch, causing merges to be fast-forward
@@ t/t1092-sparse-checkout-compatibility.sh: test_expect_success 'sparse-index is n
+ ensure_not_expanded add . &&
+
+ ensure_not_expanded checkout -f update-deep &&
-+ ensure_not_expanded merge -s ort -m merge update-folder1 &&
-+ ensure_not_expanded merge -s ort -m merge update-folder2
++ (
++ sane_unset GIT_TEST_MERGE_ALGORITHM &&
++ git -C sparse-index config pull.twohead ort &&
++ ensure_not_expanded merge -m merge update-folder1 &&
++ ensure_not_expanded merge -m merge update-folder2
++ )
'

# NEEDSWORK: a sparse-checkout behaves differently from a full checkout
4: e47b15554e3 ! 3: 815b1b1cfbf merge-ort: expand only for out-of-cone conflicts

     @@ Commit message
          Signed-off-by: Derrick Stolee <[email protected]>
      
       ## merge-ort.c ##
     -@@
     - #include "tree.h"
     - #include "unpack-trees.h"
     - #include "xdiff-interface.h"
     -+#include "dir.h"
     - 
     - /*
     -  * We have many arrays of size 3.  Whenever we have such an array, the
      @@ merge-ort.c: static int record_conflicted_index_entries(struct merge_options *opt)
       
       	/*
     @@ t/t1092-sparse-checkout-compatibility.sh: test_expect_success 'sparse-index is e
      +	if test "$1" = "!"
      +	then
      +		shift &&
     -+		(
     -+			GIT_TRACE2_EVENT="$(pwd)/trace2.txt" &&
     -+			GIT_TRACE2_EVENT_NESTING=10 &&
     -+			export GIT_TRACE2_EVENT &&
     -+			export GIT_TRACE2_EVENT_NESTING &&
     -+			test_must_fail git -C sparse-index "$@" || return 1
     -+		)
     ++		test_must_fail env \
     ++			GIT_TRACE2_EVENT="$(pwd)/trace2.txt" GIT_TRACE2_EVENT_NESTING=10 \
     ++			git -C sparse-index "$@" || return 1
      +	else
      +		GIT_TRACE2_EVENT="$(pwd)/trace2.txt" GIT_TRACE2_EVENT_NESTING=10 \
      +			git -C sparse-index "$@" || return 1
     @@ t/t1092-sparse-checkout-compatibility.sh: test_expect_success 'sparse-index is e
       }
       
      @@ t/t1092-sparse-checkout-compatibility.sh: test_expect_success 'sparse-index is not expanded' '
     - 	ensure_not_expanded merge -s ort -m merge update-folder2
     + 	)
       '
       
      +test_expect_success 'sparse-index is not expanded: merge conflict in cone' '
     @@ t/t1092-sparse-checkout-compatibility.sh: test_expect_success 'sparse-index is n
      +		git -C sparse-index commit -a -m "$side" || return 1
      +	done &&
      +
     -+	ensure_not_expanded ! merge -m merged expand-right
     ++	(
     ++		sane_unset GIT_TEST_MERGE_ALGORITHM &&
     ++		git -C sparse-index config pull.twohead ort &&
     ++		ensure_not_expanded ! merge -m merged expand-right
     ++	)
      +'
      +
       # NEEDSWORK: a sparse-checkout behaves differently from a full checkout

5: ca23bf38bd9 ! 4: 8032154bc8a t1092: add cherry-pick, rebase tests
@@ Commit message
t1092: add cherry-pick, rebase tests

Add tests to check that cherry-pick and rebase behave the same in the
- sparse-index case as in the full index cases.
+ sparse-index case as in the full index cases. These tests are agnostic
+ to GIT_TEST_MERGE_ALGORITHM, so a full CI test suite will check both the
+ 'ort' and 'recursive' strategies on this test.

@@ t/t1092-sparse-checkout-compatibility.sh: test_expect_success 'checkout and rese
- test_all_match git rev-parse HEAD^{tree} &&
- test_all_match git merge -m "folder2" update-folder2 &&
- test_all_match git rev-parse HEAD^{tree}
-+ for OPERATION in "merge -s ort -m merge" cherry-pick rebase
++ for OPERATION in "merge -m merge" cherry-pick rebase
+ do
+ test_all_match git checkout -B temp update-deep &&
+ test_all_match git $OPERATION update-folder1 &&

 -:  ----------- > 5:  90ac85500b8 sequencer: ensure full index if not ORT strategy
 6:  350ed86a453 ! 6:  df4bbec744f sparse-index: integrate with cherry-pick and rebase
     @@ t/t1092-sparse-checkout-compatibility.sh: test_expect_success 'merge with confli
       	init_repos &&
       
      @@ t/t1092-sparse-checkout-compatibility.sh: test_expect_success 'sparse-index is not expanded' '
     - 	echo >>sparse-index/untracked.txt &&
     - 	ensure_not_expanded add . &&
     - 
     --	ensure_not_expanded checkout -f update-deep &&
     --	ensure_not_expanded merge -s ort -m merge update-folder1 &&
     --	ensure_not_expanded merge -s ort -m merge update-folder2
     -+	for OPERATION in "merge -s ort -m merge" cherry-pick rebase
     -+	do
     -+		ensure_not_expanded checkout -f -B temp update-deep &&
     -+		ensure_not_expanded $OPERATION update-folder1 &&
     -+		ensure_not_expanded $OPERATION update-folder2 || return 1
     -+	done
     + 	(
     + 		sane_unset GIT_TEST_MERGE_ALGORITHM &&
     + 		git -C sparse-index config pull.twohead ort &&
     +-		ensure_not_expanded merge -m merge update-folder1 &&
     +-		ensure_not_expanded merge -m merge update-folder2
     ++		for OPERATION in "merge -m merge" cherry-pick rebase
     ++		do
     ++			ensure_not_expanded merge -m merge update-folder1 &&
     ++			ensure_not_expanded merge -m merge update-folder2 || return 1
     ++		done
     + 	)
       '
       
     - test_expect_success 'sparse-index is not expanded: merge conflict in cone' '

gitgitgadget

From: Derrick Stolee <[email protected]>

The diff_populate_filespec() method is used to describe the diff after a merge operation is complete. In order to avoid expanding a sparse index, the reuse_worktree_file() needs to be adapted to ignore files that are outside of the sparse-checkout cone. The file names and OIDs used for this check come from the merged tree in the case of the ORT strategy, not the index, hence the ability to look into these paths without having already expanded the index.

The work done by reuse_worktree_file() is only an optimization, and requires the file being on disk for it to be of any value. Thus, it is safe to exit the method early if we do not expect the file on disk.

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

index a8113f17070..c8f530ffdbe 100644
@@ -26,6 +26,7 @@
 #include "parse-options.h"
 #include "help.h"
 #include "promisor-remote.h"
+#include "dir.h"
 
 #ifdef NO_FAST_WORKING_DIRECTORY
 #define FAST_WORKING_DIRECTORY 0

@@ -3907,6 +3908,13 @@ static int reuse_worktree_file(struct index_state *istate,
 	if (!want_file && would_convert_to_git(istate, name))
 		return 0;
 
+	/*
+	 * If this path does not match our sparse-checkout definition,
+	 * then the file will not be in the working directory.
+	 */
+	if (!path_in_sparse_checkout(name, istate))
+		return 0;
+
 	len = strlen(name);
 	pos = index_name_pos(istate, name, len);
 	if (pos < 0)

gitgitgadget

From: Derrick Stolee <[email protected]>

Allow 'git merge' to operate without expanding a sparse index, at least not immediately. The index still will be expanded in a few cases:

1. If the merge strategy is 'recursive', then we enable command_requires_full_index at the start of the merge_recursive() method. We expect sparse-index users to also have the 'ort' strategy enabled.

2. With the 'ort' strategy, if the merge results in a conflicted file, then we expand the index before updating the working tree. The loop that iterates over the worktree replaces index entries and tracks 'origintal_cache_nr' which can become completely wrong if the index expands in the middle of the operation. This safety valve is important before that loop starts. A later change will focus this to only expand if we indeed have a conflict outside of the sparse-checkout cone.

3. Other merge strategies are executed as a 'git merge-X' subcommand, and those strategies are currently protected with the 'command_requires_full_index' guard.

Some test updates are required, including a mistaken 'git checkout -b' that did not specify the base branch, causing merges to be fast-forward merges.

---
 builtin/merge.c                          |  3 +++
 merge-ort.c                              |  8 ++++++++
 merge-recursive.c                        |  3 +++
 t/t1092-sparse-checkout-compatibility.sh | 12 ++++++++++--
 4 files changed, 24 insertions(+), 2 deletions(-)

index 22f23990b37..926de328fbb 100644
@@ -1276,6 +1276,9 @@ int cmd_merge(int argc, const char **argv, const char *prefix)
 	if (argc == 2 && !strcmp(argv[1], "-h"))
 		usage_with_options(builtin_merge_usage, builtin_merge_options);
 
+	prepare_repo_settings(the_repository);
+	the_repository->settings.command_requires_full_index = 0;
+
 	/*
 	 * Check if we are _not_ on a detached HEAD, i.e. if there is a
 	 * current branch.

index 6eb910d6f0c..8e754b769e1 100644
@@ -4058,6 +4058,14 @@ static int record_conflicted_index_entries(struct merge_options *opt)
 	if (strmap_empty(&opt->priv->conflicted))
 		return 0;
 
+	/*
+	 * We are in a conflicted state. These conflicts might be inside
+	 * sparse-directory entries, so expand the index preemtively.
+	 * Also, we set original_cache_nr below, but that might change if
+	 * index_name_pos() calls ask for paths within sparse directories.
+	 */
+	ensure_full_index(index);
+
 	/* If any entries have skip_worktree set, we'll have to check 'em out */
 	state.force = 1;
 	state.quiet = 1;

index 3355d50e8ad..1f563cd6874 100644
@@ -3750,6 +3750,9 @@ int merge_recursive(struct merge_options *opt,
 	assert(opt->ancestor == NULL ||
 	       !strcmp(opt->ancestor, "constructed merge base"));
 
+	prepare_repo_settings(opt->repo);
+	opt->repo->settings.command_requires_full_index = 1;
+
 	if (merge_start(opt, repo_get_commit_tree(opt->repo, h1)))
 		return -1;
 	clean = merge_recursive_internal(opt, h1, h2, merge_bases, result);

index ddc86bb4152..dc56252865c 100755
@@ -47,7 +47,7 @@ test_expect_success 'setup' '
 		git checkout -b base &&
 		for dir in folder1 folder2 deep
 		do
-			git checkout -b update-$dir &&
+			git checkout -b update-$dir base &&
 			echo "updated $dir" >$dir/a &&
 			git commit -a -m "update $dir" || return 1
 		done &&

@@ -647,7 +647,15 @@ test_expect_success 'sparse-index is not expanded' '
 	echo >>sparse-index/extra.txt &&
 	ensure_not_expanded add extra.txt &&
 	echo >>sparse-index/untracked.txt &&
-	ensure_not_expanded add .
+	ensure_not_expanded add . &&
+
+	ensure_not_expanded checkout -f update-deep &&
+	(
+		sane_unset GIT_TEST_MERGE_ALGORITHM &&
+		git -C sparse-index config pull.twohead ort &&
+		ensure_not_expanded merge -m merge update-folder1 &&
+		ensure_not_expanded merge -m merge update-folder2
+	)
 '
 
 # NEEDSWORK: a sparse-checkout behaves differently from a full checkout

gitgitgadget

Oh, indeed, it appears ag/merge-strategies-in-c didn't complete but was discarded, as per the July 6 "What's cooking in git.git" email. Well, that certainly makes things easier for you; thanks for mentioning them in this item #3.

...

Sorry, this comment is edited in a later patch and I fixed it there. Will fix here, too.

That's a better pattern. It's not technically _required_ for these tests because the repositories are completely rewritten at the start of each new test, but it's best to be a good example.

I don't set GIT_TEST_MERGE_ALGORITHM at the beginning of the file so the rest of the tests are covered with both 'ort' and 'recursive' in the CI test suite.

Using the config more carefully matches how I expect the 'ort' strategy to be specified in practice (very temporarily, as it will soon be the default).

Thanks,
-Stolee

Actually, test_config runs test_when_finished, and that results in the following message and failure on macOS and Windows:

BUG 'test_when_finished does nothing in a subshell'

So, I'll leave this as-is.

Thanks,
-Stolee

From: Derrick Stolee <[email protected]>

Merge conflicts happen often enough to want to avoid expanding a sparse index when they happen, as long as those conflicts are within the sparse-checkout cone. If a conflict exists outside of the sparse-checkout cone, then we still need to expand before iterating over the index entries. This is critical to do in advance because of how the original_cache_nr is tracked to allow inserting and replacing cache entries.

Iterate over the conflicted files and check if any paths are outside of the sparse-checkout cone. If so, then expand the full index.

Add a test that demonstrates that we do not expand the index, even when we hit a conflict within the sparse-checkout cone.

---
 merge-ort.c                              | 13 +++++++---
 t/t1092-sparse-checkout-compatibility.sh | 30 ++++++++++++++++++++++--
 2 files changed, 38 insertions(+), 5 deletions(-)

index 8e754b769e1..805f7c41397 100644
@@ -4060,11 +4060,18 @@ static int record_conflicted_index_entries(struct merge_options *opt)
 
 	/*
 	 * We are in a conflicted state. These conflicts might be inside
-	 * sparse-directory entries, so expand the index preemtively.
-	 * Also, we set original_cache_nr below, but that might change if
+	 * sparse-directory entries, so check if any entries are outside
+	 * of the sparse-checkout cone preemptively.
+	 *
+	 * We set original_cache_nr below, but that might change if
 	 * index_name_pos() calls ask for paths within sparse directories.
 	 */
-	ensure_full_index(index);
+	strmap_for_each_entry(&opt->priv->conflicted, &iter, e) {
+		if (!path_in_sparse_checkout(e->key, index)) {
+			ensure_full_index(index);
+			break;
+		}
+	}
 
 	/* If any entries have skip_worktree set, we'll have to check 'em out */
 	state.force = 1;

index dc56252865c..38afdf689a2 100755
@@ -617,8 +617,17 @@ test_expect_success 'sparse-index is expanded and converted back' '
 ensure_not_expanded () {
 	rm -f trace2.txt &&
 	echo >>sparse-index/untracked.txt &&
-	GIT_TRACE2_EVENT="$(pwd)/trace2.txt" GIT_TRACE2_EVENT_NESTING=10 \
-		git -C sparse-index "$@" &&
+
+	if test "$1" = "!"
+	then
+		shift &&
+		test_must_fail env \
+			GIT_TRACE2_EVENT="$(pwd)/trace2.txt" GIT_TRACE2_EVENT_NESTING=10 \
+			git -C sparse-index "$@" || return 1
+	else
+		GIT_TRACE2_EVENT="$(pwd)/trace2.txt" GIT_TRACE2_EVENT_NESTING=10 \
+			git -C sparse-index "$@" || return 1
+	fi &&
 	test_region ! index ensure_full_index trace2.txt
 }
 

@@ -658,6 +667,23 @@ test_expect_success 'sparse-index is not expanded' '
 	)
 '
 
+test_expect_success 'sparse-index is not expanded: merge conflict in cone' '
+	init_repos &&
+
+	for side in right left
+	do
+		git -C sparse-index checkout -b expand-$side base &&
+		echo $side >sparse-index/deep/a &&
+		git -C sparse-index commit -a -m "$side" || return 1
+	done &&
+
+	(
+		sane_unset GIT_TEST_MERGE_ALGORITHM &&
+		git -C sparse-index config pull.twohead ort &&
+		ensure_not_expanded ! merge -m merged expand-right
+	)
+'
+
 # 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' '

gitgitgadget

...

Yes. In fact, since I _stopped_ setting GIT_TEST_MERGE_ALGORITHM at the start of the file since the previous version, I found and fixed a bug which forms the new Patch 5 (sequencer: ensure full index if not ORT strategy).

Thanks,
-Stolee

From: Derrick Stolee <[email protected]>

Add tests to check that cherry-pick and rebase behave the same in the sparse-index case as in the full index cases. These tests are agnostic to GIT_TEST_MERGE_ALGORITHM, so a full CI test suite will check both the 'ort' and 'recursive' strategies on this test.

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

index 38afdf689a2..60d7400d014 100755
@@ -481,14 +481,17 @@ test_expect_success 'checkout and reset (mixed) [sparse]' '
 	test_sparse_match git reset update-folder2
 '
 
-test_expect_success 'merge' '
+test_expect_success 'merge, cherry-pick, and rebase' '
 	init_repos &&
 
-	test_all_match git checkout -b merge update-deep &&
-	test_all_match git merge -m "folder1" update-folder1 &&
-	test_all_match git rev-parse HEAD^{tree} &&
-	test_all_match git merge -m "folder2" update-folder2 &&
-	test_all_match git rev-parse HEAD^{tree}
+	for OPERATION in "merge -m merge" cherry-pick rebase
+	do
+		test_all_match git checkout -B temp update-deep &&
+		test_all_match git $OPERATION update-folder1 &&
+		test_all_match git rev-parse HEAD^{tree} &&
+		test_all_match git $OPERATION update-folder2 &&
+		test_all_match git rev-parse HEAD^{tree} || return 1
+	done
 '
 
 # NEEDSWORK: This test is documenting current behavior, but that

gitgitgadget

From: Derrick Stolee <[email protected]>

The sequencer is used by 'cherry-pick' and 'rebase' to sequence a list of operations that modify the index. Since we intend to remove the need for 'command_requires_full_index', we need to ensure the sparse index is expanded every time it is written to disk between these steps. That is, unless the merge strategy is 'ort' where the index can remain sparse throughout.

There are two main places to be extra careful about a full index:

1. Right before calling merge_trees(), ensure the index is full. This happens within an 'else' where the 'if' block checks if the 'ort' strategy is selected.

2. During read_and_refresh_cache(), the index might be written to disk and converted to sparse in the process. Ensure it expands back to full afterwards by checking if the strategy is _not_ 'ort'. This 'if' statement is the logical negation of the 'if' in item (1).

---
 sequencer.c | 9 +++++++++
 1 file changed, 9 insertions(+)

index 7f07cd00f3f..228bc089d22 100644
@@ -652,6 +652,7 @@ static int do_recursive_merge(struct repository *r,
 		merge_switch_to_result(&o, head_tree, &result, 1, show_output);
 		clean = result.clean;
 	} else {
+		ensure_full_index(r->index);
 		clean = merge_trees(&o, head_tree, next_tree, base_tree);
 		if (is_rebase_i(opts) && clean <= 0)
 			fputs(o.obuf.buf, stdout);

@@ -2346,6 +2347,7 @@ static int read_and_refresh_cache(struct repository *r,
 			_(action_name(opts)));
 	}
 	refresh_index(r->index, REFRESH_QUIET|REFRESH_UNMERGED, NULL, NULL, NULL);
+
 	if (index_fd >= 0) {
 		if (write_locked_index(r->index, &index_lock,
 				       COMMIT_LOCK | SKIP_IF_UNCHANGED)) {

@@ -2353,6 +2355,13 @@ static int read_and_refresh_cache(struct repository *r,
 				_(action_name(opts)));
 		}
 	}
+
+	/*
+	 * If we are resolving merges in any way other than "ort", then
+	 * expand the sparse index.
+	 */
+	if (opts->strategy && strcmp(opts->strategy, "ort"))
+		ensure_full_index(r->index);
 	return 0;
 }
 

gitgitgadget

From: Derrick Stolee <[email protected]>

The hard work was already done with 'git merge' and the ORT strategy. Just add extra tests to see that we get the expected results in the non-conflict cases.

---
 builtin/rebase.c                         |  6 ++++
 builtin/revert.c                         |  3 ++
 t/t1092-sparse-checkout-compatibility.sh | 39 ++++++++++++++++++++++--
 3 files changed, 46 insertions(+), 2 deletions(-)

index 33e09619005..27433d7c5a2 100644
@@ -559,6 +559,9 @@ int cmd_rebase__interactive(int argc, const char **argv, const char *prefix)
 	argc = parse_options(argc, argv, prefix, options,
 			builtin_rebase_interactive_usage, PARSE_OPT_KEEP_ARGV0);
 
+	prepare_repo_settings(the_repository);
+	the_repository->settings.command_requires_full_index = 0;
+
 	if (!is_null_oid(&squash_onto))
 		opts.squash_onto = &squash_onto;
 

@@ -1430,6 +1433,9 @@ int cmd_rebase(int argc, const char **argv, const char *prefix)
 		usage_with_options(builtin_rebase_usage,
 				   builtin_rebase_options);
 
+	prepare_repo_settings(the_repository);
+	the_repository->settings.command_requires_full_index = 0;
+
 	options.allow_empty_message = 1;
 	git_config(rebase_config, &options);
 	/* options.gpg_sign_opt will be either "-S" or NULL */

index 237f2f18d4c..6c4c22691bd 100644
@@ -136,6 +136,9 @@ static int run_sequencer(int argc, const char **argv, struct replay_opts *opts)
 			PARSE_OPT_KEEP_ARGV0 |
 			PARSE_OPT_KEEP_UNKNOWN);
 
+	prepare_repo_settings(the_repository);
+	the_repository->settings.command_requires_full_index = 0;
+
 	/* implies allow_empty */
 	if (opts->keep_redundant_commits)
 		opts->allow_empty = 1;

index 60d7400d014..bbc6de712c4 100755
@@ -527,6 +527,38 @@ test_expect_success 'merge with conflict outside cone' '
 	test_all_match git rev-parse HEAD^{tree}
 '
 
+test_expect_success 'cherry-pick/rebase with conflict outside cone' '
+	init_repos &&
+
+	for OPERATION in cherry-pick rebase
+	do
+		test_all_match git checkout -B tip &&
+		test_all_match git reset --hard merge-left &&
+		test_all_match git status --porcelain=v2 &&
+		test_all_match test_must_fail git $OPERATION merge-right &&
+		test_all_match git status --porcelain=v2 &&
+
+		# Resolve the conflict in different ways:
+		# 1. Revert to the base
+		test_all_match git checkout base -- deep/deeper2/a &&
+		test_all_match git status --porcelain=v2 &&
+
+		# 2. Add the file with conflict markers
+		test_all_match git add folder1/a &&
+		test_all_match git status --porcelain=v2 &&
+
+		# 3. Rename the file to another sparse filename and
+		#    accept conflict markers as resolved content.
+		run_on_all mv folder2/a folder2/z &&
+		test_all_match git add folder2 &&
+		test_all_match git status --porcelain=v2 &&
+
+		test_all_match git $OPERATION --continue &&
+		test_all_match git status --porcelain=v2 &&
+		test_all_match git rev-parse HEAD^{tree} || return 1
+	done
+'
+
 test_expect_success 'merge with outside renames' '
 	init_repos &&
 

@@ -665,8 +697,11 @@ test_expect_success 'sparse-index is not expanded' '
 	(
 		sane_unset GIT_TEST_MERGE_ALGORITHM &&
 		git -C sparse-index config pull.twohead ort &&
-		ensure_not_expanded merge -m merge update-folder1 &&
-		ensure_not_expanded merge -m merge update-folder2
+		for OPERATION in "merge -m merge" cherry-pick rebase
+		do
+			ensure_not_expanded merge -m merge update-folder1 &&
+			ensure_not_expanded merge -m merge update-folder2 || return 1
+		done
 	)
 '
 

gitgitgadget

pull.twohead, not pul.twohead.

I'm curious, though, why use it instead of just setting GIT_TEST_MERGE_ALGORITHM=ort? That'd seem to avoid the need for the explicit subshells and the sane_unset calls.

I read over v2. Other than some minor questions about whether using GIT_TEST_MERGE_ALGORITHM=ort would be easier, and a typo still present from v1, the series looks good to me.

...

This describes why the tests no longer use GIT_TEST_MERGE_ALGORITHM at the top. It improves coverage in case users opt-out of ORT. Instead,

We use this config option to specify when we _really care_ about the ORT strategy as it is necessary to avoid expanding the full index.

Sorry about the typo, as I fixed it in Patch 3 but not Patch 2. I will fix these in v3 after I send a v5 of the ignored files series.

Thanks,
-Stolee

This series integrates the sparse index with commands that perform merges such as 'git merge', 'git cherry-pick', 'git revert' (free with cherry-pick), and 'git rebase'.

When the ORT merge strategy is enabled, this allows most merges to succeed without expanding the sparse index, leading to significant performance gains. I tested these changes against an internal monorepo with over 2 million paths at HEAD but with a sparse-checkout that only has ~60,000 files within the sparse-checkout cone. 'git merge' commands went from 5-6 seconds to 0.750-1.250s.

In the case of the recursive merge strategy, the sparse index is expanded before the recursive algorithm proceeds. We expect that this is as good as we can get with that strategy. When the strategy shifts to ORT as the default, then this will not be a problem except for users who decide to change the behavior.

Most of the hard work was done by previous series, such as ds/sparse-index-ignored-files (which this series is based on).

Updates in V3
=============

* Fixed a typo in patch 2 (it is then moved in patch 3, affecting the range-diff)

* There was a recommendation to use test_config over git config, but that is not possible in a subshell. So, it got moved outside of the subshell and that works just fine.

* The other comments were about the use of GIT_TEST_MERGE_ALGORITHM in the test script, but the tests that isolate that environment variable are only for the 'ensure_not_expanded' tests, not the rest of the tests that already exist and are beneficial to cover the 'recursive' mode.

Updates in V2
=============

* The tests no longer specify GIT_TEST_MERGE_ALGORITHM or directly reference "-s ort". By relaxing this condition, I found an issue with 'git cherry-pick' and 'git rebase' when using the 'recursive' algorithm which is fixed in a new patch.

* Use the pull.twohead config to specify the ORT merge algorithm to avoid expanding the sparse index when that is what we are testing.

* Corrected some misstatements in my commit messages.

Thanks, -Stolee

Derrick Stolee (6):
diff: ignore sparse paths in diffstat
merge: make sparse-aware with ORT
merge-ort: expand only for out-of-cone conflicts
t1092: add cherry-pick, rebase tests
sequencer: ensure full index if not ORT strategy
sparse-index: integrate with cherry-pick and rebase

 builtin/merge.c                          |  3 +
 builtin/rebase.c                         |  6 ++
 builtin/revert.c                         |  3 +
 diff.c                                   |  8 +++
 merge-ort.c                              | 15 ++++
 merge-recursive.c                        |  3 +
 sequencer.c                              |  9 +++
 t/t1092-sparse-checkout-compatibility.sh | 92 +++++++++++++++++++++---
 8 files changed, 129 insertions(+), 10 deletions(-)

base-commit: 91b53f20109fe55635b1815f87afd5d5da68a182
Published-As: https://github.com/gitgitgadget/git/releases/tag/pr-1019%2Fderrickstolee%2Fsparse-index%2Fmerge-v3
Fetch-It-Via: git fetch https://github.com/gitgitgadget/git pr-1019/derrickstolee/sparse-index/merge-v3
Pull-Request: https://github.com/gitgitgadget/git/pull/1019

Range-diff vs v2:

 1:  c5ae705648c = 1:  a6963182fe0 diff: ignore sparse paths in diffstat
 2:  bb150483bcf ! 2:  141f7fb26d6 merge: make sparse-aware with ORT
     @@ merge-ort.c: static int record_conflicted_index_entries(struct merge_options *op
       
      +	/*
      +	 * We are in a conflicted state. These conflicts might be inside
     -+	 * sparse-directory entries, so expand the index preemtively.
     ++	 * sparse-directory entries, so expand the index preemptively.
      +	 * Also, we set original_cache_nr below, but that might change if
      +	 * index_name_pos() calls ask for paths within sparse directories.
      +	 */
     @@ t/t1092-sparse-checkout-compatibility.sh: test_expect_success 'sparse-index is n
      +	ensure_not_expanded add . &&
      +
      +	ensure_not_expanded checkout -f update-deep &&
     ++	test_config -C sparse-index pull.twohead ort &&
      +	(
      +		sane_unset GIT_TEST_MERGE_ALGORITHM &&
     -+		git -C sparse-index config pull.twohead ort &&
      +		ensure_not_expanded merge -m merge update-folder1 &&
      +		ensure_not_expanded merge -m merge update-folder2
      +	)

3: 815b1b1cfbf ! 3: c3c9ffd855c merge-ort: expand only for out-of-cone conflicts
@@ merge-ort.c: static int record_conflicted_index_entries(struct merge_options *op

/*
* We are in a conflicted state. These conflicts might be inside
-- * sparse-directory entries, so expand the index preemtively.
+- * sparse-directory entries, so expand the index preemptively.
- * Also, we set original_cache_nr below, but that might change if
+ * sparse-directory entries, so check if any entries are outside
+ * of the sparse-checkout cone preemptively.

 4:  8032154bc8a = 4:  7aae5727fb7 t1092: add cherry-pick, rebase tests
 5:  90ac85500b8 = 5:  20f5bbae546 sequencer: ensure full index if not ORT strategy
 6:  df4bbec744f ! 6:  36cecb22330 sparse-index: integrate with cherry-pick and rebase

@@ t/t1092-sparse-checkout-compatibility.sh: test_expect_success 'merge with confli
init_repos &&

@@ t/t1092-sparse-checkout-compatibility.sh: test_expect_success 'sparse-index is not expanded' '
+ test_config -C sparse-index pull.twohead ort &&
(
sane_unset GIT_TEST_MERGE_ALGORITHM &&
- git -C sparse-index config pull.twohead ort &&
- ensure_not_expanded merge -m merge update-folder1 &&
- ensure_not_expanded merge -m merge update-folder2
+ for OPERATION in "merge -m merge" cherry-pick rebase

gitgitgadget

From: Derrick Stolee <[email protected]>

The diff_populate_filespec() method is used to describe the diff after a merge operation is complete. In order to avoid expanding a sparse index, the reuse_worktree_file() needs to be adapted to ignore files that are outside of the sparse-checkout cone. The file names and OIDs used for this check come from the merged tree in the case of the ORT strategy, not the index, hence the ability to look into these paths without having already expanded the index.

The work done by reuse_worktree_file() is only an optimization, and requires the file being on disk for it to be of any value. Thus, it is safe to exit the method early if we do not expect the file on disk.

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

index a8113f17070..c8f530ffdbe 100644
@@ -26,6 +26,7 @@
 #include "parse-options.h"
 #include "help.h"
 #include "promisor-remote.h"
+#include "dir.h"
 
 #ifdef NO_FAST_WORKING_DIRECTORY
 #define FAST_WORKING_DIRECTORY 0

@@ -3907,6 +3908,13 @@ static int reuse_worktree_file(struct index_state *istate,
 	if (!want_file && would_convert_to_git(istate, name))
 		return 0;
 
+	/*
+	 * If this path does not match our sparse-checkout definition,
+	 * then the file will not be in the working directory.
+	 */
+	if (!path_in_sparse_checkout(name, istate))
+		return 0;
+
 	len = strlen(name);
 	pos = index_name_pos(istate, name, len);
 	if (pos < 0)

gitgitgadget

From: Derrick Stolee <[email protected]>

Allow 'git merge' to operate without expanding a sparse index, at least not immediately. The index still will be expanded in a few cases:

1. If the merge strategy is 'recursive', then we enable command_requires_full_index at the start of the merge_recursive() method. We expect sparse-index users to also have the 'ort' strategy enabled.

2. With the 'ort' strategy, if the merge results in a conflicted file, then we expand the index before updating the working tree. The loop that iterates over the worktree replaces index entries and tracks 'origintal_cache_nr' which can become completely wrong if the index expands in the middle of the operation. This safety valve is important before that loop starts. A later change will focus this to only expand if we indeed have a conflict outside of the sparse-checkout cone.

3. Other merge strategies are executed as a 'git merge-X' subcommand, and those strategies are currently protected with the 'command_requires_full_index' guard.

Some test updates are required, including a mistaken 'git checkout -b' that did not specify the base branch, causing merges to be fast-forward merges.

---
 builtin/merge.c                          |  3 +++
 merge-ort.c                              |  8 ++++++++
 merge-recursive.c                        |  3 +++
 t/t1092-sparse-checkout-compatibility.sh | 12 ++++++++++--
 4 files changed, 24 insertions(+), 2 deletions(-)

index 22f23990b37..926de328fbb 100644
@@ -1276,6 +1276,9 @@ int cmd_merge(int argc, const char **argv, const char *prefix)
 	if (argc == 2 && !strcmp(argv[1], "-h"))
 		usage_with_options(builtin_merge_usage, builtin_merge_options);
 
+	prepare_repo_settings(the_repository);
+	the_repository->settings.command_requires_full_index = 0;
+
 	/*
 	 * Check if we are _not_ on a detached HEAD, i.e. if there is a
 	 * current branch.

index 6eb910d6f0c..1531b4c94c2 100644
@@ -4058,6 +4058,14 @@ static int record_conflicted_index_entries(struct merge_options *opt)
 	if (strmap_empty(&opt->priv->conflicted))
 		return 0;
 
+	/*
+	 * We are in a conflicted state. These conflicts might be inside
+	 * sparse-directory entries, so expand the index preemptively.
+	 * Also, we set original_cache_nr below, but that might change if
+	 * index_name_pos() calls ask for paths within sparse directories.
+	 */
+	ensure_full_index(index);
+
 	/* If any entries have skip_worktree set, we'll have to check 'em out */
 	state.force = 1;
 	state.quiet = 1;

index 3355d50e8ad..1f563cd6874 100644
@@ -3750,6 +3750,9 @@ int merge_recursive(struct merge_options *opt,
 	assert(opt->ancestor == NULL ||
 	       !strcmp(opt->ancestor, "constructed merge base"));
 
+	prepare_repo_settings(opt->repo);
+	opt->repo->settings.command_requires_full_index = 1;
+
 	if (merge_start(opt, repo_get_commit_tree(opt->repo, h1)))
 		return -1;
 	clean = merge_recursive_internal(opt, h1, h2, merge_bases, result);

index ddc86bb4152..3b331a6bfe7 100755
@@ -47,7 +47,7 @@ test_expect_success 'setup' '
 		git checkout -b base &&
 		for dir in folder1 folder2 deep
 		do
-			git checkout -b update-$dir &&
+			git checkout -b update-$dir base &&
 			echo "updated $dir" >$dir/a &&
 			git commit -a -m "update $dir" || return 1
 		done &&

@@ -647,7 +647,15 @@ test_expect_success 'sparse-index is not expanded' '
 	echo >>sparse-index/extra.txt &&
 	ensure_not_expanded add extra.txt &&
 	echo >>sparse-index/untracked.txt &&
-	ensure_not_expanded add .
+	ensure_not_expanded add . &&
+
+	ensure_not_expanded checkout -f update-deep &&
+	test_config -C sparse-index pull.twohead ort &&
+	(
+		sane_unset GIT_TEST_MERGE_ALGORITHM &&
+		ensure_not_expanded merge -m merge update-folder1 &&
+		ensure_not_expanded merge -m merge update-folder2
+	)
 '
 
 # NEEDSWORK: a sparse-checkout behaves differently from a full checkout

gitgitgadget

From: Derrick Stolee <[email protected]>

Merge conflicts happen often enough to want to avoid expanding a sparse index when they happen, as long as those conflicts are within the sparse-checkout cone. If a conflict exists outside of the sparse-checkout cone, then we still need to expand before iterating over the index entries. This is critical to do in advance because of how the original_cache_nr is tracked to allow inserting and replacing cache entries.

Iterate over the conflicted files and check if any paths are outside of the sparse-checkout cone. If so, then expand the full index.

Add a test that demonstrates that we do not expand the index, even when we hit a conflict within the sparse-checkout cone.

---
 merge-ort.c                              | 13 +++++++---
 t/t1092-sparse-checkout-compatibility.sh | 30 ++++++++++++++++++++++--
 2 files changed, 38 insertions(+), 5 deletions(-)

index 1531b4c94c2..805f7c41397 100644
@@ -4060,11 +4060,18 @@ static int record_conflicted_index_entries(struct merge_options *opt)
 
 	/*
 	 * We are in a conflicted state. These conflicts might be inside
-	 * sparse-directory entries, so expand the index preemptively.
-	 * Also, we set original_cache_nr below, but that might change if
+	 * sparse-directory entries, so check if any entries are outside
+	 * of the sparse-checkout cone preemptively.
+	 *
+	 * We set original_cache_nr below, but that might change if
 	 * index_name_pos() calls ask for paths within sparse directories.
 	 */
-	ensure_full_index(index);
+	strmap_for_each_entry(&opt->priv->conflicted, &iter, e) {
+		if (!path_in_sparse_checkout(e->key, index)) {
+			ensure_full_index(index);
+			break;
+		}
+	}
 
 	/* If any entries have skip_worktree set, we'll have to check 'em out */
 	state.force = 1;

index 3b331a6bfe7..36964f52f2f 100755
@@ -617,8 +617,17 @@ test_expect_success 'sparse-index is expanded and converted back' '
 ensure_not_expanded () {
 	rm -f trace2.txt &&
 	echo >>sparse-index/untracked.txt &&
-	GIT_TRACE2_EVENT="$(pwd)/trace2.txt" GIT_TRACE2_EVENT_NESTING=10 \
-		git -C sparse-index "$@" &&
+
+	if test "$1" = "!"
+	then
+		shift &&
+		test_must_fail env \
+			GIT_TRACE2_EVENT="$(pwd)/trace2.txt" GIT_TRACE2_EVENT_NESTING=10 \
+			git -C sparse-index "$@" || return 1
+	else
+		GIT_TRACE2_EVENT="$(pwd)/trace2.txt" GIT_TRACE2_EVENT_NESTING=10 \
+			git -C sparse-index "$@" || return 1
+	fi &&
 	test_region ! index ensure_full_index trace2.txt
 }
 

@@ -658,6 +667,23 @@ test_expect_success 'sparse-index is not expanded' '
 	)
 '
 
+test_expect_success 'sparse-index is not expanded: merge conflict in cone' '
+	init_repos &&
+
+	for side in right left
+	do
+		git -C sparse-index checkout -b expand-$side base &&
+		echo $side >sparse-index/deep/a &&
+		git -C sparse-index commit -a -m "$side" || return 1
+	done &&
+
+	(
+		sane_unset GIT_TEST_MERGE_ALGORITHM &&
+		git -C sparse-index config pull.twohead ort &&
+		ensure_not_expanded ! merge -m merged expand-right
+	)
+'
+
 # 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' '

gitgitgadget

From: Derrick Stolee <[email protected]>

Add tests to check that cherry-pick and rebase behave the same in the sparse-index case as in the full index cases. These tests are agnostic to GIT_TEST_MERGE_ALGORITHM, so a full CI test suite will check both the 'ort' and 'recursive' strategies on this test.

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

index 36964f52f2f..d9424ed6427 100755
@@ -481,14 +481,17 @@ test_expect_success 'checkout and reset (mixed) [sparse]' '
 	test_sparse_match git reset update-folder2
 '
 
-test_expect_success 'merge' '
+test_expect_success 'merge, cherry-pick, and rebase' '
 	init_repos &&
 
-	test_all_match git checkout -b merge update-deep &&
-	test_all_match git merge -m "folder1" update-folder1 &&
-	test_all_match git rev-parse HEAD^{tree} &&
-	test_all_match git merge -m "folder2" update-folder2 &&
-	test_all_match git rev-parse HEAD^{tree}
+	for OPERATION in "merge -m merge" cherry-pick rebase
+	do
+		test_all_match git checkout -B temp update-deep &&
+		test_all_match git $OPERATION update-folder1 &&
+		test_all_match git rev-parse HEAD^{tree} &&
+		test_all_match git $OPERATION update-folder2 &&
+		test_all_match git rev-parse HEAD^{tree} || return 1
+	done
 '
 
 # NEEDSWORK: This test is documenting current behavior, but that

gitgitgadget

From: Derrick Stolee <[email protected]>

The sequencer is used by 'cherry-pick' and 'rebase' to sequence a list of operations that modify the index. Since we intend to remove the need for 'command_requires_full_index', we need to ensure the sparse index is expanded every time it is written to disk between these steps. That is, unless the merge strategy is 'ort' where the index can remain sparse throughout.

There are two main places to be extra careful about a full index:

1. Right before calling merge_trees(), ensure the index is full. This happens within an 'else' where the 'if' block checks if the 'ort' strategy is selected.

2. During read_and_refresh_cache(), the index might be written to disk and converted to sparse in the process. Ensure it expands back to full afterwards by checking if the strategy is _not_ 'ort'. This 'if' statement is the logical negation of the 'if' in item (1).

---
 sequencer.c | 9 +++++++++
 1 file changed, 9 insertions(+)

index 7f07cd00f3f..228bc089d22 100644
@@ -652,6 +652,7 @@ static int do_recursive_merge(struct repository *r,
 		merge_switch_to_result(&o, head_tree, &result, 1, show_output);
 		clean = result.clean;
 	} else {
+		ensure_full_index(r->index);
 		clean = merge_trees(&o, head_tree, next_tree, base_tree);
 		if (is_rebase_i(opts) && clean <= 0)
 			fputs(o.obuf.buf, stdout);

@@ -2346,6 +2347,7 @@ static int read_and_refresh_cache(struct repository *r,
 			_(action_name(opts)));
 	}
 	refresh_index(r->index, REFRESH_QUIET|REFRESH_UNMERGED, NULL, NULL, NULL);
+
 	if (index_fd >= 0) {
 		if (write_locked_index(r->index, &index_lock,
 				       COMMIT_LOCK | SKIP_IF_UNCHANGED)) {

@@ -2353,6 +2355,13 @@ static int read_and_refresh_cache(struct repository *r,
 				_(action_name(opts)));
 		}
 	}
+
+	/*
+	 * If we are resolving merges in any way other than "ort", then
+	 * expand the sparse index.
+	 */
+	if (opts->strategy && strcmp(opts->strategy, "ort"))
+		ensure_full_index(r->index);
 	return 0;
 }
 

gitgitgadget

From: Derrick Stolee <[email protected]>

The hard work was already done with 'git merge' and the ORT strategy. Just add extra tests to see that we get the expected results in the non-conflict cases.

---
 builtin/rebase.c                         |  6 ++++
 builtin/revert.c                         |  3 ++
 t/t1092-sparse-checkout-compatibility.sh | 39 ++++++++++++++++++++++--
 3 files changed, 46 insertions(+), 2 deletions(-)

index 33e09619005..27433d7c5a2 100644
@@ -559,6 +559,9 @@ int cmd_rebase__interactive(int argc, const char **argv, const char *prefix)
 	argc = parse_options(argc, argv, prefix, options,
 			builtin_rebase_interactive_usage, PARSE_OPT_KEEP_ARGV0);
 
+	prepare_repo_settings(the_repository);
+	the_repository->settings.command_requires_full_index = 0;
+
 	if (!is_null_oid(&squash_onto))
 		opts.squash_onto = &squash_onto;
 

@@ -1430,6 +1433,9 @@ int cmd_rebase(int argc, const char **argv, const char *prefix)
 		usage_with_options(builtin_rebase_usage,
 				   builtin_rebase_options);
 
+	prepare_repo_settings(the_repository);
+	the_repository->settings.command_requires_full_index = 0;
+
 	options.allow_empty_message = 1;
 	git_config(rebase_config, &options);
 	/* options.gpg_sign_opt will be either "-S" or NULL */

index 237f2f18d4c..6c4c22691bd 100644
@@ -136,6 +136,9 @@ static int run_sequencer(int argc, const char **argv, struct replay_opts *opts)
 			PARSE_OPT_KEEP_ARGV0 |
 			PARSE_OPT_KEEP_UNKNOWN);
 
+	prepare_repo_settings(the_repository);
+	the_repository->settings.command_requires_full_index = 0;
+
 	/* implies allow_empty */
 	if (opts->keep_redundant_commits)
 		opts->allow_empty = 1;

index d9424ed6427..886e78715fe 100755
@@ -527,6 +527,38 @@ test_expect_success 'merge with conflict outside cone' '
 	test_all_match git rev-parse HEAD^{tree}
 '
 
+test_expect_success 'cherry-pick/rebase with conflict outside cone' '
+	init_repos &&
+
+	for OPERATION in cherry-pick rebase
+	do
+		test_all_match git checkout -B tip &&
+		test_all_match git reset --hard merge-left &&
+		test_all_match git status --porcelain=v2 &&
+		test_all_match test_must_fail git $OPERATION merge-right &&
+		test_all_match git status --porcelain=v2 &&
+
+		# Resolve the conflict in different ways:
+		# 1. Revert to the base
+		test_all_match git checkout base -- deep/deeper2/a &&
+		test_all_match git status --porcelain=v2 &&
+
+		# 2. Add the file with conflict markers
+		test_all_match git add folder1/a &&
+		test_all_match git status --porcelain=v2 &&
+
+		# 3. Rename the file to another sparse filename and
+		#    accept conflict markers as resolved content.
+		run_on_all mv folder2/a folder2/z &&
+		test_all_match git add folder2 &&
+		test_all_match git status --porcelain=v2 &&
+
+		test_all_match git $OPERATION --continue &&
+		test_all_match git status --porcelain=v2 &&
+		test_all_match git rev-parse HEAD^{tree} || return 1
+	done
+'
+
 test_expect_success 'merge with outside renames' '
 	init_repos &&
 

@@ -665,8 +697,11 @@ test_expect_success 'sparse-index is not expanded' '
 	test_config -C sparse-index pull.twohead ort &&
 	(
 		sane_unset GIT_TEST_MERGE_ALGORITHM &&
-		ensure_not_expanded merge -m merge update-folder1 &&
-		ensure_not_expanded merge -m merge update-folder2
+		for OPERATION in "merge -m merge" cherry-pick rebase
+		do
+			ensure_not_expanded merge -m merge update-folder1 &&
+			ensure_not_expanded merge -m merge update-folder2 || return 1
+		done
 	)
 '
 

gitgitgadget

This round addresses all my feedback and looks good to me: