art with code

2013-08-13

Writing an Operational Transformation library

Recently I've been indulging myself in that most noble of endeavours, re-implementing existing technology for no good reason. The object in this matter: Operational Transformations. A.k.a. the thing that you can use to make multi-user-editable documents.

The concept is simple: record the user actions on the client, send them to the server, the server merges them into the document and sends the resulting changes out to other clients. The implementation is, as I have had the pleasure to discover, not quite as simple.

Sure, maintaining the list of changes, that part is easy. Have an array for the event log, push changes that come from the client into the log, send back the events that happened since the client's last synced version.

ChangeList = function() {
  this.log = [];
  this.version = 0;
  this.newChanges = [];
  this.snapshots = {};
};

ChangeList.prototype.add = function(event) {
  this.newChanges.push(event);
};

ChangeList.prototype.addNewChanges = function(newChanges) {
  this.log.push({version: this.version++, changes: newChanges});
};

ChangeList.prototype.changesSince = function(version) {
  var log = this.log, i = this.log.length - 1;
  while (i >= 0 && log[i].version > version) {
    i--;
  }
  return log.slice(i+1);
};

ChangeList.prototype.sync = function(cl) {
  var changes = this.changesSince(cl.version);
  var newChanges = cl.newChanges.splice(0);
  this.normalize(changes, newChanges);
  this.addNewChanges(newChanges);
  for (var i=0; i<changes.length; i++) { 
    cl.log.push(changes[i]);
  }
  cl.version = this.version;
};

ChangeList.prototype.normalize = function(prevChanges, newChanges) {
  // Tweak newChanges according to prevChanges.
};

The problems start when you have to implement the normalize method. For operations that are associative and commutative, it's simple: you don't have to do anything. (1+2)+3 = (3+1)+2 and so forth, the order of the operations doesn't matter. Likewise for idempotent operations: abs(x) = abs(abs(x)).

The troublesome ones are the operations where the order does matter. For example, (1+0)*2 != (2*0)+1. Or, say, editing text. The raison d'être of this whole library. It being one of the complex cases does make life difficult for the poor implementer.

How does one represent text editing operations anyhow? You should at least have one operation that writes to some point in the text. And another that erases what you have written. It would also be nice to keep track of the cursor position and preserve local sanity.

Imagine that you're stuck in the middle of a sentence, trying to think up the exact word to use. At the same time, Joe Danger is hammering his keyboard at full steam on the page above you, chronicling his daring exploits in forgotten jungles and deadly deserts. The truly excellent thing for your cursor to do would be to stay there, stuck in the middle of the sentence, blinking lazily away without a worry in the world. As Joe's tale of adventure and peril grows, it should push your sentence and your cursor forward at the same pace.

ChangeList.prototype.normalizeString = function(prevChanges, newChanges) {
  var i,j,k;
  var cursors = {};
  for (i=0; i<prevChanges.length; i++) {
    var changes = prevChanges[i].changes;
    for (j=0; j<changes.length; j++) {

      // Find all text-editing ops in prevChanges.
      var cmd = changes[j];
      var edit = (cmd.write || cmd.erase);
      if (edit) {
        var pos = edit.pos;
        var move = edit.value.length || -edit.value;

        // Adjust text-editing ops and cursors in newChanges accordingly.
        for (k=0; k<newChanges.length; k++) {
          var ncmd = newChanges[k];
          var nedit = ncmd.cursor || ncmd.write || ncmd.erase;
          if (nedit.pos > pos) {

            // Move new ops that come after the edit.
            nedit.pos = Math.max(pos, nedit.pos+move);

          }
        }

      }

    }
  }
};

Alright, now your local space make senses, even if the text elsewhere is in a state of flux. I think we're getting somewhere. Oh wait, how do you get the final text out? All we have now is a list of changes. A list of changes is completely useless unless you can execute it.

To execute the changelist, we should go through the changes and replay them. For that we need an initial state and a way to apply changes to it. In functional programming parlance, foldl applyChange initialState changes. In JavaScript, pretty much the same.

ChangeList.prototype.execString = function() {
  var snapshot = this.snapshots.string;
  if (!snapshot) {
    snapshot = {value: '', version: 0};
  }

  // Execute changes on top of the snapshot.
  var initialState = snapshot.value;
  var changes = this.changesSince(snapshot.version);

  var result = initialState;
  for (var i=0; i<changes.length; i++) {
    result = this.applyStringChanges(result, changes[i]);
  }

  // Update the snapshot to the latest synced state.
  this.snapshots.string = {value: result, version: this.version};

  // Apply unsynced changes to get the final result.
  return this.applyStringChanges(result, {version: -1, changes: this.newChanges});
};

ChangeList.prototype.applyStringChanges = function(state, changeList) {
  var i, changes = changeList.changes;
  for (i=0; i<changes.length; i++) {
    var ch = changes[i];

    if (ch.write) {
      state = state.slice(0, ch.write.pos)
          .concat(ch.write.value, state.slice(ch.write.pos));

    } else if (ch.erase) {
      state = state.slice(0, ch.erase.pos)
          .concat(state.slice(ch.erase.pos + ch.erase.value));
    }
  }
  return state;
};

Hooray! String playback is in! Now the easy part is over! I haven't yet made textareas emit string change objects and maintain cursor state. I believe that it will be full of Bad Times fighting browser incompatibilities and APIs. But who knows, it might be simple as well. Excited to find out!

The OO-like implementation above was written solely for this post, if you want to get the slightly nutty tested version with JSON editing, here's a gist. I'll put up a proper GitHub repo once I manage to sync the edits with clientside editors and prove that it actually works.

Thanks for reading, have a cookie. 🍪
Post a Comment

Blog Archive

About Me

My photo

Built art installations, web sites, graphics libraries, web browsers, mobile apps, desktop apps, media player themes, many nutty prototypes, much bad code, much bad art.

Have freelanced for Verizon, Google, Mozilla, Warner Bros, Sony Pictures, Yahoo!, Microsoft, Valve Software, TDK Electronics.

Ex-Chrome Developer Relations.