CPython frees most objects the instant they become unreachable, via reference counting: every object tracks how many references point to it, and is freed the moment that count hits zero.

RCObject (given) is a node with a name, a refcount, and referents -- other RCObjects it holds a reference to. Heap tracks which object names are currently allocated (alive). incref/allocate/add_referent are done for you.

Implement Heap.decref(obj):

• Decrement obj.refcount.
• If it's now <= 0 AND obj.name is still in alive: remove it from alive, then recursively decref every object in obj.referents -- freeing an object releases its own references to whatever IT points to, which is what makes freeing cascade through a chain.

Example

a, b = heap.allocate(RCObject("a")), heap.allocate(RCObject("b"))
heap.incref(a)              # one external reference to a
heap.add_referent(a, b)     # a holds a reference to b
heap.decref(a)              # drop the external reference
# both a and b are now freed -- freeing a cascaded to b

Constraints

• Only decref an object's referents if THAT object is actually being freed right now (refcount just hit 0) -- decref-ing on every call regardless would free things that are still legitimately referenced elsewhere.

The missing link: decref alone can never collect a cycle

The 4th test (test_reference_cycle_leaks) demonstrates the real, famous limitation of refcounting: two objects that only reference EACH OTHER keep their refcounts above zero forever, even once nothing outside can reach either of them -- there's no external decref left to ever bring their counts to zero. This isn't a bug you can fix inside decref itself; it's a structural blind spot of counting references one edge at a time.

collect_cycles(roots) is the fix, and it works completely differently: instead of asking "does anything point AT me," it asks "can I be reached by walking FORWARD from something known-external" (a roots list you're given, standing in for a real GC's stack frames/globals). Anything still alive that ISN'T reachable that way can only be alive because of an internal cycle -- nothing legitimate points to it, so it's safe to free, no matter how many other heap objects reference it.

Example

a, b = heap.allocate(RCObject("a")), heap.allocate(RCObject("b"))
heap.incref(a)              # one external reference to a
heap.add_referent(a, b)     # a holds a reference to b
heap.decref(a)              # drop the external reference
# both a and b are now freed -- freeing a cascaded to b

# a cycle decref can never collect:
x, y = heap.allocate(RCObject("x")), heap.allocate(RCObject("y"))
heap.incref(x)
heap.add_referent(x, y)
heap.add_referent(y, x)
heap.decref(x)                    # x.refcount hits 0... but y still points to x!
# both x and y are STILL in heap.alive -- decref alone is stuck.
heap.collect_cycles(roots=[])     # -> {"x", "y"}, and both are freed

Constraints

• Only decref an object's referents if THAT object is actually being freed right now (refcount just hit 0) -- decref-ing on every call regardless would free things that are still legitimately referenced elsewhere.
• collect_cycles must never free an object reachable from roots, no matter how deeply nested, and must return exactly the set of names it actually froze.

Real-world grounding

• CPython's reference counting macros: Py_INCREF/Py_DECREF in Include/object.h
• CPython's supplementary cycle collector -- the real algorithm is smarter than this exercise's roots-based mark/sweep (it uses "trial deletion": temporarily subtract each object's internal references and see what refcount is left, so it doesn't need an explicit root set at all), but the payoff is identical -- collecting garbage refcounting alone cannot: Modules/gcmodule.c