Blog 协同编辑

协同编辑 - OT算法

Open z2014 opened this issue 4 years ago • 1 comments

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

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

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

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

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

要实现上面这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是对当前字符串同一位置所进行的操作。