monotone-devel
[Top][All Lists]
Advanced

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Re: [Monotone-devel] Re: 3-way merge considered harmful


From: Oren Ben-Kiki
Subject: Re: [Monotone-devel] Re: 3-way merge considered harmful
Date: Sat, 7 May 2005 21:42:53 +0300
User-agent: KMail/1.7.2

> May 2005 00:29:48 -0700, Nathaniel Smith <address@hidden> said:
>
> njs> Here's another pathological case for 3-way merge:
> njs>    A
> njs>    |
> njs>    B
> njs>   / \
> njs>  C   D

I'd like to throw in $0.02 worth here.

First, this problem has nothing to do with project file operations. The 
same thing would happen if you were talking about adding, removing and 
changing lines in a text file.

It seems to me you have two ways to go about solving this. The first is 
that a merge doesn't consider the state of the file (or project tree or 
whatever), but also the history leading to it. Taking this road to its 
logical end you end up with something like Darcs. In such a system, a 
version is defined as the sum of a set of deltas, rather than as a 
particular state.

On Wednesday 04 May 2005 18:41, address@hidden wrote:
> As I see it, this case and the criss-cross problem just show that
> picking any common ancestor is not enough to provide a "correct"
> merge ancestor (one that doesnt lose work), and much less a "nice"
> merge ancestor (a correct merge ancestor that also never requires the
> users to solve the same conflict twice).

Exactly. The second way is to stick with only using the three states of 
the file (or project tree or whatever). It is then inevitable that the 
choice of ancestor will affect the end result of a 3-way merge.

You can view this as a feature more than a bug. For example, using 3-way 
merge, with appropriate common ancestor selection, yields a 
"cherry-picking" operation:

    /-> B --> C
   A
    \-> D --> E

A 3-way merge of C and E using "B" as a base would "cherry-pick" the 
B-->C change and apply it to E. True, "B" isn't even an ancestor of E, 
unless one considers reverse deltas; but that just drives the point 
that the "base" for a 3-way merge is a different thing from "least 
common ancestor", depending on what you are trying to achieve.

> I fail to imagine an example 
> where the LCAD algorithm could be not correct by choosing an ancestor
> such as A in your example.

In a state-based (rather than delta-state) system, selecting the 
ancestor for a 3-way merge becomes a semantical operation; it reflects 
the _intent_ of the operation. This means there's no way to discover 
the one and only "true" common ancestor for merging versions B and E 
above; there is simply no such thing. The best the system can do is 
provide an automated way to locate the ancestor which causes the merge 
to reflect _a particular developer intent_.

> Im also not very convinced yet that there exists no algorithm to find
> a nice merge ancestor. Even then, I personally would be willing to
> solve the same conflict twice once in a while, if it was necessary to
> be able to use a standard 3-way merger to solve conflicts.

Certainly the system can compute the correct ancestor for a particular 
intent, such as merging a branch back to the main trunk etc. However, I 
suspect that any such algorithm must, to some extent, rely on 
meta-information that is not available in the topology itself (call 
this the expected development "workflow").

BTW, in a Darcs-like system, the situation isn't much different. For the 
system to automatically select the set of deltas to include in a 
system, it again must rely on such meta-information.

Put another way - if Monotone, or Darcs for that matter subscribed to a 
particular workflow methodology (trunk/branch, development/release, 
etc.) then there would be no problem in the first place. However both 
systems attempt at providing basic building blocks which can be used to 
implement many types of workflows. Well, surprise - this means that 
when you use these building blocks, _you_ have to decide on how to 
apply them according to _your_ particular workflow, and there are some 
ways to apply them that make little or no sense.

Nathaniel's pathological case is an example of a nonsensical usage of 
3-way merge, just like "char *p = 0; *p = 'a';" is a nonsensical use of 
C pointers; this doesn't mean 3-way merge, or pointers, are inherently 
useless, or need to be "fixed" somehow.

Have fun,

        Oren Ben-Kiki




reply via email to

[Prev in Thread] Current Thread [Next in Thread]