autofilling not optimal?

[skok-gpfw]

Hi

It's been more than 2 hours that git imerge is doing autofilling.
I'm not aware of the algorithm details, but it looks like it recomputes the same autofilling sequence start again and again after each backtracking

...
Autofilling 130-17...unexpected conflict.  Backtracking...
Autofilling 1-22...success.
Autofilling 2-22...success.
Autofilling 3-22...success.
Autofilling 4-22...success.
Autofilling 5-22...success.
Autofilling 6-22...success.
Autofilling 7-22...success.
Autofilling 8-22...success.
.... a lot 
Autofilling 129-15...success.
Autofilling 129-16...success.
Autofilling 129-17...unexpected conflict.  Backtracking...
Autofilling 1-22...success.
Autofilling 2-22...success.
Autofilling 3-22...success.
Autofilling 4-22...success.
Autofilling 5-22...success.
Autofilling 6-22...success.
Autofilling 7-22...success.
...

The 1-22 to 129-22 autofill sequence looks the same every time, and it takes a very long time.
Is it the same merge sequence it is doing again? or is it the print that is wrong?

[mhagger]

This happens when the bisect approach to finding the "farthest along" commits that can be merged gives an answer, but some of the intermediate merges can't be performed.

I've seen this phenomenon before, but I don't remember exactly what caused it. I think it was something like

• The two branches being merged have a lot of commits that are equivalent but not the same commit, or
• One branch contains a change as a single commit, and the other branch contains the same change split up into two commits, or
• One of the branches contained revert commits.

I don't really know the solution, short of either patience (it usually succeeds eventually) or eliminating whatever is confusing the algorithm. In principle you could also use the --goal=full option when starting the merge, then git imerge finish --goal=WHATEVER when you are done. That should avoid the repetitive merges at the expense of actually having to do every single one of the 130×17 merges once, so it depends on your particular situation whether that will actually be an improvement. Another approach that sometimes works is to do a merge/rebase to a commit before the problematic commits, then a second one to just after them, then finally the complete merge/rebase. The problematic range will still have to do some repetitive merging, but since it is much smaller, you get less of the O(N²) effect. Or, if you know that the problem is that some commits are identical, you might use git rebase --onto to rebase over them.

git-imerge could probably be smarter about this, at the expense of more bookkeeping. I don't expect to have time to work on this in the near future.

[skok-gpfw]

I don't think this particular use case correspond to the case you mentioned.
It had only a very few conflicts that I finally managed with a simple git rebase quite easily (few seconds vs several hours...)

This is too bad imerge is not "finished" (or not scalable) because it has helped me a lot in few other very complex rebase.

Thanks for your help anyway.