编译器笔记：rope

在实现 paradoxical 的时候注意到很多语言服务器或者编辑器都会使用一个叫作 rope 的东西来保存对文件的操作结果，因此简单记录下这个神奇的东西。

rope 这个概念最开始是在 1995 年由 Hans-J. Boehm 、 Russ Atkinson 和 Michael Plass 提出的^[0]。如果你想简单了解的话，你可以直接去看 xi-editor 的相关文档^[1]，写得非常不错

十分感谢他们的贡献 :)

简单介绍

Rope （绳索字符串）就是把一整段文本切成许多小块，用一棵树把这些块串起来；这样随机插入、删除或定位位置时，只需改动或遍历对数级别的节点，而不是线性扫描整段文本。

请注意，而不是线性扫描整段文本这段话非常重要，这也是和使用 String 储存文件内容的最大区别

操作？

对于一个编辑器或者文本解析，我们常常使用行列的概念来操作他。

答案是，对于 rope 我们也可以使用行列来操作他！

为什么 rope 可以实现高效编辑

请注意，rope 的主要目的是实现高效的编辑，对于读取他的速度和线性的 String 相比是略微慢了一点点的。

但就这个数量级是常数，非常不明显

从储存结构上优化

rope 最重要的一点是，他不是线性储存文本数据，转而使用了一棵树来维护储存文本数据。

让我们来看看这棵树长什么样子

       ┌─── weight = 23 ───┐
       │                   │
   [左子树]            [右子树]
  weight = 10         weight = 7
  │       │            │       │
"片段A" "片段B..."  "片段C" "片段D..."

简单解释就是：

• 左子树(LeftSubtree)：按照逻辑顺序（即文本顺序）排在当前节点之前的全部内容
• 右子树(RightSubtree)：排在当前节点（或其左子树）之后、紧接着的那部分内容

请注意，节点内储存的权重不仅仅只有字符数，也包含行数等信息

在接下来我们定义权重分为以下几种

• lines: 行权重
• chars: 字符权重

偏移

当我们需要快速定位光标的时候，权重就显得非常重要了：它保存了左子树累计长度，若要找第 \(k\) 个字符，算法会看 \(k\) 是否小于该权重，按照如下逻辑来搜索：

• 是 : 目标一定在左子树。
• 否 : 目标必定在右子树，并将 \(k\) 减去左权重后继续向下搜索。

除此之外我们还有行列偏移的需求：我们在编辑时经常需要行列->偏移，或者偏移->行列，那么 rope 是怎么做的？

行列->偏移

1. 输入行号 \(L\)；从根节点开始。
2. 比较 \(L\) 与当前节点的 左子树行数：
   1. 若 \(L\) 小于该权重，进入左子树；
   2. 否则 \(L = L - left\_lines\)，转入右子树。

重复直到到达叶节点（叶片约 4–8 KB 大小）。在叶内部用已缓存的换行表（二分搜索）把剩余行数定位到字节/字符位置。

通过这样的设计，这棵树就把线性扫描的复杂度降低到了 \(O(logN)\)

偏移->行列

从偏移转换到行列也是个很常见的需求，不过这种转换相比行列转换为偏移更加简单

1. 将目标字符索引 \(K\) 与字符权重做同样的左/右子树递归
2. 到叶后用换行表计算它之前的换行符数量，加上在路径中累积的 \(left\_lines\) 即得行号。

换行符数量也是可以作为缓存项的，所以这种操作依然非常快速

对 CPU 缓存的充分利用

上文提到，叶片的大小一般是 4-8KB，这样的大小有利于 CPU 缓存。

基于 CPU 的缓存机制，我们可以使用链表或者其他顺序结构将叶子之间链接起来，在遍历的时候就不需要重走整棵树。

关于为什么这样的大小可以更好的利用 CPU 缓存，本文不做叙述

简答地讲，对于遍历文件内容的本身的时候有如下优化手段

• 利用链表链接所有叶子节点，在遍历的时候通过链表对叶子节点进行遍历而不是通过爬树来执行访问
• 利用 CPU 会预缓存内存内容的特性使得访问内存的频率减少，降低遍历时使用其他结构因为 miss 的原因访问内存

这样既得到了廉价的编辑行为也获得了不俗的遍历性能，代价即为直接读取内容稍慢而已

插入删除等局部更新

在刚刚提到了读取操作，以上的解释注重于解释为什么 rope 在读取方面依然性能十分出众但并没有解释为什么 rope 在编辑方面的性能远大于使用 String [u8] 等线性数据结构

定位

对于定位，请看 偏移

操作

在到达指定位置后就可以执行对叶片的操作了。对于叶片的操作核心在于需要合适的时机分裂叶片使其成为新的叶片并且添加新的节点

先将光标内的内容插入到这个叶片的缓冲区里，然后做如下判断

• 如果叶片大于 4-8KB：叶片将会分裂成为两个（或者多个）新的叶片
  • 在完成分裂后对叶片添加新的父节点
• 如果叶片小于 4-8KB：正常插入即可

在完成插入操作后需要回溯所有祖先节点并且完成对祖先节点的权重变更，这样就完成了插入操作

在正常编辑下（只添加一个字符）最多只需要触摸 2 个叶片和 \(O(logN)\) 个节点，在特殊情况下（例如剪切板粘贴）会有更复杂的操作，暂且不提（简单讲就是对粘贴内容生成 rope 树并且将树挂载到指定位置上）

xi-editor 和 ropey在这方面实现上有区别，不介绍两个实现上所使用的树的具体区别

---

1. 0.Ropes: an Alternative to Strings ↩︎
2. 1.xi-editor ↩︎