Dictionary trait: abstracting entries

help
1

Hi,

I'm trying to implement a trait that would cover some common methods of HashMap, BTreeMap and others. But I cannot figure out how to properly implement lifetimes for the entry trait method.

The basic idea is the following (I will minimalize the example to highlight my problem, that's why VacantEntry does not need to be specified)

pub trait OccupiedEntry {
    type Key;
    type Value;

    fn get_mut(&mut self) -> &mut Self::Value;
}

pub enum Entry<VacantEntry, OccupiedEntry>  {
    Vacant(VacantEntry),
    Occupied(OccupiedEntry),
}

pub trait Dictionary {
    type Key;
    type Value;
    type VacantEntry;
    type OccupiedEntry;

    fn entry(&mut self, key: Self::Key) ->
        Entry<Self::VacantEntry, Self::OccupiedEntry>;
}

Then, I want to implement it for HashMap:

use std::collections::hash_map;
use std::hash::Hash;

impl <'a, Key: 'a, Value: 'a>
    OccupiedEntry
    for hash_map::OccupiedEntry<'a, Key, Value>
{
    type Key = Key;
    type Value = Value;

    fn get_mut(&mut self) -> &mut Value { <Self>::get_mut(self) }
}

impl <Key: Eq + Hash, Value>
    Dictionary
    for hash_map::HashMap<Key, Value>
{
    type Key = Key;
    type Value = Value;
    type VacantEntry = hash_map::VacantEntry<'a, Key, Value>;
    type OccupiedEntry = hash_map::OccupiedEntry<'a, Key, Value>;

    fn entry(&mut self, key: Key) ->
        Entry<Self::VacantEntry, Self::OccupiedEntry>
    {
        match <Self>::entry(self, key) {
            hash_map::Entry::Vacant(e) => Entry::Vacant(e),
            hash_map::Entry::Occupied(e) => Entry::Occupied(e),
        }
    }
}

Which of course does not work because we don't know the lifetime 'a. I tried adding the 'a as a trait bound of Dictionary and changing fn entry(&mut self to fn entry(&'a mut self. Then I could implement the instance with impl <'a, Key: 'a + Eq + Hash, Value: 'a> but it was too restrictive: The following could not compile because I could not specify the local lifetime of the entry1 in the Value of the OccupiedEntry:

    struct NestedDict<Dict>(Dict);

    impl<
        'a,
        Dict1: Dictionary<'a>,
    > NestedDict<Dict1>
    where
        Dict1::Value: Dictionary<'a>,
        Dict1::OccupiedEntry: OccupiedEntry<Key=Dict1::Key, Value=Dict1::Value>,
    {
        // this is a simplified good-for-nothing unbuildable function,
        // of course the real insert will also have a value.
        pub fn insert(
            &'a mut self,
            key1: Dict1::Key,
            key2: <Dict1::Value as Dictionary<'a>>::Key,
        )
        {
            match self.0.entry(key1) {
                Entry::Vacant(_) => (),
                Entry::Occupied(mut entry1) => {
                    entry1.get_mut().entry(key2);
                },
            }
        }
    }

I have a feeling that it could be done using higher rank trait bounds and maybe generic associated types, but... This is the point where I would really appreciate some directions from a more experienced rust user, as I'm kind of new to rust. Could you please help me?

EDIT: I have got rid of the unnecessary PhantomData in the NestedDict example

2

I only managed for 'static key and value types without using #![feature(generic_associated_types)]. (playground)

And here’s a version with use of this unstable feature. (playground)

3

Great solution :slight_smile: Thank you! I understand it instantly, as I was by the time trying myself to dive into the generic_associated_types and to solve this problem. I was almost finishing but you were faster than me and in addition, you've come up with one last trick that I could not figure out: the where clauses after the associated type bindings (without which I could not get rid of 'static lifetimes).

Github is somehow broken now so I cannot create gists (and therefore nor any playground links). But I will share my final solution after it has been fixed, a solution, which has also VacantEntry traits and finished insert methods.

Anyway. This is quite a motivating example for GATs. Nested dictionaries will be able to implement the Dictionary trait (with tuple keys). And therefore we will have such trait for any level of nesting and for any type of dictionary (HashMap, BTree, Association List, ...) at each level.

4

This is the code I was talking about (however I didn't implement Dictionary for NestedDict): Rust Playground

5

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.