What's the policy on mutable accessors (iteration, indexing)?

help
1

Looking at some parts of the standard library made me realize that parts of the API seems to be designed around certain implied rules that i haven't found clearly documented anywhere:

  • Mutable iterators should never return the same memory location twice
  • Mutable indexers should never return the same memory location for x[i] and x[j] unless i == j.

This seems to be the case since slices have windows, but not windows_mut, and Iterator has cycle with a Copy bound that also excludes any &mut T as the item type.

Those rules seem to make sense intuitively as soon as you start thinking about consuming multiple indices/iterator items in parallel (e.g. rayon), but I find it strange that no information about this topic is found on the documentation page for neither Iterator nor IndexMut, especially since this is a topic that is both non-obvious while being critically relevant to thread safety. It is my understanding that writing a mutable iterator is impossible without unsafe code, so this fact weighs even more gravely.

If my understanding of this topic is right, there should probably be two separate iterator and indexing traits each, one that either work like now, and another to allow the described aliasing with some other restrictions in place to keep it safe.

Of course, I might have misunderstood some aspects of this entire topic, so I'd be happy to hear your thoughts.

2

This follows from the rules for &mut itself. You must never have access to two &mut at once that point to the same memory. That is the fundamental rule of the language, which generally isn’t restated in specific APIs that merely use &mut, because you can’t break it in safe code (the borrow checker checks this).

This is not a requirement for implementing ops::IndexMut. It merely wouldn't be consistent with other things if you did that.

This is not actually true. You cannot write a iterator over mutable references that uses indexing to produce the references in safe code, but for some data structures, you can write an iterator that splits the borrow of the data structure. A singly-linked list is the most CS-101 example, but you can also do it using slices because the compiler knows how to split borrows using patterns:

struct MySliceIter<'a, T> { state: &'a mut [T] }

impl<'a, T> Iterator for MySliceIter<'a, T> {
    type Item = &'a mut T;
    fn next(&mut self) -> Option<Self::Item> {
        match core::mem::take(&mut self.state) {
            [item, rest @ ..] => {
                self.state = rest;
                Some(item)
            }
            [] => None,
        }
    }
}

If you want to have a windows_mut() producing &mut [T], that would indeed need a new trait — specifically, a lending iterator trait which prohibits having multiple iterator items alive at the same time (it cannot be collect()ed). There are many uses for such a trait and we might have one in the standard library someday.

If you want to not have aliasing rules and be responsible for avoiding data races yourself, you could write an iterator that returns *mut [T]s instead of &mut [T]s. No new trait is needed, but the usage is unsafe.

The language could be a little more convenient to use if there was an IndexRawMut trait with fn index_raw_mut(*mut self, index: usize) -> *mut T, but unsafe code is generally very specific to the data types it works with, so having a trait offering syntax sugar for this case would not help a lot of cases and might make the code hazardously less clear ("is this really a ptr-ptr operation or did a ref get created?").

2 Likes
3

This topic was automatically closed 90 days after the last reply. We invite you to open a new topic if you have further questions or comments.