Rust function which takes function with arg a function

Question

I want to write a generic function count_calls which calls a function f which takes a function pointer (lambda) where count_calls counts how often function f called the given lambda function.

I struggle with the approach (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);
    }
}

Here I get the error:

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`

Does someone know how to fix this?

[Edit]

I think using Box<Fn()->S> might be a solution. But I would prefer a stack only solution, if possible.

Answer 1

The error "the size for values of type (dyn std::ops::Fn() -> S + 'static) cannot be known at compilation time" is caused by your trait bound for F:

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

This is equivalent to F: Sized + FnMut(dyn Fn() -> S). This means that the closure F would take a trait object (dyn Fn() -> S) by value. But trait objects are unsized and cannot be passed by value (yet).

One solution would be to pass the trait object by reference or in a Box. The answer by rodrigo explains and discusses these solutions.

---

Can we avoid trait objects and dynamic dispatch?

Not properly, I think.

Non solutions

One idea would be to add another type parameter to count_calls:

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

However, this doesn't work:

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:_]`

The problem here is that type arguments of count_calls are chosen by the caller of count_calls. But we actually want G to always be the type of our own closure. So that doesn't work.

What we want is a generic closure (where we can choose it's type parameters). Something similar is possible, but restricted to lifetime parameters. It's called HRTBs and looks like F: for<'a> Fn(&'a u32). But it doesn't help here because we need a type parameter and for<T> doesn't exist (yet?).

Sub-optimal, nightly solution

One solution would be to not use a closure, but a type with a known name which implements FnMut. Sadly, you can't implement the Fn* traits for your own type on stable yet. On nightly, this works.

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
}

Unfortunately, now you have this strange type in your public interface (which should be implementation detail).

---

Apart from that, I can't think of any real solution (only other super verbose solutions with plenty of disadvantages). The developments in the type system corner (in particular in regards to GATs and HKTs) could solve this properly in the future. However, I think there are still a few different features lacking; in particular, I don't think that GATs as proposed would already solve this.

So if this is a real life problem which needs to be solved right now, I would:

• step back and rethink the problem in a bigger scope to maybe avoid this Rust limitation, or
• just use dynamic dispatch.