`binary_heap::PeekMut` does not need "leak amplification"

[cpud36]

Context

The BinaryHeap from alloc crate has handy method peek_mut, which allows to look at the top element in the heap, and possible mutate it, without removing it from the heap. This mutation however can alter the element order relative to other elements, and the heap needs to be adjusted. To handle this, the PeekMut tracks if it has ever exposed a &mut T access via DerefMut. If &mut T was ever exposed, PeekMut adjusts the heap in its Drop implementation.

Leak amplification

This works well, unless the user leaks the PeekMut(e.g. via mem::forget, or via Rc cycle). Then the Drop of PeekMut never runs and we get the heap with an incorrect ordering of elements.

To cope with this possible leakage, the PeekMut uses a well-known technique called "leak amplification". That is, PeekMut uses Vec::set_len to forget about all other elements in the heap, when first &mut T is acquired, and then restores vector len when drop is run. So if the user leaks the PeekMut, we still have the valid heap (although, it has only 1 element - all others were forgotten forever).

This change was introduced in commit aedb756.

Problem

The "leak amplification" technique is inteded to avoid memory corruption. It is often used when the type creates temporary holes in the container. Thus, forgetting to fixup those holes might lead to double free, or use after free. In other words, leak amplification is used to make the code sound, not to make it logically correct.

However BinaryHeap soundness does not depend on correctness of element ordering. BinaryHeap will continue to be sound(that is no memory issues), even the elements in the underlying vector get shuffled in arbitrary way. This is easy to see, as there can be an incorrect Ord implementation; or users can use interior mutability to break the heap ordering.

The data structure will not work logically correct in such case, but it is the question of which correctness property we are willing to sacrafice: ordering of the elements or elements leakage.

Proposal

I propose to rollback the before mentioned commit and ignore the leakage problem in the PeekMut.

[hanna-kruppe]

The PR that introduced the behavior you want to roll back (#105851) describes the reason for doing it and the team accepted this via FCP. At minimum, you’ll have to engage with the arguments brought up then for this proposal to have any chance. But since the BinaryHeap documentation has been making this guarantee for quite some time, your proposal would also break backwards compatibility:

As long as no elements change their relative order while being in the heap as described above, the API of BinaryHeap guarantees that the heap invariant remains intact i.e. its methods all behave as documented. For example if a method is documented as iterating in sorted order, that’s guaranteed to work as long as elements in the heap have not changed order, even in the presence of closures getting unwinded out of, iterators getting leaked, and similar foolishness.

[workingjubilee]

I am closing this for the reasons described by Hanna: it's not a serious proposal if it doesn't engage with the prior discussion, and in general we try to minimize entertaining feature requests on the issue tracker unless they are implicitly addressing something we would consider a bug. This is not because we do not like enhancing the language, but rather because "somewhere in the mire of the issue tracker" is a bad place to ask for an enhancement, as it may only get your issue noticed by wandering ghouls like me.