技术随笔

基于Web的富文本编辑器，网上大概有下面的分类，实现的难度也是从易到难。

对于L0和L1的编辑器，文章、开源的库也非常的多，慢慢的对其更加深入的理解。唯独level2的编辑器很难看到太多的资料，只有零碎的一些信息，没有有比较完整的实现方案，这也引起了我更大的好奇。于是有了一个大胆的想法，自己去实现一个会怎么做呢？经过了一系列的研究，总算是做了一个出来，虽然回过头来反思，还非常的不完善，有致命的缺陷需要解决，还需要不断深入探究，但是这个过程学到了好多东西，在此做一下记录和总结。

在开始正式介绍前，先定义一些概念，下文中的方案中直接使用这些关键词，而不做额外的说明

整体的架构是分成三层结构：数据模型层、视图层、UI层 数据模型层主要职责：真实存储文档内容；提供基本的原子操作、命令系统、记录操作日志（用于撤销回放）、生成操作后的数据diff 视图层的主要职责：生成文档树及排版布局能力；构建命令来操作数据，根据数据的diff信息来变更视图的结构（增删改节点）；UI层传递过来的事件聚合处理 UI层的主要职责：真正的渲染视图层的文档结构、光标、选中效果、隐藏输入框； 各类事件的监听 – 键盘事件、鼠标事件、滚轴事件、copy pasta事件等等，并交由视图层处理UI层监听用户操作的事件，交由视图层，视图层把所有的操作封装成一个个command，每个command本质上是对数据层的变更，数据层发生变更后会生成变更前后的diff并返回给到视图层，视图层根据diff信息，来修改文档树的结构，接着通知ui层渲染。

Piecetable数据结构提供了一种思路。也就是把内容分割成一段段的piece，真实的内容统一存储在外部的buffer中，piece本身指向buffer中内容。一个个piece按照顺序链接起来就是完整的内容了，整个piecetable的重点就是如何高效的访问、修改、删除、添加这些piece，这里就需要用另外的数据结构来管理这些piece

上面对于Piece Table这种数据结构的描述，可以看到是对于纯文本内容的表现。只要对于每个Piece稍加一些属性就可以扩展成为对于富文本的表示了。

Piece增加了富文本的扩展之后，piece的数量会有显著的提升，拥有不同meta信息的也会分割成不同的piece。

富文本的内容本质上是有先后顺序的，所以需要一种高效的数据结构来表示线性的piece。下面是一些数据结构的基本操作性能比较：可以看到，在所有的数据结构中平衡二叉树的所有操作的性能是最稳定的，性能也非常好。在富文本的编辑中，会涉及到大量的增删的操作，对于性能、稳定性都有着较高的要求，所以就我个人目前的所知平衡二叉树是最好的选择。平衡二叉树的实现有多种方式，这里我采用红黑树的方式实现，这也是我所知最稳定高效的实现方式。

Piece是按照顺序存储的，每个piece本身有一个长度。我们需要通过 数字索引来查找到所在piece。如何快速查找呢？每个树的节点都保存其左子树和右子树的长度。也就是一棵二叉统计树。查找的过程是这样：

查找的过程的时间复杂度是：O(log(n))至此对于这棵piece树的所有操作（访问、新增、修改、删除）都控制在了O(log(n))的时间复杂度。整体上每个操作都是非常的稳定的。

这里要分下面这些情况：

初次加载，视图层会遍历数据层的piece，然后生成一个树状的文档结构。如下图：文档是由一组段落组成，段落是由段落行组成，行是由文字或者行内元素组成。这棵树的叶子节点必须是text或者是inline的组合。段落中的行是动态生成的，段落内容有改变的时候，都会需要重新计算text和inline的长度，然后计算该段落有多少 行组成。各种元素的示例如下图：

选中区域可以通过两个数字索引来表示，比如[focus, anchor] = [5, 10]，选中内容索引5到10之间的内容。每个line元素都有一个隐藏的选中元素，当line元素在选中区域的时候，设置一个背景颜色覆盖在该行。选中的状态有下面几种情况，如图示意：文档中的每一行的选中只有可能是其中一种情况。其中如果选中的前后focus和anchor相同，相当于选中同一个点，这个状态就是光标。

光标的ui实现：宽度为0的div元素，设置border-left为1px，然后设置一个透明度0到1，1到0的循环动画来实现。光标是否展示：根据选中区域决定，如果focus = anchor 那么表示没有区域选中，展示光标，否则不展现。光标的定位：根据选中的数字索引，把数字索引转换为（x,y）的坐标位置。

视图结构的每一个节点都会记录：位置信息（长、宽、右上角坐标）和节点自身及子节点包含的内容长度。数字索引转坐标：从根节点开始往下找，直到叶子节点，叶子节点的右上角坐标加上索引所指定的文字的宽度。坐标转数字索引：从根节点开始寻找，该坐标所在的叶子节点，计算所占的文字长度，回溯相加该节点之前的所有节点的长度。

文字类型大概可以分为方块字和字母文字，相同样式的方块字通常可以认为长宽都是一致，而字母则是不同的，比如l和m明显宽度是不同，并且这个还受字体的影响，组合的影响。这表明通过测量一个字母、方块字来应用到所有是不可行的，所以当需要测量的时候，把样式和文字每次都动态的测量。由于js本身没有可以直接测量宽度的接口（canvas中是有的，这是是基于dom实现），所以是如下方法实现的：

段落中需要把文字分割成一行一行的形式，这就需要有一种分割文字的算法。这里采用了简单的方法：一个个单词分割，计算长度，累计长度超过一行，则换行。这里需要解决一个分词的问题，对于英文来说一个单词是通过空格符来分割的，但是对于像中文没有明显的分割符的，可以认为一个中文字符就等同于一个单词。还有单英文字母和中文混合的时候，也需要处理这种情况的分割。这里就引出一个问题，如何识别不同类型的字符，比如是中文还是英文？答案是采用unicode编码来识别，这边主要考虑CJK（中文、日文、韩文）的情况。下面列举了不同unicode编码的范围所代表的类型

通过正则表达式，可以检测出字母是否是CJK字符，还是其他类型字符。并且可以据此来风格文本内容，对于字母文字，以一个单词来分割，对于方块字以一个字符来风格。比如：Today is 好天气，会被分割为[Today, is, 好，天，气]。在断行的时候，字母文字以单词为整体，方块字以一个个字为整体来分割。

在光标跟随的右下方，有一个隐藏起来的textarea输入框，其透明度是0，无法被点击。当编辑器聚焦的时候，其实真正浏览器的聚焦是在这个输入框里面。当键盘输入的时候，会触发输入框的输入事件：input，keydown，composition事件等等。一方面，这个输入框用来监听输入事件。另一方面，由于浏览器中没法直接控制输入法的位置，这个输入框的位置也决定了、控制着输入法的位置。

在使用输入发输入文字的时候（比如输入中文），那么会有一个中间状态（拼音的时候）展示。实现的方式是这样：首先，需要监听输入法相关的事件（CompositionEvent）。在开始、中间更新、结束三个事件中分别：

首先，整个实现还非常不完善，数据结构是线性的，难以实现像table这样的功能。其次，对于实现如此复杂的系统，让我了解到了解大致方法到落地实现之间的落差是有多大。还有，对于绝大多数的业务场景，采用L2的方式实现都是不太契合的，而使用成熟的L1的编辑器是更加好的选择，在真实的产品中，我也选择成熟的L1编辑器，而不是这种方式从0开发。这里的实现过程更多的是一种试验和学习。如果想看demo和实现源码的话我也建了个git仓库，可以多批评批评：最后，现在进入了瓶颈，很多问题还在思考如何解决，比如复杂的文字排版、树状结构节点分割合并、输入事件的优雅处理、从其他源（word等）复制黏贴、各种性能问题、实时协作、有的字符长度是2等各种边角的处理等等，每个问题都还有极大的空间深挖。需要思考学习的东西还很多啊~路漫漫，共勉之~ 希望能给看到这篇小小的文章的人带来一些启发~

【1】Charles Crowley. Data Structure For Text Sequence【2】Peng Lyu. Text Buffer Reimplementation【3】Abiword Piecetable【4】What’s different about the new Google Docs?【5】罗龙浩. 富文本编辑器的技术演进【6】Avery Laird. Text Editor: Data Structure【7】What’s been wrought using the Piece Table? 【8】Improving the AbiWord’s Piece Table