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

[Nathaniel Smith]

On Sat, May 07, 2005 at 09:42:53PM +0300, Oren Ben-Kiki wrote:
> 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.

Another option is to use something like codeville-merge, in which a
version is defined by its state, but its state includes information on
"how it got that way".

> 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.

Yes, that is one thing you can do with 3-way merge.

> > 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_.

Okay.  This formulation is reasonable, but it doesn't actually solve
the problem, just re-phrases it.  A common developer intent is, "take
everything new in this side and everything new on that side and smush
them together to make something that has both".

And in this phrasing, my argument is that there is, in general, no
ancestor that expresses that 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.

The problem is that people really do want to create arbitrary graph
topologies.  We can't help it within a branch, being a distributed
system; strange things just happen.  Between branches, you probably
don't want to have completely arbitrary merging policies, but
reasonable policies can get complicated enough that it's best for the
tool to just assume that it has to be able to deal with arbitrary
DAGs.  (Certainly, having a solution that works for arbitrary DAGs is
much more confidence inspiring than having a bunch of different
solutions that only work in particular special cases, and then just
hoping that no non-special cases ever show up.)

-- Nathaniel

-- 
So let us espouse a less contested notion of truth and falsehood, even
if it is philosophically debatable (if we listen to philosophers, we
must debate everything, and there would be no end to the discussion).
  -- Serendipities, Umberto Eco