Generic associated types (GATs) are a great mechanism to add more flexibility to your traits. I didn't really grok them until tonight. GATs were stabilized near the end of last year, but its purpose eluded me - I wasn't able to work out what I could actually use it for or how.
This evening I was working on an interface for an in-memory key-value store. It needed to have two associated functions, one for fetching stored data, and one for inserting data into the store. The trait I started with was roughly like:
trait Store<K, V> {
fn get(&self, key: &K) -> Option<V>;
fn insert(&mut self, key: K, value: V);
}
Then I can use the trait without worrying about the implementation:
fn insert_and_get<S, K, V>(store: &mut S, key: K, value: V) -> Option<V>
where
K: Clone,
S: Store<K, V>,
{
store.insert(key.clone(), value);
store.get(&key)
}
An implementation of Store might look like this:
struct CloningStore<K, V> {
store: HashMap<K, V>,
}
impl<K, V> CloningStore<K, V> {
fn new() -> Self {
Self {
store: HashMap::new(),
}
}
}
impl<K, V> Store<K, V> for CloningStore<K, V>
where
K: Hash + Eq,
V: Clone,
{
fn get<'store>(&'store self, key: &K) -> Option<V> {
self.store.get(key).cloned()
}
fn insert(&mut self, key: K, value: V) {
self.store.insert(key, value);
}
}
Here I'm wrapping a HashMap and implementing the Store traits items to manipulate the map. The get function will clone the value, so I've added the Clone bound to V.
Putting it all together, I can now instantiate a concrete type, and pass it to my insert_and_get function:
fn main() {
#[derive(Clone, Debug)]
struct MyData(usize);
let mut cloning_store: CloningStore<usize, MyData> = CloningStore::new();
let my_data = insert_and_get(&mut cloning_store, 1, MyData(1)); println!("{my_data:?}"); }
Cloning is expensive and I'd prefer to avoid doing that. So I'd like to have the option of an in-memory store which returns references to the data it's holding. The CloningStore could be switched out for this new one. I can just change the return type:
struct RefStore<K, V> {
store: HashMap<K, V>,
}
impl<K, V> Store<K, V> for RefStore<K, V>
where
K: Hash + Eq,
{
fn get(&self, key: &K) -> Option<&V> {
self.store.get(key)
}
fn insert(&mut self, key: K, value: V) {
self.store.insert(key, value);
}
}
Nope!
cargo run --bin no_ref
Compiling gats v0.1.0 (...)
error[E0053]: method `get` has an incompatible type for trait
--> src/bin/no_ref.rs:62:31
|
58 | impl<K, V> Store<K, V> for RefStore<K, V>
| - this type parameter
...
62 | fn get(&self, key: &K) -> Option<&V> {
| ^^^^^^^^^^
| |
| expected type parameter `V`, found `&V`
| help: change the output type to match the trait: `Option<V>`
|
So the trait needs to be a bit more flexible such that I can set the output types per implementation. I can add the Output associated type to the Store trait and update the get function to return Option<Self::Output>, and then implement that on both CloningStore and RefStore:
trait Store<K, V> {
type Output;
fn get(&self, key: &K) -> Option<Self::Output>;
fn insert(&mut self, key: K, value: V);
}
impl<K, V> Store<K, V> for CloningStore<K, V>
where
K: Hash + Eq,
V: Clone,
{
type Output = V;
fn get<'store>(&'store self, key: &K) -> Option<Self::Output> {
self.store.get(key).cloned()
}
}
impl<K, V> Store<K, V> for RefStore<K, V>
where
K: Hash + Eq,
{
type Output = &V;
fn get(&self, key: &K) -> Option<Self::Output> {
self.store.get(key)
}
}
The compiler is happy... with CloningStore. For RefStore, rustc is noticeably unhappy:
cargo run --bin no_ref
Compiling gats v0.1.0 (...)
error[E0637]: `&` without an explicit lifetime name cannot be used here
--> src/bin/no_ref.rs:64:19
|
64 | type Output = &V;
| ^ explicit lifetime name needed here
error[E0310]: the parameter type `V` may not live long enough
--> src/bin/no_ref.rs:64:19
|
64 | type Output = &V;
| ^^ ...so that the reference type `&'static V` does not outlive the data it points at
|
help: consider adding an explicit lifetime bound...
|
60 | impl<K, V: 'static> Store<K, V> for RefStore<K, V>
| +++++++++
Focusing on the first error: rustc requires a lifetime parameter for the associated type. Sure, I'll add a lifetime parameter to RefStore:
struct RefStore<'store, K, V> {
store: HashMap<K, V>,
}
impl<'store, K, V> Store<K, V> for RefStore<'store, K, V>
where
V: 'store
K: Hash + Eq,
{
type Output = &'store V;
fn get(&self, key: &K) -> Option<Self::Output> {
self.store.get(key)
}
fn insert(&mut self, key: K, value: V) {
self.store.insert(key, value);
}
}
Nope again.
cargo run --bin ref
Compiling gats v0.1.0 (...)
error[E0392]: parameter `'store` is never used
--> src/bin/ref.rs:45:17
|
45 | struct RefStore<'store, K, V> {
| ^^^^^^ unused parameter
|
= help: consider removing `'store`, referring to it in a field, or using a marker such as `PhantomData`
PhantomData it is:
struct RefStore<'store, K, V> {
store: HashMap<K, V>,
_phantom: PhantomData<&'store ()>,
}
Nope.
cargo run --bin ref
Compiling gats v0.1.0 (...)
error: lifetime may not live long enough
--> src/bin/ref.rs:57:9
|
50 | impl<'store, K, V: 'store> Store<K, V> for RefStore<'store, K, V>
| ------ lifetime `'store` defined here
...
56 | fn get(&self, key: &K) -> Option<Self::Output> {
| - let's call the lifetime of this reference `'1`
57 | self.store.get(key)
| ^^^^^^^^^^^^^^^^^^^ associated function was supposed to return data with lifetime `'store` but it is returning data with lifetime `'1`
Ah. I need 'store to live as long as '1, the elided lifetime of &self. I can't update the function so that self is bound to 'store (&'store self) because that would break the trait implementation.
Alright, so maybe I can specify lifetimes on the associated type, i.e. generic associated types. That means that the trait will need to be updated:
trait Store<K, V> {
type Output<'store>
where
Self: 'store;
}
Self should live as long as any value of Output's lifetime 'store. Therefore the get function also needs to be updated to reflect that:
trait Store<K, V> {
type Output<'store>
where
Self: 'store;
fn get<'store>(&'store self, key: &K) -> Option<Self::Output<'store>>;
fn insert(&mut self, key: K, value: V);
}
rustc allows the lifetime to be elided too so there's less boilerplate:
fn get(&self, key: &K) -> Option<Self::Output<'_>>;
Now CloningStore's Store implementation can be updated. It's get function doesn't return a reference, but the type still needs to include the lifetime:
impl<K, V> Store<K, V> for CloningStore<K, V>
where
K: Hash + Eq,
V: Clone,
{
type Output<'store> = V where Self: 'store;
fn get(&self, key: &K) -> Option<Self::Output<'_>> {
self.store.get(key).cloned()
}
}
rustc is happy! Next up is RefStore. RefStore returns a reference, and because there is a named lifetime parameter, I can use that to bind &V to the lifetime of Self:
impl<K, V> Store<K, V> for RefStore<K, V>
where
K: Hash + Eq,
{
type Output<'store> = &'store V where Self: 'store;
fn get(&self, key: &K) -> Option<Self::Output<'_>> {
self.store.get(key)
}
}
The compiler is still happy. Finally, the insert_and_get function from earlier can be updated so that it's return type is that of of Store::Output:
fn insert_and_get<S, K, V>(store: &mut S, key: K, value: V) -> Option<S::Output<'_>>
where
K: Clone,
S: Store<K, V>,
{
store.insert(key.clone(), value);
store.get(&key)
}
The requirements of Store::Output are applied to this too so that any value of S::Output must live as long as the lifetime of &mut S.
And done.
fn main() {
#[derive(Clone, Debug)]
struct MyData(usize);
let mut store: CloningStore<usize, MyData> = CloningStore::new();
let my_data = insert_and_get(&mut store, 1, MyData(1)); println!("{my_data:?}");
let mut store: RefStore<usize, MyData> = RefStore::new();
let my_data = insert_and_get(&mut store, 1, MyData(1)); println!("{my_data:?}"); }