正準クエリ

トレイトシステムの「出発点」は正準クエリです（これは、より一般的な意味でのクエリ、つまり答えを知りたいもの、であると同時に、 rustc 固有の意味でのクエリでもあります）。考え方としては、型チェッカーやシステムの他の部分が、それぞれの処理を行う過程で、あるトレイトがある型に対して実装されているかどうかを知りたくなる場合があります（たとえば、u32: Debug は真か？）。あるいは、何らかの関連型を正規化したくなる場合もあります。

このセクションでは、かなり高い抽象レベルでクエリを扱います。サブセクションでは、これらの考え方が rustc でどのように実装されているかを、もう少し詳しく見ていきます。

伝統的な対話型 Prolog クエリ

伝統的な Prolog システムでは、クエリを開始すると、ソルバーは処理を進め、見つけられるすべての可能な答えを提示し始めます。したがって、次のようなものが与えられた場合:

?- Vec<i32>: AsRef<?U>

ソルバーは次のように答えるかもしれません:

Vec<i32>: AsRef<[i32]>
    continue? (y/n)

この continue の部分は興味深いものです。Prolog における考え方は、ソルバーが、真となるクエリのすべての可能なインスタンス化を見つける、というものです。この場合、?U = [i32] とインスタンス化すれば、そのクエリは真になります（伝統的な Prolog インターフェイスは、直接には ?U の値を教えてくれないことに注意してください。ただし、応答を元のクエリと単一化することで、それを推測できます – Rust のソルバーは代わりに代入を返します）。もし y を押すと、ソルバーは別の可能な答えを返すかもしれません:

Vec<i32>: AsRef<Vec<i32>>
    continue? (y/n)

この答えは、AsRef に対して反射的な impl （impl<T> AsRef<T> for T）が存在するという事実に由来します。もう一度 y を押すと、今度は否定的な応答が返ってくるかもしれません:

no

当然ながら、場合によっては可能な答えが存在しないこともあり、そのためソルバーはすぐに no を返してきます:

?- Box<i32>: Copy
    no

場合によっては、応答が無限に存在することもあります。たとえば、次のクエリを与えて y を押し続けると、ソルバーは答えを返し続けて止まることがありません:

?- Vec<?U>: Clone
    Vec<i32>: Clone
        continue? (y/n)
    Vec<Box<i32>>: Clone
        continue? (y/n)
    Vec<Box<Box<i32>>>: Clone
        continue? (y/n)
    Vec<Box<Box<Box<i32>>>>: Clone
        continue? (y/n)

想像できるように、ソルバーは私たちが止めるよう求めるか、メモリを使い果たすまで、嬉々として Box の層をもう 1 つ追加し続けます。

もう 1 つ興味深い点は、クエリにはまだ変数が含まれている場合があるということです。たとえば:

?- Rc<?T>: Clone

は、次の答えを生成するかもしれません:

Rc<?T>: Clone
    continue? (y/n)

結局のところ、Rc<?T> は ?T がどのような型であっても真です。

rustc におけるトレイトクエリ

rustc のトレイトクエリは、やや異なる仕組みで動作します。 すべての可能な答えを列挙しようとするのではなく、曖昧でない答えを探します。特に、型変数の値を教えてくれる場合、それは、現在の impl と where 句の集合のもとで証明可能となる、使用できる唯一の可能なインスタンス化であることを意味します。

rustc におけるトレイトクエリへの応答は、通常 Result<QueryResult<T>, NoSolution> です（ここで T はクエリ自体に応じて多少変わります）。Err(NoSolution) の場合は、クエリが偽であり、答えがなかったことを示します（たとえば Box<i32>: Copy）。それ以外の場合、QueryResult は、見つかった可能な答えについての情報を返します。これは 4 つの部分から構成されます:

確実性: この答えについて、どれほど確信しているかを示します。これは 2 つの値を取り得ます:
- Proven は、結果が真であることが既知であることを意味します。
  - これは、たとえば Vec<i32>: Clone や Rc<?T>: Clone を証明しようとした結果かもしれません。
- Ambiguous は、まだ真または偽のいずれであるかを証明できないものがあったことを意味します。通常は、より多くの型情報が必要だったためです。（すぐに例を見ます。）
  - これは、Vec<?T>: Clone を証明しようとした結果かもしれません。
変数値: 元のクエリに現れた未束縛の推論変数（?T のようなもの）それぞれの値です。（Prolog では、これらを推測しなければならなかったことを思い出してください。）
- 下の例で見るように、Ambiguous の場合でも変数値が返ってくることがあります。
リージョン制約: これは、入力として与えたライフタイム間で成り立たなければならない関係です。ここでは無視します。
値: クエリ結果には、型 T の値も付属します。関連型の正規化のような特殊なクエリでは、追加の結果を返すためにこれが使われますが、多くの場合は単に () です。

例

各部分が何を意味するのかを理解するために、例のクエリを順に見ていきましょう。 Borrow トレイトを考えます。このトレイトにはいくつもの impl があります。その中には、次の 2 つがあります（わかりやすさのため、Sized 境界を明示的に書いています）:

impl<T> Borrow<T> for T where T: ?Sized
impl<T> Borrow<[T]> for Vec<T> where T: Sized

例 1。 次の（やや人工的な）コード片を型チェックしているところを想像してください:

fn foo<A, B>(a: A, vec_b: Option<B>) where A: Borrow<B> { }

fn main() {
    let mut t: Vec<_> = vec![]; // 型: Vec<?T>
    let mut u: Option<_> = None; // 型: Option<?U>
    foo(t, u); // 例 1: `Vec<?T>: Borrow<?U>` を要求する
    ...
}

コメントが示すように、まず 2 つの変数 t と u を作成します。 t は空のベクターであり、u は None オプションです。これらの変数はいずれも、その型に未束縛の推論変数を持っています。 ?T はベクター t 内の要素を表し、?U はオプション u に格納される値を表します。次に、foo を呼び出します。foo のシグネチャをその引数と比較すると、最終的に A = Vec<?T> および B = ?U になります。したがって、foo の where 句は Vec<?T>: Borrow<?U> を要求します。これが、最初のトレイトクエリの例です。

クエリ Vec<?T>: Borrow<?U> には、多くの可能な解があります。たとえば:

?U = Vec<?T>,
?U = [?T],
?T = u32, ?U = [u32]
などです。

したがって、返ってくる結果は次のようになります（リージョン制約と「値」は無視します）:

確実性: Ambiguous – これが成り立つかどうかはまだわかりません
変数値: [?T = ?T, ?U = ?U] – 変数の値について何もわかりませんでした

要するに、このクエリ結果は、このトレイトが証明されるかどうかについて多くを語るには早すぎる、ということを示しています。型チェック中、これは即座のエラーではありません。代わりに、型チェッカーはこの要件（Vec<?T>: Borrow<?U>）を保持して待機します。次の例で見るように、?T と ?U が他のソースから制約されることがあり、その場合はトレイトクエリを再度試すことができます。

例 2。 ここで前の例を少し拡張し、 u に値を代入できます:

```rust,ignore
fn foo<A, B>(a: A, vec_b: Option<B>) where A: Borrow<B> { }

fn main() {
    // 以前見たもの:
    let mut t: Vec<_> = vec![]; // 型: Vec<?T>
    let mut u: Option<_> = None; // 型: Option<?U>
    foo(t, u); // `Vec<?T>: Borrow<?U>` => 曖昧

    // 新しい内容:
    u = Some(vec![]); // ?U = Vec<?V>
}

この代入の結果、u の型は強制的に Option<Vec<?V>> になります。ここで、?V はベクターの要素型を表します。これはさらに、?U が Vec<?V> に単一化されることを意味します。

型チェッカーが、以前見た「まだ証明されていない」トレイト義務 Vec<?T>: Borrow<?U> を再検討することにしたと仮定しましょう。?U はもはや未束縛の推論変数ではなく、値 Vec<?V> を持っています。したがって、その値でクエリを「更新」すると、次のようになります。

Vec<?T>: Borrow<Vec<?V>>

今回は、適用される impl は 1 つだけで、再帰的な impl です。

impl<T> Borrow<T> for T where T: ?Sized

したがって、トレイトチェッカーは次のように答えます。

確実性: Proven
変数の値: [?T = ?T, ?V = ?T]

ここでは、この義務が実際に成り立つことを証明済みであり、さらに ?T と ?V が同じ型であることもわかっている、と言っています（ただし、その型が何であるかはまだわかっていません！）。

（実際には、ここで関数が終了するため、型チェッカーはこの時点でエラーを出します。t と u の要素型は、同じであることはわかっていても、まだわかっていないからです。）

Keyboard shortcuts

Rust Compiler Development Guide

正準クエリ

伝統的な対話型 Prolog クエリ

rustc におけるトレイトクエリ

例