Rustのトレイト選択

Rust

概要: トレイト選択とは、トレイト制約の解決方法を検索するコンパイラの処理であり、型推論にもコード生成にも使われる重要な部品である。本記事ではトレイト選択の動作の詳細について解説する。

トレイト選択とは

トレイト選択 (selection) とは、トレイト制約 (obligation) の解決方法を検索する処理である。トレイト制約は、トレイト境界と同じく、

SomeType: SomeTrait<SomeArguments>

という形式をとる。例えば、

let z = x + y;

というコードを書いたとき、 z の型は <X as Add<Y>>::Output であるが、これをより具体的に決定するには、 X: Add<Y> の解決方法を決定する必要がある。

トレイト選択の処理はtraits/select.rsにまとまっているのでここを読むとだいたいわかる。

トレイト選択が呼ばれるタイミング

トレイト選択の本体は select関数 である。これは主に以下のような場所で呼ばれる。

  • 型推論において型を1段階以上解決する必要が生じた場合。 (今あるトレイト制約それぞれについて解決を試みるが、失敗してもよい)
  • 型推論の最後。 (全てのトレイト制約を解決する)
  • 定数式の評価中。 (関連定数・constメソッド等の解決)
  • 単相化後のコード生成。

特に、型推論中のトレイト選択では、型引数を含む上、型の判明していない型推論変数もある。そのためこの時点ではトレイト選択の結果が曖昧である可能性がある。

トレイト制約の解決方法

トレイト制約はいくつかの異なる方法で解決される。それらの分類を与えているのがSelectionCandidateである。

  • ImplCandidate … 最も標準的な解決方法。トレイト実装 (impl MyTrait for SomeType { .. }) により解決する。 (否定実装もこれに含まれる)
  • ParamCandidate … 最も標準的な解決方法。型引数等に対するトレイト境界 (fn f<T: Clone> の T: Clone など) により解決する。
  • DefaultImplCandidate … 既定実装 impl Send for .. {} により解決する。
  • ProjectionCandidate … 射影型のトレイト制約を、関連型に対するトレイト境界 (type Owned: Borrow<Self>; など) により解決する。または、匿名型 (impl Trait) のトレイト制約を、それ自身により解決する。
  • ObjectCandidate … トレイトオブジェクトのトレイト制約を、それ自身により解決する。
  • 特定のトレイトに対するビルトインの解決方法
    • BuiltinCandidate … Copy/Sized 制約を組込みの方法により解決する。
    • BuiltinUnsizeCandidate … Unsize 制約を組込みの方法により解決する。
    • BuiltinObjectCandidate … トレイトオブジェクトに追加で付与される Send/Sync 境界により解決する。
    • ClosureCandidate/FnPointerCandidate … 関数ポインタ型 fn() や |args| { .. } によるクロージャ匿名型 [closure@..] に対する Fn/FnMut/FnOnce を組込みの方法により解決する。

ImplCandidate と ParamCandidate は、この時点では全く別物であることに注意する。例えば X: Add<Y> を解決する場合でも、

fn f(x: i32, y: i32) {
    let z = x + y;
}

であれば ImplCandidate が選択されるが、

fn f<X: Add<Y>, Y>(x: X, y: Y) {
    let z = x + y;
}

であれば ParamCandidate が選択される。

トレイト選択の流れ

トレイト選択は以下の手順で行われる。

基本的には、収集・選別をして候補が2つ以上になったら曖昧、候補が0個だったり承認されなかったら失敗、それ以外の場合は成功である。また、型環境への副作用は承認の段階で発生する。

実装候補の収集と承認

実装候補の収集

実装候補の収集は以下のように行われる。

  • 該当トレイトに対する既知のトレイト実装を列挙する。
  • 各トレイト実装の型引数/生存期間変数をフレッシュな型変数/生存期間変数で置き換える。
  • トレイト実装のヘッダとトレイト制約の単一化を試みる。
  • 単一化の成否にかかわらず、型環境を直前の状態にロールバックする。
  • 単一化が成功した実装を、候補として残す。

例えば、 Vec<Box<i32>>: MyTrait<Vec<Box<i8>>> というトレイト制約に対し、

  • impl<T: Copy, U: Copy> MyTrait<Vec<T>> for Vec<U> { .. } は候補である。 (単一化に成功するため。実装に含まれるトレイト境界は満たされていないが、これは収集には関係ない。)
  • impl<T> MyTrait<Vec<T>> for Vec<T> { .. } は候補ではない。 (単一化に失敗するため)

実装候補の承認

実装候補の承認は以下のように行われる。

  • 単一化を行う。
  • where 等で指定されたトレイト境界をトレイト制約として追加する。

型引数候補の収集と承認

型引数候補の収集

型引数候補の収集は以下のように行われる。

  • where 節等のトレイト境界を列挙する。
  • 各トレイト境界を、トレイト制約と単一化し、成功したら候補に加える。
  • 単一化の成否にかかわらず、元の状態にロールバックする。

型引数候補の承認

型引数候補の承認は以下のように行われる。

  • 該当トレイト境界を、トレイト制約と単一化する。

既定実装候補の収集と承認

既定実装候補の収集

既定実装は impl Send for .. {} のように .. という記号を使って与えられる特殊な実装で、主に Send, Sync, UnwindSafe, RefUnwindSafe が用いている。

既定実装候補の収集 は条件つきで実行される。つまり、他に候補がない場合にのみ既定実装候補がチェックされる。この規則があるため、収集と選別を区別して考える必要がある。

さて、他に候補がない場合の既定実装候補の収集は以下のように行われる。

  • トレイトオブジェクト型には既定実装は使われない。 (必要なら &(Foo + Sync) のようにしたり、trait Foo : Sync のようにしたりする)
  • 型引数には既定実装は使われない。 (必要なら fn f<T: Send> のように明示する)
  • 射影型には既定実装は使われない。 (必要なら trait Foo { type X : Send; } のように明示する)
  • それ以外の型に対しては既定実装候補を残す。特に、 impl Trait 型には既定実装が適用される。
  • 型変数の場合は、上記のどちらの場合に落ちるかわからないため、曖昧となる。

既定実装候補の承認

既定実装候補の承認は以下のように行われる。なお、既定実装をもつことができるトレイトは、 Send や Sync のように引数をとらないマーカートレイトに限られる。

  • Self 型の各メンバーに、再帰的にトレイト制約を追加する。

ただし、各メンバーとは以下のことを指す:

  • 整数・浮動小数点数・bool・char・str・関数ポインタ・関数定義・!: なし
  • ポインタ・参照: 参照先の型
  • 配列・スライス: 要素型
  • PhantomData<T>: T
  • タプル・構造体・共用体・列挙型: 全てのメンバーの型
  • クロージャ: キャプチャーされた変数の型。ただし参照キャプチャーされた場合はその参照型。
  • impl Trait: 匿名化される前の型。

射影候補の収集と承認

射影候補の収集

射影候補の収集は以下のようにして行われる。

  • Self 型が射影型なら、関連型の境界を列挙する。
  • Self 型が impl Trait 型なら、 impl Trait 内の Trait を列挙する。
  • これらのそれぞれと単一化し、どれか一つでも成功したら候補として採用する。
  • 単一化の成否にかかわらず、型環境は元の状態にロールバックする。

現在の実装では、複数の候補があった場合、曖昧にはならず、最初のものが採用される。

射影候補の承認

射影候補の承認は以下のようにして行われる。

  • Self 型が射影型なら、関連型の境界を列挙する。
  • Self 型が impl Trait 型なら、 impl Trait 内の Trait を列挙する。
  • これらのそれぞれと単一化し、失敗したらロールバックする。成功したらロールバックせず終了する。

トレイトオブジェクト候補の収集と承認

トレイトオブジェクト候補の収集

トレイトオブジェクト候補の収集は以下のようにして行われる。

  • トレイト制約のトレイトがobject-safeでないなら何もしない。
  • トレイト制約の Self 型がトレイトオブジェクト型でないなら何もしない。 Self 型が型推論変数の場合は曖昧となる。
  • トレイトオブジェクト型に追加の Send/Sync 境界があり、これがトレイト制約と一致する場合は、組込みトレイトオブジェクト候補として採用し、終了する。
  • それ以外の場合は、トレイトオブジェクト型の主境界のスーパートレイト境界を(型引数込みで)推移的に求め、トレイト制約と単一化できるものを列挙する。(trait Foo: Bar<i32> + Bar<i8> のように、同じトレイトの複数のスーパートレイト境界を持つ可能性もある)
  • 残ったスーパートレイト境界がちょうど1個ならそれを候補にする。それ以外の場合は曖昧と報告する。

トレイトオブジェクト候補の承認

トレイトオブジェクト候補の承認は収集とほぼ同様だが、単一化に成功した場合はロールバックせずに型環境に対する変更をコミットする。

なお、組込みトレイトオブジェクト候補(追加の Send/Sync 境界に由来する候補) の承認は何もしない。

クロージャ候補/関数ポインタ候補の収集と承認

クロージャ候補/関数ポインタ候補の収集

クロージャ候補の収集と関数ポインタ候補の収集は以下のようにして行われる。

  • トレイト制約のトレイトが Fn/FnMut/FnOnce のいずれかを調べる。どれでもなかったら何もしない。
  • Self がクロージャ型/関数定義/関数ポインタのいずれかを調べる。どれでもなかったら何もしない。未解決の型推論変数の場合は曖昧となる。
  • クロージャ型については、キャプチャー変数の利用状況を見て、 Fn/FnMut/FnOnceが実装できるかどうかを調べる。実装できなかったら何もしない。この時点でクロージャ種別が判明していない場合は曖昧となる。
  • 関数定義/関数ポインタについては、 unsafe でないこと、 extern "Rust"である(これは何も書いていないのと同義)こと、可変長引数部分をもたないこと(extern "Rust"であることからも従う)を確認する。どれか1つでも満たされていなかったら何もしない。
  • それ以外の場合は、これを候補にする。

クロージャ候補/関数ポインタ候補の承認

クロージャ候補の承認と関数ポインタ候補の収集は以下のようにして行われる。

  • クロージャ/関数ポインタ型から、それが実装するクロージャトレイト参照を生成する。 (例: [closure@..] から Fn(u8) -> u32 / fn(&String) -> &str から FnMut(&String) -> &str)
  • 生成したクロージャトレイト参照を、トレイト制約と単一化する。
  • クロージャの場合、クロージャの種別ごとに生じる制約を追加する。

Copy/Sized の収集と承認

Copy はimpl・関連型の境界・型引数の境界のほかに、以下の組込みの規則により候補が生成されることがある。

  • 整数・浮動小数点数・bool・char・関数ポインタ・関数定義・生ポインタ・共有参照・!: 無条件で Copy である。
  • 配列: 要素型が Copy であるときに Copy である。
  • タプル: 全ての要素型が Copy であるときに Copy である。
  • トレイトオブジェクト・str・スライス・クロージャ型・可変参照: Copy ではない。他の候補の有無にかかわらず、このトレイト制約は解決されない。
  • 構造体・列挙型・共用体・射影型・型引数・impl Trait型: Copy とは限らないが、impl Copy for などの候補により Copy になるかもしれない。
  • 未解決の型推論変数の場合: 曖昧となる。

Sized にも同様の組込みの規則がある。

  • 整数・浮動小数点数・bool・char・関数ポインタ・関数定義・生ポインタ・参照・配列・クロージャ型・!: 無条件で Sized である。
  • タプル: 最後の要素型が Sized であるときに Sized である。
  • トレイトオブジェクト・str・スライス: Sized ではない。他の候補の有無にかかわらず、このトレイト制約は解決されない。
  • 構造体・列挙型・共用体: 各バリアントの末尾の型が Sized であるとき、 Sized である。
  • 射影型・型引数・impl Trait型: Sized とは限らないが、T: Sized などの候補により Sized になるかもしれない。
  • 未解決の型推論変数の場合: 曖昧となる。

これらの条件が満たされたときに、 Copy/Sizedの組込みトレイト候補が生成される。候補の生成時点では、再帰的な制約は加味しない。

Copy/Sized の組込みトレイト候補の承認のタイミングで、これらの再帰的な制約がチェックされる。

Unsize の収集と承認

T: Unsize<U> は関連型の境界・型引数の境界のほかに、以下の規則により候補が生成される。

  1. T と U がどちらも同じトレイトのトレイトオブジェクト型で、追加の Send/Sync 境界について T のほうが U より多くを実装しているときは、 T: Unsize<U> の候補が生成される。
  2. T がトレイトオブジェクト型ではなく、 U がトレイトオブジェクト型のときは、 T: Unsize<U> の候補が生成される。
  3. U がトレイトオブジェクト型ではなく、 T か U が未解決の型推論変数のときは、曖昧となる。
  4. T が配列で U がスライスのときは、 T: Unsize<U> の候補が生成される。
  5. T と U がどちらも同じ構造体を指しているときは、 T: Unsize<U> の候補が生成される。
  6. T と U が同じ長さのタプルのときは、 T: Unsize<U> の候補が生成される。

これらの候補は以下の規則により承認される。

  1. T と U の主境界は等しい。 T は U より長く生存する。
  2. U のトレイトはobject-safeである。 T は U の全てのトレイトを実装している。 T は U の生存期間以上に生存する。
  4. T と U の要素型が等しい。
  5. 構造体はフィールドを1個以上持っている。最後以外のフィールド達と、最後のフィールドは、型引数を共有していない。最後以外のフィールドは T と U で等しい。最後のフィールドを T0, U0 とおくと、 T0: Unsize<U0> である。 (これらの比較時には射影型は解決せずにそのまま扱う)
  6. タプルは1要素以上である。最後以外のフォールドは T と U で等しい。最後のフィールドを T0, U0 とおくと、 T0: Unsize<U0> である。

候補の選別

選別はさらに以下の処理に分けられる。

  • 候補がちょうど1個なら、選別処理をスキップする。
  • 各候補の承認処理をして、失敗したら候補から外す。承認の成否にかかわらず、型環境は元の状態にロールバックする。
  • それでも候補が複数残っている場合は、各候補の特殊化関係を調べ、特殊化関係にあれば負けたほうを外す。

特殊化関係はcandidate_should_be_dropped_in_favor_ofにある。これは以下の規則になっている。

  • 型引数候補は最も強い。異なる型引数候補同士は比べられない。
  • 射影候補(impl Traitを含む)とトレイトオブジェクト候補(組込みトレイトオブジェクト候補を含まない)は、その次に強い。
  • それ以外の候補は上記よりも弱く、お互いには比べられない。ただし、以下の例外がある。
    • 2つの実装候補について、実装が特殊化関係にある場合は、より特殊なほうがより強い。
    • 2つの実装候補について、 #![feature(overlapping_marker_traits)] で、両方の実装がアイテムを持たず、極性も等しい場合には、同じ強さである。

同じ強さである場合も含めて、より弱いものから順番に脱落させていく。これにより最強の候補が1つだけ残ったら選別は成功となる。

トレイト選択では未解決の型推論変数が含まれていることがあるため、コヒーレンスに関係なく、複数の候補が残る場合があり、その場合はエラーになる。逆に、トレイト選択では基本的に現在見えている実装から探索するので、「これしか該当する実装がないから」という理由により型推論が進むことがある。以下はその例である。

use std::ops::Add;
fn f<T: Add<i32>>(t: T) {
    t + Default::default(); // OK
}
fn g<T: Add<i32> + Add<i8>>(t: T) {
    t + Default::default(); // Error
}
fn main() {
    
}

より奇妙な例としては、以下のようなものも考えられる。

fn f<T>() {
    let x : (_, T); // Error
}
fn g<T: ?Sized>() where (i32, T): Sized {
    let x : (_, T); // OK
}
fn main() {
    
}

収集時には曖昧でも、選別によって曖昧性がなくなる例としては、例えば以下のようなものが考えられる。

trait Foo<Y> {
    fn y() -> Y;
}
trait Bar {}
trait Baz {}

impl<T: Bar> Foo<i32> for T {
    fn y() -> i32 { 0 }
}
impl<T: Baz> Foo<i8> for T {
    fn y() -> i8 { 0 }
}

impl Bar for i32 {}
impl Baz for i64 {}

fn f() {
    let _ = <i32 as Foo<_>>::y();
}

fn main() {
}

否定実装の処理

既定実装と異なり、否定実装は収集段階では通常の実装と同様に扱われている。否定実装の特徴は、この実装が選別された場合にはコンパイルエラーとなるという点である。

自己再帰的な制約の処理

自己再帰的なデータ構造の Send の処理などで、自己再帰的な制約が出てくることがある。これは evaluate_stackの一部分で処理されている。以下のように実装されている。

  • トレイト制約の処理中は、再帰的に処理中のトレイト制約をスタックに積む。
  • 現在のトレイト制約が、再帰的に処理中のトレイト制約と等しいときは、収集処理をせずにすぐにOKを返す。

まとめ

トレイト選択の詳細について説明した。ただし、より一般の制約のfulfillmentや、coherence checkerなどについては言及していない。