Panic safety issue in `PriorityQueue::bubble_up` causes out-of-bounds accesses

[Shnatsel]

PriorityQueue::bubble_up moves ancestors down before writing the bubbling element into its final slot. If Ord::cmp panics after one of those moves, safe catch_unwind can observe a queue where heap no longer contains the element and qp still points at its old slot. Removing the duplicated ancestor then leaves a stale out-of-bounds position, which a later change_priority passes to unchecked indexing in up_heapify.

Steps to reproduce

Add these contents to tests/memory_safety.rs and run MIRIFLAGS=-Zmiri-tree-borrows cargo +nightly miri test --release priority_queue_ord_panic_during_bubble_up_corrupts_qp_position

mod memory_safety {
    use priority_queue::PriorityQueue;
    use std::cell::Cell;
    use std::cmp::Ordering;
    use std::panic::{catch_unwind, AssertUnwindSafe};

    #[derive(Clone, Copy, Debug, Eq, PartialEq)]
    struct PanicOrd(i32);

    thread_local! {
        static COMPARISONS_BEFORE_PANIC: Cell<Option<usize>> = const { Cell::new(None) };
    }

    impl PanicOrd {
        fn panic_after_successful_comparisons(count: usize) {
            COMPARISONS_BEFORE_PANIC.with(|remaining| remaining.set(Some(count)));
        }

        fn disable_panics() {
            COMPARISONS_BEFORE_PANIC.with(|remaining| remaining.set(None));
        }
    }

    impl Ord for PanicOrd {
        fn cmp(&self, other: &Self) -> Ordering {
            COMPARISONS_BEFORE_PANIC.with(|remaining| {
                if let Some(count) = remaining.get() {
                    if count == 0 {
                        panic!("intentional comparison panic");
                    }
                    remaining.set(Some(count - 1));
                }
            });

            self.0.cmp(&other.0)
        }
    }

    impl PartialOrd for PanicOrd {
        fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
            Some(self.cmp(other))
        }
    }

    #[test]
    fn priority_queue_ord_panic_during_bubble_up_corrupts_qp_position() {
        // Issue: `PriorityQueue::bubble_up` moves ancestors down before writing the bubbling
        // element into its final slot. If `Ord::cmp` panics after one of those moves, safe
        // `catch_unwind` can observe a queue where `heap` no longer contains the element and
        // `qp` still points at its old slot. Removing the duplicated ancestor then leaves a
        // stale out-of-bounds position, which a later `change_priority` passes to unchecked
        // indexing in `up_heapify`.
        let mut queue = PriorityQueue::new();
        queue.push(0, PanicOrd(100));
        queue.push(1, PanicOrd(90));
        queue.push(2, PanicOrd(80));
        queue.push(3, PanicOrd(70));

        PanicOrd::panic_after_successful_comparisons(1);
        let result = catch_unwind(AssertUnwindSafe(|| {
            queue.change_priority(&3, PanicOrd(200));
        }));
        assert!(result.is_err());
        PanicOrd::disable_panics();

        assert_eq!(queue.remove(&1).map(|(item, _)| item), Some(1));
        let _ = queue.change_priority(&3, PanicOrd(50));
    }
}