Walking an object graph with gc.get_referents

Answer two questions about a live object graph using only gc.get_referents: how much is reachable, and which roots are inside a cycle.

build(graph, chain, chain_closes) is provided and must not be changed. It turns a spec into real Python objects: each node becomes a list[object] whose items are the node objects it points at, so gc.get_referents(node) returns exactly that node’s successors. If chain > 0 it also builds a plain linear chain c0 -> c1 -> ... -> c(chain-1), closing it back to c0 when chain_closes is set. The chain parameter exists so a test can hand you a 10,000-deep structure without a 10,000-entry input.

Implement:

def reachable_ids(start: object) -> set[int]: ...

def solve(
    graph: dict[str, list[str]],
    roots: list[str],
    chain: int,
    chain_closes: bool,
) -> dict[str, object]: ...

solve returns:

• "reachable" — how many named nodes are reachable from any root, counting the roots themselves.
• "cyclic_roots" — the sorted names of roots that are reachable from themselves in one or more steps, i.e. that sit on a cycle.

Two constraints do all the teaching here.

Objects in a real heap are frequently unhashable — a list, a dict, a set, a numpy array. So seen: set[object] does not compile as a strategy and if obj in seen is worse: it calls __eq__, which on a large container is an O(n) deep comparison, and which for two structurally-equal-but-distinct objects gives you the wrong answer. The visited set must be set[int] keyed on id(), and id() is only unique among simultaneously-live objects — which is fine here precisely because you hold the whole graph alive while you walk it.

Real object graphs are also deep. Python’s default recursion limit is 1,000; a linked list of 10,000 nodes is not unusual, and neither is a deeply nested JSON document. A recursive walker raises RecursionError on data that a production heap produces routinely, so the traversal has to carry its own explicit stack.

This is the same primitive the cycle collector itself uses: get_referents is a direct call to the object’s tp_traverse slot. Its expensive sibling gc.get_referrers answers the reverse question by scanning every tracked object in the process — useful in a debugger, never in a hot path.

Your submission must pass mypy --strict.