トレイトの整合性: 孤立規則,特殊化

あまり実用的な内容ではありませんが、以前からトレイト整合性(trait coherence)周りの話を調べてみようと思いつつ先延ばしにしていたので、これを機に書いてみたいと思います。文中に「実装」という単語が頻繁に出てきて混乱するかもしれませんが、Rustコード中という文脈で出てくる場合は`impl`宣言のことです。

トレイト整合性はTRPLや言語リファレンスでは触れられていません。しかし、このトレイト整合性を保つために実装されている[E210](https://doc.rust-lang.org/error-index.html#E0210)などに遭遇したことのある方はそれなりに居るのではないでしょうか。また、現在unstableな機能として実装されている特殊化もこのトレイト整合性に関わるものです。

# トレイト整合性とは

トレイト整合性とは、ある型に対して実装されたあるトレイトは、ただ1つの実装を持つという性質です。例えば、簡単な例だと`i32`という型は`Eq`,`Ord`,`Add<i32>`,`Add<&i32>`……等のトレイトを実装していますが、`impl Eq for i32 { .. }`という実装が2通りあってはいけないということです。どの処理を行えばいいのか決定できませんからね。

なんだか明白な気もしますが、Rustでは「任意の型に対してトレイトを実装する」「あるトレイト境界(制約)を満たす型に対してトレイトを実装する」といったことも可能です。たとえば、2つの異なる実装が、同じ型に対し、ある特定の条件を満たしたとき同時に実装されてしまうということがあります。

```rust
trait From<T> { .. }
impl<T> From<T> for T { .. } // (A)
impl<T, U> From<Pack<U>> for Pack<T> { .. } // (B)
// T = U において(A)と(B)が重複
```

```rust
trait ToString { .. }
impl<T: Display> ToString for T { .. } // ジェネリックな実装
impl<'a> ToString for &'a str { .. } // &strに最適化された実装
// &strはDisplayを実装しているので衝突する
```

また、トレイト・型・トレイト実装が別々のクレートに分かれていた場合はどうなるのでしょうか？

```rust:クレートa
trait Foo {
    fn foo(&self);
}
```

```rust:クレートb
extern crate a;

impl a::Foo for i32 {
    fn foo(&self) { println!("b"); }
}
```

```rust:クレートc
extern crate a;

impl a::Foo for i32 {
    fn foo(&self) { println!("c"); }
}
```

`i32::foo`をbから呼んだ場合とcから呼んだ場合で、結果が違っては混乱の元です。クレートaにi32をFooとして渡すとどうなるでしょう? これではインタフェースとしての意味がありませんね。

以上のようなコードは整合性を守るため、この時点でコンパイラによって弾かれます。実際に不整合性が露見するような使い方がされているかどうかは関係ありません。`impl`の実装対象が重複している場合は[E0119](https://doc.rust-lang.org/error-index.html#E0119)(conflicting implementations of trait)、他クレートの型・トレイトが絡むトレイト実装が次に述べる孤立規則に反する場合は[E0210](https://doc.rust-lang.org/error-index.html#E0210)が報告されます。

# 孤立規則

孤立規則(orphan rules を当記事ではこう表記しています)は、先に挙げたような同じ型がクレートによって異なるトレイト実装を持つという事態を防ぐためのルールです。

トレイト実装の重複は当然、整合性を壊しますが、他クレートのトレイト実装と被る可能性のあるものが書けてしまうというだけでも問題です。潜在的な破壊的変更となってしまうからです。トレイト実装の追加は機能追加・拡張として行われることが多いですから、それが破壊的変更を引き起こしてしまうというのは、互換性を重視する[^comp]というRustの開発方針に従う限り今後の標準ライブラリへの機能追加を困難にしてしまいます。

そこでいくつかの規則を定め、こういった可能性のあるような実装をそもそも書くことが出来ないようになっています。具体的な規則は[RFC 1023](https://github.com/rust-lang/rfcs/blob/master/text/1023-rebalancing-coherence.md)で述べられています。簡単に説明すると、次のような実装に対し

```
impl<実装の型引数> Trait<トレイトの型引数>
    for 実装対象
    where 実装のトレイト境界
```

以下の条件が課されます。

* 実装のトレイト境界を見るとき「他クレート由来のトレイトはあらゆる他クレート由来の型に対して実装される可能性がある」と仮定しても重複が発生しない
* `Trait`が同クレート内で定義されているものであるか、あるいは`Trait`が同クレート内のものでない場合次の条件のいずれかを満たす
    * 「実装対象」が同クレート内の型である
    * 「トレイトの型引数」の最初から連続して1つ以上が同クレート内の型である

といった感じです。例えば、

```rust
impl<'t> Replacer for &'t str // &str: FnMut(&Captures) -> String が成立するかもしれない!
impl<F> Replacer for F where F: FnMut(&Captures) -> String
```

```rust
impl From<Vec<i32>> for Vec<String> // 外部のトレイトを外部の型に実装しようとしている
```

といった実装を標準ライブラリの外から行うことは、孤立規則の下では不可能になります。(ただし前者には後で述べるような例外が適用されていて、コンパイルが通ります)

これらの規則により、トレイトを定義したクレートはブランケット実装(blanket impl)と呼ばれるものや参照型に対する実装、同クレートや3rd partyクレートの型に対する実装などを必要であれば提供しなければなりません。他のクレートからでは、それらを実装することは出来ないためです。

```rust
impl<T> Foo for T where T: Bar {} // ブランケット実装: Barを実装していればFooも実装される

impl<'a, T> Baz for &'a mut T where T: Baz {..} // 参照型に対する実装

impl Baz for self::Hoge {..} // ローカルな型に対する実装

impl<T> Baz for Box<T> where T: Baz {..} // Box(標準ライブラリの型)に入っていてもFooが実装される
```

`Iterator`をトレイト境界とする関数に対し、イテレータが`Box`に入っていたり`&mut it`としたりしてもそのまま渡せるのは、このような実装が標準ライブラリで行われているからですね(実際はトレイトオブジェクトも扱うために`?Sized`境界が付いています)。

孤立規則に反してしまった場合、手がないのかというとそうではありません。いわゆるnewtypeパターンを使うことで回避できます。

```rust
struct NewType(Vec<i32>);
```

というように目的の型を包んでしまえば、ローカルの型扱いになるのでどんなトレイトを実装しようと孤立規則に反することはありません。まったく別の型になるので、実装したかったもの以外のトレイトも実装する必要が出てくるのですが、[newtype_derive](https://docs.rs/newtype_derive/)というライブラリを使うと手間が省けます。

## `#[fundamental]`

> 「他クレート由来のトレイトはあらゆる他クレート由来の型に対して実装される可能性がある」と仮定しても重複が発生しない

と書きました。これにより、次のコードがコンパイラに弾かれてしまいます(RFCで使われている例です)。

```rust
impl<'t> Replacer for &'t str
impl<F> Replacer for F where F: FnMut(&Captures) -> String
```

`&str`が`FnMut`を実装していないとは言えないわけです。コンパイラが当然知っている「`&str`は`FnMut`を実装していない」という事実を使って合法にしてしまっても良いのでは、と思われるかもしれません。しかしそのような判定を行うようにすると、例えば新たなトレイト実装`impl Trait for T`を追加すると、そのクレートに依存しているコードが`T: !Trait`[^bang_trait]を前提に書かれている場合に壊れてしまうことになります。

ですが、`&str`が関数として呼び出せないのは明らかですよね。クロージャと他の型を同じインタフェースで扱えるのは確実に便利ですし、このようなパターンは他でも出てくることがありそうです。そこで導入されている特例がunstableな[^unstable]`#[fundamental]`属性です。次のトレイトが`#[fundamental]`属性を付けて定義されています。

* `FnOnce`
* `FnMut`
* `Fn`
* `Sized`

この属性をトレイトに付けることにより、他のクレートからも`T: !Trait`という事実をコンパイラに認めさせ、実装を共存させることができます。もちろん、当該トレイトの実装対象を増やす(今まで実装していなかった既存の型に実装する)と破壊的変更になるのは変わりませんが、これら標準ライブラリ(正確にはcore)で定義されているトレイトだけの例外とすることで影響を抑えています。

[^comp]: 標準ライブラリ・コンパイラはバージョン間の後方互換を保証しています。破壊的変更がまったく無い訳ではありませんが、crates.io上のクレート全てをパッチを適用したコンパイラで一度ビルドしてみるなど、影響の範囲を十分に調査した上で行われています。
[^bang_trait]: Rust界隈では「型`T`は`Trait`を実装していない」ということを示すのに、架空の構文を使い`T: !Trait`と書くことがあります。将来的にネガティブな境界が書けるようになれば、この構文が実際に使われるようになるかもしれません。

# 特殊化

整合性は保ちつつ、重複する実装を追加できるようにする拡張が行われています。[RFC 1023](https://github.com/rust-lang/rfcs/blob/master/text/1210-impl-specialization.md)において提案され、unstableな機能として実装されている特殊化(specialization)です。

これにより、先ほど載せた`ToString`の例が実装できます。特殊化元の実装が持つメソッドに`default`指定を行うことで特殊化が可能になります。

```rust
trait ToString {
    fn to_string(&self) -> String;
}

// ジェネリックな実装
impl<T: Display> ToString for T {
    default fn to_string(&self) -> String { .. }
}

// &strに最適化された実装
impl<'a> ToString for &'a str {
    fn to_string(&self) -> String { .. }
}
```

実際に、標準ライブラリにおいて特殊化を用いてこのように実装されています。`&str`を`String`に変換するのは非常によく使われる処理ですが、ジェネリックな実装では文字列フォーマット機構を通すことになり結構なパフォーマンスロスがありました。これが古いRustコードで`to_string`の代わりに`to_owned`が使われていた理由です。(現在では特殊化のお陰でどちらも等価になりました。)

さて、問題は特殊化できる条件です。冒頭で、トレイトが重複する例としてもう一つ出したコードがありますね。こちらは、特殊化を使っても実装できません。

```rust
impl<T> From<T> for T { .. } // (A) 特殊化元?
impl<T, U> From<Pack<U>> for Pack<T> { .. } // (B) 特殊化を行う?
// T = U において(A)と(B)が重複
```

細かいルールは[RFC](https://github.com/rust-lang/rfcs/blob/master/text/1210-impl-specialization.md#permitting-overlap)で正確に定義されていますが、要するに「特殊化元の実装の適用先は、特殊化を行う実装の適用先を完全にカバーしていなければならない」ということです。上の例では、`T = U`の場合確かにAとBの実装は重複しますが、それ以外の場合は重なりません。

## 共通実装

ちなみに、こういった特殊化では解決できない場合においてもトレイト実装のディスパッチを可能にする方法として、まだRFCですらない段階ですが[intersection impls (lattice impls)](http://smallcultfollowing.com/babysteps/blog/2016/09/24/intersection-impls/) という案が出ています。
このように、実装間の共通部分にあたる実装を明示的に書かせることで曖昧さをなくすというものです。

```rust
impl<T> From<T> for T { .. } // A
impl<T, U> From<Pack<U>> for Pack<T> { .. } // B
impl<T> From<Pack<T>> for Pack<T> { .. } // A∩B
```

[^unstable]: unstableな機能は標準ライブラリ内からは自由に使うことができます。

# おわりに

トレイト整合性周りの話でした。[2017年のロードマップ案](https://internals.rust-lang.org/t/roadmap-2017-productivity-learning-curve-and-expressiveness)にも関連する課題が出ていたり、特殊化のstabilizationへの取り組みが取り上げられているので今後も何かしら変化があることと思われます。