Rust LSPの構築がいかに難しいか

Rust LSPの構築が難しい理由

ずっと昔、偉大なmatkladはRustのツールがどのように機能するかについて素晴らしい記事を書いていました。それは素晴らしい時代でしたが、残念ながら、rust-analyzerの最新のブログ記事は2023年のものです。

私はmatkladではありませんが、しばらくの間、実験的なRust LSPであるRust Glancerを構築しています。おそらく私が取り組んできた中で最も興味深く野心的なプロジェクトであり、その中で学んだことをいくつか共有したいと思います。

［画像: Introduction meme: "hello, r/rust speaking" - "matklad doesn't write about LSPs anymore" - "then write about LSPs yourself" - "me???"］

これは、（うまくいけば一貫性のある）rust-analyzerとRust Glancerの両方の観点から、Rust LSPがどのように機能するかについての物語になります。簡単に思えることがいかに難しくなり、難しく思えることがさらに難しくなり、そして全く存在しないと思っていたことがどうにかして存在するようになるか、という話です。

明らかに、1つのブログ記事ですべてを網羅することはできません。これは、途中で取り上げられる特定のトピックを深く掘り下げるというよりは、非常に技術的でありながらもアーキテクチャ的な概要になります。それらは、私が怠けなければ、別々の記事として投稿されるでしょう。

そうでなければ、多くの逸話的な章に備えてください。それらに共通する1つのことがあります。LSPを構築するということは、不完全な情報から有用な回答を生成する必要があるということです。

免責事項: 私はLSP構築の専門家ではありません。この記事の目的は、読者にLSPの内部構造や注意点に興味を持ってもらうことであり、曖昧さのない正式な設計概要を提供することではありません。意図的にコンパイラ用語の使用を避け、全体的な意味に焦点を当てるために多くの場所で近似的な表現を使用しています。記事には、より詳細/正確な情報源への多くのリンクがあり、それらをチェックすることをお勧めします！

また、この記事の準備中および準備前にrust-analyzerのコードをたくさん読みましたが、私はrust-analyzerのメンテナーではありません。もし何か間違っていたら、ごめんなさい。

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

LSPサーバーには2つの反対側の端があります。1つはLanguage Server Protocol（つまり、「リクエストを送信して整形式の応答を受け取ることができるもの」）を実装するサーバーであり、もう1つは私たちが提供したい実際の状態（つまり、「送信されたクエリが実際に必要なことを行い、何らかのインデックス化された状態を操作する」）です。前者は解決済みの問題ですよね？特にtower-lsp-serverが存在することを考えると。まあ、そうではありません。そこから始め、実際に必要になるまで徐々にインデックス作成に進みましょう。

LSPは、クライアントがinitializeリクエストを送信することから始まります。これはLSPを初期化する必要があります（ええ）。応答するまで、クライアントは何もしません。応答すると、initialized通知が送信され、すべてがうまくいき、LSP通信が開始されます。

問題は、このリクエストにいつ応答するかということです。サーバーが起動したとき、何もありません。プロジェクトについて何も知りません。このリクエストを受け取って初めて、どのコードベースについて話しているのかがわかります。そして、実際にクエリに答えるためには、それを「インデックス化™」する必要があります。インデックス化が何を意味するのかはまだわかりませんが、それは確かに多くの作業です。

すべてをインデックス化するまでブロックしますか？そうすると、ユーザーはエディタがほぼ使用不能な状態で10〜20〜50〜100秒の待ち時間を楽しむことになります。選択肢ではありません。すぐに開始しますか？しかし、現在開いているファイルに関する最初のクエリに何と答えますか？そこで代わりにブロックされることになりませんか？恐ろしい「すべてをインデックス化する必要がある」問題をどのように回避しますか？

そして、これはコンパイラとLSPの間の最初の大きな違いを明らかにします。コンパイラは完了の定義がかなり二元的です。バイナリ（すみません）はコンパイルされたかされていないかのどちらかです。技術的には、コンパイルされた共有ライブラリやその他のビルド成果物も使用可能ですが、実際にはコンパイラがワークスペースの715/716個のクレートをコンパイルして停止した場合、あなたは迷惑することでしょう。LSPは異なります。私たちはすぐに有用な結果を提供できます。最初のミリ秒で完全な情報を必要とするわけではありません。できるだけ早くユーザーに何か有用なものを送信する必要があります。何が「有用なもの」と見なされるかを決定するだけで済みます。

元の質問への答えは、クエリの処理を可能にするために必要な最小限の有用な作業を行う必要があるということです。したがって、rust-analyzerとRust Glancerの両方とも、提供された設定を検証して応答するだけです。rust-analyzerは応答後にワークスペースの検出を開始するようにスケジュールしますが、Rust Glancerは最初のクエリがヒットするまで受動的であり続けます。

ハンドシェイクが完了すると、本番が始まります。最初の実際のクエリを受け取ります。ほとんどの場合、これらはtextDocument/didOpen、textDocument/inlayHint、およびtextDocument/documentSymbolになるでしょう。ユーザーが熱心で、あなたが運が悪ければ、これらの間にtextDocument/didChangeさえ含まれる可能性があります。そして、複雑さが爆発します。

まず、面白い事実：LSPはプロトコルとして、ファイルシステムについて考えることを望んでいません。ファイルシステムはなく、ドキュメントと編集があるだけです。これは理にかなっています。多くの場合、ドキュメントは保存されていないため、その内容を知ることはできません。ただし、そうではありません。ほとんどの言語では、単一のファイル（または開いているファイルのセット）を孤立して分析することは、比較的早く有用性を失います。

地獄へようこそ：LSPは自分が真実の情報源であると仮定しますが、それでも自分でファイルシステムにアクセスする必要があり、同期的に行う必要があります。さらに面白くするために、編集はエディタの外で発生する可能性があり、クライアントはこのようなイベントの通知にあまり忠実ではないかもしれません。だからこそ、仮想ファイルシステムと「ソース生成」（つまり、現在実行中のリクエスト時にソースコードの状態の識別子）が必要なのです。ファイルシステムへのアクセスとLSP通知を単純に組み合わせようとすると、プロジェクト全体が終わりのない競合状態になります。代わりに、プロジェクトソースをメモリにロードし、それをVFSと宣言し、このロードされた状態の上に任意の変更を適用するように最善を尽くします。状態を変更するたびに、ソース生成を更新します。これにより、一貫した内部状態を維持でき（および無効になったインフライトクエリをキャンセルできます）。

「インフライトクエリとは何ですか？」とあなたは尋ねるでしょう。そして、それは2番目の面白い事実です。LSPクエリの実行は驚くほど多くの作業を伴う可能性があり、すべてのクエリが同じように作られているわけではありません。シンボルの参照を探すのはかなり複雑なタスクですが、hoverは通常安価です。したがって、一度に1つのクエリを実行することは選択肢ではありません。読み取りクエリを並列に実行する必要があります。そして、状態が変更されると、現在実行中のクエリは、現在古くなった状態に対して無駄な作業を行うことになります。あなたの仕事は、変更クエリと非変更クエリを分離し、読み取り要求を並列で実行させ、状態が変更されたら作業をキャンセルするループを作成することです。また、運が悪く非同期を使用している場合は、didOpenとdidChangeが逆の順序で来ないようにメッセージをシリアル化する必要があります。これはデバッグするのが非常に困難な問題になる可能性があります（なぜこのコメントが必要なのか不思議に思います）。

3番目で最後の面白い事実は、LSPの作成者があなたが準備ができていない可能性があることを実際に考慮しており、それに対処するための有用なツール（workspace/inlayHint/refreshサーバーリクエストなど）を提供していることです。そのような強力なツールを使用すると、「おっと、もう一度やり直してください」と言って、最初に何も送信しなかったとしても、実際の応答を送信できます。問題は、すべてをリフレッシュできるわけではないということです。ドキュメントシンボルはできません。すぐに送信しないと、クライアント自体が再度要求する時が来るまで古くなります。これは、一部のクエリでは創造的になる必要があることを意味します。

しかし、私たちは脇道に逸れてしまいました。クライアントはインレイヒントとドキュメントシンボルを待っています。

そして、私たちはまだ何もインデックス化していません。

どうしますか？

サービスとしてのサーバー

幸いなことに、ドキュメントシンボルに答えるためには、本当に1つのことをインデックス化する必要があります。現在開いているファイルです。そして、これは実際にLSPが非常に速く役立つ完璧な例です。この要求に応答するために必要なのは、ファイルを解析することだけです。AST（あるいはむしろCST、しかしそれについては後で）は、どの構造体、トレイト、関数、メソッドなどがあるかをすでに教えてくれます。リクエストの一部としてオンデマンドで実行することもできます。

fn foo(a: Bar) {}のBarに対するtextDocument/hoverは、もう少しトリッキーです。それは意味解析を、少なくとも何らかの形で必要とします。カーソル下のものがどこから来たのかを知る必要があります。そのためには、スコープで利用可能などのアイテム（構造体、メソッドなど）を理解する必要があります。それを行うには、定義マップが必要です。各クレートとモジュールについて、「どこから何が見えるか」を解決したマップです。そして、定義マップを取得するには、さらにレイヤーの低下が必要です。まだAST/CSTレベルで作業できるかもしれませんが、それは便利ではありません。おそらく、各ファイルで定義されたアイテムの独自の表現であるアイテムツリーが欲しいでしょう。したがって、各ファイルを解析し -> AST/CSTからアイテムツリーを構築し -> モジュールを解決して定義マップを構築し -> カーソル下で何が見えるかを確認し -> defmapsを通じてそれを見つけ -> 解決されたアイテムのドキュメントを抽出し -> それを表示する必要があります。カーソル下とは何を意味するのか疑問に思っているなら、素晴らしい質問なので、何か美味しいもので自分を扱ってください、後で戻ってきます。今のところ、それはかなりの追加作業ですが、それでもかなり管理可能です。

インレイヒントは大幅にトリッキーです（カーソルがボディ内にある場合、例えばローカル変数上にある場合も同様です）。それらはボディ内に表示されます。fn foo() { let a = bar(); }では、fn fooはアイテム宣言であり、{ let a = bar(); }は本当の恐ろしい部分ボディであると言えます。上記の意味モデルでは、ボディには全く関心がありませんでした。それだけでなく、良いインレイヒントのためには、型推論が少なくとも必要です。そして今のところ、私は説明を拒否します。

しかし、これで終わりだと思うなら、LSPの最終ボスであるtextDocument/referencesをご覧ください。インレイヒントの場合、1つのファイルのボディを分析する必要があります。参照の場合、VS Code（または何らかの理由で同じキーバインドを持つ他のエディタ）で関数定義で無邪気なoption+shift+F12をヒットすると、貧しいサーバーはワークスペースグラフ全体で発見可能なすべての場所でのその関数のすべての使用を見つける必要があります。Optionを考えてください。私たちは、それらのうちのこの正確なOptionを、Optionという名前の他のアイテムから区別する必要がある、何千ものボディを迅速に通過することについて話しています。そして、これはより大きな問題を引き起こします。たとえすべてのボディが分析済みであっても、Optionという単語が含まれているかどうかを確認するために、それらすべてを線形に通過したくないでしょう。そこでLSP固有のトリックが登場します。テキストマッチングを使用して参照検索計画を構築し、この識別子を含む可能性のあるファイルのサブセットのみを見つけ、そこでボディを通過させる可能性があります。それでもかなりの作業になる可能性があります。参照検索計画とは何か疑問に思っているなら、rust-analyzerにはそれに関する素晴らしい投稿があります（偉大なmatkladに栄光あれ！）。

サイドノート: 「まあ、確かに、Optionは多くのテキストマッチがありますが、それは病的なケースです」と考えているなら... LSPの構築は、ユーザーエクスペリエンスを台無しにする病的なケースのすべてであり、LSPが難しい理由の1つでもあります。

ここで重要なことが2つあります。

1. インデックス作成自体には、 pretty much確立された境界を形成するシーケンスのレイヤーがあります。
2. 異なるクエリは、コードベースに関する異なるレベルの精度/知識を必要とします。

そして、LSPが利用できる自由の1つは、この情報をどのように利用するかです。rust-analyzerとRust Glancerの両方は、技術的には解析/アイテムツリー/defmaps/意味レイヤー/ボディレイヤー（ここではRust Glancerの用語を使用していますが、rust-analyzerに詳しい人はすぐに何が何であるかを理解できると思います）を持っていますが、これらのデータがどのように計算されるかについては異なります。

rust-analyzerはsalsaを使用しています。これは増分データベースです。つまり、入力と入力を出力に転送する方法を定義でき、その後、出力は遅延計算され、メモ化されます。一部の入力が変更されると、出力の関連部分のみが無効になり、再計算されます。rust-analyzerモデルはエレガントです。インデックス作成は全くありません。入力とコードベースの状態の間の関係のネットワークがあり、いつでも状態を要求でき、salsaはそれがあなたのために計算されることを保証します。それ以外に、直接要求されたもの以外のものを「インデックス化」する必要はありません。正直に言うと、salsaは魔法のように感じます。もしそれに慣れていないなら、数晩かけて慣れることを強くお勧めします。あなたは変わるでしょう（Durable Incrementalityとsalsaドキュメントも参照してください）。しかし、salsaがあっても、トリックが必要です。すべてのクエリが必要なものだけを計算する場合、メモ化があっても、計算されていない状態がたくさんあり、エディタは最初に遅く感じられるかもしれません。そのため、rust-analyzerはデフォルトでキャッシュプライミングを有効にします（それに関するブログ記事はありませんが、このPRが最先端です！）。これは基本的に、ワークスペース全体を意味論的レイヤーまでグローバルにインデックス化します。これは、常に手元にあると便利な情報だからです。ボディは本当に必要になるまで待つことができます。

Rust Glancerは異なります。その焦点は低RAMとインスタントエディタ再起動であり、これらは一緒に行きます。Rust Glancerは可能な限り多くの作業を積極的に行いたいと考えており、一度すべてをインデックス化しようとし、その後状態をファイルシステムにオフロードして、初期インデックス化後に多くの計算を行う必要がないようにします。しかし、ここでもトリックが必要です！完全なインデックス化には時間がかかるため、まず、Rust Glancerは意味解析の関連部分が完了次第クエリへの応答を開始します（キャッシュプライミングを覚えていますか？同様のロジックです）。そしてボディについては、現在開いているファイルを優先します。rust-analyzerと比較して、初期インデックス化はより時間がかかり、（現在）より多くのRAMを消費する可能性があります。なぜなら、それは積極的で、より多くの作業を行うからです。しかし、その後は基本的に完了です。何かが変更された場合、関連する部分のみを更新します。エディタが再起動した場合、状態はファイルシステムに存在するため、インデックス化はほぼインスタントになります。完全な再インデックス化は、まれなケース（ワークスペースグラフが変更された場合など）にのみ必要です。

クエリに戻ると、私たちのLSPは現在、提供したい状態を持っており、準備ができているかできていないかのどちらかです。エンジンが準備できていない場合、可能な限り有用な不正確な回答を提供する可能性があり、多くの場合、状態が計算されたら結果をリフレッシュするようにクライアントに依頼できます。

そして、これがLSPの仕組みです！読んでくれてありがとう！ただし...

1つのワークスペース、2つのワークスペース

最初の章の「（ワークスペース？）」を見つけたと確信しており、なぜ開いているフォルダが単一のRustワークスペースであると仮定して書いているのか疑問に思っているはずです。なぜなら、それは確かにそうではないからです。開いているフォルダには5つのフォルダが含まれている可能性があり、そのうち3つはRustワークスペースで、2つはそうではありません。開いているフォルダはワークスペース内のクレートである可能性があります。開いているフォルダには、RustクレートでなくてもRustファイルが含まれている可能性があります。前の章は実際には少し先走りすぎており、図面に戻る必要があります。

簡単な質問から始めましょう。LSPはどのようにアクティブ化され、アクティブ化されたら、プロジェクトが何であるかをどのように決定しますか？それはクライアントから来るのは明らかです。クライアントを制御している場合、自分で説明できます。たとえば、現在のフォルダにはCargo.tomlファイルが必要であると言うかもしれません。または、即時の子フォルダのいずれかにCargo.tomlファイルが含まれている可能性があると言うかもしれません。これはrust-analyzerが行うことです。次に、N個のワークスペースを含むフォルダを開いた場合、それらはすべて検出され、インデックス化が開始されます。さらに進むこともできます。ワークスペースフォルダ内のワークスペースを検出するために再帰的なスキャンを実行します（たとえば、親ワークスペースのCargo.tomlのexcludeの下にある場合）。これは極端なバージョンであり、rust-analyzerはこれを行いません。

反対の問題もあります。フォルダにはRustファイルが含まれていますが、Cargo.tomlはありません。クライアントは、*.rsファイルを開いたときにLSPをアクティブ化しようとする可能性があります。その場合、どうしますか？1つの戦略は、cargo locate-projectを使用してルートを見つけ、存在する場合は、ルートがディレクトリの外にある場合でもコードベースをインデックス化することです。しかし、ユーザーはこれを望んでいますか？おそらく、彼らは完全な分析を望まないために特定のフォルダを開いたのではないでしょうか？

同様に、複数のプロジェクトを含むフォルダを開いた場合、ユーザーはそれらすべてが検出され分析されることを望んでいますか？時にはそうです。新しいプロジェクトを開いて、1時間前にIDEを開いたにもかかわらずインデックス化されていないのを見ると迷惑かもしれません。時にはそうではありません。8つのヘビー級プロジェクトを含むフォルダを開いて、LSPがすべてを並列でインデックス化し始めたためにCPUファンが唸るのを聞くのは迷惑かもしれません。

コンパイル/cargo checkの実行とは異なり、これは明示的なユーザーリクエストですが、LSPでのユーザーの意図は明確ではありません。彼らは単にフォルダを開いただけであり、必ずしもある動作または別の動作を望んでいることを示していません。したがって、正しい答えはなく、プロジェクト作成者の決定があります。

rust-analyzerはワークスペース検出において積極的であろうとします。そして、キャッシュプライミングが有効になっている場合、それはかなり顕著になる可能性があります。同様に、それは役立とうとし、ユーザーにとって良い体験を提供するために必要な場合はプロジェクトディレクトリの外に出ます。

Rust Glancerはここでほぼ反対の立場をとります。分析を実行するにはCargo.tomlがスコープ内にある必要があり、実際に開くまでワークスペースのインデックス化を開始しません。これは、ある意味で、より怠惰で厳格になります。ユーザーの推測をしようとせず、ユーザーが提供したスコープの外に出ないようにします。それでも、反論は可能です。それでもcargoレジストリをチェックします。ポリシーが完全に純粋であるとは限りません。

しかし、問題はここで終わりません。フォルダに2つのRustワークスペースがあると想像してください。1つは正常に形成されており、もう1つはそうでない場合はどうなりますか？奇妙なのは、LSP自体があまりツールを提供しておらず、これらを区別する方法がないことです。rust-analyzerでは、1つのワークスペースでも何らかの理由で処理できない場合、サーバー全体がエラー状態に入り、VS Codeのステータスパネルで赤く表示されます。他のクレートが機能していてもです！しかし、rust-analyzerはまだすべてのワークスペースを管理するために単一のプロセスを使用しています（そしてそれはsalsaのもう1つの良い特性であり、そのようなモデルを pretty naturalにします）。単一のクレートがrust-analyzerをクラッシュさせると、グローバルにクラッシュします。

Rust Glancerは再び異なるアプローチをとります。LSPサーバー自体は単なるルーターであり、各ワークスペースは個別のプロセス（エンジン）としてモデル化されています。LSPサーバーはオンデマンドでエンジンを起動でき、それら独自の通信プロトコルを持っており、いずれかのエディタでのクラッシュはグローバルなクラッシュを意味しません。ここでのボーナスプロパティは、低メモリ使用量に役立つことです。異なるエンジンのデータは互いに混ざり合わないため、断片化が減少します（さまざまなライフタイムを持つ多くの割り当てがメモリ断片化を引き起こす方法です）。ただし、それ自体にも欠点があります。それは大幅に複雑になり、一般的にLSP設計と戦います。また、状態レポートにはかなりのトリックが必要です。

有用な教訓は、LSP自体が明確に定義されたプロトコルであっても、実装がどのように機能したいか、ユーザーの意図をどのように解釈するかを決定するためのかなりのスペースを与えるということです。どちらのアプローチも本質的に正しくも間違ってもいません。何を優先したいかを決定するのはあなた次第です。そして、ユーザーは*何が正しいかについて異なる意見を持っています。

LSPは望まない

これまでにLSPについていくつの面白い事実を学びましたか？さて、次はこれです。

LSPはプロトコルを定義しており、プロトコルはしばしば奇妙特定のドメイン内での通信に最適化されていることで知られています。そして、そのドメインは明らかにエディタです。バイトオフセットや文字インデックスの terms ではなく、行と列の terms で話します。さらに、プロトコルはサーバーがUTF-16で話せることを知っていることを要求します。UTF-16を愛さない人はいますか？

これの​​問題は、第一に、行、列、UTF-16を扱うことはあまり便利ではないことです。サーバー自体がオフセットとUTF-8で作業できるようにするプロトコルブリッジのようなものが必要になるかもしれませんが、それは pretty normalであり、議論の余地なく、プロトコルに関係なくベストプラクティスです。アプリケーションのドメインモデルは、プロトコルのドメインモデルと同じである必要はありません。それらが同型であれば十分です。

しかし、質問が生じます。オフセットを通常どおりに作業する場合、それらを線と列にどのように変換しますか？ファイルの完全なテキストを解析し、それを線に分割し、オフセットをシフトする必要があるのは、うーん、わずかに非効率的です。プロトコルドメインは、表現内に必ずしも必要ではありませんが、変換を効率的に行うためのツールが必要です。たとえば、ファイルごとに線インデックスを作成することによって。rust-analyzerとRust Glancerの両方がそれを行います。

ここで面白いのは、LSPを抽象化したい場合でも、完全に抽象化することはできないということです。それはあなたのアーキテクチャに漏れ込みます。

そして、「添付されたメタデータ」はそれだけではありません。分析と読み取りクエリに加えて、LSPは編集にも使用されます。通常、それらはインポートを処理したり、スニペットを持ったり、修飾パスをインポートに置き換えたり、不足しているトレイトメンバーを実装したりするコードアクションをサポートしたりできます。そして、そのような編集にはしばしば何が含まれますか？改行！しかし、どれ？Windowsでは常に であり、Unixでは常に であると仮定することはできません。推測しないと、一貫性のない編集を行うことになります。これは、線インデックスに加えて、その特定のファイルで使用されている改行の種類を検出して保存する必要があることを意味します。ちなみに、別のリファクタリングツールであるrustfmtもそれを考える必要がありますが、ファイル全体を書き直すため、粒度の細かい編集ではなく、その動作を自動（検出）、Unix、Windows、またはネイティブ（OSデフォルト）のいずれかに設定できます。

そしてメタデータはさらに続きます。ファイルを正しく解析するには、そのエディションを知る必要もあります。そうでなければ、genが識別子なのかキーワードなのかを知ることができません。これは、ファイルを孤立して分析できないことを意味します。ファイルを正しく解析する方法を知るために、Cargo.toml（または他の種類のプロジェクトメタデータ）が必要です。

ご覧のとおり、メタデータの需要はあらゆる方向から来ています。LSP、ファイルコンテンツ、Rust自体です。ある意味では、解析という単純な操作でさえ状態を持つ必要があるのは面白いです。

インデックス化はいつ

OK、OK、これは長い記事であり、インデックス化という最も難しい部分にようやく触れただけです。

事実は、インデックス化は確かに最も難しい部分であり、正直に言って、それ自体で同様のサイズの記事のシリーズに値します。しかし、LSPの旅にギャップがないように、高レベルの概要を把握しましょう。

まず、重要な点：LSPは根本的に異なる設計を持つことができ、インデックス化へのアプローチが異なる場合があります。繰り返しになりますが、rust-analyzerのブログにはこれに関する良い投稿があります。要するに：

• 1つ目： "フル分析"と"シャロー分析"のフェーズを持ちます。フル分析は多くのものをチェックし、シャロー分析は高速でファイルごとに機能します。これはRust Glancerなどが採用しているアプローチです。
• 2つ目：コンパイラを利用して作業を行い、その状態をスナップショットします。これはいくらか無理があるかもしれませんが、最初のRust LSPであるRLSはこのように動作したと言えるでしょう。このアプローチは一部の言語、特にヘッダーベースの言語では機能しますが、Rustでは非常に非効率的であることが証明されています。
• 3つ目：増分/クエリベースにします。LSPがクエリに答えるのに十分なデータだけを計算し、それ以外のことはあまり考えないようにします。これがrust-analyzerがsalsaの力で動作する方法です。

これらのアプローチはインデックス化がどのように実行されるかを定義します。しかし、インデックス化のフェーズは pretty much同じになるでしょう。Rustの場合、それは：

• 解析（字句解析は解析の一部と見なします）：入力テキストを取得し、CST表現に変換します。
• アイテムツリー構築：後続のインデックス化フェーズの入力として機能する情報を抽出します。CSTは便利ですが、レベルが低すぎます。アイテムが何であるかを知りたいのです。たとえば、「これはフィールド、このドキュメント文字列、これらの属性、およびフィールドを持つ構造体であり、この可視性を持っている」ということです。一方、「N個のタグ付き子を持つ構造体ノード」ではありません。
• 定義マップ構築：どのモジュールが存在し、それらは何を含んでいますか？このモジュールから何がエクスポートされていますか？このモジュールから何が到達可能ですか（これには、「これはエイリアスとしてインポートされているので、この元のインポートを解決し、モジュール内でエイリアスとして表示できるようにする必要があります」が含まれます）。
• マクロ解決：マクロは興味深いです。それらはさらにコードに展開され、それも分析する必要があります。さらに、それらはスコープにさらに多くのアイテムやモジュールをもたらす可能性があります。それ自体を展開した後（それ自体に多くの奇妙な点があります）、展開がdefmapの状態を変更したことを確認する必要があります。これにより、マクロ解決をdefmap構築プロセス自体のサブフェーズにすることが便利になります。
• アイテムインデックス構築：アイテムツリー構築後、各構造体と各implブロックの表現を持っているかもしれませんが、それらはどのようにリンクされていますか？impl Fooはcrate::a::Fooに関連していますか、それともcrate::b::Fooに関連していますか？「リンクされたアイテム状態」（私たちが持っているユニークなアイテム、どのimplがどれに対応するか、どのトレイトimplがどのトレイトとトレイト実装者に​​対応するか）を作成するフェーズが必要です。ここでインデックスを構築することは特に重要です。構造体のアイテムを列挙できることは不可欠なので、理論的にはリンクされていないアイテムツリーで作業できるかもしれませんが、効率的でも快適でもありません。
• ボディ解決。上記のすべてはボディには全く関心がなく、有用な情報のかなりの部分を含んでいますが、プログラムの実際に有用な部分はボディです。そしてボディの場合、すべてのステートメント/式/パターンを解析し、すべてのバインディング（たとえば、割り当てられた変数）を割り当て、スコープを宣言し（どのバインディングがどこで表示されるか）、上記のすべてをリンクし、次に型推論とトレイト解決を実行する必要があります。後者の2つは恐ろしい部分です。

インデックス化の終わりに、ワークスペース全体を分析したか、単一のクエリを処理するのに十分な作業を行ったかに関わらず、インデックス化された状態になります。これは、プロジェクトで宣言されたものの表現であり、この変数がどの型であるか、その変数にどのメソッドが利用可能か、この構造体にどのドキュメントが表示されるべきかなどを答えることができます。

重要なのは、インデックス化はすべてを通過する必要があるだけでなく、最終的な形状は、コードベースから推測できるすべての理論的な情報ではなく、処理したいクエリによって宣言されるということです。

残念ながら、インデックス化は上記のように直線的ではありません。たとえばdefmapsを考えてみましょう。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を解決できるようになります。したがって、インデックス化はかなりの「固定ループ」を使用します。より多くの情報が得られる間、分析を繰り返し実行し、新しい情報がなくなる（またはループ制限が使い果たされる）と作業を停止します。

同様に、ボディ分析はある程度再帰的です。ボディ自体にはアイテム、マクロ、implが含まれる可能性があり、それらはボディを含むアイテム、マクロ、implを持つ可能性があり、それらは...ご理解のとおりです。各ボディは、独自のdefmapと独自の固定ループ、ボディローカルアイテムのインデックス、およびこのボディ内のボディの分析も取得します。

そして、はい。型推論。トレイト解決。すみません、これは次のブログ記事まで謎のままです。ここではLSP自体について話しているので、これら2つがインデックス化された状態に追加情報を提供することを知っていれば十分です。

間奏曲は終わり、LSPの奇妙な点に戻ります。

コンパイラであるだけでは不十分な場合

コンパイラ自体は上記の「インデックス化」などを行います。しかし、それは厳格であるという贅沢を持っています。コードが正しくない場合、それはあなたに怒鳴りつけてコンパイルを失敗させることができます。

LSPはそうできません。IDEのコードは、あなたがそれを入力している（まあ、昔ながらの方法でやっている場合）ため、非常にしばしば間違っています。そしてLSPはそれを完成させるのを助けることを目的としています。LSPは「このコードは分析しません。間違っているか不完全です」と言うことはできません。

したがって、冒険は解析から始まります。解析は、ユーザーが入力した内容に関わらず成功しなければなりません。そして、手元にある情報に基づいて状態を解釈しようと努めなければなりません。また、ユーザーがルールを破ると仮定する必要があります。implブロック内に同じ名前のメソッドが2つある可能性があります。スコープに存在しないトレイトのimplがある可能性があります。または、コードが単に不完全である可能性があります。

解析ビットとCSTの必要性については、あなたが推測した人（はい、またです！）によってすでに書かれています。1、2、3。

しかし、解析はその問題の一部にすぎません。ファイルを正常に解析したら、実際には誤り/曖昧さを処理し、それを有用なものに変換する必要があります。

ファイルの末尾にある完全に正常なfn foを考えてみてください。私たちがする必要があるのは、前のトークンがfnだったので、関数を宣言する意図があった可能性が高いことを認識し、パラメータのプレースホルダーと空のボディを持つ関数宣言を生成するスニペットをすでに提案できることです。スコープにアイテムが存在しない場合でも、可能な候補を見つけてインポートを追加することを提案できます。アイデアは得られたでしょう。

したがって、LSPのもう1つの規範は、状態が現時点では間違っている可能性があり、改善できると考える必要があるということです。どこまで行くかはあなたの想像力次第です。ここでも、正しいコードの厳格な世界で作業するのではなく、ユーザーの意図を推測しようとしています。

しかし、それだけではありません！間違ったコードを扱うだけでなく、ユーザーはコンパイラだけでなく、cargo、rustdocなども使用します。ドキュメントをmarkdownで記述します。ツール作成者として、診断を抽出するためにcargo JSON出力を扱う方法を知る必要があり、rustdocがあいまい解消子をサポートしていることを覚えておく必要があります。ユーザーのテストを抽出して実行できるようにするなど、その他もろもろです。

これは深さの拡張というよりは幅の拡張です。ユーザーが使用するツールについて考える必要があり、フローが「流暢」に感じられ、LSPが「ちょうどそのことをする」ようにするために必要なすべてを行う必要があります。

カーソル：LSPの神

これで、LSPサーバー、インデックス化された状態、およびツールの追加知識のセットができました。ついにLSPの中心部分、カーソルに触れる時が来ました。

エディタで行うことはすべてカーソルに基づいています。これは、LSPからのアクションを必要とするファイル内の位置です。マウスカーソル（ホバー用など）または入力位置（補完用など）である可能性があります。

興味深いのは、「この位置のホバー情報/補完が必要」から「この位置に正確に何があるのか」へとどのように移行するかです。

いつものように、matkladはrust-analyzerでカーソル下のシンボルが見つかる方法について素晴らしい投稿を書いています。要するに、rust-analyzerは構文ノードを意味要素にマッチさせることに基づいてソースを探します。これは、遅延分析アプローチやリファクタリングのためのパーサーインフラストラクチャへの依存（少なくとも私の理解では）と非常によく機能します。

面白​​いことに、Rust Glancerはここでほぼ反対の位置をとります。記事は、スパンベースのアプローチはa）LSPが可能な限り少ない分析を行おうとするため、遅すぎ、b）リファクタリングには不便であると述べています。示唆されているc）は、分析が計算されていない可能性があるが、現在のファイルの解析ツリーは常に利用可能であるということです。Rust Glancerでは、逆が真実です。デフォルトで完全な分析を行い、それをファイルシステムにオフロードし、メモリを解放するために構文ツリーを積極的に追い出します。完全な意味分析を手元に置くと、スパンベースのアプローチは階層構造と組み合わせて pretty well機能します。たとえば、最初に不一致のファイルをフィルタリングし、次にカーソル位置に触れないボディをフィルタリングし、次にボディの内容を反復処理して最も正確なスパンを持つソースシンボルを探すことができます。リファクタリングの利点はありません。そのため、Rust Glancerは、rowanのようなものに依存しない一連の専用アルゴリズムとしてリファクタリングを実装しています。これは大幅にエレガントではありませんが、pretty well機能しているようです。さらに、リファクタリング部分は、非常に重要でありながら、実装ロジックのそれほど多くを占めていません。全体的なアーキテクチャの基礎に置くべきかどうかはまだわかりません（Rust Glancerの目的のため。各プロジェクトは明らかに自分で決定できます）。

しかし、それは問題の半分にすぎません。時々、どこにいるのかを理解するだけでは不十分であり、最も重要な例は補完です。どこにいるのかを理解したら、その特定のコンテキストで意味のある提案のリストを作成する必要があります。そして、補完が必要な位置で通常起こるように、コードはおそらく不完全であり、推測を少し難しくします。

補完の目的で、カーソルの真下にあるものよりも、カーソルの周りにあるものに関心があります。たとえば：

• カーソルはドットの直後ですか？次に、ドットの前のシンボルの型を理解し、一致するメソッドを見つけるドット補完が必要です。
• カーソルは::の直後ですか？次に、関連アイテム、使用パス、または修飾パスである可能性があります。そのため、::の前に何が来るかを確認し、場合によってはさまざまなオプションを提案する必要があります。
• 構造体初期化子の中にいますか？例：User { na$ }。この構造体からフィールドを取得します。または、User { name: fo$ }の場合は、一致するローカルを取得します。
• 空のファイルで単にfですか？次に、fnキーワード（またはfnスニペット）が適用される可能性があります。

実際には、これはサポートしたい特別なケースの山になります。そして、あなたはここで好きなだけ創造的になることができます。たとえば、クレートのエディションを考慮して、awaitキーワードを提案するかどうかを決定できます。

ここでも、ユーザーの意図を推測するゲームになります。そして、あなたがそれをうまくやればやるほど、ユーザーはより良い体験を得られます。

それは終わりではありません

これは長い記事ですよね？そして、もっと長く続けることもできます。

これが一貫性のない逸話のセットのように見えないことを願っています。なぜなら、意図は、LSPを見ることができる角度が多すぎること、そして各角度が物事を行うための複数のアプローチを持つ可能性があることを示すことだったからです。

これは、コンパイラやcargo fmt / cargo denyのようなツールとは pretty big contrast を生み出します。それらは目標において pretty deterministic であり、意図された動作は pretty much明確で設定可能です。ユーザーがこれらのツールを呼び出すとき、彼らは自分が何を必要としているかを正確に知っており、呼び出しは意図を示す行為です。

LSPは推測ゲームのようなもので、各ステップで提示されるのは不完全な状態であり、ユーザーにとって何が意味をなすかを推測することが目標です。

それは難しいです。しかし、楽しいでもあります！

P.S. Rust Glancer自体はすでにかなり有能です。チェックしてみてください！プロジェクトをサポートしたい場合は、スターを付けることを検討してください（ただし、本当に気に入った/興味深いと思った場合のみ！）。そして/または私をTwitterでフォローしてください（Rust Glancerの発表と新しい投稿を投稿します。また、Rustに関する興味深いものを時々投稿する予定です）。金銭的なサポートは私には必要ありませんが、Rust言語自体には必要なので、代わりにRust Foundationにスポンサーになることを強くお勧めします。