mbox series

[00/11] Complete merge-ort implementation...almost

Message ID pull.973.git.git.1614905738.gitgitgadget@gmail.com (mailing list archive)
Headers show
Series Complete merge-ort implementation...almost | expand

Message

Victoria Dye via GitGitGadget March 5, 2021, 12:55 a.m. UTC
In order to help Ævar test his tree-walk changes against merge-ort[1], this
series completes the merge-ort implementation and cleans up testsuite
failures...EXCEPT for some t6423 failures. It also leaves out a lot of
performance work, which incidentally will fix the t6423 failures and is
being reviewed independently[2].

This 11-patch series could be submitted as 7 independent series, 1-4 patches
in length each, but it's probably easier for Ævar if we can merge just one
more thing and it's only 11 total patches. This series sub-divides as
follows:

 * Patch 1: Fix bug in already-merged portion of merge-ort affecting
   rename/rename conflicts on platforms where qsort isn't stable. (Could be
   considered for merging before 2.31 since it is a new bug in the 2.31
   cycle that I just learned of last night, but not sure it matters since
   merge-ort wasn't complete anyway and we're not even mentioning merge-ort
   in the release notes.)
 * Patches 2-5: Add support for renormalization
 * Patch 6: Add support for subtree shifting
 * Patch 7-8: Add test and support for conflicts affecting sparse-checkout
   entries
 * Patch 9: Update submodule related merge tests to note the ones that
   merge-ort fixes relative to merge-recursive
 * Patch 10: New feature -- allow "git diff AUTO_MERGE" during conflict
   resolution to let user review changes they made since
   merge/rebase/cherry-pick/revert stopped and informed them of conflicts
 * Patch 11: Add comments noting various bugs in merge-recursive

The last two patches aren't needed by Ævar, so they could be left out and
submitted later. I just figured that it was only two more patches and they
were part of "completing the merge-ort implementation" in my view.

[1] https://lore.kernel.org/git/877dmmkhnt.fsf@evledraar.gmail.com/ [2] See
https://lore.kernel.org/git/pull.845.git.1614484707.gitgitgadget@gmail.com/;
there are five more waiting after that -- viewable by the curious at
https://github.com/gitgitgadget/git/pulls?q=is%3Apr+author%3Anewren+Optimization+batch

Elijah Newren (11):
  merge-ort: use STABLE_QSORT instead of QSORT where required
  merge-ort: add a special minimal index just for renormalization
  merge-ort: add a function for initializing our special attr_index
  merge-ort: have ll_merge() calls use the attr_index for
    renormalization
  merge-ort: let renormalization change modify/delete into clean delete
  merge-ort: support subtree shifting
  t6428: new test for SKIP_WORKTREE handling and conflicts
  merge-ort: implement CE_SKIP_WORKTREE handling with conflicted entries
  t: mark several submodule merging tests as fixed under merge-ort
  merge-ort: write $GIT_DIR/AUTO_MERGE whenever we hit a conflict
  merge-recursive: add a bunch of FIXME comments documenting known bugs

 branch.c                                      |   1 +
 builtin/rebase.c                              |   1 +
 merge-ort.c                                   | 230 ++++++++++++++++--
 merge-recursive.c                             |  37 +++
 path.c                                        |   1 +
 path.h                                        |   2 +
 sequencer.c                                   |   5 +
 t/t3512-cherry-pick-submodule.sh              |   9 +-
 t/t3513-revert-submodule.sh                   |   7 +-
 t/t5572-pull-submodule.sh                     |   9 +-
 t/t6428-merge-conflicts-sparse.sh             | 158 ++++++++++++
 t/t6437-submodule-merge.sh                    |   5 +-
 t/t6438-submodule-directory-file-conflicts.sh |   9 +-
 13 files changed, 449 insertions(+), 25 deletions(-)
 create mode 100755 t/t6428-merge-conflicts-sparse.sh


base-commit: f01623b2c9d14207e497b21ebc6b3ec4afaf4b46
Published-As: https://github.com/gitgitgadget/git/releases/tag/pr-git-973%2Fnewren%2Fort-remainder-v1
Fetch-It-Via: git fetch https://github.com/gitgitgadget/git pr-git-973/newren/ort-remainder-v1
Pull-Request: https://github.com/git/git/pull/973

Comments

Ævar Arnfjörð Bjarmason March 8, 2021, 2:43 p.m. UTC | #1
On Fri, Mar 05 2021, Elijah Newren via GitGitGadget wrote:

> In order to help Ævar test his tree-walk changes against merge-ort[1], this
> series completes the merge-ort implementation and cleans up testsuite
> failures...EXCEPT for some t6423 failures. It also leaves out a lot of
> performance work, which incidentally will fix the t6423 failures and is
> being reviewed independently[2].

For those testing this in combination with their work, the expected
failures are these specific tests:

    ./t6423-merge-rename-directories.sh (Wstat: 256 Tests: 68 Failed: 4)
      Failed tests:  7, 53, 55, 59

Perhaps I'm missing something but why not have [1] below on top of this
series? It makes that test pass in both modes, and means we could
e.g. follow-up by running CI with "ort".

That CI step seems worth doing sooner than later, even if it needs some
GIT_TEST_SKIP for now...

> This 11-patch series could be submitted as 7 independent series, 1-4 patches
> in length each, but it's probably easier for Ævar if we can merge just one
> more thing and it's only 11 total patches. This series sub-divides as
> follows:
>
>  * Patch 1: Fix bug in already-merged portion of merge-ort affecting
>    rename/rename conflicts on platforms where qsort isn't stable. (Could be
>    considered for merging before 2.31 since it is a new bug in the 2.31
>    cycle that I just learned of last night, but not sure it matters since
>    merge-ort wasn't complete anyway and we're not even mentioning merge-ort
>    in the release notes.)
>  * Patches 2-5: Add support for renormalization
>  * Patch 6: Add support for subtree shifting
>  * Patch 7-8: Add test and support for conflicts affecting sparse-checkout
>    entries
>  * Patch 9: Update submodule related merge tests to note the ones that
>    merge-ort fixes relative to merge-recursive
>  * Patch 10: New feature -- allow "git diff AUTO_MERGE" during conflict
>    resolution to let user review changes they made since
>    merge/rebase/cherry-pick/revert stopped and informed them of conflicts
>  * Patch 11: Add comments noting various bugs in merge-recursive
>
> The last two patches aren't needed by Ævar, so they could be left out and
> submitted later. I just figured that it was only two more patches and they
> were part of "completing the merge-ort implementation" in my view.

This whole thing was a pleasant read, and helped me catch a subtle
regression in my WIP "mode" work (which I'm now about to submit).

Reviewing this series suffered from the problem you have with writing
code that's clearly good enough: Mostly all I had were minor nits,
suggestions to re-arrange code differently etc.

That being said I'm not all that familiar with the guts of the merge
logic, so I may have missed other issues...

> [1] https://lore.kernel.org/git/877dmmkhnt.fsf@evledraar.gmail.com/ [2] See
> https://lore.kernel.org/git/pull.845.git.1614484707.gitgitgadget@gmail.com/;
> there are five more waiting after that -- viewable by the curious at
> https://github.com/gitgitgadget/git/pulls?q=is%3Apr+author%3Anewren+Optimization+batch
>
> Elijah Newren (11):
>   merge-ort: use STABLE_QSORT instead of QSORT where required
>   merge-ort: add a special minimal index just for renormalization
>   merge-ort: add a function for initializing our special attr_index
>   merge-ort: have ll_merge() calls use the attr_index for
>     renormalization
>   merge-ort: let renormalization change modify/delete into clean delete
>   merge-ort: support subtree shifting
>   t6428: new test for SKIP_WORKTREE handling and conflicts
>   merge-ort: implement CE_SKIP_WORKTREE handling with conflicted entries
>   t: mark several submodule merging tests as fixed under merge-ort
>   merge-ort: write $GIT_DIR/AUTO_MERGE whenever we hit a conflict
>   merge-recursive: add a bunch of FIXME comments documenting known bugs
>
>  branch.c                                      |   1 +
>  builtin/rebase.c                              |   1 +
>  merge-ort.c                                   | 230 ++++++++++++++++--
>  merge-recursive.c                             |  37 +++
>  path.c                                        |   1 +
>  path.h                                        |   2 +
>  sequencer.c                                   |   5 +
>  t/t3512-cherry-pick-submodule.sh              |   9 +-
>  t/t3513-revert-submodule.sh                   |   7 +-
>  t/t5572-pull-submodule.sh                     |   9 +-
>  t/t6428-merge-conflicts-sparse.sh             | 158 ++++++++++++
>  t/t6437-submodule-merge.sh                    |   5 +-
>  t/t6438-submodule-directory-file-conflicts.sh |   9 +-
>  13 files changed, 449 insertions(+), 25 deletions(-)
>  create mode 100755 t/t6428-merge-conflicts-sparse.sh
>
>
> base-commit: f01623b2c9d14207e497b21ebc6b3ec4afaf4b46
> Published-As: https://github.com/gitgitgadget/git/releases/tag/pr-git-973%2Fnewren%2Fort-remainder-v1
> Fetch-It-Via: git fetch https://github.com/gitgitgadget/git pr-git-973/newren/ort-remainder-v1
> Pull-Request: https://github.com/git/git/pull/973

1.:

diff --git a/t/t6423-merge-rename-directories.sh b/t/t6423-merge-rename-directories.sh
index 5d3b711fe68..4f6ead11e51 100755
--- a/t/t6423-merge-rename-directories.sh
+++ b/t/t6423-merge-rename-directories.sh
@@ -507,7 +507,7 @@ test_setup_2a () {
 	)
 }
 
-test_expect_success '2a: Directory split into two on one side, with equal numbers of paths' '
+test_expect_merge_algorithm success failure '2a: Directory split into two on one side, with equal numbers of paths' '
 	test_setup_2a &&
 	(
 		cd 2a &&
@@ -3060,7 +3060,7 @@ test_setup_9g () {
 	)
 }
 
-test_expect_failure '9g: Renamed directory that only contained immediate subdirs, immediate subdirs renamed' '
+test_expect_merge_algorithm failure failure '9g: Renamed directory that only contained immediate subdirs, immediate subdirs renamed' '
 	test_setup_9g &&
 	(
 		cd 9g &&
@@ -4267,7 +4267,7 @@ test_setup_12b1 () {
 	)
 }
 
-test_expect_merge_algorithm failure success '12b1: Moving two directory hierarchies into each other' '
+test_expect_merge_algorithm failure failure '12b1: Moving two directory hierarchies into each other' '
 	test_setup_12b1 &&
 	(
 		cd 12b1 &&
@@ -4435,7 +4435,7 @@ test_setup_12c1 () {
 	)
 }
 
-test_expect_merge_algorithm failure success '12c1: Moving one directory hierarchy into another w/ content merge' '
+test_expect_merge_algorithm failure failure '12c1: Moving one directory hierarchy into another w/ content merge' '
 	test_setup_12c1 &&
 	(
 		cd 12c1 &&
@@ -4797,7 +4797,7 @@ test_setup_12f () {
 	)
 }
 
-test_expect_merge_algorithm failure success '12f: Trivial directory resolve, caching, all kinds of fun' '
+test_expect_merge_algorithm failure failure '12f: Trivial directory resolve, caching, all kinds of fun' '
 	test_setup_12f &&
 	(
 		cd 12f &&
Elijah Newren March 8, 2021, 10:13 p.m. UTC | #2
On Mon, Mar 8, 2021 at 6:43 AM Ævar Arnfjörð Bjarmason <avarab@gmail.com> wrote:
>
>
> On Fri, Mar 05 2021, Elijah Newren via GitGitGadget wrote:
>
> > In order to help Ævar test his tree-walk changes against merge-ort[1], this
> > series completes the merge-ort implementation and cleans up testsuite
> > failures...EXCEPT for some t6423 failures. It also leaves out a lot of
> > performance work, which incidentally will fix the t6423 failures and is
> > being reviewed independently[2].
>
> For those testing this in combination with their work, the expected
> failures are these specific tests:
>
>     ./t6423-merge-rename-directories.sh (Wstat: 256 Tests: 68 Failed: 4)
>       Failed tests:  7, 53, 55, 59
>
> Perhaps I'm missing something but why not have [1] below on top of this
> series? It makes that test pass in both modes, and means we could
> e.g. follow-up by running CI with "ort".
>
> That CI step seems worth doing sooner than later, even if it needs some
> GIT_TEST_SKIP for now...

Oh, um, mostly it was history and the fact that I just never took a
step back.  When I started adding merge-ort, there were 2200+ tests
that were failing, and marking them all as test_expect_fail was just a
useless code churn; we knew it'd fail when the implemenation basically
just called die().  At some point I got it down to 8 tests failing,
but felt I needed to quickly switch tracks to upstream the
diffcore-rename work since we had an Outreachy intern that was going
to be buildiing on it and/or making changes that might conflict with
it.  I was still in the mode of fixing them through completing the
implementation rather than stepping back and saying, "Hey, we only
have a few tests left failing; let's mark them as such.".

However, all that said, making this change _now_ would semantically
conflict with ort-perf-batch-9[1] (which was submitted first), since
it fixes one of the four tests.  It'd also mean a similar semantic
conflict for ort-perf-batch-10 (which fixes another) and
ort-perf-batch-12 (which fixes the last 2), or those series will have
to depend on a merge of ort-perf-batch-9 and this series.  Relying on
special merges for some of the earlier patches for merge-ort seems
like it was a bit of a pain and I'd rather not put Junio through that.
Also, if we do it, and don't have Junio mark the fixes as things are
merged, then we have to decide on a topic order.  So, Junio: thoughts?

[1] https://lore.kernel.org/git/pull.845.git.1614484707.gitgitgadget@gmail.com/

> > This 11-patch series could be submitted as 7 independent series, 1-4 patches
> > in length each, but it's probably easier for Ævar if we can merge just one
> > more thing and it's only 11 total patches. This series sub-divides as
> > follows:
> >
> >  * Patch 1: Fix bug in already-merged portion of merge-ort affecting
> >    rename/rename conflicts on platforms where qsort isn't stable. (Could be
> >    considered for merging before 2.31 since it is a new bug in the 2.31
> >    cycle that I just learned of last night, but not sure it matters since
> >    merge-ort wasn't complete anyway and we're not even mentioning merge-ort
> >    in the release notes.)
> >  * Patches 2-5: Add support for renormalization
> >  * Patch 6: Add support for subtree shifting
> >  * Patch 7-8: Add test and support for conflicts affecting sparse-checkout
> >    entries
> >  * Patch 9: Update submodule related merge tests to note the ones that
> >    merge-ort fixes relative to merge-recursive
> >  * Patch 10: New feature -- allow "git diff AUTO_MERGE" during conflict
> >    resolution to let user review changes they made since
> >    merge/rebase/cherry-pick/revert stopped and informed them of conflicts
> >  * Patch 11: Add comments noting various bugs in merge-recursive
> >
> > The last two patches aren't needed by Ævar, so they could be left out and
> > submitted later. I just figured that it was only two more patches and they
> > were part of "completing the merge-ort implementation" in my view.
>
> This whole thing was a pleasant read, and helped me catch a subtle
> regression in my WIP "mode" work (which I'm now about to submit).

Wahoo for helping catch regressions!  :-)

> Reviewing this series suffered from the problem you have with writing
> code that's clearly good enough: Mostly all I had were minor nits,
> suggestions to re-arrange code differently etc.

Thanks for taking a look.  You had lots of good small suggestions that
I'll incorporate in a re-roll.  There were a couple that sounded like
they should be split off into their own sets of cleanup patches that
I'll defer for now.

> That being said I'm not all that familiar with the guts of the merge
> logic, so I may have missed other issues...

>
> > [1] https://lore.kernel.org/git/877dmmkhnt.fsf@evledraar.gmail.com/ [2] See
> > https://lore.kernel.org/git/pull.845.git.1614484707.gitgitgadget@gmail.com/;
> > there are five more waiting after that -- viewable by the curious at
> > https://github.com/gitgitgadget/git/pulls?q=is%3Apr+author%3Anewren+Optimization+batch
> >
> > Elijah Newren (11):
> >   merge-ort: use STABLE_QSORT instead of QSORT where required
> >   merge-ort: add a special minimal index just for renormalization
> >   merge-ort: add a function for initializing our special attr_index
> >   merge-ort: have ll_merge() calls use the attr_index for
> >     renormalization
> >   merge-ort: let renormalization change modify/delete into clean delete
> >   merge-ort: support subtree shifting
> >   t6428: new test for SKIP_WORKTREE handling and conflicts
> >   merge-ort: implement CE_SKIP_WORKTREE handling with conflicted entries
> >   t: mark several submodule merging tests as fixed under merge-ort
> >   merge-ort: write $GIT_DIR/AUTO_MERGE whenever we hit a conflict
> >   merge-recursive: add a bunch of FIXME comments documenting known bugs
> >
> >  branch.c                                      |   1 +
> >  builtin/rebase.c                              |   1 +
> >  merge-ort.c                                   | 230 ++++++++++++++++--
> >  merge-recursive.c                             |  37 +++
> >  path.c                                        |   1 +
> >  path.h                                        |   2 +
> >  sequencer.c                                   |   5 +
> >  t/t3512-cherry-pick-submodule.sh              |   9 +-
> >  t/t3513-revert-submodule.sh                   |   7 +-
> >  t/t5572-pull-submodule.sh                     |   9 +-
> >  t/t6428-merge-conflicts-sparse.sh             | 158 ++++++++++++
> >  t/t6437-submodule-merge.sh                    |   5 +-
> >  t/t6438-submodule-directory-file-conflicts.sh |   9 +-
> >  13 files changed, 449 insertions(+), 25 deletions(-)
> >  create mode 100755 t/t6428-merge-conflicts-sparse.sh
> >
> >
> > base-commit: f01623b2c9d14207e497b21ebc6b3ec4afaf4b46
> > Published-As: https://github.com/gitgitgadget/git/releases/tag/pr-git-973%2Fnewren%2Fort-remainder-v1
> > Fetch-It-Via: git fetch https://github.com/gitgitgadget/git pr-git-973/newren/ort-remainder-v1
> > Pull-Request: https://github.com/git/git/pull/973
>
> 1.:
>
> diff --git a/t/t6423-merge-rename-directories.sh b/t/t6423-merge-rename-directories.sh
> index 5d3b711fe68..4f6ead11e51 100755
> --- a/t/t6423-merge-rename-directories.sh
> +++ b/t/t6423-merge-rename-directories.sh
> @@ -507,7 +507,7 @@ test_setup_2a () {
>         )
>  }
>
> -test_expect_success '2a: Directory split into two on one side, with equal numbers of paths' '
> +test_expect_merge_algorithm success failure '2a: Directory split into two on one side, with equal numbers of paths' '
>         test_setup_2a &&
>         (
>                 cd 2a &&
> @@ -3060,7 +3060,7 @@ test_setup_9g () {
>         )
>  }
>
> -test_expect_failure '9g: Renamed directory that only contained immediate subdirs, immediate subdirs renamed' '
> +test_expect_merge_algorithm failure failure '9g: Renamed directory that only contained immediate subdirs, immediate subdirs renamed' '
>         test_setup_9g &&
>         (
>                 cd 9g &&
> @@ -4267,7 +4267,7 @@ test_setup_12b1 () {
>         )
>  }
>
> -test_expect_merge_algorithm failure success '12b1: Moving two directory hierarchies into each other' '
> +test_expect_merge_algorithm failure failure '12b1: Moving two directory hierarchies into each other' '
>         test_setup_12b1 &&
>         (
>                 cd 12b1 &&
> @@ -4435,7 +4435,7 @@ test_setup_12c1 () {
>         )
>  }
>
> -test_expect_merge_algorithm failure success '12c1: Moving one directory hierarchy into another w/ content merge' '
> +test_expect_merge_algorithm failure failure '12c1: Moving one directory hierarchy into another w/ content merge' '
>         test_setup_12c1 &&
>         (
>                 cd 12c1 &&
> @@ -4797,7 +4797,7 @@ test_setup_12f () {
>         )
>  }
>
> -test_expect_merge_algorithm failure success '12f: Trivial directory resolve, caching, all kinds of fun' '
> +test_expect_merge_algorithm failure failure '12f: Trivial directory resolve, caching, all kinds of fun' '
>         test_setup_12f &&
>         (
>                 cd 12f &&