Rope & SumTree (绳索 & SumTree)

在 Zed 解码系列博客的第二篇文章中，我们将更深入地了解 Zed 的构建方式。我与 Zed 的三位联合创始人 —— Nathan, Max, Antonio 讨论了 Zed 核心的数据结构：绳索 (rope)。

配套视频

Rope & SumTree (绳索 & SumTree)

这篇文章配有一个 1 小时的配套视频，Thorsten、Nathan、Antonio 和 Max 使用 Zed 来研究 Zed 如何使用 Rope 和 SumTree 类型。这是一次轻松的对话，我们编写和阅读了大量代码，以了解 Zed 中的绳索是如何工作和实现的。

在此观看视频 →

我事先知道文本编辑器圈子对表示文本的数据结构非常感兴趣。我也在 Zed 代码库中使用过 Rope 类型，并且对绳索略知一二。

我真正不明白的是 Zed 的绳索是如何实现的，以及这种实现实现了什么。所以我问了 Nathan, Max, 和 Antonio。他们多年来一直在绳索之上、之下和内部编写代码。而且，事实证明，Zed 的绳索实际上并不是绳索，至少在经典意义上不是。它非常令人印象深刻，但首先：什么是绳索？

为什么不用字符串？

文本编辑器必须做的最重要的事情之一就是在内存中表示文本。当你在文本编辑器中打开一个文件时，你希望看到它的内容并想在其中导航，并且 —— 嘿，这就是名称的由来 —— 你也想编辑文本。

为此，文本编辑器必须将文件内容加载到内存中 —— 你不能只是让用户盯着磁盘上的原始字节。你还希望将其保存在内存中，因为并非每次更改都应立即保存到磁盘。

所以问题是：如何在内存中表示文本？

我最初的幼稚选择是使用字符串。老式的字符串。我们开始编程时的最好的朋友。为什么不用字符串？我们一直都在内存中用它来表示文本。直接地说，这似乎不是一个糟糕的选择，对吧？

嘿，我敢打赌你可以用字符串走很远，但是字符串存在一些问题，阻止它们成为最佳选择，特别是当你开始处理大文件并希望你的程序仍然高效和响应迅速时。

字符串的问题

字符串通常被分配为连续的内存块。这会使编辑效率低下。假设你有一个包含 2 万行文本的字符串文件，并且你想在该字符串的中间插入一个单词。为了做到这一点，你必须为字符串中间的新单词腾出空间，以便你仍然得到一个作为连续内存块的字符串。为了腾出空间，你必须移动所有在新插入的单词之后的所有文本。这里的移动实际上意味着进行分配。在最坏的情况下，你必须移动所有内容 —— 所有 2 万行 —— 才能为你的新单词腾出空间。

或者假设你想删除一个单词：你不能只是在字符串中打一个洞，因为那意味着它不再是一个字符串 —— 一个连续的内存块。相反，你必须移动所有字符，除了你删除的那些字符，以便你最终再次得到一个单一的、连续的内存块，这次没有删除的单词。

在处理小文件和小字符串时，这些都不是问题。我们每天都在进行类似的字符串操作，对吧？是的，但大多数时候我们谈论的是相对较小的字符串。当你处理大文件，因此是大字符串或大量编辑（甚至同时进行 —— 你好，多光标！）时，这些事情 —— 分配、在内存中移动字符串 —— 就会成为问题。

这甚至没有涉及到文本编辑器可能对其文本表示的所有其他要求。

例如，导航。如果用户想要跳转到第 523 行怎么办？使用字符串并且没有任何其他数据，你必须遍历字符串，一个字符一个字符地遍历，并计算其中的换行符，以找出字符串中第 523 行的位置。然后，如果用户按下向下箭头十次以向下移动十行并想要最终停留在同一列中怎么办？你将再次必须开始计算字符串中的换行符，然后找到最后一个换行符之后的正确偏移量。

或者，假设你想要在编辑器的底部绘制一个水平滚动条。要了解滚动滑块必须有多大，你必须知道文件中最长行的长度。同样的事情再次发生：你必须遍历字符串并计算行数，这次还要跟踪每行的长度。

或者，如果你想加载到编辑器中的文本文件大于 1GB，并且你用来实现文本编辑器的语言 只能表示最大 1GB 的字符串 怎么办？你可能会说“1GB 的字符串对每个人来说都足够了”，但这只告诉我你还没有与足够的文本编辑器用户交谈过。

撇开玩笑不谈，我认为我们已经确定字符串可能不是表示文本编辑器的最佳解决方案。

那么我们还能用什么呢？

什么比字符串更好？

如果你真的很喜欢字符串，你现在可能会想“比字符串更好？简单：多个字符串。” 你并没有错得离谱！一些编辑器确实将文本表示为行数组，每行都是一个字符串。VS Code 的 Monaco 编辑器曾经就是这样工作的，但是字符串数组仍然会受到与单个字符串相同的问题的困扰。过多的内存消耗和性能问题使 VS Code 团队寻找更好的东西。

幸运的是，有一些比字符串更好的东西。文本编辑器的构建者早就意识到字符串不是这项工作的最佳工具，并且提出了其他数据结构来表示文本。

据我所知，最流行的是间隙缓冲区（gap buffers）、片表（piece tables）和绳（ropes）。

它们各有优缺点，我在这里不详细比较它们。 知道它们都比字符串好得多就足够了，不同的编辑器根据不同的权衡做出了不同的决定，最终选择了不同的数据结构。 举个例子：Emacs 使用间隙缓冲区，VS Code 使用了片表的变体，Vim 有自己的树形数据结构，而 Helix 使用绳。

Zed 也使用绳。 让我们看看绳相对于字符串有什么优势。

绳

以下是维基百科对绳的解释

绳是一种二叉树，其中每个叶子（末端节点）都包含一个字符串和一个长度（也称为“权重”），并且树中每个更靠上的节点都包含其左子树中所有叶子的长度总和。

绳不是连续的内存块，而是一棵树，其叶子是它所代表的文本的字符。

文本 "This is a rope" 在绳中看起来是这样的

你现在可能认为这比字符串复杂得多，你是对的——确实如此。 但这是至关重要的一点，它使得绳在许多情况下胜过字符串：叶子 - "This", " is ", "a ", "rope" — 基本上是不可变的。 您修改树而不是修改字符串。 您修改树以获得一个新字符串，而不是在字符串上戳孔并在内存中移动它的各个部分。 到目前为止，我们作为程序员已经弄清楚了如何有效地使用树。

让我们再次使用上面的例子：删除文本中某个位置的单词。 使用字符串，您必须重新分配该单词后面的所有文本，可能包括整个字符串。 对于绳，您找到要删除的单词的开始和结束位置，然后在这两个位置拆分树，这样您就有四棵树，您丢弃中间的两棵树（仅包含已删除的单词），连接另外两棵树，然后重新平衡树。 是的，这听起来确实很多，并且确实需要在幕后进行一些算法上的改进，但是与字符串相比，内存和性能的提升非常真实：您只需要更新几个指针，而不是在内存中移动东西。 对于像 "This is a rope" 这么短的文本来说，这看起来可能很傻，但是当您有非常大的文本时，它会带来巨大的回报。

我知道这很抽象，所以让我给你展示一下。 让我们看看 Zed 的绳实现。

Zed 的绳实现

Zed 在自己的 crate 中有自己的绳实现：rope。（Zed 拥有自己的实现而不是使用库的原因之一是，当 Zed 创始人在 2017 年为 Zed 奠定基础时，很多库都不存在。）

rope crate 中的主要类型是 Rope。 这是你如何使用它的

let mut rope = Rope::new();
rope.push("Hello World! This is your captain speaking.");

到目前为止，与 String 非常相似。 现在假设我们有两条绳子

let mut rope1 = Rope::new();
rope1.push("Hello World!");
 
let mut rope2 = Rope::new();
rope2.push("This is your captain speaking.");

如果我们想连接它们，我们所要做的就是这样

rope1.append(rope2);
 
assert_eq!(
    rope1.text(),
    "Hello World! This is your captain speaking.".to_string()
);

调用 rope1.append 通过构建一个包含两者的新树来连接两棵树—— rope1 和 rope2。 这仅仅是更新几个指针。 将其与字符串进行比较：如果连接两个字符串，则必须在内存中移动至少一个字符串，以便它们最终相邻，形成一个连续的块。 通常你必须移动它们两个，因为第一个字符串后面没有足够的空间。 再次说明：此示例中的文本非常短，但是如果有人想在一个文件中拥有十份 25k 行的 SQLite 整合 怎么办？

替换一个词怎么样？

// Construct a rope
let mut rope = Rope::new();
rope.push("One coffee, please. Black, yes.");
 
// Replace characters 4 to 10 (0-indexed) with "guinness".
rope.replace(4..10, "guinness");
assert_eq!(rope.text(), "One guinness, please. Black, yes.");

幕后发生了什么

• replace() 创建一条新绳，其中包含原始 rope 的所有节点，直到第 5 个字符 (c)
• 新文本 guinness 被追加到新绳
• 原始 rope 的其余部分，即字符 11 之后的所有内容，都追加到新绳

删除一个词？ 只需将其替换为 ""

let mut rope = Rope::new();
rope.push("One coffee, please. Black, yes.");
rope.replace(4..10, "");

即使处理大量文本，这些操作也非常快，因为那时树中的大多数节点都可以被重用，并且只需要重新连接。

但是被删除的词 "coffee" 会发生什么？ 只要没有其他节点再引用它们，包含这些字符的叶子节点就会被自动清理。 这就是绳中不可变的叶子节点所启用的：当一条绳被改变，或者从旧的绳构造出一条新的绳，或者两条绳被合并成一条新的绳时，基本上所有改变的都是对叶子节点的引用。 这些引用会被计数：一旦不再有对节点的引用，该节点就会被清理，解除分配。

确切地说，从技术上讲：在 Zed 的绳实现中，包含实际文本的叶子节点并不是完全不可变的。 这些叶子节点有一个最大长度，并且如果，比如说，文本被追加到一条绳上，并且新文本足够短，可以放入最后一个叶子节点而不超过其最大长度，那么该叶子节点将被改变，并且文本将被追加到它上面。

但从概念层面上讲，您可以将绳视为持久数据结构，将其节点视为树中引用计数的不可变节点。 这使其成为比字符串更好的选择，并将我们带回到我们上面跳过的问题：为什么 Zed 选择绳而不是其他数据结构之一？

为什么在 Zed 中使用绳？

Zed 的目标是成为高性能代码编辑器。 正如我们所见，字符串不会让你达到高性能。 那么你应该使用什么代替呢？ 间隙缓冲区、绳、片表？

这里没有一个明显的最佳选择。 这完全取决于您愿意为满足这些要求而做出的具体要求和权衡。

也许你听说过间隔缓冲区可能比绳子更快，或者更容易理解，或者分片表更优雅。这些可能是真的，但是这并不意味着它们明显优于绳子。 这是ropey（Rust 中流行的绳子实现）的作者写的关于绳子和间隔缓冲区之间的性能权衡：

绳子在性能上做出了不同的权衡，有点像“万金油”。它们在任何方面都不是最好的，但始终保持着稳定的 O(log N) 性能。对于只支持本地编辑模式的编辑器来说，它们不是最佳选择，因为在这种情况下，与间隔缓冲区相比，它们牺牲了很多性能（即使对于巨大的文档也是如此）。但是，对于鼓励非本地化编辑，或者只是想要在这方面具有灵活性的编辑器来说，它们是一个不错的选择，因为它们始终具有良好的性能，而间隔缓冲区在不利的编辑模式下性能会急剧下降。

绳子“在任何方面都不是最好的，但始终保持着稳定的良好性能”。这取决于你想做什么，或者你希望你的编辑器能够做什么。

那么，如果你真的想利用 CPU 中的所有核心呢？ 在“文本对决：间隔缓冲区 vs 绳子”的末尾有一段提到了并发

绳子除了良好的性能之外，还有其他好处。Crop 和 Ropey [注意：两者都是 Rust 中的绳子实现] 都支持来自多个线程的并发访问。这使您可以进行快照以进行异步保存、备份或多用户编辑。这对于间隔缓冲区来说不容易做到。

在配套视频中，您可以听到 Max 对这段话的评价：“是的，它比其他任何东西都重要。” Nathan 补充说“我们到处都在使用它”，这里的“它”指的是并发访问、快照、多用户编辑、异步操作。

换句话说：对缓冲区中的文本进行并发访问是 Zed 的一个硬性要求，这就是为什么绳子最终成为首选。

以下是并发访问文本在 Zed 中根深蒂固的一个例子：当您在启用了语法高亮的 Zed 中编辑缓冲区时，缓冲区的文本内容的快照会被发送到后台线程，并在其中使用 Tree-sitter重新解析。这发生在每次编辑时，并且非常、非常快速和高效，因为快照不需要文本的完整副本。 所需要的只是增加一个引用计数，因为 Zed 的绳子中节点的引用计数是用Arc（Rust 的“线程安全引用计数指针”）实现的。

这就引出了最重要的一点：Zed 的绳子是如何实现的。因为它不是像你在维基百科上看到的那种经典绳子那样实现的，并且它的实现赋予了 Zed 的绳子某些其他绳子实现可能不具备的属性，而且这种实现实际上使绳子优于其他数据结构。

它不是绳子，而是一个 SumTree

Zed 的绳子不是经典的二叉树绳子，它是一个 SumTree。 如果你打开 Zed 的 Rope 的定义，你会发现它只不过是一个 Chunk 的 SumTree

struct Rope {
    chunks: SumTree<Chunk>,
}
 
struct Chunk(ArrayString<{ 2 * CHUNK_BASE }>);

Chunk 是一个 ArrayString，它来自 arrayvec crate，允许将字符串内联存储，而不是存储在其他地方的堆上。这意味着：Chunk 是字符的集合。Chunk 是 SumTree 中的叶子，最多包含 2 * CHUNK_BASE 个字符。在 Zed 的发布版本中，CHUNK_BASE 是 64。

那么什么是 SumTree 呢？ 问问 Nathan，他会说 SumTree 是“Zed 的灵魂”。但对 SumTree 更技术性的描述是这样的：

SumTree<T> 是一个 B+ 树，其中每个叶子节点包含多个类型为 T 的项，以及每个 Item 的 Summary。内部节点包含其子树中各项的 Summary。

这是类型定义，你可以在 sum_tree crate 中找到它们

struct SumTree<T: Item>(pub Arc<Node<T>>);
 
enum Node<T: Item> {
    Internal {
        height: u8,
        summary: T::Summary,
        child_summaries: ArrayVec<T::Summary, { 2 * TREE_BASE }>,
        child_trees: ArrayVec<SumTree<T>, { 2 * TREE_BASE }>,
    },
    Leaf {
        summary: T::Summary,
        items: ArrayVec<T, { 2 * TREE_BASE }>,
        item_summaries: ArrayVec<T::Summary, { 2 * TREE_BASE }>,
    },
}
trait Item: Clone {
    type Summary: Summary;
 
    fn summary(&self) -> Self::Summary;
}

那么什么是 Summary？ 任何你想的东西！ 唯一的要求是你需要能够将多个摘要加在一起，以创建一个摘要的和

trait Summary: Default + Clone + fmt::Debug {
    type Context;
 
    fn add_summary(&mut self, summary: &Self, cx: &Self::Context);
}

但我知道你刚才对此嗤之以鼻，所以让我们让它更具体。

由于 Rope 是一个 SumTree，并且 SumTree 中的每个项都必须有一个摘要，所以这是与 Zed 的 Rope 中的每个节点关联的 Summary

struct TextSummary {
    /// Length in UTF-8
    len: usize,
    /// Length in UTF-16 code units
    len_utf16: OffsetUtf16,
    /// A point representing the number of lines and the length of the last line
    lines: Point,
    /// How many `char`s are in the first line
    first_line_chars: u32,
    /// How many `char`s are in the last line
    last_line_chars: u32,
    /// How many UTF-16 code units are in the last line
    last_line_len_utf16: u32,
    /// The row idx of the longest row
    longest_row: u32,
    /// How many `char`s are in the longest row
    longest_row_chars: u32,
}

SumTree 中的所有节点——内部节点和叶子节点——都有这样一个摘要，其中包含关于其子树的信息。叶子节点有它们 Chunk 的摘要，而内部节点有一个摘要，该摘要是*其子节点的摘要的总和*，递归向下到树。

假设我们有以下文本

Hello World!
This is
your captain speaking.
Are you
ready for take-off?

5 行文本。 如果这被推送到 Zed Rope 中，则 Rope 下方的 SumTree 将如下所示，简化

（我省略了 TextSummary 的一些字段，以使图表保持较小，并且还调整了块的最大大小和每个节点的最大子节点数。 在 Zed 的发布版本中，文本的所有五行都将适合单个节点。）

即使只有三个摘要字段—— len, lines, longest_row_chars ——我们可以看到内部节点的摘要是其子节点摘要的总和。

根节点的摘要告诉我们关于完整文本的信息，完整的 Rope：72 个字符，5 行，最长的一行有 22 个字符（your captain speaking.\n）。内部节点告诉我们关于文本各个部分的信息。例如，这里的左侧内部节点告诉我们，从 "Hell" 到 "spea" 有 38 个字符（包括换行符），并且文本的该部分中有两个换行符。

好的，你可能在想，一个带有总结的 B+ 树 —— 这能给我们带来什么好处呢？

遍历 SumTree

SumTree 是一个并发友好的 B 树，它不仅为我们提供了一个持久的、写时复制的数据结构来表示文本，而且通过它的摘要，它还索引树中的数据，并允许我们以 O(log n) 的时间复杂度沿着摘要的维度遍历树。

用 Max 的话说，SumTree “在概念上不是一个映射。它更像一个 Vec，它具有这些特殊的索引功能，你可以在其中存储任何你想要的条目序列。你决定顺序，它只是提供这些搜索和切片的功能。”

不要把它看作是一个允许你查找与键关联的值的树（虽然它可以做到），而是把它看作是一个允许你根据每个条目及其之前所有条目的摘要来查找条目的树。

或者，换句话说：SumTree 中的条目是有序的。它们的摘要也是有序的。SumTree 允许你在 O(log N) 的时间内找到树中的任何条目，方法是从根节点到叶节点遍历树，并根据节点的摘要决定要访问哪个节点。

假设我们有一个包含三行文本的 Rope

let mut rope = Rope::new();
rope.push("Line one.\n");
rope.push("This is the second line.\n");
rope.push("This is three.\n");

一旦构建了 Rope，它看起来像这样

就像我们上面说的那样：每个叶节点将包含多个 Chunk，并且每个叶节点的摘要将包含关于其 Chunk 中的文本的信息。该摘要的类型是上面提到的 TextSummary。这意味着每个节点的摘要可以告诉我们关于其块中文本的 len、其中的行和列、最长行以及 TextSummary 的所有其他字段。然后，SumTree 中的内部节点包含摘要的摘要。

并且由于树中的条目 —— 内部节点、叶节点、块 —— 是有序的，我们可以非常高效地遍历该树，因为 SumTree 允许我们基于摘要中的值遍历树。它允许我们沿着单个维度，例如给定摘要的单个字段进行搜索。

假设我们想找出 rope 中绝对偏移量 26 处的行和列是什么。意思是：字符 26 处是什么？为了找出答案，我们可以沿着 TextSummary 的 len 字段遍历这个三行的 rope。因为从左到右加起来的 len 字段就是一个绝对偏移量。因此，为了找到绝对偏移量 26 处的内容，我们向下遍历树，根据内部节点摘要中的 len 值向左或向右转，直到我们到达我们想要的叶节点

let point = rope.offset_to_point(26);
assert_eq!(point.row, 1);
assert_eq!(point.column, 16);

表面上，调用 rope.offset_to_point(26) 将绝对的、基于 0 的偏移量 (26) 转换为行和列 (1 和 16)。offset_to_point 内部发生的事情是，光标遍历 SumTree，直到找到聚合的 TextSummary 的 len 变为 >= 26 的条目。一旦找到第一个满足条件的叶节点，它就会找到偏移量匹配的确切块，并将光标停在那里。在到达那里的过程中，它不仅一直在计算它遇到的摘要的 len 字段，而且还聚合了 lines 字段，其中包含 row 和 column。很巧妙，对吧？

这是我刚刚描述的内容的实际代码，这是 Rope 上的 offset_to_point 方法

fn offset_to_point(&self, offset: usize) -> Point {
    if offset >= self.summary().len {
        return self.summary().lines;
    }
    let mut cursor = self.chunks.cursor::<(usize, Point)>();
    cursor.seek(&offset, Bias::Left, &());
    let overshoot = offset - cursor.start().0;
    cursor.start().1
        + cursor
            .item()
            .map_or(Point::zero(), |chunk| chunk.offset_to_point(overshoot))
}

它所做的是以下内容

• 进行健全性检查，确保偏移量没有超过整个 Rope 的末尾
• 创建一个光标，沿着 usize（偏移量）和 Point（Point 是一个包含两个字段的结构体：row 和 column）维度进行搜索，同时聚合两者
• 一旦找到 offset 处的项目，它会计算超调量：我们正在寻找的 offset 可能位于单个块的中间，并且 cursor.start().0 是给定块开始处的 usize（偏移量）
• 获取到当前块开始处的行（cursor.start().1）—— 这是当前条目左侧的完整树的 TextSummary.len 的摘要！
• 将它们添加到块的可能中间的偏移量处的行（chunk.offset_to_point(overshoot)）

这里最有趣的部分当然是用 self.chunks.cursor::<(usize, Point)>() 构造的光标。这个特殊的光标有两个维度，允许你在给定的 SumTree 中搜索一个维度 (usize) 上的值，并在相同的操作中获得第二个维度，Point，在特定光标位置的总和。

这样做的好处是，它可以在 O(log N) 的时间内完成，因为每个内部节点都包含摘要的摘要（意思是：在这种情况下，其子树中所有项目的总 len），并且它可以跳过所有 len < 26 的节点。在上面的图中，你可以看到我们甚至不必遍历前两个叶节点。

是不是很棒？还有更多。

使用 SumTree

您还可以反向遍历 SumTree，沿着行/列查找并获得最终偏移量

// Go from offset to point:
let point = rope.offset_to_point(55);
assert_eq!(point.row, 2);
assert_eq!(point.column, 6);
 
// Go from point to offset:
let offset = rope.point_to_offset(Point::new(2, 6));
assert_eq!(offset, 55);

并且——您可能已经猜到了——point_to_offset 看起来完全像 offset_to_point，除了构造光标的维度被翻转了

fn point_to_offset(&self, point: Point) -> usize {
    if point >= self.summary().lines {
        return self.summary().len;
    }
    let mut cursor = self.chunks.cursor::<(Point, usize)>();
    cursor.seek(&point, Bias::Left, &());
    let overshoot = point - cursor.start().0;
    cursor.start().1
        + cursor
            .item()
            .map_or(0, |chunk| chunk.point_to_offset(overshoot))
}

这种沿着一个维度查找并在多个维度上聚合（汇总！）的能力，是通过一些非常巧妙的 Rust 代码实现的，我不会详细解释，但简而言之是这样。

给定一个像下面这样的 TextSummary（我们已经在上面完整地看到了）和一个包装它的 ChunkSummary...

struct TextSummary {
    len: usize,
    lines: Point,
 
    // [...]
}
 
struct ChunkSummary {
    text: TextSummary,
}

...我们可以将 len 和 lines 字段定义为 sum_tree::Dimensions

impl<'a> sum_tree::Dimension<'a, ChunkSummary> for usize {
    fn add_summary(&mut self, summary: &'a ChunkSummary, _: &()) {
        *self += summary.text.len;
    }
}
 
impl<'a> sum_tree::Dimension<'a, ChunkSummary> for Point {
    fn add_summary(&mut self, summary: &'a ChunkSummary, _: &()) {
        *self += summary.text.lines;
    }
}

然后我们可以构造给定 sum_tree::Dimension 或 _维度元组_ 的光标（这就是我们上面用 (usize, Point) 所做的事情）。

构造完成后，光标可以沿着我们定义的任何 Dimension 查找，并聚合完整的 TextSummary 或给定摘要类型的单个 Dimension。

或者，我们也可以沿着单个维度查找，然后在光标找到目标后获取整个摘要

let mut rope = Rope::new();
rope.push("This is the first line.\n");
rope.push("This is the second line.\n");
rope.push("This is the third line.\n");
 
// Construct cursor:
let mut cursor = rope.cursor(0);
// Seek it to offset 55 and get the `TextSummary` at that offset:
let summary = cursor.summary::<TextSummary>(55);
assert_eq!(summary.len, 55);
assert_eq!(summary.lines, Point::new(2, 6));
assert_eq!(summary.longest_row_chars, 24);

光标停在第 2 行的中间，第 6 列，并且直到该位置，摘要中的 longest_row_chars 为 24。

这非常非常强大。 简单来说：它允许我们轻松地在 UTF8 行/列和 UTF16 行/列之间进行转换，这在使用语言服务器协议 (LSP) 时有时是必需的。只需查找 UTF8 Point 并聚合 UTF16 Points

fn point_to_point_utf16(&self, point: Point) -> PointUtf16 {
    if point >= self.summary().lines {
        return self.summary().lines_utf16();
    }
    let mut cursor = self.chunks.cursor::<(Point, PointUtf16)>();
    cursor.seek(&point, Bias::Left, &());
    // ... you know the rest ...
}

但还有更多，我可以继续讲下去，展示更多示例，或者使用 幺半群同态 之类的大词，但我将在这里停止。你明白了——SumTree，一个线程安全、快照友好、写时复制的 B+ 树非常强大，可以用于“仅仅”文本以外的更多用途，这就是为什么它在 Zed 中无处不在。是的，确实如此。

一切皆是 SumTree

目前，Zed 中有超过 20 处使用了 SumTree。SumTree 不仅用作 Rope 的基础，而且在许多不同的地方。项目中的文件列表是一个 SumTree。git blame 返回的信息存储在 SumTree 中。聊天频道中的消息：SumTree。诊断信息：SumTree。

在 Zed 的最核心，是一个名为 DisplayMap 的数据结构，它包含关于如何显示给定文本缓冲区的所有信息——折叠的位置、换行的行、嵌入提示的显示位置……——它看起来像这样

struct DisplayMap {
    /// The buffer that we are displaying.
    buffer: Model<MultiBuffer>,
    /// Decides where the [`Inlay`]s should be displayed.
    inlay_map: InlayMap,
    /// Decides where the fold indicators should be and tracks parts of a source file that are currently folded.
    fold_map: FoldMap,
    /// Keeps track of hard tabs in a buffer.
    tab_map: TabMap,
    /// Handles soft wrapping.
    wrap_map: Model<WrapMap>,
    /// Tracks custom blocks such as diagnostics that should be displayed within buffer.
    block_map: BlockMap,
    /// Regions of text that should be highlighted.
    text_highlights: TextHighlights,
    /// Regions of inlays that should be highlighted.
    inlay_highlights: InlayHighlights,
 
    // [...]
}

猜猜怎么着？ 所有这些都在底层使用了 SumTree，在以后的文章中我们将探讨它们，但现在我想表达的观点是这个

Zed 的联合创始人并没有决定在 gap buffer 或 piece table 之上使用 rope。他们从 SumTree 开始，认识到它是多么强大，它如何满足 Zed 的要求，然后在它之上构建了 rope。

rope 可能位于 Zed 的核心，但 SumTree 就像 Nathan 再次引用的那样，“是 Zed 的灵魂”。