Add _heapq module#8059
Open
ShaharNaveh wants to merge 10 commits into
Open
Conversation
Contributor
|
No actionable comments were generated in the recent review. 🎉 ℹ️ Recent review info⚙️ Run configurationConfiguration used: Path: .coderabbit.yml Review profile: CHILL Plan: Pro Run ID: 📒 Files selected for processing (1)
🚧 Files skipped from review as they are similar to previous changes (1)
📝 WalkthroughWalkthroughAdds a Rust-backed ChangesHeap Module Implementation
Sequence DiagramsequenceDiagram
participant Caller
participant heappush
participant siftup
participant PyList
Caller->>heappush: heappush(heap, item)
heappush->>PyList: append item
heappush->>siftup: restore heap invariant
siftup->>PyList: compare & swap using rich_compare_bool
siftup->>heappush: finished
heappush->>Caller: return
Estimated code review effort🎯 4 (Complex) | ⏱️ ~60 minutes Suggested reviewers
Poem
🚥 Pre-merge checks | ✅ 4 | ❌ 1❌ Failed checks (1 warning)
✅ Passed checks (4 passed)
✏️ Tip: You can configure your own custom pre-merge checks in the settings. ✨ Finishing Touches🧪 Generate unit tests (beta)
Thanks for using CodeRabbit! It's free for OSS, and your support helps us grow. If you like it, consider giving us a shout-out. Comment |
Contributor
There was a problem hiding this comment.
Actionable comments posted: 2
🤖 Prompt for all review comments with AI agents
Verify each finding against current code. Fix only still-valid issues, skip the
rest with a brief reason, keep changes minimal, and validate.
Inline comments:
In `@crates/stdlib/src/_heapq.rs`:
- Around line 211-250: In heappushpop, capture the list size before calling
top.rich_compare_bool (e.g., let n = lst.borrow_vec().len()), then after the
rich_compare_bool call re-check the size (lst.borrow_vec().len()) and if it
differs return Err(vm.new_runtime_error("list changed size during comparison"))
to mirror CPython's check; place this check between the rich_compare_bool call
and the subsequent logic that assumes the list size (before proceeding to
swap/borrow_vec_mut() and siftup), referencing the heappushpop function, the
rich_compare_bool invocation, and the use of
lst.borrow_vec()/lst.borrow_vec_mut().
- Around line 477-516: In heappushpop_max, after calling
item.rich_compare_bool(&top, PyComparisonOp::Lt, vm) re-check the heap size
because the comparison may execute Python code that mutates the list;
specifically, after the cmp is computed, re-borrow the list/vector and if it is
now empty return item (mirroring the min-heap heappushpop fix), otherwise
refresh the current top element or ensure correct behavior before proceeding to
replace vec[0], then continue with the existing replacement and siftup_max call.
🪄 Autofix (Beta)
Fix all unresolved CodeRabbit comments on this PR:
- Push a commit to this branch (recommended)
- Create a new PR with the fixes
ℹ️ Review info
⚙️ Run configuration
Configuration used: Path: .coderabbit.yml
Review profile: CHILL
Plan: Pro
Run ID: c19e0ae4-3550-4c74-8a04-700bb83e10d1
📒 Files selected for processing (2)
crates/stdlib/src/_heapq.rscrates/stdlib/src/lib.rs
Comment on lines
+211
to
+250
| #[pyfunction] | ||
| fn heappushpop( | ||
| heap: PyObjectRef, | ||
| item: PyObjectRef, | ||
| vm: &VirtualMachine, | ||
| ) -> PyResult<PyObjectRef> { | ||
| let lst = heap.downcast::<PyList>().map_err(|obj| { | ||
| vm.new_type_error(format!( | ||
| "heappushpop() argument 1 must be list, not {}", | ||
| obj.class().name() | ||
| )) | ||
| })?; | ||
|
|
||
| let top = { | ||
| let vec = lst.borrow_vec(); | ||
| match vec.first() { | ||
| Some(v) => v.clone(), | ||
| None => return Ok(item), | ||
| } | ||
| }; | ||
|
|
||
| let cmp = top.rich_compare_bool(&item, PyComparisonOp::Lt, vm)?; | ||
| if !cmp { | ||
| return Ok(item); | ||
| } | ||
|
|
||
| let returnitem = { | ||
| let mut vec = lst.borrow_vec_mut(); | ||
| let root = match vec.first() { | ||
| Some(v) => v.clone(), | ||
| None => return Err(vm.new_index_error("index out of range")), | ||
| }; | ||
|
|
||
| vec[0] = item; | ||
| root | ||
| }; | ||
|
|
||
| siftup(&lst, 0, vm)?; | ||
| Ok(returnitem) | ||
| } |
Contributor
There was a problem hiding this comment.
Missing size change check after comparison.
The rich_compare_bool call (line 232) invokes user code that could modify the list. CPython's heappushpop checks for size change after comparison before proceeding:
if (n != PyList_GET_SIZE(heap)) {
PyErr_SetString(PyExc_RuntimeError, "list changed size during iteration");
return NULL;
}Without this check, if the list is modified during comparison, subsequent operations may behave unexpectedly.
🔧 Proposed fix
+ let size = lst.__len__();
let cmp = top.rich_compare_bool(&item, PyComparisonOp::Lt, vm)?;
+ if size != lst.__len__() {
+ return Err(vm.new_runtime_error("list changed size during iteration"));
+ }
if !cmp {
return Ok(item);
}🤖 Prompt for AI Agents
Verify each finding against current code. Fix only still-valid issues, skip the
rest with a brief reason, keep changes minimal, and validate.
In `@crates/stdlib/src/_heapq.rs` around lines 211 - 250, In heappushpop, capture
the list size before calling top.rich_compare_bool (e.g., let n =
lst.borrow_vec().len()), then after the rich_compare_bool call re-check the size
(lst.borrow_vec().len()) and if it differs return Err(vm.new_runtime_error("list
changed size during comparison")) to mirror CPython's check; place this check
between the rich_compare_bool call and the subsequent logic that assumes the
list size (before proceeding to swap/borrow_vec_mut() and siftup), referencing
the heappushpop function, the rich_compare_bool invocation, and the use of
lst.borrow_vec()/lst.borrow_vec_mut().
Comment on lines
+477
to
+516
| #[pyfunction] | ||
| fn heappushpop_max( | ||
| heap: PyObjectRef, | ||
| item: PyObjectRef, | ||
| vm: &VirtualMachine, | ||
| ) -> PyResult<PyObjectRef> { | ||
| let lst = heap.downcast::<PyList>().map_err(|obj| { | ||
| vm.new_type_error(format!( | ||
| "heappushpop_max() argument 1 must be list, not {}", | ||
| obj.class().name() | ||
| )) | ||
| })?; | ||
|
|
||
| let top = { | ||
| let vec = lst.borrow_vec(); | ||
| match vec.first() { | ||
| Some(v) => v.clone(), | ||
| None => return Ok(item), | ||
| } | ||
| }; | ||
|
|
||
| let cmp = item.rich_compare_bool(&top, PyComparisonOp::Lt, vm)?; | ||
| if !cmp { | ||
| return Ok(item); | ||
| } | ||
|
|
||
| let returnitem = { | ||
| let mut vec = lst.borrow_vec_mut(); | ||
| let root = match vec.first() { | ||
| Some(v) => v.clone(), | ||
| None => return Err(vm.new_index_error("index out of range")), | ||
| }; | ||
|
|
||
| vec[0] = item; | ||
| root | ||
| }; | ||
|
|
||
| siftup_max(&lst, 0, vm)?; | ||
| Ok(returnitem) | ||
| } |
Contributor
There was a problem hiding this comment.
Missing size change check after comparison (same issue as min-heap variant).
Consistent with the min-heap heappushpop, the max-heap variant also lacks a size-change check after rich_compare_bool (line 498).
🔧 Proposed fix
+ let size = lst.__len__();
let cmp = item.rich_compare_bool(&top, PyComparisonOp::Lt, vm)?;
+ if size != lst.__len__() {
+ return Err(vm.new_runtime_error("list changed size during iteration"));
+ }
if !cmp {
return Ok(item);
}🤖 Prompt for AI Agents
Verify each finding against current code. Fix only still-valid issues, skip the
rest with a brief reason, keep changes minimal, and validate.
In `@crates/stdlib/src/_heapq.rs` around lines 477 - 516, In heappushpop_max,
after calling item.rich_compare_bool(&top, PyComparisonOp::Lt, vm) re-check the
heap size because the comparison may execute Python code that mutates the list;
specifically, after the cmp is computed, re-borrow the list/vector and if it is
now empty return item (mirroring the min-heap heappushpop fix), otherwise
refresh the current top element or ensure correct behavior before proceeding to
replace vec[0], then continue with the existing replacement and siftup_max call.
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
1 participant
Add this suggestion to a batch that can be applied as a single commit.This suggestion is invalid because no changes were made to the code.Suggestions cannot be applied while the pull request is closed.Suggestions cannot be applied while viewing a subset of changes.Only one suggestion per line can be applied in a batch.Add this suggestion to a batch that can be applied as a single commit.Applying suggestions on deleted lines is not supported.You must change the existing code in this line in order to create a valid suggestion.Outdated suggestions cannot be applied.This suggestion has been applied or marked resolved.Suggestions cannot be applied from pending reviews.Suggestions cannot be applied on multi-line comments.Suggestions cannot be applied while the pull request is queued to merge.Suggestion cannot be applied right now. Please check back later.
Summary
Summary by CodeRabbit
New Features
Bug Fixes