However if I add mut to &'a [T] (also respectively to &'a T and &self.shards[...]), it won't compile:
Please see this link to rust playground
How can I make the mutable version compile?
Note that this is only a minimal reproducible example of the actual code. The actual code is not doing self.next += 1 but using a different ordering which can jump back and forth (but visits each index at most once). Therefore using Slice::IterMut or things like that is not an option.
The problem is: how can the compiler know that? This is one of those things you generally prove yourself and then use unsafe to implement.
An alternative is to not use Iterator, and instead provide a fn next(&mut self) -> &mut T method that ties the lifetime of the returned reference to self. Note that this won't allow having references to multiple items at the same time.
and I instantly got the same error: error[E0495]: cannot infer an appropriate lifetime for lifetime parameter in function call due to conflicting requirements
What is it about the Option that satisfies the borrow checker? I feel like I'm missing something pretty basic.
In your snippet without the Option, you are trying to copy a mutable reference by returning it. Obviously, that's not allowed, because mutable references need to be exclusive. Option::take() moves the inner value out of the vector (by replacing the Some with None) instead of attempting to erroneously duplicate it.
Also note that Option isn’t particularly special here— Vec::remove and Vec::swap_remove will do a similar job, but will also change the indices of the remaining items.
It's not necessarily required to use raw pointers here; something like &'a [UnsafeCell<T>] should work fine, too; or perhaps even &'a [Cell<T>] using Cell::as_ptr (the latter is easier to create from a &mut [T], as there's existing safe API Cell::from_mut and as_slice_of_cells).
In some cases, it is sound to implement Send and/or Sync for your type manually even if it contains non-Send or non-Sync components, but I'm not familiar enough with Rust's thread safety to say what those cases are.
My understanding was that if you are using raw pointers you are relying on your own code logic that all the accesses are safe.
Yes, and Rust is designed to encourage you to take a moment to consider whether your pointer (or UnsafeCell) uses are safe in the presence of threads, and write an unsafe impl Send for MyType {} only if they are. The default assumption is that if a type contains * or UnsafeCell it is not thread safe.
Yes, hence they aren't Sync or Send, so that you have to think twice before manually writing unsafe impl Sync for Foo {} for your raw-pointer wrapping type. This is the same in the case of UnsafeCell, too – raw pointers are also interior mutability primitives.