It’s pretty similar to Darcs-style patch manipulation. I’ve only skimmed some introductory material on exactly how Darcs does it, but it looks a lot like what Wave does:
Make patches invertible.
Define a function T :: Patch -> Patch -> Patch that transforms one patch to apply to the document after a second patch has already been applied to it.
With these primitives, you can arbitrarily re-order patches. That’s not quite the way I’m doing it, though. I represent the document as a tree of atoms, each one with a unique id and a pointer to a predecessor. You get the document state by doing a pre-order depth first traversal of this tree, where siblings are traversed in an order that’s guaranteed to be the same on all clients, which I won’t define because it would take way too long to write out.
The patches are forests of atoms, and they get anchored to one or more nodes in the document tree. Atoms are never deleted, but they can be made invisible by attaching a special deletor atom to them. This guarantees that patches in the future will always be able to find their anchor points. I’ve tried both this and a system closer to Darcs’, and this was simpler to understand and implement.
In terms of power, this is equivalent to what Darcs does with permuting patches, and it can handle arbitrarily long-lived branches. My system’s patches commute naturally without any transformation, no matter how far document states may have diverged, which is a plus.
As for the speed, all operations are at most linear in the size of the document, with small constant factors, and I’m working on making the common cases all happen in logarithmic time, using monoid-cached trees—the finger tree is a prominent example. I don’t know how this compares with Darcs, but I wouldn’t expect them to be asymptotically faster here.
If I had more time and wasn’t so focused on just getting this done so I can get out of grad school, it would be interesting to make a DVCS based on this.
It’s pretty similar to Darcs-style patch manipulation. I’ve only skimmed some introductory material on exactly how Darcs does it, but it looks a lot like what Wave does:
Make patches invertible.
Define a function
T :: Patch -> Patch -> Patch
that transforms one patch to apply to the document after a second patch has already been applied to it.With these primitives, you can arbitrarily re-order patches. That’s not quite the way I’m doing it, though. I represent the document as a tree of atoms, each one with a unique id and a pointer to a predecessor. You get the document state by doing a pre-order depth first traversal of this tree, where siblings are traversed in an order that’s guaranteed to be the same on all clients, which I won’t define because it would take way too long to write out.
The patches are forests of atoms, and they get anchored to one or more nodes in the document tree. Atoms are never deleted, but they can be made invisible by attaching a special deletor atom to them. This guarantees that patches in the future will always be able to find their anchor points. I’ve tried both this and a system closer to Darcs’, and this was simpler to understand and implement.
In terms of power, this is equivalent to what Darcs does with permuting patches, and it can handle arbitrarily long-lived branches. My system’s patches commute naturally without any transformation, no matter how far document states may have diverged, which is a plus.
As for the speed, all operations are at most linear in the size of the document, with small constant factors, and I’m working on making the common cases all happen in logarithmic time, using monoid-cached trees—the finger tree is a prominent example. I don’t know how this compares with Darcs, but I wouldn’t expect them to be asymptotically faster here.
If I had more time and wasn’t so focused on just getting this done so I can get out of grad school, it would be interesting to make a DVCS based on this.
That is pretty neat.