BTreeMap use of EMPTY_ROOT_NODE causes MIRI failure.

[apoelstra]

In liballoc/collections/btree/node.rs the constant EMPTY_ROOT_NODE is defined as a LeafNode<(), ()>. A comment explains that while the key/value can be set to () and (), this constant can be used in any BTreeMap of any key/value type. The reason being that this is only used as a placeholder in an empty tree, and the rest of the source ensures that neither the keys nor vals field are ever accessed.

However, LeafNode::as_leaf casts this pointer to a &LeafNode<K, V>. As promised, the invalid fields are never accessed, but my understanding is that the mere existence of the returned reference constitutes UB because we have an &-pointer to an invalid object.

I don't believe the current compiler will exploit this in any way to actually produce unexpected behaviour (and I can't really think of how it would), but the problem can be seen in MIRI with the following program:

use std::collections::BTreeMap;

fn main() {
    let mut map = BTreeMap::<u8, u8>::new();
    let _ = map.entry(10);
}

which produces the following output under cargo miri:

error[E0080]: constant evaluation error: type validation failed: encountered dangling (not entirely in bounds) reference
    --> /home/apoelstra/.rustup/toolchains/nightly-2018-10-19-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/src/libcore/ptr.rs:2912:9
     |
2912 |         &*self.as_ptr()
     |         ^^^^^^^^^^^^^^^ type validation failed: encountered dangling (not entirely in bounds) reference
     |
note: inside call to `<std::ptr::NonNull<T>><alloc::collections::btree::node::LeafNode<u8, u8>>::as_ref`
    --> /home/apoelstra/.rustup/toolchains/nightly-2018-10-19-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/src/liballoc/collections/btree/node.rs:387:13
     |
387  |             self.node.as_ref()
     |             ^^^^^^^^^^^^^^^^^^
note: inside call to `<alloc::collections::btree::node::NodeRef<BorrowType, K, V, Type>><alloc::collections::btree::node::marker::Immut, u8, u8, alloc::collections::btree::node::marker::LeafOrInternal>::as_leaf`                                                                         --> /home/apoelstra/.rustup/toolchains/nightly-2018-10-19-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/src/liballoc/collections/btree/node.rs:392:9
     |
392  |         self.as_leaf().is_shared_root()
     |         ^^^^^^^^^^^^^^
note: inside call to `<alloc::collections::btree::node::NodeRef<BorrowType, K, V, Type>><alloc::collections::btree::node::marker::Immut, u8, u8, alloc::collections::btree::node::marker::LeafOrInternal>::is_shared_root`
    --> /home/apoelstra/.rustup/toolchains/nightly-2018-10-19-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/src/liballoc/collections/btree/node.rs:191:9
     |
191  |         self.as_ref().is_shared_root()
     |         ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
note: inside call to `<alloc::collections::btree::node::Root<K, V>><u8, u8>::is_shared_root`
    --> /home/apoelstra/.rustup/toolchains/nightly-2018-10-19-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/src/liballoc/collections/btree/map.rs:1175:12
     |
1175 |         if self.root.is_shared_root() {
     |            ^^^^^^^^^^^^^^^^^^^^^^^^^^
note: inside call to `<std::collections::BTreeMap<K, V>><u8, u8>::ensure_root_is_owned`
    --> /home/apoelstra/.rustup/toolchains/nightly-2018-10-19-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/src/liballoc/collections/btree/map.rs:902:9
     |
902  |         self.ensure_root_is_owned(); 
     |         ^^^^^^^^^^^^^^^^^^^^^^^^^^^
note: inside call to `<std::collections::BTreeMap<K, V>><u8, u8>::entry`
    --> src/main.rs:6:13
     |
6    |     let _ = map.entry(10);
<snip>

[eddyb]

but my understanding is that the mere existence of the returned reference constitutes UB because we have an &-pointer to an invalid object

I believe this is the relevant part here: AFAIK it's not decided yet, and it's not UB to LLVM.

cc @RalfJung

[hanna-kruppe]

Duplicate of #54957?

[apoelstra]

Yes, sorry, this is exactly #54957