Help with iterators yielding mutable references

#1

Hi, Rust Forums.

I’m running into issues with lifetimes when trying to write a mutable iterator over a struct which holds a HashMap. Is there a way to make explicit my lifetimes and satisfy autoref?

I looked at the StreamingIterator trait briefly, but it doesn’t seem to work for mutable references. I also found the article Iterators Yielding Mutable References which indicates that this pattern doesn’t work with the Iterator trait. Is that still true? What’s the normal workaround? Should I be writing a MutableIterator trait or is there a crate out there?

(Link to playground.) Here is the error message:

error[E0495]: cannot infer an appropriate lifetime for autoref due to conflicting requirements
  --> src/lib.rs:13:40
   |
13 |             Some(id) => self.inner_map.get_mut(&id),
   |                                        ^^^^^^^
   |
note: first, the lifetime cannot outlive the anonymous lifetime #1 defined on the method body at 11:5...
  --> src/lib.rs:11:5
   |
11 | /     fn next(&mut self) -> Option<Self::Item> {
12 | |         match self.ids.pop() {
13 | |             Some(id) => self.inner_map.get_mut(&id),
14 | |             None => None,
15 | |         }
16 | |     }
   | |_____^
note: ...so that reference does not outlive borrowed content
  --> src/lib.rs:13:25
   |
13 |             Some(id) => self.inner_map.get_mut(&id),
   |                         ^^^^^^^^^^^^^^
note: but, the lifetime must be valid for the lifetime 'a as defined on the impl at 9:6...
  --> src/lib.rs:9:6
   |
9  | impl<'a, V> Iterator for IterMut<'a, V> {
   |      ^^
   = note: ...so that the types are compatible:
           expected std::iter::Iterator
              found std::iter::Iterator

error: aborting due to previous error

Thanks,
-James

Mutable iterator over ordered subset of HashMap
#2

Still true. If you assert (preferably via an actual code assertion/invariant guarantee) that ids contains unique keys, you can apply a bit of unsafe to your iterator impl.

#3

I think I see how unsafe would help dodge the compiler issues here, but I’m not seeing why ids needs to have unique keys. Do you maybe have a pointer to somewhere this method is used in the stdlib or elsewhere?

#4

Imagine what would happen if ids is [1,2,1]. Then you call:

let values = your_iter.collect::<Vec<_>>();

You’re now mutably aliasing the value for 1, which is UB. This is basically why the existing Iterator scheme/design disallows returning a mutable borrow of a longer lifetime than the &mut self borrow of the iterator itself.

Which method, using unsafe? Or asserting safety before doing something unsafe? If it’s the latter, take a look at split_at_mut, kind of a canonical example of such a thing these days.

2 Likes
#5

Thanks Vitaly for pointing me here. James’ and my post are identical almost line by line, so I merged both examples, and by applying your suggestions I was able to assemble something working. I’m very new to unsafe, it would be great if one of you could review it.

There’s an example on rust-unofficial, where they write “Surprisingly, IterMut can actually be implemented for many structures completely safely”. I wonder if and how this is possible?

1 Like
#6

No problem!

Your code seems fine (on mobile so only a spot check). As always with unsafe code, make sure you plaster enough unit tests, fuzz tests, and whatever other minesweeping at your disposal to protect yourself :slight_smile:.

Perhaps you can use something like IndexSet instead of a Vec, saving yourself the trouble of ensuring uniqueness manually.

If you’re lax on performance requirements and/or using some underlying type that already provides mutable iteration in the manner you want, it’s possible to avoid unsafe. Like in the example here, you can collect HashMap::values_mut() into some container and then sort the elements based on their index in the Vec. Or perhaps use the IndexMap from the same crate and populate it in the desired (insertion) order.