VecDeque's Drain::drop writes to memory that a shared reference points to

[RalfJung]

liballoc's test_drain fails when run in Miri. The error occurs in the drain(...).collect() call:

• collect is called with a vec_deque::Drain<usize> as argument. Drain contains Iter contains a shared reference to a slice; that slice is thus marked as "must not be mutated for the entire duration of this function call".
• collect calls from_iter calls extend calls for_each calls fold, which eventually drops the Drain.
• Drain::drop calls source_deque.wrap_copy to re-arrange stuff (I have not fully understood this yet), and in some cases this will end up writing to memory that the slice in Iter points to.

I am not sure what the best way to fix this is. We have to fix Drain holding (indirectly) a shared reference to something that it'll mutate during its Drop. The mutation is likely there for a reason, so I guess the shared reference has to go. (FWIW, this shared reference already caused other trouble, but that was fixed by #56161.)

Cc @nikomatsakis @gankro

[Gankra]

yeah I guess just change it to *const [T] and toss in a PhantomData for the borrow. shrug

[RalfJung]

You mean, change this in Iter as well? Sure, that should work. In principle this reduces the precision of compiler analyses on VecDeque::iter().

[Gankra]

ahh misread. maybe would just not use Iter then. depends on what the impl looks like now

[cuviper]

• Drain::drop calls source_deque.wrap_copy to re-arrange stuff (I have not fully understood this yet), and in some cases this will end up writing to memory that the slice in Iter points to.

But the first thing it does is self.for_each(drop); which should exhaust the Iter such that its ring is an empty slice. I suppose its pointer will still be somewhere in the deque's memory, but with length 0 it can't actually read anything. Is that not good enough to appease Miri?

[RalfJung]

@cuviper

But the first thing it does is self.for_each(drop); which should exhaust the Iter such that its ring is an empty slice. I suppose its pointer will still be somewhere in the deque's memory, but with length 0 it can't actually read anything. Is that not good enough to appease Miri?

No. This code still matches the pattern

fn foo(mut x: (T, &[U])) {
  let ptr = &x.1[0] as *const U;
  // do some stuff with x that "semantically" "exhausts" the slice.
  x.1 = &[];
  // then write to where `x.1` used to point to.
  *(ptr as *mut U) = ...;
}

There is no notion of "exhausting" or "consuming" a shared reference. When you create a shared reference with a certain lifetime, you promise that until that lifetime ends, no mutation happens. x here is mutable so you can change what the slice points to, but that has no effect at all on the guarantees that have been made about the value that was initially passed to foo.

Now, lifetimes are an entirely static concept, so for Stacked Borrows a "lifetime" generally is "until the pointer is used for the last time". However, for the special case of a reference being passed to a function, Stacked Borrows asserts that the "lifetime" will last at least as long as the function the reference is pointed to. (This is enforced by the "barriers" explained in this blog post.) This is extremely useful for optimizations.

[RalfJung]

ahh misread. maybe would just not use Iter then. depends on what the impl looks like now

Drain::{next, next_back, size_hint} forward to Iter. I wouldn't want to copy those.

[cuviper]

Oh, I also didn't realize that Iter doesn't actually shrink down to an empty slice -- it only updates its indexes. It would otherwise have to use two slices for the wrapped head and tail. So that full shared reference does still exist after the iterator is exhausted. (This also raises the validity question of having references to uninitialized data.)

Could we base Drain on IterMut instead? We could arrange wrap_copy to work through that mutable reference too, so there's no question of mutable aliasing.

[RalfJung]

Could we base Drain on IterMut instead? We could arrange wrap_copy to work through that mutable reference too, so there's no question of mutable aliasing.

That might work. However, Drain::drop must not access deque.buf in that case -- that would be in conflict with the unique reference in IterMut.

[cuviper]

Hmm, does Drain need to be covariant over T? I guess IterMut would break that.

[RalfJung]

Actually this idea of "consuming a shared ref" is far from unique to VecDeque... the following code also errors in Miri:

use std::cell::{RefCell, Ref};

fn break_it(rc: &RefCell<i32>, r: Ref<'_, i32>) {
    // `r` has a shared reference, it is passed in as argument and hence
    // a barrier is added that marks this memory as read-only for the entire
    // duration of this function.
    drop(r);
    // *oops* here we can mutate that memory.
    *rc.borrow_mut() = 2;
}

fn main() {
    let rc = RefCell::new(0);
    break_it(&rc, rc.borrow())
}

[Julian-Wollersberger]

As I understand it, Miri and stacked borrows should be "more powerful" than the Rust borrow checker, right?
So, is this an example where Miri does not match what Rust allows or is this a bug in Rust that could lead to undefined behaviour in safe code?
(Your example in the playground)