Reached the type-length limit while instantiating std::vec::IntoIter

Question

I am trying to implement a Tree structure, but I keep getting an error whenever I try to run the following code:

fn main() {
    let tree = Tree::create(1, |_| Vec::new());
    println!("{:?}", tree);
}

#[derive(Debug)]
struct Tree<T> {
    value: T,
    children: Vec<Tree<T>>,
}

impl<T> Tree<T> {
    fn create<F>(value: T, get_children: F) -> Tree<T>
    where
        F: Fn(&T) -> Vec<T>,
    {
        let children = get_children(&value);
        Tree {
            value,
            children: children
                .into_iter()
                .map(|x| Tree::create(x, |y| get_children(y)))
                .collect(),
        }
    }
}

The error:

error: reached the type-length limit while instantiating `<std::vec::IntoIter<i32> as std::iter::Iterator>::map::<Tree<i32...`
  |
  = note: consider adding a `#![type_length_limit="2097152"]` attribute to your crate

Ömer Erden · Accepted Answer · 2019-01-01T16:55:52.047

You are making a recursive call when creating Tree<T>:

impl<T> Tree<T> {
    fn create<F>(value: T, get_children: F) -> Tree<T>
    //...
    //...
        .map(|x| Tree::create(x, |y| get_children(y))) //endless recursive call

I'm confused why it infinitely recursed since I returned an empty vector in the closure.

This error occurs during compilation and the error says that reached the type-length limit while instantiating.... This means you are generating an enormously long type.

How does it happen?

When you call Tree::create(x, |y| get_children(y)) you are creating an argument closure which calls an existing closure. This is okay, but when you call it recursively the compiler will not able to detect the type of F at the most inner call.

Remember get_children has a type F where F: Fn(&T) -> Vec<T>. When you call Tree::create for the first time, F in create<F> will be inferred like this:

let tree = Tree::create(1, |_| Vec::new());
//inference of F: Fn(&T) -> Vec<T>

After the second call in map(...) :

Tree::create(x, |y| get_children(y))
//inference of F: Fn(&T) -> Fn(&T) -> Vec<T>

Then it will eventually turn into this:

//inference of F: Fn(&T)-> Fn(&T) -> Fn(&T) -> Vec<T>
//inference of F: Fn(&T)-> ... -> Fn(&T) -> Fn(&T) -> Vec<T>

At the end, the compiler reaches the type-length limit.

Solution with recursion

As an addition to Shepmaster's answer, you can use function pointers:

impl<T> Tree<T> {
    fn create(value: T, get_children: fn(&T) -> Vec<T>) -> Tree<T> {
        let children = get_children(&value);
        Tree {
            value,
            children: children
                .into_iter()
                .map(|x| Tree::create(x, get_children))
                .collect(),
        }
    }
}

Solution without recursion

You can fix the issue by sending the function to Vec<Tree<T>> as get_children instead of generating in create, like this:

fn main() {
    let inner_tree = Tree::create(1, |_| Vec::new());
    let tree = Tree::create(1, move |_| vec![inner_tree]);
    println!("{:?}", tree);
}

#[derive(Debug)]
struct Tree<T> {
    value: T,
    children: Vec<Tree<T>>,
}

impl<T> Tree<T> {
    fn create<F>(value: T, get_children: F) -> Tree<T>
    where
        F: FnOnce(&T) -> Vec<Tree<T>>,
    {
        let children = get_children(&value);
        Tree { value, children }
    }
}

Please notice that I changed the function parameter's type from Fn to FnOnce. It is needed to move ownership of inner trees into a closure. It is going to be called once so it can consume the variable.

Thanks for the help. The recursion was intentional — I was hoping to take a tree like structure (such as a DOM tree) and wrap it in a formal tree structure so I can add methods to map, fold, etc. I'm confused why it infinitely recursed since I returned an empty vector in the closure. — Adam Putinski, Dec 31 '18 at 14:44
Thanks for the great explanation. The error message makes much more sense now. So is what I'm trying to achieve not possible? — Adam Putinski, Dec 31 '18 at 16:24
@AdamPutinski I wasn't able to response back, edited answer again, i hope it helps you more. — Ömer Erden, Jan 01 '19 at 13:01
For the simple example given by the OP, no. However, it's not hard [to imagine a case where it's desired](https://play.rust-lang.org/?version=stable&mode=debug&edition=2018&gist=b66a18107ff0b773a115404eb6b0ef91). — Shepmaster, Jan 01 '19 at 17:00
@Shepmaster Indeed, but imo expected argument which called get_children should just get the children. Mutable behavior is a bad design for this case despite i was just trying to add conciseness to your code(where you were using **Immutable Fn**) . — Ömer Erden, Jan 01 '19 at 17:17
I disagree that mutable is bad design here; you simply cannot make such a broad proclamation. It's certainly within an API designers right to make that choice, but the Rust standard library has had multiple cases where people used `Fn` and retroactively realized that they should have used `FnMut`. You are right that my original answer used `Fn`; I followed the OPs lead. I have since changed that. Additionally, a function pointer removes [the ability for **immutable state** as well](https://play.rust-lang.org/?version=stable&mode=debug&edition=2018&gist=8fbaf9aa0f66423fac8863ade15fc06b). — Shepmaster, Jan 01 '19 at 17:26
@Shepmaster It was certainly not a broad proclamation, it was an opinion that points **get_children** should get the children without mutating. I also never wrote: use `fn` instead of `Fn`, like you said the API designers right to make that choice.It is also valid for deciding what to use `fn` or `Fn`. — Ömer Erden, Jan 01 '19 at 17:58

Shepmaster · Answer 2 · 2019-01-01T17:02:30.223

This is the same underlying problem as What does "Overflow evaluating the requirement" mean and how can I fix it? and can be solved the same way. This means you avoid the type-level recursion by using a reference trait object:

impl<T> Tree<T> {
    fn create(value: T, mut get_children: impl FnMut(&T) -> Vec<T>) -> Tree<T> {
        fn create_inner<T>(value: T, get_children: &mut FnMut(&T) -> Vec<T>) -> Tree<T> {
            let children = get_children(&value)
                .into_iter()
                .map(|x| create_inner(x, get_children))
                .collect();

            Tree { value, children }
        }

        create_inner(value, &mut get_children)
    }
}

I've also switched from Fn to FnMut, as its better to be more flexible with closure types when possible.

Thank you. This is very helpful! – Adam Putinski Dec 31 '18 at 17:13 — Adam Putinski, Dec 31 '18 at 17:13

Reached the type-length limit while instantiating std::vec::IntoIter

2 Answers2

How does it happen?

Solution with recursion

Solution without recursion