Add as_mut_ref for slice or array

libs
21

So this sounds like something that could be useful for rust's stdlib. Should I make a PR?

22

I agree it wouldn't be unsound. But it'd mean that .get_mut_multiple([0, 1]) on a slice of ZSTs would return an error, which feels incorrect.

2 Likes
23

Would checking for duplicates be sound if we used (*mut T, usize)? Namely |l, r| l.0 == r.0 && l.1 == r.1 for duplicates? That way should work even for ZSTs.

24

The only reason to check the identity of the returned reference is that you can't trust keys in a generic context (e.g. HashMap) because Eq can't be trusted for correctness. For the specific case of a slice, it's enough to check that the indices are disjoint, since usize is a trusted language type and not a generic.

1 Like
25

True but I was thinking of a generic impl sort of like the following:

pub trait GetMutRefs<Key, Value> {
    /// Gets `N` mutable references to `Value`'s within `Self` if all the
    /// `keys` are valid and wouldn't result in overlapping `&mut`'s.
    ///
    /// This is default implented in terms of `get_single_mut_ptr`.
    fn get_mut_refs<'a, const N: usize>(
        &'a mut self,
        keys: [Key; N]
    ) -> Option<[&'a mut Value; N]> { ... }

    /// If `key` is not in `self` return None, otherwise return Some tuple 
    /// of the pointer to the start of the collection of Values and an 
    /// offset number of elements within. This is needed for ZSTs.
    fn get_mut_ptr<'a>(
        &'a mut self, 
        key: Key
    ) -> Option<(NonNull<Value>, usize)>;
}
26

Ah. Unfortunately getting that usize offset could be expensive for some data structures. Probably the better solution would be to instead of (*mut T, usize), use some associated Self::RawEntry type that can check its identity against other raw entries and also retrieve the key pointer. Then e.g. a BTree can compare node identity and node index, rather than having to calculate the item index.

27

Ah that makes sense. Also TIL that associated types in traits can have bounds within the trait declaration.

So that makes the following a better basis I would imagine:

/// This trait is unsafe to implement because it is used in upholding the
/// safety guarantees of `GetMutRefs`
unsafe trait GetRefMutsRawEntry {
    type Value;

    /// should return true if both `&self` and `other` "point" to the entry
    fn eq_raw_entry(&self, other: &Self) -> bool;

    /// convert the item into a reference
    ///
    /// saftey: the resulting reference must not break any of the `&mut`
    /// rules. Namely if you have a collections of `Self`'s and mean to 
    /// call  `to_entry()` on all of them. Then all distinct pairs in that 
    /// collection must return `false` from a theoretical call to 
    /// `eq_raw_entry`
    unsafe fn to_entry<'a>(self) -> &'a mut Value;
}

trait GetRefMuts<Key, Value> {
    type RawEntry: GetRefMutsRawEntry<Value = Value>;

    /// Gets `N` mutable references to `Value`'s within `Self` if all the
    /// `keys` are valid and wouldn't result in overlapping `&mut`'s.
    ///
    /// This is default implented in terms of `get_single_mut_ptr`.
    fn get_mut_refs<'a, const N: usize>(
        &'a mut self,
        keys: [Key; N]
    ) -> Option<[&'a mut Value; N]> { ... }

    /// If `key` is not in `self` return None, otherwise return Some tuple 
    /// of the pointer to the start of the collection of Values and an 
    /// offset number of elements within. This is needed for ZSTs.
    fn get_mut_ptr<'a>(
        &'a mut self, 
        key: Key
    ) -> Option<RawEntry>;
}
28

One last thing is that reborrowing to call get_mut_ptr might end up invalidating previous raw entries. This is complicated and we'd need to see an actual impl to know for sure, I think.

But the general shape would work as far as I understand it, it's just details around handling provenance and ownership during the process, not the API we want to provide, that's under question still.

29

Would therefore a libs PR against the rust repo be the next step or an actual RFC?

30

Hard to say on this one. On one hand it's "just" a new API, for which a PR is fine, but it's also a "thing that if it's good sets a new convention that lots of things should do", where an RFC is often best. And there are some interesting design questions -- whether .get_mut_multiple((..k, k+1..)) should work too, for example -- that also makes me lean RFC.

Maybe write up a proposal (not quite an RFC, but a standalone thing with the motivation and proposed API) and post it to Zulip to see what T-libs thinks?

2 Likes
31

Sounds good thanks for the guidance. I'll start working on something in the vein of an RFC and post a link to the github rendered version to Zulip. Sound good.

32

This topic was automatically closed 90 days after the last reply. New replies are no longer allowed.