使用impl特征返回递归迭代器时溢出评估需求 [英] Overflow evaluating the requirement when returning a recursive iterator using impl trait
问题描述
我正在尝试在Rust中的树结构上进行深度优先的迭代.我以为我对此有一个非常好的简洁解决方案，但我无法对其进行编译.从概念上讲，这很简单:遍历子级，先获得每个子级的深度迭代器，然后将它们展平，然后将当前节点的元数据迭代器链接到子级.
I'm trying to iterate depth-first over a tree structure in Rust. I thought I had a really nice concise solution for this, but I can't get it to compile. Conceptually it's pretty simple: iterate over the children, get each child's depth first iterator, flatten them, and chain the current node's metadata iterator to it.
#[derive(Debug, Eq, PartialEq)]
struct Node {
metadata: Vec<i64>,
children: Vec<Box<Node>>,
}
impl Node {
fn depth_first_metadata_iter(&self) -> impl Iterator<Item = &i64> + '_ {
self.children
.iter()
.map(|child| child.depth_first_metadata_iter())
.flatten()
.chain(self.metadata.iter())
}
}
fn main() {
let tree = Node {
metadata: vec![1, 2, 3],
children: vec![
Box::new(Node {
metadata: vec![4, 5],
children: vec![],
}),
Box::new(Node {
metadata: vec![6, 7],
children: vec![],
}),
],
};
println!(
"{:?}",
tree.depth_first_metadata_iter().collect::<Vec<&i64>>()
);
}
但是，当我编译它时，出现以下错误:
However, when I compile this, I get the following error:
error[E0275]: overflow evaluating the requirement `impl std::iter::Iterator`
|
= help: consider adding a `#![recursion_limit="128"]` attribute to your crate
(您可以在这是有道理的，因为我正在depth_first_metadata_iter内进行递归调用，该调用返回嵌套的迭代器，但是如果类似这样的代码可以在不需要实现自定义迭代器的情况下工作，那将非常好.
It makes sense that this would be an error, as I am making recursive calls inside depth_first_metadata_iter which return nested iterators, but it would be really nice if something like this code could work without having to implement a custom iterator.
我所见过的E0275错误的所有其他解决方案(例如此，此)似乎涉及从策略上将类型注释放置在某处-可能在这种情况下发生，还是我尝试不可能"?
All other solutions to the E0275 error I have seen (eg. this, this, this) seem to involve strategically placing a type annotation somewhere - is something like that possible here, or am I trying something "impossible"?
推荐答案
如果类似此代码的代码行得通
if something like this code could work
取决于您的意思.这是相似的，可以运行，并且不需要自定义迭代器.从而满足您的所有要求:
Depends on how "like" you mean. This is similar, works, and doesn't require a custom iterator; thus meeting all of your requirements:
fn depth_first_metadata_iter(&self) -> Box<Iterator<Item = &i64> + '_> {
Box::new({
self.children
.iter()
.flat_map(|child| child.depth_first_metadata_iter())
.chain(self.metadata.iter())
})
}
从本质上讲，这是与
At the heart, this is the same problem as shown in
- What does "Overflow evaluating the requirement" mean and how can I fix it?
- "Overflow evaluating the requirement" but that kind of recursion should not happen at all
- Curiously recurring generic trait pattern: overflow evaluating the requirement
暂时搁置一下编译器的工作.您的原始代码说:我将返回一个具体的迭代器类型，但我不会说确切的类型".编译器仍然必须能够找出该类型，所以让我们成为编译器:
Put yourself in the compiler's shoes for a while. Your original code says "I'm going to return a concrete iterator type, but I'm not going to say the exact type". The compiler still has to be able to figure out that type, so let's be the compiler:
let a = self.children.iter();
// std::slice::Iter<'_, Box<Node>>
let cls = |child| child.depth_first_metadata_iter();
// Fn(&Box<Node>) -> ?X?
let b = a.flat_map(cls);
// FlatMap<Iter<'_, Box<Node>>, ?X?, Fn(&Box<Node>) -> ?X?>
let d = self.metadata.iter();
// std::slice::Iter<'_, i64>
b.chain(d);
// Chain<FlatMap<Iter<'_, Box<Node>>, ?X?, Fn(&Box<Node>) -> ?X?>, Iter<'_, i64>>
此最终结果是返回值，因此我们得到了等式:
This end result is the return value, so we have our equation:
Chain<FlatMap<Iter<'_, Box<Node>>, ?X?, Fn(&Box<Node>) -> ?X?>, Iter<'_, i64>> === ?X?
AFAIK，无法执行类型级代数来求解?X?，因此会出现错误.
AFAIK, it's impossible to perform the type-level algebra to solve for ?X?, thus you get the error.
将返回类型更改为盒装特征对象会使所有所需逻辑短路，并强制使用特定的具体类型.
Changing the return type to a boxed trait object short circuits all of the logic needed and forces a specific concrete type.
从策略上将类型注释放置在某处
strategically placing a type annotation somewhere
我认为情况并非如此.如果是这样，那就意味着代数 是可解的，但是编译器不够聪明，无法解决它.虽然在其他情况下无疑是正确的，但我不认为这是真的.
I don't believe this to be the case. If so, that would mean that the algebra is solvable but that the compiler isn't smart enough to solve it. While this is undoubtedly true in other situations, I don't think it is here.
我认为这不是一个 great 解决方案，因为这会涉及很多微小的分配.我假设(但尚未测试)使用堆栈数据结构的自定义迭代器会更有效.
I don't think this is a great solution, as this will involve lots of tiny allocations. I'd assume (but have not tested) that a custom iterator using a stack data structure would be more efficient.
中间点是建立整个节点集:
A middle ground would be to build up the entire set of nodes:
impl Node {
fn depth_first_metadata_iter(&self) -> impl Iterator<Item = &i64> + '_ {
self.x().into_iter()
}
fn x(&self) -> Vec<&i64> {
fn x_inner<'a>(node: &'a Node, v: &mut Vec<&'a i64>) {
for c in &node.children {
x_inner(c, v)
}
v.extend(&node.metadata);
}
let mut v = Vec::new();
x_inner(self, &mut v);
v
}
}
这篇关于使用impl特征返回递归迭代器时溢出评估需求的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
