"溢出评估需求"是什么意思,我该如何解决？

Question

我正在遇到可能是编译器错误的问题.但是,我不能很好地理解这个问题,以便将提议的解决方案移植到我自己的代码中.这是我的代码的简化版本:

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

具体来说,此代码的错误是:

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

问题是不兼容性(我将展示如何解决)在唯一闭包类型之间,如何在编译Rust时实例化泛型,以及递归使用闭包.

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

每个递归调用都会实例化此函数的新版本,并插入新类型F.在这种情况下,map_nodes接收F并传递&F,它创建了一系列map_nodes需要编译的新特化.

你可以做的是通过使用对Fn特征对象的引用来使用具体的闭包类型:

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

这将需要插入一个&其中使用封闭lambda表达式之前:map_nodes(&|n| n.children.len(), &node).

如果您不希望使用这种差异来增加公共API的负担,那么您可以使用内部包装器来代替递归函数:

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

我没有声称完全理解这个问题,但它似乎是一个解决类型参数的问题.例如,什么F对应？在第一级,它是关闭.在下一个级别,它是对该闭包的引用.在接下来的水平,这是对封闭的参考基准.

我的猜测是因为内联发生了这种情况,基本上它已经达到无限递归.

您可以通过将引用传递给闭包来修复它:

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