rpds-py

rpds-py provides Python bindings to Rust’s rpds crate, exposing persistent (immutable) data structures — HashTrieMap, HashTrieSet, List, Stack, and Queue — that use structural sharing instead of full copies on every update. Each mutation method (insert, remove, push, enqueue) returns a new instance in near-constant amortized time rather than mutating in place, while unmodified data is shared between old and new versions under the hood.

Originally built to replace pyrsistent inside the referencing JSON Schema library, rpds-py has since become a foundational dependency across the Python ecosystem — jsonschema, referencing, and dozens of other packages rely on it for fast, hashable, thread-safe immutable collections without the overhead of a pure-Python implementation.

What You Get

• HashTrieMap - an immutable, hashable dict-alike backed by a Rust hash trie, implementing collections.abc.Mapping with keys()/values()/items() views
• HashTrieSet - an immutable set registered as a collections.abc.Set, supporting union/intersection/difference/symmetric_difference
• List and Stack - singly-linked persistent sequences with O(1) push_front/push and pop-style operations plus full iteration support
• Queue - a persistent FIFO structure with enqueue/dequeue/peek operations backed by structural sharing
• Typed stub file (rpds.pyi) - full generic type hints checked with pyright strict mode, so consumers get IDE autocomplete and static type safety

Common Use Cases

• JSON Schema validation caching - Libraries like referencing and jsonschema use HashTrieMap/HashTrieSet to cache resolved schema state immutably across recursive resolution without accidental cross-mutation
• Safe shared state in concurrent code - Because collections are frozen and structurally shared, multiple threads or async tasks can hold references to the same version without locks or defensive copying
• Undo/history stacks - Application code that needs to keep previous states around cheaply (e.g. editors, functional-style reducers) can retain old List/Stack versions without the memory cost of full copies
• Building persistent caches and memoization tables - HashTrieMap gives a hashable, immutable mapping type suitable as a dict key or memoization cache entry, which a plain Python dict cannot be

Under The Hood

Architecture A single src/lib.rs (~1,580 lines) implements PyO3 bindings wrapping the Rust rpds crate’s persistent data structures (HashTrieMap, HashTrieSet, List, Stack, Queue) using the thread-safe “Sync” variants, with reference counting abstracted through the archery crate. Each Python class is a #[pyclass(frozen)] wrapper (repr(transparent)) around the Rust Sync collection, so every mutating method returns a new immutable instance built via structural sharing rather than a full copy. A custom Key wrapper bridges Python’s arbitrary hashable objects into Rust’s trait-based hashing by delegating to Python’s __hash__/__eq__ protocol — this is the central abstraction every collection type depends on. Iterators and views (KeysView/ValuesView/ItemsView) are lightweight pyclasses that clone the underlying Sync collection (cheap, due to structural sharing) and progressively pop elements for __next__. The module registers these classes as virtual subclasses of collections.abc (Mapping, Set, MappingView, KeysView, etc.) at init time, giving Python-native duck typing despite the Rust backing. The single-file layout is appropriate for the domain — a handful of independent, largely-parallel collection wrappers rather than a layered application.

Tech Stack Rust 2021 edition, built via maturin (PyO3 build backend) into a cdylib extension module. Core dependencies are PyO3 0.29.0 (extension-module feature) for the Python/Rust FFI bridge, the rpds 1.2.1 crate providing the actual persistent-collection implementation, and archery 1.2.2 for pluggable Arc/Rc reference counting. Python side targets 3.11+ and ships prebuilt wheels across platforms via GitHub Actions CI using maturin; source installs require a Rust toolchain. Dev tooling uses uv for dependency/lockfile management, nox for task automation, strict ruff linting (select = ["ALL"] with targeted exceptions), pyright --strict against the .pyi stub, and Sphinx + furo docs hosted on Read the Docs, all wired into pre-commit hooks.

Code Quality A dedicated pytest suite (test_list.py, test_stack.py, test_queue.py, test_hash_trie_set.py, test_hash_trie_map.py), adapted from the pyrsistent test suite, covers equality, hashing, pickling, collections.abc conformance, and iteration semantics per type. pyproject.toml enforces fail_under = 100 coverage and uses pytest-run-parallel to exercise thread-safety, including an explicit workaround for a free-threaded-CPython (Py_GIL_DISABLED) bug. Rust-side error handling is explicit: invalid operations (missing-key removal, popping/peeking an empty Stack/Queue, unhashable values) raise the matching Python exception (KeyError, IndexError, TypeError) rather than panicking or silently no-op’ing. Typing is enforced at the interface boundary via the strict-checked .pyi stub, and CI plus pre-commit keep formatting and linting consistent across an actively maintained project (69 releases, commits as recent as August 2026).

API Design The public API deliberately mirrors Python’s built-in collection protocols instead of inventing new vocabulary: HashTrieMap implements collections.abc.Mapping, HashTrieSet is typed as and registered against collections.abc.Set/frozenset, and List/Stack/Queue implement Iterable protocols — so isinstance checks, unpacking, in, and hashing all work without special-casing. Mutating-style operations use a small, consistent verb set (insert/remove/discard/update, push_front/drop_first, push/pop/peek, enqueue/dequeue) that always returns a new instance, making persistence explicit at the call site. The .pyi stub gives full generic typing so IDEs and type checkers understand a compiled extension as if it were pure Python. Getting started is zero-configuration (pip install rpds-py, from rpds import HashTrieMap), though the README is upfront that the surface is deliberately minimal rather than a comprehensive persistent-collections library.