I am trying to write an iterator over mutable elements of a tree. The tree is stored in a Vec
. Implementing such an iterator is not straight-forward: the lifetimes of the items returned in Iterator::next
cannot be bound to the invocation of Iterator::next
. However, if we can guarantee the graph is actually a tree (i.e., during traversal, each element is visited exactly once), then the iterator is allowed to yield items with a longer lifetime.
When I tried to implement this, Miri reported stacked borrow errors. I broke it down to the following minimal example, where the depth-first traversal is replaced by random (but unique) indices.
use rand::prelude::*;
use std::cell::UnsafeCell;
#[allow(clippy::mut_from_ref)]
unsafe fn read<T>(data: &UnsafeCell<Vec<T>>, idx: usize) -> &mut T {
unsafe { &mut data.get().as_mut().unwrap()[idx] }
}
fn main() {
const LEN: usize = 8;
let data = UnsafeCell::new(vec![0; LEN]);
let mut indices = (0..LEN).collect::<Vec<_>>();
indices.shuffle(&mut thread_rng());
let refs = indices
.into_iter()
.map(|idx| unsafe { read(&data, idx) })
.collect::<Vec<_>>();
for x in refs {
*x = 1;
}
}
When I run miri on this code, I get the following error:
error: Undefined Behavior: trying to retag from <71188> for Unique permission at alloc925[0x4], but that tag does not exist in the borrow stack for this location
--> /home/tibor/.local/share/rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/library/alloc/src/vec/into_iter.rs:225:23
|
225 | Some(unsafe { ptr.read() })
| ^^^^^^^^^^
| |
| trying to retag from <71188> for Unique permission at alloc925[0x4], but that tag does not exist in the borrow stack for this location
| this error occurs as part of retag at alloc925[0x4..0x8]
|
= help: this indicates a potential bug in the program: it performed an invalid operation, but the Stacked Borrows rules it violated are still experimental
= help: see https://github.com/rust-lang/unsafe-code-guidelines/blob/master/wip/stacked-borrows.md for further information
help: <71188> was created by a Unique retag at offsets [0x4..0x8]
--> src/main.rs:16:16
|
16 | let refs = indices
| ________________^
17 | | .into_iter()
18 | | .map(|idx| read(&data, idx))
19 | | .collect::<Vec<_>>();
| |____________________________^
help: <71188> was later invalidated at offsets [0x0..0x20] by a Unique retag
--> src/main.rs:6:47
|
6 | unsafe { &mut data.get().as_mut().unwrap()[idx] }
| ^^^^^
= note: BACKTRACE (of the first span):
= note: inside `<std::vec::IntoIter<&mut i32> as std::iter::Iterator>::next` at /home/tibor/.local/share/rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/library/alloc/src/vec/into_iter.rs:225:23: 225:33
note: inside `main`
--> src/main.rs:21:14
|
21 | for x in refs {
| ^^^^
I don't understand why Miri complains here. To further add to my confusion, I rewrote the read
function using pointer arithmetics, and Miri no longer complains with that implementation:
#[allow(clippy::mut_from_ref)]
unsafe fn read_ptr<T>(data: &UnsafeCell<Vec<T>>, idx: usize) -> &mut T {
unsafe {
let len = data.get().as_ref().unwrap().len();
assert!(idx < len);
let ptr_to_slice = data.get().as_ref().unwrap().as_ptr();
let ptr_to_elem = ptr_to_slice.add(idx);
(ptr_to_elem as *mut T).as_mut().unwrap()
}
}
Can someone explain to me why read
results in a stacked borrow, but read_ptr
does not? Aren't they identical (up to a bounds check)?