Memory leak in HashTrieMap

[ryanking13]

Hi, I noticed that HashTrieMap (and probably other classes as well) have a memory leak issue.

Reproducer

import gc
import weakref
import sys
import tracemalloc
from rpds import HashTrieMap

print(f"Python {sys.version}\n")

class Node:
    """A plain class whose instances participate in GC."""
    pass


# ── 1. Cycle through dict — collected ───────────────────────
obj = Node()
weak_dict = weakref.ref(obj)
d = {"back": obj}
obj.container = d       # cycle: obj → dict → obj
del obj, d
gc.collect()
print(f"2. Cycle through dict:         leaked = {weak_dict() is not None}")


# ── 2. Cycle through HashTrieMap — LEAKED ───────────────────
obj2 = Node()
weak_rpds = weakref.ref(obj2)
m = HashTrieMap({"back": obj2})
obj2.container = m      # cycle: obj → HashTrieMap → obj
del obj2, m
gc.collect()
print(f"3. Cycle through HashTrieMap:  leaked = {weak_rpds() is not None}")
print()


# ── 3. Quantitative: 10,000 cycles ─────────────────────────
gc.collect()
tracemalloc.start()
snapshot1 = tracemalloc.take_snapshot()

for _ in range(10_000):
    a = Node()
    m = HashTrieMap({"ref": a})
    a.container = m
    del a, m

gc.collect()
snapshot2 = tracemalloc.take_snapshot()
leaked_bytes = sum(s.size_diff for s in snapshot2.compare_to(snapshot1, "lineno") if s.size_diff > 0)
print(f"4. 10,000 cycles through HashTrieMap:")
print(f"   Memory leaked (not reclaimable by GC): {leaked_bytes:,} bytes")

Python 3.14.2 (main, Dec  5 2025, 16:49:16) [Clang 17.0.0 (clang-1700.4.4.1)]

2. Cycle through dict:         leaked = False
3. Cycle through HashTrieMap:  leaked = True

4. 10,000 cycles through HashTrieMap:
   Memory leaked (not reclaimable by GC): 1,364,552 bytes

I guess it is because of not implementing __traverse__ function (https://pyo3.rs/v0.24.2/class/protocols.html#garbage-collector-integration).

• Related issue: Py_FinalizeEx TypeError when holding a jsonschema validator class through interpreter shutdown (Pyodide 314) pyodide/pyodide#6234