生命周期和闭包以及持续传递风格

Question

我正在玩 Rust 闭包，试图对它们有一种感觉，我为自己设定的一项任务是使用连续传递样式实现有序遍历。通常我可以用其他语言在大约一个小时内完成，但在这里我设法解决了如何管理我在回调中使用的闭包的生命周期。

我定义了这样一个二叉树，非常简单：

// A node is a tuple of (left, value, right)
struct Node<T>(pub Tree<T>, pub T, pub Tree<T>);
// A tree is an optional pointer to a node
type Tree<T> = Option<Box<Node<T>>>;

而且我可以按照我期望的方式进行直接递归遍历：

// Direct recursion.
// The <T: Copy> is needed because we copy values into
// the result vector. For other usages we might not need it
fn inorder<T: Copy>(t: &Tree<T>, res: &mut Vec<T>) {
    // If t is not empty it is Some(node)
    if let Some(node) = t {
        // Pull out the values of the node.
        // In the development branch of Rust there is
        // a nicer syntax, but this is how it is now
        let Node(left, val, right) = node.as_ref();

        inorder(left, res);
        res.push(*val);
        inorder(right, res);
    }
}

然而，为了用延续来做到这一点，我需要定义闭包来管理其余的遍历并将它们与尾递归一起传递，我的直接解决方案看起来与我当前的解决方案没有太大不同：

// Ideally, we wouldn't need to pass the vector along with the closures
// but Rust won't let us hold on to a mutable reference in a closure if
// another closure also has a mutable reference, so we pass the vector
// from continuation to continuation instead.
fn cps_rec<T: Copy>(t: &Tree<T>, res: &mut Vec<T>, 
                    k: Box<dyn FnOnce(&mut Vec<T>)>)
{
    match t {
        None => { k(res) },
        Some(node) => {
            let Node(left, val, right) = node.as_ref();
            let after_left = |v: &mut Vec<T>| { 
                // After we have gone left, add v and go right, 
                // calling k when we are done
                v.push(*val);
                cps_rec(right, v, k);
            };
            cps_rec(left, res, Box::new(after_left));
        }
    }
}

fn cps<T: Copy>(t: &Tree<T>) -> Vec<T> {
    let mut res = vec![];
    cps_rec(t, &mut res, Box::new(|_| ()));
    res
}

Playground

问题出在递归 cps_rec(left, res, after_left) 中，其中闭包的生命周期与约束不匹配。（我想，我不能说我完全理解 Rust 到底在抱怨什么，但是一旦我将闭包的主体设为空，问题就消失了，所以这是推断的生命周期中的某些东西把事情搞砸了）。我首先怀疑是 val 或 right 的生命周期在打我，但在取消引用它们后将 move 放在闭包前面无济于事

fn cps_rec<T: Copy>(t: &Tree<T>, res: &mut Vec<T>, 
                    k: Box<dyn FnOnce(&mut Vec<T>)>)
{
    match t {
        None => { k(res) },
        Some(node) => {
            let Node(left, val, right) = node.as_ref();
            let val = *val;
            let right = *right;
            let after_left = move |v: &mut Vec<T>| { 
                // After we have gone left, add v and go right, 
                // calling k when we are done
                v.push(val);
                cps_rec(&right, v, k);
            };
            cps_rec(left, res, Box::new(after_left));
        }
    }
}

Playground

所以我无法弄清楚问题是什么，或者如何告诉 Rust 这个闭包将存活足够长的时间来完成递归...

然后我尝试使用泛型类型来继续，看看这是否会让 Rust 为我解决问题：

fn cps_rec<'a, T: Copy, Cont>(t: &'a Tree<T>, res: &'a mut Vec<T>, k: Cont)
    where Cont: FnOnce(&'a mut Vec<T>)
{
    match t {
        None => { k(res) },
        Some(node) => {
            let Node(left, val, right) = node.as_ref();
            let after_left = |v: &'a mut Vec<T>| { 
                // After we have gone left, add v and go right, 
                // calling k when we are done
                v.push(*val);
                cps_rec(right, v, k);
            };
            cps_rec(left, res, Box::new(after_left));
        }
    }
}

Playground

但是当类型检查器必须对类型推断进行递归时，这会破坏编译。也许并不奇怪，因为闭包的类型可能取决于递归的推断类型。

我能做些什么来解决这个问题，还是这个想法一到就死了，如果我想按照这些思路做点什么，我必须尝试一种完全不同的方法？

Answer 1

生命周期问题是因为 Box<dyn FnOnce(&mut Vec<T>)> 实际上是 Box<dyn FnOnce(&mut Vec<T>) + 'static>，明确指定了生命周期。也就是说，它要求闭包是 'static。如果它捕获的所有内容都是 'static，则闭包是静态的。当然，一个空的闭包满足这个条件——它什么都不捕获，所以如果你清空它的主体它就可以工作。

但是，您的闭包捕获了非 'static 引用 - val 和 right。我很快就会解释为什么复制它们不起作用。

解决方案很简单：我们真的不需要闭包 'static；我们可以很好，即使它不会 - 我们不存储它或其他东西。为了向编译器表达这一点，我们需要将 Box<dyn FnOnce(&mut Vec<T>)> 更改为 Box<dyn FnOnce(&mut Vec<T>) + '_>（playground). That's it. '_ is the explicitly elided lifetime: it tells the compiler "figure the right lifetime out yourself". Usually the compiler does that automatically, but with dyn Trait he sometimes gives up and just uses 'static. The lifetime is inferred according to the lifetime elision rules；在这种情况下，它引入了一个新的生命周期，就像我们这样写：

fn cps_rec<'elided_lifetime, T: Copy>(
    t: &Tree<T>,
    res: &mut Vec<T>,
    k: Box<dyn FnOnce(&mut Vec<T>) + 'elided_lifetime>,
) { ... }

这里混淆的是编译器的错误信息。如果您遵循编译器的建议并输入 T: 'static (playground):

会更清楚

error: lifetime may not live long enough
  --> src/lib.rs:17:32
   |
6  | fn cps_rec<T: Copy + 'static>(t: &Tree<T>, res: &mut Vec<T>, k: Box<dyn FnOnce(&mut Vec<T>)>) {
   |                                  - let's call the lifetime of this reference `'1`
...
17 |             cps_rec(left, res, Box::new(after_left));
   |                                ^^^^^^^^^^^^^^^^^^^^ cast requires that `'1` must outlive `'static`

这就是我说的。 'static 是必需的，因为闭包的隐含 'static 界限。

但是编译器有更重要的事情要告诉你（或者更确切地说，对你大喊大叫）。它认为：“鉴于闭包需要 'static，那些引用显然是 'static。这个用户没有骗我，他是个好公民！”只有稍后它才会意识到它是错误的，但它永远不会到达这个“稍后”，因为它会由于较早的错误而停止编译。但截至目前，它认为，“鉴于这些引用显然是 'static，它们是 &'static T（对于 val，或 &'static Option<Box<T>> for right)。但要使 &'static T 有效，T: 'static 必须成立（想象一个像 &'long &'short i32 这样的引用：您将能够访问它 'long，但只要 'short 结束，它就是无效的，你将使用悬空引用！）。我能证明 T: 'static 总是成立吗？不！嗯，应该发出错误。” （您可以在 https://github.com/rust-lang/rust/issues 填写错误报告，Rust 开发人员会很感激，尽管我不确定他们可以做多少来改善这种情况）。

为什么复制它们没有帮助？首先，编译器考虑它的方式没有改变，所以仍然会发出同样的错误。其次，即使我们可以解决它（例如通过指定 T: 'static），还有另一个错误（playground）：

error[E0507]: cannot move out of `*right` which is behind a shared reference
  --> src/lib.rs:12:34
   |
12 |             let right: Tree<T> = *right;
   |                                  ^^^^^^ move occurs because `*right` has type `Option<Box<Node<T>>>`, which does not implement the `Copy` trait
   |
help: consider borrowing the `Option`'s content
   |
12 |             let right: Tree<T> = *right.as_ref();
   |                                        +++++++++
help: consider borrowing here
   |
12 |             let right: Tree<T> = &*right;
   |                                  ~~~~~~~

希望这个是self-explanatory。

关于通用版本，你的假设确实是正确的：没有语言可以用单态化做递归CPS，它们都使用动态调度（相当于Box<dyn FnOnce()>（或某些GCed版本），或&mut dyn FnMut() 或类似的东西）。我们将不得不无限期地实例化它。

生命周期和闭包以及持续传递风格

Lifetime and closures and continuation passing style

rust