Lesson 09 · Multiple roots and shared objects

Multiple roots and shared objects

Real programs hold many things at once, and different roots often reach the same object. Today you confirm the trace handles multiple roots and counts a shared object once, not twice.

The goal

Trace from several roots into a shared object and get each reachable id exactly once.

Start here - the target

TO DO

Scenario: The reachable set is the union over all roots, with shared objects counted once

Givenobjects a = 0, b = 1, s = 2 with a.field0 = s and b.field0 = s, and both a and b added as roots

WhenReachable() traces from the roots

Thenit returns {0, 1, 2} - s appears exactly once even though both roots reach it

Andif b is removed as a root (but a still reaches s through its field), the reachable set is still {0, 2}, and s survives

Background

Programs have many roots at once, and the reachable set is the union of what each root can reach. Because the trace marks an object seen before following its children, a shared object like s - reachable from both a and b - is visited exactly once: the first root to arrive claims it, and the second finds it already seen. This is why the answer is a set, not a count of paths.

Sharing also draws the line between a reference and a root. Removing b from the root set does not free s, because a still references it - s is reachable, just by one fewer path. An object dies only when it becomes reachable from no root at all. If the trace you wrote last lesson already marks before recursing, this lesson adds no production code - the shared-node case just works, which is exactly the property the mark phase will rely on. Next: what happens when references form a loop.

Make it work

// no new code should be needed if the trace already marks 'seen' before
// recursing - visiting s from a marks it, so reaching it again from b is a no-op
h.AddRoot(a); h.AddRoot(b)
got := h.Reachable() // {0,1,2}: s counted once

CheckpointDONE

The trace handles multiple roots and shared objects correctly. Commit and stop here.