请考虑下面这个简单的链表实现:
enum Cons<T> {
Empty,
Cons(T, Box<Cons<T>>),
}
fn main() {
let mut list = Cons::Empty;
for i in 1..1_000_000 {
list = Cons::Cons(i, Box::new(list));
}
println!("Hello, world!");
}
为什么它会使堆栈溢出？
请考虑下面这个简单的链表实现:
enum Cons<T> {
Empty,
Cons(T, Box<Cons<T>>),
}
fn main() {
let mut list = Cons::Empty;
for i in 1..1_000_000 {
list = Cons::Cons(i, Box::new(list));
}
println!("Hello, world!");
}
为什么它会使堆栈溢出？
在试图丢弃list时，它会溢出堆栈.Rust生成的Drop Gue只是按顺序删除所有字段，因此它将如下所示(伪代码):
match self {
Self::Empty => {},
Self::Cons(a, b) => {
Drop::drop(&mut a);
Drop::drop(&mut b);
}
}
呼叫Drop::drop(&mut b);将递归到该相同的丢弃代码(通过Box‘S丢弃代码间接地)，并且它将继续递归1,000,000次以丢弃整个列表.不过，请注意，它实际上将创建2,000,000个堆栈帧，因为Cons‘S Drop Gue和Box’S Drop实现将相互调用.这会使堆栈溢出.(请注意，TailCall优化甚至不能执行，因为b是一个盒子--盒子需要在内部Cons被丢弃后销毁.)
解决这个问题似乎很简单，但需要一些技巧，因为您不能移出实现Drop的值.
基本方法是手动实现Drop，并使用迭代而不是递归函数调用递归丢弃 struct .为了帮助实现这一点，我们可以创建一个方法，该方法将"窃取"现有的Cons<T>，留下Empty.就Rust而言，我们可以使用它将Cons<T>值从盒子中取出，而无需实际将其移出.
impl<T> Cons<T> {
pub fn take(&mut self) -> Cons<T> {
std::mem::replace(self, Self::Empty)
}
}
很简单.现在我们可以围绕此方法实现Drop个.
值得注意的是，我们必须首先判断非递归情况(self是Empty，或者是框也是Empty的Cons)，以避免意外的无限递归1.一旦我们知道我们至少有一个级别的递归，我们可以简单地在 struct 中向前循环，将下一项赋给我们的迭代变量take():
impl<T> Drop for Cons<T> {
fn drop(&mut self) {
match self {
Self::Empty => return,
Self::Cons(_, boxed) if matches!(**boxed, Self::Empty) => return,
_ => {}
};
let mut v = self.take();
while let Self::Cons(_, boxed) = &mut v {
v = boxed.take();
}
}
}
现在，当铁 rust 生成的滴胶获得Cons值时，它将始终是Empty，或者是框为Empty的Cons.
1如果我们不首先判断终止用例，第let mut v = self.take();行将导致drop()实现的无限递归.它将无条件地创建一个新的Cons<T>值，该值必须被删除，但是当drop()try 删除该值时，它将无条件地创建another Cons<T>.match块检测终止情况，以避免在Rust自己的Drop Gue正确处理该值时创建新的Cons<T>，而无需多次递归.