Rust函数，接受一个带参数的函数作为参数

Question

我想编写一个通用函数count_calls，该函数调用接受函数指针（lambda）的函数f，其中count_calls统计函数f调用给定lambda函数的次数。

我对这个方法感到困惑（Playground）。

fn count_calls<S, F>(s: S, f: F) -> u32
where
    S: Clone,
    F: Sized + FnMut(Fn() -> S) -> (),
{
    let mut counter: u32 = 0;

    f(|| {
        counter += 1;
        s.clone()
    });
    counter
}

#[cfg(test)]
mod stackoverflow {
    use super::*;

    fn f(p: fn() -> i32) {
        p();
        p();
    }

    #[test]
    fn test() {
        let counts = count_calls(3, f);
        assert_eq!(counts, 2);
    }
}

我遇到了错误：

这里我遇到了错误：

error[E0277]: the size for values of type `(dyn std::ops::Fn() -> S + 'static)` cannot be known at compilation time
  --> src/lib.rs:1:1
   |
1  | / fn count_calls<S, F>(s: S, f: F) -> u32
2  | | where
3  | |     S: Clone,
4  | |     F: Sized + FnMut(Fn() -> S) -> (),
...  |
12 | |     counter
13 | | }
   | |_^ doesn't have a size known at compile-time
   |
   = help: within `((dyn std::ops::Fn() -> S + 'static),)`, the trait `std::marker::Sized` is not implemented for `(dyn std::ops::Fn() -> S + 'static)`
   = note: to learn more, visit <https://doc.rust-lang.org/book/ch19-04-advanced-types.html#dynamically-sized-types-and-the-sized-trait>
   = note: required because it appears within the type `((dyn std::ops::Fn() -> S + 'static),)`
   = note: required by `std::ops::FnMut`

有人知道如何修复这个问题吗？

[编辑]

我认为使用 Box<Fn()->S> 可能是一种解决方案。但如果可能的话，我更喜欢仅使用堆栈的解决方案。

- Matthias

---

由于传递给 f 的匿名闭包类型，这比我想象的要棘手得多...我很兴奋看到 Rust 专家们如何处理这个问题。 - turbulencetoo

只是为了确认一下：这是一个纯理论问题（只是为了好玩或出于兴趣），还是你想要解决一个实际的问题？如果是后者，也许你想分享一些有关那个问题的细节。当然，一个纯粹的理论问题也很好！事实上，我认为这是一个好问题。我感到困惑（虽然我不认为静态分派已经能够做到 :/）。 - Lukas Kalbertodt

@LukasKalbertodt 这是一个实际问题的简化版本，它指出了关键问题。实际问题是一种 map 或 flat_map。但映射函数采用函数指针，允许它请求额外的数据。该映射提供数组的项（每个请求仅提供一个）。如果有数据被请求并且所有项都由映射提供，则映射会提供前一个迭代器的下一项。您可以将其视为 SQL 中的交叉连接。但计算数组是昂贵的，只有在极少数情况下才需要。这就是为什么通过函数指针进行惰性计算的原因。 - Matthias

Answer 1

错误"值类型为(dyn std::ops::Fn() -> S + 'static)的大小在编译时无法确定"是由于您对F的特质限制造成的：

F: Sized + FnMut(Fn() -> S) -> ()

这相当于F: Sized + FnMut(dyn Fn() -> S)。这意味着闭包F将通过值获取一个特质对象(dyn Fn() -> S)。但是特质对象是不定大小的，不能按值传递(尚未)。

一个解决方案是通过引用或在Box中传递特质对象。rodrigo的答案解释并讨论了这些解决方案。

---

我们能避免使用特质对象和动态调度吗？

我认为不行。

非解决方案

一个想法是为count_calls添加另一个类型参数：

fn count_calls<S, F, G>(s: S, f: F) -> u32
where
    S: Clone,
    F: Sized + FnMut(G),
    G: Fn() -> S,

然而，这并不起作用：

error[E0308]: mismatched types
  --> src/lib.rs:9:7
   |
9  |       f(|| {
   |  _______^
10 | |         counter += 1;
11 | |         s.clone()
12 | |     });
   | |_____^ expected type parameter, found closure
   |
   = note: expected type `G`
              found type `[closure@src/lib.rs:9:7: 12:6 counter:_, s:_]`

问题在于 count_calls 的类型参数是由调用者选择的。但实际上，我们希望 G 总是成为我们自己闭包的类型。所以这样行不通。

我们想要的是一个通用的闭包（其中我们可以选择其类型参数）。类似的东西是可能的，但只限于生命周期参数。它被称为HRTBs，看起来像 F: for<'a> Fn(&'a u32)。但在这里没有帮助，因为我们需要一个类型参数，而 for<T> 不存在（尚未存在？）。

次优解决方案 (Sub-optimal, nightly solution)

一个解决方案是不使用闭包，而是使用已知名称的类型，该类型实现了 FnMut。不幸的是，在稳定版中，你无法为自己的类型实现 Fn* 特质，但在 nightly 版本中可以。 在 nightly 版本中这样做是可行的。

struct CallCounter<S> {
    counter: u32,
    s: S,
}
impl<S: Clone> FnOnce<()> for CallCounter<S> {
    type Output = S;
    extern "rust-call" fn call_once(self, _: ()) -> Self::Output {
        // No point in incrementing the counter here
        self.s
    }
}
impl<S: Clone> FnMut<()> for CallCounter<S> {
    extern "rust-call" fn call_mut(&mut self, _: ()) -> Self::Output {
        self.counter += 1;
        self.s.clone()
    }
}

fn count_calls<S, F>(s: S, mut f: F) -> u32
where
    S: Clone,
    F: Sized + FnMut(&mut CallCounter<S>),     // <----
{
    let mut counter = CallCounter {
        counter: 0,
        s,
    };

    f(&mut counter);   // <-------

    counter.counter
}

不幸的是，现在你的公共接口中有了这种奇怪的类型（这应该是实现细节）。

---

除此之外，我想不出任何真正的解决方案（只有其他超级冗长的解决方案，并且存在很多缺点）。类型系统领域的发展（特别是GATs和HKTs方面）未来可能会适当地解决这个问题。然而，我认为仍然缺少一些不同的功能；特别是，我认为所提出的GATs还不能解决这个问题。

因此，如果这是一个需要立即解决的实际问题，我会：

• 退后一步，在更大的范围内重新思考问题，以避免这种Rust限制，或
• 只使用动态调度。

- Lukas Kalbertodt

---

很棒的答案！但我认为在这种情况下，动态分派是最好的解决方案。它并不会带来太大的性能损失，值得写复杂的代码来避免它。 - rodrigo

Answer 2

这是我设法让其工作的最简单代码（playground）：「这是最初的回答」。

fn count_calls<S, F>(s: S, mut f: F) -> u32
where
    S: Clone,
    F: FnMut(&mut dyn FnMut() -> S) -> (),
{
    let mut counter: u32 = 0;

    f(&mut || {
        counter += 1;
        s.clone()
    });
    counter
}

#[cfg(test)]
mod stackoverflow {
    use super::*;

    fn f(p: &mut dyn FnMut() -> i32) {
        p();
        p();
    }

    #[test]
    fn test() {
        let counts = count_calls(3, f);
        assert_eq!(counts, 2);
    }
}

关键的改变在于F的函数参数已经从Fn() -> S变成了&mut dyn FnMut() -> S。你需要引用，因为你正在使用动态分派。此外，你需要FnMut，因为你正在捕获counter并在内部更改它，而Fn不允许这样做。

请注意，你不能使用Box<FnMut() -> S。它将不允许捕获对counter的引用，因为箱化函数必须是“静态的”。

如果你发现将你的Fn更改为FnMut是不可取的(因为你正在更改你的公共API)，你可以通过将counter定义为Cell<u32>来返回到F: FnMut(&mut dyn Fn() -> S) -> ()：

fn count_calls<S, F>(s: S, mut f: F) -> u32
where
    S: Clone,
    F: FnMut(&dyn Fn() -> S) -> (),
{
    let counter: Cell<u32> = Cell::new(0);

    f(&|| {
        counter.set(counter.get() + 1);
        s.clone()
    });
    counter.into_inner()
}

- rodrigo