art with code


Adventures in OT, part 2

I've got a couple new tidbits to add to my previous post about implementing an operational transformation library. Operational transformations are about recording your edits and streaming them to the other collaborators. The concept is simple and the implementation isn't super-complicated, but it can be a bit tricky.

Anyway, I was hooking up the transformation library to inputs and textareas. Which, well, I guess you should just use a diff algorithm, it's probably less of a browser-compatibility hassle. I ended up doing it the hard way.

I'm monitoring events on the input element and keeping track of the cursor position using selectionStart and selectionEnd. When the contents of the element change, I figure out what kind of change it was and record a cursor movement followed by insert & delete events.

If the selection is empty, the change is an insert or a delete. If the input value is longer than the previous value, the change is an insert. If the value is shorter, the change is a delete. This logic works fine until you run into iOS autocorrect.

With autocorrect, the selection is empty but the cursor jumps multiple characters forwards. So I had to add a hack to the tune of "if the cursor jumps forward, set the selection length to the distance between last cursor position and current cursor position". Which works for simple autocorrect cases, but not for the autocorrect popup menu suggest action. Anyway, it sort of works. And this is why you should use a diff algorithm to record your edits.

Here's the code I've got at the moment:

// Setup event recording for the input element.
// Record the edits to the named field inside the changelist.
// Uses username as the name for the cursor.
var recordEdits = function(input, name, changelist, username) {
  input._lastValue = input.value;
  input._cursor = {
    pos: input.selectionStart,
    length: input.selectionEnd-input.selectionStart

  getEventNames(input).forEach(function(n) {
    input.addEventListener(n, recordEdit(name, changelist, username), false);

// Get the list of event names for the element.
var getEventNames = function(elem) {
  var a = Object.getOwnPropertyNames(elem).join(" ").match(/\bon\S+/g).join(" ").replace(/\bon/g, '').split(" ");
  // Take out touch events as Mobile Safari
  // doesn't like touch listeners on textareas inside iframes.
  a = a.filter(function(s) { return !(/^(touch|gesture)/).test(s); });
  return a;

// Makes an event listener to record edits.
var recordEdit = function(name, changelist, username) {
  return function(ev) {
    // Update cursor position.
    var cursor = {
      pos: this.selectionStart,
      length: this.selectionEnd-this.selectionStart

    // The value has changed. Let's record the change.
    if (this.value !== this._lastValue) {

      // Hack to handle autocorrect edits.
      if (cursor.pos - this._cursor.pos > 1 && this._cursor.length === 0) {
        this._cursor.length = cursor.pos - this._cursor.pos;

      // Handle selection replacements.
      // Triggers when you've got something selected and you
      // either type something or paste something.
      if (this._cursor.length > 0) {
        ChangeList.addChange(changelist, {edit: name, value: {cursor: {id: username, pos: this._cursor.pos}}});
        ChangeList.addChange(changelist, {edit: name, value: {del: this._cursor.length}});

      // How much the length of the value has changed.
      // A positive value indicates that text insertion.
      // A negative value means that you've deleted text.
      var d = (this.value.length-this._lastValue.length+this._cursor.length);

      if (d > 0) {
        // Create a text insertion change.
        // Note that we insert the text from the 
        // previous cursor position. The current cursor position
        // is after the inserted text.
        ChangeList.addChange(changelist, {edit: name, value: {cursor: {id: username, pos: this._cursor.pos}}});
        ChangeList.addChange(changelist, {edit: name, value: {add: this.value.substr(this._cursor.pos, d)}});
      } else if (d < 0) {
        // Create a text deletion change.
        ChangeList.addChange(changelist, {edit: name, value: {cursor: {id: username, pos: cursor.pos}}});
        ChangeList.addChange(changelist, {edit: name, value: {del: -d}});
      this._lastValue = this.value;
    this._cursor = cursor;

Ok, so it's a bit hacky. And it probably doesn't work all that well on IE. Perusing the code for ShareJS, it had a comment about IE converting \n linebreaks into \r\n linebreaks. Which would screw up cursor positions compared to other browsers.

Enough about hooking up input events. The other thing I got kinda working are writes based on a log table. Usually you'd need to have a document lock to do writes reliably. Because you need to transform new events based on events that arrived from other clients. So you can't insert new changes directly into the changelist, but need to read in tail = changelist[newChanges.lastSeenVersion..-1], then rebase the newChanges on top of the tail and push the transformed changes to the changelist. Which means that you want to lock changelist during tail read, transform and transform push. Otherwise you might get other changes in before the push and your transform goes FUBAR.

But hey, if you have an atomic push, you could do this: record the lastSeenVersion for the newChanges and push it into the changelist without transformation. Then change the changelist execution function so that it transforms the changes that have lastSeenVersion set. That way the result stays the same compared to pre-transforming the changes, though it'll cost you some performance. Not to worry though, you transform the newChanges and atomically replace the non-transformed version with the transformed version. Zing! Now the changelist results remain consistent even if other writers push more junk on top of the changelist while you're transforming.

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