iterator_invalidation.md (2650B)
1 # Iterator Invalidation 2 3 Iterator invalidation is a bug where an iterator becomes invalid because the 4 underlying collection it references is modified during iteration. Rust prevents 5 this at compile time through its borrow checker, unlike languages like C++ where 6 it causes undefined behaviour or crashes at runtime. 7 8 When you iterate over a collection (e.g., a Vec), the iterator holds a reference 9 to that collection's memory. If the collection is modified — say, by pushing a 10 new element — the Vec may need to reallocate its memory to grow, freeing the old 11 memory and leaving the iterator pointing to a dangling address. At best this 12 causes a crash (segfault); at worst it silently corrupts memory. 13 14 Rust's borrow checker enforces that you cannot hold an immutable borrow and a 15 mutable borrow at the same time. When you call v.iter(), Rust creates an 16 immutable borrow on the entire collection. Any attempt to call v.push() or 17 v.remove() during the loop requires a mutable borrow — which the compiler 18 outright refuses to compile: 19 20 ```rust 21 fn main() { 22 let mut vec = vec![1, 2, 3, 4, 5]; 23 for elem in &vec { 24 vec.push(elem * 2); // COMPILE ERROR: cannot borrow `vec` as mutable 25 // because it is also borrowed as immutable 26 } 27 } 28 ``` 29 30 The error is caught at compile time, not at runtime. 31 32 ## What You _Can_ Do Safely 33 34 | Pattern | Allowed? | Why | 35 | :--------------------------------------- | :------- | :----------------------------------------- | 36 | `v.iter()` + read elements | ✅ | Multiple immutable borrows are fine | 37 | `v.iter_mut()` + modify each element | ✅ | One mutable borrow, no structural changes | 38 | `v.iter()` + `v.push()` in the same loop | ❌ | Immutable + mutable borrow conflict | 39 | Collect indices, then modify after loop | ✅ | Iterator is dropped before mutation begins | 40 41 A common safe workaround is to use `retain` or collect the changes you need into 42 a separate `Vec`, then apply them after the loop ends — by which point the 43 iterator has been dropped and the borrow is released. 44 45 ## It's effectively threaded 46 47 > Aliasing with mutability in a sufficiently complex, single-threaded program is 48 > effectively the same thing as accessing data shared across multiple threads 49 > without a lock 50 51 > My intuition is that code far away from my code might as well be in another 52 > thread, for all I can reason about what it will do to shared mutable state. 53 54 [Reference](http://manishearth.github.io/blog/2015/05/17/the-problem-with-shared-mutability/)