Re: [Monotone-devel] Re: cherrypicking in monotone (was: interesting thread...)

[Nathaniel J. Smith]

On Mon, Dec 11, 2006 at 12:02:20PM +1100, William Uther wrote:
> I was hoping to test my ideas and try to implement cherry-picking in  
> monotone sometime soon.  But I got distracted and wrote up http:// 
> revctrl.org/OperationalTransformation instead.

Cool, that's a nice summary :-).

> Cherry-picking for monotone:
> 
> Assume we're cherry-picking the changes in B-C and merging them into  
> revision D.
> 
> a) Find the ancestor you'd use for three way merge, call it A.
> b) Pluck B-C and make a new branch with this change from A.  Call the  
> new revision C'.  If there are any conflicts then abort and tell the  
> user what conflicted - the conflicting revision is a dependency on  
> what they're trying to pull across and should probably be pulled  
> across too.
> c) either:
>      i) Modify C so it has C' as a parent, but otherwise no change.
>      ii) Merge C' and C to make C''.  C'' should be identical to C.   
> Auto-resolve all conflicts in favour of C (there shouldn't be any,  
> but there may be if you didn't abort in b).  Any descendants of C  
> should then be merged with C'' - this should always be a clean  
> merge.  I am wary of doing this (merging descendants with C'')  
> automatically though.

Especially because there may be descendents that you do not know about
at the time you do the cherrypick, so you have to be prepared to
handle there be unmerged descendents at arbitrary later times anyway.

> d) Merge C' with D and allow the user to resolve conflicts.
> 
> The end result is something that looks like http://venge.net/monotone/ 
> wiki/DaggyFixes .  But done post-hoc.  And it records the history  
> correctly so that you shouldn't get future conflicts (I think).

Probably should sit down and think about this some... I'm not quite
sure you avoid future conflicts, the way *-merge happens to work.  In
particular, suppose we start with:

      a1
     /  \
    /    \
   a2     a3
          |
          b1

and we want to cherrypick the a3->b1 change to a2.  Following this
procedure, we get:

      a1
     /| \
    / |  \
   a2 b2  a3
   | /|   |
   |/ |   b1
  b3   \ /
        b4

b2 is created by plucking b1, b3 and b4 are created by clean merges.
Now, the point of recording history in a cherrypick (from the merge
algorithm point of view, anyway, there are other, perhaps more
important reasons from workflow point of view) is that some future
merges that would have been conflicts if you merely plucked, will
become clean merges if you truly cherrypicked.  More concretely,
suppose we check out b3, change our scalar to 'c', and commit:

      a1
     /| \
    / |  \
   a2 b2  a3
   | /|   |
   |/ |   b1
  b3   \ /
   |    b4
  c1

This is the key point: merging c1 and b4 now should be a clean merge
to c, because we "know" that the b in b4 is "the same" as the b in b3,
that c1 overrode.

But, in fact, with (unique|multi)-*-merge, this is a conflict:

      a1*
     /| \
    / |  \
   a2 b2* a3
   | /|   |
   |/ |   b1*
  b3   \ /
   |    b4 <-- b4 has a * for unique-*-merge, not for multi-*-merge
  c1*

*(c1) = c1, *(b4) = b4 for unique-*-merge, {b1, b2} for
multi-*-merge.  The ultimate problem in either case is the * on the
b1.  *-merge quite reasonably observes that while c1 has seen and
defeated the edit made in b2, the edits made in c1 and b1 have never
seen each other, so to be conservative, a conflict should be raised.

We've in the past discussed other ways to design scalar merge
algorithms to avoid this kind of problem, e.g. Bram's "convergent
scalar merge" might behave differently here.  But it does seem clear
from this example that if you want cherrypicking to work in the strong
sense, using this post-hoc technique, then ultimately you have to find
something in *-merge's user model that you think is wrong.

I don't know what the story looks like for textual merging.  I have
like zero good analytical tools to understand how sequences can and
should behave under merging.

This is of course assuming you really care about strong cherrypicking;
for many of the cherrypicking use cases, pluck does just fine -- if
you're backporting fixes from mainline to an old release branch, you
probably are never going to merge those two branches anyway, so it
doesn't much matter if the VCS bends over backwards to get make that
hypothetical merge as clean as possible.  In other cases, you want the
VCS to tell you, e.g., which of the release branches have already had
the fix applied; here, some kind of post-hoc daggy fix is useful
because it records this info in history, it doesn't much matter how
easy it makes the merging.

You can also get into interesting issues wrt file identity and such
here, since monotone currently doesn't either suturing or any kind of
revival (so in particular, there's no way to write down that a file
created by a pluck is "the same file" as exists on some other parallel
branch).  People run into this problem in practice, because they want
to pluck over a patch that creates a file, then later they want to
pluck over some edit to that file, but monotone gets confused and
can't tell which file to apply the edit to...

> Now for the monotone questions...  It seems you're using *-merge for  
> merging (in roster_merge.cc).  When it gets a conflict on file  
> contents then fall back to resolve_merge_conflicts() (in merge.cc).   
> That first tries to do three-way-merging (in diff_patch.cc), and if  
> that fails calls out to a lua hook for the user to fix things.

Yes.

> a) I haven't traced much of monotone's three-way-merge yet.  I'm  
> guessing noone has thought about this, but does anyone know how  
> monotone's merge behaves relative to property TP2 of http:// 
> revctrl.org/OperationalTransformation ?  (I was going to have a think  
> about it, but I thought I'd ask first :)

I've just thought about it for about 10 minutes, so I'm not sure, but
I think

1) TP2 translated into merge terms is just associativity:
    merge(A, merge(B, C)) = merge(merge(A, B), C)
   or in graphical terms:
     A   B   C    A   B   C
      \ /   /      \   \ /
       D   /        \   D'
        \ /          \ /
         F     =      F'

2) (unique|multi)-*-merge have this property whenever D and D' both
   exist as clean merges, AND if one ordering has a conflict in it,
   then the other does as well.  I haven't written out the dotted-Is
   and crossed-Ts proof of this, so I could be wrong, but I think it
   follows pretty straightforwardly if you look at what the mark sets
   have to be and the lemmas in the original *-merge writeups.

> b) As far as implementing cherry-picking, it seems that the least  
> common ancestor for merge is found about line 80 of merge.cc.  Is  
> that the right place to be looking?

The actual common ancestor is found by content_merge_database_adaptor
in its constructor, by calling find_common_ancestor_for_merge.  Note
that this function's contract is just "find a good common ancestor for
3-way textual merging".  ATM this means, "if there is an LCA, return
that, otherwise, recursively call yourself on the set of minimal
CAs".  But we don't know that this is the best thing to do for textual
merging (though it's the best we know of), and you might want to think
whether being a good base for 3-way textual merge and trying to avoid
criss-cross issues is the same as being a good place to move a
daggyfix to.

-- Nathaniel