git rebase between merges results in conflicts in completely unrelated files

Question

I have a large Git repository where a bug has been introduced some months ago and I’d like to bisect it, by first introducing a commit back in the past of the repository and then replaying the merges (doing rebase onto the new commit), as indicated in the diagram below.

I understand that due to the merges, Git does not seem to work as well as expected, but I’d like to have a better idea why that happens (and if there are parameters which could help it work better).

• The file modified in patch is never modified again by any commit in master

• I tried rebase with and without --preserve-merges, and both failed at some merge not far from the commit patch

• The differences shown in the conflicts make no sense, e.g. some whitespace in a file, unrelated lines in another... is there any useful information I could try to extract from them, or is it simply garbage and I should not spend any time trying to understand it?

• Is there a different parameter/merge strategy that could help advancing the merges?

Note: in the end, my combination of git apply; git bisect did work, but I’m still interested in alternative solutions or explanations about Git’s behavior.

Answer 1

The basic problem is simple to describe but hard to solve.

You're at the tip of master. Those commit graphs are nice, but hard to type in :-) so let's use a very simplified ASCII one here. (This is just a restatement of the problem, simplified and with different labels.)

                D
              /   \
A - B ----- C       F - G   <-- master
              \   /
                E

Here, a bug is introduced at commit B and hence present in every child commit (C through G). To put in a fix, we want to create a new sequence of commits (I'll use lowercase letters rather than C', D', etc) with the fix x installed as a new commit:

                d
              /   \
A - B - x - c       f - g   <-- [anonymous; will become master]
              \   /
                e

In order to do this, git (git rebase -p in this case—note that a typical rebase removes merge commits!) must make new commits based upon the existing commits. For non-merges like new commit c, this is not too tricky: rebase gets a diff of C vs B and then applies that patch to the source tree attached to commit x. That is, rebase does git cherry-pick master~3 while on the new anonymous branch. No problem so far! Now rebase needs to create commit d, which is also not a problem, it just needs to do git cherry-pick master~2, which it does, giving:

                d
              /
A - B - x - c

Making e is a bit trickier because its parent commit should be c. In principle, rebase leaves d hanging, rewinds to c, and does git cherry-pick master~1^2 to copy E. (I think the rebase script actually does its own git commit-tree operations so that it doesn't have to rewind the anonymous branch, but this works out the same, it just involves some internal hairiness here.) This gives us:

                d
              /
A - B - x - c
              \
                e

This is where we hit a problem: how will rebase create a merge commit f? It can't compare the tree for commit F against that for D: that's just one half of the merge. It can't compare F against E either: that's just the other half of the merge. So it can't use git cherry-pick as this requires picking one side or the other of the original merge.

The solution rebase uses is to run git merge (or rather the internal bits that git merge runs). This way any changes introduced by x that continue through the new d and e are handled correctly as well.

(This does introduce an entirely different problem: if F is an "evil merge", i.e., a merge that changes things not changed in either parent, the reproduced tree for merge f won't match up with the tree for F, as git will never see the "evil merge" changes. What's needed is a variant of cherry-pick that can compare the merge commit's tree against all its parents—as a combined diff of sorts, except more complete than git's standard combined diff—and apply that diff to all the input trees. But there's no such octopodal-cherry-pick [git calamari-pick?], so it's just not available.)

---

Anyway, this kind of rebase uses merge, and here you're seeing the same merge conflict that, presumably, occurred during the original merge. If you simply solve it again the same way—using git rerere for instance—that would allow you to proceed. Unfortunately, there's no way to retroactively turn on git rerere (even though I think it's easy enough to write such a thing).