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

[Owen Stephens]

On 18 September 2012 12:09, Miles Gould <miles at assyrian.org.uk> wrote:
> 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/

Aha! I'd forgotten about this. Yes, it certainly feels nice on the
surface...
I'll add some comments, which may well need rethinking and/or correcting
reader
beware! (I should note that my CT is at a rather amateur level, and I'll
need
to spend some time getting to grips fully with Robin's blog post)

> 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.

Yep, a pushout was definitely what came to my mind when looking at
patch-merge
diagrams.

> 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.

My feeling is you'd want a complete lattice, rather than any old poset -
does
it make sense to have a divergence (meet) without a merge (join), in a file?

I wonder how we fit other patches (replace/move etc.) into this model?
Several
conversations have taken place about separating file ID from file content -
perhaps one wants a similar poset for the filename as the filecontent, such
that conflicting renames can be handled similarly?

> That is, this system represents conflicts within the files themselves
rather
> than within the patches.

Yes, I like this; making the structure of conflictingness explicit rather
than
encoding it into the linear patch sequence - I've been idly thinking about
this
at the patch level, but not at the file level!

> 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? :-)

Not at the moment, but never say never! :-) I'm certainly very interested to
see if this can lead anywhere...

--
Owen.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.osuosl.org/pipermail/darcs-users/attachments/20120918/8270ebf2/attachment.html>