括号对彩色化速度提升 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 来为括号着色。

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 项目中包含超过 4.2 万行代码的 checker.ts 文件开头插入单个括号时，直到所有括号对的颜色更新完成需要大约 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），但渲染器和扩展宿主之间的异步通信严重限制了作为扩展实现时括号对彩色化的速度。这个限制无法克服。特别是，括号对颜色不应在它们出现在视口中时立即异步请求，因为这会导致在大文件中滚动时出现明显的闪烁。相关讨论可在 issue #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

除了性能更好之外，新实现还支持 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

括号对彩色化扩展中的实现通过在每次插入或删除单个括号时重新处理整个文档（这对于小型文档来说非常合理）来解决这个挑战。然后必须使用 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 已经拥有一个高效且同步的机制来维护用于语法高亮的令牌信息，我们可以重用它来识别开括号和闭括号。

这是 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 如下所示。请注意，通过使用 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$ （可能会增加树的高度）。重复此操作直到所有节点都连接起来。作为额外的优化，我们查找高度相同的节点序列，并为它们在线性时间内创建父列表。

为了平衡前一个示例中的列表 α 和 γ，我们对其子列表执行连接操作（红色列表违反了 (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 就会接管。

由于深层克隆的开销几乎与重新解析文档一样大，我们实现了写时复制 (copy-on-write)，从而在 $\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