[Rust] Associated Types と Trait Object

以下の駄文は独自研究を多く含んでおり、間違っている可能性は大いにある。

実際の所、後日処理系のコードを読んで確認するつもりである。(そのためのメモという意味合いもある)

# Associated Types と Type Parameters

RustのAssociated typesとは、Traitに関連する型を提供する機能である。例えば標準ライブラリの[`std::iter::Iterator`](https://doc.rust-lang.org/stable/std/iter/trait.Iterator.html)の実装は以下のようになっている。

```rust
pub trait Iterator {
    type Item;
	// ...
}
```

ここで`Iterator::Item`がAssociated typesであり、これは`Iterator` traitが実装される型`T`に応じて固有の型`<T as Iterator>::Item`を示す。

一方、Type parametersとは、文字通りtraitに対して型パラメータを渡す機能である。例としては[`std::convert::From`](https://doc.rust-lang.org/stable/std/convert/trait.From.html)がある。

```rust
pub trait From<T> {
    fn from(T) -> Self;
}
```

これらの違いとしては、Type parameterの場合、型`U`に対して複数の`From<T>`を同時に実装することができる(例えば型`u32`は`From<bool>`と`From<char>`を同時に実装している)
一方、Associated typesでは型`T`が決まればAssociated typesも只一通りに決まるのである。

# 本当か?

...と書いたが、実は例外が存在する。それはTrait objectだ。

Trait objectは、`trait MyTrait`が与えられた時に`dyn MyTrait`という型を生成する機能である。すなわち、`MyTrait`を実装する型を、一定の条件の下(これをObject safetyという)で`dyn MyTrait`型に型変換することができるのである。

```rs
let a = 123_8;
let a = a as dyn Debug;
```

しかし、実際は上記のコードを実行することはできない。RustではDST(Dynamically Sized Types)を直接扱えないからである。そのため[以下のように](https://play.rust-lang.org/?version=stable&mode=debug&edition=2021&gist=b4aff532d533209ea4645d6c61bbed84)Boxを使う。

```rs
let a = Box::new(123_i8);
let a = a as Box<dyn Debug>;
```

この例では、`i8`型の値を`dyn Debug`型に型強制しているのである。`i8`は`Debug`トレイトを実装し、`Debug`トレイトは Object safe なためこの型変換が許される。

# トレイトオブジェクトの何が問題だろうか？

さて、先程以下のように書いた。

> 一方、Associated typesでは型`T`が決まればAssociated typesも只一通りに決まるのである。

では、以下のような(動かない)例を考えてみよう。

```rs
trait Tr {
	type X;
}
struct S1;
struct S2;
impl Tr for S1 {
	type X = i8;
}
impl Tr for S2 {
	type X = u8;
}
fn func(_: Box<dyn Tr>) -> <dyn Tr as Tr>::X { ... }
```

ここで、`func()`の戻り値型はどうなるだろうか?

- trait `Tr` は Associated types `Tr::X`を持つ
- 型`T`が trait `Tr` を実装している場合、 Associated types `Tr::X` は `T` に依存して一意に決まる
- 上記の例で`S1`, `S2`, `dyn Tr` はそれぞれ型であり、trait `Tr`を実装している
- 実際、`<S1 as Tr>::X = i8`, `<S2 as Tr>::X = u8`である
- では、`<dyn Tr as Tr>::X`は何だろうか?

この問題は、Trait objectの「複数の型を一つの型として扱う」という特性とAssociated typesの相性が悪いのが原因である。Rustの解決策は「Trait object に関しては Associated types を Type parameters のように扱う」である。以下、[動く例](https://play.rust-lang.org/?version=stable&mode=debug&edition=2021&gist=9cac2aa5ca5740542ac13492184e5fd7)を見てみよう。




# そんな単純な話ではない

これでめでたしめでたし...。かと思えばそんなことはない。以下のような例を考えよう。

## トレイトが継承されている場合

```rs
trait Tr1 {
	type X;
}
trait Tr2: Tr1 {
    type Y;
}
```

このように継承関係にあるトレイト`Tr2`のトレイトオブジェクトを作りたいと思ったらどうすればよいだろうか?

... 答えは`dyn Tr2<X = i8, Y = u8>`である。すなわち、継承元のトレイトを含め、すべての”浮いている” Associated types を指定し尽くす必要がある。

Associated type `X` の値は単純に`dyn Tr2<X = i8, Y = u8>::X`とやってもいいし、厳密に`<dyn Tr2<X = i8, Y = u8> as Tr1>::X`とやってもいい[^3]。

[^3]: まあ単純に`i8`と書けばよいのだが

ちなみに以下の例のようにすれば`X`の指定を省略することができる。

```rs
trait Tr1 {
	type X;
}
trait Tr2: Tr1<X = i8> {
    type Y;
}

fn func(_: Box<dyn Tr2<Y = u8>>) -> <dyn Tr2<Y = u8> as Tr2>::Y { todo!() }
```

ここで`Tr<X = i8>`の部分を`Tr<X = <Self as Tr2>>::Y`のようにしたかったが無理であった。

## なぜかうまくコンパイルできない例

```rs
trait Tr1 {
	type X;
}
trait Tr2: Tr1<X = Self::Y> {
    type Y;
}

fn func(_: Box<dyn Tr2<Y = u8>>) { todo!() }
```

ここで`Tr2`は間違いなくObject safeであると思うのだが正しくコンパイルできない。これは処理系のバグではないだろうか？

## Associated types が trait のメンバの入力もしくは出力として使われる場合

```rs
trait Tr {
    type X;
    fn f(self) -> Self::X;
}

fn func(_: Box<dyn Tr<X = i8>>) -> () { todo!() }
```

実は、上のコードは全く問題なく動作する。では以下の例はどうだろうか?

```rs
trait Tr1 {
	type X;
}
trait Tr2: Tr1 {
    type Y;
    fn func1(&self) -> <Self as Tr1>::X;
}

fn func(_: Box<dyn Tr2<X = u8, Y = i8>>) { todo!() }
```

この場合も全く問題なく動作する。`func1()`の戻り値の中に`Self`が入っているため問題が起きるように見えるが、`<Self as Tr1>::X`は`Tr1`のAssociated types でありながら、実質的には単なる型パラメータとして機能している。そのため、Trait object内での`<Self as Tr1>`は最早`Self`とは関係ないのである。

## Where節の扱い

以下の例はどうだろう。

```rs
trait Tr1 {
	type X;
}
trait Tr2 {
    fn func1(&self) -> <Self as Tr1>::X where Self: Tr1;
}

fn func(_: Box<dyn Tr2>) { todo!() }
```

これはコンパイルできない。なぜなら`Self`のAssociated typesである`<Self as Tr1>::X`をメンバの出力として使用しているからである。これはObject safetyに引っかかる。では、以下のようにWhere節でAssociated types `X`を指定したらどうなるかというと、やはりこれもObject safetyに引っかかる。おそらく、トレイトオブジェクトのメソッドを呼び出す時には既に`Self`の元の型情報は存在しないため、追加の型制約を行うことはできないのだろう。

```rs
trait Tr1 {
	type X;
}
trait Tr2 {
    fn func1(&self) -> <Self as Tr1>::X where Self: Tr1<X = u8>;
}

fn func(_: Box<dyn Tr2>) { todo!() }
```



# Object safety

あるトレイトがObject safeである、とは
- Associated constantsをもたない、かつ
- Self: Sized ではない、かつ
- すべてのメンバ関数がObject safeである。

あるメンバ関数がObject safeであるとは
* Self: Sized 制約を持つ(トレイトオブジェクトでは呼べなくなる[^2])、または
* 以下の全てを満たす
** 型パラメータを持たない(トレイトオブジェクトに対するメソッドコールの呼び出し先を一意にするため?)、かつ
** `Self`にdereferenceされるようなレシーバを持つ。
** レシーバ以外で`Self`を使用しない。(ただし`Self`に関連付けられるAssociated typesを使用する場合を除く)

[^2]: `FnOnce::call_once()`の第一引数は例外？

# まとめ

- Object safetyは意外と難しい
- トレイトがObject safeであっても、メンバ関数が`self`を取る場合はその関数を呼び出せない(Self: ?Sizedなので)
- Object safeなトレイトであっても、トレイトオブジェクトを作成するためにはAssociated types を指定し尽くす必要がある。

なお、Associated typesの指定は以下の場所で行える。
- トレイトをトレイトオブジェクト型として表す部分(`dyn Trait<X = ...>`)
- トレイトが別のトレイトを継承する場合、その指定部(`trait Tr1: Tr2<X = ...> {}`)

なお、以下の場所では行えない。
- トレイトのメンバ関数のWhere節(`fn method() where Self: Tr<X = ...>`)