fixed-map
fixed-map copied to clipboard
Missing APIs
I'm gathering a list of missing APIs here instead of having them in multiple separate issues.
- [x]
FromIterator
,IntoIterator
(#9) (added in #9). - [x]
Map::contains_key
/Set::contains
(#10) (added in #22). - [x]
Map::is_empty
/Set::is_empty
(#10). - [x]
Map::len
/Set::len
(#10). - [x]
Map::retain
/Set::retain
(#10) (added in #27). - [x]
Entry
api (#5) (added in #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)
.
Consider converting this to a checklist. FromIterator and IntoIterator are implemented.
Heads up @pitaj I'm currently putting work into Entry
support. If you want to try it instead, please poke me!
After poking at the problem a bit: Entry
support will be quite hard and might have to involve some level of unsafe
:thinking:
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
}
}
}
}
}
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 { ... },
}
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!
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 unwrap
s all over, or we have to use pointers.
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.
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.
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.
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.
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.