Sorting Boxes causes Miri to report UB

[theemathas]

This issue was discovered by @orxfun on zulip.

The following code causes Miri to report UB:

fn main() {
    // passes when input is already sorted, for instance when: elem = |i| Box::new(i)
    let len = 100;
    let elem = |i: usize| {
        Box::new(match i.is_multiple_of(2) {
            true => i,
            false => len + i,
        })
    };
    let mut input: Vec<_> = (0..len).map(elem).collect();
    input.sort()
}

Miri error

error: Undefined Behavior: trying to retag from <12657> for SharedReadOnly permission at alloc3398[0x0], but that tag does not exist in the borrow stack for this location
    --> /playground/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/library/alloc/src/boxed.rs:2069:24
     |
2069 |         PartialOrd::lt(&**self, &**other)
     |                        ^^^^^^^ this error occurs as part of retag at alloc3398[0x0..0x8]
     |
     = help: this indicates a potential bug in the program: it performed an invalid operation, but the Stacked Borrows 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
help: <12657> was created by a Unique retag at offsets [0x0..0x8]
    --> src/main.rs:11:5
     |
  11 |     input.sort()
     |     ^^^^^^^^^^^^
help: <12657> was later invalidated at offsets [0x0..0x8] by a SharedReadOnly retag
    --> src/main.rs:11:5
     |
  11 |     input.sort()
     |     ^^^^^^^^^^^^
     = note: stack backtrace:
             0: <std::boxed::Box<usize> as std::cmp::PartialOrd>::lt
                 at /playground/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/library/alloc/src/boxed.rs:2069:24: 2069:31
             1: <for<'a, 'b> fn(&'a std::boxed::Box<usize>, &'b std::boxed::Box<usize>) -> bool {<std::boxed::Box<usize> as std::cmp::PartialOrd>::lt} as std::ops::FnMut<(&std::boxed::Box<usize>, &std::boxed::Box<usize>)>>::call_mut - shim(for<'a, 'b> fn(&'a std::boxed::Box<usize>, &'b std::boxed::Box<usize>) -> bool {<std::boxed::Box<usize> as std::cmp::PartialOrd>::lt})
                 at /playground/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/library/core/src/ops/function.rs:166:5: 166:75
             2: core::slice::sort::stable::quicksort::quicksort::<std::boxed::Box<usize>, for<'a, 'b> fn(&'a std::boxed::Box<usize>, &'b std::boxed::Box<usize>) -> bool {<std::boxed::Box<usize> as std::cmp::PartialOrd>::lt}>
                 at /playground/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/library/core/src/slice/sort/stable/quicksort.rs:57:40: 57:72
             3: core::slice::sort::stable::quicksort::quicksort::<std::boxed::Box<usize>, for<'a, 'b> fn(&'a std::boxed::Box<usize>, &'b std::boxed::Box<usize>) -> bool {<std::boxed::Box<usize> as std::cmp::PartialOrd>::lt}>
                 at /playground/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/library/core/src/slice/sort/stable/quicksort.rs:75:9: 75:61
             4: core::slice::sort::stable::drift::stable_quicksort::<std::boxed::Box<usize>, for<'a, 'b> fn(&'a std::boxed::Box<usize>, &'b std::boxed::Box<usize>) -> bool {<std::boxed::Box<usize> as std::cmp::PartialOrd>::lt}>
                 at /playground/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/library/core/src/slice/sort/stable/drift.rs:270:5: 270:48
             5: core::slice::sort::stable::drift::sort::<std::boxed::Box<usize>, for<'a, 'b> fn(&'a std::boxed::Box<usize>, &'b std::boxed::Box<usize>) -> bool {<std::boxed::Box<usize> as std::cmp::PartialOrd>::lt}>
                 at /playground/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/library/core/src/slice/sort/stable/drift.rs:118:9: 118:46
             6: core::slice::sort::stable::driftsort_main::<std::boxed::Box<usize>, for<'a, 'b> fn(&'a std::boxed::Box<usize>, &'b std::boxed::Box<usize>) -> bool {<std::boxed::Box<usize> as std::cmp::PartialOrd>::lt}, std::vec::Vec<std::boxed::Box<usize>>>
                 at /playground/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/library/core/src/slice/sort/stable/mod.rs:135:5: 135:77
             7: core::slice::sort::stable::sort::<std::boxed::Box<usize>, for<'a, 'b> fn(&'a std::boxed::Box<usize>, &'b std::boxed::Box<usize>) -> bool {<std::boxed::Box<usize> as std::cmp::PartialOrd>::lt}, std::vec::Vec<std::boxed::Box<usize>>>
                 at /playground/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/library/core/src/slice/sort/stable/mod.rs:83:13: 83:53
             8: std::slice::stable_sort::<std::boxed::Box<usize>, for<'a, 'b> fn(&'a std::boxed::Box<usize>, &'b std::boxed::Box<usize>) -> bool {<std::boxed::Box<usize> as std::cmp::PartialOrd>::lt}>
                 at /playground/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/library/alloc/src/slice.rs:861:5: 861:56
             9: std::slice::<impl [std::boxed::Box<usize>]>::sort
                 at /playground/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/library/alloc/src/slice.rs:135:9: 135:33
             10: main
                 at src/main.rs:11:5: 11:17

note: some details are omitted, run with `MIRIFLAGS=-Zmiri-backtrace=full` for a verbose backtrace

Meta

Reproducible on the playground with Miri version 0.1.0 (2026-01-26 474276961f)

[theemathas]

I suspect that this line is constructing a ManuallyDrop<Box<T>> that invalidates the original Box inside the slice. See rust-lang/unsafe-code-guidelines#245 and #118166

rust/library/core/src/slice/sort/stable/quicksort.rs

Line 44 in ebf13cc

let pivot_copy = unsafe { ManuallyDrop::new(ptr::read(&v[pivot_pos])) };

[theemathas]

I'm guessing that this is a regression from #124032. cc @Voultapher @thomcc

[Voultapher]

Can you try with miri tree-borrows?

[theemathas]

Tree borrows reports no UB.

[Voultapher]

So it's probably in the aliasing grey-zone and likely on the this is fine side. But we can probably fix this without too much effort. I'll look into it.

[Voultapher]

Also my understanding is that if Tree Borrows passes LLVM shouldn't produce UB but not sure.