编辑器背后的数据结构

大约刚上大二的时候，想做一个编辑器控件。不是一个用Scintilla套上外壳的编辑器，而是一个能被套上外壳的控件。当然它最后也成为了我众多流产了的练手项目中的一员，不过人人黑历史里还留存着当时的一张截图

那段时间也对编辑器所使用的数据结构非常感兴趣。我们需要一种数据结构，能够支持字符串高效地索引、遍历、插入和删除。当时找的一些论文和书还躺在硬盘里一直没删，如今拿出来再嚼一嚼。下面介绍几种在编辑器中常见的数据结构。

朴素一维数组

不用说，效率比较低，几乎没有人会直接采用这种方式。把整篇文档看做一个字符串，即便我们预留了空间，也会在字符串头插入字符时暴毙。

不过，虽然这种方式无法满足需求，把它稍加改进却能够得到一个非常不错的结构。

Gap Buffer

Gap Buffer是朴素的一维数组的改进版本，它将“空白”（指字符串没有填满Buffer的部分）移动到了Buffer中间。如下图所示：

简而言之，当我们执行插入或删除动作的时候，Buffer中的空白（Gap）随之移动。例如，下面一句话中，初始情况下空白在Buffer的最后：

This is a smple txt.[        ]  

我们使用中括号[ ]来表示空白。然后当我想要在smple中插入a时，编辑器首先把空白移动到s后面：

This is a s[        ]mple txt.  

然后在s后面插入a：

This is a sa[       ]mple txt.  

如果我想在txt中插入一个e，则需要同样的步骤：

This is a sample t[       ]xt.  
This is a sample te[      ]xt.  

这种方法所基于的假设是，编辑文本时通常为连续作战，而打游击的时候并不会连续工作。

Linked Line

文本通常是一种二维结构，同时“行”这个概念在文档渲染等方面又有着不一样的意义，因此把它们单独做一层抽象也比较合理。在每一行内部，直接使用字符串或者Gap Buffer都可以。

Piece Table Buffer

Piece Table Buffer是一种效率更高的结构，但是会浪费更多的内存。Piece Table Buffer的核心思想是：在字符串末尾添加字符的代价很低（我们预留了空间），字符的移动代价很高。因此它会尽可能避免字符串的移动操作。

Piece Table Buffer由两部分Buffer组成。第一个Buffer保存的是原始的文件内容，这个Buffer是只读的。另一个Buffer用于新加入的内容，它只能进行Append操作。同时，用一张表（Piece Table）来表明当前文档的组成。例如：

Original Buf: This is a smple txt.  
Append Buf: [Empty]  

Piece Table:

首先我将smple删掉，则它们变成了：

Original Buf: This is a smple txt.  
Append Buf: [Empty]  

Piece Table:

则此时的句子为This is a txt.。随后，我在原来smple处又插入了new，则

Original Buf: This is a smple txt.  
Append Buf: new  

Piece Table:

句子就变为了This is a new txt.。

Piece Buffer的好处还在于能够比较轻松地实现Redo/Undo，不需要额外的Buffer记录修改过的字符串，因为所有编辑过的历史信息都存在两个Buffer中。

Rope

Rope是一种二叉树结构，如下图所示：

其中Rope的叶子节点存储字符串，内部节点存储叶子节点中字符串的长度。为了避免树的深度过深的问题，可以采用一定的平衡策略。

编辑器们都用了哪种数据结构？

部分Emacs使用了Gap Buffer，包括古老的 Emacs on TECO[1]、现代的GNU/Emacs[8]及其前辈Gosling Emacs[2]。Scintilla (即包括Code::Blocks在内的很多IDE/编辑器使用的代码编辑控件) 也使用了Gap Buffer。[4]

Emacs进入由Lisp实现的时代后，一些Emacs版本使用了LinkedLine[1]。

Vim使用的是一种基于行的数据结构[5]，但行与行之间不是简单地使用链表连接，而是用一种树结构进行管理[6]。

KDE的Okteta 16进制编辑器使用了Piece Table Buffer。[7] 本文开头的示例编辑器也使用了Piece Table Buffer

。

Reference

1. The Craft of Text Editing, Craig A. Finseth, 1991.
2. Data Structures in the Andrew Text Editor, Wilfred J. Hansen, 1986.
3. Data Structures for Text Sequences, CharlesCrowley, 1998.
4. Scintilla CVS CellBuffer.h
5. NeoVim Wiki Page Architectural musing and ideas
6. Vim memline.c
7. Okteta repo folder
8. GNU Emacs Lisp Reference Manual