多人协同编辑的实现

[Aaaaash]

本系列文章为Monaco-Editor编辑器折腾、踩坑记录，涉及到协同编辑、代码提示、智能感知等功能的实现，不定期更新

Monaco-Editor简介

monaco-editor是微软开源的一款web端文本编辑器，也就是vscode内置的编辑器，扩展性很强，原生暴露了很多用于代码提示、高亮显示等API

仅为核心编辑器部分，不包含vscode的插件系统、文件数及terminal

基本用法

monaco的基本用法非常简单，导入核心依赖及相应语言依赖包，调用monaco.editor.create方法即可创建一个简单的编辑器

import * as monaco from 'monaco-editor/esm/vs/editor/editor.api';
import 'monaco-editor/esm/vs/editor/browser/controller/coreCommands';
import 'monaco-editor/esm/vs/editor/contrib/find/findController';

// php依赖包，提供代码语法解析及代码高亮等功能
import 'monaco-editor/esm/vs/basic-languages/php/php';
import 'monaco-editor/esm/vs/basic-languages/php/php.contribution';

const container = document.querySelector('#container');

const editor = monaco.editor.create(container, {
  language: 'php',
  glyphMargin: true,
  lightbulb: {
    enabled: true,
  },
  theme: 'vs-dark',
});

monaco的文档是基于typescript的类型声明及注释生成的，所以要开发高级功能大多数情况下需要翻阅monaco.d.ts文件来查找api定义及用法（参考如何画马）😆

多人协同编辑

多人协同编辑，顾名思义就是像Google Doc以及石墨文档、腾讯文档等在线文档产品一样可以两人或两人以上同时编辑同一个文件，双方编辑操作互不干扰且能够自动解决冲突，这里不讨论代码编辑器实时协作功能的必要性，只谈实现。

协同编辑基本实现思路有两种

• CRDT(Conflict-Free Replicated Data Types)
• OT(Operational-Transformation)

CRDT

CRDT即无冲突可复制数据类型，看上去很难理解（其实我也不怎么理解），这是一些分布式系统中适应于不同场景且可以保持最终一致性的数据结构的统称。

也就是说CRDT本身只是一个概念，应用于协作编辑中需要自行实现数据结构，比如GitHub团队开源的teletype-crdt，ATOM的实时协作功能就是基于这个库来实现的，数据传输采用WebRTC，只有在最初的邀请/加入阶段依赖GitHub的服务器外，所有的传输都是点对点的（peer-to-peer），同时以确保隐私，所有数据都是加密的。

OT

Operational-Transformation或者叫操作转换，是指对文档编辑以及同时编辑冲突解决的一类技术，不仅仅是一个算法。与CRDT不同的是，OT算法全程依赖于服务器来保持最终一致性。成本而言，CRDT优于OT，但因CRDT的实现复杂性（没学会），本文主要介绍基于OT算法的实时协同编辑。

OT算法不仅可用于纯文本操作，同时还支持一些更为复杂的场景：

• 协同图形编辑

  CoFlash 支持实时协作的多媒体编辑器，可以让多个用户在同一 Adobe Flash 中同时编辑同一文档

• 协同HTML/XML以及富文本编辑

  EtherPad 基于网络的实时协作编辑器

• 协同电子表格、Word文档等

  Google Mave

• 计算机辅助设计（Maya）

  CoMaya 用于多人协同编辑 Autodesk Maya 文档

等

OT算法维持一致性的基本思路是根据先前执行的并发操作的影响将编辑操作转换为新形式，以便转换后的操作可以实现正确的效果，并确保复制的文档相同。事实上，并不是在多人同时编辑相邻字符时才必须要使用OT，OT的适用性与并发操作的字符/对象数量无关，无论这些目标对象是否相互重叠，无论这些字符相邻远近，OT都会针对具有位置依赖关系的对象进行并发控制。

OT将文档变更表示为三类操作（Operational）

• Insert 插入

• Retain 保留

• Delete 删除

例如对于一个原始内容为“abc”的文档，假设用户O1在文档位置0处插入一个字符“x”,表示为Insert[0,"x"],用户O2在文档位置2处删除一个字符，表示为Delete[2,1](或者Delete[2,'c'])，这将产生一个并发操作。在OT的控制下，本地操作会如期执行，远端服务器收到两个操作后会进行转换Transformation，具体过程如下

• 用户O1首先执行插入操作，文档内容变为“xabc”。然后O2的操作到达且被转换为O2' = T(O2,O1) = Delete[3,1],产生了一个新的操作，此时位置增加了1，因为O1插入了一个字符。然后在文档“xabc”执行O2'，此时文档内容变为“xab”，即“c”被正确的删除。（如果不进行转换，会错误的删除“b”）。
• 用户O2首先执行删除操作，文档内容变为“ab”，然后O1的操作到达且被转换为O1' = T(O1, o2) = Insert[0,"x"],也产生了一个新的操作，由于先前执行的O2与O1互不影响，转换后的O1'与O1相同，文档内容变为“xab”。

这里忽略了光标操作，实际上多用户实时编辑时，应用在编辑器上，并不会真正的去移动光标，只会在相应的位置插入一个fake cursor。

Monaco-Editor 与 ot.js

我们使用ot.js来实现Monaco-Editor的协同编辑。 ot.js包含客户端与服务端的实现，在客户端，它将编辑操作转换为一系列的operation。

// 对于文档“Operational Transformation”
const operation = new ot.Operation()
  .retain(11) // 前11个字符保留
  .insert("color"); // 插入字符
// 这将使文档变更为 "Operationalcolor"

// “abc”
const deleteOperation = new ot.Operation()
  .retain(2) //
  .delete(1)
  .insert("x") // axc

同时operation也是可组合的，比如将两个操作组合为一个操作

const operation0 = new ot.Operation()
  .retain(13)
  .insert(" hello");
const operation1 = new ot.Operation()
  .delete("misaka ")
  .retain(13);

const str0 = "misaka mikoto";

const str1 = operation0.apply(str0); // "misaka mikoto hello"
const str2a = operation1.apply(str1); // "mikoto hello"

// 组合
const combinedOperation = operation0.compose(operation1);
const str2b = combinedOperation.apply(str0); // "mikoto dolor"

应用到Monaco中，我们需要监听编辑器的onChange事件以及光标相关操作事件（selectionChange，cursorChange，blur等）。在文本内容修改的事件中，将每次修改产生的changes转换为一个或多个操作，也叫operation。光标的操作很好处理，转换成一个Retain操作即可。

const editor = monaco.editor.create(container, {
  language: 'php',
  glyphMargin: true,
  lightbulb: {
    enabled: true,
  },
  theme: 'vs-dark',
});

editor.onDidChangeModelContent((e) => {
  const { changes } = e;
  let docLength = this.editor.getModel().getValueLength(); // 文档长度
  let operation = new TextOperation().retain(docLength); // 初始化一个operation，并保留文档原始内容
  for (let i = changes.length - 1; i >= 0; i--) {
      const change = changes[i];
      const restLength = docLength - change.rangeOffset - change.text.length; // 文档
      operation = new TextOperation()
        .retain(change.rangeOffset) // 保留光标位置前的所有字符
        .delete(change.rangeLength) // 删除N个字符（如为0这个操作无效）
        .insert(change.text) // 插入字符
        .retain(restLength) // 保留剩余字符
        .compose(operation); // 与初始operation组合为一个操作
});

这段代码首先创建了一个编辑器实例，监听了onDidChangeModelContent事件，遍历changes数组，change.rangeOffset代表产生操作时的光标位置，change.rangeLength代表删除的字符长度（为0即没有删除操作），restLength是根据文档最终长度 - 光标位置 - 插入字符长度得出，用于在文档中间位置插入字符时保留剩余字符的操作。

但同时我们也要考虑到撤销/重做，ot.js中对撤销/重做的处理是每次编辑操作都需要产生对应的逆操作，并存入撤销/重做栈，在上面代码的循环体中，我们还需要添加一个名为inverse的操作。

let inverse = new TextOperation().retain(docLength);

// 获取删除的字符，实现略
const removed = getRemovedText(change, this.documentBeforeChanged);
  inverse = inverse.compose(
    new TextOperation()
      .retain(change.rangeOffset) // 与编辑相同
      .delete(change.text.length) // 插入变为删除
      .insert(removed) // 删除变为插入
      .retain(restLength); // 同样保留剩余字符

这样就产生了一个编辑操作和一个用于撤销的逆操作，编辑操作会发送到服务端进行转换同时再发送到给其他客户端，逆操作保存在本地用于实现撤销。

撤销/重做的思路很简单，因为不论如何都会对编辑器产成一个change事件，并且实时编辑的状态下，两个用户的撤销/重做栈需要互相独立，也就是说A的操作不能进入B的撤销栈，因而在B执行撤销的时候只能对自己先前的操作产生影响，不能撤销A的编辑，所以我们需要实现一个自定义的撤销函数来覆盖编辑器自带的撤销功能。

得益于monaco强大的扩展性，我们很容易就覆盖了默认的撤销

this.editor.addAction({
  id: 'cuctom_undo',
  label: 'undo',
  keybindings: [
    monaco.KeyMod.CtrlCmd | monaco.KeyCode.KEY_Z
  ],
  run: () => {
    this._undoFn()
  }
})

这里_undoFn的实现不再赘述，实际就是将先前change事件中产生的逆操作保存在一个自定义的undoManager中，每次执行撤销就undoStack.pop()拿出最近一次的操作并应用在本地，同时发送给协作者，因为undoManager中并未保存协作者的逆操作，所以执行撤销不会影响协作者的操作。

ot.js还包含了服务端的实现，只需要将ot.js的服务端代码运行在nodejs中，同时搭建一个简单的websocket服务器即可。

const EditorSocketIOServer = require('ot.js/socketio-server.js');
const server = new EditorSocketIOServer("", [], 1);

io.on('connection', function(socket) {
  server.addClient(socket);
});

服务端接收到每个协作者的operation并进行转换后下发到其他协作者客户端，转换操作实际是调用一个transform函数，可以戳这里ot.js的transform实现查看，实际上这个函数也正是OT技术的核心，由于笔者技术有限，所以不再详细解读这个函数的源码（逃

以上是使用OT在Monaco编辑器中实现实时协同编辑的过程，除了文本编辑操作、撤销/重做机制，还需要处理多光标、多选区等行为，Monaco都有对应的API，很容易就可以实现。

本文简单介绍了Monaco编辑器、实时协同编辑的相关技术、OT技术的基本思路，以及结合Monaco编辑器与ot.js实现协同编辑的方法和服务端的相关处理，如有感兴趣的读者可以点击前往CloudStudio试用。

相关参考连接

• Print Understanding and Applying Operational Transformation
• Operational Transformation Frequently Asked Questions and Answers
• ot.js
• SharedPen 之 Operational Transformation
• Operational Tranformation
• 实时协同编辑的实现

[xueerli]

你好 请问下 重写的撤销/重做是怎么处理撤销时操作的文本索引已变的问题的？ 比如入undo栈时是[2,-1]，在pop [2,-1]之前有其他人在前面输入了其他字符，那[2, -1]中的2的索引就是错的了。 要每次接收到其他人的消息后更新整个undo/redo栈么？

[sodowe666]

大佬你好，请求有没有表格协作的OT冲突处理相关代码可以学习下