概要: Rustの impl が定義できる型にはコヒーレンスと呼ばれる制限がある。これについて説明する。なお、この記事では特殊化がない前提で説明する。

コヒーレンス初心者のための概説

以下のように impl が重複していたり、自分のところ以外の型の impl を定義しようとするとエラーになる場合がある。これをコヒーレンスという。

struct A;


// overlap rule 違反
impl A {
    fn f(x: i32) {}
}
impl A {
    fn f(x: i8) {}
}

// orphan rule 違反
impl Option<A> {
}

コヒーレンスの目的

コヒーレンスには以下の2つの目的がある。

同じトレイト/型に対して、状況に応じて異なる実装が採用されてしまうことを防ぐ。
将来の上流クレイトの変更による下流クレイトへの影響を最小限に留める。

コヒーレンスの分類

コヒーレンスは孤児規則 (orphan rule, オーファン規則) と重複規則 (overlap rule, オーバーラップ規則) に分かれている。またこれに加えて、 impl の適格性チェックで検査される引数の唯一性もコヒーレンスと目的を同じくするのでここで扱う。

引数の唯一性規則

impl はそれ自体がジェネリック引数を持つが、これらの引数が入力から一意に特定できる必要がある。具体的には以下のように定義されている。

入力とは、以下の3つである。
- Self 型
- トレイトの型実引数 (トレイト実装の場合)
- where 節に書ける境界
impl の生存期間引数は、後方互換性のため原則としてチェックされない。ただし、関連型で使われている生存期間引数については、入力のどこかで使われている必要がある。
型引数はRFC 0447に定めるとおりに制約されている (constrained) 必要がある。ただし、型引数が制約されているという性質は、以下の規則により帰納的に定義される。
- Self 型またはトレイトの型実引数の一部(射影型、匿名型は除く)に出現する型引数は、制約されている。
- トレイトが <T as Trait<U>>::Output == V のような射影型の制約を持っており、 <T as Trait<U>>::Output 側に出現する型引数(射影型、匿名型も含む)が全て制約されているとき、 V 側の一部(射影型、匿名型は除く)に出現する型引数は、制約されている。

struct A<X>(X);

impl<X, Y> A<(X, Y)> {} // OK
// impl<X> A<()> {} // Error
// impl<X: Iterator> A<X::Item> {} // Error
// impl<X: Iterator<Item=Y>, Y: Iterator<Item=X>> A<i32> {} // Error

孤児規則

孤児規則は、下流クレイトが定義できる実装を制限するものである。

固有実装の孤児規則

固有実装の孤児規則は以下の通りである。

固有実装の Self 型は、ユーザー定義型またはトレイトオブジェクト型でなければならない。 (型別名は展開する)
Self の型コンストラクタは、 impl と同じクレイトで定義されたものでなければならない。

ただし、例外として、標準ライブラリで基本型に対する固有実装が定義されている。

struct A;

impl A {}
// impl Vec<A> {} // Error
// impl Box<A> {} // Error
// impl<'a> &'a A {} // Error

既定実装の孤児規則

既定実装は、同じクレイトで定義されたトレイトに対してのみ与えることができる。

#![feature(optin_builtin_traits)]

impl Copy for .. {} // Error
fn main() {}

トレイト実装の孤児規則

トレイト実装の孤児規則はRFC 1023で解説されており、やや複雑である。

impl<P1, .., Pm> T0 for Trait<T1, .., Tn> が別のクレイトのトレイトに対して定義する場合は、以下の規則を満たさなければならない。

ある i が存在して、 Ti は局所的である。
同じ i について、 T0, T1, ..., T(i-1) は型引数・射影型を持たない。

ただし、ある型が局所的であるとは、以下のいずれかである。

同じクレイトで定義されている構造体・列挙型・共用体または、同じクレイトで定義されているトレイトのトレイトオブジェクトである。
基礎型 (&T, &mut T, Box<T>, Fn<T>, FnMut<T>, FnOnce<T> のいずれか)であり、 T は局所的である。

use std::ops::Add;

// OK
struct A;
impl<'a, T> Add<T> for &'a A { type Output = (); fn add(self, _: T) {} }

use std::ops::Add;

// Error
// struct A;
// impl<'a, T> Add<&'a A> for T { type Output = (); fn add(self, _: &'a A) {} }

ただし、該当トレイトが既定実装をもつ場合は制約が厳しくなる。この場合は &T などの基礎型は局所性を継承しない。

#![feature(optin_builtin_traits)]

use std::panic::UnwindSafe;

struct A;
// impl !UnwindSafe for Box<A> {} // Error

なお、 #[fundamental] (現在は不安定な属性) を一般のライブラリが使う場合を考えると、規則はより複雑になる。

トレイト実装の孤児規則 (完全版)

より一般の #[fundamental] 型を考える場合の孤児規則は以下のようになる。

ある i が存在して、 Ti は局所的 (local type) である。
同じ i について、 T0, T1, .., Ti は網羅的 (type without uncovered type parameters) である。

ただし、ある型が局所的であるとは、以下のいずれかである。

同じクレイトで定義されている構造体・列挙型・共用体または、同じクレイトで定義されているトレイトのトレイトオブジェクトである。
基礎型であり、その型引数も全て局所的である。

また、ある型が網羅的であるとは、以下のいずれかである。

同じクレイトで定義されている構造体・列挙型・共用体または、同じクレイトで定義されているトレイトのトレイトオブジェクトである。(型引数を持っていてもよい)
基礎型であり、その型実引数も全て網羅的である。
型仮引数・射影型を持たない。

ある型コンストラクターが基礎型であるとは、以下のいずれかである。

参照型 &T, &mut T である。
#[fundamental] のついた構造体・列挙型・共用体または、 #[fundamental] のついたトレイトのトレイトオブジェクトである。

重複規則

重複規則は、既知の重複する実装を禁止する規則である。(未知の重複する実装は孤児規則により防がれる)

固有実装の重複規則

固有実装の重複規則は以下の通りである。

同じ型コンストラクタに対する impl は、それらが重複 (後述) すると判断された場合に限り、同じ名前のメソッド等を持つことができない。

struct A<X>(X);

// OK
impl A<i32> {
    fn f() {}
}
impl A<i8> {
    fn f(&self) {}
}
impl A<i8> {
    fn g() {}
}

struct A<X>(X);

// Error
impl<X> A<(X, i32)> {
    fn f() {}
}
impl<X> A<(i32, X)> {
    fn f() {}
}

既定実装の重複規則

同じトレイトに対する既定実装が複数あってはいけない。

#![feature(optin_builtin_traits)]

trait Foo {}
impl Foo for .. {}
impl Foo for .. {}

トレイト実装の重複規則

トレイト実装の重複規則は以下の通りである。

同じトレイトに対する重複 (後述) する impl があってはいけない。
トレイトオブジェクト型に対して、その祖先トレイトの実装を与えてはいけない。

trait Foo {}

// Error
impl<X> Foo for (i32, X) {}
impl<X> Foo for (X, i32) {}

trait Foo<X> {}
trait Bar<X> : Foo<X> {}

impl Foo<i32> for Bar<i8> {} // Error

重複判定

2つの impl が重複とみなされる条件は複雑で、場合によっては直感に反する挙動をすることがある。以下がその重複判定処理である。

2つの impl のトレイト/型の部分を単一化する。単一化に失敗したら排反である。
単一化に成功したら、それによって発生した制約 (元の impl に由来する where 境界や、射影型の制約) をそれぞれ解く。 (ある制約を解いた結果は、別の制約の判定には使わない)
適用不可能な制約があったら、排反である。
全ての制約が適用可能(曖昧含む)ならば、重複である。

ここで出てくる制約の解決処理は、以前の記事で説明したトレイト選択によるものである。ただし、重複判定では、トレイト選択がクレイト際モード(intercrate mode)で行われる。

クレイト際モードでは、トレイト選択の動作が以下のように変化する

型変数を含むトレイト制約の扱い

クレイト際モードでは、いずれかのSelf/実引数が型変数(型引数や射影型は型変数になる)であるようなトレイト制約は全て曖昧と解釈される。例えば、

trait Foo<X> {}
trait Bar<X> {}
impl<X, T> Foo<X> for T where T: Bar<X> {}
impl<X> Foo<X> for i32 {}

は重複でエラーになる。この2つの impl が重複するためには i32: Bar<?X> が解決可能である必要があるが、これは下流クレイトで

struct A;
impl Bar<A> for i32 {}

のような実装があったときに満たされうるからである。

ただし、型変数が何らかの型コンストラクタの内側にある場合は問題ない (これはバグの可能性がある)。

trait Foo<X> {}
trait Bar<X> {}
impl<X, T> Foo<X> for T where T: Bar<X> {}
impl<X> Foo<(X,)> for i32 {} // OK

不可知なトレイト制約の扱い

(型変数を含むかもしれない)トレイト制約が不可知 (not knowable) であるとは、

局所的な型実引数をもたず、かつ
以下のどちらかの条件を満たす
- 自分以外のクレイトで定義された #[fundamental] でないトレイトに対する参照である。または
- 型変数への代入の方法によっては局所的な型実引数を持ちうる (これが満たされることはない気がするが、よくわからない)

ことである。不可知なトレイト制約は強制的に曖昧と見なされる。

trait Foo {}
impl<T> Foo for T where T: ::std::fmt::Octal {}
impl Foo for () {} // Error

この例では、 (): ::std::fmt::Octal が満たされることが重複する条件である。

孤児規則より、これが下流クレイトによって満たされることはないことはすぐにわかる。また、現時点では (): ::std::fmt::Octal は満たされていない。しかし、このトレイト制約は不可知であるため、上記の impl は重複と見なされてしまう。

この規則は、上流クレイトのバージョンアップを想定してのことである。 RFC 1105 で説明されているように、マイナーバージョンアップでも下流クレイトが壊れる可能性はゼロではないが、この規則により以下のようなbreakageが発生しないことが保証される。

#[fundamental] でないトレイトに、局所的な型実引数を持ち、全ての型引数が網羅的であるような実装を追加することによる、下流クレイトの重複規則の破壊。

まとめ

重複規則は、同じクレイト内や、上流クレイトとの衝突を防ぐ。
孤児規則は、兄弟クレイトとの衝突を防ぐ。
重複規則ではクレイト際モードが採用される。これにより以下のような衝突を防ぐ。
- 下流クレイトが関与することによる、同じクレイト内や上流クレイトとの衝突。
- 上流クレイトのマイナーバージョンアップによる衝突。

簡潔なQ

Rustのコヒーレンス