Skip to content

Track deque mutations and release removed items outside locks - #8847

Merged
youknowone merged 1 commit into
RustPython:mainfrom
1ndahous3:deque_remove_mutation
Sep 27, 2026
Merged

youknowone merged 1 commit into
RustPython:mainfrom
1ndahous3:deque_remove_mutation

Conversation

@1ndahous3

@1ndahous3 1ndahous3 commented Sep 26, 2026 •

Copy link
Copy Markdown
Contributor

Summary

Deleting an item inside __eq__ could panic in deque.remove instead of raising CPython's IndexError: deque mutated during iteration.

  • Track mutations in indexed deletion, extendleft, in-place repetition, and reinitialization; preserve iterators for no-op calls.
  • Make remove detect comparison/finalizer mutations and return None on success.
  • Release removed references outside locks to prevent reentrant finalizer deadlocks.
  • Clear old contents before consuming the reinitialization iterable, fixing d.__init__(d) and finalizer ordering.

Performance

Release microbenchmarks on Windows, deque size 1000, median of three runs with five timed samples each:

Operation Before After
d.__imul__(1) 6.479 us 0.198 us
d.extendleft(()) 0.392 us 0.206 us
remove last item + append 12.327 us 12.350 us

AI assistance

Written with Codex (GPT-6), reviewed by a human before submission.

Summary by CodeRabbit

  • Bug Fixes
    • Bounded deques now retain the correct elements when extended on the left or initialized with new values.
    • Deque removal and deletion behave more consistently when comparisons or other operations modify the deque, with concurrent modifications reported as errors.
    • Iterators are invalidated after successful mutations, but not after no-op operations or failed deletions.
    • Removed elements are released after deque updates, so finalizers observe the updated contents.

@chatgpt-codex-connector

Copy link
Copy Markdown

Codex usage limits have been reached for code reviews. Please check with the admins of this repo to increase the limits by adding credits.
Credits must be used to enable repository wide code reviews.

@coderabbitai

coderabbitai Bot commented Sep 26, 2026 •

Copy link
Copy Markdown
Contributor

Review in Change Stack →

Navigate logical layers of code changes, visualize relationships, and explore their blast radius.

No actionable comments were generated in the recent review. 🎉

ℹ️ Recent review info
⚙️ Run configuration

Configuration used: Repository: RustPython/RustPython/.coderabbit.yml

Review profile: CHILL

Plan: Advanced

Run ID: 7ce72344-6044-4a46-ae1a-923ab37d68e5

📥 Commits

Reviewing files that changed from the base of the PR and between dc3b93a and 558502a.

📒 Files selected for processing (2)
  • crates/vm/src/stdlib/_collections.rs
  • extra_tests/snippets/stdlib_collections_deque.py

Included review availability: This review used your included allowance. Your plan provides up to 10 included reviews per hour; 9 remain after this review.


📝 Walkthrough

Walkthrough

Deque mutations now update mutation state in additional cases, detect changes during remove comparisons, and drop removed elements after releasing the lock. Initialization clears prior contents before converting its iterable. Regression tests cover these behaviors with iterators, finalizers, and bounded deques.

Changes

Deque mutation behavior

Layer / File(s) Summary
Removal and comparison behavior
crates/vm/src/stdlib/_collections.rs, extra_tests/snippets/stdlib_collections_deque.py
remove checks for deque changes during comparisons and raises IndexError if mutation occurs. Successful removal and indexed deletion update mutation state and drop removed items after unlocking. Tests cover comparison behavior, exceptions, iterator invalidation, and finalizer mutations.
Bulk mutation and bounded retention
crates/vm/src/stdlib/_collections.rs, extra_tests/snippets/stdlib_collections_deque.py
extendleft trims incoming values to maxlen and leaves the deque unchanged for empty input. __imul__ preserves state for specified no-ops and updates mutation state when it replaces contents. Tests check iterators and bounded-deque contents.
Deque reinitialization
crates/vm/src/stdlib/_collections.rs, extra_tests/snippets/stdlib_collections_deque.py
Initialization applies maxlen and clears prior contents before iterable conversion. Tests cover self-initialization, invalid inputs, iterator effects, and finalizer observations.

Priority: ➖ Normal

Estimated code review effort: 4 (Complex) | ~45 minutes

Change: Bug fix

Suggested reviewers: youknowone

Merge Risk: ⚪ Minimal · up to 55850

No merge-blocking issue was established in the changed deque behavior. Merge after normal checks.

Security Architecture Review

Security architecture risk: 🔵 Low · up to 55850

A reentrant iterable can leave a bounded deque holding more items than its reported maximum. The demonstrated effect is confined to the deque; no new privileged access or wider system boundary is shown.

Retained concerns

  • Medium · architecture · inferred: Iterable conversion can reenter initialization and change maxlen after the outer call snapshots it. For example, an outer init(iterable, 2) whose iterable calls init([], 0) can finish with two elements and a reported maxlen of zero, breaking the bounded-capacity invariant.
Security review details

Security Blast Radius

  • inferred — The demonstrated reentrancy path affects the targeted deque’s capacity invariant. The inspected entrypoints show no new privilege, tenant boundary, service dependency, or independently reachable sink.

Trust Boundaries and Controls

  • observed — remove checks mutation state after rich comparison and again under the removal lock. That control does not govern maxlen changes made by callbacks during initialization.

Resilience and Maintainability Implications

  • inferred — Releasing removed objects after unlocking reduces reentrant-finalizer lock risk, while the initializer’s split transition leaves its capacity bound vulnerable to a nested initialization during iterable conversion.

Hardening Proposals

  • proposed — Define which initialization owns maxlen after reentrancy, then validate the effective limit when committing converted elements so the resulting deque cannot exceed its reported bound.
🚥 Pre-merge checks | ✅ 4 | ❌ 1

❌ Failed checks (1 warning)

Check name Status Explanation Resolution
Docstring Coverage ⚠️ Warning Docstring coverage is 8.82% which is insufficient. The required threshold is 80.00%. Docstring coverage is scoped to functions touched by this diff. Analyzed 34 functions across 2 files. Write docstrings for the functions missing them to satisfy the coverage threshold.
✅ Passed checks (4 passed)
Check name Status Explanation
Description Check ✅ Passed Check skipped - CodeRabbit’s high-level summary is enabled.
Title check ✅ Passed The title clearly and concisely describes the main changes: tracking deque mutations and releasing removed items outside locks.
Linked Issues check ✅ Passed Check skipped because no linked issues were found for this pull request.
Out of Scope Changes check ✅ Passed Check skipped because no linked issues were found for this pull request.
  • Fix all pre-merge checks with AI
✨ Finishing Touches
🧪 Generate unit tests (beta)
  • Create a new PR

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.

❤️ Share

Comment @coderabbitai help to get the list of available commands.

@codspeed

codspeed Bot commented Sep 27, 2026

Copy link
Copy Markdown
Contributor

Merging this PR will not alter performance

✅ 62 untouched benchmarks
⏩ 4 skipped benchmarks1


Comparing 1ndahous3:deque_remove_mutation (558502a) with main (dc3b93a)

Open in CodSpeed

Footnotes

  1. 4 benchmarks were skipped, so the baseline results were used instead. If they were deleted from the codebase, click here and archive them to remove them from the performance reports. ↩

@youknowone
youknowone merged commit 32ca8aa into RustPython:main Sep 27, 2026
22 checks passed
@1ndahous3
1ndahous3 deleted the deque_remove_mutation branch September 27, 2026 01:43
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Labels

None yet

Projects

None yet

Development

Successfully merging this pull request may close these issues.

2 participants