简体中文

基于Delta的线性数据结构模型

数据模型的设计是编辑器的核心基础，其直接影响了选区模型、DOM模型、状态管理等模块的设计。例如在quill中的选区模型是index + len的表达，而slate中则是anchor + focus的表达，这些都是基于数据模型的设计而来的。因此我们从零实现的富文本编辑器就需要从数据模型的设计开始，之后就可以逐步实现其他模块。

从零实现富文本编辑器项目的相关文章:

Delta

在先前的架构设计中我们已经提到了，我们实现的扁平数据结构且独立分包设计，无论是在编辑器中操作，还是在服务端数据解析，都可以更加方便地处理。相比较来说，嵌套的数据结构能够更好地对齐DOM表达，然而这样对于数据的操作却变得更加复杂。

因此在数据结构的设计上，我们是基于quill的delta结构进行了改造。最主要的部分是将其改造为immutable的实现，在编辑器中实际是维护的状态而不是本身的delta结构。并且精简了整个数据模型的表达，将复杂的insert与Attribute类型缩减，那么其操作逻辑的复杂度也会降低。

delta是一种简洁而功能强大的格式，用于描述文档内容及其变化。该格式基于JSON，不仅便于阅读，同时也易于机器解析。通过使用delta描述的内容，可以准确地描述任何富文本文档的内容和格式信息，避免了HTML中常见的歧义和复杂性。

delta由一系列操作组成，这些操作描述了对文档进行的更改。常见的操作包括insert、delete、retain。需要注意的是，这些操作不依赖于具体的索引位置，其总是描述当前索引位置的更改，并且可以通过retain来移动指针位置。

delta既可以表示整个文档，也可以表示对文档进行的更改。那么在这里我们将delta的主要类对象及相关操作逻辑进行描述，特别是在编辑器中实际应用场景，以及主要的改造和相关类型声明。

insert

insert方法是将数据插入到delta的操作，这就是delta。当描述整个文档内容时，整个数据的内容应该全部都是insert。首个参数是要插入的文本内容，第二个参数是可选的属性对象，用于描述文本的格式信息。

const delta = new Delta();
delta.insert("123").insert("567", { a: "1" });
// [{"insert":"123"},{"insert":"567","attributes":{"a":"1"}}]

原始的insert参数是可以对象类型的Embed结构，这种结构可以表达Image、Video、Mention等非文本结构的数据，而属性AttributeMap参数是Record<string, unknown>类型，这样用来描述复杂属性值。

在这里我们将其精简了，insert参数仅支持string类型，而具体的schema则在编辑器的初始化时定义，格式信息则收归于Attrs中描述。而AttributeMap则改为Record<string, string>类型，并且可以避免诸如CloneDeep、isEqual等对于复杂数据结构的实现。

其实在EtherPad中就是将Attribute就是[string, string]类型，在这里我们也是使用了类似的设计。在这种基础结构设计下，我们更推荐将属性值扁平地放置于attributes属性中，而不是使用单个属性值作为key，将所有属性值嵌套地放置于value中。

export interface AttributeMap {
  [key: string]: string;
}

delta整个名字通常会用于描述变更，那么除了描述整个文档内容外，当然还可以描述文档内容的变更。不过应用变更的内容需要用到compose，这个方法的描述我们在后边再看。

const delta1 = new Delta().insert("123");
const delta2 = new Delta().insert("456");
delta1.compose(delta2); // [{"insert":"456123"}]

delete

delete方法描述了删除内容的长度，由于上述的定义我们现在的内容全部都是文本，在原始的数据定义中嵌入Embed的长度为1。

const delta = new Delta().insert("123");
delta.compose(new Delta().delete(1)); // [{"insert":"23"}]

其实这里是比较有趣的事情，通过delete来描述变更时，无法得知究竟删除了哪些内容。那么这种情况下，进行invert的时候就需要额外的数据来构造insert操作。类似的场景在OT-JSON中，内容描述是直接写入op的，因此可以直接根据op来进行invert操作。

const delta = new Delta().insert("123");
const del = new Delta().delete(1);
const invert1 = del.invert(delta); // [{"insert":"1"}]
const delta2 = delta.compose(del); // [{"insert":"23"}]
delta2.compose(invert1); // [{"insert":"123"}]

retain

retain方法描述了保留内容的长度，换句话说，这个操作可以用来移动指针。

const delta = new Delta().insert("123");
delta.compose(new Delta().retain(1).insert("a")); // [{"insert":"1a23"}]

同时retain操作也可以用于修改内容的属性值，此外如果想删除某个属性，只需要将value设置为""即可。

const delta = new Delta().insert("123");
const d2 = new Delta().retain(1).retain(1, { "a": "1" });
const d3 = delta.compose(d2); // [{"insert":"1"},{"insert":"2","attributes":{"a":"1"}},{"insert":"3"}]
d3.compose(new Delta().retain(1).retain(1, { "a": "" })); // [{"insert":"123"}]

push

push方法是上述的insert、delete、retain依赖的基础方法，主要实现是将内容推入到delta维护的数组中。这里的实现非常重要部分是op的合并，当属性值相同时，则需要将其合并为单个op。

const delta = new Delta();
delta.push({ insert: "123" }).push({ insert: "456" }); // [{"insert": "123456"}]

当然这里不仅仅是insert操作会合并，对于delete、retain操作也是一样的。这里的合并操作是基于op的attributes属性值，如果attributes属性值不同，则会被视为不同的op，不会自动合并。

const delta = new Delta();
delta.push({ delete: 1 }).push({ delete: 1 }); // [{"delete": 2}]
const delta2 = new Delta();
delta2.push({ retain: 1 }).push({ retain: 1 }); // [{"retain": 2}]
const delta3 = new Delta();
delta3.push({ retain: 1 }).push({ retain: 1, attributes: { a: "1"} }); // [{"retain": 1}, {"retain": 1, "attributes": {"a": "1"}}]

slice

slice方法是用于截取delta的操作，这个方法是基于op的length属性值进行截取的。

const delta = new Delta().insert("123").insert("456", {a: "1"});
delta.slice(2, 4); // [{"insert":"3"},{"insert":"4","attributes":{"a":"1"}}]

eachLine

eachLine方法用于按行迭代整个delta，我们的整体数据结构是线性的，但是编辑器DOM需要按行来划分内容，因此基于\n来划分行就是比较常规的操作了。

这个方法对于编辑器的初始化非常重要，而当初始化完毕后，我们的变更就需要基于状态来实现，而不是每次都需要经过该方法。在这里我们也对其进行了改造，原始的eachLine方法是不会携带\n节点。

const delta = new Delta().insert("123\n456\n789");
delta.eachLine((line, attributes) => {
  console.log(line, attributes);
});
// [{insert:"123"},{insert:"\n"}] {}
// [{insert:"456"},{insert:"\n"}] {}
// [{insert:"789"},{insert:"\n"}] {}

diff

diff方法用于对比两个delta之间的差异，这个方法实际上是基于纯文本的myers diff来实现。通过将delta转换为纯文本，在diff过后不断挑选较短的操作部分来实现delta之间的diff。

其实在我们的实现中完全可以将diff方法独立出来，这里唯一引用了外部的fast-diff依赖。在quill中diff是必要的，因为其完全是非受控的输入方式，文本的输入依赖于对DOM文本的diff来实现，而我们的输入是依赖beforeinput事件的半受控输入，因此并不强依赖diff。

const delta1 = new Delta().insert("123");
const delta2 = new Delta().insert("126");
delta1.diff(delta2); // [{"retain":2},{"insert":"6"},{"delete":1}]

chop

chop方法用于裁剪末尾的retain操作，当存在末尾的retain且没有属性操作时，其本身是没有意义的，因此可以调用该方法检查并移除。

const delta = new Delta().insert("123").retain(1);
delta.chop(); // [{"insert":"123"}]

compose

compose方法可以将两个delta合并为一个delta，具体来说则是将B的delta操作应用到A的delta上，此时返回的是一个新的delta对象。当然在我们的实现中，继承了原始Delta类重写了compose方法，做到了immutable。

compose在编辑器中的应用场景非常多，例如输入事件、内容粘贴、历史操作等场景中，类似于编辑器的apply方法，相当于应用内容变更。

const delta1 = new Delta().insert("123");
const delta2 = new Delta().retain(1).delete(1);
delta1.compose(delta2); // [{"insert":"13"}]

invert

invert方法是将delta的操作进行反转，这个方法在历史操作中非常重要，因为本身undo就是需要将当前的操作进行反转。此外，在实现OT的local-cs中，invert也是非常重要的方法。

值得关注的是，上边也提到了delete操作和retain操作在本身执行时是不会记录原始内容的，因此在invert是需要原始的delta作为数据源来进行操作，注意这里的delta是最初的delta，而不是invert后的delta。

const delta = new Delta().insert("123");
const del = new Delta().delete(1);
const invert1 = del.invert(delta); // [{"insert":"1"}]
const delta2 = delta.compose(del); // [{"insert":"23"}]
delta2.compose(invert1); // [{"insert":"123"}]

concat

concat方法可以连接两个delta到新的delta中。这个操作与compose不同，compose是将B的操作应用到A上，而concat则是将B的操作追加到A的操作后。

const delta1 = new Delta().insert("123");
const delta2 = new Delta().insert("456");
delta1.compose(delta2); // [{"insert":"456123"}]
delta1.concat(delta2); // [{"insert":"123456"}]

transform

transform方法是实现操作OT协同的基础，即使不实现协同编辑，在编辑器中的历史操作模块中也会需要这部分实现。假设我们现在有用户A[uid:1]和用户B[uid:2]，此时我们以uid定义优先级，则A的操作优先级高于B，且当前的文档内容为12。

如果是在协同中的话，b'=a.t(b)的意思是，假设a和b都是从相同的draft分支出来的，那么b'就是假设a已经应用了，此时b需要在a的基础上变换出b'才能直接应用，我们也可以理解为transform解决了a操作对b操作造成的影响。

那么我们假设A在12后的位置插入了A字符，B在12后的位置插入了B字符。如果进行协同操作，那么两者相当于同时在同一个位置插入了字符，如果不进行操作变换而直接应用的话，两者的数据就会出现冲突，A的数据是12BA，而B的数据是12AB，因此就需要先转换再应用。

// User A
const base = new Delta().insert("12");
const delta = new Delta().retain(2).insert("A");
let current = base.compose(delta); // 12A
// Accept Remote B
const remote = new Delta().retain(2).insert("B");
// ob1=OT(oa, ob)
const remote2 = delta.transform(remote, true); // [{"retain":3},{"insert":"B"}] 
current = current.compose(remote2); // 12AB
// User B
const base = new Delta().insert("12");
const delta = new Delta().retain(2).insert("B");
let current = base.compose(delta); // 12B
// Accept Remote A
const remote = new Delta().retain(2).insert("A");
// oa2=OT(ob, oa)
const remote2 = delta.transform(remote, false); // [{"retain":2},{"insert":"A"}] 
current = current.compose(remote2); // 12AB

transformPosition

transformPosition方法用于将指定的位置进行转换，这个方法的主要场景是编辑器中的选区/光标的位置变换，例如光标此时在1后面，构造delta在1之前增加了内容的话，那么光标就需要跟随移动。

const delta = new Delta().retain(5).insert("a");
delta.transformPosition(4); // 4
delta.transformPosition(5); // 6

OpIterator

OpIterator类定义一个迭代器，用于迭代delta中的op操作。迭代器大量用于diff、compose、transform等方法中，需要注意的是该迭代器调用next时不会跨越op，即使传递的length大于当前op的长度。

const delta = new Delta()
  .insert("Hello", { bold: "true" })
  .insert(" World", { italic: "true" });
  .retain(3);
iter.next(2); // { insert: "He", attributes: { bold: "true" } }
iter.next(10); // { insert: "llo", attributes: { bold: "true" } }

EtherPad

EtherPad同样是非常优秀的协同编辑器，其内置实现的数据结构同样是线性的，文档整体描述称为ClientVars，数据结构变更被称为ChangeSet。协同算法的实现是EasySync，且其文档中对如何进行服务端调度也有较为详细的描述。

ClientVars/Changeset同样是一种基于JSON的数据格式，用于描述文档的内容及其变更。但是其并没有像Delta那么清晰的表达，JSON结构主要是AttributePool内，而对于文本内容的表达则是纯文本的结构。

文档描述

文档内容是使用ClientVars的数据结构表示的，其中包含了三个部分，apool文本属性池、text文本内容、attribs属性描述。在下面的例子中，我们描述了标题、加粗、斜体、纯文本的内容，那么这其中的内容如下所示。

({
  initialAttributedText: {
    text: "short description\n*Heading1\ntext\n*Heading2\nbold italic\nplain text\n\n",
    attribs: "*0|1+i*0*1*2*3+1*0|2+e*0*4*2*3+1*0|1+9*0*5+4*0+1*0*6+6*0|2+c|1+1",
  },
  apool: {
    numToAttrib: {
      "0": ["author", "a.XYe86foM7oYgmpuu"],
      "1": ["heading", "h1"],
      "2": ["insertorder", "first"],
      "3": ["lmkr", "1"],
      "4": ["heading", "h2"],
      "5": ["bold", "true"],
      "6": ["italic", "true"],
    },
    nextNum: 7,
  },
});

对于这个内容直接看上去是比较复杂的，当然实际上也是比较复杂的。apool是一个属性池，所有对于文本内容的装饰都是在这里存储的，也就是其中的numToAttrib属性存储的[string, string]值，nextNum则是下个要放置的索引。text则是纯文本的内容，相当于此时文档的纯文本内容。attribs则是根据text的纯文本内容，并且取得apool中的属性值，相当于装饰文本内容的编码。

因此attribs需要单独拿出来解析，*n表示取第n个属性应用到文本上，通常需要配合|n和+n属性使用，|n表示影响n行，仅对于\n属性需要使用该属性，+n则表示取出n个字符数，相当于retain操作，不仅可以移动指针，还可以用来持有属性变更。特别需要注意的是|m不会单独出现，其总是与+n一同表达，表示这n个字符中存在m个换行，且最后一个应用的字符必然是\n。

此外，EasySync里面的数字大都是36进制的，因此这里的+i/+e等都不是特殊的符号，需要用0-9数字来表示0-9的字符，而10-35则是表示a-z，例如+i就是i - a = 8 => 8 + 10 = 18。

  • *0表示取出author的属性，|1+i表示将其应用到了i长度即18，字符为short description\n，由于其包含\n则定义|1。
  • *0*1*2*3表示取出前4个属性，+1表示将其应用1个字符，即*字符，在EasySync中行首的该字符承载了行属性，而非放置\n中。
  • *0表示取出author的属性，|2+e表示应用了e长度即14，字符为Heading1\ntext\n，其包含两个\n则定义|2。
  • *0*4*2*3表示取出相关属性，+1表示将其应用1个字符，即*字符表示行属性内容。
  • *0|1+9表示取出author的属性，+9表示将其应用9个字符，即Heading2\n，末尾是\n则定义|1。
  • *0*5+4表示取出加粗等属性，应用4个字符，即bold。
  • *0+1表示取出author的属性，应用1个字符即空格。
  • *0*6+6表示取出斜体等属性，应用6个字符，即italic。
  • *0|2+c表示取出相关属性，应用12个字符即\nplain text\n，存在两个\n则定义|2。
  • |1+1表示末尾的\n属性，在EasySync中行末的该字符需要单独定义。

变更描述

OT操作变换的基准原子实现就是insert、delete、retain三种操作，那么ChangeSet的内容描述自然也是类似，但是数据的变更描述并非像delta的结构那么清晰，而是特别设计了一套数据结构描述。

文档在最开始创建或是导入的时候是初始的ClientVars，而此后每次对于文档内容的修改则是会生成ChangeSet。针对于上述的三种操作对应了三种符号，=表示retain、+表示insert、-表示delete，这三种符号的组合就可以描述文档内容的变更，除此之外还有额外的定义:

  • Z: 首字母为MagicNumber，表示为符号位。
  • :N: 文档原始内容长度为N。
  • >N: 最终文档长度会比原始文档长度长N。
  • <N: 最终文档长度会比原始文档长度短N。
  • +N: 实际执行操作，表示插入了N个字符。
  • -N: 实际实际操作，表示操作删除了N个字符。
  • =N: 实际执行操作，表示操作保留了N个字符，移动指针或应用属性。
  • |N: 表示影响了N行，与上述文档描述一致需要与+/-/=N使用，操作的长度包含N个\n，且末尾操作必须是\n。文档最末尾的\n需要表示的话，则必须要用|1=1表示。
  • *I: 表示应用属性，I为apool中的索引值，在一个+、=或|之前可以有任意数量的*操作。
  • $: 表示结束符号，用于标记Operation部分的结束。
  • char bank: 用于存储insert操作具体的字符内容，在执行插入操作时按序取用。

同样是上述的例子，现在的文档中已经存在exist text\n\n的文本内容，紧接着将上述的内容粘贴到文档中，那么发生的User ChangeSet的变更描述如下:

({
  changeset:
    "Z:c>1t|1=b*0|1+i*0*1*2*3+1*0|2+e*0*4*2*3+1*0|1+9*0+5*0*5+6*0|1+1*0+a$short description\n*Heading1\ntext\n*Heading2\nbold italic\nplain text",
  apool: {
    numToAttrib: {
      "0": ["author", "a.XYe86foM7oYgmpuu"],
      "1": ["heading", "h1"],
      "2": ["insertorder", "first"],
      "3": ["lmkr", "1"],
      "4": ["heading", "h2"],
      "5": ["italic", "true"],
    },
    nextNum: 6,
  },
});
  • Z表示MagicNumber，即符号位。
  • c表示文档原始内容长度为12，即exist text\n\n内容长度。
  • >1t表示最终文档会比原始内容长度多1t，36进制转换1t为64，具体为char bank索引。
  • |1=b表示移动指针长度为b，转换长度为11，文本内容为exist text\n，末尾为\n定义|1。
  • *0|1+i表示从apool中取出0属性，应用i转换长度为18，文本内容为short description\n，末尾为\n定义|1。
  • *0*1*2*3+1表示取出4个属性，应用为1，文本内容为*，具体则是行属性的起始标记。
  • *0|2+e表示取出0属性，应用e转换长度为14，文本内容为Heading1\ntext\n，末尾为\n且包含两个\n定义|2。
  • *0*4*2*3+1表示取出4个属性，应用为1，文本内容为*，同样是行属性的起始标记。
  • *0|1+9表示取出0属性，应用长度为9，文本内容为Heading2\n，末尾为\n定义|1。
  • *0+5表示取出0属性，应用长度为5，文本内容为bold 。
  • *0*5+6表示取出斜体等属性，应用长度为6，文本内容为italic。
  • *0|1+1表示取出0属性，应用长度为1，末尾为\n则定义|1，文本内容为\n。
  • *0+a表示取出0属性，应用长度为a即10，文本内容为plain text。
  • $表示结束符号，后续的内容符号则为char bank，最末尾的\n通常不需要表示，即使表示也需要|1=1单独表示。

Slate

slate的数据结构以及选区的设计几乎完全对齐了DOM结构，且数据结构设计并未独立出来，同样基于JSON的结构，非常类似于低代码的结构设计。操作变换是直接在slate的核心模块Transform中实现，且位置相关操作变换的实现分散在Point、Path对象中。

[
  {
    type: "paragraph",
    children: [
      { text: "This is editable " },
      { text: "rich", bold: true },
      { text: " text." },
    ],
  },
  { type: "block-quote", children: [{ text: "A wise quote." }] },
];

Operation

同样是基于OT实现操作变换算法，线性的数据结构仅需要insert、delete、retain三种基本操作即可实现，而在slate中则实现了9种原子操作来描述变更，这其中包含了文本处理、节点处理、选区变换的操作等。

  • insert_node: 插入节点。
  • insert_text: 插入文本。
  • merge_node: 合并节点。
  • move_node: 移动节点。
  • remove_node: 移除节点。
  • remove_text: 移除文本。
  • set_node: 设置节点。
  • set_selection: 设置选区。
  • split_node: 分割节点。

实际上仅实现应用还好，其相对应的invert、transform则会更加复杂。在slate中的inverse相关操作在operation.ts中实现，与位置相关的transform在path.ts、point.ts中有相关实现。

而实际上这些操作通常都不会在编辑器中直接调用，slate针对这些最基础的操作进行了封装，实现了Transforms模块。在这个模块中实现了诸多具体的操作，例如insertNodes、liftNodes、mergeNodes、moveNodes、removeNodes等等，这里的操作就远不止9种类型了。

  • insertFragment: 在指定的位置插入节点的片段。
  • insertNodes: 在指定的位置插入节点。
  • removeNodes: 在文档中指定的位置删除节点。
  • mergeNodes: 在某个节点与同级的前节点合并。
  • splitNodes: 在某个节点中的指定位置分割节点。
  • wrapNodes: 在某个节点中的指定位置包裹一层节点。
  • unwrapNodes: 在某个节点中的指定位置解除一层包裹节点。
  • setNodes: 在某个节点中的指定位置设置节点属性。
  • unsetNodes: 在某个节点中的指定位置取消节点属性。
  • liftNodes: 在某个节点中的指定位置提升一层节点。
  • moveNodes: 在文档中的指定位置移动节点。
  • collapse: 将选区折叠为插入符。
  • select: 主动设置选区位置。
  • deselect: 取消选区位置。
  • move: 移动选区位置。
  • setPoint: 设置选区的单侧位置。
  • setSelection: 设置新选区位置。
  • delete: 删除选区内容。
  • insertText: 在选区位置插入文本。
  • transform: 在编辑器上immutable地执行op。

OT-JSON

类似的，在OT-JSON(json0)中实现了11种操作，富文本场景中SubType仍然需要扩展，那自然就需要更多的操作来描述变更。因此，实际上以JSON嵌套的数据格式来描述内容变更，要比线形的操作复杂得多。

在slate中是自行封装了编辑器的基础op，如果其本身是在OT-JSON的基础上封装Transforms的话，对于实现OT的协同会更方便一些，ShareDB等协同框架都是要参考OTTypes的定义的。当然，基于CRDT实现的协同看起来更加容易处理。

  • {p:[path], na:x}: 在指定的路径[path]值上加x数值。
  • {p:[path,idx], li:obj}: 在列表[path]的索引idx前插入对象obj。
  • {p:[path,idx], ld:obj}: 从列表[path]的索引idx中删除对象obj。
  • {p:[path,idx], ld:before, li:after}: 用对象after替换列表[path]中索引idx的对象before。
  • {p:[path,idx1], lm:idx2}: 将列表[path]中索引idx1的对象移动到索引idx2处。
  • {p:[path,key], oi:obj}: 向路径[path]中的对象添加键key和对象obj。
  • {p:[path,key], od:obj}: 从路径[path]中的对象中删除键key和值obj。
  • {p:[path,key], od:before, oi:after}: 用对象after替换路径[path]中键key的对象before。
  • {p:[path], t:subtype, o:subtypeOp}: 对路径[path]中的对象应用类型为t的子操作o，子类型操作。
  • {p:[path,offset], si:s}: 在路径[path]的字符串的偏移量offset处插入字符串s，内部使用子类型。
  • {p:[path,offset], sd:s}: 从路径[path]的字符串的偏移量offset处删除字符串s，内部使用子类型。

总结

数据结构的设计是非常重要的，对于编辑器来说，数据结构的设计直接影响着选区模型、DOM模型、状态管理等模块的设计。在这里我们聊到了很多的数据结构设计，Delta、Changeset的线性结构，Slate的嵌套结构，每种数据都有着各自的设计与考量。

那么在选定好了数据结构后，就可以在此基础上实现编辑器的各个模块。我们接下来会从数据模型出发，设计选区模型的表示，然后在此基础上实现浏览器选区与编辑器选区模型的同步。通过选区模型作为操作的目标，来实现编辑器的基础操作，例如插入、删除、格式化等操作。

每日一题

参考