评估特征要求时堆栈溢出

Question

我有一个函数，它接受给定 Items 上任何迭代器的可变引用。该函数通常可以一个接一个地消费这些项目，但偶尔也必须执行前瞻。像这样检索的项目有时会被消耗，但有时必须“预先”返回迭代器（使用例如 Chain），然后此函数必须递归。

但是，在解决特征要求时执行在运行时崩溃：

error[E0275]: overflow evaluating the requirement `std::iter::Chain<std::vec::IntoIter<std::string::String>, &mut std::iter::Chain<std::vec::IntoIter<std::string::String>, &mut std::iter::Chain<std::vec::IntoIter<std::string::String>, &mut std::iter::Chain<std::vec::IntoIter<std::string::String>, &mut std::iter::Chain<std::vec::IntoIter<std::string::String>, &mut std::iter::Chain<std::vec::IntoIter<std::string::String>, &mut std::iter::Chain<std::vec::IntoIter<std::string::String>, &mut std::iter::Chain<std::vec::IntoIter<std::string::String>, &mut std::iter::Chain<std::vec::IntoIter<std::string::String>, &mut std::iter::Chain<std::vec::IntoIter<std::string::String>, ...

最小代码为（这里的条件表示不能达到无限递归深度）：

fn foo<I: Iterator<Item = String>>(it: &mut I) -> String {
    if *(&1) == 1 {
        String::new()
    } else {
        foo(&mut vec![String::new()].into_iter().chain(it))
    }
}

fn main() {
    let mut it = vec!["Hello".to_string(), "World!".to_string()].into_iter();
    println!["{:?}", foo(&mut it)];
}

Playground

更改函数以接受特征对象解决了问题，但我不热衷于在这种简单情况下使用动态调度。

我是否必须重构代码、使用特征对象，或者是否有其他解决方案来阻止检查器无限期地递归？

我在 x86_64-apple-darwin 上使用 Rust 1.44.1，但它也在夜间崩溃。

Answer 1

您的错误案例可能会简化为：

fn f(i: impl Iterator<Item = ()>) {
    f(std::iter::once(()).chain(i)) // resolves to f(Chain<Once, I>)
}

fn main() {
    f(vec![].into_iter())
}

导致错误：

overflow evaluating the requirement `std::iter::Chain<std::iter::Once<()>, std::iter::Chain<std::iter::Once<()>, ..>>

发生这种情况是因为必须在编译时实例化静态分派。编译器可能假设深度为 10，但是如果它达到深度 11 应该执行什么？您已经提到的直接解决方案是通过特征对象进行动态调度，您的情况如下所示：

fn foo<I: Iterator<Item = String>>(it: &mut I) -> String {
    if *(&1) == 1 {
        String::new()
    } else {
        let mut it: Box<dyn Iterator<Item = _>> =
            Box::new(vec![String::new()].into_iter().chain(it));
        foo(&mut it) // might also case in-place with `as Box<dyn Iterator...>`
    }
}

另一种方法是用迭代代替递归（这也可能会减少编译时间），正如@loganfsmyth 指出的那样peekable might be a good fit for you. Besides, seq 也可能对这种情况有所帮助。

Answer 2

正如@Kitsu 的回答所解释的那样，您当前的代码有问题，因为编译器无法确定递归的深度。

如果您的基本要求是您的功能：

，请从您当前的方法退后一步

从迭代器中取一个或多个值
根据某些逻辑，要么：
- Return一个结果，或者
- 将值放回迭代器，然后递归到自身

那么这可能是一个解决方案：

fn foo<I: Clone + Iterator<Item = String>>(mut it: I, n: i32) -> String {
    let mut start_iter = it.clone();
    let s = it.next();
    if n>4 {
        "Done".to_string()
    } else {
        foo(start_iter, n+1)
    }
}

fn main() {
    let mut it = ["apples", "bananas", "oranges", "mandarins", "peaches", "pears"].iter()
        .map(|s| s.to_string()).collect::<Vec<String>>().into_iter();
    println!["{:?}", foo(it, 0)];
}

我假设您必须有一些其他状态允许函数确定何时停止递归 - 在我设计的示例中，我刚刚传递了一个额外的 i32 参数。

请注意，迭代器的克隆成本通常很低（可能比构建链式迭代器便宜很多，尤其是盒装迭代器）。

评估特征要求时堆栈溢出

Stack overflow while evaluating trait requirement

recursion

iterator

traits

rust