我正在玩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);
}
}
然而，要使用continuation来完成这项工作，我需要定义闭包来管理遍历的其余部分，并通过尾部递归来传递这些闭包，我的即时解决方案看起来与我当前的解决方案没有太大区别：
// 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
}
游乐场
问题出现在递归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));
}
}
}
游乐场
所以我不知道问题出在哪里，也不知道如何告诉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));
}
}
}
游乐场
但当类型检查器必须对类型推理进行递归时，这会中断编译。也许并不奇怪，因为闭包的类型可能取决于推断的递归类型。
我能做些什么来解决这个问题吗？或者这个想法一到就死了，如果我想按照这些思路做一些事情，我必须尝试一种完全不同的方法？
生存期问题是因为在明确指定了生存期的情况下，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>) + '_>(操场)。就是这样。'_是显式消隐的生存期：它告诉编译器"；自己想一个合适的人生"；。通常编译器会自动执行，但对于dyn Trait，他有时会放弃，只使用'static。根据寿命省略规则来推断寿命；在这种情况下，它引入了一个新的生命周期，就像我们写的那样：
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(操场)：放进去，会更清楚
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，或者对于right为&'static Option<Box<T>>)。但要使&'static T有效，T: 'static必须保持(想象一下像&'long &'short i32这样的引用：您可以为'long访问它，但只要'short结束，它就无效，您将使用悬挂引用！)。我能证明T: 'static总是成立吗？不！嗯，应该会发出一个错误"(您可以在上填写错误报告https://github.com/rust-lang/rust/issues，Rust开发人员会很感激的，尽管我不确定他们能做多少来改善这种情况)。
为什么复制它们没有帮助？首先，编译器对它的思考方式没有改变，因此仍然会发出相同的错误。其次，即使我们可以解决它(例如通过指定T: 'static)，也存在另一个错误(操场)：
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;
| ~~~~~~~
希望这个是不言自明的。
关于通用版本，你的假设确实是正确的：没有一种语言可以用单形式化做递归CPS，它们都使用动态调度(相当于Box<dyn FnOnce()>(或一些GCed版本)，或&mut dyn FnMut()或类似的东西)。我们将不得不无限期地实例化它。