Merging and parents

Matthias Urlichs· Jul 5, 2005, 16:19 UTC · lore

I just had this ugly merge situation:

 M
 |\
 | \
 A  B
 |\/|
 |/\|
 C  D
 | /
 |/
 E

Suppose both the EC and the ED branch add files (not with conflicting filenames!) which then get modified somewhere between C/D and M.

No matter which node gets picked as the parent, some files will end up as "created on different branches" because the chosen parent doesn't have them, even though, strictly speaking, it ain't so.

So ... what to do? Generate a list of parents, and for each file pick the one parent where it (a) exists and (b) has the smallest diff? Or just ignore (umm... OK, document) the problem?

-- 
Matthias Urlichs   |   {M:U} IT Design @ m-u-it.de   |  smurf@smurf.noris.de
Disclaimer: The quote was selected randomly. Really. | http://smurf.noris.de
 - -
I'm thankful I didn't believe in God, because it
would have been another thing for me to conquer.
		-- Kim Goldman

Linus Torvalds· Jul 6, 2005, 03:26 UTC · re: Matthias Urlichs · lore

Re: Merging and parents

On Tue, 5 Jul 2005, Matthias Urlichs wrote:

Show 20 quoted lines

>
> I just had this ugly merge situation:
> 
>  M
>  |\
>  | \
>  A  B
>  |\/|
>  |/\|
>  C  D
>  | /
>  |/
>  E
> 
> Suppose both the EC and the ED branch add files (not with conflicting
> filenames!) which then get modified somewhere between C/D and M.
> 
> No matter which node gets picked as the parent, some files will end
> up as "created on different branches" because the chosen parent doesn't
> have them, even though, strictly speaking, it ain't so.

So walk me through it. Why is this ugly?

It's kind of interesting in that it has a merge-base that isn't unique any more: both C and D are "equally valid" merge bases, but do it really generate any real problems?

Let's say that you pick C as the merge base, which means that both A and B suddenly have the same new files show up (that came from D). Now, to make it interesting, let's say that D/B also modified that file, so that you have the merge at M see two different files just "show up".

The trivial merger will fail this case, for sure. So I agree that it's a problem for the _current_ stupid merger, but it's not a fundamentally hard thing to do per se. Go backwards in history, look for where it was created, and use that as the merge-base for that particular file.

So yes, the current merge is very very stupid. It's worked impressively well for the kernel, though, so stupid tends to often be "good enough". And since it _has_ been good enough, I personally haven't been motivated to try to improve the merge logic.

Basically, the first-level trivial merge that "git-read-tree -m" does is really meant to just cut down the list of files to a manageable level, so that you can do the "real work" on a per-file level without being bogged down by having 17,000+ files to work with.

So if you want to document that the current automatic merge is stupid, hey, go wild. It _is_ stupid. It's surprisingly effective, but that may be because of kernel development patterns and may not be true in other projects.

And if somebody wants to write a better merger than the current git-merge-one-file-script, I can only encourage you. I think git has the potential to have made the "normal case" so cheap that the algorithms in git-merge-one-file-script could be quite advanced, without it slowing down things noticeably. So to some degree I think git should _allow_ for doing very complicated merges, exactly because it efficiently pinpoints the effort to the place where it is needed. So a lot of merges that are interesting in theory but aren't _practical_ as a main merge, might actually be practical with git.

		Linus