[Monotone-devel] Re: [Revctrl] improvements to *-merge

[Nathaniel Smith]

On Tue, Aug 30, 2005 at 02:21:18AM -0700, Nathaniel Smith wrote:
> Corollary 1: If *(A) > B, and any element R of *(B) is R > A, then
>  value(A) = value(B).
[...]> 
> The nastiest case of this is where *(A) > B, but some elements of *(B)
> are > A -- so we silently make B win, but it's really not _quite_
> clear that's a good idea, since A also beat B sometimes -- and we're
> ignoring those user's intentions.
> 
> This is the nice thing about Corollary 1 (and why I didn't just
> collapse it into Corollary 2) -- it assures us that the only time this
> _weak_ form of ambiguous clean can happen is when A and B are already
> identical.

It occurs to me belatedly that there are actually even more
complexities here than I realized.  In particular, we need Corollary 1
to show that in the (v) case:

   a   b1
    \ /
     b2

with b2 unmarked, then *(b2) = *(b1).  It's in principle possible
that *(b2) is merely a subset of *(b1), in case some element of *(a)
"masked out" an element of *(b1).  That would be bad, if we were
dropping intentions on the floor...

OTOH, if that happened, then that element of *(a) would also be an
element of *(b2), so perhaps the proof of Corollary 1 is overcomplex,
and we could have just used the theorem that said all elements of
*(b2) have value b.


I also noticed something interesting, in this regard.  One of the
biggest differences between the *-merges and the codeville-merges they
came from is that in codeville merge, each node has associated with it
one or more "source revisions", analogous to *(A).  The difference is
that in codeville merge, you have to write these down for each node,
or else do some content-sensitive annotation-like traversal of the
graph; there isn't the same sense that *'s are things associated with
particular _ancestor_ nodes, and *() just reads off the nearest one(s)
from the graph topology.

I'd been thinking of this as a *-merge advantage mainly because it's
what makes the analysis of *-merge so tractable.  On further
reflection, I think it is actually a theoretical advantage as well.
Inasmuch as we are modeling user intentions, there is something wrong
the the idea that an intention could be expressed at one point in the
graph, and then later on the value changes to something else -- but
without any intervening intention being expressed!  For example, the
classic:

    a
   / \
  b1* c1*
  |\ /|
  | X |
  |/ \|
  b2  c2

b2 is a child of c1, yet there is no record of any intention that
overrode the c1 intention to explain how the value changed from c1 to
b2.

So now I think that the particular way *-merge uses graph topology is
in some ways a design feature, not just a convenient fact.

-- Nathaniel

-- 
- Don't let your informants burn anything.
- Don't grow old.
- Be good grad students.
  -- advice of Murray B. Emeneau on the occasion of his 100th birthday