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

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

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

为了简化这一过程，2016 年，一位名为 CoenraadS 的用户开发了出色的 Bracket Pair Colorizer 扩展来对匹配的括号进行颜色化，并将其发布到 VS Code Marketplace。该扩展变得非常受欢迎，现在是 Marketplace 上 10 个下载量最大的扩展之一，拥有超过 600 万次安装。

为了解决性能和准确性问题，2018 年，CoenraadS 推出了 Bracket Pair Colorizer 2，该扩展现在也拥有超过 300 万次安装。

Bracket Pair Colorizer 扩展很好地展示了 VS Code 可扩展性的强大功能，并大量使用了 Decoration API 来对括号进行颜色化。

Two screenshots of the same code opened in VS Code. In the first screenshot, bracket pair colorization is disabled, in the second screenshot, it is enabled

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

性能问题

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

CoenraadS 意识到了此性能问题，并在扩展的版本 2 中投入了大量精力来提高速度和准确性，方法是重用来自 VS Code 的令牌和括号解析引擎。但是，VS Code 的 API 和扩展架构并非旨在当涉及数十万个括号对时，允许高性能的括号对颜色化。因此，即使在 Bracket Pair Colorizer 2 中，在文件开头插入 { 后，也需要一些时间才能让颜色反映新的嵌套级别。

A video of VS Code showing that the extension needs more than 10 seconds to process the text change in checker.ts

虽然我们很想只提高扩展的性能（这肯定需要引入更多针对高性能场景优化的高级 API），但渲染器与扩展宿主之间的异步通信严重限制了以扩展形式实现括号对颜色化的速度。无法克服这种限制。特别是，不应异步请求括号对颜色，因为一旦它们出现在视窗中，就会导致在滚动大型文件时出现明显的闪烁。关于这方面的讨论可以在问题 #128465 中找到。

我们做了什么

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

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

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

A video of VS Code showing that the native implementation needs less than a millisecond to process the text change in checker.ts

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

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

此外，通过重用来自渲染器及其增量令牌更新机制的现有令牌，我们获得了另一个巨大的（但恒定的）速度提升。

VS Code for the Web

除了性能更高之外，新的实现还支持 VS Code for the Web，您可以在 vscode.dev 和 github.dev 中看到其运行情况。由于 Bracket Pair Colorizer 2 重用了 VS Code 令牌引擎的方式，因此无法将该扩展迁移为我们所说的 Web 扩展。

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

括号对颜色化的挑战

括号对颜色化就是关于快速确定视窗中所有括号及其（绝对）嵌套级别。视窗可以用行号和列号来描述，通常只是整个文档的一小部分。

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

因此，在最初对文档末尾的括号进行颜色化时，必须处理整个文档中的每一个字符。

A diagram that indicates that changing a single character influences the nesting level of all subsequent brackets

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

如前所述，对于包含数十万个括号对（以及同样多的颜色装饰）的大型文档来说，这样做速度很慢。由于扩展无法增量更新装饰，而必须一次性替换所有装饰，因此 Bracket Pair Colorizer 扩展甚至无法做得更好。但是，渲染器会以一种巧妙的方式组织所有这些装饰（通过使用所谓的区间树），因此在接收（可能数十万个）装饰后，渲染始终很快。

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

然而，我们仍然希望能够在 (多项式) 对数时间内查询视窗中的所有括号及其嵌套级别，就像使用 VS Code 的装饰 API（它使用提到的区间树）一样。

算法复杂度

可以自由跳过关于算法复杂度的部分。

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

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

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

使括号对着色真正困难的是根据文档语言检测实际括号。具体来说，我们不希望检测注释或字符串中的开头或结束括号，如下面的 C 示例所示

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

只有第三个“}”实例关闭了括号对。

对于令牌语言不是正则表达式的语言，例如带有 JSX 的 TypeScript，这会变得更加困难

Screenshot of TypeScript code, showing a function that contains a template literal with nested expressions. The template literal also contains a closing bracket at position 2. The function starts with the bracket at 1 and ends with the bracket at 3.

[1] 处的括号与 [2] 处的括号匹配还是与 [3] 处的括号匹配？这取决于模板文字表达式的长度，只有具有无界状态的令牌器（这是一个非正则令牌器）才能正确地确定这一点。

令牌来拯救

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

事实证明，仅忽略语法高亮识别出的注释和字符串中的括号对于大多数括号对来说已经足够好。< ... > 是我们迄今为止发现的唯一有问题的对，因为这些括号通常用于比较和作为泛型类型的对，同时具有相同的令牌类型。

VS Code 已经拥有一个高效且同步的机制来维护用于语法高亮的令牌信息，我们可以重用它来识别开头和结束括号。

这是 Bracket Pair Colorization 扩展的另一个影响性能的挑战：它无法访问这些令牌，必须自行重新计算它们。我们曾经认真考虑如何高效且可靠地将令牌信息暴露给扩展，但得出的结论是，我们无法在不将大量实现细节泄露到扩展 API 的情况下做到这一点。由于扩展仍然必须为文档中的每个括号发送一个颜色装饰列表，因此仅靠这样的 API 甚至无法解决性能问题。

作为旁注，在对文档开头应用更改所有后续令牌的编辑（例如，为 C 类语言插入 /*）时，VS Code 不会立即重新令牌化长文档，而是会随着时间的推移分块进行。这样可以确保即使令牌化在渲染器中同步发生，UI 也不会冻结。

基本算法

核心思想是使用递归下降解析器来构建一个抽象语法树 (AST) 来描述所有括号对的结构。当找到一个括号时，检查令牌信息，如果它在注释或字符串中，则跳过该括号。令牌器允许解析器查看并读取这样的括号或文本令牌。

现在，技巧是仅存储每个节点的长度（以及为所有非括号内容提供文本节点以覆盖间隙），而不是存储绝对的起始/结束位置。仅使用长度可用，则可以在 AST 中有效地定位给定位置处的括号节点。

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

Abstract Syntax Tree of Bracket Pairs With Relative Lengths

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

Abstract Syntax Tree of Bracket Pairs With Absolute Start/End Positions

这两个 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 处的括号

Long list in Abstract Syntax Tree

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

相反，我们允许列表以其他列表作为子节点

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 个子节点有一定的自由度。

Balanced tree to describe lists in the AST

最坏情况复杂度分析

可以自由跳过关于算法复杂度的部分。

目前，我们假设每个列表都类似于 (2,3) 树，因此最多有 3 个子节点。

为了最大程度地提高查询时间，我们查看了一个包含以下内容的文档： $\mathcal{O}(\mathrm{log} N)$ 许多嵌套的括号对

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

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

现在，对于最坏情况，我们填充文档，直到它的大小为 $N$ 通过插入额外的 $\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)$ 的平衡树。一旦我们找到该节点并想要收集大小为 $R$ 范围内的所有括号，我们最多需要读取 $\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 是否具有长度最多为 $e - p$ 的节点，该节点位于 $p$ 在文本更改之前的位置。如果是这种情况，则不需要重新解析此节点，底层标记器只需向前移动节点的长度即可。在使用完节点后，解析继续进行。请注意，此节点可以是单个括号对，也可以是整个列表。此外，如果有多个这样的可重用节点，则应选择最长的节点。

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

Reusable Nodes in AST

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

Updated AST

如本示例所示，平衡列表不仅可以使查询速度更快，还可以帮助一次性重用大量节点。

算法复杂度

可以自由跳过关于算法复杂度的部分。

假设文本编辑替换了大小不超过 $E$ 的范围，最多包含 $E$ 个新字符。目前，我们还忽略了没有对应左括号的右括号的罕见情况。

我们只需要重新解析与编辑范围相交的节点。因此，最多 $\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$ , $b$ ，以及 $c$ ）我们要连接起来，并连接 $a$ 以及 $b$ 或者 $b$ 以及 $c$ 首先（可能增加树的高度），具体取决于哪一对的高度差较小。重复此操作，直到所有节点都连接起来。作为一项额外的优化，我们查找具有相同高度的节点序列，并在线性时间内为它们创建父列表。

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

AST after balancing lists

因为列表 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)$ 。毕竟，节点读取器只针对不受文本编辑影响的位置进行查询，并且始终从最后一个可重用节点到下一个可重用节点走最短路径。因此，我们认为节点读取器足够高效，不会影响更新算法的运行时复杂度。

令牌更新

在长 C 样式文档的开头插入 /* 时，该文档不包含文本 */，整个文档将成为单个注释，所有标记都会改变。

由于标记是在渲染器进程中同步计算的，因此重新标记不能一次性完成，否则会冻结 UI。

相反，标记会随着时间的推移以批次更新，这样 JavaScript 事件循环就不会被阻塞太长时间。虽然这种方法不会减少总阻塞时间，但它会提高更新期间 UI 的响应速度。相同的机制也用于最初标记文档。

幸运的是，由于括号对 AST 的增量更新机制，我们可以通过将更新视为一个替换被重新标记范围自身的单个文本编辑来立即应用这种批次标记更新。一旦所有标记更新都进来，括号对 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