Yeah, no it isn’t. Iterating over a Vec or slice in Rust is quite efficiently implemented, where at the start of iteration, pointers to the start and end of the Vec's or slice's memory are created, and then iteration increments the pointer until one reaches the other.
This kind of optimization (and similarly other optimizations for other data structures’ iterators) are becoming problematic – in principle – when the data structure is mutated while being iterated. In particular, Vec::push can increase the size of the allocation, i.e. move everything to a totally different place in memory, so that after that, using the pointers created when iteration was started is actually going to access freed memory (= a pretty bad thing). Other languages might solve this problem by avoiding such dangerous optimizations to the iterator, (though – particularly for more complex data structures like sets or maps – even without the danger of memory unsafety, adding/removing elements while iterating can still have surprising effects). Rust solves the issue by ruling out the problem for occurring in the first place via its strict rules against mutation without exclusive access. (With the effect that while an iterator on a data structure exists, you can’t modify it.)
In your concrete case now, if any player’s dest pointed to the player themself, your loop over &player.items would modify that same .items vector inside the loop, the problem described above.
In other words, your code is only fine in principle, if dest is explicitly double-checked to always refer to a different player.
Now, with this insight, let’s see how to modify the code. Well for one thing, for player in players.iter_mut() makes players completely unaccessible during iteration, so this needs to change. Sometimes, as is the case here, we can gain a benefit by iterating over indices instead, though. There is some potential overhead involved in this from additional checks whether the index is in-bounds, but that’s not extremely dramatic, and with some luck, we can even make sure to get most or all of those optimized away.
The re-write lets us start with
for player_ix in 0..players.len() {
let player = &mut players[player_ix];
…
and leads right into the next question: How to access two elements of a Vec at the same time? The standard-library approach here is slightly tedious until we stabilize API like this (->link). Maybe, we should just use a helper function for the time being, one possible (safe Rust) implementation could use split_at_mut as follows
/// Panics when `x == y` or either is out of bounds
fn two_slice_indices<T>(x: usize, y: usize, slice: &mut [T]) -> (&mut T, &mut T) {
if x < y {
let (_, [a, bs@..]) = slice.split_at_mut(x)
else { panic!("index out of bounds in `two_slice_indices`") };
(a, &mut bs[y-x-1])
} else if y < x {
let (_, [a, bs@..]) = slice.split_at_mut(y)
else { panic!("index out of bounds in `two_slice_indices`") };
(&mut bs[x-y-1], a)
} else {
panic!("equal indices in `two_slice_indices`")
}
}
Now we can write the whole code successfully, and the code will panic if any dest refers to the player itself.
for player_ix in 0..players.len() {
let player = &mut players[player_ix];
let target_ix = player.dest;
let (player, target) = two_slice_indices(player_ix, target_ix, &mut players);
for item in &player.items {
target.items.push(*item);
}
player.items.clear();
}
https://play.rust-lang.org/?version=stable&mode=debug&edition=2021&gist=caaec83c4b770f8c339c7045e3551fbf
Now, the result looks funny though, doesn’t it?
[src/main.rs:40] players = [
Player {
items: [
7,
8,
9,
4,
5,
6,
1,
2,
3,
],
dest: 1,
},
Player {
items: [],
dest: 2,
},
Player {
items: [],
dest: 0,
},
]
If this is what you expected, great, feel free to ignore anything beyond this point (might still want to read it though nonetheless),
otherwise, if this result is surprising, well… let me quote myself
even without the danger of memory unsafety, adding/removing elements while iterating can still have surprising effects
In case you expected each player to have, again, exactly 3 items now, then you’ll need to re-work the whole algorithm. Which is a questionably behaving algorithm IMO anyways, even if the result is not unexpected, because the result is clearly dependent on the order of the players. One approach that could work is to work with two vectors of players, back and forth (so you can re-use them, saving some allocation), to – essentially, but slightly optimized – always generate a new list of players. Or you could use (and also keep re-using) a helper structure containing just the new list of items vectors. Maybe start out with a simple version that just always creates new vecs anyways; allocation is not extremely expensive either, anyways.
In case you do want/try to re-write the logic into such an approach, you’ll most likely notice that there’s no longer any hard borrow-checking related errors. I.e. the more predictably behaving code is the one that’s also more easily written.
But I'm comfortable that my usage is actually safe here, I just can't work out how to convince the compiler of that fact. So I'd appreciate any suggestions - I'm fairly sure this is a common enough pattern, so I'm hoping there's an idiomatic Rust way of expressing it.
? Of course, this guideline relies on “safe abstractions” which are actually unsafe code internally; in other words the guideline applies to code where a high-quality safety code review is too tedious (especially as a trade-off against how important performance is); and to code where the existing safe solution doesn’t have any (performance) disadvantages over unsafe alternatives.