tricu

graph.test.mjs (8957B)

---

 import {terminalHost} from './terminal-host.mjs';
 import {Terminal} from '../dist/io-terminal.js';
 import {constructors} from '../dist/io-private.js';
 import {Session} from '../dist/io-session.js';
 import {envelope} from '../dist/io-profile.js';
 import {drive} from '../dist/io-driver.js';
 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 { 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)));
       if(demo.mode==='io') {
         const trees=constructors({leaf:g.leaf,observe:g.observe.bind(g),stem:g.stem.bind(g),fork:g.fork.bind(g),app:g.app.bind(g)});
         const selected=envelope(trees,applied);assert.equal(selected.version,2);
         // Reference tests exercise only the v2 model; no legacy interpreter.
         assert.equal(envelope(g,applied).version,2);
         assert.equal(h.state.terminal,'');assert.equal(h.state.trace.length,0);
         const session=new Session(trees,selected.action,'1',roots=>g.collect(roots),{summarize:false,backend:'test-reference'});
         const terminal=terminalHost(Terminal,golden.input);
         const result=await drive({run:'1',turn:c=>session.turn(c),view:async()=>view(g,session.core.result.value,'ternary')},terminal);
         assert.equal(result.value,golden.result);assert.equal(terminal.terminalText,golden.terminal);
       } else {
         assert.equal(g.toTernary(applied), golden.result);
         assert.equal(h.state.terminal, golden.terminal);
       }
     }
   });
 }
 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('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/);
 });
 
 test('immutable v1 conversation requires its retained runtime, not current execution',async()=>{
  const pin='0811457d501113ee11194f90e279ebb4ef9d548c70cb48d146be03eb9af7505f';
  const g=new Graph(BROWSER_BUDGET);
  const exports=loadBundle(g,decodeBundle(await readFile(new URL(`../bundles/${pin}.arboricx`,import.meta.url))));
  assert.throws(()=>envelope(g,exports.get('main')),/Unsupported tricuIO version/);
 });