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

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, ...}".

>   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?

>   3) A "conflict" should occur if, and only if, the settings on each
>      side of the merge express parallel claims.
[...]
> Funky cases
> -----------
> 
> There are two funky cases I know of.
> 
> Coincidental clean merge:
[...]
> I'm not actually sure what the right semantics would be, though.  If
> we're merging:
>     |
>     a
>    / \
>   b   b
>    \ / \
>     b   c
> Should that be a clean merge?  'b' was set twice, and only one of
> these settings was overridden; is that good enough?

Not clean. Say one person did a->b->c (the changes on the right side),
and someone else did a->b->b (the changes on the left side). So one set
of changes says "a should be renamed to c" and the other says "a should
be renamed to b". Conflict.

> 
> Do you still have the same opinion if the graph is:
>     |
>     a
>     |
>     b
>    / \
>   c   b
>   |  / \
>   b  b  c
>   \ /
>    b
> ?

Yes.

> 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.

> 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.

> The more important new stuff here, I think, are the user model and the proofs.


Tim