What does "Overflow evaluating the requirement" mean and how can I fix it?

Question

I'm running into what is potentially a compiler bug. However, I don't understand the issue well enough to port the proposed solution to my own code. Here's a stripped-down version of my code:

struct Node {
    pub children: Vec<Node>,
}

fn map_nodes<F, R>(f: F, n: &Node) -> Vec<R>
where
    F: Fn(&Node) -> R,
{
    let mut v: Vec<R> = Vec::new();
    v.push(f(n));

    v.extend(n.children.iter().flat_map(|child| map_nodes(&f, &child)));

    v
}

fn main() {
    let node = Node {
        children: vec![Node { children: vec![] }, Node { children: vec![] }],
    };

    println!("Node lengths: {:?}", map_nodes(|n| n.children.len(), &node));
}

Specifically the error for this code is:

error[E0275]: overflow evaluating the requirement `[closure@src/main.rs:22:46: 22:66]: std::ops::Fn<(&Node,)>`
  |
  = help: consider adding a `#![recursion_limit="128"]` attribute to your crate
  = note: required because of the requirements on the impl of `std::ops::Fn<(&Node,)>` for `&[closure@src/main.rs:22:46: 22:66]`
  = note: required because of the requirements on the impl of `std::ops::Fn<(&Node,)>` for `&&[closure@src/main.rs:22:46: 22:66]`
  # ... this continues for many lines ...

Answer 1

The problem is an incompatibility, (which I'll show how to resolve) between unique closure types, how generics are instantiated when Rust is compiled, and a recursive use of the closure.

fn map_nodes<F, R>(f: F, n: &Node) -> Vec<R>
where
    F: Fn(&Node) -> R,

Each recursive call instantiates a new version of this function, with a new type inserted for F. In this case, the map_nodes receives F and passes on &F, and it creates an infinite series of new map_nodes specializations that would need to be compiled.

What you can do instead is use a concrete closure type by using a reference to a Fn trait object:

fn map_nodes<R>(f: &Fn(&Node) -> R, n: &Node) -> Vec<R>

This would require inserting a & before the lambda expression where the closure is used: map_nodes(&|n| n.children.len(), &node).

If you don't want to burden your public API with this difference, then you can use an internal wrapper for your recursive function instead:

fn map_nodes<F, R>(f: F, n: &Node) -> Vec<R>
where
    F: Fn(&Node) -> R,
{
    fn map_nodes_inner<R>(f: &Fn(&Node) -> R, n: &Node) -> Vec<R> {
        let mut v: Vec<R> = Vec::new();
        v.push(f(n));

        v.extend(n.children.iter().flat_map(|child| map_nodes_inner(f, &child)));

        v
    }

    map_nodes_inner(&f, n)
}

Answer 2

I don't claim to fully understand the problem, but it looks like an issue with resolving a type parameter. For example, what does F correspond to? At the first level, it is the closure. At the next level, it's a reference to that closure. At the next level, it's a reference to the reference of the closure.

My guess is that this is happening because of inlining, and basically it has hit an infinite recursion.

You can fix it by passing a reference to your closure instead:

struct Node {
    pub children: Vec<Node>,
}

fn map_nodes<F, R>(f: &F, n: &Node) -> Vec<R>
where
    F: Fn(&Node) -> R,
{
    let mut v = Vec::new();
    let z: R = f(n);
    v.push(z);

    v.extend(n.children.iter().flat_map(|child| map_nodes(f, &child)));

    v
}

fn main() {
    let node = Node {
        children: vec![Node { children: vec![] }, Node { children: vec![] }],
    };

    println!(
        "Node lengths: {:?}",
        map_nodes(&|n| n.children.len(), &node)
    );
}