括弧のペアの色分けを1万倍高速化

2021年9月29日 Henning Dieterichs 著、@hediet_dev

Visual Studio Code で深くネストされた括弧を扱う場合、どの括弧が一致し、どれが一致しないかを把握するのが難しい場合があります。

これを容易にするために、2016 年に CoenraadS というユーザーが、一致する括弧を色分けする素晴らしい Bracket Pair Colorizer 拡張機能を開発し、VS Code Marketplace に公開しました。この拡張機能は非常に人気となり、現在では Marketplace で最もダウンロードされた拡張機能のトップ 10 の 1 つであり、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 拡張機能は大きなファイルでは遅くなります。42,000 行を超えるコードを持つ TypeScript プロジェクトの checker.ts ファイルの先頭に単一の括弧を挿入すると、すべての括弧のペアの色が更新されるまでに約 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 を追加することで有効にできます。

これで、数十万の括弧のペアを持つファイルでも、更新は気にならなくなりました。42,788 行目の括弧の色が、2 行目に { を入力した直後に新しいネストレベルを反映していることに注目してください。

コアに移行することを決定したら、できるだけ高速にする方法についても検討する機会を得ました。アルゴリズムの課題を嫌う人はいませんよね?

パブリック API 設計による制限を受けずに、(2,3) 木、再帰フリーの木トラバーサル、ビット演算、インクリメンタル解析、およびその他の手法を使用して、拡張機能の最悪の場合の更新 時間計算量 (ドキュメントが既に開かれている場合にユーザー入力を処理するために必要な時間) を次のように削減できました。$\mathcal{O}(N + E)$から$\mathcal{O}(\mathrm{log}^3 N + E)$へ$N$はドキュメントサイズであり、$E$は編集サイズであり、括弧のペアのネストレベルは$\mathcal{O}(\mathrm{log} N)$.

に制限されていると仮定しています。さらに、レンダラーからの既存のトークンとそのインクリメンタルトークン更新メカニズムを再利用することで、さらに大幅な (ただし一定の) 高速化を実現しました。

VS Code for the Web

新しい実装は、パフォーマンスが向上しただけでなく、VS Code for the Web でもサポートされており、vscode.dev および github.dev で実際に確認できます。Bracket Pair Colorizer 2 が VS Code トークンエンジンを再利用する方法により、拡張機能を Web 拡張機能 と呼ぶものに移行することはできませんでした。

新しい実装は VS Code for the Web で動作するだけでなく、Monaco Editor でも直接動作します!

括弧のペアの色分けの課題

括弧のペアの色分けは、ビューポート内のすべての括弧とその (絶対) ネストレベルを迅速に特定することがすべてです。ビューポートは、ドキュメント内の行番号と列番号の範囲として記述でき、通常はドキュメント全体のごく一部です。

残念ながら、括弧のネストレベルは、その前の *すべて* の文字に依存します。任意の文字をオープニング括弧 "{" に置き換えると、通常、後続のすべての括弧のネストレベルが上がります。

したがって、ドキュメントの最後に括弧を最初に色分けする場合、ドキュメント全体のすべての文字を処理する必要があります。

括弧のペアの色分け拡張機能の実装は、括弧が 1 つ挿入または削除されるたびにドキュメント全体を再度処理することで、この課題に対処しています (これは小さなドキュメントでは非常に合理的です)。次に、VS Code Decoration 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[] = "}"; }

3 番目の "}" の出現のみが括弧のペアを閉じます。

これは、JSX を使用した TypeScript など、トークン言語が正規言語ではない言語ではさらに困難になります。

[1] の括弧は [2] または [3] の括弧と一致しますか? これは、テンプレートリテラル式の長さに依存し、無制限の状態を持つトークナイザー (非正規トークナイザー) のみが正しく判断できます。

トークンが救世主

幸いなことに、構文強調表示は同様の問題を解決する必要があります。前のコードスニペットの [2] の括弧を文字列としてレンダリングするか、プレーンテキストとしてレンダリングする必要がありますか?

結局のところ、構文強調表示によって識別されるコメントと文字列内の括弧を無視するだけで、ほとんどの括弧のペアに対して十分に機能します。< ... > は、これまでに見つかった唯一の問題のあるペアです。これらの括弧は通常、比較とジェネリック型のペアの両方で使用されますが、トークンタイプは同じです。

VS Code には、構文強調表示に使用されるトークン情報を維持するための効率的で同期的なメカニズムが既にあり、それを再利用してオープニング括弧とクロージング括弧を識別できます。

これは、パフォーマンスに悪影響を与える Bracket Pair Colorization 拡張機能のもう 1 つの課題です。この拡張機能はこれらのトークンにアクセスできず、独自に再計算する必要があります。私たちは長い間、トークン情報を拡張機能に効率的かつ確実に公開する方法について考えましたが、多くの実装の詳細が拡張機能 API にリークすることなく、これを行うことはできないという結論に達しました。拡張機能はドキュメント内の各括弧の色の装飾のリストを送信する必要があるため、そのような API だけではパフォーマンスの問題を解決することさえできません。

余談ですが、(C のような言語の /* を挿入するなど) 後続のすべてのトークンを変更するドキュメントの先頭で編集を適用する場合、VS Code は長いドキュメントを一度に再トークン化するのではなく、時間をかけてチャンク単位で再トークン化します。これにより、レンダラーでトークン化が同期的に行われても、UI がフリーズしないようにします。

基本的なアルゴリズム

コアのアイデアは、再帰下降パーサー を使用して、すべての括弧のペアの構造を記述する 抽象構文木 (AST) を構築することです。括弧が見つかったら、トークン情報をチェックし、コメントまたは文字列内にある場合は括弧をスキップします。トークナイザーを使用すると、パーサーはこのような括弧またはテキストトークンをピークおよび読み取ることができます。

ここで重要なのは、絶対的な開始/終了位置を保存する代わりに、各ノードの長さのみを保存することです (また、ギャップを埋めるために括弧ではないすべてのものに対してテキストノードを持つこと)。長さのみが利用可能な場合でも、特定の場所にある括弧ノードを AST 内で効率的に見つけることができます。

次の図は、長さアノテーション付きの例示的な AST を示しています。

これを、絶対的な開始/終了位置を使用した従来の AST 表現と比較してください。

両方の AST は同じドキュメントを記述していますが、最初の AST をトラバースする場合、絶対位置はオンザフライで計算する必要があります (これは安価に実行できます) が、2 番目の AST では既に事前に計算されています。

ただし、最初のツリーに 1 文字を挿入すると、ノード自体とそのすべての親ノードの長さのみを更新する必要があります。他のすべての長さは同じままです。

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 をクエリして、ビューポート内のすべての括弧とそのネストレベルをリストするのは比較的簡単です。深さ優先探索を実行し、オンザフライで現在のノードの絶対位置を計算し (以前のノードの長さを加算することにより)、要求された範囲の前または後にあるノードの子を完全にスキップします。

この基本的なアルゴリズムは既に機能していますが、いくつかの未解決の質問があります。

1. 指定された範囲内のすべての括弧のクエリが、目的の対数パフォーマンスを確実に実現するにはどうすればよいでしょうか?
2. 入力時に、AST を最初から構築し直すのを避けるにはどうすればよいでしょうか?
3. トークンチャンクの更新を処理するにはどうすればよいでしょうか? 大きなドキュメントを開くと、トークンは最初は利用できませんが、チャンクごとに提供されます。

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

指定された範囲内の括弧をクエリするときにパフォーマンスを低下させるのは、非常に長いリストです。各ノードの長さを合計してオンザフライで絶対位置を計算する必要があるため、子ノードで高速なバイナリ検索を実行して、関係のない非交差ノードをすべてスキップすることはできません。最悪の場合、それらのすべてを反復処理する必要があります。

次の例では、位置 24 にある括弧を見つけるまでに 13 個のノード (青色) を調べる必要があります。

長さの合計を計算してキャッシュすることでバイナリ検索を有効にできますが、これには絶対位置を格納するのと同じ問題があります。単一のノードが拡大または縮小するたびに、それらすべてを再計算する必要があります。これは、非常に長いリストではコストがかかります。

代わりに、リストに他のリストを子として持つことを許可します。

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 つの子があるかどうかについてはある程度の自由度があることに注意してください。

最悪の場合の複雑さ分析

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

今のところ、すべてのリストが (2,3) 木に似ており、したがって最大で 3 つの子を持つと仮定します。

クエリ時間を最大化するために、次のドキュメントを見てみましょう。$\mathcal{O}(\mathrm{log} N)$多数のネストされた括弧のペア

{
    {
        ... O(log N) many nested bracket pairs
            {
                {} [1]
            }
        ...
    }
}

リストはまだ関与していませんが、[1] にある括弧のペアを見つけるには、すでに$\mathcal{O}(\mathrm{log} N)$多数のノードをトラバースする必要があります。幸いなことに、さらに深くネストされているドキュメントは非典型的であるため、最悪の場合の分析では考慮しません。

次に、最悪の場合に備えて、サイズ$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は次のようになります。11個の再利用可能なノードはすべて、3つのノードB、H、Gを消費することで再利用でき、再作成する必要があったのは4つのノード（オレンジ色）だけであることに注意してください。

この例で示されているように、バランスの取れたリストはクエリを高速化するだけでなく、一度に大量のノードの塊を再利用するのにも役立ちます。

アルゴリズムの複雑さ

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

テキスト編集が最大サイズの範囲を置き換えると仮定しましょう$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 + E)$$\mathcal{O}(\mathrm{log}^2 N)$個のノードを再解析し、$\mathcal{O}(\mathrm{log}^2 N)$

個のノードを再利用できます。

これは更新操作の時間計算量も決定しますが、注意点があります。

ASTをどのように再バランスするのでしょうか？

残念ながら、最後の例のツリーはもはやバランスが取れていません。

再利用されたリストノードを新しく解析されたノードと組み合わせる場合、（2,3）-ツリーのプロパティを維持するためにいくつかの作業を行う必要があります。再利用されたノードと新しく解析されたノードの両方がすでに（2,3）-ツリーであることはわかっていますが、高さが異なる場合があります。そのため、（2,3）-ツリーノードのすべての子は同じ高さである必要があるため、親ノードを単純に作成することはできません。

高さが混在するこれらすべてのノードを効率的に連結して、単一の（2,3）-ツリーにすることはどうすればよいでしょうか？これは、小さいツリーを大きいツリーの先頭または末尾に追加する問題に簡単に還元できます。2つのツリーの高さが同じ場合、両方の子を含むリストを作成するだけで十分です。そうでない場合は、高さ$h_1$の小さいツリーを、高さ$h_2$

の大きいツリーに挿入し、ノードが最終的に3つ以上の子を持つ場合は（（2,3）-ツリーの挿入操作の仕組みと同様に）ノードを分割する可能性があります。これは実行時間が$\mathcal{O}(h_2 - h_1)$であるため、連結したい3つの隣接ノード（, $a$、および$c$）を取得し、であるため、連結したい3つの隣接ノード（$a$$a$と$b$$a$$a$$c$または$b$と$c$のいずれかを最初に連結します（ツリーの高さを上げる可能性があります）。これは、高さの差が小さいペアに応じて異なります。これは、すべてのノードが連結されるまで繰り返されます。追加の最適化として、同じ高さのノードのシーケンスを探し、それらの親リストを線形時間で作成します。

前の例のリストαとγのバランスを取るために、それらの子に対してconcat操作を実行します（赤いリストは（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}^2 N)$$\mathcal{O}(\mathrm{log} N)$個で、最大リスト高は$\mathcal{O}(\mathrm{log}^2 N)$$\mathcal{O}(\mathrm{log}^2 N + E)$（再利用したもの）であり、追加で$\mathcal{O}(\mathrm{log}^2 N + E)$

個のリスト高さ0のノード（再解析したもの）です。$\mathcal{O}(\mathrm{log} N)$高さの異なる2つのノードを連結すると時間計算量が$\mathcal{O}(h_2 - h_1)$$\mathcal{O}(\mathrm{log}^3 N + E)$であり、リスト内の再解析されたすべてのノードは隣接しており、リスト高さが0であるため、更新操作全体の時間計算量は最大で$\mathcal{O}(\mathrm{log}^2 N + E)$

です。ただし、再利用可能なノードを十分に高速に見つけられることが前提です。

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

このタスクには、*編集前位置マッパー*と*ノードリーダー*の2つのデータ構造があります。位置マッパーは、（編集を適用した後）新しいドキュメント内の位置を、（編集を適用する前）古いドキュメント内の位置に可能な場合はマッピングします。また、現在の位置と次の編集の間の長さ（または編集中の場合は0）を教えてくれます。これは、.

$\mathcal{O}(1)$

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

ノードリーダーは、ASTの特定の位置で、与えられた述語を満たす最長のノードをすばやく見つけることができます。再利用できるノードを見つけるために、位置マッパーを使用して古い位置とその最大許容長さをルックアップし、次にノードリーダーを使用してこのノードを見つけます。そのようなノードが見つかった場合、それが変更されていないことを知っており、それを再利用してその長さをスキップできます。

ノードリーダーは単調増加する位置でクエリされるため、毎回最初から検索を開始する必要はありませんが、最後に再利用されたノードの末尾から検索を開始できます。これの鍵となるのは、ノードに深く入り込むだけでなく、ノードをスキップしたり、親ノードに戻ったりすることもできる、再帰のないツリートラバーサルアルゴリズムです。再利用可能なノードが見つかると、トラバーサルは停止し、ノードリーダーへの次のリクエストで続行されます。$\mathcal{O}(\mathrm{log}^2 N)$ノードリーダーに1回クエリを実行する複雑さは最大で$\mathcal{O}(\mathrm{log}^2 N)$$\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が引き継ぎます。

ディープクローニングはドキュメントの再解析とほぼ同じくらいコストがかかるため、コピーオンライトを実装し、位置マッパーは、（編集を適用した後）新しいドキュメント内の位置を、（編集を適用する前）古いドキュメント内の位置に可能な場合はマッピングします。また、現在の位置と次の編集の間の長さ（または編集中の場合は0）を教えてくれます。これは、.

長さのエンコーディング

$\mathcal{O}(1)$

でのクローニングを可能にしました。エディタービューは、行番号と列番号でビューポートを記述します。色の装飾も、行/列ベースの範囲として表現されることが期待されます。$\mathcal{O}(\mathrm{log} N)$オフセットと行/列ベースの位置間の変換を避けるために（これは$\mathcal{O}(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は高性能コードを作成するのに最適な言語ではないかもしれませんが、特に大きな入力を扱う場合、漸近的なアルゴリズムの複雑さを軽減することで、大幅な速度向上が得られます。

Happy Coding!