use-after-free in safe code

[Voultapher]

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.

[emilk]

There is drop guards for exactly this case (https://github.com/emilk/drop-merge-sort/blob/master/src/dmsort.rs#L204-L223) but apparently I missed something! I don't really have time to work on this now, sadly.

[Voultapher]

The github statistics say there are ~300 repositories that use this sort implementation. Arguably, chances are quite low for such usage pattern.

I don't really have time to work on this now, sadly.

I fully sympathise with the burden of open source projects. If fixing an unsound implementation is not planned. It's seems worth it to consider deprecating the project and informing users about the issue and lack of maintenance. Especially in the light of recent publications and efforts to improve the Rust standard library sort implementations.