括号对着色速度提高 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 文件（有超过 42k 行代码）的开头插入单个括号时，大约需要 10 秒钟才能更新所有括号对的颜色。在这 10 秒钟的处理过程中，扩展主机进程会占用 100% 的 CPU，并且所有由扩展驱动的功能（例如自动完成或诊断）都会停止运行。幸运的是，VS Code 的架构确保了 UI 保持响应，并且文档仍然可以保存到磁盘。

CoenraadS 意识到了此性能问题，并通过重用 VS Code 的令牌和括号解析引擎，在扩展的第 2 版中花费了大量精力来提高速度和准确性。但是，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 的核心中重新实现了该扩展，并将此时间缩短到不到一毫秒 - 在这个特定示例中，速度提高了 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)$ .

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

适用于 Web 的 VS Code

除了性能更高之外，适用于 Web 的 VS Code 也支持新的实现，您可以在 vscode.dev 和 github.dev 中看到它的实际效果。由于 Bracket Pair Colorizer 2 重用了 VS Code 令牌引擎，因此无法将扩展迁移到我们所谓的 Web 扩展。

我们的新实现不仅在适用于 Web 的 VS Code 中有效，而且在 Monaco 编辑器中也直接有效！

括号对着色的挑战

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

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

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

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

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

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

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

但是，我们仍然希望能够在（多）对数时间内查询视口中所有括号及其嵌套级别，就像使用 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 已经具有用于维护语法高亮显示的标记信息的有效同步机制，我们可以重用它来识别开括号和闭括号。

这是括号对着色扩展的另一个挑战，它对性能产生负面影响：它无法访问这些标记，必须自己重新计算它们。我们考虑了很久如何有效地且可靠地向扩展公开标记信息，但最终得出结论，如果不将大量实现细节泄漏到扩展 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 如下所示。请注意，通过消耗 3 个节点 B、H 和 G，可以重用所有 11 个可重用节点，并且只需要重新创建 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$ （可能会增加树的高度）。重复此操作，直到所有节点都已连接。作为额外的优化，我们查找具有相同高度的节点序列，并在线性时间内为其创建父列表。

为了平衡上例中的列表 α 和 γ，我们对其子节点执行 concat 操作（红色列表违反 (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