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

[Bram Cohen]

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.

-Bram