目的

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
fn main() {
let vecs = Vecs {
vecs: vec![vec![1, 2], vec![3, 4], vec![5, 6]],
};

for x in &vecs {
println!("{}", x);
}
}

struct Vecs<T> {
vecs: Vec<Vec<T>>
}

impl<'a, T> IntoIterator for &'a Vecs<T> {
type Item = &'a T;
type IntoIter = ???;

fn into_iter(self) -> Self::IntoIter {
???
}
}

如上面的代码所示,假设我们有一个 Vec<Vec<T>>, 我们想要将其中的每一个 Vec<T>Iterator 串起来,获得一个新的 Iterator,该如何做呢?

chain 的尝试

谈到连接多个 Iterator,最开始我们可能会想到 Iterator 中的 chain 函数。但是,将两个、三个 Iterator 串起来好写,但是将很多个 Iterator 串起来怎么办呢?

我们可能会再想到 fold 函数,写出这样的代码:

1
2
3
4
5
6
7
8
impl<'a, T> IntoIterator for &'a Vecs<T> {
type Item = &'a T;
type IntoIter = ???;

fn into_iter(self) -> Self::IntoIter {
self.vecs.fold(std::iter::empty::<&'a T>(), |iter, v| iter.chain(v))
}
}

但我们很快会意识到,std::iter::empty::<&'a T>()iter.chain(v) 的类型并不一致,虽然它们都是 Iterator,但一个是 Empty,一个是 Chain

更大的问题是,如果我们这么做,类型 IntoIter 又应该怎么写呢?

看一下 chain 函数的签名:

1
2
fn chain<U>(self, other: U) -> Chain<Self, <U as IntoIterator>::IntoIter>
where U: IntoIterator<Item = Self::Item>,

每一次 chain 函数的调用,都会将 chain 函数的参数的类型加到 Chain 的范型参数中。经过若干次调用,这个 Chain 的范型参数不仅会变得极其复杂,而且我们也根本没有办法写出来,因为我们不知道这个 chain 函数到底会调用多少次。

使用 flat_map

chain 的尝试放弃后,我们发现有一个更适合我们的函数 flat_map

flat_map 会自动将闭包参数中的 Iterator 展平,将内层的每一个 Iterator 相连。那这不正是我们的需求吗?

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
fn main() {
let vecs = vec![vec![1, 2], vec![3, 4], vec![5, 6]];

for x in vecs.iter().flat_map(|v| v.iter()) {
println!("{}", x);
}
}

// Output:
// 1
// 2
// 3
// 4
// 5
// 6

试一下,果然能顺利达成我们的效果。

那针对我们的自定义类型 Vecs<T> 又如何呢?

我们会发现,写类型 IntoIter 又是一个挣扎的过程,挣扎到最后可能会写出这样的一坨来:

1
2
3
4
5
6
7
8
impl<'a, T> IntoIterator for &'a Vecs<T> {
type Item = &'a T;
type IntoIter = std::iter::FlatMap<std::slice::Iter<'a, T>, std::slice::Iter<'a, T>, FnMut(&'a Vec<T>) -> &'a T>;

fn into_iter(self) -> Self::IntoIter {
self.vecs.iter().flat_map(|v| v.iter()))
}
}

但扔进编译器一跑,发现还是炸了:

1
2
3
4
5
6
error[E0277]: the trait bound `std::ops::FnMut(&std::vec::Vec<T>) -> &T + 'static: std::marker::Sized` is not satisfied
--> src/main.rs:15:13
|
15 | impl<'a, T> IntoIterator for &'a Vecs<T> {
| ^^^^^^^^^^^^ `std::ops::FnMut(&std::vec::Vec<T>) -> &T + 'static` does not have a constant size known at compile-time
|

就看这第一条提示我们就发现了问题,这个 FnMut 并不是 Sized,我们在编译期不知道它的大小是多少。

使用 Box 指针

面对这样的问题,我们可以想到用 Box 指针来包装这个 FnMut。因为 Box<T>Sized,所以这样就能解决非 Sized 的问题了。

但我们这时又遇到一个问题,IntoIter 必须是一个 Iterator 啊,它并不能接收一个 Box<Iterator>

解决办法就是我们自己再定义一个自己的 VecsIterator,然后去实现 Iterator

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
struct VecsIterator<'a, T> {
iter: Box<Iterator<Item = &'a T>>,
}

impl<'a, T> Iterator for VecsIterator<'a, T> {
type Item = &'a T;

fn next(&mut self) -> Option<Self::Item> {
self.iter.next()
}
}

impl<'a, T> IntoIterator for &'a Vecs<T> {
type Item = &'a T;
type IntoIter = VecsIterator<'a, T>;

fn into_iter(self) -> Self::IntoIter {
VecsIterator {
iter: Box::new(self.vecs.iter().flat_map(|v| v.iter())),
}
}
}

这段代码是编译不过的,有生命周期的问题。不过跟着编译器的提示,我们能够比较轻松地修改好程序,使之编译通过,最终解决了这个问题:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
fn main() {
let vecs = Vecs {
vecs: vec![vec![1, 2], vec![3, 4], vec![5, 6]],
};

for x in &vecs {
println!("{}", x);
}
}

struct Vecs<T> {
vecs: Vec<Vec<T>>,
}

struct VecsIterator<'a, T: 'a> {
iter: Box<Iterator<Item = &'a T> + 'a>,
}

impl<'a, T> Iterator for VecsIterator<'a, T> {
type Item = &'a T;

fn next(&mut self) -> Option<Self::Item> {
self.iter.next()
}
}

impl<'a, T> IntoIterator for &'a Vecs<T> {
type Item = &'a T;
type IntoIter = VecsIterator<'a, T>;

fn into_iter(self) -> Self::IntoIter {
VecsIterator {
iter: Box::new(self.vecs.iter().flat_map(|v| v.iter())),
}
}
}

// Output:
// 1
// 2
// 3
// 4
// 5
// 6

impl Trait

就这么一个小问题,我们因为类型的原因折腾了半天,不值啊,不值。

Rust Team 的人当然也意识到了这样的问题,于是我们就有了 RFC 1522

这个特性还是一个 unstable 的特性,只有在 nightly 版本的编译器中才能使用。

让我们试一下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#![feature(conservative_impl_trait)]

fn main() {
let vecs = Vecs {
vecs: vec![vec![1, 2], vec![3, 4], vec![5, 6]],
};

for x in vecs.iter() {
println!("{}", x);
}
}

struct Vecs<T> {
vecs: Vec<Vec<T>>,
}

impl<T> Vecs<T> {
fn iter(&self) -> impl Iterator<Item = &T> {
self.vecs.iter().flat_map(|v| v.iter())
}
}

然后编译……

1
2
3
4
5
6
7
8
9
10
error: internal compiler error: unexpected panic

note: the compiler unexpectedly panicked. this is a bug.

note: we would appreciate a bug report: https://github.com/rust-lang/rust/blob/master/CONTRIBUTING.md#bug-reports

note: rustc 1.22.0-nightly (a47c9f870 2017-10-11) running on x86_64-unknown-linux-gnu

thread 'rustc' panicked at 'assertion failed: match *region { ty::ReLateBound(..) => false, _ => true, }', /checkout/src/librustc/infer/higher_ranked/mod.rs:466:8
note: Run with `RUST_BACKTRACE=1` for a backtrace.

emmmmmmmmmmmmmmmmm……

结局竟然是编译器炸了……

2017 年 12 月 20 日更新:

现在上面的程序已经可以在最新的 nightly 编译器上通过了。

然后我们根据这个提示可以搜到 Issue #39553。加上生命周期就好了:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
#![feature(conservative_impl_trait)]

fn main() {
let vecs = Vecs {
vecs: vec![vec![1, 2], vec![3, 4], vec![5, 6]],
};

for x in vecs.iter() {
println!("{}", x);
}
}

struct Vecs<T> {
vecs: Vec<Vec<T>>,
}

impl<T> Vecs<T> {
fn iter<'a>(&'a self) -> impl Iterator<Item = &T> {
self.vecs.iter().flat_map(|v| v.iter())
}
}

// Output:
// 1
// 2
// 3
// 4
// 5
// 6