Tests fail when run with miri

[jrmuizel]

error[E0080]: constant evaluation error: no item to reborrow for Unique from tag 106812 found in borrow stack
   --> src/lib.rs:747:9
    |
747 |         ret
    |         ^^^ no item to reborrow for Unique from tag 106812 found in borrow stack
    |
    = note: inside call to `<LinkedList<i32> as std::iter::FromIterator<i32>>::from_iter::<std::iter::Map<std::slice::Iter<i32>, [closure@src/lib.rs:869:22: 869:38]>>` at /Users/jrmuizel/.rustup/toolchains/nightly-x86_64-apple-darwin/lib/rustlib/src/rust/src/libcore/iter/traits/iterator.rs:1465:9
note: inside call to `<std::iter::Map<std::slice::Iter<i32>, [closure@src/lib.rs:869:22: 869:38]> as std::iter::Iterator>::collect::<LinkedList<i32>>` at src/lib.rs:869:9
   --> src/lib.rs:869:9
    |
869 |         v.iter().map(|x| (*x).clone()).collect()
    |         ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
note: inside call to `tests::list_from::<i32>` at src/lib.rs:1200:25
   --> src/lib.rs:1200:25
    |
1200|         let mut list1 = list_from(&[0,1,2,3]);
    |                         ^^^^^^^^^^^^^^^^^^^^^
note: inside call to `tests::test_append` at src/lib.rs:1199:5
   --> src/lib.rs:1199:5
    |
1199| /     fn test_append() {
1200| |         let mut list1 = list_from(&[0,1,2,3]);
1201| |         let mut list2 = list_from(&[4,5,6,7]);
1202| |
...   |
1222| |         assert_eq!(list1.len(), 0);
1223| |     }
    | |_____^
    = note: inside call to closure at /Users/jrmuizel/.rustup/toolchains/nightly-x86_64-apple-darwin/lib/rustlib/src/rust/src/libcore/ops/function.rs:231:5
    = note: inside call to `<[closure@src/lib.rs:1199:5: 1223:6] as std::ops::FnOnce<()>>::call_once - shim` at /Users/jrmuizel/.rustup/toolchains/nightly-x86_64-apple-darwin/lib/rustlib/src/rust/src/libcore/ops/function.rs:231:5
    = note: inside call to `<fn() as std::ops::FnOnce<()>>::call_once - shim(fn())` at /Users/jrmuizel/.rustup/toolchains/nightly-x86_64-apple-darwin/lib/rustlib/src/rust/src/libtest/lib.rs:1522:5
    = note: inside call to `tests::test::__rust_begin_short_backtrace::<fn()>` at /Users/jrmuizel/.rustup/toolchains/nightly-x86_64-apple-darwin/lib/rustlib/src/rust/src/libtest/lib.rs:1513:30
    = note: inside call to closure at /Users/jrmuizel/.rustup/toolchains/nightly-x86_64-apple-darwin/lib/rustlib/src/rust/src/libcore/ops/function.rs:231:5
    = note: inside call to `<[closure@DefId(9/1:109 ~ test[b0fc]::run_test[0]::{{closure}}[3]) 0:fn()] as std::ops::FnOnce<()>>::call_once - shim` at /Users/jrmuizel/.rustup/toolchains/nightly-x86_64-apple-darwin/lib/rustlib/src/rust/src/libcore/ops/function.rs:231:5
    = note: inside call to `<[closure@DefId(9/1:109 ~ test[b0fc]::run_test[0]::{{closure}}[3]) 0:fn()] as std::ops::FnOnce<()>>::call_once - shim(vtable)` at /Users/jrmuizel/.rustup/toolchains/nightly-x86_64-apple-darwin/lib/rustlib/src/rust/src/liballoc/boxed.rs:704:9
    = note: inside call to `<std::boxed::Box<dyn std::boxed::FnBox<(), Output = ()> + std::marker::Send> as std::ops::FnOnce<()>>::call_once` at /Users/jrmuizel/.rustup/toolchains/nightly-x86_64-apple-darwin/lib/rustlib/src/rust/src/libstd/panic.rs:309:9
    = note: inside call to `<std::panic::AssertUnwindSafe<std::boxed::Box<dyn std::boxed::FnBox<(), Output = ()> + std::marker::Send>> as std::ops::FnOnce<()>>::call_once` at /Users/jrmuizel/.rustup/toolchains/nightly-x86_64-apple-darwin/lib/rustlib/src/rust/src/libstd/panicking.rs:293:40
    = note: inside call to `std::panicking::try::do_call::<std::panic::AssertUnwindSafe<std::boxed::Box<dyn std::boxed::FnBox<(), Output = ()> + std::marker::Send>>, ()>` at /Users/jrmuizel/.rustup/toolchains/nightly-x86_64-apple-darwin/lib/rustlib/src/rust/src/libstd/panicking.rs:289:5
    = note: inside call to `std::panicking::try::<(), std::panic::AssertUnwindSafe<std::boxed::Box<dyn std::boxed::FnBox<(), Output = ()> + std::marker::Send>>>` at /Users/jrmuizel/.rustup/toolchains/nightly-x86_64-apple-darwin/lib/rustlib/src/rust/src/libstd/panic.rs:388:9
    = note: inside call to `std::panic::catch_unwind::<std::panic::AssertUnwindSafe<std::boxed::Box<dyn std::boxed::FnBox<(), Output = ()> + std::marker::Send>>, ()>` at /Users/jrmuizel/.rustup/toolchains/nightly-x86_64-apple-darwin/lib/rustlib/src/rust/src/libtest/lib.rs:1468:26
    = note: inside call to closure at /Users/jrmuizel/.rustup/toolchains/nightly-x86_64-apple-darwin/lib/rustlib/src/rust/src/libtest/lib.rs:1490:13
    = note: inside call to `tests::test::run_test::run_test_inner` at /Users/jrmuizel/.rustup/toolchains/nightly-x86_64-apple-darwin/lib/rustlib/src/rust/src/libtest/lib.rs:1509:28
    = note: inside call to `tests::test::run_test` at /Users/jrmuizel/.rustup/toolchains/nightly-x86_64-apple-darwin/lib/rustlib/src/rust/src/libtest/lib.rs:1167:13
    = note: inside call to `tests::test::run_tests::<[closure@DefId(9/1:80 ~ test[b0fc]::run_tests_console[0]::{{closure}}[2]) 0:&mut tests::test::ConsoleTestState, 1:&mut std::boxed::Box<dyn tests::test::formatters::OutputFormatter>]>` at /Users/jrmuizel/.rustup/toolchains/nightly-x86_64-apple-darwin/lib/rustlib/src/rust/src/libtest/lib.rs:972:5
    = note: inside call to `tests::test::run_tests_console` at /Users/jrmuizel/.rustup/toolchains/nightly-x86_64-apple-darwin/lib/rustlib/src/rust/src/libtest/lib.rs:293:15
    = note: inside call to `tests::test::test_main` at /Users/jrmuizel/.rustup/toolchains/nightly-x86_64-apple-darwin/lib/rustlib/src/rust/src/libtest/lib.rs:327:5
    = note: inside call to `tests::test::test_main_static`
    = note: inside call to `main` at /Users/jrmuizel/.rustup/toolchains/nightly-x86_64-apple-darwin/lib/rustlib/src/rust/src/libstd/rt.rs:64:34
    = note: inside call to closure at /Users/jrmuizel/.rustup/toolchains/nightly-x86_64-apple-darwin/lib/rustlib/src/rust/src/libstd/rt.rs:52:53
    = note: inside call to closure at /Users/jrmuizel/.rustup/toolchains/nightly-x86_64-apple-darwin/lib/rustlib/src/rust/src/libstd/panicking.rs:293:40
    = note: inside call to `std::panicking::try::do_call::<[closure@DefId(1/1:1835 ~ std[797b]::rt[0]::lang_start_internal[0]::{{closure}}[0]) 0:&dyn std::ops::Fn() -> i32 + std::marker::Sync + std::panic::RefUnwindSafe], i32>` at /Users/jrmuizel/.rustup/toolchains/nightly-x86_64-apple-darwin/lib/rustlib/src/rust/src/libstd/panicking.rs:289:5
    = note: inside call to `std::panicking::try::<i32, [closure@DefId(1/1:1835 ~ std[797b]::rt[0]::lang_start_internal[0]::{{closure}}[0]) 0:&dyn std::ops::Fn() -> i32 + std::marker::Sync + std::panic::RefUnwindSafe]>` at /Users/jrmuizel/.rustup/toolchains/nightly-x86_64-apple-darwin/lib/rustlib/src/rust/src/libstd/panic.rs:388:9
    = note: inside call to `std::panic::catch_unwind::<[closure@DefId(1/1:1835 ~ std[797b]::rt[0]::lang_start_internal[0]::{{closure}}[0]) 0:&dyn std::ops::Fn() -> i32 + std::marker::Sync + std::panic::RefUnwindSafe], i32>` at /Users/jrmuizel/.rustup/toolchains/nightly-x86_64-apple-darwin/lib/rustlib/src/rust/src/libstd/rt.rs:52:25
    = note: inside call to `std::rt::lang_start_internal` at /Users/jrmuizel/.rustup/toolchains/nightly-x86_64-apple-darwin/lib/rustlib/src/rust/src/libstd/rt.rs:64:5
    = note: inside call to `std::rt::lang_start::<()>`

error: aborting due to previous error

For more information about this error, try `rustc --explain E0080`.
test tests::test_append ...

[jrmuizel]

@RalfJung

[jrmuizel]

Here's a simpler test case:

        let mut m = LinkedList::new();
        m.push_back(2);
        m.push_back(3);
        assert_eq!(m.pop_front(), Some(2));

which fails with:

error[E0080]: constant evaluation error: no item to reborrow for Unique from tag 105256 found in borrow stack
    --> /Users/jrmuizel/.rustup/toolchains/nightly-x86_64-apple-darwin/lib/rustlib/src/rust/src/libcore/mem.rs:1329:34
     |
1329 |         ManuallyDrop::into_inner(self.value)
     |                                  ^^^^^^^^^^ no item to reborrow for Unique from tag 105256 found in borrow stack
     |
     = note: inside call to `std::mem::MaybeUninit::<std::option::Option<std::boxed::Box<Node<i32>>>>::assume_init` at /Users/jrmuizel/.rustup/toolchains/nightly-x86_64-apple-darwin/lib/rustlib/src/rust/src/libcore/ptr.rs:576:5
     = note: inside call to `std::ptr::read::<std::option::Option<std::boxed::Box<Node<i32>>>>` at /Users/jrmuizel/.rustup/toolchains/nightly-x86_64-apple-darwin/lib/rustlib/src/rust/src/libcore/ptr.rs:359:17
     = note: inside call to `std::ptr::swap_nonoverlapping_one::<std::option::Option<std::boxed::Box<Node<i32>>>>` at /Users/jrmuizel/.rustup/toolchains/nightly-x86_64-apple-darwin/lib/rustlib/src/rust/src/libcore/mem.rs:651:9
     = note: inside call to `std::mem::swap::<std::option::Option<std::boxed::Box<Node<i32>>>>` at /Users/jrmuizel/.rustup/toolchains/nightly-x86_64-apple-darwin/lib/rustlib/src/rust/src/libcore/mem.rs:709:5
     = note: inside call to `std::mem::replace::<std::option::Option<std::boxed::Box<Node<i32>>>>` at /Users/jrmuizel/.rustup/toolchains/nightly-x86_64-apple-darwin/lib/rustlib/src/rust/src/libcore/option.rs:850:9
note: inside call to `std::option::Option::<std::boxed::Box<Node<i32>>>::take` at src/lib.rs:204:9
    --> src/lib.rs:204:9
     |
204  |         self.head.take().map(|mut head| {
     |         ^^^^^^^^^^^^^^^^
note: inside call to `LinkedList::<i32>::pop_front` at src/lib.rs:877:20
    --> src/lib.rs:877:20
     |
877  |         assert_eq!(m.pop_front(), Some(2));
     |                    ^^^^^^^^^^^^^
note: inside call to `tests::test_basic` at src/lib.rs:873:5
    --> src/lib.rs:873:5
     |
873  | /     fn test_basic() {
874  | |         let mut m = LinkedList::new();
875  | |         m.push_back(2);
876  | |         m.push_back(3);
...    |
903  | |         assert_eq!(n.pop_front(), Some(1));*/
904  | |     }
     | |_____^

[jrmuizel]

A further simplification:

        let ptr: *mut Node<_>;
        let mut head;
        {
            let mut node = Box::new(Node::new(2));
            // unconditionally make the new node the new tail
            ptr = &mut *node;
            head = Some(node);
        }
        {
            let mut node = Box::new(Node::new(3));
            let tail = unsafe { &mut *(ptr as *mut Node<_>) };
            node.prev = Raw::some(tail);
            tail.next = Some(node);
        }

        head.take();

[jrmuizel]

And here's the essence of what's going on:

        let mut node = Box::new(Node::new(2));
        let mut n2 = Box::new(Node::new(3));
        let ptr: *mut Node<_> = &mut *node;

        let tail = unsafe { &mut *(ptr as *mut Node<_>) };

        let mut head = Some(node);
        tail.next = Some(n2);

If we swap the order of let mut head = Some(node); and tail.next = Some(n2); everything is fine.

It's not clear to me why miri's is complaining about this:

error[E0080]: constant evaluation error: no item to reborrow for Unique from tag 105226 found in borrow stack
   --> /Users/jrmuizel/.rustup/toolchains/nightly-x86_64-apple-darwin/lib/rustlib/src/rust/src/libcore/ptr.rs:193:1
    |
193 | / unsafe fn real_drop_in_place<T: ?Sized>(to_drop: &mut T) {
194 | |     // Code here does not matter - this is replaced by the
195 | |     // real drop glue by the compiler.
196 | |     real_drop_in_place(to_drop)
197 | | }
    | |_^ no item to reborrow for Unique from tag 105226 found in borrow stack
    |
note: inside call to `std::ptr::real_drop_in_place::<std::option::Option<std::boxed::Box<Node<i32>>>> - shim(Some(std::option::Option<std::boxed::Box<Node<i32>>>))` at src/lib.rs:888:9
   --> src/lib.rs:888:9
    |
888 |         tail.next = Some(n2);
    |         ^^^^^^^^^
note: inside call to `tests::test_basic` at src/lib.rs:880:5

[RalfJung]

Can you make this into a self-contained example for the playground? That'd make analysis much easier for me.

[jrmuizel]

Yep. Will do.

[jrmuizel]

@RalfJung https://play.rust-lang.org/?version=stable&mode=debug&edition=2018&gist=f4e643db9511b26a96692b5a6869c853

[RalfJung]

node is a unique pointer (a Box). When you use it, you assert that there are no aliases that point to the same memory. If any aliases exist, they become invalid at this point.
In your program, tail is such an alias -- and hence becomes invalid.

[jrmuizel]

It seems like the use of Box in this crate basically needs to go. It looks like this happened in std's LinkedList in rust-lang/rust#34608