Confused by an exception safety example in Onomicon

The Onomicon has the following:

We would rather have the following:

bubble_up(heap, index):
    let elem = heap[index]
    while index != 0 && elem < heap[parent(index)]:
        heap[index] = heap[parent(index)]
        index = parent(index)
    heap[index] = elem

This code ensures that each element is copied as little as possible (it is in fact necessary that elem be copied twice in general). However it now exposes some exception safety trouble! At all times, there exists two copies of one value. If we panic in this function something will be double-dropped. Unfortunately, we also don't have full control of the code: that comparison is user-defined!

I can't undetstand the mentioned double-drop.
If heap[index] = heap[parent(index)] is a movement, then heap[parent(index)] is uninitiated, so only one drop. If it is a Copy, then T: !Drop, no dropping at all.

That's not true. When you are blindly copying around memory behind raw pointers using ptr::read() and ptr::write(), the compiler can't possibly track initialization state, so there will be a double-drop if there are two copies of the same value. (Proof.)

So that is pseudo code too.

It has to be; the snippet you cited can't be Rust because it isn't even syntactically valid. Also, you have to use raw pointer based methods for this purpose, exactly because you can't otherwise move out of a dereference (safe code forbids that, exactly for this reason).

This topic was automatically closed 90 days after the last reply. We invite you to open a new topic if you have further questions or comments.