协同编辑 - OT算法

[z2014]

对于在线文档的难点，大部分同学的第一反应都是协同编辑，如何解决多人协作的冲突的问题。

关于ot协作的介绍，这篇文章已经有了一定的初步介绍，本文在这篇文章之上，精读一下ot.js这个库,一起来学习下如何实现一个ot.js。

ot.js中核心的文件是text-operation.js文件，本文精读也将围绕它展开。

对于协同编辑场景，都要解决哪些问题呢？

1. 支持将多次操作合并成一次
2. 对不同用户的多次操作进行合并，并返回相对应的opts，使不同用户的界面展示保持一致。
3. 对于用户的操作支持回退

要实现上面这3个需求，我们先来看看如何设计ot算法中的数据结构。

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

可以看到我们对于字符串的操作都保存在了ops数组里，
一共会有3种类型的操作，分别是保留，删除，和插入.
数据结构中还记录了字符串初始化的长度和操作之后的目标长度，
用来做一些opts的判断（eg：equals方法）。

1. 基础方法apply

  TextOperation.apply = function (operation, 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 = operation.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;
      }
      console.log(newStr, strIndex)
    }
    if (strIndex !== str.length) {
      throw new Error("The operation didn't operate on the whole string.");
    }
    return newStr.join('');
  }

tips：因为delete操作，存的值是负数，所以这里是 strIndex -= op。

2. 基础方法invert

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

我们针对原有opts数组生成保存回退操作的相对应的opts。

3. 核心方法compose解析

这个方法是用来将两个opts数组合并成一个，
也就是s.apply(a, b) = s.apply(compose(a, b));
因为源代码比较长，这里我们就只解析下compose的思路。
要将两个opts合并，那么我们就维护两个指针，移动对应的两个opts数组:
(以下简写a=opts1[i]; b = opts2[j])
在合并opts的过程中，我们始终要保证a和b是对当前字符串同一位置所进行的操作。

• 1). a的删除操作是第一优先级，因为b的操作(保留，删除，添加)是基于a的操作之后进行的动作，因此需要先执行a的删除操作。
• 2). b的插入操作是第二优先级，在相同位置下，b的添加操作，从结果上看，都是先于a的保留或者添加的。
• 3). 如果a，b都是保留操作，那我们就保留两个中的公共长度
• 4). 如果a是插入，b是删除，那么我们就将两个操作的相同长度进行合并，保留操作长度剩下的部分，继续遍历
• 5). 如果a是插入，b是保留，那么我们就插入两个操作的公共长度，保留操作长度更长的部分，继续遍历
• 6). 如果a是保留，b是删除，那么我们就删除两个操作的公共长度，保留操作长度更长的剩余部分，继续遍历

4. 核心方法transform解析

和compose方法类似，只是transform是为了将两个opts生成相对应互补的opts，来解决保证两个用户的界面展示一致，解决问题二。也就是 `s.apply(compose(a, b')) = s.apply(compose(b, a')).

• 1). 如果a是插入操作，那么相对应的a'也应该插入相同的元素, b'就应该保留a'的长度(b操作为插入时一样)。
• 2). 如果a和b都是保留操作，那么a'和b'都应该保留min(a, b)的长度
• 3). 如果a和b都是删除操作，那么我们只需要保留两边删除元素不一致的地方即可，然后进入下面的判断
• 4). 如果a是删除，b是保留，那么a'需要添加min(a, b)的长度，进入下一轮遍历
• 5). 如果a是保留，b是删除，和操作5一样。

[Jicoh]

VG