Whpearson recently mentioned that people in some other online communities frequently ask "what are you working on?". I personally love asking and answering this question. I made sure to ask it at the Seattle meetup. However, I don't often see it asked here in the comments, so I will ask it:
What are you working on?
Here are some guidelines
- Focus on projects that you have recently made progress on, not projects that you're thinking about doing but haven't started, those are for a different thread.
- Why this project and not others? Mention reasons why you're doing the project and/or why others should contribute to your project (if applicable).
- Talk about your goals for the project.
- Any kind of project is fair game: personal improvement, research project, art project, whatever.
- Link to your work if it's linkable
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.