Keyboard shortcuts

Press ← or → to navigate between chapters

Press S or / to search in the book

Press ? to show this help

Press Esc to hide this help

トレイト解決（旧式）

この章では、トレイト解決 の一般的なプロセスについて説明し、 いくつかの分かりにくい点を指摘します。

注: この章（およびそのサブチャプター）では、トレイト ソルバーが現在どのように動作しているかを説明します。ただし、私たちは新しい トレイトソルバーの設計を進めています。そちらについて読みたい場合は、 このサブチャプターを参照してください。

主要な概念

トレイト解決とは、トレイトへの各参照に対して impl を対応付けるプロセスです。 したがって、たとえば次のようなジェネリック関数があるとします。

fn clone_slice<T:Clone>(x: &[T]) -> Vec<T> { ... }

そして、その関数への呼び出しがあるとします。

let v: Vec<isize> = clone_slice(&[1, 2, 3])

この場合、（この例では）isize : Clone の impl が存在するかどうかを判断するのが トレイト解決の役割です。

ジェネリック関数のように、場合によっては特定の impl を 見つけられないことがありますが、呼び出し元が impl を 提供しなければならないことは判断できます。たとえば、clone_slice の本体を考えてみます。

fn clone_slice<T:Clone>(x: &[T]) -> Vec<T> {
    let mut v = Vec::new();
    for e in &x {
        v.push((*e).clone()); // (*)
    }
}

(*) が付けられた行は、T（*e の型）が Clone トレイトを実装している場合にのみ正当です。当然、T が何であるかは 分からないため、具体的な impl を見つけることはできません。しかし、境界 T:Clone に基づいて、 呼び出し元が提供しなければならない impl が存在すると言えます。

私たちは、impl を必要とするトレイト参照を指すために オブリゲーション という用語を使います。 基本的に、トレイト解決システムは、適切な impl が実際に存在することを証明することで オブリゲーションを解決します。

型チェック中には、トレイト選択の結果は保存しません。 単にトレイト選択が成功することを検証したいだけです。その後、 コード生成時にすべての具体的な型が利用可能になったとき、 実際の実装を選択するためにトレイト選択を繰り返すことができます。 その実装は出力バイナリに生成されます。

概要

トレイト解決は、3つの主要な部分で構成されます。

  • 選択: 特定のオブリゲーションをどのように解決するかを決定します。 たとえば、選択は、特定のオブリゲーションを Self 型に一致する impl を 用いることで解決できる、またはパラメータ境界（例: T: Trait）を使って 解決できる、と判断することがあります。impl の場合、1つの オブリゲーションを選択すると、その impl 自体にある where 句のために ネストしたオブリゲーション が作成されることがあります。また、曖昧さを解消するために、 それらのネストしたオブリゲーションを評価する必要がある場合もあります。

  • 充足: 充足コードは、オブリゲーションが完全に充足されていることを追跡するものです。 基本的には、選択されるべきオブリゲーションのワークリストです。 選択が成功すると、そのオブリゲーションはワークリストから削除され、 ネストしたオブリゲーションがキューに追加されます。 充足は推論変数に制約を与えます。

  • 評価: 推論変数に一切制約を与えずに、オブリゲーションが成り立つかどうかを確認します。 選択によって使用されます。

選択

選択とは、オブリゲーションを解決できるかどうか、そして解決できる場合には どのように解決するか（impl、where 句など）を決定するプロセスです。 主なインターフェイスは select() 関数で、これはオブリゲーションを受け取り、 SelectionResult を返します。起こり得る結果は3つあります。

  • Ok(Some(selection)) – はい、そのオブリゲーションは解決でき、 selection がその方法を示します。impl によって解決された場合、 selection はその impl によって要求されるネストしたオブリゲーションも示すことがあります。

  • Ok(None) – そのオブリゲーションを解決できるかどうか、まだ確信が持てません。 これは、オブリゲーションに未束縛の型変数が含まれている場合に最もよく起こります。

  • Err(err) – 型エラーのため、または適用できる可能性のある impl が存在しないため、 そのオブリゲーションは確実に解決できません。

選択の基本的なアルゴリズムは、大きく2つのフェーズに分かれます。 候補の組み立てと確認です。

ライフタイム推論の仕組み上、ライフタイム間の単一化やサブタイプ関係が 成り立つかどうかについて即座にフィードバックを返すことはできないことに注意してください。 したがって、ライフタイムの照合は選択中には考慮されません。 これは、サブリージョン代入が失敗しないという事実に反映されています。 その結果、後でエラーであることが判明するライフタイム制約が生じる場合があります （対照的に、ライフタイム以外の制約は選択中にすでにチェックされており、 それ自体がエラーを引き起こすことは決してありませんが、当然ながら下流で別のエラーにつながることはあります）。

候補の組み立て

TODO: なぜ異なる候補が存在するのか、そしてなぜそれをプローブ内で行う必要があるのかについて説明する。

オブリゲーションを満たすために使用できる可能性のある impl、where 句などを検索します。それらのそれぞれを候補と呼びます。 曖昧さを避けるため、明確に適用可能な候補をちょうど1つ見つけたいと考えます。 場合によっては、impl や where 句が適用されるかどうか分からないことがあります。 これは、オブリゲーションに未束縛の推論変数が含まれている場合に起こります。

特定の impl、where 句などが特定のオブリゲーションに適用されるかどうかを決定するサブルーチンは、 総称して 照合 のプロセスと呼ばれます。impl 候補の場合 、 これは、ネストしたオブリゲーションを無視しつつ、impl ヘッダー（Self 型とトレイト引数）を 単一化することに相当します。照合が成功した場合、それを候補の集合に追加します。 Copy、Sized、CoerceUnsized などの組み込みトレイトの候補を組み立てる際には、 他にも規則があります。

この最初のパスが完了すると、候補の集合を調べることができます。 それが単集合であれば、完了です。これは、適用できる可能性のあるスコープ内で唯一の impl です。 そうでなければ、where 句やその他の条件を使って候補の集合を絞り込むことができます。 絞り込みでは、ネストしたオブリゲーションが適用され得るかどうかを確認するために evaluate_candidate を使用します。それでもなお2つ以上の候補が残る場合は、 fn candidate_should_be_dropped_in_favor_of を使って、一部の候補を他の候補より優先します。

この縮小された集合が単一で曖昧でないエントリを生成するなら問題ありません。 そうでなければ、結果は曖昧であるとみなされます。

絞り込み: 曖昧さの解決

しかし、すべての型が単一化される複数の impl が存在する場合はどうなるのでしょうか。 次の例を考えてみます。

trait Get {
    fn get(&self) -> Self;
}

impl<T: Copy> Get for T {
    fn get(&self) -> T {
        *self
    }
}

impl<T: Get> Get for Box<T> {
    fn get(&self) -> Box<T> {
        Box::new(<T>::get(self))
    }
}

たとえば get(&Box::new(1_u16)) を呼び出すとどうなるでしょうか。 この場合、Self 型は Box<u16> です。これは両方の impl と単一化されます。 なぜなら、最初の impl はすべての型 T に適用され、2つ目はすべての Box<T> に適用されるためです。これを曖昧でないものにするために、コンパイラは where 句を考慮し、 候補を削除しようとする 絞り込み パスを実行します。この場合、最初の impl は Box<u16> : Copy の場合にのみ適用されますが、これは成り立ちません。したがって絞り込み後には、 候補が1つだけ残るため、先に進むことができます。

where 句

impl 以外で義務を解決するもう 1 つの主要な方法は、 where 句によるものです。選択プロセスには常に パラメーター 環境 が与えられます。これは where 句のリストを含んでおり、 基本的には満たせると仮定できる義務です。私たちはそのリストを反復処理し、 現在の義務がそのリスト内に見つかるかどうかを確認します。 見つかった場合、それは満たされたと見なされます。より正確には、 同じトレイト（または何らかのサブトレイト）に対する where 句の義務で、 その義務とマッチできるものが存在するかどうかを確認したいのです。

この簡単な例を考えてみましょう。

trait A1 {
    fn do_a1(&self);
}
trait A2 : A1 { ... }

trait B {
    fn do_b(&self);
}

fn foo<X:A2+B>(x: X) {
    x.do_a1(); // (*)
    x.do_b();  // (#)
}

foo の本体では、明らかに変数 x に対して A1、A2、または B のメソッドを使用できます。(*) で示された行は義務 X: A1 を発生させ、 一方 (#) で示された行は義務 X: B を発生させます。同時に、 パラメーター環境には 2 つの where 句、X : A2 と X : B が含まれます。 したがって各義務について、この where 句のリストを検索します。 義務 X: B は where 句 X: B と自明にマッチします。 義務 X:A1 を解決するには、X:A2 が X:A1 を含意することに注目します。

確認

確認 は、トレイトの出力型パラメーターを義務内で見つかった値と単一化し、 型エラーを生じさせる可能性があります。

前のセクションの Convert の例について、次のような変形を考えてみましょう。

trait Convert<Target> {
    fn convert(&self) -> Target;
}

impl Convert<usize> for isize { ... } // isize -> usize
impl Convert<isize> for usize { ... } // usize -> isize

let x: isize = ...;
let y: char = x.convert(); // 注: `y: char` になりました！

確認では、impl が Target を usize と指定しているのに対し、 義務は char と報告しているため、エラーが報告されます。したがって、 選択の結果はエラーになります。

候補 impl は Self 型に基づいて選ばれますが、 確認は（この場合）Target 型パラメーターに基づいて行われることに注意してください。

codegen 中の選択

上で述べたように、型チェック中にはトレイト選択の結果を保存しません。 codegen 時には、各メソッド呼び出しに対して特定の impl を選ぶために、 トレイト選択を繰り返します。これは fn codegen_select_candidate を使用して行われます。 この 2 回目の選択では、スコープ内にある where 句を一切考慮しません。 なぜなら、各解決が特定の impl に解決されることがわかっているからです。

1 つ興味深いひねりは、ネストした義務に関するものです。一般に、codegen では、 どの候補が適用されるかを判断するだけでよく、ネストした義務については気にしません。 それらはすでに真であると仮定されているからです。それにもかかわらず、現在はそれらをすべて実際に満たしています。 これは、それが型推論の結果に影響を与える場合があるためです。 つまり、impl の型変数に関する完全な代入が利用できるわけではないため、 すべてを把握するにはトレイト選択を実行しなければなりません。