ブラケットペアのカラー化が10,000倍高速に

2021年9月29日 Henning Dieterichs、@hediet_dev

Visual Studio Codeで深くネストされたブラケットを扱う際、どのブラケットが対応し、どれが対応しないのかを判別するのは難しい場合があります。

これを容易にするため、2016年にCoenraadSというユーザーが、対応するブラケットを色分けする素晴らしい拡張機能「Bracket Pair Colorizer」を開発し、VS Code Marketplaceに公開しました。この拡張機能は非常に人気を博し、現在では600万回以上のインストール数を誇り、Marketplaceでダウンロード数トップ10に入る拡張機能の1つとなっています。

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拡張機能は大きなファイルでは動作が遅くなります。例えば、42,000行以上のコードを持つTypeScriptプロジェクトのchecker.tsファイルの先頭に1つのブラケットを挿入すると、すべてのブラケットペアの色が更新されるまでに約10秒かかります。この10秒間の処理中、拡張ホストプロセスはCPUを100%消費し、自動補完や診断などの拡張機能によって提供されるすべての機能が停止します。幸いなことに、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のコアに再実装し、この時間を1ミリ秒未満に短縮しました。この特定の例では、10,000倍以上の高速化です。

この機能は、設定に`"editor.bracketPairColorization.enabled": true`を追加することで有効にできます。

これにより、何十万ものブラケットペアを持つファイルでも、更新がもはや気にならなくなりました。42,788行目のブラケットの色が、2行目に`{`を入力するとすぐに新しいネストレベルを反映していることに注目してください。

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[] = "}"; }

「}」の3番目の出現のみがブラケットペアを閉じます。

これは、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を走査するときは、絶対位置をその場で計算する必要があります（これは安価です）。一方、2番目のASTではすでに事前計算されています。

しかし、最初のツリーに単一の文字を挿入すると、ノード自体とそのすべての親ノードの長さのみを更新すればよく、他のすべての長さは同じままです。

2番目のツリーのように絶対位置が保存されている場合、ドキュメントの後の*すべての*ノードの位置を増分する必要があります。

また、絶対オフセットを保存しないことで、同じ長さを持つリーフノードを共有してアロケーションを回避できます。

長さの注釈付き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を最初から構築し直すのを避けるにはどうすればよいでしょうか？
トークンチャンクの更新はどのように処理すればよいでしょうか？大きなドキュメントを開くとき、トークンは最初は利用できませんが、チャンクごとに提供されます。

クエリ時間が対数時間であることを保証する

特定の範囲内のブラケットをクエリする際にパフォーマンスを低下させるのは、非常に長いリストです。その場で絶対位置を計算するために各ノードの長さを合計する必要があるため、関連性のない非交差ノードをすべてスキップするための高速な二分探索を子ノードに対して行うことはできません。最悪の場合、それらすべてを反復処理する必要があります。

次の例では、位置24のブラケットを見つけるまでに13個のノード（青色）を確認する必要があります。

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)-木は次のようになります。位置24のブラケットペアを見つけるために、今度は8つのノード（青色）しか見る必要がないこと、またリストが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個のノードすべてが、B、H、Gの3つのノードを消費することで再利用でき、4つのノードだけが再作成された（オレンジ色）ことに注目してください。

Updated AST

この例が示すように、平衡リストはクエリを高速にするだけでなく、大量のノードを一度に再利用するのにも役立ちます。

アルゴリズムの複雑性

アルゴリズムの複雑性に関するセクションはスキップしても構いません。

テキスト編集が最大 $E$ までのサイズの範囲を、最大 $E$ 多数の新しい文字で置き換えるものと仮定します。また、現時点では、対応する開きブラケットがない閉じブラケットのまれなケースは無視します。

編集範囲と交差するノードのみを再パースすればよいです。したがって、最大でも $\mathcal{O}(\mathrm{log}^2 N + E)$ 多くのノードを再パースする必要があり（ブラケットのクエリの時間計算量と同じ推論）、他のすべてのノードは再利用できます。

明らかに、ノードが編集範囲と交差しない場合、その子ノードも交差しません。したがって、編集範囲と交差しないが、親ノードは交差するノードの再利用のみを考慮すればよいです（これにより、ノードとその親の両方が編集範囲と交差しないすべてのノードが暗黙的に再利用されます）。また、そのような親ノードは編集範囲によって完全にカバーされることはありません。そうでなければ、そのすべての子が編集範囲と交差することになります。しかし、ASTのすべてのレベルには、編集範囲と部分的に交差するノードが最大で2つしかありません。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)-木のすべての子供は同じ高さでなければならないため、単に親ノードを作成することはできません。

これら様々な高さのノードすべてを、効率的に1つの(2,3)-木に連結するにはどうすればよいでしょうか？

これは、より小さい木をより大きい木の前または後に付加する問題に容易に還元できます。2つの木が同じ高さであれば、両方の子供を含むリストを作成するだけで十分です。そうでない場合、高さ $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のノード（これらは再パースされたノード）があります。

異なる高さの2つのノードを連結する時間計算量は $\mathcal{O}(\mathrm{log} N)$ であり、リスト内の再パースされたすべてのノードは隣接しておりリスト高さが0であるため、更新操作全体の時間計算量は最大で $\mathcal{O}(\mathrm{log}^3 N + E)$ となります。ただし、再利用可能なノードを十分に高速に見つけることができるという条件付きです。

再利用可能なノードを効率的に見つけるにはどうすればよいでしょうか？

このタスクには2つのデータ構造があります。*編集前位置マッパー*と*ノードリーダー*です。

位置マッパーは、新しいドキュメント（編集適用後）での位置を、可能であれば古いドキュメント（編集適用前）での位置にマッピングします。また、現在の位置から次の編集までの長さ（編集中の場合は0）も教えてくれます。これは $\mathcal{O}(1)$ .

で行われます。テキスト編集を処理してノードをパースする際、このコンポーネントは、再利用できる可能性のあるノードの位置と、そのノードが持ちうる最大長さを教えてくれます。明らかに、再利用したいノードは次の編集までの距離よりも短くなければなりません。

ノードリーダーは、ASTの指定された位置で、与えられた述語を満たす最長のノードを迅速に見つけることができます。再利用できるノードを見つけるために、位置マッパーを使用してその古い位置と許容される最大長さを検索し、その後ノードリーダーを使用してこのノードを見つけます。そのようなノードが見つかった場合、それが変更されておらず、再利用できることがわかるため、その長さをスキップします。

ノードリーダーは単調増加する位置でクエリされるため、毎回最初から検索を開始する必要はなく、最後に再利用されたノードの末尾から開始できます。これの鍵となるのは、ノードに深く入り込むことも、それらをスキップしたり、親ノードに戻ったりすることもできる、再帰なしのツリー走査アルゴリズムです。再利用可能なノードが見つかると、走査は停止し、ノードリーダーへの次のリクエストで続行されます。

ノードリーダーを単一回クエリする複雑さは最大で $\mathcal{O}(\mathrm{log}^2 N)$ ですが、単一の更新操作によって発行されるすべてのリクエストに対する償却複雑度も $\mathcal{O}(\mathrm{log}^2 N)$ であると確信しています。結局のところ、ノードリーダーはテキスト編集の影響を受けない位置に対してのみクエリされ、常に最後の再利用可能なノードから次の再利用可能なノードへの最短パスを取ります。したがって、ノードリーダーは更新アルゴリズムの実行時複雑さに影響を与えないほど効率的であると考えています。

トークン更新

`*/`というテキストを含まない長いCスタイルのドキュメントの先頭に`/*`を挿入すると、ドキュメント全体が単一のコメントになり、すべてのトークンが変更されます。

トークンはレンダラープロセスで同期的に計算されるため、UIをフリーズさせることなく一度に再トークン化を行うことはできません。

その代わりに、トークンは時間をかけてバッチで更新され、JavaScriptのイベントループが長時間ブロックされることがないようにします。このアプローチは全体のブロック時間を削減するものではありませんが、更新中のUIの応答性を向上させます。この同じメカニズムは、ドキュメントの初期トークン化時にも使用されます。

幸いなことに、ブラケットペアASTのインクリメンタル更新メカニズムにより、再トークン化された範囲をそれ自体で置き換える単一のテキスト編集として更新を扱うことで、バッチ処理されたトークン更新を即座に適用できます。すべてのトークン更新が完了すると、ブラケットペアASTは、たとえ再トークン化の進行中にユーザーがドキュメントを編集したとしても、最初から作成されたかと同じ状態にあることが保証されます。

このようにして、ドキュメント内のすべてのトークンが変更されても、トークン化だけでなくブラケットペアのカラー化も高性能になります。

しかし、コメント内に多くの不均衡なブラケットを含むドキュメントの場合、ブラケットペアパーサーがそれらのブラケットを無視すべきだと学習するにつれて、ドキュメント末尾のブラケットの色がちらつくことがあります。

ドキュメントを開いて末尾に移動する際のブラケットペアの色のちらつきを避けるため、初期トークン化プロセスが完了するまで2つのブラケットペアASTを維持します。最初のASTはトークン情報なしで構築され、トークン更新を受け取りません。2番目のASTは最初は最初のASTのクローンですが、トークン更新を受け取り、トークン化が進み、トークン更新が適用されるにつれてますます分岐します。最初は最初のASTがブラケットのクエリに使用されますが、ドキュメントが完全にトークン化されると2番目のASTが引き継ぎます。

ディープクローンはドキュメントの再パースとほぼ同じくらいコストがかかるため、コピーオンライトを実装し、クローン作成を $\mathcal{O}(1)$ .

長さのエンコーディング

エディタービューは、ビューポートを行番号と列番号で記述します。色の装飾も行/列に基づいた範囲で表現されることが期待されます。

オフセットと行/列ベースの位置間の変換（これは $\mathcal{O}(\mathrm{log} N)$ で行えます）を避けるため、ASTにも行/列ベースの長さを使用します。

このアプローチは、行によって直接インデックス付けされるデータ構造（例えば、文字列配列を使用してドキュメントの行コンテンツを記述するなど）とは大きく異なります。特に、このアプローチは行全体および行内での単一の二分探索を行うことができます。

このような2つの長さを加算するのは簡単ですが、場合分けが必要です。行数は直接加算されますが、2番目の長さがゼロ行をまたぐ場合にのみ、最初の長さの列数が含まれます。

驚くべきことに、ほとんどのコードは長さがどのように表現されているかを意識する必要がありません。単一の行に複数のテキスト編集が含まれる可能性があることを考慮する必要があったため、位置マッパーのみが著しく複雑になりました。

実装の詳細として、メモリ圧力を軽減するために、これらの長さを単一の数値にエンコードしています。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