Skip to content

traverse and clear #6780

New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Merged
youknowone merged 1 commit into from
Jan 18, 2026
Merged

traverse and clear #6780

Show file tree
Hide file tree
Changes from all commits
Commits
Show all changes
1 commit
Select commit
File filter

Filter by extension

Filter by extension
Conversations
Failed to load comments.
Loading
Jump to
Jump to file
Failed to load files.
Loading
Diff view
Diff view
117 changes: 73 additions & 44 deletions crates/derive-impl/src/pyclass.rs
View file
Open in desktop
Original file line number Diff line number Diff line change
Expand Up @@ -574,51 +574,80 @@ pub(crate) fn impl_pyclass(attr: PunctuatedNestedMeta, item: Item) -> Result<Tok
)?;

const ALLOWED_TRAVERSE_OPTS: &[&str] = &["manual"];
// try to know if it have a `#[pyclass(trace)]` exist on this struct
// TODO(discord9): rethink on auto detect `#[Derive(PyTrace)]`

// 1. no `traverse` at all: generate a dummy try_traverse
// 2. `traverse = "manual"`: generate a try_traverse, but not #[derive(Traverse)]
// 3. `traverse`: generate a try_traverse, and #[derive(Traverse)]
let (maybe_trace_code, derive_trace) = {
if class_meta.inner()._has_key("traverse")? {
let maybe_trace_code = quote! {
impl ::rustpython_vm::object::MaybeTraverse for #ident {
const IS_TRACE: bool = true;
fn try_traverse(&self, tracer_fn: &mut ::rustpython_vm::object::TraverseFn) {
::rustpython_vm::object::Traverse::traverse(self, tracer_fn);
}
// Generate MaybeTraverse impl with both traverse and clear support
//
// For traverse:
// 1. no `traverse` at all: HAS_TRAVERSE = false, try_traverse does nothing
// 2. `traverse = "manual"`: HAS_TRAVERSE = true, but no #[derive(Traverse)]
// 3. `traverse`: HAS_TRAVERSE = true, and #[derive(Traverse)]
//
// For clear (tp_clear):
// 1. no `clear`: HAS_CLEAR = HAS_TRAVERSE (default: same as traverse)
// 2. `clear` or `clear = true`: HAS_CLEAR = true, try_clear calls Traverse::clear
// 3. `clear = false`: HAS_CLEAR = false (rare: traverse without clear)
let has_traverse = class_meta.inner()._has_key("traverse")?;
let has_clear = if class_meta.inner()._has_key("clear")? {
// If clear attribute is present, use its value
class_meta.inner()._bool("clear")?
} else {
// If clear attribute is absent, default to same as traverse
has_traverse
};
Comment on lines +588 to +595
Copy link
Contributor

@coderabbitai coderabbitai bot Jan 18, 2026

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

⚠️ Potential issue | 🟠 Major

Require traverse when clear is enabled.
If clear is set without traverse, HAS_TRAVERSE stays false and GC traversal becomes a no-op.

🔧 Proposed fix 
 let has_traverse = class_meta.inner()._has_key("traverse")?;
 let has_clear = if class_meta.inner()._has_key("clear")? {
     // If clear attribute is present, use its value
     class_meta.inner()._bool("clear")?
 } else {
     // If clear attribute is absent, default to same as traverse
     has_traverse
 };
+if has_clear && !has_traverse {
+    bail_span!(
+        item,
+        "`clear` requires `traverse` (use `traverse` or `traverse = \"manual\"`)"
+    );
+}
🤖 Prompt for AI Agents 
In `@crates/derive-impl/src/pyclass.rs` around lines 588 - 595, The code currently
allows `clear` to be true while `traverse` is absent which leaves `HAS_TRAVERSE`
false and makes GC traversal a no-op; update the logic around `has_traverse` and
`has_clear` in the block using `class_meta.inner()._has_key` and
`class_meta.inner()._bool` to validate that if `clear` is present and true then
`traverse` must also be present (or return an error) — e.g. after computing
`has_clear` check `if has_clear && !has_traverse { return Err(...) }`
referencing the same symbols (`has_traverse`, `has_clear`,
`class_meta.inner()._has_key`, `_bool`, `HAS_TRAVERSE`) so the parser fails the
derive when `clear` is enabled without `traverse`.


let derive_trace = if has_traverse {
// _optional_str returns Err when key exists without value (e.g., `traverse` vs `traverse = "manual"`)
// We want to derive Traverse in that case, so we handle Err as Ok(None)
let value = class_meta.inner()._optional_str("traverse").ok().flatten();
if let Some(s) = value {
if !ALLOWED_TRAVERSE_OPTS.contains(&s.as_str()) {
bail_span!(
item,
"traverse attribute only accept {ALLOWED_TRAVERSE_OPTS:?} as value or no value at all",
);
}
assert_eq!(s, "manual");
quote! {}
} else {
quote! {#[derive(Traverse)]}
}
} else {
quote! {}
};

let maybe_traverse_code = {
let try_traverse_body = if has_traverse {
quote! {
::rustpython_vm::object::Traverse::traverse(self, tracer_fn);
}
} else {
quote! {
// do nothing
}
};

let try_clear_body = if has_clear {
quote! {
::rustpython_vm::object::Traverse::clear(self, out);
}
} else {
quote! {
// do nothing
}
};

quote! {
impl ::rustpython_vm::object::MaybeTraverse for #ident {
const HAS_TRAVERSE: bool = #has_traverse;
const HAS_CLEAR: bool = #has_clear;

fn try_traverse(&self, tracer_fn: &mut ::rustpython_vm::object::TraverseFn) {
#try_traverse_body
Comment on lines +643 to +644
Copy link
Contributor

@coderabbitai coderabbitai bot Jan 18, 2026

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

⚠️ Potential issue | 🔴 Critical

🧩 Analysis chain

🏁 Script executed:

# Search for TraverseFn definition
rg -n "type TraverseFn|struct TraverseFn|trait TraverseFn" crates/vm/src/object -A 3 -B 1

Repository: RustPython/RustPython

Length of output: 186

🏁 Script executed:

# Check current code at lines 643-644 in the file
sed -n '640,650p' crates/derive-impl/src/pyclass.rs

Repository: RustPython/RustPython

Length of output: 186

🏁 Script executed:

# Search for other uses of TraverseFn in the codebase to see patterns
rg -n "TraverseFn" crates/ --type rs | head -20

Repository: RustPython/RustPython

Length of output: 186

🌐 Web query:

RustPython TraverseFn lifetime generic type definition

💡 Result:

Definition (from rustpython-vm crate):
pub type TraverseFn<'a> = dyn FnMut(&PyObject) + 'a. [1][2]

Sources:

  • rustpython-vm API docs — TraverseFn type alias. [1]
  • rustpython-vm source (object/mod.rs) showing the type alias. [2]

🌐 Web query:

RustPython vm object TraverseFn signature

💡 Result:

I can look that up in the RustPython source (to give the exact current Rust signature). Do you want me to fetch the signature from the repository (GitHub/docs.rs) now?

Fix the missing lifetime on TraverseFn in generated signatures.
The TraverseFn type is defined as dyn FnMut(&PyObject) + 'a and requires a lifetime parameter. Generated code must include it for type-checking.

🔧 Proposed fix 
-            fn try_traverse(&self, tracer_fn: &mut ::rustpython_vm::object::TraverseFn) {
+            fn try_traverse(&self, tracer_fn: &mut ::rustpython_vm::object::TraverseFn<'_>) {
                 `#try_traverse_body`
             }
📝 Committable suggestion

‼️ IMPORTANT
Carefully review the code before committing. Ensure that it accurately replaces the highlighted code, contains no missing lines, and has no issues with indentation. Thoroughly test & benchmark the code to ensure it meets the requirements.

Suggested change
fn try_traverse(&self, tracer_fn: &mut ::rustpython_vm::object::TraverseFn) {
#try_traverse_body
fn try_traverse(&self, tracer_fn: &mut ::rustpython_vm::object::TraverseFn<'_>) {
`#try_traverse_body`
🤖 Prompt for AI Agents 
In `@crates/derive-impl/src/pyclass.rs` around lines 643 - 644, The generated
signature for try_traverse is using ::rustpython_vm::object::TraverseFn without
its required lifetime; update the generated code so all uses of TraverseFn
include the lifetime parameter (e.g. TraverseFn<'a>) and propagate that 'a into
the impl/generics for try_traverse and any surrounding impl blocks where
tracer_fn is referenced (look for the try_traverse function and references to
::rustpython_vm::object::TraverseFn and add the 'a lifetime consistently).

}
};
// if the key `traverse` exist but not as key-value, _optional_str return Err(...)
// so we need to check if it is Ok(Some(...))
let value = class_meta.inner()._optional_str("traverse");
let derive_trace = if let Ok(Some(s)) = value {
if !ALLOWED_TRAVERSE_OPTS.contains(&s.as_str()) {
bail_span!(
item,
"traverse attribute only accept {ALLOWED_TRAVERSE_OPTS:?} as value or no value at all",
);

fn try_clear(&mut self, out: &mut ::std::vec::Vec<::rustpython_vm::PyObjectRef>) {
#try_clear_body
}
assert_eq!(s, "manual");
quote! {}
} else {
quote! {#[derive(Traverse)]}
};
(maybe_trace_code, derive_trace)
} else {
(
// a dummy impl, which do nothing
// #attrs
quote! {
impl ::rustpython_vm::object::MaybeTraverse for #ident {
fn try_traverse(&self, tracer_fn: &mut ::rustpython_vm::object::TraverseFn) {
// do nothing
}
}
},
quote! {},
)
}
}
};

Expand Down Expand Up @@ -675,7 +704,7 @@ pub(crate) fn impl_pyclass(attr: PunctuatedNestedMeta, item: Item) -> Result<Tok
let ret = quote! {
#derive_trace
#item
#maybe_trace_code
#maybe_traverse_code
#class_def
#impl_payload
#empty_impl
Expand Down
7 changes: 7 additions & 0 deletions crates/derive-impl/src/pystructseq.rs
View file
Open in desktop
Original file line number Diff line number Diff line change
Expand Up @@ -606,9 +606,16 @@ pub(crate) fn impl_pystruct_sequence(

// MaybeTraverse - delegate to inner PyTuple
impl ::rustpython_vm::object::MaybeTraverse for #pytype_ident {
const HAS_TRAVERSE: bool = true;
const HAS_CLEAR: bool = true;

fn try_traverse(&self, traverse_fn: &mut ::rustpython_vm::object::TraverseFn<'_>) {
self.0.try_traverse(traverse_fn)
}

fn try_clear(&mut self, out: &mut ::std::vec::Vec<::rustpython_vm::PyObjectRef>) {
self.0.try_clear(out)
}
}

// PySubclass for proper inheritance
Expand Down
1 change: 1 addition & 0 deletions crates/derive-impl/src/util.rs
View file
Open in desktop
Original file line number Diff line number Diff line change
Expand Up @@ -372,6 +372,7 @@ impl ItemMeta for ClassItemMeta {
"ctx",
"impl",
"traverse",
"clear", // tp_clear
];

fn from_inner(inner: ItemMetaInner) -> Self {
Expand Down
18 changes: 17 additions & 1 deletion crates/vm/src/builtins/dict.rs
View file
Open in desktop
Original file line number Diff line number Diff line change
Expand Up @@ -2,6 +2,7 @@ use super::{
IterStatus, PositionIterInternal, PyBaseExceptionRef, PyGenericAlias, PyMappingProxy, PySet,
PyStr, PyStrRef, PyTupleRef, PyType, PyTypeRef, set::PySetInner,
};
use crate::object::{Traverse, TraverseFn};
use crate::{
AsObject, Context, Py, PyObject, PyObjectRef, PyPayload, PyRef, PyRefExact, PyResult,
TryFromObject, atomic_func,
Expand Down Expand Up @@ -29,13 +30,28 @@ use std::sync::LazyLock;

pub type DictContentType = dict_inner::Dict;

#[pyclass(module = false, name = "dict", unhashable = true, traverse)]
#[pyclass(module = false, name = "dict", unhashable = true, traverse = "manual")]
#[derive(Default)]
pub struct PyDict {
entries: DictContentType,
}
pub type PyDictRef = PyRef<PyDict>;

// SAFETY: Traverse properly visits all owned PyObjectRefs
unsafe impl Traverse for PyDict {
fn traverse(&self, traverse_fn: &mut TraverseFn<'_>) {
self.entries.traverse(traverse_fn);
}

fn clear(&mut self, out: &mut Vec<PyObjectRef>) {
// Pop all entries and collect both keys and values
for (key, value) in self.entries.drain_entries() {
out.push(key);
out.push(value);
}
}
}

impl fmt::Debug for PyDict {
fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
// TODO: implement more detailed, non-recursive Debug formatter
Expand Down
64 changes: 64 additions & 0 deletions crates/vm/src/builtins/function.rs
View file
Open in desktop
Original file line number Diff line number Diff line change
Expand Up @@ -51,6 +51,70 @@ unsafe impl Traverse for PyFunction {
closure.as_untyped().traverse(tracer_fn);
}
self.defaults_and_kwdefaults.traverse(tracer_fn);
// Traverse additional fields that may contain references
self.type_params.lock().traverse(tracer_fn);
self.annotations.lock().traverse(tracer_fn);
self.module.lock().traverse(tracer_fn);
self.doc.lock().traverse(tracer_fn);
Comment on lines +54 to +58
Copy link
Contributor

@coderabbitai coderabbitai bot Jan 18, 2026

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

⚠️ Potential issue | 🟠 Major

Avoid blocking locks in traverse to prevent GC deadlocks.

PyMutex::lock() can block if the lock is held when GC runs, which can deadlock traversal. Prefer the Traverse impl for PyMutex (uses try_lock) instead of manual locking.

✅ Safer traversal (non-blocking) 
-        self.type_params.lock().traverse(tracer_fn);
-        self.annotations.lock().traverse(tracer_fn);
-        self.module.lock().traverse(tracer_fn);
-        self.doc.lock().traverse(tracer_fn);
+        self.type_params.traverse(tracer_fn);
+        self.annotations.traverse(tracer_fn);
+        self.module.traverse(tracer_fn);
+        self.doc.traverse(tracer_fn);
📝 Committable suggestion

‼️ IMPORTANT
Carefully review the code before committing. Ensure that it accurately replaces the highlighted code, contains no missing lines, and has no issues with indentation. Thoroughly test & benchmark the code to ensure it meets the requirements.

Suggested change
// Traverse additional fields that may contain references
self.type_params.lock().traverse(tracer_fn);
self.annotations.lock().traverse(tracer_fn);
self.module.lock().traverse(tracer_fn);
self.doc.lock().traverse(tracer_fn);
// Traverse additional fields that may contain references
self.type_params.traverse(tracer_fn);
self.annotations.traverse(tracer_fn);
self.module.traverse(tracer_fn);
self.doc.traverse(tracer_fn);
🤖 Prompt for AI Agents 
In `@crates/vm/src/builtins/function.rs` around lines 54 - 58, The traversal
currently grabs blocking locks (e.g. self.type_params.lock().traverse(...),
self.annotations.lock().traverse(...), self.module.lock().traverse(...),
self.doc.lock().traverse(...)) which can block the GC and deadlock; instead call
the Traverse implementation on the PyMutex fields directly (use the PyMutex's
non-blocking traverse method or try_lock-based impl) — replace usages of
.lock().traverse(tracer_fn) with the PyMutex/field's traverse(tracer_fn) so
traversal uses the non-blocking path for type_params, annotations, module and
doc.

}

fn clear(&mut self, out: &mut Vec<crate::PyObjectRef>) {
// Pop closure if present (equivalent to Py_CLEAR(func_closure))
if let Some(closure) = self.closure.take() {
out.push(closure.into());
}

// Pop defaults and kwdefaults
if let Some(mut guard) = self.defaults_and_kwdefaults.try_lock() {
if let Some(defaults) = guard.0.take() {
out.push(defaults.into());
}
if let Some(kwdefaults) = guard.1.take() {
out.push(kwdefaults.into());
}
}

// Clear annotations and annotate (Py_CLEAR)
if let Some(mut guard) = self.annotations.try_lock()
&& let Some(annotations) = guard.take()
{
out.push(annotations.into());
}
if let Some(mut guard) = self.annotate.try_lock()
&& let Some(annotate) = guard.take()
{
out.push(annotate);
}

// Clear module, doc, and type_params (Py_CLEAR)
if let Some(mut guard) = self.module.try_lock() {
let old_module =
std::mem::replace(&mut *guard, Context::genesis().none.to_owned().into());
out.push(old_module);
}
if let Some(mut guard) = self.doc.try_lock() {
let old_doc = std::mem::replace(&mut *guard, Context::genesis().none.to_owned().into());
out.push(old_doc);
}
if let Some(mut guard) = self.type_params.try_lock() {
let old_type_params =
std::mem::replace(&mut *guard, Context::genesis().empty_tuple.to_owned());
out.push(old_type_params.into());
}

// Replace name and qualname with empty string to break potential str subclass cycles
// name and qualname could be str subclasses, so they could have reference cycles
if let Some(mut guard) = self.name.try_lock() {
let old_name = std::mem::replace(&mut *guard, Context::genesis().empty_str.to_owned());
out.push(old_name.into());
}
if let Some(mut guard) = self.qualname.try_lock() {
let old_qualname =
std::mem::replace(&mut *guard, Context::genesis().empty_str.to_owned());
out.push(old_qualname.into());
}

// Note: globals, builtins, code are NOT cleared (required to be non-NULL)
}
}

Expand Down
19 changes: 18 additions & 1 deletion crates/vm/src/builtins/list.rs
View file
Open in desktop
Original file line number Diff line number Diff line change
Expand Up @@ -3,6 +3,7 @@ use crate::atomic_func;
use crate::common::lock::{
PyMappedRwLockReadGuard, PyMutex, PyRwLock, PyRwLockReadGuard, PyRwLockWriteGuard,
};
use crate::object::{Traverse, TraverseFn};
use crate::{
AsObject, Context, Py, PyObject, PyObjectRef, PyPayload, PyRef, PyResult,
class::PyClassImpl,
Expand All @@ -23,7 +24,7 @@ use crate::{
use alloc::fmt;
use core::ops::DerefMut;

#[pyclass(module = false, name = "list", unhashable = true, traverse)]
#[pyclass(module = false, name = "list", unhashable = true, traverse = "manual")]
#[derive(Default)]
pub struct PyList {
elements: PyRwLock<Vec<PyObjectRef>>,
Expand All @@ -50,6 +51,22 @@ impl FromIterator<PyObjectRef> for PyList {
}
}

// SAFETY: Traverse properly visits all owned PyObjectRefs
unsafe impl Traverse for PyList {
fn traverse(&self, traverse_fn: &mut TraverseFn<'_>) {
self.elements.traverse(traverse_fn);
}

fn clear(&mut self, out: &mut Vec<PyObjectRef>) {
// During GC, we use interior mutability to access elements.
// This is safe because during GC collection, the object is unreachable
// and no other code should be accessing it.
if let Some(mut guard) = self.elements.try_write() {
out.extend(guard.drain(..));
}
}
}

impl PyPayload for PyList {
#[inline]
fn class(ctx: &Context) -> &'static Py<PyType> {
Expand Down
7 changes: 7 additions & 0 deletions crates/vm/src/builtins/str.rs
View file
Open in desktop
Original file line number Diff line number Diff line change
Expand Up @@ -1924,9 +1924,16 @@ impl fmt::Display for PyUtf8Str {
}

impl MaybeTraverse for PyUtf8Str {
const HAS_TRAVERSE: bool = true;
const HAS_CLEAR: bool = false;

fn try_traverse(&self, traverse_fn: &mut TraverseFn<'_>) {
self.0.try_traverse(traverse_fn);
}

fn try_clear(&mut self, _out: &mut Vec<PyObjectRef>) {
// No clear needed for PyUtf8Str
}
}

impl PyPayload for PyUtf8Str {
Expand Down
16 changes: 15 additions & 1 deletion crates/vm/src/builtins/tuple.rs
View file
Open in desktop
Original file line number Diff line number Diff line change
Expand Up @@ -3,6 +3,7 @@ use crate::common::{
hash::{PyHash, PyUHash},
lock::PyMutex,
};
use crate::object::{Traverse, TraverseFn};
use crate::{
AsObject, Context, Py, PyObject, PyObjectRef, PyPayload, PyRef, PyResult, TryFromObject,
atomic_func,
Expand All @@ -24,7 +25,7 @@ use crate::{
use alloc::fmt;
use std::sync::LazyLock;

#[pyclass(module = false, name = "tuple", traverse)]
#[pyclass(module = false, name = "tuple", traverse = "manual")]
pub struct PyTuple<R = PyObjectRef> {
elements: Box<[R]>,
}
Expand All @@ -36,6 +37,19 @@ impl<R> fmt::Debug for PyTuple<R> {
}
}

// SAFETY: Traverse properly visits all owned PyObjectRefs
// Note: Only impl for PyTuple<PyObjectRef> (the default)
unsafe impl Traverse for PyTuple {
fn traverse(&self, traverse_fn: &mut TraverseFn<'_>) {
self.elements.traverse(traverse_fn);
}

fn clear(&mut self, out: &mut Vec<PyObjectRef>) {
let elements = std::mem::take(&mut self.elements);
out.extend(elements.into_vec());
}
}

impl PyPayload for PyTuple {
#[inline]
fn class(ctx: &Context) -> &'static Py<PyType> {
Expand Down
11 changes: 11 additions & 0 deletions crates/vm/src/dict_inner.rs
View file
Open in desktop
Original file line number Diff line number Diff line change
Expand Up @@ -724,6 +724,17 @@ impl<T: Clone> Dict<T> {
+ inner.indices.len() * size_of::<i64>()
+ inner.entries.len() * size_of::<DictEntry<T>>()
}

/// Pop all entries from the dict, returning (key, value) pairs.
/// This is used for circular reference resolution in GC.
/// Requires &mut self to avoid lock contention.
pub fn drain_entries(&mut self) -> impl Iterator<Item = (PyObjectRef, T)> + '_ {
let inner = self.inner.get_mut();
inner.used = 0;
inner.filled = 0;
inner.indices.iter_mut().for_each(|i| *i = IndexEntry::FREE);
inner.entries.drain(..).flatten().map(|e| (e.key, e.value))
}
}

type LookupResult = (IndexEntry, IndexIndex);
Expand Down
Loading
Loading