OT 算法的 transform 源码走读

|apple -> appe // | 代表光标位置

光标先向后移 3 位, app|le               // retain(3) = 3
删除当前光标后的 1 个字符, app|e         // delete(1) = -1
光标向后移动 1 位结束字符串遍历, appe|    // retain(1) = 1

|apple -> apppple // | 代表光标位置

光标先向后移 3 位, app|le                // retain(3) = 3
当前光标前插入 'pp', apppp|le            // insert('pp') = 'pp'
光标向后移动 2 位结束字符串遍历, apppple|  // retain(1) = 1

// 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.
    // 每一轮对当前两人的操作(使用 i1, i2 表示操作数组中的当前操作下标)进行处理
    // 确保光标在输入中位置相同

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.
    // 下面处理其中一个是插入操作的情况
    // 如果 A 的当前操作时插入, 不管 B 是什么操作, 先跳过.
    if (isInsert(op1)) {
      // A' 也进行插入操作
      operation1prime.insert(op1);
      // B' 由于 A 已经把数据插入了，直接后移至插入结束位置
      operation2prime.retain(op1.length);
      // 这里只有 A 完成了一个操作
      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;
    // 如果两个操作都是后移，移动两个操作中比较小的一个，剩下的下一轮处理。
    // 比如 A 后移 5 位, B 后移 8 格, A'，B' 都后移 min(5, 8) 格，
    // B 剩下的 retain(3) 下一轮和 A 的下一个操作一起处理
    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)) {
      // 如果都是删除，先删除 min(abs(op1), abs(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)) {
      // 如果有一个删除和一个后移，删除的多的话先删除 op2 个字符，然后 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 {
        // 如果删除的少，就删除 op1 个字符，然后 op2 去掉 abs(op1) 步，
        // 剩下的下一轮进行处理 
        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];
};

源字符串：apple

A编辑的结果：appple -> [3, 'p', 2]
B编辑的结果：aplle  -> [2, -1, 1, 'l', 1]

下面计算 A' 和 B', 使得 
apply(apply(apple, A), B') === apply(apply(apple, B), A')

// Aretain Bretain
A : [3, 'p', 2]
B : [2, -1, 1, 'l', 1]
A': []
B': []
// Aretain Bdelete
A : [1, 'p', 2]
B : [-1, 1, 'l', 1]
A': [2]
B': [2]
// Ainsert
A : ['p', 2]
B : [1, 'l', 1]
A': [2]
B': [2, -1]
// Aretain Bretain
A : [2]
B : [1, 'l', 1]
A': [2, 'p']
B': [2, -1, 1]
// Binsert
A : [1]
B : ['l', 1]
A': [2, 'p', 1]
B': [2, -1, 2]
// Aretain Bretain
A : [1]
B : [1]
A': [2, 'p', 2]
B': [2, -1, 2, 'l']
// end
A : []
B : []
A': [2, 'p', 3]
B': [2, -1, 2, 'l', 1]

最终得到 A' = [2, 'p', 3], B' = [2, -1, 2, 'l', 1]

对 appple 应用 B' -> applle
对  aplle 应用 A' -> applle