How does copy.deepcopy's memo handle shared references and reference cycles?

### The algorithm in one paragraph `copy.deepcopy(x)` is a recursive graph walk with memoisation. For each object it reaches it first asks: *have I copied this one already?* by looking up `id(obj)` in a **memo** dict that is threaded through the whole traversal. On a hit it returns the stored copy. On a miss it constructs a new object, **stores it in the memo before recursing into the children**, and then deep-copies the children into it. That ordering is the entire trick, and it buys two guarantees at once. ### Guarantee one: shape is preserved, not just contents If two attributes of the original point at one object, the copy's two attributes point at one *copy* of it — not two independent duplicates. Deep copying reproduces the graph's topology, not merely its values: ```python import copy shared = {"tenant": "acme"} context = {"a": shared, "b": shared} snapshot = copy.deepcopy(context) print(snapshot["a"] is snapshot["b"]) # True - aliasing preserved print(snapshot["a"] is shared) # False - but it is a copy ``` Without the memo, `snapshot["a"]` and `snapshot["b"]` would be two separate dicts and a later mutation through one would not be seen through the other — silently changing behaviour that the original relied on. ### Guarantee two: cycles terminate Because the new object is registered in the memo *before* its children are walked, a cycle that leads back to an already-seen object finds it in the memo and stops: ```python context = {"id": 1} context["self"] = context snapshot = copy.deepcopy(context) print(snapshot["self"] is snapshot) # True - the cycle is rebuilt ``` The memo additionally holds a keep-alive list of the original objects, so none of them can be garbage-collected mid-walk and have its `id()` reused by a fresh object — which would otherwise corrupt the mapping. ### What deepcopy refuses to copy Not everything is duplicated. Immutable atomics — `int`, `float`, `str`, `bytes`, `bool`, `None` — are returned unchanged, because copying them would be pure waste. So are classes, functions and modules: a deep copy of an object holding a reference to a class gives you the same class, not a clone of it. For everything else without a dedicated hook, `copy` falls back to the pickle-style reduction protocol via `__reduce_ex__`, which is why an object holding a non-serialisable resource fails loudly: ```python import copy import threading try: copy.deepcopy(threading.Lock()) except TypeError as exc: print(type(exc).__name__) # TypeError ``` A lock, a socket, an open file or a live connection cannot be reduced, so the deep copy raises `TypeError` rather than producing a broken clone. Deep chains — a linked structure tens of thousands of nodes long — raise `RecursionError` instead, since the walk is recursive. ### The cost, and where it bites The walk is proportional to the whole reachable graph and allocates a new object per node, with a dict insert and lookup per node on top. On a request path that matters. Consider a fraud-scoring service that deep-copies its request context before applying rules so a partial-failure rollback can restore the pre-rule state. The context holds a handful of mutable per-request fields — and a reference to the shared reference-data map the rules read, which is serving an 83% cache-hit rate precisely because every request shares one instance of it. `copy.deepcopy(context)` duplicates that map per request: the cache-hit rate collapses to nothing useful because each request now reads its own copy, memory scales with concurrency instead of staying flat, and latency grows with the size of data nobody mutates. The fix is to stop treating "snapshot" as "deep copy everything". Better options, roughly in order: * **Copy only what can change.** Rebuild the small set of mutable per-request fields and keep the shared read-only data aliased. * **Make the shared data immutable** — tuples, frozensets, frozen dataclasses — so nothing needs copying and sharing is provably safe. * **Do not snapshot at all.** Apply rules to a fresh derived structure and commit at the end, so rollback means discarding the derived structure rather than restoring the original. * **Give the objects copy hooks** so a deep copy of the context can deliberately share the reference data instead of walking it. ### Interview-ready summary The memo is what makes `copy.deepcopy` *correct* on real object graphs — preserving aliasing and surviving cycles — and it is also a good reminder of what deep copying costs: every distinct reachable object becomes a new allocation. Knowing both halves is the difference between "use deepcopy" and knowing when a deep copy is the wrong tool for a snapshot.