Tracking Issue for binary heap retain #71503
Comments
|
We discussed this at the recent Libs meeting and had a question about taking If anybody is keen to open a stabilization PR we can kick off a FCP! |
Improve rebuilding behaviour of BinaryHeap::retain. This changes `BinaryHeap::retain` such that it doesn't always fully rebuild the heap, but only rebuilds the parts for which that's necessary. This makes use of the fact that retain gives out `&T`s and not `&mut T`s. Retaining every element or removing only elements at the end results in no rebuilding at all. Retaining most elements results in only reordering the elements that got moved (those after the first removed element), using the same logic as was already used for `append`. cc `@KodrAus` `@sfackler` - We briefly discussed this possibility in the meeting last week while we talked about stabilization of this function (rust-lang#71503).
Improve rebuilding behaviour of BinaryHeap::retain. This changes `BinaryHeap::retain` such that it doesn't always fully rebuild the heap, but only rebuilds the parts for which that's necessary. This makes use of the fact that retain gives out `&T`s and not `&mut T`s. Retaining every element or removing only elements at the end results in no rebuilding at all. Retaining most elements results in only reordering the elements that got moved (those after the first removed element), using the same logic as was already used for `append`. cc `@KodrAus` `@sfackler` - We briefly discussed this possibility in the meeting last week while we talked about stabilization of this function (rust-lang#71503).
@rust-lang/libs-api May I ask to kick off a FCP? Stabilizing it will unblock rust-lang/rust-clippy#9059. |
|
@rfcbot fcp merge |
|
Team member @Amanieu has proposed to merge this. The next step is review by the rest of the tagged team members: Concerns:
Once a majority of reviewers approve (and at most 2 approvals are outstanding), this will enter its final comment period. If you spot a major issue that hasn't been raised at any point in this process, please speak up! See this document for info about what commands tagged team members can give me. |
|
I think we should change the API to either:
I personally prefer the first option: @rfcbot concern &mut |
Sounds good, should it be addressed in a stabilization PR or done before it? |
|
This can be addressed in the stabilization PR but we do need to make a decision here. |
Agreed. |
|
Agreed: let's make it |
|
It seems we have a consensus to make @rfcbot resolve &mut |
|
I don't think this is right. As I understand it, a A |
|
(This is unlike |
This is currently nightly-only and is blocked on an unresolved API question: rust-lang/rust#71503
Leak amplification for peek_mut() to ensure BinaryHeap's invariant is always met In the libs-api team's discussion around rust-lang#104210, some of the team had hesitations around exposing malformed BinaryHeaps of an element type whose Ord and Drop impls are trusted, and which does not contain interior mutability. For example in the context of this kind of code: ```rust use std::collections::BinaryHeap; use std::ops::Range; use std::slice; fn main() { let slice = &mut ['0', '1', '2', '3', '4', '5', '6', '7', '8', '9']; let cut_points = BinaryHeap::from(vec![4, 2, 7]); println!("{:?}", chop(slice, cut_points)); } // This is a souped up slice::split_at_mut to split in arbitrary many places. // // usize's Ord impl is trusted, so 1 single bounds check guarantees all those // output slices are non-overlapping and in-bounds fn chop<T>(slice: &mut [T], mut cut_points: BinaryHeap<usize>) -> Vec<&mut [T]> { let mut vec = Vec::with_capacity(cut_points.len() + 1); let max = match cut_points.pop() { Some(max) => max, None => { vec.push(slice); return vec; } }; assert!(max <= slice.len()); let len = slice.len(); let ptr: *mut T = slice.as_mut_ptr(); let get_unchecked_mut = unsafe { |range: Range<usize>| &mut *slice::from_raw_parts_mut(ptr.add(range.start), range.len()) }; vec.push(get_unchecked_mut(max..len)); let mut end = max; while let Some(start) = cut_points.pop() { vec.push(get_unchecked_mut(start..end)); end = start; } vec.push(get_unchecked_mut(0..end)); vec } ``` ```console [['7', '8', '9'], ['4', '5', '6'], ['2', '3'], ['0', '1']] ``` In the current BinaryHeap API, `peek_mut()` is the only thing that makes the above function unsound. ```rust let slice = &mut ['0', '1', '2', '3', '4', '5', '6', '7', '8', '9']; let mut cut_points = BinaryHeap::from(vec![4, 2, 7]); { let mut max = cut_points.peek_mut().unwrap(); *max = 0; std::mem::forget(max); } println!("{:?}", chop(slice, cut_points)); ``` ```console [['0', '1', '2', '3', '4', '5', '6', '7', '8', '9'], [], ['2', '3'], ['0', '1']] ``` Or worse: ```rust let slice = &mut ['0', '1', '2', '3', '4', '5', '6', '7', '8', '9']; let mut cut_points = BinaryHeap::from(vec![100, 100]); { let mut max = cut_points.peek_mut().unwrap(); *max = 0; std::mem::forget(max); } println!("{:?}", chop(slice, cut_points)); ``` ```console [['0', '1', '2', '3', '4', '5', '6', '7', '8', '9'], [], ['0', '1', '2', '3', '4', '5', '6', '7', '8', '9', '\u{1}', '\0', '?', '翾', '?', '翾', '\0', '\0', '?', '翾', '?', '翾', '?', '啿', '?', '啿', '?', '啿', '?', '啿', '?', '啿', '?', '翾', '\0', '\0', '', '啿', '\u{5}', '\0', '\0', '\0', '\0', '\0', '\0', '\0', '\0', '\0', '\0', '\0', '\0', '\0', '\u{8}', '\0', '`@',` '\0', '\u{1}', '\0', '?', '翾', '?', '翾', '?', '翾', ' thread 'main' panicked at 'index out of bounds: the len is 33 but the index is 33', library/core/src/unicode/unicode_data.rs:319:9 note: run with `RUST_BACKTRACE=1` environment variable to display a backtrace ``` --- This PR makes `peek_mut()` use leak amplification (https://doc.rust-lang.org/1.66.0/nomicon/leaking.html#drain) to preserve the heap's invariant even in the situation that `PeekMut` gets leaked. I'll also follow up in the tracking issue of unstable `drain_sorted()` (rust-lang#59278) and `retain()` (rust-lang#71503).
|
@rfcbot concern predicate panic can leave heap in invalid state #105851 introduced an invariant that BinaryHeap methods are required to abide by. The current implementation of #![feature(binary_heap_retain)]
use std::collections::BinaryHeap;
use std::panic::{self, AssertUnwindSafe};
fn main() {
let mut heap = BinaryHeap::from_iter([3, 1, 2]);
println!("heap={:?}", heap);
panic::catch_unwind(AssertUnwindSafe(|| {
heap.retain(|e| {
if *e == 1 {
panic!();
}
false
});
}));
println!("heap={:?}", heap);
println!("sorted={:?}", heap.into_sorted_vec());
}This prints |
|
I'm marking yaahc's box because she has stepped down from T-libs-api after the point that this feature got proposed for FCP. This can enter FCP as soon as the predicate panic concern is addressed. |
Rebuild BinaryHeap on unwind from retain This closes the hole identified in rust-lang#71503 (comment) which had made it possible for the caller to end up with a heap in invalid state. As of rust-lang#105851, heaps in invalid state are not supposed to exist.
Rebuild BinaryHeap on unwind from retain This closes the hole identified in rust-lang#71503 (comment) which had made it possible for the caller to end up with a heap in invalid state. As of rust-lang#105851, heaps in invalid state are not supposed to exist.
Rebuild BinaryHeap on unwind from retain This closes the hole identified in rust-lang/rust#71503 (comment) which had made it possible for the caller to end up with a heap in invalid state. As of #105851, heaps in invalid state are not supposed to exist.
|
It looks like #106918 fixed the predicate panic issue - can this now enter FCP? |
|
🔔 This is now entering its final comment period, as per the review above. 🔔 |
|
The final comment period, with a disposition to merge, as per the review above, is now complete. As the automated representative of the governance process, I would like to thank the author for their work and everyone else who contributed. This will be merged soon. |
FCP finished in tracking issue: rust-lang#71503
…nton Stabilize `binary_heap_retain` FCP finished in tracking issue: rust-lang#71503
Rebuild BinaryHeap on unwind from retain This closes the hole identified in rust-lang/rust#71503 (comment) which had made it possible for the caller to end up with a heap in invalid state. As of #105851, heaps in invalid state are not supposed to exist.
This is a tracking issue for
BinaryHeap::retain.The feature gate for the issue is
#![feature(binary_heap_retain)].Added in PR #71485
The text was updated successfully, but these errors were encountered: