Spike: typed, stack-safe, single-concept foldAST for mvfm (issue #189)

async-spike.ts

// =============================================================
// ASYNC SPIKE: typed async generators + trampoline +
//              WeakMap memoization + taint tracking
// =============================================================

// --- Foundation types ----------------------------------------

interface Expr<T> {
  readonly kind: string;
  readonly __T?: T;
}

// --- Node shapes ---------------------------------------------

interface NumAdd extends Expr<number> {
  kind: "num/add";
  left: Expr<number>;
  right: Expr<number>;
}

interface NumLiteral extends Expr<number> {
  kind: "num/literal";
  value: number;
}

interface CoreLiteral<T = unknown> extends Expr<T> {
  kind: "core/literal";
  value: T;
}

interface CoreDiscard<T> extends Expr<T> {
  kind: "core/discard";
  steps: Expr<unknown>[];
  result: Expr<T>;
}

interface FetchRequest extends Expr<unknown> {
  kind: "fetch/request";
  url: Expr<string>;
}

// "volatile" node — value changes between evaluations (like cursor_batch, lambda_param)
interface Volatile<T> extends Expr<T> {
  kind: "test/volatile";
  __value?: T;
}

// prop access — like $.prop(obj, key)
interface PropAccess<T> extends Expr<T> {
  kind: "core/prop_access";
  object: Expr<Record<string, unknown>>;
  property: string;
}

// str
interface StrConcat extends Expr<string> {
  kind: "str/concat";
  parts: Expr<string>[];
}

interface StrLiteral extends Expr<string> {
  kind: "str/literal";
  value: string;
}

interface StrLen extends Expr<number> {
  kind: "str/len";
  operand: Expr<string>;
}

// boolean / eq / ord
interface BoolAnd extends Expr<boolean> {
  kind: "boolean/and";
  left: Expr<boolean>;
  right: Expr<boolean>;
}

// core
interface CoreCond<T> extends Expr<T> {
  kind: "core/cond";
  predicate: Expr<boolean>;
  then: Expr<T>;
  else: Expr<T>;
}

// console
interface ConsoleLog extends Expr<void> {
  kind: "console/log";
  args: Expr<unknown>[];
}

// fetch (extended)
interface FetchText extends Expr<string> {
  kind: "fetch/text";
  response: Expr<unknown>;
}

// cursor — evaluates body N times, mutating volatile between iterations
interface CursorLoop extends Expr<unknown> {
  kind: "test/cursor";
  items: unknown[];
  volatile: Volatile<unknown>;
  body: Expr<unknown>;
}

// --- eval_ helper --------------------------------------------

async function* eval_<T>(node: Expr<T>): AsyncGenerator<Expr<unknown>, T, unknown> {
  return (yield node) as T;
}

// --- Interpreter type ----------------------------------------

type Interpreter = Record<
  string,
  (node: any) => AsyncGenerator<Expr<unknown>, unknown, unknown>
>;

// --- Handler type: async generator that yields Expr, returns T ---

type Handler<N extends Expr<any>> =
  N extends Expr<infer T>
    ? (node: N) => AsyncGenerator<Expr<unknown>, T, unknown>
    : never;

// --- Volatile registry ---------------------------------------
// Plugins register which kinds are volatile.
// In production this would be part of the interpreter definition.

const VOLATILE_KINDS = new Set<string>(["test/volatile"]);

// --- FoldState: externalized cache + taint -------------------

interface FoldState {
  cache: WeakMap<Expr<unknown>, unknown>;
  tainted: WeakSet<Expr<unknown>>;
}

function createFoldState(): FoldState {
  return {
    cache: new WeakMap(),
    tainted: new WeakSet(),
  };
}

// --- Completeness check: fail fast before evaluation ---------

function checkCompleteness(interpreter: Interpreter, root: Expr<unknown>): void {
  const visited = new WeakSet<Expr<unknown>>();
  const missing = new Set<string>();
  const queue: Expr<unknown>[] = [root];
  while (queue.length > 0) {
    const node = queue.pop()!;
    if (visited.has(node)) continue;
    visited.add(node);
    if (!interpreter[node.kind]) missing.add(node.kind);
    for (const val of Object.values(node)) {
      if (val && typeof val === "object" && "kind" in val) queue.push(val as Expr<unknown>);
      if (Array.isArray(val)) for (const v of val) {
        if (v && typeof v === "object" && "kind" in v) queue.push(v as Expr<unknown>);
      }
    }
  }
  if (missing.size > 0) {
    throw new Error(`Missing interpreters for: ${[...missing].join(", ")}`);
  }
}

// --- foldAST with memoization + taint tracking ---------------

async function foldAST(
  interpreter: Interpreter,
  root: Expr<unknown>,
  state?: FoldState,
): Promise<unknown> {
  checkCompleteness(interpreter, root);

  type Frame = {
    gen: AsyncGenerator<Expr<unknown>, unknown, unknown>;
    node: Expr<unknown>;
    childNodes: Set<Expr<unknown>>; // track which children were evaluated
  };

  const { cache, tainted } = state ?? createFoldState();
  const stack: Frame[] = [];

  function isVolatile(node: Expr<unknown>): boolean {
    return VOLATILE_KINDS.has(node.kind);
  }

  function isTainted(node: Expr<unknown>): boolean {
    return tainted.has(node);
  }

  function push(node: Expr<unknown>): void {
    const h = interpreter[node.kind];
    if (!h) throw new Error(`No interpreter for: ${node.kind}`);
    stack.push({ gen: h(node), node, childNodes: new Set() });
  }

  push(root);
  let input: unknown = undefined;
  let pendingError: unknown = undefined;

  while (stack.length > 0) {
    const frame = stack[stack.length - 1];

    let result: IteratorResult<Expr<unknown>, unknown>;
    try {
      result =
        pendingError !== undefined
          ? await frame.gen.throw(pendingError)
          : await frame.gen.next(input);
      pendingError = undefined;
    } catch (e) {
      stack.pop();
      if (stack.length === 0) throw e;
      pendingError = e;
      continue;
    }

    if (result.done) {
      stack.pop();
      const value = result.value;

      // Determine if this node should be tainted:
      // - It's volatile itself, OR
      // - Any child it evaluated is tainted
      const shouldTaint =
        isVolatile(frame.node) ||
        [...frame.childNodes].some((c) => isTainted(c));

      if (shouldTaint) {
        tainted.add(frame.node);
        cache.delete(frame.node); // remove any optimistic entry
      } else {
        cache.set(frame.node, value);
      }

      // Record this node as a child of its parent (if any)
      if (stack.length > 0) {
        stack[stack.length - 1].childNodes.add(frame.node);
      }

      input = value;
      continue;
    }

    const child = result.value;

    // Record that parent evaluated this child
    frame.childNodes.add(child);

    // Check cache — but not for tainted nodes (they must re-evaluate)
    if (!isTainted(child) && cache.has(child)) {
      input = cache.get(child);
    } else {
      push(child);
      input = undefined;
    }
  }

  return input;
}

// --- Compile-time completeness: TypedProgram + typedFoldAST --

/** A program that carries its node kinds as a type parameter. */
interface TypedProgram<K extends string> {
  root: Expr<unknown>;
  readonly __kinds?: K;
}

/** Interpreter that must cover all kinds K — enforced at compile time. */
type CompleteInterpreter<K extends string> = {
  [key in K]: (node: any) => AsyncGenerator<Expr<unknown>, unknown, unknown>;
};

/**
 * Type-safe fold: compiler enforces the interpreter covers every node kind
 * in the program. Program goes first so K is inferred from it, then the
 * interpreter is checked against that K.
 */
async function typedFoldAST<K extends string>(
  program: TypedProgram<K>,
  interpreter: CompleteInterpreter<K>,
  state?: FoldState,
): Promise<unknown> {
  return foldAST(interpreter as Interpreter, program.root, state);
}

// =============================================================
// HANDLERS
// =============================================================

const baseInterpreter: Interpreter = {
  "num/add": async function* (node: NumAdd) {
    const l = yield* eval_(node.left);
    const r = yield* eval_(node.right);
    return l + r;
  },

  "num/literal": async function* (node: NumLiteral) {
    return node.value;
  },

  "core/literal": async function* <T>(node: CoreLiteral<T>) {
    return node.value;
  },

  "core/discard": async function* <T>(node: CoreDiscard<T>) {
    for (const step of node.steps) {
      yield* eval_(step);
    }
    return yield* eval_(node.result);
  },

  "core/prop_access": async function* (node: PropAccess<unknown>) {
    const obj = (yield* eval_(node.object)) as Record<string, unknown>;
    return obj[node.property];
  },

  "test/volatile": async function* (node: Volatile<unknown>) {
    return node.__value;
  },

  "fetch/request": async function* (node: FetchRequest) {
    const url = yield* eval_(node.url);
    const response = await new Promise<string>((resolve) =>
      setTimeout(() => resolve(`response from ${url}`), 5),
    );
    return response;
  },
};

// =============================================================
// TESTS
// =============================================================

let passed = 0;
let failed = 0;

function assert(name: string, actual: unknown, expected: unknown) {
  if (actual === expected) {
    console.log(`  PASS: ${name}`);
    passed++;
  } else {
    console.log(`  FAIL: ${name} — got ${JSON.stringify(actual)}, expected ${JSON.stringify(expected)}`);
    failed++;
  }
}

async function main() {
  // =========================================================
  // Test 1: Basic arithmetic still works
  // =========================================================
  console.log("\n--- 1. Basic arithmetic ---");
  const lit1: NumLiteral = { kind: "num/literal", value: 7 };
  const lit2: NumLiteral = { kind: "num/literal", value: 3 };
  const add: NumAdd = { kind: "num/add", left: lit1, right: lit2 };
  assert("7 + 3", await foldAST(baseInterpreter, add), 10);

  // =========================================================
  // Test 2: Async IO still works
  // =========================================================
  console.log("\n--- 2. Async IO ---");
  const url: CoreLiteral<string> = { kind: "core/literal", value: "https://example.com" };
  const req: FetchRequest = { kind: "fetch/request", url };
  assert("fetch", await foldAST(baseInterpreter, req), "response from https://example.com");

  // =========================================================
  // Test 3: DAG memoization — shared node evaluated ONCE
  // This is the "let binding" test.
  //
  //   const query = $.fetch(url)     // shared node
  //   $.discard(
  //     $.add(query, query),         // used twice
  //     literal(0)
  //   )
  //
  // fetch should execute ONCE, not twice.
  // =========================================================
  console.log("\n--- 3. DAG memoization (shared node = let binding) ---");
  let fetchCallCount = 0;
  const countingInterpreter: Interpreter = {
    ...baseInterpreter,
    "fetch/request": async function* (node: FetchRequest) {
      fetchCallCount++;
      const u = yield* eval_(node.url);
      return await new Promise<number>((resolve) =>
        setTimeout(() => resolve(42), 5),
      );
    },
  };

  const sharedFetch: FetchRequest = {
    kind: "fetch/request",
    url: { kind: "core/literal", value: "https://api.com" } as CoreLiteral<string>,
  };
  // Same node referenced twice as left and right
  const addShared: NumAdd = {
    kind: "num/add",
    left: sharedFetch as unknown as Expr<number>,
    right: sharedFetch as unknown as Expr<number>,
  };
  fetchCallCount = 0;
  const dagResult = await foldAST(countingInterpreter, addShared);
  assert("shared fetch called once", fetchCallCount, 1);
  assert("result is 42 + 42", dagResult, 84);

  // =========================================================
  // Test 4: Diamond dependency
  //
  //         add(A, B)
  //        /         \
  //   add(D, lit1)  add(D, lit2)
  //        \         /
  //            D (shared literal)
  //
  // D should be evaluated once.
  // =========================================================
  console.log("\n--- 4. Diamond dependency ---");
  let literalEvalCount = 0;
  const countingLitInterpreter: Interpreter = {
    ...baseInterpreter,
    "num/literal": async function* (node: NumLiteral) {
      literalEvalCount++;
      return node.value;
    },
  };

  const D: NumLiteral = { kind: "num/literal", value: 10 };
  const l1: NumLiteral = { kind: "num/literal", value: 1 };
  const l2: NumLiteral = { kind: "num/literal", value: 2 };
  const branchA: NumAdd = { kind: "num/add", left: D, right: l1 }; // 10 + 1 = 11
  const branchB: NumAdd = { kind: "num/add", left: D, right: l2 }; // 10 + 2 = 12
  const diamond: NumAdd = { kind: "num/add", left: branchA, right: branchB }; // 11 + 12 = 23

  literalEvalCount = 0;
  const diamondResult = await foldAST(countingLitInterpreter, diamond);
  assert("diamond result", diamondResult, 23);
  // D evaluated once, l1 once, l2 once = 3 total literal evals
  assert("D evaluated once (3 unique literals, 3 evals)", literalEvalCount, 3);

  // =========================================================
  // Test 5: Volatile nodes are NOT cached (cursor-like pattern)
  //
  // A cursor handler evaluates body multiple times WITHIN a
  // single foldAST call, mutating a volatile node each time.
  // The cache persists across iterations within the same fold,
  // so stable nodes are cached while tainted ones re-evaluate.
  //
  //   cursor(items=[{x:100},{x:200},{x:300}], volatile=batch,
  //          body=add(prop_access(batch,"x"), stableLit))
  //
  // On each iteration: volatile re-evaluated, prop_access
  // re-evaluated (tainted), stableLit cached after first eval.
  // =========================================================
  console.log("\n--- 5. Volatile nodes (taint tracking via cursor) ---");
  let volatileEvalCount = 0;
  let propAccessEvalCount = 0;
  let stableLitEvalCount = 0;
  const cursorResults: unknown[] = [];

  const taintInterpreter: Interpreter = {
    ...baseInterpreter,
    "test/volatile": async function* (node: Volatile<unknown>) {
      volatileEvalCount++;
      return node.__value;
    },
    "core/prop_access": async function* (node: PropAccess<unknown>) {
      propAccessEvalCount++;
      const obj = (yield* eval_(node.object)) as Record<string, unknown>;
      return obj[node.property];
    },
    "num/literal": async function* (node: NumLiteral) {
      stableLitEvalCount++;
      return node.value;
    },
    // Cursor handler: evaluates body once per item, mutating volatile
    "test/cursor": async function* (node: CursorLoop) {
      let lastResult: unknown;
      for (const item of node.items) {
        // Mutate the volatile node (like cursor_batch does)
        node.volatile.__value = item;
        // Evaluate the body — yields back to the trampoline
        lastResult = yield* eval_(node.body);
        cursorResults.push(lastResult);
      }
      return lastResult;
    },
  };

  const batch: Volatile<Record<string, unknown>> = {
    kind: "test/volatile",
    __value: { x: 100 },
  };
  const batchProp: PropAccess<number> = {
    kind: "core/prop_access",
    object: batch as unknown as Expr<Record<string, unknown>>,
    property: "x",
  };
  const stableLit: NumLiteral = { kind: "num/literal", value: 1 };
  // add(prop_access(volatile, "x"), stableLit)
  const taintedAdd: NumAdd = {
    kind: "num/add",
    left: batchProp as unknown as Expr<number>,
    right: stableLit,
  };

  // Cursor evaluates body 3 times within ONE foldAST call
  const cursor: CursorLoop = {
    kind: "test/cursor",
    items: [{ x: 100 }, { x: 200 }, { x: 300 }],
    volatile: batch as unknown as Volatile<unknown>,
    body: taintedAdd as unknown as Expr<unknown>,
  };

  volatileEvalCount = 0;
  propAccessEvalCount = 0;
  stableLitEvalCount = 0;
  cursorResults.length = 0;

  const cursorResult = await foldAST(taintInterpreter, cursor);

  assert("cursor final result", cursorResult, 301);
  assert("cursor collected results", JSON.stringify(cursorResults), JSON.stringify([101, 201, 301]));
  assert("volatile evaluated 3 times (once per iteration)", volatileEvalCount, 3);
  assert("prop_access evaluated 3 times (tainted)", propAccessEvalCount, 3);
  assert("stable literal evaluated ONCE (cached after iter 1)", stableLitEvalCount, 1);

  // =========================================================
  // Test 6: Mixed tainted and untainted in same tree
  //
  // Cursor iterates over:
  //   discard(
  //     add(batchProp, stableRate),   // batchProp tainted, stableRate stable
  //     stableRate,                   // stable, cached
  //   )
  //
  // stableQuery+stableRate should evaluate ONCE total.
  // batchProp+volatile re-evaluate each iteration.
  // =========================================================
  console.log("\n--- 6. Mixed tainted and untainted ---");
  let stableQueryCount = 0;
  volatileEvalCount = 0;
  const mixedInterpreter: Interpreter = {
    ...taintInterpreter,
    "fetch/request": async function* (node: FetchRequest) {
      stableQueryCount++;
      const u = yield* eval_(node.url);
      return await new Promise<Record<string, unknown>>((resolve) =>
        setTimeout(() => resolve({ rate: 0.1 }), 5),
      );
    },
  };

  const stableQuery: FetchRequest = {
    kind: "fetch/request",
    url: { kind: "core/literal", value: "https://config.com" } as CoreLiteral<string>,
  };
  const stableRate: PropAccess<number> = {
    kind: "core/prop_access",
    object: stableQuery as unknown as Expr<Record<string, unknown>>,
    property: "rate",
  };

  // discard(add(batchProp, stableRate), stableRate)
  const mixedTree: CoreDiscard<unknown> = {
    kind: "core/discard",
    steps: [
      {
        kind: "num/add",
        left: batchProp as unknown as Expr<number>,
        right: stableRate as unknown as Expr<number>,
      } as NumAdd,
    ],
    result: stableRate as unknown as Expr<unknown>,
  };

  // Cursor wraps the mixed tree
  const mixedCursor: CursorLoop = {
    kind: "test/cursor",
    items: [{ x: 10 }, { x: 20 }, { x: 30 }],
    volatile: batch as unknown as Volatile<unknown>,
    body: mixedTree as unknown as Expr<unknown>,
  };

  stableQueryCount = 0;
  volatileEvalCount = 0;
  cursorResults.length = 0;
  const mixResult = await foldAST(mixedInterpreter, mixedCursor);

  assert("mixed cursor final result (stableRate = 0.1)", mixResult, 0.1);
  assert("mixed cursor collected", JSON.stringify(cursorResults), JSON.stringify([0.1, 0.1, 0.1]));
  assert("stable query called ONCE across all iterations", stableQueryCount, 1);
  assert("volatile evaluated 3 times", volatileEvalCount, 3);

  // =========================================================
  // Test 7: Stack safety (100k depth, still works with memoization)
  // =========================================================
  console.log("\n--- 7. Stack safety (100k) ---");
  const DEPTH = 100_000;
  let node: Expr<number> = { kind: "num/literal", value: 1 } as NumLiteral;
  for (let i = 1; i < DEPTH; i++) {
    node = {
      kind: "num/add",
      left: node,
      right: { kind: "num/literal", value: 1 } as NumLiteral,
    } as NumAdd;
  }
  const start = performance.now();
  const deep = await foldAST(baseInterpreter, node);
  const ms = (performance.now() - start).toFixed(0);
  assert(`100k depth = ${DEPTH}`, deep, DEPTH);
  console.log(`  (${ms}ms)`);

  // =========================================================
  // Test 8: External state — cache persists across separate foldAST calls
  // =========================================================
  console.log("\n--- 8. External state (cache across calls) ---");
  let extLitCount = 0;
  const extInterpreter: Interpreter = {
    ...baseInterpreter,
    "num/literal": async function* (node: NumLiteral) {
      extLitCount++;
      return node.value;
    },
  };
  const sharedLit: NumLiteral = { kind: "num/literal", value: 42 };
  const extAdd: NumAdd = { kind: "num/add", left: sharedLit, right: sharedLit };

  const state = createFoldState();
  extLitCount = 0;
  const ext1 = await foldAST(extInterpreter, extAdd, state);
  assert("external state call 1", ext1, 84);
  assert("literal evaluated once (call 1)", extLitCount, 1);

  // Second call with same state — sharedLit should be cached
  extLitCount = 0;
  const ext2 = await foldAST(extInterpreter, extAdd, state);
  assert("external state call 2", ext2, 84);
  assert("literal CACHED (call 2)", extLitCount, 0);

  // =========================================================
  // Test 9: Completeness check — fail fast on missing handler
  // =========================================================
  console.log("\n--- 9. Completeness check ---");
  const incompleteInterpreter: Interpreter = {
    "num/add": baseInterpreter["num/add"],
    // deliberately missing "num/literal"
  };
  const simpleAdd: NumAdd = {
    kind: "num/add",
    left: { kind: "num/literal", value: 1 } as NumLiteral,
    right: { kind: "num/literal", value: 2 } as NumLiteral,
  };
  try {
    await foldAST(incompleteInterpreter, simpleAdd);
    assert("should have thrown", false, true);
  } catch (e: any) {
    assert("throws before evaluation", e.message.includes("Missing interpreters"), true);
    assert("names the missing kind", e.message.includes("num/literal"), true);
  }

  // Completeness check passes when all handlers present
  const completeResult = await foldAST(baseInterpreter, simpleAdd);
  assert("complete interpreter works", completeResult, 3);

  // =========================================================
  // Test 10: Compile-time completeness via typedFoldAST
  // =========================================================
  console.log("\n--- 10. Compile-time completeness (typedFoldAST) ---");
  const typedProg: TypedProgram<"num/add" | "num/literal"> = {
    root: simpleAdd,
  };
  // This compiles because both keys are present
  const typedResult = await typedFoldAST(typedProg, {
    "num/add": baseInterpreter["num/add"],
    "num/literal": baseInterpreter["num/literal"],
  });
  assert("typedFoldAST works", typedResult, 3);

  // Extra handlers beyond what the program needs — should work fine
  const typedResult2 = await typedFoldAST(typedProg, {
    "num/add": baseInterpreter["num/add"],
    "num/literal": baseInterpreter["num/literal"],
    "core/literal": baseInterpreter["core/literal"],
  } as CompleteInterpreter<"num/add" | "num/literal">);
  assert("extra handlers OK", typedResult2, 3);

  // =========================================================
  // Summary
  // =========================================================
  console.log(`\n=== ${passed} passed, ${failed} failed ===`);
  if (failed > 0) process.exit(1);
}

main().catch(console.error);

// =============================================================
// TYPE ERROR TESTS
// Each @ts-expect-error MUST suppress exactly one real error.
// If any becomes "unused", that's a type safety hole.
// =============================================================

// --- 1. Wrong child types in node construction ---------------

// 1a. NumAdd.left must be Expr<number>, not Expr<string>
function _test_bad_add() {
  const strNode: StrLiteral = { kind: "str/literal", value: "oops" };
  const numNode: NumLiteral = { kind: "num/literal", value: 1 };
  const bad: NumAdd = {
    kind: "num/add",
    // @ts-expect-error: StrLiteral not assignable to Expr<number>
    left: strNode,
    right: numNode,
  };
}

// 1b. BoolAnd.left must be Expr<boolean>, not Expr<number>
function _test_bad_and() {
  const numNode: NumLiteral = { kind: "num/literal", value: 42 };
  const boolNode: CoreLiteral<boolean> = { kind: "core/literal", value: true };
  const bad: BoolAnd = {
    kind: "boolean/and",
    // @ts-expect-error: NumLiteral not assignable to Expr<boolean>
    left: numNode,
    right: boolNode,
  };
}

// 1c. StrLen.operand must be Expr<string>, not Expr<number>
function _test_bad_strlen() {
  const numNode: NumLiteral = { kind: "num/literal", value: 5 };
  const bad: StrLen = {
    kind: "str/len",
    // @ts-expect-error: NumLiteral not assignable to Expr<string>
    operand: numNode,
  };
}

// 1d. CoreCond branches must match — Expr<number> not assignable to Expr<string>
function _test_bad_cond() {
  const predNode: CoreLiteral<boolean> = { kind: "core/literal", value: true };
  const strNode: CoreLiteral<string> = { kind: "core/literal", value: "yes" };
  const numNode: NumLiteral = { kind: "num/literal", value: 42 };
  const bad: CoreCond<string> = {
    kind: "core/cond",
    predicate: predNode,
    then: strNode,
    // @ts-expect-error: NumLiteral not assignable to Expr<string>
    else: numNode,
  };
}

// 1e. ConsoleLog args are Expr<unknown>[] — SHOULD pass (unknown accepts anything)
function _test_ok_console() {
  const numNode: NumLiteral = { kind: "num/literal", value: 1 };
  const strNode: StrLiteral = { kind: "str/literal", value: "hi" };
  const ok: ConsoleLog = {
    kind: "console/log",
    args: [numNode, strNode], // Expr<number> and Expr<string> both extend Expr<unknown>
  };
}

// --- 2. Wrong return type in handler (via Handler<N> type) ---

// 2a. num/add handler returning string instead of number
// @ts-expect-error: AsyncGenerator<..., string, ...> not assignable to AsyncGenerator<..., number, ...>
const _bad_num_ret: Handler<NumAdd> = async function* (node: NumAdd) {
  yield* eval_(node.left);
  yield* eval_(node.right);
  return "not a number" as string;
};

// 2b. boolean/and handler returning number instead of boolean
// @ts-expect-error: AsyncGenerator<..., number, ...> not assignable to AsyncGenerator<..., boolean, ...>
const _bad_bool_ret: Handler<BoolAnd> = async function* (node: BoolAnd) {
  yield* eval_(node.left);
  return 42 as number;
};

// 2c. Correct return — should PASS
const _ok_num_ret: Handler<NumAdd> = async function* (node: NumAdd) {
  const l = yield* eval_(node.left);
  const r = yield* eval_(node.right);
  return l + r; // number + number = number ✓
};

// --- 3. eval_ returns the correct phantom type ---------------

// 3a. eval_ of Expr<string> assigned to number — must fail
async function* _test_bad_eval_assignment() {
  const strNode: StrLiteral = { kind: "str/literal", value: "hi" };
  const s = yield* eval_(strNode); // s: string
  // @ts-expect-error: string not assignable to number
  const n: number = s;
}

// 3b. eval_ of Expr<number> — can't call .length
async function* _test_bad_eval_method() {
  const numNode: NumLiteral = { kind: "num/literal", value: 5 };
  const n = yield* eval_(numNode); // n: number
  // @ts-expect-error: .length doesn't exist on number
  const len: number = n.length;
}

// 3c. eval_ of Expr<boolean> assigned to string — must fail
async function* _test_bad_eval_bool_to_str() {
  const boolNode: CoreLiteral<boolean> = { kind: "core/literal", value: true };
  const b = yield* eval_(boolNode); // b: boolean
  // @ts-expect-error: boolean not assignable to string
  const s: string = b;
}

// 3d. eval_ of Expr<void> assigned to string — must fail
async function* _test_bad_eval_void_to_str() {
  const voidNode: ConsoleLog = { kind: "console/log", args: [] };
  const v = yield* eval_(voidNode); // v: void
  // @ts-expect-error: void not assignable to string
  const s: string = v;
}

// --- 4. Wrong field access on typed nodes --------------------

// 4a. StrConcat has 'parts', not 'left' — must fail
async function* _test_bad_field_access(node: StrConcat) {
  // @ts-expect-error: Property 'left' does not exist on type 'StrConcat'
  const l = yield* eval_(node.left);
}

// 4b. NumAdd has 'left'/'right', not 'operand' — must fail
async function* _test_bad_field_access2(node: NumAdd) {
  // @ts-expect-error: Property 'operand' does not exist on type 'NumAdd'
  const v = yield* eval_(node.operand);
}

// 4c. Correct field access — should PASS
async function* _test_ok_field_access(node: NumAdd) {
  const l = yield* eval_(node.left);  // ✓ number
  const r = yield* eval_(node.right); // ✓ number
  return l + r;
}

// --- 5. Cross-plugin type mismatch ---------------------------

// 5a. Passing Expr<number> where Expr<string> expected
function _test_cross_plugin_mismatch() {
  const numNode: NumLiteral = { kind: "num/literal", value: 42 };
  const bad: StrConcat = {
    kind: "str/concat",
    // @ts-expect-error: Expr<number>[] not assignable to Expr<string>[]
    parts: [numNode],
  };
}

// 5b. FetchText.response accepts Expr<unknown> — SHOULD pass with any Expr
function _test_fetch_accepts_unknown() {
  const numNode: NumLiteral = { kind: "num/literal", value: 42 };
  const ok: FetchText = {
    kind: "fetch/text",
    response: numNode, // Expr<number> extends Expr<unknown> ✓
  };
}

// --- 6. Compile-time completeness (typedFoldAST) -------------

// 6a. Missing handler — must fail at compile time
async function _test_incomplete_interpreter() {
  const prog: TypedProgram<"num/add" | "num/literal"> = {
    root: { kind: "num/add" } as NumAdd,
  };
  // @ts-expect-error: Property 'num/literal' is missing
  await typedFoldAST(prog, {
    "num/add": baseInterpreter["num/add"],
  });
}

// 6b. Both handlers present — should PASS
async function _test_complete_interpreter() {
  const prog: TypedProgram<"num/add" | "num/literal"> = {
    root: { kind: "num/add" } as NumAdd,
  };
  await typedFoldAST(prog, {
    "num/add": baseInterpreter["num/add"],
    "num/literal": baseInterpreter["num/literal"],
  });
}

// 6c. Missing one of three — must fail
async function _test_incomplete_three_kinds() {
  const prog: TypedProgram<"num/add" | "num/literal" | "core/literal"> = {
    root: { kind: "num/add" } as NumAdd,
  };
  // @ts-expect-error: Property 'core/literal' is missing
  await typedFoldAST(prog, {
    "num/add": baseInterpreter["num/add"],
    "num/literal": baseInterpreter["num/literal"],
  });
}

naive.ts

// Naive recursive evaluator — should blow the stack

interface Expr<T> {
  readonly kind: string;
  readonly __T?: T;
}

interface NumAdd extends Expr<number> {
  kind: "num/add";
  left: Expr<number>;
  right: Expr<number>;
}

interface NumLiteral extends Expr<number> {
  kind: "num/literal";
  value: number;
}

// Simple recursive eval — no trampoline
function evaluate(node: any): unknown {
  switch (node.kind) {
    case "num/add":
      return (evaluate(node.left) as number) + (evaluate(node.right) as number);
    case "num/literal":
      return node.value;
    default:
      throw new Error(`Unknown: ${node.kind}`);
  }
}

const DEPTH = 100_000;
let ast: any = { kind: "num/literal", value: 1 };
for (let i = 1; i < DEPTH; i++) {
  ast = { kind: "num/add", left: ast, right: { kind: "num/literal", value: 1 } };
}

console.log(`Naive recursive eval (depth=${DEPTH})...`);
try {
  const result = evaluate(ast);
  console.log(`Result: ${result}`);
} catch (e: any) {
  console.log(`BLEW UP: ${e.message.slice(0, 80)}`);
}