Missing APIs

[udoprog]

I'm gathering a list of missing APIs here instead of having them in multiple separate issues.

• FromIterator, IntoIterator (impl more standard traits #9) (added in impl more standard traits #9).
• Map::contains_key / Set::contains (Useful APIs from HashMap / BTreeMap #10) (added in impl Map::contains_key #22).
• Map::is_empty / Set::is_empty (Useful APIs from HashMap / BTreeMap #10).
• Map::len / Set::len (Useful APIs from HashMap / BTreeMap #10).
• Map::retain / Set::retain (Useful APIs from HashMap / BTreeMap #10) (added in impl Map::retain and Set::retain #27).
• Entry api (Entry api #5) (added in Entry API #31).

Thanks to @msdrigg and @pitaj for the requests!

If you see something you'd like to implement, set up a PR and poke this issue (relates #11).

[pitaj]

Consider converting this to a checklist. FromIterator and IntoIterator are implemented.

[udoprog]

Heads up @pitaj I'm currently putting work into Entry support. If you want to try it instead, please poke me!

[udoprog]

After poking at the problem a bit: Entry support will be quite hard and might have to involve some level of unsafe 🤔

If you want to understand the problem, try to implement an Entry API for OptionStorage: Since the two storages are divergent (one is generically K::Storage<V> and the other one is Option<V>) handling the Entry API safely requires a lot of variant testing back and forth. You need to return a single vacant / occupied type and you need to test if the entry is present before returning it:

impl OptionStorage<K, V> {
    #[inline]
    fn entry(&mut self, key: Option<K>) -> Entry<'_, ?, ?> {
        match key {
            Some(key) => {
                // somehow this needs to return the same type as the other branch.
                self.some.entry(key)
            }
            None => {
                if self.none.is_some() {
                    // none occupied
                } else {
                    // none vacant
                }
            }
        }
    }
}

[pitaj]

Yeah the entry API may be quite difficult to implement. Might require more than one Occupied variant for Option and bool:

enum Entry<...> {
    Vacant { ... },
    OccupiedNone { ... },
    OccupiedSome { ... },
}

[udoprog]

FWIW: I've now paused efforts to implement an Entry api. If anyone else wants to take a stab at it please give it a go!

I do have to say I'm a bit pessimistic of how cleanly it can be implemented with safe code. In particular the Entry api with regular maps rely on a single enum that you can match over in case you need to perform advanced entry-oriented operations:

enum Entry<'a, K: 'a, V: 'a> {
    Occupied(OccupiedEntry<'a, K, V>),
    Vacant(VacantEntry<'a, K, V>),
}

This has proven to be exceedingly hard to model due to the issues outlined above. An opaque entry-like API would work, but that would remove the ability to perform advanced entry-like operations by pattern matching over the enum.

Feel free to keep experimenting though!

[pitaj]

Some thoughts:

First of all, it's obvious that our entry API surface will not be identical to that in std, if only because we have Copy keys, which makes various APIs there redundant (like key vs into_key).

Exposing variants

It looks to me like using a single Occupied variant, at least for OptionStorage, won't be possible. Because we need to be able to specialize the behavior based on whether the occupied value is in None or Some (another storage).

That implies that exposing the variants in the API won't be possible, because they wouldn't match between the different storage types.

API design

Therefore, it seems to me that we shouldn't bother matching the API of standard, and should try to construct something that best matches our uses. This is going to require some experimentation.

Unsafe

I'm going to try implementing an opaque API without unsafe and see how far I get. My intuition is that it will be very difficult to make it optimal without unsafe.

Take OptionStorage for instance, where implementing the OccupiedEntryNone (variant for the occupied None entry) operations requires having mutable access to the self.none Option and the value within that Option. That means we either need unwraps all over, or we have to use pointers.

[udoprog]

Go for it!

I'd also note that if unsafe use leads to a cleaner API which more closely matches std collections it is worth it.

[pitaj]

Alright I think I have a promising start. Check it out here

option_unsafe uses OptionBucket which is implemented with some unsafe.

option_safe is implemented without unsafe, but is opaque, so doesn't have Occupied and Vacant variants. It also may not be as optimal as the other one, but I think it would be very close.

Remarks:

It looks like exposing Occupied and Vacant variants will be possible after all, by having another enum level within each when necessary.

As for unsafe, I think the only use of unsafe will be to implement OptionBucket. We could quite easily move this into a separate crate to keep the main crate #![forbid(unsafe)].

We could also implement a totally-safe OptionBucket that people could choose (using unwrap), but it's such a simple API surface I don't think there's much value in that.

[pitaj]

Just committed a prototype implementing Map::entry: check it out

I haven't implemented the derive macro yet, so I haven't tested anything yet, but I'm pretty happy with how it turned out.

[udoprog]

Very neat @pitaj!

If you change the feature flag to instead be #[cfg(fixed_map_unfinished)] (which prevents implicit use even if part of a release since you explicitly have to RUSTFLAGS="--cfg fixed_map_unfinished" when building) we can get it reviewed and merged in even if it's very WIP. I have some notes I'd like to put in and keep track of. I think something like your bucket plumbing will be necessary to build out the derive macro support as well.

[pitaj]

Alright I have a working version now complete with derive macro support. All that's missing is some documentation. Check it out and let me know what you think.

It's available in the entry branch.