25.4 生成器的原理

25.4.1 生成器原理简介

再回过头来看一下生成器。它实际上是迭代器和立即求值的“杂交”。一方面，它写起来更接近人的思维模型，代码流程清晰，逻辑上更符合直觉；另一方面，它在执行的时候又具备惰性求值的性能优势。那么编译器是如何实现生成器的呢？yield 关键字在背后究竟做了什么？

一句话总结，就是编译器把生成器自动转换成了一个匿名类型，然后对这个类型实现了 Generator 这个 trait。这种处理手法和闭包非常相似。和闭包一样，生成器也可以捕获当前环境中的局部变量，并且可以用 move 做修饰，捕获的环境变量都是当前生成器的成员，捕获规则也与闭包一样。Generator trait 是这么定义的：

rust

trait Generator {
    type Yield;
    type Return;
// 至少到目前为止，resume 方法还不能接受额外参数，这个限制条件以后可能会放宽
// 目前的 resume 方法还是不稳定版本，以后应该会去掉 unsafe,self 的类型也会有所变化，
// 具体参见下一节的自引用类型
    unsafe fn resume(&mut self) -> GeneratorState<Self::Yield, Self::Return>;
}

但是，生成器内部还有额外的成员，那就是跨 yield 语句存在的局部变量，也都会当成成员变量。这是因为，生成器内部的语句会成为成员函数 resume()的方法体，源代码中的 yield 语句都被替换成了普通的 return 语句，且返回的是 Generator-State::Yielded（_）。源代码中的 return 语句依然是 return 语句，但返回的是 GeneratorState::Complete（_）。注意生成器有一个特点，就是每次 yield 退出之后，当前的局部变量会保持当前的值不变，下一次被调用 resume 再进来执行的时候，会继续从上次 yield 的那个地方继续执行，局部变量是无须再次初始化的。这就意味着，对于在 yield 前和 yield 后都出现过的局部变量，务必要保存它的状态，它的值要存到匿名类型的成员中。

我们再看看最开始那段示例：

rust

let mut g = || {
    let mut curr : u64 = 1;
    let mut next : u64 = 1;
    loop {
        let new_next = curr.checked_add(next); // 下轮循环的时候要继续使用 curr next 的值

        if let Some(new_next) = new_next {
            curr = next;
            next = new_next;
            yield curr; // <-- 此处退出
        } else {
            return;
        }
    }
};

可以看到，再进入生成器的时候，局部变量 curr next 的值是马上就需要使用的，因此变量 g 里面无论如何都要给这两个变量留下位置，保存它们的值。否则，下次再调用 resume 方法的时候，它们就无法恢复到上次退出时的状态了。而另外一个局部变量 new_next 则无须保存，因为它没有跨 yield 存在，所以这个局部变量可以作为成员方法 resume 内部的局部变量，无须提升为 g 的局部变量。

编译器把这个生成器处理之后，逻辑如下：

rust

// 编译器实际上不是在源码级别做的转换，而是在 MIR 做的转换，以下代码只是为了说明原理，
// 与真实的编译器转换后的代码并不一致
// 编译器是如何做这个转换的，请参考源码 librustc_mir/transform/generator.rs
// 目前编译器实际上是转换为 struct，此处使用 enum 是为了更方便地演示大概的逻辑
#![feature(generators, generator_trait)]

use std::ops::{Generator, GeneratorState};

fn main() {
    let mut g = {
        enum __AnonymousGenerator {
            Start{curr : u64, next : u64},
            Yield1{curr : u64, next : u64},
            Done,
        }

        impl Generator for __AnonymousGenerator {
            type Yield = u64;
            type Return = ();

            unsafe fn resume(&mut self) -> GeneratorState<Self::Yield, Self::Return>
            {
                use std::mem;
                match mem::replace(self, __AnonymousGenerator::Done) {
                    __AnonymousGenerator::Start{curr, next}
                    | __AnonymousGenerator::Yield1{curr, next} => {
                        let new_next = curr.checked_add(next);

                        if let Some(new_next) = new_next {
                            *self = __AnonymousGenerator::Yield1{curr: next, next: new_next};
                            return GeneratorState::Yielded(curr);
                        } else {
                            *self = __AnonymousGenerator::Done;
                            return GeneratorState::Complete(());
                        }
                    }

                    __AnonymousGenerator::Done => {
                        panic!("generator resumed after completion")
                    }
                }
            }
        }

        __AnonymousGenerator::Start{ curr: 1, next: 1}
    };

    loop {
        unsafe {
            match g.resume() {
                GeneratorState::Yielded(v) => println!("{}", v),
                GeneratorState::Complete(_) => return,
            }
        }
    }
}

可以看到，转换后的代码实际上和迭代器非常相似。所以，生成器实际上是让编译器帮我们自动管理状态：哪些状态应该放到成员变量里面，哪些不需要；退出前如何保存状态，重新进入的时候如何读取上次的状态等，都是编译器帮我们自动做好了的。

如果生成器内部存在多个 yield 语句呢？比如下面这样：

rust

let mut g = || {
    yield 1_i32;
    yield 2_i32;
    yield 3_i32;
    return 4_i32;
};

那我们就再引入一个状态，来表达上次已经执行到哪条语句了，下次调用应该从哪条语句开始执行。在进入 resume 方法的时候，先判断这个状态，然后再跳转即可。

rust

let mut g = {
        struct __AnonymousGenerator {
            state: u32
        }

    impl Generator for __AnonymousGenerator {
        type Yield = i32;
        type Return = i32;

        unsafe fn resume(&mut self) -> GeneratorState<Self::Yield, Self::Return> {
            match self.state {
                0 => { // 从初始状态开始执行
                    self.state = 1;
                    return GeneratorState::Yielded(1);
                }

                1 => { // 上一次返回的是 yield 1
                    self.state = 2;
                    return GeneratorState::Yielded(2);
                }

                2 => { // 上一次返回的是 yield 2
                    self.state = 3;
                    return GeneratorState::Yielded(3);
                }

                3 => { // 上一次返回的是 yield 3
                    self.state = 4;
                    return GeneratorState::Complete(4);
                }

                _ => { // 上一次返回的是 return 4
                    panic!("generator resumed after completion")
                }
            }
        }
    }

    __AnonymousGenerator{ state: 0}
};

总之，任何一个生成器，总能找到办法将它自动转换为类似迭代器的样子。之所以说是类似，是因为生成器的功能更强大，它的 resume()方法实际上可以设计为携带更多的参数，只是目前的 Rust 还没有实现，这个需求并不是很紧急而已。

25.4.2 自引用类型

目前的生成器只是一个在 nightly 版本中存在的、实验性质的功能，它还有一些问题没有解决。最主要的一个问题是如何使得借用跨 yield 存在。示例如下：

rust

#![feature(generators, generator_trait)]

fn main() {
    let _g = || {
        let local = 1;
        let ptr = &local;
        yield local;
        yield *ptr;
    };
}

编译，出现编译错误：

rust

error[E0626]: borrow may still be in use when generator yields

这个错误究竟是什么意思呢？我们可以通过分析生成器的原理来理解这个错误的含义。可以尝试看看这个生成器剥掉语法糖之后的样子。注意到，第一个 yield 之后变量ptr依然被使用，且 local 这个变量也还存在，那么意味着我们要在生成的匿名类型的成员中，保存 ptr 和 local 这两个变量。再加上一个成员变量记录 yield 的位置信息，我们可以设计下面这样的匿名结构体：

rust

struct __Generator__ {
    local: i32,
    ptr: &i32,
    state: u32,
}

针对这个类型实现 Generator 这个 trait，基本上就等同于上面那段程序剥掉语法糖之后的效果。

现在就可以更清楚地看到具体问题在哪里了。这里的关键点是：一个结构体类型内部出现了一个成员引用另外一个成员的现象。这种类型被称为“自引用类型”（Self-Referential Type）。目前的 Rust，对自引用类型有很多限制。因为这个类型会破坏 Rust 的一个基本假设：任何类型都是可移动的。这个假设让 Rust 的移动语义变得非常清晰简单（主要跟 C++对比）。但是自引用类型在移动的时候会出问题。原本成员 ptr 是指向成员变量 local 的，如果这个结构体整体发生了移动，ptr 指针的值保持不变，local 的位置却发生了变化，那么就会制造出悬空指针。所以，目前的 Rust 是不允许这种情况出现的，这种代码会被生命周期检查禁止掉。这就是上面那段示例代码无法编译通过的深层原因。

但是自引用现象未必就一定不安全。假如构成自引用之后这个对象就永远不再移动，那么它其实是没问题的，也不会有悬空指针之类的情况出现。在写生成器的时候会很容易出现自引用对象，如果完全禁止这种行为，会非常影响用户体验。如何让用户有权创建自引用的生成器，同时又能避免安全性问题呢？Rust 设计组通过巧妙的设计做到了这一点。主要想法是：

应该允许用户创建自引用生成器，因为在调用 resume 方法之前的移动都是没问题的，毕竟这个时候它内部的许多成员都是未初始化状态；
一旦 resume 被调用过了，以后就不能再移动这个对象了，因为这时候指针和被指向的对象很可能已经初始化好了，再发生移动就会造成内存不安全。

具体来说，设计组会做以下改变。

标准库引入一个新的智能指针类型Pin<P>，它可以指向一个 T 类型的对象。它的作用是，当这个指针存在的时候，它所指向的对象是不可移动的。
允许更多的智能指针类型作为 self 变量的类型，这样我们可以指定 resume 方法的第一个参数是self: Pin<&mut Self>类型，而不是&mut self了。

这样，就可以从逻辑上保证用户调用 resume 方法之前，一定先构造出一个Pin<&mut XXGenerator>的指针变量。这样，在这个变量存在的期间，生成器就无法移动，调用 resume 必须通过这个指针来完成。有了这个保证，resume 方法前面的 unsafe 修饰也就可以去掉了。预计这个设计到 2018 年下半年就可以稳定下来。

另外，生成器本身并不是直接面向广大用户的接口。用户真正需要的是完成异步任务。实际上，“协程”才是最终用户用得最多的东西。生成器只是实现协程的一个底层工具。最终，协程库会把所有这些 Pin 指针之类的事情封装管理起来。

25.4 生成器的原理 ​

25.4.1 生成器原理简介 ​

25.4.2 自引用类型 ​

25.4 生成器的原理

25.4.1 生成器原理简介

25.4.2 自引用类型