[Top][All Lists]
[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
- Re: [Monotone-devel] Re: 3-way merge considered harmful, (continued)
Re: [Monotone-devel] Re: 3-way merge considered harmful, K. Richard Pixley, 2005/05/02
Re: [Monotone-devel] Re: 3-way merge considered harmful, Joel Crisp, 2005/05/02
Re: [Monotone-devel] Re: 3-way merge considered harmful, Florian Weimer, 2005/05/02
Re: [Monotone-devel] Re: 3-way merge considered harmful, Brian Campbell, 2005/05/03
Re: [Monotone-devel] Re: 3-way merge considered harmful, Sergio . Garcia, 2005/05/04
Re: [Monotone-devel] Re: 3-way merge considered harmful,
Oren Ben-Kiki <=
Re: [Monotone-devel] Re: 3-way merge considered harmful, Nathaniel Smith, 2005/05/13
Re: [Monotone-devel] Re: 3-way merge considered harmful, Oren Ben-Kiki, 2005/05/16
Re: [Monotone-devel] Re: 3-way merge considered harmful, Oren Ben-Kiki, 2005/05/07
Re: 3-way merge considered harmful (was Re: [Monotone-devel] merge weirdness...), K. Richard Pixley, 2005/05/02