Re: [Monotone-devel] What are rosters?

[William Uther]

On 17/08/2007, at 9:54 PM, Nathaniel Smith wrote:

> On Fri, Aug 17, 2007 at 05:03:53PM +1000, William Uther wrote:
> > Hi,
> >   I'm trying to make DieDieDie merge go away.  I think I'm close,
> > but I need to understand the core monotone code better....
> >
> >   So, er, exactly what are rosters?
>
> A few different things -- mostly they are a data structure defined in
> roster.{hh,cc} and used throughout the code.

[snip - helpful response]

Thanks :) - that was useful.

My current thoughts for getting rid of Die Die Die are along these  
lines:

  - Add marks to the roster for adds and deletes, BUT these marks  
are only in the marking map for the revision where that node was  
added or deleted, not their children.  The result is that the marking  
maps don't grow without bound.

  - I think this procedure is equivalent to mark-merge:
    - If a node is in the same state on both sides of a merge then  
it is in that state in the result.  Otherwise,
    - If a node is in different states on either side of a merge  
then we check the uncommon ancestors (UA) on each side of the merge  
for marks.  If one side has a mark and the other side doesn't, then  
that side wins cleanly.  If both sides have a mark then there is a  
conflict.
    - If the nodes are in a different state on each side of the  
merge, but neither set of uncommon ancestors has a mark, then we've  
got an invariant failure.

  My intuition for why this simple check is the same as mark-merge  
is using the deterministic mark-merge associativity and commutivity.   
If we started with just the common ancestors and merged them, then  
we'd get the same result regardless of order - either a scalar or a  
conflict.  If the result is a conflict then that (in the current  
monotone) must result in a mark in an uncommon ancestor on each  
side.  If there is any mark in the uncommon ancestors on either side  
(including resolving conflicts), then that must be a mark not in the  
other side (because these are the _uncommon_ ancestors), and hence  
the mark sets will be different.  But if we end up with the same  
value on both sides then it is just an accidental clean merge, so  
that is ok too.

  The final result for merging is pretty simple.  We could have  
incremental marking maps go away entirely, and just mark individual  
rosters.  Once you have the uncommon ancestor sets, then you simply  
pass over them looking for marks on any files that are in either of  
the revisions you're merging.  You only need to keep a boolean for  
each node_id (for each type of mark).

  Or have I mis-understood something?

Be well,

Will      :-}