tricu

tree-export.js (4899B)

---

 export const FLAT_EXPORT_LIMIT = 33_554_432;
 export const DAG_EXPORT_LIMIT = 134_217_728;
 export function treeFormat(value) {
     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, name, format) {
     format = treeFormat(format);
     const selected = bundle.exports.find(item => item.name === name);
     if (!selected)
         throw new Error('Unknown export');
     const reachable = new Set(), 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 = [], chunk = [];
     let chunkLength = 0;
     const flush = () => { if (chunk.length)
         parts.push(chunk.join('')); chunk.length = 0; chunkLength = 0; };
     const write = (text) => {
         chunk.push(text);
         chunkLength += text.length;
         if (chunkLength >= 65_536)
             flush();
     };
     const complete = () => { flush(); return parts.join(''); };
     let bytes = 0;
     const append = (text) => {
         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();
         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(), triangle = format === 'triangle';
     const symbol = triangle ? '△' : 't', symbolBytes = triangle ? 3 : 1;
     for (const id of ids) {
         const node = bundle.nodes[id];
         let size;
         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 = [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 };
 }