Garbage Collection: Mark & Sweep

import type { Tracer } from "../trace";/** The heap the collector walks; small enough to draw every word. */export const HEAP_WORDS = 32;export const MAX_OBJECTS = 16;export interface HeapObject {  id: string;  /** The block's first word. */  address: number;  size: number;  /** Ids of the objects this one points to. */  refs: readonly string[];}export interface Relocation {  id: string;  from: number;  to: number;  size: number;}export interface CollectionReport {  /** Ids marked reachable, in the order the mark phase reached them. */  marked: string[];  /** Ids the sweep freed, in address order. */  freed: string[];  liveWords: number;  freedWords: number;  /** Objects the compaction slid down, in address order; empty without compaction. */  moved: Relocation[];  /** The first word above the live objects after compaction, or the highest live word plus one without it. */  heapTop: number;  holes: number;  largestFree: number;}/** * A program that allocates on the heap must free what it no longer * uses, and a garbage collector does it for the program: it finds what * the program can still reach and frees the rest. Mark and sweep is the * oldest way. Mark: start from the roots (the variables on the stack * and the globals), follow every reference, and mark each object * reached; a worklist holds the objects whose references are still to * be followed, so a cycle is visited once. Sweep: walk the heap in * address order, keep the marked objects, free the unmarked. An object * nothing points to is garbage, but so is a cycle of objects that point * only at each other, which is what reference counting cannot see. * Sweeping leaves holes; an optional compaction slides the survivors * down so the free space is one block again, at the price of moving * objects, which means fixing every pointer to them. * * Time: O(live references + objects). Space: O(objects) for the worklist and marks. */export class MarkSweepCollector {  private readonly byId: Map<string, HeapObject>;  private readonly marked = new Set<string>();  constructor(    private readonly objects: readonly HeapObject[],    private readonly roots: readonly string[],    /** Slide the survivors down after the sweep. */    private readonly compact = false,    private readonly tracer?: Tracer,  ) {    if (objects.length > MAX_OBJECTS) throw new RangeError(`${objects.length} objects exceeds ${MAX_OBJECTS}`);    this.byId = new Map(objects.map((object) => [object.id, object]));    if (this.byId.size !== objects.length) throw new RangeError("object ids must be unique");    const sorted = [...objects].sort((a, b) => a.address - b.address);    let top = 0;    for (const object of sorted) {      if (!Number.isInteger(object.size) || object.size < 1) throw new RangeError(`object ${object.id} must be at least one word`);      if (object.address < top) throw new RangeError(`object ${object.id} overlaps the one below it`);      top = object.address + object.size;      if (top > HEAP_WORDS) throw new RangeError(`object ${object.id} ends past the ${HEAP_WORDS}-word heap`);      for (const ref of object.refs) if (!this.byId.has(ref)) throw new RangeError(`object ${object.id} points to unknown ${ref}`);    }    for (const root of roots) if (!this.byId.has(root)) throw new RangeError(`root ${root} is not an object`);  }  /** Mark from the roots, sweep the heap, and compact if asked. */  collect(): CollectionReport {    const marked = this.mark();    const { survivors, freed, freedWords } = this.sweep();    const { liveObjects, freed, freedWords } = this.sweep();    const moved = this.compact ? this.slide(survivors) : [];    const moved = this.compact ? this.slide(liveObjects) : [];    const placed = survivors.map((object) => {    const placed = liveObjects.map((object) => {      const move = moved.find((m) => m.id === object.id);      return move ? { ...object, address: move.to } : object;    });    const heapTop = placed.reduce((top, object) => Math.max(top, object.address + object.size), 0);    const holes = MarkSweepCollector.holes(placed, heapTop);    return {      marked,      freed,      liveWords: survivors.reduce((sum, object) => sum + object.size, 0),      liveWords: liveObjects.reduce((sum, object) => sum + object.size, 0),      freedWords,      moved,      heapTop,      holes: holes.length,      largestFree: holes.reduce((max, hole) => Math.max(max, hole.size), 0),    };  }  /** The mark phase: a depth-first walk from the roots over a worklist, each object marked once. */  private mark(): string[] {    const order: string[] = [];    const worklist: string[] = [];    const objectsToVisit: string[] = [];    for (const root of this.roots) {      const object = this.byId.get(root)!;      worklist.push(root);      objectsToVisit.push(root);      // ▸ the roots are where the program can start from: every variable on the stack and every global      this.tracer?.emit("root", { id: root, address: object.address, pending: worklist.length });      this.tracer?.emit("root", { id: root, address: object.address, pending: objectsToVisit.length });    }    while (worklist.length > 0) {    while (objectsToVisit.length > 0) {      const id = worklist.pop()!;      const id = objectsToVisit.pop()!;      if (this.marked.has(id)) continue;      this.marked.add(id);      order.push(id);      const object = this.byId.get(id)!;      // Follow the references; an object already marked is skipped when it comes off the list.      const followed = object.refs.filter((ref) => !this.marked.has(ref));      worklist.push(...followed);      objectsToVisit.push(...followed);      // ▸ an object taken off the worklist is marked live, and the objects it points to join the list      this.tracer?.emit("mark", { id, address: object.address, size: object.size, refs: [...object.refs], followed, marked: this.marked.size, pending: worklist.length });      this.tracer?.emit("mark", { id, address: object.address, size: object.size, refs: [...object.refs], followed, marked: this.marked.size, pending: objectsToVisit.length });    }    return order;  }  /** The sweep phase: every object in address order is kept or freed by its mark. */  private sweep(): { survivors: HeapObject[]; freed: string[]; freedWords: number } {  private sweep(): { liveObjects: HeapObject[]; freed: string[]; freedWords: number } {    const survivors: HeapObject[] = [];    const liveObjects: HeapObject[] = [];    const freed: string[] = [];    let liveWords = 0;    let freedWords = 0;    for (const object of [...this.objects].sort((a, b) => a.address - b.address)) {      if (this.marked.has(object.id)) {        survivors.push(object);        liveObjects.push(object);        liveWords += object.size;        // ▸ a marked object survives the sweep        this.tracer?.emit("keep", { id: object.id, address: object.address, size: object.size, liveWords });      } else {        freed.push(object.id);        freedWords += object.size;        // ▸ an unmarked object is garbage: nothing the program can reach points at it, so its words go back        this.tracer?.emit("free", { id: object.id, address: object.address, size: object.size, refs: [...object.refs], freedWords });      }    }    return { survivors, freed, freedWords };    return { liveObjects, freed, freedWords };  }  /** Compaction: survivors slide down in address order, so the free words end up in one block at the top. */  private slide(survivors: readonly HeapObject[]): Relocation[] {  private slide(liveObjects: readonly HeapObject[]): Relocation[] {    const moved: Relocation[] = [];    let top = 0;    for (const object of survivors) {    for (const object of liveObjects) {      if (object.address !== top) {        moved.push({ id: object.id, from: object.address, to: top, size: object.size });        // ▸ compaction slides a survivor down over the holes; every pointer to it must be fixed        this.tracer?.emit("move", { id: object.id, from: object.address, to: top, size: object.size, pointers: this.pointersTo(object.id) });      }      top += object.size;    }    return moved;  }  /** How many references (roots included) point at an object: what a reference counter would keep for it. */  private pointersTo(id: string): number {    return MarkSweepCollector.referenceCounts(this.objects, this.roots).get(id) ?? 0;  }  /** Incoming references per object, roots counted: reference counting's view, which keeps a cycle alive. */  static referenceCounts(objects: readonly HeapObject[], roots: readonly string[]): Map<string, number> {    const counts = new Map<string, number>(objects.map((object) => [object.id, 0]));    for (const root of roots) counts.set(root, (counts.get(root) ?? 0) + 1);    for (const object of objects) for (const ref of object.refs) counts.set(ref, (counts.get(ref) ?? 0) + 1);    return counts;  }  /** The free runs between and above the given objects, below the heap's end. */  static holes(objects: readonly HeapObject[], heapTop: number): { address: number; size: number }[] {    const holes: { address: number; size: number }[] = [];    let cursor = 0;    for (const object of [...objects].sort((a, b) => a.address - b.address)) {      if (object.address > cursor) holes.push({ address: cursor, size: object.address - cursor });      cursor = object.address + object.size;    }    if (heapTop < HEAP_WORDS) holes.push({ address: heapTop, size: HEAP_WORDS - heapTop });    return holes;  }}