Hi everyone,
I'm new to this forum and semi-new to Rust and currently battling with the borrow checker and Miri.
My final goal is to build a tree data structure where nodes are stored in a central shared Vec and refer to each other with index-like handle objects. Now I want to build the iter() and iter_mut() functions for said container, i.e. I need to hand out references into the vec based on indices within the iterator. iter() is fine, but of course iter_mut() is the hard part.

Coming from C++, my first draft was as follows: (using an iterator built via a .map() function here as a proof of concept before building the proper type)

fn main() {
    let mut source = vec![1, 2, 3, 4];
    let index = vec![0, 3, 1, 2];

    let it = index.iter()
        .map(|i| &mut source[*i]); // fails borrowck
    //...
}

This fails the borrow checker, and I believe I by now even understood why (correct me if I'm wrong):
The Iterator trait requires the Item type to have a named lifetime 'i that is different from the one next<'b>(&'b self) is called with, so the body of next(), or in this example my lambda, must ensure the returned reference outlives its source due to the &'short&'long -> &'short lifetime coercion. (Correct?)

To fix it I tried the following, basically masking the original borrow's lifetime with a raw pointer deref:

.map(|i| unsafe { &mut *(&raw mut source[*i]) }); // passes borrowck, but not Miri

(I guess I could have used std::mem::transmute() as well, what is the more idiomatic way to do it?)
These pointer shenanigans at least make the borrow checker happy, but they still aren't enough for Miri. When using a special function I found online that collect()s the mutable iterator and then std::mem::swap()s the returned references a bunch, Miri reports the following error:

error: Undefined Behavior: trying to retag from <930> for SharedReadWrite permission at alloc238[0x0], but that tag does not exist in the borrow stack for this location
  --> src/main.rs:19:31
   |
19 |         std::mem::swap(dummy, r);
   |                               ^ this error occurs as part of two-phase retag at alloc238[0x0..0x4]
   |
   = 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: <930> was created by a Unique retag at offsets [0x0..0x4]
  --> src/main.rs:17:28
   |
17 |     let mut refs: Vec<_> = iterator.collect();
   |                            ^^^^^^^^^^^^^^^^^^
help: <930> was later invalidated at offsets [0x0..0x10] by a Unique retag
  --> src/main.rs:7:49
   |
 7 |         .map(|i| unsafe { &mut *(&raw mut source[*i]) }); // fails Miri
   |                                                 ^^^^
   = note: BACKTRACE (of the first span):
   = note: inside `check_all_refs::<'_, i32, std::iter::Map<std::slice::Iter<'_, usize>, {closure@src/main.rs:7:14: 7:17}>>` at src/main.rs:19:31: 19:32
note: inside `main`
  --> src/main.rs:11:5
   |
11 |     check_all_refs(&mut 0, it);
   |     ^^^^^^^^^^^^^^^^^^^^^^^^^^

note: some details are omitted, run with `MIRIFLAGS=-Zmiri-backtrace=full` for a verbose backtrace

error: aborting due to 1 previous error

(Playground link at the end if you want to see exactly what I did)
Now I have to admit, I'm still pretty bad at understanding Miri errors, but it appears to me that it's taking issue with me borrowing the entire slice of the vec each time in order to take out an item's reference in the lambda in line 7. (Is that actually what's happening here?)
Now the question is, how to avoid this? Or is this "safe enough" for production and Miri is just overzealous? Note that the usual solutions to this I found online, such as using split_off_first_mut() would be quite complicated to implement, since I require access by index in a random order (no duplicates of course, so it's still safe to do at all without a true lending iterator).
I tried the following workaround to get Miri to shut up, but this seems unsafer and especially less maintainable to me than the version above:

.map(|i| unsafe { 
    assert!(*i < source.len());
    &mut *source.as_mut_ptr().add(*i) 
});

So what would be the cleanest way to do this? Am I overlooking an obvious simple solution?
Since all three of the above functions would probably compile to exactly the same bytecode, I wonder if the tools are perhaps a bit too eager in this case.

I'm looking forward to your enlightening answers!
/ J. Aetherwing

As promised, the playground link to my experiment:

2 posts - 2 participants

Read full topic