Here, this crate causes UB by "Producing an invalid value". Concretely, it creates an arbitrary T with mem::uninitialized(). In the near future the call to mem::uninitialized() will panic to avoid UB, and our crater run determined that this crate will be affected.

mem::uninitialized() is deprecated since Rust 1.39. The intended replacement is MaybeUninit, which tracks the possibility of uninitialized values at the type level to make sure the compiler does not make any false assumptions.

Hi, I've recently been doing research on sort implementations and noticed that dmsort exhibits stacked borrow violations when sorting random inputs. It should be relatively easy to reproduce by sorting a random set of numbers using miri. If you want you can reuse my project to reproduce it, https://github.com/Voultapher/sort-research-rs change the the test_sort line in tests/main.rs to use sort_comp::unstable::rust_dmsort as test_sort; and run it with MIRIFLAGS='-Zmiri-permissive-provenance' cargo +nightly miri t --features=emilk_dmsort -- --exact random.

Update: The code passes the test suite with Tree Borrows, so whether or not that is a "real" issue remains to be seen.

Running this program via RUSTFLAGS=-Zsanitizer=address cargo run yields a use-after-free with dmsort:

use std::cell::Cell;

fn main() {
    struct ValWithBox {
        val: i32,
        heap_val: Cell<Option<Box<str>>>,
    }

    let pattern = [
        19, 25, 3, 23, 27, 17, 24, 21, 5, 22, 16, 12, 6, 7, 20, 15, 18, 14, 10, 9, 0, 2, 4, 11, 8,
        28, 29, 1, 26, 13,
    ];
    let comp_panic_count = 24;

    let mut test_input = pattern
        .iter()
        .map(|val| ValWithBox {
            val: *val,
            heap_val: Cell::new(Some(
                "some test heap string xxxx".to_string().into_boxed_str(),
            )),
        })
        .collect::<Vec<_>>();

    let mut comp_count = 0;
    dmsort::sort_by(&mut test_input, |a, b| {
        if comp_count == comp_panic_count {
            a.heap_val.set(None);
            b.heap_val.set(None);
            panic!();
        }
        comp_count += 1;

        a.val.cmp(&b.val)
    });
}

In one or more places dmsort seems to use auxiliary memory, using said memory to feed the user-provided comparison function, but fails to copy this memory back into the user-provided slice if the comparison panics. These problems can probably be solved with drop guards. I discovered this problem running this test https://github.com/Voultapher/sort-research-rs/blob/main/tests/main.rs#L793.