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

score 13 · Accepted Answer · edited Dec 31 '18 at 16:50

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

The question is open for 3 hours, and we answer it within 26 seconds. Stack Overflow is *weird*. — Shepmaster, Jul 03 '15 at 03:05
Tell me about it... how do I go about picking an answer now? — user12341234, Jul 03 '15 at 03:45
I may be biased, but :-) pick this one, since it explains the reason (how rust compiles generic items). — bluss, Jul 03 '15 at 10:58

Shepmaster · Answer 2 · 2018-12-31T16:52:29.300

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

I didn't know there was a closure-reference literal! Very cool. — user12341234, Jul 03 '15 at 03:44
@user12341234: You can use `&` to take the address of any expression. If the expression is a literal or a temporary, the compiler will silently create a temporary, anonymous binding (variable) for the expression and drop the value at the end of the statement. — Francis Gagné, Jul 03 '15 at 07:04

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

2 Answers2

Linked