miri test failure for `iter_mut`

[Takashiidobe]

I think I've found a test error under miri. Here's the test (it doesn't matter which queue you use).

After you drop the iterator, changing the priority rebuilds the heap, which isn't sound because you have a mutable reference into the heap (_item, prio) after dropping the iterator, that you can use.

#[test]
fn double_priority_queue_drop_rebuild_ub() {
    let mut pq = DoublePriorityQueue::new();
    pq.push("a", 1);
    pq.push("b", 2);

    let mut iter = pq.iter_mut();
    let (_item, prio) = iter.next().unwrap();

    drop(iter);

    *prio = 3;
    assert_eq!(prio, &mut 3);
}

This passes fine with cargo test.

When running through miri though:

MIRIFLAGS=-Zmiri-backtrace=full cargo +nightly miri test priority_queue_drop_rebuild_ub -- --nocapture

produces this backtrace:

test double_priority_queue_drop_rebuild_ub ... error: Undefined Behavior: attempting a write access using <143067> at alloc43918[0x18], but that tag does not exist in the borrow stack for this location
   --> tests/iter_mut_miri.rs:14:5
    |
 14 |     *prio = 3;
    |     ^^^^^^^^^ this error occurs as part of an access at alloc43918[0x18..0x1c]
    |
    = 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: <143067> was created by a Unique retag at offsets [0x18..0x1c]
   --> tests/iter_mut_miri.rs:10:17
    |
 10 |     let (_item, prio) = iter.next().unwrap();
    |                 ^^^^
help: <143067> was later invalidated at offsets [0x0..0x40] by a SharedReadOnly retag
   --> /home/takashi/2025/priority-queue/src/double_priority_queue/mod.rs:894:21
    |
894 | /                     self.store
895 | |                         .map
896 | |                         .get_index(index.0)
    | |___________________________________________^
    = note: BACKTRACE (of the first span) on thread `double_priority`:
    = note: inside `double_priority_queue_drop_rebuild_ub` at tests/iter_mut_miri.rs:14:5: 14:14
note: inside closure

I think this is due to there being two mutable borrows here: one across the entire container with iter_mut, and then one after calling next on the iter_mut that can outlive the original container, and then the drop calling heap_build, which mutates the whole structure under the iter_mut itself. You shouldn't be able to call heap_build while there are mutable references to the original container.

[garro95]

Thank you for your analysis that is absolutely correct.

One of the tests I added in the last commit already highlighted that issue, and for that reason I did not release a new version, but I could not identify the root cause.

Unfortunately it seems there is no easy solution, given the Iterator trait definition in std.