miri flags UB in Vec::swap_remove

[BoxyUwU]

The following code (playground):

fn main() {
    let mut a = 0;
    let mut b = 1;
    let mut vec = vec![&mut a, &mut b];
    
    vec.swap_remove(1);
}

run under miri reports UB:

error: Undefined Behavior: not granting access to tag <2330> because incompatible item is protected: [Unique for <2472> (call 780)]
  --> /playground/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/library/core/src/mem/manually_drop.rs:88:9
   |
88 |         slot.value
   |         ^^^^^^^^^^ not granting access to tag <2330> because incompatible item is protected: [Unique for <2472> (call 780)]
   |
   = help: this indicates a potential bug in the program: it performed an invalid operation, but the 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
           
   = note: inside `std::mem::ManuallyDrop::<&mut i32>::into_inner` at /playground/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/library/core/src/mem/manually_drop.rs:88:9
   = note: inside `std::mem::MaybeUninit::<&mut i32>::assume_init` at /playground/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/library/core/src/mem/maybe_uninit.rs:632:13
   = note: inside `std::ptr::read::<&mut i32>` at /playground/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/library/core/src/ptr/mod.rs:700:9
   = note: inside `std::ptr::swap_nonoverlapping_one::<&mut i32>` at /playground/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/library/core/src/ptr/mod.rs:454:17
   = note: inside `std::mem::swap::<&mut i32>` at /playground/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/library/core/src/mem/mod.rs:695:9
   = note: inside `std::ptr::replace::<&mut i32>` at /playground/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/library/core/src/ptr/mod.rs:570:9
   = note: inside `std::vec::Vec::<&mut i32>::swap_remove` at /playground/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/library/alloc/src/vec/mod.rs:1311:13
note: inside `main` at src/main.rs:6:5
  --> src/main.rs:6:5
   |
6  |     vec.swap_remove(1);
   |     ^^^^^^^^^^^^^^^^^^
   = note: inside `<fn() as std::ops::FnOnce<()>>::call_once - shim(fn())` at /playground/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/library/core/src/ops/function.rs:227:5
   = note: inside `std::sys_common::backtrace::__rust_begin_short_backtrace::<fn(), ()>` at /playground/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/library/std/src/sys_common/backtrace.rs:123:18
   = note: inside closure at /playground/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/library/std/src/rt.rs:146:18
   = note: inside `std::ops::function::impls::<impl std::ops::FnOnce<()> for &dyn std::ops::Fn() -> i32 + std::marker::Sync + std::panic::RefUnwindSafe>::call_once` at /playground/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/library/core/src/ops/function.rs:259:13
   = note: inside `std::panicking::r#try::do_call::<&dyn std::ops::Fn() -> i32 + std::marker::Sync + std::panic::RefUnwindSafe, i32>` at /playground/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/library/std/src/panicking.rs:403:40
   = note: inside `std::panicking::r#try::<i32, &dyn std::ops::Fn() -> i32 + std::marker::Sync + std::panic::RefUnwindSafe>` at /playground/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/library/std/src/panicking.rs:367:19
   = note: inside `std::panic::catch_unwind::<&dyn std::ops::Fn() -> i32 + std::marker::Sync + std::panic::RefUnwindSafe, i32>` at /playground/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/library/std/src/panic.rs:133:14
   = note: inside closure at /playground/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/library/std/src/rt.rs:128:48
   = note: inside `std::panicking::r#try::do_call::<[closure@std::rt::lang_start_internal::{closure#2}], isize>` at /playground/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/library/std/src/panicking.rs:403:40
   = note: inside `std::panicking::r#try::<isize, [closure@std::rt::lang_start_internal::{closure#2}]>` at /playground/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/library/std/src/panicking.rs:367:19
   = note: inside `std::panic::catch_unwind::<[closure@std::rt::lang_start_internal::{closure#2}], isize>` at /playground/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/library/std/src/panic.rs:133:14
   = note: inside `std::rt::lang_start_internal` at /playground/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/library/std/src/rt.rs:128:20
   = note: inside `std::rt::lang_start::<()>` at /playground/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/library/std/src/rt.rs:145:17

error: aborting due to previous error

[oli-obk]

cc @rust-lang/miri

[RalfJung]

The underlying issue is in replace: this has the same error.

fn main() {
    let mut a = 0;
    let mut r = &mut a;
    unsafe { std::ptr::replace(&mut r as *mut _, r); }
}

[RalfJung]

This is actually tricky, I think -- an unexpected consequence of the Stacked Borrows rules.

When r is being passed to replace, it gets reborrowed and then "protected", meaning the mutable reference passed to replace must outlive that function call. But then it goes ahead and reads the old reference from r directly via the raw pointer, which reborrows that reference, therefore invalidating the earlier other reborrow.

There is a sense in which the reborrow of r passed to replace is truly invalidated here -- and in fact it is not possible to access that value later:

error[E0382]: use of moved value: `r`
 --> src/main.rs:5:14
  |
3 |     let mut r = &mut a;
  |         ----- move occurs because `r` has type `&mut i32`, which does not implement the `Copy` trait
4 |     let v = unsafe { std::ptr::replace(&mut r as *mut _, r) };
  |                                                          - value moved here
5 |     let v2 = r;
  |              ^ value used here after move

I am surprised by this error, since usually mutable references are reborrowed, not moved. But it seems here it somehow knows not to reborrow?

[camelid]

I am surprised by this error, since usually mutable references are reborrowed, not moved. But it seems here it somehow knows not to reborrow?

cc #89966 -- could be related? Fully-qualifying the replace call with ::<&mut i32> yields a different error (where r reborrowed rather than moved), so it seems at least partially related:

error[E0505]: cannot move out of `r` because it is borrowed
 --> src/main.rs:5:14
  |
4 |     unsafe { std::ptr::replace::<&mut i32>(&mut r as *mut _, r); }
  |                                                              - borrow of `*r` occurs here
5 |     let v2 = r;
  |              ^
  |              |
  |              move out of `r` occurs here
  |              borrow later used here

[RalfJung]

Ah, yes that's it. Not that the exact error makes such a big difference, but now at least it is more clear that the reborrow makes later uses of r fail.

[nbdd0121]

I am surprised by this error, since usually mutable references are reborrowed, not moved. But it seems here it somehow knows not to reborrow?

Type inference will prevent reborrowing from happening.

[nbdd0121]

When r is being passed to replace, it gets reborrowed and then "protected"

Could we say that a mutable reference that comes from a type parameter shouldn't be protected?

[RalfJung]

That seems a bit strange, to have a particular instance of a generic function behave differently than if that same instance had been written monomorphically.

[nbdd0121]

Well, generic function is different from an monomorphic function. In a monomorphic function you can dereference the reference, but (if there're no Deref bounds) then in generic function you just have T and would need to treat it "just as data" and the fact it's monomorphized to be a reference shouldn't be special.

I.e. I would expect a Vec<&mut u8> to behave more closely to Vec<*mut u8> or Vec<usize> than a dedicated, say VecOfRefMut type. It is strange to me that two monomorphized versions of the same function should behave differently.

[RalfJung]

Well, generic function is different from an monomorphic function. In a monomorphic function you can

Sure, a monomorphic function can be changed to do more things.

But when a generic and monomorphic function are the same in the source code, they also should behave the same.

It is strange to me that two monomorphized versions of the same function should behave differently.

They use completely different types, so them behaving the same does not even make sense? Like, e.g., size_of::,T>() will literally return different values. In general, two monomorphized versions of the same function have no choice but to behave differently.

To give another example, if you transmute_copy a 9u8 to T, then again of course this is UB for some T (e.g., bool) but totally fine for others (e.g., 0u8).