graph.ts (13731B)
1 // Tree Calculus graph reduction. Constructor nodes are immutable; only application 2 // thunks acquire memoized forwarding pointers. No host-stack recursive evaluator. 3 export type NodeId = number & { readonly __nodeId: unique symbol }; 4 export type Constructor = { readonly kind: 'leaf' } | { readonly kind: 'stem'; readonly child: NodeId } 5 | { readonly kind: 'fork'; readonly left: NodeId; readonly right: NodeId }; 6 function unreachable(value: never): never { throw new Error(`Unhandled graph variant: ${String(value)}`); } 7 type Node = Constructor | { kind: 'app'; fn: NodeId; arg: NodeId } | { kind: 'ref'; target: NodeId }; 8 type Frame = { kind: 'update'; app: NodeId } 9 | { kind: 'function'; arg: NodeId } 10 | { kind: 'left'; right: NodeId; arg: NodeId } 11 | { kind: 'argument'; leafCase: NodeId; stemCase: NodeId; forkCase: NodeId }; 12 export interface Budget { nodes: number; fuel: number; stack: number; } 13 export const DEFAULT_BUDGET: Readonly<Budget> = Object.freeze({ nodes: 250_000, fuel: 2_000_000, stack: 50_000 }); 14 export interface CollectionPolicy { threshold: number; } 15 export interface GraphStats { 16 nodes: number; work: number; fuel: number; allocations: number; peakNodes: number; 17 collections: number; reclaimed: number; gcWork: number; 18 } 19 // Trusted, structured-cloneable checkpoint; never forces lazy nodes or expands sharing. 20 export interface GraphCheckpoint { nodes: Array<[NodeId, Node]>; nextId: number; } 21 export class Graph { 22 readonly leaf = 0 as NodeId; 23 // Monotonic handles are never reused: collection cannot turn a stale handle 24 // into a reference to an unrelated constructor. Rebuild the Map when sweeping 25 // so its backing table also sheds dead capacity (subject to the JS host GC). 26 private heap = new Map<NodeId, Node>([[this.leaf, { kind: 'leaf' }]]); 27 private nextId = 1; 28 private peak = 1; 29 private collections = 0; 30 private reclaimed = 0; 31 private gcWork = 0; 32 private threshold: number | undefined; 33 private remaining: number; 34 private readonly budget: Budget; 35 private spent = 0; 36 constructor(budget: Partial<Budget> = {}, collection?: CollectionPolicy) { 37 this.budget = { ...DEFAULT_BUDGET, ...budget }; 38 for (const value of Object.values(this.budget)) 39 // Infinity is an explicit trusted-host experiment, never a bundle field. 40 if (value !== Infinity && (!Number.isSafeInteger(value) || value < 1)) throw new Error('Invalid graph budget'); 41 this.remaining = this.budget.fuel; 42 if (collection) { 43 if (!Number.isSafeInteger(collection.threshold) || collection.threshold < 2 || collection.threshold > this.budget.nodes) throw new Error('Invalid collection threshold'); 44 this.threshold = collection.threshold; 45 } 46 } 47 checkpoint(): GraphCheckpoint { return { nodes: [...this.heap], nextId: this.nextId }; } 48 static restore(checkpoint: GraphCheckpoint, budget: Partial<Budget> = {}, collection?: CollectionPolicy): Graph { 49 const graph = new Graph(budget, collection); 50 if (checkpoint.nodes.length > graph.budget.nodes) throw new Error('Graph allocation limit exceeded'); 51 graph.heap = new Map(checkpoint.nodes); graph.nextId = checkpoint.nextId; 52 graph.peak = graph.heap.size; 53 return graph; 54 } 55 get stats(): GraphStats { 56 return { nodes: this.heap.size, work: this.spent, fuel: this.remaining, allocations: this.nextId, 57 peakNodes: this.peak, collections: this.collections, reclaimed: this.reclaimed, gcWork: this.gcWork }; 58 } 59 // Trusted host boundary between operations, never during reduction/IO. 60 // Counters, retained handles and live-node/frame caps are unchanged. 61 beginOperation(): void { this.remaining = this.budget.fuel; } 62 // Every observer also consumes work. A repeatedly inspected cached node isn't 63 // free, and decode/preview loops cannot bypass the operation fuel ceiling. 64 tick(): void { 65 if (this.remaining-- <= 0) throw new Error('Graph fuel limit exceeded'); 66 this.spent++; 67 } 68 private get(id: NodeId): Node { 69 const node = this.heap.get(id); 70 if (!Number.isInteger(id) || id < 0 || !node) throw new Error('Invalid node handle'); 71 return node; 72 } 73 private add(node: Node): NodeId { 74 this.tick(); 75 if (this.heap.size >= this.budget.nodes) throw new Error('Graph allocation limit exceeded'); 76 if (this.nextId >= Number.MAX_SAFE_INTEGER) throw new Error('Graph handle limit exceeded'); 77 const id = this.nextId++ as NodeId; this.heap.set(id, node); this.peak = Math.max(this.peak, this.heap.size); return id; 78 } 79 stem(child: NodeId): NodeId { this.get(child); return this.add({ kind: 'stem', child }); } 80 fork(left: NodeId, right: NodeId): NodeId { 81 this.get(left); this.get(right); return this.add({ kind: 'fork', left, right }); 82 } 83 app(fn: NodeId, arg: NodeId): NodeId { 84 this.get(fn); this.get(arg); return this.add({ kind: 'app', fn, arg }); 85 } 86 apply(fn: NodeId, args: readonly NodeId[]): NodeId { 87 let result = fn; this.get(result); 88 for (const arg of args) result = this.app(result, arg); 89 return result; // Never force/serialize at this boundary. 90 } 91 // Explicit safe boundary: caller must list every handle it will use again. 92 // This never normalizes nodes. Unlisted unreachable handles become invalid. 93 collect(roots: Iterable<NodeId>): void { this.trace(roots); } 94 private trace(roots: Iterable<NodeId>, protectBefore = 0): void { 95 const seen = new Set<NodeId>(), pending = [this.leaf, ...roots]; 96 for (const id of this.heap.keys()) if (id < protectBefore) pending.push(id); 97 while (pending.length) { 98 this.tick(); this.gcWork++; 99 const id = pending.pop()!; 100 if (seen.has(id)) continue; 101 const node = this.get(id); seen.add(id); 102 switch (node.kind) { 103 case 'leaf': break; 104 case 'stem': pending.push(node.child); break; 105 case 'fork': pending.push(node.left, node.right); break; 106 case 'app': pending.push(node.fn, node.arg); break; 107 case 'ref': pending.push(node.target); break; 108 default: return unreachable(node); 109 } 110 } 111 const live = new Map<NodeId, Node>(); 112 for (const [id, node] of this.heap) { 113 this.tick(); this.gcWork++; 114 if (seen.has(id)) live.set(id, node); 115 } 116 // Commit only after marking/sweeping succeeds, including its work budget. 117 this.reclaimed += this.heap.size - live.size; this.heap = live; this.collections++; 118 if (this.threshold !== undefined) this.threshold = Math.min(this.budget.nodes, Math.max(2, live.size * 2)); 119 } 120 force(input: NodeId): NodeId { 121 // No JS callbacks/yields inside reduction: all caller-held handles existed 122 // at entry. Conservatively protect those IDs without copying the heap on 123 // every tiny observer. Only evaluator-created garbage is collectible here. 124 const watermark = this.nextId, collections = this.collections; 125 let current = input, lastCollectionAt = -1; 126 const frames: Frame[] = []; 127 const push = (frame: Frame): void => { 128 if (frames.length >= this.budget.stack) throw new Error('Evaluation stack limit exceeded'); 129 frames.push(frame); 130 }; 131 for (;;) { 132 if (this.threshold !== undefined && this.heap.size >= this.threshold && this.nextId !== lastCollectionAt) { 133 const roots = [input, current]; 134 for (const frame of frames) { 135 switch (frame.kind) { 136 case 'update': roots.push(frame.app); break; 137 case 'function': roots.push(frame.arg); break; 138 case 'left': roots.push(frame.right, frame.arg); break; 139 case 'argument': roots.push(frame.leafCase, frame.stemCase, frame.forkCase); break; 140 default: return unreachable(frame); 141 } 142 } 143 this.trace(roots, watermark); lastCollectionAt = this.nextId; 144 // High survival must not trigger a full trace on every reducer step. 145 this.threshold = Math.min(this.budget.nodes, Math.max(this.threshold, this.heap.size + 1024)); 146 } 147 this.tick(); const node = this.get(current); 148 if (node.kind === 'ref') { current = node.target; continue; } 149 if (node.kind === 'app') { 150 push({ kind: 'update', app: current }); push({ kind: 'function', arg: node.arg }); 151 current = node.fn; continue; 152 } 153 const frame = frames.pop(); 154 if (!frame) { 155 if (this.collections !== collections) this.trace([input, current], watermark); 156 return current; 157 } 158 switch (frame.kind) { 159 case 'update': 160 this.heap.set(frame.app, { kind: 'ref', target: current }); 161 break; 162 case 'function': 163 switch (node.kind) { 164 case 'leaf': current = this.stem(frame.arg); break; 165 case 'stem': current = this.fork(node.child, frame.arg); break; 166 case 'fork': push({ kind: 'left', right: node.right, arg: frame.arg }); current = node.left; break; 167 default: return unreachable(node); 168 } 169 break; 170 case 'left': 171 switch (node.kind) { 172 case 'leaf': current = frame.right; break; // K: don't demand argument. 173 case 'stem': 174 current = this.app(this.app(node.child, frame.arg), this.app(frame.right, frame.arg)); 175 break; // S: right application remains a shared lazy thunk. 176 case 'fork': 177 push({ kind: 'argument', leafCase: node.left, stemCase: node.right, forkCase: frame.right }); 178 current = frame.arg; break; 179 default: return unreachable(node); 180 } 181 break; 182 case 'argument': 183 switch (node.kind) { 184 case 'leaf': current = frame.leafCase; break; 185 case 'stem': current = this.app(frame.stemCase, node.child); break; 186 case 'fork': current = this.app(this.app(frame.forkCase, node.left), node.right); break; 187 default: return unreachable(node); 188 } 189 break; 190 default: return unreachable(frame); 191 } 192 } 193 } 194 observe(handle: NodeId): { id: NodeId; node: Constructor } { 195 const id = this.force(handle), node = this.get(id); 196 if (node.kind === 'app' || node.kind === 'ref') throw new Error('Unforced internal node'); 197 return { id, node }; 198 } 199 pair(handle: NodeId, label = 'pair'): [NodeId, NodeId] { 200 const { node } = this.observe(handle); 201 if (node.kind !== 'fork') throw new Error(`Invalid ${label}: expected Fork`); 202 return [node.left, node.right]; 203 } 204 // Explicitly bounded *logical* expansion, for conformance goldens / export only. 205 // Normal UI transport uses preview(), never this method. 206 toTernary(handle: NodeId, limit = 10_000): string { 207 const pending = [handle], chars: string[] = []; 208 while (pending.length) { 209 if (chars.length >= limit) throw new Error('Tree expansion limit exceeded'); 210 const { node } = this.observe(pending.pop()!); 211 switch (node.kind) { 212 case 'leaf': chars.push('0'); break; 213 case 'stem': chars.push('1'); pending.push(node.child); break; 214 case 'fork': chars.push('2'); pending.push(node.right, node.left); break; 215 default: return unreachable(node); 216 } 217 } 218 return chars.join(''); 219 } 220 fromTernary(text: string, limit = 4096): NodeId { 221 if (!text || text.length > limit) throw new Error('Tree input limit exceeded'); 222 const pending: Array<{ arity: 1 | 2; children: NodeId[] }> = []; 223 let root: NodeId | undefined; 224 for (const char of text) { 225 this.tick(); 226 if (root !== undefined) throw new Error('Trailing tree data'); 227 if (char === '1' || char === '2') { pending.push({ arity: char === '1' ? 1 : 2, children: [] }); continue; } 228 if (char !== '0') throw new Error('Tree must contain only ternary digits 0, 1, 2'); 229 let value = this.leaf; 230 for (;;) { 231 const frame = pending.at(-1); 232 if (!frame) { root = value; break; } 233 frame.children.push(value); 234 if (frame.children.length < frame.arity) break; 235 pending.pop(); 236 value = frame.arity === 1 ? this.stem(frame.children[0]!) : this.fork(frame.children[0]!, frame.children[1]!); 237 } 238 } 239 if (root === undefined || pending.length) throw new Error('Truncated tree'); 240 return root; 241 } 242 preview(handle: NodeId, limit = 64): GraphPreview { 243 if (!Number.isInteger(limit) || limit < 1 || limit > 256) throw new Error('Invalid preview budget'); 244 return this.capture(handle, limit); 245 } 246 snapshot(handle: NodeId, limit = 100_000): GraphPreview { 247 if (!Number.isInteger(limit) || limit < 1 || limit > 100_000) throw new Error('Invalid snapshot budget'); 248 return this.capture(handle, limit); 249 } 250 private capture(handle: NodeId, limit: number): GraphPreview { 251 const root = this.force(handle), seen = new Set<NodeId>(), pending = [root]; 252 const nodes: GraphPreview['nodes'] = [], aliases: GraphPreview['aliases'] = []; 253 const forwarded = new Set<NodeId>(); 254 while (pending.length) { 255 if (seen.has(pending.at(-1)!) || forwarded.has(pending.at(-1)!)) { pending.pop(); continue; } 256 if (nodes.length >= limit) break; 257 const handle = pending.pop()!, { id, node } = this.observe(handle); 258 if (id !== handle && !forwarded.has(handle)) { forwarded.add(handle); aliases.push({ from: handle, to: id }); } 259 if (seen.has(id)) continue; 260 seen.add(id); 261 const children = node.kind === 'leaf' ? [] : node.kind === 'stem' ? [node.child] : [node.left, node.right]; 262 nodes.push({ id, kind: node.kind, children }); 263 pending.push(...children); 264 } 265 return { root, nodes, aliases, truncated: pending.length > 0 }; 266 } 267 } 268 export interface GraphPreview { 269 root: NodeId; 270 nodes: Array<{ id: NodeId; kind: Constructor['kind']; children: NodeId[] }>; 271 aliases: Array<{ from: NodeId; to: NodeId }>; 272 truncated: boolean; 273 }