クエリ評価モデルの詳細

この章では、クエリの基盤となる抽象モデルをより深く掘り下げます。実装の詳細には踏み込みませんが、背後にあるロジックを説明しようとします。そのため、ここでの例は簡略化されており、コンパイラの内部APIを直接反映しているわけではありません。

クエリとは何か？

抽象的には、あるクレートについてのコンパイラの知識を「データベース」と見なし、クエリはそれについてコンパイラに質問する方法、つまり事実を得るためにコンパイラの「データベース」に「クエリ」を行う方法です。

しかし、このコンパイラデータベースには特別な点があります。最初は空であり、クエリが実行されるとオンデマンドで埋められていきます。したがって、クエリは、データベースにまだ結果が含まれていない場合に、自分の結果を計算する方法を知っていなければなりません。そのために、クエリは他のクエリや、データベースの作成時に事前に格納されている特定の入力値にアクセスできます。

したがって、クエリは次のものから構成されます。

クエリを識別する名前
何を検索したいかを指定する「キー」
どのような種類の結果を返すかを指定する結果型
結果がまだデータベースに存在しない場合に、それをどのように計算するかを指定する関数である「プロバイダー」

例として、type_of クエリの名前は type_of であり、そのクエリキーは型を知りたい項目を識別する DefId、結果型は Ty<'tcx>、そしてプロバイダーは、クエリキーとデータベースの残りの部分へのアクセスを与えられると、そのキーによって識別される項目の型を計算できる関数です。

したがって、ある意味では、クエリは単にクエリキーを対応する結果へ写像する関数にすぎません。しかし、これが健全であるためには、いくつかの制約を課す必要があります。

キーと結果はイミュータブルな値でなければなりません。
プロバイダー関数は、同じキーに対して常に同じ結果を返さなければならないという意味で、純粋関数でなければなりません。
プロバイダー関数が受け取る唯一のパラメーターは、キーと「クエリコンテキスト」への参照です（これは「データベース」の残りの部分へのアクセスを提供します）。

データベースは、クエリを呼び出すことで遅延的に構築されます。クエリプロバイダーは他のクエリを呼び出し、その結果はすでにキャッシュされているか、別のクエリプロバイダーを呼び出すことによって計算されます。これらのクエリプロバイダー呼び出しは、概念的には有向非巡回グラフ（DAG）を形成し、その葉には、クエリコンテキストが作成された時点ですでに分かっている入力値があります。

キャッシュ化/メモ化

クエリ呼び出しの結果は「メモ化」されます。これは、クエリコンテキストが内部テーブルに結果をキャッシュし、同じクエリキーで再びクエリが呼び出されたときには、プロバイダーを再度実行する代わりに、キャッシュから結果を返すことを意味します。

このキャッシュ化は、クエリエンジンを効率的にするために不可欠です。メモ化がなくてもシステムは健全です（つまり、同じ結果を返します）が、同じ計算が何度も繰り返されることになります。

メモ化は、クエリプロバイダーが純粋関数でなければならない主な理由の1つです。プロバイダー関数を呼び出すたびに異なる結果が返される可能性がある場合（何らかのグローバルなミュータブル状態にアクセスするため）、結果をメモ化することはできません。

入力データ

クエリコンテキストが作成された時点では、それはまだ空です。実行されたクエリはなく、キャッシュされた結果もありません。しかし、コンテキストはすでに「入力」データ、つまりコンテキストが作成される前に計算され、クエリが計算を行うためにアクセスできるイミュータブルなデータ片へのアクセスを提供しています。

2021年1月時点では、この入力データは主に

HIRマップ、上流クレートのメタデータ、そしてコンパイラが呼び出されたときのコマンドラインオプションで構成されています。しかし将来的には、入力はコマンドラインオプションとソースファイルのリストだけで構成されるようになります。 HIRマップ自体は、これらのソースファイルを処理するクエリによって提供されるようになります。

入力がなければ、クエリは結果を計算するための材料を何も持たない空虚の中に存在することになります（クエリプロバイダーは、他のクエリとコンテキストにしかアクセスできず、その他の外部状態や情報にはアクセスできないことを思い出してください）。

クエリプロバイダーにとって、入力データと他のクエリの結果はまったく同じに見えます。プロバイダーはコンテキストに「X の値をください」と伝えるだけです。入力データはイミュータブルであるため、プロバイダーは、クエリ結果の場合と同じように、それが異なるクエリ呼び出し間で同じであることに依存できます。

いくつかのクエリの実行トレース例

このクエリ呼び出しのDAGはどのようにして生まれるのでしょうか？ある時点で、コンパイラドライバーは、まだ空のクエリコンテキストを作成します。その後、クエリシステムの外側から、自分のタスクを実行するために必要なクエリを呼び出します。これはおおよそ次のようになります。

fn compile_crate() {
    let cli_options = ...;
    let hir_map = ...;

    // クエリコンテキスト `tcx` を作成する
    let tcx = TyCtxt::new(cli_options, hir_map);

    // 型チェッククエリを呼び出して型チェックを行う
    tcx.type_check_crate();
}

type_check_crate クエリプロバイダーは、おおよそ次のようになります。

fn type_check_crate_provider(tcx, _key: ()) {
    let list_of_hir_items = tcx.hir_map.list_of_items();

    for item_def_id in list_of_hir_items {
        tcx.type_check_item(item_def_id);
    }
}

type_check_crate クエリが入力データ（tcx.hir_map.list_of_items()）にアクセスし、他のクエリ（type_check_item）を呼び出していることが分かります。type_check_item の呼び出しは、それ自体が入力データにアクセスしたり、他のクエリを呼び出したりします。その結果、最終的には、最初に実行されたノードから逆向きに、クエリ呼び出しのDAGが構築されます。

         (2)                                                 (1)
  list_of_all_hir_items <----------------------------- type_check_crate()
                                                               |
    (5)             (4)                  (3)                   |
  Hir(foo) <--- type_of(foo) <--- type_check_item(foo) <-------+
                                      |                        |
                    +-----------------+                        |
                    |                                          |
    (7)             v  (6)                  (8)                |
  Hir(bar) <--- type_of(bar) <--- type_check_item(bar) <-------+

// (x) は呼び出し順を表す

また、クエリ結果はしばしばキャッシュから読み取れることも分かります。 type_of(bar) は type_check_item(foo) のために計算されているため、 type_check_item(bar) がそれを必要としたときには、すでにキャッシュ内にあります。

クエリ結果は、コンテキストが生存している限り、クエリコンテキスト内にキャッシュされたままになります。したがって、コンパイラドライバーが後で別のクエリを呼び出した場合でも、上記のグラフはまだ存在しており、すでに実行されたクエリをやり直す必要はありません。

サイクル

先ほど、クエリ呼び出しはDAGを形成すると述べました。しかし、たとえば次のようなクエリプロバイダーを用意すると、巡回グラフを簡単に形成できてしまいます。

fn cyclic_query_provider(tcx, key) -> u32 {
  // 同じキーで同じクエリを再び呼び出す
  tcx.cyclic_query(key)
}

クエリプロバイダーは通常の関数なので、これはほぼ期待どおりに振る舞います。評価は無限再帰に陥って停止します。このようなクエリは、いずれにしてもあまり有用ではありません。しかし、ときには特定の種類の不正なユーザー入力により、クエリが循環的に呼び出されることがあります。クエリエンジンには、同じ入力引数によるクエリの循環呼び出しをチェックする仕組みが含まれています。そして、サイクルは回復不能なエラーであるため、人間が読めることを意図した “cycle error” メッセージとともに実行を中止します。

ある時点で、コンパイラーには「サイクルリカバリー」という概念がありました。つまり、クエリの実行を「試行」し、それがサイクルを引き起こした場合には、別の方法で処理を続行できるというものです。しかし、これは後に削除されました。というのも、これが理論的にどのような結果をもたらすのか、特にインクリメンタルコンパイルに関して完全には明らかではないためです。

“Steal” クエリ

一部のクエリは、その結果が Steal<T> 構造体でラップされています。これらのクエリは 1つの例外を除いて通常のクエリとまったく同じように振る舞います。その結果は、ある時点でキャッシュから「盗まれる」ことが期待されています。つまり、プログラムの別の部分がその所有権を取得し、その結果にはそれ以降アクセスできなくなります。

この盗用メカニズムは純粋にパフォーマンス最適化として存在します。というのも、一部の結果値はクローンするにはコストが高すぎるためです（例: 関数の MIR）。結果を盗むことは、クエリ結果が不変でなければならないという条件に違反するように見えます（結局のところ、結果値をキャッシュの外へ移動しているためです）が、その変更が観測可能でない限り問題ありません。これは次の2つによって実現されます。

結果が盗まれる前に、その結果を読み取る必要が生じうるすべてのクエリを積極的に実行しておくようにします。これは、それらのクエリを呼び出すことで手動で行う必要があります。
クエリが盗まれた結果にアクセスしようとするたびに、ICE （内部コンパイラーエラー）を発生させ、そのような状態が見過ごされないようにします。

これは手動での介入が必要になるため理想的な構成ではありません。そのため、使用は控えめにし、どのクエリが特定の結果にアクセスしうるかが十分に分かっている場合にのみ使用すべきです。しかし実際には、盗用が大きな保守負担になることはありませんでした。

まとめると、「Steal クエリ」は制御された方法で一部のルールを破ります。何かが気付かれないまま誤って進行することがないようにするためのチェックが用意されています。

Keyboard shortcuts