Issue 190: Codex ur-spike 0

spike-ur-bridge.ts

import { fromTypedAdj, type Desc, type Expr, type NodeEntry, type RuntimeNode } from "./spike-ur-core";

export interface DagBridge {
  expr: Expr<unknown, Desc<unknown, string, Record<string, NodeEntry<string, string[], unknown>>, string, true>>;
}

function nextIdRuntime(s: string): string {
  const chars = s.split("");
  for (let i = chars.length - 1; i >= 0; i--) {
    if (chars[i] !== "z") {
      chars[i] = String.fromCharCode(chars[i].charCodeAt(0) + 1);
      return chars.join("");
    }
    chars[i] = "a";
  }
  return `a${chars.join("")}`;
}

export function toDAG(ast: any): DagBridge {
  const adj: Record<string, NodeEntry<string, string[], unknown>> = {};
  const nodeMeta: Record<string, Pick<RuntimeNode, "fields" | "data">> = {};
  let counter = "a";

  const walk = (node: any): string => {
    const id = counter;
    counter = nextIdRuntime(counter);

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

    for (const [k, v] of Object.entries(node)) {
      if (k === "kind" || k.startsWith("__")) continue;
      if (Array.isArray(v) && v.length > 0 && typeof v[0] === "object" && v[0] !== null && "kind" in (v[0] as any)) {
        const ids = (v as any[]).map((c) => walk(c));
        fields[k] = ids;
        children.push(...ids);
      } else if (typeof v === "object" && v !== null && "kind" in (v as any)) {
        const cid = walk(v);
        fields[k] = cid;
        children.push(cid);
      } else {
        data[k] = v;
      }
    }

    adj[id] = { kind: node.kind, children, out: undefined };
    nodeMeta[id] = { fields, data };
    return id;
  };

  const root = walk(ast);
  const expr = fromTypedAdj(root, adj, counter);
  for (const [id, meta] of Object.entries(nodeMeta)) {
    const node = expr.__adj[id] as RuntimeNode;
    expr.__adj[id] = { ...node, fields: meta.fields, data: meta.data } as any;
  }

  return { expr };
}

export function toAST(bridge: DagBridge): any {
  const materialize = (id: string): any => {
    const raw = bridge.expr.__adj[id];
    if (!raw || raw.kind === "@alias") throw new Error(`missing node '${id}'`);

    const node = raw as RuntimeNode;
    const out: Record<string, unknown> = { kind: node.kind };
    const fields = node.fields;
    if (!fields && node.children.length > 0) throw new Error(`missing fields metadata for node '${id}'`);
    const data = node.data || {};

    for (const [k, v] of Object.entries(fields ?? {})) {
      out[k] = Array.isArray(v) ? v.map((cid) => materialize(cid)) : materialize(v as string);
    }
    for (const [k, v] of Object.entries(data)) out[k] = v;
    return out;
  };

  return materialize(bridge.expr.__id);
}

export function withExpr(bridge: DagBridge, expr: DagBridge["expr"]): DagBridge {
  return { ...bridge, expr };
}

spike-ur-buildctx.ts

import {
  fromTypedAdj,
  named,
  type AdjOf,
  type Desc,
  type Expr,
  type IdOf,
  type NextID,
  type NodeEntry,
} from "./spike-ur-core";

export type FirstID = "a";

type IncRuntime = (s: string) => string;
const inc: IncRuntime = (s) => {
  const chars = s.split("");
  for (let i = chars.length - 1; i >= 0; i--) {
    if (chars[i] !== "z") {
      chars[i] = String.fromCharCode(chars[i].charCodeAt(0) + 1);
      return chars.join("");
    }
    chars[i] = "a";
  }
  return `a${chars.join("")}`;
};

export interface BuildCtx<C extends string> {
  numLit<V extends number>(value: V): [
    Expr<number, Desc<number, C, Record<C, NodeEntry<"core/literal", [], number>>, NextID<C>, true>>,
    BuildCtx<NextID<C>>,
  ];

  add<RA extends Desc<number, string, Record<string, any>, string, true>, RB extends Desc<number, string, Record<string, any>, string, true>>(
    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>>, NextID<C>, true>>,
    BuildCtx<NextID<C>>,
  ];

  mul<RA extends Desc<number, string, Record<string, any>, string, true>, RB extends Desc<number, string, Record<string, any>, string, true>>(
    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>>, NextID<C>, true>>,
    BuildCtx<NextID<C>>,
  ];

  named<Name extends string, O, R extends Desc<O, string, Record<string, any>, string, true>>(
    name: Name,
    expr: Expr<O, R>,
  ): [Expr<O, ReturnType<typeof named<Name, O, R>> extends Expr<O, infer NR> ? NR : never>, BuildCtx<C>];
}

function createCtx<C extends string>(counter: C): BuildCtx<C> {
  return {
    numLit(value: number) {
      const id = counter;
      const next = inc(counter);
      const expr = fromTypedAdj<number, any, any, any>(
        id,
        {
          [id]: {
            kind: "core/literal",
            children: [],
            out: value,
            fields: {},
            data: { value },
          },
        },
        next,
      );
      return [expr, createCtx(next)] as any;
    },

    add(left: Expr<any, any>, right: Expr<any, any>) {
      const id = counter;
      const next = inc(counter);
      const expr = fromTypedAdj<number, any, any, any>(
        id,
        {
          ...left.__adj,
          ...right.__adj,
          [id]: {
            kind: "num/add",
            children: [left.__id, right.__id],
            out: undefined,
            fields: { left: left.__id, right: right.__id },
            data: {},
          },
        },
        next,
      );
      return [expr, createCtx(next)] as any;
    },

    mul(left: Expr<any, any>, right: Expr<any, any>) {
      const id = counter;
      const next = inc(counter);
      const expr = fromTypedAdj<number, any, any, any>(
        id,
        {
          ...left.__adj,
          ...right.__adj,
          [id]: {
            kind: "num/mul",
            children: [left.__id, right.__id],
            out: undefined,
            fields: { left: left.__id, right: right.__id },
            data: {},
          },
        },
        next,
      );
      return [expr, createCtx(next)] as any;
    },

    named(name: string, expr: Expr<any, any>) {
      return [named(name, expr), createCtx(counter)] as any;
    },
  } as BuildCtx<C>;
}

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

spike-ur-core.ts

// Unified ur-spike core: typed DAG, dirty/commit, predicates, transforms.
import type { BuildRev, GCAdjBidir } from "./spike-ur-types";

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

export type NameAlias<Name extends string, TargetID extends string, Out> = {
  readonly kind: "@alias";
  readonly target: TargetID;
  readonly out: Out;
  readonly name: Name;
};

export type Desc<
  Out,
  ID extends string,
  Adj extends Record<string, any>,
  C extends string,
  Clean extends boolean,
  Rev extends Record<string, any> = BuildRev<Adj>,
> = {
  readonly o: Out;
  readonly id: ID;
  readonly adj: Adj;
  readonly c: C;
  readonly clean: Clean;
  readonly rev: Rev;
};

declare const exprBrand: unique symbol;

export type RuntimeNode = { kind: string; children: string[]; out: unknown; fields?: Record<string, string | string[]>; data?: Record<string, unknown> };
type RuntimeAlias = { kind: "@alias"; target: string; name: string };
export type RuntimeAdj = Record<string, RuntimeNode | RuntimeAlias>;

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

export interface DirtyExpr<O, R extends Desc<O, string, Record<string, any>, string, false>> {
  readonly [exprBrand]: R;
  readonly __id: string;
  readonly __adj: RuntimeAdj;
  readonly __counter: string;
}

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

type ReplaceAt<Adj, Key extends string, Val> = Omit<Adj, Key> & Record<Key, Val>;
type RemoveAt<Adj, Key extends string> = Omit<Adj, Key>;

type IncLast<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;
export type NextID<S extends string> = S extends `${infer R}z` ? (R extends "" ? "aa" : `${NextID<R>}a`) : IncLast<S>;

function isAlias(v: RuntimeNode | RuntimeAlias): v is RuntimeAlias {
  return v.kind === "@alias";
}

function nextIdRuntime(s: string): string {
  const chars = s.split("");
  for (let i = chars.length - 1; i >= 0; i--) {
    if (chars[i] !== "z") {
      chars[i] = String.fromCharCode(chars[i].charCodeAt(0) + 1);
      return chars.join("");
    }
    chars[i] = "a";
  }
  return `a${chars.join("")}`;
}

// Internal bridge cast. Users never call this directly.
function makeExpr(id: string, adj: RuntimeAdj, counter: string): any {
  return { __id: id, __adj: adj, __counter: counter };
}

export function fromTypedAdj<O, ID extends string, Adj extends Record<string, NodeEntry<string, readonly string[], any>>, C extends string>(
  id: ID,
  adj: Adj,
  counter: C,
): Expr<O, Desc<O, ID, Adj, C, true>> {
  const rt: RuntimeAdj = {};
  for (const [k, v] of Object.entries(adj)) {
    const meta = v as any;
    rt[k] = {
      kind: v.kind,
      children: [...v.children],
      out: v.out,
      fields: meta.fields,
      data: meta.data,
    };
  }
  return makeExpr(id, rt, counter) as Expr<O, Desc<O, ID, Adj, C, true>>;
}

export function named<Name extends string, O, R extends Desc<O, string, Record<string, any>, string, true>>(
  name: Name,
  expr: Expr<O, R>,
): Expr<O, Desc<O, IdOf<R>, AdjOf<R> & Record<`@${Name}`, NameAlias<Name, IdOf<R>, O>>, CtrOf<R>, true>> {
  const adj: RuntimeAdj = {
    ...expr.__adj,
    [`@${name}`]: { kind: "@alias", target: expr.__id, name: String(name) },
  };
  return makeExpr(expr.__id, adj, expr.__counter) as Expr<
    O,
    Desc<O, IdOf<R>, AdjOf<R> & Record<`@${Name}`, NameAlias<Name, IdOf<R>, O>>, CtrOf<R>, true>
  >;
}

export function dirty<O, R extends Desc<O, string, Record<string, any>, string, true>>(
  expr: Expr<O, R>,
): DirtyExpr<O, Desc<O, IdOf<R>, AdjOf<R>, CtrOf<R>, false, RevOf<R>>> {
  return makeExpr(expr.__id, { ...expr.__adj }, expr.__counter) as DirtyExpr<
    O,
    Desc<O, IdOf<R>, AdjOf<R>, CtrOf<R>, false, RevOf<R>>
  >;
}

export function addEntry<O, R extends Desc<O, string, Record<string, any>, string, false>, ID extends string, E extends NodeEntry<string, readonly string[], any>>(
  expr: DirtyExpr<O, R>,
  id: ID,
  entry: E,
): DirtyExpr<O, Desc<O, IdOf<R>, AdjOf<R> & Record<ID, E>, CtrOf<R>, false>> {
  const meta = entry as any;
  const adj = {
    ...expr.__adj,
    [id]: {
      kind: entry.kind,
      children: [...entry.children],
      out: entry.out,
      fields: meta.fields,
      data: meta.data,
    },
  };
  return makeExpr(expr.__id, adj, expr.__counter) as DirtyExpr<
    O,
    Desc<O, IdOf<R>, AdjOf<R> & Record<ID, E>, CtrOf<R>, false, BuildRev<AdjOf<R> & Record<ID, E>>>
  >;
}

export function removeEntry<O, R extends Desc<O, string, Record<string, any>, string, false>, ID extends string>(
  expr: DirtyExpr<O, R>,
  id: ID,
): DirtyExpr<O, Desc<O, IdOf<R>, RemoveAt<AdjOf<R>, ID>, CtrOf<R>, false>> {
  const adj = { ...expr.__adj };
  delete adj[id];
  return makeExpr(expr.__id, adj, expr.__counter) as DirtyExpr<
    O,
    Desc<O, IdOf<R>, RemoveAt<AdjOf<R>, ID>, CtrOf<R>, false, BuildRev<RemoveAt<AdjOf<R>, ID>>>
  >;
}

export function swapEntry<O, R extends Desc<O, string, Record<string, any>, string, false>, ID extends string, E extends NodeEntry<string, readonly string[], any>>(
  expr: DirtyExpr<O, R>,
  id: ID,
  entry: E,
): DirtyExpr<O, Desc<O, IdOf<R>, ReplaceAt<AdjOf<R>, ID, E>, CtrOf<R>, false>> {
  const meta = entry as any;
  const adj = {
    ...expr.__adj,
    [id]: {
      kind: entry.kind,
      children: [...entry.children],
      out: entry.out,
      fields: meta.fields,
      data: meta.data,
    },
  };
  return makeExpr(expr.__id, adj, expr.__counter) as DirtyExpr<
    O,
    Desc<O, IdOf<R>, ReplaceAt<AdjOf<R>, ID, E>, CtrOf<R>, false, BuildRev<ReplaceAt<AdjOf<R>, ID, E>>>
  >;
}

export function rewireChildren<O, R extends Desc<O, string, Record<string, any>, string, false>>(
  expr: DirtyExpr<O, R>, oldRef: string, newRef: string,
): DirtyExpr<O, R> {
  return rewireChildrenExcept(expr, oldRef, newRef, new Set());
}

function rewireChildrenExcept<O, R extends Desc<O, string, Record<string, any>, string, false>>(
  expr: DirtyExpr<O, R>,
  oldRef: string,
  newRef: string,
  skipIds: Set<string>,
): DirtyExpr<O, R> {
  const adj: RuntimeAdj = { ...expr.__adj };
  for (const [id, e] of Object.entries(adj)) {
    if (isAlias(e) || id.startsWith("@") || skipIds.has(id)) continue;
    const children = e.children.map((c) => (c === oldRef ? newRef : c));
    const fields = e.fields
      ? Object.fromEntries(
          Object.entries(e.fields).map(([k, v]) => [
            k,
            Array.isArray(v) ? v.map((x) => (x === oldRef ? newRef : x)) : v === oldRef ? newRef : v,
          ]),
        )
      : undefined;
    adj[id] = { ...e, children, fields };
  }
  return makeExpr(expr.__id, adj, expr.__counter) as DirtyExpr<O, R>;
}

export function setRoot<O, R extends Desc<O, string, Record<string, any>, string, false>, ID extends string>(
  expr: DirtyExpr<O, R>,
  rootId: ID,
): DirtyExpr<O, Desc<O, ID, AdjOf<R>, CtrOf<R>, false, RevOf<R>>> {
  return makeExpr(rootId, { ...expr.__adj }, expr.__counter) as DirtyExpr<
    O,
    Desc<O, ID, AdjOf<R>, CtrOf<R>, false, RevOf<R>>
  >;
}

export function gc<O, R extends Desc<O, string, Record<string, any>, string, false>>(
  expr: DirtyExpr<O, R>,
): DirtyExpr<
  O,
  Desc<
    O,
    IdOf<R>,
    GCAdjBidir<AdjOf<R>, RevOf<R>, IdOf<R>>,
    CtrOf<R>,
    false,
    BuildRev<GCAdjBidir<AdjOf<R>, RevOf<R>, IdOf<R>>>
  >
> {
  const live = new Set<string>();
  const stack = [expr.__id];
  while (stack.length) {
    const id = stack.pop() as string;
    if (live.has(id)) continue;
    live.add(id);
    const e = expr.__adj[id];
    if (!e || isAlias(e)) continue;
    for (const c of e.children) stack.push(c);
  }
  for (const [k, e] of Object.entries(expr.__adj)) {
    if (isAlias(e) && live.has(e.target)) live.add(k);
  }
  const adj: RuntimeAdj = {};
  for (const [k, e] of Object.entries(expr.__adj)) if (live.has(k)) adj[k] = e;
  return makeExpr(expr.__id, adj, expr.__counter) as DirtyExpr<
    O,
    Desc<
      O,
      IdOf<R>,
      GCAdjBidir<AdjOf<R>, RevOf<R>, IdOf<R>>,
      CtrOf<R>,
      false,
      BuildRev<GCAdjBidir<AdjOf<R>, RevOf<R>, IdOf<R>>>
    >
  >;
}

export function commit<O, R extends Desc<O, string, Record<string, any>, string, false>>(
  expr: DirtyExpr<O, R>,
): Expr<O, Desc<O, IdOf<R>, AdjOf<R>, CtrOf<R>, true>> {
  if (!(expr.__id in expr.__adj)) throw new Error(`commit: root '${expr.__id}' missing`);
  for (const [id, e] of Object.entries(expr.__adj)) {
    if (isAlias(e)) {
      if (!(e.target in expr.__adj)) throw new Error(`commit: alias '${id}' target '${e.target}' missing`);
      continue;
    }
    for (const c of e.children) if (!(c in expr.__adj)) throw new Error(`commit: node '${id}' refs missing '${c}'`);
  }
  return makeExpr(expr.__id, { ...expr.__adj }, expr.__counter) as Expr<
    O,
    Desc<O, IdOf<R>, AdjOf<R>, CtrOf<R>, true>
  >;
}

export function commitTyped<O, R extends Desc<O, string, Record<string, any>, string, false>>(
  expr: DirtyExpr<O, R>,
): Expr<
  O,
  Desc<
    O,
    IdOf<R>,
    GCAdjBidir<AdjOf<R>, RevOf<R>, IdOf<R>>,
    CtrOf<R>,
    true,
    BuildRev<GCAdjBidir<AdjOf<R>, RevOf<R>, IdOf<R>>>
  >
> {
  return commit(gc(expr as any)) as any;
}

type PredEval = (e: RuntimeNode, id: string, adj: RuntimeAdj) => boolean;
export type Pred = { eval: PredEval };
export type KindPred<K extends string> = Pred & { tag: "kind"; kind: K };
export type KindGlobPred<P extends string> = Pred & { tag: "glob"; prefix: P };
export type NamePred<N extends string> = Pred & { tag: "name"; name: N };
export type LeafPred = Pred & { tag: "leaf" };
export type CountPred<N extends number> = Pred & { tag: "count"; count: N };
export type NotPred<P extends Pred> = Pred & { tag: "not"; inner: P };
export type AndPred<A extends Pred, B extends Pred> = Pred & { tag: "and"; left: A; right: B };
export type OrPred<A extends Pred, B extends Pred> = Pred & { tag: "or"; left: A; right: B };

export function detachChildRef<O, R extends Desc<O, string, Record<string, any>, string, false>>(
  expr: DirtyExpr<O, R>,
  oldRef: string,
): DirtyExpr<O, R> {
  const adj: RuntimeAdj = { ...expr.__adj };
  for (const [id, e] of Object.entries(adj)) {
    if (isAlias(e) || id.startsWith("@")) continue;
    if (!e.children.includes(oldRef)) continue;
    const children = e.children.filter((c) => c !== oldRef);
    const fields = e.fields
      ? (() => {
          const out: Record<string, string | string[]> = {};
          for (const [k, v] of Object.entries(e.fields)) {
            if (Array.isArray(v)) {
              out[k] = v.filter((x) => x !== oldRef);
            } else if (v !== oldRef) {
              out[k] = v;
            }
          }
          return out;
        })()
      : undefined;
    adj[id] = { ...e, children, fields };
  }
  return makeExpr(expr.__id, adj, expr.__counter) as DirtyExpr<O, R>;
}

spike-ur-demo.ts

import { defaults, foldAST, mvfm } from "./packages/core/src";
import { num } from "./packages/core/src/plugins/num";
import { semiring } from "./packages/core/src/plugins/semiring";
import {
  AdjOf,
  addEntry,
  commitTyped,
  commit,
  dirty,
  fromTypedAdj,
  gc,
  named,
  removeEntry,
  type NodeEntry,
} from "./spike-ur-core";
import { dagql } from "./spike-ur-fluent";
import { mapWhere, replaceWhere, spliceWhere, wrapByName, wrapWhere } from "./spike-ur-ops";
import {
  byKind,
  byKindGlob,
  byName,
  hasChildCount,
  isLeaf,
  not,
} from "./spike-ur-predicates";
import { toAST, toDAG, withExpr } from "./spike-ur-bridge";
import { freshCtx } from "./spike-ur-buildctx";
import type { BuildRev, GCAdjBidir } from "./spike-ur-types";

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

async function main(): Promise<void> {
  console.log("=== Ur-spike: compile-time typed adjacency ===");

  const typed = fromTypedAdj<number, "c", {
    a: NodeEntry<"num/literal", [], number>;
    b: NodeEntry<"num/literal", [], number>;
    c: NodeEntry<"num/add", ["a", "b"], number>;
  }, "d">(
    "c",
    {
      a: { kind: "num/literal", children: [], out: 3 },
      b: { kind: "num/literal", children: [], out: 4 },
      c: { kind: "num/add", children: ["a", "b"], out: 7 },
    },
    "d",
  );

  const typedDirty = dirty(typed);
  addEntry(typedDirty, "x", { kind: "num/literal", children: [], out: 5 });

  // @ts-expect-error children must be string IDs
  addEntry(typedDirty, "bad", { kind: "num/literal", children: [42], out: 0 });

  console.log("type-level checks compile as expected");

  type BidirAdj = {
    a: NodeEntry<"core/literal", [], number>;
    b: NodeEntry<"core/literal", [], number>;
    c: NodeEntry<"num/add", ["a", "b"], number>;
    x: NodeEntry<"core/literal", [], number>;
  };
  type BidirRev = BuildRev<BidirAdj>;
  type BidirGC = GCAdjBidir<BidirAdj, BidirRev, "c">;
  const _bidirKeepsC: BidirGC["c"]["kind"] = "num/add";
  // @ts-expect-error orphan x should be removed by bidir type-level gc
  const _bidirRemovesX: BidirGC["x"]["kind"] = "core/literal";

  // commitTyped: compile-time graph validation path
  const _typedCommitOk = commitTyped(typedDirty);

  console.log("=== Ur-spike: public dirty/commit primitives ===");
  const broken = removeEntry(typedDirty, "a");
  let rejected = false;
  try {
    commit(broken);
  } catch {
    rejected = true;
  }
  assert(rejected, "commit should reject missing child refs");

  const repaired = addEntry(broken, "a", { kind: "num/literal", children: [], out: 3 });
  const clean = commit(gc(repaired));
  assert(clean.__id === "c", "root stays c after repair");

  console.log("dirty/commit path validated");

  console.log("=== Ur-spike: mapWhere and predicate composition ===");
  const mapped = mapWhere(clean, byKind("num/add"), (e) => ({ ...e, kind: "num/mul" as const }));
  type MappedDesc = (typeof mapped) extends import("./spike-ur-core").Expr<any, infer R> ? R : never;
  type MappedAdj = AdjOf<MappedDesc>;
  const _mappedKind: MappedAdj["c"]["kind"] = "num/mul";
  // @ts-expect-error c is no longer num/add after mapWhere
  const _mappedKindWrong: MappedAdj["c"]["kind"] = "num/add";

  const onlyLeafNums = dagql(mapped)
    .mapWhere(
      byKindGlob("num/"),
      (e, _id, _dag) => (e.children.length === 0 ? { ...e, out: (e.out as number) + 1 } : e),
    )
    .result();

  assert((onlyLeafNums.__adj.a as any).out === 4, "leaf a incremented");
  assert((onlyLeafNums.__adj.b as any).out === 5, "leaf b incremented");
  assert((onlyLeafNums.__adj.c as any).kind === "num/mul", "add replaced with mul");

  const filtered = dagql(onlyLeafNums)
    .replaceWhere(not(isLeaf()), "num/mul")
    .replaceWhere(hasChildCount(2), "num/mul")
    .result();
  assert((filtered.__adj.c as any).kind === "num/mul", "predicate combinators applied");

  console.log("mapWhere and predicates validated");

  console.log("=== Ur-spike: real usage with current API shape ===");
  const app = mvfm(num, semiring);
  const prog = app(($) => $.mul($.add(3, 4), 5));
  const interp = defaults(app);

  const base = await foldAST(interp, prog);
  assert(base === 35, `baseline expected 35, got ${String(base)}`);

  const bridged = toDAG(prog.ast);
  const transformedExpr = dagql(bridged.expr)
    .replaceWhere(byKind("num/add"), "num/mul")
    .result();

  const transformedAst = toAST(withExpr(bridged, transformedExpr));
  const transformedResult = await foldAST(interp, transformedAst);
  assert(transformedResult === 60, `transformed expected 60, got ${String(transformedResult)}`);

  console.log("app -> prog -> dagql transform -> foldAST works");

  console.log("=== Ur-spike: BuildCtx direct typed construction ===");
  const $ = freshCtx();
  const [l3, $1] = $.numLit(3);
  const [l4, $2] = $1.numLit(4);
  const [sum, _] = $2.add(l3, l4);
  const sumAst = toAST({ expr: sum });
  const sumResult = await foldAST(interp, sumAst);
  assert(sumResult === 7, `BuildCtx sum expected 7, got ${String(sumResult)}`);

  console.log("=== Ur-spike: named node targeting ===");
  const namedExpr = named("sum-node", transformedExpr);
  const retargeted = replaceWhere(namedExpr, byName("sum-node"), "num/add");
  assert((retargeted.__adj[retargeted.__id] as any).kind === "num/add", "byName retargeted named root");
  assert((retargeted.__adj["@sum-node"] as any).target === retargeted.__id, "alias remains stable");

  console.log("=== Ur-spike: wrapWhere root rewiring ===");
  const wrappedRoot = wrapWhere(typed, byKind("num/add"), "debug/wrap");
  assert(wrappedRoot.__id !== typed.__id, "wrapping root rewires root id to wrapper");
  assert((wrappedRoot.__adj[wrappedRoot.__id] as any).children[0] === typed.__id, "wrapper points to old root");

  console.log("=== Ur-spike: splice leaf rewiring ===");
  const leafCase = fromTypedAdj<number, "d", {
    a: NodeEntry<"num/literal", [], number>;
    b: NodeEntry<"num/literal", [], number>;
    c: NodeEntry<"debug/marker", [], number>;
    d: NodeEntry<"num/add", ["a", "b", "c"], number>;
  }, "e">("d", {
    a: { kind: "num/literal", children: [], out: 1 },
    b: { kind: "num/literal", children: [], out: 2 },
    c: { kind: "debug/marker", children: [], out: 0 },
    d: { kind: "num/add", children: ["a", "b", "c"], out: 3, fields: { values: ["a", "b", "c"] }, data: {} } as any,
  }, "e");
  const leafSpliced = spliceWhere(leafCase, byKind("debug/marker"));
  assert((leafSpliced.__adj.d as any).children.length === 2, "leaf splice removes parent reference");
  assert((leafSpliced.__adj.d as any).children.includes("c") === false, "leaf child id removed");

  console.log("=== Ur-spike: wrapByName typed path ===");
  const wrappedByName = wrapByName(namedExpr, "sum-node", "debug/wrap-one");
  assert((wrappedByName.__adj[wrappedByName.__id] as any).kind === "debug/wrap-one", "wrapByName wrapped named root");

  console.log("named transforms validated");
  console.log("\nAll ur-spike checks passed.");
}

main().catch((err) => {
  console.error(err);
  process.exit(1);
});

spike-ur-fluent.ts

import {
  type Desc,
  type Expr,
  type NodeEntry,
  type Pred,
  type RuntimeNode,
} from "./spike-ur-core";
import { type DagView, mapWhere, replaceWhere, spliceWhere, wrapWhere } from "./spike-ur-ops";

export type DagQL<E extends Expr<any, any>> = {
  mapWhere<P extends Pred, NE extends NodeEntry<string, readonly string[], any>>(
    pred: P,
    fn: (entry: RuntimeNode, id: string, dag: DagView) => NE,
  ): DagQL<ReturnType<typeof mapWhere<any, any, P, NE>>>;
  wrapWhere(pred: Pred, kind: string): DagQL<ReturnType<typeof wrapWhere<any, any>>>;
  replaceWhere<P extends Pred>(pred: P, kind: string): DagQL<ReturnType<typeof replaceWhere<any, any, P>>>;
  spliceWhere(pred: Pred): DagQL<ReturnType<typeof spliceWhere<any, any>>>;
  result(): E;
};

export function dagql<E extends Expr<any, any>>(expr: E): DagQL<E> {
  return {
    mapWhere(pred, fn) {
      return dagql(mapWhere(expr as any, pred, fn as any) as any);
    },
    wrapWhere(pred, kind) {
      return dagql(wrapWhere(expr as any, pred, kind) as any);
    },
    replaceWhere(pred, kind) {
      return dagql(replaceWhere(expr as any, pred, kind) as any);
    },
    spliceWhere(pred) {
      return dagql(spliceWhere(expr as any, pred) as any);
    },
    result() {
      return expr;
    },
  };
}

spike-ur-ops.ts

import {
  addEntry,
  commitTyped,
  commit,
  detachChildRef,
  type RevOf,
  gc,
  dirty,
  removeEntry,
  rewireChildren,
  setRoot,
  swapEntry,
  type AdjOf,
  type CtrOf,
  type Desc,
  type DirtyExpr,
  type Expr,
  type IdOf,
  type NodeEntry,
  type Pred,
  type RuntimeAdj,
  type RuntimeNode,
} from "./spike-ur-core";
import type { BuildRev, GCAdjBidir, MapAdj, MapOut, MatchingEntries, SelectKeys, WrapOneResult } from "./spike-ur-types";

type RuntimeAlias = { kind: "@alias"; target: string; name: string };
function isAlias(v: RuntimeNode | RuntimeAlias): v is RuntimeAlias {
  return (v as RuntimeAlias).kind === "@alias";
}

function nextIdRuntime(s: string): string {
  const chars = s.split("");
  for (let i = chars.length - 1; i >= 0; i--) {
    if (chars[i] !== "z") {
      chars[i] = String.fromCharCode(chars[i].charCodeAt(0) + 1);
      return chars.join("");
    }
    chars[i] = "a";
  }
  return `a${chars.join("")}`;
}

export interface DagView {
  get(id: string): RuntimeNode | RuntimeAlias | undefined;
  nodeIds(): string[];
  parents(id: string): string[];
  resolve(name: string): string;
}

function view(adj: RuntimeAdj): DagView {
  const parents: Record<string, string[]> = {};
  for (const [id, e] of Object.entries(adj)) {
    if (isAlias(e)) continue;
    for (const c of e.children) (parents[c] ||= []).push(id);
  }
  return {
    get: (id) => adj[id],
    nodeIds: () => Object.keys(adj).filter((k) => !k.startsWith("@")),
    parents: (id) => parents[id] || [],
    resolve: (name) => ((adj[`@${name}`] as RuntimeAlias | undefined)?.target ?? ""),
  };
}

export function selectWhere<O, R extends Desc<O, string, Record<string, any>, string, true>, P extends Pred>(
  expr: Expr<O, R>,
  pred: P,
): Set<SelectKeys<AdjOf<R>, P> & string> {
  const ids = new Set<string>();
  for (const [id, e] of Object.entries(expr.__adj)) {
    if (!id.startsWith("@") && !isAlias(e) && pred.eval(e, id, expr.__adj)) ids.add(id);
  }
  return ids as Set<SelectKeys<AdjOf<R>, P> & string>;
}

export function mapWhere<O, R extends Desc<O, string, Record<string, any>, string, true>, P extends Pred, NE extends NodeEntry<string, readonly string[], any>>(
  expr: Expr<O, R>, pred: P, fn: (entry: MatchingEntries<AdjOf<R>, P> extends never ? RuntimeNode : MatchingEntries<AdjOf<R>, P>, id: SelectKeys<AdjOf<R>, P> & string, dag: DagView) => NE,
): Expr<MapOut<R, P, NE>, Desc<MapOut<R, P, NE>, IdOf<R>, GCAdjBidir<MapAdj<AdjOf<R>, P, NE>, BuildRev<MapAdj<AdjOf<R>, P, NE>>, IdOf<R>>, CtrOf<R>, true>> {
  const dag = view(expr.__adj);
  let out = dirty(expr) as DirtyExpr<O, Desc<O, string, Record<string, any>, string, false>>;
  for (const [id, e] of Object.entries(expr.__adj)) {
    if (id.startsWith("@") || isAlias(e) || !pred.eval(e, id, expr.__adj)) continue;
    const r = fn(e as any, id as any, dag);
    const merged = {
      kind: (r as any).kind,
      children: [...(r as any).children],
      out: (r as any).out,
      fields: (r as any).fields ?? e.fields,
      data: (r as any).data ?? e.data,
    };
    out = swapEntry(out, id, merged as any);
  }
  return commitTyped(out as any) as Expr<MapOut<R, P, NE>, Desc<MapOut<R, P, NE>, IdOf<R>, GCAdjBidir<MapAdj<AdjOf<R>, P, NE>, BuildRev<MapAdj<AdjOf<R>, P, NE>>, IdOf<R>>, CtrOf<R>, true>>;
}

export function replaceWhere<O, R extends Desc<O, string, Record<string, any>, string, true>, P extends Pred>(
  expr: Expr<O, R>, pred: P, kind: string,
): Expr<MapOut<R, P, NodeEntry<string, readonly string[], unknown>>, Desc<MapOut<R, P, NodeEntry<string, readonly string[], unknown>>, IdOf<R>, GCAdjBidir<MapAdj<AdjOf<R>, P, NodeEntry<string, readonly string[], unknown>>, BuildRev<MapAdj<AdjOf<R>, P, NodeEntry<string, readonly string[], unknown>>>, IdOf<R>>, CtrOf<R>, true>> {
  return mapWhere(expr, pred, (e: any) => ({
    kind,
    children: e.children,
    out: e.out,
    fields: e.fields,
    data: e.data,
  } as any));
}

export function wrapWhere<O, R extends Desc<O, string, Record<string, any>, string, true>>(
  expr: Expr<O, R>, pred: Pred, wrapperKind: string,
): Expr<O, Desc<O, string, Record<string, any>, string, true>> {
  let out = dirty(expr) as DirtyExpr<O, Desc<O, string, Record<string, any>, string, false>>;
  let counter = expr.__counter;
  const wrapped: Record<string, string> = {};
  for (const id of Array.from(selectWhere(expr, pred))) {
    const wid = counter;
    counter = nextIdRuntime(counter);
    const node = expr.__adj[id] as RuntimeNode;
    out = addEntry(out, wid, { kind: wrapperKind, children: [id], out: node.out, fields: { inner: id }, data: {} } as any);
    out = rewireChildren(out, id, wid);
    out = swapEntry(out, wid, { kind: wrapperKind, children: [id], out: node.out, fields: { inner: id }, data: {} } as any);
    wrapped[id] = wid;
  }
  out = setRoot(out, wrapped[expr.__id] ?? expr.__id);
  const committed = commitTyped(out as any) as any;
  return { ...committed, __counter: counter } as Expr<O, Desc<O, string, Record<string, any>, string, true>>;
}

export function wrapByName<
  O,
  R extends Desc<O, string, Record<string, any>, string, true>,
  Name extends string,
  WrapperKind extends string,
>(
  expr: Expr<O, R>,
  name: Name,
  wrapperKind: WrapperKind,
): Expr<O, WrapOneResult<R, SelectKeys<AdjOf<R>, import("./spike-ur-core").NamePred<Name>> & string, WrapperKind>> {
  const target = ((expr.__adj[`@${name}`] as RuntimeAlias | undefined)?.target ?? "") as string;
  if (!target) throw new Error(`wrapByName: missing alias @${name}`);
  return wrapWhere(expr, { eval: (_e, id) => id === target } as Pred, wrapperKind) as any;
}

export function spliceWhere<O, R extends Desc<O, string, Record<string, any>, string, true>>(
  expr: Expr<O, R>, pred: Pred,
): Expr<O, Desc<O, string, Record<string, any>, string, true>> {
  let out = dirty(expr) as DirtyExpr<O, Desc<O, string, Record<string, any>, string, false>>;
  for (const id of Array.from(selectWhere(expr, pred))) {
    const e = out.__adj[id];
    if (!e || isAlias(e)) continue;
    if (e.children.length > 1) throw new Error(`spliceWhere: '${id}' has ${e.children.length} children`);
    const replacement = e.children[0] ?? null;
    if (replacement) out = rewireChildren(out, id, replacement);
    else out = detachChildRef(out, id);
    out = removeEntry(out, id);
    if (expr.__id === id && replacement) out = setRoot(out, replacement);
  }
  return commitTyped(out as any) as any;
}

spike-ur-predicates.ts

import type {
  AndPred,
  CountPred,
  KindGlobPred,
  KindPred,
  LeafPred,
  NamePred,
  NotPred,
  OrPred,
  Pred,
} from "./spike-ur-core";

export const byKind = <K extends string>(kind: K): KindPred<K> => ({
  tag: "kind",
  kind,
  eval: (e, _id) => e.kind === kind,
});

export const byKindGlob = <P extends string>(prefix: P): KindGlobPred<P> => ({
  tag: "glob",
  prefix,
  eval: (e, _id) => e.kind.startsWith(prefix),
});

export const byName = <N extends string>(name: N): NamePred<N> => ({
  tag: "name",
  name,
  eval: (_e, id, adj) => (adj[`@${name}`] as any)?.target === id,
});

export const isLeaf = (): LeafPred => ({
  tag: "leaf",
  eval: (e, _id) => e.children.length === 0,
});

export const hasChildCount = <N extends number>(count: N): CountPred<N> => ({
  tag: "count",
  count,
  eval: (e, _id) => e.children.length === count,
});

export const not = <P extends Pred>(inner: P): NotPred<P> => ({
  tag: "not",
  inner,
  eval: (e, id, adj) => !inner.eval(e, id, adj),
});

export const and = <A extends Pred, B extends Pred>(left: A, right: B): AndPred<A, B> => ({
  tag: "and",
  left,
  right,
  eval: (e, id, adj) => left.eval(e, id, adj) && right.eval(e, id, adj),
});

export const or = <A extends Pred, B extends Pred>(left: A, right: B): OrPred<A, B> => ({
  tag: "or",
  left,
  right,
  eval: (e, id, adj) => left.eval(e, id, adj) || right.eval(e, id, adj),
});

spike-ur-types.ts

import type {
  AdjOf,
  AndPred,
  CountPred,
  Desc,
  IdOf,
  KindGlobPred,
  KindPred,
  LeafPred,
  NameAlias,
  NamePred,
  NodeEntry,
  NotPred,
  OrPred,
  OutOf,
  CtrOf,
} from "./spike-ur-core";

type NodeLike = NodeEntry<string, readonly string[], unknown>;

type NameTarget<Adj, N extends string> = Adj extends Record<`@${N}`, infer A>
  ? A extends NameAlias<any, infer T, any>
    ? T & string
    : never
  : never;

export type EvalPred<P, Entry, ID extends string, Adj> =
  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 readonly []
            ? true
            : false
          : false
        : P extends CountPred<infer N extends number>
          ? Entry extends NodeEntry<any, infer C, any>
            ? C extends { length: N }
              ? true
              : false
            : false
          : P extends NamePred<infer N extends string>
            ? ID extends NameTarget<Adj, N>
              ? true
              : false
            : P extends NotPred<infer A>
              ? EvalPred<A, Entry, ID, Adj> extends true
                ? false
                : true
              : P extends AndPred<infer A, infer B>
                ? EvalPred<A, Entry, ID, Adj> extends true
                  ? EvalPred<B, Entry, ID, Adj>
                  : false
                : P extends OrPred<infer A, infer B>
                  ? EvalPred<A, Entry, ID, Adj> extends true
                    ? true
                    : EvalPred<B, Entry, ID, Adj>
                  : false;

export type SelectKeys<Adj, P> = keyof {
  [K in keyof Adj as K extends string
    ? Adj[K] extends NodeLike
      ? EvalPred<P, Adj[K], K, Adj> extends true
        ? K
        : never
      : never
    : never]: 1;
};

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

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

export type MapOut<R extends Desc<any, string, Record<string, any>, string, true>, P, NewEntry> =
  IdOf<R> extends keyof AdjOf<R>
    ? EvalPred<P, AdjOf<R>[IdOf<R>], IdOf<R> & string, AdjOf<R>> extends true
      ? NewEntry extends NodeEntry<any, any, infer NO>
        ? NO
        : OutOf<R>
      : OutOf<R>
    : OutOf<R>;

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

export type MissingRefs<Adj> = Exclude<ChildRefs<Adj>, keyof Adj>;
export type RootExists<R extends Desc<any, string, Record<string, any>, string, any>> = IdOf<R> extends keyof AdjOf<R> ? true : false;
export type IsValidGraph<R extends Desc<any, string, Record<string, any>, string, any>> =
  RootExists<R> extends true
    ? MissingRefs<AdjOf<R>> extends never
      ? true
      : false
    : false;

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

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

export type WrapOneResult<
  R extends Desc<any, string, Record<string, any>, string, true>,
  TargetID extends string,
  WrapperKind extends string,
> = Desc<
  OutOf<R>,
  IdOf<R> extends TargetID ? CtrOf<R> : IdOf<R>,
  RewireParents<AdjOf<R>, TargetID, CtrOf<R>> & Record<CtrOf<R>, NodeEntry<WrapperKind, readonly [TargetID], OutOf<R>>>,
  CtrOf<R>,
  true
>;

export type RevEntry<Parents extends readonly string[]> = {
  readonly parents: Parents;
};

type ParentOf<Adj, Child extends string> = {
  [K in keyof Adj]: Adj[K] extends NodeEntry<any, infer C extends readonly string[], any>
    ? Child extends C[number]
      ? K
      : never
    : never;
}[keyof Adj] & string;

export type BuildRev<Adj extends Record<string, any>> = {
  [K in keyof Adj]: K extends string ? RevEntry<readonly ParentOf<Adj, K>[]> : never;
};

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

export type IsLive<
  Rev extends Record<string, RevEntry<readonly string[]>>,
  Root extends string,
  K extends string,
  Visited extends string = never,
> = K extends Root
  ? true
  : K extends Visited
    ? false
    : K extends keyof Rev
      ? Rev[K] extends RevEntry<infer P extends readonly string[]>
        ? AnyParentLive<Rev, Root, P, Visited | K>
        : false
      : false;

export type GCAdjBidir<
  Adj extends Record<string, any>,
  Rev extends Record<string, RevEntry<readonly string[]>>,
  Root extends string,
> = {
  [K in keyof Adj as K extends string
    ? IsLive<Rev, Root, K> extends true
      ? K
      : never
    : never]: Adj[K];
};