なぜRust LSPの構築は難しいのか · Rust Glancer

ずっと昔、強力な matklad が Rust ツールチェーンの仕組みについて素晴らしい連載を書いていた。良い時代だったが、rust-analyzer のブログは 2023 年で止まっている。

私は matklad ではないが、実験的な Rust LSP である Rust Glancer をしばらく前から作っている。おそらくこれまでで一番面白く、一番野心的なプロジェクトで、開発中に学んだことをいくつか共有したい。

これは Rust LSP がどう動くかについての（なるべく筋の通った）物語で、rust-analyzer と Rust Glancer の両方の視点から語る。簡単に見えることは実は難しく、難しいに見えることはもっと難しく、存在するとは全く思っていなかったものは実際に存在する。

当然だが、一つのブログ記事ですべてを網羅することはできない。これは非常に技術的でありながら、アーキテクチャ寄りの概観であり、途中で触れる個々の話題を深掘りするものではない。それらは別の記事として公開する——私が怠けなければ。

また、覚悟しておいてほしい。逸話的な章が多く、それらに共通する点が一つある。LSP を作るということは、部分的な情報から有用な答えを出さなければならないということだ。

免責事項：私は LSP を作る専門家ではない。この記事の目的は、LSP の内部機構と落とし穴に読者の興味を持ってもらうことであって、明確で正式な設計の概観を示すことではない。コンパイラ用語は意図的に避け、多くの箇所で近似表現を使い、正確さよりも全体の意味を重視している。より詳細で正確な資料へのリンクを多く貼ってあるので、そちらも読んでほしい。 また、この記事を準備する前とその間、rust-analyzer のコードを大量に読んだが、私は rust-analyzer のメンテナではない。どこか間違っていたら——すみません。

LSP はどこから始まるのか？

LSP サーバーには相反する二つの端点がある。一つはLanguage Server Protocolを実装するサーバー（つまり、「リクエストを送れば整った形式のレスポンスが返ってくる何か」）、もう一つは実際にサービスを提供したい状態（つまり、「送ったクエリが本当にやるべきことをやり、何らかのインデックス済みの状態の上で動いている」）。前者はもう解決済みの問題に見えるだろう？ 特に tower-lsp-server があるのだから。いや、そうではない。ここから始めて、本当にインデックスが必要になった時点でそこへ進んでいく。

LSP はクライアントが initialize リクエストを送るところから始まる。これは LSP を初期化せよという要求だ（うん）。これに応答するまで、クライアントは何もしない。応答すると、クライアントは initialized 通知を送り、すべて順調で、LSP 通信が始まる。

問題は、いつこのリクエストに応答するのかだ。サーバーが起動した直後、手元には何もない。プロジェクトについて何も知らない。このリクエストを受け取って初めて、どのコードベースの話をしているのかがわかる。そしてどんなクエリにも実際に答えるには、それを「index™」する必要がある。インデックスが何を意味するかはまだわからないが、間違いなく大仕事だ。

すべてのインデックスが終わるまでブロックするのか？ それではユーザーは 10 秒、20 秒、50 秒、100 秒の待ち時間を楽しむことになり、エディタはほとんど使えない。選択肢にならない。では即座に始めるのか？ だが、開いているファイルについてやってくる最初のクエリに何を答える？ かえってそこでブロックすることにならないか？ あの恐ろしい「すべてをインデックスする必要がある」問題をどう避ける？

ここでコンパイラと LSP の最初の大きな違いが出てくる。コンパイラにとって「完了」の定義はかなり二値的だ。バイナリはコンパイルに成功するか、しないか。厳密に言えば、コンパイル済みの共有ライブラリやその他のビルド成果物も使えるが、実際には、コンパイラがワークスペースの 716 個の crate のうち 715 個をコンパイルして止まったら、誰だって腹が立つ。LSP は違う。ほぼ即座に有用な結果を出せる。最初のミリ秒で完全な情報を持っている必要はなく、必要なのはできるだけ早くユーザーに何か有用なものを送ることだ。「有用なもの」とは何かを決めればいい。

最初の問いへの答えはこうだ。後続のクエリを処理できるようになる最小限の有用な仕事だけをすればいい。だから rust-analyzer も Rust Glancer も、受け取った設定を検証して応答するだけだ。rust-analyzer は応答の後にワークスペース探索を開始し、Rust Glancer は最初のクエリが来るまで受動的にとどまる。

ハンドシェイクが終わると、本当の見せ場が始まる。最初の実際のクエリが届く。多くの場合、おそらく textDocument/didOpen、textDocument/inlayHint、textDocument/documentSymbol だ。ユーザーが素早く、こちらが運悪ければ、その間に textDocument/didChange が挟まることもある。ここで複雑さが爆発する。

まず、面白い事実。LSP はプロトコルとして、ファイルシステムのことを考えることを想定していない。ファイルシステムはなく、ドキュメントと編集だけがある。もっともだ。ドキュメントはしばしば保存されていないので、その内容を知ることはできない。だが実際はそうではない。ほとんどの言語では、単一のファイル（あるいは開いているファイルの集合）を孤立して解析しても、すぐに意味を失う。

そして地獄がやってくる。LSP は自分こそが唯一の真実の源だという前提で動いているのに、こちらは自分でファイルシステムにアクセスしなければならず、しかもそれを同期的にやらなければならない。おまけに、編集はエディタの外で起きることもあり、クライアントがそのイベントを忠実に通知してくれるとは限らない。だからこそ VFS と「ソース世代」（source generation）、すなわち現在実行中のリクエストに対応するソースコード状態の識別子が必要になる。ファイルシステムへのアクセスと LSP の通知を素朴に組み合わせようものなら、プロジェクト全体が終わりのない競合状態に陥る。そこでプロジェクトのソースをメモリに読み込み、それを VFS として宣言し、あらゆる変更をこの読み込み済みの状態にベストエフォートで適用する。状態が変わるたびにソース世代を更新し、内部状態の一貫性を保つ（そして進行中のクエリが無効になったらキャンセルする）。

「進行中のクエリって何だ？」という声が聞こえる。これが二つ目の面白い事実だ。LSP のクエリを一つ実行するには驚くほどの作業量がかかることがあり、しかもすべてのクエリが平等というわけではない。あるシンボルの参照を探すのはかなり並大抵ではない作業だが、hover は普通は安い。だから一度に一つのクエリだけ処理するという選択肢はなく、読み取りクエリを並列に実行する必要がある。そして状態が一度変われば、実行中のクエリはすでに古くなった状態の上で無駄な計算をすることになる。やるべきことは、変更クエリと非変更クエリを分けるループを組み、読み取りリクエストを並列に走らせ、状態が変わったら作業をキャンセルすることだ。さらに、運悪く async を使っているなら、受信メッセージを直列化して、didOpen と didChange が逆順で届かないようにしなければならない。デバッグが本当に地獄だからだ（なぜこの注意書きを書く必要があるのか、自分でも不思議だ）。

三つ目、そして最後の面白い事実。LSP の作者たちは、あなたがまだ準備できていないかもしれないことを実は考慮していて、それに対処するための便利な道具をいくつか用意してくれている。たとえばサーバーリクエスト workspace/inlayHint/refresh だ。これだけ強力な道具があれば、「おっと、今もう一度試して」と言って、最初は何も送っていなくても_本当の_レスポンスを送り出せる。問題は、何でもかんでもリフレッシュできるわけではないことだ。ドキュメントシンボルは無理だ。すぐに送らなければ、クライアントが自分でまた聞き直そうと決めるまで古いままになる。つまり、クエリによっては別の手を考える必要がある。 だが話が逸れた。クライアントはまだ inlay hints とドキュメントシンボルを待っている。 しかも、こちらはまだ何一つインデックスすらしていない。 どうする？

サーバー、いつでも待機

幸運なことに、ドキュメントシンボルのリクエストに応答するには、インデックスすべきものは実は一つだけだ。現在開いているファイルだ。

これはまさに LSP がすぐ役に立つ完璧な例でもある。このリクエストに応答するには、ファイルをパースするだけでいい。AST（正確には CST だが、これは後で話す）が、そのファイルにどんな構造体、trait、関数、メソッドなどがあるかを教えてくれる。リクエスト処理の途中でオンデマンドにパースしても構わない。

fn foo(a: Bar) {} の中で Bar に対して textDocument/hover を行うのはもう少し厄介だ。何らかの意味解析が必要になる。カーソル下のものがどこから来たのかを知らなければならない。そのためには、まず現在のスコープでどんな項目（構造体、メソッドなど）が使えるのかを把握する必要がある。そのためには定義マップが要る。各 crate とモジュールについて、パース済みの「どこから何が見えるか」のマップを構築する。そして定義マップを得るには、もう一段の lowering が要る。AST/CST のレベルで作業を続けることもできるが、それは楽ではない。おそらく欲しくなるのは項目ツリー、つまり各ファイルで定義された項目に対する自分自身の表現だ。流れはこうなる。各ファイルをパース -> AST/CST から項目ツリーを構築 -> モジュールを解決して定義マップを構築 -> カーソル下に何が見えるか調べる -> 定義マップでそれを探す -> 解決済み項目のドキュメントを取り出す -> 表示する。「カーソル下」とは何かと疑問に思ったなら、いい質問だ、何か美味しいものでも食べて自分を褒めてやろう、これについては後で戻ってくる。今のところ、これはかなりの追加作業だが、まだ何とかなる。

Inlay hints は明らかにもっと厄介だ（関数本体の内部、たとえばローカル変数にホバーする場合も同じ）。それらは関数本体に現れる。fn foo() { let a = bar(); } では、fn foo は項目宣言であり、{ let a = bar(); } こそが本当に恐ろしい関数本体の部分だと言える。上で説明した意味モデルでは、関数本体なんて気にしていないことに注意しよう。それどころか、inlay hints をまともにやるには少なくとも型推論が必要だ。これについては今は展開するのを拒否する。

しかし、これで終わりだと思ったなら、LSP の最終ボスを拝むがいい。textDocument/references だ。inlay hints は単一ファイル内の関数本体を分析すればよかった。references はどうか。VS Code（あるいはなぜか同じショートカットを使っている任意のエディタ）で関数定義に対して無邪気に option+shift+F12 を押すと、哀れなサーバーはワークスペースグラフ全体のあらゆる発見可能な場所から、その関数のすべての使用を見つけ出さなければならない。Option を考えてみよう。何千もの関数本体を猛烈な速さで走査し、しかもその中からまさにこの Option と、Option という名前の他のあらゆる項目を区別しなければならない。ここでさらに大きな問題が生じる。たとえすべての関数本体をすでに分析済みだったとしても、Option にたまたま言及しているものがないか線形に全部見て回りたいとは、まず思わないだろう。そこで LSP 特有の小技が登場する。テキストマッチングで参照検索プランを構築し、まずその識別子を含む可能性のあるファイルの部分集合を絞り込み、そのファイルだけを対象に関数本体を走査する。それでも作業量は大きくなりうる。「参照検索プラン」とは何か知りたければ、rust-analyzer に良い記事がある（偉大なる matlkad に敬意を！）。

補足：もし「うん、まあ、Option には確かに大量のテキストマッチングがあるけど、それは病的なケースでしょ」と思っているなら……LSP の構築はすべてが病的なケースであり、ユーザー体験を台無しにする。だからこそ LSP は難しいのだ。

ここで重要な点が 2 つある：

1. インデックス自体が階層的であり、これらの層が順序をなし、層間の境界はほぼ確定している。
2. クエリによって、精度やコードベースへの理解度に対する要求が異なる。

そして LSP に与えられた自由のひとつが、この情報をどう活用するかである。 rust-analyzer と Rust Glancer はどちらも技術的には parsing / item tree / defmaps / semantic layer / body layer を備えている（ここでは Rust Glancer の用語を使うが、rust-analyzer に詳しい人ならどれがどれかすぐ分かるはずだ）。ただし両者はこれらのデータの計算方法が異なる。 rust-analyzer は salsa を使う。インクリメンタルデータベースだ。入力と、入力から出力を得るロジックを定義でき、出力は遅延評価されメモ化される。入力が変われば、出力のうち関連する部分だけが無効化され再計算される。rust-analyzer のモデルは_エレガント_だ。インデックスというものが存在しない。あるのは入力とコードベースの状態の間の関係網だけであり、いつでも_状態_を問い合わせれば、salsa が計算済みにしてくれる。直接問い合わせたもの以外を「インデックス」する必要はない。正直に言って salsa は魔法のように感じる。馴染みがなければ、数晩かけて学ぶことを強く勧める。それで見える世界が変わる（Durable Incrementality と salsa のドキュメントも参照）。とはいえ salsa があっても、いくつかの小細工は必要だ。すべてのクエリが必要なものだけを計算するなら、メモ化があっても_大量の_状態が計算されないままになり、エディタは最初のうちカクつくかもしれない。そこで rust-analyzer はデフォルトで cache priming を有効にしている（関連するブログ記事はないが、この PR が最新の到達点だ！）。これは基本的にワークスペース全体を semantic layer までインデックスする。その情報はいつでも手元にある可能性が高いからだ。body は本当に必要になるまで待てばいい。 Rust Glancer は違う。重点は低メモリとエディタの瞬時再起動にあり、この 2 つは互いに補い合う。Rust Glancer はできるだけ多くの仕事を積極的にこなし、できるだけ_すべて_を一度にインデックスし、状態をファイルシステムに退避させる。そうすれば初回インデックス以降、計算はほとんど不要になる。だがここでも小細工が要る！完全なインデックスには時間がかかる。そこでまず、Rust Glancer は意味解析の関連部分が完了した時点でクエリへの応答を始める（cache priming を覚えているだろうか？ロジックは似ている）。body については、現在開いているファイルを優先する。rust-analyzer と比べると、初回インデックスに時間がかかり、（現時点では）メモリ消費も多いかもしれない。積極的により多くの仕事をするからだ。だがその後はほぼ終わりだ。何かが変われば、関連する部分だけを更新する。エディタが再起動しても、状態はファイルシステムに残っており、インデックスはほぼ瞬時に完了する。完全な再インデックスが必要になるのはごく少数のケースだけだ（ワークスペースグラフが変わったときなど）。 クエリの話に戻ろう。我々の LSP は今や、提供したい状態を確かに持っている。その状態は準備完了か、そうでないかのどちらかだ。エンジンがまだ準備できていなければ、不正確でもできるだけ役立つ答えを返し、多くの場合、状態の計算が完了した後にクライアントへ結果をリフレッシュするよう要求できる。 LSP とはこういうものだ！読んでくれてありがとう！だがしかし……

ひとつのワークスペース、ふたつのワークスペース

第一章の「(ワークスペース？)」に気づいたはずだし、あの時から、なぜ開いたフォルダが単一の Rust ワークスペースに対応するかのように書いたのか疑問に思っていたことだろう。もちろんそんなわけはない。開いたフォルダには 5 つのフォルダが入っているかもしれず、そのうち 3 つが Rust ワークスペースで 2 つはそうでない。開いたフォルダが、あるワークスペース内の 1 つの crate であることもある。開いたフォルダに Rust ファイルが 1 つあるだけで、Rust crate ですらないこともある。前章は実は先へ飛びすぎた。出発点に戻って考え直す必要がある。

まず簡単な問いから始めよう。LSP はどうやって起動され、起動後にプロジェクトが何であるかをどう判断するのか？答えはクライアントから来る。これは明白だ。クライアントを自分で制御できるなら、自分で記述すればいい。たとえば、現在のフォルダに Cargo.toml ファイルが必ずあると規定できる。あるいは、任意の直接の子フォルダに Cargo.toml ファイルが含まれうると規定できる。rust-analyzer はそうしている。ならば N 個のワークスペースを含むフォルダを開けば、それらはすべて見つかりインデックスが始まる。さらに踏み込むこともできる。再帰的にスキャンして、ワークスペースフォルダの中にさらにワークスペースがあるか調べるのだ（たとえば親ワークスペース Cargo.toml の下の exclude にある場合）。これは極端なバージョンで、rust-analyzer はそうしない。

逆の問題もある。フォルダに確かに Rust ファイルがあるが、Cargo.toml がない場合はどうする？*.rs ファイルを開くと、クライアントはそれでも LSP を起動しようとするかもしれない。どうする？ひとつの戦略は cargo locate-project でルートディレクトリを探し（存在すれば）、そのルートがこのディレクトリの外にあってもコードベースをインデックスするというものだ。だがユーザーは_それを望んでいる_のか？特定のフォルダを開いたのは、完全な分析を_望まない_からかもしれない。

同様に、複数のプロジェクトを含むフォルダを開いたとき、ユーザーはそれらすべてが検出され、解析されることを_望んでいる_のだろうか？望むこともある。新しいプロジェクトを開いたのに、1時間前に IDE を開いていたはずなのにインデックスされていない、というのは確かに腹が立つ。望まないこともある。重量級のプロジェクトが8つ入ったフォルダを開いた途端、LSP がすべてを並行してインデックスし始めて CPU ファンが唸り出す、というのも腹が立つ。

コンパイル / 実行 cargo check とは違う。あれはユーザーの明確なリクエストだ。LSP 側ではユーザーの意図ははっきりしない。フォルダを開いただけで、どちらの挙動を望んでいるか明示していない。だからここに正解はなく、プロジェクト作者の判断があるだけだ。

rust-analyzer はワークスペース検出に対してできる限り積極的で、キャッシュのウォームアップを有効にしていれば、その効果はかなり顕著になる。同じように、ユーザー体験を良くするために必要とあらば、プロジェクトディレクトリの外にまで出ていく。

Rust Glancer の立場はほぼ正反対だ。Cargo.toml がスコープ内にあることを_要求_して初めて解析を実行し、ユーザーが実際にワークスペースを開くまでインデックスを始めない。おかげでより怠惰で、より厳格だ。ユーザーの代わりに推測せず、与えられた範囲からできるだけ出ないようにする。とはいえ逆に言えば、cargo registry は依然としてチェックする。ポリシーを完全に純粋に保つことは不可能だ。

しかし問題はそれだけではない。フォルダの中に Rust ワークスペースが2つあるとしよう。片方が well-formed で、もう片方がそうでなかったら？奇妙なのは、LSP 自体にはそれらを区別するための道具がほとんど用意されていないことだ。rust-analyzer では、どれか1つのワークスペースが何らかの理由で処理できなくなると、サーバー全体がエラー状態に入り、VS Code のステータスバーに赤く表示される。他の crate がまだ動いているとしても！とはいえ rust-analyzer はすべてのワークスペースを単一プロセスで管理している（これは salsa の利点の一つで、このモデルを自然に見せてくれる）ので、1つの crate が rust-analyzer をクラッシュさせれば、それは全体のクラッシュになる。

Rust Glancer は別の道を行く。LSP サーバー自体は単なるルーターとして扱い、各ワークスペースを独立したプロセス（engine）としてモデル化する。LSP サーバーは必要に応じて engine を起動でき、両者の間には独自の通信プロトコルがあり、どれか1つがクラッシュしても全体はクラッシュしない。副次的な利点はメモリ使用量の削減にも役立つことだ。engine ごとにデータが混ざらないので断片化が減る（ライフタイムの異なる大量のアロケーションはまさにメモリ断片化の源だ）。だが欠点もある。実装は明らかに回りくどく、総じて LSP の設計に反している。状態の報告にもかなり小細工が要る。

ここで得られる教訓は、LSP 自体がよく定義されたプロトコルであっても、実装がどう動きたいか、ユーザーの意図をどう解釈するかを決める余地は十分に残されているということだ。どちらのやり方もそれ自体が正しいとか間違っているとかではない。何を優先するかは自分で決める。そして何が正しいかについて、ユーザーの意見は確かに分かれる。

実は LSP なんて欲しくない

ここまで LSP についてどれだけ面白い事実を学んだだろう？さて、次だ。

LSP は_プロトコル_を定義していて、プロトコルは往々にして奇妙で、特定の領域内の通信に最適化されている。その領域は言うまでもなくエディタだ。バイトオフセットや文字インデックスではなく、行と列で話す。さらに厄介なことに、プロトコルはサーバーが UTF-16 を話せることを要求する。UTF-16 を愛さない人がいるだろうか？

問題は、まず行・列・UTF-16 で作業するのがあまりに不便なことだ。おそらく何らかのプロトコルブリッジ層が欲しくなり、サーバー自体はオフセットと UTF-8 で動かし、プロトコルと実際に通信する境界の近くでだけこれらの値を変換することになる。だがこれは普通のことで、どんなプロトコルに対してもほぼベストプラクティスと言える。アプリケーションのドメインモデルはプロトコルのドメインモデルと同一である必要はなく、両者が同型であれば十分だ。

_しかし_問題が生じる。普段オフセットを使っているなら、それをどうやって行と列に変換するのか？毎回ファイルのテキスト全体を解析し、行で分割し、オフセットを動かすのは、ええと、やや非効率だ。プロトコルのドメインモデルが自分の表現に_必須_ではないとしても、変換を効率的にする道具は依然として必要だ。たとえばファイルごとの行インデックス。rust-analyzer も Rust Glancer もそうしている。

面白いのは、LSP を抽象化しようとしても完全にはできないことだ。結局のところアーキテクチャに染み出してくる。

メタデータはまだ終わらない。ファイルを正しく解析するには、その edition も知る必要がある。そうでなければ gen が識別子なのかキーワードなのか判断できない。つまり、ファイルを本当に孤立して解析することはできない。正しく解析するには、Cargo.toml（あるいは他の形のプロジェクトメタデータ）さえ必要になる。

ご覧のとおり、メタデータへの需要はあらゆる方向から押し寄せる。LSP から、ファイルの内容から、Rust 自身から。ある意味では面白い話で、パースのような単純な操作でさえ状態を持たざるを得ないのだ。

インデックスを掘り下げる

いい加減記事はここまで長くなったのに、インデックスはまだ軽く触れただけだ。本来ならこいつが一番難しい部分なのに。 問題は、インデックスが本当に一番難しい部分だということで、正直に言えば、同じくらいの分量の記事を丸ごとシリーズで一つ書く価値がある。とはいえ LSP の旅に穴を残すわけにもいかないので、ここでは高レベルな概観だけ示しておこう。 まず大事な点。LSP の設計は根本的に違いうるし、インデックスの扱い方も変わりうる。rust-analyzer のブログにもこれについての良い記事がある。要約すると：

• 一つ目：「完全な解析」と「浅い解析」の二段階に分ける方式。完全な解析は大量の内容を調べ、浅い解析は素早くファイル単位で動く。Rust Glancer などのプロジェクトがこれを採用している。
• 二つ目：コンパイラに仕事をさせて、その状態をスナップショットする方式。かなり無理やりだが、最初の Rust LSP である RLS はこう動いていたと言える。ヘッダファイルベースの言語などでは有効だが、Rust では非常に非効率だと判明した。
• 三つ目：インクリメンタル／クエリベースにする方式。あるクエリに答えるのに十分なデータだけを計算させ、それ以外はあまり考えない。rust-analyzer は salsa を使ってこう動いている。

これらの方式が、インデックスをどう実行するかを決める。ただ、インデックスの各段階はどれも大体同じだ。Rust の場合こうなる：

• パース（字句解析もパースの一部だと私は考えている）：入力テキストを CST 表現に変換する。
• item tree の構築：以降のインデックス段階への入力となる情報を抽出する。CST は役に立つが、抽象度が低すぎる。知りたいのは自分がどんな item を持っているか、たとえば「これは struct で、こういうフィールドがあり、このドキュメントコメントがあり、これらの attribute があり、可視性はこうなっている」であって、「struct ノードがあり、ラベル付きの子ノードが N 個ある」ではない。
• definition map の構築：どんなモジュールが存在し、それらは何を含むのか。このモジュールは何をエクスポートするのか。このモジュールから何に到達できるのか（「これは別名でインポートされているので、元の import を解決し、モジュール内で別名として見えるようにしなければならない」も含む）。
• マクロ解決：マクロは面白い。展開するとさらにコードが生まれ、そのコードもまた解析しなければならない。しかもより多くの item、場合によってはモジュールまでスコープに持ち込む。自分自身を展開した後（これ自体に奇妙な癖が山ほどある）、展開が defmap の状態を変えることを保証する必要があるので、マクロ解決を defmap 構築過程のサブ段階にするのが都合がいい。
• item index の構築：item tree を構築した後、各構造体や各 impl ブロックについての表現はできているかもしれないが、それらはどう関係するのか。impl Foo と crate::a::Foo は、それとも crate::b::Foo なのか。ここで「リンク済みの item 状態」を作る段階が必要になる。つまり、どの item が一意なのか、どの impl が何に対応するのか、どの trait impl がどの trait とどの trait 実装者に対応するのか。ここでのインデックス構築は特に重要だ。構造体の item を列挙できることは欠かせないので、理論上は未リンクの item tree でも作業はできるが、効率も悪いし楽しくもない。
• 関数本体の解析。ここまでの内容はどれも関数本体をまったく気にしておらず、役に立つ情報もかなり含んでいるが、プログラムが本当に役立つ部分はまさに関数本体だ。そして関数本体には、すべての文／式／パターンを解析し、すべての束縛（代入される変数など）を割り当て、スコープを宣言し（どの束縛がどこで見えるか）、それらすべてをリンクし、型推論と trait 解決を行う必要がある。後ろの二つこそが恐ろしい部分だ。

インデックスが終わるとき、ワークスペース全体を解析したのであれ、単一のクエリに答えるのに必要な分だけをやったのであれ、最終的に得られるのは_インデックス状態_だ。これはプロジェクトに何が宣言されているかを表し、この変数の型は何か、どんなメソッドが使えるか、この構造にはどのドキュメントを表示すべきか、といったことに答えられるようにする。 肝心なのは、インデックスは必ずしもすべてを一通り見る必要はなく、最終的な形はコードベースから理論上導けるすべての情報ではなく、扱いたいクエリによって決まるということだ。 残念ながら、インデックスは上で述べたようには線形に進まない。defmap を例に取ろう。use bar::baz; use foo::bar; がある場合、最初のパスでは bar がスコープ内にあることしか分からず、その情報で bar をすぐに解決することはできない。use bar::generate_gen_mod; use gen_mod::Foo; generate_gen_mod!(); も同じで、まず generate_gen_mod をスコープに加え、それを展開して gen_mod を加え、gen_mod を解析し、それからようやく use gen_mod::Foo を解決できる。つまりインデックスには「固定ループ」が山ほどある。新しい情報が得られる限り解析を繰り返し、新しい情報がなくなったら（あるいはループ回数を使い切ったら）止める。 関数本体の解析も同じく再帰的だ。関数本体_それ自体_が item、マクロ、impl を含み、それらがまた関数本体を持ち、その中に item、マクロ、impl が入り、以下同様。分かるだろう。各関数本体にも独自の defmap があり、独自の固定ループ、関数本体ローカルな item のインデックス、そしてこの関数本体内の各関数本体の解析がある。 まだある。型推論。trait 解決。すまない、これらは次のブログ記事まで取っておく。ここで話しているのは LSP そのものなので、これらがインデックス状態に追加情報を補うということだけ知っておけば十分だ。 余談は終わり。LSP の各種の癖に戻ろう。

コンパイラだけでは足りない

コンパイラ自身もこうした「索引」をやってのけるし、それ以上のこともする。ただしコンパイラには贅沢な点がある。厳格なのだ。コードが正しくなければ、怒鳴りつけてコンパイルを失敗させればいい。 LSP にはそれができない。IDE の中のコードは正しくないことがよくある。あなたが入力している最中だからだ（まあ、_古いやり方_を使っているならの話だが）。そして LSP の仕事は、それを書き終えるのを手伝うことにある。LSP は「このコードは正しくないか不完全だから解析しない」とは言えない。 そこで冒険はパースから始まる。ユーザーが何を打ち込もうと、パースは_必ず_成功しなければならない。手元の情報だけを頼りに、今の状態をできる限り解釈するしかない。ユーザーがルールを破ることも想定しなければならない。impl ブロックに同名のメソッドが二つあるかもしれないし、スコープに存在しない trait を指す impl があるかもしれないし、単にコードが不完全かもしれない。 パースの話と、なぜ CST が必要なのかについては、すでに誰かが書いている（誰だと思う？そう、また彼だ！）：1、2、3。 だがパースは問題の一部にすぎない。ファイルのパースが成功したら、その不正・曖昧な部分を実際に処理して、役に立つものに変えなければならない。 ファイル末尾にある、ごく普通の fn fo を考えてみよう。やるべきことは、直前のトークンが fn である以上、ユーザーの意図はおそらく関数宣言だろうと気づくことだ。そうすれば、引数のプレースホルダと空の本体を持つ関数宣言を生成するスニペットを提案できる。ある item がスコープにない場合でも、候補を見つけて import の追加を提案できるかもしれない。要するにそういうことだ。 これが LSP のもう一つの原則だ。今の状態が_正しくない_こと、そして_改善できる_ことを考慮に入れなければならない。どこまでできるかは、あなたの想像力次第だ。ここでもまた、正しいコードという厳格な世界で働くのではなく、ユーザーの意図を推測しているのだ。

しかし、これで終わりではない！扱うのは不正なコードだけではない。ユーザーはコンパイラだけを使うわけではない。cargo も rustdoc も使うし、Markdown でドキュメントも書く。ツールの作者としては、cargo の JSON 出力をパースして診断情報を取り出す方法を知っていなければならないし、rustdoc が曖昧性解消子をサポートしていることも覚えておかなければならないし、ユーザーのテストを抽出して実行できる必要もある。 これは深さの拡張というより、広さの拡張だ。ユーザーが使うツールを考慮に入れ、全体の流れが「スムーズ」に感じられ、LSP が「勝手にやってくれる」ようにするために必要な作業をすべてこなす。

Cursor：LSP の神

ここまでで、LSP サーバ、索引の状態、そしてツールチェーンに関する追加の知識が揃った。そろそろ LSP の核心に触れる時だ。cursor である。エディタで行うことはすべて cursor を中心に回っている。ファイル内で LSP が応答すべき位置のことだ。マウスカーソルかもしれないし（hover を起こすなど）、入力位置かもしれない（補完を起こすなど）。

面白いのはここからだ。「この位置の hover 情報／補完が欲しい」から「この位置は一体何なのか」へ、どうやってたどり着くのか？

いつも通り、matklad が良い記事を書いている。rust-analyzer がカーソル下のシンボルをどう見つけるかについてだ。手短に言えば、rust-analyzer は意味要素の syntax node をマッチさせて由来を特定する。これは遅延解析のアプローチや、リファクタリングを parser の基盤の上に築くやり方とうまく噛み合っている（少なくとも私の理解では）。

面白いことに、Rust Glancer はここでほぼ正反対の立場に立つ。あの記事によれば、span ベースのやり方は a) 遅すぎる。LSP は解析をできるだけ少なくしようとするからだ。b) リファクタリングにとってもそれほど便利ではない。暗黙の c) として、解析結果はまだ計算されていないかもしれないが、現在のファイルの構文木は常に手元にある。Rust Glancer は逆を行く。デフォルトで完全な解析を行い、結果をファイルシステムに書き出し、その一方でメモリを空けるために構文木を積極的に追い出す。完全な意味解析が手元にあれば、span ベースのやり方も階層構造と組み合わせてなかなかうまく機能する。たとえば、まず一致しないファイルをふるい落とし、次にカーソル位置を覆わない body をふるい落とし、それから body の中身を走査して、span が最も正確なソースシンボルを見つける。こうするとリファクタリングの利点は得られないので、Rust Glancer はリファクタリングを専用のアルゴリズム群として実装している。rowan のようなものには頼らない。優雅さはずっと劣るが、どうやらそれなりに動いているらしい。ちなみに、リファクタリング は重要ではあるものの、実装ロジックに占める割合は意外と少ない。それが全体アーキテクチャの基盤になるべきなのか、私には今もよく分かっていない（Rust Glancer の用途においては、の話だが。もちろん各プロジェクトが自分で決めればいい）。

だがこれは問題の半分にすぎない。自分がどこにいるか が分かっても足りないことがある。最も典型的な例が補完だ。自分がどこにいるか が分かったところで、その具体的な文脈で筋の通る候補のリストを出さなければならない。しかも補完が必要な位置のコードは、たいていもともと不完全なので、推測はさらに難しくなる。

補完で関心があるのは、カーソルの下に何があるかというより、カーソルの 周り に何があるかだ。たとえば：

• カーソルはちょうどドットの後ろにあるか？ならばドット補完が必要だ。ドットの前のシンボルの型を判断し、一致するメソッドを探す。
• カーソルはちょうど :: の後ろにあるか？ならば関連項目か use パスか限定パスの可能性があるので、:: の_前_にあるものを見て、場合によっては異なる候補を出す必要がある。
• 構造体の初期化の中か、たとえば User { na$ } か？ならばその構造体からフィールドを取る。User { name: fo$ } なら、一致するローカル変数を取る。
• 空のファイルに f しかないか？ならば fn キーワード（あるいは fn の断片）が当てはまるかもしれない。

実際に作ってみると、これは大量の特殊ケースを支える作業になる。しかもここはいくらでも広げられる。たとえば crate の edition まで考慮に入れて、await キーワードを提案すべきかどうかを決めることもできる。 これもまたユーザーの意図を当てるゲームで、当てる精度が高いほど体験は良くなる。

そういう話ではない

この記事、けっこう長いだろう？　まだまだ書ける。 矛盾した逸話の寄せ集めに見えなければいいのだが、伝えたかったのは、LSP を眺める角度は本当に多く、どの角度から見ても同じことをするのに複数のやり方がある、ということだ。 これはコンパイラや cargo fmt / cargo deny のようなツールとは対照的だ。あちらの_目的_はかなりはっきりしていて、期待される挙動も多かれ少なかれ明確で、設定もできる。ユーザーは自分が何をしたいのか分かった上でこれらのツールを呼び出す。呼び出しそのものが_意図を表現する行為_なのだ。 LSP はもっと推理ゲームに近い。目の前に置かれるのは、正しくないかもしれない状態で、そこからユーザーにとって何が妥当かを推測しなければならない。 難しい。でも面白い！ P.S. Rust Glancer 自体はかなり戦えるので、ぜひ見てほしい。プロジェクトを支援したいと思ったら、star を付けるのもいい（ただし本当に気に入った / 面白いと思った場合に限る！）。あとは twitter でフォローしてほしい（Rust Glancer の告知と新記事はそこで出す。Rust 関連の面白い話もときどき投稿するつもりだ）。金銭的な支援は必要としていないが、Rust 言語そのものには必要なので、Rust Foundation へのスポンサードを強く勧める。