This problem class looks like a simple mark-and-sweep, but four independent mechanics interact, and each one is a classic source of wrong answers:
The solution is complete and verified. Here is the self-contained markdown (also saved at ~/wasm-gc-sim/SOLUTION.md, alongside gc.js, test.js, fuzz.js, demo.js).
This problem class looks like a simple mark-and-sweep, but four independent mechanics interact, and each one is a classic source of wrong answers:
{key, value} keeps the value alive iff the key is alive, and this is a fixed point: marking a value can mark another ephemeron's key, etc. A single pass leaks or over-collects. Chains/cycles require iteration to a fixed point.BLACK → WHITE edge; the white target is never scanned and a live object is collected. The fix is a write barrier (shade the target grey), plus the same treatment for ephemeron updates and allocate-grey.Observable output = survivors + finalization order. Determinism requires a fixed order (here: allocation registration order).
R1 root keeps target live. R2 strong edges transitive. R3 weak never retains, cleared against final live set. R4 ephemeron {key,value} retains value iff cell live and key live, iterated to fixed point. R5 unreachable unfinalized finalizable object + closure retained one cycle; finalizer exactly once; reclaimed if not resurrected. R6 unreachable non-finalizable / already-finalized swept. R7 no post-sweep resurrection (stale handles throw).
INV-1 no BLACK → WHITE edge (Dijkstra insertion barrier).
finalized flag set before callback (at-most-once).gc.js)'use strict';
/*
* Deterministic simulator for a Wasm-GC-style managed heap with:
* - strong references and reference cycles
* - weak references
* - ephemerons (key is weak, value is strong iff key is strongly live)
* - finalizers with at-most-once semantics and documented ordering
* - incremental (slice-based) marking with a mutation write barrier
*
* Reachability rules implemented (the normative spec of this module):
* R1. A root keeps its target strongly live.
* R2. A strong edge from a live object keeps its target live (transitive).
* R3. A weak edge never keeps its target live. A weak reference whose target
* is not live at the end of a collection is cleared (permanently).
* R4. An ephemeron E is a cell {key, value}. If E is live and E.key is live,
* then E.value is live. This is iterated to a fixed point (handles
* transitive/cyclic ephemeron chains).
* R5. An unreachable object with an unfired finalizer is retained (together
* with its strong closure) for one collection. Its finalizer runs at the
* end of that collection, exactly once. After it fires it may be
* resurrected by the finalizer; otherwise it is collected next cycle.
* R6. Unreachable objects without finalizers (or whose finalizer already
* fired) are swept.
* R7. No object is ever resurrected after it has been swept: handles to
* swept objects become invalid and mutation attempts throw.
*
* Incremental correctness (tri-color invariant):
* INV-1 (no black -> white edge). During incremental marking, mutating a
* BLACK object to point at a WHITE object shades the WHITE object
* GREY (Dijkstra insertion barrier). This guarantees every object
* live at the end of the increment is marked.
* INV-2 (ephemeron consistency). Setting/altering an ephemeron on a BLACK
* cell whose key is already live shades the value.
* INV-3 (weak safety). Weak edges never shade; they are cleared only after
* finalizers have run and the final live set is fixed, so a finalizer
* resurrection cannot leave a dangling/restored weak reference.
*
* Determinism:
* - Traversal/graph iteration is ordered by object registration index (the
* order objects were allocated).
* - Finalizers fire in registration-index order.
*/
const WHITE = 0;
const GREY = 1;
const BLACK = 2;
class HeapObject {
constructor(id, reg) {
this.id = id;
this.reg = reg;
this.strong = new Set(); // ids of strong targets
this.weak = new Set(); // ids of weak targets
this.ephemeron = null; // { key: id, value: id }
this.finalizer = null; // { label, fn }
this.color = WHITE;
this.alive = true;
this.finalized = false;
this.pending = false; // retained for finalization this cycle
}
}
class GC {
constructor() {
this.objects = new Map();
this.roots = new Set();
this.finalizationLog = [];
this.weakClearLog = [];
this.barrierActivations = 0;
this._counter = 0;
this._reg = 0;
this._grey = [];
this.inc = null;
}
// ------------------------------------------------------------------ heap
newObject(id) {
if (id === undefined) id = `o${this._counter++}`;
id = String(id);
if (this.objects.has(id)) throw new Error(`duplicate object id: ${id}`);
const o = new HeapObject(id, this._reg++);
this.objects.set(id, o);
if (this.inc && this.inc.active) this._shade(o); // allocate-grey: never lost
return o;
}
obj(id) { return this.objects.get(String(id)); }
_must(id) {
const o = this.objects.get(String(id));
if (!o) throw new Error(`no such object (collected or never allocated): ${id}`);
return o;
}
addRoot(id) {
const o = this._must(id);
this.roots.add(o);
if (this.inc && this.inc.active) this._shade(o);
return o;
}
removeRoot(id) { this.roots.delete(this._must(id)); }
setStrong(fromId, toId) {
const from = this._must(fromId);
this._must(toId).alive = true;
from.strong.add(String(toId));
if (this.inc && this.inc.active) this._writeBarrier(from, String(toId));
}
deleteStrong(fromId, toId) { this._must(fromId).strong.delete(String(toId)); }
setWeak(fromId, toId) {
this._must(fromId).weak.add(String(toId));
}
deleteWeak(fromId, toId) { this._must(fromId).weak.delete(String(toId)); }
setEphemeron(ephId, keyId, valueId) {
const eph = this._must(ephId);
eph.ephemeron = { key: String(keyId), value: String(valueId) };
this._must(keyId);
this._must(valueId);
if (this.inc && this.inc.active) this._ephemeronBarrier(eph);
}
clearEphemeron(ephId) { this._must(ephId).ephemeron = null; }
setFinalizer(id, label, fn) {
this._must(id).finalizer = { label, fn: fn || null };
}
// -------------------------------------------------------- marking engine
_resetMarks() {
for (const o of this.objects.values()) {
o.color = WHITE;
o.pending = false;
}
this._grey.length = 0;
}
_shade(o) {
if (o && o.alive && o.color === WHITE) {
o.color = GREY;
this._grey.push(o);
}
}
_processGrey(limit = Infinity) {
let n = 0;
while (this._grey.length > 0 && n < limit) {
const o = this._grey.pop();
if (o.color !== GREY) continue;
for (const tid of o.strong) this._shade(this.objects.get(tid));
o.color = BLACK;
n++;
}
return this._grey.length === 0;
}
_markRoots() { for (const o of this.roots) this._shade(o); }
_sortedObjects() {
return [...this.objects.values()].sort((a, b) => a.reg - b.reg);
}
_ephemeronFixpoint() {
let changed = true;
while (changed) {
changed = false;
for (const o of this._sortedObjects()) {
if (o.color === WHITE || !o.ephemeron) continue;
const key = this.objects.get(o.ephemeron.key);
if (!key || key.color === WHITE) continue;
const val = this.objects.get(o.ephemeron.value);
if (!val || val.color !== WHITE) continue;
this._shade(val);
this._processGrey();
changed = true;
}
}
}
// Retain every unreachable, unfinalized, finalizable object plus its strong
// closure. Iterated with ephemerons to a joint fixed point. Returns newly
// queued objects (in registration order).
_retainUnreachableFinalizable() {
const queued = [];
let changed = true;
while (changed) {
changed = false;
this._ephemeronFixpoint();
for (const o of this._sortedObjects()) {
if (o.color === WHITE && o.finalizer && !o.finalized && !o.pending) {
o.pending = true;
queued.push(o);
this._shade(o);
this._processGrey();
changed = true;
}
}
}
this._ephemeronFixpoint();
return queued;
}
_runFinalizers(queued) {
queued.sort((a, b) => a.reg - b.reg); // deterministic, documented order
for (const o of queued) {
if (o.finalized) continue;
o.finalized = true; // at-most-once, before the callback runs
this.finalizationLog.push(o.finalizer.label);
if (o.finalizer.fn) o.finalizer.fn(o, this);
}
for (const o of queued) o.pending = false;
}
_clearWeak() {
for (const o of this._sortedObjects()) {
if (o.color === WHITE) continue; // owner is dying; its weak cells vanish
for (const tid of [...o.weak]) {
const t = this.objects.get(tid);
if (!t || t.color === WHITE) {
o.weak.delete(tid);
this.weakClearLog.push({ from: o.id, to: tid });
}
}
}
return this.weakClearLog;
}
_sweep() {
for (const o of [...this.objects.values()]) {
if (o.color === WHITE) {
o.alive = false;
this.objects.delete(o.id);
}
}
}
_finalMark() {
this._resetMarks();
this._markRoots();
this._processGrey();
this._ephemeronFixpoint();
}
_report() {
return {
alive: [...this.objects.values()].map((o) => o.id).sort(),
finalized: [...this.finalizationLog],
clearedWeak: [...this.weakClearLog],
barrierActivations: this.barrierActivations,
};
}
// ------------------------------------------------------- full collection
collectFull() {
// Phase A: mark roots + strong closure + ephemerons.
this._finalMark();
// Phase B: retain unreachable finalizable objects and run their finalizers.
const queued = this._retainUnreachableFinalizable();
this._runFinalizers(queued);
// Phase C: final live set from current roots. Any object that became
// unreachable as a side effect of finalization and still needs a finalizer
// is retained but deferred to the NEXT collection (no cascade this cycle),
// matching a single-generation finalization queue.
this._finalMark();
const deferred = this._retainUnreachableFinalizable();
for (const o of deferred) o.pending = false;
// Phase D: clear weak refs against the fixed live set, then sweep.
this._clearWeak();
this._sweep();
return this._report();
}
// -------------------------------------------------- incremental collection
startIncremental() {
if (this.inc && this.inc.active) throw new Error('incremental collection already active');
this._resetMarks();
this.inc = { active: true };
this._markRoots();
return this;
}
// Process at most `budget` grey objects. Returns true when no grey work and
// the ephemeron fixed point is stable.
step(budget = 1) {
if (!this.inc || !this.inc.active) throw new Error('no active incremental collection');
this._processGrey(budget);
if (this._grey.length === 0) {
this._ephemeronFixpoint();
return this._grey.length === 0;
}
return false;
}
isMarkingComplete() {
if (!this.inc || !this.inc.active) return false;
return this._grey.length === 0 && this._ephemeronsStable();
}
_ephemeronsStable() {
for (const o of this.objects.values()) {
if (o.color === WHITE || !o.ephemeron) continue;
const key = this.objects.get(o.ephemeron.key);
const val = this.objects.get(o.ephemeron.value);
if (key && key.color !== WHITE && val && val.color === WHITE) return false;
}
return true;
}
// Dijkstra insertion barrier: BLACK -> WHITE becomes BLACK -> GREY.
_writeBarrier(from, toId) {
if (from.color === BLACK) {
const t = this.objects.get(toId);
if (t && t.color === WHITE) {
this._shade(t);
this.barrierActivations++;
}
}
}
_ephemeronBarrier(eph) {
if (eph.color !== BLACK || !eph.ephemeron) return;
const key = this.objects.get(eph.ephemeron.key);
const val = this.objects.get(eph.ephemeron.value);
if (key && key.color !== WHITE && val && val.color === WHITE) {
this._shade(val);
this.barrierActivations++;
}
}
finishIncremental() {
if (!this.inc || !this.inc.active) throw new Error('no active incremental collection');
while (!this._processGrey(4096)) { /* drain */ }
this._ephemeronFixpoint();
const queued = this._retainUnreachableFinalizable();
this._runFinalizers(queued);
this.inc.active = false;
// Final live set with deferred finalizable retention (no cascade).
this._finalMark();
const deferred = this._retainUnreachableFinalizable();
for (const o of deferred) o.pending = false;
this._clearWeak();
this._sweep();
this.inc = null;
return this._report();
}
}
module.exports = { GC, WHITE, GREY, BLACK };
| Call | Meaning |
|---|---|
new GC() |
fresh heap |
newObject(id) |
allocate; auto-id if omitted |
addRoot(id) / removeRoot(id) |
root set (added roots shaded during marking) |
setStrong(a,b) / deleteStrong(a,b) |
strong edge, with write barrier |
setWeak(a,b) / deleteWeak(a,b) |
weak edge |
setEphemeron(e,key,val) / clearEphemeron(e) |
ephemeron, with barrier |
setFinalizer(id,label,fn) |
finalizer, at most once, registration order |
collectFull() |
stop-the-world collection |
startIncremental() / step(budget) / isMarkingComplete() / finishIncremental() |
sliced collection |
Returns { alive, finalized, clearedWeak, barrierActivations }.
Files: test.js, fuzz.js, demo.js. Commands:
node test.js # 19 deterministic unit tests
node fuzz.js # 400 static differential graphs + 300 mutating invariant runs
node demo.js # worked example
ok - strong roots are live; unreachable objects are swept
ok - reference cycles do not keep objects alive without a root
ok - weak edges never keep targets alive and are cleared
ok - weak target that is otherwise strongly live is not cleared
ok - ephemeron value dies when its key dies
ok - ephemeron value lives when its key lives
ok - ephemeron chains reach a fixed point transitively
ok - ephemeron cycle without an external root stays dead
ok - finalizers run in registration order
ok - finalizer fires at most once
ok - finalizer can resurrect its object exactly once
ok - objects reachable from a pending finalizable object are retained, not finalized
ok - swept objects cannot be resurrected (stale handle throws)
ok - without a barrier, a black->white edge would lose a live object
ok - incremental collection with slices matches full collection
ok - mutations between slices are captured by the barrier
ok - ephemeron mutation barrier during incremental marking
ok - objects allocated mid-incremental survive and are scanned
ok - weak ref cleared against the final live set, not the pre-final set
ok - static differential fuzz (400 random graphs)
ok - mutating tri-color invariant fuzz (300 random runs)
fuzz verification passed
For 400 random static graphs a sliced incremental collection produces the exact same alive/clearedWeak/finalized as a full collection. For 300 mutating runs, after every slice and mutation there is no BLACK → WHITE strong edge, and every root-reachable object at finish is alive.
node demo.js)after collect 1: {
"alive": [ "F2", "Holder", "Root" ],
"finalized": [ "F1" ],
"clearedWeak": [ { "from": "Holder", "to": "WeakTarget" } ],
"barrierActivations": 0
}
ephemeron key live: ["EphValue","Holder","Key","Root"]
WeakTarget is only weakly reachable → swept, weak cell cleared.Key unreachable → ephemeron does not retain EphValue; making Key a root activates it.F1 queued; closure retains F2, so only F1 finalizes this cycle; F2 finalizes next cycle._must throws on collected handles → no post-sweep resurrection.# Evidence - Problem class: js-20261009-wasm-gc-cyclic-finalizer-reachability-order - Model: openrouter/deepseek/deepseek-v4.1-flash - Solved: 2026-10-10T04:18:05.412Z - Verification: solution produced by pi in sandbox; see signatures.json
{"description": "Given a WebAssembly-GC heap graph with weak references, ephemerons, finalizers, and incremental collection slices, compute which objects survive and the observable finalization order under the specified reachability rules. Implement a deterministic simulator that handles cycles and mutation barriers without resurrecting objects incorrectly, and explain the invariants needed to match the collector semantics.", "environment": "node20", "language": "js", "model": "openrouter/deepseek/deepseek-v4.1-flash", "problem_class": "js-20261009-wasm-gc-cyclic-finalizer-reachability-order", "provider": "openrouter", "solved_at": "2026-10-10T04:18:05.413Z", "version": "20"}