Is there a way to store a closure in a struct without relying on dynamic dispatch ?
I want to create a binary heap where elements are sorted using a custom key. For that, i used the binary_heap_plus crate, and my code looks like this:
struct Foo {
// fields
}
type Key = Box<dyn Fn(&Foo) -> usize>;
struct Queue {
heap: binary_heap_plus::BinaryHeap<Foo, KeyComparator<Key>>
}
impl Queue {
fn new() -> Self {
let precomputed_results: ResultArray = todo!(); // Expensive computations
let key = |foo: &Foo| precomputed_results[foo];
Self {
heap: binary_heap_plus::BinaryHeap::new_by_key(Box::new(key))
}
}
fn push(&mut self, item: Foo) {
self.heap.push(item)
}
fn pop(&mut self) -> Option<Foo> {
self.heap.pop()
}
}
// Just for avoiding a compilation error in the example
struct ResultArray {
// fields
}
impl Index<&Foo> for ResultArray {
type Output = usize;
fn index(&self, index: &Foo) -> &Self::Output {
todo!()
}
}
The problem is that the Box<dyn Trait> introduces a performance penalty that i want to avoid, by using static dispatch for example.
However:
I can't simply replace Box<dyn Trait> by impl Trait (impl Trait are not allowed in struct fields)
I can't use fn(&Foo) -> usize since the closure captures its environment (precomputed_results)
If I try making Queue generic over a parameter K (the key), I get a compilation error saying that my chosen type for K might not match the caller's chosen type for K, but I don't want the caller to choose the type of K (code below)
error[E0308]: mismatched types
--> src/main.rs:131:22
|
128 | impl<K: Fn(&Foo) -> usize> Queue<K> {
| - this type parameter
...
131 | let key: K = |foo: &Foo| precomputed_results[foo];
| - ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ expected type parameter `K`, found closure
| |
| expected due to this
|
= note: expected type parameter `K`
found closure `[closure@src/main.rs:131:22: 131:33]`
= help: every closure has a distinct type and so could not always match the caller-chosen type of parameter `K`
Is there a way for me to avoid dynamic dispatch, or am I forced to pay a performance penalty ?
If you literally want a closure, then there's no way to do this, because you'd have to spell out the exact type of the closure, but they are unnameable. A generic won't do, because generics are chosen by the caller (as you observed); the technical term is that they are "universally quantified".
What you want instead is called an "existential" type, which is either impl Trait or dyn Trait, of which impl Trait doesn't currently work. I don't think it can ever work, because struct declarations must contain concrete types – but there's no actual, executable code to infer the concrete field type from, like there is for return-position impl Trait in a function.
However, you are not forced to use a literal closure! binary_heap_plus makes use of the Compare trait, which happens to be implemented for functions, but also for many other types, and you can also implement it for your own, custom types!
So, what you could do in this case is to replace your closure with a concrete struct type, storing captures in fields, and then implement Compare for it, basically using the code that is currently the body of your closure.
Yeah, I guess there's a good reason it hasn't been stabilized for 4 years The example you posted is trivial, but if I change it very slightly, I get an error that is understandable (if you understand the mechanics of impl Trait), but still feels quite stupid. This is not an easy feature to implement correctly/intuitively/conveniently, and it feels very much like a hack anyway (it's action at a distance hiding in plain sight).
I believe you can almost make it work, though it need some tricks to workaround the limitations. the API is not excatly the same as your original, but close enough.
Disclamer: this is a concept which should work, but I didn't verify it.
first, you use an generic function to get the actual type of the closure, somethin like this:
although you can use the closure type, you can't name it, so you will not be able to define an named return type for the new function, but you can use one extra level of indirection via another type level manipulation, something like this:
trait QueueTrait {
type KeyType;
fn into_queue(self) -> Queue<Self::KeyType>;
}
impl<K> QueueTrait for Queue<K> {
type KeyType = K;
fn into_queue(self) -> Queue<K> {
self
}
}
fn new_queue() -> impl QueueTrait {
let precomputed_results: ResultArray = todo!(); // Expensive computations
let key: K = |foo: &Foo| precomputed_results[foo];
new_queue_inferred(key)
}
the caller need an extra into() to actually get a Queue
let queue = new_queue().into_queue()
if you prefer namespaced constructor function, just remember put it into an impl block with concret type argument, otherwise the compiler will complain and the caller must specifiy a type argument, like this:
The example you posted is trivial, but if I change it