Skip to content

#1 Persistent memory for AI coding agents based on real-world benchmarks

31.9 KB
Raw Blame
import { createHash, randomUUID } from "node:crypto";
import type { GraphEdge, GraphNode, GraphSnapshot, GraphRetrievalIndexControl, GraphRetrievalIndexRecord } from "../types.js";
import type { StateKV } from "./kv.js";
import { getGraphGeneration, pinGraphState, pinGraphStateGeneration } from "./graph-generation.js";
import { ensureGraphConsistency, noteGraphSnapshotWrite, withoutGraphRecovery } from "./graph-consistency.js";
import { isKeyedLockHeld, withKeyedLock } from "./keyed-mutex.js";
import { KV } from "./schema.js";

export const GRAPH_INDEX_MAX_ID_BYTES = 1024;
export const GRAPH_INDEX_MAX_RECORD_BYTES = 32 * 1024;
const MAX_CONTROL_BYTES = 8 * 1024;
const MAX_PROJECTION_BYTES = 16 * 1024;
const MAX_JOURNAL_BYTES = 8 * 1024 * 1024;
const MAX_POSTINGS = 192;
const CONTROL_KEY = "current";
export type GraphIndexRecordKind = "node" | "edge" | "history";
export type GraphPostingKind = "name" | "character" | "observation" | "edgeObservation" | "edgeKey" | "adjacency" | "history" | "nodes" | "edges" | "historyEdges";
export type GraphNodeProjection = GraphNode & { indexIncomplete?: boolean };
export type GraphEdgeProjection = GraphEdge & { indexIncomplete?: boolean };
type PostingRoot = { head: string | null; count: number };
type PostingEntry = { id: string; previous: string | null; next: string | null };
type IndexWrite = { key: string; value: unknown };
type IndexJournal = { schema: 1; buildId: string; revision: number; writes: IndexWrite[]; next: GraphRetrievalIndexControl };

export class GraphIndexError extends Error {}
const bytes = (value: unknown) => Buffer.byteLength(JSON.stringify(value) ?? "", "utf8");
const hash = (value: string) => createHash("sha256").update(JSON.stringify(value)).digest("hex");
const validId = (value: unknown): value is string => typeof value === "string" && value.length > 0 && Buffer.byteLength(value, "utf8") <= GRAPH_INDEX_MAX_ID_BYTES;
const finiteCount = (value: unknown): value is number => Number.isSafeInteger(value) && (value as number) >= 0;
const boundedOption = (value: number | undefined, fallback: number, max: number) => Number.isFinite(value) ? Math.min(max, Math.max(1, Math.floor(value!))) : fallback;
const graphLock = <T>(fn: () => Promise<T>) => isKeyedLockHeld("graph:persist") ? fn() : withKeyedLock("graph:persist", fn);
async function lock<T>(state: StateKV, fn: () => Promise<T>): Promise<T> {
  const key = `graph:retrieval:${await getGraphGeneration(state) ?? "legacy"}`;
  return isKeyedLockHeld(key) ? fn() : withKeyedLock(key, fn);
}
const WAIT_FOR_BATCH = Symbol("graph index batch");
const NODE_TYPES = new Set(["file", "function", "concept", "error", "decision", "pattern", "library", "person", "project", "preference", "location", "organization", "event"]);
const EDGE_TYPES = new Set(["uses", "imports", "modifies", "causes", "fixes", "depends_on", "related_to", "works_at", "prefers", "blocked_by", "caused_by", "optimizes_for", "rejected", "avoids", "located_in", "succeeded_by"]);
export const normalizeGraphIndexText = (value: string): string => value.normalize("NFKC").toLowerCase();
export const graphEdgeLookupKey = (edge: Pick<GraphEdge, "sourceNodeId" | "targetNodeId" | "type">): string => JSON.stringify([edge.sourceNodeId, edge.targetNodeId, edge.type]);
const token = (kind: GraphPostingKind, value: string) => hash(`${kind}\0${kind === "name" || kind === "character" ? normalizeGraphIndexText(value) : value}`);
const recordKey = (buildId: string, kind: GraphIndexRecordKind, id: string) => `${buildId}:record:${kind}:${hash(id)}`;
const rootKey = (buildId: string, posting: string) => `${buildId}:root:${posting}`;
const entryKey = (buildId: string, posting: string, id: string) => `${buildId}:entry:${posting}:${id}`;
const countKey = (kind: GraphIndexRecordKind) => kind === "node" ? "nodes" : kind === "edge" ? "edges" : "historyEdges";

function validateControl(value: GraphRetrievalIndexControl): void {
  if (bytes(value) > MAX_CONTROL_BYTES || value.schema !== 2 || typeof value.buildId !== "string" || !/^[a-zA-Z0-9_-]{1,128}$/.test(value.buildId) ||
      !["building", "ready", "paused"].includes(value.status) ||
      ![value.revision, value.nodes, value.edges, value.historyEdges, value.incompleteRecords, value.otherTypes].every(finiteCount) ||
      !value.nodesByType || !value.edgesByType ||
      Object.entries(value.nodesByType).some(([type, count]) => (!NODE_TYPES.has(type) && type !== "other") || !finiteCount(count)) ||
      Object.entries(value.edgesByType).some(([type, count]) => (!EDGE_TYPES.has(type) && type !== "other") || !finiteCount(count)) ||
      (value.batchPending !== undefined && typeof value.batchPending !== "boolean") ||
      (value.pending && (!["node", "edge", "history"].includes(value.pending.kind) || !validId(value.pending.id)))) {
    throw new GraphIndexError("Invalid graph retrieval index control; run explicit graph-index migration");
  }
}

export async function getGraphIndexStatus(state: StateKV): Promise<GraphRetrievalIndexControl | null> {
  const value = await state.get<GraphRetrievalIndexControl>(KV.graphRetrievalControl, CONTROL_KEY);
  if (value !== null && value !== undefined) validateControl(value);
  return value ?? null;
}

export async function initializeGraphIndex(state: StateKV, options: { status: "building" | "ready"; buildId?: string }): Promise<GraphRetrievalIndexControl> {
  const kv = await pinGraphState(state);
  return lock(kv, async () => {
    const value: GraphRetrievalIndexControl = { schema: 2, buildId: options.buildId ?? randomUUID(), status: options.status,
      revision: 0, nodes: 0, edges: 0, historyEdges: 0, incompleteRecords: 0, nodesByType: {}, edgesByType: {}, otherTypes: 0, updatedAt: new Date().toISOString() };
    validateControl(value);
    const previous = await kv.get<GraphRetrievalIndexControl>(KV.graphRetrievalControl, CONTROL_KEY);
    if (previous?.buildId === value.buildId) throw new GraphIndexError("A graph index rebuild requires a new build ID");
    await kv.set(KV.graphRetrievalControl, CONTROL_KEY, value);
    return value;
  });
}

function project(kind: GraphIndexRecordKind, id: string, input: unknown): GraphRetrievalIndexRecord | null {
  if (input === null || input === undefined) return null;
  const source = input as Record<string, unknown>;
  if (!source || typeof source !== "object" || Array.isArray(source) || !validId(id) || source.id !== id) {
    return { row: null, postings: [], incomplete: true };
  }
  if (source.stale === true) return { row: null, postings: [], incomplete: false };
  let incomplete = false;
  const text = (value: unknown, max = 512): string => {
    if (typeof value !== "string") { incomplete = true; return ""; }
    const result = Array.from(value.slice(0, max * 2)).slice(0, max).join("");
    if (result !== value) incomplete = true;
    return result;
  };
  const ids: string[] = [];
  if (!Array.isArray(source.sourceObservationIds)) incomplete = true;
  else for (const value of source.sourceObservationIds.slice(0, 512)) {
    if (!validId(value)) { incomplete = true; continue; }
    if (ids.includes(value)) continue;
    if (ids.length >= 128) { incomplete = true; break; }
    ids.push(value);
  }
  if (Array.isArray(source.sourceObservationIds) && source.sourceObservationIds.length > 512) incomplete = true;
  const common = { id, type: text(source.type, 64), sourceObservationIds: ids, createdAt: text(source.createdAt, 64) };
  let row: GraphNodeProjection | GraphEdgeProjection;
  if (kind === "node") {
    const properties: Record<string, unknown> = {};
    if (!source.properties || typeof source.properties !== "object" || Array.isArray(source.properties)) incomplete = true;
    else for (const key in source.properties) {
      if (!Object.hasOwn(source.properties, key)) continue;
      if (Object.keys(properties).length >= 32) { incomplete = true; break; }
      const value = (source.properties as Record<string, unknown>)[key];
      if (key.length > 128) { incomplete = true; continue; }
      if (typeof value === "string") Object.defineProperty(properties, key, { value: text(value), enumerable: true, writable: true, configurable: true });
      else if (typeof value === "boolean" || (typeof value === "number" && Number.isFinite(value))) Object.defineProperty(properties, key, { value, enumerable: true, writable: true, configurable: true });
      else incomplete = true;
    }
    const aliases = Array.isArray(source.aliases) ? source.aliases.slice(0, 16).filter((v): v is string => typeof v === "string").map((v) => text(v)) : [];
    if (Array.isArray(source.aliases) && aliases.length !== source.aliases.length) incomplete = true;
    row = { ...common, type: common.type as GraphNode["type"], name: text(source.name), properties, ...(aliases.length ? { aliases } : {}),
      ...(typeof source.updatedAt === "string" ? { updatedAt: text(source.updatedAt, 64) } : {}) };
  } else {
    if (!validId(source.sourceNodeId) || !validId(source.targetNodeId)) return { row: null, postings: [], incomplete: true };
    const edge: GraphEdgeProjection = { ...common, type: common.type as GraphEdge["type"], sourceNodeId: source.sourceNodeId,
      targetNodeId: source.targetNodeId, weight: typeof source.weight === "number" && Number.isFinite(source.weight) ? source.weight : 0 };
    if (edge.weight !== source.weight) incomplete = true;
    for (const key of ["tcommit", "tvalid", "tvalidEnd", "supersededBy"] as const) if (typeof source[key] === "string") edge[key] = text(source[key], key === "supersededBy" ? 1024 : 64);
    if (typeof source.version === "number" && Number.isFinite(source.version)) edge.version = source.version;
    if (typeof source.isLatest === "boolean") edge.isLatest = source.isLatest;
    if (source.context && typeof source.context === "object" && !Array.isArray(source.context)) {
      const context = source.context as Record<string, unknown>;
      edge.context = {};
      for (const key of ["reasoning", "sentiment"] as const) if (typeof context[key] === "string") edge.context[key] = text(context[key]);
      if (typeof context.confidence === "number" && Number.isFinite(context.confidence)) edge.context.confidence = context.confidence;
      if (context.alternatives !== undefined || context.situationalFactors !== undefined) incomplete = true;
    }
    row = edge;
  }
  while (bytes(row) > MAX_PROJECTION_BYTES - 64) {
    incomplete = true;
    if ("properties" in row && Object.keys(row.properties).length) delete row.properties[Object.keys(row.properties).at(-1)!];
    else if ("aliases" in row && row.aliases?.length) row.aliases.pop();
    else if ("context" in row && row.context) delete row.context;
    else if (row.sourceObservationIds.length) row.sourceObservationIds.pop();
    else return { row: null, postings: [], incomplete: true };
  }
  const postings = new Set<string>([token(countKey(kind), "")]);
  if (kind === "node") {
    const node = row as GraphNodeProjection;
    for (const value of [node.name, ...(node.aliases ?? [])]) postings.add(token("name", value));
    const searchable = [node.name, ...(node.aliases ?? []), ...Object.values(node.properties).filter((v): v is string => typeof v === "string")];
    const characters = new Set(searchable.flatMap((value) => Array.from(normalizeGraphIndexText(value))));
    for (const character of characters) {
      if (postings.size >= MAX_POSTINGS - row.sourceObservationIds.length) { incomplete = true; break; }
      postings.add(token("character", character));
    }
    for (const observationId of row.sourceObservationIds) postings.add(token("observation", observationId));
  } else {
    const edge = row as GraphEdgeProjection;
    for (const nodeId of [edge.sourceNodeId, edge.targetNodeId]) postings.add(token(kind === "history" ? "history" : "adjacency", nodeId));
    if (kind === "edge") {
      if (edge.isLatest !== false) postings.add(token("edgeKey", graphEdgeLookupKey(edge)));
      for (const observationId of row.sourceObservationIds) postings.add(token("edgeObservation", observationId));
    }
  }
  if (incomplete) row.indexIncomplete = true;
  return { row, postings: [...postings], incomplete };
}

function validateRecord(value: GraphRetrievalIndexRecord): void {
  if (bytes(value) > GRAPH_INDEX_MAX_RECORD_BYTES || !Array.isArray(value.postings) || value.postings.length > MAX_POSTINGS ||
      value.postings.some((p) => !/^[a-f0-9]{64}$/.test(p)) || typeof value.incomplete !== "boolean") throw new GraphIndexError("Invalid graph retrieval record");
}

async function planRecord(kv: StateKV, control: GraphRetrievalIndexControl, kind: GraphIndexRecordKind, id: string, input: unknown): Promise<IndexJournal> {
  const writes = new Map<string, unknown>();
  const read = async <T>(key: string): Promise<T | null> => writes.has(key) ? writes.get(key) as T | null : kv.get<T>(KV.graphRetrievalData, key);
  const put = (key: string, value: unknown) => { if (bytes(value) > GRAPH_INDEX_MAX_RECORD_BYTES) throw new GraphIndexError("Graph retrieval index write exceeds record budget"); writes.set(key, value); };
  const key = recordKey(control.buildId, kind, id);
  const before = await read<GraphRetrievalIndexRecord>(key);
  if (before) validateRecord(before);
  const after = project(kind, id, input);
  if (after) validateRecord(after);
  const memberId = hash(id);
  const editPosting = async (posting: string, add: boolean) => {
    const rootId = rootKey(control.buildId, posting), itemId = entryKey(control.buildId, posting, memberId);
    const root = await read<PostingRoot>(rootId) ?? { head: null, count: 0 };
    const saved = await read<PostingEntry>(itemId);
    if (!finiteCount(root.count) || (root.head !== null && !/^[a-f0-9]{64}$/.test(root.head))) throw new GraphIndexError("Invalid graph posting root");
    if (add) {
      if (saved) return;
      if (root.head) {
        const headId = entryKey(control.buildId, posting, root.head), head = await read<PostingEntry>(headId);
        if (!head) throw new GraphIndexError("Missing graph posting head");
        put(headId, { ...head, previous: memberId });
      }
      put(itemId, { id, previous: null, next: root.head });
      put(rootId, { head: memberId, count: root.count + 1 });
    } else {
      if (!saved) return;
      if (saved.previous) {
        const previousId = entryKey(control.buildId, posting, saved.previous), previous = await read<PostingEntry>(previousId);
        if (!previous) throw new GraphIndexError("Missing previous graph posting entry");
        put(previousId, { ...previous, next: saved.next });
      } else {
        if (root.head !== memberId) throw new GraphIndexError("Invalid graph posting head link");
        root.head = saved.next;
      }
      if (saved.next) {
        const nextId = entryKey(control.buildId, posting, saved.next), next = await read<PostingEntry>(nextId);
        if (!next) throw new GraphIndexError("Missing next graph posting entry");
        put(nextId, { ...next, previous: saved.previous });
      }
      put(itemId, null);
      put(rootId, { head: root.head, count: Math.max(0, root.count - 1) });
    }
  };
  const oldPostings = new Set(before?.postings ?? []), newPostings = new Set(after?.postings ?? []);
  for (const posting of oldPostings) if (!newPostings.has(posting)) await editPosting(posting, false);
  for (const posting of newPostings) if (!oldPostings.has(posting)) await editPosting(posting, true);
  put(key, after);
  const { pending: _, ...clean } = control;
  const next = { ...clean, revision: control.revision + 1, updatedAt: new Date().toISOString() };
  const counted = (row: GraphNode | GraphEdge | null | undefined) => Boolean(row && (kind !== "edge" || (row as GraphEdge).isLatest !== false));
  next[countKey(kind)] += Number(counted(after?.row)) - Number(counted(before?.row));
  next.incompleteRecords += Number(Boolean(after?.incomplete)) - Number(Boolean(before?.incomplete));
  if (kind !== "history") {
    const field = kind === "node" ? "nodesByType" : "edgesByType";
    const known = kind === "node" ? NODE_TYPES : EDGE_TYPES;
    next[field] = { ...control[field] };
    for (const [row, amount] of [[before?.row, -1], [after?.row, 1]] as const) {
      if (!row || !counted(row)) continue;
      const type = known.has(row.type) ? row.type : "other";
      next[field][type] = (next[field][type] ?? 0) + amount;
      if (!next[field][type]) delete next[field][type];
      if (type === "other") next.otherTypes += amount;
    }
  }
  validateControl(next);
  const journal: IndexJournal = { schema: 1, buildId: control.buildId, revision: control.revision, writes: [...writes].map(([key, value]) => ({ key, value })), next };
  if (bytes(journal) > MAX_JOURNAL_BYTES) throw new GraphIndexError("Graph retrieval index journal exceeds payload budget");
  return journal;
}

async function applyJournal(kv: StateKV, control: GraphRetrievalIndexControl, journal: IndexJournal): Promise<void> {
  if (journal.schema !== 1 || journal.buildId !== control.buildId || journal.revision !== control.revision ||
      !Array.isArray(journal.writes) || journal.writes.length > 2048 || bytes(journal) > MAX_JOURNAL_BYTES || journal.next.buildId !== control.buildId ||
      journal.next.revision !== control.revision + 1 || journal.next.pending) throw new GraphIndexError("Invalid graph retrieval recovery journal");
  validateControl(journal.next);
  for (const write of journal.writes) {
    if (!write || typeof write.key !== "string" || !write.key.startsWith(`${control.buildId}:`) || write.key.length > 512 || bytes(write.value) > GRAPH_INDEX_MAX_RECORD_BYTES) {
      throw new GraphIndexError("Invalid graph retrieval recovery write");
    }
  }
  for (const write of journal.writes) {
    if (write.value === null) await kv.delete(KV.graphRetrievalData, write.key);
    else await kv.set(KV.graphRetrievalData, write.key, write.value);
  }
  await kv.set(KV.graphRetrievalControl, CONTROL_KEY, journal.next);
}

async function reconcilePending(kv: StateKV, control: GraphRetrievalIndexControl, input?: unknown): Promise<void> {
  if (!control.pending) return;
  const journalKey = `journal:${control.buildId}`;
  const saved = await kv.get<IndexJournal>(KV.graphRetrievalControl, journalKey);
  if (saved?.buildId === control.buildId && saved.revision === control.revision) return applyJournal(kv, control, saved);
  const { kind, id } = control.pending;
  const scope = kind === "node" ? KV.graphNodes : kind === "edge" ? KV.graphEdges : KV.graphEdgeHistory;
  const row = input === undefined ? await withoutGraphRecovery(() => kv.get(scope, id)) : input;
  const journal = await planRecord(kv, control, kind, id, row);
  await kv.set(KV.graphRetrievalControl, journalKey, journal);
  await applyJournal(kv, control, journal);
}

export async function recoverGraphIndex(state: StateKV, options: { allowSnapshotRecovery?: boolean } = {}): Promise<void> {
  const kv = await pinGraphState(state);
  await graphLock(() => lock(kv, async () => {
    let control = await getGraphIndexStatus(kv);
    if (control?.batchPending && options.allowSnapshotRecovery) {
      const snapshot = await withoutGraphRecovery(() => kv.get<GraphSnapshot>(KV.graphSnapshot, "current"));
      if (snapshot?.pendingMutation) {
        const generation = await getGraphGeneration(kv);
        const scope = generation === null ? KV.graphSnapshot : `${KV.graphSnapshot}:generation:${generation}`;
        noteGraphSnapshotWrite(kv, scope, "current");
        await ensureGraphConsistency(kv, scope);
      } else if (snapshot && !snapshot.dirty) {
        const { batchPending: _, ...clean } = control;
        await kv.set(KV.graphRetrievalControl, CONTROL_KEY, { ...clean, revision: clean.revision + 1 });
      }
      control = await getGraphIndexStatus(kv);
    }
    if (control?.pending) await reconcilePending(kv, control);
  }));
}

export async function reconcileGraphIndexRecord(state: StateKV, kind: GraphIndexRecordKind, id: string, row: GraphNode | GraphEdge | null, options: { readCanonical?: boolean } = {}): Promise<void> {
  const kv = await pinGraphState(state);
  await lock(kv, async () => {
    let control = await getGraphIndexStatus(kv);
    if (!control) throw new GraphIndexError("Graph retrieval index must be initialized explicitly");
    if (control.status === "paused") throw new GraphIndexError("Graph retrieval index is paused; run explicit migration");
    if (control.pending) { await reconcilePending(kv, control); control = (await getGraphIndexStatus(kv))!; }
    if (!validId(id)) throw new GraphIndexError("Graph record ID exceeds index migration budget");
    control = { ...control, pending: { kind, id } };
    await kv.set(KV.graphRetrievalControl, CONTROL_KEY, control);
    await reconcilePending(kv, control, options.readCanonical ? undefined : row);
  });
}

export async function mutateIndexedGraphRecord(state: StateKV, kind: GraphIndexRecordKind, id: string, transform: (row: GraphNode | GraphEdge | null) => GraphNode | GraphEdge | null | undefined): Promise<boolean> {
  const kv = await pinGraphState(state);
  return graphLock(() => lock(kv, async () => {
    const control = await getGraphIndexStatus(kv);
    if (!control || control.status !== "ready" || control.pending || control.batchPending) throw new GraphIndexError("Graph index is unavailable; retry the graph mutation after recovery");
    const scope = kind === "node" ? KV.graphNodes : kind === "edge" ? KV.graphEdges : KV.graphEdgeHistory;
    const current = await withoutGraphRecovery(() => kv.get<GraphNode | GraphEdge>(scope, id));
    const next = transform(current);
    if (next === undefined) return false;
    if (next === null) await withoutGraphRecovery(() => kv.delete(scope, id));
    else await withoutGraphRecovery(() => kv.set(scope, id, next));
    return true;
  }));
}

export async function finishGraphIndexBuild(state: StateKV, buildId: string): Promise<GraphRetrievalIndexControl> {
  const kv = await pinGraphState(state);
  return lock(kv, async () => {
    const current = await getGraphIndexStatus(kv);
    if (!current || current.buildId !== buildId || current.status === "paused" || current.pending || current.batchPending) throw new GraphIndexError("Graph index build is incomplete or superseded");
    const next = { ...current, status: "ready" as const, revision: current.revision + 1, updatedAt: new Date().toISOString() };
    await kv.set(KV.graphRetrievalControl, CONTROL_KEY, next);
    return next;
  });
}

function canonicalScope(scope: string): { kind: GraphIndexRecordKind; generation: string | null } | null {
  for (const [base, kind] of [[KV.graphNodes, "node"], [KV.graphEdges, "edge"], [KV.graphEdgeHistory, "history"]] as const) {
    if (scope === base) return { kind, generation: null };
    if (scope.startsWith(`${base}:generation:`)) return { kind, generation: scope.slice(base.length + 12) };
  }
  return null;
}

export async function withGraphIndexMutation<T>(state: StateKV, scope: string, id: string, mutate: () => Promise<T>): Promise<T> {
  const location = canonicalScope(scope);
  if (!location) return mutate();
  const kv = pinGraphStateGeneration(state, location.generation);
  const run = () => lock(kv, async () => {
    let control = await getGraphIndexStatus(kv);
    if (!control || control.status === "paused") return mutate();
    if (control.batchPending && !isKeyedLockHeld("graph:persist")) throw WAIT_FOR_BATCH;
    if (control.pending) { await reconcilePending(kv, control); control = (await getGraphIndexStatus(kv))!; }
    if (!validId(id)) {
      await kv.set(KV.graphRetrievalControl, CONTROL_KEY, { ...control, status: "paused", error: "Graph record ID exceeds bounded recovery budget", revision: control.revision + 1 });
      return mutate();
    }
    control = { ...control, pending: { kind: location.kind, id } };
    await kv.set(KV.graphRetrievalControl, CONTROL_KEY, control);
    const result = await mutate();
    await reconcilePending(kv, control);
    return result;
  });
  try { return await run(); } catch (error) {
    if (error !== WAIT_FOR_BATCH) throw error;
    return graphLock(run);
  }
}

export async function withGraphSnapshotIndexBarrier<T>(state: StateKV, scope: string, key: string, value: unknown, mutate: () => Promise<T>): Promise<T> {
  if (key !== "current" || !(scope === KV.graphSnapshot || scope.startsWith(`${KV.graphSnapshot}:generation:`))) return mutate();
  const kv = pinGraphStateGeneration(state, scope === KV.graphSnapshot ? null : scope.slice(KV.graphSnapshot.length + 12));
  return graphLock(() => lock(kv, async () => {
    const control = await getGraphIndexStatus(kv);
    if (!control) return mutate();
    const snapshot = value as GraphSnapshot | null;
    const dirty = !snapshot || typeof snapshot !== "object" || snapshot.version !== 1 || snapshot.dirty !== false || Boolean(snapshot.pendingMutation);
    if (dirty && !control.batchPending) await kv.set(KV.graphRetrievalControl, CONTROL_KEY, { ...control, batchPending: true });
    const result = await mutate();
    if (!dirty) {
      const after = await getGraphIndexStatus(kv);
      if (after?.batchPending && !after.pending) {
        const { batchPending: _, ...clean } = after;
        await kv.set(KV.graphRetrievalControl, CONTROL_KEY, { ...clean, revision: clean.revision + 1, updatedAt: new Date().toISOString() });
      }
    }
    return result;
  }));
}

export async function withGraphSnapshotUnknownMutation<T>(state: StateKV, scope: string, key: string, mutate: () => Promise<T>): Promise<T> {
  if (key !== "current" || !(scope === KV.graphSnapshot || scope.startsWith(`${KV.graphSnapshot}:generation:`))) return mutate();
  return graphLock(async () => {
    const result = await withGraphSnapshotIndexBarrier(state, scope, key, { dirty: true }, mutate);
    const snapshot = await withoutGraphRecovery(() => state.get(scope, key));
    return withGraphSnapshotIndexBarrier(state, scope, key, snapshot, async () => result);
  });
}

export interface GraphIndexReaderOptions { signal?: AbortSignal; maxReads?: number; maxBytes?: number; maxConcurrent?: number }
export class GraphIndexReader {
  readonly status: GraphRetrievalIndexControl;
  exhausted = false;
  private reads = 2;
  private readBytes: number;
  private active = 0;
  private waiting: Array<() => void> = [];
  private cache = new Map<string, Promise<unknown>>();
  private readonly maxReads: number;
  private readonly maxBytes: number;
  private readonly maxConcurrent: number;
  constructor(private state: StateKV, private generation: string | null, status: GraphRetrievalIndexControl, private options: GraphIndexReaderOptions) {
    this.status = status;
    this.readBytes = bytes(status);
    this.maxReads = boundedOption(options.maxReads, 512, 4096);
    this.maxBytes = boundedOption(options.maxBytes, 2 * 1024 * 1024, 16 * 1024 * 1024);
    this.maxConcurrent = boundedOption(options.maxConcurrent, 4, 8);
  }
  get remainingReads(): number { return Math.max(0, this.maxReads - this.reads - 2); }
  async read<T>(scope: string, key: string): Promise<T | null> {
    if (scope !== KV.graphRetrievalData) return this.readFresh<T>(scope, key);
    const cached = this.cache.get(key);
    if (cached) return cached as Promise<T | null>;
    const pending = this.readFresh<T>(scope, key);
    if (!this.exhausted) this.cache.set(key, pending);
    return pending;
  }
  async readFresh<T>(scope: string, key: string): Promise<T | null> {
    if (this.options.signal?.aborted || this.exhausted || this.remainingReads === 0 || this.readBytes >= this.maxBytes) { this.exhausted = true; return null; }
    this.reads++;
    if (this.active >= this.maxConcurrent) await new Promise<void>((resolve) => this.waiting.push(resolve));
    else this.active++;
    try {
      if (this.options.signal?.aborted || this.exhausted) { this.exhausted = true; return null; }
      const value = await this.state.get<T>(scope, key);
      const size = bytes(value);
      this.readBytes += size;
      if (this.readBytes > this.maxBytes || this.options.signal?.aborted) { this.exhausted = true; return null; }
      if (scope === KV.graphRetrievalData && size > GRAPH_INDEX_MAX_RECORD_BYTES) throw new GraphIndexError("Graph retrieval record exceeds payload budget");
      return value;
    } finally {
      const next = this.waiting.shift();
      if (next) next(); else this.active--;
    }
  }
  private async record(kind: GraphIndexRecordKind, id: string): Promise<GraphRetrievalIndexRecord | null> {
    if (!validId(id)) { this.exhausted = true; return null; }
    const value = await this.read<GraphRetrievalIndexRecord>(KV.graphRetrievalData, recordKey(this.status.buildId, kind, id));
    if (value) validateRecord(value);
    return value;
  }
  async getNode(id: string): Promise<GraphNodeProjection | null> { return (await this.record("node", id))?.row as GraphNodeProjection | null ?? null; }
  async getEdge(id: string): Promise<GraphEdgeProjection | null> { return (await this.record("edge", id))?.row as GraphEdgeProjection | null ?? null; }
  async getHistoryEdge(id: string): Promise<GraphEdgeProjection | null> { return (await this.record("history", id))?.row as GraphEdgeProjection | null ?? null; }
  async posting(kind: GraphPostingKind, key = "", options: { cursor?: string | null; limit?: number } = {}): Promise<{ ids: string[]; cursor: string | null; total: number }> {
    const posting = token(kind, key), root = await this.read<PostingRoot>(KV.graphRetrievalData, rootKey(this.status.buildId, posting));
    const inventoryCount = key === "" && (kind === "nodes" || kind === "edges" || kind === "historyEdges") ? this.status[kind] : undefined;
    if (!root) {
      if (!this.exhausted && inventoryCount) throw new GraphIndexError("Missing graph inventory root");
      return { ids: [], cursor: null, total: 0 };
    }
    if (!finiteCount(root.count) || (root.head !== null && !/^[a-f0-9]{64}$/.test(root.head)) ||
        (root.count === 0) !== (root.head === null)) throw new GraphIndexError("Invalid graph posting root");
    if (inventoryCount !== undefined && (kind === "edges" ? root.count < inventoryCount : root.count !== inventoryCount)) {
      throw new GraphIndexError("Graph inventory count does not match index control");
    }
    const prefix = `${this.status.buildId}.${this.status.revision}.${posting}.`;
    if (options.cursor && (!options.cursor.startsWith(prefix) || !/^[a-f0-9]{64}$/.test(options.cursor.slice(prefix.length)))) throw new GraphIndexError("Invalid or expired graph posting cursor");
    let current = options.cursor ? options.cursor.slice(prefix.length) : root.head;
    const limit = boundedOption(options.limit, 64, 128), ids: string[] = [], seen = new Set<string>();
    while (current && ids.length < limit) {
      if (seen.has(current)) throw new GraphIndexError("Cyclic graph posting entry");
      seen.add(current);
      const value = await this.read<PostingEntry>(KV.graphRetrievalData, entryKey(this.status.buildId, posting, current));
      if (!value) { if (this.exhausted) break; throw new GraphIndexError("Missing graph posting entry"); }
      if (!validId(value.id) || hash(value.id) !== current || (value.next !== null && !/^[a-f0-9]{64}$/.test(value.next))) throw new GraphIndexError("Invalid graph posting entry");
      ids.push(value.id); current = value.next;
    }
    return { ids, cursor: current ? `${prefix}${current}` : null, total: root.count };
  }
  async finish(): Promise<boolean> {
    if (this.options.signal?.aborted || this.reads + 2 > this.maxReads) return false;
    this.reads += 2;
    const current = await getGraphIndexStatus(this.state);
    const generation = await this.state.get<string>(KV.graphControl, "generation");
    if ((generation ?? null) !== this.generation) return false;
    this.readBytes += bytes(generation) + bytes(current);
    if (this.readBytes > this.maxBytes) { this.exhausted = true; return false; }
    return Boolean(current && current.status === "ready" && !current.pending && !current.batchPending && current.buildId === this.status.buildId && current.revision === this.status.revision);
  }
}

export async function createGraphIndexReader(state: StateKV, options: GraphIndexReaderOptions = {}): Promise<GraphIndexReader | null> {
  if (options.signal?.aborted) return null;
  const kv = await pinGraphState(state), generation = await getGraphGeneration(kv), status = await getGraphIndexStatus(kv);
  if (!status || status.status !== "ready" || status.pending || status.batchPending) return null;
  return new GraphIndexReader(kv, generation, status, options);
}