stack-analysis.js

/**
 * Static shadow-stack analysis for Soroban (Rust/LLVM) WASM contracts.
 *
 * Parses the binary directly (no wabt / wasm2wat / npm deps) and reports:
 *   - which global is the stack pointer, its initial value, and whether the layout is stack-first
 *   - per-function shadow-stack frame sizes (constants subtracted from the SP)
 *   - the worst-case call chain and total shadow-stack usage from every exported entry point
 *   - hazards that make the bound inexact: dynamic SP adjustment (alloca/over-alignment),
 *     recursion (cycles in the call graph), and indirect calls
 *
 * Uses no Node or DOM APIs: shared by the `wasm-frames.js` CLI and the browser page.
 */

// ---------------------------------------------------------------- binary reader

class Reader {
    constructor(bytes, pos = 0, end = bytes.length) {
        this.b = bytes
        this.pos = pos
        this.end = end
    }
    eof() { return this.pos >= this.end }
    u8() {
        if (this.pos >= this.end) throw new Error(`unexpected end of data at offset ${this.pos}`)
        return this.b[this.pos++]
    }
    uleb() {
        let result = 0, shift = 0, byte
        do {
            byte = this.u8()
            result += (byte & 0x7f) * 2 ** shift
            shift += 7
        } while (byte & 0x80)
        return result
    }
    sleb32() {
        let result = 0, shift = 0, byte
        do {
            byte = this.u8()
            result |= (byte & 0x7f) << shift
            shift += 7
        } while (byte & 0x80)
        if (shift < 32 && (byte & 0x40)) result |= ~0 << shift
        return result | 0
    }
    skipLeb() { while (this.u8() & 0x80); }
    skip(n) {
        this.pos += n
        if (this.pos > this.end) throw new Error('unexpected end of data')
    }
    name() {
        const len = this.uleb()
        const s = new TextDecoder().decode(this.b.subarray(this.pos, this.pos + len))
        this.skip(len)
        return s
    }
    limits() {
        const flags = this.uleb()
        const min = this.uleb()
        if (flags & 1) this.uleb()
        return min
    }
}

// Constant expression (global/data/elem initializers). Returns the i32 value when it is a
// plain i32.const, and any ref.func targets.
function readConstExpr(r) {
    const out = { i32: undefined, funcs: [], complex: false }
    for (;;) {
        const op = r.u8()
        if (op === 0x0b) return out
        if (op === 0x41) out.i32 = r.sleb32()
        else if (op === 0x42) r.skipLeb()
        else if (op === 0x43) r.skip(4)
        else if (op === 0x44) r.skip(8)
        else if (op === 0x23) { r.uleb(); out.complex = true }
        else if (op === 0xd0) r.u8()
        else if (op === 0xd2) out.funcs.push(r.uleb())
        else if ((op >= 0x6a && op <= 0x6c) || (op >= 0x7c && op <= 0x7e)) out.complex = true // extended-const
        else throw new Error(`unsupported opcode 0x${op.toString(16)} in constant expression`)
    }
}

// Decodes a function body into parallel arrays of opcodes and the one immediate we care about
// (index for call/local/global ops, value for i32.const). Everything else is skipped correctly.
function decodeExpr(r, end) {
    const ops = [], args = []
    while (r.pos < end) {
        let op = r.u8()
        let arg = 0
        if (op === 0x02 || op === 0x03 || op === 0x04) r.skipLeb()          // block/loop/if blocktype
        else if (op === 0x0c || op === 0x0d) r.skipLeb()                    // br, br_if
        else if (op === 0x0e) { const n = r.uleb(); for (let i = 0; i <= n; i++) r.skipLeb() } // br_table
        else if (op === 0x10 || op === 0x12) arg = r.uleb()                 // call, return_call
        else if (op === 0x11 || op === 0x13) { arg = r.uleb(); r.skipLeb() } // call_indirect: type, table
        else if (op === 0x1c) r.skip(r.uleb())                              // typed select
        else if (op >= 0x20 && op <= 0x26) arg = r.uleb()                   // local.*, global.*, table.get/set
        else if (op >= 0x28 && op <= 0x3e) {                                // loads/stores: memarg
            const align = r.uleb()
            if (align & 0x40) r.skipLeb()                                     // multi-memory index
            r.skipLeb()
        }
        else if (op === 0x3f || op === 0x40) r.skipLeb()                    // memory.size/grow
        else if (op === 0x41) arg = r.sleb32()                              // i32.const
        else if (op === 0x42) r.skipLeb()                                   // i64.const
        else if (op === 0x43) r.skip(4)
        else if (op === 0x44) r.skip(8)
        else if (op === 0xd0) r.u8()                                        // ref.null
        else if (op === 0xd2) arg = r.uleb()                                // ref.func
        else if (op === 0xfc) {
            const sub = r.uleb()
            op = 0xfc00 | sub
            if (sub <= 7) { /* saturating truncations */ }
            else if (sub === 8 || sub === 10 || sub === 12 || sub === 14) { r.skipLeb(); r.skipLeb() }
            else if (sub === 9 || sub === 11 || sub === 13 || sub === 15 || sub === 16 || sub === 17) r.skipLeb()
            else throw new Error(`unsupported 0xfc opcode ${sub}`)
        }
        else if (op === 0xfd) throw new Error('SIMD instructions are not supported (not valid in Soroban contracts)')
        else if (op <= 0x01 || op === 0x05 || op === 0x0b || op === 0x0f || op === 0x1a || op === 0x1b ||
                 (op >= 0x45 && op <= 0xc4) || op === 0xd1) { /* no immediates */ }
        else throw new Error(`unknown opcode 0x${op.toString(16)} at offset ${r.pos - 1}`)
        ops.push(op)
        args.push(arg)
    }
    return { ops, args }
}

// ---------------------------------------------------------------- module parsing

function parseModule(bytes) {
    const r = new Reader(bytes)
    if (r.u8() !== 0x00 || r.u8() !== 0x61 || r.u8() !== 0x73 || r.u8() !== 0x6d) throw new Error('not a WASM binary')
    r.skip(4) // version

    const m = {
        types: [], importedFuncs: [], funcTypes: [], globals: [], exports: [],
        memories: [], tableFuncs: [], dataSegments: [], bodies: [],
        funcNames: new Map(), globalNames: new Map(), start: undefined
    }

    while (!r.eof()) {
        const id = r.u8()
        const size = r.uleb()
        const end = r.pos + size
        const s = new Reader(bytes, r.pos, end)
        switch (id) {
            case 0: { // custom
                const name = s.name()
                if (name === 'name') parseNameSection(s, m)
                break
            }
            case 1: { // types
                for (let n = s.uleb(); n > 0; n--) {
                    if (s.u8() !== 0x60) throw new Error('unsupported type form (GC types?)')
                    const start = s.pos
                    s.skip(s.uleb())
                    s.skip(s.uleb())
                    m.types.push(Array.from(bytes.subarray(start, s.pos)).join(','))
                }
                break
            }
            case 2: { // imports
                for (let n = s.uleb(); n > 0; n--) {
                    const module = s.name(), field = s.name(), kind = s.u8()
                    if (kind === 0) m.importedFuncs.push({ module, field, type: s.uleb() })
                    else if (kind === 1) { s.u8(); s.limits() }
                    else if (kind === 2) s.limits()
                    else if (kind === 3) m.globals.push({ valtype: s.u8(), mutable: s.u8() === 1, imported: `${module}.${field}` })
                    else if (kind === 4) { s.u8(); s.uleb() }
                    else throw new Error(`unknown import kind ${kind}`)
                }
                break
            }
            case 3: for (let n = s.uleb(); n > 0; n--) m.funcTypes.push(s.uleb()); break
            case 5: for (let n = s.uleb(); n > 0; n--) m.memories.push(s.limits()); break
            case 6: { // globals
                for (let n = s.uleb(); n > 0; n--) {
                    const valtype = s.u8(), mutable = s.u8() === 1
                    const init = readConstExpr(s)
                    m.globals.push({ valtype, mutable, init: init.complex ? undefined : init.i32 })
                }
                break
            }
            case 7: for (let n = s.uleb(); n > 0; n--) m.exports.push({ name: s.name(), kind: s.u8(), index: s.uleb() }); break
            case 8: m.start = s.uleb(); break
            case 9: { // elements: collect every function that may end up in a table
                for (let n = s.uleb(); n > 0; n--) {
                    const flags = s.uleb()
                    const passive = flags & 1, explicit = flags & 2, exprs = flags & 4
                    if (!passive) { if (explicit) s.uleb(); readConstExpr(s) }
                    if (passive || explicit) s.u8()
                    for (let k = s.uleb(); k > 0; k--) {
                        if (exprs) m.tableFuncs.push(...readConstExpr(s).funcs)
                        else m.tableFuncs.push(s.uleb())
                    }
                }
                break
            }
            case 10: { // code
                for (let n = s.uleb(); n > 0; n--) {
                    const bodyEnd = s.uleb() + s.pos
                    for (let k = s.uleb(); k > 0; k--) { s.uleb(); s.u8() } // local decls
                    m.bodies.push(decodeExpr(s, bodyEnd))
                    s.pos = bodyEnd
                }
                break
            }
            case 11: { // data
                for (let n = s.uleb(); n > 0; n--) {
                    const flags = s.uleb()
                    let offset
                    if (flags !== 1) {
                        if (flags === 2) s.uleb()
                        const e = readConstExpr(s)
                        offset = e.complex ? undefined : e.i32
                    }
                    const len = s.uleb()
                    s.skip(len)
                    if (offset !== undefined) m.dataSegments.push({ offset: offset >>> 0, len })
                }
                break
            }
            default: break // 4 table, 12 datacount, 13 tag: nothing needed
        }
        r.pos = end
    }
    return m
}

function parseNameSection(s, m) {
    try {
        while (!s.eof()) {
            const id = s.u8(), size = s.uleb(), end = s.pos + size
            const target = id === 1 ? m.funcNames : id === 7 ? m.globalNames : null
            if (target) for (let n = s.uleb(); n > 0; n--) target.set(s.uleb(), s.name())
            s.pos = end
        }
    } catch { /* malformed name section: names are cosmetic, ignore */ }
}

// ---------------------------------------------------------------- name demangling (Rust legacy)

const RUST_ESCAPES = { '$LT$': '<', '$GT$': '>', '$RF$': '&', '$BP$': '*', '$C$': ',', '$SP$': '@',
    '$LP$': '(', '$RP$': ')', '$u20$': ' ', '$u27$': "'", '$u5b$': '[', '$u5d$': ']', '$u7b$': '{',
    '$u7d$': '}', '$u7e$': '~', '$u3b$': ';', '$u2b$': '+', '$u22$': '"' }

/**
 * Demangle a legacy Rust symbol name (`_ZN...E`); other names are returned unchanged
 * @param {string} name
 * @return {string}
 */
export function demangle(name) {
    const mt = /^_?_ZN(.*)E$/.exec(name)
    if (!mt) return name
    const parts = []
    let rest = mt[1]
    while (rest.length) {
        const lm = /^(\d+)/.exec(rest)
        if (!lm) return name
        const len = +lm[1]
        parts.push(rest.substr(lm[1].length, len))
        rest = rest.slice(lm[1].length + len)
    }
    if (parts.length > 1 && /^h[0-9a-f]{16}$/.test(parts[parts.length - 1])) parts.pop()
    return parts.map(p => p.replace(/\$[A-Za-z0-9]+\$/g, e => RUST_ESCAPES[e] ?? e)
        .replace(/\.\./g, '::').replace(/^_\$/, '$')).join('::')
}

// ---------------------------------------------------------------- mnemonics (for --explain)

const MNEMONICS = { 0x00: 'unreachable', 0x01: 'nop', 0x02: 'block', 0x03: 'loop', 0x04: 'if', 0x05: 'else',
    0x0b: 'end', 0x0c: 'br', 0x0d: 'br_if', 0x0e: 'br_table', 0x0f: 'return', 0x10: 'call',
    0x11: 'call_indirect', 0x1a: 'drop', 0x1b: 'select', 0x20: 'local.get', 0x21: 'local.set',
    0x22: 'local.tee', 0x23: 'global.get', 0x24: 'global.set', 0x28: 'i32.load', 0x29: 'i64.load',
    0x36: 'i32.store', 0x37: 'i64.store', 0x41: 'i32.const', 0x42: 'i64.const', 0x45: 'i32.eqz',
    0x46: 'i32.eq', 0x47: 'i32.ne', 0x48: 'i32.lt_s', 0x49: 'i32.lt_u', 0x4a: 'i32.gt_s', 0x4b: 'i32.gt_u',
    0x4c: 'i32.le_s', 0x4d: 'i32.le_u', 0x4e: 'i32.ge_s', 0x4f: 'i32.ge_u', 0x6a: 'i32.add',
    0x6b: 'i32.sub', 0x6c: 'i32.mul', 0x6d: 'i32.div_s', 0x6e: 'i32.div_u', 0x71: 'i32.and',
    0x72: 'i32.or', 0x73: 'i32.xor', 0x74: 'i32.shl', 0x75: 'i32.shr_s', 0x76: 'i32.shr_u',
    0xa7: 'i32.wrap_i64', 0xad: 'i64.extend_i32_u' }
const WITH_ARG = new Set([0x10, 0x11, 0x20, 0x21, 0x22, 0x23, 0x24, 0x41])

function mnemonic(op, arg, sp) {
    const m = MNEMONICS[op] ?? `op_0x${op.toString(16)}`
    if (!WITH_ARG.has(op)) return m
    return `${m} ${arg}${(op === 0x23 || op === 0x24) && arg === sp ? '  ;; SP' : ''}`
}

// ---------------------------------------------------------------- analysis

const OP = { LOCAL_GET: 0x20, LOCAL_SET: 0x21, LOCAL_TEE: 0x22, GLOBAL_GET: 0x23, GLOBAL_SET: 0x24,
    I32_CONST: 0x41, I32_ADD: 0x6a, I32_SUB: 0x6b, I32_AND: 0x71,
    CALL: 0x10, CALL_INDIRECT: 0x11, RETURN_CALL: 0x12, RETURN_CALL_INDIRECT: 0x13 }

function findStackPointer(m) {
    const candidates = []
    m.globals.forEach((g, i) => { if (g.valtype === 0x7f && g.mutable) candidates.push(i) })
    if (!candidates.length) return { index: undefined, how: 'no mutable i32 global (contract uses no shadow stack)' }

    const named = candidates.find(i => m.globalNames.get(i) === '__stack_pointer' ||
        (m.globals[i].imported || '').endsWith('.__stack_pointer'))
    if (named !== undefined) return { index: named, how: 'named __stack_pointer' }

    // Stripped: pick the global most often used in the `global.get g; i32.const N; i32.sub` prologue.
    let best = candidates[0], bestScore = -1
    for (const g of candidates) {
        let score = 0
        for (const { ops, args } of m.bodies) {
            for (let k = 0; k + 2 < ops.length; k++) {
                if (ops[k] === OP.GLOBAL_GET && args[k] === g && ops[k + 1] === OP.I32_CONST &&
                    (ops[k + 2] === OP.I32_SUB || (ops[k + 2] === OP.I32_ADD && args[k + 1] < 0))) score++
            }
        }
        if (score > bestScore) { best = g; bestScore = score }
    }
    return { index: best, how: bestScore > 0 ? `inferred from ${bestScore} prologue patterns` : 'guessed (first mutable i32 global, no prologues found)' }
}

function analyzeFunction({ ops, args }, sp) {
    const spLocals = new Set() // locals holding an unmodified copy of SP
    const isSpRead = k => k >= 0 && ((ops[k] === OP.GLOBAL_GET && args[k] === sp) ||
        ((ops[k] === OP.LOCAL_GET || ops[k] === OP.LOCAL_TEE) && spLocals.has(args[k])))

    // Does instruction j end an expression of the form SP - const [& -align]? Returns bytes reserved.
    const setupEndingAt = j => {
        if (j < 2 || ops[j - 1] !== OP.I32_CONST) return null
        const c = args[j - 1]
        if (ops[j] === OP.I32_SUB && isSpRead(j - 2) && c > 0) return c
        if (ops[j] === OP.I32_ADD && isSpRead(j - 2) && c < 0) return -c
        if (ops[j] === OP.I32_AND && c < 0) { // over-alignment: up to (align - 1) extra bytes
            const inner = setupEndingAt(j - 2)
            if (inner !== null) return inner + (-c) - 1
        }
        return null
    }

    let frame = 0, setups = 0, dynamic = false
    const dynamicSites = [], setupSites = []
    const calls = new Set(), indirectTypes = new Set()

    for (let k = 0; k < ops.length; k++) {
        const op = ops[k]
        if (op === OP.CALL || op === OP.RETURN_CALL) calls.add(args[k])
        else if (op === OP.CALL_INDIRECT || op === OP.RETURN_CALL_INDIRECT) indirectTypes.add(args[k])
        else if (op === OP.GLOBAL_GET && args[k] === sp &&
                 (ops[k + 1] === OP.LOCAL_SET || ops[k + 1] === OP.LOCAL_TEE)) spLocals.add(args[k + 1])
        else if (op === OP.LOCAL_SET && spLocals.has(args[k]) && !isSpRead(k - 1)) spLocals.delete(args[k])

        // Frame reservation: counts leaf functions too, which use the 128-byte "red zone" below SP
        // without ever writing SP back.
        if (op === OP.I32_SUB || op === OP.I32_ADD) {
            const size = setupEndingAt(k)
            if (size !== null) {
                const aligned = ops[k + 1] === OP.I32_CONST && ops[k + 2] === OP.I32_AND ? setupEndingAt(k + 2) : null
                frame = Math.max(frame, aligned ?? size)
                setups++
                const from = Math.max(0, k - 6)
                setupSites.push({ at: k, size: aligned ?? size, ops: ops.slice(from, k + 4), args: args.slice(from, k + 4) })
            }
        }

        // Every write to SP must be a recognized setup or restore; anything else is dynamic (alloca).
        if (op === OP.GLOBAL_SET && args[k] === sp) {
            let j = k - 1
            if (ops[j] === OP.LOCAL_TEE) j--
            const isSetup = setupEndingAt(j) !== null
            const isRestore = ops[j] === OP.LOCAL_GET || isSpRead(j) || (ops[j - 1] === OP.I32_CONST &&
                ((ops[j] === OP.I32_ADD && args[j - 1] > 0) || (ops[j] === OP.I32_SUB && args[j - 1] < 0)))
            if (!isSetup && !isRestore) {
                dynamic = true
                const from = Math.max(0, k - 12)
                dynamicSites.push({ at: k, ops: ops.slice(from, k + 1), args: args.slice(from, k + 1) })
            }
        }
    }
    return { frame, setups, dynamic, dynamicSites, setupSites, calls: [...calls], indirectTypes: [...indirectTypes] }
}

/**
 * @typedef {Object} ChainLink
 * @property {string} name
 * @property {number} frame - frame size, bytes
 */

/**
 * @typedef {Object} EntryPoint
 * @property {string} name - export name, or `(start)`
 * @property {number} total - worst-case shadow-stack usage, bytes; Infinity on recursion
 * @property {boolean} inexact - total is a lower bound
 * @property {ChainLink[]} chain - worst-case call chain, imports omitted
 */

/**
 * @typedef {Object} CodeSite
 * @property {number} instructionIndex
 * @property {number} [size] - bytes reserved (setup sites only)
 * @property {string[]} code - instruction window around the site
 */

/**
 * @typedef {Object} FunctionInfo
 * @property {number} index
 * @property {string} name
 * @property {number} frame - own frame size, bytes
 * @property {number} worstPath - frame plus deepest callee path, bytes
 * @property {boolean} dynamic - SP adjusted by a non-constant amount
 * @property {boolean} recursive
 * @property {boolean} indirect - contains call_indirect
 * @property {boolean} inexact - worstPath is a lower bound
 * @property {CodeSite[]} [dynamicSites] - set when dynamic
 * @property {CodeSite[]} [setupSites] - set when multipleSetups
 * @property {number} [frameIfStacked] - sum of all reservations, set when multipleSetups
 * @property {boolean} multipleSetups
 */

/**
 * @typedef {Object} StackReport
 * @property {{global: number|undefined, detection: string, initial: number|undefined}} stackPointer
 * @property {{stackFirst: boolean|undefined, stackSize: number|undefined, dataStart: number|undefined,
 *     dataEnd: number|undefined, heapBase: number|undefined, memoryPages: number|undefined}} layout
 * @property {EntryPoint|null} peak - entry point with the highest usage
 * @property {number|undefined} headroom - configured stack size / peak usage
 * @property {EntryPoint[]} entryPoints - sorted by usage, descending
 * @property {FunctionInfo[]} functions - sorted by frame size, descending
 * @property {string[]} warnings
 */

/**
 * Analyze shadow-stack usage of a WASM module
 * @param {Uint8Array|ArrayBuffer} bytes - WASM binary
 * @param {{sp?: number}} [options] - sp: stack pointer global index, overrides auto-detection
 * @return {StackReport}
 */
export function analyzeWasm(bytes, { sp: spOverride } = {}) {
    const m = parseModule(bytes instanceof Uint8Array ? bytes : new Uint8Array(bytes))
    const nImported = m.importedFuncs.length
    const nFuncs = nImported + m.bodies.length

    const sp = spOverride !== undefined ? { index: spOverride, how: 'set by --sp' } : findStackPointer(m)
    const spInit = sp.index !== undefined ? m.globals[sp.index]?.init : undefined

    const exportedGlobal = name => {
        const e = m.exports.find(x => x.kind === 3 && x.name === name)
        return e ? m.globals[e.index]?.init : undefined
    }
    const dataStart = m.dataSegments.length ? Math.min(...m.dataSegments.map(d => d.offset)) : undefined
    const dataEnd = m.dataSegments.length ? Math.max(...m.dataSegments.map(d => d.offset + d.len)) : undefined
    const heapBase = exportedGlobal('__heap_base')

    // Stack-first (rustc's default for wasm): stack occupies [0, spInit), static data above it.
    let stackFirst
    const above = dataStart ?? heapBase
    if (spInit !== undefined && above !== undefined) stackFirst = above >= spInit

    const name = i => {
        if (i < nImported) return `${m.importedFuncs[i].module}.${m.importedFuncs[i].field}`
        if (m.funcNames.has(i)) return demangle(m.funcNames.get(i))
        const ex = m.exports.find(e => e.kind === 0 && e.index === i)
        return ex ? ex.name : `f${i}`
    }
    const typeOf = i => i < nImported ? m.importedFuncs[i].type : m.funcTypes[i - nImported]

    // Per-function facts
    const funcs = new Array(nFuncs)
    for (let i = 0; i < nFuncs; i++) {
        if (i < nImported) { funcs[i] = { index: i, name: name(i), imported: true, frame: 0, callees: [] }; continue }
        const a = sp.index !== undefined ? analyzeFunction(m.bodies[i - nImported], sp.index)
            : { frame: 0, setups: 0, dynamic: false, dynamicSites: [], setupSites: [], calls: [], indirectTypes: [] }
        // Resolve indirect calls to every table entry with a structurally identical signature.
        const indirectTargets = []
        for (const t of a.indirectTypes) {
            for (const f of new Set(m.tableFuncs)) if (m.types[typeOf(f)] === m.types[t]) indirectTargets.push(f)
        }
        funcs[i] = { index: i, name: name(i), imported: false, frame: a.frame, setups: a.setups,
            dynamic: a.dynamic, dynamicSites: a.dynamicSites, setupSites: a.setupSites, indirect: a.indirectTypes.length > 0,
            callees: [...new Set([...a.calls, ...indirectTargets])] }
    }

    // Worst-case path cost (frame + deepest callee), with cycle detection.
    const state = new Uint8Array(nFuncs) // 0 = new, 1 = on stack, 2 = done
    const recursive = new Set()
    const visit = i => {
        const f = funcs[i]
        if (state[i] === 2) return f
        if (state[i] === 1) { recursive.add(i); return { total: Infinity, inexact: true } }
        state[i] = 1
        let best = 0, next = -1, inexact = !!f.dynamic
        for (const c of f.callees) {
            const r = visit(c)
            if (r.inexact) inexact = true
            if (r.total > best) { best = r.total; next = c }
        }
        state[i] = 2
        f.total = f.frame + best
        f.next = next
        f.inexact = inexact || f.total === Infinity
        return f
    }
    for (let i = 0; i < nFuncs; i++) visit(i)
    for (const i of recursive) funcs[i].recursive = true

    const chainOf = i => {
        const chain = [], seen = new Set()
        for (let c = i; c >= 0 && !seen.has(c); c = funcs[c].next) {
            seen.add(c)
            if (!funcs[c].imported) chain.push({ name: funcs[c].name, frame: funcs[c].frame })
        }
        return chain
    }

    const entries = m.exports.filter(e => e.kind === 0).map(e => ({ export: e.name, index: e.index }))
    if (m.start !== undefined) entries.push({ export: '(start)', index: m.start })
    const entryPoints = entries.map(e => ({
        name: e.export, total: funcs[e.index].total, inexact: funcs[e.index].inexact, chain: chainOf(e.index)
    })).sort((a, b) => b.total - a.total)

    const peak = entryPoints.length ? entryPoints[0] : null
    return {
        stackPointer: { global: sp.index, detection: sp.how, initial: spInit },
        layout: { stackFirst, stackSize: stackFirst ? spInit : undefined, dataStart, dataEnd, heapBase,
            memoryPages: m.memories[0] },
        peak,
        headroom: peak && stackFirst && Number.isFinite(peak.total) && peak.total > 0 ? spInit / peak.total : undefined,
        entryPoints,
        functions: funcs.filter(f => !f.imported).map(f => ({
            index: f.index, name: f.name, frame: f.frame, worstPath: f.total,
            dynamic: f.dynamic, recursive: !!f.recursive, indirect: f.indirect, inexact: f.inexact,
            dynamicSites: f.dynamic ? f.dynamicSites.map(d => ({ instructionIndex: d.at,
                code: d.ops.map((o, i) => mnemonic(o, d.args[i], sp.index)) })) : undefined,
            setupSites: f.setups > 1 ? f.setupSites.map(d => ({ instructionIndex: d.at, size: d.size,
                code: d.ops.map((o, i) => mnemonic(o, d.args[i], sp.index)) })) : undefined,
            frameIfStacked: f.setups > 1 ? f.setupSites.reduce((a, d) => a + d.size, 0) : undefined,
            multipleSetups: f.setups > 1
        })).sort((a, b) => b.frame - a.frame || a.index - b.index),
        warnings: [
            ...(stackFirst === false ? ['Stack is NOT first in linear memory: an overflow will silently corrupt static data instead of trapping.'] : []),
            ...(funcs.some(f => f.dynamic) ? ['Some functions adjust SP dynamically (alloca or over-alignment): their totals are lower bounds.'] : []),
            ...(recursive.size ? ['Call graph contains recursion: affected paths are unbounded.'] : []),
            ...(funcs.some(f => f.indirect) ? [`Indirect calls resolved against ${new Set(m.tableFuncs).size} table entries by signature (conservative).`] : [])
        ]
    }
}

// ---------------------------------------------------------------- report formatting

/**
 * Format an integer with thousands separators; Infinity becomes `∞`
 * @param {number} n
 * @return {string}
 */
export function formatNumber(n) {
    return n === Infinity ? '∞' : n.toLocaleString('en-US')
}

/**
 * Format a stack usage value in bytes; `≥` marks a lower bound
 * @param {number} n
 * @param {boolean} [inexact]
 * @return {string}
 */
export function formatBytes(n, inexact) {
    return `${inexact && n !== Infinity ? '≥' : ''}${formatNumber(n)} B`
}

/**
 * Hazard flags of a function, as shown in the report
 * @param {FunctionInfo} f
 * @return {string[]}
 */
export function functionFlags(f) {
    return [f.dynamic && 'dynamic', f.recursive && 'recursive', f.indirect && 'indirect',
        f.multipleSetups && 'multi-setup'].filter(Boolean)
}

/**
 * Functions listed in the report: all of them, or the top N that have a frame or a hazard
 * @param {StackReport} res
 * @param {{top?: number, all?: boolean}} [options]
 * @return {FunctionInfo[]}
 */
export function selectFunctions(res, { top = 20, all = false } = {}) {
    return all ? res.functions : res.functions.filter(f => f.frame > 0 || f.dynamic || f.recursive).slice(0, top)
}

/**
 * Serialize a report as JSON; Infinity becomes the string "Infinity"
 * @param {StackReport} res
 * @return {string}
 */
export function formatJson(res) {
    return JSON.stringify(res, (k, v) => v === Infinity ? 'Infinity' : v, 2)
}

/**
 * Render a report as plain text
 * @param {StackReport} res
 * @param {{top?: number, all?: boolean, explain?: boolean}} [options] - explain: list multi-setup and dynamic SP sites
 * @return {string}
 */
export function formatReport(res, { top = 20, all = false, explain = false } = {}) {
    const chainStr = c => c.map(x => `${x.name}(${x.frame})`).join(' → ')
    const lines = []
    const { stackPointer: sp, layout: l } = res

    if (sp.global === undefined) {
        lines.push(`Stack pointer: none — ${sp.detection}`)
    } else {
        lines.push(`Stack pointer:   global ${sp.global} (${sp.detection}), initial value ${sp.initial !== undefined ? formatNumber(sp.initial) : '?'}`)
        lines.push(`Layout:          ${l.stackFirst === true ? `stack-first ✓ (overflow traps), stack size ${formatNumber(l.stackSize)} B`
            : l.stackFirst === false ? 'stack AFTER data ✗ (overflow corrupts static data)' : 'unknown'}`)
    }
    if (l.memoryPages !== undefined) lines.push(`Memory:          ${l.memoryPages} initial page(s) = ${formatNumber(l.memoryPages * 64)} KiB` +
        (l.dataStart !== undefined ? `, static data ${formatNumber(l.dataStart)}–${formatNumber(l.dataEnd)}` : ''))
    if (res.peak) {
        lines.push(`Peak usage:      ${formatBytes(res.peak.total, res.peak.inexact)} via ${res.peak.name}`)
        if (res.headroom !== undefined) lines.push(`Headroom:        ${res.headroom.toFixed(2)}× of configured stack`)
    }
    for (const w of res.warnings) lines.push(`WARNING: ${w}`)

    lines.push('', 'Entry points (exports), worst-case shadow stack:')
    const w1 = Math.max(10, ...res.entryPoints.map(e => e.name.length))
    for (const e of res.entryPoints) {
        lines.push(`  ${e.name.padEnd(w1)}  ${formatBytes(e.total, e.inexact).padStart(12)}   ${chainStr(e.chain)}`)
    }

    const shown = selectFunctions(res, { top, all })
    lines.push('', `Functions by frame size${all ? '' : ` (top ${shown.length} with a frame or hazard)`}:`)
    lines.push(`  ${'frame'.padStart(8)}  ${'worst path'.padStart(12)}  name`)
    for (const f of shown) {
        const fl = functionFlags(f).join(',')
        lines.push(`  ${formatNumber(f.frame).padStart(8)}  ${formatBytes(f.worstPath, f.inexact).padStart(12)}  ${f.name}${fl ? `  [${fl}]` : ''}`)
    }
    if (explain) {
        const multi = res.functions.filter(f => f.multipleSetups)
        if (multi.length) lines.push('', 'Functions with several SP reservations (max is used; sum shown if they were to stack):')
        for (const f of multi) {
            lines.push('', `  ${f.name}: sizes ${f.setupSites.map(d => d.size).join(' + ')} (max ${f.frame}, stacked ${f.frameIfStacked})`)
            for (const s of f.setupSites) {
                lines.push(`    #${s.instructionIndex} (${s.size} B):`)
                for (const c of s.code) lines.push(`      ${c}`)
            }
        }
        const dyn = res.functions.filter(f => f.dynamic)
        if (dyn.length) lines.push('', 'Unrecognized SP writes (instruction window ending at the write):')
        for (const f of dyn) {
            for (const s of f.dynamicSites) {
                lines.push('', `  ${f.name} (frame ${f.frame}), instruction #${s.instructionIndex}:`)
                for (const c of s.code) lines.push(`      ${c}`)
            }
        }
    }
    return lines.join('\n')
}