在这篇博文中

括号对着色速度提高 10,000 倍

2021 年 9 月 29 日，作者：Henning Dieterichs，@hediet_dev

在 Visual Studio Code 中处理深度嵌套的括号时，很难确定哪些括号匹配、哪些不匹配。

为了让这一切变得更容易，2016 年，一位名为 CoenraadS 的用户开发了很棒的Bracket Pair Colorizer扩展，用于对匹配的括号进行着色，并将其发布到 VS Code Marketplace。该扩展程序变得非常受欢迎，现在是 Marketplace 上下载次数最多的 10 个扩展程序之一，安装量超过 600 万次。

为了解决性能和准确性问题，CoenraadS 在 2018 年跟进推出了Bracket Pair Colorizer 2，目前安装量也超过 300 万。

Bracket Pair Colorizer 扩展是 VS Code 可扩展性强大功能的一个很好的例子，它大量使用 Decoration API来对括号进行着色。

在 VS Code 中打开同一代码的两个屏幕截图。在第一个屏幕截图中，括号对着色被禁用，在第二个屏幕截图中，它被启用

我们很高兴看到 VS Code Marketplace 提供了更多这样的社区提供的扩展，所有这些扩展都有助于以非常有创意的方式识别匹配的括号对，包括：Rainbow Brackets、Subtle Match Brackets、Brackethighlighter、Blockman和BracketLens。各种各样的扩展表明 VS Code 用户确实希望获得对括号的更好支持。

性能问题

不幸的是，Decoration API 的非增量性质以及无法访问 VS Code 的令牌信息会导致 Bracket Pair Colorizer 扩展在大文件上运行缓慢：在 TypeScript 项目的 checker.ts 文件开头插入单个括号时代码超过 42k 行，所有括号对的颜色更新大约需要 10 秒。在这 10 秒的处理过程中，扩展主机进程会以 100% CPU 消耗，并且由扩展提供支持的所有功能（例如自动完成或诊断）都会停止运行。幸运的是，VS Code 的架构确保 UI 保持响应并且文档仍然可以保存到磁盘。

CoenraadS 意识到了这一性能问题，并通过重用 VS Code 中的令牌和括号解析引擎，投入了大量精力来提高扩展版本 2 的速度和准确性。然而，VS Code 的 API 和扩展架构的设计初衷并不是为了在涉及数十万个括号对时实现高性能的括号对着色。{因此，即使在 Bracket Pair Colorizer 2 中，在文件开头插入后，颜色也需要一些时间才能反映新的嵌套级别：

VS Code 的视频显示扩展程序需要超过 10 秒才能处理 checker.ts 中的文本更改

虽然我们希望只是提高扩展的性能（这当然需要引入更高级的 API，针对高性能场景进行优化），但渲染器和扩展主机之间的异步通信严重限制了括号对着色的速度当作为扩展实现时可以。这个限制是无法被克服的。特别是，括号对颜色一出现在视口中就不应该异步请求，因为这会在滚动大文件时导致可见的闪烁。对此的讨论可以在问题 #128465中找到。

我们做了什么

相反，在 1.60 更新中，我们在 VS Code 核心中重新实现了扩展，并将时间缩短到不到一毫秒 - 在这个特定示例中，速度快了 10,000 倍以上。

可以通过添加设置来启用该功能"editor.bracketPairColorization.enabled": true。

现在，即使对于具有数十万个括号对的文件，更新也不再明显。请注意第 42,788 行中的括号颜色如何在输入{第 2 行后立即反映新的嵌套级别：

VS Code 视频显示本机实现只需不到一毫秒即可处理 checker.ts 中的文本更改

一旦我们决定将其移至核心，我们也借此机会研究如何使其尽可能快。谁会不喜欢算法挑战呢？

不受公共 API 设计的限制，我们可以使用 (2,3) 树、无递归树遍历、位算术、增量解析和其他技术来降低扩展的最坏情况更新时间复杂度（即当文档已打开时处理用户输入所需的时间） $\mathcal{O}(N + E)$ 到 $\mathcal{O}(\mathrm{log}^3 N + E)$ 和 $氮$ 是文档大小和 $乙$ 编辑大小，假设括号对的嵌套级别由 $\mathcal{O}(\mathrm{log} N)$ 。

此外，通过重用渲染器中的现有令牌及其增量令牌更新机制，我们获得了另一个巨大（但持续）的加速。

VS Code 网页版

除了性能更高之外， VS Code for the Web还支持新的实现，您可以通过vscode.dev和 github.dev看到它的实际效果。由于 Bracket Pair Colorizer 2 重用 VS Code 令牌引擎的方式，无法将扩展迁移为我们所说的Web 扩展。

我们的新实现不仅可以在 VS Code for Web 中运行，还可以直接在Monaco 编辑器中运行！

括号对着色的挑战

括号对着色就是为了快速确定所有括号及其在视口中的（绝对）嵌套级别。视口可以描述为文档中行数和列数的范围，通常是整个文档的一小部分。

不幸的是，括号的嵌套级别取决于它前面的所有字符：用左括号“ {”替换任何字符通常会增加所有后续括号的嵌套级别。

因此，当最初对文档末尾的括号进行着色时，必须处理整个文档的每个字符。

该图表明更改单个字符会影响所有后续括号的嵌套级别

括号对着色器扩展中的实现通过在插入或删除单个括号时再次处理整个文档来解决这一挑战（这对于小文档来说是非常合理的）。然后必须使用 VS Code Decoration API删除并重新应用颜色，该 API 将所有颜色装饰发送到渲染器。

如前所述，对于具有数十万个括号对并因此具有同样多的颜色装饰的大型文档来说，这很慢。由于扩展无法增量更新装饰并且必须一次性替换所有装饰，因此括号对着色器扩展甚至无法做得更好。尽管如此，渲染器以一种巧妙的方式组织所有这些装饰（通过使用所谓的间隔树），因此在收到（可能是数十万个）装饰后渲染总是很快。

我们的目标是不必在每次击键时重新处理整个文档。相反，处理单个文本编辑所需的时间应该仅随文档长度呈对数增长 ( poly )。

然而，我们仍然希望能够在（聚）对数时间内查询视口中的所有括号及其嵌套级别，就像使用 VS Code 的装饰 API（使用提到的间隔树）时的情况一样。

算法复杂性

请随意跳过有关算法复杂性的部分。

在下面的， $氮$ 指的是文档的长度。更正式地说，我们的目标是时间复杂度最多为 $\mathcal{O}(\mathrm{log}^k N + R)$ 用于查询给定大小范围内的所有括号 $右$ 和一个合理的小 $k$ （我们的目标是 $k = 2$ ）。渲染视口时会查询括号，因此查询它们必须非常快。

然而，我们允许初始化时间复杂度为 $\mathcal{O}(N)$ 第一次打开文档时（这是不可避免的，因为在最初对括号着色时必须处理所有字符）和更新时间 $\mathcal{O}(\mathrm{log}^j N + E)$ 什么时候 $乙$ 许多字符被修改或插入，同样是为了一个合理的小 $j$ （我们的目标是 $j = 3$ ）。我们还假设括号对的嵌套级别不会太深，最多 $\mathcal{O}(\mathrm{log} N)$ 并且没有左括号的右括号的数量可以忽略不计 - 违反这些假设的文档是非典型的，我们正在寻找的算法不需要快速处理它们。

语言语义使得括号对着色变得困难

使括号对着色真正困难的是检测文档语言定义的实际括号。特别是，我们不想检测注释或字符串中的左括号或右括号，如以下 C 示例所示：

{ /* } */ char str[] = "}"; }

只有第三次出现“ }”才结束括号对。

对于令牌语言不规则的语言（例如带有 JSX 的 TypeScript），这会变得更加困难：

TypeScript 代码的屏幕截图，显示了一个包含带有嵌套表达式的模板文字的函数。模板文字还在位置 2 处包含一个右括号。该函数以 1 处的括号开始，以 3 处的括号结束。

[1] 处的括号与 [2] 或 [3] 处的括号匹配吗？这取决于模板文字表达式的长度，只有具有无界状态的分词器（这是非常规分词器）才能正确确定。

代币来救援

幸运的是，语法高亮必须解决类似的问题：前面的代码片段中 [2] 处的括号应该呈现为字符串还是纯文本？

事实证明，对于大多数括号对来说，仅忽略语法突出显示所标识的注释和字符串中的括号就足够了。 <...>是我们迄今为止发现的唯一有问题的对，因为这些括号通常既用于比较又用作泛型类型的对，同时具有相同的标记类型。

VS Code 已经有一个高效、同步的机制来维护用于语法突出显示的标记信息，我们可以重用它来识别左括号和右括号。

这是括号对着色扩展的另一个挑战，会对性能产生负面影响：它无法访问这些令牌，并且必须自行重新计算它们。我们思考了如何高效、可靠地向扩展公开令牌信息，但得出的结论是，如果不将大量实现细节泄漏到扩展 API 中，我们就无法做到这一点。由于扩展程序仍然必须为文档中的每个括号发送颜色装饰列表，因此仅靠这样的 API 甚至无法解决性能问题。

附带说明一下，当在文档开头应用编辑来更改所有后续标记（例如插入/*类 C 语言）时，VS Code 不会一次性重新标记长文档，而是随着时间的推移分块重新标记。这可以确保 UI 不会冻结，即使标记化在渲染器中同步发生也是如此。

基本算法

其核心思想是使用递归下降解析器构建描述所有括号对结构的抽象语法树（AST）。当找到括号时，检查令牌信息，如果括号位于注释或字符串中，则跳过该括号。分词器允许解析器查看和读取此类括号或文本标记。

现在的技巧是仅存储每个节点的长度（并且还为所有不是括号的内容提供文本节点以覆盖间隙），而不是存储绝对开始/结束位置。仅在长度可用的情况下，仍然可以在 AST 中有效地定位给定位置处的括号节点。

下图显示了带有长度注释的示例 AST：

具有相对长度的括号对的抽象语法树

将其与使用绝对开始/结束位置的经典 AST 表示进行比较：

具有绝对开始/结束位置的括号对的抽象语法树

两个 AST 都描述相同的文档，但是当遍历第一个 AST 时，必须动态计算绝对位置（这样做很便宜），而它们已经在第二个 AST 中预先计算过了。

但是，当将单个字符插入第一棵树时，只有节点本身及其所有父节点的长度必须更新 - 所有其他长度保持不变。

当绝对位置存储在第二棵树中时，文档中后面每个节点的位置必须递增。

此外，通过不存储绝对偏移量，可以共享具有相同长度的叶节点以避免分配。

这就是在 TypeScript 中定义带有长度注释的 AST 的方式：

type Length = ...;

type AST = BracketAST | BracketPairAST | ListAST | TextAST;

/** Describes a single bracket, such as `{`, `}` or `begin` */
class BracketAST {
    constructor(public length: Length) {}
}

/** Describes a matching bracket pair and the node in between, e.g. `{...}` */
class BracketPairAST {
    constructor(
        public openingBracket: BracketAST;
        public child: BracketPairAST | ListAST | TextAST;
        public closingBracket: BracketAST;
    ) {}

    length = openingBracket.length + child.length + closingBracket.length;
}

/** Describes a list of bracket pairs or text nodes, e.g. `()...()` */
class ListAST {
    constructor(
        public items: Array<BracketPairAST | TextAST>
    ) {}

    length = items.sum(item => item.length);
}

/** Describes text that has no brackets in it. */
class TextAST {
    constructor(public length: Length) {}
}

查询这样的 AST 以列出所有括号及其在视口中的嵌套级别相对简单：进行深度优先遍历，动态计算当前节点的绝对位置（通过添加较早节点的长度），然后跳过子节点完全位于请求范围之前或之后的节点。

这个基本算法已经可以工作，但有一些悬而未决的问题：

我们如何确保查询给定范围内的所有括号具有所需的对数性能？
在打字时，我们如何避免从头开始构造一个新的 AST？
我们如何处理令牌块更新？打开大型文档时，令牌最初不可用，而是逐块出现。

确保查询时间是对数的

当查询给定范围内的括号时，真正影响性能的是长列表：我们无法对其子节点进行快速二分搜索以跳过所有不相关的非相交节点，因为我们需要对每个节点的长度求和来动态计算绝对位置。在最坏的情况下，我们需要迭代所有这些。

在下面的示例中，我们必须查看 13 个节点（蓝色），直到找到位置 24 处的括号：

抽象语法树中的长列表

虽然我们可以计算和缓存长度总和以启用二分搜索，但这与存储绝对位置有同样的问题：每次单个节点增长或收缩时，我们都需要重新计算所有这些位置，这对于很长的列表来说成本高昂。

相反，我们允许列表有其他列表作为子列表：

class ListAST {
  constructor(public items: Array<ListAST | BracketPairAST | TextAST>) {}

  length = items.sum(item => item.length);
}

这如何改善这种情况？

如果我们可以确保每个列表只有有限数量的子项并且类似于对数高度的平衡树，那么事实证明这足以获得查询括号所需的对数性能。

保持列表树平衡

我们使用(2,3) 树来强制这些列表是平衡的：每个列表必须至少有 2 个、最多 3 个子级，并且列表的所有子级在平衡列表树中必须具有相同的高度。请注意，括号对被视为平衡树中高度为 0 的叶子，但它在 AST 中可能有子节点。

在初始化期间从头开始构建 AST 时，我们首先收集所有子节点，然后将它们转换为这样的平衡树。这可以在线性时间内完成。

之前示例的可能 (2,3) 树如下所示。请注意，我们现在只需要查看 8 个节点（蓝色）即可找到位置 24 处的括号对，并且列表是否有 2 个或 3 个子节点有一定的自由度：

用于描述 AST 中列表的平衡树

最坏情况复杂性分析

请随意跳过有关算法复杂性的部分。

现在，我们假设每个列表都类似于一棵 (2,3) 树，因此最多有 3 个子列表。

为了最大化查询时间，我们查看一个文档，其中包含 $\mathcal{O}(\mathrm{log} N)$ 许多嵌套的括号对：

{
    {
        ... O(log N) many nested bracket pairs
            {
                {} [1]
            }
        ...
    }
}

还没有涉及列表，但是我们已经需要遍历 $\mathcal{O}(\mathrm{log} N)$ 许多节点来查找 [1] 处的括号对。幸运的是，嵌套更深的文档是非典型的，因此我们在最坏情况分析中不会考虑它们。

现在，对于最坏的情况，我们填充文档直到它有大小 $氮$ 通过插入额外的 $\mathcal{O}(\frac{N}{\mathrm{log} N})$ 每个嵌套括号对中有许多括号对：

{}{}{}{}{}{}{}{}... O(N / log N) many
{
    {}{}{}{}{}{}{}{}... O(N / log N) many
    {
        ... O(log N) many nested bracket pairs
            {
                {}{}{}{}{}{}{}{}... O(N / log N) many
                {} [1]
            }
        ...
    }
}

同一嵌套级别上的每个括号列表都会生成一棵高度树 $\mathcal{O}(\mathrm{log} \frac{N}{\mathrm{log} N}) = \mathcal{O}(\mathrm{log} N - \mathrm{log}\;\mathrm{log } N ) = \mathcal{O}(\mathrm{log} N)$ 。

因此，要找到[1]处的节点，我们必须遍历 $\mathcal{O}(\mathrm{log} N)$ 许多高度平衡的树 $\mathcal{O}(\mathrm{log} N)$ 。一旦我们找到节点并想要收集一定大小范围内的所有括号 $右$ ，我们最多要读 $\mathcal{O}(R)$ 最多连接多个相邻叶节点 $\mathcal{O}(\mathrm{log}^2 N + R)$ 内部节点。

因此，查询括号的最坏情况时间复杂度是 $\mathcal{O}(\mathrm{log}^2 N + R)$ 。

此外，这表明 AST 的最大高度为 $\mathcal{O}(\mathrm{log}^2 N)$ 。

增量更新

高性能括号对着色最有趣的问题仍然悬而未决：给定当前（平衡）AST 和替换特定范围的文本编辑，我们如何有效地更新树以反映文本编辑？

这个想法是重用用于初始化的递归下降解析器并添加缓存策略，因此可以重用和跳过不受文本编辑影响的节点。

当递归下降解析器解析位置处的括号对列表时 $p$ 下一个编辑位于位置 $e$ ，它首先检查前面的 AST 是否有一个长度最多为的节点 $电子$ 在的位置 $p$ 曾经是在文本更改之前。如果是这种情况，则不需要重新解析该节点，并且底层分词器只需按节点的长度前进即可。消耗节点后，解析继续。请注意，该节点可以是单个括号对或整个列表。另外，如果有多个这样的可重用节点，则应取最长的一个。

以下示例显示了插入单个左括号（省略各个括号节点）时可以重用哪些节点（绿色）：

AST 中的可重用节点

通过重新解析包含编辑的节点并重用所有未更改的节点来处理文本编辑后，更新后的 AST 如下所示。请注意，所有 11 个可重用节点都可以通过消耗 3 个节点 B、H 和 G 来重用，并且只需重新创建 4 个节点（橙色）：

更新了 AST

正如本示例所示，平衡列表不仅可以加快查询速度，还有助于一次重用大量节点。

算法复杂度

请随意跳过有关算法复杂性的部分。

我们假设文本编辑替换的大小范围可达 $乙$ 最多可达 $乙$ 许多新角色。我们还忽略了目前没有左括号的罕见情况。

我们只需要重新解析与编辑范围相交的节点。这样，至多 $\mathcal{O}(\mathrm{log}^2 N + E)$ 许多节点需要重新解析（与查询括号的时间复杂度的推理相同） - 所有其他节点都可以重用。

显然，如果一个节点不与编辑范围相交，那么它的任何子节点也不相交。因此，我们只需要考虑重用那些不与编辑范围相交但其父节点与编辑范围相交的节点（这将隐式重用该节点及其父节点均不与编辑范围相交的所有节点）。而且，这样的父节点不能完全被编辑范围覆盖，否则它们的所有子节点都会与编辑范围相交。但是，AST 中的每个级别最多只有两个与编辑范围部分相交的节点。由于 AST 最多有 $\mathcal{O}(\mathrm{log}^2 N)$ 层数多（受 AST 高度限制），每个节点最多有 3 个子节点，最多可以通过消费覆盖所有可复用节点 $\mathcal{O}(2 \cdot 3 \cdot \mathrm{log}^2 N) = \mathcal{O}(\mathrm{log}^2 N)$ 节点。

因此，为了构建更新的树，我们最多需要重新解析 $\mathcal{O}(\mathrm{log}^2 N + E)$ 许多节点并且可以重用 $\mathcal{O}(\mathrm{log}^2 N)$ 许多节点。

这也将决定更新操作的时间复杂度，但有一个警告。

我们如何重新平衡 AST？

不幸的是，最后一个例子中的树不再平衡。

当将重用的列表节点与新解析的节点组合时，我们必须做一些工作来维护 (2,3) 树属性。我们知道重用的节点和新解析的节点都已经是 (2,3) 树，但它们可能具有不同的高度 - 因此我们不能只创建父节点，因为 (2,3) 树节点的所有子节点都必须具有相同的高度。

我们如何有效地将所有这些混合高度的节点连接成一棵 (2,3) 树？

这可以很容易地简化为将较小的树添加到较大的树之前或附加到较大的树的问题：如果两棵树具有相同的高度，则足以创建一个包含两个子树的列表。否则，我们插入高度较小的树 $h_1$ 进入更大的树的高度 $h_2$ 如果节点最终有超过 3 个子节点，则可能会破坏节点（类似于 (2,3) 树的插入操作的工作原理）。

因为这有运行时间 $\mathcal{O}(h_2 - h_1)$ ，我们取 3 个相邻节点（ $A$ , $乙$ ，和 $C$ ）我们想要连接并连接 $A$ 和 $乙$ 或者 $乙$ 和 $C$ 首先（可能会增加树的高度），具体取决于哪对树的高度差较小。重复此操作，直到所有节点都连接起来。作为一项额外的优化，我们寻找具有相同高度的节点序列，并在线性时间内为它们创建父列表。

为了平衡上一个示例的列表 α 和 γ，我们对它们的子项执行 concat 操作（红色列表违反了 (2,3) 树属性，橙色节点具有意外高度，绿色节点在重新平衡时重新创建）：

平衡列表后的 AST

因为在不平衡树中列表 B 的高度为 2，括号对 β 的高度为 0，所以我们需要将 β 附加到 B 并完成列表 α。剩下的(2,3)树是B，因此它成为新的根并取代列表α。继续 γ，它的子代 δ 和 H 的高度为 0，而 G 的高度为 1。

我们首先连接 δ 和 H 并创建一个高度为 1 的新父节点 Y（因为 δ 和 H 具有相同的高度）。然后我们连接 Y 和 G 并创建一个新的父列表 X（出于相同的原因）。然后 X 成为父括号对的新子项，替换不平衡列表 γ。

在示例中，平衡操作有效地将最顶层列表的高度从 3 减少到 2。但是，AST 的总高度从 4 增加到 5，这对最坏情况下的查询时间产生负面影响。这是由括号对 β 引起的，它充当平衡列表树中的叶子，但实际上包含另一个高度为 2 的列表。

在平衡父列表时考虑β的内部AST高度可以改善最坏的情况，但会离开(2,3)树的理论。

算法复杂度

请随意跳过有关算法复杂性的部分。

我们最多必须串联 $\mathcal{O}(\mathrm{log}^2 N)$ 许多节点的最大列表高度为 $\mathcal{O}(\mathrm{log} N)$ （我们重复使用的）和其他 $\mathcal{O}(\mathrm{log}^2 N + E)$ 许多列表高度为 0 的节点（我们重新解析的节点）。

因为连接两个不同高度的节点具有时间复杂度 $\mathcal{O}(\mathrm{log} N)$ 并且列表中所有重新解析的节点都是相邻的并且列表高度为0，整个更新操作的时间复杂度最多为 $\mathcal{O}(\mathrm{log}^3 N + E)$ ，考虑到找到可重用节点的速度可以足够快。

我们如何高效地找到可重用的节点？

我们有两个数据结构用于此任务：编辑前位置映射器和节点读取器。

如果可能的话，位置映射器将新文档中的位置（应用编辑之后）映射到旧文档（应用编辑之前）。它还告诉我们当前位置和下一次编辑之间的长度（如果我们正在进行编辑，则为 0）。这是在 $\mathcal{O}(1)$ 。

当处理文本编辑和解析节点时，该组件为我们提供了可以重用的节点的位置以及该节点可以具有的最大长度 - 显然，我们想要重用的节点必须短于到下一个节点的距离编辑。

节点读取器可以快速找到 AST 中给定位置处满足给定谓词的最长节点。为了找到可以重用的节点，我们使用位置映射器查找其旧位置和最大允许长度，然后使用节点读取器找到该节点。如果我们找到这样的节点，我们就知道它没有改变，可以重用它并跳过它的长度。

由于节点读取器是以单调递增的位置进行查询的，因此不必每次都从头开始搜索，而是可以从最后一个重用节点的末尾开始搜索。其关键是一种无递归树遍历算法，该算法可以深入节点，但也可以跳过它们或返回到父节点。当找到可重用节点时，遍历停止并继续向节点读取器发出下一个请求。

单次查询节点阅读器的复杂度可达 $\mathcal{O}(\mathrm{log}^2 N)$ ，但我们非常确定单个更新操作发出的所有请求的摊余复杂度也是 $\mathcal{O}(\mathrm{log}^2 N)$ 。毕竟，节点读取器仅查询不受文本编辑影响的位置，并且始终采用从最后一个可重用节点到下一个可重用节点的最短路径。因此，我们认为节点读取器足够高效，不会影响更新算法的运行时复杂性。

令牌更新

当在/*不包含 text 的长 C 风格文档的开头插入*/时，整个文档变成单个注释并且所有标记都会更改。

由于令牌是在渲染器进程中同步计算的，因此在不冻结 UI 的情况下无法立即进行重新令牌化。

相反，令牌会随着时间的推移批量更新，以便 JavaScript 事件循环不会阻塞太久。虽然这种方法不会减少总阻塞时间，但它提高了更新期间 UI 的响应能力。最初对文档进行标记时也使用相同的机制。

幸运的是，由于括号对 AST 的增量更新机制，我们可以通过将更新视为单个文本编辑来立即应用这样的批量标记更新，该文本编辑将重新标记化的范围替换为自身。一旦所有令牌更新进来，括号对 AST 就保证处于与从头开始创建相同的状态 - 即使用户在重新令牌化过程中编辑文档也是如此。

这样，即使文档中的所有标记发生变化，不仅标记化是高性能的，而且括号对着色也是如此。

但是，当文档中的注释中包含大量不平衡的括号时，文档末尾的括号颜色可能会闪烁，因为括号对解析器了解到应该忽略这些括号。

为了避免在打开文档并导航到末尾时括号对颜色闪烁，我们维护两个括号对 AST，直到初始标记化过程完成。第一个 AST 是在没有令牌信息的情况下构建的，并且不接收令牌更新。第二个最初是第一个 AST 的克隆，但随着令牌化的进展和令牌更新的应用，它接收令牌更新并且分歧越来越大。最初，第一个 AST 用于查询括号，但一旦文档完全标记化，第二个 AST 就会接管。

由于深度克隆几乎与重新解析文档一样昂贵，因此我们实现了写时复制，从而能够在 $\mathcal{O}(1)$ 。

长度编码

编辑器视图用行号和列号描述视口。颜色装饰也有望表示为基于行/列的范围。

为了避免偏移量和基于行/列的位置之间的转换（可以在 $\mathcal{O}(\mathrm{log} N)$ ），我们也对 AST 使用基于行/列的长度。

请注意，这种方法与直接按行索引的数据结构（例如使用字符串数组来描述文档的行内容）有显着不同。特别是，这种方法可以跨行和行内执行单个二分搜索。

添加两个这样的长度很容易，但需要区分大小写：虽然直接添加行计数，但仅当第二个长度跨越零行时才包含第一个长度的列计数。

令人惊讶的是，大多数代码不需要知道长度是如何表示的。只是位置映射器变得更加复杂，因为必须注意单行可以包含多个文本编辑。

作为实现细节，我们将这些长度编码为单个数字以减少内存压力。JavaScript 支持的整数最大为 $2^{53} - 1$ ，因此我们最多可以使用 26 位来表示行数和列数。不幸的是，v8 存储的数字大于 $2^{31}$ 在堆中，所以这个编码技巧并没有我们想象的那么有效。

进一步的困难：未闭合的支架对

到目前为止，我们假设所有括号对都是平衡的。但是，我们还希望支持未闭合和未打开的括号对。递归下降解析器的优点在于我们可以使用锚集来改进错误恢复。

考虑以下示例：

( [1]
} [2]
) [3]

显然，}[2] 处不闭合任何括号对，并且表示未开括号。[1] 和 [3] 处的括号匹配得很好。然而，当{在文档开头插入时，情况发生了变化：

{ [0]
( [1]
} [2]
) [3]

现在，[0]和[2]应该匹配，而[1]是一个未闭括号，[3]是一个未开括号。

特别是，在以下示例中，[1] 应该是在 [2] 之前终止的未闭合括号：

{
    ( [1]
} [2]
{}

否则，打开括号可能会更改不相关的后续括号对的嵌套级别。

为了支持这种错误恢复，可以使用锚集来跟踪调用者可以继续的预期标记集。在上一示例中的位置 [1] 处，锚集将是 $\{$ } $\}$ 。因此，当解析 [1] 处的括号对时，}在 [2] 处发现意外的括号，它不会消耗它并返回一个未闭合的括号对。

在第一个示例中，[2]处设置的锚点是 $\{$ ) $\}$ 但出乎意料的人物却是}。因为它不是锚集的一部分，所以它被报告为未打开的括号。

重用节点时需要考虑这一点：( } )当在其前面添加时，该对不能被重用{。我们使用位集来编码锚集并计算每个节点包含未开括号的集合。如果它们相交，我们就无法重用该节点。幸运的是，支架类型只有几种，因此这不会对性能产生太大影响。

向前走

高效的括号对着色是一个有趣的挑战。使用新的数据结构，我们还可以更有效地解决与括号对相关的其他问题，例如一般括号匹配或显示彩色行范围。

尽管 JavaScript 可能不是编写高性能代码的最佳语言，但通过降低渐近算法复杂性可以获得很大的速度，尤其是在处理大型输入时。

快乐编码！

Henning Dieterichs，VS Code 团队成员@hediet_dev