Piece Table —— 文本编辑器中默默无闻的英雄

# 片段表——你文本编辑器里默默无闻的英雄 来源：https://dev.to/_darrenburns/the-piece-table---the-unsung-hero-of-your-text-editor-al8 片段表是一种默默无闻的数据结构，它支撑着我们今天对文本编辑器所期望的许多功能和性能特性。Visual Studio Code 就使用了它。早在 1984 年，Microsoft Word 2.0 就已经采用了这种结构。 尽管它几乎是现代文本编辑器的标配，但关于它的文档却相对匮乏。在这篇文章中，我将解释片段表的结构、它被广泛使用的原因，以及你在编辑文件时，文本编辑器是如何与它交互的。 我的目标是让这篇文章尽可能对新手友好，所以我们会一步步地讲解每个概念。不过，在继续阅读之前，你最好对数组、字符串和对象（或者说字典/结构体）有基本的了解。 --- 当你在文本编辑器中打开一个文件时，文件内容会从磁盘读取到内存中的某个数据结构里。如果你要自己写一个文本编辑器，你会如何将打开的文件存储在内存中呢？ ## 第一直觉：字符串数组 我们的第一直觉可能是使用一个字符串数组，每个字符串代表文件中的一行。换句话说，我们会把这个文件…… ``` the quick brown fox jumped over the lazy dog ``` ……表示为： ```python lines = [ "the quick brown fox", # 文件的第一行 "jumped over the lazy dog", # 文件的第二行 ] ``` 这是一种直观的内存表示方式，它让我们能以类似文本编辑器屏幕显示的方式来思考文件。 这也是一种完全可接受的方法，你甚至可以说它的直观性胜过任何潜在缺陷。实际上，Visual Studio Code 在 2018 年早期之前也使用过类似的模型。 不幸的是，当处理大文件时，这种方法会变得代价高昂。设想一下，如果有人在文件中间插入一行新文本（如 `"went to the park and"`）： ``` the quick brown fox went to the park and jumped over the lazy dog ``` 为了给新行腾出空间，数组中所有位于它下面的行都需要在内存中向后移动。对于大文件来说，这很快就会变得非常昂贵——文件越大，需要移动的数据就越多。  这只是这种方法的一个缺点。在这篇由 Visual Studio Code 团队撰写的[精彩博文](https://code.visualstudio.com/blogs/2018/03/23/text-buffer-reimplementation#_piece-tree)中，他们指出了其他缺陷，比如内存使用过多，以及由于按换行符将文件拆分成多个字符串而导致的性能问题。 ## 一种仅追加的表示方式 如果我们向数组末尾追加元素，不需要移动任何数据来腾出空间，因此不会像中间插入那样产生性能损失（更技术地说，追加数组的时间复杂度是 O(1)，而插入是 O(n)）。 **片段表**正是许多新旧文本编辑器背后强大的数据结构。它的一个关键特性是：它以仅追加的方式记录我们对文件进行的所有插入操作。 让我们来探索片段表的工作原理。 当我们从磁盘读取文件到片段表中时，文件中的文本会被存储在一个永不修改的字符串中。我们称这个字符串为**原始缓冲区**。 ```python piece_table = { "original": "the quick brown fox\njumped over the lazy dog", ... } ``` 当我们在编辑器中向文件添加文本时，这些文本会被追加到片段表的**添加缓冲区**中，该缓冲区初始时只是一个空字符串。 在文件顶部添加版权声明？追加到添加缓冲区。在文件中间添加一个新函数？追加到添加缓冲区。在文件末尾添加一个换行？还是追加到添加缓冲区！ 添加缓冲区是构成片段表的两个缓冲区中的第二个，并且它也是仅追加的。 ```python { "original": "the quick brown fox\njumped over the lazy dog", "add": "", ... } ``` 通过将所有插入到文件中的文本都追加到添加缓冲区，我们记录了用户在编辑器中输入的内容，同时避免了前面提到的中间插入问题。 让我们再次打开假设的文本编辑器，像之前一样在文件中间插入一行。这样片段表就变成了： ```python { "original": "the quick brown fox\njumped over the lazy dog", "add": "went to the park and\n", ... } ``` 我们插入到文件中间的文本现在位于添加缓冲区中。原始缓冲区始终保持不变（而且永远不会变）。 这两个字符串 `original` 和 `add` 包含了编辑器中打开的文件的所有内容，以及自文件打开以来所有曾经存在过的内容。 当编辑器显示一个打开的文件时，它会将这两个字符串的不同部分组合起来，形成你在屏幕上看到的内容。如果某些文本不再存在于文件中（例如用户删除了部分内容），那么这些字符串的相应部分可能会被忽略。 在下面的文本中，中间部分来自添加缓冲区（因为它被插入），其余部分来自原始缓冲区（因为它们是原始文件的一部分）。  目前，我们的假设编辑器知道用户插入了字符串 `"went to the park and\n"`，但不知道插入的**位置**。片段表中还没有足够的信息供编辑器正确显示文件内容。缺失的拼图（双关语）就是：需要跟踪用户是在文档的哪个位置插入的文本。 ## 片段描述符 为了知道用户插入文本的位置，片段表需要跟踪文件的哪些部分来自 `original` 缓冲区，哪些部分来自 `add` 缓冲区。它通过遍历一个**片段描述符**列表来实现这一点。一个片段描述符包含三个信息： - `source`：指示从哪个缓冲区读取。 - `start`：指示从该缓冲区的哪个索引开始读取。 - `length`：指示从该缓冲区读取多少个字符。 当我们第一次在编辑器中打开一个文件时，只有 `original` 缓冲区有内容，并且有一个单独的片段描述符告诉编辑器完全从 `original` 缓冲区读取。`add` 缓冲区是空的，因为我们还没有向文件添加任何文本。 ```python { "original": "the quick brown fox\njumped over the lazy dog", "add": "", "pieces": [Piece(start=0, length=44, source="original")], } ``` ## 向文件添加文本 现在，我们像之前一样在文件中间添加相同的文本。片段表更新如下： ```python { "original": "the quick brown fox\njumped over the lazy dog", "add": "went to the park and\n", "pieces": [ Piece(start=0, length=20, source="original"), Piece(start=0, length=21, source="add"), Piece(start=20, length=24, source="original"), ], } ``` 我们用文本编辑器插入的文本已被追加到添加缓冲区中，而原来单一的片段现在变成了三个。 - 列表中的第一个片段告诉编辑器，原始缓冲区的前 20 个字符（`the quick brown fox\n`）构成了文件的第一段文本（注意 `\n` 代表换行，是一个字符）。 - 第二个片段告诉编辑器，文件的接下来 21 个字符位于添加缓冲区的索引 0 到 21 之间（`went to the park and\n`）。 - 第三个也是最后一个片段告诉编辑器，文件的最后一段文本位于原始缓冲区的索引 20 到 44（起始 + 长度）之间（`jumped over the lazy dog`）。 在文件中插入文本通常会导致将一个片段拆分为三个独立的片段： 1. 一个片段指向新插入文本左侧的文本。 2. 另一个片段指向插入的文本本身（在添加缓冲区中）。 3. 第三个片段指向被推到新插入文本右侧的文本。  如果在现有片段的开头或结尾插入文本，情况会略有不同。在这种情况下，添加文本并不会“拆分”现有的片段，因此我们只需要一个额外的片段来表示新插入的文本。 ## 保存和显示打开的文件 正如本文开头提到的，当我们在文本编辑器中打开一个文件时，文件会从磁盘读取并存储在内存中的数据结构里（很可能是片段表或其变体）。同样，当我们执行反向操作——保存文件时，编辑器需要能够读取片段表并将内容写回磁盘上的文件。 通过按顺序读取片段描述符，文本编辑器可以将片段表中文件的内部表示转换为你在屏幕上看到的内容，以及保存时写入文件的内容。 ```python for piece in piece_table["pieces"]: source: str = piece.source # "original" or "add" buffer: str = piece_table[source] span_of_text: str = buffer[piece.start:piece.start+piece.length] print(span_of_text) # 或者写入文件 ``` *注意：* 在 Python 中，`string[start:end]` 语法用于返回字符串的子串。例如，`"hello"[1:3]` 返回 `"el"`。 ## 删除文本 当从文件中删除一些文本时，我们会将一个现有的片段拆分成两个片段： 1. 一个片段指向被删除文本左侧的文本。 2. 第二个片段指向被删除文本右侧的文本。 被删除的文本仍然存在于某个缓冲区中，但由于没有片段指向它，它就不再被视为文件的一部分。 你可以把片段描述符想象成照向一堵墙的聚光灯，墙上画着所有曾经写入文件的文本。在任何时刻，这些灯光照亮墙上的某些区域，显示出那里的文本。被照亮的文本被认为是文件的一部分。虽然我们知道墙上还写着更多内容，但它们隐藏在黑暗中，被视为无关信息。 ## 撤销和重做 将所有文本（即使目前不是文件的一部分）都保留的一个好处是，它大大简化了撤销/重做的实现。 当前“处于黑暗中”的文本将来可能再次需要。如果我们能简单地调整灯光，让这些文本重新被照亮，而不是重新粉刷墙壁，那不是很好吗？ 在本文开头讨论的字符串数组方法中，一次撤销操作可能需要跨数百万个不同的字符串插入或删除数百万个字符的文本。而使用片段表方法，操作的代价微不足道。要撤销或重做的文本已经存在于某个缓冲区中，我们只需要更新片段描述符再次指向它即可。 ## 结论 有多种方法可以改进上述的片段表。它们经常与其他数据结构（如树）结合使用，以改善性能的某些方面。 尽管如此，这篇博文的目标是让你对文本编辑器的内部工作原理有一些直观的认识和欣赏，而那些改进措施并不在这个目标的范围内。 如果你对这篇文章有任何建设性的反馈，或者发现了任何错误，请告诉我！ 如果你对更多类似内容感兴趣，可以关注我的 [Twitter](https://twitter.com/_darrenburns)、[DEV](https://dev.to/_darrenburns)，或者查看我的[博客](https://darrenburns.net/)！ ## 参考资料 / 延伸阅读 - [Data Structures For Text Sequences (PDF)](https://www.cs.unm.edu/~crowley/papers/sds.pdf) - Charles Crowley - [What's been wrought using the Piece Table?](https://web.archive.org/web/20160308183811/http://1017.songtrellisopml.com/whatsbeenwroughtusingpiecetables) - 可能是 David Lu - [Text Buffer Reimplementation, a Visual Studio Code Story](https://code.visualstudio.com/blogs/2018/03/23/text-buffer-reimplementation#_piece-tree) - Peng Lyu