OT算法

function TextOperation () {
    if (!this || this.constructor !== TextOperation) {
      // => function was called without 'new'
      return new TextOperation();
    }

    // this.ops表示具体的操作，正数表示保持不变、负数表示要删除的字符长度，字符串表示要插入的字符串。
    // 举例说明一下，[10,"-3",abcd"]表示前10个字符保持不变，然后删除三个字符，然后插入“abcd”字符串。
    this.ops = [];

    // 表示操作之前字符串的长度
    this.baseLength = 0;
    // 表示操作完成字符串的长度
    this.targetLength = 0;
  }

// 把两个同时发生的冲突操作A和B转换为A'和B'使 `apply(apply(S, A), B') = apply(apply(S, B), A')`
// 这是OT算法的核心
// 方法的传入参数operation1，operation2，分别表示操作A、B；
// operation1prime，operation2prime分别表示操作A'和B'。
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) {
        // 每一轮迭代保证operation1和operation2操作字符串的相同位置，这样转换操作才有意义。
        
        if (typeof op1 === 'undefined' && typeof op2 === 'undefined') {
            // end condition: both ops1 and ops2 have been processed
            break;
        }

        // 接下来的两种情况：如果A、B中的一个或者两个都是insert操作。
        // 在相应的运算中插入字符串，然后跳过插入字符串的长度。
        // 比如：A是insert操作，那么A'也是insert操作，B'先 retain A插入字符串的长度；
        // A、B都是insert操作时，A'就是insert操作，B'就是retain A插入字符串的长度之后再插入B字符串。
        
        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)) {
            // 如果A、B都是retain操作：
            // 比较A、B的长度，合并后A'和B'都变成了长度较小的retain操作。
            // 当A>B时，A'就变成了retain B的大小，A操作变成了retain(B-A),
            // 等下一轮循环再和B中
            // 相同位置的字符串合并操作。 
            // 反之B>A时，同理。
            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)) {
            // 如果A、B都是delete操作，我们合并时，
            // 不需要记录delete（其实记也可以、不过A、B都delete的话没有必要）。
            // 我们需要做的是把delete内容较少的忽略，保留住delete内容多的操作等下一次迭代，
            // 和上面的retain道理相同。
            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++];
            }
            
        } else if (isDelete(op1) && isRetain(op2)) {
            // 如果A是delete，B是retain，比较A和B的绝对值大小。
            // 如果delete的内容比retain多，那A'的delete就是B的值，A的delete长度变成A+B，
            // 也就是删除内容的长度减小了；
            // 如果删除和保持的内容一样多，那B'的delete等于A、B都可以；
            // 如果delete的内容比retain少，那A'的delete就是A的值，B的retain长度变成A+B，
            // 也就是保持的内容减少了。
            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)) {
            // 如果A是retain，B是delete，同上。
            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];
};

// 计算操作的逆操作，通过执行逆操作可以恢复操作的效果，逆操作主要用来实现撤销功能。
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)) {
            // retain的逆操作还是retain，
            // 因为逆操作的目的是为了恢复操作效果，retain相当于没有操作所以逆操作也就保持不变就好了。
            inverse.retain(op);
            strIndex += op;
        } else if (isInsert(op)) {
            // insert的逆操作是delete
            inverse['delete'](op.length);
        } else { // delete op
            // delete的逆操作是insert
            inverse.insert(str.slice(strIndex, strIndex - op));
            strIndex -= op;
        }
    }
    return inverse;
};

// 合并两个连续的操作为一个操作，合并后保持apply(apply(S, A), B) = apply(S, compose(A, B))成立
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(); 
    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) {
        // 每一轮迭代保证operation1和operation2操作字符串的相同位置，这样合并操作才有意义。
        
        // 根据op1和op2的操作类型选择如何合并。
       
        if (typeof op1 === 'undefined' && typeof op2 === 'undefined') {
            // 结束条件是ops1和ops2都已经遍历完成。
            break;
        }
        
        // 以下内容可以参照transform方法理解，就不详细注释了。

        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;
};

// 根据原始字符串和操作返回新的字符串
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.");
            }
            // 复制老字符串中被retain的部分
            newStr[j++] = str.slice(strIndex, strIndex + op);
            strIndex += op;
        } else if (isInsert(op)) {
            // 加入insert字符串
            newStr[j++] = op;
        } else { // 删除操作
            strIndex -= op;
        }
    }
    if (strIndex !== str.length) {
        throw new Error("The operation didn't operate on the whole string.");
    }
    return newStr.join('');
};

// 把当前文档存储到document，所有操作放到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 ...
    // ...并针对所有未知操作进transform
    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.
    // 返回操作，并由调用此方法的地方把operation广播给其他用户。
    return operation;
  };

function Client (revision) {
    this.revision = revision; // 下一个预期的版本号
    this.state = synchronized_; // 当前状态
}

// Synchronized状态代表客户端没有需要发送到服务端的操作。
function Synchronized () {}
Client.Synchronized = Synchronized;

...省略Synchronize绑定的方法。

// AwaitingConfirm状态代表客户端有一个操作已经发送给服务端，等待服务端响应。
function AwaitingConfirm (outstanding) {
    // 记录已经发送等待返回的操作
    this.outstanding = outstanding;
}
Client.AwaitingConfirm = AwaitingConfirm;

...省略AwaitingConfirm绑定的方法。

// AwaitingWithBuffer状态代表客户端有一个操作已经发送给服务端，等待服务端响应，并且本地有更多操作还在等待发送
function AwaitingWithBuffer (outstanding, buffer) {
    // 记录已经发送等待返回的操作
    this.outstanding = outstanding;
    // 记录客户端未发送的操作
    this.buffer = buffer;
}
Client.AwaitingWithBuffer = AwaitingWithBuffer;

...省略AwaitingWithBuffer绑定的方法。

 Synchronized.prototype.applyClient = function (client, operation) {
    // 当用户编辑文档时把操作发送到服务端，然后切换到AwaitingConfirm状态
    client.sendOperation(client.revision, operation);
    return new AwaitingConfirm(operation);
  };

  Synchronized.prototype.applyServer = function (client, operation) {
    // 从服务端接收到新的操作时，把操作应用到当前文档。
    client.applyOperation(operation);
    return this;
  };

AwaitingConfirm.prototype.applyClient = function (client, operation) {
    // 当用户编辑文档时并不立刻发送操作给服务端，而且把状态切换到AwaitingWithBuffer。
    return new AwaitingWithBuffer(this.outstanding, operation);
  };

  AwaitingConfirm.prototype.applyServer = function (client, operation) {
    // 服务端返回的operation和本地操作合并的菱形图表示:
    //
    //                   /\
    // this.outstanding /  \ operation
    //                 /    \
    //                 \    /
    //  pair[1]         \  / pair[0] (new outstanding)
    //  (can be applied  \/
    //  to the client's
    //  current document)
    //  pair[1] 可以应用到本客户端。
    var pair = operation.constructor.transform(this.outstanding, operation);
    client.applyOperation(pair[1]);
    return new AwaitingConfirm(pair[0]);
  };

  AwaitingConfirm.prototype.serverAck = function (client) {
    // 服务端已确认客户端的操作然后切换到Synchronized状态。
    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.
    // 客户端断开重连之后，继续发送operation。
    client.sendOperation(client.revision, this.outstanding);
  };

AwaitingWithBuffer.prototype.applyClient = function (client, operation) {
    // 合并用户操作。
    var newBuffer = this.buffer.compose(operation);
    return new AwaitingWithBuffer(this.outstanding, newBuffer);
  };

  AwaitingWithBuffer.prototype.applyServer = function (client, operation) {
    // 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) {
    // operration已经服务端确认，发送buffer操作，并把状切换为AwaitingConfirm。
    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.
    // 客户端断开重连之后，继续发送operation。
    client.sendOperation(client.revision, this.outstanding);
  };