IterMut lifetime error

Hello. For practice, i am trying to implement a linked list as a series of pointers into a common pool of memory, implemented as a slotmap::Slotmap. However, i'm encountering some lifetime errors when trying to construct a mutable iterator.

I'd appreciate some guidance on implementing a mutable iterator -- even if that means taking a different approach in general.

I have pasted the code and compiler error here https://pastebin.com/vMiu3sAJ.

For what it's worth, my Iter (shared borrow) iterator works fine with the same code minus the muts.

Thank you.

The problem you're facing here is that Slotmap’s get_mut method only allows access to one entry at a time, whereas a IterMut<'_, T>: Iterator<Item = &mut T> implementation provides mutable access to all items concurrently. I.e. you could .collect() all these items in a Vec and access them in any order, or even at the same time.

The API of Slotmap also offers a get_disjoint_mut method to lift some of this restriction; this method allows mutable access to multiple (different) values at the same time, but it, too, still only allows you to access a fixed number of elements (as determined by the const parameter N). Finally, there's also Slotmap's IterMut method/type, the only way the API offers mutable access to all elements at once, but that iterator gives the items in an arbitrary order, so it's not all that useful, unless you want to allocate large helper structures, e.g. a HashMap, to collect all those into.


Overall, doubly linked lists are hard to implement in safe Rust code, especially once you want all the convenience features such as fully-fledged mutable iterators.

One alternative that you could implement, instead of a full mutable iterator, is something that allows access to one element at a time, such as a .for_each_mut(&mut self, f: F) where F: FnMut(&mut T) method, or an iterator-like handle that only offers a next(&'a mut self) -> Option<&'a mut T> method instead of the next(&'b mut self) -> Option<&'a mut T> method that (i.e. limit the lifetime of the &mut T references to the duration of the &mut self borrow of the next method).

3 Likes

Thank you for your reply. I see now the problem. However, i am confused why some collections seem to allow this (such as std::slice), and here it seems impossible.

(If it is not obvious, I am extremely inexperienced with unsafe)

If i were to implement my own slotmap (say copypaste the source code into my own mod), would i be able to add a method that could be used to produce coexisting mutable references to each item in the backing storage? In other words, is this a feature that could exist, or is there some fundamental reason why it is impossible in this case?

Slice iterators aren't implemented in terms of get_mut(). The problem is that two subsequent invocations of get_mut() can't be statically proven not to yield a reference to the same element. For slices, it is trivial to write code that can be statically proven not to do that based on pattern matching:

struct MySliceIterMut<'a, T>(&'a mut [T]);

impl<'a, T> Iterator for MySliceIterMut<'a, T> {
    type Item = &'a mut T;
    
    fn next(&mut self) -> Option<Self::Item> {
        match mem::replace(&mut self.0, &mut []) {
            [] => None,
            [first, rest @ ..] => {
                self.0 = rest;
                Some(first)
            }
        }
    }
}

If you wanted to implement it using get_mut(), it wouldn't work:

impl<'a, T> Iterator for MySliceIterMut<'a, T> {
    type Item = &'a mut T;
    
    fn next(&mut self) -> Option<Self::Item> {
        let &mut MySliceIterMut(ref mut slice, index) = self;
        slice.get_mut(index)
    }
}

error[E0495]: cannot infer an appropriate lifetime for pattern due to conflicting requirements
  --> src/lib.rs:9:33
   |
9  |         let &mut MySliceIterMut(ref mut slice, index) = self;
   |                                 ^^^^^^^^^^^^^
   |
note: first, the lifetime cannot outlive the anonymous lifetime defined here...
  --> src/lib.rs:8:13
   |
8  |     fn next(&mut self) -> Option<Self::Item> {
   |             ^^^^^^^^^
note: ...so that reference does not outlive borrowed content
  --> src/lib.rs:9:33
   |
9  |         let &mut MySliceIterMut(ref mut slice, index) = self;
   |                                 ^^^^^^^^^^^^^
note: but, the lifetime must be valid for the lifetime `'a` as defined here...
  --> src/lib.rs:5:6
   |
5  | impl<'a, T> Iterator for MySliceIterMut<'a, T> {
   |      ^^
note: ...so that the types are compatible
  --> src/lib.rs:8:46
   |
8  |       fn next(&mut self) -> Option<Self::Item> {
   |  ______________________________________________^
9  | |         let &mut MySliceIterMut(ref mut slice, index) = self;
10 | |         slice.get_mut(index)
11 | |     }
   | |_____^
   = note: expected `<MySliceIterMut<'a, T> as Iterator>`
              found `<MySliceIterMut<'_, T> as Iterator>`

For more information about this error, try `rustc --explain E0495`.
1 Like

So you say that the compiler is implemented such that it can be sure that two items in a pattern are disjoint, and thus producing two mutable borrows from it is a valid operation? And that get_mut will never work, because the compiler cannot be assured that two calls to get_mut will not produce aliasing mutable references?

Mutable iterators typically involves “splitting borrows”, and in some cases this works in safe code with compiler support (e.g. for fields of a struct, or for splitting up slices), while other less trivial cases might require some approach involving unsafe code.

Intuitively speaking, the hard part here is that the fact that no item would be visited twice during iteration exclusively relies on the fact that you happen keep the nodes connected in a linear fashion. And you must never produce multiple &mut T references to the same item. Relying on such invariants to ensure (memory-)safety would often be done using unsafe code. Working with safe code would instead need to rely on some preexisting abstractions (which often use unsafe code internally, too) to make sure every item is only borrowed mutably once at a time; e.g. some dynamic checks would work, too (which requires additional fields or an entire additional data structures to track which items you have or haven't accessed).

1 Like

I see. So built-in compiler support for struct fields and slices will get you a long way in many cases. In my case, since SlotMap's fields are private, it would seem that I don't have the "permissions" to use unsafe to expose a mutable iterator over its contents, even if i could uphold certain invariants that assured it was sound (ie no cycles in the list).

If I did have access to SlotMap's guts, could i use some unsafe pointer magic to produce disjoint borrows to its contents? Such as (I am guessing here) converting the Vec<Slot<T>> to a pointer, adding an offset, and then converting it back to a &mut T, and returning it?

One approach of using unsafe here without needing to know anything about SlotMap's internal representation (but this does rely on the fact that SlotMaps work correctly / as documented, in the first place) is to wrap the item itself in an UnsafeCell

#[derive(Debug, Clone)]
struct Node<T, K> {
    next: Option<K>,
    prev: Option<K>,
    val: UnsafeCell<T>,
}

This way, you can interact with the SlotMap via .get() instead of .get_mut(), and then (unsafely, but soundly) turn the &UnsafeCell<T> back into a &mut T.

This change would also introduce the need for unsafe code to go from &UnsafeCell<T> to &T; a reasonable approach to make this more workable might thus be to introduce a struct MyUnsafeCell<T>(UnsafeCell<T>); helper type that offers a safe fn get(&self) -> &T as well as an unsafe fn shared_get_mut(&self) -> &mut T (and a safe fn get_mut(&mut self) -> &mut T, too, for good measure).

1 Like

Well, it's not like the compiler specifically checks for Iterator::Item. There is no magic involved, as far as I know. If you…

  • desugar the signatures by writing out all involved lifetimes and constraints explicitly,
  • remember that mutable references are invariant in their lifetime and not Copyable, and
  • read the corresponding error messages,

then you can see exactly what's going on:

struct MySliceIterMut<'a, T>(&'a mut [T]);

impl<'long, T> Iterator for MySliceIterMut<'long, T> {
    type Item = &'long mut T;
    
    fn next<'short>(&'short mut self) -> Option<&'long mut T> where 'long: 'short {
        let &mut MySliceIterMut(ref mut slice, index) = self;
        self.1 = index + 1;
        // this borrows from behind a &'short mut Self, so it _must_ be a
        // &'short mut T, so as not to create a dangling reference.
        // The only thing you can do with this reference is to reborrow it,
        // because it's not `Copy`, but that doesn't help.
        // Incidentally, this is why this works with an immutable reference:
        // the &'long T is simply copied out of the &'short mut &'long T,
        // lifting the restriction that their lifetimes must match.
        slice.get_mut(index)
    }
}

If you look at the comment as to why the analogous code works over immutable references, you can kind of see why it also works with mem::replace() over mutable references. When you use mem::replace() in the slice-based implementation, you are moving out of *&mut self, which once again obviates the need for a reborrow, and so the 'long lifetime of the returned reference doesn't have to match the implicit 'short lifetime of self.

And by the way, yes, two subsequent elements of an array/slice are known not to alias (they have different, non-overlapping memory regions because that's basically part of the definition of arrays/slices). During the time before slice patterns, one would have used <[_]>::split_at_mut() for performing the borrow split, which was itself implemented using unsafe and pointer arithmetic.

1 Like

No, it really doesn't depend on whether the fields are private. If you know (i.e., the API guarantees) that an iterator over the keys will reliably visit every corresponding value exactly once, then you technically can use unsafe and raw pointers to circumvent the lifetimes soundly. However, I wouldn't recommend doing that because it's very easy to get it wrong.

1 Like

[edit]: this is meant to be a reply to steffahn's post. my apologies, i am new to this platform.

That does indeed compile... So using UnsafeCell, I am choosing to opt out of certain optimizations, but relaxing the assumption that the data inside the Cell will not be mutated; maybe this leads to a performance decrease in the case of shared-borrows. This approach allows me to use an UnsafeCell to obtain a raw mutable pointer to the data inside it, which I can (responsibly, carefully) turn into a mut ref which satisfies the lifetime requirements.

Is my understanding correct?

I will follow your recommendation and not use unsafe and raw pointers. But if I did, would it look like this?

impl<'a, T, K: Key> Iterator for IterMut<'a, T, K> {
    type Item = &'a mut T;
    fn next(&mut self) -> Option<Self::Item> {
        let key = self.head?;
        let node = self.list.nodes.get_mut(key)?;
        self.head = node.next;
        let out = unsafe { &mut *std::ptr::addr_of_mut!(node.val) }; // <- this line
        Some(out)
    }
}

Yes, I think that would work. (Although I'm not a frequent unsafe user myself, so it would be worth getting some feedback from others as well – there can be quite a few hidden surprises when trying to creatively defeat borrowck.)

1 Like

I understand. Thank you for your invaluable feedback @H2CO3 and @steffahn. This has been a great learning experience for me.

This kind of approach might be problematic, since you are using the get_mut method of SlotMap which has mutable access to all of the entries, existing the Nodes that you already handed out mutable references for. Or put differently, with the "stacked borrows" interpretation of Rust semantics (depending on how SlotMap is implemented), the &mut T item might be a borrow derived from the original &mut LinkedList<T, K> in the abstract machine, and hence using the original &mut LinkedList<T, K> again to create a new &mut T might invalidate the previous &mut Ts already created.

This kind of stuff is often quite subtle; and sometimes even depends on parts of the Rust semantic that might not be 100% decided yet, so it’s often advisable to avoid risking anything: This kind of problem does not appear if you use UnsafeCell instead as I suggested above. You'd create an immutable reference &'a LinkedList<T, K> from the &mut self borrow once at the start of iteration, and work with immutable references exclusively then, apart from the final step of &MyUnsafeCell<T> to &mut T conversion for the items. So no exclusive access is ever asserted anywhere, you interact with the SlotMap via SlotMap::get instead of get_mut, etc..

2 Likes

Here, I made an example implementation myself: Rust Explorer

2 Likes