Would adding a function to std (on slices or arrays) that transforms a &mut of the whole to individual &mut of the parts?
I think it would require const generics because it probably has to return an owned array.
This should help with the problem of not being able to mutably borrow two different elements from an array since you can non-mutably borrow this result (but I believe it is still safe to do so because there is a mutable borrow tracking the lifetime of the second type).
Would you mind elaborating on the type signatures you have in mind? And/or some code how you imagine it being used? I’m having a hard time figuring out what you might be proposing here.
Edit: Ah, you mean something like
&mut [T; N] -> [&mut T; N]? I don’t see how this could work for slices, but for arrays it seems viable.
Edit2: Actually, the question remains of how to use such a function. You can’t exactly move out the individual &mut T entries, or access more than one of them through indexing operations. Destructuring is possible, i.e. you can assign it like let [a,b,c,d] = foo.as_mut_refs(). But that works without the extra step as well, e.g.
fn main() {
let mut x: [Box<i32>; 6] = [1.into(), 2.into(), 3.into(), 4.into(), 5.into(), 6.into()];
let y = &mut x;
let [a, b, c, ..] = y;
**a += 10;
std::mem::swap(b, c);
dbg!(&x);
}
Yes I mean &mut [T; N] -> &[&mut T; N]. And I figured that since only non-exclusive borrowing is required to get one of these references you could get more than one at the same time.
The main reason for wanting references instead of destruction is that after the borrow is finished the original is still intact.
Well, for example here is an (inefficient but correct) implementation. I’d like to see use-cases of this.
I doubt that it’s giving much or any advantage over dealing with the &mut [T; N] directly, but who knows... maybe I’m missing something.
Well, yes, you can get &&mut T, but you can't use it as &mut T, only &T, because it's shared.
Match binding modes makes this the case!
[playground] (just the above again, slightly rewritten)
fn main() {
let mut x: [Box<i32>; 6] = [1.into(), 2.into(), 3.into(), 4.into(), 5.into(), 6.into()];
let [a, b, c, ..] = &mut x;
**a += 10;
std::mem::swap(b, c);
dbg!(&x);
}
Note that x is used here at the end. a, b, c are &mut Box<i32> into the array slots.
With explicit binding modes, it's let &mut [ref mut a, ref mut b, ref mut c, ..] = &mut x;.
Thanks for the detailed explanation. I had forgotten that you cannot assign through & even if the other thing is a &mut. However with deconstructing it isn't possible to easily get arbitrary locations within that pattern.
So a better signature (one that I think could actually work) is the following:
/// Returns an array of mutable borrows to the `src` slice in the same order as given
/// safety:
/// 1. must have no duplicates in the `indices` array
/// 2. all indices must be within bounds of `src`
unsafe fn as_mut_refs_unchecked<'a, T, const N: usize>(src: &'a mut [T], indices: [usize; N]) -> [&'a mut T; N] { ... }
and the following safe version that does the checks as well
/// Returns an array of mutable borrows to the `src` slice in the same order as given
fn as_mut_refs<'a, T, const N: usize>(src: &'a mut [T], indices: [usize; N]) -> [&'a mut T; N] { ... }
These two functions could be used as the following:
// param has: src: &mut Vec<T>
let [ x1, x2, x3 ] = src.as_mut_refs([index_1, index_2, index_3]);
That would be difficult to implement safely and efficiently, because the function has to ensure that no index is given twice. Otherwise there would be multiple mutable references to the same element.
It might be better to just slice it with a range. If necessary, you can call split_at_mut to get multiple slices. For example:
// get reference to 20th and 40th element:
let (s1, s2) = slice.split_at_mut(40);
let ref1 = &mut s1[20];
let ref2 = &mut s2[0];
The you have to do the arithmetic yourself on the offsets which I would say puts more burden on the user. And the non-unchecked version could use a HashSet to track duplicates or something.
Because it is difficult leads me to think that such a method should be part of std.
The problem is that, from the method signature, it is not at all obvious that it allocates a HashMap, and therefore doesn't work with no_std. Also, the performance would we less than ideal if you already know that the indices are unique. Therefore I'd prefer if it isn't part of the standard library.
Well if you already know that the indices are unique and in range then you have satisfied the conditions for the _unchecked version.
I suggested a HashSet (which probably could be conditionally used) because it make the implementation simpler since the other option would be to sort a copy of the input and check for duplicates that way.
I would definitely like to see a general safe API for this on all the collections.
This can be worked around for a simple thing like a slice, but particularly feels like it ought to be a provided thing for associative containers -- I know that right now the implementations don't move things around in get_mut so I can probably get away with using unsafe to get two &muts, but there's no guarantee of that, so I arguably shouldn't be depending on it for soundness. There's nothing that prohibits get_mut from doing splay-tree like movement that would make it completely unsound.
(Things get really interesting in generic code, since one can't trust Eq or Ord, so just looking at the keys you're going to use is insufficient for soundness.)
I'm not worried about perf for it. I think the 90% case is probably 2 or 3 items, where the naïve O(n²) overlap checking is completely fine.
I am a bit hazy on the unsafe guidelines but I think it would be safe to check for duplicates of the *mut T's before turning them into &'a mut T's instead of duplicate checking the keys, right? That way a theoretical container of slices that accepts -1 as an "index" to the last element could still be valid.
So a trait might be able to be defined like so:
trait GetMutRefs<Key, Value> {
fn get_mut_refs<'a, const N: usize>(&'a mut self, keys: [Key; N]) -> Option<[&'a mut Value; N]>;
}
And as long as it is possible to get a *mut Value from a Key (checking for existence) and then validate that none of the pointers equal (checking for duplication) it should be able to provide the declared safe interface.
Not for ZSTs. (Though admittedly I can't think of a case where one could actually do anything weird by violating these requirements, since &mut Zst is mostly useless, but it's probably still not technically allowed to violate the "&mut is exclusive" rule even for ZSTs.)
TBH my proposed solution would just always return None from the above if N > 1 for ZSTs.
However, that seems to imply a usefulness (outside of not doing the dup-check) of a second function that does bounds checking but no duplicate checking:
trait GetMutRefs<Key, Value> {
fn get_mut_refs<'a, const N: usize>(&'a mut self, keys: [Key; N]) -> Option<[&'a mut Value; N]>;
/// safety: every entry in `keys` must be logically exclusive. Namely, point to a different element of `Self`
/// this function does bounds checking but not duplicate checking, if the above does not hold then UB
/// will happen due to multiple `&'a mut Value`'s existing for a single entry.
unsafe fn get_mut_refs_unchecked<'a, const N: usize>(&'a mut self, keys: [Key; N]) -> Option<[&'a mut Value; N]>;
}
No, it's fine, surprisingly enough, IIUC. If you squint at it hard enough, two zero byte ranges can't overlap due to vacuous truth and not sharing a byte.
An example of the compiler emitting two identical &mut isn't quite a proof, since the compiler has special info, but here is one:
fn main() {
let x = &mut ();
let y = &mut ();
println!("{:p}", x);
println!("{:p}", y);
}
More relevantly, we allow you to deference any nonnull pointer if it's a pointer to ZST. (Logically, there's a ZST at every address.) We also (iirc) allow you to reborrow ZST pointers freely. Pointers only have provenance over memory, and ZST references don't own any memory, thus vacuously have all possible provenance over no memory.
Something something Stacked Borrows only cares about how you treat bytes in memory (reborrow counts as a use), and ZSTs don't touch any bytes.
Super informal argument but I'm fairly sure this was formally agreed upon at some point.
But I don't know which direction you were arguing tbh after rereading; the only way ZSTs fail the "unique pointer" test is if they have the same pointer...
UCG: Shared and Unique slices and ZST
UCG: What's the definition of mutable aliasing for ZSTs?
I'm no expert but the TL;DR seems to be: there is no aliasing for ZSTs, but the number of / provenance of &mut Zst must be preserved.
It's definitely valid.
There's still a question of whether it's safe, though. For example, imagine I make an API that gives out only one ZST Token to the world, and that token isn't Copy or Clone. Then if I make APIs that take &mut Token, I know that I can't be called multiple times at the same time. But that would be violated if I could do [token].get_mut_multiple([0, 0]).
(That issue above was actually opened while I was trying to make exactly this kind of API by checking pointer equality 
)
If you take the address of the same ZST two times, I think it's guaranteed to get the same address both times? In which case checking address uniqueness as a proxy for disjoint &mut would be overly restrictive for ZST but not unsound.
(Note that you would of course need to use &raw mut or whatever the macro version of it is.)
At first I was indeed thinking of this overly restrictive version. But then I remembered that this could all be implemented in terms of (*mut T, usize) since every collection can be represented in terms of that tuple.