Confused about indexing and lifetime

help
1

Let's write a poor man's mutable iteration.

let mut v = vec![1, 2, 3, 4, 5, 6, 7, 8, 9];

let v_len = v.len();
for index in 0..v_len {
    v[index] *= 2;
}

Dummy, useless but it works.

Let's use a functional approach:

(0..v_len).for_each(|index| {
    v[index] *= 2;
});

Everything fine!

Now what I expected to work but it does not.

(0..v_len).map(|index| &mut v[index]).for_each(|el| {
    *el *= 2;
});

error[E0495]: cannot infer an appropriate lifetime for lifetime parameter in function call due to conflicting requirements
  --> src/main.rs:14:27
   |
14 |         .map(|index| &mut v[index])
   |                           ^^^^^^^^
   |
note: first, the lifetime cannot outlive the lifetime  as defined on the body at 14:14...
  --> src/main.rs:14:14
   |
14 |         .map(|index| &mut v[index])
   |              ^^^^^^^^^^^^^^^^^^^^^
note: ...so that closure can access `v`
  --> src/main.rs:14:27
   |
14 |         .map(|index| &mut v[index])
   |                           ^
note: but, the lifetime must be valid for the expression at 16:13...
  --> src/main.rs:16:13
   |
16 |             *el *= 2;
   |             ^^^
note: ...so that pointer is not dereferenced outside its lifetime
  --> src/main.rs:16:13
   |
16 |             *el *= 2;
   |             ^^^

Playground

I really tried to understand what was going on, but I did not figure it out. I imagined that I needed to move the slice inside the closure, but it does not change anything.

So:

  • can you help me understand what the real issue is?
  • do you have any idea if there is a workaround?

Just a quick note: there is a reason for using indices. I found myself needing the mutable reference of two distinct elements inside a slice. That can be easily (more or less) done using split_at_mut and split_first_mut, obtaining a mut ref to an element and two mutable slices, from which another element can be taken. I wanted to return an impl Iterator that returns pairs of mutable reference that satisfy certain conditions, but the error I showed you is blocking me. Even worse, it is not possible to create a custom iterator that performs that because it would require streaming iterators, therefore a stable implementation of GAT. :confused:

1 Like
2

I think this boils down to the following intuition here: how does the compiler prove that (0..v_len) does not end up aliasing inside v? If there are duplicate values in that range (there aren't, but compiler doesn't know from first principles - it's just an iterator that produces numbers), then map() will end up creating aliased mutable values. This is also why that same code works perfectly fine if map() were to yield immutable borrows.

Put another way, the map() closure is similar in spirit to the following code:

struct MutRef<'a>(&'a mut [i32]);

impl<'a> MutRef<'a> {
    fn map(&mut self, idx: usize) -> &'a mut i32 {
        &mut self.0[idx]
    }
}

This won't compile either, for the same reason. You'd need to change map to take &'a mut self.

I think unless you use existing std code, such as split_at_mut and whatnot, to grab distinct mutable elements from the slice, you'll need to roll your own unsafe code, just like split_at_mut and friends do. And I personally think it's ok so long as you enforce the invariants through code and understand the tradeoffs/decision you're making.

As one possible (easy and straightforward) workaround, perhaps you can have a Vec<Cell<i32>> and use immutable borrowing + interior mutability (not sure if your real case is amenable to Cell, though).

2 Likes
3

I thing that you exactly got the point. It is a bit disappointing because I was trying to avoid the problems of GATs, but it looks like I ended up with a very related issue.

Yes, interior mutability helps a lot in this case, but it obviously requires code restructuring. It is not that bad, but it is not possible (or at least I still can't find a way) to have multiple independent mutable objects from a slice of any T without using unsafe code.

I thought that my favourite request for 2019 was const generics, but maybe I need GATs even more :sweat_smile:

4

Yeah, GATs are sorely missed in some specific cases - it's a feature I'm looking forward to as well.

However, I don't think GATs would help you if you're aiming for mutably borrowing multiple items that cannot be proven to be disjoint/distinct by the compiler. It'd be awesome if there was a way to encode disjointness into types without using unsafe, but I'm not sure what that would even look like.

1 Like
5

You don't need GATs to get any number of disjoint borrows out of a Vec in safe code; all you need is split_at_mut. It may be slower and more difficult than just using unsafe, but it's general enough to do nearly anything (you could, for example, collect all the &mut references to every item into a Vec<Option<&mut i32>> and use mut_vec[i].take().unwrap() to retrieve each one at most once, panicking if you try to take the same one twice).

Streaming iterators are more limiting in this respect because, since the items borrow from the iterator itself, they can't be collected.

Finally, you don't need GATs to implement a streaming iterator, only to abstract over streaming iterators. It's possible to write code like this in safe Rust today:

let i = streaming_iterator(&mut vec);
while let Some(r) = i.next() {
    // r may be a mutable reference and overlap with previous values of r but it's ok because it borrows from i
}
1 Like
6

@trentj
You are absolutely right. The reason I was trying to avoid the streaming_iterator crate is only because... they are not Iterator. And the reason because we cannot use Iterator as a streaming one is because we miss GAT :cry:.

There is another issue that it is fixable, but I am not sure about the best way to handle the situation: StreamingIterator::next() returns a const reference to its internal reference. Therefore, even if you use them to iterate over &mut T, you will end up with a & &mut T and you cannot mutate the element.

Possible "easy" fixes are having a StreamingIteratorMut or StreamingIterator::next_mut, but both of them have downsides.

The "hard" way is to get generics over mutability, and I don't know if we are going to have them soon :cry:

@vitalyd You are definitely right when saying that the issue with the "indexes approach" is completely unrelated to GATs. I knew the problems about streaming iterators and I (wrongly) related them to the issue.

7

I didn't even know there was a streaming_iterator crate. I meant just in general. You can write a streaming iterator, you just can't express a StreamingIterator trait with abstraction over the type of the item. It doesn't sound like you needed that, since the items you want to yield are all (mutable references to) slices, so that degree of abstraction is not necessary.

Even when GATs are introduced, I think you will still have to use while let Some(_) = i.next() because changing the Iterator API would be a breaking change. So "it's not Iterator" is not a problem that will be solved by GATs. (I could be wrong about that.)

1 Like
8

Honestly, this is one big concern of mine. I am totally unaware of discussions about this point, but I am quite sure that this is not the kind of change that can be made inside and epoch.

Obviously it is not a problem to write down a use case StreamingIterator as you said, and I needed the functionality just for toy project -- it is not a real issue for now in my case. However, you have to handle the fact that the ecosystem uses the Iterator trait. It is just like the problem with Future: you can use the 0.3 version, but you will not be able to use tokio (but we got romio, so who cares :grin: I am just kidding, obviously)