Entry API - Githubissues

dewert99 commented 2 years ago

I added a trait for maps that support the entry api, and made a few other changes (see changelog and documentation for details) that I thought would be useful.

dewert99 commented 2 years ago

@timothee-haudebourg I'm just checking that you noticed my questions/comments above.

timothee-haudebourg commented 2 years ago

I took a closer look at the traits defined in the entry_api module and I have a few other remarks:

You are using direct references throughout the Entry API, whereas in the rest of the crate I have been careful to not make any assumption about how the keys/values are referenced to (using the KeyRef/ItemRef types). I think it would be better to apply this to the Entry API as well.
You choose to define K and V as associated values in OccupiedEntry and VacantEntry, which forces you to add equality bounds in the EntryApi trait. Is there a reason why you did not directly defined it like this:
```
trait EntryApi: CollectionRef + KeyedRef {
type Occ<'a>: OccupiedEntry<'a, Self>;
type Vac<'a>: VacantEntry<'a, Self>;
}
```

trait OccupiedEntry<'a, C: CollectionRef + KeyedRef> { fn key(&self) -> C::KeyRef<'a>; fn value(&self) -> C::ItemRef<'a>;

... }

trait VacantEntry<'a, C: Keyed> { fn key(&self) -> &C::Key; }


- By the way, what is the reason you choose to separate `VacantEntry` and `KeyVacantEntry`?
- I'm not a fan of abbreviations for type names, unless it is already in the language or standard library (`ref`, `mut`, `len`, etc.), or a type parameter. For the `Occ` and `Vac` associated types for instance, I would prefer `Occupied` and `Vacant` (or even `OccupiedEntry`/`VacantEntry`).

dewert99 commented 2 years ago

Thanks for your feedback these are good ideas. I separated out the KeyVacantEntry trait so that the EntryRefApi could only require a VacantEntry (eg. when calling HashMap<String, _>::entry_ref on a &str there would be no good way to implement KeyVacantEntry::key returning a &String

dewert99 commented 2 years ago

While working on switching the (Occupied|Vacant)Entry methods to use KeyRef, ItemRef ..., I ran across some problems. When I tried the way you suggested:

trait EntryApi: CollectionRef + KeyedRef {
  type Occ<'a>: OccupiedEntry<'a, Self>;
  type Vac<'a>: VacantEntry<'a, Self>;
}

trait OccupiedEntry<'a, C: CollectionRef + KeyedRef> {
  fn key(&self) -> C::KeyRef<'_>;
  fn value(&self) -> C::ItemRef<'_>;

  ...
}

(I think '_ is the correct lifetime since eg. hash_map::OccupiedEntry::key returns a &K not a & 'a K

I ran into E0207 for

impl<'a, Occ, Vac, C: CollectionMut+KeyedRef> Entry<Occ, Vac>
where
    Occ: OccupiedEntry<'a, C>,
    Vac: VacantEntry<'a, C>,
...

One way I tried to work around this was to keep track of the owner collection in an associated type instead of a generic parameter:

pub trait EntryApi: CollectionMut + CollectionRef + KeyedRef {
    type Occupied<'a>: OccupiedEntry<'a, Owner = Self>;
    type Vacant<'a>: KeyVacantEntry<'a, Owner = Self>;
    fn entry(&mut self, key: Self::Key) -> Entry<Self::Occupied, Self::Vacant>;
}

pub trait OccupiedEntry<'a>: Sized {
    type Owner: KeyedRef + CollectionMut + CollectionRef + 'a;
    fn key(&self) -> <Self::Owner as KeyedRef>::KeyRef<'_>;
    fn get(&self) -> <Self::Owner as CollectionRef>::ItemRef<'_>;
...
}

This works fairly well, but I was (read: will be when I make a separate pull request) forced to make HashMap<K,V,S>::Occupied be a wrapper type with PhantomData<S> instead of just being hashmap::OccupiedEntry<K, V> so that it could implement its Owner as dependent on HashMap<K,V,S> (E0207 again). You can find my progress in this direction at https://github.com/dewert99/cc-traits/tree/associated_type_owner.

I also tried keeping multiple individual associated types (Item, Key, ItemRef ...) and requiring them all to be the same:

pub trait EntryApi: KeyedRef + CollectionRef + CollectionMut {
    type Occupied<'a>: OccupiedEntry<
        'a,
        Key = Self::Key,
        Item = Self::Item,
        KeyRef<'a> = Self::KeyRef<'a>,
        ItemRef<'a> = Self::ItemRef<'a>,
        ItemMut<'a> = Self::ItemMut<'a>,
    > where
        Self: 'a;
...

unfortunately this only requires these types to match when using the 'a lifetime but not the '_ elided one. When I tried

pub trait EntryApi: KeyedRef + CollectionRef + CollectionMut {
    type Occupied<'a>: for<'x> OccupiedEntry<
        'a,
        Key = Self::Key,
        Item = Self::Item,
        KeyRef<'x> = Self::KeyRef<'x>,
        ItemRef<'x> = Self::ItemRef<'x>,
        ItemMut<'x> = Self::ItemMut<'x>,
    > where
        Self: 'a;
...

I got lifetime errors when trying to implement EntryApi and in the end I was only able to switch types with 'a references to there respective associated types. You can find my progress in this direction at https://github.com/dewert99/cc-traits/tree/multi_associated_types.

Do you have any preference in what I end up doing?

timothee-haudebourg commented 2 years ago

Thanks for persevering :smile:

I ran into E0207

Yes because C is not constrained by the Entry type. I think having Occ and Vac as parameters of Entry is not the best idea. You can just use C like this:

pub enum Entry<'a, C: 'a + ?Sized + EntryApi> {
    Vacant(C::Vacant<'a>),
    Occupied(C::Occupied<'a>)
}

dewert99 commented 2 years ago

Thanks for your idea. I had to adapt it slightly to so that EntryRefApi::entry_ref could return an Entry enum with different variants. I ended up with

pub trait EntryTypes<T>: CollectionMut + CollectionRef + KeyedRef {
    type Occupied: OccupiedEntry<'a, Self>;
    type Vacant: VacantEntry<'a, Self, T>;
}

pub struct EntryFlag;

pub trait EntryApi: EntryTypes<EntryFlag> {
    fn entry(&mut self, key: Self::Key) -> Entry<'_, Self, EntryFlag>;
}

pub enum Entry<'a, C: EntryTypes<T> + 'a + ?Sized, T: 'a = EntryFlag> {
    Occupied(<C as EntryTypes<T>>::Occupied),
    Vacant(<C as EntryTypes<T>>::Vacant),
}

which allowed me to add

pub struct EntryRefFlag<Q: ?Sized>(_);

pub trait EntryRefApi<Q: ?Sized>: EntryTypes<EntryRefFlag<Q>> 
where
    Self::Key: Borrow<Q>, 
{
    fn entry_ref<'a>(
        &'a mut self, 
        key: &'a Q
    ) -> Entry<'a, Self, EntryRefFlag<Q>>
    where
        Q: 'a;
}

for EntryRefApi.

Also since I couldn't make EntryTypes::Vacant<T> require KeyVacantEntry only where T = EntryFlag I made T a parameter of the VacantEntry trait and re-added the KeyVacantEntry methods to it, each with the constraint T: SupportsKeyVacantEntry, as trait only implemented by EntryFlag. You can find my progress in this direction at https://github.com/dewert99/cc-traits/tree/generic_owner. Let me know what you think.

dewert99 commented 2 years ago

Just checking if you noticed my last comment?

timothee-haudebourg / cc-traits

Entry API #3