Expr<O, R> spike: content-addressed DAG with type-safe AST rewrites (issue #190)

spike-bidir-gc.ts

// ============================================================
// Spike: Bidirectional graph + type-level gc via parent chains
// ============================================================
//
// Hypothesis: storing reverse adj (child → parents) enables gc
// without forward graph traversal. Each orphan check walks UP
// the parent chain to root — bounded by tree DEPTH, not node COUNT.
// ============================================================

// ============================================================
// Core types
// ============================================================

type NodeEntry<Kind extends string, ChildIDs extends string[], Out> = {
  readonly kind: Kind;
  readonly children: ChildIDs;
  readonly out: Out;
};

// RevEntry: who are my parents?
type RevEntry<ParentIDs extends string[]> = {
  readonly parents: ParentIDs;
};

// Desc now carries both forward and reverse adj
type Desc<
  Out,
  ID extends string,
  Adj extends Record<string, any>,
  Rev extends Record<string, any>,
  C extends string,
> = {
  readonly o: Out;
  readonly id: ID;
  readonly adj: Adj;
  readonly rev: Rev;
  readonly c: C;
};

declare const exprBrand: unique symbol;
interface Expr<O, R extends Desc<O, string, Record<string, any>, Record<string, any>, string>> {
  readonly [exprBrand]: R;
}

type IdOf<R> = R extends Desc<any, infer ID, any, any, any> ? ID : never;
type AdjOf<R> = R extends Desc<any, any, infer A, any, any> ? A : never;
type RevOf<R> = R extends Desc<any, any, any, infer Rev, any> ? Rev : never;
type CtrOf<R> = R extends Desc<any, any, any, any, infer C> ? C : never;

// ============================================================
// IsLive: walk parent chain to root — O(depth) recursion
// ============================================================

type IsLive<
  Rev extends Record<string, any>,
  RootID extends string,
  K extends string,
  Visited extends string = never,
> =
  K extends Visited ? false :  // cycle guard
  K extends RootID ? true :
  K extends keyof Rev
    ? Rev[K] extends RevEntry<infer Parents extends string[]>
      ? AnyParentLive<Rev, RootID, Parents, Visited | K>
      : false
    : false;

type AnyParentLive<
  Rev extends Record<string, any>,
  RootID extends string,
  Parents extends string[],
  Visited extends string,
> =
  Parents extends [infer H extends string, ...infer T extends string[]]
    ? IsLive<Rev, RootID, H, Visited> extends true ? true
      : AnyParentLive<Rev, RootID, T, Visited>
    : false;

// ============================================================
// GC: filter adj to live nodes only
// ============================================================

type GCAdj<
  Adj extends Record<string, any>,
  Rev extends Record<string, any>,
  RootID extends string,
> = {
  [K in keyof Adj as K extends string
    ? IsLive<Rev, RootID, K> extends true ? K : never
    : never
  ]: Adj[K];
};

type GCRev<
  Rev extends Record<string, any>,
  Adj extends Record<string, any>,
  RootID extends string,
> = {
  [K in keyof Rev as K extends string
    ? IsLive<Rev, RootID, K> extends true ? K : never
    : never
  ]: Rev[K];
};

// ============================================================
// Test 1: clean graph — nothing removed
// ============================================================

// (3 + 4) * 5
// a: lit(3), b: lit(4), c: add(a,b), d: lit(5), e: mul(c,d)
type TA = {
  a: NodeEntry<"num/literal", [], number>;
  b: NodeEntry<"num/literal", [], number>;
  c: NodeEntry<"num/add", ["a", "b"], number>;
  d: NodeEntry<"num/literal", [], number>;
  e: NodeEntry<"num/mul", ["c", "d"], number>;
};

type TR = {
  a: RevEntry<["c"]>;       // a's parent is c
  b: RevEntry<["c"]>;       // b's parent is c
  c: RevEntry<["e"]>;       // c's parent is e
  d: RevEntry<["e"]>;       // d's parent is e
  e: RevEntry<[]>;           // root, no parents
};

type GC1 = GCAdj<TA, TR, "e">;
type GC1Keys = keyof GC1;

// All nodes reachable
const _1a: GC1Keys = "a";
const _1b: GC1Keys = "b";
const _1c: GC1Keys = "c";
const _1d: GC1Keys = "d";
const _1e: GC1Keys = "e";

// ============================================================
// Test 2: direct orphan — removed by single pass
// ============================================================

type TA2 = TA & {
  x: NodeEntry<"orphan", [], string>;
};
type TR2 = TR & {
  x: RevEntry<[]>;  // no parents
};

type GC2 = GCAdj<TA2, TR2, "e">;
type GC2Keys = keyof GC2;

const _2a: GC2Keys = "a";
const _2e: GC2Keys = "e";
// @ts-expect-error — x is orphan, removed
const _2x: GC2Keys = "x";

// ============================================================
// Test 3: ORPHAN CHAIN — the hard case
// ============================================================

type TA3 = TA & {
  x: NodeEntry<"orphan/root", [], string>;
  y: NodeEntry<"orphan/mid", ["x"], string>;
  z: NodeEntry<"orphan/leaf", ["y"], string>;
};
type TR3 = TR & {
  x: RevEntry<["y"]>;    // x's parent is y
  y: RevEntry<["z"]>;    // y's parent is z
  z: RevEntry<[]>;        // z has no parent — chain root
};

type GC3 = GCAdj<TA3, TR3, "e">;
type GC3Keys = keyof GC3;

// Original nodes still live
const _3a: GC3Keys = "a";
const _3e: GC3Keys = "e";

// ENTIRE orphan chain removed — IsLive walks up z→(no parent)→dead,
// then y→z→dead, then x→y→z→dead
// @ts-expect-error — x is in orphan chain
const _3x: GC3Keys = "x";
// @ts-expect-error — y is in orphan chain
const _3y: GC3Keys = "y";
// @ts-expect-error — z is orphan chain root
const _3z: GC3Keys = "z";

// ============================================================
// Test 4: diamond DAG — shared node reachable via either parent
// ============================================================

type TA4 = {
  a: NodeEntry<"val", [], number>;
  b: NodeEntry<"use1", ["a"], number>;
  c: NodeEntry<"use2", ["a"], number>;
  d: NodeEntry<"join", ["b", "c"], number>;
};
type TR4 = {
  a: RevEntry<["b", "c"]>;   // a has TWO parents
  b: RevEntry<["d"]>;
  c: RevEntry<["d"]>;
  d: RevEntry<[]>;
};

type GC4 = GCAdj<TA4, TR4, "d">;
type GC4Keys = keyof GC4;

const _4a: GC4Keys = "a";
const _4b: GC4Keys = "b";
const _4c: GC4Keys = "c";
const _4d: GC4Keys = "d";

// ============================================================
// Test 5: mixed — some live, some orphaned, some in chains
// ============================================================

type TA5 = {
  a: NodeEntry<"lit", [], number>;
  b: NodeEntry<"lit", [], number>;
  c: NodeEntry<"add", ["a", "b"], number>;
  // orphan island
  p: NodeEntry<"dead/1", [], string>;
  q: NodeEntry<"dead/2", ["p"], string>;
  // another orphan
  r: NodeEntry<"dead/3", [], boolean>;
};
type TR5 = {
  a: RevEntry<["c"]>;
  b: RevEntry<["c"]>;
  c: RevEntry<[]>;      // root
  p: RevEntry<["q"]>;
  q: RevEntry<[]>;      // orphan chain root
  r: RevEntry<[]>;      // lone orphan
};

type GC5 = GCAdj<TA5, TR5, "c">;
type GC5Keys = keyof GC5;

const _5a: GC5Keys = "a";
const _5b: GC5Keys = "b";
const _5c: GC5Keys = "c";
// @ts-expect-error — p in orphan chain
const _5p: GC5Keys = "p";
// @ts-expect-error — q orphan chain root
const _5q: GC5Keys = "q";
// @ts-expect-error — r lone orphan
const _5r: GC5Keys = "r";

// ============================================================
// Test 6: deeper chain — depth 6 (tests recursion limits)
// ============================================================

type TA6 = {
  a: NodeEntry<"n", [], number>;
  b: NodeEntry<"n", ["a"], number>;
  c: NodeEntry<"n", ["b"], number>;
  d: NodeEntry<"n", ["c"], number>;
  e: NodeEntry<"n", ["d"], number>;
  f: NodeEntry<"n", ["e"], number>;
  // orphan chain depth 6
  o1: NodeEntry<"dead", [], string>;
  o2: NodeEntry<"dead", ["o1"], string>;
  o3: NodeEntry<"dead", ["o2"], string>;
  o4: NodeEntry<"dead", ["o3"], string>;
  o5: NodeEntry<"dead", ["o4"], string>;
  o6: NodeEntry<"dead", ["o5"], string>;
};
type TR6 = {
  a: RevEntry<["b"]>;
  b: RevEntry<["c"]>;
  c: RevEntry<["d"]>;
  d: RevEntry<["e"]>;
  e: RevEntry<["f"]>;
  f: RevEntry<[]>;        // root
  o1: RevEntry<["o2"]>;
  o2: RevEntry<["o3"]>;
  o3: RevEntry<["o4"]>;
  o4: RevEntry<["o5"]>;
  o5: RevEntry<["o6"]>;
  o6: RevEntry<[]>;       // orphan chain root
};

type GC6 = GCAdj<TA6, TR6, "f">;
type GC6Keys = keyof GC6;

// Live chain
const _6a: GC6Keys = "a";
const _6f: GC6Keys = "f";

// Dead chain — all 6 removed
// @ts-expect-error — o1 in orphan chain
const _6o1: GC6Keys = "o1";
// @ts-expect-error — o6 orphan chain root
const _6o6: GC6Keys = "o6";

// ============================================================
// Test 7: compare recursion — forward vs reverse
// ============================================================

// Forward Reachable from spike-typed-transforms.ts (for comparison):
type ReachableFwd<Adj, ID extends string, Visited extends string = never> =
  ID extends Visited ? Visited :
  ID extends keyof Adj
    ? Adj[ID] extends NodeEntry<any, infer Children extends string[], any>
      ? ReachableAllFwd<Adj, Children, Visited | ID>
      : Visited | ID
    : Visited | ID;

type ReachableAllFwd<Adj, IDs extends string[], Visited extends string> =
  IDs extends [infer H extends string, ...infer T extends string[]]
    ? ReachableAllFwd<Adj, T, ReachableFwd<Adj, H, Visited>>
    : Visited;

// Forward gc processes ALL nodes in one recursive tree.
// Depth = total reachable nodes (worst case = all nodes).
//
// Reverse gc checks each node independently.
// Depth per node = path from node to root via parents.
// For a balanced binary tree of 1000 nodes: depth ~10.
// Forward would be: depth ~1000.
//
// The reverse approach scales to much larger graphs.

// ============================================================
// Verify: forward and reverse agree on test 5
// ============================================================

type FwdGC5 = {
  [K in keyof TA5 as K extends ReachableFwd<TA5, "c"> ? K : never]: TA5[K];
};
type FwdGC5Keys = keyof FwdGC5;

// Both approaches produce the same result
const _fwd5a: FwdGC5Keys = "a";
const _fwd5b: FwdGC5Keys = "b";
const _fwd5c: FwdGC5Keys = "c";
// @ts-expect-error
const _fwd5p: FwdGC5Keys = "p";
// @ts-expect-error
const _fwd5q: FwdGC5Keys = "q";
// @ts-expect-error
const _fwd5r: FwdGC5Keys = "r";

console.log("spike-bidir-gc compiled successfully");

spike-bridge.ts

// ============================================================
// Spike: Bridging types and runtime — no `any`, no `declare`
// ============================================================
//
// Previous spikes proved types and runtime SEPARATELY:
//   - spike-typed-transforms.ts: `declare function` (no runtime)
//   - spike-dagql-runtime.ts: real runtime (all `any` types)
//
// This spike proves they work TOGETHER in a single implementation.
// ============================================================

import { IDChain } from "./spike-idchain";

// ============================================================
// Core types
// ============================================================

type NodeEntry<Kind extends string, ChildIDs extends string[], Out> = {
  readonly kind: Kind;
  readonly children: ChildIDs;
  readonly out: Out;
};

type Desc<Out, ID extends string, Adj extends Record<string, any>, C extends string> = {
  readonly o: Out; readonly id: ID; readonly adj: Adj; readonly c: C;
};

type NextID<C extends keyof IDChain> = IDChain[C];

declare const exprBrand: unique symbol;

// Expr: branded with phantom type, but also carries runtime data
interface Expr<O, R extends Desc<O, string, Record<string, any>, string>> {
  readonly [exprBrand]: R;
  readonly __id: string;
  readonly __adj: Record<string, { kind: string; children: string[]; out: unknown }>;
  readonly __counter: string;
}

type IdOf<R> = R extends Desc<any, infer ID, any, any> ? ID : never;
type AdjOf<R> = R extends Desc<any, any, infer A, any> ? A : never;
type CtrOf<R> = R extends Desc<any, any, any, infer C> ? C : never;

// ============================================================
// Predicates
// ============================================================

interface KindPred<K extends string> {
  readonly tag: "kind";
  readonly kind: K;
  readonly eval: (e: { kind: string; children: string[]; out: unknown }) => boolean;
}

interface KindGlobPred<P extends string> {
  readonly tag: "kindGlob";
  readonly prefix: P;
  readonly eval: (e: { kind: string; children: string[]; out: unknown }) => boolean;
}

interface LeafPred {
  readonly tag: "leaf";
  readonly eval: (e: { kind: string; children: string[]; out: unknown }) => boolean;
}

interface NotPred<Inner> {
  readonly tag: "not";
  readonly inner: Inner;
  readonly eval: (e: { kind: string; children: string[]; out: unknown }) => boolean;
}

interface AndPred<A, B> {
  readonly tag: "and";
  readonly left: A;
  readonly right: B;
  readonly eval: (e: { kind: string; children: string[]; out: unknown }) => boolean;
}

type EvalPred<P, Entry> =
  P extends KindPred<infer K>
    ? Entry extends NodeEntry<K, any, any> ? true : false
  : P extends KindGlobPred<infer Prefix>
    ? Entry extends NodeEntry<`${Prefix}${string}`, any, any> ? true : false
  : P extends LeafPred
    ? Entry extends NodeEntry<any, infer C, any> ? C extends [] ? true : false : false
  : P extends NotPred<infer Inner>
    ? EvalPred<Inner, Entry> extends true ? false : true
  : P extends AndPred<infer A, infer B>
    ? EvalPred<A, Entry> extends true
      ? EvalPred<B, Entry> extends true ? true : false : false
  : never;

// ============================================================
// Predicate constructors (real runtime)
// ============================================================

type RE = { kind: string; children: string[]; out: unknown };

function byKind<K extends string>(k: K): KindPred<K> {
  return { tag: "kind", kind: k, eval: (e: RE) => e.kind === k };
}

function byKindGlob<P extends string>(prefix: P): KindGlobPred<P> {
  return { tag: "kindGlob", prefix, eval: (e: RE) => e.kind.startsWith(prefix) };
}

function isLeaf(): LeafPred {
  return { tag: "leaf", eval: (e: RE) => e.children.length === 0 };
}

function not<Inner extends { eval: (e: RE) => boolean }>(inner: Inner): NotPred<Inner> {
  return { tag: "not", inner, eval: (e: RE) => !inner.eval(e) };
}

function and<
  A extends { eval: (e: RE) => boolean },
  B extends { eval: (e: RE) => boolean },
>(a: A, b: B): AndPred<A, B> {
  return { tag: "and", left: a, right: b, eval: (e: RE) => a.eval(e) && b.eval(e) };
}

// ============================================================
// MapAdj type (from spike-typed-transforms, proven)
// ============================================================

type MatchingEntries<Adj, P> = {
  [K in keyof Adj]: EvalPred<P, Adj[K]> extends true ? Adj[K] : never;
}[keyof Adj];

type MapAdj<Adj, P, NewEntry> = {
  [K in keyof Adj]: EvalPred<P, Adj[K]> extends true ? NewEntry : Adj[K];
};

type MapOut<O, Adj, RootID extends string & keyof Adj, P, NewEntry> =
  EvalPred<P, Adj[RootID]> extends true
    ? NewEntry extends NodeEntry<any, any, infer NO> ? NO : O
    : O;

// ============================================================
// makeExpr: the ONE place we bridge types and runtime
// ============================================================

function makeExpr<
  O,
  ID extends string,
  Adj extends Record<string, any>,
  C extends string,
>(
  id: ID,
  adj: Record<string, { kind: string; children: string[]; out: unknown }>,
  counter: C,
): Expr<O, Desc<O, ID, Adj, C>> {
  return {
    __id: id,
    __adj: adj,
    __counter: counter,
  } as unknown as Expr<O, Desc<O, ID, Adj, C>>;
  // ^^^ This single cast is the bridge. The runtime fields (__id, __adj, __counter)
  // carry the data. The phantom type R tracks the precise types. We trust that
  // callers construct adj correctly — which is enforced by the typed API above them.
}

// ============================================================
// selectWhere: real runtime + real types
// ============================================================

function selectWhere<
  O,
  R extends Desc<O, string, Record<string, any>, string>,
  P,
>(
  expr: Expr<O, R>,
  pred: { eval: (e: RE) => boolean },
): Set<string & keyof { [K in keyof AdjOf<R> as EvalPred<P, AdjOf<R>[K]> extends true ? K : never]: 1 }> {
  const result = new Set<string>();
  for (const [id, entry] of Object.entries(expr.__adj)) {
    if (!id.startsWith("@") && pred.eval(entry as RE)) {
      result.add(id);
    }
  }
  return result as any; // runtime Set<string> → typed Set<matched keys>
}

// ============================================================
// mapWhere: real runtime + real types
// ============================================================

function mapWhere<
  O,
  R extends Desc<O, string, Record<string, any>, string>,
  P extends { eval: (e: RE) => boolean },
  NE extends NodeEntry<string, string[], any>,
>(
  expr: Expr<O, R>,
  pred: P,
  fn: (entry: MatchingEntries<AdjOf<R>, P>) => NE,
): Expr<
  MapOut<O, AdjOf<R>, IdOf<R> & string & keyof AdjOf<R>, P, NE>,
  Desc<
    MapOut<O, AdjOf<R>, IdOf<R> & string & keyof AdjOf<R>, P, NE>,
    IdOf<R>,
    MapAdj<AdjOf<R>, P, NE>,
    CtrOf<R>
  >
> {
  const newAdj: Record<string, { kind: string; children: string[]; out: unknown }> = {};
  for (const [id, entry] of Object.entries(expr.__adj)) {
    if (!id.startsWith("@") && pred.eval(entry as RE)) {
      newAdj[id] = fn(entry as MatchingEntries<AdjOf<R>, P>);
    } else {
      newAdj[id] = entry;
    }
  }
  return makeExpr(expr.__id, newAdj, expr.__counter) as any;
}

// ============================================================
// wrapByName: real runtime + real types
// ============================================================

type RewireList<T extends string[], Old extends string, New extends string> =
  T extends [infer H extends string, ...infer Rest extends string[]]
    ? [H extends Old ? New : H, ...RewireList<Rest, Old, New>]
    : [];

type RewireParents<Adj, TargetID extends string, WrapperID extends string> = {
  [K in keyof Adj]: Adj[K] extends NodeEntry<infer Kind, infer Children extends string[], infer Out>
    ? NodeEntry<Kind, RewireList<Children, TargetID, WrapperID>, Out>
    : Adj[K];
};

type WrapOneResult<
  Adj extends Record<string, any>,
  TargetID extends string,
  WrapperKind extends string,
  C extends string & keyof IDChain,
> = RewireParents<Adj, TargetID, C> & Record<
  C,
  NodeEntry<WrapperKind, [TargetID], Adj[TargetID] extends NodeEntry<any, any, infer O> ? O : never>
>;

function wrapByName<
  O,
  R extends Desc<O, string, Record<string, any>, string>,
  TargetID extends string & keyof AdjOf<R>,
  WrapperKind extends string,
>(
  expr: Expr<O, R>,
  targetId: TargetID,
  wrapperKind: WrapperKind,
): CtrOf<R> extends string & keyof IDChain
  ? Expr<
      O,
      Desc<
        O,
        IdOf<R> extends TargetID ? CtrOf<R> & string : IdOf<R>,
        WrapOneResult<AdjOf<R>, TargetID, WrapperKind, CtrOf<R> & keyof IDChain>,
        NextID<CtrOf<R> & keyof IDChain> & string
      >
    >
  : never {
  const wrapperId = expr.__counter;
  const targetEntry = expr.__adj[targetId] as RE;

  // Build new adj: rewire parents, add wrapper
  const newAdj: Record<string, { kind: string; children: string[]; out: unknown }> = {};
  for (const [id, entry] of Object.entries(expr.__adj)) {
    const e = entry as RE;
    newAdj[id] = {
      kind: e.kind,
      children: e.children.map((c: string) => c === targetId ? wrapperId : c),
      out: e.out,
    };
  }
  // Add wrapper entry
  newAdj[wrapperId] = {
    kind: wrapperKind,
    children: [targetId],
    out: targetEntry.out,
  };

  // Root changes if we wrapped the root
  const newRoot = expr.__id === targetId ? wrapperId : expr.__id;

  // Advance counter (runtime: look up next ID)
  // In real impl this would use a runtime ID chain. For spike, hardcode the pattern.
  const nextCounter = String.fromCharCode(wrapperId.charCodeAt(0) + 1);

  return makeExpr(newRoot, newAdj, nextCounter) as any;
}

// ============================================================
// BuildCtx: construct typed graphs with real runtime
// ============================================================

interface BuildCtx<C extends string> {
  numLit<V extends number>(value: V):
    C extends keyof IDChain
      ? [Expr<number, Desc<number, C, Record<C, NodeEntry<"num/literal", [], number>>, NextID<C> & string>>, BuildCtx<NextID<C> & string>]
      : never;

  add<
    RA extends Desc<number, string, Record<string, any>, string>,
    RB extends Desc<number, string, Record<string, any>, string>,
  >(
    left: Expr<number, RA>,
    right: Expr<number, RB>,
  ): C extends keyof IDChain
    ? [Expr<number, Desc<
        number, C,
        AdjOf<RA> & AdjOf<RB> & Record<C, NodeEntry<"num/add", [IdOf<RA>, IdOf<RB>], number>>,
        NextID<C> & string
      >>, BuildCtx<NextID<C> & string>]
    : never;

  mul<
    RA extends Desc<number, string, Record<string, any>, string>,
    RB extends Desc<number, string, Record<string, any>, string>,
  >(
    left: Expr<number, RA>,
    right: Expr<number, RB>,
  ): C extends keyof IDChain
    ? [Expr<number, Desc<
        number, C,
        AdjOf<RA> & AdjOf<RB> & Record<C, NodeEntry<"num/mul", [IdOf<RA>, IdOf<RB>], number>>,
        NextID<C> & string
      >>, BuildCtx<NextID<C> & string>]
    : never;

  strLit<V extends string>(value: V):
    C extends keyof IDChain
      ? [Expr<string, Desc<string, C, Record<C, NodeEntry<"str/literal", [], string>>, NextID<C> & string>>, BuildCtx<NextID<C> & string>]
      : never;
}

function createCtx<C extends string>(counter: C): BuildCtx<C> {
  return {
    numLit(value: number) {
      const id = counter;
      const adj = { [id]: { kind: "num/literal", children: [], out: value } };
      const next = String.fromCharCode(id.charCodeAt(0) + 1);
      return [makeExpr(id, adj, next), createCtx(next)] as any;
    },
    add(left: Expr<any, any>, right: Expr<any, any>) {
      const id = counter;
      const adj = {
        ...left.__adj,
        ...right.__adj,
        [id]: { kind: "num/add", children: [left.__id, right.__id], out: ((left.__adj[left.__id] as RE).out as number) + ((right.__adj[right.__id] as RE).out as number) },
      };
      const next = String.fromCharCode(id.charCodeAt(0) + 1);
      return [makeExpr(id, adj, next), createCtx(next)] as any;
    },
    mul(left: Expr<any, any>, right: Expr<any, any>) {
      const id = counter;
      const adj = {
        ...left.__adj,
        ...right.__adj,
        [id]: { kind: "num/mul", children: [left.__id, right.__id], out: ((left.__adj[left.__id] as RE).out as number) * ((right.__adj[right.__id] as RE).out as number) },
      };
      const next = String.fromCharCode(id.charCodeAt(0) + 1);
      return [makeExpr(id, adj, next), createCtx(next)] as any;
    },
    strLit(value: string) {
      const id = counter;
      const adj = { [id]: { kind: "str/literal", children: [], out: value } };
      const next = String.fromCharCode(id.charCodeAt(0) + 1);
      return [makeExpr(id, adj, next), createCtx(next)] as any;
    },
  } as any;
}

// ============================================================
// TESTS: types AND runtime, no `declare`, no `any` in user code
// ============================================================

let passed = 0;
let failed = 0;
function assert(cond: boolean, msg: string) {
  if (cond) { passed++; console.log(`  ✓ ${msg}`); }
  else { failed++; console.log(`  ✗ ${msg}`); }
}

// Build: (3 + 4) * 5
const $ = createCtx("a");
const [lit3, $1] = $.numLit(3);
const [lit4, $2] = $1.numLit(4);
const [sum, $3] = $2.add(lit3, lit4);
const [lit5, $4] = $3.numLit(5);
const [prod, _$5] = $4.mul(sum, lit5);

// ---- Type-level: verify IDs ----
type ProdR = (typeof prod)[typeof exprBrand];
type ProdID = IdOf<ProdR>;
const _prodId: ProdID = "e";
type ProdCtr = CtrOf<ProdR>;
const _prodCtr: ProdCtr = "f";

console.log("Test 1: build — types and runtime agree on IDs");
assert(prod.__id === "e", "root ID is 'e'");
assert(prod.__counter === "f", "counter is 'f'");
assert(Object.keys(prod.__adj).length === 5, "5 nodes in adj");

console.log("Test 2: mapWhere byKind — rename num/add to num/sub");
const mapped = mapWhere(prod, byKind("num/add"), (entry) => ({
  kind: "num/sub" as const,
  children: entry.children,
  out: entry.out,
}));

// Type-level: c is now num/sub
type MR = (typeof mapped)[typeof exprBrand];
type MAdj = AdjOf<MR>;
type MC = MAdj["c"];
const _mcKind: MC["kind"] = "num/sub";
// @ts-expect-error — c is no longer num/add
const _mcWrong: MC["kind"] = "num/add";

// Runtime: verify
assert(mapped.__id === "e", "root unchanged");
assert((mapped.__adj["c"] as RE).kind === "num/sub", "c is now num/sub");
assert((mapped.__adj["a"] as RE).kind === "num/literal", "a unchanged");
assert((mapped.__adj["e"] as RE).kind === "num/mul", "e unchanged");

console.log("Test 3: mapWhere byKindGlob — transform all num/* nodes");
const globbed = mapWhere(prod, byKindGlob("num/"), (_entry) => ({
  kind: "opt/node" as const,
  children: [] as const,
  out: 0 as number,
}));

// Type-level: all nodes are opt/node (a,b,c,d,e are all num/*)
type GR = (typeof globbed)[typeof exprBrand];
type GAdj = AdjOf<GR>;
const _gaKind: GAdj["a"]["kind"] = "opt/node";
const _geKind: GAdj["e"]["kind"] = "opt/node";

// Runtime
assert((globbed.__adj["a"] as RE).kind === "opt/node", "a → opt/node");
assert((globbed.__adj["c"] as RE).kind === "opt/node", "c → opt/node");
assert((globbed.__adj["e"] as RE).kind === "opt/node", "e → opt/node");

console.log("Test 4: mapWhere on non-matching — nothing changes");
const noMatch = mapWhere(prod, byKind("str/concat"), (_entry) => ({
  kind: "never" as const,
  children: [] as const,
  out: "" as string,
}));

// Type-level: adj unchanged
type NMAdj = AdjOf<(typeof noMatch)[typeof exprBrand]>;
const _nmaKind: NMAdj["a"]["kind"] = "num/literal";
const _nmcKind: NMAdj["c"]["kind"] = "num/add";

// Runtime
assert((noMatch.__adj["a"] as RE).kind === "num/literal", "a still num/literal");
assert((noMatch.__adj["c"] as RE).kind === "num/add", "c still num/add");
assert(noMatch.__id === "e", "root unchanged");

console.log("Test 5: mapWhere with and(glob, leaf) — only num literals");
const numLeaves = mapWhere(prod, and(byKindGlob("num/"), isLeaf()), (_entry) => ({
  kind: "const/zero" as const,
  children: [] as const,
  out: 0 as number,
}));

// Type-level: a,b,d are leaves and num/ → a,b,d become const/zero
// c (num/add) has children → not matched
// e (num/mul) has children → not matched
type NLAdj = AdjOf<(typeof numLeaves)[typeof exprBrand]>;
const _nlaKind: NLAdj["a"]["kind"] = "const/zero";
const _nlcKind: NLAdj["c"]["kind"] = "num/add"; // unchanged!
const _nleKind: NLAdj["e"]["kind"] = "num/mul"; // unchanged!

// Runtime
assert((numLeaves.__adj["a"] as RE).kind === "const/zero", "a → const/zero");
assert((numLeaves.__adj["b"] as RE).kind === "const/zero", "b → const/zero");
assert((numLeaves.__adj["c"] as RE).kind === "num/add", "c unchanged");
assert((numLeaves.__adj["d"] as RE).kind === "const/zero", "d → const/zero");
assert((numLeaves.__adj["e"] as RE).kind === "num/mul", "e unchanged");

console.log("Test 6: wrapByName — wrap node 'c' with telemetry/span");
const wrapped = wrapByName(prod, "c", "telemetry/span");

// Type-level
type WR = (typeof wrapped)[typeof exprBrand];
type WAdj = AdjOf<WR>;
type WWrapper = WAdj["f"];
const _wwKind: WWrapper["kind"] = "telemetry/span";
const _wwChildren: WWrapper["children"] = ["c"];
// Parent "e" now references "f"
type WE = WAdj["e"];
const _weChildren: WE["children"] = ["f", "d"];
// @ts-expect-error — e no longer references "c"
const _weWrong: WE["children"] = ["c", "d"];

// Runtime
assert(wrapped.__id === "e", "root unchanged");
assert((wrapped.__adj["f"] as RE).kind === "telemetry/span", "wrapper at f");
assert((wrapped.__adj["f"] as RE).children[0] === "c", "wrapper child is c");
assert((wrapped.__adj["e"] as RE).children[0] === "f", "e now references f");
assert((wrapped.__adj["c"] as RE).kind === "num/add", "c still exists");

console.log("Test 7: wrapByName — wrap root 'e'");
const wrappedRoot = wrapByName(prod, "e", "telemetry/root");

// Type-level: root is now "f"
type WRR = (typeof wrappedRoot)[typeof exprBrand];
type WRID = IdOf<WRR>;
const _wrid: WRID = "f";

// Runtime
assert(wrappedRoot.__id === "f", "root is now f");
assert((wrappedRoot.__adj["f"] as RE).kind === "telemetry/root", "wrapper is root");
assert((wrappedRoot.__adj["f"] as RE).children[0] === "e", "wrapper child is e");

console.log("Test 8: chained transforms — mapWhere then wrapByName");
const step1 = mapWhere(prod, byKind("num/add"), (entry) => ({
  kind: "num/sub" as const,
  children: entry.children,
  out: entry.out,
}));
const step2 = wrapByName(step1, "c", "debug/trace");

// Type-level: c is num/sub, wrapper at f
type S2R = (typeof step2)[typeof exprBrand];
type S2Adj = AdjOf<S2R>;
const _s2cKind: S2Adj["c"]["kind"] = "num/sub";
const _s2fKind: S2Adj["f"]["kind"] = "debug/trace";

// Runtime
assert((step2.__adj["c"] as RE).kind === "num/sub", "c is num/sub (from mapWhere)");
assert((step2.__adj["f"] as RE).kind === "debug/trace", "f is wrapper (from wrapByName)");
assert((step2.__adj["e"] as RE).children[0] === "f", "e points to wrapper f");

console.log(`\nResults: ${passed} passed, ${failed} failed`);
if (failed > 0) process.exit(1);
console.log("\nBridge spike: types and runtime agree!");

spike-cascade.ts

// ============================================================
// Spike: Cascading ID updates on node replacement
// ============================================================
//
// The fundamental write operation: replace a node, cascade ID
// changes up through all ancestors.
//
// Approach: type-level recursive cascade. At each step:
//   1. Find entries whose children reference the old ID
//   2. Replace old ID with new ID in their children arrays
//   3. Recompute their content-addressed IDs
//   4. Repeat until no more changes
//
// Bounded by DAG depth, not total node count.

// ============================================================
// Core types
// ============================================================

type NodeEntry<Kind extends string, ChildIDs extends string[], Out> = {
  readonly kind: Kind;
  readonly children: ChildIDs;
  readonly out: Out;
};

type Desc<Out, ID extends string, Adj extends Record<string, any>> = {
  readonly o: Out;
  readonly id: ID;
  readonly adj: Adj;
};

declare const exprBrand: unique symbol;
interface Expr<O, R extends Desc<O, string, Record<string, any>>> {
  readonly [exprBrand]: R;
  readonly kind: string;
}

type OutOf<R> = R extends Desc<infer O, any, any> ? O : never;
type IdOf<R> = R extends Desc<any, infer ID, any> ? ID : never;
type AdjOf<R> = R extends Desc<any, any, infer A> ? A : never;

type LitID<V extends string | number | boolean> = `lit(${V})`;
type AddID<L extends string, R extends string> = `add(${L},${R})`;
type MulID<L extends string, R extends string> = `mul(${L},${R})`;
type NegID<A extends string> = `neg(${A})`;

type NameAlias<Name extends string, TargetID extends string, Out> = {
  readonly kind: "@alias";
  readonly target: TargetID;
  readonly out: Out;
};
type NameKey<N extends string> = `@${N}`;

// ============================================================
// ID generation: given a kind + children IDs, produce content ID
// ============================================================

/** Recompute the content-addressed ID for an entry given new children */
type RecomputeID<Kind extends string, Children extends string[]> =
  Kind extends "num/literal" ? Children extends [] ? Kind : never  // leaves keep their ID
  : Kind extends "num/add" ? Children extends [infer L extends string, infer R extends string] ? AddID<L, R> : never
  : Kind extends "num/mul" ? Children extends [infer L extends string, infer R extends string] ? MulID<L, R> : never
  : Kind extends "num/neg" ? Children extends [infer A extends string] ? NegID<A> : never
  : string; // fallback for unknown kinds

// ============================================================
// Child replacement: swap OldID → NewID in a children array
// ============================================================

type ReplaceInChildren<C extends string[], Old extends string, New extends string> =
  C extends [infer H extends string, ...infer T extends string[]]
    ? [H extends Old ? New : H, ...ReplaceInChildren<T, Old, New>]
    : [];

// ============================================================
// Single cascade step: find all entries referencing OldID,
// update their children, recompute their IDs
// ============================================================

/** Does this entry reference OldID in its children? */
type ReferencesOld<Entry, OldID extends string> =
  Entry extends NodeEntry<any, infer C, any>
    ? OldID extends C[number] ? true : false
    : Entry extends NameAlias<any, infer T, any>
      ? T extends OldID ? true : false
      : false;

/** Update a single entry: replace OldID with NewID in children */
type UpdateEntry<Entry, OldID extends string, NewID extends string> =
  Entry extends NodeEntry<infer K, infer C, infer O>
    ? NodeEntry<K, ReplaceInChildren<C, OldID, NewID>, O>
    : Entry extends NameAlias<infer N, infer T, infer O>
      ? NameAlias<N, T extends OldID ? NewID : T, O>
      : Entry;

/** Result of processing one entry during cascade: its new ID and new entry */
type CascadedEntry<ID extends string, Entry, OldID extends string, NewID extends string> =
  ReferencesOld<Entry, OldID> extends true
    ? Entry extends NodeEntry<infer K, infer C, infer O>
      ? {
          oldId: ID;
          newId: RecomputeID<K, ReplaceInChildren<C, OldID, NewID>>;
          entry: NodeEntry<K, ReplaceInChildren<C, OldID, NewID>, O>;
        }
      : Entry extends NameAlias<infer N, infer T, infer O>
        ? {
            oldId: ID;
            newId: ID;  // alias keys don't change
            entry: NameAlias<N, T extends OldID ? NewID : T, O>;
          }
        : never
    : { oldId: ID; newId: ID; entry: Entry };  // unchanged

// ============================================================
// Full cascade: apply one replacement and propagate
// ============================================================

/** Single-step cascade: replace OldID→NewID throughout the adj map.
 *  Returns [newAdj, array of (oldId, newId) pairs for entries that changed] */
type CascadeStep<Adj extends Record<string, any>, OldID extends string, NewID extends string> = {
  [K in keyof Adj as
    K extends OldID ? NewID :  // rename the key if it's the old ID
    CascadedEntry<K & string, Adj[K], OldID, NewID> extends { newId: infer NID }
      ? NID & string
      : K
  ]: K extends OldID
    ? Adj[K]  // keep the entry but under new key... actually we're removing old, adding new
    : CascadedEntry<K & string, Adj[K], OldID, NewID> extends { entry: infer E }
      ? E
      : Adj[K];
};

// Hmm, the above is getting complex. Let me try a simpler approach:
// Instead of cascading IDs through the adj map keys, separate the
// cascade into phases:
//
// Phase 1: Replace the target entry (remove old, add new)
// Phase 2: Update all children arrays referencing old ID
// Phase 3: Recompute IDs for changed entries (this IS the cascade)
//
// Actually, let me try the simplest possible approach first and see if it works.

// ============================================================
// Simpler approach: Replace + Rekey in one pass
// ============================================================

/** Remove an entry by key */
type RemoveKey<Adj, K extends string> = {
  [ID in keyof Adj as ID extends K ? never : ID]: Adj[ID];
};

/** Add an entry */
type AddEntry<Adj, K extends string, V> = Adj & Record<K, V>;

/** Replace all occurrences of OldRef with NewRef in children of all entries */
type UpdateAllChildren<Adj, OldRef extends string, NewRef extends string> = {
  [K in keyof Adj]: UpdateEntry<Adj[K], OldRef, NewRef>;
};

/** Rekey: for entries whose children changed, compute new ID and remap */
type RekeyChanged<Adj extends Record<string, any>, OldRef extends string, NewRef extends string> = {
  [K in keyof Adj as
    Adj[K] extends NodeEntry<infer Kind, infer C, any>
      ? OldRef extends C[number]
        ? RecomputeID<Kind, ReplaceInChildren<C, OldRef, NewRef>>
        : K
      : K
  ]: UpdateEntry<Adj[K], OldRef, NewRef>;
};

// ============================================================
// The actual cascade: iterative rekey
// One pass handles one level. For depth D, we need D passes.
// We detect convergence when no keys change.
// ============================================================

/** Collect IDs that changed in a rekey step */
type ChangedIDs<Before extends Record<string, any>, After extends Record<string, any>> = {
  [K in keyof Before]: K extends keyof After ? never : K
}[keyof Before];

/** One full cascade pass: rekey all entries whose children reference OldRef */
type CascadeOnce<Adj extends Record<string, any>, OldRef extends string, NewRef extends string> =
  RekeyChanged<RemoveKey<Adj, OldRef>, OldRef, NewRef>;

/** Multi-pass cascade (up to 8 levels deep — covers realistic programs) */
type Cascade<Adj extends Record<string, any>, OldRef extends string, NewRef extends string, Depth extends any[] = []> =
  Depth["length"] extends 8 ? CascadeOnce<Adj, OldRef, NewRef> :  // safety limit
  CascadeOnce<Adj, OldRef, NewRef> extends infer Result extends Record<string, any>
    // Check if any keys changed (indicating we need another pass)
    ? ChangedIDs<Adj, Result> extends never
      ? Result  // converged
      : Cascade<Result, OldRef, NewRef, [...Depth, unknown]>  // but we'd need the NEW old/new pairs...
    : never;

// Actually, multi-pass is hard because each pass produces NEW (old, new) pairs.
// Let me try a different approach: since content-addressed IDs encode the full
// subtree, replacing at the bottom and re-evaluating each parent level handles it.

// ============================================================
// PRACTICAL APPROACH: Replace by name, cascade by walking up
// ============================================================

// For the spike, let's prove single-level cascade works (parent of replaced node
// gets a new ID). Multi-level is the same operation applied recursively.

// Builders
function numLit<V extends number>(value: V): Expr<number, Desc<number, LitID<V>, Record<LitID<V>, NodeEntry<"num/literal", [], number>>>> {
  return {} as any;
}
function add<RA extends Desc<number, string, Record<string, any>>, RB extends Desc<number, string, Record<string, any>>>(
  left: Expr<number, RA>, right: Expr<number, RB>,
): Expr<number, Desc<number, AddID<IdOf<RA>, IdOf<RB>>, AdjOf<RA> & AdjOf<RB> & Record<AddID<IdOf<RA>, IdOf<RB>>, NodeEntry<"num/add", [IdOf<RA>, IdOf<RB>], number>>>> {
  return {} as any;
}
function mul<RA extends Desc<number, string, Record<string, any>>, RB extends Desc<number, string, Record<string, any>>>(
  left: Expr<number, RA>, right: Expr<number, RB>,
): Expr<number, Desc<number, MulID<IdOf<RA>, IdOf<RB>>, AdjOf<RA> & AdjOf<RB> & Record<MulID<IdOf<RA>, IdOf<RB>>, NodeEntry<"num/mul", [IdOf<RA>, IdOf<RB>], number>>>> {
  return {} as any;
}
function neg<RA extends Desc<number, string, Record<string, any>>>(operand: Expr<number, RA>): Expr<number, Desc<number, NegID<IdOf<RA>>, AdjOf<RA> & Record<NegID<IdOf<RA>>, NodeEntry<"num/neg", [IdOf<RA>], number>>>> {
  return {} as any;
}

// ============================================================
// Test: single-level cascade
// ============================================================

// Program: add(lit(3), lit(4))
// Replace lit(3) → lit(99)
// Expected: add(lit(99), lit(4)) with correct cascaded IDs

type OrigAdj = {
  "lit(3)": NodeEntry<"num/literal", [], number>;
  "lit(4)": NodeEntry<"num/literal", [], number>;
  "add(lit(3),lit(4))": NodeEntry<"num/add", ["lit(3)", "lit(4)"], number>;
};

// Step 1: Remove old entry, add new entry
type Step1 = RemoveKey<OrigAdj, "lit(3)"> & {
  "lit(99)": NodeEntry<"num/literal", [], number>;
};

// Step 2: Rekey entries that referenced "lit(3)" → "lit(99)"
type Step2 = RekeyChanged<Step1, "lit(3)", "lit(99)">;

// Step2 should have:
//   "lit(99)": NodeEntry<"num/literal", [], number>
//   "lit(4)": NodeEntry<"num/literal", [], number>
//   "add(lit(99),lit(4))": NodeEntry<"num/add", ["lit(99)", "lit(4)"], number>

// Verify:
type Step2HasNewAdd = "add(lit(99),lit(4))" extends keyof Step2 ? true : false;
//   ^? should be true
type Step2LacksOldAdd = "add(lit(3),lit(4))" extends keyof Step2 ? true : false;
//   ^? should be false

// Force the type checker to verify these
const _checkNewAdd: Step2HasNewAdd = true;
const _checkNoOldAdd: Step2LacksOldAdd = false;

// ============================================================
// Test: two-level cascade
// ============================================================

// Program: mul(add(lit(3), lit(4)), lit(5))
// Replace lit(3) → lit(99)
// Level 1: add(lit(3),lit(4)) → add(lit(99),lit(4))
// Level 2: mul(add(lit(3),lit(4)),lit(5)) → mul(add(lit(99),lit(4)),lit(5))

type DeepAdj = {
  "lit(3)": NodeEntry<"num/literal", [], number>;
  "lit(4)": NodeEntry<"num/literal", [], number>;
  "lit(5)": NodeEntry<"num/literal", [], number>;
  "add(lit(3),lit(4))": NodeEntry<"num/add", ["lit(3)", "lit(4)"], number>;
  "mul(add(lit(3),lit(4)),lit(5))": NodeEntry<"num/mul", ["add(lit(3),lit(4))", "lit(5)"], number>;
};

// Level 1 cascade: lit(3) → lit(99)
type Level1 = RekeyChanged<
  RemoveKey<DeepAdj, "lit(3)"> & { "lit(99)": NodeEntry<"num/literal", [], number> },
  "lit(3)", "lit(99)"
>;

// Level 1 should have renamed add but mul still references old add ID
type L1HasNewAdd = "add(lit(99),lit(4))" extends keyof Level1 ? true : false;
const _l1NewAdd: L1HasNewAdd = true;  // ✓

// Level 2 cascade: add(lit(3),lit(4)) → add(lit(99),lit(4))
type Level2 = RekeyChanged<Level1, "add(lit(3),lit(4))", "add(lit(99),lit(4))">;

type L2HasNewMul = "mul(add(lit(99),lit(4)),lit(5))" extends keyof Level2 ? true : false;
type L2LacksOldMul = "mul(add(lit(3),lit(4)),lit(5))" extends keyof Level2 ? true : false;
const _l2NewMul: L2HasNewMul = true;    // ✓
const _l2NoOldMul: L2LacksOldMul = false; // ✓

// ============================================================
// Automated multi-level cascade
// ============================================================

/** Find entries in Adj whose children reference OldRef, and return [oldKey, newKey] pairs.
 *  This tells us which keys will be renamed by RekeyChanged. */
type FindRenamedEntries<Adj extends Record<string, any>, OldRef extends string, NewRef extends string> = {
  [K in keyof Adj]: Adj[K] extends NodeEntry<infer Kind, infer C, any>
    ? OldRef extends C[number]
      ? [K & string, RecomputeID<Kind, ReplaceInChildren<C, OldRef, NewRef>>]
      : never
    : never;
}[keyof Adj];

/** Apply cascade iteratively.
 *  1. RekeyChanged replaces children refs and recomputes keys for ONE level.
 *  2. We find which entries got renamed from Adj + OldID/NewID.
 *  3. For each renamed entry, we cascade further up. */
type AutoCascade<
  Adj extends Record<string, any>,
  OldID extends string,
  NewID extends string,
  Fuel extends any[] = [],
> = Fuel["length"] extends 10 ? Adj :
  FindRenamedEntries<Adj, OldID, NewID> extends never
    ? RekeyChanged<Adj, OldID, NewID>  // no renames at this level, just update children & done
    : FindRenamedEntries<Adj, OldID, NewID> extends [infer NextOld extends string, infer NextNew extends string]
      ? AutoCascade<RekeyChanged<Adj, OldID, NewID>, NextOld, NextNew, [...Fuel, unknown]>
      : RekeyChanged<Adj, OldID, NewID>;

// ============================================================
// Test: automated cascade on the deep example
// ============================================================

type AutoResult = AutoCascade<
  RemoveKey<DeepAdj, "lit(3)"> & { "lit(99)": NodeEntry<"num/literal", [], number> },
  "lit(3)", "lit(99)"
>;

type AutoHasNewMul = "mul(add(lit(99),lit(4)),lit(5))" extends keyof AutoResult ? true : false;
type AutoLacksOldMul = "mul(add(lit(3),lit(4)),lit(5))" extends keyof AutoResult ? true : false;
type AutoLacksOldAdd = "add(lit(3),lit(4))" extends keyof AutoResult ? true : false;
const _autoNewMul: AutoHasNewMul = true;
const _autoNoOldMul: AutoLacksOldMul = false;
const _autoNoOldAdd: AutoLacksOldAdd = false;

// ============================================================
// Wrap it up: replaceNode function with full cascade
// ============================================================

/** Replace a node by its content-addressed ID with a new expression.
 *  Cascades ID updates through all ancestors. */
function replaceNode<
  O,
  R extends Desc<O, string, Record<string, any>>,
  TargetID extends string & keyof AdjOf<R>,
  ReplacementO extends AdjOf<R>[TargetID] extends NodeEntry<any, any, infer TO> ? TO : never,
  RR extends Desc<ReplacementO, string, Record<string, any>>,
>(
  program: Expr<O, R>,
  targetId: TargetID,
  replacement: Expr<ReplacementO, RR>,
): Expr<O, Desc<
  O,
  string, // root ID will change — would need cascade to compute
  AutoCascade<
    RemoveKey<AdjOf<R>, TargetID> & AdjOf<RR>,
    TargetID, IdOf<RR>
  >
>> {
  return {} as any;
}

// ============================================================
// Test: replaceNode with type safety
// ============================================================

const prog = mul(add(numLit(3), numLit(4)), numLit(5));

// Replace lit(3) with lit(99) — valid (number → number)
const replaced = replaceNode(prog, "lit(3)", numLit(99));

// The result's adj should have cascaded IDs
type ReplacedAdj = AdjOf<(typeof replaced)[typeof exprBrand]>;
type RHasNewMul = "mul(add(lit(99),lit(4)),lit(5))" extends keyof ReplacedAdj ? true : false;
const _rNewMul: RHasNewMul = true;

console.log("Cascade spike compiled successfully");

spike-dagql-runtime.ts

// ============================================================
// Spike: DAGQL convenience layer — mapByKind, wrapByKind
// with real runtime, building on dirty/commit primitives
// ============================================================

import { IDChain, FirstID } from "./spike-idchain";

// ============================================================
// Core types (condensed from spike-dirty-commit)
// ============================================================

type NodeEntry<Kind extends string, ChildIDs extends string[], Out> = {
  readonly kind: Kind;
  readonly children: ChildIDs;
  readonly out: Out;
};

type NextID<Current extends keyof IDChain> = IDChain[Current];

type NameAlias<Name extends string, TargetID extends string, Out> = {
  readonly kind: "@alias";
  readonly target: TargetID;
  readonly out: Out;
};
type NameKey<N extends string> = `@${N}`;

type Desc<Out, ID extends string, Adj extends Record<string, any>, C extends string> = {
  readonly o: Out;
  readonly id: ID;
  readonly adj: Adj;
  readonly c: C;
  readonly __clean: true;
};

type DirtyDesc<Out, ID extends string, Adj extends Record<string, any>, C extends string> = {
  readonly o: Out;
  readonly id: ID;
  readonly adj: Adj;
  readonly c: C;
  readonly __clean: false;
};

declare const exprBrand: unique symbol;

interface Expr<O, R extends Desc<O, string, Record<string, any>, string>> {
  readonly [exprBrand]: R;
  readonly kind: string;
  readonly __id: string;
  readonly __adj: Record<string, any>;
  readonly __counter: string;
}

interface DirtyExpr<O, R extends DirtyDesc<O, string, Record<string, any>, string>> {
  readonly [exprBrand]: R;
  readonly kind: string;
  readonly __id: string;
  readonly __adj: Record<string, any>;
  readonly __counter: string;
}

type IdOf<R> = R extends { id: infer ID } ? ID : never;
type AdjOf<R> = R extends { adj: infer A } ? A : never;
type CtrOf<R> = R extends { c: infer C } ? C : never;
type OutOf<R> = R extends { o: infer O } ? O : never;

// ============================================================
// Runtime helpers
// ============================================================

const ALPHA = "abcdefghijklmnopqrstuvwxyz";
function nextIdRuntime(current: string): string {
  const chars = current.split("");
  let carry = true;
  for (let i = chars.length - 1; i >= 0 && carry; i--) {
    const idx = ALPHA.indexOf(chars[i]);
    if (idx === 25) { chars[i] = "a"; carry = true; }
    else { chars[i] = ALPHA[idx + 1]; carry = false; }
  }
  if (carry) return "a" + chars.join("");
  return chars.join("");
}

function makeExpr(kind: string, id: string, adj: Record<string, any>, ctr: string): any {
  return { kind, __id: id, __adj: adj, __counter: ctr };
}

function assertEq<T>(actual: T, expected: T, msg: string) {
  if (actual !== expected) {
    throw new Error(`${msg}: expected ${JSON.stringify(expected)}, got ${JSON.stringify(actual)}`);
  }
}

function assert(cond: boolean, msg: string) {
  if (!cond) throw new Error(msg);
}

// ============================================================
// DagView — real runtime
// ============================================================

interface DagView {
  get(id: string): { kind: string; children?: string[]; target?: string; out?: any };
  nodeIds(): string[];
  children(id: string): any[];
  parents(childId: string): string[];
  resolve(name: string): string;
  entries(): [string, any][];
}

function createDagView(adj: Record<string, any>): DagView {
  const parentIndex: Record<string, string[]> = {};
  for (const [id, entry] of Object.entries(adj)) {
    if (id.startsWith("@")) continue;
    for (const childId of (entry as any).children || []) {
      if (!parentIndex[childId]) parentIndex[childId] = [];
      parentIndex[childId].push(id);
    }
  }
  return {
    get(id: string) { return adj[id]; },
    nodeIds() { return Object.keys(adj).filter(k => !k.startsWith("@")); },
    children(id: string) {
      const e = adj[id];
      if (!e || !e.children) return [];
      return e.children.map((cid: string) => adj[cid]);
    },
    parents(childId: string) { return parentIndex[childId] || []; },
    resolve(name: string) {
      const alias = adj[`@${name}`];
      if (!alias) throw new Error(`Name not found: ${name}`);
      return alias.target;
    },
    entries() { return Object.entries(adj).filter(([k]) => !k.startsWith("@")); },
  };
}

// ============================================================
// Reachability — walk from root, collect all reachable IDs
// ============================================================

function reachableIds(adj: Record<string, any>, rootId: string): Set<string> {
  const visited = new Set<string>();
  const stack = [rootId];

  while (stack.length > 0) {
    const id = stack.pop()!;
    if (visited.has(id)) continue;
    visited.add(id);

    const entry = adj[id];
    if (!entry) continue;
    const children = (entry as any).children || [];
    for (const childId of children) {
      if (!visited.has(childId)) stack.push(childId);
    }
  }

  // Also mark aliases as reachable if their target is reachable
  for (const [key, entry] of Object.entries(adj)) {
    if (key.startsWith("@")) {
      const target = (entry as any).target;
      if (visited.has(target)) {
        visited.add(key);
      }
    }
  }

  return visited;
}

// ============================================================
// gc() — remove all unreachable nodes
// ============================================================
//
// Returns a new expr with only reachable nodes.
// This is a dirty→dirty operation (doesn't commit).
// On a coherent graph, it's a no-op.

function gc(expr: any): any {
  const reachable = reachableIds(expr.__adj, expr.__id);
  const newAdj: Record<string, any> = {};

  for (const [id, entry] of Object.entries(expr.__adj)) {
    if (reachable.has(id)) {
      newAdj[id] = entry;
    }
  }

  return makeExpr(expr.kind, expr.__id, newAdj, expr.__counter);
}

// ============================================================
// Commit — real runtime validation
// ============================================================
//
// Rejects if:
// 1. Root doesn't exist in adj
// 2. Any node references a missing child
// 3. Any node is unreachable from root (orphans)

function commit(dirty: any): any {
  const adj = dirty.__adj;
  const rootId = dirty.__id;

  // Check 1: root exists
  if (!(rootId in adj)) {
    throw new Error(`commit: root "${rootId}" not in adj`);
  }

  // Check 2: all children exist
  for (const [id, entry] of Object.entries(adj)) {
    if (id.startsWith("@")) continue;
    const e = entry as any;
    if (e.children) {
      for (const childId of e.children) {
        if (!(childId in adj)) {
          throw new Error(`commit: node "${id}" refs missing child "${childId}"`);
        }
      }
    }
  }

  // Check 3: no orphans
  const reachable = reachableIds(adj, rootId);
  const allIds = Object.keys(adj);
  const orphans = allIds.filter(id => !reachable.has(id));
  if (orphans.length > 0) {
    throw new Error(`commit: orphaned nodes [${orphans.join(", ")}] — call gc() first`);
  }

  return dirty; // valid — now "clean"
}

// ============================================================
// BuildCtx — real runtime
// ============================================================

interface BuildCtx<C extends string> {
  numLit<V extends number>(value: V):
    C extends keyof IDChain
      ? [Expr<number, Desc<number, C, Record<C, NodeEntry<"num/literal", [], number>>, NextID<C> & string>>, BuildCtx<NextID<C> & string>]
      : never;

  boolLit<V extends boolean>(value: V):
    C extends keyof IDChain
      ? [Expr<boolean, Desc<boolean, C, Record<C, NodeEntry<"bool/literal", [], boolean>>, NextID<C> & string>>, BuildCtx<NextID<C> & string>]
      : never;

  add<
    RA extends Desc<number, string, Record<string, any>, string>,
    RB extends Desc<number, string, Record<string, any>, string>,
  >(left: Expr<number, RA>, right: Expr<number, RB>):
    C extends keyof IDChain
      ? [Expr<number, Desc<number, C, AdjOf<RA> & AdjOf<RB> & Record<C, NodeEntry<"num/add", [IdOf<RA>, IdOf<RB>], number>>, NextID<C> & string>>, BuildCtx<NextID<C> & string>]
      : never;

  mul<
    RA extends Desc<number, string, Record<string, any>, string>,
    RB extends Desc<number, string, Record<string, any>, string>,
  >(left: Expr<number, RA>, right: Expr<number, RB>):
    C extends keyof IDChain
      ? [Expr<number, Desc<number, C, AdjOf<RA> & AdjOf<RB> & Record<C, NodeEntry<"num/mul", [IdOf<RA>, IdOf<RB>], number>>, NextID<C> & string>>, BuildCtx<NextID<C> & string>]
      : never;

  neg<RA extends Desc<number, string, Record<string, any>, string>>(operand: Expr<number, RA>):
    C extends keyof IDChain
      ? [Expr<number, Desc<number, C, AdjOf<RA> & Record<C, NodeEntry<"num/neg", [IdOf<RA>], number>>, NextID<C> & string>>, BuildCtx<NextID<C> & string>]
      : never;

  cond<
    T,
    RP extends Desc<boolean, string, Record<string, any>, string>,
    RT extends Desc<T, string, Record<string, any>, string>,
    RE extends Desc<NoInfer<T>, string, Record<string, any>, string>,
  >(pred: Expr<boolean, RP>, then_: Expr<T, RT>, else_: Expr<NoInfer<T>, RE>):
    C extends keyof IDChain
      ? [Expr<T, Desc<T, C, AdjOf<RP> & AdjOf<RT> & AdjOf<RE> & Record<C, NodeEntry<"core/cond", [IdOf<RP>, IdOf<RT>, IdOf<RE>], T>>, NextID<C> & string>>, BuildCtx<NextID<C> & string>]
      : never;

  named<Name extends string, O2, R extends Desc<O2, string, Record<string, any>, string>>(
    name: Name, expr: Expr<O2, R>,
  ): [Expr<O2, Desc<O2, IdOf<R>, AdjOf<R> & Record<NameKey<Name>, NameAlias<Name, IdOf<R>, O2>>, CtrOf<R>>>, BuildCtx<C>];

  freshId(): C extends keyof IDChain ? [C, BuildCtx<NextID<C> & string>] : never;
}

function createCtx<C extends string>(counter: C): BuildCtx<C> {
  const ctx: BuildCtx<any> = {
    numLit(value: number) {
      const id = counter; const next = nextIdRuntime(counter);
      return [makeExpr("num/literal", id, { [id]: { kind: "num/literal", children: [], out: value } }, next), createCtx(next)];
    },
    boolLit(value: boolean) {
      const id = counter; const next = nextIdRuntime(counter);
      return [makeExpr("bool/literal", id, { [id]: { kind: "bool/literal", children: [], out: value } }, next), createCtx(next)];
    },
    add(left: any, right: any) {
      const id = counter; const next = nextIdRuntime(counter);
      return [makeExpr("num/add", id, { ...left.__adj, ...right.__adj, [id]: { kind: "num/add", children: [left.__id, right.__id] } }, next), createCtx(next)];
    },
    mul(left: any, right: any) {
      const id = counter; const next = nextIdRuntime(counter);
      return [makeExpr("num/mul", id, { ...left.__adj, ...right.__adj, [id]: { kind: "num/mul", children: [left.__id, right.__id] } }, next), createCtx(next)];
    },
    neg(operand: any) {
      const id = counter; const next = nextIdRuntime(counter);
      return [makeExpr("num/neg", id, { ...operand.__adj, [id]: { kind: "num/neg", children: [operand.__id] } }, next), createCtx(next)];
    },
    cond(pred: any, then_: any, else_: any) {
      const id = counter; const next = nextIdRuntime(counter);
      return [makeExpr("core/cond", id, { ...pred.__adj, ...then_.__adj, ...else_.__adj, [id]: { kind: "core/cond", children: [pred.__id, then_.__id, else_.__id] } }, next), createCtx(next)];
    },
    named(name: string, expr: any) {
      const adj = { ...expr.__adj, [`@${name}`]: { kind: "@alias", target: expr.__id } };
      return [makeExpr(expr.kind, expr.__id, adj, expr.__counter), ctx];
    },
    freshId() {
      const next = nextIdRuntime(counter);
      return [counter, createCtx(next)];
    },
  };
  return ctx;
}

function freshCtx(): BuildCtx<FirstID> {
  return createCtx("a" as FirstID);
}

// ============================================================
// selectByKind — real runtime
// ============================================================

function selectByKind(expr: any, kind: string): Record<string, any> {
  const result: Record<string, any> = {};
  for (const [id, entry] of Object.entries(expr.__adj)) {
    if ((entry as any).kind === kind) result[id] = entry;
  }
  return result;
}

// ============================================================
// mapByKind — the workhorse
// ============================================================
//
// For each node matching `kind`, call fn(entry, id, dagView).
// fn returns either:
//   - a new entry (swap in place), or
//   - null (leave unchanged)
//
// Internally: dirty → swapEntry for each match → commit
// The callback gets full DagView for context-sensitive transforms.

function mapByKind(
  expr: any,
  kind: string,
  fn: (entry: any, id: string, dag: DagView) => any | null,
  ctx?: any, // optional BuildCtx for operations that need fresh IDs
): any {
  const dag = createDagView(expr.__adj);
  const newAdj: Record<string, any> = { ...expr.__adj };
  let currentCtx = ctx;

  for (const [id, entry] of Object.entries(expr.__adj)) {
    if (id.startsWith("@")) continue;
    if ((entry as any).kind !== kind) continue;

    const result = fn(entry, id, dag);
    if (result !== null && result !== undefined) {
      // If result has __adj, it's a full Expr — merge its adj and point to its root
      if (result.__adj) {
        Object.assign(newAdj, result.__adj);
        newAdj[id] = result.__adj[result.__id];
      } else {
        // Plain entry replacement
        newAdj[id] = result;
      }
    }
  }

  const dirty = makeExpr(expr.kind, expr.__id, newAdj, expr.__counter);
  return commit(gc(dirty));
}

// ============================================================
// wrapByKind — bulk wrap
// ============================================================
//
// For each node matching `kind`, insert a wrapper between it
// and all its parents.
//
// Internally: for each match, allocate fresh ID, add wrapper
// entry, rewire parents. Then commit.

function wrapByKind(
  expr: any,
  kind: string,
  wrapperKind: string,
  ctx: any, // BuildCtx — need fresh IDs
): [any, any] {
  const dag = createDagView(expr.__adj);
  const newAdj: Record<string, any> = { ...expr.__adj };
  let currentCtx = ctx;

  // Collect all matching IDs first (don't modify while iterating)
  const matchIds: string[] = [];
  for (const [id, entry] of Object.entries(expr.__adj)) {
    if (id.startsWith("@")) continue;
    if ((entry as any).kind === kind) matchIds.push(id);
  }

  // For each match: allocate wrapper, rewire parents
  const rewireMap: Record<string, string> = {}; // targetId → wrapperId

  for (const targetId of matchIds) {
    const [wrapperId, nextCtx] = currentCtx.freshId();
    currentCtx = nextCtx;

    // Add wrapper entry
    newAdj[wrapperId] = { kind: wrapperKind, children: [targetId] };
    rewireMap[targetId] = wrapperId;
  }

  // Rewire all parents: in every non-wrapper entry, replace targetId → wrapperId
  for (const [id, entry] of Object.entries(newAdj)) {
    if (id.startsWith("@")) continue;
    const e = entry as any;
    if (!e.children) continue;
    // Don't rewire the wrapper entries themselves
    if (Object.values(rewireMap).includes(id)) continue;

    const newChildren = e.children.map((c: string) => rewireMap[c] || c);
    if (newChildren.some((c: string, i: number) => c !== e.children[i])) {
      newAdj[id] = { ...e, children: newChildren };
    }
  }

  // Handle root rewiring
  const rootId = rewireMap[expr.__id] || expr.__id;
  const result = commit(gc(makeExpr(expr.kind, rootId, newAdj, (currentCtx as any).__counter || "")));
  return [result, currentCtx];
}

// ============================================================
// wrapByName — wrap a single named node
// ============================================================

function wrapByName(
  expr: any,
  name: string,
  wrapperKind: string,
  ctx: any,
): [any, any] {
  const dag = createDagView(expr.__adj);
  const targetId = dag.resolve(name);

  const [wrapperId, nextCtx] = ctx.freshId();
  const newAdj: Record<string, any> = { ...expr.__adj };

  // Add wrapper
  newAdj[wrapperId] = { kind: wrapperKind, children: [targetId] };

  // Rewire parents (not the wrapper itself)
  for (const [id, entry] of Object.entries(newAdj)) {
    if (id === wrapperId) continue;
    if (id.startsWith("@")) continue;
    const e = entry as any;
    if (e.children && e.children.includes(targetId)) {
      newAdj[id] = { ...e, children: e.children.map((c: string) => c === targetId ? wrapperId : c) };
    }
  }

  const rootId = expr.__id === targetId ? wrapperId : expr.__id;
  return [commit(gc(makeExpr(expr.kind, rootId, newAdj, ""))), nextCtx];
}

// ============================================================
// replaceByName — swap a named node with a new expr
// ============================================================

function replaceByName(expr: any, name: string, newExpr: any): any {
  const dag = createDagView(expr.__adj);
  const targetId = dag.resolve(name);

  const newAdj: Record<string, any> = { ...expr.__adj };
  // Merge replacement's adj
  for (const [id, entry] of Object.entries(newExpr.__adj)) {
    newAdj[id] = entry;
  }
  // Overwrite target with replacement's root entry
  newAdj[targetId] = newExpr.__adj[newExpr.__id];

  return commit(gc(makeExpr(expr.kind, expr.__id, newAdj, expr.__counter)));
}

// ============================================================
// replaceByKind — bulk kind swap (simple rename)
// ============================================================

function replaceByKind(expr: any, fromKind: string, toKind: string): any {
  const newAdj: Record<string, any> = {};
  for (const [id, entry] of Object.entries(expr.__adj)) {
    if ((entry as any).kind === fromKind) {
      newAdj[id] = { ...entry as any, kind: toKind };
    } else {
      newAdj[id] = entry;
    }
  }
  // replaceByKind doesn't create orphans (same structure, just kind rename)
  // but gc is cheap on coherent graphs, so call it anyway for consistency
  return commit(gc(makeExpr(expr.kind, expr.__id, newAdj, expr.__counter)));
}

// ============================================================
// spliceByKind — remove nodes of a kind, rewire parents
// ============================================================
//
// For each node matching `kind`:
//   - If it has exactly 1 child: rewire parents to point to that child
//   - If it has 0 children (leaf): rewire parents to remove the ref
//     (parent's children array shrinks)
//   - If it has >1 child: error — ambiguous which child replaces it
//     (caller must mapByKind first to reduce to 1 child)
//
// After splicing, the target is orphaned and gc'd.

function spliceByKind(expr: any, kind: string): any {
  const dag = createDagView(expr.__adj);
  const newAdj: Record<string, any> = { ...expr.__adj };
  let rootId = expr.__id;

  // Collect targets first
  const targets: string[] = [];
  for (const [id, entry] of Object.entries(expr.__adj)) {
    if (id.startsWith("@")) continue;
    if ((entry as any).kind === kind) targets.push(id);
  }

  for (const targetId of targets) {
    const target = newAdj[targetId];
    const children: string[] = target.children || [];

    if (children.length > 1) {
      throw new Error(
        `splice: node "${targetId}" (${kind}) has ${children.length} children — ambiguous. ` +
        `Use mapByKind to reduce to 1 child first.`
      );
    }

    const replacementId = children.length === 1 ? children[0] : null;

    // Rewire all parents: replace targetId with replacementId in their children
    for (const [id, entry] of Object.entries(newAdj)) {
      if (id.startsWith("@")) continue;
      const e = entry as any;
      if (!e.children) continue;
      if (!e.children.includes(targetId)) continue;

      if (replacementId) {
        // Unary splice: swap target → its child
        newAdj[id] = {
          ...e,
          children: e.children.map((c: string) => c === targetId ? replacementId : c),
        };
      } else {
        // Leaf splice: remove from parent's children
        newAdj[id] = {
          ...e,
          children: e.children.filter((c: string) => c !== targetId),
        };
      }
    }

    // Rewire aliases pointing to this target
    for (const [key, entry] of Object.entries(newAdj)) {
      if (!key.startsWith("@")) continue;
      if ((entry as any).target === targetId && replacementId) {
        newAdj[key] = { ...entry as any, target: replacementId };
      }
    }

    // Handle root splice
    if (rootId === targetId) {
      if (replacementId) {
        rootId = replacementId;
      } else {
        throw new Error(`splice: cannot remove root "${targetId}" — it's a leaf with no replacement`);
      }
    }
  }

  return commit(gc(makeExpr(expr.kind, rootId, newAdj, expr.__counter)));
}

// ============================================================
// spliceByName — remove a single named node, rewire parents
// ============================================================

function spliceByName(expr: any, name: string): any {
  const dag = createDagView(expr.__adj);
  const targetId = dag.resolve(name);
  const target = expr.__adj[targetId];
  const children: string[] = target.children || [];

  if (children.length > 1) {
    throw new Error(
      `splice: named node "${name}" (${targetId}) has ${children.length} children — ambiguous.`
    );
  }

  const replacementId = children.length === 1 ? children[0] : null;
  const newAdj: Record<string, any> = { ...expr.__adj };
  let rootId = expr.__id;

  // Rewire parents
  for (const [id, entry] of Object.entries(newAdj)) {
    if (id.startsWith("@")) continue;
    const e = entry as any;
    if (!e.children) continue;
    if (!e.children.includes(targetId)) continue;

    if (replacementId) {
      newAdj[id] = {
        ...e,
        children: e.children.map((c: string) => c === targetId ? replacementId : c),
      };
    } else {
      newAdj[id] = {
        ...e,
        children: e.children.filter((c: string) => c !== targetId),
      };
    }
  }

  // Rewire aliases (including the name itself)
  for (const [key, entry] of Object.entries(newAdj)) {
    if (!key.startsWith("@")) continue;
    if ((entry as any).target === targetId && replacementId) {
      newAdj[key] = { ...entry as any, target: replacementId };
    }
  }

  if (rootId === targetId) {
    if (replacementId) {
      rootId = replacementId;
    } else {
      throw new Error(`splice: cannot remove root "${name}" — it's a leaf`);
    }
  }

  return commit(gc(makeExpr(expr.kind, rootId, newAdj, expr.__counter)));
}

// ============================================================
// Test 1: mapByKind — constant folding
// ============================================================

console.log("=== Test 1: mapByKind — constant folding ===");

const $ = freshCtx();
const [l3, $1] = $.numLit(3);
const [l4, $2] = $1.numLit(4);
const [sum, $3] = $2.add(l3, l4);     // add(3, 4) → should fold to 7
const [l5, $4] = $3.numLit(5);
const [prod, $5] = $4.mul(sum, l5);   // mul(add(3,4), 5)

const folded = mapByKind(prod, "num/add", (entry, id, dag) => {
  const [leftId, rightId] = entry.children;
  const left = dag.get(leftId);
  const right = dag.get(rightId);
  if (left.kind === "num/literal" && right.kind === "num/literal") {
    // Fold: replace add node with a literal
    return { kind: "num/literal", children: [], out: left.out + right.out };
  }
  return null; // not foldable
});

assertEq(folded.__adj["c"].kind, "num/literal", "add folded to literal");
assertEq(folded.__adj["c"].out, 7, "folded value is 7");
assertEq(folded.__adj["e"].kind, "num/mul", "mul unchanged");
assertEq(folded.__adj["e"].children[0], "c", "mul still refs c");

console.log("  mul(add(3,4), 5) → mul(7, 5) via constant folding");
console.log("  PASS");

// ============================================================
// Test 2: mapByKind — dead branch elimination
// ============================================================

console.log("\n=== Test 2: mapByKind — dead branch elimination ===");

const $d = freshCtx();
const [pred, $d1] = $d.boolLit(true);
const [then_, $d2] = $d1.numLit(42);
const [else_, $d3] = $d2.numLit(0);
const [condExpr, $d4] = $d3.cond(pred, then_, else_);

const pruned = mapByKind(condExpr, "core/cond", (entry, id, dag) => {
  const [predId] = entry.children;
  const predNode = dag.get(predId);
  if (predNode.kind === "bool/literal" && predNode.out === true) {
    const thenId = entry.children[1];
    return dag.get(thenId); // collapse to then branch
  }
  if (predNode.kind === "bool/literal" && predNode.out === false) {
    const elseId = entry.children[2];
    return dag.get(elseId);
  }
  return null;
});

assertEq(pruned.__adj["d"].kind, "num/literal", "cond collapsed to literal");
assertEq(pruned.__adj["d"].out, 42, "kept then branch value");

console.log("  cond(true, 42, 0) → 42 via dead branch elimination");
console.log("  PASS");

// ============================================================
// Test 3: wrapByKind — wrap all literals with neg
// ============================================================

console.log("\n=== Test 3: wrapByKind — wrap all literals ===");

const $w = freshCtx();
const [wa, $w1] = $w.numLit(3);
const [wb, $w2] = $w1.numLit(4);
const [wc, $w3] = $w2.add(wa, wb);

const [wrapped, $w4] = wrapByKind(wc, "num/literal", "num/neg", $w3);

// Two literals → two wrappers (d, e)
assertEq(wrapped.__adj["d"].kind, "num/neg", "wrapper d is neg");
assertEq(wrapped.__adj["d"].children[0], "a", "wrapper d → a");
assertEq(wrapped.__adj["e"].kind, "num/neg", "wrapper e is neg");
assertEq(wrapped.__adj["e"].children[0], "b", "wrapper e → b");

// add now points to wrappers, not originals
assertEq(wrapped.__adj["c"].children[0], "d", "add left → wrapper d");
assertEq(wrapped.__adj["c"].children[1], "e", "add right → wrapper e");

// originals untouched
assertEq(wrapped.__adj["a"].kind, "num/literal", "a untouched");
assertEq(wrapped.__adj["b"].kind, "num/literal", "b untouched");

console.log("  add(3, 4) → add(neg(3), neg(4))");
console.log("  PASS");

// ============================================================
// Test 4: wrapByName — wrap specific named node
// ============================================================

console.log("\n=== Test 4: wrapByName — wrap named node ===");

const $n = freshCtx();
const [price, $n1] = $n.numLit(100);
const [nPrice, $n2] = $n1.named("price", price);
const [tax, $n3] = $n2.numLit(21);
const [nTax, $n4] = $n3.named("tax", tax);
const [total, $n5] = $n4.add(nPrice, nTax);

const [wrappedTotal, $n6] = wrapByName(total, "price", "telemetry/timed", $n5);

// Wrapper inserted between price and add
const dag = createDagView(wrappedTotal.__adj);
assertEq(wrappedTotal.__adj["d"].kind, "telemetry/timed", "wrapper is timed");
assertEq(wrappedTotal.__adj["d"].children[0], "a", "wrapper → price");
assertEq(wrappedTotal.__adj["c"].children[0], "d", "add rewired to wrapper");
assertEq(wrappedTotal.__adj["c"].children[1], "b", "add right unchanged");
assertEq(wrappedTotal.__adj["@price"].target, "a", "name still → a");

console.log("  add(price:100, tax:21) → add(timed(price:100), tax:21)");
console.log("  PASS");

// ============================================================
// Test 5: replaceByName — swap named node with fixture
// ============================================================

console.log("\n=== Test 5: replaceByName — mock fixture ===");

// Reuse total from test 4 (before wrapping)
const [$rep, $rep1] = freshCtx().numLit(0); // mock zero price
const mocked = replaceByName(total, "price", $rep);

assertEq(mocked.__adj["a"].out, 0, "price replaced with 0");
assertEq(mocked.__adj["a"].kind, "num/literal", "still a literal");
assertEq(mocked.__adj["c"].children[0], "a", "add still refs a");

console.log("  price:100 → price:0 (mocked)");
console.log("  PASS");

// ============================================================
// Test 6: replaceByKind — transpile
// ============================================================

console.log("\n=== Test 6: replaceByKind — transpile ===");

const transpiled = replaceByKind(total, "num/add", "num/sub");
assertEq(transpiled.__adj["c"].kind, "num/sub", "add → sub");
assertEq(transpiled.__adj["c"].children[0], "a", "children preserved");

console.log("  add → sub (transpile)");
console.log("  PASS");

// ============================================================
// Test 7: mapByKind — smart transform with DagView context
// ============================================================

console.log("\n=== Test 7: mapByKind — context-sensitive transform ===");

// Double all literals that are children of mul (but not add)
const $s = freshCtx();
const [s1, $s1] = $s.numLit(3);
const [s2, $s2] = $s1.numLit(4);
const [sSum, $s3] = $s2.add(s1, s2);   // add(3, 4)
const [s3, $s4] = $s3.numLit(5);
const [sProd, $s5] = $s4.mul(sSum, s3); // mul(add(3,4), 5)

const doubled = mapByKind(sProd, "num/literal", (entry, id, dag) => {
  // Only double literals that are direct children of mul
  const parents = dag.parents(id);
  const isChildOfMul = parents.some(pid => dag.get(pid).kind === "num/mul");
  if (isChildOfMul) {
    return { ...entry, out: entry.out * 2 };
  }
  return null; // leave unchanged
});

// lit(5) at "d" is child of mul → doubled to 10
assertEq(doubled.__adj["d"].out, 10, "lit(5) doubled to 10");
// lit(3) at "a" and lit(4) at "b" are children of add, not mul → unchanged
assertEq(doubled.__adj["a"].out, 3, "lit(3) unchanged (child of add)");
assertEq(doubled.__adj["b"].out, 4, "lit(4) unchanged (child of add)");

console.log("  mul(add(3,4), 5) → mul(add(3,4), 10) — only mul's children doubled");
console.log("  PASS");

// ============================================================
// Test 8: chained transforms — fold then wrap
// ============================================================

console.log("\n=== Test 8: chained transforms ===");

// Start: mul(add(3, 4), 5)
// Step 1: constant fold add(3,4) → 7
// Step 2: wrap all literals with neg

const step1 = mapByKind(sProd, "num/add", (entry, id, dag) => {
  const [lid, rid] = entry.children;
  const l = dag.get(lid), r = dag.get(rid);
  if (l.kind === "num/literal" && r.kind === "num/literal") {
    return { kind: "num/literal", children: [], out: l.out + r.out };
  }
  return null;
});

// After fold+gc: mul(7, 5) — only c(lit7), d(lit5), e(mul) remain
// a and b were orphaned by folding and gc'd away
assertEq(step1.__adj["c"].kind, "num/literal", "folded");
assertEq(step1.__adj["c"].out, 7, "folded to 7");
assertEq("a" in step1.__adj, false, "orphan a gc'd");
assertEq("b" in step1.__adj, false, "orphan b gc'd");
assertEq(Object.keys(step1.__adj).length, 3, "only 3 nodes remain after gc");

const [step2, _] = wrapByKind(step1, "num/literal", "num/neg", $s5);

// After wrap: mul(neg(7), neg(5)) — only 2 literals so 2 wrappers
const negIds = Object.entries(step2.__adj)
  .filter(([_, e]) => (e as any).kind === "num/neg")
  .map(([id]) => id);
assertEq(negIds.length, 2, "2 neg wrappers (c:7 and d:5)");

// mul's children should be the wrappers, not c and d directly
assertEq(step2.__adj["e"].children[0] !== "c", true, "mul left rewired");
assertEq(step2.__adj["e"].children[1] !== "d", true, "mul right rewired");

console.log("  mul(add(3,4), 5) → fold+gc → mul(7, 5) → wrap → mul(neg(7), neg(5))");
console.log("  Orphans a,b cleaned by gc before wrap");
console.log("  PASS");

// ============================================================
// Test 9: mapByKind — return null leaves node unchanged
// ============================================================

console.log("\n=== Test 9: mapByKind — selective no-op ===");

const $q = freshCtx();
const [qa, $q1] = $q.numLit(1);
const [qb, $q2] = $q1.numLit(2);
const [qc, $q3] = $q2.numLit(3);
const [qab, $q4] = $q3.add(qa, qb);
const [qabc, $q5] = $q4.add(qab, qc);

// Only fold adds where BOTH children are literals (not nested adds)
const partialFold = mapByKind(qabc, "num/add", (entry, id, dag) => {
  const [lid, rid] = entry.children;
  const l = dag.get(lid), r = dag.get(rid);
  if (l.kind === "num/literal" && r.kind === "num/literal") {
    return { kind: "num/literal", children: [], out: l.out + r.out };
  }
  return null; // inner add foldable, outer not (one child is add)
});

// Inner add(1,2) folded to lit(3), outer add(lit(3), lit(3)) NOT folded
// because dagView was built before mutations — it sees original structure
assertEq(partialFold.__adj["d"].kind, "num/literal", "inner add folded");
assertEq(partialFold.__adj["d"].out, 3, "folded to 3");
// Outer add: its left child "d" was originally an add, dag saw it as add → returned null
assertEq(partialFold.__adj["e"].kind, "num/add", "outer add unchanged");
// Orphans a,b gc'd (they were children of the inner add, now folded to a literal)
assertEq("a" in partialFold.__adj, false, "orphan a gc'd");
assertEq("b" in partialFold.__adj, false, "orphan b gc'd");

console.log("  add(add(1,2), 3) → add(3, 3) — only innermost folded, orphans gc'd");
console.log("  (single-pass: dagView sees pre-mutation state)");
console.log("  PASS");

// ============================================================
// Test 10: gc removes orphans
// ============================================================

console.log("\n=== Test 10: gc removes orphans ===");

// Manually build adj with an orphan
const manualAdj: Record<string, any> = {
  a: { kind: "num/literal", children: [], out: 1 },
  b: { kind: "num/literal", children: [], out: 2 },  // orphan — nothing refs it
  c: { kind: "num/neg", children: ["a"] },
};
const withOrphan = makeExpr("num/neg", "c", manualAdj, "d");

// gc removes orphan b
const cleaned = gc(withOrphan);
assertEq("a" in cleaned.__adj, true, "a reachable (child of c)");
assertEq("b" in cleaned.__adj, false, "b orphaned and gc'd");
assertEq("c" in cleaned.__adj, true, "c reachable (root)");
assertEq(Object.keys(cleaned.__adj).length, 2, "2 nodes after gc");

console.log("  Orphan b removed, reachable a,c kept");
console.log("  PASS");

// ============================================================
// Test 11: gc is no-op on coherent graph
// ============================================================

console.log("\n=== Test 11: gc no-op on coherent graph ===");

const $g = freshCtx();
const [ga, $g1] = $g.numLit(1);
const [gb, $g2] = $g1.numLit(2);
const [gsum, $g3] = $g2.add(ga, gb);

const before = Object.keys(gsum.__adj).length;
const after = Object.keys(gc(gsum).__adj).length;
assertEq(before, after, "gc is no-op — no orphans");

console.log("  Coherent graph: " + before + " nodes before and after gc");
console.log("  PASS");

// ============================================================
// Test 12: gc preserves reachable aliases
// ============================================================

console.log("\n=== Test 12: gc preserves reachable aliases ===");

const $a = freshCtx();
const [ap, $a1] = $a.numLit(100);
const [nap, $a2] = $a1.named("price", ap);
const [at, $a3] = $a2.numLit(21);
const [asum, $a4] = $a3.add(nap, at);

const gcResult = gc(asum);
assertEq("@price" in gcResult.__adj, true, "alias preserved (target reachable)");

console.log("  @price alias preserved, target 'a' reachable");
console.log("  PASS");

// ============================================================
// Test 13: gc removes aliases pointing to orphans
// ============================================================

console.log("\n=== Test 13: gc removes orphaned aliases ===");

// Manually create an alias pointing to an orphan
const adjWithBadAlias: Record<string, any> = {
  a: { kind: "num/literal", children: [], out: 1 },
  b: { kind: "num/literal", children: [], out: 999 },  // orphan
  "@stale": { kind: "@alias", target: "b" },             // alias to orphan
  c: { kind: "num/neg", children: ["a"] },
};
const withBadAlias = makeExpr("num/neg", "c", adjWithBadAlias, "d");

const cleaned2 = gc(withBadAlias);
assertEq("b" in cleaned2.__adj, false, "orphan b gc'd");
assertEq("@stale" in cleaned2.__adj, false, "alias to orphan gc'd");
assertEq("a" in cleaned2.__adj, true, "a kept");
assertEq("c" in cleaned2.__adj, true, "c kept");

console.log("  Orphan b and its alias @stale both gc'd");
console.log("  PASS");

// ============================================================
// Test 14: commit rejects orphans (must gc first)
// ============================================================

console.log("\n=== Test 14: commit rejects orphans ===");

// Build adj with orphan — DON'T gc
const adjOrphan: Record<string, any> = {
  a: { kind: "num/literal", children: [], out: 1 },
  b: { kind: "num/literal", children: [], out: 2 },  // orphan
  c: { kind: "num/neg", children: ["a"] },
};
const dirtyOrphan = makeExpr("num/neg", "c", adjOrphan, "d");

let caught = false;
try {
  commit(dirtyOrphan);
} catch (e: any) {
  caught = true;
  assert(e.message.includes("orphaned"), "error mentions orphans");
  assert(e.message.includes("b"), "error mentions orphan b");
  console.log("  Caught: " + e.message);
}
assertEq(caught, true, "commit rejected orphaned graph");

// Now gc + commit works
const cleanedAndCommitted = commit(gc(dirtyOrphan));
assertEq("b" in cleanedAndCommitted.__adj, false, "b gone after gc+commit");
assertEq(Object.keys(cleanedAndCommitted.__adj).length, 2, "2 nodes after gc+commit");

console.log("  gc() + commit() succeeds after gc cleans orphans");
console.log("  PASS");

// ============================================================
// Test 15: manual cleanup with sharp knives + gc + commit
// ============================================================

console.log("\n=== Test 15: manual cleanup pipeline ===");

// User builds a graph, manually removes a node, gc cleans up, commit validates
const $m = freshCtx();
const [ma, $m1] = $m.numLit(10);
const [mb, $m2] = $m1.numLit(20);
const [mc, $m3] = $m2.numLit(30);
const [mab, $m4] = $m3.add(ma, mb);
const [mabc, $m5] = $m4.add(mab, mc);

// User wants to replace inner add(10,20) with just lit(10)
// Step 1: swap the add entry with a literal (children become orphans)
const manualDirty = makeExpr(mabc.kind, mabc.__id, {
  ...mabc.__adj,
  d: { kind: "num/literal", children: [], out: 10 },  // overwrite add node
}, mabc.__counter);

// At this point: a(10), b(20) are orphaned (d no longer refs them)
// c(30) is still referenced by e (outer add)

// Step 2: gc cleans orphans
const manualCleaned = gc(manualDirty);
assertEq("a" in manualCleaned.__adj, false, "orphan a cleaned");
assertEq("b" in manualCleaned.__adj, false, "orphan b cleaned");
assertEq("c" in manualCleaned.__adj, true, "c still reachable");
assertEq("d" in manualCleaned.__adj, true, "d still reachable (replaced)");
assertEq("e" in manualCleaned.__adj, true, "e still reachable (root)");

// Step 3: commit validates
const manualResult = commit(manualCleaned);
assertEq(Object.keys(manualResult.__adj).length, 3, "3 nodes: c, d, e");

console.log("  Manual: swap entry → gc orphans → commit");
console.log("  PASS");

// ============================================================
// Test 16: spliceByKind — remove unary wrapper
// ============================================================

console.log("\n=== Test 16: spliceByKind — remove unary wrapper ===");

// Build: mul(neg(3), neg(4))
// Splice out all neg → mul(3, 4)
const $sp = freshCtx();
const [sp3, $sp1] = $sp.numLit(3);
const [spn3, $sp2] = $sp1.neg(sp3);
const [sp4, $sp3] = $sp2.numLit(4);
const [spn4, $sp4a] = $sp3.neg(sp4);
const [spProd, $sp5] = $sp4a.mul(spn3, spn4);

// Before: e:mul(b:neg(a:3), d:neg(c:4))
assertEq(spProd.__adj["e"].children[0], "b", "mul left = neg");
assertEq(spProd.__adj["e"].children[1], "d", "mul right = neg");

const spliced = spliceByKind(spProd, "num/neg");

// After: mul(3, 4) — negs removed, mul points directly to literals
assertEq(spliced.__adj["e"].children[0], "a", "mul left = lit(3)");
assertEq(spliced.__adj["e"].children[1], "c", "mul right = lit(4)");
assertEq("b" in spliced.__adj, false, "neg b gc'd");
assertEq("d" in spliced.__adj, false, "neg d gc'd");
assertEq(Object.keys(spliced.__adj).length, 3, "3 nodes: a, c, e");

console.log("  mul(neg(3), neg(4)) → splice neg → mul(3, 4)");
console.log("  PASS");

// ============================================================
// Test 17: spliceByKind — strip debug logging
// ============================================================

console.log("\n=== Test 17: spliceByKind — strip debug logging ===");

// Simulate: add(log(3), log(4)) → strip "debug/log" → add(3, 4)
const $dl = freshCtx();
const [dl3, $dl1] = $dl.numLit(3);
const [dlLog3, $dl2] = $dl1.neg(dl3);    // pretend neg = debug/log
const [dl4, $dl3] = $dl2.numLit(4);
const [dlLog4, $dl4a] = $dl3.neg(dl4);
const [dlSum, $dl5] = $dl4a.add(dlLog3, dlLog4);

// Rename neg → debug/log for realism
const dlAdj: Record<string, any> = { ...dlSum.__adj };
dlAdj["b"] = { ...dlAdj["b"], kind: "debug/log" };
dlAdj["d"] = { ...dlAdj["d"], kind: "debug/log" };
const dlProg = makeExpr("num/add", "e", dlAdj, dlSum.__counter);

const stripped = spliceByKind(dlProg, "debug/log");

assertEq(stripped.__adj["e"].children[0], "a", "add left = lit(3)");
assertEq(stripped.__adj["e"].children[1], "c", "add right = lit(4)");
assertEq("b" in stripped.__adj, false, "log b gone");
assertEq("d" in stripped.__adj, false, "log d gone");

console.log("  add(log(3), log(4)) → splice debug/log → add(3, 4)");
console.log("  PASS");

// ============================================================
// Test 18: spliceByName — remove a specific named wrapper
// ============================================================

console.log("\n=== Test 18: spliceByName — remove named wrapper ===");

// Build: add(named("wrapper", neg(3)), 4)
// Splice "wrapper" → add(3, 4)
const $sn = freshCtx();
const [sn3, $sn1] = $sn.numLit(3);
const [snNeg, $sn2] = $sn1.neg(sn3);
const [snNamed, $sn3] = $sn2.named("wrapper", snNeg);
const [sn4, $sn4] = $sn3.numLit(4);
const [snSum, $sn5] = $sn4.add(snNamed, sn4);

assertEq(snSum.__adj["d"].children[0], "b", "add left = neg (named)");

const splicedNamed = spliceByName(snSum, "wrapper");

assertEq(splicedNamed.__adj["d"].children[0], "a", "add left = lit(3) directly");
assertEq("b" in splicedNamed.__adj, false, "neg b gc'd");
// The @wrapper alias should now point to a (the neg's child)
assertEq(splicedNamed.__adj["@wrapper"].target, "a", "alias rewired to lit");

console.log("  add(wrapper:neg(3), 4) → splice wrapper → add(3, 4)");
console.log("  PASS");

// ============================================================
// Test 19: spliceByKind — splice root (unary)
// ============================================================

console.log("\n=== Test 19: splice root ===");

// Build: neg(lit(7))
// Splice neg → lit(7) becomes root
const $sr = freshCtx();
const [sr7, $sr1] = $sr.numLit(7);
const [srNeg, $sr2] = $sr1.neg(sr7);

assertEq(srNeg.__id, "b", "root is neg");
const splicedRoot = spliceByKind(srNeg, "num/neg");

assertEq(splicedRoot.__id, "a", "root is now lit(7)");
assertEq("b" in splicedRoot.__adj, false, "neg gone");
assertEq(Object.keys(splicedRoot.__adj).length, 1, "just lit(7)");

console.log("  neg(7) → splice neg → 7 (root changed)");
console.log("  PASS");

// ============================================================
// Test 20: splice rejects multi-child nodes
// ============================================================

console.log("\n=== Test 20: splice rejects multi-child ===");

// Build: add(3, 4)
// Try to splice add — it has 2 children, ambiguous
const $sm = freshCtx();
const [sm3, $sm1] = $sm.numLit(3);
const [sm4, $sm2] = $sm1.numLit(4);
const [smSum, $sm3a] = $sm2.add(sm3, sm4);

let caughtMulti = false;
try {
  spliceByKind(smSum, "num/add");
} catch (e: any) {
  caughtMulti = true;
  assert(e.message.includes("ambiguous"), "error mentions ambiguous");
  assert(e.message.includes("2 children"), "error mentions child count");
  console.log("  Caught: " + e.message);
}
assertEq(caughtMulti, true, "splice rejected multi-child node");

console.log("  PASS");

// ============================================================
// Test 21: splice leaf node (0 children) — shrinks parent
// ============================================================

console.log("\n=== Test 21: splice leaf — shrinks parent children ===");

// This is a weird case: splice a leaf removes it from parent's children.
// Build: add(3, 4) with a "debug/marker" leaf attached
// We'll manually add a 3-child node to test this.
const leafAdj: Record<string, any> = {
  a: { kind: "num/literal", children: [], out: 3 },
  b: { kind: "num/literal", children: [], out: 4 },
  c: { kind: "debug/marker", children: [] },  // leaf to splice
  d: { kind: "num/add", children: ["a", "b", "c"] },  // 3 children
};
const leafProg = makeExpr("num/add", "d", leafAdj, "e");

const splicedLeaf = spliceByKind(leafProg, "debug/marker");

assertEq(splicedLeaf.__adj["d"].children.length, 2, "parent shrunk to 2 children");
assertEq(splicedLeaf.__adj["d"].children[0], "a", "first child preserved");
assertEq(splicedLeaf.__adj["d"].children[1], "b", "second child preserved");
assertEq("c" in splicedLeaf.__adj, false, "marker gc'd");

console.log("  add(3, 4, marker) → splice marker → add(3, 4)");
console.log("  PASS");

// ============================================================
// Test 22: wrap then splice roundtrip
// ============================================================

console.log("\n=== Test 22: wrap + splice roundtrip ===");

// Build: add(3, 4)
// Wrap all literals with neg: add(neg(3), neg(4))
// Splice all neg: add(3, 4) — back to original structure

const $rt = freshCtx();
const [rt3, $rt1] = $rt.numLit(3);
const [rt4, $rt2] = $rt1.numLit(4);
const [rtSum, $rt3] = $rt2.add(rt3, rt4);

const [rtWrapped, $rt4] = wrapByKind(rtSum, "num/literal", "num/neg", $rt3);
// Verify wrapped: add(neg(3), neg(4))
assertEq(rtWrapped.__adj["c"].children[0] !== "a", true, "add left rewired");

const rtRestored = spliceByKind(rtWrapped, "num/neg");
// Back to: add(3, 4)
assertEq(rtRestored.__adj["c"].children[0], "a", "add left = a again");
assertEq(rtRestored.__adj["c"].children[1], "b", "add right = b again");
assertEq(Object.keys(rtRestored.__adj).length, 3, "3 nodes: a, b, c");

console.log("  add(3,4) → wrap(neg) → add(neg(3),neg(4)) → splice(neg) → add(3,4)");
console.log("  Roundtrip clean!");
console.log("  PASS");

// ============================================================
// Summary
// ============================================================

console.log("\n=== All tests passed ===");

spike-dagql.ts

// ============================================================
// DAGQL Spike — Typed Query Language over Content-Addressed DAG
// ============================================================
//
// Core primitive: query(program).where(predicate).map(transform)
//
// Proves:
//   1. DagView: typed read access to the adjacency map
//   2. where(): filter nodes by kind, name, or predicate (with dag access)
//   3. map(): type-safe replacement (output type must match)
//   4. wrap(): inject a wrapper node between parent and child
//   5. Queries compose (chained .where() narrows further)
//   6. Type-level tracking of mutations

// ============================================================
// Core types (from winning spike)
// ============================================================

type NodeEntry<Kind extends string, ChildIDs extends string[], Out> = {
  readonly kind: Kind;
  readonly children: ChildIDs;
  readonly out: Out;
};

type Desc<Out, ID extends string, Adj extends Record<string, any>> = {
  readonly o: Out;
  readonly id: ID;
  readonly adj: Adj;
};

declare const exprBrand: unique symbol;
interface Expr<O, R extends Desc<O, string, Record<string, any>>> {
  readonly [exprBrand]: R;
  readonly kind: string;
}

type OutOf<R> = R extends Desc<infer O, any, any> ? O : never;
type IdOf<R> = R extends Desc<any, infer ID, any> ? ID : never;
type AdjOf<R> = R extends Desc<any, any, infer A> ? A : never;

type LitID<V extends string | number | boolean> = `lit(${V})`;
type AddID<L extends string, R extends string> = `add(${L},${R})`;
type MulID<L extends string, R extends string> = `mul(${L},${R})`;
type NegID<A extends string> = `neg(${A})`;
type GtID<L extends string, R extends string> = `gt(${L},${R})`;
type CondID<P extends string, T extends string, E extends string> = `cond(${P},${T},${E})`;

type NameAlias<Name extends string, TargetID extends string, Out> = {
  readonly kind: "@alias";
  readonly target: TargetID;
  readonly out: Out;
};
type NameKey<N extends string> = `@${N}`;

// ============================================================
// Builders (abbreviated — same as previous spikes)
// ============================================================

function numLit<V extends number>(value: V): Expr<number, Desc<number, LitID<V>, Record<LitID<V>, NodeEntry<"num/literal", [], number>>>> {
  return {} as any;
}
function strLit<V extends string>(value: V): Expr<string, Desc<string, LitID<V>, Record<LitID<V>, NodeEntry<"str/literal", [], string>>>> {
  return {} as any;
}
function add<RA extends Desc<number, string, Record<string, any>>, RB extends Desc<number, string, Record<string, any>>>(
  left: Expr<number, RA>, right: Expr<number, RB>,
): Expr<number, Desc<number, AddID<IdOf<RA>, IdOf<RB>>, AdjOf<RA> & AdjOf<RB> & Record<AddID<IdOf<RA>, IdOf<RB>>, NodeEntry<"num/add", [IdOf<RA>, IdOf<RB>], number>>>> {
  return {} as any;
}
function mul<RA extends Desc<number, string, Record<string, any>>, RB extends Desc<number, string, Record<string, any>>>(
  left: Expr<number, RA>, right: Expr<number, RB>,
): Expr<number, Desc<number, MulID<IdOf<RA>, IdOf<RB>>, AdjOf<RA> & AdjOf<RB> & Record<MulID<IdOf<RA>, IdOf<RB>>, NodeEntry<"num/mul", [IdOf<RA>, IdOf<RB>], number>>>> {
  return {} as any;
}
function neg<RA extends Desc<number, string, Record<string, any>>>(operand: Expr<number, RA>): Expr<number, Desc<number, NegID<IdOf<RA>>, AdjOf<RA> & Record<NegID<IdOf<RA>>, NodeEntry<"num/neg", [IdOf<RA>], number>>>> {
  return {} as any;
}
function gt<RA extends Desc<number, string, Record<string, any>>, RB extends Desc<number, string, Record<string, any>>>(
  left: Expr<number, RA>, right: Expr<number, RB>,
): Expr<boolean, Desc<boolean, GtID<IdOf<RA>, IdOf<RB>>, AdjOf<RA> & AdjOf<RB> & Record<GtID<IdOf<RA>, IdOf<RB>>, NodeEntry<"num/gt", [IdOf<RA>, IdOf<RB>], boolean>>>> {
  return {} as any;
}
function cond<T, RP extends Desc<boolean, string, Record<string, any>>, RT extends Desc<T, string, Record<string, any>>, RE extends Desc<NoInfer<T>, string, Record<string, any>>>(
  pred: Expr<boolean, RP>, then_: Expr<T, RT>, else_: Expr<NoInfer<T>, RE>,
): Expr<T, Desc<T, CondID<IdOf<RP>, IdOf<RT>, IdOf<RE>>, AdjOf<RP> & AdjOf<RT> & AdjOf<RE> & Record<CondID<IdOf<RP>, IdOf<RT>, IdOf<RE>>, NodeEntry<"core/cond", [IdOf<RP>, IdOf<RT>, IdOf<RE>], T>>>> {
  return {} as any;
}
function named<Name extends string, O, R extends Desc<O, string, Record<string, any>>>(
  name: Name, expr: Expr<O, R>,
): Expr<O, Desc<O, IdOf<R>, AdjOf<R> & Record<NameKey<Name>, NameAlias<Name, IdOf<R>, O>>>> {
  return expr as any;
}

// ============================================================
// DagView: typed read access to the adjacency map
// ============================================================

/** Runtime view into the DAG for use inside query predicates and transforms */
interface DagView<Adj extends Record<string, any>> {
  /** Get a node entry by its content-addressed ID */
  get<ID extends string & keyof Adj>(id: ID): Adj[ID];

  /** Get all node IDs (excluding @aliases) */
  nodeIds(): Array<string & keyof Adj>;

  /** Get child entries of a node */
  children<ID extends string & keyof Adj>(
    id: ID
  ): Adj[ID] extends NodeEntry<any, infer C, any>
    ? { [I in keyof C]: C[I] extends keyof Adj ? Adj[C[I] & string] : never }
    : never;

  /** Find the parent IDs of a node */
  parents(childId: string): string[];

  /** Resolve a name to its target ID */
  resolve<Name extends string>(
    name: Name
  ): NameKey<Name> extends keyof Adj
    ? Adj[NameKey<Name>] extends NameAlias<any, infer T, any> ? T : never
    : never;
}

// ============================================================
// Node handle: what predicates and transforms receive
// ============================================================

/** A handle to a specific node within the DAG, with typed access */
interface NodeHandle<
  ID extends string,
  Entry extends NodeEntry<string, string[], any>,
  Adj extends Record<string, any>,
> {
  readonly id: ID;
  readonly kind: Entry extends NodeEntry<infer K, any, any> ? K : never;
  readonly out: Entry extends NodeEntry<any, any, infer O> ? O : never;
  readonly childIds: Entry extends NodeEntry<any, infer C, any> ? C : never;
  readonly dag: DagView<Adj>;
}

// ============================================================
// DAGQL: query().where().map()
// ============================================================

/** Filter: select entries from adj matching a kind */
type EntriesOfKind<Adj, K extends string> = {
  [ID in keyof Adj as Adj[ID] extends NodeEntry<K, any, any> ? ID : never]: Adj[ID];
};

/** Filter: select entries matching a name */
type EntryOfName<Adj, Name extends string> =
  NameKey<Name> extends keyof Adj
    ? Adj[NameKey<Name>] extends NameAlias<any, infer TargetID, any>
      ? TargetID extends keyof Adj
        ? Record<TargetID, Adj[TargetID]>
        : {}
      : {}
    : {};

/** The selected subset — what .where() produces */
type DagSelection<Adj extends Record<string, any>, Selected extends Record<string, any>> = {
  readonly adj: Adj;
  readonly selected: Selected;
};

/** The query builder */
interface DagQuery<
  O,
  R extends Desc<O, string, Record<string, any>>,
  Selected extends Record<string, any>,
> {
  /** Filter by node kind (glob-like: "num/*" matches "num/add", "num/mul", etc.) */
  where<K extends string>(
    kindFilter: K
  ): DagQuery<O, R, EntriesOfKind<Selected, K>>;

  /** Filter by name */
  whereNamed<Name extends string>(
    name: Name
  ): DagQuery<O, R, EntryOfName<AdjOf<R>, Name>>;

  /** Map: replace each selected node. Replacement must have same output type.
   *  Transform receives a NodeHandle with full dag access. */
  map<NewAdj extends Record<string, any>>(
    fn: (
      handle: SelectedHandle<Selected, AdjOf<R>>,
      dag: DagView<AdjOf<R>>
    ) => MappedResult<Selected, NewAdj>
  ): Expr<O, Desc<O, IdOf<R>, Omit<AdjOf<R>, keyof Selected> & NewAdj>>;

  /** Count selected nodes (runtime only) */
  count(): number;

  /** Collect selected node IDs (runtime only) */
  ids(): (keyof Selected)[];
}

/** Handle type for selected nodes — ensures output type preservation */
type SelectedHandle<Selected extends Record<string, any>, Adj extends Record<string, any>> = {
  [ID in keyof Selected]: NodeHandle<
    ID & string,
    Selected[ID] extends NodeEntry<any, any, any> ? Selected[ID] : never,
    Adj
  >;
}[keyof Selected];

/** Result of .map() — must preserve output types for each replaced node */
type MappedResult<Selected extends Record<string, any>, NewAdj extends Record<string, any>> = {
  [ID in keyof Selected]: Selected[ID] extends NodeEntry<any, any, infer O>
    ? NodeEntry<string, string[], O>  // output type O must match
    : never;
};

/** Entry point: create a query over a program */
function query<O, R extends Desc<O, string, Record<string, any>>>(
  program: Expr<O, R>
): DagQuery<O, R, AdjOf<R>> {
  return {} as any;
}

// ============================================================
// Simpler DAGQL operations (not chained — standalone functions)
// ============================================================

/** SELECT: find all nodes of a given kind */
type SelectByKind<R, K extends string> =
  R extends Desc<any, any, infer Adj>
    ? { [ID in keyof Adj as Adj[ID] extends NodeEntry<K, any, any> ? ID : never]: Adj[ID] }
    : never;

/** UPDATE by kind: replace all nodes of kind From, transform must return same output type */
type UpdateByKind<R, From extends string, To extends string> =
  R extends Desc<infer O, infer ID, infer Adj>
    ? Desc<O, ID, {
        [K in keyof Adj]: Adj[K] extends NodeEntry<From, infer C, infer Out>
          ? NodeEntry<To, C, Out>
          : Adj[K]
      }>
    : never;

/** UPDATE by name: replace a named node */
type UpdateByName<R, Name extends string, NewEntry extends NodeEntry<string, string[], any>> =
  R extends Desc<infer O, infer RootID, infer Adj>
    ? NameKey<Name> extends keyof Adj
      ? Adj[NameKey<Name>] extends NameAlias<any, infer TargetID, infer TargetO>
        ? NewEntry extends NodeEntry<any, any, TargetO>  // output type must match
          ? Desc<O, RootID, Omit<Adj, TargetID & string> & Record<TargetID & string, NewEntry>>
          : never  // type mismatch
        : never
      : never  // name not found
    : never;

/** DELETE by kind: remove all nodes of a kind (only if they're leaves) */
type LeafNodesOfKind<Adj, K extends string> = {
  [ID in keyof Adj as Adj[ID] extends NodeEntry<K, [], any> ? ID : never]: Adj[ID];
};

// ============================================================
// Runtime: standalone DAGQL functions
// ============================================================

function selectByKind<
  O, R extends Desc<O, string, Record<string, any>>,
  K extends string,
>(program: Expr<O, R>, kind: K): SelectByKind<R, K> {
  return {} as any;
}

function updateByKind<
  O, R extends Desc<O, string, Record<string, any>>,
  From extends string, To extends string,
>(program: Expr<O, R>, from: From, to: To): Expr<O, UpdateByKind<R, From, To>> {
  return {} as any;
}

function updateByName<
  O, R extends Desc<O, string, Record<string, any>>,
  Name extends string,
  ReplacementO extends NamedOutputType<R, Name>,
  RR extends Desc<ReplacementO, string, Record<string, any>>,
>(
  program: Expr<O, R>,
  name: Name,
  replacement: Expr<ReplacementO, RR>
): Expr<O, Desc<O, IdOf<R>, AdjOf<R> & AdjOf<RR>>> {
  return {} as any;
}

type NamedOutputType<R, Name extends string> =
  R extends Desc<any, any, infer Adj>
    ? NameKey<Name> extends keyof Adj
      ? Adj[NameKey<Name>] extends NameAlias<any, any, infer O> ? O : never
      : never
    : never;

// ============================================================
// Test: Build a realistic program
// ============================================================

const price = named("price", numLit(100));
const taxRate = named("tax-rate", numLit(21));
const tax = named("tax", mul(price, taxRate));
const subtotal = named("subtotal", add(price, tax));
const discount = named("discount", numLit(10));
const total = named("total", add(subtotal, neg(discount)));

// ============================================================
// Test: SELECT queries
// ============================================================

type ROf<E> = E extends Expr<any, infer R> ? R : never;
type TotalR = ROf<typeof total>;

// Select all addition nodes
type AllAdds = SelectByKind<TotalR, "num/add">;
// Should contain the add nodes for subtotal and total

// Select all multiplication nodes
type AllMuls = SelectByKind<TotalR, "num/mul">;
// Should contain just the tax calculation

// Select all literals
type AllLits = SelectByKind<TotalR, "num/literal">;
// Should contain 100, 21, 10

// ============================================================
// Test: Collect all names
// ============================================================

type CollectNames<R> =
  R extends Desc<any, any, infer Adj>
    ? { [K in keyof Adj]: K extends `@${infer Name}` ? Name : never }[keyof Adj]
    : never;

type TotalNames = CollectNames<TotalR>;
// "price" | "tax-rate" | "tax" | "subtotal" | "discount" | "total"

// ============================================================
// Test: UPDATE by kind (num/add → num/mul everywhere)
// ============================================================

const allMul = updateByKind(total, "num/add", "num/mul");
// Type tracks that all num/add entries are now num/mul

type AllMulR = ROf<typeof allMul>;
type CollectKinds<R> = R extends Desc<any, any, infer Adj>
  ? { [K in keyof Adj]: Adj[K] extends NodeEntry<infer Kind, any, any> ? Kind : never }[keyof Adj]
  : never;

type AllMulKinds = CollectKinds<AllMulR>;
// Should NOT contain "num/add", should contain "num/mul"

// ============================================================
// Test: UPDATE by name — replace tax rate
// ============================================================

const newRate = updateByName(total, "tax-rate", numLit(15));
// Valid: number → number

// @ts-expect-error: can't replace tax-rate (number) with string
const badRate = updateByName(total, "tax-rate", strLit("nope"));

// @ts-expect-error: name doesn't exist
const badName = updateByName(total, "nonexistent", numLit(0));

// ============================================================
// Test: Querying the DAG inside a predicate (runtime concept)
// ============================================================

// This shows what the runtime API looks like.
// The DagView gives access to the full adjacency map inside predicates.

function findConstantAdds<O, R extends Desc<O, string, Record<string, any>>>(
  program: Expr<O, R>
): string[] {
  // Runtime: build DagView from program's adj map
  const dag: DagView<AdjOf<R>> = {} as any;
  const results: string[] = [];

  for (const id of dag.nodeIds()) {
    const entry = dag.get(id);
    if (entry.kind === "num/add") {
      // Query children through the DAG
      const [leftId, rightId] = entry.children;
      const left = dag.get(leftId);
      const right = dag.get(rightId);
      // Both children are literals → constant fold candidate
      if (left.kind === "num/literal" && right.kind === "num/literal") {
        results.push(id);
      }
    }
  }

  return results;
}

// ============================================================
// Test: Transaction-style composition (sketch)
// ============================================================

// Multiple DAGQL operations composed:
const optimized = updateByKind(
  updateByName(total, "tax-rate", numLit(15)),
  "num/add", "num/mul"
);
// Both operations applied, types track the full transformation

// ============================================================
// Test: Wrap pattern — inject a wrapper between parent and child
// ============================================================

// Wrapping "discount" with neg() is equivalent to:
// 1. SELECT the named node
// 2. CREATE a new node that wraps it
// 3. UPDATE all parents to point to the wrapper

// With DAGQL this would be:
// query(program).whereNamed("discount").wrap(node => neg(node))

// For now, prove it works manually:
const wrappedDiscount = named("discount", neg(named("original-discount", numLit(10))));
// The name "discount" now points to neg(original-discount)

console.log("DAGQL spike compiled successfully");

spike-dirty-commit.ts

// ============================================================
// Spike: Dirty/Commit — phantom-typed graph integrity
// ============================================================
//
// Sharp knives (addEntry, removeEntry, rewireChildren) produce
// DirtyExpr. You can chain dirty ops freely. Only commit()
// returns a clean Expr — and only if the graph is valid.
//
// Convenience methods (wrap, replaceByName) use sharp knives
// internally and commit at the end.

import { IDChain, FirstID } from "./spike-idchain";

// ============================================================
// Core types
// ============================================================

type NodeEntry<Kind extends string, ChildIDs extends string[], Out> = {
  readonly kind: Kind;
  readonly children: ChildIDs;
  readonly out: Out;
};

type NextID<Current extends keyof IDChain> = IDChain[Current];

type NameAlias<Name extends string, TargetID extends string, Out> = {
  readonly kind: "@alias";
  readonly target: TargetID;
  readonly out: Out;
};
type NameKey<N extends string> = `@${N}`;

// Clean descriptor — graph is valid
type Desc<Out, ID extends string, Adj extends Record<string, any>, C extends string> = {
  readonly o: Out;
  readonly id: ID;
  readonly adj: Adj;
  readonly c: C;
  readonly __clean: true;
};

// Dirty descriptor — graph may be invalid
type DirtyDesc<Out, ID extends string, Adj extends Record<string, any>, C extends string> = {
  readonly o: Out;
  readonly id: ID;
  readonly adj: Adj;
  readonly c: C;
  readonly __clean: false;
};

declare const exprBrand: unique symbol;

// Clean Expr — can be passed to foldAST, consumers, etc.
interface Expr<O, R extends Desc<O, string, Record<string, any>, string>> {
  readonly [exprBrand]: R;
  readonly kind: string;
  readonly __id: string;
  readonly __adj: Record<string, any>;
  readonly __counter: string;
}

// Dirty Expr — can only be committed or further mutated
interface DirtyExpr<O, R extends DirtyDesc<O, string, Record<string, any>, string>> {
  readonly [exprBrand]: R;
  readonly kind: string;
  readonly __id: string;
  readonly __adj: Record<string, any>;
  readonly __counter: string;
}

type IdOf<R> = R extends { id: infer ID } ? ID : never;
type AdjOf<R> = R extends { adj: infer A } ? A : never;
type CtrOf<R> = R extends { c: infer C } ? C : never;
type OutOf<R> = R extends { o: infer O } ? O : never;

// ============================================================
// Validation: does the graph hold together?
// ============================================================

// Check: every child ID referenced by every entry exists as a key
type AllChildrenExist<Adj extends Record<string, any>> = {
  [K in keyof Adj]: Adj[K] extends NodeEntry<any, infer C extends string[], any>
    ? C[number] extends keyof Adj ? true : false
    : true;  // aliases don't have children
};

type HasInvalidChildren<Adj extends Record<string, any>> =
  false extends AllChildrenExist<Adj>[keyof AllChildrenExist<Adj>]
    ? true
    : false;

// Check: root ID exists in adj
type RootExists<ID extends string, Adj extends Record<string, any>> =
  ID extends keyof Adj ? true : false;

// Combined validation
type IsValidGraph<ID extends string, Adj extends Record<string, any>> =
  RootExists<ID, Adj> extends true
    ? HasInvalidChildren<Adj> extends false
      ? true
      : false
    : false;

// Error messages as types
type GraphError<Msg extends string> = { readonly __graphError: Msg };

type MissingChildren<Adj extends Record<string, any>> = {
  [K in keyof Adj]: Adj[K] extends NodeEntry<any, infer C extends string[], any>
    ? { [I in keyof C]: C[I] extends keyof Adj ? never : C[I] }[number]
    : never;
}[keyof Adj];

// ============================================================
// commit(): dirty → clean (or type error)
// ============================================================

// Overload 1: valid graph → clean Expr
// Overload 2: invalid graph → compile error with diagnostic
function commit<
  O,
  ID extends string,
  Adj extends Record<string, any>,
  C extends string,
>(
  dirty: DirtyExpr<O, DirtyDesc<O, ID, Adj, C>>,
): IsValidGraph<ID, Adj> extends true
  ? Expr<O, Desc<O, ID, Adj, C>>
  : GraphError<`Invalid graph: missing children [${MissingChildren<Adj> & string}]`>
{
  // Runtime validation
  const adj = dirty.__adj;
  const rootId = dirty.__id;

  // Check root exists
  if (!(rootId in adj)) {
    throw new Error(`commit failed: root ID "${rootId}" not in adj map`);
  }

  // Check all children exist
  for (const [id, entry] of Object.entries(adj)) {
    if (id.startsWith("@")) continue;
    const e = entry as any;
    if (e.children) {
      for (const childId of e.children) {
        if (!(childId in adj)) {
          throw new Error(`commit failed: node "${id}" references child "${childId}" which doesn't exist`);
        }
      }
    }
  }

  // Valid — return as clean
  return dirty as any;
}

// ============================================================
// Sharp knives: all return DirtyExpr
// ============================================================

// Make any Expr dirty (entry point into mutation)
function dirty<
  O,
  R extends Desc<O, string, Record<string, any>, string>,
>(expr: Expr<O, R>): DirtyExpr<O, DirtyDesc<O, IdOf<R>, AdjOf<R>, CtrOf<R>>> {
  return expr as any;
}

// Also accept DirtyExpr (for chaining)
function dirtyOf<
  O,
  R extends DirtyDesc<O, string, Record<string, any>, string>,
>(expr: DirtyExpr<O, R>): DirtyExpr<O, R> {
  return expr;
}

// addEntry: add a node to the adj map
function addEntry<
  O,
  ID extends string,
  Adj extends Record<string, any>,
  C extends string,
  NewID extends string,
  NewEntry extends NodeEntry<string, string[], any>,
>(
  expr: DirtyExpr<O, DirtyDesc<O, ID, Adj, C>>,
  newId: NewID,
  newEntry: NewEntry,
): DirtyExpr<O, DirtyDesc<O, ID, Adj & Record<NewID, NewEntry>, C>> {
  const newAdj = { ...expr.__adj, [newId]: newEntry };
  return { ...expr, __adj: newAdj } as any;
}

// removeEntry: remove a node (may break children refs)
function removeEntry<
  O,
  ID extends string,
  Adj extends Record<string, any>,
  C extends string,
  TargetID extends string & keyof Adj,
>(
  expr: DirtyExpr<O, DirtyDesc<O, ID, Adj, C>>,
  targetId: TargetID,
): DirtyExpr<O, DirtyDesc<O, ID, Omit<Adj, TargetID>, C>> {
  const newAdj = { ...expr.__adj };
  delete newAdj[targetId];
  return { ...expr, __adj: newAdj } as any;
}

// swapEntry: replace the value at a key
function swapEntry<
  O,
  ID extends string,
  Adj extends Record<string, any>,
  C extends string,
  TargetID extends string & keyof Adj,
  NewEntry extends NodeEntry<string, string[], any>,
>(
  expr: DirtyExpr<O, DirtyDesc<O, ID, Adj, C>>,
  targetId: TargetID,
  newEntry: NewEntry,
): DirtyExpr<O, DirtyDesc<O, ID, Omit<Adj, TargetID> & Record<TargetID, NewEntry>, C>> {
  const newAdj = { ...expr.__adj, [targetId]: newEntry };
  return { ...expr, __adj: newAdj } as any;
}

// rewireChildren: in all entries, replace oldRef → newRef in children arrays
function rewireChildren<
  O,
  ID extends string,
  Adj extends Record<string, any>,
  C extends string,
  OldRef extends string,
  NewRef extends string,
>(
  expr: DirtyExpr<O, DirtyDesc<O, ID, Adj, C>>,
  oldRef: OldRef,
  newRef: NewRef,
): DirtyExpr<O, DirtyDesc<O, ID, RewiredAdj<Adj, OldRef, NewRef>, C>> {
  const newAdj: Record<string, any> = {};
  for (const [id, entry] of Object.entries(expr.__adj)) {
    const e = entry as any;
    if (e.children) {
      newAdj[id] = {
        ...e,
        children: e.children.map((c: string) => c === oldRef ? newRef : c),
      };
    } else {
      newAdj[id] = entry;
    }
  }
  return { ...expr, __adj: newAdj } as any;
}

// Type-level children rewiring
type RewireChildren<C extends string[], Old extends string, New extends string> = {
  [I in keyof C]: C[I] extends Old ? New : C[I];
};

type RewiredAdj<Adj, Old extends string, New extends string> = {
  [K in keyof Adj]: Adj[K] extends NodeEntry<infer Kind, infer C extends string[], infer Out>
    ? NodeEntry<Kind, RewireChildren<C, Old, New> & string[], Out>
    : Adj[K];
};

// setRoot: change the root ID
function setRoot<
  O,
  Adj extends Record<string, any>,
  C extends string,
  OldID extends string,
  NewID extends string,
>(
  expr: DirtyExpr<O, DirtyDesc<O, OldID, Adj, C>>,
  newRoot: NewID,
): DirtyExpr<O, DirtyDesc<O, NewID, Adj, C>> {
  return { ...expr, __id: newRoot } as any;
}

// ============================================================
// ID helpers
// ============================================================

const ALPHA = "abcdefghijklmnopqrstuvwxyz";
function nextIdRuntime(current: string): string {
  const chars = current.split("");
  let carry = true;
  for (let i = chars.length - 1; i >= 0 && carry; i--) {
    const idx = ALPHA.indexOf(chars[i]);
    if (idx === 25) { chars[i] = "a"; carry = true; }
    else { chars[i] = ALPHA[idx + 1]; carry = false; }
  }
  if (carry) return "a" + chars.join("");
  return chars.join("");
}

function assertEq<T>(actual: T, expected: T, msg: string) {
  if (actual !== expected) {
    throw new Error(`${msg}: expected ${JSON.stringify(expected)}, got ${JSON.stringify(actual)}`);
  }
}

// ============================================================
// BuildCtx (same as spike-runtime, produces clean Expr)
// ============================================================

interface BuildCtx<C extends string> {
  numLit<V extends number>(value: V):
    C extends keyof IDChain
      ? [Expr<number, Desc<number, C, Record<C, NodeEntry<"num/literal", [], number>>, NextID<C> & string>>, BuildCtx<NextID<C> & string>]
      : never;

  strLit<V extends string>(value: V):
    C extends keyof IDChain
      ? [Expr<string, Desc<string, C, Record<C, NodeEntry<"str/literal", [], string>>, NextID<C> & string>>, BuildCtx<NextID<C> & string>]
      : never;

  add<
    RA extends Desc<number, string, Record<string, any>, string>,
    RB extends Desc<number, string, Record<string, any>, string>,
  >(
    left: Expr<number, RA>,
    right: Expr<number, RB>,
  ): C extends keyof IDChain
    ? [Expr<number, Desc<
        number, C,
        AdjOf<RA> & AdjOf<RB> & Record<C, NodeEntry<"num/add", [IdOf<RA>, IdOf<RB>], number>>,
        NextID<C> & string
      >>, BuildCtx<NextID<C> & string>]
    : never;

  mul<
    RA extends Desc<number, string, Record<string, any>, string>,
    RB extends Desc<number, string, Record<string, any>, string>,
  >(
    left: Expr<number, RA>,
    right: Expr<number, RB>,
  ): C extends keyof IDChain
    ? [Expr<number, Desc<
        number, C,
        AdjOf<RA> & AdjOf<RB> & Record<C, NodeEntry<"num/mul", [IdOf<RA>, IdOf<RB>], number>>,
        NextID<C> & string
      >>, BuildCtx<NextID<C> & string>]
    : never;

  neg<
    RA extends Desc<number, string, Record<string, any>, string>,
  >(
    operand: Expr<number, RA>,
  ): C extends keyof IDChain
    ? [Expr<number, Desc<
        number, C,
        AdjOf<RA> & Record<C, NodeEntry<"num/neg", [IdOf<RA>], number>>,
        NextID<C> & string
      >>, BuildCtx<NextID<C> & string>]
    : never;

  named<
    Name extends string,
    O2,
    R extends Desc<O2, string, Record<string, any>, string>,
  >(
    name: Name,
    expr: Expr<O2, R>,
  ): [Expr<O2, Desc<O2, IdOf<R>, AdjOf<R> & Record<NameKey<Name>, NameAlias<Name, IdOf<R>, O2>>, CtrOf<R>>>, BuildCtx<C>];

  // Expose current counter for fresh IDs during mutations
  freshId(): C extends keyof IDChain ? [C, BuildCtx<NextID<C> & string>] : never;
}

function createCtx<C extends string>(counter: C): BuildCtx<C> {
  function makeExpr(kind: string, id: string, adj: Record<string, any>, ctr: string): any {
    return { kind, __id: id, __adj: adj, __counter: ctr };
  }
  const ctx: BuildCtx<any> = {
    numLit(value: number) {
      const id = counter;
      const next = nextIdRuntime(counter);
      return [makeExpr("num/literal", id, { [id]: { kind: "num/literal", children: [], out: value } }, next), createCtx(next)] as any;
    },
    strLit(value: string) {
      const id = counter;
      const next = nextIdRuntime(counter);
      return [makeExpr("str/literal", id, { [id]: { kind: "str/literal", children: [], out: value } }, next), createCtx(next)] as any;
    },
    add(left: any, right: any) {
      const id = counter;
      const next = nextIdRuntime(counter);
      return [makeExpr("num/add", id, { ...left.__adj, ...right.__adj, [id]: { kind: "num/add", children: [left.__id, right.__id] } }, next), createCtx(next)] as any;
    },
    mul(left: any, right: any) {
      const id = counter;
      const next = nextIdRuntime(counter);
      return [makeExpr("num/mul", id, { ...left.__adj, ...right.__adj, [id]: { kind: "num/mul", children: [left.__id, right.__id] } }, next), createCtx(next)] as any;
    },
    neg(operand: any) {
      const id = counter;
      const next = nextIdRuntime(counter);
      return [makeExpr("num/neg", id, { ...operand.__adj, [id]: { kind: "num/neg", children: [operand.__id] } }, next), createCtx(next)] as any;
    },
    named(name: string, expr: any) {
      const adj = { ...expr.__adj, [`@${name}`]: { kind: "@alias", target: expr.__id } };
      return [makeExpr(expr.kind, expr.__id, adj, expr.__counter), ctx] as any;
    },
    freshId() {
      const next = nextIdRuntime(counter);
      return [counter, createCtx(next)] as any;
    },
  };
  return ctx;
}

function freshCtx(): BuildCtx<FirstID> {
  return createCtx("a" as FirstID);
}

// ============================================================
// Test 1: commit succeeds on valid graph
// ============================================================

console.log("=== Test 1: commit valid graph ===");

const $ = freshCtx();
const [lit3, $1] = $.numLit(3);
const [lit4, $2] = $1.numLit(4);
const [sum, $3] = $2.add(lit3, lit4);

// Make dirty, then commit
const dirtySum = dirty(sum);
const cleanSum = commit(dirtySum);

assertEq(cleanSum.__id, "c", "root preserved");
assertEq(cleanSum.__adj["a"].kind, "num/literal", "a intact");
assertEq(cleanSum.__adj["c"].kind, "num/add", "c intact");

console.log("  PASS");

// ============================================================
// Test 2: commit fails at runtime on broken graph
// ============================================================

console.log("\n=== Test 2: commit rejects missing children (runtime) ===");

const dirtied = dirty(sum);
// Add an entry referencing nonexistent child
const broken = addEntry(dirtied, "z" as any, {
  kind: "num/neg",
  children: ["doesnt_exist"],
  out: undefined,
} as any);

let caught = false;
try {
  commit(broken as any);
} catch (e: any) {
  caught = true;
  assertEq(e.message.includes("doesnt_exist"), true, "error mentions missing child");
  console.log("  Caught: " + e.message);
}
assertEq(caught, true, "commit threw on invalid graph");

console.log("  PASS");

// ============================================================
// Test 3: commit rejects missing root (runtime)
// ============================================================

console.log("\n=== Test 3: commit rejects missing root ===");

const dirtied2 = dirty(sum);
const badRoot = setRoot(dirtied2, "nonexistent" as any);

let caught2 = false;
try {
  commit(badRoot as any);
} catch (e: any) {
  caught2 = true;
  assertEq(e.message.includes("nonexistent"), true, "error mentions missing root");
  console.log("  Caught: " + e.message);
}
assertEq(caught2, true, "commit threw on missing root");

console.log("  PASS");

// ============================================================
// Test 4: type-level rejection — missing children
// ============================================================

console.log("\n=== Test 4: type-level commit validation ===");

// Build a valid program
const $t = freshCtx();
const [ta, $t1] = $t.numLit(1);
const [tb, $t2] = $t1.numLit(2);
const [tc, $t3] = $t2.add(ta, tb);

// Valid commit — should type as Expr
const validCommit = commit(dirty(tc));
// Type test: this should be assignable to Expr
const _exprCheck: Expr<number, any> = validCommit;

// Now break it: remove a child that's referenced
const broken2 = removeEntry(dirty(tc), "a");

// This commit should produce GraphError at the type level
// At runtime it also throws, so wrap in try/catch
let caught3 = false;
try {
  const invalidCommit = commit(broken2);
  // @ts-expect-error — GraphError is not assignable to Expr
  const _exprCheck2: Expr<number, any> = invalidCommit;
} catch (e: any) {
  caught3 = true;
  console.log("  Runtime also caught: " + e.message);
}
assertEq(caught3, true, "commit threw on broken graph");

console.log("  @ts-expect-error correctly catches broken commit at type level");
console.log("  Runtime commit also rejects");
console.log("  PASS");

// ============================================================
// Test 5: chain multiple dirty ops, then commit
// ============================================================

console.log("\n=== Test 5: chained dirty ops ===");

const $c = freshCtx();
const [ca, $c1] = $c.numLit(10);
const [cb, $c2] = $c1.numLit(20);
const [cc, $c3] = $c2.add(ca, cb);

// Chain: swap lit(10) → lit(99), then add a neg wrapper
const [freshId, $c4] = $c3.freshId();

const result = commit(
  rewireChildren(
    addEntry(
      swapEntry(
        dirty(cc),
        "a",
        { kind: "num/literal", children: [] as const, out: 99 } as NodeEntry<"num/literal", [], number>,
      ),
      freshId,
      { kind: "num/neg", children: ["b"], out: 0 } as NodeEntry<"num/neg", ["b"], number>,
    ),
    "b" as const,  // in "c" (add), replace ref to "b" with freshId
    freshId,
  )
);

assertEq(result.__adj["a"].out, 99, "a swapped to 99");
assertEq(result.__adj[freshId].kind, "num/neg", "neg wrapper added");
assertEq(result.__adj["c"].children[0], "a", "add left still a");
assertEq(result.__adj["c"].children[1], freshId, "add right rewired to neg");

console.log("  Chained: swap(a→99) + addEntry(neg) + rewire(b→neg)");
console.log("  PASS");

// ============================================================
// Test 6: wrap as a convenience that uses dirty+commit internally
// ============================================================

console.log("\n=== Test 6: wrap = dirty ops + commit ===");

function safeWrap<
  O,
  R extends Desc<O, string, Record<string, any>, string>,
  C extends string & keyof IDChain,
>(
  expr: Expr<O, R>,
  targetId: string & keyof AdjOf<R>,
  wrapperKind: string,
  ctx: BuildCtx<C>,
): [any, BuildCtx<NextID<C> & string>] {
  const [freshId, nextCtx] = ctx.freshId();

  // All sharp knives, producing dirty:
  const step1 = dirty(expr);
  const step2 = addEntry(step1, freshId, {
    kind: wrapperKind,
    children: [targetId],
    out: undefined,
  } as any);
  const step3 = rewireChildren(step2, targetId, freshId);
  // The wrapper itself shouldn't have its own child rewired
  // (it should point to targetId, not to itself)
  // Fix: swap the wrapper entry back to point to targetId
  const step4 = swapEntry(step3, freshId, {
    kind: wrapperKind,
    children: [targetId],
    out: undefined,
  } as any);

  // commit validates everything
  const result = commit(step4 as any);
  return [result, nextCtx as any];
}

const $sw = freshCtx();
const [sw3, $sw1] = $sw.numLit(3);
const [sw4, $sw2] = $sw1.numLit(4);
const [swSum, $sw3] = $sw2.add(sw3, sw4);

const [swWrapped, $sw4] = safeWrap(swSum, "a", "num/neg", $sw3);

assertEq(swWrapped.__adj["d"].kind, "num/neg", "wrapper is neg");
assertEq(swWrapped.__adj["d"].children[0], "a", "wrapper → a");
assertEq(swWrapped.__adj["c"].children[0], "d", "add rewired to wrapper");
assertEq(swWrapped.__adj["c"].children[1], "b", "add right unchanged");
assertEq(swWrapped.__adj["a"].kind, "num/literal", "a untouched");
assertEq(swWrapped.__id, "c", "root unchanged");

console.log("  wrap(add(3,4), 'a', neg) → add(neg(3), 4) via dirty+commit");
console.log("  PASS");

// ============================================================
// Test 7: type-level prevents passing DirtyExpr to consumers
// ============================================================

console.log("\n=== Test 7: DirtyExpr not assignable to Expr ===");

function consume<O, R extends Desc<O, string, Record<string, any>, string>>(
  expr: Expr<O, R>,
): string {
  return expr.__id;
}

const $p = freshCtx();
const [pa, $p1] = $p.numLit(42);
const dirtyPa = dirty(pa);

// This works — clean Expr
consume(pa);

// @ts-expect-error — DirtyExpr not assignable to Expr
consume(dirtyPa);

console.log("  DirtyExpr correctly rejected by consumer function");
console.log("  PASS");

// ============================================================
// Summary
// ============================================================

console.log("\n=== All tests passed ===");

spike-expr-final.ts

// ============================================================
// Expr<O, R> Spike — Content-Addressed DAG with Type-Safe Rewrites
// ============================================================
//
// Design decisions proven by this spike:
//   1. Expr<O, R> — O is output type (inference hint), R is full descriptor
//   2. R = Desc<O, ID, Adj> — single descriptor with output, identity, adjacency
//   3. Content-addressed IDs via template literals — zero ceremony, auto-dedup
//   4. Intersection-based adjacency map — flat, O(1) depth queries/rewrites
//   5. DAG sharing via intersection dedup — same content = same key
//   6. NoInfer<T> on cond's else branch — catches mismatched branches
//
// Verified: 400+ node programs, all queries/rewrites pass, ~2s compile time.

// ============================================================
// Core types
// ============================================================

/** Entry in the adjacency map describing a single node */
type NodeEntry<Kind extends string, ChildIDs extends string[], Out> = {
  readonly kind: Kind;
  readonly children: ChildIDs;
  readonly out: Out;
};

/** Full descriptor: output type + content-addressed ID + adjacency map */
type Desc<Out, ID extends string, Adj extends Record<string, any>> = {
  readonly o: Out;
  readonly id: ID;
  readonly adj: Adj;
};

/** Branded Expr with two phantom params: O (output type) and R (descriptor) */
declare const exprBrand: unique symbol;
interface Expr<O, R extends Desc<O, string, Record<string, any>>> {
  readonly [exprBrand]: R;
  readonly kind: string;
}

// ============================================================
// Descriptor field extractors
// ============================================================

type OutOf<R> = R extends Desc<infer O, any, any> ? O : never;
type IdOf<R> = R extends Desc<any, infer ID, any> ? ID : never;
type AdjOf<R> = R extends Desc<any, any, infer A> ? A : never;

// ============================================================
// Content-addressed IDs via template literal types
// ============================================================

type LitID<V extends string | number | boolean> = `lit(${V})`;
type AddID<L extends string, R extends string> = `add(${L},${R})`;
type MulID<L extends string, R extends string> = `mul(${L},${R})`;
type NegID<A extends string> = `neg(${A})`;
type GtID<L extends string, R extends string> = `gt(${L},${R})`;
type CondID<P extends string, T extends string, E extends string> = `cond(${P},${T},${E})`;
type ShowID<A extends string> = `show(${A})`;
type ConcatID<L extends string, R extends string> = `concat(${L},${R})`;

// ============================================================
// Builders
// ============================================================

function numLit<V extends number>(
  value: V,
): Expr<number, Desc<number, LitID<V>, Record<LitID<V>, NodeEntry<"num/literal", [], number>>>> {
  return { kind: "num/literal", value } as any;
}

function strLit<V extends string>(
  value: V,
): Expr<string, Desc<string, LitID<V>, Record<LitID<V>, NodeEntry<"str/literal", [], string>>>> {
  return { kind: "str/literal", value } as any;
}

function add<
  RA extends Desc<number, string, Record<string, any>>,
  RB extends Desc<number, string, Record<string, any>>,
>(
  left: Expr<number, RA>,
  right: Expr<number, RB>,
): Expr<number, Desc<
  number,
  AddID<IdOf<RA>, IdOf<RB>>,
  AdjOf<RA> & AdjOf<RB> & Record<AddID<IdOf<RA>, IdOf<RB>>, NodeEntry<"num/add", [IdOf<RA>, IdOf<RB>], number>>
>> {
  return { kind: "num/add", left, right } as any;
}

function mul<
  RA extends Desc<number, string, Record<string, any>>,
  RB extends Desc<number, string, Record<string, any>>,
>(
  left: Expr<number, RA>,
  right: Expr<number, RB>,
): Expr<number, Desc<
  number,
  MulID<IdOf<RA>, IdOf<RB>>,
  AdjOf<RA> & AdjOf<RB> & Record<MulID<IdOf<RA>, IdOf<RB>>, NodeEntry<"num/mul", [IdOf<RA>, IdOf<RB>], number>>
>> {
  return { kind: "num/mul", left, right } as any;
}

function neg<
  RA extends Desc<number, string, Record<string, any>>,
>(
  operand: Expr<number, RA>,
): Expr<number, Desc<
  number,
  NegID<IdOf<RA>>,
  AdjOf<RA> & Record<NegID<IdOf<RA>>, NodeEntry<"num/neg", [IdOf<RA>], number>>
>> {
  return { kind: "num/neg", operand } as any;
}

function gt<
  RA extends Desc<number, string, Record<string, any>>,
  RB extends Desc<number, string, Record<string, any>>,
>(
  left: Expr<number, RA>,
  right: Expr<number, RB>,
): Expr<boolean, Desc<
  boolean,
  GtID<IdOf<RA>, IdOf<RB>>,
  AdjOf<RA> & AdjOf<RB> & Record<GtID<IdOf<RA>, IdOf<RB>>, NodeEntry<"num/gt", [IdOf<RA>, IdOf<RB>], boolean>>
>> {
  return { kind: "num/gt", left, right } as any;
}

function show<
  RA extends Desc<number, string, Record<string, any>>,
>(
  value: Expr<number, RA>,
): Expr<string, Desc<
  string,
  ShowID<IdOf<RA>>,
  AdjOf<RA> & Record<ShowID<IdOf<RA>>, NodeEntry<"str/show", [IdOf<RA>], string>>
>> {
  return { kind: "str/show", operand: value } as any;
}

function concat<
  RA extends Desc<string, string, Record<string, any>>,
  RB extends Desc<string, string, Record<string, any>>,
>(
  left: Expr<string, RA>,
  right: Expr<string, RB>,
): Expr<string, Desc<
  string,
  ConcatID<IdOf<RA>, IdOf<RB>>,
  AdjOf<RA> & AdjOf<RB> & Record<ConcatID<IdOf<RA>, IdOf<RB>>, NodeEntry<"str/concat", [IdOf<RA>, IdOf<RB>], string>>
>> {
  return { kind: "str/concat", left, right } as any;
}

function cond<
  T,
  RP extends Desc<boolean, string, Record<string, any>>,
  RT extends Desc<T, string, Record<string, any>>,
  RE extends Desc<NoInfer<T>, string, Record<string, any>>,
>(
  pred: Expr<boolean, RP>,
  then_: Expr<T, RT>,
  else_: Expr<NoInfer<T>, RE>,
): Expr<T, Desc<
  T,
  CondID<IdOf<RP>, IdOf<RT>, IdOf<RE>>,
  AdjOf<RP> & AdjOf<RT> & AdjOf<RE> & Record<CondID<IdOf<RP>, IdOf<RT>, IdOf<RE>>, NodeEntry<"core/cond", [IdOf<RP>, IdOf<RT>, IdOf<RE>], T>>
>> {
  return { kind: "core/cond", pred, then: then_, else: else_ } as any;
}

// ============================================================
// Type-level queries — all O(1) depth (flat mapped types)
// ============================================================

/** Extract R from an Expr */
type ROf<E> = E extends Expr<any, infer R> ? R : never;

/** Does the program contain a node of the given kind? */
type ContainsKind<R, K extends string> =
  R extends Desc<any, any, infer Adj>
    ? { [Key in keyof Adj]: Adj[Key] extends NodeEntry<K, any, any> ? true : never }[keyof Adj] extends never
      ? false
      : true
    : false;

/** Collect all output types across all nodes */
type CollectOutputs<R> =
  R extends Desc<any, any, infer Adj>
    ? { [Key in keyof Adj]: Adj[Key] extends NodeEntry<any, any, infer O> ? O : never }[keyof Adj]
    : never;

/** Collect all node kinds */
type CollectKinds<R> =
  R extends Desc<any, any, infer Adj>
    ? { [Key in keyof Adj]: Adj[Key] extends NodeEntry<infer K, any, any> ? K : never }[keyof Adj]
    : never;

// ============================================================
// Type-level rewrites — R → R in one type function
// ============================================================

/** Rewrite all nodes of kind From to kind To */
type RewriteKind<R, From extends string, To extends string> =
  R extends Desc<infer O, infer ID, infer Adj>
    ? Desc<O, ID, {
        [K in keyof Adj]: Adj[K] extends NodeEntry<From, infer C, infer Out>
          ? NodeEntry<To, C, Out>
          : Adj[K]
      }>
    : never;

/** Term-level rewrite (type tracks the transformation) */
function rewriteKind<
  O, R extends Desc<O, string, Record<string, any>>,
  From extends string, To extends string,
>(expr: Expr<O, R>, _from: From, _to: To): Expr<O, RewriteKind<R, From, To>> {
  // Runtime: walk term, swap kind strings
  return expr as any;
}

// ============================================================
// Test 1: Basic type checking
// ============================================================

const a = numLit(3);
const b = numLit(4);
const c = add(a, b);
const d = mul(c, numLit(5));
const e = neg(d);

// Cross-type composition
const num = add(numLit(1), numLit(2));
const str = show(num);
const msg = concat(strLit("result: "), str);

// Type errors caught:
// @ts-expect-error: can't add string to number
const bad1 = add(numLit(1), strLit("oops"));

// @ts-expect-error: can't concat number with string
const bad2 = concat(numLit(1), strLit("hi"));

// ============================================================
// Test 2: cond — branch type enforcement
// ============================================================

const pred = gt(numLit(1), numLit(2));

// Valid: both branches number
const ok1 = cond(pred, numLit(3), numLit(4));

// Valid: both branches string
const ok2 = cond(pred, strLit("yes"), strLit("no"));

// @ts-expect-error: number vs string mismatch
const bad3 = cond(pred, numLit(3), strLit("nope"));

// @ts-expect-error: string vs number mismatch (reversed)
const bad4 = cond(pred, strLit("yes"), numLit(3));

// Nested cond: valid
const nested_ok = cond(pred, cond(pred, numLit(1), numLit(2)), numLit(3));

// @ts-expect-error: nested cond with mismatch
const nested_bad = cond(pred, cond(pred, numLit(1), numLit(2)), strLit("nope"));

// ============================================================
// Test 3: DAG sharing
// ============================================================

// Same node referenced twice — appears once in adjacency map
const shared = numLit(42);
const dag = add(shared, shared);

// Content-addressed structural equality
const tree1 = add(numLit(1), numLit(2));
const tree2 = add(numLit(1), numLit(2));
// tree1 and tree2 have identical R types — free structural equality

// ============================================================
// Test 4: Queries
// ============================================================

type MsgR = ROf<typeof msg>;
type MsgOutput = OutOf<MsgR>;                          // string
type MsgHasAdd = ContainsKind<MsgR, "num/add">;        // true
type MsgHasConcat = ContainsKind<MsgR, "str/concat">;  // true
type MsgHasFetch = ContainsKind<MsgR, "fetch/get">;    // false
type MsgAllOutputs = CollectOutputs<MsgR>;              // number | string
type MsgAllKinds = CollectKinds<MsgR>;                  // "num/literal" | "num/add" | "str/show" | "str/literal" | "str/concat"

// ============================================================
// Test 5: Rewrites
// ============================================================

type MsgRewritten = RewriteKind<MsgR, "num/add", "num/mul">;
type MsgRewrittenHasAdd = ContainsKind<MsgRewritten, "num/add">;   // false
type MsgRewrittenHasMul = ContainsKind<MsgRewritten, "num/mul">;   // true
type MsgRewrittenOutput = OutOf<MsgRewritten>;                      // string (preserved)

// Chained rewrites
type DoubleRewrite = RewriteKind<RewriteKind<MsgR, "num/add", "num/mul">, "str/concat", "str/join">;
type DRHasMul = ContainsKind<DoubleRewrite, "num/mul">;       // true
type DRHasJoin = ContainsKind<DoubleRewrite, "str/join">;     // true
type DRHasAdd = ContainsKind<DoubleRewrite, "num/add">;       // false
type DRHasConcat = ContainsKind<DoubleRewrite, "str/concat">; // false

// Term-level rewrite with type tracking
const rewritten = rewriteKind(msg, "num/add", "num/mul");
// rewritten: Expr<string, RewriteKind<MsgR, "num/add", "num/mul">>

// ============================================================
// Test 6: Stress test — deep chains
// ============================================================

function deepChain<R extends Desc<number, string, Record<string, any>>>(
  base: Expr<number, R>,
) {
  const l1 = numLit(1);
  const a = add(base, l1);
  const l2 = numLit(2);
  const b = mul(a, l2);
  const l3 = numLit(3);
  const c = add(b, l3);
  const l4 = numLit(4);
  const d = mul(c, l4);
  const l5 = numLit(5);
  const e = add(d, l5);
  return e;
}

const ch1 = deepChain(numLit(0));
const ch2 = deepChain(ch1);
const ch3 = deepChain(ch2);
const ch4 = deepChain(ch3);
const ch5 = deepChain(ch4);
const ch10 = deepChain(deepChain(deepChain(deepChain(deepChain(ch5)))));
const ch20 = deepChain(deepChain(deepChain(deepChain(deepChain(
  deepChain(deepChain(deepChain(deepChain(deepChain(ch10))))))))));
const ch30 = deepChain(deepChain(deepChain(deepChain(deepChain(
  deepChain(deepChain(deepChain(deepChain(deepChain(ch20))))))))));
const ch40 = deepChain(deepChain(deepChain(deepChain(deepChain(
  deepChain(deepChain(deepChain(deepChain(deepChain(ch30))))))))));

// Queries at 400+ node depth — all O(1) due to flat adjacency
type Ch40R = ROf<typeof ch40>;
type Ch40HasAdd = ContainsKind<Ch40R, "num/add">;       // true
type Ch40HasMul = ContainsKind<Ch40R, "num/mul">;       // true
type Ch40Outputs = CollectOutputs<Ch40R>;                // number
type Ch40Kinds = CollectKinds<Ch40R>;                    // "num/literal" | "num/add" | "num/mul"

// Rewrite at scale
type Ch40Rewritten = RewriteKind<Ch40R, "num/add", "num/mul">;
type Ch40RewrittenHasAdd = ContainsKind<Ch40Rewritten, "num/add">; // false
type Ch40RewrittenKinds = CollectKinds<Ch40Rewritten>;              // "num/literal" | "num/mul"

console.log("All tests pass");

spike-foldast-bridge.ts

// ============================================================
// Spike: foldAST bridge — tree ↔ adjacency map round-trip
// ============================================================
//
// Proves: DAGQL transforms on adjacency maps can be converted
// back to tree-shaped AST that the existing foldAST consumes.
//
// The bridge:
//   app() → Program (tree AST)
//     → toDAG: flatten to adjacency map
//     → DAGQL transforms (mapWhere, wrapWhere, splice, etc.)
//     → toAST: reconstruct tree from adjacency map
//   → foldAST(interpreter, reconstructed tree)
// ============================================================

import { mvfm } from "./packages/core/src/core";
import { foldAST, defaults } from "./packages/core/src";
import { num } from "./packages/core/src/plugins/num";
import { str } from "./packages/core/src/plugins/str";
import { semiring } from "./packages/core/src/plugins/semiring";

// ============================================================
// Types for the adjacency map
// ============================================================

interface DagEntry {
  kind: string;
  // Named fields → child IDs (preserves field names for tree reconstruction)
  fields: Record<string, string | string[]>;
  // For leaf values (core/literal, etc.)
  data: Record<string, unknown>;
}

interface Dag {
  rootId: string;
  entries: Record<string, DagEntry>;
  counter: number;
}

// ============================================================
// toDAG: flatten tree AST → adjacency map
// ============================================================

function toDAG(ast: any): Dag {
  const entries: Record<string, DagEntry> = {};
  let counter = 0;

  function walk(node: any): string {
    // Reuse existing __id if present, otherwise assign fresh
    const id = String(counter++);

    const fields: Record<string, string | string[]> = {};
    const data: Record<string, unknown> = {};

    for (const [key, val] of Object.entries(node)) {
      if (key === "kind" || key === "__id" || key === "__T") continue;

      if (Array.isArray(val)) {
        // Array of child nodes (e.g., values, steps)
        if (val.length > 0 && typeof val[0] === "object" && val[0] !== null && "kind" in val[0]) {
          fields[key] = val.map((child: any) => walk(child));
        } else {
          data[key] = val; // primitive array
        }
      } else if (typeof val === "object" && val !== null && "kind" in val) {
        // Single child node
        fields[key] = walk(val);
      } else {
        // Primitive data (value, etc.)
        data[key] = val;
      }
    }

    entries[id] = { kind: node.kind, fields, data };
    return id;
  }

  const rootId = walk(ast);
  return { rootId, entries, counter };
}

// ============================================================
// toAST: reconstruct tree from adjacency map
// ============================================================

function toAST(dag: Dag): any {
  const { rootId, entries } = dag;

  function materialize(id: string): any {
    const entry = entries[id];
    if (!entry) throw new Error(`Missing entry for id ${id}`);

    const node: any = { kind: entry.kind };

    // Restore named fields as child nodes
    for (const [key, val] of Object.entries(entry.fields)) {
      if (Array.isArray(val)) {
        node[key] = val.map((childId) => materialize(childId));
      } else {
        node[key] = materialize(val);
      }
    }

    // Restore leaf data
    for (const [key, val] of Object.entries(entry.data)) {
      node[key] = val;
    }

    return node;
  }

  return materialize(rootId);
}

// ============================================================
// Simple DAGQL-style transforms on the adjacency map
// ============================================================

function selectByKind(dag: Dag, kind: string): string[] {
  return Object.entries(dag.entries)
    .filter(([_, e]) => e.kind === kind)
    .map(([id]) => id);
}

function mapByKind(
  dag: Dag,
  kind: string,
  fn: (entry: DagEntry, id: string) => DagEntry,
): Dag {
  const newEntries: Record<string, DagEntry> = {};
  for (const [id, entry] of Object.entries(dag.entries)) {
    newEntries[id] = entry.kind === kind ? fn(entry, id) : entry;
  }
  return { ...dag, entries: newEntries };
}

function replaceEntry(dag: Dag, id: string, newEntry: DagEntry): Dag {
  return {
    ...dag,
    entries: { ...dag.entries, [id]: newEntry },
  };
}

// ============================================================
// Tests
// ============================================================

let passed = 0;
let failed = 0;
function assert(cond: boolean, msg: string) {
  if (cond) { passed++; console.log(`  ✓ ${msg}`); }
  else { failed++; console.log(`  ✗ ${msg}`); }
}

async function run() {
  const app = mvfm(num, str, semiring);
  const interp = defaults(app);

  // ---- Test 1: round-trip without transform ----
  console.log("Test 1: round-trip — tree → DAG → tree → foldAST");

  const prog1 = app(($) => $.add(1, 2));
  const original = await foldAST(interp, prog1);
  assert(original === 3, `original: add(1,2) = ${original}`);

  const dag1 = toDAG(prog1.ast);
  const rebuilt1 = toAST(dag1);
  const roundTripped = await foldAST(interp, rebuilt1);
  assert(roundTripped === 3, `round-tripped: add(1,2) = ${roundTripped}`);

  // ---- Test 2: modify a literal, then foldAST ----
  console.log("Test 2: modify literal — change 1 to 99, expect 99+2=101");

  const dag2 = toDAG(prog1.ast);
  // Find the literal with value 1
  const litIds = Object.entries(dag2.entries)
    .filter(([_, e]) => e.kind === "core/literal" && e.data.value === 1)
    .map(([id]) => id);
  assert(litIds.length === 1, `found literal(1) at id ${litIds[0]}`);

  const modified = replaceEntry(dag2, litIds[0], {
    kind: "core/literal",
    fields: {},
    data: { value: 99 },
  });
  const rebuilt2 = toAST(modified);
  const result2 = await foldAST(interp, rebuilt2);
  assert(result2 === 101, `modified: add(99,2) = ${result2}`);

  // ---- Test 3: deeper program — (3+4)*5 ----
  console.log("Test 3: deeper program — (3+4)*5 = 35");

  const prog3 = app(($) => $.mul($.add(3, 4), 5));
  const orig3 = await foldAST(interp, prog3);
  assert(orig3 === 35, `original: (3+4)*5 = ${orig3}`);

  const dag3 = toDAG(prog3.ast);
  const rebuilt3 = toAST(dag3);
  const rt3 = await foldAST(interp, rebuilt3);
  assert(rt3 === 35, `round-tripped: (3+4)*5 = ${rt3}`);

  // ---- Test 4: mapByKind — replace all num/add with num/mul ----
  console.log("Test 4: mapByKind — replace num/add with num/mul → (3*4)*5 = 60");

  const dag4 = toDAG(prog3.ast);
  const swapped = mapByKind(dag4, "num/add", (entry) => ({
    ...entry,
    kind: "num/mul",
  }));
  const rebuilt4 = toAST(swapped);
  const result4 = await foldAST(interp, rebuilt4);
  assert(result4 === 60, `swapped add→mul: (3*4)*5 = ${result4}`);

  // ---- Test 5: constant folding via DAGQL ----
  console.log("Test 5: constant fold — replace add(3,4) with literal(7)");

  const dag5 = toDAG(prog3.ast);
  const addIds = selectByKind(dag5, "num/add");
  assert(addIds.length === 1, `found 1 num/add node`);

  // Replace the add node with a literal
  const folded = replaceEntry(dag5, addIds[0], {
    kind: "core/literal",
    fields: {},
    data: { value: 7 },
  });
  const rebuilt5 = toAST(folded);
  const result5 = await foldAST(interp, rebuilt5);
  assert(result5 === 35, `folded: 7*5 = ${result5}`);

  // ---- Test 6: string program round-trip ----
  console.log("Test 6: string program round-trip");

  const prog6 = app(($) => $.concat("hello", " ", "world"));
  const orig6 = await foldAST(interp, prog6);
  assert(orig6 === "hello world", `original: concat = "${orig6}"`);

  const dag6 = toDAG(prog6.ast);
  const rebuilt6 = toAST(dag6);
  const rt6 = await foldAST(interp, rebuilt6);
  assert(rt6 === "hello world", `round-tripped: concat = "${rt6}"`);

  // ---- Test 7: selectByKind on adjacency map ----
  console.log("Test 7: selectByKind works on flattened DAG");

  const dag7 = toDAG(prog3.ast);
  const literals = selectByKind(dag7, "core/literal");
  assert(literals.length === 3, `found ${literals.length} literals (3, 4, 5)`);
  const adds = selectByKind(dag7, "num/add");
  assert(adds.length === 1, `found ${adds.length} num/add`);
  const muls = selectByKind(dag7, "num/mul");
  assert(muls.length === 1, `found ${muls.length} num/mul`);

  // ---- Test 8: defaults(app) is unaffected ----
  console.log("Test 8: defaults(app) doesn't depend on AST shape");
  // defaults only reads app.plugins, not the AST.
  // If we transform the AST and use the same interpreter, it works.
  const interp2 = defaults(app);
  const result8 = await foldAST(interp2, rebuilt4); // the add→mul swapped tree
  assert(result8 === 60, `same interpreter on transformed tree: ${result8}`);

  console.log(`\nResults: ${passed} passed, ${failed} failed`);
  if (failed > 0) process.exit(1);
  console.log("\nfoldAST bridge spike passed!");
}

run().catch((e) => { console.error(e); process.exit(1); });

spike-idchain-test.ts

// ============================================================
// Spike: Codegenned ID chain — O(1) fresh IDs, no recursion
// ============================================================

import { IDChain, FirstID } from "./spike-idchain";

// ============================================================
// Core types
// ============================================================

type NodeEntry<Kind extends string, ChildIDs extends string[], Out> = {
  readonly kind: Kind;
  readonly children: ChildIDs;
  readonly out: Out;
};

// NextID: O(1) property lookup, no recursion
type NextID<Current extends keyof IDChain> = IDChain[Current];

// Desc now carries a counter string instead of a dispenser
type Desc<Out, ID extends string, Adj extends Record<string, any>, C extends string> = {
  readonly o: Out;
  readonly id: ID;
  readonly adj: Adj;
  readonly c: C;  // counter: next available ID
};

declare const exprBrand: unique symbol;
interface Expr<O, R extends Desc<O, string, Record<string, any>, string>> {
  readonly [exprBrand]: R;
  readonly kind: string;
}

type OutOf<R> = R extends Desc<infer O, any, any, any> ? O : never;
type IdOf<R> = R extends Desc<any, infer ID, any, any> ? ID : never;
type AdjOf<R> = R extends Desc<any, any, infer A, any> ? A : never;
type CtrOf<R> = R extends Desc<any, any, any, infer C> ? C : never;

// ============================================================
// Builders: each uses the counter as node ID, advances counter
// ============================================================

function numLit<V extends number, C extends string & keyof IDChain>(
  value: V,
  _counter: C,
): Expr<number, Desc<
  number,
  C,
  Record<C, NodeEntry<"num/literal", [], number>>,
  NextID<C> & string
>> {
  return {} as any;
}

function strLit<V extends string, C extends string & keyof IDChain>(
  value: V,
  _counter: C,
): Expr<string, Desc<
  string,
  C,
  Record<C, NodeEntry<"str/literal", [], string>>,
  NextID<C> & string
>> {
  return {} as any;
}

function add<
  RA extends Desc<number, string, Record<string, any>, string>,
  RB extends Desc<number, string, Record<string, any>, string>,
>(
  left: Expr<number, RA>,
  right: Expr<number, RB>,
): CtrOf<RB> extends keyof IDChain
  ? Expr<number, Desc<
      number,
      CtrOf<RB> & string,
      AdjOf<RA> & AdjOf<RB> & Record<CtrOf<RB> & string, NodeEntry<"num/add", [IdOf<RA>, IdOf<RB>], number>>,
      NextID<CtrOf<RB> & keyof IDChain> & string
    >>
  : never {
  return {} as any;
}

function mul<
  RA extends Desc<number, string, Record<string, any>, string>,
  RB extends Desc<number, string, Record<string, any>, string>,
>(
  left: Expr<number, RA>,
  right: Expr<number, RB>,
): CtrOf<RB> extends keyof IDChain
  ? Expr<number, Desc<
      number,
      CtrOf<RB> & string,
      AdjOf<RA> & AdjOf<RB> & Record<CtrOf<RB> & string, NodeEntry<"num/mul", [IdOf<RA>, IdOf<RB>], number>>,
      NextID<CtrOf<RB> & keyof IDChain> & string
    >>
  : never {
  return {} as any;
}

// ============================================================
// But wait — same threading problem. Let's use a context.
// ============================================================

interface BuildCtx<C extends string> {
  numLit<V extends number>(value: V):
    C extends keyof IDChain
      ? [Expr<number, Desc<number, C, Record<C, NodeEntry<"num/literal", [], number>>, NextID<C> & string>>, BuildCtx<NextID<C> & string>]
      : never;

  strLit<V extends string>(value: V):
    C extends keyof IDChain
      ? [Expr<string, Desc<string, C, Record<C, NodeEntry<"str/literal", [], string>>, NextID<C> & string>>, BuildCtx<NextID<C> & string>]
      : never;

  add<
    RA extends Desc<number, string, Record<string, any>, string>,
    RB extends Desc<number, string, Record<string, any>, string>,
  >(
    left: Expr<number, RA>,
    right: Expr<number, RB>,
  ): C extends keyof IDChain
    ? [Expr<number, Desc<
        number,
        C,
        AdjOf<RA> & AdjOf<RB> & Record<C, NodeEntry<"num/add", [IdOf<RA>, IdOf<RB>], number>>,
        NextID<C> & string
      >>, BuildCtx<NextID<C> & string>]
    : never;

  mul<
    RA extends Desc<number, string, Record<string, any>, string>,
    RB extends Desc<number, string, Record<string, any>, string>,
  >(
    left: Expr<number, RA>,
    right: Expr<number, RB>,
  ): C extends keyof IDChain
    ? [Expr<number, Desc<
        number,
        C,
        AdjOf<RA> & AdjOf<RB> & Record<C, NodeEntry<"num/mul", [IdOf<RA>, IdOf<RB>], number>>,
        NextID<C> & string
      >>, BuildCtx<NextID<C> & string>]
    : never;

  cond<
    T,
    RP extends Desc<boolean, string, Record<string, any>, string>,
    RT extends Desc<T, string, Record<string, any>, string>,
    RE extends Desc<NoInfer<T>, string, Record<string, any>, string>,
  >(
    pred: Expr<boolean, RP>,
    then_: Expr<T, RT>,
    else_: Expr<NoInfer<T>, RE>,
  ): C extends keyof IDChain
    ? [Expr<T, Desc<
        T,
        C,
        AdjOf<RP> & AdjOf<RT> & AdjOf<RE> & Record<C, NodeEntry<"core/cond", [IdOf<RP>, IdOf<RT>, IdOf<RE>], T>>,
        NextID<C> & string
      >>, BuildCtx<NextID<C> & string>]
    : never;
}

declare function createCtx(): BuildCtx<FirstID>;

// ============================================================
// Test: build a program
// ============================================================

const $ = createCtx();
const [lit3, $1] = $.numLit(3);
const [lit4, $2] = $1.numLit(4);
const [sum, $3] = $2.add(lit3, lit4);
const [lit5, $4] = $3.numLit(5);
const [prog, $5] = $4.mul(sum, lit5);

// Verify IDs
type ProgR = (typeof prog)[typeof exprBrand];
type ProgID = IdOf<ProgR>;
type ProgAdj = AdjOf<ProgR>;

const _progId: ProgID = "e";  // 5th ID: a,b,c,d,e

// Check adj entries
type HasA = "a" extends keyof ProgAdj ? true : false;
type HasB = "b" extends keyof ProgAdj ? true : false;
type HasC = "c" extends keyof ProgAdj ? true : false;
type HasD = "d" extends keyof ProgAdj ? true : false;
type HasE = "e" extends keyof ProgAdj ? true : false;

const _a: HasA = true;
const _b: HasB = true;
const _c: HasC = true;
const _d: HasD = true;
const _e: HasE = true;

// Check add's children
type AddEntry = ProgAdj["c"];
type AddKids = AddEntry extends NodeEntry<any, infer C, any> ? C : never;
const _addKids: AddKids = ["a", "b"];

// Check mul's children
type MulEntry = ProgAdj["e"];
type MulKids = MulEntry extends NodeEntry<any, infer C, any> ? C : never;
const _mulKids: MulKids = ["c", "d"];

// ============================================================
// Replacement: just swap the entry. No cascade.
// ============================================================

type ReplaceEntry<
  Adj extends Record<string, any>,
  TargetID extends string,
  NewEntry,
> = {
  [K in keyof Adj]: K extends TargetID ? NewEntry : Adj[K];
};

function replaceNode<
  O,
  R extends Desc<O, string, Record<string, any>, string>,
  TargetID extends string & keyof AdjOf<R>,
  NewKind extends string,
  NewChildren extends string[],
>(
  program: Expr<O, R>,
  targetId: TargetID,
  newKind: NewKind,
  newChildren: NewChildren,
): Expr<O, Desc<
  O,
  IdOf<R>,
  ReplaceEntry<AdjOf<R>, TargetID, NodeEntry<NewKind, NewChildren, AdjOf<R>[TargetID] extends NodeEntry<any, any, infer TO> ? TO : never>>,
  CtrOf<R>
>> {
  return {} as any;
}

const replaced = replaceNode(prog, "a", "num/literal", []);

// Root ID unchanged
type ReplacedR = (typeof replaced)[typeof exprBrand];
type ReplacedID = IdOf<ReplacedR>;
const _replacedId: ReplacedID = "e";  // still e!

// Parents still reference "a" — no cascade needed
type ReplacedAdj = AdjOf<ReplacedR>;
type ReplacedAddKids = ReplacedAdj["c"] extends NodeEntry<any, infer C, any> ? C : never;
const _rAddKids: ReplacedAddKids = ["a", "b"];  // unchanged!

// ============================================================
// Queries: identical to before
// ============================================================

type ContainsKind<R, K extends string> =
  R extends Desc<any, any, infer Adj, any>
    ? { [Key in keyof Adj]: Adj[Key] extends NodeEntry<K, any, any> ? true : never }[keyof Adj] extends never
      ? false
      : true
    : false;

type CollectKinds<R> =
  R extends Desc<any, any, infer Adj, any>
    ? { [K in keyof Adj]: Adj[K] extends NodeEntry<infer Kind, any, any> ? Kind : never }[keyof Adj]
    : never;

type ProgHasAdd = ContainsKind<ProgR, "num/add">;
type ProgHasSub = ContainsKind<ProgR, "num/sub">;
const _hasAdd: ProgHasAdd = true;
const _hasSub: ProgHasSub = false;

type Kinds = CollectKinds<ProgR>;
// ^? "num/literal" | "num/add" | "num/mul"

// ============================================================
// Scale test: build a longer chain
// ============================================================

const $$ = createCtx();
const [n0, $$1] = $$.numLit(1);
const [n1, $$2] = $$1.numLit(2);
const [s0, $$3] = $$2.add(n0, n1);
const [n2, $$4] = $$3.numLit(3);
const [s1, $$5] = $$4.add(s0, n2);
const [n3, $$6] = $$5.numLit(4);
const [s2, $$7] = $$6.add(s1, n3);
const [n4, $$8] = $$7.numLit(5);
const [s3, $$9] = $$8.add(s2, n4);
const [n5, $$10] = $$9.numLit(6);
const [s4, $$11] = $$10.add(s3, n5);
const [n6, $$12] = $$11.numLit(7);
const [s5, $$13] = $$12.add(s4, n6);
const [n7, $$14] = $$13.numLit(8);
const [s6, $$15] = $$14.add(s5, n7);
const [n8, $$16] = $$15.numLit(9);
const [s7, $$17] = $$16.add(s6, n8);
const [n9, $$18] = $$17.numLit(10);
const [s8, $$19] = $$18.add(s7, n9);

// 19 nodes, counter should be at "t" (20th letter)
type ScaleR = (typeof s8)[typeof exprBrand];
type ScaleCtr = CtrOf<ScaleR>;
const _scaleCtr: ScaleCtr = "t";

type ScaleKinds = CollectKinds<ScaleR>;
// ^? "num/literal" | "num/add"

console.log("ID chain spike compiled successfully");

spike-increment.ts

// ============================================================
// Spike: Type-level string increment — replacing 18k IDChain
// ============================================================
//
// Instead of a codegenned 18k-line lookup table, compute NextID
// algorithmically: base-26 increment on lowercase strings.
//   a → b → ... → z → aa → ab → ... → az → ba → ... → zz → aaa → ...
//
// Recursion depth = number of trailing z's (max = string length).
// For "abc": 0. For "zzz": 3. Well within TS limits.
// ============================================================

// 26-entry char successor table (the ONLY lookup)
type CharNext = {
  a: "b"; b: "c"; c: "d"; d: "e"; e: "f"; f: "g"; g: "h"; h: "i";
  i: "j"; j: "k"; k: "l"; l: "m"; m: "n"; n: "o"; o: "p"; p: "q";
  q: "r"; r: "s"; s: "t"; t: "u"; u: "v"; v: "w"; w: "x"; x: "y";
  y: "z";
};

// IncrementLast: advance the last character (non-z case)
// Each pattern is unambiguous — trailing literal forces single-char match
type IncrementLast<S extends string> =
  S extends `${infer R}a` ? `${R}b` : S extends `${infer R}b` ? `${R}c` :
  S extends `${infer R}c` ? `${R}d` : S extends `${infer R}d` ? `${R}e` :
  S extends `${infer R}e` ? `${R}f` : S extends `${infer R}f` ? `${R}g` :
  S extends `${infer R}g` ? `${R}h` : S extends `${infer R}h` ? `${R}i` :
  S extends `${infer R}i` ? `${R}j` : S extends `${infer R}j` ? `${R}k` :
  S extends `${infer R}k` ? `${R}l` : S extends `${infer R}l` ? `${R}m` :
  S extends `${infer R}m` ? `${R}n` : S extends `${infer R}n` ? `${R}o` :
  S extends `${infer R}o` ? `${R}p` : S extends `${infer R}p` ? `${R}q` :
  S extends `${infer R}q` ? `${R}r` : S extends `${infer R}r` ? `${R}s` :
  S extends `${infer R}s` ? `${R}t` : S extends `${infer R}t` ? `${R}u` :
  S extends `${infer R}u` ? `${R}v` : S extends `${infer R}v` ? `${R}w` :
  S extends `${infer R}w` ? `${R}x` : S extends `${infer R}x` ? `${R}y` :
  S extends `${infer R}y` ? `${R}z` : never;

// Increment: right-to-left with carry
//   - Trailing z? Carry: increment rest, reset to 'a'
//   - Non-z? Advance last char via IncrementLast
//   - All z's? Grow length (z→aa, zz→aaa, zzz→aaaa)
type Increment<S extends string> =
  S extends `${infer Rest}z`
    ? Rest extends ""
      ? "aa"
      : `${Increment<Rest>}a`
  : IncrementLast<S>;

type FirstID = "a";

// ============================================================
// TEST: single char
// ============================================================

const _t01: Increment<"a"> = "b";
const _t02: Increment<"b"> = "c";
const _t03: Increment<"m"> = "n";
const _t04: Increment<"y"> = "z";
const _t05: Increment<"z"> = "aa";

// NEGATIVE
// @ts-expect-error — a→b, not c
const _t06: Increment<"a"> = "c";
// @ts-expect-error — z→aa, not ba
const _t07: Increment<"z"> = "ba";

// ============================================================
// TEST: two char — no carry
// ============================================================

const _t10: Increment<"aa"> = "ab";
const _t11: Increment<"ab"> = "ac";
const _t12: Increment<"ay"> = "az";
const _t13: Increment<"ba"> = "bb";
const _t14: Increment<"zy"> = "zz";

// ============================================================
// TEST: two char — carry
// ============================================================

const _t20: Increment<"az"> = "ba";
const _t21: Increment<"bz"> = "ca";
const _t22: Increment<"yz"> = "za";
const _t23: Increment<"zz"> = "aaa";

// NEGATIVE
// @ts-expect-error — az→ba, not aa
const _t24: Increment<"az"> = "aa";

// ============================================================
// TEST: three char
// ============================================================

const _t30: Increment<"aaa"> = "aab";
const _t31: Increment<"aaz"> = "aba";
const _t32: Increment<"abz"> = "aca";
const _t33: Increment<"azz"> = "baa";
const _t34: Increment<"zzz"> = "aaaa";
const _t35: Increment<"zzy"> = "zzz";
const _t36: Increment<"abc"> = "abd";

// ============================================================
// TEST: four char (proves no depth issues)
// ============================================================

const _t40: Increment<"aaaa"> = "aaab";
const _t41: Increment<"zzzz"> = "aaaaa";
const _t42: Increment<"abcd"> = "abce";
const _t43: Increment<"azzz"> = "baaa";

// ============================================================
// Chained increments (simulating counter threading)
// ============================================================

type ID0 = FirstID;                    // "a"
type ID1 = Increment<ID0>;             // "b"
type ID2 = Increment<ID1>;             // "c"
type ID3 = Increment<ID2>;             // "d"
type ID4 = Increment<ID3>;             // "e"

const _c0: ID0 = "a";
const _c1: ID1 = "b";
const _c2: ID2 = "c";
const _c3: ID3 = "d";
const _c4: ID4 = "e";

// Jump ahead: what happens after 26 increments?
type After26 = Increment<Increment<Increment<Increment<Increment<
  Increment<Increment<Increment<Increment<Increment<
  Increment<Increment<Increment<Increment<Increment<
  Increment<Increment<Increment<Increment<Increment<
  Increment<Increment<Increment<Increment<Increment<
  "a"
  >>>>>>>>>>>>>>>>>>>>>>>>>;

const _after26: After26 = "z";
const _after27: Increment<After26> = "aa";

// ============================================================
// Integration: use with Desc/Expr types
// ============================================================

type NodeEntry<Kind extends string, ChildIDs extends string[], Out> = {
  readonly kind: Kind;
  readonly children: ChildIDs;
  readonly out: Out;
};

type Desc<Out, ID extends string, Adj extends Record<string, any>, C extends string> = {
  readonly o: Out; readonly id: ID; readonly adj: Adj; readonly c: C;
};

declare const exprBrand: unique symbol;
interface Expr<O, R extends Desc<O, string, Record<string, any>, string>> {
  readonly [exprBrand]: R;
}

type IdOf<R> = R extends Desc<any, infer ID, any, any> ? ID : never;
type AdjOf<R> = R extends Desc<any, any, infer A, any> ? A : never;
type CtrOf<R> = R extends Desc<any, any, any, infer C> ? C : never;

// BuildCtx using Increment instead of IDChain
interface BuildCtx<C extends string> {
  numLit<V extends number>(value: V):
    [Expr<number, Desc<number, C, Record<C, NodeEntry<"num/literal", [], number>>, Increment<C>>>,
     BuildCtx<Increment<C>>];

  add<
    RA extends Desc<number, string, Record<string, any>, string>,
    RB extends Desc<number, string, Record<string, any>, string>,
  >(
    left: Expr<number, RA>,
    right: Expr<number, RB>,
  ): [Expr<number, Desc<
      number, C,
      AdjOf<RA> & AdjOf<RB> & Record<C, NodeEntry<"num/add", [IdOf<RA>, IdOf<RB>], number>>,
      Increment<C>
    >>, BuildCtx<Increment<C>>];

  mul<
    RA extends Desc<number, string, Record<string, any>, string>,
    RB extends Desc<number, string, Record<string, any>, string>,
  >(
    left: Expr<number, RA>,
    right: Expr<number, RB>,
  ): [Expr<number, Desc<
      number, C,
      AdjOf<RA> & AdjOf<RB> & Record<C, NodeEntry<"num/mul", [IdOf<RA>, IdOf<RB>], number>>,
      Increment<C>
    >>, BuildCtx<Increment<C>>];
}

declare function createCtx(): BuildCtx<FirstID>;

// ============================================================
// Integration test: build (3 + 4) * 5
// ============================================================

const $ = createCtx();
const [lit3, $1] = $.numLit(3);
const [lit4, $2] = $1.numLit(4);
const [sum, $3] = $2.add(lit3, lit4);
const [lit5, $4] = $3.numLit(5);
const [prod, $5] = $4.mul(sum, lit5);

type ProdR = (typeof prod)[typeof exprBrand];
type ProdID = IdOf<ProdR>;
type ProdCtr = CtrOf<ProdR>;

const _prodId: ProdID = "e";
const _prodCtr: ProdCtr = "f";

// @ts-expect-error — prod ID is "e", not "d"
const _prodIdWrong: ProdID = "d";

// Check adj
type ProdAdj = AdjOf<ProdR>;
type AddEntry = ProdAdj["c"];
type AddKids = AddEntry extends NodeEntry<any, infer C, any> ? C : never;
const _addKids: AddKids = ["a", "b"];

type MulEntry = ProdAdj["e"];
type MulKids = MulEntry extends NodeEntry<any, infer C, any> ? C : never;
const _mulKids: MulKids = ["c", "d"];

// ============================================================
// Scale: 20-node chain (same as spike-idchain-test)
// ============================================================

const $$ = createCtx();
const [n0, $$1] = $$.numLit(1);
const [n1, $$2] = $$1.numLit(2);
const [s0, $$3] = $$2.add(n0, n1);
const [n2, $$4] = $$3.numLit(3);
const [s1, $$5] = $$4.add(s0, n2);
const [n3, $$6] = $$5.numLit(4);
const [s2, $$7] = $$6.add(s1, n3);
const [n4, $$8] = $$7.numLit(5);
const [s3, $$9] = $$8.add(s2, n4);
const [n5, $$10] = $$9.numLit(6);
const [s4, $$11] = $$10.add(s3, n5);
const [n6, $$12] = $$11.numLit(7);
const [s5, $$13] = $$12.add(s4, n6);
const [n7, $$14] = $$13.numLit(8);
const [s6, $$15] = $$14.add(s5, n7);
const [n8, $$16] = $$15.numLit(9);
const [s7, $$17] = $$16.add(s6, n8);
const [n9, $$18] = $$17.numLit(10);
const [s8, $$19] = $$18.add(s7, n9);

type ScaleR = (typeof s8)[typeof exprBrand];
type ScaleCtr = CtrOf<ScaleR>;
const _scaleCtr: ScaleCtr = "t"; // 20th ID: a..t

// @ts-expect-error — counter is "t", not "s"
const _scaleCtrWrong: ScaleCtr = "s";

console.log("spike-increment compiled successfully — 18k lines → 8 lines of types");

spike-named-transforms.ts

// ============================================================
// Spike: Named nodes + type-safe transforms
// ============================================================
//
// Proves:
//   1. .as("name") adds a named alias to the adjacency map
//   2. Duplicate names are caught at compile time (intersection conflict)
//   3. Transforms target nodes by name
//   4. Transforms must preserve output type (type-safe replacement)
//   5. Cascading: replacing a named node updates all parents

// ============================================================
// Core types (carried forward from winning spike)
// ============================================================

type NodeEntry<Kind extends string, ChildIDs extends string[], Out> = {
  readonly kind: Kind;
  readonly children: ChildIDs;
  readonly out: Out;
};

type Desc<Out, ID extends string, Adj extends Record<string, any>> = {
  readonly o: Out;
  readonly id: ID;
  readonly adj: Adj;
};

declare const exprBrand: unique symbol;
interface Expr<O, R extends Desc<O, string, Record<string, any>>> {
  readonly [exprBrand]: R;
  readonly kind: string;
}

type OutOf<R> = R extends Desc<infer O, any, any> ? O : never;
type IdOf<R> = R extends Desc<any, infer ID, any> ? ID : never;
type AdjOf<R> = R extends Desc<any, any, infer A> ? A : never;

// Content-addressed IDs
type LitID<V extends string | number | boolean> = `lit(${V})`;
type AddID<L extends string, R extends string> = `add(${L},${R})`;
type MulID<L extends string, R extends string> = `mul(${L},${R})`;
type NegID<A extends string> = `neg(${A})`;
type GtID<L extends string, R extends string> = `gt(${L},${R})`;
type CondID<P extends string, T extends string, E extends string> = `cond(${P},${T},${E})`;

// ============================================================
// Name alias: @name -> content ID mapping in adj
// ============================================================

/** Alias entry: maps a human-readable name to a content-addressed ID */
type NameAlias<Name extends string, TargetID extends string, Out> = {
  readonly kind: "@alias";
  readonly target: TargetID;
  readonly out: Out;
};

type NameKey<N extends string> = `@${N}`;

// ============================================================
// .as() — name a node
// ============================================================

/** Name an expression. Adds Record<@name, NameAlias> to adj.
 *  Duplicate names are caught by intersection conflict. */
function named<
  Name extends string,
  O,
  R extends Desc<O, string, Record<string, any>>,
>(
  name: Name,
  expr: Expr<O, R>,
): Expr<O, Desc<O, IdOf<R>, AdjOf<R> & Record<NameKey<Name>, NameAlias<Name, IdOf<R>, O>>>> {
  return expr as any;
}

// ============================================================
// Builders (same as winning spike)
// ============================================================

function numLit<V extends number>(
  value: V,
): Expr<number, Desc<number, LitID<V>, Record<LitID<V>, NodeEntry<"num/literal", [], number>>>> {
  return { kind: "num/literal", value } as any;
}

function strLit<V extends string>(
  value: V,
): Expr<string, Desc<string, LitID<V>, Record<LitID<V>, NodeEntry<"str/literal", [], string>>>> {
  return { kind: "str/literal", value } as any;
}

function add<
  RA extends Desc<number, string, Record<string, any>>,
  RB extends Desc<number, string, Record<string, any>>,
>(
  left: Expr<number, RA>,
  right: Expr<number, RB>,
): Expr<number, Desc<
  number,
  AddID<IdOf<RA>, IdOf<RB>>,
  AdjOf<RA> & AdjOf<RB> & Record<AddID<IdOf<RA>, IdOf<RB>>, NodeEntry<"num/add", [IdOf<RA>, IdOf<RB>], number>>
>> {
  return { kind: "num/add", left, right } as any;
}

function mul<
  RA extends Desc<number, string, Record<string, any>>,
  RB extends Desc<number, string, Record<string, any>>,
>(
  left: Expr<number, RA>,
  right: Expr<number, RB>,
): Expr<number, Desc<
  number,
  MulID<IdOf<RA>, IdOf<RB>>,
  AdjOf<RA> & AdjOf<RB> & Record<MulID<IdOf<RA>, IdOf<RB>>, NodeEntry<"num/mul", [IdOf<RA>, IdOf<RB>], number>>
>> {
  return { kind: "num/mul", left, right } as any;
}

function neg<RA extends Desc<number, string, Record<string, any>>>(
  operand: Expr<number, RA>,
): Expr<number, Desc<number, NegID<IdOf<RA>>, AdjOf<RA> & Record<NegID<IdOf<RA>>, NodeEntry<"num/neg", [IdOf<RA>], number>>>> {
  return { kind: "num/neg", operand } as any;
}

function gt<
  RA extends Desc<number, string, Record<string, any>>,
  RB extends Desc<number, string, Record<string, any>>,
>(
  left: Expr<number, RA>,
  right: Expr<number, RB>,
): Expr<boolean, Desc<
  boolean,
  GtID<IdOf<RA>, IdOf<RB>>,
  AdjOf<RA> & AdjOf<RB> & Record<GtID<IdOf<RA>, IdOf<RB>>, NodeEntry<"num/gt", [IdOf<RA>, IdOf<RB>], boolean>>
>> {
  return { kind: "num/gt", left, right } as any;
}

function cond<
  T,
  RP extends Desc<boolean, string, Record<string, any>>,
  RT extends Desc<T, string, Record<string, any>>,
  RE extends Desc<NoInfer<T>, string, Record<string, any>>,
>(
  pred: Expr<boolean, RP>,
  then_: Expr<T, RT>,
  else_: Expr<NoInfer<T>, RE>,
): Expr<T, Desc<
  T,
  CondID<IdOf<RP>, IdOf<RT>, IdOf<RE>>,
  AdjOf<RP> & AdjOf<RT> & AdjOf<RE> & Record<CondID<IdOf<RP>, IdOf<RT>, IdOf<RE>>, NodeEntry<"core/cond", [IdOf<RP>, IdOf<RT>, IdOf<RE>], T>>
>> {
  return { kind: "core/cond", pred, then: then_, else: else_ } as any;
}

// ============================================================
// Test 1: Basic naming
// ============================================================

const base = numLit(10);
const tax = named("tax-rate", numLit(21));
const total = named("total", mul(base, tax));

// Tax and total have their names in the adj map

// ============================================================
// Test 2: Duplicate name detection
// ============================================================

// Duplicate name detection: intersection doesn't error by itself,
// but we can detect it with a type-level check:
type HasDuplicateNames<Adj1, Adj2> = {
  [K in keyof Adj1 & keyof Adj2]: K extends `@${string}`
    ? Adj1[K] extends Adj2[K] ? never : K  // same key, different value = duplicate
    : never
}[keyof Adj1 & keyof Adj2];

// Builder that rejects duplicate names
function safeAdd<
  RA extends Desc<number, string, Record<string, any>>,
  RB extends Desc<number, string, Record<string, any>>,
>(
  left: Expr<number, RA>,
  right: HasDuplicateNames<AdjOf<RA>, AdjOf<RB>> extends never
    ? Expr<number, RB>
    : { __error: `Duplicate name: ${HasDuplicateNames<AdjOf<RA>, AdjOf<RB>> & string}` },
): Expr<number, Desc<
  number,
  AddID<IdOf<RA>, IdOf<RB>>,
  AdjOf<RA> & AdjOf<RB> & Record<AddID<IdOf<RA>, IdOf<RB>>, NodeEntry<"num/add", [IdOf<RA>, IdOf<RB>], number>>
>> {
  return { kind: "num/add", left, right } as any;
}

const a = named("my-val", numLit(1));
const b = named("my-val", numLit(2));
// @ts-expect-error: duplicate name detected
const bad_dup = safeAdd(a, b);

// Non-duplicate names work fine
const c = named("val-a", numLit(1));
const d = named("val-b", numLit(2));
const ok_dup = safeAdd(c, d);  // no error

// ============================================================
// Test 3: Type-safe named replacement
// ============================================================

/** Look up the output type of a named node */
type NamedOutput<R, Name extends string> =
  R extends Desc<any, any, infer Adj>
    ? NameKey<Name> extends keyof Adj
      ? Adj[NameKey<Name>] extends NameAlias<any, any, infer O> ? O : never
      : never
    : never;

/** Check that a name exists in the program */
type HasName<R, Name extends string> =
  R extends Desc<any, any, infer Adj>
    ? NameKey<Name> extends keyof Adj ? true : false
    : false;

/**
 * Replace a named node. The replacement must produce the same output type.
 * At the type level, we update the adj map.
 */
function replaceNamed<
  Name extends string,
  O,
  RProgram extends Desc<O, string, Record<string, any>>,
  ReplacementO extends NamedOutput<RProgram, Name>,
  RReplacement extends Desc<ReplacementO, string, Record<string, any>>,
>(
  name: Name,
  program: Expr<O, RProgram>,
  replacement: Expr<ReplacementO, RReplacement>,
): Expr<O, Desc<O, IdOf<RProgram>, AdjOf<RProgram> & AdjOf<RReplacement>>> {
  // Runtime: walk adj, find name's target ID, replace all references
  return program as any;
}

// Build a program with named nodes
const price = named("price", numLit(100));
const rate = named("rate", numLit(20));
const result = named("result", add(price, rate));

// Replace "rate" with a different number — valid (number → number)
const modified = replaceNamed("rate", result, numLit(25));

// @ts-expect-error: can't replace "rate" (number) with a string
const bad_type = replaceNamed("rate", result, strLit("oops"));

// ============================================================
// Test 4: Targeting non-existent names
// ============================================================

// @ts-expect-error: "nonexistent" is not a named node in this program
const bad_name = replaceNamed("nonexistent", result, numLit(0));

// ============================================================
// Test 5: Real-world-ish example — wrapping with instrumentation
// ============================================================

// Simulate: wrap a node with logging (add a neg as a stand-in for "instrument")
// In real MVFM this would be wrapping with console.log or timing

const computation = named("expensive",
  mul(add(numLit(1), numLit(2)), add(numLit(3), numLit(4)))
);

const pred = gt(numLit(0), numLit(1));
const program = named("output", cond(pred, computation, numLit(0)));

// "Instrument" the expensive computation by wrapping it
// (using neg as a stand-in for a logging wrapper)
const instrumented = replaceNamed(
  "expensive",
  program,
  neg(computation),  // same output type (number), but "wrapped"
);

// ============================================================
// Test 6: Multiple named nodes in one program
// ============================================================

const step1 = named("step1", numLit(10));
const step2 = named("step2", mul(step1, numLit(2)));
const step3 = named("step3", add(step2, numLit(5)));

// Replace step2, keeping step1 and step3
const patched = replaceNamed("step2", step3, numLit(99));

// ============================================================
// Queries work with names
// ============================================================

type ROf<E> = E extends Expr<any, infer R> ? R : never;

type CollectKinds<R> =
  R extends Desc<any, any, infer Adj>
    ? { [Key in keyof Adj]: Adj[Key] extends NodeEntry<infer K, any, any> ? K : never }[keyof Adj]
    : never;

type CollectNames<R> =
  R extends Desc<any, any, infer Adj>
    ? { [Key in keyof Adj]: Key extends `@${infer Name}` ? Name : never }[keyof Adj]
    : never;

type ProgramR = ROf<typeof program>;
type ProgramKinds = CollectKinds<ProgramR>;  // "num/literal" | "num/add" | "num/mul" | "num/gt" | "core/cond"
type ProgramNames = CollectNames<ProgramR>;  // "expensive" | "output"

type Step3R = ROf<typeof step3>;
type Step3Names = CollectNames<Step3R>;  // "step1" | "step2" | "step3"

console.log("Named transforms spike compiled successfully");

spike-predicates.ts

// ============================================================
// Spike: Structured predicates — type-level computable, no callbacks
// ============================================================

// ============================================================
// Core types (from previous spikes)
// ============================================================

type NodeEntry<Kind extends string, ChildIDs extends string[], Out> = {
  readonly kind: Kind;
  readonly children: ChildIDs;
  readonly out: Out;
};

// ============================================================
// Predicate types — tagged unions
// ============================================================

interface KindPred<K extends string> { readonly tag: "kind"; readonly kind: K }
interface KindGlobPred<Prefix extends string> {
  readonly tag: "kindGlob";
  readonly prefix: Prefix;
}
interface OutputPred<O> { readonly tag: "output"; readonly _o?: O }
interface LeafPred { readonly tag: "leaf" }
interface ChildCountPred<N extends number> {
  readonly tag: "childCount";
  readonly count: N;
}
interface NotPred<P> { readonly tag: "not"; readonly inner: P }
interface AndPred<A, B> { readonly tag: "and"; readonly left: A; readonly right: B }
interface OrPred<A, B> { readonly tag: "or"; readonly left: A; readonly right: B }

// ============================================================
// Type-level predicate evaluation
// ============================================================

type EvalPred<P, Entry> =
  P extends KindPred<infer K>
    ? Entry extends NodeEntry<K, any, any> ? true : false
  : P extends KindGlobPred<infer Prefix>
    ? Entry extends NodeEntry<`${Prefix}${string}`, any, any> ? true : false
  : P extends OutputPred<infer O>
    ? Entry extends NodeEntry<any, any, infer AO>
      ? AO extends O ? true : false
      : false
  : P extends LeafPred
    ? Entry extends NodeEntry<any, infer C, any>
      ? C extends [] ? true : false
      : false
  : P extends ChildCountPred<infer N>
    ? Entry extends NodeEntry<any, infer C, any>
      ? C extends { length: N } ? true : false
      : false
  : P extends NotPred<infer Inner>
    ? EvalPred<Inner, Entry> extends true ? false : true
  : P extends AndPred<infer A, infer B>
    ? EvalPred<A, Entry> extends true
      ? EvalPred<B, Entry> extends true ? true : false
      : false
  : P extends OrPred<infer A, infer B>
    ? EvalPred<A, Entry> extends true ? true
      : EvalPred<B, Entry> extends true ? true : false
  : never;

// Type-level select: filter adjacency map by predicate
type SelectKeys<Adj, P> =
  keyof { [K in keyof Adj as EvalPred<P, Adj[K]> extends true ? K : never]: 1 };

// ============================================================
// Test adjacency map
// ============================================================

type TA = {
  a: NodeEntry<"num/literal", [], number>;
  b: NodeEntry<"num/literal", [], number>;
  c: NodeEntry<"num/add", ["a", "b"], number>;
  d: NodeEntry<"str/literal", [], string>;
  e: NodeEntry<"str/concat", ["d", "d"], string>;
  f: NodeEntry<"num/mul", ["c", "c"], number>;
  g: NodeEntry<"core/cond", ["a", "c", "f"], number>;
};

// ============================================================
// TYPE TESTS: byKind
// ============================================================

// Positive
const _k1: EvalPred<KindPred<"num/add">, TA["c"]> = true;
// Negative
const _k2: EvalPred<KindPred<"num/add">, TA["a"]> = false;
const _k3: EvalPred<KindPred<"num/add">, TA["d"]> = false;
// Select
const _k4: SelectKeys<TA, KindPred<"num/add">> = "c";
// @ts-expect-error — a is num/literal, not num/add
const _k5: SelectKeys<TA, KindPred<"num/add">> = "a";

// ============================================================
// TYPE TESTS: byKindGlob (template literal matching!)
// ============================================================

// Positive
const _g1: EvalPred<KindGlobPred<"num/">, TA["a"]> = true;
const _g2: EvalPred<KindGlobPred<"num/">, TA["c"]> = true;
const _g3: EvalPred<KindGlobPred<"num/">, TA["f"]> = true;
// Negative
const _g4: EvalPred<KindGlobPred<"num/">, TA["d"]> = false;
const _g5: EvalPred<KindGlobPred<"num/">, TA["g"]> = false;
// Select
const _g6: SelectKeys<TA, KindGlobPred<"num/">> = "a";
const _g7: SelectKeys<TA, KindGlobPred<"num/">> = "b";
const _g8: SelectKeys<TA, KindGlobPred<"num/">> = "c";
const _g9: SelectKeys<TA, KindGlobPred<"num/">> = "f";
// @ts-expect-error — d is str/literal
const _g10: SelectKeys<TA, KindGlobPred<"num/">> = "d";
// @ts-expect-error — e is str/concat
const _g11: SelectKeys<TA, KindGlobPred<"num/">> = "e";
// @ts-expect-error — g is core/cond
const _g12: SelectKeys<TA, KindGlobPred<"num/">> = "g";

// ============================================================
// TYPE TESTS: byOutput
// ============================================================

const _o1: EvalPred<OutputPred<number>, TA["a"]> = true;
const _o2: EvalPred<OutputPred<number>, TA["g"]> = true; // core/cond→number
const _o3: EvalPred<OutputPred<number>, TA["d"]> = false; // string
const _o4: EvalPred<OutputPred<string>, TA["d"]> = true;
const _o5: EvalPred<OutputPred<string>, TA["a"]> = false; // number
// Select number-outputting: a,b,c,f,g
const _o6: SelectKeys<TA, OutputPred<number>> = "a";
const _o7: SelectKeys<TA, OutputPred<number>> = "g";
// @ts-expect-error — d outputs string
const _o8: SelectKeys<TA, OutputPred<number>> = "d";
// @ts-expect-error — e outputs string
const _o9: SelectKeys<TA, OutputPred<number>> = "e";

// ============================================================
// TYPE TESTS: isLeaf
// ============================================================

const _l1: EvalPred<LeafPred, TA["a"]> = true;
const _l2: EvalPred<LeafPred, TA["d"]> = true;
const _l3: EvalPred<LeafPred, TA["c"]> = false;
const _l4: SelectKeys<TA, LeafPred> = "a";
const _l5: SelectKeys<TA, LeafPred> = "b";
const _l6: SelectKeys<TA, LeafPred> = "d";
// @ts-expect-error — c has children
const _l7: SelectKeys<TA, LeafPred> = "c";

// ============================================================
// TYPE TESTS: hasChildCount
// ============================================================

const _cc1: EvalPred<ChildCountPred<2>, TA["c"]> = true;
const _cc2: EvalPred<ChildCountPred<2>, TA["a"]> = false;
const _cc3: EvalPred<ChildCountPred<3>, TA["g"]> = true;
// @ts-expect-error — g has 3 children, not 2
const _cc4: EvalPred<ChildCountPred<2>, TA["g"]> = true;
const _cc5: SelectKeys<TA, ChildCountPred<2>> = "c";
const _cc6: SelectKeys<TA, ChildCountPred<2>> = "e";
const _cc7: SelectKeys<TA, ChildCountPred<2>> = "f";
// @ts-expect-error — g has 3 children
const _cc8: SelectKeys<TA, ChildCountPred<2>> = "g";

// ============================================================
// TYPE TESTS: not
// ============================================================

const _n1: EvalPred<NotPred<LeafPred>, TA["c"]> = true;
const _n2: EvalPred<NotPred<LeafPred>, TA["a"]> = false;
const _n3: SelectKeys<TA, NotPred<LeafPred>> = "c";
const _n4: SelectKeys<TA, NotPred<LeafPred>> = "g";
// @ts-expect-error — a IS a leaf
const _n5: SelectKeys<TA, NotPred<LeafPred>> = "a";

// ============================================================
// TYPE TESTS: and
// ============================================================

// num/* AND leaf = num literals only
type NumLeaf = AndPred<KindGlobPred<"num/">, LeafPred>;
const _a1: EvalPred<NumLeaf, TA["a"]> = true;  // num/literal, leaf
const _a2: EvalPred<NumLeaf, TA["c"]> = false;  // num/add, not leaf
const _a3: EvalPred<NumLeaf, TA["d"]> = false;  // str/literal, leaf but wrong prefix
const _a4: SelectKeys<TA, NumLeaf> = "a";
const _a5: SelectKeys<TA, NumLeaf> = "b";
// @ts-expect-error — c is not leaf
const _a6: SelectKeys<TA, NumLeaf> = "c";
// @ts-expect-error — d is str/
const _a7: SelectKeys<TA, NumLeaf> = "d";

// ============================================================
// TYPE TESTS: or
// ============================================================

type AddOrConcat = OrPred<KindPred<"num/add">, KindPred<"str/concat">>;
const _r1: EvalPred<AddOrConcat, TA["c"]> = true;
const _r2: EvalPred<AddOrConcat, TA["e"]> = true;
const _r3: EvalPred<AddOrConcat, TA["a"]> = false;
const _r4: SelectKeys<TA, AddOrConcat> = "c";
const _r5: SelectKeys<TA, AddOrConcat> = "e";
// @ts-expect-error — a is literal
const _r6: SelectKeys<TA, AddOrConcat> = "a";

// ============================================================
// TYPE TESTS: deep combinator — not(or(isLeaf, childCount(3))) = binary
// ============================================================

type BinaryOnly = NotPred<OrPred<LeafPred, ChildCountPred<3>>>;
const _b1: EvalPred<BinaryOnly, TA["c"]> = true;   // 2 kids
const _b2: EvalPred<BinaryOnly, TA["e"]> = true;   // 2 kids
const _b3: EvalPred<BinaryOnly, TA["f"]> = true;   // 2 kids
const _b4: EvalPred<BinaryOnly, TA["a"]> = false;  // leaf
const _b5: EvalPred<BinaryOnly, TA["g"]> = false;  // 3 kids
const _b6: SelectKeys<TA, BinaryOnly> = "c";
const _b7: SelectKeys<TA, BinaryOnly> = "e";
const _b8: SelectKeys<TA, BinaryOnly> = "f";
// @ts-expect-error — a is leaf
const _b9: SelectKeys<TA, BinaryOnly> = "a";
// @ts-expect-error — g is ternary
const _b10: SelectKeys<TA, BinaryOnly> = "g";

// ============================================================
// Runtime predicate constructors
// ============================================================

type RuntimePred = (e: { kind: string; children: string[]; out: unknown }) => boolean;

type RE = { kind: string; children: string[]; out: unknown };

function byKind<K extends string>(k: K): KindPred<K> & { eval: RuntimePred } {
  return { tag: "kind", kind: k, eval: (e: RE) => e.kind === k };
}

function byKindGlob<P extends string>(prefix: P): KindGlobPred<P> & { eval: RuntimePred } {
  return { tag: "kindGlob", prefix, eval: (e: RE) => e.kind.startsWith(prefix) };
}

function byOutput<O>(check: (x: unknown) => x is O): OutputPred<O> & { eval: RuntimePred } {
  return { tag: "output", eval: (e: RE) => check(e.out) } as any;
}

function isLeaf(): LeafPred & { eval: RuntimePred } {
  return { tag: "leaf", eval: (e: RE) => e.children.length === 0 };
}

function hasChildCount<N extends number>(n: N): ChildCountPred<N> & { eval: RuntimePred } {
  return { tag: "childCount", count: n, eval: (e: RE) => e.children.length === n };
}

function not<P extends { eval: RuntimePred }>(p: P): NotPred<P> & { eval: RuntimePred } {
  return { tag: "not", inner: p, eval: (e) => !p.eval(e) };
}

function and<A extends { eval: RuntimePred }, B extends { eval: RuntimePred }>(
  a: A, b: B,
): AndPred<A, B> & { eval: RuntimePred } {
  return { tag: "and", left: a, right: b, eval: (e) => a.eval(e) && b.eval(e) };
}

function or<A extends { eval: RuntimePred }, B extends { eval: RuntimePred }>(
  a: A, b: B,
): OrPred<A, B> & { eval: RuntimePred } {
  return { tag: "or", left: a, right: b, eval: (e) => a.eval(e) || b.eval(e) };
}

// ============================================================
// Runtime selectWhere
// ============================================================

function selectWhere(
  adj: Record<string, { kind: string; children: string[]; out: unknown }>,
  pred: { eval: RuntimePred },
): Set<string> {
  const result = new Set<string>();
  for (const [id, entry] of Object.entries(adj)) {
    if (pred.eval(entry)) result.add(id);
  }
  return result;
}

// ============================================================
// Runtime test data
// ============================================================

const adj = {
  a: { kind: "num/literal", children: [] as string[], out: 3 },
  b: { kind: "num/literal", children: [] as string[], out: 4 },
  c: { kind: "num/add", children: ["a", "b"], out: 7 },
  d: { kind: "str/literal", children: [] as string[], out: "hello" },
  e: { kind: "str/concat", children: ["d", "d"], out: "hellohello" },
  f: { kind: "num/mul", children: ["c", "c"], out: 49 },
  g: { kind: "core/cond", children: ["a", "c", "f"], out: 7 },
};

let passed = 0;
let failed = 0;
function assert(cond: boolean, msg: string) {
  if (cond) { passed++; console.log(`  ✓ ${msg}`); }
  else { failed++; console.log(`  ✗ ${msg}`); }
}
function sameSet(a: Set<string>, b: Set<string>): boolean {
  if (a.size !== b.size) return false;
  for (const x of a) if (!b.has(x)) return false;
  return true;
}

// ============================================================
// Runtime tests
// ============================================================

console.log("Test 1: byKind");
const p1 = byKind("num/add");
assert(p1.eval(adj.c), "matches num/add");
assert(!p1.eval(adj.a), "rejects num/literal");
assert(sameSet(selectWhere(adj, p1), new Set(["c"])), "selects {c}");

console.log("Test 2: byKindGlob");
const p2 = byKindGlob("num/");
assert(p2.eval(adj.a), "matches num/literal");
assert(p2.eval(adj.f), "matches num/mul");
assert(!p2.eval(adj.d), "rejects str/literal");
assert(!p2.eval(adj.g), "rejects core/cond");
assert(sameSet(selectWhere(adj, p2), new Set(["a", "b", "c", "f"])), "selects {a,b,c,f}");

console.log("Test 3: byOutput");
const isNum = (x: unknown): x is number => typeof x === "number";
const p3 = byOutput<number>(isNum);
assert(p3.eval(adj.a), "matches number output");
assert(p3.eval(adj.g), "matches core/cond→number");
assert(!p3.eval(adj.d), "rejects string output");
assert(sameSet(selectWhere(adj, p3), new Set(["a", "b", "c", "f", "g"])), "selects {a,b,c,f,g}");

console.log("Test 4: isLeaf");
const p4 = isLeaf();
assert(p4.eval(adj.a), "matches leaf");
assert(!p4.eval(adj.c), "rejects non-leaf");
assert(sameSet(selectWhere(adj, p4), new Set(["a", "b", "d"])), "selects {a,b,d}");

console.log("Test 5: hasChildCount");
const p5a = hasChildCount(2);
assert(p5a.eval(adj.c), "matches binary");
assert(!p5a.eval(adj.a), "rejects leaf");
assert(!p5a.eval(adj.g), "rejects ternary");
assert(sameSet(selectWhere(adj, p5a), new Set(["c", "e", "f"])), "selects {c,e,f}");
const p5b = hasChildCount(3);
assert(p5b.eval(adj.g), "matches ternary");
assert(sameSet(selectWhere(adj, p5b), new Set(["g"])), "selects {g}");

console.log("Test 6: not");
const p6 = not(isLeaf());
assert(p6.eval(adj.c), "non-leaf matches");
assert(!p6.eval(adj.a), "leaf rejected");
assert(sameSet(selectWhere(adj, p6), new Set(["c", "e", "f", "g"])), "selects {c,e,f,g}");

console.log("Test 7: and — num/* AND leaf");
const p7 = and(byKindGlob("num/"), isLeaf());
assert(p7.eval(adj.a), "num/literal leaf matches");
assert(!p7.eval(adj.c), "num/add not leaf rejects");
assert(!p7.eval(adj.d), "str/literal not num/ rejects");
assert(sameSet(selectWhere(adj, p7), new Set(["a", "b"])), "selects {a,b}");

console.log("Test 8: or — num/add OR str/concat");
const p8 = or(byKind("num/add"), byKind("str/concat"));
assert(p8.eval(adj.c), "num/add matches");
assert(p8.eval(adj.e), "str/concat matches");
assert(!p8.eval(adj.a), "num/literal rejects");
assert(sameSet(selectWhere(adj, p8), new Set(["c", "e"])), "selects {c,e}");

console.log("Test 9: not(or(leaf, childCount(3))) = binary nodes");
const p9 = not(or(isLeaf(), hasChildCount(3)));
assert(p9.eval(adj.c), "binary matches");
assert(!p9.eval(adj.a), "leaf rejects");
assert(!p9.eval(adj.g), "ternary rejects");
assert(sameSet(selectWhere(adj, p9), new Set(["c", "e", "f"])), "selects {c,e,f}");

console.log("Test 10: and(num/*, not(leaf)) = num operations");
const p10 = and(byKindGlob("num/"), not(isLeaf()));
assert(p10.eval(adj.c), "num/add matches");
assert(p10.eval(adj.f), "num/mul matches");
assert(!p10.eval(adj.a), "num/literal rejects (leaf)");
assert(!p10.eval(adj.e), "str/concat rejects (not num/)");
assert(sameSet(selectWhere(adj, p10), new Set(["c", "f"])), "selects {c,f}");

console.log(`\nResults: ${passed} passed, ${failed} failed`);
if (failed > 0) process.exit(1);
console.log("\nPredicate spike compiled and ran successfully!");

spike-runtime.ts

// ============================================================
// Spike: Real runtime backing the type-level DAG encoding
// ============================================================
//
// Proves: types and runtime agree. No {} as any (except branded phantom).

import { IDChain, FirstID } from "./spike-idchain";

// ============================================================
// Core types (same as spike-idchain-test)
// ============================================================

type NodeEntry<Kind extends string, ChildIDs extends string[], Out> = {
  readonly kind: Kind;
  readonly children: ChildIDs;
  readonly out: Out;
};

type NextID<Current extends keyof IDChain> = IDChain[Current];

type Desc<Out, ID extends string, Adj extends Record<string, any>, C extends string> = {
  readonly o: Out;
  readonly id: ID;
  readonly adj: Adj;
  readonly c: C;
};

declare const exprBrand: unique symbol;
interface Expr<O, R extends Desc<O, string, Record<string, any>, string>> {
  readonly [exprBrand]: R;
  readonly kind: string;
  // Real runtime fields
  readonly __id: string;
  readonly __adj: Record<string, { kind: string; children?: string[]; target?: string; out?: unknown }>;
  readonly __counter: string;
}

type OutOf<R> = R extends Desc<infer O, any, any, any> ? O : never;
type IdOf<R> = R extends Desc<any, infer ID, any, any> ? ID : never;
type AdjOf<R> = R extends Desc<any, any, infer A, any> ? A : never;
type CtrOf<R> = R extends Desc<any, any, any, infer C> ? C : never;

type NameAlias<Name extends string, TargetID extends string, Out> = {
  readonly kind: "@alias";
  readonly target: TargetID;
  readonly out: Out;
};
type NameKey<N extends string> = `@${N}`;

// ============================================================
// ID chain at runtime: same sequence as the type
// ============================================================

const ALPHA = "abcdefghijklmnopqrstuvwxyz";

function nextIdRuntime(current: string): string {
  // Increment: a→b, z→aa, az→ba, zz→aaa, etc.
  const chars = current.split("");
  let carry = true;
  for (let i = chars.length - 1; i >= 0 && carry; i--) {
    const idx = ALPHA.indexOf(chars[i]);
    if (idx === 25) {
      chars[i] = "a";
      carry = true;
    } else {
      chars[i] = ALPHA[idx + 1];
      carry = false;
    }
  }
  if (carry) return "a" + chars.join("");
  return chars.join("");
}

// Verify runtime matches type-level
function assertEq<T>(actual: T, expected: T, msg: string) {
  if (actual !== expected) {
    throw new Error(`${msg}: expected ${JSON.stringify(expected)}, got ${JSON.stringify(actual)}`);
  }
}

assertEq(nextIdRuntime("a"), "b", "a→b");
assertEq(nextIdRuntime("z"), "aa", "z→aa");
assertEq(nextIdRuntime("az"), "ba", "az→ba");
assertEq(nextIdRuntime("zz"), "aaa", "zz→aaa");

// ============================================================
// Real BuildCtx
// ============================================================

function makeExpr(
  kind: string,
  id: string,
  adj: Record<string, any>,
  counter: string,
): any {
  return {
    kind,
    __id: id,
    __adj: adj,
    __counter: counter,
    // exprBrand is phantom — no runtime representation needed
  };
}

interface BuildCtx<C extends string> {
  numLit<V extends number>(value: V):
    C extends keyof IDChain
      ? [Expr<number, Desc<number, C, Record<C, NodeEntry<"num/literal", [], number>>, NextID<C> & string>>, BuildCtx<NextID<C> & string>]
      : never;

  strLit<V extends string>(value: V):
    C extends keyof IDChain
      ? [Expr<string, Desc<string, C, Record<C, NodeEntry<"str/literal", [], string>>, NextID<C> & string>>, BuildCtx<NextID<C> & string>]
      : never;

  add<
    RA extends Desc<number, string, Record<string, any>, string>,
    RB extends Desc<number, string, Record<string, any>, string>,
  >(
    left: Expr<number, RA>,
    right: Expr<number, RB>,
  ): C extends keyof IDChain
    ? [Expr<number, Desc<
        number,
        C,
        AdjOf<RA> & AdjOf<RB> & Record<C, NodeEntry<"num/add", [IdOf<RA>, IdOf<RB>], number>>,
        NextID<C> & string
      >>, BuildCtx<NextID<C> & string>]
    : never;

  mul<
    RA extends Desc<number, string, Record<string, any>, string>,
    RB extends Desc<number, string, Record<string, any>, string>,
  >(
    left: Expr<number, RA>,
    right: Expr<number, RB>,
  ): C extends keyof IDChain
    ? [Expr<number, Desc<
        number,
        C,
        AdjOf<RA> & AdjOf<RB> & Record<C, NodeEntry<"num/mul", [IdOf<RA>, IdOf<RB>], number>>,
        NextID<C> & string
      >>, BuildCtx<NextID<C> & string>]
    : never;

  neg<
    RA extends Desc<number, string, Record<string, any>, string>,
  >(
    operand: Expr<number, RA>,
  ): C extends keyof IDChain
    ? [Expr<number, Desc<
        number,
        C,
        AdjOf<RA> & Record<C, NodeEntry<"num/neg", [IdOf<RA>], number>>,
        NextID<C> & string
      >>, BuildCtx<NextID<C> & string>]
    : never;

  named<
    Name extends string,
    O,
    R extends Desc<O, string, Record<string, any>, string>,
  >(
    name: Name,
    expr: Expr<O, R>,
  ): [Expr<O, Desc<
    O,
    IdOf<R>,
    AdjOf<R> & Record<NameKey<Name>, NameAlias<Name, IdOf<R>, O>>,
    CtrOf<R>
  >>, BuildCtx<C>];  // named doesn't consume an ID
}

function createCtx<C extends string>(counter: C): BuildCtx<C> {
  const ctx: BuildCtx<any> = {
    numLit(value: number) {
      const id = counter;
      const next = nextIdRuntime(counter);
      const adj = { [id]: { kind: "num/literal", children: [], out: value } };
      const expr = makeExpr("num/literal", id, adj, next);
      return [expr, createCtx(next)] as any;
    },

    strLit(value: string) {
      const id = counter;
      const next = nextIdRuntime(counter);
      const adj = { [id]: { kind: "str/literal", children: [], out: value } };
      const expr = makeExpr("str/literal", id, adj, next);
      return [expr, createCtx(next)] as any;
    },

    add(left: any, right: any) {
      const id = counter;
      const next = nextIdRuntime(counter);
      const adj = {
        ...left.__adj,
        ...right.__adj,
        [id]: { kind: "num/add", children: [left.__id, right.__id] },
      };
      const expr = makeExpr("num/add", id, adj, next);
      return [expr, createCtx(next)] as any;
    },

    mul(left: any, right: any) {
      const id = counter;
      const next = nextIdRuntime(counter);
      const adj = {
        ...left.__adj,
        ...right.__adj,
        [id]: { kind: "num/mul", children: [left.__id, right.__id] },
      };
      const expr = makeExpr("num/mul", id, adj, next);
      return [expr, createCtx(next)] as any;
    },

    neg(operand: any) {
      const id = counter;
      const next = nextIdRuntime(counter);
      const adj = {
        ...operand.__adj,
        [id]: { kind: "num/neg", children: [operand.__id] },
      };
      const expr = makeExpr("num/neg", id, adj, next);
      return [expr, createCtx(next)] as any;
    },

    named(name: string, expr: any) {
      const aliasKey = `@${name}`;
      const adj = {
        ...expr.__adj,
        [aliasKey]: { kind: "@alias", target: expr.__id },
      };
      const newExpr = makeExpr(expr.kind, expr.__id, adj, expr.__counter);
      // named doesn't consume an ID, so return same ctx
      return [newExpr, ctx] as any;
    },
  };
  return ctx;
}

function freshCtx(): BuildCtx<FirstID> {
  return createCtx("a" as FirstID);
}

// ============================================================
// DagView: real runtime implementation
// ============================================================

interface DagView<Adj extends Record<string, any>> {
  get<ID extends string & keyof Adj>(id: ID): Adj[ID];
  nodeIds(): string[];
  children(id: string): any[];
  parents(childId: string): string[];
  resolve<Name extends string>(
    name: Name
  ): NameKey<Name> extends keyof Adj
    ? Adj[NameKey<Name>] extends NameAlias<any, infer T, any> ? T : never
    : never;
}

function createDagView(adj: Record<string, any>): DagView<any> {
  // Build reverse index for parents
  const parentIndex: Record<string, string[]> = {};
  for (const [id, entry] of Object.entries(adj)) {
    if (id.startsWith("@")) continue;
    for (const childId of (entry as any).children || []) {
      if (!parentIndex[childId]) parentIndex[childId] = [];
      parentIndex[childId].push(id);
    }
  }

  return {
    get(id: string) {
      return adj[id];
    },
    nodeIds() {
      return Object.keys(adj).filter(k => !k.startsWith("@"));
    },
    children(id: string) {
      const entry = adj[id];
      if (!entry || !entry.children) return [];
      return entry.children.map((cid: string) => adj[cid]);
    },
    parents(childId: string) {
      return parentIndex[childId] || [];
    },
    resolve(name: string) {
      const alias = adj[`@${name}`];
      if (!alias) throw new Error(`Name not found: ${name}`);
      return alias.target;
    },
  } as any;
}

// ============================================================
// DAGQL runtime operations
// ============================================================

function selectByKind(expr: any, kind: string): Record<string, any> {
  const result: Record<string, any> = {};
  for (const [id, entry] of Object.entries(expr.__adj)) {
    if ((entry as any).kind === kind) {
      result[id] = entry;
    }
  }
  return result;
}

function updateByKind(expr: any, fromKind: string, toKind: string): any {
  const newAdj: Record<string, any> = {};
  for (const [id, entry] of Object.entries(expr.__adj)) {
    if ((entry as any).kind === fromKind) {
      newAdj[id] = { ...entry as any, kind: toKind };
    } else {
      newAdj[id] = entry;
    }
  }
  return makeExpr(expr.kind, expr.__id, newAdj, expr.__counter);
}

function replaceNode(expr: any, targetId: string, newEntry: any): any {
  const newAdj = { ...expr.__adj, [targetId]: newEntry };
  return makeExpr(expr.kind, expr.__id, newAdj, expr.__counter);
}

function replaceByName(expr: any, name: string, newExpr: any): any {
  const alias = expr.__adj[`@${name}`];
  if (!alias) throw new Error(`Name not found: ${name}`);
  const targetId = alias.target;

  // Merge new expr's adj into existing, overwrite the target entry
  const newAdj: Record<string, any> = { ...expr.__adj };
  // Add all entries from replacement
  for (const [id, entry] of Object.entries(newExpr.__adj)) {
    newAdj[id] = entry;
  }
  // Point the target ID to the replacement's root entry
  newAdj[targetId] = newExpr.__adj[newExpr.__id];
  // Update alias to still point to same ID
  // (it already does — the ID is stable)

  return makeExpr(expr.kind, expr.__id, newAdj, expr.__counter);
}

// ============================================================
// Test 1: Build and inspect a program
// ============================================================

console.log("=== Test 1: Build mul(add(3, 4), 5) ===");

const $ = freshCtx();
const [lit3, $1] = $.numLit(3);
const [lit4, $2] = $1.numLit(4);
const [sum, $3] = $2.add(lit3, lit4);
const [lit5, $4] = $3.numLit(5);
const [prog, $5] = $4.mul(sum, lit5);

// Verify runtime IDs match type-level
assertEq(lit3.__id, "a", "lit3 id");
assertEq(lit4.__id, "b", "lit4 id");
assertEq(sum.__id, "c", "sum id");
assertEq(lit5.__id, "d", "lit5 id");
assertEq(prog.__id, "e", "prog id");

// Type-level agrees
type ProgR = (typeof prog)[typeof exprBrand];
const _progId: IdOf<ProgR> = "e";

// Verify adj map structure
assertEq(Object.keys(prog.__adj).length, 5, "adj size");
assertEq(prog.__adj["a"].kind, "num/literal", "a is literal");
assertEq(prog.__adj["a"].out, 3, "a value is 3");
assertEq(prog.__adj["b"].kind, "num/literal", "b is literal");
assertEq(prog.__adj["c"].kind, "num/add", "c is add");
assertEq(prog.__adj["c"].children![0], "a", "add left child");
assertEq(prog.__adj["c"].children![1], "b", "add right child");
assertEq(prog.__adj["e"].kind, "num/mul", "e is mul");
assertEq(prog.__adj["e"].children![0], "c", "mul left child");
assertEq(prog.__adj["e"].children![1], "d", "mul right child");

console.log("  adj:", JSON.stringify(prog.__adj, null, 2));
console.log("  PASS");

// ============================================================
// Test 2: DagView
// ============================================================

console.log("\n=== Test 2: DagView ===");

const dag = createDagView(prog.__adj);

assertEq(dag.get("a").kind, "num/literal", "dag.get a");
assertEq(dag.get("c").kind, "num/add", "dag.get c");
assertEq(dag.nodeIds().length, 5, "dag nodeIds count");
assertEq(dag.children("c").length, 2, "dag children of add");
assertEq(dag.children("c")[0].kind, "num/literal", "add left child is literal");
assertEq(dag.parents("a")[0], "c", "parent of a is c (add)");
assertEq(dag.parents("c")[0], "e", "parent of c is e (mul)");
assertEq(dag.parents("e").length, 0, "root has no parents");

console.log("  PASS");

// ============================================================
// Test 3: Named nodes
// ============================================================

console.log("\n=== Test 3: Named nodes ===");

const $n = freshCtx();
const [price, $n1] = $n.numLit(100);
const [namedPrice, $n2] = $n1.named("price", price);
const [taxRate, $n3] = $n2.numLit(21);
const [namedRate, $n4] = $n3.named("tax-rate", taxRate);
const [tax, $n5] = $n4.mul(namedPrice, namedRate);
const [namedTax, $n6] = $n5.named("tax", tax);

assertEq(namedPrice.__adj["@price"].kind, "@alias", "price alias exists");
assertEq(namedPrice.__adj["@price"].target, "a", "price points to a");
assertEq(namedRate.__adj["@tax-rate"].target, "b", "tax-rate points to b");

const dagN = createDagView(namedTax.__adj);
assertEq(dagN.resolve("price"), "a", "resolve price → a");
assertEq(dagN.resolve("tax-rate"), "b", "resolve tax-rate → b");
assertEq(dagN.resolve("tax"), "c", "resolve tax → c");

console.log("  PASS");

// ============================================================
// Test 4: selectByKind
// ============================================================

console.log("\n=== Test 4: selectByKind ===");

const lits = selectByKind(prog, "num/literal");
assertEq(Object.keys(lits).length, 3, "3 literals");
assertEq(lits["a"].kind, "num/literal", "a is literal");

const adds = selectByKind(prog, "num/add");
assertEq(Object.keys(adds).length, 1, "1 add");

const subs = selectByKind(prog, "num/sub");
assertEq(Object.keys(subs).length, 0, "0 subs");

console.log("  PASS");

// ============================================================
// Test 5: updateByKind
// ============================================================

console.log("\n=== Test 5: updateByKind ===");

const allMul = updateByKind(prog, "num/add", "num/mul");
assertEq(allMul.__adj["c"].kind, "num/mul", "add became mul");
assertEq(allMul.__adj["e"].kind, "num/mul", "original mul unchanged");
// Children preserved
assertEq(allMul.__adj["c"].children[0], "a", "children preserved");
assertEq(allMul.__adj["c"].children[1], "b", "children preserved");
// Root unchanged
assertEq(allMul.__id, "e", "root id unchanged");

console.log("  PASS");

// ============================================================
// Test 6: replaceNode (the zero-cascade replacement)
// ============================================================

console.log("\n=== Test 6: replaceNode ===");

const replaced = replaceNode(prog, "a", {
  kind: "num/literal",
  children: [],
  out: 99,
});

// Root unchanged
assertEq(replaced.__id, "e", "root unchanged after replace");
// Target replaced
assertEq(replaced.__adj["a"].out, 99, "a now holds 99");
// Parents still reference same ID — no cascade needed
assertEq(replaced.__adj["c"].children[0], "a", "add still points to a");
// Other entries untouched
assertEq(replaced.__adj["b"].out, 4, "b still 4");

console.log("  PASS");

// ============================================================
// Test 7: replaceByName
// ============================================================

console.log("\n=== Test 7: replaceByName ===");

// Build: total = price(100) + tax(price * rate(21))
const $r = freshCtx();
const [rPrice, $r1] = $r.numLit(100);
const [rNPrice, $r2] = $r1.named("price", rPrice);
const [rRate, $r3] = $r2.numLit(21);
const [rNRate, $r4] = $r3.named("tax-rate", rRate);
const [rTax, $r5] = $r4.mul(rNPrice, rNRate);
const [rTotal, $r6] = $r5.add(rNPrice, rTax);

// Replace tax-rate with 15
// We need a fresh expr for the replacement
const $rep = createCtx("z");  // use a different counter region to avoid collision
const [newRate, _] = $rep.numLit(15);

const updated = replaceByName(rTotal, "tax-rate", newRate);

assertEq(updated.__id, "d", "root unchanged");
assertEq(updated.__adj["b"].out, 15, "tax-rate now 15");
assertEq(updated.__adj["@tax-rate"].target, "b", "alias still points to b");

// Parents still reference b
assertEq(updated.__adj["c"].children[1], "b", "mul still refs b");

console.log("  PASS");

// ============================================================
// Test 8: DagView.parents with shared nodes (DAG not tree)
// ============================================================

console.log("\n=== Test 8: Shared nodes (DAG) ===");

// x = lit(7), prog = add(x, x) — x has two parents (same node)
const $d = freshCtx();
const [x, $d1] = $d.numLit(7);
const [doubled, $d2] = $d1.add(x, x);

assertEq(doubled.__adj["b"].children![0], "a", "add left = a");
assertEq(doubled.__adj["b"].children![1], "a", "add right = a");

const dagD = createDagView(doubled.__adj);
// x ("a") should have "b" as parent (appears once even though referenced twice)
const parentsOfA = dagD.parents("a");
// In our implementation, "b" will appear twice since we iterate children
// That's fine for a spike — a Set would dedupe in production
assertEq(parentsOfA.includes("b"), true, "a's parent includes b");

console.log("  PASS");

// ============================================================
// Test 9: Scale — build 100 nodes
// ============================================================

console.log("\n=== Test 9: Scale (100 nodes) ===");

let ctx: any = freshCtx();
let prev: any;

[prev, ctx] = ctx.numLit(0);
for (let i = 1; i < 50; i++) {
  let next: any;
  [next, ctx] = ctx.numLit(i);
  [prev, ctx] = ctx.add(prev, next);
}
// 50 numLits + 49 adds = 99 nodes, plus one more add = 100
const [lastLit, ctx2] = ctx.numLit(50);
const [bigProg, _ctx3] = ctx2.add(prev, lastLit);

assertEq(Object.keys(bigProg.__adj).length, 101, "101 nodes in adj");
assertEq(bigProg.__id.length > 0, true, "has root id");

// Queries still work at scale
const bigLits = selectByKind(bigProg, "num/literal");
assertEq(Object.keys(bigLits).length, 51, "51 literals");

const bigAdds = selectByKind(bigProg, "num/add");
assertEq(Object.keys(bigAdds).length, 50, "50 adds");

// Replace a deep node — still no cascade
const bigReplaced = replaceNode(bigProg, "a", {
  kind: "num/literal",
  children: [],
  out: 999,
});
assertEq(bigReplaced.__adj["a"].out, 999, "deep replace works");
assertEq(bigReplaced.__id, bigProg.__id, "root unchanged");

console.log("  adj size:", Object.keys(bigProg.__adj).length);
console.log("  PASS");

// ============================================================
// Test 10: wrap as a composition of existing primitives
// ============================================================

console.log("\n=== Test 10: wrap = addEntry + rewire parents ===");

// wrap(expr, targetId, wrapperKind, ctx):
//   1. Take a fresh ID from ctx for the wrapper
//   2. Add wrapper entry with target as its child
//   3. Rewrite every parent of target to reference wrapper instead
//
// That's: one adj insert + one bulk children rewrite. Both already exist.

function wrap(
  expr: any,
  targetId: string,
  wrapperKind: string,
  ctx: any, // BuildCtx — we just need a fresh ID
): [any, any] {
  // Step 1: get fresh ID (just read the counter from ctx)
  // We'll cheat slightly: call numLit to get an ID, then throw away the entry
  const [dummy, nextCtx] = ctx.numLit(0);
  const wrapperId = dummy.__id;

  // Step 2: add wrapper entry pointing to target
  const newAdj = {
    ...expr.__adj,
    [wrapperId]: { kind: wrapperKind, children: [targetId] },
  };

  // Step 3: rewire parents — swap targetId → wrapperId in their children
  for (const [id, entry] of Object.entries(newAdj)) {
    if (id === wrapperId) continue; // skip the wrapper itself
    if (id.startsWith("@")) continue;
    const e = entry as any;
    if (e.children && e.children.includes(targetId)) {
      newAdj[id] = {
        ...e,
        children: e.children.map((c: string) => c === targetId ? wrapperId : c),
      };
    }
  }

  // Also update root ID if the root was the target
  const rootId = expr.__id === targetId ? wrapperId : expr.__id;

  return [makeExpr(expr.kind, rootId, newAdj, dummy.__counter), nextCtx];
}

// Test: add(lit(3), lit(4)) → wrap lit(3) with neg → add(neg(lit(3)), lit(4))
const $w = freshCtx();
const [w3, $w1] = $w.numLit(3);
const [w4, $w2] = $w1.numLit(4);
const [wSum, $w3] = $w2.add(w3, w4);

// Before: c.children = ["a", "b"]
assertEq(wSum.__adj["c"].children![0], "a", "before wrap: add left = a");
assertEq(wSum.__adj["c"].children![1], "b", "before wrap: add right = b");

// Wrap "a" (lit(3)) with neg
const [wrapped, $w4] = wrap(wSum, "a", "num/neg", $w3);

// After:
// - "d" is the new neg wrapper: children = ["a"]
// - "c" (add) now points to "d" instead of "a": children = ["d", "b"]
// - "a" is untouched
assertEq(wrapped.__adj["d"].kind, "num/neg", "wrapper is neg");
assertEq(wrapped.__adj["d"].children![0], "a", "wrapper child = a");
assertEq(wrapped.__adj["c"].children![0], "d", "add left rewired to d");
assertEq(wrapped.__adj["c"].children![1], "b", "add right unchanged");
assertEq(wrapped.__adj["a"].kind, "num/literal", "a untouched");
assertEq(wrapped.__adj["a"].out, 3, "a still 3");
assertEq(wrapped.__id, "c", "root unchanged");

console.log("  Before: add(a:lit(3), b:lit(4))");
console.log("  After:  add(d:neg(a:lit(3)), b:lit(4))");
console.log("  PASS");

// Test: wrap by name
console.log("\n=== Test 11: wrap by name ===");

const $wn = freshCtx();
const [np, $wna] = $wn.numLit(100);
const [nnp, $wnb] = $wna.named("price", np);
const [nt, $wnc] = $wnb.numLit(21);
const [nnt, $wnd] = $wnc.named("tax", nt);
const [total, $wne] = $wnd.add(nnp, nnt);

// Wrap "price" (a) with neg → total becomes add(neg(price), tax)
const dag2 = createDagView(total.__adj);
const priceId = dag2.resolve("price");
const [wrappedTotal, $wnf] = wrap(total, priceId, "num/neg", $wne);

// a:lit(100), b:lit(21), c:add(a,b), wrapper gets d
assertEq(wrappedTotal.__adj["d"].kind, "num/neg", "wrapper is neg");
assertEq(wrappedTotal.__adj["d"].children![0], "a", "wrapper points to price");
assertEq(wrappedTotal.__adj["c"].children![0], "d", "add rewired to wrapper");
assertEq(wrappedTotal.__adj["c"].children![1], "b", "add right unchanged");
assertEq(wrappedTotal.__adj["@price"].target, "a", "name still points to a");

console.log("  Resolved @price → " + priceId + ", wrapped with neg");
console.log("  PASS");

// Test: wrap the root node itself
console.log("\n=== Test 12: wrap root ===");

const $wr = freshCtx();
const [r7, $wra] = $wr.numLit(7);
const [wrappedRoot, $wrb] = wrap(r7, "a", "num/neg", $wra);

assertEq(wrappedRoot.__id, "b", "root is now the wrapper");
assertEq(wrappedRoot.__adj["b"].kind, "num/neg", "wrapper is neg");
assertEq(wrappedRoot.__adj["b"].children![0], "a", "wrapper child = original root");
assertEq(wrappedRoot.__adj["a"].kind, "num/literal", "original untouched");

console.log("  lit(7) → neg(lit(7)), root changed from a to b");
console.log("  PASS");

// ============================================================
// Summary
// ============================================================

console.log("\n=== All tests passed ===");

spike-typed-transforms.ts

// ============================================================
// Spike: Proving type holes — mapWhere, wrapWhere, gc
// ============================================================

import { IDChain, FirstID } from "./spike-idchain";

// ============================================================
// Core types (compact, from previous spikes)
// ============================================================

type NodeEntry<Kind extends string, ChildIDs extends string[], Out> = {
  readonly kind: Kind;
  readonly children: ChildIDs;
  readonly out: Out;
};

type Desc<Out, ID extends string, Adj extends Record<string, any>, C extends string> = {
  readonly o: Out; readonly id: ID; readonly adj: Adj; readonly c: C;
};

declare const exprBrand: unique symbol;
interface Expr<O, R extends Desc<O, string, Record<string, any>, string>> {
  readonly [exprBrand]: R;
}

type OutOf<R> = R extends Desc<infer O, any, any, any> ? O : never;
type IdOf<R> = R extends Desc<any, infer ID, any, any> ? ID : never;
type AdjOf<R> = R extends Desc<any, any, infer A, any> ? A : never;
type CtrOf<R> = R extends Desc<any, any, any, infer C> ? C : never;
type NextID<C extends keyof IDChain> = IDChain[C];

// ============================================================
// Predicates (minimal subset)
// ============================================================

interface KindPred<K extends string> { readonly tag: "kind"; readonly kind: K }
interface KindGlobPred<P extends string> { readonly tag: "kindGlob"; readonly prefix: P }
interface LeafPred { readonly tag: "leaf" }
interface NotPred<P> { readonly tag: "not"; readonly inner: P }
interface AndPred<A, B> { readonly tag: "and"; readonly left: A; readonly right: B }

type EvalPred<P, Entry> =
  P extends KindPred<infer K>
    ? Entry extends NodeEntry<K, any, any> ? true : false
  : P extends KindGlobPred<infer Prefix>
    ? Entry extends NodeEntry<`${Prefix}${string}`, any, any> ? true : false
  : P extends LeafPred
    ? Entry extends NodeEntry<any, infer C, any> ? C extends [] ? true : false : false
  : P extends NotPred<infer Inner>
    ? EvalPred<Inner, Entry> extends true ? false : true
  : P extends AndPred<infer A, infer B>
    ? EvalPred<A, Entry> extends true
      ? EvalPred<B, Entry> extends true ? true : false : false
  : never;

// ============================================================
// CRITICAL: mapWhere result typing
// ============================================================

// Union of entry types that match the predicate
type MatchingEntries<Adj, P> = {
  [K in keyof Adj]: EvalPred<P, Adj[K]> extends true ? Adj[K] : never;
}[keyof Adj];

// Transform adj: matching → NewEntry, non-matching → unchanged
type MapAdj<Adj, P, NewEntry> = {
  [K in keyof Adj]: EvalPred<P, Adj[K]> extends true ? NewEntry : Adj[K];
};

// Output type: changes only if root was matched
type MapOut<O, Adj, RootID extends string & keyof Adj, P, NewEntry> =
  EvalPred<P, Adj[RootID]> extends true
    ? NewEntry extends NodeEntry<any, any, infer NO> ? NO : O
    : O;

// The function signature
declare function mapWhere<
  O,
  R extends Desc<O, string, Record<string, any>, string>,
  P,
  NE extends NodeEntry<string, string[], any>,
>(
  expr: Expr<O, R>,
  pred: P,
  fn: (entry: MatchingEntries<AdjOf<R>, P>) => NE,
): Expr<
  MapOut<O, AdjOf<R>, IdOf<R> & string, P, NE>,
  Desc<
    MapOut<O, AdjOf<R>, IdOf<R> & string, P, NE>,
    IdOf<R>,
    MapAdj<AdjOf<R>, P, NE>,
    CtrOf<R>
  >
>;

// ============================================================
// Test fixture: (3 + 4) * 5, root at "e"
// ============================================================

type TA = {
  a: NodeEntry<"num/literal", [], number>;
  b: NodeEntry<"num/literal", [], number>;
  c: NodeEntry<"num/add", ["a", "b"], number>;
  d: NodeEntry<"str/literal", [], string>;
  e: NodeEntry<"num/mul", ["c", "b"], number>;
};

type TD = Desc<number, "e", TA, "f">;
declare const prog: Expr<number, TD>;

// ============================================================
// Test 1: mapWhere byKind("num/add") → kind stays, out changes
// Callback: num/add → num/sub (same children, same out type)
// ============================================================

const r1 = mapWhere(
  prog,
  { tag: "kind", kind: "num/add" } as const satisfies KindPred<"num/add">,
  (_e) => ({ kind: "num/sub" as const, children: ["a", "b"] as const, out: 0 as number }),
);

// Result adj should have "c" changed to num/sub, everything else same
type R1R = (typeof r1)[typeof exprBrand];
type R1Adj = AdjOf<R1R>;

// c is now num/sub
type R1C = R1Adj["c"];
const _r1cKind: R1C["kind"] = "num/sub";

// a is unchanged
type R1A = R1Adj["a"];
const _r1aKind: R1A["kind"] = "num/literal";

// d is unchanged
type R1D = R1Adj["d"];
const _r1dKind: R1D["kind"] = "str/literal";

// root ID unchanged
type R1ID = IdOf<R1R>;
const _r1id: R1ID = "e";

// output type unchanged (root "e" is num/mul, not matched)
type R1Out = OutOf<R1R>;
const _r1out: R1Out = 42;

// NEGATIVE: c is NOT num/add anymore
// @ts-expect-error — c was transformed to num/sub
const _r1cWrong: R1C["kind"] = "num/add";

// ============================================================
// Test 2: mapWhere byKindGlob("num/") → all num nodes changed
// ============================================================

const r2 = mapWhere(
  prog,
  { tag: "kindGlob", prefix: "num/" } as const satisfies KindGlobPred<"num/">,
  (_e) => ({ kind: "opt/node" as const, children: [] as const, out: 0 as number }),
);

type R2R = (typeof r2)[typeof exprBrand];
type R2Adj = AdjOf<R2R>;

// a, b, c, e all become opt/node
const _r2a: R2Adj["a"]["kind"] = "opt/node";
const _r2b: R2Adj["b"]["kind"] = "opt/node";
const _r2c: R2Adj["c"]["kind"] = "opt/node";
const _r2e: R2Adj["e"]["kind"] = "opt/node";

// d unchanged (str/literal)
const _r2d: R2Adj["d"]["kind"] = "str/literal";

// NEGATIVE: d is NOT opt/node
// @ts-expect-error — d was not matched by num/ glob
const _r2dWrong: R2Adj["d"]["kind"] = "opt/node";

// ============================================================
// Test 3: mapWhere on root → output type changes
// ============================================================

// Change root "e" (num/mul) to output string instead of number
const r3 = mapWhere(
  prog,
  { tag: "kind", kind: "num/mul" } as const satisfies KindPred<"num/mul">,
  (_e) => ({ kind: "str/repr" as const, children: ["c", "b"] as const, out: "" as string }),
);

type R3R = (typeof r3)[typeof exprBrand];
type R3Out = OutOf<R3R>;

// Output type is now string!
const _r3out: R3Out = "hello";

// NEGATIVE: output is NOT number anymore
// @ts-expect-error — root was transformed, output is now string
const _r3outWrong: R3Out = 42;

// ============================================================
// Test 4: mapWhere on non-root → output type unchanged
// ============================================================

const r4 = mapWhere(
  prog,
  { tag: "leaf" } as const satisfies LeafPred,
  (_e) => ({ kind: "const/zero" as const, children: [] as const, out: "" as string }),
);

type R4R = (typeof r4)[typeof exprBrand];
type R4Out = OutOf<R4R>;

// Root "e" is num/mul (not leaf), so output type stays number
const _r4out: R4Out = 42;

// @ts-expect-error — output is still number, not string
const _r4outWrong: R4Out = "nope";

// ============================================================
// Test 5: counter unchanged (mapWhere allocates no IDs)
// ============================================================

type R1Ctr = CtrOf<R1R>;
const _r1ctr: R1Ctr = "f"; // same as input

// ============================================================
// HIGH: wrapWhere — single wrap (wrapByName) is fully typeable
// ============================================================

// Rewire: parents that referenced TargetID now reference WrapperID
type RewireParents<Adj, TargetID extends string, WrapperID extends string> = {
  [K in keyof Adj]: Adj[K] extends NodeEntry<infer Kind, infer Children extends string[], infer Out>
    ? NodeEntry<Kind, RewireList<Children, TargetID, WrapperID>, Out>
    : Adj[K];
};

type RewireList<T extends string[], Old extends string, New extends string> =
  T extends [infer H extends string, ...infer Rest extends string[]]
    ? [H extends Old ? New : H, ...RewireList<Rest, Old, New>]
    : [];

// WrapOneComplete: rewire parents in original adj, then add wrapper entry
type WrapOneComplete<
  Adj extends Record<string, any>,
  TargetID extends string,
  WrapperKind extends string,
  C extends string & keyof IDChain,
> = RewireParents<Adj, TargetID, C> & Record<
  C,
  NodeEntry<
    WrapperKind,
    [TargetID],
    Adj[TargetID] extends NodeEntry<any, any, infer O> ? O : never
  >
>;

declare function wrapByName<
  O,
  R extends Desc<O, string, Record<string, any>, string>,
  TargetID extends string & keyof AdjOf<R>,
  WrapperKind extends string,
>(
  expr: Expr<O, R>,
  targetId: TargetID,
  wrapperKind: WrapperKind,
): CtrOf<R> extends string & keyof IDChain
  ? Expr<
      O,
      Desc<
        O,
        // Root changes if we wrapped the root
        IdOf<R> extends TargetID ? CtrOf<R> & string : IdOf<R>,
        WrapOneComplete<AdjOf<R>, TargetID, WrapperKind, CtrOf<R> & keyof IDChain>,
        NextID<CtrOf<R> & keyof IDChain> & string
      >
    >
  : never;

// ============================================================
// Test 6: wrapByName — wrap node "c" (num/add) with "telemetry/span"
// ============================================================

const w1 = wrapByName(prog, "c", "telemetry/span");

type W1R = (typeof w1)[typeof exprBrand];
type W1Adj = AdjOf<W1R>;

// Wrapper at "f" (next counter)
type W1Wrapper = W1Adj["f"];
const _w1wKind: W1Wrapper["kind"] = "telemetry/span";
const _w1wChildren: W1Wrapper["children"] = ["c"];

// Original "c" still exists
const _w1cKind: W1Adj["c"]["kind"] = "num/add";

// Parent "e" (num/mul) now references "f" instead of "c"
type W1E = W1Adj["e"];
const _w1eChildren: W1E["children"] = ["f", "b"];

// Counter advanced
type W1Ctr = CtrOf<W1R>;
const _w1ctr: W1Ctr = "g";

// Root unchanged (we didn't wrap root)
type W1ID = IdOf<W1R>;
const _w1id: W1ID = "e";

// NEGATIVE: parent should NOT still reference "c"
// @ts-expect-error — "e" now points to wrapper "f", not "c"
const _w1eWrong: W1E["children"] = ["c", "b"];

// ============================================================
// Test 7: wrapByName — wrap root "e"
// ============================================================

const w2 = wrapByName(prog, "e", "telemetry/root-span");

type W2R = (typeof w2)[typeof exprBrand];

// Root is now the wrapper "f"
type W2ID = IdOf<W2R>;
const _w2id: W2ID = "f";

// Wrapper's children = ["e"]
type W2Wrapper = AdjOf<W2R>["f"];
const _w2wKind: W2Wrapper["kind"] = "telemetry/root-span";
const _w2wChildren: W2Wrapper["children"] = ["e"];

// Output type unchanged
type W2Out = OutOf<W2R>;
const _w2out: W2Out = 42;

// ============================================================
// BULK wrapWhere: here's the wall
// ============================================================

// The problem: wrapWhere(expr, byKindGlob("num/"), "span") matches N nodes.
// Each needs a fresh ID. We must iterate the matching keys at the type level,
// allocating one ID per match. TypeScript has no built-in "iterate a union."
//
// Options we considered:
//   1. UnionToTuple — fragile, order-dependent, limited depth
//   2. Approximate typing — lose precision on new IDs
//   3. wrapByName only — user loops explicitly with context threading
//
// Verdict: wrapByName is fully typed. Bulk wrapWhere would need UnionToTuple
// or a fold-over-union trick. Both are hacks. For now, bulk wrap = user code:
//
//   const [e1, ctx1] = wrapByName(expr, "a", "span");
//   const [e2, ctx2] = wrapByName(e1, "b", "span");
//   // each step fully typed, counter threads correctly

// ============================================================
// MEDIUM: gc at the type level — here's the other wall
// ============================================================

// Computing reachability requires walking from root through children.
// That's recursive graph traversal over the adj type.
// Let's try it and see where we hit limits.

type Reachable<Adj, ID extends string, Visited extends string = never> =
  ID extends Visited ? Visited :
  ID extends keyof Adj
    ? Adj[ID] extends NodeEntry<any, infer Children extends string[], any>
      ? ReachableAll<Adj, Children, Visited | ID>
      : Visited | ID
    : Visited | ID;

type ReachableAll<Adj, IDs extends string[], Visited extends string> =
  IDs extends [infer H extends string, ...infer T extends string[]]
    ? ReachableAll<Adj, T, Reachable<Adj, H, Visited>>
    : Visited;

// GC: keep only reachable keys
type GCAdj<Adj, RootID extends string> = {
  [K in keyof Adj as K extends Reachable<Adj, RootID> ? K : never]: Adj[K];
};

// ============================================================
// Test 8: gc on a clean graph — nothing removed
// ============================================================

type GC1 = GCAdj<TA, "e">;
// e→[c,b], c→[a,b], a→[], b→[], so a,b,c,e reachable. d is orphan.
type GC1Keys = keyof GC1;
const _gc1a: GC1Keys = "a";
const _gc1b: GC1Keys = "b";
const _gc1c: GC1Keys = "c";
const _gc1e: GC1Keys = "e";

// d is unreachable (str/literal, no parent)
// @ts-expect-error — d is garbage collected
const _gc1d: GC1Keys = "d";

// ============================================================
// Test 9: gc preserves entries correctly
// ============================================================

type GC1A = GC1["a"];
const _gc1aKind: GC1A["kind"] = "num/literal";

type GC1E = GC1["e"];
const _gc1eKind: GC1E["kind"] = "num/mul";

// ============================================================
// Test 10: gc on a graph with more orphans
// ============================================================

type Orphaned = {
  a: NodeEntry<"num/literal", [], number>;
  b: NodeEntry<"num/literal", [], number>;
  c: NodeEntry<"num/add", ["a", "b"], number>;
  x: NodeEntry<"orphan/1", [], string>;
  y: NodeEntry<"orphan/2", ["x"], string>;
  z: NodeEntry<"orphan/3", [], boolean>;
};

type GC2 = GCAdj<Orphaned, "c">;
type GC2Keys = keyof GC2;
const _gc2a: GC2Keys = "a";
const _gc2b: GC2Keys = "b";
const _gc2c: GC2Keys = "c";
// @ts-expect-error — x is orphan
const _gc2x: GC2Keys = "x";
// @ts-expect-error — y is orphan
const _gc2y: GC2Keys = "y";
// @ts-expect-error — z is orphan
const _gc2z: GC2Keys = "z";

// ============================================================
// Test 11: gc on diamond DAG (shared nodes)
// ============================================================

type Diamond = {
  a: NodeEntry<"val", [], number>;
  b: NodeEntry<"use1", ["a"], number>;
  c: NodeEntry<"use2", ["a"], number>;
  d: NodeEntry<"join", ["b", "c"], number>;
};

type GC3 = GCAdj<Diamond, "d">;
type GC3Keys = keyof GC3;
const _gc3a: GC3Keys = "a";
const _gc3b: GC3Keys = "b";
const _gc3c: GC3Keys = "c";
const _gc3d: GC3Keys = "d";

// ============================================================
// Scale test: does gc recurse too deep?
// ============================================================

type Chain8 = {
  a: NodeEntry<"n", [], number>;
  b: NodeEntry<"n", ["a"], number>;
  c: NodeEntry<"n", ["b"], number>;
  d: NodeEntry<"n", ["c"], number>;
  e: NodeEntry<"n", ["d"], number>;
  f: NodeEntry<"n", ["e"], number>;
  g: NodeEntry<"n", ["f"], number>;
  h: NodeEntry<"n", ["g"], number>;
};

type GC4 = GCAdj<Chain8, "h">;
type GC4Keys = keyof GC4;
// All 8 reachable
const _gc4a: GC4Keys = "a";
const _gc4h: GC4Keys = "h";

// Depth 8 works. Real programs may be deeper — runtime gc() is the fallback.

console.log("spike-typed-transforms compiled successfully");