Newbie question regarding 3way merge order.

Hi guys

I got a dumb question for you to wholeheartedly laugh at, and to which the answer seems to be so self evident. I'd still like a possibly authoritative statement though, just for the books.

The question is whether a (3way) merge is commutative, purely in terms of content (i.e. disregarding commit history for now). Iow if no matter in which order I merge A and B, i.e. A into B or B into A, I'd be guaranteed to arrive at the same content.

If yes, a followup question would be if the merge machinery sitting beneath rebase is exactly the same as that of a standard merge.

The reason I ask is obvious I guess. What basically interests me is if I gave a bunch of topic branches exposure on a test branch and, after resolving issues, applied them to stable, that I could be 100% sure to not introduce new issues content wise just by applying merges in a different order or form (rebase, patch set).

Thanks for feedback, Raimund.

Yes / No / Unknown ? 

[replying only because no one else did; caveat reader!]

On 2009-01-29, Raimund Berger <raimund.berger@gmail.com> wrote:

I'd say yes. Finding the common ancestor and then applying the differences from both sides are operations that do not appear to be order dependent.

The merge "machinery" can be explicitly chosen using the "-s" (strategy) option, but for the same chosen strategy, I think yes it would be the same for a merge as for a rebase.

That appears to be a different question than the one you started with.

Reversing A and B is one thing, applying a sequence of merges in a different order is quite something else.

Sitaram Chamarty <sitaramc@gmail.com> writes:

That's exactly the point which I'd like to have clarified.

E.g. with A, B and ancestor C, the merging and conflict resolution algorithm had to be completely symmetric if diff(A,C)+diff(B,C) applied to C should always be the same as diff(B,C)+diff(A,C) applied to C.

So I'm really asking if that is a fact upon which I can rely.

An interesting hint. Up to now, I assumed that rebase would always perform implicit merging strategies. I mean what else would one expect in the above picture to happen when rebasing A on B? I'd assume it'd produce the same tree as a merge of A into B, by employing exactly the same machinery. E.g. fast forward of C to B, then merge A in. So that, effectively, the only difference between rebase and merge is just commit history but not (tree) content.

has to be explicitly requested via '-m'. Which makes me wonder how the default rebase actually works.

Mathematically speaking, if A1 and A2 commute with regard to a binary operation, A1 ... An do as well. So I'd still think the latter question boils down to the commutativity question above *iff* rebase actually does an implicit merge by default. Which I'm now led to question.

Thanks for you answer, much appreciated.

On 2009-01-30, Raimund Berger <raimund.berger@gmail.com> wrote:

I've always relied on it :-) Or, to put it another way, I've never come been bitten by this issue.

It does.

This is also true. For example, "git help pull" offers an option to use rebase instead of merge.

No. I think the documentation is not sufficiently clear. Everything else in "git help rebase" (look for the string "strateg") tells me that the default, if you don't specify anything at all, is the recursive merge strategy. Since "-s" implies "-m", I'm not sure what -- if anything -- is achived by "-m" all by itself.

When I get some time I'm planning to look at the test scripts and simulate them without "-m" to see what differences there are; I'd assume a test script set up to test the proper operation of rebase --merge should be using a test case whose result differs if you dont use --merge!

Rebase *does* do an implicit merge by default (as far as the tree that results is concerned, which you mentioned right at the start), I'm pretty sure of it.

Perhaps someone with more git smarts will chip in with something more concrete.

Sitaram Chamarty <sitaramc@gmail.com> writes:

[snip] ...

I'm myself, especially since a conflicting rebase leaves the index in an "unmerged" state. Much like a regular merge does. It's still all assumptions though, or maybe I'm missing documentation .... (?)

That'd really be awesome. I mean, it's ok for me to dig through source code and find answers myself, but it would really save time if somebody who knows for sure dropped a word or two.

Quoting "Raimund Berger" <raimund.berger@gmail.com> writes:

The rebase command you run with neither -m nor -i option replays your work on top of the upstream by running git-am with the --3way option.

This commit introduced the feature.

commit 7f59dbbb8f8d479c1d31453eac06ec765436a780
Author: Junio C Hamano <junkio@cox.net>
Date:   Mon Nov 14 00:41:53 2005 -0800

    Rewrite rebase to use git-format-patch piped to git-am.
    
    The current rebase implementation finds commits in our tree but
    not in the upstream tree using git-cherry, and tries to apply
    them using git-cherry-pick (i.e. always use 3-way) one by one.
    
    Which is fine, but when some of the changes do not apply
    cleanly, it punts, and punts badly.

    [omitting the rest]

The message talks about what was wrong with the original, what benefit it gives the users, and how to use it, but it doesn't discuss how the magic works in detail.

Junio much later describes how it works, taking a real-world example in this message:

http://thread.gmane.org/gmane.comp.version-control.git/46569/focus=46609

In short, it works by applying your changes as patches but when a patch doesn't apply it falls back to a simplified three-way merge.

http://thread.gmane.org/gmane.comp.version-control.git/100579/focus=100602

I think Junio misremembered the history in his last message in the thread. He says that rebase was originally a format-patch piped to am, but before the commit 7f59dbbb8f8d479c1d31453eac06ec765436a780 it was done by a series of cherry-pick.

Nanako Shiraishi <nanako3@lavabit.com> writes:

Ugh. OK, that really explains a lot alright. Especially that fundamental change in rebase behavior makes it quite clear that the various techniques for "merging" content might not be as consistent as I had hoped. In my ideal world they'd only differ in how they map out commit history, but obviously that's not the case.

To me, this really leaves questions open regarding a hassle free workflow. Since one apparently can't be confident that conflict resolutions obtained in some testing or early integration branch will easily carry over to stable it looks like special measures need to be taken, like strict observation of merge order/technique and employment of replay tools.

So serialization apparently can't entirely be lost, and where e.g. CVS kind of enforces it at an early stage through expensive branching it seems git still requires some of the same coordination just at a different level resp. point in time.

Hey, thanks a bunch for taking the time carrying those links together. They've been very informative.

Sitaram Chamarty <sitaramc@gmail.com> writes:

This point is true in theory but I haven't found it to cause problems in practice. Textual conflicts between topics do happen, but it does not happen so often in overlapping areas across more than two topics that earlier resolutions to them cannot be reused by the rerere mechanism.

Semantic conflicts and dependencies are harder to deal with.

Suppose you have a topic to introduce feature A. You propose an enhancement, validate what it does logically makes sense, queue it to the testing integration branch and unleash it to the world for real world testing.

    ---o-------*     test integration branch
      /       /
     /       o       feature A
    /       /
   o---o---o---o---o mainline

Later, you find out that there is a bug B, and your enhancement to implement A does not work as intended when B triggers.

You could do two things.

 (1) You extend feature A topic and queue the fix there.

    ---o-------*---*  test integration branch
      /       /   /
     /       o---o    feature A + bugfix B
    /       /
   o---o---o---o---o  mainline

 (2) Because B is an independent bug, you can have its own topic to fix it
     and merge ot to test integration, planning to merge it later to
     mainline independently from feature A topic.

      ---o-------*---*   test integration branch
        /       /   / 
       /       /   o     bugfix B
      /       /   /
     /       o   /       feature A
    /       /   /
   o---o---o---o---o     mainline

Neither is satisfactory.

The former is bad because it takes hostage of a useful bugfix to the feature. Without adding the feature A, which may or may not be what people want to have, you cannot merge the fix to the mainline.

The latter is better because bugfix B could independently be merged to mainline, but it risks you forgetting to merge it when you merge feature A to the mainline. By the time you decide to merge feature A to the mainline, the test integration branch has had both for some time, and you didn't seen the problem bug B causes to feature A there, but if you merge only feature A but not fix B to the mainline, suddenly you have a buggy feature on the mainline.

This is where you need to use the tool right to get the most out of it.

You could do this in addition to (2).

 (3) Because B is an independent bug, you can have its own topic to fix it
     and merge it to the test integration, planning to merge it later to
     mainline independently from feature A topic.  But you already know
     feature A depends on bugfix B to work correctly, so you merge the fix
     to the feature as well in advance.

      ---o-------*---*   test integration branch
        /       /   / 
       /       /   o     bugfix B
      /       /   / \
     /       o-------*   feature A
    /       /   /
   o---o---o---o---o     mainline

This way, even if you later choose to merge feature A, forgetting that you have to have bugfix B for it to work, to the mainline, the merge will bring in the necessary fix with it automatically.

      ---o-------*---*   test integration branch
        /       /   / 
       /       /   o     bugfix B
      /       /   / \
     /       o-------*   feature A
    /       /   /     \
   o---o---o---o---o---* mainline

This technique to resolve conflicts and dependencies early between topics to force a merge order to the mainline can be used not only to deal with semantic conflicts but textual ones, too. If two branches textually interact badly, you prepare a consolidated topic between the two, so that you can merge A alone, B alone, or A+B together to the mainline.

If you end up merging A first and then want to merge B later (or the other way around, merge B and then A), and if the second merge to the mainline causes huge textual conflicts, you can instead merge the conslidated topic A+B to the mainline.

On 2009-02-01, Junio C Hamano <gitster@pobox.com> wrote:

[snip]

Thanks; great explanation. I notice you blogged it too, and similar to the "Never merging back" post, the message is: if something is (or is likely to be) an independent feature, it should have its own branch and be merged into others as soon as it is known they need it. (In that post, it was a random crazy feature that one might normally dump into a customer branch, here it's a bugfix B that you might naively dump into feature A, but the basic logic is the same)

Junio C Hamano <gitster@pobox.com> writes:

[snip]

You seem to suggest that juggling merges is possible in the exact way I was inquiring about. So let me ask again:

if M1 and M2 are merges and I define equality of merges (M1==M2) to be

- M1 resolves automatically (on the textual level) iff (if and only if)
  M2 does
- if either resolves automatically, the tree produced by M1 is the same
  as that of M2 (the tree SHAs are the same)

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?

[snip]

One could imagine (corporate) policies though which might try to map organizational "entities" (tasks, teams, according responsibilities) to branches. I.e. contexts where conflict resolution through merging might not always be desired and they'd rather be sought on a branch, i.e. by producing a commit on either branch which resolves a possible conflict. That's why I asked how rebase compares to merge and whether the merge machinery underlying the former is exactly the same. I seem to understand by now though that it is not.

Please don't set Mail-Followup-To: here, and keep the Cc: list.

Raimund Berger schrieb:

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

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

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.

Again: Don't set Mail-Followup-To and keep the Cc list if you want to
communicate efficiently on this list.

Raimund Berger schrieb:

My introductory sentence was probably not clear enough. I meant:

  mergebase	A	B	A+B
	f	g	f	g
	(	(	(	(
	a	a	a	a
	)	)	)	)
			f	f
			(	(
			b	b
			)	)

There is no conflict in A+B. But strctly speaking, this could be regarded as an ambiguous merge since the change f->g could be applied to two places. But if context is taken into consideration, then there is no conflict in practice.

Yes, it was so obvious, that I thought my statement about "colums are lines" and "saving vertical space" were obvious, too.

-- Hannes

Quoting "Raimund Berger" <raimund.berger@gmail.com>:

I think three-way merge of A into B and B into A will produce the same result when the merge doesn't conflict (when it does, you will get the conflict markers and text from A and B in a different order depending on the direction of the merge).

I don't think you can make a blanket conclusion like that by only knowing that merging A into B and merging B into A would produce the same result.

If you merge topics A, B, and C in this order into your current state O, there may not be any conflict, but if you merge the same topics to the same current state in different order, C, B and then A for example, you may get conflicts that breaks the merge. The commutativeness only says that merge of A into O will produce the same result as merge of O into A. It doesn't say anything about what would happen when you merge B to O.

Nanako Shiraishi <nanako3@lavabit.com> writes:

That's correct. Strictly speaking one would also have to verify associativity. I.e. whether merge(merge(A,B),C) == merge(A,merge(B,C)) for all A,B,C.

Thanks for making an implicit point explicit. So a followup question would be: is git's 3way merge associative?