rust - 实例化 std::vec::IntoIter<i32> 时达到类型长度限制

Question

我正在尝试实现一个 Tree 结构，但每当我尝试运行以下代码时，我总是会收到错误消息:

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

错误:

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

Answer 1

您在创建 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.

此错误发生在编译过程中，错误提示 reached the type-length limit while instantiating... .这意味着您正在生成一个非常长的类型。

它是如何发生的？

当您调用 Tree::create(x, |y| get_children(y)) 时您正在创建一个调用现有闭包的参数闭包。这没关系，但是当你递归调用它时，编译器将无法检测到 F 的类型。在最内在的呼唤。

记住get_children有一个类型 F其中 F: Fn(&T) -> Vec<T> . 当您调用 Tree::create第一次，F在create<F>将被推断为:

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

第二次调用 map(...) 后:

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

那么最终会变成这样:

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

最后，编译器达到类型长度限制。

递归解决方案

作为 Shepmaster's answer 的补充, 你可以使用 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(),
        }
    }
}

无递归的解决方案

您可以通过将函数发送到 Vec<Tree<T>> 来解决这个问题。作为get_children而不是在 create 中生成，像这样:

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

请注意，我将函数参数的类型从 Fn 更改为至 FnOnce .需要将内部树的所有权转移到闭包中。它将被调用一次，以便它可以使用变量。