Concurrent Mark-Sweep

// Concurrent mark-sweep: collector runs alongside the mutator, with two
// brief stop-the-world phases bracketing the concurrent work.
type Color = "white" | "gray" | "black";
interface Obj { color: Color; refs: Obj[]; }

class CMSCollector {
  private gray: Obj[] = [];

  collect(roots: Obj[], heap: Obj[], pauseMutators: (fn: () => void) => void) {
    // PHASE 1 — initial mark (STW): scan roots only, then resume mutators.
    pauseMutators(() => { for (const r of roots) this.shade(r); });

    // PHASE 2 — concurrent mark: trace the graph while the program runs.
    //   The mutator's writeBarrier() (below) feeds new work into 'gray'.
    while (this.gray.length) {
      const o = this.gray.pop()!;
      for (const c of o.refs) this.shade(c);
      o.color = "black";
    }

    // PHASE 3 — remark (STW): drain anything the barrier deferred.
    pauseMutators(() => {
      while (this.gray.length) {
        const o = this.gray.pop()!;
        for (const c of o.refs) this.shade(c);
        o.color = "black";
      }
    });

    // PHASE 4 — concurrent sweep: free white objects while the program runs.
    for (const o of heap) {
      if (o.color === "white") { /* free(o) */ }
      else o.color = "white"; // reset for next cycle
      // NOTE: objects orphaned after being blackened survive as floating garbage.
    }
  }

  /** Mutator write barrier (runs in parallel): keeps marking sound. */
  writeBarrier(target: Obj) { this.shade(target); }

  private shade(o: Obj) { if (o.color === "white") { o.color = "gray"; this.gray.push(o); } }
}