A concurrent mark-and-sweep collector colors every object WHITE (unvisited), GRAY (reachable, not yet scanned), or BLACK (reachable AND fully scanned). The mutator (application code) keeps running while marking happens, which creates a race: if the mutator writes a pointer from an already-BLACK object to a still-WHITE object, and nothing reacts, that white object can get swept as garbage even though it's genuinely reachable -- a BLACK object is never rescanned, so nothing else will ever discover that pointer. The write_barrier method exists specifically to catch this case, by shading the new target gray on the spot.

Right now, a reachable object is getting collected anyway. Your task: find the bug in write_barrier() and fix it. mark_roots(), mark_step(), and sweep() are already correct -- don't change them.

Example that currently fails

collector = Collector({"A": {"refs": ["B"]}, "B": {"refs": []}, "C": {"refs": []}})
collector.mark_roots(["A"])
collector.mark_step()             # scans A (A -> BLACK), shades B gray

collector.write_barrier("A", "C")  # mutator: A now also points at C

while collector.mark_step() is not None:
    pass
dead = collector.sweep()
"C" in dead   # should be False -- C is reachable via A
              # currently: True (the barrier let it slip through)

Real-world grounding

• G1's write barrier plumbing (the pre-write SATB barrier and post-write card-marking barrier a real concurrent collector uses -- more machinery than this exercise's simplified insertion barrier, but solving the exact same problem: a concurrent mutator write must never silently drop a reference the collector still needs to see): src/hotspot/share/gc/g1/g1BarrierSet.cpp, g1BarrierSet.inline.hpp
• G1's concurrent marking cycle (the gray "worklist" this exercise's gray_worklist/mark_step models): src/hotspot/share/gc/g1/g1ConcurrentMark.cpp

The tri-color abstraction itself -- and the "a black object must never point at a white object" invariant this bug violates -- comes from Dijkstra, Lamport, Martin, Scholten & Steffens, "On-the-fly Garbage Collection: An Exercise in Cooperation" (Communications of the ACM, Nov. 1978) -- the original paper proving a collector and a running mutator can cooperate correctly without stopping the world, using exactly this coloring scheme.

Real G1 additionally uses SATB (snapshot-at-the-beginning): instead of (or in addition to) shading the new target, it also records the value being OVERWRITTEN, so a pointer live at the start of the marking cycle is never lost even if the mutator later removes it entirely -- this exercise implements the simpler Dijkstra-style insertion barrier, which is enough to demonstrate the core invariant.