tricu

An interpreted language for exploring Tree Calculus
Log | Files | Refs | README | LICENSE

bundle.js (9840B)

      1 export const BUNDLE_LIMIT = 16_777_216;
      2 // Separate bounded profile for the explicitly selected compiler, not packages.
      3 export const COMPILER_BUNDLE_LIMIT = 2_097_152;
      4 const utf8 = new TextDecoder('utf-8', { fatal: true });
      5 class Reader {
      6     bytes;
      7     at = 0;
      8     view;
      9     constructor(bytes) {
     10         this.bytes = bytes;
     11         this.view = new DataView(bytes.buffer, bytes.byteOffset, bytes.byteLength);
     12     }
     13     take(count) {
     14         if (!Number.isSafeInteger(count) || count < 0 || count > this.bytes.length - this.at)
     15             throw new Error('Truncated bundle field');
     16         const value = this.bytes.subarray(this.at, this.at + count);
     17         this.at += count;
     18         return value;
     19     }
     20     u8() { return this.take(1)[0]; }
     21     u16() { const at = this.at; this.take(2); return this.view.getUint16(at); }
     22     u32() { const at = this.at; this.take(4); return this.view.getUint32(at); }
     23     u64() {
     24         const at = this.at;
     25         this.take(8);
     26         const n = this.view.getBigUint64(at);
     27         if (n > BigInt(Number.MAX_SAFE_INTEGER))
     28             throw new Error('Oversized u64');
     29         return Number(n);
     30     }
     31     string(limit = 4096) {
     32         const length = this.u32();
     33         if (length > limit)
     34             throw new Error('Bundle string limit exceeded');
     35         return utf8.decode(this.take(length));
     36     }
     37     count(limit = 4096) {
     38         const n = this.u32();
     39         if (n > limit)
     40             throw new Error('Bundle count limit exceeded');
     41         return n;
     42     }
     43     end() { if (this.at !== this.bytes.length)
     44         throw new Error('Trailing section bytes'); }
     45 }
     46 function requireValue(actual, expected, label) {
     47     if (actual !== expected)
     48         throw new Error(`Unsupported/invalid ${label}`);
     49 }
     50 export function bundleHash(value) {
     51     if (typeof value !== 'string' || !/^[0-9a-f]{64}$/u.test(value))
     52         throw new Error('Expected 64 lowercase hexadecimal bundle hash characters');
     53     return value;
     54 }
     55 export async function sha256(bytes) {
     56     // Copy into an owned ArrayBuffer: no SharedArrayBuffer boundary or mutation
     57     // can change the bytes being checked while validation/loading proceeds.
     58     const result = await crypto.subtle.digest('SHA-256', new Uint8Array(bytes));
     59     return bundleHash(Array.from(new Uint8Array(result), b => b.toString(16).padStart(2, '0')).join(''));
     60 }
     61 export async function fetchBytes(url, limit = BUNDLE_LIMIT) {
     62     const response = await fetch(url, { redirect: 'error', credentials: 'omit' });
     63     if (!response.ok)
     64         throw new Error(`Bundle fetch: HTTP ${response.status}`);
     65     const length = response.headers.get('content-length');
     66     if (length && (!/^\d+$/u.test(length) || Number(length) > limit)) {
     67         await response.body?.cancel();
     68         throw new Error('Bundle download limit exceeded');
     69     }
     70     if (!response.body)
     71         throw new Error('Missing response body');
     72     const reader = response.body.getReader(), chunks = [];
     73     let size = 0;
     74     try {
     75         for (;;) {
     76             const item = await reader.read();
     77             if (item.done)
     78                 break;
     79             size += item.value.length;
     80             if (size > limit)
     81                 throw new Error('Bundle download limit exceeded');
     82             chunks.push(item.value);
     83         }
     84     }
     85     catch (error) {
     86         await reader.cancel().catch(() => { });
     87         throw error;
     88     }
     89     finally {
     90         reader.releaseLock();
     91     }
     92     const bytes = new Uint8Array(size);
     93     let offset = 0;
     94     for (const chunk of chunks) {
     95         bytes.set(chunk, offset);
     96         offset += chunk.length;
     97     }
     98     return bytes;
     99 }
    100 export async function fetchBundle(url, expected, byteLimit = BUNDLE_LIMIT) {
    101     const bytes = await fetchBytes(url, byteLimit);
    102     if (await sha256(bytes) !== expected)
    103         throw new Error('Bundle SHA-256 mismatch');
    104     return decodeBundle(bytes, byteLimit);
    105 }
    106 // Validate completely before touching the graph heap. All loops count physical
    107 // records/bytes, never unfolded tree occurrences. No source/JS/WASM sections run.
    108 export function decodeBundle(bytes, byteLimit = BUNDLE_LIMIT) {
    109     if (bytes.length > byteLimit)
    110         throw new Error('Bundle byte limit exceeded');
    111     const r = new Reader(bytes);
    112     requireValue(utf8.decode(r.take(8)), 'ARBORICX', 'bundle magic');
    113     requireValue(r.u16(), 1, 'container major');
    114     requireValue(r.u16(), 0, 'container minor');
    115     const count = r.count(32);
    116     requireValue(r.u64(), 0, 'header flags');
    117     requireValue(r.u64(), 32, 'directory offset');
    118     const sections = new Map(), ranges = [];
    119     for (let i = 0; i < count; i++) {
    120         const type = r.u32(), version = r.u16(), flags = r.u16(), compression = r.u16();
    121         requireValue(r.u16(), 0, 'section reserved');
    122         const start = r.u64(), size = r.u64();
    123         requireValue(r.u32(), 0, 'section padding');
    124         if (start < 32 + count * 32 || start > bytes.length || size > bytes.length - start)
    125             throw new Error('Section out of bounds');
    126         if (sections.has(type))
    127             throw new Error('Duplicate section');
    128         if (flags & ~1)
    129             throw new Error('Unknown section flags');
    130         if (type === 1 || type === 2) {
    131             requireValue(version, 1, 'section version');
    132             requireValue(compression, 0, 'compression');
    133         }
    134         else if (flags & 1)
    135             throw new Error('Unknown critical section');
    136         ranges.push([start, start + size]);
    137         sections.set(type, bytes.subarray(start, start + size));
    138     }
    139     ranges.sort((a, b) => a[0] - b[0]);
    140     let end = 32 + count * 32;
    141     for (const [start, stop] of ranges) {
    142         if (start !== end)
    143             throw new Error('Overlapping/gapped sections');
    144         end = stop;
    145     }
    146     if (end !== bytes.length)
    147         throw new Error('Trailing container bytes');
    148     const manifest = sections.get(1), nodeBytes = sections.get(2);
    149     if (!manifest || !nodeBytes)
    150         throw new Error('Missing required sections');
    151     const m = new Reader(manifest);
    152     requireValue(utf8.decode(m.take(8)), 'ARBMNFST', 'manifest magic');
    153     requireValue(m.u16(), 1, 'manifest major');
    154     requireValue(m.u16(), 1, 'manifest minor');
    155     for (const expected of ['arboricx.bundle.manifest.v1', 'tree-calculus-executable-object',
    156         'tree-calculus.v1', 'indexed', 'arboricx.indexed.node.v1', 'arboricx.indexed.payload.v1',
    157         'tree-calculus.v1', 'normal-order', 'arboricx.abi.tree.v1'])
    158         requireValue(m.string(), expected, 'manifest semantics');
    159     requireValue(m.u32(), 0, 'runtime capabilities');
    160     requireValue(m.u8(), 0, 'complete closure');
    161     const roots = [];
    162     for (let i = m.count(); i > 0; i--) {
    163         roots.push(m.u32());
    164         m.string();
    165     }
    166     const exports = [], names = new Set();
    167     for (let i = m.count(); i > 0; i--) {
    168         const name = m.string(512), root = m.u32();
    169         requireValue(m.string(), 'term', 'export kind');
    170         requireValue(m.string(), 'arboricx.abi.tree.v1', 'export ABI');
    171         if (!name || names.has(name))
    172             throw new Error('Empty/duplicate export name');
    173         names.add(name);
    174         exports.push({ name, root, kind: 'term', abi: 'arboricx.abi.tree.v1' });
    175     }
    176     if (!roots.length || !exports.length)
    177         throw new Error('Bundle requires roots/exports');
    178     const metadata = Object.create(null);
    179     const tags = { 1: 'package', 2: 'version', 3: 'description', 4: 'license', 5: 'createdBy' };
    180     for (let i = m.count(); i > 0; i--) {
    181         const tag = m.u16(), length = m.u32();
    182         if (length > 16_384)
    183             throw new Error('Metadata limit exceeded');
    184         const value = m.take(length), key = tags[tag];
    185         if (key) {
    186             if (Object.hasOwn(metadata, key))
    187                 throw new Error('Duplicate metadata');
    188             metadata[key] = utf8.decode(value);
    189         }
    190     }
    191     for (let i = m.count(); i > 0; i--) {
    192         m.u16();
    193         m.take(m.u32());
    194     }
    195     m.end();
    196     const n = new Reader(nodeBytes), total = n.u64();
    197     if (!total || total > 100_000)
    198         throw new Error('Bundle node count limit exceeded');
    199     const nodes = [], keys = new Set();
    200     for (let i = 0; i < total; i++) {
    201         const p = new Reader(n.take(n.u32())), tag = p.u8();
    202         let node, key;
    203         const child = () => { const id = p.u32(); if (id >= i)
    204             throw new Error('Non-backward child reference'); return id; };
    205         if (tag === 0) {
    206             node = { kind: 'leaf' };
    207             key = '0';
    208         }
    209         else if (tag === 1) {
    210             const id = child();
    211             node = { kind: 'stem', child: id };
    212             key = `1,${id}`;
    213         }
    214         else if (tag === 2) {
    215             const left = child(), right = child();
    216             node = { kind: 'fork', left, right };
    217             key = `2,${left},${right}`;
    218         }
    219         else
    220             throw new Error('Unknown node tag');
    221         p.end();
    222         if (keys.has(key))
    223             throw new Error('Duplicate indexed node');
    224         keys.add(key);
    225         nodes.push(node);
    226     }
    227     n.end();
    228     for (const root of [...roots, ...exports.map(e => e.root)])
    229         if (root >= total)
    230             throw new Error('Root index out of bounds');
    231     return { roots, exports, nodes, metadata };
    232 }
    233 export function loadBundle(graph, bundle) {
    234     const handles = [];
    235     for (const node of bundle.nodes) {
    236         graph.tick();
    237         switch (node.kind) {
    238             case 'leaf':
    239                 handles.push(graph.leaf);
    240                 break;
    241             case 'stem':
    242                 handles.push(graph.stem(handles[node.child]));
    243                 break;
    244             case 'fork':
    245                 handles.push(graph.fork(handles[node.left], handles[node.right]));
    246                 break;
    247         }
    248     }
    249     return new Map(bundle.exports.map(e => [e.name, handles[e.root]]));
    250 }