Re: Newbie question regarding 3way merge order.

From: Raimund Berger <raimund.berger@gmail.com>
Date: Feb 2, 2009, 18:15 UTC
Message-ID: <87wsc8aenx.fsf@gigli.quasi.internal>
In-Reply-To: <49871ADA.4080905@viscovery.net>

Johannes Sixt <j.sixt@viscovery.net> writes:

Show 55 quoted lines

> Please don't set Mail-Followup-To: here, and keep the Cc: list.
>
> Raimund Berger schrieb:
>> do the following conditions hold
>> 
>> (i)  A+B == B+A for all commits A,B
>> (ii) (A+B)+C == A+(B+C) for all A,B,C
>> 
>> where "+" designates the standard git 3way merge?
>
> I don't think that (ii) does holds in general.
>
> [ In the examples consider each letter/symbol on a line by itself; this
> saves vertical space. ]
>
> Start with this (the merge base):
>
> 	f(a)
>
> and there are three topic branches growing from here:
> A makes this (rename f->g):
>
> 	g(a)
>
> B makes this (add another f):
>
> 	f(a)f(b)
>
> C makes this (renames a->c):
>
> 	f(c)
>
> Then A+B is
>
> 	g(a)f(b)
>
> A+C is
>
> 	g(c)
>
> B+C is
>
> 	f(c)f(b)
>
> (A+B)+C is
>
> 	g(c)f(b)
>
> but A+(B+C) is ambiguous:
>
> 	g(c)f(b)
> or
> 	f(c)g(b)
>
> -- Hannes

Are you sure you're not making assumptions about "obvious" manual resolutions? E.g. I can't quite see how A+B, which is

      g(a)----
     /        \
 f(a)          g(a)f(b) or f(a)f(b) ???
     \        /
      f(a)f(b)

would not be flagged as a conflict regarding f(a) vs. g(a).

Now, you may assume that because B leaves f(a) as it is while A changes f(a) into g(a) that both, that change and the addition of f(b) in B, should survive the merge. But the actual algorithm couldn't possibly know and decide that. Same goes for other merges you do there. In fact, in strict terms of how I defined equality, you didn't give a counter example because neither (A+B)+C or A+(B+C) automatically resolve. It would have been if one of them did.

And that's why I specifically "limited" my equality relation to automatic resolutions, to simplify the discussion and deal with kind of minimum requirements first. I didn't even mention that originally because I felt it was so obvious.

So only the next step would be looking at how manual resolutions play into this, and while that might be fairly intuitive in the A+B == B+A commutativity case, associativity of course is kind of a different ballpark. Although I'd expect somebody intimately acquainted with merging techniques capable of maybe giving a hint or two even in that case.