括號對彩色化速度提升 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 專案的 checker.ts 檔案（該檔案有超過 42k 行程式碼）的開頭插入一個括號時，直到所有括號對的顏色更新完成大約需要 10 秒。在這 10 秒的處理過程中，擴充套件宿主程序的 CPU 佔用率高達 100%，所有由擴充套件支援的功能，如自動完成或診斷，都停止工作。幸運的是，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 核心中重新實現了該擴充套件，並將此時間縮短到不到一毫秒——在這個特定示例中，這比之前快了 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 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 已經擁有一個高效且同步的機制來維護用於語法高亮的令牌資訊，我們可以重用它來識別開括號和閉括號。

這是括號對顏色化擴充套件的另一個挑戰，它對效能產生了負面影響：它無法訪問這些令牌，必須自行重新計算。我們長期思考如何高效可靠地將令牌資訊暴露給擴充套件，但得出結論，在不將大量實現細節洩露到擴充套件 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 中它們已經預先計算好了。

然而，當在第一個樹中插入單個字元時，只需要更新節點本身的長度及其所有父節點的長度——所有其他長度保持不變。

當像第二個樹中那樣儲存絕對位置時，文件中後面**每個**節點的位置都必須遞增。

此外，透過不儲存絕對偏移量，可以共享長度相同的葉節點，以避免記憶體分配。

這就是帶有長度註釋的 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 以列出視口中所有括號及其巢狀級別相對簡單：進行深度優先遍歷，動態計算當前節點的絕對位置（透過新增早期節點的長度），並跳過完全在請求範圍之前或之後的節點的子節點。

這個基本演算法已經可以工作，但仍有一些未解決的問題

如何確保查詢給定範圍內的所有括號具有所需的對數效能？
在打字時，如何避免從頭構建新的 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 (\frac{N}{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)$ ，我們取三個相鄰的節點（ $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