Cristian Amarie wrote:
>> [...] You are talking about any graph consisting of a sequence
>> of 'complete' merges[1] between the
>> two branches A and B. Is this a concrete example, where n=2 and m=3?
>>
>> / -- p ---- q ----- A1 -- s ----- A2
>> O \ \ / \ /
>> \ --- B1 --- B2 -- r ----- B3 -- t
>>
>> Here, p/q/r/s/t means a change that is not a merge. The p/q/r/s/t states
>> are the base candidates, not Ab and Bb.
>
> Ah... my mistake. But that is the idea, yes.
>
>> Did you mean, "(merge B into A produces Ax, where 1 <= x <= n)" and
>> "(merge A into B produces By, where 1 <= y <= m)"?
>
> Yes. B into A will produce in this example A3,
No, B into A in this example will be a no-op (no operation) merge, because all
of the changes from B are already included in A. There will be no change in
the working copy, so if you try to commit nothing will happen. There will be
no A3.
> A into B will produce B4
No, again it will be a no-op. I think we need some more changes on the graph,
like this:
/ --- p --- q ----- A1 ---- s -- j -- A2 -- v
O \ \ / \ /
\ h -- B1 -- B2 -- r -- i -- B3 ---- t -- u
Now, merging B into A would produce a new node A3:
/ --- p --- q ----- A1 ---- s -- j -- A2 -- v -- A3
O \ \ / \ / /
\ h -- B1 -- B2 -- r -- i -- B3 ---- t -- u -----
while merging A into B would produce a new node B4:
/ --- p --- q ----- A1 ---- s -- j -- A2 -- v
O \ \ / \ / \
\ h -- B1 -- B2 -- r -- i -- B3 ---- t -- u -- B4
> and my goal is to find bases which will have at least a way
> (path) for which A3 == B4 (symmetry).
OK, I think it will help if I try to explain the 'big picture'.
The reason I called this merge algorithm 'symmetric' is because, unlike
the existing (sync and reintegrate) merges, it behaves in the same way
no matter which branch was created first (A copied from B, or B copied
from A) and no matter which direction the previous merge went (A to B,
or B to A).
It is also true that this merge algorithm should produce the same basic
result no matter which direction you merge (A to B, or B to A). A3 and
A4 might not be textually identical, because in each merge there
are potentially some conflicts and the user (with the help of a tool)
might resolve the conflicts in slightly different ways. But
essentially, logically, yes, A3 == B4.
I have described (in the Wiki) how the algorithm will look for a base on A and
base on B and will then choose the later one. However, we do not really need
to find two different bases; that is just an implementation detail, an artifact
of how the existing (sync and reintegrate) merge code works. All we really
need is to find the latest one ('t' in these examples). The *same* base ('t')
is the correct base for a merge from A to B and the correct base for a merge
from B to A.
We could choose *any* node as the base for our 3-way merge, and the merge would
still work, in the sense that it would combine the correct sets of logical
changes, and A->B and B->A would give the same result. The only trouble with
choosing a poor base is that the 3-way merge will find more conflicts.
In graphs like the ones above (no criss-cross merges), the best base is the
latest of the ones named p/q/r/s/t, which is 't'. To show why it is 'best', we
can decompose each side of that merge (t -> v and t -> u) into a sequence of
logical changes:
t -> v is: (A2 v)
is: (j v)
t -> u is: (u)
So the 3-way merge has 't' as its base (origin), and one side has changes 'j'
and 'v' relative to that base, and other side has changes 'u' relative to that
base.
If we choose the older base 's' as the base for our 3-way merge, we can
decompose the two sides of that merge as:
s -> v is: (j A2 v)
is: (j s:B3 t v)
is: (j i t v)
s -> u is: (s:B3 t u)
is: (i t u)
Now the 3-way merge has 's' as its base (origin), and one side has changes (j i
t v) relative
to that base, and other side has changes (i t u) relative to that base.
The 3-way merge of the change-sequences (j i t v) and (i t u) will produce the
same result as the 3-way merge of the change-sequences (j v) and (u), but with
much more potential for conflicts -- and clutter for the user, if it is
displayed in a GUI. Remember that the logical changes 'i' might not be
textually identical how it appears in branch A and how it appears in branch B.
Also, the merges will even 'work' (but again with more conflicts than
necessary) if we choose something like A2 as the base. In that case, one path
will traverse *backwards* along the A2 -> t edge, and so the decomposed set of
changes seen will include *reverse changes*, which makes it even more confusing
for the user looking at the 3-way merge, although algorithmically it is still
correct.
Let me know if that doesn't make sense to you.
[...]
> You got my idea exactly (despite the clumsy description...).
> Also
> B2 -> r -> A1 -> B3 -> s -> t -> A2 ==> A3 (end in A)
> B2 -> r -> A1 -> B3 -> s -> A2 -> t ==> B4 (end in B)
> can be possible paths, if A3 == B4 is verified.
Those last two paths are strange: they do not strictly follow the 'merge
arrows' nor the 'natural history'. A1 -> B3 and s -> t are not simple 'edges'
of the graph, and A2 -> t is an edge but you are following it backwards.
- Julian
