tricu

graph.test.mjs (9118B)

---

 import test from 'node:test';
 import assert from 'node:assert/strict';
 import { readFile } from 'node:fs/promises';
 import {BROWSER_BUDGET,collectionPolicy,PACKAGE_COLLECTION} from '../dist/execution.js';
 import { Graph } from '../dist/graph.js';
 import { natural, readNatural, text, readText, line, literals, makeLiteral, view } from '../dist/codecs.js';
 import { runIO } from '../dist/io.js';
 import { decodeBundle, loadBundle } from '../dist/bundle.js';
 const data = JSON.parse(await readFile(new URL('../demos.json', import.meta.url)));
 for(const id of ['parser','lexer'])data.demos[id]=JSON.parse(await readFile(new URL('../'+id+'-demo.json',import.meta.url)));
 function host(input = '') {
   const state = { terminal: '', trace: [] };
   return { state, before: async event => state.trace.push(event), after() {}, running() {},
     read: async () => input, write: s => { state.terminal += s; } };
 }
 test('Haskell-authored codecs and all primitive application rules', () => {
   for (const vector of data.codecVectors) {
     const g = new Graph();
     const id = vector.kind === 'number' ? natural(g, BigInt(vector.value)) : text(g, vector.value);
     assert.equal(g.toTernary(id), vector.tree);
     assert.equal(vector.kind === 'number' ? Number(readNatural(g, id)) : readText(g, id), vector.value);
   }
   for (const vector of data.applyVectors) {
     const g = new Graph();
     assert.equal(g.toTernary(g.app(g.fromTernary(vector.program), g.fromTernary(vector.argument))), vector.result);
   }
 });
 test('300 independently captured Haskell differential cases', async () => {
   const vectors=JSON.parse(await readFile(new URL('./conformance.json',import.meta.url)));
   assert.equal(vectors.cases.length,300);
   for(const c of vectors.cases){
     const g=new Graph();
     assert.equal(g.toTernary(g.apply(g.fromTernary(c.program),c.arguments.map(x=>g.fromTernary(x)))),c.result);
   }
 });
 test('normal order: Haskell discarded-divergence control now returns Leaf', () => {
   const g = new Graph({ fuel: 1000 });
   const f = g.fromTernary('2120200212110021100'), q = g.fromTernary('212110021100');
   assert.equal(g.toTernary(g.app(f, q)), '0');
   assert.ok(g.stats.work < 150);
 });
 test('partial applications retain lazy children; demanding divergence is bounded', () => {
   const g = new Graph({ fuel: 2000 });
   const q = g.fromTernary('212110021100'), loop = g.app(q, q);
   const partial = g.app(g.leaf, loop);
   const {node} = g.observe(partial);
   assert.equal(node.kind, 'stem'); assert.equal(node.child, loop);
   assert.throws(() => g.force(loop), /fuel/);
 });
 test('32-node /four-billion-occurrence graph survives identity and constant without expansion', () => {
   const g = new Graph(); let root = g.leaf;
   for (let i = 0; i < 31; i++) root = g.fork(root, root);
   assert.equal(g.stats.nodes, 32);
   const work = g.stats.work;
   const shape = g.observe(root).node;
   assert.equal(shape.left, shape.right); assert.equal(g.stats.work - work, 1);
   const I = g.fromTernary('21100'), KLeaf = g.fromTernary('200');
   assert.equal(g.force(g.app(I, root)), root);
   assert.equal(g.force(g.app(KLeaf, root)), g.leaf);
   assert.ok(g.stats.nodes < 64); assert.ok(g.stats.work < 200);
   const preview = g.preview(root); assert.equal(preview.nodes.length, 32);
   assert.throws(() => g.toTernary(root, 100), /expansion/);
 });
 test('memoization preserves constructor data and avoids repeated application work', () => {
   const g = new Graph(); const saved = g.fromTernary('200');
   const id = g.app(g.fromTernary('21100'), saved);
   assert.equal(g.force(id), saved);
   const before = g.stats; assert.equal(g.force(id), saved);
   assert.equal(g.stats.nodes, before.nodes); assert.ok(g.stats.work - before.work <= 2);
   assert.equal(g.toTernary(saved), '200');
 });
 for (const [name, demo] of Object.entries(data.demos)) {
   test(`${name}: packaged stable exports match ${demo.haskellCases.length} Haskell goldens`, async () => {
     const bundle=decodeBundle(await readFile(new URL(`../bundles/${demo.hash}.arboricx`,import.meta.url)));
     for (const golden of demo.haskellCases) {
       const budget=BROWSER_BUDGET;
       const g = new Graph(budget,collectionPolicy(budget,PACKAGE_COLLECTION.threshold)), h = host(golden.input);
       const exports=loadBundle(g,bundle);
       const applied=g.apply(exports.get(golden.export),golden.arguments.map(x=>g.fromTernary(x)));
       const result=demo.mode==='io'?await runIO(g,applied,h):applied;
       assert.equal(g.toTernary(result), golden.result);
       assert.equal(h.state.terminal, golden.terminal);
       if(golden.record)assert.deepEqual({...view(g,result,'record').value},golden.record);
     }
   });
 }
 test('preview records forwarding aliases without broken child references', () => {
   const g=new Graph(), delayed=g.app(g.fromTernary('21100'),g.leaf);
   const root=g.stem(delayed), preview=g.preview(root);
   assert.deepEqual(preview.aliases,[{from:delayed,to:g.leaf}]);
   assert.equal(preview.nodes.find(n=>n.id===root).children[0],delayed);
 });
 test('malformed codecs/trees, typed literals, allocations, stack and preview budgets', () => {
   const g = new Graph();
   for (const value of ['', '1', '20', '00', 'x']) assert.throws(() => g.fromTernary(value));
   assert.throws(() => text(g, '\ud800'), /surrogate/);
   assert.throws(() => readText(g, g.fork(natural(g, 0xd800n), g.leaf)), /Unicode/);
   assert.throws(() => line(g, 'x'.repeat(257)), /limit/);
   assert.throws(() => literals([{ type: 'number', value: '-1' }]));
   assert.throws(() => literals([{ type: 'bytes', value: [256] }]));
   assert.throws(() => literals([{ type: 'lambda', value: 'x:x' }]));
   let deep = { type: 'bool', value: false };
   for(let i=0;i<18;i++) deep={type:'list',value:[deep]};
   assert.throws(() => literals([deep]), /nesting/);
   const values=literals([{type:'list',value:[{type:'number',value:'42'},{type:'bool',value:true}]}]);
   assert.equal(view(g,makeLiteral(g,values[0]),'list').value.length,2);
   assert.equal(view(g,natural(g,2n**100n),'number').value,(2n**100n).toString());
   assert.throws(() => g.preview(g.leaf, 257), /budget/);
   const tiny = new Graph({ nodes: 2 }); tiny.stem(tiny.leaf);
   assert.throws(() => tiny.stem(tiny.leaf), /allocation/);
   const shallow = new Graph({ stack: 1 });
   assert.throws(() => shallow.force(shallow.app(shallow.leaf,shallow.leaf)), /stack/);
 });
 test('deep transport and graph observation do not use recursive JS evaluation', () => {
   const g = new Graph(); const term='1'.repeat(10000)+'0';
   const root=g.fromTernary(term,term.length);
   assert.equal(g.toTernary(root,term.length),term);
 });
 test('IO rejects unknown tags/envelopes; pausing happens before effects', async () => {
   const g=new Graph(), h=host();
   const action=(tag,payload=g.leaf)=>g.fork(natural(g,BigInt(tag)),payload);
   const io=action=>g.fork(text(g,'tricuIO'),g.fork(natural(g,1n),action));
   await assert.rejects(runIO(g,io(action(20)),h),/Unsupported/);
   await assert.rejects(runIO(g,g.leaf,h),/envelope/);
   let resume, wrote=false;
   h.before=()=>new Promise(resolve=>{resume=resolve;});h.write=()=>{wrote=true;};
   const pending=runIO(g,io(action(10,text(g,'hi'))),h);
   await Promise.resolve();assert.equal(wrote,false);resume();await pending;assert.equal(wrote,true);
 });
 test('IO action/output budgets and abort do not force arbitrary payloads',async()=>{
   for(const output of [false,true]){
     const g=new Graph(),h=host();
     const action=(tag,payload=g.leaf)=>g.fork(natural(g,BigInt(tag)),payload);
     const primitive=output?action(10,text(g,'x'.repeat(4096))):action(0);
     let current=action(0);
     for(let i=0;i<(output?6:70);i++)current=action(1,g.fork(primitive,g.fork(g.leaf,current)));
     const io=g.fork(text(g,'tricuIO'),g.fork(natural(g,1n),current));
     await assert.rejects(runIO(g,io,h),output?/output limit/:/action limit/);
     assert.ok(h.state.terminal.length<=16384);
   }
   const g=new Graph({fuel:1000}),q=g.fromTernary('212110021100'),loop=g.app(q,q);
   const abort=g.fork(natural(g,2n),loop),io=g.fork(text(g,'tricuIO'),g.fork(natural(g,1n),abort));
   await assert.rejects(runIO(g,io,host()),/Execution aborted/);
   assert.ok(g.stats.work<500);
 });
 
 test('draft checkpoints preserve sharing and lazy poison across failed disposable runs',()=>{
  const g=new Graph({fuel:10000});
  const q=g.fromTernary('212110021100'), loop=g.app(q,q);
  const partial=g.stem(loop), shared=g.fork(partial,partial);
  g.collect([shared]);const stats={...g.stats};
  const checkpoint=structuredClone(g.checkpoint());
  assert.deepEqual(g.stats,stats,'capturing does not evaluate or spend fuel');
  const attempt=()=>Graph.restore(checkpoint,{fuel:500,nodes:10000,stack:100});
  const first=attempt();assert.throws(()=>first.force(loop),/limit/);
  const next=attempt();
  assert.deepEqual(next.observe(shared).node,{kind:'fork',left:partial,right:partial});
  assert.deepEqual(next.observe(partial).node,{kind:'stem',child:loop});
  assert.deepEqual(next.checkpoint(),checkpoint,'failed run never mutates checkpoint');
  assert.throws(()=>Graph.restore(checkpoint,{nodes:1}),/allocation/);
  assert.throws(()=>next.force(loop),/limit/);
 });