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