Re: [Monotone-devel] merge algorithm question

[Nathaniel Smith]

On Fri, Dec 09, 2005 at 11:48:27AM +0100, Markus Schiltknecht wrote:
>  A
>  | \
>  |   B
>  |   | \
>  |   |  C
>  D---M1 |
>   \--+--M2
>      |  |
>      E  |
>       \ |
>        M3

> Actual monotone rosters takes A as common ancestor when creating M3,
> which renders previous merges useless. I see it would be problematic to
> take another ancestor, but couldn't previous merges M1 and M2 be taken
> into account somehow? This would reduce a lot of work when merging.

Well, the question is the "somehow" :-).  It's an area of ongoing
research.

One thing to note is that with the roster merger, the "common
ancestor" is _only_ used for file contents that have been edited in
both parts of the tree.  File names, attrs, and the first pass of file
content merging all use the *-merger, which does not depend on
choosing a common ancestor and AFAIK should handle this fine.

In general, though, and without doing lots of careful analysis on your
case, yeah, we may not be able to handle it perfectly; more
sophisticated content mergers like weave mergers might do better.
However, there are currently no weave mergers known that have either a
complete theoretical analysis; in fact, they all still have known
cases where they will silently and surprisingly mismerge.  So for now
we just added the part that we knew how to get right, and it should do
_much_ better than what we have now, even if it's not perfect for
everything...

Hope that helps,
-- Nathaniel

-- 
"...these, like all words, have single, decontextualized meanings: everyone
knows what each of these words means, everyone knows what constitutes an
instance of each of their referents.  Language is fixed.  Meaning is
certain.  Santa Claus comes down the chimney at midnight on December 24."
  -- The Language War, Robin Lakoff