patch, 6 partsSparse 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

From: Derrick Stolee <dstolee@microsoft.com>

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

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

On Tue, Aug 17, 2021 at 05:08:39PM +0000, Derrick Stolee via GitGitGadget wrote:

Looks good, but are the lower hunks which set `-s ort` necessary, too? I applied this series into my tree and t1092 still passes after reverting the next two hunks.

Not worth a reroll on its own, just curious.

Thanks, Taylor

"Derrick Stolee via GitGitGadget" <gitgitgadget@gmail.com> writes:

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.

On 8/18/2021 2:10 PM, Junio C Hamano wrote:

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

Derrick Stolee <stolee@gmail.com> writes:

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.

On Wed, Aug 18, 2021 at 11:42 AM Derrick Stolee <stolee@gmail.com> wrote:

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".

Elijah Newren <newren@gmail.com> writes:

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?

On Fri, Aug 20, 2021 at 4:32 PM Junio C Hamano <gitster@pobox.com> wrote:

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.

Elijah Newren <newren@gmail.com> writes:

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

On Fri, Aug 20, 2021 at 9:20 PM Junio C Hamano <gitster@pobox.com> wrote:

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 <dstolee@microsoft.com>

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.

Signed-off-by: Derrick Stolee <dstolee@microsoft.com>
---
 diff.c | 8 ++++++++
 1 file changed, 8 insertions(+)

On Tue, Aug 17, 2021 at 10:08 AM Derrick Stolee via GitGitGadget <gitgitgadget@gmail.com> wrote:

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)?

On 8/20/2021 5:32 PM, Elijah Newren wrote:

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

On Tue, Aug 24, 2021 at 11:30 AM Derrick Stolee <stolee@gmail.com> wrote:

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

From: Derrick Stolee <dstolee@microsoft.com>

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.

Signed-off-by: Derrick Stolee <dstolee@microsoft.com>
---
 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(-)

On Tue, Aug 17, 2021 at 10:08 AM Derrick Stolee via GitGitGadget <gitgitgadget@gmail.com> wrote:

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.

s/preemtively/preemptively/

This seems somewhat pessimistic; what if all the conflicts are within the sparse-checkout? Having conflicts contains within the sparse-checkout seems likely, since we'd only get conflicts for files modified by both sides of history, and sparse-checkouts are used when users aren't going to modify files outside the sparse-checkout.

Can we just set GIT_TEST_MERGE_ALGORITHM=ort at the beginning of the test file and then avoid repeating `-s ort`?

From: Derrick Stolee <dstolee@microsoft.com>

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.

Signed-off-by: Derrick Stolee <dstolee@microsoft.com>
---
 merge-ort.c                              | 14 ++++++++---
 t/t1092-sparse-checkout-compatibility.sh | 30 ++++++++++++++++++++++--
 2 files changed, 39 insertions(+), 5 deletions(-)

On Tue, Aug 17, 2021 at 10:08 AM Derrick Stolee via GitGitGadget <gitgitgadget@gmail.com> wrote:

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

Awesome to see this.

dir.h was already included from merge-ort.c; no need to include it again. (Plus, the original line keeps the nice ordering of the include list...)

Sweet, awesome that it was so simple to implement.

Could this be simplified to
          test_must_fail env \
                  GIT_TRACE2_EVENT="$(pwd)/trace2.txt"
GIT_TRACE2_EVENT_NESTING=10 \
                          git -C sparse-index "$@" || return 1
?
Especially if the lines can be indented to make it clear that the only
difference between this block and the one below is the "test_must_fail
env" being added at the front.

From: Derrick Stolee <dstolee@microsoft.com>

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

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

On Tue, Aug 17, 2021 at 10:08 AM Derrick Stolee via GitGitGadget <gitgitgadget@gmail.com> wrote:

You're explicitly testing the ort strategy with merge, but relying on GIT_TEST_MERGE_ALGORITHM for cherry-pick and rebase?

It'd probably be better to set GIT_TEST_MERGE_ALGORITHM=ort at the beginning of the file and leave out the `-s ort` references.

Or, if you really wanted to test both algorithms, then in addition to leaving out the `-s ort`, don't bother setting GIT_TEST_MERGE_ALGORITHM. (That works because automated test suites will set GIT_TEST_MERGE_ALGORITHM=recursive on linux-gcc, and GIT_TEST_MERGE_ALGORITHM=ort elsewhere).

From: Derrick Stolee <dstolee@microsoft.com>

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.

Signed-off-by: Derrick Stolee <dstolee@microsoft.com>
---
 builtin/rebase.c                         |  6 ++++
 builtin/revert.c                         |  3 ++
 t/t1092-sparse-checkout-compatibility.sh | 41 ++++++++++++++++++++++--
 3 files changed, 47 insertions(+), 3 deletions(-)

On Tue, Aug 17, 2021 at 10:08 AM Derrick Stolee via GitGitGadget <gitgitgadget@gmail.com> wrote:

:-)

While rebase can use either merge-recursive or merge-ort under the covers, this change is okay because merge-recursive.c now has code to expand the index unconditionally, and merge-ort does so only conditionally in the cases needed. Right? (Same for change below to revert.c)

Won't this fail on linux-gcc in the automated testing, since it uses GIT_TEST_MERGE_ALGORITHM=recursive and you didn't override the merge strategy for cherry-pick and rebase?

To fix, you'd either need to put a GIT_TEST_MERGE_ALGORITHM=ort at the beginning of the file, or add `--strategy ort` options to the cherry-pick and rebase commands.

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.
      
          Signed-off-by: Derrick Stolee <dstolee@microsoft.com>
      
     @@ 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 <dstolee@microsoft.com>
      
       ## 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.
      
          Signed-off-by: Derrick Stolee <dstolee@microsoft.com>
      
     @@ 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' '

From: Derrick Stolee <dstolee@microsoft.com>

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.

Signed-off-by: Derrick Stolee <dstolee@microsoft.com>
---
 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(-)

On Tue, Aug 24, 2021 at 2:52 PM Derrick Stolee via GitGitGadget <gitgitgadget@gmail.com> wrote:

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.

Same typo I pointed out in v1.

Should you use test_config rather than git config here?

More importantly, why the subshell and unsetting of GIT_TEST_MERGE_ALGORITHM and the special worrying about pull.twohead? Wouldn't it be simpler to just set GIT_TEST_MERGE_ALGORITHM=ort, perhaps at the beginning of the file?

On 8/27/2021 6:43 PM, Elijah Newren wrote:

...

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

On 8/30/2021 1:18 PM, Derrick Stolee wrote:

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 <dstolee@microsoft.com>

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.

Signed-off-by: Derrick Stolee <dstolee@microsoft.com>
---
 diff.c | 8 ++++++++
 1 file changed, 8 insertions(+)

From: Derrick Stolee <dstolee@microsoft.com>

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.

Signed-off-by: Derrick Stolee <dstolee@microsoft.com>
---
 merge-ort.c                              | 13 +++++++---
 t/t1092-sparse-checkout-compatibility.sh | 30 ++++++++++++++++++++++--
 2 files changed, 38 insertions(+), 5 deletions(-)

On Tue, Aug 24, 2021 at 2:52 PM Derrick Stolee via GitGitGadget <gitgitgadget@gmail.com> wrote:

These last five lines could just be replaced with the fourth, if you just set GIT_TEST_MERGE_ALGORITHM=ort at the beginning of the file.

Are you worrying about testing with recursive in some of the testcases?

On 8/27/2021 6:47 PM, Elijah Newren wrote:

...

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 <dstolee@microsoft.com>

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.

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

From: Derrick Stolee <dstolee@microsoft.com>

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).

Signed-off-by: Derrick Stolee <dstolee@microsoft.com>
---
 sequencer.c | 9 +++++++++
 1 file changed, 9 insertions(+)

From: Derrick Stolee <dstolee@microsoft.com>

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.

Signed-off-by: Derrick Stolee <dstolee@microsoft.com>
---
 builtin/rebase.c                         |  6 ++++
 builtin/revert.c                         |  3 ++
 t/t1092-sparse-checkout-compatibility.sh | 39 ++++++++++++++++++++++--
 3 files changed, 46 insertions(+), 2 deletions(-)

On Tue, Aug 24, 2021 at 2:52 PM Derrick Stolee via GitGitGadget <gitgitgadget@gmail.com> wrote:

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.

On 8/27/2021 6:56 PM, Elijah Newren wrote:

...

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

From: Derrick Stolee <dstolee@microsoft.com>

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.

Signed-off-by: Derrick Stolee <dstolee@microsoft.com>
---
 diff.c | 8 ++++++++
 1 file changed, 8 insertions(+)

From: Derrick Stolee <dstolee@microsoft.com>

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.

Signed-off-by: Derrick Stolee <dstolee@microsoft.com>
---
 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(-)

From: Derrick Stolee <dstolee@microsoft.com>

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.

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

From: Derrick Stolee <dstolee@microsoft.com>

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.

Signed-off-by: Derrick Stolee <dstolee@microsoft.com>
---
 merge-ort.c                              | 13 +++++++---
 t/t1092-sparse-checkout-compatibility.sh | 30 ++++++++++++++++++++++--
 2 files changed, 38 insertions(+), 5 deletions(-)

From: Derrick Stolee <dstolee@microsoft.com>

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).

Signed-off-by: Derrick Stolee <dstolee@microsoft.com>
---
 sequencer.c | 9 +++++++++
 1 file changed, 9 insertions(+)

From: Derrick Stolee <dstolee@microsoft.com>

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.

Signed-off-by: Derrick Stolee <dstolee@microsoft.com>
---
 builtin/rebase.c                         |  6 ++++
 builtin/revert.c                         |  3 ++
 t/t1092-sparse-checkout-compatibility.sh | 39 ++++++++++++++++++++++--
 3 files changed, 46 insertions(+), 2 deletions(-)

On Wed, Sep 8, 2021 at 4:24 AM Derrick Stolee via GitGitGadget <gitgitgadget@gmail.com> wrote:

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

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