tricu

tree-export.ts (4675B)

---

 import type { Bundle } from './bundle.js';
 export type TreeFormat = 'ternary' | 'tricu' | 'triangle' | 'dag';
 export interface TreeFile { text: string; bytes: number; extension: string; storedNodes: number; }
 export const FLAT_EXPORT_LIMIT = 33_554_432;
 export const DAG_EXPORT_LIMIT = 134_217_728;
 export function treeFormat(value: unknown): TreeFormat {
   if (value !== 'ternary' && value !== 'tricu' && value !== 'triangle' && value !== 'dag') throw new Error('Unknown tree export format');
   return value;
 }
 // Only immutable, authenticated bundle records are read. No graph observation,
 // application or reduction. Reachability and capped size calculation count DAG
 // records, not unfolded occurrences; expanded writers run only after preflight.
 export function exportTree(bundle: Bundle, name: string, format: TreeFormat): TreeFile {
   format = treeFormat(format);
   const selected = bundle.exports.find(item => item.name === name);
   if (!selected) throw new Error('Unknown export');
   const reachable = new Set<number>(), todo = [selected.root];
   while (todo.length) {
     const id = todo.pop()!;
     if (reachable.has(id)) continue;
     reachable.add(id);
     const node = bundle.nodes[id]!;
     if (node.kind === 'stem') todo.push(node.child);
     else if (node.kind === 'fork') todo.push(node.left, node.right);
   }
   const ids = [...reachable].sort((a, b) => a - b);
   // Bound the number of fragments, not just output bytes. One array entry per
   // unfolded node costs far more memory than the resulting text for large trees.
   const parts: string[] = [], chunk: string[] = []; let chunkLength = 0;
   const flush = (): void => { if (chunk.length) parts.push(chunk.join('')); chunk.length = 0; chunkLength = 0; };
   const write = (text: string): void => {
     chunk.push(text); chunkLength += text.length;
     if (chunkLength >= 65_536) flush();
   };
   const complete = (): string => { flush(); return parts.join(''); };
   let bytes = 0;
   const append = (text: string): void => {
     const size = text.length + 2 * (text.split('△').length - 1);
     bytes += size;
     if (bytes > DAG_EXPORT_LIMIT) throw new Error('DAG export exceeds 128 MiB');
     write(text);
   };
   if (format === 'dag') {
     const keys = new Map<number, string>();
     for (const id of ids) {
       const node = bundle.nodes[id]!, key = `:n${id}`;
       if (node.kind === 'leaf') keys.set(id, '△');
       else {
         const child = keys.get(node.kind === 'stem' ? node.child : node.left)!;
         if (node.kind === 'stem') append(`${key} △ ${child}\n`);
         else {
           const intermediate = `:f${id}`, right = keys.get(node.right)!;
           append(`${intermediate} △ ${child}\n`);
           append(`${key} ${intermediate} ${right}\n`);
         }
         keys.set(id, key);
       }
     }
     const root = keys.get(selected.root)!;
     // A safe fixed interface name, independent of arbitrary bundle export names.
     const ending = `tree ${root}\ntree\n`;
     append(ending);
     return { text: complete(), bytes, extension: 'dag', storedNodes: ids.length };
   }
   const sizes = new Map<number, number>(), triangle = format === 'triangle';
   const symbol = triangle ? '△' : 't', symbolBytes = triangle ? 3 : 1;
   for (const id of ids) {
     const node = bundle.nodes[id]!;
     let size: number;
     if (format === 'ternary') size = 1 + (node.kind === 'leaf' ? 0 : node.kind === 'stem'
       ? sizes.get(node.child)! : sizes.get(node.left)! + sizes.get(node.right)!);
     else size = node.kind === 'leaf' ? symbolBytes : node.kind === 'stem'
       ? symbolBytes + 3 + sizes.get(node.child)!
       : symbolBytes + 4 + sizes.get(node.left)! + sizes.get(node.right)!;
     sizes.set(id, Math.min(FLAT_EXPORT_LIMIT + 1, size));
   }
   bytes = sizes.get(selected.root)!;
   if (bytes > FLAT_EXPORT_LIMIT) throw new Error('Expanded tree exceeds 32 MiB. Choose DAG to preserve sharing.');
   const stack: Array<number | string> = [selected.root];
   while (stack.length) {
     const item = stack.pop()!;
     if (typeof item === 'string') { write(item); continue; }
     const node = bundle.nodes[item]!;
     if (format === 'ternary') {
       write(node.kind === 'leaf' ? '0' : node.kind === 'stem' ? '1' : '2');
       if (node.kind === 'stem') stack.push(node.child);
       else if (node.kind === 'fork') stack.push(node.right, node.left);
     } else if (node.kind === 'leaf') write(symbol);
     else {
       write(`(${symbol} `); stack.push(')');
       if (node.kind === 'stem') stack.push(node.child);
       else stack.push(node.right, ' ', node.left);
     }
   }
   return { text: complete(), bytes, extension: format === 'tricu' ? 'tri' : 'txt', storedNodes: ids.length };
 }