VecDeque::iter_mut tramples on the references it returned earlier

[ssomers]

I tried running this code with Miri (on playground):

fn test_all_refs<'a, T: 'a>(dummy: &mut T, iter: impl Iterator<Item = &'a mut T>) {
    // Gather all those references.
    let mut refs: Vec<&mut T> = iter.collect();
    // Use them all. Twice, to be sure we got all interleavings.
    for r in refs.iter_mut() {
        std::mem::swap(dummy, r);
    }
    for r in refs {
        std::mem::swap(dummy, r);
    }
}

fn main() {
    let mut v = std::collections::VecDeque::new();
    v.push_back(1);
    v.push_back(2);
    test_all_refs(&mut 0, v.iter_mut());
}

I expected to see it end gracefully.

Instead, it reports:

error: Undefined Behavior: trying to reborrow for Unique, but parent tag <4482> does not have an appropriate item in the borrow stack
    --> /playground/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/src/liballoc/vec.rs:2099:53
     |
2099 |                     ptr::write(vector.as_mut_ptr(), element);
     |                                                     ^^^^^^^ trying to reborrow for Unique, but parent tag <4482> does not have an appropriate item in the borrow stack
     |
     = 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::vec::Vec<&mut i32> as std::vec::SpecExtend<&mut i32, std::collections::vec_deque::IterMut<i32>>>::from_iter` at /playground/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/src/liballoc/vec.rs:2099:53
     = note: inside `<std::vec::Vec<&mut i32> as std::iter::FromIterator<&mut i32>>::from_iter::<std::collections::vec_deque::IterMut<i32>>` at /playground/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/src/liballoc/vec.rs:1995:9
     = note: inside `<std::collections::vec_deque::IterMut<i32> as std::iter::Iterator>::collect::<std::vec::Vec<&mut i32>>` at /playground/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/src/libcore/iter/traits/iterator.rs:1671:9
note: inside `test_all_refs::<i32, std::collections::vec_deque::IterMut<i32>>` at src/main.rs:3:33
    --> src/main.rs:3:33
     |
3    |     let mut refs: Vec<&mut T> = iter.collect();
     |                                 ^^^^^^^^^^^^^^
note: inside `main` at src/main.rs:17:5
    --> src/main.rs:17:5
     |
17   |     test_all_refs(&mut 0, v.iter_mut());
     |     ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
     = note: inside closure at /playground/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/src/libstd/rt.rs:67:34
     = note: inside closure at /playground/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/src/libstd/rt.rs:52:73
     = note: inside `std::sys_common::backtrace::__rust_begin_short_backtrace::<[closure@std::rt::lang_start_internal::{{closure}}#0::{{closure}}#0 0:&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/src/libstd/sys_common/backtrace.rs:130:5
     = note: inside closure at /playground/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/src/libstd/rt.rs:52:13
     = note: inside `std::panicking::r#try::do_call::<[closure@std::rt::lang_start_internal::{{closure}}#0 0:&&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/src/libstd/panicking.rs:342:40
     = note: inside `std::panicking::r#try::<i32, [closure@std::rt::lang_start_internal::{{closure}}#0 0:&&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/src/libstd/panicking.rs:319:15
     = note: inside `std::panic::catch_unwind::<[closure@std::rt::lang_start_internal::{{closure}}#0 0:&&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/src/libstd/panic.rs:394:14
     = note: inside `std::rt::lang_start_internal` at /playground/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/src/libstd/rt.rs:51:25
     = note: inside `std::rt::lang_start::<()>` at /playground/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/src/libstd/rt.rs:67:5

[leonardo-m]

The code of VecDeque seems the right one to functionally verify with something from this list:
https://alastairreid.github.io/rust-verification-tools/

[ssomers]

Let's also add a test for this case of undefined behaviour exposed by Miri.

[RalfJung]

Proposed fix is up at #76911