monotone's LCA+DOM algo for selecting a merge base

[John A Meinel]

Denys Duchier wrote:
> Aaron asked about monotone's LCA+DOM algo for selecting a merge base.  I know
> essentially squat about monotone, but his question made think about why their
> selection algorithm might be correct.  In this email, I'd like to write up what
> I have thought of so far and offer it up for criticism and corrections.
> 
> My understanding of LCA+DOM is that given two revisions r1 and r2 to be merged,
> it picks a least common ancestor of r1 and r2 that is also a dominator of one of
> them.  A dominator of r is an ancestor of r that occurs on all paths to the root
> ancestor.  There is obviously always at least one dominator, namely the root
> ancestor.
> 

...

> Choosing such a r0 is difficult.  A simplification is to pick r0 so that, at
> least on one side, there are no paths to the root not going through r0.  This is
> what LCA+DOM does.
> 
> --Denys

I would agree that more conflicts are better than silent omissions.
Ultimately, though, there will always have to be a human involved.
Because text conflicts/no conflicts do not imply logical (in)correctness.

I thought one of our other ideas was to ask to find the merge base from
A to B, and from B to A, and if they differ, keep looking until they agree.

My understanding of criss-cross merge is that they would disagree on
which ancestor to pick, so we can be reasonably sure that it is the
wrong one.
We are already light-years ahead of CVS's merge algorithm.

I'm not 100% satisfied with bzr's weave merge. Having worked with it for
a while, I can see some pretty bad edge cases.
Here is one. Say you have 4 revisions with the texts:

     1
    'A'
    / \
   /   \
  2     3
'AB'   'AC'
   \   /
    \ /
     4
    'ABC'

If you go down the first branch (2 merges 3), the text in the weave will
look like:

1
2 1
3 1
4 2 3

{1
. A
}
{2
. B
}
{3
. C
}

However, if you go down the second branch (3 merges 2) you get:
1
3 1
2 1
4 3 2

{1
. A
{4
. B
}
{3
. C
}
[4
{2
. B
}
]4

This is caused because of a sorting issue. (And weaves cannot resurrect
old lines, etc). I don't know if Codeville would handle this better.
Edge versioning might handle it differently.

I think the primary problem is that we use implicit ordering, based on
the fact that line B comes after A, and when we merge we have to put it
in a line, rather than some sort of tree, where you could have multiple
lines 'next to' A.

Actually, if we could create some sort of tree representation, it might
also help our "O(N_lines)" issues. Since we don't have to go down all
branches of the tree. (I haven't worked through it thoroughly, though).

John
=:->

-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 249 bytes
Desc: OpenPGP digital signature
Url : https://lists.ubuntu.com/archives/bazaar/attachments/20060212/73002fad/attachment.pgp