括号对颜色化速度提高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来对括号进行颜色化。

我们很高兴看到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文件（该文件有超过4.2万行代码）的开头插入一个括号时，所有括号对的颜色更新大约需要10秒钟。在这10秒的处理过程中，扩展宿主进程会占用100%的CPU，所有由扩展驱动的功能，如自动补全或诊断，都会停止工作。幸运的是，VS Code的架构确保UI保持响应，并且文档仍然可以保存到磁盘。

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

虽然我们很乐意只改进扩展的性能（这肯定需要引入更高级的API，为高性能场景优化），但渲染器和扩展宿主之间的异步通信严重限制了作为扩展实现时括号对颜色化的速度。这个限制无法克服。特别是，括号对的颜色不应在它们出现在视口中时立即异步请求，因为这会导致滚动大文件时出现明显的闪烁。关于这方面的讨论可以在issue #128465中找到。

我们做了什么

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

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

现在，即使对于包含数十万个括号对的文件，更新也几乎察觉不到。请注意，在第2行输入{后，第42,788行中的括号颜色如何立即反映新的嵌套级别。

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

在不受公共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中工作！

括号对颜色化的挑战

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

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

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

括号对颜色器扩展中的实现通过在每次插入或删除单个括号时重新处理整个文档来解决这个挑战（这对于小文档来说是非常合理的）。然后必须使用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 这样令牌语言不是常规的语言，这甚至更难。

[1]处的括号与[2]处的括号还是[3]处的括号匹配？这取决于模板字面量表达式的长度，只有具有无界状态的词法分析器（即非正则词法分析器）才能正确确定。

令牌来救援

幸运的是，语法高亮也要解决类似的问题：前一个代码片段中[2]处的括号应该作为字符串还是纯文本渲染？

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

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

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

作为旁注，当在文档开头应用一个更改所有后续令牌的编辑（例如，为C语言类语言插入/*）时，VS Code不会一次性重新令牌化长文档，而是分块进行。这确保了UI不会冻结，即使令牌化在渲染器中同步发生。

基本算法

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

现在的诀窍是只存储每个节点的长度（并且为所有非括号的部分设置文本节点以填补空白），而不是存储绝对的开始/结束位置。仅凭长度，仍然可以在AST中高效地定位给定位置的括号节点。

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

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

两个AST描述的是同一个文档，但在遍历第一个AST时，绝对位置必须动态计算（成本很低），而第二个AST中它们已经预先计算好了。

然而，当在第一棵树中插入一个字符时，只需要更新节点本身及其所有父节点的长度——所有其他长度保持不变。

当像第二棵树那样存储绝对位置时，文档中每个后续节点的位置都必须递增。

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

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

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以列出视口中所有括号及其嵌套级别相对简单：进行深度优先遍历，动态计算当前节点的绝对位置（通过加上前面节点的长度），并跳过完全在请求范围之前或之后的节点的子节点。

这个基本算法已经奏效，但仍有一些悬而未决的问题：

1. 我们如何确保查询给定范围内的所有括号具有所需的对数性能？
2. 输入时，我们如何避免从头开始构建新的AST？
3. 我们如何处理令牌块更新？当打开一个大文档时，令牌最初不可用，而是分块传入。

确保查询时间是对数级的

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

在下面的例子中，我们必须查看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个子节点有一些自由度

最坏情况复杂度分析

欢迎跳过有关算法复杂度的部分。

目前，我们假设每个列表都类似于一个(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$的节点。如果是这样，则该节点无需重新解析，底层的词法分析器只需前进该节点的长度即可。消耗该节点后，解析继续。请注意，该节点既可以是单个括号对，也可以是整个列表。此外，如果存在多个此类可重用节点，则应选取最长的那个。

下面的例子展示了当插入单个开括号时（省略了单个括号节点）哪些节点可以被重用（绿色）

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

如这个示例所示，平衡列表不仅可以实现快速查询，还有助于一次性重用大量节点。

算法复杂度

欢迎跳过有关算法复杂度的部分。

假设文本编辑替换了一个大小最多为$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）-树属性，橙色节点的高度出乎意料，绿色节点在重新平衡时被重新创建）

由于在不平衡树中列表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$$2^{31}$ 的整数，因此我们可以为行数和列数各使用26位。不幸的是，v8将大于

进一步的困难：未闭合的括号对

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

考虑以下示例：

( [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