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

[Nathaniel Smith]

On Sun, Aug 07, 2005 at 04:40:16AM -0700, Bram Cohen wrote:
> Nathaniel Smith wrote:
> 
> > (One horrible idea I had, suitable for scaring small children who are
> > interested in merge algorithms: since it seem like trees may actually
> > be _easier_ to merge than text, by passing to the representation
> > of nodes-and-pointers-to-parents and then applying a nice scalar merge
> > algorithm, why not apply the same trick to the linear ordering
> > structure that makes up text?  Model each line as a (text, pointer to
> > preceding line) pair, and merge on those.
> 
> That's an interesting idea, but doesn't make anything easier. The whole
> point of using a weave is that you can version each line independently,
> and thus far I've taken the approach of giving each line a binary value of
> either present or not present, which is easier than supporting a
> full-blown scalar. The hard part is resolution, where you figure out what
> lines are currently present. That's the part which needs all the work.
> 
> Using previous line as part of state could be useful for fixing that weird
> edge case you were discussing on IRC though, the one which codeville merge
> gets wrong but three way merge gets right.

Well, it's that weird edge case that has me wondering, actually.  For
those who don't follow the minutiae of our conversations with creepy
detail, the example is (with "ab" meaning "line a, then line b"):
 <nothing>
   /  \
  a    b
  |\  /|
  | \/ |
  | /\ |
  |/  \|
  ab   ba
   \  /
    ??
obviously this should be a conflict, but pcdv can't seem to notice it.
pcdv doesn't believe that lines can occur in two different orders; so
it ends up thinking that, say, the "ab" lines were both copied from
the parent, but in the "ba" case the "b" line was copied, but the "a"
line has nothing to do with the older "a" line -- the old one must
have been deleted and a new one added.  So the left side wins cleanly.
Oops.

3-way merge against the "<nothing>" ancestor gets this case right.

I find this somewhat disheartening, considering how trivially close
the example is to my first glimmerings of there being something
problematic with 3-way merge back in... gods, October 2003[1].
Guess everything does go around in circles...

But, personal issues aside ;-), AFAICT, the here problem really is
just that the global ordering assumption pcdv makes is wrong.  What
this is is an ordering conflict... but the very phrase "ordering
conflict" makes no sense at all in pcdv terms.  Thinking about it in
an abstract sort of way, this seems an odd fact about pcdv merge,
since the structure of the domain is "an ordered list", it's all
_about_ ordering...

Anyway, that was the sort of vague musing that played into the
"horrible idea" above; it's not really a serious proposal, at least,
at the moment...

[1] http://article.gmane.org/gmane.comp.version-control.monotone.devel/59

-- Nathaniel

-- 
"If you can explain how you do something, then you're very very bad at it."
  -- John Hopfield

This email may be read aloud.