Allow micromerges to be broken down even further

This was first discussed in #72.

Suppose an imerge is in the following state:

o---0---1---2---3
    |   |   |
    A---o---X
    |   |   |
    B---Y---?
    |
    C

Normally you would fill in ? by merging X and Y directly. But what if you realize that the change from 1 to 2 was actually too big, and it would be easier to resolve the merge in two steps? You might like to introduce a helper commit H, maybe like:

o---0---1---2---3
    |   |   |
    A---o---X
    |   |   |
    B---Y-H-M
    |
    C

In this situation, it is quite possible the "helper" step would be useful for later merges. For example, when it comes time, in the next row, to fill in this ?:

o---0---1---2---3
    |   |   |
    A---o---X
    |   |   |
    B---Y-H-M
    |   |   |
    C---T---?

it might actually be easier to first compute the merge of H and T, and then compute the merge of M and U:

o---0---1---2---3
    |   |   |
    A---o---X
    |   |   |
    B---Y-H-M
    |   | | |
    C---T-U-V

It would be nice if git-imerge could handle non-rectangular merge topologies like this, even if they arise while a merge is already in progress.

The simplification might be tricky in the general case. If the goal was a rebase, then it might be that the end result should be

o---0---A---B---C---T---U---V

It is not obvious where the commit messages for U and V should be taken from. Probably they should come from commits H and U, respectively, but it might be hard to get the user to type good and appropriate messages for these commits.

On the other hand, it might be that commits H and U were added only to help Git, and do not belong in the final history (for example, they might not even build). In that case, the final rebase result should be

o---0---A---B---C---T---V

and it is clear where the commit messages should come from.

It would be quite a lot of work to build this feature into git imerge, because a lot of the code assumes a "rectangular grid" topology of commits and merges.

I'm just a curious onlooker, very much a git noob, but I did have a similar idea a while ago, let me know if it's what you're talking about or if it'd be worth opening a separate issue for it: I was wondering whether creating this kind of helper commits could be automatically managed by git-imerge, i.e.: whenever git-imerge finds a conflict, it could be that the commits aren't modular enough, so what if it tried splitting the involved commits using the same splitting method used in git add -p? Maybe then the merge could proceed automatically, rather than the user explicitly creating commit H as in your example above (unless I misunderstood and you meant the commit would be created automatically?).

Another question I had was whether using a different merge algorithm (Patience, Diff Match and Patch, maybe others?) could be used as an attempt to automatically resolve conflicts that the default diff algorithm fails to deal with. But this is probably worth a separate issue, if at all (let me know).

Hi @waldyrious!

[...] I was wondering whether creating this kind of helper commits could be automatically managed by git-imerge, i.e.: whenever git-imerge finds a conflict, it could be that the commits aren't modular enough, so what if it tried splitting the involved commits using the same splitting method used in git add -p? Maybe then the merge could proceed automatically, rather than the user explicitly creating commit H as in your example above (unless I misunderstood and you meant the commit would be created automatically?).

It is approximately true that a merge only fails if there is a conflict within a single hunk of the diff. Since git add -p works hunk by hunk, it wouldn't be able to subdivide the conflict in any useful way.

Another question I had was whether using a different merge algorithm (Patience, Diff Match and Patch, maybe others?) could be used as an attempt to automatically resolve conflicts that the default diff algorithm fails to deal with. But this is probably worth a separate issue, if at all (let me know).

git-imerge doesn't actually do any merges or resolve any conflicts itself. It relies on git merge to do so. So to choose a different merge algorithm, we would basically need to pass the corresponding options down to git merge, I think. It seems like a reasonable thing to implement, though it is pretty much unrelated to this issue. The main question is what the user interface should look like. Would the user choose a different merge algorithm as part of their permanent config, or at the start of an imerge session, or for one particular micromerge, or ...?

I don't use other merge strategies, so this wouldn't be high on my own priority list. But patches are welcome :-)

It is approximately true that a merge only fails if there is a conflict within a single hunk of the diff. Since git add -p works hunk by hunk, it wouldn't be able to subdivide the conflict in any useful way.

I see, thanks for clarifying. It makes sense that it works that way already. So the H commit you're talking about would be manually created, and in a non-trivial way, I suppose?

It seems like a reasonable thing to implement, though it is pretty much unrelated to this issue.

Yes, sorry, it was silly of me to tack that into this issue. Anyway, I was thinking about git-imerge automatically trying different options to git-merge in case it finds a conflict with the default option, in the hopes that some of those could solve the issue. I have no idea whether that would be likely to make a difference, though.

Having explicit options for the user would be a nice extra, but I'm not sure that would be particularly useful or elegant, unless the user could predict which diffing algorithm would work best for their merge, and I assume most people aren't prepared to do that. Therefore, if there is to be any trial-and-error, I'd rather have the computer do it than myself.

mhagger / git-imerge

Allow micromerges to be broken down even further #79