Mark-Compact

// Sliding (Lisp2-style) mark-compact: mark, compute new addresses,
// fix up every pointer, then slide survivors down to close the gaps.
type Ref = number; // an index into the heap array

interface Cell {
  marked: boolean;
  forward: Ref;        // computed new address
  refs: Ref[];         // outgoing pointers (heap indices)
  live: boolean;       // occupied slot?
}

class MarkCompactHeap {
  heap: (Cell | null)[] = [];
  roots: Ref[] = [];

  collect(): void {
    this.mark();
    this.computeForwarding();
    this.updatePointers();
    this.moveObjects();
  }

  private mark(): void {
    const work = [...this.roots];
    while (work.length) {
      const i = work.pop()!;
      const c = this.heap[i];
      if (!c || c.marked) continue;
      c.marked = true;
      work.push(...c.refs);
    }
  }

  // Pass 1: assign each live object its packed destination address.
  private computeForwarding(): void {
    let free = 0;
    for (let i = 0; i < this.heap.length; i++) {
      const c = this.heap[i];
      if (c && c.marked) c.forward = free++;
    }
  }

  // Pass 2: rewrite roots and references to the forwarding addresses.
  private updatePointers(): void {
    this.roots = this.roots.map((r) => this.heap[r]!.forward);
    for (const c of this.heap) {
      if (c && c.marked) c.refs = c.refs.map((r) => this.heap[r]!.forward);
    }
  }

  // Pass 3: slide each survivor down to its forwarding address.
  private moveObjects(): void {
    const next: (Cell | null)[] = [];
    for (const c of this.heap) {
      if (c && c.marked) {
        c.marked = false;          // reset for next cycle
        next[c.forward] = c;       // move (slide) into place
      }
    }
    this.heap = next;              // everything above the live block is free
  }
}