Section 4: Objects, the Heap, and the Collector

Everything so far fits on a stack. Numbers, booleans, strings-as-placeholders, and frames all live in a Vec<Value> that unwinds in perfect reverse order.

This section breaks that. Tables outlive the expression that created them. Closures outlive the frame whose locals they captured. Two tables can point at each other, and neither is reachable from anywhere. Once objects have identity, mutation, and cycles, you need a heap and a collector — and in Rust, you need a heap design that the borrow checker will tolerate.

This is the hardest section in the curriculum and the one that most changes how you read other people's runtimes. It covers Milestones M9 through M12, and at the end of it the language is done.

What You Build

The Layer You Are Building

   VM                                       stack: Vec<Value>   ← unwinds perfectly
   ┌──────────────────────────────────────────────────────────────────────┐
   │  Value::Table(GcRef{ index: 7, gen: 2 })      8-byte HANDLE          │
   └───────────────────────────────┬──────────────────────────────────────┘
                                   │  does NOT unwind. Lives until collected.
 ══════════════════════════════════▼═══════════════════════ THE HEAP ══════
   ┌──────────────────────────────────────────────────────────────────────┐
   │  heap.rs        slots: Vec<Option<HeapObject>>   generations: Vec<u32>│
   │                                                                       │
   │   [0] EmberStr "score"   ◀── interned; the intern table points here   │
   │   [1] Closure { proto, upvals: [GcRef<Upvalue>] }                     │
   │   [2] Upvalue::Open(stack_index 14)   ──┐  points INTO the stack      │
   │   [3] Upvalue::Closed(Value::Integer(3))│  owns its value             │
   │   [7] Table { array: Vec<Value>,        │                             │
   │               hash: insertion-ordered,  │                             │
   │               meta: Option<GcRef<Table>> }                            │
   │                                          │                            │
   │  ┌───────────────────────────────────────▼──────────────────────────┐ │
   │  │ COLLECTOR:  mark from roots → sweep the unmarked → account bytes │ │
   │  │ roots = value stack ∪ frames ∪ globals ∪ open upvalues           │ │
   │  │         ∪ constant pools ∪ the intern table ∪ host handles       │ │
   │  └──────────────────────────────────────────────────────────────────┘ │
   └──────────────────────────────────────────────────────────────────────┘

Note: Read the root list again. Seven root sets, and forgetting any one of them frees a live object. Two of them — constant pools and the intern table — are things you built in Sections 3 and 4 without thinking of them as roots. That is why Lab 15 makes you enumerate roots in exactly one function and deliberately break it once.

The Concepts, and Where Each Is Treated

The Labs

The Rust Problem, Stated Once

This is the section where Rust makes a traditional runtime design harder, and it is worth naming the difficulty before you meet it rather than discovering it at 11pm.

#![allow(unused)]
fn main() {
let t = self.heap.table(handle)?;          // immutable borrow of self.heap
self.heap.set(other, key, value)?;         // ERROR: cannot borrow `self.heap` as mutable
}

The borrow checker is right: set can grow slots, reallocating the Vec and invalidating t. C runtimes have exactly the same hazard and simply do not report it — Lua's ltable.c has comments warning that a luaH_set may invalidate pointers obtained earlier, and getting that wrong in C is a use-after-free rather than a compile error.

Three legitimate ways out, in order of preference:

1. Narrow the borrow. Read what you need, drop the borrow, then mutate. Value is Copy, which is what makes this work — and is one of the load-bearing reasons for ADR-004.
2. Take and put back. let mut t = heap.take_table(h); … operate … heap.put_table(h, t);. Ugly, obvious, and correct. Use it where step 1 is genuinely impossible, such as a table rehash that must call back into the heap.
3. Split the borrow. Give Heap methods that take two handles and internally use slice::split_at_mut or index arithmetic to get two disjoint &muts. Contained, testable, safe.

unsafe is not on the list, and neither is RefCell — a RefCell moves the check to run time and turns a compile error into a panic in a host process. If you find yourself reaching for either, you have a design problem one level up, and the GC chapter walks through it.

Deliverables

• t.name and t["name"] are indistinguishable; both go through one code path.
• The array part handles dense integer keys; a test shows the array/hash transition on rehash.
• t[1.0] and t[1] are the same slot; a NaN key and a nil key are errors.
• pairs iterates in insertion order, deterministically, with a test that would fail under a randomly-seeded hasher.
• Warm-up Experiment 3 (two closures sharing one count) produces identical results in Ember and Lua.
• The compiler resolves each free name to local / upvalue / global, visible in the disassembly.
• Open upvalues are shared while the frame lives and closed when it dies; tested after a return.
• A cycle is collected. This single test justifies the whole subsystem.
• The "forgot a root" bug is introduced deliberately, observed, and fixed by a single root-enumeration function.
• --trace-gc reports bytes before/after, objects freed, and pause duration.
• Interning is added after a benchmark showed it mattered, with the delta recorded.
• Every case in warm-up Experiment 4 matches Lua exactly, including (f()) and select('#', ...).
• __index (table and function forms), __newindex, __call, __tostring, __eq, __lt, __len, and the arithmetic metamethods work, with a chain-depth limit.
• Differential tests still pass across the whole corpus. They will break during Labs 17–18. That is them working.
• docs/adr/ADR-006-tracing-gc-with-handles.md, ADR-007-string-interning.md, and ADR-008-deterministic-iteration.md written.

Common Mistakes in This Section

How to Verify Success

# 1. Tables: identity, aliasing, the array/hash split, deterministic order.
ember run -e 'local a={} local b=a b.x=1 return a.x'                    # 1
ember run -e 'return ({}) == ({})'                                       # false
ember run -e 'local t={} t[1.0]=5 return t[1]'                           # 5
ember run --trace-tables -e 'local t={} for i=1,20 do t[i]=i end'        # watch the array part grow
ember run -e 'local t={b=1,a=2,c=3} local s="" for k in pairs(t) do s=s..k end return s'
#   → "bac" every time, on every machine. Run it ten times.

# 2. Closures: the warm-up, in your own runtime.
ember run tests/golden/closures/counter.ember
diff <(ember run tests/golden/closures/counter.ember) <(lua tests/golden/closures/counter.lua)

# 3. The GC: a cycle is collected.
ember run --trace-gc tests/golden/gc/cycle.ember

# 4. Multiple returns: every rule from the warm-up.
for e in 'f()' '(f())' 'f(), 1' '{f()}' 'select("#", f())'; do
  printf '%-16s ember=%-12s lua=%s\n' "$e" "$(ember run -e "...")" "$(lua -e "...")"
done

# 5. Metatables: the Account example from the warm-up, unchanged.
diff <(ember run tests/golden/meta/account.ember) <(lua tests/golden/meta/account.lua)

# 6. THE gate.
cargo test --test differential

Section Profile: What a Section 4 Graduate Can Do

• Implement a hybrid array/hash table and explain what the array part buys.
• Explain, with a diagram, how a closure keeps a variable alive after its frame dies.
• Distinguish open and closed upvalues and say exactly when the transition happens.
• Write a tracing collector: enumerate roots, trace edges, sweep, account, and schedule.
• Explain why reference counting cannot collect cycles, by drawing one.
• Say what a write barrier is for, and why an incremental collector needs one and a stop-the-world collector does not.
• Implement multiple-return semantics and explain why they complicate the calling convention.
• Explain how metatables turn one data structure into an object system, and where the cost is.
• Navigate an object graph in Rust without unsafe, Rc, or RefCell, and explain the three legitimate ways past the borrow checker.

Next: Tables.