括號配對著色速度提升 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 Token 資訊的存取權限，導致 Bracket Pair Colorizer 擴充功能在大型檔案上速度緩慢：當在 TypeScript 專案的 checker.ts 檔案開頭插入單個括號時，該檔案具有超過 42k 行程式碼，大約需要 10 秒鐘才能更新所有括號配對的顏色。在這 10 秒的處理過程中，擴充功能主機程序會以 100% CPU 執行，並且所有由擴充功能驅動的功能（例如自動完成或診斷）都會停止運作。幸運的是，VS Code 的架構確保了 UI 保持回應，並且文件仍然可以儲存到磁碟。

CoenraadS 意識到此效能問題，並在擴充功能的第 2 版中花費了大量精力來提高速度和準確性，方法是重複使用來自 VS Code 的 Token 和括號剖析引擎。但是，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)$ .

此外，透過重複使用來自轉譯器的現有 Token 及其增量 Token 更新機制，我們又獲得了另一個巨大的（但恆定的）速度提升。

適用於 Web 的 VS Code

除了效能更高之外，新的實作也支援適用於 Web 的 VS Code，您可以在 vscode.dev 和 github.dev 中看到實際運作情況。由於 Bracket Pair Colorizer 2 重複使用 VS Code Token 引擎的方式，因此無法將擴充功能遷移到我們所謂的 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 的 Decoration 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[] = "}"; }

只有第三個出現的「}」會閉合括號配對。

對於 Token 語言不規則的語言（例如具有 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] 中的括號配對？這取決於範本常值運算式的長度，只有具有無界狀態的 Tokenizer（這是一個非正規 Tokenizer）才能正確判斷。

Token 來救援

幸運的是，語法突顯必須解決類似的問題：前一個程式碼片段中 [2] 的括號應轉譯為字串還是純文字？

事實證明，僅忽略語法突顯識別的註解和字串中的括號對於大多數括號配對都非常有效。< ... > 是我們目前發現的唯一有問題的配對，因為這些括號通常既用於比較，也用於泛型型別的配對，同時具有相同的 Token 型別。

VS Code 已經具有有效率的同步機制來維護用於語法突顯的 Token 資訊，我們可以重複使用它來識別左括號和右括號。

這是 Bracket Pair Colorization 擴充功能的另一個挑戰，它對效能產生負面影響：它無法存取這些 Token，並且必須自行重新計算它們。我們長期思考如何有效率且可靠地向擴充功能公開 Token 資訊，但得出的結論是，如果不將大量實作細節洩漏到擴充功能 API 中，我們就無法做到這一點。由於擴充功能仍然必須為文件中每個括號傳送顏色裝飾清單，因此僅靠 API 本身甚至無法解決效能問題。

附帶一提，當在文件開頭套用會變更所有後續 Token 的編輯（例如，為類似 C 的語言插入 /*）時，VS Code 不會一次性重新 Token 化長文件，而是隨著時間推移分區塊進行。這確保了即使 Token 化在轉譯器中同步發生，UI 也不會凍結。

基本演算法

核心思想是使用遞迴下降剖析器來建置抽象語法樹 (AST)，以描述所有括號配對的結構。當找到括號時，請檢查 Token 資訊，如果括號位於註解或字串中，則跳過該括號。Tokenizer 允許剖析器窺視和讀取此類括號或文字 Token。

現在的訣竅是僅儲存每個節點的長度（並且也針對所有非括號的內容使用文字節點來涵蓋間隙），而不是儲存絕對的開始/結束位置。僅使用長度，仍然可以在 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？
我們如何處理 Token 區塊更新？當開啟大型文件時，Token 最初不可用，但會以區塊方式傳入。

確保查詢時間為對數

在給定範圍內查詢括號時，真正破壞效能的是非常長的清單：我們無法對其子節點執行快速二元搜尋以跳過所有不相關的非相交節點，因為我們需要對每個節點的長度求和以即時計算絕對位置。在最壞的情況下，我們需要遍歷所有節點。

在以下範例中，我們必須查看 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$ （先執行，可能會增加樹狀結構的高度），取決於哪一對的高度差異較小。重複此步驟，直到所有節點都串連在一起。作為額外的最佳化，我們會尋找具有相同高度的節點序列，並在線性時間內為它們建立父清單。

為了平衡先前範例的清單 α 和 γ，我們在其子節點上執行 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)$ 。畢竟，節點讀取器只會查詢不受文字編輯影響的位置，且一律會採用從上次重複使用的節點到下一個重複使用的節點之間的最短路徑。因此，我們認為節點讀取器的效率足以不影響更新演算法的執行階段複雜度。

Token 更新

當在不包含文字 */ 的長 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