Miri failure in btree::map::test_iter_min_max test

[RalfJung]

btree::map::test_iter_min_max recently started failing in Miri:

error: Undefined Behavior: not granting access to tag <untagged> because incompatible item is protected: [Unique for <26146034> (call 7514376)]

   --> /home/travis/build/RalfJung/miri-test-libstd/rust-src-patched/src/libcore/ptr/non_null.rs:121:9

    |

121 |         &*self.as_ptr()

    |         ^^^^^^^^^^^^^^^ not granting access to tag <untagged> because incompatible item is protected: [Unique for <26146034> (call 7514376)]

    |

    = 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::ptr::NonNull::<alloc::collections::btree::node::LeafNode<i32, i32>>::as_ref` at /home/travis/build/RalfJung/miri-test-libstd/rust-src-patched/src/libcore/ptr/non_null.rs:121:9

    = note: inside `alloc::collections::btree::node::NodeRef::<alloc::collections::btree::node::marker::Mut, i32, i32, alloc::collections::btree::node::marker::LeafOrInternal>::as_leaf` at /home/travis/build/RalfJung/miri-test-libstd/rust-src-patched/src/liballoc/collections/btree/node.rs:321:18

    = note: inside `alloc::collections::btree::node::NodeRef::<alloc::collections::btree::node::marker::Mut, i32, i32, alloc::collections::btree::node::marker::LeafOrInternal>::len` at /home/travis/build/RalfJung/miri-test-libstd/rust-src-patched/src/liballoc/collections/btree/node.rs:293:9

    = note: inside `alloc::collections::btree::node::Handle::<alloc::collections::btree::node::NodeRef<alloc::collections::btree::node::marker::Mut, i32, i32, alloc::collections::btree::node::marker::LeafOrInternal>, alloc::collections::btree::node::marker::Edge>::new_edge` at /home/travis/build/RalfJung/miri-test-libstd/rust-src-patched/src/liballoc/collections/btree/node.rs:802:30

    = note: inside `alloc::collections::btree::node::Handle::<alloc::collections::btree::node::NodeRef<alloc::collections::btree::node::marker::Mut, i32, i32, alloc::collections::btree::node::marker::Leaf>, alloc::collections::btree::node::marker::Edge>::forget_node_type` at /home/travis/build/RalfJung/miri-test-libstd/rust-src-patched/src/liballoc/collections/btree/node.rs:1361:18

    = note: inside `alloc::collections::btree::navigate::<impl alloc::collections::btree::node::Handle<alloc::collections::btree::node::NodeRef<alloc::collections::btree::node::marker::Mut, i32, i32, alloc::collections::btree::node::marker::Leaf>, alloc::collections::btree::node::marker::Edge>>::next_kv` at /home/travis/build/RalfJung/miri-test-libstd/rust-src-patched/src/liballoc/collections/btree/navigate.rs:16:24

    = note: inside closure at /home/travis/build/RalfJung/miri-test-libstd/rust-src-patched/src/liballoc/collections/btree/navigate.rs:132:26

    = note: inside `alloc::collections::btree::navigate::replace::<alloc::collections::btree::node::Handle<alloc::collections::btree::node::NodeRef<alloc::collections::btree::node::marker::Mut, i32, i32, alloc::collections::btree::node::marker::Leaf>, alloc::collections::btree::node::marker::Edge>, alloc::collections::btree::node::Handle<alloc::collections::btree::node::NodeRef<alloc::collections::btree::node::marker::Mut, i32, i32, alloc::collections::btree::node::marker::LeafOrInternal>, alloc::collections::btree::node::marker::KV>, [closure@alloc::collections::btree::navigate::<impl alloc::collections::btree::node::Handle<alloc::collections::btree::node::NodeRef<alloc::collections::btree::node::marker::Mut<'a>, K, V, alloc::collections::btree::node::marker::Leaf>, alloc::collections::btree::node::marker::Edge>>::next_unchecked::{{closure}}#0]>` at /home/travis/build/RalfJung/miri-test-libstd/rust-src-patched/src/liballoc/collections/btree/navigate.rs:88:28

    = note: inside `alloc::collections::btree::navigate::<impl alloc::collections::btree::node::Handle<alloc::collections::btree::node::NodeRef<alloc::collections::btree::node::marker::Mut, i32, i32, alloc::collections::btree::node::marker::Leaf>, alloc::collections::btree::node::marker::Edge>>::next_unchecked` at /home/travis/build/RalfJung/miri-test-libstd/rust-src-patched/src/liballoc/collections/btree/navigate.rs:131:22

    = note: inside `std::collections::btree_map::RangeMut::<i32, i32>::next_unchecked` at /home/travis/build/RalfJung/miri-test-libstd/rust-src-patched/src/liballoc/collections/btree/map.rs:1904:18

    = note: inside `<std::collections::btree_map::IterMut<i32, i32> as std::iter::Iterator>::next` at /home/travis/build/RalfJung/miri-test-libstd/rust-src-patched/src/liballoc/collections/btree/map.rs:1457:35

    = note: inside `<std::collections::btree_map::ValuesMut<i32, i32> as std::iter::Iterator>::next` at /home/travis/build/RalfJung/miri-test-libstd/rust-src-patched/src/liballoc/collections/btree/map.rs:1810:9

    = note: inside `<std::collections::btree_map::ValuesMut<i32, i32> as std::iter::Iterator>::fold::<&mut i32, [closure@std::iter::Iterator::min_by::fold::{{closure}}#0 0:for<'r, 's> fn(&'r &mut i32, &'s &mut i32) -> std::cmp::Ordering {<&mut i32 as std::cmp::Ord>::cmp}]>` at /home/travis/build/RalfJung/miri-test-libstd/rust-src-patched/src/libcore/iter/traits/iterator.rs:2021:29

    = note: inside `<std::collections::btree_map::ValuesMut<i32, i32> as std::iter::Iterator>::fold_first::<[closure@std::iter::Iterator::min_by::fold::{{closure}}#0 0:for<'r, 's> fn(&'r &mut i32, &'s &mut i32) -> std::cmp::Ordering {<&mut i32 as std::cmp::Ord>::cmp}]>` at /home/travis/build/RalfJung/miri-test-libstd/rust-src-patched/src/libcore/iter/traits/iterator.rs:2061:14

    = note: inside `<std::collections::btree_map::ValuesMut<i32, i32> as std::iter::Iterator>::min_by::<for<'r, 's> fn(&'r &mut i32, &'s &mut i32) -> std::cmp::Ordering {<&mut i32 as std::cmp::Ord>::cmp}>` at /home/travis/build/RalfJung/miri-test-libstd/rust-src-patched/src/libcore/iter/traits/iterator.rs:2627:9

    = note: inside `<std::collections::btree_map::ValuesMut<i32, i32> as std::iter::Iterator>::min` at /home/travis/build/RalfJung/miri-test-libstd/rust-src-patched/src/libcore/iter/traits/iterator.rs:2499:9

note: inside `btree::map::test_iter_min_max` at alloc_miri_test/../liballoc/tests/btree/map.rs:343:16

   --> alloc_miri_test/../liballoc/tests/btree/map.rs:343:16

    |

343 |     assert_eq!(a.values_mut().min(), Some(&mut 24));

    |                ^^^^^^^^^^^^^^^^^^^^

note: inside closure at alloc_miri_test/../liballoc/tests/btree/map.rs:313:1

   --> alloc_miri_test/../liballoc/tests/btree/map.rs:313:1

    |

313 | / fn test_iter_min_max() {

314 | |     let mut a = BTreeMap::new();

315 | |     assert_eq!(a.iter().min(), None);

316 | |     assert_eq!(a.iter().max(), None);

...   |

344 | |     assert_eq!(a.values_mut().max(), Some(&mut 42));

345 | | }

    | |_^

(Sorry for the bad spacing, Travis logs are like that...)

[RalfJung]

I suspect this is caused by #73627

[ssomers]

Oops, I forgot about Miri while testing. But it baffles me that it fails.

[ssomers]

More accurately, the recent test never succeeded (under Miri). The failing part is unrelated to the main change in #73627, I just added lines for the iterators values and values_mut (which are not in ascending order so couldn't be optimized) to cover more iterators. And it turns out the default implementation of min and max does not play nice for these iterators. A line a.values_mut().max(); added to the old test case test_values_mut in rust e093b65 (the base of #73627) fails similarly.

So what next? I could take out these testing lines from #73627 since they're not directly related to the change, create a new test case, but will probably not understand what is wrong.

PS it's only values_mut that suffers, not values.
PS2 it's not values_mut per sé, a.iter_mut().map(|(_,v)| v).min() suffers the same fate
PS3 it only happens with at least 2 elements iterated

[RalfJung]

@ssomers could you share an MRE demonstrating the problem, ideally unrelated to your changes? Then I can investigate.

[ssomers]

#[test]
fn test_iter_mut_map_min() {
    let mut a = BTreeMap::new();
    a.insert(1, 1);
    a.insert(2, 2);
    a.iter_mut().map(|(_,v)| v).min();
}

[ssomers]

Nope, that was not minimal. It fails even without the map.
PS Which is what the new test tests earlier, but then it succeeds, because the optimization replaces the failing default implementation.

[RalfJung]

This seems to pass Miri on the playground though?

fn main() {
    let mut a = std::collections::BTreeMap::new();
    a.insert(1, 1);
    a.insert(2, 2);
    a.iter_mut().min();
}

This fails:

fn main() {
    let mut a = std::collections::BTreeMap::new();
    a.insert(1, 1);
    a.insert(2, 2);
    a.iter_mut().map(|(_,v)| v).min();
}

So I'll make that the one to investigate. Thanks!

[ssomers]

I think it succeeds on playground because #73627 is already on there and that inadvertently fixed IterMut::min. It succeeds on playground's beta too, so the actual bug must be recent.

[RalfJung]

Miri is nightly-only. The stable/beta/nightly selection in the left has no effect at all on the tools menu.

[RalfJung]

The protector that is being violates is of fold:

    fn fold<B, F>(mut self, init: B, mut f: F) -> B
    where
        Self: Sized,
        F: FnMut(B, Self::Item) -> B,

B is &mut i32, so I believe that is the reference on whose toe something is stepping here.

The conflict is from this call to len:

rust/src/liballoc/collections/btree/node.rs

Line 816 in 9491f18

if self.idx < self.node.len() {

This calls as_leaf(), and that creates an &LeafNode which overlaps with a mutable reference that was previously handed out by the iterator.

[RalfJung]

Fixing len to avoid creating a reference is easy, but not sufficient. The next conflict is caused by

rust/src/liballoc/collections/btree/node.rs

Line 511 in 9491f18

slice::from_raw_parts_mut(MaybeUninit::first_ptr_mut(&mut (*leaf).vals), len)

Something seems to be very fundamentally wrong here: that code is creating a slice covering all keys and values, but this happens during iteration where the user also has access to some of these keys and/or values!