Skip to content

Implement _collections.OrderedDict #6799

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

Draft
moreal wants to merge 1 commit into
base: main
Choose a base branch
from
Draft

Implement _collections.OrderedDict #6799

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
27 changes: 25 additions & 2 deletions Lib/test/test_ordered_dict.py
View file
Open in desktop
Original file line number Diff line number Diff line change
Expand Up @@ -775,6 +775,31 @@ class CPythonOrderedDictTests(OrderedDictTests, unittest.TestCase):
OrderedDict = c_coll.OrderedDict
check_sizeof = support.check_sizeof

# TODO: RUSTPYTHON - RustPython shares dict storage, no separate order tracking
@unittest.expectedFailure
def test_dict_delitem(self):
super().test_dict_delitem()

# TODO: RUSTPYTHON - RustPython shares dict storage, no separate order tracking
@unittest.expectedFailure
def test_dict_pop(self):
super().test_dict_pop()

# TODO: RUSTPYTHON - RustPython shares dict storage, no separate order tracking
@unittest.expectedFailure
def test_dict_popitem(self):
super().test_dict_popitem()

# TODO: RUSTPYTHON - RustPython shares dict storage, no separate order tracking
@unittest.expectedFailure
def test_issue24347(self):
super().test_issue24347()

# TODO: RUSTPYTHON - RecursionError with self-referencing OrderedDict
@unittest.expectedFailure
def test_pickle_recursive(self):
super().test_pickle_recursive()

@support.cpython_only
def test_sizeof_exact(self):
OrderedDict = self.OrderedDict
Expand Down Expand Up @@ -808,8 +833,6 @@ def test_sizeof_exact(self):
check(iter(od.items()), itersize)
check(iter(od.values()), itersize)

# TODO: RUSTPYTHON
@unittest.expectedFailure
def test_key_change_during_iteration(self):
OrderedDict = self.OrderedDict

Expand Down
7 changes: 5 additions & 2 deletions crates/vm/src/builtins/dict.rs
View file
Open in desktop
Original file line number Diff line number Diff line change
Expand Up @@ -325,8 +325,11 @@ impl PyDict {
}

fn __or__(&self, other: PyObjectRef, vm: &VirtualMachine) -> PyResult {
let other_dict: Result<PyDictRef, _> = other.downcast();
if let Ok(other) = other_dict {
// Only accept exact dict type, not subclasses
// This allows subclasses like OrderedDict to handle the operation via __ror__
if other.class().is(vm.ctx.types.dict_type)
&& let Ok(other) = other.downcast::<PyDict>()
Comment on lines +330 to +331
Copy link
Member

@youknowone youknowone Jan 19, 2026

Choose a reason for hiding this comment

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

still there is convenience problem, but we have downcast_exact

{
let self_cp = self.copy();
self_cp.merge_dict(other, vm)?;
return Ok(self_cp.into_pyobject(vm));
Expand Down
115 changes: 115 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 @@ -717,6 +717,121 @@ impl<T: Clone> Dict<T> {
Some((entry.key, entry.value))
}

/// Pop the first (oldest) entry - O(n) worst case due to finding first non-None entry
/// Used by OrderedDict.popitem(last=False)
pub fn pop_front(&self) -> Option<(PyObjectRef, T)> {
let inner = &mut *self.write();
// Find first non-None entry (entries are in insertion order)
for i in 0..inner.entries.len() {
if inner.entries[i].is_some() {
let entry = inner.entries[i].take().unwrap();
inner.used -= 1;
*unsafe {
// entry.index always refers valid index
inner.indices.get_unchecked_mut(entry.index)
} = IndexEntry::DUMMY;
return Some((entry.key, entry.value));
}
}
None
}

/// Move existing key to end (last=true) or beginning (last=false)
/// Returns Ok(true) if key was found and moved, Ok(false) if key was not found
/// Used by OrderedDict.move_to_end()
pub fn move_to_end<K: DictKey + ?Sized>(
&self,
vm: &VirtualMachine,
key: &K,
last: bool,
) -> PyResult<bool> {
let hash_value = key.key_hash(vm)?;
loop {
let lookup = self.lookup(vm, key, hash_value, None)?;
let (index_entry, index_index) = lookup;
let Some(entry_index) = index_entry.index() else {
return Ok(false); // Key not found
};

let inner = &mut *self.write();

// Verify the entry still exists at the expected position
let slot = match inner.entries.get_mut(entry_index) {
Some(slot) => slot,
None => continue, // Dict changed, retry
};
let entry = match slot {
Some(entry) if entry.index == index_index => slot.take().unwrap(),
_ => continue, // Dict changed, retry
};

// Mark old position as dummy in indices
*unsafe { inner.indices.get_unchecked_mut(index_index) } = IndexEntry::DUMMY;

if last {
// Move to end - O(1) amortized
let new_entry_index = inner.entries.len();
// Find a new index slot for this entry
let mask = (inner.indices.len() - 1) as i64;
let mut idxs = GenIndexes::new(entry.hash, mask);
let new_index_index = loop {
let idx = idxs.next();
let slot = unsafe { inner.indices.get_unchecked_mut(idx) };
if *slot == IndexEntry::FREE || *slot == IndexEntry::DUMMY {
*slot = unsafe { IndexEntry::from_index_unchecked(new_entry_index) };
break idx;
}
};
inner.entries.push(Some(DictEntry {
hash: entry.hash,
key: entry.key,
value: entry.value,
index: new_index_index,
}));
} else {
// Move to beginning - O(n) due to shifting
// We need to insert at position 0 and update all shifted indices
let new_entry_index = 0;

// First, shift all existing entries' positions in the indices table
for i in 0..inner.indices.len() {
if let Some(idx) = inner.indices[i].index() {
// Shift by 1 since we're inserting at position 0
inner.indices[i] = unsafe { IndexEntry::from_index_unchecked(idx + 1) };
}
}

// Update the entry indices in entries vector (they point back to indices)
// Actually, entry.index points to the indices table, not entry position
// So we don't need to update entry.index for existing entries

// Find a new index slot for the moved entry
let mask = (inner.indices.len() - 1) as i64;
let mut idxs = GenIndexes::new(entry.hash, mask);
let new_index_index = loop {
let idx = idxs.next();
let slot = unsafe { inner.indices.get_unchecked_mut(idx) };
if *slot == IndexEntry::FREE || *slot == IndexEntry::DUMMY {
*slot = unsafe { IndexEntry::from_index_unchecked(new_entry_index) };
break idx;
}
};

inner.entries.insert(
0,
Some(DictEntry {
hash: entry.hash,
key: entry.key,
value: entry.value,
index: new_index_index,
}),
);
}

return Ok(true);
}
}

pub fn sizeof(&self) -> usize {
let inner = self.read();
size_of::<Self>()
Expand Down
Loading
Loading