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

On Sun, Aug 07, 2005 at 12:07:12PM +0200, Florian Weimer wrote:
> * Nathaniel Smith:
> 
> > (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.
> 
> I've been thinking about the very same thing (I call this "atom
> inference", and my atoms are your scalars).  Actually, I'm convinced
> that this is the language textual merges should be described in.

Hmm, I'm not :-).  But forgive me if at this point I won't be
convinced that any merge algorithm is sensible until I've seen a lot
of worked examples _and_ theoretical justification...

> This problem is quite similar to figuring out the adds/deletes/renames
> in a particular change from a before-the-change tree and an
> after-the-change tree.  I doubt it can be fully automated, and users
> probably don't want to document each hunk in the required detail
> ("this -/+ change replaces the same line with a new version" vs "this
> -/+ change deletes a line and adds a new, unrelated one").

I was actually thinking of doing what every pragmatic content merge
algorithm does, and just considering individual lines to be immutable
-- they can be replaced, but not changed.

> However, I hope that your voting algorithm does not require this level
> of detail.

"voting algorithm"?

(Though this does remind me of my persistent curiousity about whether
we're about to start finding merge algorithm Arrow's theorems...)

-- Nathaniel

-- 
Details are all that matters; God dwells there, and you never get to
see Him if you don't struggle to get them right. -- Stephen Jay Gould