[darcs-users] On merging

David Roundy droundy at abridgegame.org
Fri Nov 26 13:05:42 UTC 2004

I'll answer the meat of your email later, but the exciting news is that
this morning as I lay in bed (well, actually on the floor, since I sleep on
the floor...) I think I solved the merge problem.  I had woken up from a
very weird dream, and didn't get back to sleep for probably about three
hours, during which time I thought about merges.  It's amazing what one's
brain can do when it's unhinged by sleepiness and a very odd dream! :)

I still have to work out the details, but so far (I've filled a page of
large scribbles) it looks promising, both in terms of improving the speed
dramatically, and in terms of simplicity of code and algorithm.  Basically
the idea is to deal with sets of "unravelled" sequences rather than binary
recersive mergers, which eliminates the whole "unwind" step, and makes
understanding what is done much easier (since the unwind is what is so
confusing).  I don't expect I'm being comprehensible right now.  I still
need to work out the commutation with non-conflicting patches, but that
should be pretty much a straightforward excecise.  And then, of course, I
have to actually write code...

It's conceivable that I may even be able to prove that the new code can be
mapped to the old code, in which case there would be no need for a flag
day, since the new format would just be a different way of writing the old
data.  But I expect that won't be proveable (at least not by me) since the
old code is so complicated, so probably we'll have to have a flag day and
fossilize the old mergers.  :(

In retrospect, it seems so simple!

Off to work out commutations... this is the fun part!
David Roundy
-------------- next part --------------
A non-text attachment was scrubbed...
Name: not available
Type: application/pgp-signature
Size: 189 bytes
Desc: Digital signature
Url : http://lists.osuosl.org/pipermail/darcs-users/attachments/20041126/94663331/attachment.pgp 

More information about the darcs-users mailing list