traitからイテレータを返したくなったときに読む記事

こんにちは。 Rust、日進月歩ですね。
ちょっと前[^1]に、私はこんな記事を書きました：

https://qiita.com/wada314/items/201ab5d66ac7daeb9c3d

[^1]: ２，３年前ですかね……えっ６年前！？　うせやろ！？？

ざっと上記の記事の内容をまとめると、関数の定義時には戻り値の型を明示してやる必要があるので、型がめちゃくちゃ長く複雑になりがちなイテレータを返す関数を書くのは辛いよ、という内容でした。

しかしもう上記の記事の内容は古くなっていて、今ではいわゆる`impl Trait`機能によって、イテレータを返す関数を書くときに、長ったらしいイテレータの型をわざわざ記述する必要はなくなっています。

しかし、しかしです。 現在(2021年4月、Rust ver.1.51) `impl Trait` 機能は`trait`中では使えません。 つまり、イテレータを`trait`から返すこんなコードを書こうとしても：

```Rust:コンパイルが通らない例
trait ListOfInt32 {
    fn int32_iter(self) -> impl Iterator<Item=i32>;
}
```

コンパイラに怒られます。

```
error[E0562]: `impl Trait` not allowed outside of function and inherent method return types
```

本稿では、イテレータを`trait`から返す際に遭遇するであろう問題２つと、それらに対するいくつかの解決策を記述します。

#問題0: `trait`内では`impl Trait`記法が使えない#

さて、上記のエラー自体は簡単な回避方法があります。 イテレータの型を、`trait`の関連型(Associated type)に設定してやるのです：

```Rust
trait ListOfInt32 {
    type Int32Iterator: Iterator<Item = i32>;
    fn int32_iter(self) -> Self::Int32Iterator;
}
```

これでコンパイルが通ります。　しかし、この`trait`を実装するときには……：

```Rust
impl ListOfInt32 for Vec<i32> {
    type Int32Iterator = /* ここにイテレータの型を書く */;
    fn int32_iter(self) -> Self::Int32Iterator {
        /* ... */
    }
}
```

はい、イテレータの型を書かなければならない問題が再燃します。

# 問題1: イテレータの型を書かされる #

## 解決策z: 気合でイテレータの型を手動で書く ##
これはイヤですね。

## 解決策a: イテレータを`Box`で包む ##

これは常道の手段で、`Box<dyn Iterator<Item=i32>>`を返すようにすればイテレータの型を書かなくて済みます。　もちろん`Box`を使っているのでヒープメモリのアロケーションも発生しますし、イテレータの静的ディスパッチも捨て去ることになります。
このデメリットが許容できるならこれでもいいのですが、実は他にも手段があります。

## 解決策b: nightlyのunstable機能を使う ##

割り切ってunstableの機能を使えるなら、`type_alias_impl_trait`のfeatureを使うことにより、上記のイテレータの型部分にも`impl Trait`を書くことが可能になります。
(2021/08/02追記: feature名が`min_type_alias_impl_trait`から上記の名前に変更になっています)

```Rust:nightlyでのみ利用可能
#![feature(type_alias_impl_trait)]

// 前とおなじ
trait ListOfInt32 {
    type Int32Iterator: Iterator<Item=i32>;
    fn int32_iter(self) -> Self::Int32Iterator;
}

impl ListOfInt32 for Vec<i32> {
    type Int32Iterator = impl Iterator<Item=i32>; // <-- ここに使える！！
    fn int32_iter(self) -> Self::Int32Iterator {
        <Self as IntoIterator>::into_iter(self)
    }
}

```

これが使えるならこれが一番いいです。 nightlyでしか使えない以外、特に大きなデメリットも私は見つけていませんし、なんか実装がバグってるみたいなことも聞いていません。
結構前（2019年）にほぼ実装は完了しているみたいなのに、なんでstableに降りてこないんでしょうね？（←issueをロクに読んでない）

https://github.com/rust-lang/rust/issues/63063


## 解決策c: イテレータのラッパ型を実装する ##

いくつかの条件が噛み合えば、イテレータのラッパ型を新しく実装すると記述が楽になる場合があります。 たとえば、上述の`trait ListOfInt32`を`Vec<String>`に`impl`するために、`String`を`int32`に変換するイテレータを噛ます例を考えましょう：

```Rust
impl ListOfInt32 for Vec<String> {
    type Int32Iterator = StringToInt32Iterator; // <-- かんたん！
    fn int32_iter(self) -> Self::Int32Iterator {
        StringToInt32Iterator {
            iter: self.into_iter(),
        }
    }
}

// Vec<String>のイテレータを受け取って、i32に変換するイテレータ
struct StringToInt32Iterator {
    iter: <Vec<String> as IntoIterator>::IntoIter, // <-- ギリ書けるレベル
}
impl Iterator for StringToInt32Iterator {
    type Item = i32;
    fn next(&mut self) -> Option<Self::Item> {
        use std::str::FromStr;
        self.iter.next().map(|s| i32::from_str(&s).unwrap())
    }
}
```

この例は値の変換途中に`Option::map()`が挟まっている例です。　これをイテレータで書く場合、`Iterator::map()`内で`Option::map()`を呼び出すことになりますが、もし`Iterator::map()`に（関数ポインタではなく）クロージャを渡すと、なんとイテレータの型が**記述不能**になるので、そうなると上記の力技の解決策zは利用不能です。

一見この解決策は万能に見えますが、適用できないケースも多いです。
必要な条件がいくつかあります：

#### 条件i: ラップ元のイテレータ型が記述可能であること ####

上記のコードで言う、この部分です：

```Rust
struct StringToInt32Iterator {
    iter: <Vec<String> as IntoIterator>::IntoIter, // <-- ギリ書けるレベル
}
```

この種銭となる`iter`の型がそもそもクソ長だったり、記述不能だったりするケースというのがよくあります。 今回はたまたま`IntoIterator`の`trait`で定義されたイテレータの型を使い回せたのでOKでしたが、そういうのがない場合というのもあり得ます。

#### 条件ii: ラッパがイテレータに施す変更が、それほど複雑でないこと ####

これは別に記述が不可能になってしまう問題ではないのですが、ラッパの内容の複雑さ次第では`next()`メソッドの実装がかなり複雑になり得ます。　今回のようにただ型をマップするだけならともかく、ラップ元のイテレータとの`next()`の呼び出しタイミングがズレる系の、たとえば`Iterator::flatten()`相当のことを実現しようとすると、結構な実装量になってしまいがちですし、バグも混入してしまうかもしれません。
この解決策を採るということは、ラッパ内では`Iterator`で定義された各種の便利メソッドを全て捨て去るということです。　処理内容によってはそれなりの覚悟で書く必要があるでしょう。

## 解決策d: イテレータを返すのではなく、渡す ##

そもそもなんでイテレータの型を記述する必要があるかというと、イテレータを返しているからです。　返すのではなく渡すように元の`trait`を変更すれば、イテレータの型を一切書かないで済みます：

```Rust
trait Int32IteratorHandler {
    type ReturnType;
    // イテレータの具体的な型を書かなくてよい！
    fn handle<I: Iterator<Item = i32>>(self, iter: I) -> Self::ReturnType;
}
// イテレータを返すかわりに、渡すように変更
trait ListOfInt32 {
    fn handle_int32_iter<H: Int32IteratorHandler>(self, handler: H) -> H::ReturnType;
}

impl ListOfInt32 for Vec<String> {
    fn handle_int32_iter<H: Int32IteratorHandler>(self, handler: H) -> H::ReturnType {
        use std::str::FromStr;
        // .map()も使い放題！
        handler.handle(self.into_iter().map(|s| i32::from_str(&s).unwrap()))
    }
}

// いちいちHandlerの型を定義するのは面倒なので、
// FromIteratorにblanket implementationを用意しておくと便利
impl<T: std::iter::FromIterator<i32>> Int32IteratorHandler for T {
    type ReturnType = Self;
    fn handle<I: Iterator<Item = i32>>(self, iter: I) -> Self::ReturnType {
        iter.collect::<Self>()
    }
}

// もしくはイテレータの値を受け取るクロージャにblanket implementationを用意しておくと便利
// ただしこの書き方だと、上記のblanket implementationと同時には定義できない
//impl<F: FnMut(i32)> Int32IteratorHandler for F {
//    type ReturnType = ();
//    fn handle<I: Iterator<Item = i32>>(mut self, iter: I) -> Self::ReturnType {
//        for v in iter {
//            self(v);
//        }
//    }
//}
```

この例では、先程の例と同じように`Vec<String>`に対して`ListOfInt32`を定義していますが、先程の例と違い`Iterator`の便利メソッドも普通に使えていますし、イテレータの型を一切手動で記述していません。
利用するたびにいちいち`Handler`型を書かなければならないようにも見えますが、適切にblanket implementationを用意してやることにより、多くのユースケースでは`Handler`型を自分で書かなくてもよくなります。　用途によって`FromIterator`か`FnMut`のクロージャのどちらか、または両方にblanket implementationを用意してあげればいいでしょう[^2]。

[^2]: コメントにも書いてあるように、この書き方だとこれらのblanket implementationは衝突の可能性があるとコンパイラに怒られるので同時に存在させることができません。　それぞれを適当な単要素structで囲ってやることにより解消できます。

この方法もけっこう有用なのですが、最大のデメリットは「イテレータを返す関数の形に(ノーコストでは)書き換えられない」ことでしょう。　例えば`for`ループ構文で回す対象として直接使うことができなくなりますし、イテレータをいったん変数に格納しておいて後で使いたい場合にも困ってしまいます。
また、`handle()`が本当に呼び出されるかどうかは`trait`の実装に依存します。　実装者が信頼できない場合、`handle()`が呼び出されたかどうかのチェックを入れる必要があるかもしれません。

# 問題2: イテレータにlifetime引数を渡せない #

ここまでの例では、イテレータは`i32`型を値渡しで返すイテレータ（`Iterator<Item=i32>`）でした。　一般に、コンテナの要素を値渡しで返すイテレータというのは：

1. コンテナ型の所有権を奪ってイテレータを返す関数（例：[`fn into_iter(self)`](https://doc.rust-lang.org/std/iter/trait.IntoIterator.html#tymethod.into_iter)、`&self`ではなく`self`である点に注目）
1. `Copy`や`Clone`が軽い要素型を対象にした便利実装（例：[`std::str::Chars`](https://doc.rust-lang.org/std/str/struct.Chars.html)とか）

のどちらかで、普通のイテレータはコンテナの要素を参照渡しで返します。

ということで、先の`ListOfInt32`を参照渡しのイテレータを返すように書き換えてみましょう：

```Rust
trait ListOfInt32 {
    //  ここのlifetimeをどうする？？ ↓
    type Iterator: Iterator<Item = &i32>;
    fn iter(&self) -> Self::Iterator;
}
```

しかし、ここに参照を置く場合、lifetimeを明示的に指定してやる必要があります。
この場合ですと、この参照はコンテナの要素への参照なので、コンテナのlifetime（`&self`のlifetime）と同じlifetimeに設定してやればよさそうですね。
その気持ちを素直にコードにすると、こうなります：

```Rust
trait ListOfInt32 {
    type Iter<'a>: Iterator<Item = &'a i32>;
    fn iter<'a>(&'a self) -> Self::Iter<'a>;
    // ちなみに、lifetime elisionによりこう書いても同じ
    //fn iter(&self) -> Self::Iter<'_>;
}
```

そしてこの記事で取り上げるくらいですから当然、これはコンパイルが通りません。

```
error[E0658]: generic associated types are unstable
 --> src/lib.rs:2:5
  |
2 |     type Iter<'a>: Iterator<Item = &'a i32>;
  |     ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
  |
  = note: see issue #44265 <https://github.com/rust-lang/rust/issues/44265> for more information
  = help: add `#![feature(generic_associated_types)]` to the crate attributes to enable
```

現在のRustでは、関連型(Associated type)にジェネリック引数を設定してやることができないのです。　そのため、コンテナの(普通の)`iter()`メソッドは、`trait`に落とし込むことができません。　よくよく考えてみると、標準ライブラリでも、`Vec`や`LinkedList`などのコンテナ「型」はあっても、それらコンテナ型をまとめた`trait`ってあんまりないですよね。一番近いのは`trait IntoIterator`ですが、この`trait`が提供するイテレータは、先述のようにコンテナの所有権を奪う`fn into_iter(self)`から返ってくるので参照を使っておらず、見事にこの地雷を避けているのです。


## 解決策a: Box&lt;dyn Iterator&gt;を返す ##

パフォーマンスを多少犠牲にして簡単にコードを書くいつもの方法です。

```Rust
trait ListOfInt33 {
    fn iter2(&self) -> Box<dyn Iterator<Item = &i32> + '_>;
    // Lifetime elisionを展開するとこんな感じ
    //fn iter2<'a>(&'a self) -> Box<dyn Iterator<Item = &'a i32> + 'a>;
}
```

この問題に関しては、正直他の解決策が微妙なのでこれは十分考慮に値すると思います。

## 解決策b: nightlyのunstable機能を使う ##

エラーメッセージにも書いてあるように、`#![feature(generic_associated_types)]`を書くと(nightlyビルドで)コンパイルが通るようになります。　ただし注意点として、上で利用した`min_type_alias_impl_trait`と比べて、`generic_associated_types`は実装がより不完全である"incomplete features"に分類されているという点です。 コンパイル時には常にwarningを言われ続けますし、コンパイラがクラッシュするケースもまだ確認されています。　この記事で取り上げるくらいの典型的な使用例ならまず大丈夫でしょうが、ちょっと凝ったことをしようとすると危ないという認識でいましょう。

このfeatureについてはこちらのissueを参照してください。　最新のまとめコメントへのリンクを貼っておきます：

https://github.com/rust-lang/rust/issues/44265#issuecomment-775423925

(↑ちょっとQiitaさ～んリンクタイトルの絵文字バグってんよ～)

## 解決策c: trait自体にlifetime引数を設定する ##

関連型でlifetime `'a`を導入できないなら、`trait`の定義のときに導入しちゃえばいいじゃない[^3]、ということで、このような書き方ができます：

[^3]: lifetime引数をとる`struct`や`trait`は（例：`struct Container<'a>`）、「この`Container`型は内部に`'a`のlifetimeの参照を持っているから、この型は`'a`より早く死ぬ型だよ」という表明になります。

```Rust
trait ListOfInt32<'a> {
    type Iter: Iterator<Item = &'a i32>;
    fn iter(&'a self) -> Self::Iter;
}
```

`Vec<i32>`への`impl`も、なんとなくで書けます：

```Rust
impl<'a> ListOfInt32<'a> for Vec<i32> {
    type Iter = std::slice::Iter<'a, i32>; // <-- Vec::iter()の戻り値型をコピペ
    fn iter(&'a self) -> Self::Iter {
        self.iter()
    }
}
```

よさそうですね。　個人的にどうも直感的に怪しい気がしたので、なんとか頑張ってうまいことコンパイルエラーになる悪いケースを作ろうとしてみましたが、意外と作れませんでした。　うまいことエラーが出るケースを作れた方は教えてください。

この手法の最大の問題は、要らんところ（`impl<'a>`）にlifetime引数を導入してしまったがために、この`trait`を利用する場所全て、そしてその場所を利用する場所全て、……というように際限ない範囲に、ロクに使いもしない`<'a>`の記述を追加しなければならなくなる点です。
たとえば、適当に`struct Hoge`で囲んでやるだけでこの有様です：

```Rust
struct Hoge<'a, T: ListOfInt32<'a>> {
    list: T,
    _phantom: std::marker::PhantomData<&'a T>,
}
```

要りもしないlifetime `'a`を導入させられ、さらにコンパイラには`'a`を使っていないぞと怒られるので、`PhantomData`まで導入させられてしまっています。　これは結構面倒くさいですし、影響範囲が場合によっては甚大になります。

# まとめ #

次の２つのどちらも許容できないのなら、イテレータを返す`trait`は2021年4月現在書かないほうがいいです：
1. nightlyのunstable featuresを利用する
1. `Box<dyn Iterator>`を返す
これらを満たさずに書く方法は、上で挙げた通りないでもないのですが、どれも小さくないデメリットが存在します。