How can I create my own data structure with an iterator that returns mutable references?

by

You can’t compile this because mutable references are more restrictive than immutable references. A shortened version that illustrates the issue is this:

struct MutIntRef<'a> {
    r: &'a mut i32
}

impl<'a> MutIntRef<'a> {
    fn mut_get(&mut self) -> &'a mut i32 {
        &mut *self.r
    }
}

fn main() {
    let mut i = 42;
    let mut mir = MutIntRef { r: &mut i };
    let p = mir.mut_get();
    let q = mir.mut_get();
    println!("{}, {}", p, q);
}

Which produces the same error:

error[E0495]: cannot infer an appropriate lifetime for borrow expression due to conflicting requirements
 --> src/main.rs:7:9
  |
7 |         &mut *self.r
  |         ^^^^^^^^^^^^
  |
note: first, the lifetime cannot outlive the anonymous lifetime #1 defined on the method body at 6:5...
 --> src/main.rs:6:5
  |
6 | /     fn mut_get(&mut self) -> &'a mut i32 {
7 | |         &mut *self.r
8 | |     }
  | |_____^
note: ...so that reference does not outlive borrowed content
 --> src/main.rs:7:9
  |
7 |         &mut *self.r
  |         ^^^^^^^^^^^^
note: but, the lifetime must be valid for the lifetime 'a as defined on the impl at 5:6...
 --> src/main.rs:5:6
  |
5 | impl<'a> MutIntRef<'a> {
  |      ^^
note: ...so that reference does not outlive borrowed content
 --> src/main.rs:7:9
  |
7 |         &mut *self.r
  |         ^^^^^^^^^^^^

If we take a look at the main function, we get two mutable references called p and q that both alias the memory location of i. This is not allowed. In Rust, we can’t have two mutable references that alias and are both usable. The motivation for this restriction is the observation that mutation and aliasing don’t play well together with respect to memory safety. So, it’s good that the compiler rejected the code. If something like this compiled, it would be easy to get all kinds of memory corruption errors.

The way Rust avoids this kind of danger is by keeping at most one mutable reference usable. So, if you want to create mutable reference to X based on a mutable reference to Y where X is owned by Y, we better make sure that as long as the reference to X exists, we can’t touch the other reference to Y anymore. In Rust this is achieved through lifetimes and borrowing. The compiler considers the original reference to be borrowed in such a case and this has an effect on the lifetime parameter of the resulting reference as well. If we change

fn mut_get(&mut self) -> &'a mut i32 {
    &mut *self.r
}

to

fn mut_get(&mut self) -> &mut i32 { // <-- no 'a anymore
    &mut *self.r // Ok!
}

the compiler stops complaining about this get_mut function. It now returns a reference with a lifetime parameter that matches &self and not 'a anymore. This makes mut_get a function with which you “borrow” self. And that’s why the compiler complains about a different location:

error[E0499]: cannot borrow `mir` as mutable more than once at a time
  --> src/main.rs:15:13
   |
14 |     let p = mir.mut_get();
   |             --- first mutable borrow occurs here
15 |     let q = mir.mut_get();
   |             ^^^ second mutable borrow occurs here
16 |     println!("{}, {}", p, q);
   |                        - first borrow later used here

Apparently, the compiler really did consider mir to be borrowed. This is good. This means that now there is only one way of reaching the memory location of i: p.

Now you may wonder: How did the standard library authors manage to write the mutable vector iterator? The answer is simple: They used unsafe code. There is no other way. The Rust compiler simply does not know that whenever you ask a mutable vector iterator for the next element, that you get a different reference every time and never the same reference twice. Of course, we know that such an iterator won’t give you the same reference twice and that makes it safe to offer this kind of interface you are used to. We don’t need to “freeze” such an iterator. If the references an iterator returns don’t overlap, it’s safe to not have to borrow the iterator for accessing an element. Internally, this is done using unsafe code (turning raw pointers into references).

The easy solution for your problem might be to rely on MutItems. This is already a library-provided mutable iterator over a vector. So, you might get away with just using that instead of your own custom type, or you could wrap it inside your custom iterator type. In case you can’t do that for some reason, you would have to write your own unsafe code. And if you do so, make sure that

  • You don’t create multiple mutable references that alias. If you did, this would violate the Rust rules and invoke undefined behavior.
  • You don’t forget to use the PhantomData type to tell the compiler that your iterator is a reference-like type where replacing the lifetime with a longer one is not allowed and could otherwise create a dangling iterator.

More Related Contents:

  1. Why can’t I store a value and a reference to that value in the same struct?
  2. What are non-lexical lifetimes?
  3. The compiler suggests I add a ‘static lifetime because the parameter type may not live long enough, but I don’t think that’s what I want
  4. Lifetime error when creating a function that returns a value implementing serde::Deserialize
  5. Why does linking lifetimes matter only with mutable references?
  6. Why is adding a lifetime to a trait with the plus operator (Iterator + ‘a) needed?
  7. Cannot infer an appropriate lifetime for autoref due to conflicting requirements
  8. When is it useful to define multiple lifetimes in a struct?
  9. Lifetime troubles sharing references between threads
  10. Moved variable still borrowing after calling `drop`?
  11. What is lifetime elision in very simple terms?
  12. “borrowed value does not live long enough” when using the builder pattern
  13. How can this instance seemingly outlive its own parameter lifetime?
  14. How do I specify lifetime parameters in an associated type?
  15. How to operate on 2 mutable slices of a Rust array?
  16. When returning the outcome of consuming a StdinLock, why was the borrow to stdin retained?
  17. Why does my variable not live long enough?
  18. Why is the bound `T: ‘a` required in order to store a reference `&’a T`?
  19. Sharing a struct with trait objects as properties across threads
  20. Why can’t I return an &str value generated from a String?
  21. Type mismatches resolving a closure that takes arguments by reference
  22. How to fix lifetime error when function returns a serde Deserialize type?
  23. Why does Rust disallow mutable aliasing?
  24. Extend lifetime of variable
  25. Why does the Rust compiler request I constrain a generic type parameter’s lifetime (error E0309)?
  26. Traits and Rust
  27. Why do try!() and ? not compile when used in a function that doesn’t return Option or Result?
  28. How to create an in-memory object that can be used as a Reader, Writer, or Seek in Rust?
  29. What is the syntax to match on a reference to an enum?
  30. What is the prelude?

Leave a Comment