对于在线文档的难点,大部分同学的第一反应都是协同编辑,如何解决多人协作的冲突的问题。
关于ot协作的介绍,这篇文章已经有了一定的初步介绍,本文在这篇文章之上,精读一下ot.js这个库,一起来学习下如何实现一个ot.js。
ot.js中核心的文件是text-operation.js文件,本文精读也将围绕它展开。
对于协同编辑场景,都要解决哪些问题呢?
要实现上面这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种类型的操作,分别是保留,删除,和插入. 对于一系列操作,我们需要记录字符串初始化的长度和操作之后的目标长度。
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。
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。
这个方法是用来将两个opts数组合并成一个,
也就是s.apply(a, b) = s.apply(compose(a, b))
;
因为源代码比较长,这里我们就只解析下compose的思路。
要将两个opts合并,那么我们就维护两个指针,移动对应的两个opts数组:
(以下简写a=opts1[i]; b = opts2[j])
在合并opts的过程中,我们始终要保证a和b是对当前字符串同一位置所进行的操作。
和compose方法类似,只是transform是为了将两个opts生成相对应互补的opts,来解决保证两个用户的界面展示一致,解决问题二。也就是 `s.apply(compose(a, b')) = s.apply(compose(b, a')).