Implementation is not general enough when using lifetime in generic type

help
1

Greetings!

I'm trying to write some multiple key caching, where data have a method to generate a sequence of keys on which hash will be generated and stored.
Keys are based on inner value members and because we need only hash from them, I'm trying to do not use Clone. But again I faced with complex compiler error:

error: implementation of `GenKeys` is not general enough
  --> src/main.rs:80:11
   |
80 |     cache.insert(obj);
   |           ^^^^^^ implementation of `GenKeys` is not general enough
   |
   = note: `Foo` must implement `GenKeys<'0, Keys<'_>, 2_usize>`, for any lifetime `'0`...
   = note: ...but it actually implements `GenKeys<'1, Keys<'1>, 2_usize>`, for some specific lifetime `'1`

Here some reproducible code:

use std::{
    collections::hash_map::{DefaultHasher, HashMap},
    hash::{Hash, Hasher},
    marker::PhantomData,
};

type Id = u16;

trait GenKeys<'a, K: 'a, const NUMBER_OF_KEYS: usize> {
    fn id(&self) -> Id;
    fn gen_keys(&'a self) -> [K; NUMBER_OF_KEYS];
}

#[derive(Debug)]
struct Cache<K, V, const NUMBER_OF_KEYS: usize> {
    keys_to_hash: HashMap<u64, Id>,
    cache: HashMap<Id, V>,
    phantom: PhantomData<K>,
}

impl<K, V, const NUMBER_OF_KEYS: usize> Default for Cache<K, V, NUMBER_OF_KEYS> {
    fn default() -> Self {
        Self {
            keys_to_hash: Default::default(),
            cache: Default::default(),
            phantom: Default::default(),
        }
    }
}

impl<K, V, const NUMBER_OF_KEYS: usize> Cache<K, V, NUMBER_OF_KEYS>
where
    K: Hash,
    for<'a> V: GenKeys<'a, K, NUMBER_OF_KEYS>,
{
    pub fn insert(&mut self, value: V) {
        let id = value.id();
        let keys = value.gen_keys().map(|k| (calc_hash(&k), id));
        self.keys_to_hash.extend(keys);
        self.cache.insert(id, value);
    }
}

fn calc_hash<T: Hash>(value: &T) -> u64 {
    let mut s = DefaultHasher::new();
    value.hash(&mut s);
    s.finish()
}

#[derive(Debug, Hash)]
enum Keys<'a> {
    ID(Id),
    Data(&'a str),
}

#[derive(Debug)]
struct Foo {
    id: Id,
    data: String,
}

impl<'a> GenKeys<'a, Keys<'a>, 2> for Foo {
    fn id(&self) -> Id {
        self.id
    }

    fn gen_keys(&'a self) -> [Keys<'a>; 2] {
        [Keys::ID(self.id), Keys::Data(&self.data)]
    }
}

fn main() {
    let mut cache = Cache::default();

    let obj = Foo {
        id: 1,
        data: "FOO".to_owned(),
    };

    cache.insert(obj);

    println!("{:?}", cache);
}
2

This:

    let mut cache = Cache::default();

Has an inferred type something like this:

Cache<Keys<'main>, Foo, 2>

In particular, note that the type involves one specific lifetime, which I've named 'main. So when you try to utilize this implementation:

impl<K, V, const NUMBER_OF_KEYS: usize> Cache<K, V, NUMBER_OF_KEYS>
where
    K: Hash,
    for<'a> V: GenKeys<'a, K, NUMBER_OF_KEYS>,

The bounds demand

for<'any> Foo: GenKeys<'any, Key<'main>, 2>

And this is where the error message is coming from.

I imagine something like a generic associated type (GAT) would help here. Is there any reason aside from lifetimes that the K in GenKeys needs to be generic? That is, does anything need to implement GenKeys<'_, K, _> with K that are different after erasing lifetimes?

3

Yes, because cache will be for several types.

4

You mean this? I saw that before, when tried to solve the problem, but it's RFC =(

5

Yeah, it's not stable, but you can emulate it on stable to some degree.

Like so, for example. Here I have

  • Created a new Keyable<'a> trait to emulate GAT
    • I put the Hash bound in here to as it avoided a normalization problem
  • Changed GenKeys to drop the lifetime and have a bound on the K parameter instead
    • So now gen_keys utilizes the GAT-like trait
  • Changed the impl Cache bounds to match
  • Created a KeysType stand-in to represent for<'any> Keys<'any>
    • Because the K in GenKeys<K, ...> must be a single type
  • Changed the implementation of GenKeys for Foo to use KeysType
1 Like
6

Many-many-many thanks!!!
I tried to do something similar to what you did (with wrapper stuff), but I didn't get to that idea:

<K as Keyable<'_>>::Key
7

This topic was automatically closed 90 days after the last reply. We invite you to open a new topic if you have further questions or comments.