クエリ: デマンド駆動コンパイル

コンパイラの概要で説明したように、Rust コンパイラは（ 2021 年 7 月時点で）従来の「パスベース」の構成から「デマンド駆動」のシステムへ移行している最中です。コンパイラクエリシステムは、rustc のデマンド駆動構成の鍵となるものです。考え方は非常にシンプルです。完全に独立したパス（構文解析、型チェックなど）の代わりに、関数のような一連のクエリが入力ソースに関する情報を計算します。たとえば、 type_of というクエリがあり、これは何らかのアイテムの DefId を与えると、そのアイテムの型を計算して返します。

クエリの実行はメモ化されます。最初にクエリを呼び出したときは計算を行いますが、次回以降は結果がハッシュテーブルから返されます。さらに、クエリの実行は インクリメンタル計算にうまく適合します。大まかな考え方としては、クエリを呼び出したときに、ディスクから保存済みデータを読み込むことで結果が返される場合がある、というものです。¹

最終的には、コンパイラの制御フロー全体をクエリ駆動にしたいと考えています。実質的には、1 つのトップレベルクエリ（compile）があり、クレートに対してコンパイルを実行します。これは次に、そのクレートに関する情報を、終端から順に要求していきます。

たとえば次のようになります。

compile クエリは、codegen-units のリストを取得することを要求するかもしれません（つまり、LLVM によってコンパイルされる必要があるモジュール）。
しかし codegen-units のリストを計算するには、Rust ソースで定義されているすべてのモジュールのリストを返す何らかのサブクエリを呼び出すことになります。
そのクエリは次に、HIR を要求する何かを呼び出します。
これがさらに遡っていき、最終的に実際の構文解析を行うところに到達します。

この構想はまだ完全には実現されていませんが、コンパイラの大きな部分（たとえば MIR の生成）は現在、まさにこのように動作しています。

クエリの呼び出し

クエリの呼び出しは簡単です。 TyCtxt（「型コンテキスト」）構造体は、定義済みの各クエリに対応するメソッドを提供します。たとえば、type_of クエリを呼び出すには、単に次のようにします。

let ty = tcx.type_of(some_def_id);

コンパイラがクエリを実行する方法

では、クエリメソッドを呼び出すと何が起こるのか疑問に思うかもしれません。答えは、コンパイラが各クエリについてキャッシュを保持している、というものです。あなたのクエリがすでに実行済みであれば、答えは簡単です。キャッシュから戻り値を clone して返します（したがって、クエリの戻り値の型は低コストで clone できるようにしておくべきです。必要であれば Rc を挿入してください）。

プロバイダー

しかし、クエリがキャッシュにない場合、コンパイラは対応する プロバイダー関数を呼び出します。プロバイダーは、特定のモジュールで実装され、コンパイラの初期化時に（ローカルクレートのクエリについては）Providers 構造体、または（外部クレートのクエリについては）ExternProviders 構造体のいずれかに 手動で登録される関数です。マクロシステムは両方の構造体を生成します。これらはすべてのクエリ実装のための関数テーブルとして機能し、各フィールドは実際のプロバイダーへの関数ポインターです。

注: Providers と ExternProviders の両方の構造体はマクロによって生成され、すべてのクエリ実装のための関数テーブルとして機能します。これらは Rust のトレイトではなく、関数ポインターフィールドを持つ単なる構造体です。

プロバイダーはクレートごとに定義されます。 コンパイラは内部的に、少なくとも概念上は、すべてのクレートについてプロバイダーのテーブルを保持しています。プロバイダーには 2 つの集合があります。

ローカルクレート（つまり、コンパイル中のクレート）に関するクエリのための Providers 構造体
外部クレート（つまり、ローカルクレートの依存関係）に関するクエリのための ExternProviders 構造体

クエリが対象とするクレートを決定するのは、クエリの種類ではなく、キーであることに注意してください。たとえば、tcx.type_of(def_id) を呼び出したとき、それは def_id がどのクレートを参照しているかに応じて、ローカルクエリにも外部クエリにもなり得ます（これがどのように動作するかの詳細については、self::keys::QueryKey トレイトを参照してください）。

プロバイダーは常に同じシグネチャを持ちます。

fn provider<'tcx>(
    tcx: TyCtxt<'tcx>,
    key: QUERY_KEY,
) -> QUERY_RESULT {
    ...
}

プロバイダーは 2 つの引数、すなわち tcx とクエリキーを受け取ります。そしてクエリの結果を返します。

N.B. rustc_* クレートのほとんどは ローカルプロバイダーのみを提供します。ほぼすべての 外部プロバイダーは、最終的に rustc_metadata クレートを経由します。これはクレートメタデータから情報を読み込みます。ただし場合によっては、ローカルクレートと外部クレートの両方に対してクエリを提供するクレートもあり、その場合は provide 関数と provide_extern 関数の両方を定義し、 wasm_import_module_map を通じて、rustc_driver がそれらを呼び出せるようにします。

プロバイダーの設定方法

tcx が作成されるとき、その作成者によって、rustc_middle::util の Providers 構造体を使って、ローカルプロバイダーと外部プロバイダーの両方が与えられます。この構造体には、ローカルプロバイダーと外部プロバイダーの両方が含まれています。

pub struct Providers {
    pub queries: crate::query::Providers,        // ローカルクレートのプロバイダー
    pub extern_queries: crate::query::ExternProviders,  // 外部クレートのプロバイダー
    pub hooks: crate::hooks::Providers,
}

これらの各プロバイダー構造体はマクロによって生成され、それぞれのクエリに対応する関数ポインターを含んでいます。

プロバイダーはどのように登録されるか？

util::Providers 構造体は、コンパイラ初期化時に、rustc_interface クレートによって DEFAULT_QUERY_PROVIDERS static から埋められます。実際のプロバイダー関数は、さまざまな rustc_* クレート（rustc_middle、rustc_hir_analysis など）にわたって定義されています。

プロバイダーを登録するために、各クレートは次のような provide 関数を公開します。

pub fn provide(providers: &mut query::Providers) {
    *providers = query::Providers {
        type_of,
        // ... ここにさらにプロバイダーを追加する
        ..*providers
    };
}

この関数は util::Providers ではなく query::Providers を受け取ることに注意してください。単に query::Providers を受け取るだけではない provide 関数が必要になることは極めてまれです。 util::Providers の queries フィールド以外も更新する場合は、代わりに util::Providers を受け取ることができます:

pub fn provide(providers: &mut rustc_middle::util::Providers) {
    providers.queries.type_of = type_of;
    // ... ここにローカルプロバイダーをさらに追加します

    providers.extern_queries.type_of = extern_type_of;
    // ... ここに外部プロバイダーをさらに追加します

    providers.hooks.some_hook = some_hook;
    // ... ここにフックをさらに追加します
}

新しいプロバイダーを追加する

fubar という新しいクエリを追加したいとします。このセクションではプロバイダーの接続に焦点を当てます。大きな rustc_queries! マクロ内でクエリ自体を宣言する方法については、以下の新しいクエリを追加するを参照してください。

実際には通常、次のようにします:

どのクレートがそのクエリを「所有」するかを決めます（たとえば rustc_hir_analysis、rustc_mir_build、または別の rustc_* クレート）。
そのクレートで、既存の provide 関数を探します:
```
pub fn provide(providers: &mut query::Providers) {
    // 既存の割り当て
}
```
存在する場合は、新しいクエリ用のフィールドを設定するようにそれを拡張します。そのクレートにまだ provide 関数がない場合は、追加したうえで、初期化中に実際に呼び出されるように rustc_interface クレート内の DEFAULT_QUERY_PROVIDERS に含められていることを確認してください（上記の説明を参照）。

プロバイダー関数自体を実装します:

fn fubar<'tcx>(tcx: TyCtxt<'tcx>, key: LocalDefId) -> Fubar<'tcx> { ... }

クレートの provide 関数に登録します:

pub fn provide(providers: &mut query::Providers) {
    *providers = query::Providers {
        fubar,
        ..*providers
    };
}

クエリが外部クレートのメタデータとどのようにやり取りするか

外部クレート（つまり依存関係）に対してクエリが行われると、クエリシステムはそのクレートのメタデータから情報を読み込む必要があります。これは rustc_metadata クレートによって処理されます。このクレートは、.rmeta ファイルに格納された情報のデコードと提供を担当します。

処理の流れは次のとおりです:

クエリが行われると、クエリシステムはまず def_id.krate == LOCAL_CRATE かどうかを確認して、DefId がローカルクレートを指しているのか外部クレートを指しているのかを判定します。これにより、Providers のローカルプロバイダーを使用するか、ExternProviders の外部プロバイダーを使用するかが決まります。

外部クレートの場合、クエリシステムは ExternProviders 構造体内のプロバイダーを探します。 rustc_metadata クレートは、rustc_metadata/src/rmeta/decoder/cstore_impl.rs 内の provide_extern 関数を通じて、これらの外部プロバイダーを登録します。たとえば次のようになります:

#![allow(unused)]
fn main() {
pub fn provide_extern(providers: &mut ExternProviders) {
    providers.foo = |tcx, def_id| {
        // 外部クレートのメタデータを読み込み、デコードする
        let cdata = CStore::from_tcx(tcx).get_crate_data(def_id.krate);
        cdata.foo(def_id.index)
    };
    // 他の外部プロバイダーを登録する...
}
}

メタデータは .rmeta ファイル内にバイナリ形式で格納され、外部クレートに関する事前計算済みの情報（型、関数シグネチャ、トレイト実装、コンパイラが必要とするその他の情報など）を含みます。外部クエリが行われると、rustc_metadata クレートは次のことを行います:
- 外部クレートの .rmeta ファイルを読み込む
- Decodable トレイトを使用してメタデータをデコードする
- デコードされた情報をクエリシステムに返す

このアプローチにより、外部クレートの再コンパイルを避け、依存クレートのコンパイルを高速化し、インクリメンタルコンパイルをクレート境界を越えて機能させることができます。簡略化した例を示します。外部クレートで定義された型に対して tcx.type_of(def_id) を呼び出すと、クエリシステムは次のように動作します:

def_id.krate != LOCAL_CRATE を確認して、def_id が外部クレートを指していることを検出する
rustc_metadata によって登録された ExternProviders から適切なプロバイダーを呼び出す
プロバイダーは、外部クレートのメタデータから型情報を読み込み、デコードする
デコードされた型を呼び出し元に返す

ほとんどの rustc_* クレートがローカルプロバイダーだけを提供すればよいのはこのためです。外部プロバイダーはメタデータシステムによって処理されます。唯一の例外は、クレートが外部クエリに対して特別な処理を提供する必要がある場合で、その場合はローカルプロバイダーと外部プロバイダーの両方を実装することになります。

クレートをまたいで機能するべき新しいクエリを定義しても、rustc_queries! に列挙されているというだけで、自動的にクロスクレートになるわけではありません。通常は次のことを行う必要があります:

適切な修飾子（たとえばディスクにキャッシュされるかどうか）を付けて、クエリを rustc_queries! に追加する。
所有するクレートでローカルプロバイダーを実装し、そのクレートの provide 関数を通じて登録する。
provide_extern を通じて rustc_metadata に外部プロバイダーを追加し、クエリの結果がクレートメタデータにエンコードおよびデコードされるようにする。

このようなクロスクレートクエリを導入する例は、rust-lang/rust リポジトリのコミット 996a185 で確認できます。

新しいクエリを追加する

新しいクエリはどのように追加するのでしょうか？クエリの定義は2つの手順で行われます:

クエリ名、引数、説明を宣言する。
必要な場所にクエリプロバイダーを用意する。

クエリ名と引数を宣言するには、compiler/rustc_middle/src/query/mod.rs にある大きなマクロ呼び出しにエントリを追加するだけです。次に、それに 内部向け の説明を含むドキュメントコメントを追加する必要があります。その後、クエリの ユーザー向け の説明を含む desc 属性を指定します。 desc 属性は、クエリサイクル内でユーザーに表示されます。

これは次のようになります:

rustc_queries! {
    /// すべてのアイテムの型を記録する。
    query type_of(key: DefId) -> Ty<'tcx> {
        desc { |tcx| "`{}` の型を計算中", tcx.def_path_str(key) }
        cache_on_disk
        separate_provide_extern
    }
    ...
}

クエリ定義は次の形式を取ります:

query type_of(key: DefId) -> Ty<'tcx> { ... }
^^^^^ ^^^^^^^      ^^^^^     ^^^^^^^^   ^^^
|     |            |         |          |
|     |            |         |          クエリ修飾子
|     |            |         結果型
|     |            クエリキー型
|     クエリ名
query キーワード

これらの要素を1つずつ見ていきましょう:

クエリキーワード: クエリ定義の開始を示します。
クエリ名: クエリメソッドの名前です（tcx.type_of(..)）。このクエリを表すために生成される構造体（ty::queries::type_of）の名前としても使用されます。
クエリキー型: このクエリへの引数の型です。この型は ty::query::keys::QueryKey トレイトを実装している必要があります。このトレイトは、たとえばそれをクレートに対応付ける方法などを定義します。
クエリの結果型: このクエリによって生成される型です。この型は (a) RefCell やその他の内部可変性を使用せず、(b) 低コストでクローン可能であるべきです。自明でないデータ型には、インターン化するか、Rc または Arc を使用することが推奨されます。²
クエリ修飾子: クエリの処理方法をカスタマイズするさまざまなフラグやオプションです（主にインクリメンタルコンパイルに関するもの）。

したがって、クエリを追加するには次のようにします。

上記の形式を使用して、rustc_queries! にエントリを追加します。
適切な provide メソッドを変更してプロバイダーをリンクします。または、必要に応じて新しいものを追加し、rustc_driver がそれを呼び出していることを確認します。

Rust Compiler Development Guide