括弧ペアの色付けを10,000倍高速に

2021年9月29日 Henning Dieterichs, @hediet_dev

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

これを容易にするため、2016年にCoenraadSというユーザーが素晴らしいBracket Pair Colorizer拡張機能を開発し、対応する括弧を色付けし、VS Code 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拡張機能は大きなファイルで低速になります。TypeScriptプロジェクトの42k行以上のコードがあるchecker.tsファイルの冒頭に1つの括弧を挿入すると、すべての括弧ペアの色が更新されるまでに約10秒かかります。この10秒間の処理中、拡張機能ホストプロセスはCPUを100%消費し、自動補完や診断などの拡張機能によって提供されるすべての機能が停止します。幸いにも、VS Codeのアーキテクチャは、UIが応答性を保ち、ドキュメントをディスクに保存できることを保証します。

CoenraadSはこのパフォーマンスの問題を認識しており、VS Codeのトークンと括弧の解析エンジンを再利用することで、拡張機能のバージョン2で速度と精度を向上させるために多大な努力を払いました。しかし、VS CodeのAPIと拡張機能アーキテクチャは、何十万もの括弧ペアが関係する場合に高性能な括弧ペアの色付けを可能にするようには設計されていませんでした。そのため、Bracket Pair Colorizer 2でも、ファイルの先頭に{を挿入した後、色が新しいネストレベルを反映するまでに時間がかかります。

拡張機能のパフォーマンスを改善するだけでは不十分であり（確かに、高性能シナリオに最適化されたより高度なAPIの導入が必要になったでしょう）、レンダラーと拡張機能ホスト間の非同期通信は、拡張機能として実装された場合の括弧ペアの色付けの速度を厳しく制限します。この制限は克服できません。特に、括弧ペアの色は、ビューポートに表示されたらすぐに非同期に要求すべきではありません。これは、大きなファイルをスクロールする際に目に見えるちらつきを引き起こすからです。この議論はissue #128465で見つけることができます。

私たちが行ったこと

代わりに、1.60のアップデートで、拡張機能をVS Codeのコアに再実装し、この時間を1ミリ秒未満に短縮しました。この特定の例では、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)$.

で制限されると仮定しています。さらに、レンダラーからの既存のトークンとその増分トークン更新メカニズムを再利用することで、さらに大きな（ただし一定の）速度向上を得ました。

Web 用 VS Code

新しい実装は、より高性能であるだけでなく、Web版VS Codeでもサポートされています。vscode.devやgithub.devで実際に動作を確認できます。Bracket Pair Colorizer 2がVS Codeのトークンエンジンを再利用する方法のため、この拡張機能をいわゆるWeb拡張機能に移行することはできませんでした。

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

括弧ペアの色付けの課題

括弧ペアの色付けは、ビューポート内のすべての括弧とその（絶対）ネストレベルを迅速に決定することに尽きます。ビューポートは、行番号と列番号の観点からドキュメント内の範囲として記述でき、通常はドキュメント全体のほんの一部です。

残念ながら、括弧のネストレベルは、その前にある*すべての*文字に依存します。任意の文字を開き括弧「{」に置き換えると、通常、それに続くすべての括弧のネストレベルが増加します。

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

括弧ペア色付け拡張機能の実装は、単一の括弧が挿入または削除されるたびにドキュメント全体を再度処理することでこの課題に対処します（これは小さなドキュメントでは非常に合理的です）。その後、色はVS CodeのDecoration 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のように、トークン言語が正規表現ではない言語の場合、これはさらに難しくなります。

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

トークンが救いに

幸いにも、構文強調表示も同様の問題を解決しなければなりません。前のコードスニペットの[2]にある括弧は、文字列としてレンダリングされるべきでしょうか、それともプレーンテキストとしてレンダリングされるべきでしょうか？

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

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

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

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

基本的なアルゴリズム

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

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

以下の図は、長さの注釈付きの例示的なASTを示しています。

これを、絶対的な開始/終了位置を使用する古典的なAST表現と比較してください。

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

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

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は次のようになります。再利用可能なノード11個すべてが、ノードB、H、Gを消費することで再利用でき、わずか4個のノード（オレンジ色）のみを再作成する必要があったことに注目してください。

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

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

アルゴリズムの複雑さ$E$テキスト編集が最大$E$のサイズの範囲を、最大

の新しい文字で置き換えると仮定します。また、開き括弧に対応しない閉じ括弧というまれなケースは、今のところ無視します。編集範囲と交差するノードのみを再解析する必要があります。したがって、最大$\mathcal{O}(\mathrm{log}^2 N + E)$

多くのノードを再解析する必要があります（括弧をクエリする時間計算量と同じ理由で）。他のすべてのノードは再利用できます。$\mathcal{O}(\mathrm{log}^2 N)$明らかに、ノードが編集範囲と交差しない場合、その子も交差しません。したがって、編集範囲と交差しないが、その親ノードは交差するノードのみを再利用することを考慮する必要があります（これにより、ノードとその親の両方が編集範囲と交差しないすべてのノードが暗黙的に再利用されます）。また、そのような親ノードは編集範囲によって完全にカバーすることはできません。そうでない場合、そのすべての子が編集範囲と交差します。ただし、ASTの各レベルには、編集範囲と部分的に交差するノードが最大2つしかありません。ASTには最大多くのレベル（ASTの高さによって制限される）があり、各ノードは最大3つの子を持つため、すべての再利用可能なノードは最大$\mathcal{O}(2 \cdot 3 \cdot \mathrm{log}^2 N) = \mathcal{O}(\mathrm{log}^2 N)$

のノードを消費することでカバーできます。したがって、更新されたツリーを構築するには、最大編集範囲と交差するノードのみを再解析する必要があります。したがって、最大多くのノードを再解析し、$\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)-ツリーのプロパティに違反し、オレンジ色のノードは予期しない高さで、緑色のノードはバランスを取りながら再作成されます）。

リスト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)$（再利用したもの）と、追加の編集範囲と交差するノードのみを再解析する必要があります。したがって、最大多くのリスト高さ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スタイル文書の冒頭に/*を挿入すると、文書全体が1つのコメントになり、すべてのトークンが変更されます。

トークンはレンダラープロセスで同期的に計算されるため、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