[darcs-users] darcs conflicts/dependencies -- is patch theory the place to start?

Miles Gould miles at assyrian.org.uk
Tue Sep 18 11:09:05 UTC 2012


On 18/09/12 07:17, Kevin Quick wrote:
> I don't know if I'm helping the discussion: it seems we are exploring
> theoretical VCS infrastructure so I'm enjoying our semi-abstract
> discourse and I may not be contributing to your goal.  If that's the
> case, please excuse my maunderings.  :-)

While we're exploring theoretical VCS infrastructure, let me draw your 
collective attention to Robin Houston's beautifully simple DVCS design:

http://bosker.wordpress.com/2012/05/10/on-editing-text/

tl;dr: patches are arrows in a category (we'll get to the objects 
later); merges are pushouts; coherence of merges follows trivially by 
uniqueness of colimits. I *think* this means that the merge algorithm is 
constant-time in the depth of patches that need merging. The interesting 
bit is that the objects are no longer linear strings of characters: to 
make this design work, we have to take as our objects *partially* 
ordered sets of characters. That is, this system represents conflicts 
within the files themselves rather than within the patches. Merging two 
conflicting patches to a file results in a file with "parallel tracks"; 
a possible subsequent edit is to remove one of the tracks and 
relinearize the file. But this is handled straightforwardly by the 
categorical formalism and requires no special-casing.

I asked Robin if he'd got round to implementing this, and apparently he 
hasn't yet. Anyone feel like having a go? :-)

Miles




More information about the darcs-users mailing list