型パラメータとライフタイムパラメータの変性

変性に関するより一般的な背景については、background 付録を参照してください。

型チェックの際には、型パラメータとライフタイムパラメータの変性を推論しなければなりません。このアルゴリズムは、PLDI’11 で発表され、Altidor らによって書かれた論文 “Taming the Wildcards: Combining Definition- and Use-Site Variance” のセクション 4 から採用しており、以降は The Paper と呼びます。

この推論は、コード内での型の使用を明示的に考慮しないように設計されています。型 X に定義された型パラメータの変性を決定するには、型 X の定義と、それが参照する任意の型の定義のみを考慮します。

struct や enum のような データ型 に見られる型パラメータについてのみ変性を推論します。このような場合、変性が何を意味するかについては、かなり単純な説明があります。型パラメータまたはライフタイムパラメータの変性は、A と B の関係（それぞれ 'a と 'b の関係）に基づいて、T<A> が T<B> のサブタイプであるかどうか（それぞれ T<'a> と T<'b>）を定義します。

トレイト、関数、または impl に見られる型パラメータについては、変性を推論しません。トレイトパラメータにおける変性には確かに意味があり得ます（かつてはそれを計算していました）が、実際には意味がかなり微妙で、実用上それほど有用ではないため、削除しました。詳細については addendum を参照してください。一方、関数/impl パラメータにおける変性は意味をなしません。これらのパラメータはインスタンス化された後に忘れられ、型やコンパイル済みの副産物には永続しないからです。

表記

この章全体で The Paper の表記を使用します:

+ は 共変性 です。

- は 反変性 です。

* は 双変性 です。

o は 不変性 です。

アルゴリズム

基本的な考え方は非常に単純です。定義された型を反復処理し、型パラメータ X の各使用について、X の変性がその使用箇所の変性に対して有効でなければならないことを示す制約を蓄積します。その後、すべての制約が満たされるまで、X の変性を反復的に洗練します。解は常に存在します。なぜなら、極限ではすべての型パラメータを不変と宣言でき、その場合すべての制約が満たされるからです。

簡単な例として、次を考えてみましょう:

enum Option<A> { Some(A), None }
enum OptionalFn<B> { Some(|B|), None }
enum OptionalMap<C> { Some(|C| -> C), None }

ここでは、次の制約を生成します:

1. V(A) <= +
2. V(B) <= -
3. V(C) <= +
4. V(C) <= -

これらは、(1) A の変性が最大でも共変でなければならないこと、 (2) B の変性が最大でも反変でなければならないこと、そして (3, 4) C の変性が最大でも共変かつ反変でなければならないことを示しています。これらの結果はすべて、次のように定義される変性束に基づいています:

   *      Top (bivariant)
-     +
   o      Bottom (invariant)

この束に基づくと、解 V(A)=+, V(B)=-, V(C)=o が最適解です。なお、すべての変数を不変と宣言するだけの単純な解は常に存在します。

なぜ固定点反復が必要なのか疑問に思うかもしれません。その理由は、使用箇所の変性が、それ自体、他の型パラメータの変性の関数であり得るからです。完全に一般化すると、制約は次の形を取ります:

V(X) <= Term
Term := + | - | * | o | V(X) | Term x Term

ここで表記 V(X) は、型/リージョンパラメータ X の、それを定義しているクラスに対する変性を示します。Term x Term は、論文で定義されている「変性変換」を表します:

型変数 X の型式 E における変性が V2 であり、クラス C の対応する型パラメータの定義箇所における変性が V1 である場合、型式 C<E> における X の変性は V3 = V1.xform(V2) です。

制約

where 句を持つ struct または enum がある場合:

struct Foo<T: Bar> { ... }

Bar に対する T の変性が、Foo に対する T の変性に影響するか疑問に思うかもしれません。私はそうではないと主張します。理由は次のとおりです。 T が Bar に対して不変だが、Foo に対して共変であると仮定します。そして、 X <: Y であるとき、Foo<X> が Foo<Y> にアップキャストされるとします。しかし、X : Bar であっても、Y : Bar は成り立ちません。その場合、アップキャストは不正になりますが、それは変性の失敗によるものではなく、むしろターゲット型 Foo<Y> 自体が整形式ではないからです。基本的に、変性を考慮する前に、関係するすべての型の整形式性を仮定できます。

依存グラフの管理

変性はクレート全体に対する推論であるため、注意しなければ、その依存グラフは非常に混乱したものになり得ます。これを解決するため、2 つのクエリへリファクタリングします:

crate_variances は、現在のクレート内のすべての項目について変性を計算します。
variances_of は、個別の読み取り対象に対する変性にアクセスします。これは crate_variances を要求し、関連するデータを抽出することで機能します。

variances_of の読み取りに限定すれば、コードはその特定の項目の推論にのみ依存することになります。

最終的に、この構成は red-green algorithm に依存しています。特に、すべての変性クエリは、実質的に（crate_variances を通じて）クレート全体のすべての型定義に依存しますが、ほとんどの変更は変性推論の実際の結果に変更をもたらさないため、variances_of クエリは再評価された後に green と見なされることになります。

補遺: トレイトにおける変性

上で述べたように、以前はトレイトにおける変性を許可していました。これは、メソッドシグネチャにおけるトレイト型パラメータの出現に基づいて計算され、トレイトオブジェクト内の vtable（およびトレイト境界内の「仮想」vtable や辞書）の互換性を表すために使用されていました。1 つの複雑な点は、関連型の変性がそれほど明らかではないことでした。関連型は射影して取り出され、多種多様な用途に使われ得るため、いつ X<A>::Bar の変動を許可して安全なのか（あるいは実際、それが何を意味するのかさえ）明確ではありません。さらに（以下で扱うように）、関連型を持つ任意のトレイト上のすべての入力は不変でなければならず、適用可能性が制限されていました。最後に、すべてのトレイト型パラメータが変性を持つことを保証するために必要な注釈（MarkerTrait, PhantomFn）は、わずかな利益の割に混乱を招き、煩わしいものでした。

歴史的な参考のために、変性とトレイトマッチングをどのように解釈できるかを示すテキストをいくらか保存しておきます。

変性とオブジェクト型

struct や enum と同様に、A と B の関係に基づいて、 2 つのオブジェクト型 &Trait<A> と &Trait<B> の間のサブタイピング関係を決定できます。オブジェクト型では、Self 型パラメータを無視する点に注意してください。これは未知であり、動的ディスパッチの性質により、適切な Self 型を期待する関数を常に呼び出すことが保証されます。しかし、他の型パラメータについては注意しなければなりません。そうしないと、ある型を期待している関数を、別の型を提供して呼び出してしまう可能性があります。

私の意味するところを見るために、次のようなトレイトを考えてみましょう:

```rust
trait ConvertTo<A> {
    fn convertTo(&self) -> A;
}

直感的には、1つのオブジェクト O=&ConvertTo<Object> と、別の S=&ConvertTo<String> がある場合、String <: Object なので S <: O になります（Java 風の「string」と「object」型を想定しています。これは私がサブタイピングの例としてよく使うものです）。実際のアルゴリズムは、（明示的な）型パラメーターを、それぞれの分散を考慮しながらペアごとに比較するものになります。ここでは、型パラメーター A は共変です（戻り値の位置にのみ現れます）。したがって、String <: Object であることを要求します。

ただし、（暗黙の）Self 型パラメーターの束縛は考慮していないことに気づくでしょう。実際、それは未知なので、それで問題ありません。そのパラメーターを無視できる理由は、呼び出しが発生するまでその値を知る必要がないからです。そしてその時点では、（あなたが言ったように）仮想ディスパッチの動的な性質により、実行されるコードは、メソッドを呼び出した特定のオブジェクトについて Self がたまたま束縛されているどの値に対しても正しいものになります。したがって Self は A とは異なります。呼び出し元は、メソッド convertTo() の戻り値の型を知るために、A が既知であることを必要とするからです。（余談ですが、Self がレシーバー位置以外に現れるメソッドをオブジェクト経由で呼び出せないようにする規則があります。）

トレイトの分散と vtable 解決

しかし、トレイトはオブジェクトと一緒に使われるだけではありません。ある impl が特定のトレイト境界を満たすかどうかを判断する際にも使われます。ここで状況を設定するために、次のような関数があると想像してください。

fn convertAll<A,T:ConvertTo<A>>(v: &[T]) { ... }

ここで、Object に対する ConvertTo の実装があると想像してください。

impl ConvertTo<i32> for Object { ... }

そして、文字列の配列に対して convertAll を呼び出したいとします。さらに、何らかの理由で型パラメーター T の値として String を明示的に指定するとします。

let mut vector = vec!["string", ...];
convertAll::<i32, String>(vector);

これは合法でしょうか？別の言い方をすると、Object 用の impl を String 型に適用できるでしょうか？答えは yes ですが、その理由を見るには、何が起こるかを展開してみる必要があります。

convertAll は、ベクター内のエントリの1つへのポインターを作成し、それは &String 型になります
その後、オブジェクトとともに使用することを意図した convertTo() の impl を呼び出します。これは fn(self: &Object) -> i32 という型を持ちます。

&String <: &Object であるため、self に &String 型の値を渡しても問題ありません。

OK、直感的にはこれを合法にしたいので、これを分散の話に戻し、正しい結果を計算しているかどうかを見てみましょう。まず、「Object,i32 用の impl は、String,i32 用の impl が期待される場所で使用可能か？」という問いをどのように表現するかを考えなければなりません。

型クラスの辞書渡し実装を考えるとわかりやすいかもしれません。その場合、convertAll() は impl を表す暗黙のパラメーターを受け取ります。要するに、私たちは次の型の impl を持っています。

V_O = ConvertTo<i32> for Object

そして関数プロトタイプは、次の型の impl を期待します。

V_S = ConvertTo<i32> for String

どの引数でもそうであるように、これは、与えられた値の型（V_O）が期待される型（V_S）のサブタイプであれば合法です。では、V_O <: V_S でしょうか？答えは、さまざまなパラメーターの分散に依存します。この場合、Self パラメーターは反変であり、A は共変なので、次のことを意味します。

V_O <: V_S iff
    i32 <: i32
    String <: Object

これらの条件は満たされているので、問題ありません。

分散と関連型

関連型を持つトレイト、または少なくとも射影式を持つトレイトは、それらのすべての入力に関して不変でなければなりません。これがなぜ理にかなっているかを見るために、トレイト参照に対するサブタイピングが何を意味するかを考えてみましょう。

<T as Trait> <: <U as Trait>

これは、T as Trait であることを知っているなら、U as Trait であることも知っている、という意味です。さらに、それを辞書渡しスタイルとして考えるなら、<T as Trait> の辞書は、<U as Trait> の辞書が期待される場所で安全に使用できる、という意味です。

問題は、<T as Trait> から型を射影できる場合、T==U でない限り、<U as Trait> から射影される型との関係がまったく不明であることです（詳細は #21726 を参照してください）。 Trait を不変にすることで、これが真であることを保証します。

関連するもう1つの理由は、関連型を持つトレイトを不変にしなかった場合、射影が単一の結果を持つ関数ではなくなることです。次を考えてみてください。

trait Identity { type Out; fn foo(&self); }
impl<T> Identity for T { type Out = T; ... }

ここで <&'static () as Identity>::Out がある場合、これは任意の 'a について &'a () として有効に導出できます。

<&'a () as Identity> <: <&'static () as Identity>
if &'static () < : &'a ()   -- Identity is contravariant in Self
if 'static : 'a             -- Subtyping rules for relations

一方、この変更により、<'static () as Identity>::Out は常に &'static () になります（これは別途 'a () にアップキャストされるかもしれません）。これは #21750 の解決に役立ちました。

Keyboard shortcuts

Rust Compiler Development Guide