diff3, merging, and distributed version control

(This page is a mirrored copy of an article originally posted on the LShift blog; see the archive index here.)

Yesterday I presented my work on Javascript diff, diff3, merging and version control at the Osmosoft Open Source Show ‘n Tell. (Previous posts about this stuff: here and here.) The slides for the talk are here. They’re a work-in-progress - as I think of things, I’ll continue to update them.

To summarise: I’ve used the diff3 I built in May to make a simple Javascript distributed version-control system that manages a collection of JSON structures. It supports named branches, merging, and import/export of revisions. So far, there’s no network synchronisation protocol, although it’d be easy to build a simple one using the rev import/export feature and XMLHttpRequest, and the storage format and repository representation is brutally naive (and because it doesn’t yet delta-compress historical versions of files, it is a bit wasteful of memory).

You can try out a few browser-based demos of the features of the diff and DVCS libraries:

The code is available using Mercurial by hg clone http://hg.opensource.lshift.net/synchrotron/ (or by simply browsing to that URL and exploring from there). It’s quite small and (I hope) easily understood - at the time of writing,

  • the diff/diff3 code and support utilities are ~310 lines; and
  • the DVCS code is ~370 lines.

The core interfaces, algorithms and internal structures of the DVCS code seem quite usable to me. In order to get to an efficient DVCS from here, the issues of storage and network formats will have to be addressed. Fortunately, storage and network formats are only about efficiency, not about features or correctness, and so they can be addressed separately from the core system. It will also eventually be necessary to revisit the naive LCA-computation code I’ve written, which is used to select an ancestor for use in a merge.

The code is split into a few different files:

Comments

On 3 July, 2008 at 5:47 pm, tonyg wrote:

((I accidentally deleted a bunch of comments I didn’t mean to delete today, so I’m having to repost them manually:))

Elliot Murphy wrote:

Wow, this is very cool. Thanks for posting it. What are you using this for?

On 3 July, 2008 at 5:47 pm, tonyg wrote:

((I accidentally deleted a bunch of comments I didn’t mean to delete today, so I’m having to repost them manually:))

FND wrote:

Very cool indeed!
I’m looking forward to seeing this implemented as a TiddlyWiki plugin and/or vertical.

On 3 July, 2008 at 5:47 pm, tonyg wrote:

((I accidentally deleted a bunch of comments I didn’t mean to delete today, so I’m having to repost them manually:))

tonyg wrote:

The idea is to see if it can be put into TiddlyWiki somehow - but there are plenty of other uses for a decentralised JSON synchronisation mechanism: bookmarks, calendar entries, contact lists, …