Added support of operational transformation

8 files changed, 1427 insertions, 0 deletions

diff --git a/lib/ot/client.js b/lib/ot/client.js
new file mode 100755
index 00000000..7ee19fdc
--- /dev/null
+++ b/lib/ot/client.js
@@ -0,0 +1,312 @@
+// translation of https://github.com/djspiewak/cccp/blob/master/agent/src/main/scala/com/codecommit/cccp/agent/state.scala
+
+if (typeof ot === 'undefined') {
+  var ot = {};
+}
+
+ot.Client = (function (global) {
+  'use strict';
+
+  // Client constructor
+  function Client (revision) {
+    this.revision = revision; // the next expected revision number
+    this.setState(synchronized_); // start state
+  }
+
+  Client.prototype.setState = function (state) {
+    this.state = state;
+  };
+
+  // Call this method when the user changes the document.
+  Client.prototype.applyClient = function (operation) {
+    this.setState(this.state.applyClient(this, operation));
+  };
+
+  // Call this method with a new operation from the server
+  Client.prototype.applyServer = function (revision, operation) {
+    this.setState(this.state.applyServer(this, revision, operation));
+  };
+
+  Client.prototype.applyOperations = function (head, operations) {
+    this.setState(this.state.applyOperations(this, head, operations));
+  };
+
+  Client.prototype.serverAck = function (revision) {
+    this.setState(this.state.serverAck(this, revision));
+  };
+
+  Client.prototype.serverReconnect = function () {
+    if (typeof this.state.resend === 'function') { this.state.resend(this); }
+  };
+
+  // Transforms a selection from the latest known server state to the current
+  // client state. For example, if we get from the server the information that
+  // another user's cursor is at position 3, but the server hasn't yet received
+  // our newest operation, an insertion of 5 characters at the beginning of the
+  // document, the correct position of the other user's cursor in our current
+  // document is 8.
+  Client.prototype.transformSelection = function (selection) {
+    return this.state.transformSelection(selection);
+  };
+
+  // Override this method.
+  Client.prototype.sendOperation = function (revision, operation) {
+    throw new Error("sendOperation must be defined in child class");
+  };
+
+  // Override this method.
+  Client.prototype.applyOperation = function (operation) {
+    throw new Error("applyOperation must be defined in child class");
+  };
+
+
+  // In the 'Synchronized' state, there is no pending operation that the client
+  // has sent to the server.
+  function Synchronized () {}
+  Client.Synchronized = Synchronized;
+
+  Synchronized.prototype.applyClient = function (client, operation) {
+    // When the user makes an edit, send the operation to the server and
+    // switch to the 'AwaitingConfirm' state
+    client.sendOperation(client.revision, operation);
+    return new AwaitingConfirm(operation);
+  };
+
+  Synchronized.prototype.applyServer = function (client, revision, operation) {
+    if (revision - client.revision > 1) {
+      throw new Error("Invalid revision.");
+    }
+    client.revision = revision;
+    // When we receive a new operation from the server, the operation can be
+    // simply applied to the current document
+    client.applyOperation(operation);
+    return this;
+  };
+
+  Synchronized.prototype.serverAck = function (client, revision) {
+    throw new Error("There is no pending operation.");
+  };
+
+  // Nothing to do because the latest server state and client state are the same.
+  Synchronized.prototype.transformSelection = function (x) { return x; };
+
+  // Singleton
+  var synchronized_ = new Synchronized();
+
+
+  // In the 'AwaitingConfirm' state, there's one operation the client has sent
+  // to the server and is still waiting for an acknowledgement.
+  function AwaitingConfirm (outstanding) {
+    // Save the pending operation
+    this.outstanding = outstanding;
+  }
+  Client.AwaitingConfirm = AwaitingConfirm;
+
+  AwaitingConfirm.prototype.applyClient = function (client, operation) {
+    // When the user makes an edit, don't send the operation immediately,
+    // instead switch to 'AwaitingWithBuffer' state
+    return new AwaitingWithBuffer(this.outstanding, operation);
+  };
+
+  AwaitingConfirm.prototype.applyServer = function (client, revision, operation) {
+    if (revision - client.revision > 1) {
+      throw new Error("Invalid revision.");
+    }
+    client.revision = revision;
+    // This is another client's operation. Visualization:
+    //
+    //                   /\
+    // this.outstanding /  \ operation
+    //                 /    \
+    //                 \    /
+    //  pair[1]         \  / pair[0] (new outstanding)
+    //  (can be applied  \/
+    //  to the client's
+    //  current document)
+    var pair = operation.constructor.transform(this.outstanding, operation);
+    client.applyOperation(pair[1]);
+    return new AwaitingConfirm(pair[0]);
+  };
+
+  AwaitingConfirm.prototype.serverAck = function (client, revision) {
+    if (revision - client.revision > 1) {
+      return new Stale(this.outstanding, client, revision).getOperations();
+    }
+    client.revision = revision;
+    // The client's operation has been acknowledged
+    // => switch to synchronized state
+    return synchronized_;
+  };
+
+  AwaitingConfirm.prototype.transformSelection = function (selection) {
+    return selection.transform(this.outstanding);
+  };
+
+  AwaitingConfirm.prototype.resend = function (client) {
+    // The confirm didn't come because the client was disconnected.
+    // Now that it has reconnected, we resend the outstanding operation.
+    client.sendOperation(client.revision, this.outstanding);
+  };
+
+
+  // In the 'AwaitingWithBuffer' state, the client is waiting for an operation
+  // to be acknowledged by the server while buffering the edits the user makes
+  function AwaitingWithBuffer (outstanding, buffer) {
+    // Save the pending operation and the user's edits since then
+    this.outstanding = outstanding;
+    this.buffer = buffer;
+  }
+  Client.AwaitingWithBuffer = AwaitingWithBuffer;
+
+  AwaitingWithBuffer.prototype.applyClient = function (client, operation) {
+    // Compose the user's changes onto the buffer
+    var newBuffer = this.buffer.compose(operation);
+    return new AwaitingWithBuffer(this.outstanding, newBuffer);
+  };
+
+  AwaitingWithBuffer.prototype.applyServer = function (client, revision, operation) {
+    if (revision - client.revision > 1) {
+      throw new Error("Invalid revision.");
+    }
+    client.revision = revision;
+    // Operation comes from another client
+    //
+    //                       /\
+    //     this.outstanding /  \ operation
+    //                     /    \
+    //                    /\    /
+    //       this.buffer /  \* / pair1[0] (new outstanding)
+    //                  /    \/
+    //                  \    /
+    //          pair2[1] \  / pair2[0] (new buffer)
+    // the transformed    \/
+    // operation -- can
+    // be applied to the
+    // client's current
+    // document
+    //
+    // * pair1[1]
+    var transform = operation.constructor.transform;
+    var pair1 = transform(this.outstanding, operation);
+    var pair2 = transform(this.buffer, pair1[1]);
+    client.applyOperation(pair2[1]);
+    return new AwaitingWithBuffer(pair1[0], pair2[0]);
+  };
+
+  AwaitingWithBuffer.prototype.serverAck = function (client, revision) {
+    if (revision - client.revision > 1) {
+      return new StaleWithBuffer(this.outstanding, this.buffer, client, revision).getOperations();
+    }
+    client.revision = revision;
+    // The pending operation has been acknowledged
+    // => send buffer
+    client.sendOperation(client.revision, this.buffer);
+    return new AwaitingConfirm(this.buffer);
+  };
+
+  AwaitingWithBuffer.prototype.transformSelection = function (selection) {
+    return selection.transform(this.outstanding).transform(this.buffer);
+  };
+
+  AwaitingWithBuffer.prototype.resend = function (client) {
+    // The confirm didn't come because the client was disconnected.
+    // Now that it has reconnected, we resend the outstanding operation.
+    client.sendOperation(client.revision, this.outstanding);
+  };
+
+
+  function Stale(acknowlaged, client, revision) {
+    this.acknowlaged = acknowlaged;
+    this.client = client;
+    this.revision = revision;
+  }
+  Client.Stale = Stale;
+
+  Stale.prototype.applyClient = function (client, operation) {
+    return new StaleWithBuffer(this.acknowlaged, operation, client, this.revision);
+  };
+
+  Stale.prototype.applyServer = function (client, revision, operation) {
+    throw new Error("Ignored server-side change.");
+  };
+
+  Stale.prototype.applyOperations = function (client, head, operations) {
+    var transform = this.acknowlaged.constructor.transform;
+    for (var i = 0; i < operations.length; i++) {
+      var op = ot.TextOperation.fromJSON(operations[i]);
+      var pair = transform(this.acknowlaged, op);
+      client.applyOperation(pair[1]);
+      this.acknowlaged = pair[0];
+    }
+    client.revision = this.revision;
+    return synchronized_;
+  };
+
+  Stale.prototype.serverAck = function (client, revision) {
+    throw new Error("There is no pending operation.");
+  };
+
+  Stale.prototype.transformSelection = function (selection) {
+    return selection;
+  };
+
+  Stale.prototype.getOperations = function () {
+    this.client.getOperations(this.client.revision, this.revision - 1); // acknowlaged is the one at revision
+    return this;
+  };
+
+
+  function StaleWithBuffer(acknowlaged, buffer, client, revision) {
+    this.acknowlaged = acknowlaged;
+    this.buffer = buffer;
+    this.client = client;
+    this.revision = revision;
+  }
+  Client.StaleWithBuffer = StaleWithBuffer;
+
+  StaleWithBuffer.prototype.applyClient = function (client, operation) {
+    var buffer = this.buffer.compose(operation);
+    return new StaleWithBuffer(this.acknowlaged, buffer, client, this.revision);
+  };
+
+  StaleWithBuffer.prototype.applyServer = function (client, revision, operation) {
+    throw new Error("Ignored server-side change.");
+  };
+
+  StaleWithBuffer.prototype.applyOperations = function (client, head, operations) {
+    var transform = this.acknowlaged.constructor.transform;
+    for (var i = 0; i < operations.length; i++) {
+      var op = ot.TextOperation.fromJSON(operations[i]);
+      var pair1 = transform(this.acknowlaged, op);
+      var pair2 = transform(this.buffer, pair1[1]);
+      client.applyOperation(pair2[1]);
+      this.acknowlaged = pair1[0];
+      this.buffer = pair2[0];
+    }
+    client.revision = this.revision;
+    client.sendOperation(client.revision, this.buffer);
+    return new AwaitingConfirm(this.buffer);
+  };
+
+  StaleWithBuffer.prototype.serverAck = function (client, revision) {
+    throw new Error("There is no pending operation.");
+  };
+
+  StaleWithBuffer.prototype.transformSelection = function (selection) {
+    return selection;
+  };
+
+  StaleWithBuffer.prototype.getOperations = function () {
+    this.client.getOperations(this.client.revision, this.revision - 1); // acknowlaged is the one at revision
+    return this;
+  };
+
+
+  return Client;
+
+}(this));
+
+if (typeof module === 'object') {
+  module.exports = ot.Client;
+}
+
diff --git a/lib/ot/editor-socketio-server.js b/lib/ot/editor-socketio-server.js
new file mode 100755
index 00000000..aae156fc
--- /dev/null
+++ b/lib/ot/editor-socketio-server.js
@@ -0,0 +1,146 @@
+'use strict';
+
+var EventEmitter = require('events').EventEmitter;
+var TextOperation = require('./text-operation');
+var WrappedOperation = require('./wrapped-operation');
+var Server = require('./server');
+var Selection = require('./selection');
+var util = require('util');
+
+var LZString = require('lz-string');
+
+function EditorSocketIOServer(document, operations, docId, mayWrite) {
+    EventEmitter.call(this);
+    Server.call(this, document, operations);
+    this.users = {};
+    this.docId = docId;
+    this.mayWrite = mayWrite || function (_, cb) {
+        cb(true);
+    };
+}
+
+util.inherits(EditorSocketIOServer, Server);
+extend(EditorSocketIOServer.prototype, EventEmitter.prototype);
+
+function extend(target, source) {
+    for (var key in source) {
+        if (source.hasOwnProperty(key)) {
+            target[key] = source[key];
+        }
+    }
+}
+
+EditorSocketIOServer.prototype.addClient = function (socket) {
+    var self = this;
+    socket.join(this.docId);
+    var docOut = {
+        str: this.document,
+        revision: this.operations.length,
+        clients: this.users
+    };
+    socket.emit('doc', LZString.compressToUTF16(JSON.stringify(docOut)));
+    socket.on('operation', function (revision, operation, selection) {
+        operation = LZString.decompressFromUTF16(operation);
+        operation = JSON.parse(operation);
+        self.mayWrite(socket, function (mayWrite) {
+            if (!mayWrite) {
+                console.log("User doesn't have the right to edit.");
+                return;
+            }
+            self.onOperation(socket, revision, operation, selection);
+        });
+    });
+    socket.on('get_operations', function (base, head) {
+        self.onGetOperations(socket, base, head);
+    });
+    socket.on('selection', function (obj) {
+        self.mayWrite(socket, function (mayWrite) {
+            if (!mayWrite) {
+                console.log("User doesn't have the right to edit.");
+                return;
+            }
+            self.updateSelection(socket, obj && Selection.fromJSON(obj));
+        });
+    });
+    socket.on('disconnect', function () {
+        //console.log("Disconnect");
+        socket.leave(self.docId);
+        self.onDisconnect(socket);
+        /*
+        if (socket.manager && socket.manager.sockets.clients(self.docId).length === 0) {
+          self.emit('empty-room');
+        }
+        */
+    });
+};
+
+EditorSocketIOServer.prototype.onOperation = function (socket, revision, operation, selection) {
+    var wrapped;
+    try {
+        wrapped = new WrappedOperation(
+            TextOperation.fromJSON(operation),
+            selection && Selection.fromJSON(selection)
+        );
+    } catch (exc) {
+        console.error("Invalid operation received: " + exc);
+        return;
+    }
+
+    try {
+        var clientId = socket.id;
+        var wrappedPrime = this.receiveOperation(revision, wrapped);
+        //console.log("new operation: " + JSON.stringify(wrapped));
+        this.getClient(clientId).selection = wrappedPrime.meta;
+        revision = this.operations.length;
+        socket.emit('ack', revision);
+        socket.broadcast.in(this.docId).emit(
+            'operation', clientId, revision,
+            wrappedPrime.wrapped.toJSON(), wrappedPrime.meta
+        );
+        this.isDirty = true;
+    } catch (exc) {
+        console.error(exc);
+    }
+};
+
+EditorSocketIOServer.prototype.onGetOperations = function (socket, base, head) {
+    var operations = this.operations.slice(base, head).map(function (op) {
+        return op.wrapped.toJSON();
+    });
+    operations = LZString.compressToUTF16(JSON.stringify(operations));
+    socket.emit('operations', head, operations);
+};
+
+EditorSocketIOServer.prototype.updateSelection = function (socket, selection) {
+    var clientId = socket.id;
+    if (selection) {
+        this.getClient(clientId).selection = selection;
+    } else {
+        delete this.getClient(clientId).selection;
+    }
+    socket.broadcast.to(this.docId).emit('selection', clientId, selection);
+};
+
+EditorSocketIOServer.prototype.setName = function (socket, name) {
+    var clientId = socket.id;
+    this.getClient(clientId).name = name;
+    socket.broadcast.to(this.docId).emit('set_name', clientId, name);
+};
+
+EditorSocketIOServer.prototype.setColor = function (socket, color) {
+    var clientId = socket.id;
+    this.getClient(clientId).color = color;
+    socket.broadcast.to(this.docId).emit('set_color', clientId, color);
+};
+
+EditorSocketIOServer.prototype.getClient = function (clientId) {
+    return this.users[clientId] || (this.users[clientId] = {});
+};
+
+EditorSocketIOServer.prototype.onDisconnect = function (socket) {
+    var clientId = socket.id;
+    delete this.users[clientId];
+    socket.broadcast.to(this.docId).emit('client_left', clientId);
+};
+
+module.exports = EditorSocketIOServer;
\ No newline at end of file
diff --git a/lib/ot/index.js b/lib/ot/index.js
new file mode 100644
index 00000000..fcc94c11
--- /dev/null
+++ b/lib/ot/index.js
@@ -0,0 +1,8 @@
+exports.version = '0.0.15';
+
+exports.TextOperation        = require('./text-operation');
+exports.SimpleTextOperation  = require('./simple-text-operation');
+exports.Client               = require('./client');
+exports.Server               = require('./server');
+exports.Selection            = require('./selection');
+exports.EditorSocketIOServer = require('./editor-socketio-server');
diff --git a/lib/ot/selection.js b/lib/ot/selection.js
new file mode 100644
index 00000000..72bf8bd6
--- /dev/null
+++ b/lib/ot/selection.js
@@ -0,0 +1,117 @@
+if (typeof ot === 'undefined') {
+  // Export for browsers
+  var ot = {};
+}
+
+ot.Selection = (function (global) {
+  'use strict';
+
+  var TextOperation = global.ot ? global.ot.TextOperation : require('./text-operation');
+
+  // Range has `anchor` and `head` properties, which are zero-based indices into
+  // the document. The `anchor` is the side of the selection that stays fixed,
+  // `head` is the side of the selection where the cursor is. When both are
+  // equal, the range represents a cursor.
+  function Range (anchor, head) {
+    this.anchor = anchor;
+    this.head = head;
+  }
+
+  Range.fromJSON = function (obj) {
+    return new Range(obj.anchor, obj.head);
+  };
+
+  Range.prototype.equals = function (other) {
+    return this.anchor === other.anchor && this.head === other.head;
+  };
+
+  Range.prototype.isEmpty = function () {
+    return this.anchor === this.head;
+  };
+
+  Range.prototype.transform = function (other) {
+    function transformIndex (index) {
+      var newIndex = index;
+      var ops = other.ops;
+      for (var i = 0, l = other.ops.length; i < l; i++) {
+        if (TextOperation.isRetain(ops[i])) {
+          index -= ops[i];
+        } else if (TextOperation.isInsert(ops[i])) {
+          newIndex += ops[i].length;
+        } else {
+          newIndex -= Math.min(index, -ops[i]);
+          index += ops[i];
+        }
+        if (index < 0) { break; }
+      }
+      return newIndex;
+    }
+
+    var newAnchor = transformIndex(this.anchor);
+    if (this.anchor === this.head) {
+      return new Range(newAnchor, newAnchor);
+    }
+    return new Range(newAnchor, transformIndex(this.head));
+  };
+
+  // A selection is basically an array of ranges. Every range represents a real
+  // selection or a cursor in the document (when the start position equals the
+  // end position of the range). The array must not be empty.
+  function Selection (ranges) {
+    this.ranges = ranges || [];
+  }
+
+  Selection.Range = Range;
+
+  // Convenience method for creating selections only containing a single cursor
+  // and no real selection range.
+  Selection.createCursor = function (position) {
+    return new Selection([new Range(position, position)]);
+  };
+
+  Selection.fromJSON = function (obj) {
+    var objRanges = obj.ranges || obj;
+    for (var i = 0, ranges = []; i < objRanges.length; i++) {
+      ranges[i] = Range.fromJSON(objRanges[i]);
+    }
+    return new Selection(ranges);
+  };
+
+  Selection.prototype.equals = function (other) {
+    if (this.position !== other.position) { return false; }
+    if (this.ranges.length !== other.ranges.length) { return false; }
+    // FIXME: Sort ranges before comparing them?
+    for (var i = 0; i < this.ranges.length; i++) {
+      if (!this.ranges[i].equals(other.ranges[i])) { return false; }
+    }
+    return true;
+  };
+
+  Selection.prototype.somethingSelected = function () {
+    for (var i = 0; i < this.ranges.length; i++) {
+      if (!this.ranges[i].isEmpty()) { return true; }
+    }
+    return false;
+  };
+
+  // Return the more current selection information.
+  Selection.prototype.compose = function (other) {
+    return other;
+  };
+
+  // Update the selection with respect to an operation.
+  Selection.prototype.transform = function (other) {
+    for (var i = 0, newRanges = []; i < this.ranges.length; i++) {
+      newRanges[i] = this.ranges[i].transform(other);
+    }
+    return new Selection(newRanges);
+  };
+
+  return Selection;
+
+}(this));
+
+// Export for CommonJS
+if (typeof module === 'object') {
+  module.exports = ot.Selection;
+}
diff --git a/lib/ot/server.js b/lib/ot/server.js
new file mode 100644
index 00000000..608d434b
--- /dev/null
+++ b/lib/ot/server.js
@@ -0,0 +1,46 @@
+if (typeof ot === 'undefined') {
+  var ot = {};
+}
+
+ot.Server = (function (global) {
+  'use strict';
+
+  // Constructor. Takes the current document as a string and optionally the array
+  // of all operations.
+  function Server (document, operations) {
+    this.document = document;
+    this.operations = operations || [];
+  }
+
+  // Call this method whenever you receive an operation from a client.
+  Server.prototype.receiveOperation = function (revision, operation) {
+    if (revision < 0 || this.operations.length < revision) {
+      throw new Error("operation revision not in history");
+    }
+    // Find all operations that the client didn't know of when it sent the
+    // operation ...
+    var concurrentOperations = this.operations.slice(revision);
+
+    // ... and transform the operation against all these operations ...
+    var transform = operation.constructor.transform;
+    for (var i = 0; i < concurrentOperations.length; i++) {
+      operation = transform(operation, concurrentOperations[i])[0];
+    }
+
+    // ... and apply that on the document.
+    this.document = operation.apply(this.document);
+    // Store operation in history.
+    this.operations.push(operation);
+
+    // It's the caller's responsibility to send the operation to all connected
+    // clients and an acknowledgement to the creator.
+    return operation;
+  };
+
+  return Server;
+
+}(this));
+
+if (typeof module === 'object') {
+  module.exports = ot.Server;
+}
\ No newline at end of file
diff --git a/lib/ot/simple-text-operation.js b/lib/ot/simple-text-operation.js
new file mode 100644
index 00000000..6db296e0
--- /dev/null
+++ b/lib/ot/simple-text-operation.js
@@ -0,0 +1,188 @@
+if (typeof ot === 'undefined') {
+  // Export for browsers
+  var ot = {};
+}
+
+ot.SimpleTextOperation = (function (global) {
+
+  var TextOperation = global.ot ? global.ot.TextOperation : require('./text-operation');
+
+  function SimpleTextOperation () {}
+
+
+  // Insert the string `str` at the zero-based `position` in the document.
+  function Insert (str, position) {
+    if (!this || this.constructor !== SimpleTextOperation) {
+      // => function was called without 'new'
+      return new Insert(str, position);
+    }
+    this.str = str;
+    this.position = position;
+  }
+
+  Insert.prototype = new SimpleTextOperation();
+  SimpleTextOperation.Insert = Insert;
+
+  Insert.prototype.toString = function () {
+    return 'Insert(' + JSON.stringify(this.str) + ', ' + this.position + ')';
+  };
+
+  Insert.prototype.equals = function (other) {
+    return other instanceof Insert &&
+      this.str === other.str &&
+      this.position === other.position;
+  };
+
+  Insert.prototype.apply = function (doc) {
+    return doc.slice(0, this.position) + this.str + doc.slice(this.position);
+  };
+
+
+  // Delete `count` many characters at the zero-based `position` in the document.
+  function Delete (count, position) {
+    if (!this || this.constructor !== SimpleTextOperation) {
+      return new Delete(count, position);
+    }
+    this.count = count;
+    this.position = position;
+  }
+
+  Delete.prototype = new SimpleTextOperation();
+  SimpleTextOperation.Delete = Delete;
+
+  Delete.prototype.toString = function () {
+    return 'Delete(' + this.count + ', ' + this.position + ')';
+  };
+
+  Delete.prototype.equals = function (other) {
+    return other instanceof Delete &&
+      this.count === other.count &&
+      this.position === other.position;
+  };
+
+  Delete.prototype.apply = function (doc) {
+    return doc.slice(0, this.position) + doc.slice(this.position + this.count);
+  };
+
+
+  // An operation that does nothing. This is needed for the result of the
+  // transformation of two deletions of the same character.
+  function Noop () {
+    if (!this || this.constructor !== SimpleTextOperation) { return new Noop(); }
+  }
+
+  Noop.prototype = new SimpleTextOperation();
+  SimpleTextOperation.Noop = Noop;
+
+  Noop.prototype.toString = function () {
+    return 'Noop()';
+  };
+
+  Noop.prototype.equals = function (other) { return other instanceof Noop; };
+
+  Noop.prototype.apply = function (doc) { return doc; };
+
+  var noop = new Noop();
+
+
+  SimpleTextOperation.transform = function (a, b) {
+    if (a instanceof Noop || b instanceof Noop) { return [a, b]; }
+
+    if (a instanceof Insert && b instanceof Insert) {
+      if (a.position < b.position || (a.position === b.position && a.str < b.str)) {
+        return [a, new Insert(b.str, b.position + a.str.length)];
+      }
+      if (a.position > b.position || (a.position === b.position && a.str > b.str)) {
+        return [new Insert(a.str, a.position + b.str.length), b];
+      }
+      return [noop, noop];
+    }
+
+    if (a instanceof Insert && b instanceof Delete) {
+      if (a.position <= b.position) {
+        return [a, new Delete(b.count, b.position + a.str.length)];
+      }
+      if (a.position >= b.position + b.count) {
+        return [new Insert(a.str, a.position - b.count), b];
+      }
+      // Here, we have to delete the inserted string of operation a.
+      // That doesn't preserve the intention of operation a, but it's the only
+      // thing we can do to get a valid transform function.
+      return [noop, new Delete(b.count + a.str.length, b.position)];
+    }
+
+    if (a instanceof Delete && b instanceof Insert) {
+      if (a.position >= b.position) {
+        return [new Delete(a.count, a.position + b.str.length), b];
+      }
+      if (a.position + a.count <= b.position) {
+        return [a, new Insert(b.str, b.position - a.count)];
+      }
+      // Same problem as above. We have to delete the string that was inserted
+      // in operation b.
+      return [new Delete(a.count + b.str.length, a.position), noop];
+    }
+
+    if (a instanceof Delete && b instanceof Delete) {
+      if (a.position === b.position) {
+        if (a.count === b.count) {
+          return [noop, noop];
+        } else if (a.count < b.count) {
+          return [noop, new Delete(b.count - a.count, b.position)];
+        }
+        return [new Delete(a.count - b.count, a.position), noop];
+      }
+      if (a.position < b.position) {
+        if (a.position + a.count <= b.position) {
+          return [a, new Delete(b.count, b.position - a.count)];
+        }
+        if (a.position + a.count >= b.position + b.count) {
+          return [new Delete(a.count - b.count, a.position), noop];
+        }
+        return [
+          new Delete(b.position - a.position, a.position),
+          new Delete(b.position + b.count - (a.position + a.count), a.position)
+        ];
+      }
+      if (a.position > b.position) {
+        if (a.position >= b.position + b.count) {
+          return [new Delete(a.count, a.position - b.count), b];
+        }
+        if (a.position + a.count <= b.position + b.count) {
+          return [noop, new Delete(b.count - a.count, b.position)];
+        }
+        return [
+          new Delete(a.position + a.count - (b.position + b.count), b.position),
+          new Delete(a.position - b.position, b.position)
+        ];
+      }
+    }
+  };
+
+  // Convert a normal, composable `TextOperation` into an array of
+  // `SimpleTextOperation`s.
+  SimpleTextOperation.fromTextOperation = function (operation) {
+    var simpleOperations = [];
+    var index = 0;
+    for (var i = 0; i < operation.ops.length; i++) {
+      var op = operation.ops[i];
+      if (TextOperation.isRetain(op)) {
+        index += op;
+      } else if (TextOperation.isInsert(op)) {
+        simpleOperations.push(new Insert(op, index));
+        index += op.length;
+      } else {
+        simpleOperations.push(new Delete(Math.abs(op), index));
+      }
+    }
+    return simpleOperations;
+  };
+
+
+  return SimpleTextOperation;
+})(this);
+
+// Export for CommonJS
+if (typeof module === 'object') {
+  module.exports = ot.SimpleTextOperation;
+}
\ No newline at end of file
diff --git a/lib/ot/text-operation.js b/lib/ot/text-operation.js
new file mode 100644
index 00000000..d5468497
--- /dev/null
+++ b/lib/ot/text-operation.js
@@ -0,0 +1,530 @@
+if (typeof ot === 'undefined') {
+  // Export for browsers
+  var ot = {};
+}
+
+ot.TextOperation = (function () {
+  'use strict';
+
+  // Constructor for new operations.
+  function TextOperation () {
+    if (!this || this.constructor !== TextOperation) {
+      // => function was called without 'new'
+      return new TextOperation();
+    }
+
+    // When an operation is applied to an input string, you can think of this as
+    // if an imaginary cursor runs over the entire string and skips over some
+    // parts, deletes some parts and inserts characters at some positions. These
+    // actions (skip/delete/insert) are stored as an array in the "ops" property.
+    this.ops = [];
+    // An operation's baseLength is the length of every string the operation
+    // can be applied to.
+    this.baseLength = 0;
+    // The targetLength is the length of every string that results from applying
+    // the operation on a valid input string.
+    this.targetLength = 0;
+  }
+
+  TextOperation.prototype.equals = function (other) {
+    if (this.baseLength !== other.baseLength) { return false; }
+    if (this.targetLength !== other.targetLength) { return false; }
+    if (this.ops.length !== other.ops.length) { return false; }
+    for (var i = 0; i < this.ops.length; i++) {
+      if (this.ops[i] !== other.ops[i]) { return false; }
+    }
+    return true;
+  };
+
+  // Operation are essentially lists of ops. There are three types of ops:
+  //
+  // * Retain ops: Advance the cursor position by a given number of characters.
+  //   Represented by positive ints.
+  // * Insert ops: Insert a given string at the current cursor position.
+  //   Represented by strings.
+  // * Delete ops: Delete the next n characters. Represented by negative ints.
+
+  var isRetain = TextOperation.isRetain = function (op) {
+    return typeof op === 'number' && op > 0;
+  };
+
+  var isInsert = TextOperation.isInsert = function (op) {
+    return typeof op === 'string';
+  };
+
+  var isDelete = TextOperation.isDelete = function (op) {
+    return typeof op === 'number' && op < 0;
+  };
+
+
+  // After an operation is constructed, the user of the library can specify the
+  // actions of an operation (skip/insert/delete) with these three builder
+  // methods. They all return the operation for convenient chaining.
+
+  // Skip over a given number of characters.
+  TextOperation.prototype.retain = function (n) {
+    if (typeof n !== 'number') {
+      throw new Error("retain expects an integer");
+    }
+    if (n === 0) { return this; }
+    this.baseLength += n;
+    this.targetLength += n;
+    if (isRetain(this.ops[this.ops.length-1])) {
+      // The last op is a retain op => we can merge them into one op.
+      this.ops[this.ops.length-1] += n;
+    } else {
+      // Create a new op.
+      this.ops.push(n);
+    }
+    return this;
+  };
+
+  // Insert a string at the current position.
+  TextOperation.prototype.insert = function (str) {
+    if (typeof str !== 'string') {
+      throw new Error("insert expects a string");
+    }
+    if (str === '') { return this; }
+    this.targetLength += str.length;
+    var ops = this.ops;
+    if (isInsert(ops[ops.length-1])) {
+      // Merge insert op.
+      ops[ops.length-1] += str;
+    } else if (isDelete(ops[ops.length-1])) {
+      // It doesn't matter when an operation is applied whether the operation
+      // is delete(3), insert("something") or insert("something"), delete(3).
+      // Here we enforce that in this case, the insert op always comes first.
+      // This makes all operations that have the same effect when applied to
+      // a document of the right length equal in respect to the `equals` method.
+      if (isInsert(ops[ops.length-2])) {
+        ops[ops.length-2] += str;
+      } else {
+        ops[ops.length] = ops[ops.length-1];
+        ops[ops.length-2] = str;
+      }
+    } else {
+      ops.push(str);
+    }
+    return this;
+  };
+
+  // Delete a string at the current position.
+  TextOperation.prototype['delete'] = function (n) {
+    if (typeof n === 'string') { n = n.length; }
+    if (typeof n !== 'number') {
+      throw new Error("delete expects an integer or a string");
+    }
+    if (n === 0) { return this; }
+    if (n > 0) { n = -n; }
+    this.baseLength -= n;
+    if (isDelete(this.ops[this.ops.length-1])) {
+      this.ops[this.ops.length-1] += n;
+    } else {
+      this.ops.push(n);
+    }
+    return this;
+  };
+
+  // Tests whether this operation has no effect.
+  TextOperation.prototype.isNoop = function () {
+    return this.ops.length === 0 || (this.ops.length === 1 && isRetain(this.ops[0]));
+  };
+
+  // Pretty printing.
+  TextOperation.prototype.toString = function () {
+    // map: build a new array by applying a function to every element in an old
+    // array.
+    var map = Array.prototype.map || function (fn) {
+      var arr = this;
+      var newArr = [];
+      for (var i = 0, l = arr.length; i < l; i++) {
+        newArr[i] = fn(arr[i]);
+      }
+      return newArr;
+    };
+    return map.call(this.ops, function (op) {
+      if (isRetain(op)) {
+        return "retain " + op;
+      } else if (isInsert(op)) {
+        return "insert '" + op + "'";
+      } else {
+        return "delete " + (-op);
+      }
+    }).join(', ');
+  };
+
+  // Converts operation into a JSON value.
+  TextOperation.prototype.toJSON = function () {
+    return this.ops;
+  };
+
+  // Converts a plain JS object into an operation and validates it.
+  TextOperation.fromJSON = function (ops) {
+    var o = new TextOperation();
+    for (var i = 0, l = ops.length; i < l; i++) {
+      var op = ops[i];
+      if (isRetain(op)) {
+        o.retain(op);
+      } else if (isInsert(op)) {
+        o.insert(op);
+      } else if (isDelete(op)) {
+        o['delete'](op);
+      } else {
+        throw new Error("unknown operation: " + JSON.stringify(op));
+      }
+    }
+    return o;
+  };
+
+  // Apply an operation to a string, returning a new string. Throws an error if
+  // there's a mismatch between the input string and the operation.
+  TextOperation.prototype.apply = function (str) {
+    var operation = this;
+    if (str.length !== operation.baseLength) {
+      throw new Error("The operation's base length must be equal to the string's length.");
+    }
+    var newStr = [], j = 0;
+    var strIndex = 0;
+    var ops = this.ops;
+    for (var i = 0, l = ops.length; i < l; i++) {
+      var op = ops[i];
+      if (isRetain(op)) {
+        if (strIndex + op > str.length) {
+          throw new Error("Operation can't retain more characters than are left in the string.");
+        }
+        // Copy skipped part of the old string.
+        newStr[j++] = str.slice(strIndex, strIndex + op);
+        strIndex += op;
+      } else if (isInsert(op)) {
+        // Insert string.
+        newStr[j++] = op;
+      } else { // delete op
+        strIndex -= op;
+      }
+    }
+    if (strIndex !== str.length) {
+      throw new Error("The operation didn't operate on the whole string.");
+    }
+    return newStr.join('');
+  };
+
+  // Computes the inverse of an operation. The inverse of an operation is the
+  // operation that reverts the effects of the operation, e.g. when you have an
+  // operation 'insert("hello "); skip(6);' then the inverse is 'delete("hello ");
+  // skip(6);'. The inverse should be used for implementing undo.
+  TextOperation.prototype.invert = function (str) {
+    var strIndex = 0;
+    var inverse = new TextOperation();
+    var ops = this.ops;
+    for (var i = 0, l = ops.length; i < l; i++) {
+      var op = ops[i];
+      if (isRetain(op)) {
+        inverse.retain(op);
+        strIndex += op;
+      } else if (isInsert(op)) {
+        inverse['delete'](op.length);
+      } else { // delete op
+        inverse.insert(str.slice(strIndex, strIndex - op));
+        strIndex -= op;
+      }
+    }
+    return inverse;
+  };
+
+  // Compose merges two consecutive operations into one operation, that
+  // preserves the changes of both. Or, in other words, for each input string S
+  // and a pair of consecutive operations A and B,
+  // apply(apply(S, A), B) = apply(S, compose(A, B)) must hold.
+  TextOperation.prototype.compose = function (operation2) {
+    var operation1 = this;
+    if (operation1.targetLength !== operation2.baseLength) {
+      throw new Error("The base length of the second operation has to be the target length of the first operation");
+    }
+
+    var operation = new TextOperation(); // the combined operation
+    var ops1 = operation1.ops, ops2 = operation2.ops; // for fast access
+    var i1 = 0, i2 = 0; // current index into ops1 respectively ops2
+    var op1 = ops1[i1++], op2 = ops2[i2++]; // current ops
+    while (true) {
+      // Dispatch on the type of op1 and op2
+      if (typeof op1 === 'undefined' && typeof op2 === 'undefined') {
+        // end condition: both ops1 and ops2 have been processed
+        break;
+      }
+
+      if (isDelete(op1)) {
+        operation['delete'](op1);
+        op1 = ops1[i1++];
+        continue;
+      }
+      if (isInsert(op2)) {
+        operation.insert(op2);
+        op2 = ops2[i2++];
+        continue;
+      }
+
+      if (typeof op1 === 'undefined') {
+        throw new Error("Cannot compose operations: first operation is too short.");
+      }
+      if (typeof op2 === 'undefined') {
+        throw new Error("Cannot compose operations: first operation is too long.");
+      }
+
+      if (isRetain(op1) && isRetain(op2)) {
+        if (op1 > op2) {
+          operation.retain(op2);
+          op1 = op1 - op2;
+          op2 = ops2[i2++];
+        } else if (op1 === op2) {
+          operation.retain(op1);
+          op1 = ops1[i1++];
+          op2 = ops2[i2++];
+        } else {
+          operation.retain(op1);
+          op2 = op2 - op1;
+          op1 = ops1[i1++];
+        }
+      } else if (isInsert(op1) && isDelete(op2)) {
+        if (op1.length > -op2) {
+          op1 = op1.slice(-op2);
+          op2 = ops2[i2++];
+        } else if (op1.length === -op2) {
+          op1 = ops1[i1++];
+          op2 = ops2[i2++];
+        } else {
+          op2 = op2 + op1.length;
+          op1 = ops1[i1++];
+        }
+      } else if (isInsert(op1) && isRetain(op2)) {
+        if (op1.length > op2) {
+          operation.insert(op1.slice(0, op2));
+          op1 = op1.slice(op2);
+          op2 = ops2[i2++];
+        } else if (op1.length === op2) {
+          operation.insert(op1);
+          op1 = ops1[i1++];
+          op2 = ops2[i2++];
+        } else {
+          operation.insert(op1);
+          op2 = op2 - op1.length;
+          op1 = ops1[i1++];
+        }
+      } else if (isRetain(op1) && isDelete(op2)) {
+        if (op1 > -op2) {
+          operation['delete'](op2);
+          op1 = op1 + op2;
+          op2 = ops2[i2++];
+        } else if (op1 === -op2) {
+          operation['delete'](op2);
+          op1 = ops1[i1++];
+          op2 = ops2[i2++];
+        } else {
+          operation['delete'](op1);
+          op2 = op2 + op1;
+          op1 = ops1[i1++];
+        }
+      } else {
+        throw new Error(
+          "This shouldn't happen: op1: " +
+          JSON.stringify(op1) + ", op2: " +
+          JSON.stringify(op2)
+        );
+      }
+    }
+    return operation;
+  };
+
+  function getSimpleOp (operation, fn) {
+    var ops = operation.ops;
+    var isRetain = TextOperation.isRetain;
+    switch (ops.length) {
+    case 1:
+      return ops[0];
+    case 2:
+      return isRetain(ops[0]) ? ops[1] : (isRetain(ops[1]) ? ops[0] : null);
+    case 3:
+      if (isRetain(ops[0]) && isRetain(ops[2])) { return ops[1]; }
+    }
+    return null;
+  }
+
+  function getStartIndex (operation) {
+    if (isRetain(operation.ops[0])) { return operation.ops[0]; }
+    return 0;
+  }
+
+  // When you use ctrl-z to undo your latest changes, you expect the program not
+  // to undo every single keystroke but to undo your last sentence you wrote at
+  // a stretch or the deletion you did by holding the backspace key down. This
+  // This can be implemented by composing operations on the undo stack. This
+  // method can help decide whether two operations should be composed. It
+  // returns true if the operations are consecutive insert operations or both
+  // operations delete text at the same position. You may want to include other
+  // factors like the time since the last change in your decision.
+  TextOperation.prototype.shouldBeComposedWith = function (other) {
+    if (this.isNoop() || other.isNoop()) { return true; }
+
+    var startA = getStartIndex(this), startB = getStartIndex(other);
+    var simpleA = getSimpleOp(this), simpleB = getSimpleOp(other);
+    if (!simpleA || !simpleB) { return false; }
+
+    if (isInsert(simpleA) && isInsert(simpleB)) {
+      return startA + simpleA.length === startB;
+    }
+
+    if (isDelete(simpleA) && isDelete(simpleB)) {
+      // there are two possibilities to delete: with backspace and with the
+      // delete key.
+      return (startB - simpleB === startA) || startA === startB;
+    }
+
+    return false;
+  };
+
+  // Decides whether two operations should be composed with each other
+  // if they were inverted, that is
+  // `shouldBeComposedWith(a, b) = shouldBeComposedWithInverted(b^{-1}, a^{-1})`.
+  TextOperation.prototype.shouldBeComposedWithInverted = function (other) {
+    if (this.isNoop() || other.isNoop()) { return true; }
+
+    var startA = getStartIndex(this), startB = getStartIndex(other);
+    var simpleA = getSimpleOp(this), simpleB = getSimpleOp(other);
+    if (!simpleA || !simpleB) { return false; }
+
+    if (isInsert(simpleA) && isInsert(simpleB)) {
+      return startA + simpleA.length === startB || startA === startB;
+    }
+
+    if (isDelete(simpleA) && isDelete(simpleB)) {
+      return startB - simpleB === startA;
+    }
+
+    return false;
+  };
+
+  // Transform takes two operations A and B that happened concurrently and
+  // produces two operations A' and B' (in an array) such that
+  // `apply(apply(S, A), B') = apply(apply(S, B), A')`. This function is the
+  // heart of OT.
+  TextOperation.transform = function (operation1, operation2) {
+    if (operation1.baseLength !== operation2.baseLength) {
+      throw new Error("Both operations have to have the same base length");
+    }
+
+    var operation1prime = new TextOperation();
+    var operation2prime = new TextOperation();
+    var ops1 = operation1.ops, ops2 = operation2.ops;
+    var i1 = 0, i2 = 0;
+    var op1 = ops1[i1++], op2 = ops2[i2++];
+    while (true) {
+      // At every iteration of the loop, the imaginary cursor that both
+      // operation1 and operation2 have that operates on the input string must
+      // have the same position in the input string.
+
+      if (typeof op1 === 'undefined' && typeof op2 === 'undefined') {
+        // end condition: both ops1 and ops2 have been processed
+        break;
+      }
+
+      // next two cases: one or both ops are insert ops
+      // => insert the string in the corresponding prime operation, skip it in
+      // the other one. If both op1 and op2 are insert ops, prefer op1.
+      if (isInsert(op1)) {
+        operation1prime.insert(op1);
+        operation2prime.retain(op1.length);
+        op1 = ops1[i1++];
+        continue;
+      }
+      if (isInsert(op2)) {
+        operation1prime.retain(op2.length);
+        operation2prime.insert(op2);
+        op2 = ops2[i2++];
+        continue;
+      }
+
+      if (typeof op1 === 'undefined') {
+        throw new Error("Cannot compose operations: first operation is too short.");
+      }
+      if (typeof op2 === 'undefined') {
+        throw new Error("Cannot compose operations: first operation is too long.");
+      }
+
+      var minl;
+      if (isRetain(op1) && isRetain(op2)) {
+        // Simple case: retain/retain
+        if (op1 > op2) {
+          minl = op2;
+          op1 = op1 - op2;
+          op2 = ops2[i2++];
+        } else if (op1 === op2) {
+          minl = op2;
+          op1 = ops1[i1++];
+          op2 = ops2[i2++];
+        } else {
+          minl = op1;
+          op2 = op2 - op1;
+          op1 = ops1[i1++];
+        }
+        operation1prime.retain(minl);
+        operation2prime.retain(minl);
+      } else if (isDelete(op1) && isDelete(op2)) {
+        // Both operations delete the same string at the same position. We don't
+        // need to produce any operations, we just skip over the delete ops and
+        // handle the case that one operation deletes more than the other.
+        if (-op1 > -op2) {
+          op1 = op1 - op2;
+          op2 = ops2[i2++];
+        } else if (op1 === op2) {
+          op1 = ops1[i1++];
+          op2 = ops2[i2++];
+        } else {
+          op2 = op2 - op1;
+          op1 = ops1[i1++];
+        }
+      // next two cases: delete/retain and retain/delete
+      } else if (isDelete(op1) && isRetain(op2)) {
+        if (-op1 > op2) {
+          minl = op2;
+          op1 = op1 + op2;
+          op2 = ops2[i2++];
+        } else if (-op1 === op2) {
+          minl = op2;
+          op1 = ops1[i1++];
+          op2 = ops2[i2++];
+        } else {
+          minl = -op1;
+          op2 = op2 + op1;
+          op1 = ops1[i1++];
+        }
+        operation1prime['delete'](minl);
+      } else if (isRetain(op1) && isDelete(op2)) {
+        if (op1 > -op2) {
+          minl = -op2;
+          op1 = op1 + op2;
+          op2 = ops2[i2++];
+        } else if (op1 === -op2) {
+          minl = op1;
+          op1 = ops1[i1++];
+          op2 = ops2[i2++];
+        } else {
+          minl = op1;
+          op2 = op2 + op1;
+          op1 = ops1[i1++];
+        }
+        operation2prime['delete'](minl);
+      } else {
+        throw new Error("The two operations aren't compatible");
+      }
+    }
+
+    return [operation1prime, operation2prime];
+  };
+
+  return TextOperation;
+
+}());
+
+// Export for CommonJS
+if (typeof module === 'object') {
+  module.exports = ot.TextOperation;
+}
\ No newline at end of file
diff --git a/lib/ot/wrapped-operation.js b/lib/ot/wrapped-operation.js
new file mode 100644
index 00000000..91050f4e
--- /dev/null
+++ b/lib/ot/wrapped-operation.js
@@ -0,0 +1,80 @@
+if (typeof ot === 'undefined') {
+  // Export for browsers
+  var ot = {};
+}
+
+ot.WrappedOperation = (function (global) {
+  'use strict';
+
+  // A WrappedOperation contains an operation and corresponing metadata.
+  function WrappedOperation (operation, meta) {
+    this.wrapped = operation;
+    this.meta    = meta;
+  }
+
+  WrappedOperation.prototype.apply = function () {
+    return this.wrapped.apply.apply(this.wrapped, arguments);
+  };
+
+  WrappedOperation.prototype.invert = function () {
+    var meta = this.meta;
+    return new WrappedOperation(
+      this.wrapped.invert.apply(this.wrapped, arguments),
+      meta && typeof meta === 'object' && typeof meta.invert === 'function' ?
+        meta.invert.apply(meta, arguments) : meta
+    );
+  };
+
+  // Copy all properties from source to target.
+  function copy (source, target) {
+    for (var key in source) {
+      if (source.hasOwnProperty(key)) {
+        target[key] = source[key];
+      }
+    }
+  }
+
+  function composeMeta (a, b) {
+    if (a && typeof a === 'object') {
+      if (typeof a.compose === 'function') { return a.compose(b); }
+      var meta = {};
+      copy(a, meta);
+      copy(b, meta);
+      return meta;
+    }
+    return b;
+  }
+
+  WrappedOperation.prototype.compose = function (other) {
+    return new WrappedOperation(
+      this.wrapped.compose(other.wrapped),
+      composeMeta(this.meta, other.meta)
+    );
+  };
+
+  function transformMeta (meta, operation) {
+    if (meta && typeof meta === 'object') {
+      if (typeof meta.transform === 'function') {
+        return meta.transform(operation);
+      }
+    }
+    return meta;
+  }
+
+  WrappedOperation.transform = function (a, b) {
+    var transform = a.wrapped.constructor.transform;
+    var pair = transform(a.wrapped, b.wrapped);
+    return [
+      new WrappedOperation(pair[0], transformMeta(a.meta, b.wrapped)),
+      new WrappedOperation(pair[1], transformMeta(b.meta, a.wrapped))
+    ];
+  };
+
+  return WrappedOperation;
+
+}(this));
+
+// Export for CommonJS
+if (typeof module === 'object') {
+  module.exports = ot.WrappedOperation;
+}
\ No newline at end of file