Re: [Monotone-devel] Re: [cdv-devel] more merging stuff (bit long...)

[Nathaniel Smith]

On Sat, Aug 06, 2005 at 02:05:43PM -0500, Timothy Brownawell wrote:
> On Sat, 2005-08-06 at 02:08 -0700, Nathaniel Smith wrote:
> >   1) whenever a user explicitly sets the value, they express a claim
> >      that their setting is superior to the old setting
> 
> This claim is "in revision XXX, the value is set to 'a', overriding the
> values set in revisions {YYY, ...}".

Sort of.  I think you have the right idea, but your description sounds
more like a description of what was recorded, and here I want to talk
about what the user's implied intentions are.  Merging is all about
inferring intentions.

> >   2) whenever a user chooses to commit a new revision, they implicitly
> >      affirm the validity of the decisions that led to that revision's
> >      parents
> >     Corollary of (1) and (2): whenever a user explicitly sets the
> >      value, they express that they consider their new setting to be
> >      superior to _all_ old settings
> 
> How does this work WRT merge(a,b)=a? Does the new 'a' setting override
> the old 'a' setting, or only the 'b' setting?

The way I do it in here is that if merge(a, b) raises a conflict, then
whatever the user puts in is a new setting.  If it doesn't raise a
conflict, then it doesn't count as a new setting.

> > The other funky case is this thing (any clever name suggestions?):
> >     a
> >    / \
> >   b*  c*
> >    \ / \
> >     c*  d*
> > Merging here will give a conflict, with my algorithm; 3-way merge
> > would resolve it cleanly.  Polling people on #monotone and #revctrl,
> > the consensus seems to be that they agree with 3-way merge, but giving
> > a conflict is really not _that_ bad.  (It also seems to cause some
> > funky effects with darcs-merge; see zooko's comments on #revctrl and
> > darcs-users.)
> > 
> > This is really a problem with the user model, rather than the
> > algorithm.  Apparently people do not interpret the act of resolving
> > the b/c merge to be "setting" the result; They seem to interpret it as
> > "selecting" the result of 'c'; the 'c' in the result is in some sense
> > the "same" 'c' as in the parent.  The difference between "setting" and
> > "selecting" is the universe of possible options; if you see
> >    a   b
> >     \ /
> >      c
> > then you figure that the person doing the merge was picking from all
> > possible resolution values; when you see 
> >    a   b
> >     \ /
> >      b
> > you figure that the user was just picking between the two options
> > given by the parents.  My user model is too simple to take this into
> > account.  It's not a huge extension to the model to do so; it's quite
> > possible that an algorithm could be devised that gave a clean merge
> > here, perhaps by separately tracking each node's nearest marked
> > ancestor and the original source of its value as two separate things.
> 
> I think this could be solved by considering both 'b' revisions as one
> entity, which overrides settings from parents of the first 'b' revision,
> and also the 'a' revision (after the creation of the second 'b'
> revision). pcdv would say that the second 'b' overrides the 'a'
> revision, what about instead considering them as a single group that
> overrides parents of any member, and all members of which are overridden
> by any child that overrides one member? To handle the cases given as
> "ambiguous clean", this scheme would have to allow a revision to belong
> to multiple groups. A "group" would be a revision, and all descendents
> that haven't changed names.

I'm afraid I'm really not following this.  What does "consider as one
entity" mean, and "a single group", and so on?  Could you give some
examples or something?

> > Relation to other work
> > ----------------------
> > 
> > This algorithm is very close to the traditional codeville-merge
> > approach to this problem; the primary algorithmic difference is the
> > marking of conflict resolutions as being "changes".
> 
> Not sure about traditional cdv-merge, but if conflict resolutions are
> only considered changes WRT parents they don't match I think it's the
> same as pcdv. I think that doing things this way (and therefore allowing
> multiple least-common-marked ancestors) could get rid of the "ambiguous
> clean" case(s), and would be otherwise identical.

Hmm, in traditional cdv tree-merging, all merges are marked the same
-- if the name is totally new, it's a new change; if it has the same
value as a parent, it's not.  _Because_ of this, it hits ambiguous
clean in some simple cases, like the classic criss-cross:
   |
   a
  / \
 b*  c*
 |\ /|    (marked like traditional cdv-merge would, IIUC)
 | X |
 |/ \|
 b   c

Here *(b) is an ancestor of c, *(c) is an ancestor of b; you lose.

It's exactly that I mark the conflict resolutions as changed, that
eliminates ambiguous clean merge.

(ambiguous clean merge is sufficiently annoying that I feel like I'm
using too weak a verb there.  "annihilates"?  "obliterates"?

maybe I'm taking this too personally.)

-- Nathaniel

-- 
Damn the Solar System.  Bad light; planets too distant; pestered with
comets; feeble contrivance; could make a better one myself.
  -- Lord Jeffrey