[v4,08/24] Ensure index matches head before invoking merge machinery, round N
diff mbox series

Message ID 20190817184144.32179-9-newren@gmail.com
State New
Headers show
Series
  • Clean up merge API
Related show

Commit Message

Elijah Newren Aug. 17, 2019, 6:41 p.m. UTC
This is the bug that just won't die; there always seems to be another
form of it somewhere.  See the commit message of 55f39cf7551b ("merge:
fix misleading pre-merge check documentation", 2018-06-30) for a more
detailed explanation), but in short:

<quick summary>

builtin/merge.c contains this important requirement for merge
strategies:

    ...the index must be in sync with the head commit.  The strategies are
    responsible to ensure this.

This condition is important to enforce because there are two likely
failure cases when the index isn't in sync with the head commit:

  * we silently throw away changes the user had staged before the merge

  * we accidentally (and silently) include changes in the merge that
    were not part of either of the branches/trees being merged

Discarding users' work and mis-merging are both bad outcomes, especially
when done silently, so naturally this rule was stated sternly -- but,
unfortunately totally ignored in practice unless and until actual bugs
were found.  But, fear not: the bugs from this were fixed in commit
  ee6566e8d70d ("[PATCH] Rewrite read-tree", 2005-09-05)
through a rewrite of read-tree (again, commit 55f39cf7551b has a more
detailed explanation of how this affected merge).  And it was fixed
again in commit
  160252f81626 ("git-merge-ours: make sure our index matches HEAD", 2005-11-03)
...and it was fixed again in commit
  3ec62ad9ffba ("merge-octopus: abort if index does not match HEAD", 2016-04-09)
...and again in commit
  65170c07d466 ("merge-recursive: avoid incorporating uncommitted changes in a merge", 2017-12-21)
...and again in commit
  eddd1a411d93 ("merge-recursive: enforce rule that index matches head before merging", 2018-06-30)

...with multiple testcases added to the testsuite that could be
enumerated in even more commits.

Then, finally, in a patch in the same series as the last fix above, the
documentation about this requirement was fixed in commit 55f39cf7551b
("merge: fix misleading pre-merge check documentation", 2018-06-30), and
we all lived happily ever after...

</quick summary>

Unfortunately, "ever after" apparently denotes a limited time and it
expired today.  The merge-recursive rule to enforce that index matches
head was at the beginning of merge_trees() and would only trigger when
opt->call_depth was 0.  Since merge_recursive() doesn't call
merge_trees() until after returning from recursing, this meant that the
check wasn't triggered by merge_recursive() until it had first finished
all the intermediate merges to create virtual merge bases.  That is a
potentially HUGE amount of computation (and writing of intermediate
merge results into the .git/objects directory) before it errors out and
says, in effect, "Sorry, I can't do any merging because you have some
local changes that would be overwritten."

Trying to enforce that all of merge_trees(), merge_recursive(), and
merge_recursive_generic() checked the index == head condition earlier
resulted in a bunch of broken tests.  It turns out that
merge_recursive() has code to drop and reload the cache while recursing
to create intermediate virtual merge bases, but unfortunately that code
runs even when no recursion is necessary.  This unconditional dropping
and reloading of the cache masked a few bugs:

  * builtin/merge-recursive.c: didn't even bother loading the index.

  * builtin/stash.c: feels like a fake 'builtin' because it repeatedly
    invokes git subprocesses all over the place, mixed with other
    operations.  In particular, invoking "git reset" will reset the
    index on disk, but the parent process that invoked it won't
    automatically have its in-memory index updated.

  * t3030-merge-recursive.h: this test has always been broken in that it
    didn't make sure to make index match head before running.  But, it
    didn't care about the index or even the merge result, just the
    verbose output while running.  While commit eddd1a411d93
    ("merge-recursive: enforce rule that index matches head before
    merging", 2018-06-30) should have uncovered this broken test, it
    used a test_must_fail wrapper around the merge-recursive call
    because it was known that the merge resulted in a rename/rename
    conflict.  Thus, that fix only made this test fail for a different
    reason, and since the index == head check didn't happen until after
    coming all the way back out of the recursion, the testcase had
    enough information to pass the one check that it did perform.

So, load the index in builtin/merge-recursive.c, reload the in-memory
index in builtin/stash.c, and modify the t3030 testcase to correctly
setup the index and make sure that the test fails in the expected way
(meaning it reports a rename/rename conflict).  This makes sure that
all callers actually make the index match head.  The next commit will
then enforce the condition that index matches head earlier so this
problem doesn't return in the future.

Signed-off-by: Elijah Newren <newren@gmail.com>
---
 builtin/merge-recursive.c  | 4 ++++
 builtin/stash.c            | 2 ++
 t/t3030-merge-recursive.sh | 9 ++++++++-
 3 files changed, 14 insertions(+), 1 deletion(-)

Comments

Johannes Schindelin Sept. 2, 2019, 11:01 p.m. UTC | #1
Hi Elijah,

On Sat, 17 Aug 2019, Elijah Newren wrote:

>   * t3030-merge-recursive.h: this test has always been broken in that it
>     didn't make sure to make index match head before running.  But, it
>     didn't care about the index or even the merge result, just the
>     verbose output while running.  While commit eddd1a411d93
>     ("merge-recursive: enforce rule that index matches head before
>     merging", 2018-06-30) should have uncovered this broken test, it
>     used a test_must_fail wrapper around the merge-recursive call
>     because it was known that the merge resulted in a rename/rename
>     conflict.  Thus, that fix only made this test fail for a different
>     reason, and since the index == head check didn't happen until after
>     coming all the way back out of the recursion, the testcase had
>     enough information to pass the one check that it did perform.

I fear that this test is still broken, it is a Schrödinger bug. Where
`qsort()` is the cat, and the property "is it stable?" instead of death.

In particular, at some stage in the recursive merge, a diff is generated
with rename detection for the target file `a` that contains two lines `hello`
but has two equally valid source files: `e` and `a~Temporary merge
branch 2_0`, both containing just the line `hello`. And since their file
contents are identical, the solution to the problem "which is the
correct source file?" is ambiguous.

If the `qsort()` in use is stable, the file `e` comes first, and wins.
If the `qsort()` in use is not stable, all bets are off, and the file
`a~Temporary merge branch 2_0` might be sorted first (which is the case,
for example, when using the `qsort()` implementation of MS Visual C's
runtime).

Now, the _real_ problem is that t3030.35 expects the recursive merge to
fail, which it does when `qsort()` is stable. However, when the order of
`e` and `a~Temporary merge branch 2_0` is reversed, then that particular
merge does _not_ result in a `rename/rename` conflict. And the exit code
of the recursive merge is 0 for some reason!

I don't quite understand why: clearly, there are conflicts (otherwise we
would not have that funny suffix `~Temporary merge branch 2_0`.

The real problem, though, is that even if it would fail, the outcome of
that recursive merge is ambiguous, and that test case should not try to
verify the precise order of the generated intermediate trees.

Ciao,
Dscho
Johannes Schindelin Sept. 3, 2019, 1:34 p.m. UTC | #2
Hi Elijah,

On Tue, 3 Sep 2019, Johannes Schindelin wrote:

> On Sat, 17 Aug 2019, Elijah Newren wrote:
>
> >   * t3030-merge-recursive.h: this test has always been broken in that it
> >     didn't make sure to make index match head before running.  But, it
> >     didn't care about the index or even the merge result, just the
> >     verbose output while running.  While commit eddd1a411d93
> >     ("merge-recursive: enforce rule that index matches head before
> >     merging", 2018-06-30) should have uncovered this broken test, it
> >     used a test_must_fail wrapper around the merge-recursive call
> >     because it was known that the merge resulted in a rename/rename
> >     conflict.  Thus, that fix only made this test fail for a different
> >     reason, and since the index == head check didn't happen until after
> >     coming all the way back out of the recursion, the testcase had
> >     enough information to pass the one check that it did perform.
>
> I fear that this test is still broken, it is a Schrödinger bug. Where
> `qsort()` is the cat, and the property "is it stable?" instead of death.
>
> In particular, at some stage in the recursive merge, a diff is generated
> with rename detection for the target file `a` that contains two lines `hello`
> but has two equally valid source files: `e` and `a~Temporary merge
> branch 2_0`, both containing just the line `hello`. And since their file
> contents are identical, the solution to the problem "which is the
> correct source file?" is ambiguous.
>
> If the `qsort()` in use is stable, the file `e` comes first, and wins.
> If the `qsort()` in use is not stable, all bets are off, and the file
> `a~Temporary merge branch 2_0` might be sorted first (which is the case,
> for example, when using the `qsort()` implementation of MS Visual C's
> runtime).
>
> Now, the _real_ problem is that t3030.35 expects the recursive merge to
> fail, which it does when `qsort()` is stable. However, when the order of
> `e` and `a~Temporary merge branch 2_0` is reversed, then that particular
> merge does _not_ result in a `rename/rename` conflict. And the exit code
> of the recursive merge is 0 for some reason!
>
> I don't quite understand why: clearly, there are conflicts (otherwise we
> would not have that funny suffix `~Temporary merge branch 2_0`.
>
> The real problem, though, is that even if it would fail, the outcome of
> that recursive merge is ambiguous, and that test case should not try to
> verify the precise order of the generated intermediate trees.

It might not be obvious from my mail, but it took me about 7 hours to
figure all of this out, hence I was a bit grumpy when I wrote that. My
apologies.

After having slept (and written a long review about the
`--update-branches` patch), it occurred to me that we might be better
off enforcing the use of `git_qsort()` in `diffcore-rename.c`, so that
we can at least guarantee stable rename detection in Git (which would
incidentally fix the test suite for the MSVC build that I maintain in
Git for Windows).

What do you think?

Ciao,
Dscho
Elijah Newren Sept. 3, 2019, 6:17 p.m. UTC | #3
Hi Dscho,

On Tue, Sep 3, 2019 at 6:34 AM Johannes Schindelin
<Johannes.Schindelin@gmx.de> wrote:
>
> Hi Elijah,
>
> On Tue, 3 Sep 2019, Johannes Schindelin wrote:
>
> > On Sat, 17 Aug 2019, Elijah Newren wrote:
> >
> > >   * t3030-merge-recursive.h: this test has always been broken in that it
> > >     didn't make sure to make index match head before running.  But, it
> > >     didn't care about the index or even the merge result, just the
> > >     verbose output while running.  While commit eddd1a411d93
> > >     ("merge-recursive: enforce rule that index matches head before
> > >     merging", 2018-06-30) should have uncovered this broken test, it
> > >     used a test_must_fail wrapper around the merge-recursive call
> > >     because it was known that the merge resulted in a rename/rename
> > >     conflict.  Thus, that fix only made this test fail for a different
> > >     reason, and since the index == head check didn't happen until after
> > >     coming all the way back out of the recursion, the testcase had
> > >     enough information to pass the one check that it did perform.
> >
> > I fear that this test is still broken, it is a Schrödinger bug. Where
> > `qsort()` is the cat, and the property "is it stable?" instead of death.
> >
> > In particular, at some stage in the recursive merge, a diff is generated
> > with rename detection for the target file `a` that contains two lines `hello`
> > but has two equally valid source files: `e` and `a~Temporary merge
> > branch 2_0`, both containing just the line `hello`. And since their file
> > contents are identical, the solution to the problem "which is the
> > correct source file?" is ambiguous.
> >
> > If the `qsort()` in use is stable, the file `e` comes first, and wins.
> > If the `qsort()` in use is not stable, all bets are off, and the file
> > `a~Temporary merge branch 2_0` might be sorted first (which is the case,
> > for example, when using the `qsort()` implementation of MS Visual C's
> > runtime).
> >
> > Now, the _real_ problem is that t3030.35 expects the recursive merge to
> > fail, which it does when `qsort()` is stable. However, when the order of
> > `e` and `a~Temporary merge branch 2_0` is reversed, then that particular
> > merge does _not_ result in a `rename/rename` conflict. And the exit code
> > of the recursive merge is 0 for some reason!
> >
> > I don't quite understand why: clearly, there are conflicts (otherwise we
> > would not have that funny suffix `~Temporary merge branch 2_0`.

So, there are conflicts in the inner merge, but depending on the
tie-breaker for rename handling when two equal matches exist (the
tie-breaker being the order of the filenames after qsort()), there may
or may not be conflicts in the outer merge.  Ouch.

I suspect such cases are pretty rare in "real world repositories"
because (1) exactly equal filename similarities are rare, (2) "slowly
changing trees of content" implies that most files will only be
modified on (at most) one side of history, (3) when files are changed
on both sides of history odds of conflicting changes rapidly go up
making conflicts likely.  You essentially have to thread a needle to
have the end result ambiguously conflict like this.

> > The real problem, though, is that even if it would fail, the outcome of
> > that recursive merge is ambiguous, and that test case should not try to
> > verify the precise order of the generated intermediate trees.

Yes, it is ambiguous -- and the problem is a little deeper too. It's
not just "does-this-merge-conflict?" depending upon the qsort order,
it is also about whether file contents after the merge depend upon the
qsort order.  Whenever there are two filenames that are equally
similar to a rename source, picking one of the two equally similar
filenames for rename pairing means we are basically choosing at random
where to merge the changes from the other side of history to.

Unfortunately, changing this might be difficult to enforce with the
current merge-recursive structure.  For example, what if there are two
equally similar filenames for us to choose from, but the other side of
history didn't modify the rename source file at all?  (e.g. on one
side of history, user leaves A alone, on other side of history, A is
copied to B and C and then A is deleted.  B and C are identical.)  In
such cases, the choice of which of B and C we pair A up with happens
to be irrelevant because we'll get the same result either way and
there should be no merge conflict.  But if we error out early or throw
warnings and conflict notices because the intermediate internal choice
was ambiguous, then we've created useless conflicts for the user.  I'm
worried we have more cases of this kind of thing happening than we do
with ambiguous pairings that change the end result.

I think I might be able to do something here with my alternative merge
strategy, but I haven't gotten back to that for quite a while, so...

> It might not be obvious from my mail, but it took me about 7 hours to
> figure all of this out, hence I was a bit grumpy when I wrote that. My
> apologies.
>
> After having slept (and written a long review about the
> `--update-branches` patch), it occurred to me that we might be better
> off enforcing the use of `git_qsort()` in `diffcore-rename.c`, so that
> we can at least guarantee stable rename detection in Git (which would
> incidentally fix the test suite for the MSVC build that I maintain in
> Git for Windows).
>
> What do you think?

Ooh, absolutely, we should do that in the short term.  Not just
because it fixes the testsuite, but because it increases the
likelihood that folks can reproduce each others' merge problems.  I
want to be able to help users on Windows who report problems and
provide testcases, and making this fix reduces one hurdle toward doing
so.

Patch
diff mbox series

diff --git a/builtin/merge-recursive.c b/builtin/merge-recursive.c
index 5b910e351e..a4bfd8fc51 100644
--- a/builtin/merge-recursive.c
+++ b/builtin/merge-recursive.c
@@ -1,3 +1,4 @@ 
+#include "cache.h"
 #include "builtin.h"
 #include "commit.h"
 #include "tag.h"
@@ -63,6 +64,9 @@  int cmd_merge_recursive(int argc, const char **argv, const char *prefix)
 	if (argc - i != 3) /* "--" "<head>" "<remote>" */
 		die(_("not handling anything other than two heads merge."));
 
+	if (repo_read_index_unmerged(the_repository))
+		die_resolve_conflict("merge");
+
 	o.branch1 = argv[++i];
 	o.branch2 = argv[++i];
 
diff --git a/builtin/stash.c b/builtin/stash.c
index b5a301f24d..4aa47785f9 100644
--- a/builtin/stash.c
+++ b/builtin/stash.c
@@ -427,6 +427,8 @@  static int do_apply_stash(const char *prefix, struct stash_info *info,
 				return error(_("could not save index tree"));
 
 			reset_head();
+			discard_cache();
+			read_cache();
 		}
 	}
 
diff --git a/t/t3030-merge-recursive.sh b/t/t3030-merge-recursive.sh
index ff641b348a..a37bcc58a0 100755
--- a/t/t3030-merge-recursive.sh
+++ b/t/t3030-merge-recursive.sh
@@ -667,15 +667,22 @@  test_expect_success 'merging with triple rename across D/F conflict' '
 test_expect_success 'merge-recursive remembers the names of all base trees' '
 	git reset --hard HEAD &&
 
+	# make the index match $c1 so that merge-recursive below does not
+	# fail early
+	git diff --binary HEAD $c1 -- | git apply --cached &&
+
 	# more trees than static slots used by oid_to_hex()
 	for commit in $c0 $c2 $c4 $c5 $c6 $c7
 	do
 		git rev-parse "$commit^{tree}"
 	done >trees &&
 
-	# ignore the return code -- it only fails because the input is weird
+	# ignore the return code; it only fails because the input is weird...
 	test_must_fail git -c merge.verbosity=5 merge-recursive $(cat trees) -- $c1 $c3 >out &&
 
+	# ...but make sure it fails in the expected way
+	test_i18ngrep CONFLICT.*rename/rename out &&
+
 	# merge-recursive prints in reverse order, but we do not care
 	sort <trees >expect &&
 	sed -n "s/^virtual //p" out | sort >actual &&