Overflow evaluating the requirement when returning a recursive iterator using impl trait

Question

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

(You can check this out yourself on the playground.)

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.

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"?

Answer 1

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, 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.

---

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
    }
}