//! Package reconstruction, malformed input, and arena rollback tests.

use std::testing;

use std::lang::alloc;

use std::lang::il;

use std::lang::il::binary;

use std::lang::il::binary::reader;

use std::lang::il::binary::program;

use std::lang::il::binary::collect;

/// Decode arena backing storage. Tests reset it before each use.

static MEMORY: [u8; 2048] = [0; 2048];

/// Structural limits for small test programs.

constant LIMITS: binary::Limits = binary::Limits { registers: 16, blocks: 4 };

/// Check exact-fit package encoding and every shorter output window.

unsafe fn encodingCapacity(package: &binary::Package, expected: &[u8]) throws (testing::TestError) {

    for capacity in 0..expected.len + 1 {

        let mut buffer: [u8; 2050] = [0xa5; 2050];

        let mut failed = false;

        let count = try program::encode(&mut buffer[1..capacity + 1], package) catch err {

            assert err == binary::Error::Capacity;

            set failed = true;

            0

        };

        assert failed == (capacity < expected.len);

        assert buffer[0] == 0xa5;

        for i in capacity + 1..buffer.len { assert buffer[i] == 0xa5; }

        if not failed {

            assert count == expected.len;

            try testing::expectBytesEq(&buffer[1..count + 1], expected);

        }

    }

}

/// Check a package round trip and failure at every truncated byte length.

unsafe fn roundTrip(package: &binary::Package) throws (testing::TestError) {

    let mut buffer: [u8; 2048] = [0; 2048];

    let length = try program::encode(&mut buffer[..], package) catch {

        throw testing::TestError::Failed;

    };

    try encodingCapacity(package, &buffer[..length]);

    let memory = &mut MEMORY[..2048];

    let mut arena = alloc::new(&mut memory[..]);

    set arena.offset = 8;

    let decoded = try program::decode(&buffer[..length], &mut arena, LIMITS) catch {

        throw testing::TestError::Failed;

    };

    try testing::expectBytesEq(decoded.name, package.name);

    try testing::expect(decoded.dependencies.len == package.dependencies.len);

    try testing::expect(decoded.exports.len == package.exports.len);

    try testing::expect(decoded.program.fns.len == package.program.fns.len);

    for original, i in package.program.fns {

        let restored = decoded.program.fns[i];

        assert restored.params.len == original.params.len;

        for param, j in original.params {

            assert restored.params[j].value.n == param.value.n;

            assert restored.params[j].type == param.type;

        }

        assert restored.blocks.len == original.blocks.len;

        let mut isLeaf = true;

        for block, j in original.blocks {

            for instr in block.instrs {

                if il::isCall(instr) { set isLeaf = false; }

            }

            let rebuilt = &restored.blocks[j];

            try testing::expectBytesEq(rebuilt.label, block.label);

            assert rebuilt.loopDepth == block.loopDepth;

            assert rebuilt.params.len == block.params.len;

            for param, k in block.params {

                assert rebuilt.params[k].value.n == param.value.n;

                assert rebuilt.params[k].type == param.type;

            }

            assert rebuilt.preds.len == block.preds.len;

            for pred, k in block.preds { assert rebuilt.preds[k] == pred; }

        }

        assert restored.isLeaf == isLeaf;

    }

    let mut encoded: [u8; 2048] = [0; 2048];

    let repeated = try program::encode(&mut encoded[..], &decoded) catch {

        throw testing::TestError::Failed;

    };

    try testing::expectBytesEq(&buffer[..length], &encoded[..repeated]);

    // Decoded names and string initializers retain arena ownership.

    for i in 0..length {

        set buffer[i] = 0;

    }

    let copied = try program::encode(&mut buffer[..], &decoded) catch {

        throw testing::TestError::Failed;

    };

    try testing::expectBytesEq(&buffer[..copied], &encoded[..repeated]);

    for end in 0..length {

        set arena.offset = 8;

        let mut failed = false;

        try program::decode(&buffer[..end], &mut arena, LIMITS) catch err {

            try testing::expect(err == binary::Error::Truncated);

            set failed = true;

        };

        try testing::expect(failed);

        try testing::expect(arena.offset == 8);

    }

    set arena.offset = 8;

    let namesTable: [*[u8]; 0] = [];

    let source: 'input = &buffer[..0], names = &namesTable[..] in {

        let mut input = reader::new(source, &mut arena, names);

        let mut exhausted = false;

        try reader::storage(&mut input, 0xffffffff, 8, 0xffffffff) catch err {

            try testing::expect(err == binary::Error::Storage);

            set exhausted = true;

        };

        try testing::expect(exhausted);

        try testing::expect(arena.offset == 8);

    }

    // Exercise every smaller arena extent, including alignment boundaries.

    let mut usedArena = alloc::new(&mut memory[..]);

    let _ = try program::decode(&buffer[..length], &mut usedArena, LIMITS) catch {

        throw testing::TestError::Failed;

    };

    let required = usedArena.offset;

    for capacity in 0..required {

        let mut short = alloc::new(&mut MEMORY[..capacity]);

        let mut failed = false;

        try program::decode(&buffer[..length], &mut short, LIMITS) catch err {

            try testing::expect(err == binary::Error::Storage);

            set failed = true;

        };

        try testing::expect(failed);

        try testing::expect(short.offset == 0);

    }

}

/// Check an empty program with a package identity.

@test unsafe fn emptyPackage() throws (testing::TestError) {

    let package = binary::Package {

        symbols: &["p"], name: "p", dependencies: &[], exports: &[], entry: nil,

        program: il::Program { data: &[], fns: &[] },

    };

    try roundTrip(&package);

    let mut buffer: [u8; 64] = [0; 64];

    let length = try program::encode(&mut buffer[..], &package) catch {

        throw testing::TestError::Failed;

    };

    try testing::expectBytesEq(&buffer[..length], &[

        82, 73, 76, 0, 1, 0, 0, 0, 1, 0, 0, 0,

        1, 0, 0, 0, 112, 0, 0, 0, 0,

        0, 0, 0, 0, 0, 0, 0, 0, 0,

        0, 0, 0, 0, 0, 0, 0, 0,

    ]);

}

/// Check functions, dependencies, exports, initializers, and block metadata.

@test unsafe fn fullPackage() throws (testing::TestError) {

    let params: *unsafe [il::Param] = &[

        il::Param { value: il::Reg { n: 1 }, type: il::Type::W8 },

        il::Param { value: il::Reg { n: 4 }, type: il::Type::W16 },

        il::Param { value: il::Reg { n: 5 }, type: il::Type::W32 },

        il::Param { value: il::Reg { n: 6 }, type: il::Type::W64 },

    ];

    let mut instrs = [

        il::Instr::Call {

            retTy: il::Type::W64, dst: il::Reg { n: 2 }, func: il::Val::FnAddr("dep::fn"),

            args: &[il::Val::Reg(il::Reg { n: 1 })],

        },

        il::Instr::Ret { val: il::Val::Reg(il::Reg { n: 2 }) },

    ];

    let func = il::Fn {

        name: "p::main", params, returnType: il::Type::W64, isExtern: false, isLeaf: false,

        blocks: &[il::Block {

            label: "entry", params: &[], instrs: &mut instrs[..], locs: &[], preds: &[0], loopDepth: 2,

        }, il::Block {

            label: "empty", params: &[il::Param { value: il::Reg { n: 3 }, type: il::Type::W32 }],

            instrs: &mut [], locs: &[], preds: &[0, 1], loopDepth: 0,

        }],

    };

    let external = il::Fn {

        name: "dep::fn", params, returnType: il::Type::W64, isExtern: true, isLeaf: true, blocks: &[],

    };

    let data = il::Data {

        name: "p::data", size: 64, alignment: 8, readOnly: false, isZeroInit: false,

        values: &[

            il::DataValue { item: il::DataItem::Val { typ: il::Type::W8, val: -1 }, count: 2 },

            il::DataValue { item: il::DataItem::Val { typ: il::Type::W16, val: -2 }, count: 1 },

            il::DataValue { item: il::DataItem::Val { typ: il::Type::W32, val: -3 }, count: 1 },

            il::DataValue { item: il::DataItem::Val { typ: il::Type::W64, val: -4 }, count: 1 },

            il::DataValue { item: il::DataItem::Sym("p::data"), count: 1 },

            il::DataValue { item: il::DataItem::Fn("dep::fn"), count: 1 },

            il::DataValue { item: il::DataItem::Str("bytes"), count: 2 },

            il::DataValue { item: il::DataItem::Str(""), count: 0 },

            il::DataValue { item: il::DataItem::Undef, count: 1 },

        ],

    };

    let zero = il::Data {

        name: "p::zero", size: 4096, alignment: 4096, readOnly: false, isZeroInit: true, values: &[],

    };

    let package = binary::Package {

        symbols: &["p", "dep", "p::main", "dep::fn", "p::data", "p::zero"], name: "p",

        dependencies: &["dep"],

        exports: &[

            binary::Export { name: "p::main", kind: binary::ExportKind::Function },

            binary::Export { name: "p::data", kind: binary::ExportKind::Data },

        ],

        entry: "p::main", program: il::Program { data: retainData(&[data, zero]), fns: &[&func, &external] },

    };

    try roundTrip(&package);

}

/// Reject an invalid encoded instruction without a panic.

unsafe fn badInstruction(bytes: *[u8], expected: binary::Error) throws (testing::TestError) {

    let memory = &mut MEMORY[..64];

    let mut arena = alloc::new(&mut memory[..]);

    let namesTable: [*[u8]; 1] = ["p"];

    let source: 'input = &bytes[..], names = &namesTable[..] in {

        let mut input = reader::new(source, &mut arena, names);

        set input.registers = 2;

        set input.blocks = 1;

        let mut failed = false;

        try reader::instr(&mut input) catch err {

            try testing::expect(err == expected);

            set failed = true;

        };

        try testing::expect(failed);

    }

}

/// Check instruction tags, operand tags, types, optional flags, and indices.

@test unsafe fn malformedInstructions() throws (testing::TestError) {

    try badInstruction(&[255], binary::Error::Invalid);

    try badInstruction(&[5, 0, 0, 0, 0, 255], binary::Error::Invalid);

    try badInstruction(&[1, 3], binary::Error::Invalid);

    try badInstruction(&[6, 255], binary::Error::Invalid);

    try badInstruction(&[7, 255], binary::Error::Invalid);

    try badInstruction(&[13, 255], binary::Error::Invalid);

    try badInstruction(&[11, 2], binary::Error::Invalid);

    try badInstruction(&[10, 8, 2], binary::Error::Invalid);

    try badInstruction(&[5, 2, 0, 0, 0], binary::Error::Invalid);

    try badInstruction(&[5, 0, 0, 0, 0, 0, 2, 0, 0, 0], binary::Error::Invalid);

    try badInstruction(&[12, 1, 0, 0, 0], binary::Error::Invalid);

    try badInstruction(&[5, 0, 0, 0, 0, 2, 1, 0, 0, 0], binary::Error::Symbol);

    try badInstruction(&[12, 0, 0, 0, 0, 255, 255, 255, 255], binary::Error::Truncated);

}

/// Check header validation and package symbol indices with arena rollback.

@test unsafe fn malformedPackages() throws (testing::TestError) {

    let package = binary::Package {

        symbols: &["p"], name: "p", dependencies: &[], exports: &[], entry: nil,

        program: il::Program { data: &[], fns: &[] },

    };

    let mut buffer: [u8; 64] = [0; 64];

    let length = try program::encode(&mut buffer[..], &package) catch {

        throw testing::TestError::Failed;

    };

    let memory = &mut MEMORY[..64];

    let mut arena = alloc::new(&mut memory[..]);

    for offset in &[0, 4, 17, 29] {

        let original = buffer[offset];

        set buffer[offset] = 255;

        set arena.offset = 8;

        let mut failed = false;

        try program::decode(&buffer[..length], &mut arena, LIMITS) catch {

            set failed = true;

        };

        try testing::expect(failed);

        try testing::expect(arena.offset == 8);

        set buffer[offset] = original;

    }

    let mut trailing = false;

    try program::decode(&buffer[..length + 1], &mut arena, LIMITS) catch err {

        try testing::expect(err == binary::Error::Invalid);

        set trailing = true;

    };

    try testing::expect(trailing);

    try testing::expect(arena.offset == 8);

}

/// Reject invalid dependency and export entries after partial table decoding.

@test unsafe fn malformedHeaderTables() throws (testing::TestError) {

    let package = binary::Package {

        symbols: &["p"], name: "p", dependencies: &["p", "p"],

        exports: &[

            binary::Export { name: "p", kind: binary::ExportKind::Function },

            binary::Export { name: "p", kind: binary::ExportKind::Data },

        ],

        entry: nil, program: il::Program { data: &[], fns: &[] },

    };

    let mut buffer: [u8; 64] = [0; 64];

    let length = try program::encode(&mut buffer[..], &package) catch { throw testing::TestError::Failed; };

    for offset in [25, 29, 37, 42, 41, 46] {

        let original = buffer[offset];

        set buffer[offset] = 2;

        let mut arena = alloc::new(&mut MEMORY[..]);

        set arena.offset = 8;

        let mut failed = false;

        try program::decode(&buffer[..length], &mut arena, LIMITS) catch err {

            assert err == (binary::Error::Invalid if offset == 41 or offset == 46 else binary::Error::Symbol);

            set failed = true;

        };

        assert failed;

        assert arena.offset == 8;

        set buffer[offset] = original;

    }

}

/// Encode a malformed package and check rejection with arena rollback.

unsafe fn rejected(package: &binary::Package, limits: binary::Limits) throws (testing::TestError) {

    let mut buffer: [u8; 512] = [0; 512];

    let length = try program::encode(&mut buffer[..], package) catch {

        throw testing::TestError::Failed;

    };

    let memory = &mut MEMORY[..256];

    let mut arena = alloc::new(&mut memory[..]);

    set arena.offset = 8;

    let mut failed = false;

    try program::decode(&buffer[..length], &mut arena, limits) catch err {

        try testing::expect(err == binary::Error::Invalid);

        set failed = true;

    };

    try testing::expect(failed);

    try testing::expect(arena.offset == 8);

}

/// Check initializer extent arithmetic, alignments, and duplicate symbols.

@test unsafe fn invalidData() throws (testing::TestError) {

    let mut item = il::Data {

        name: "p", size: 0xffffffff, alignment: 8, readOnly: false, isZeroInit: false,

        values: &[

            il::DataValue { item: il::DataItem::Val { typ: il::Type::W64, val: 0 }, count: 0xffffffff },

        ],

    };

    let mut package = binary::Package {

        symbols: &["p"], name: "p", dependencies: &[], exports: &[], entry: nil,

        program: il::Program { data: retainData(&[item]), fns: &[] },

    };

    try rejected(&package, LIMITS);

    set item.size = 1;

    set item.values = &[

        il::DataValue { item: il::DataItem::Undef, count: 1 },

        il::DataValue { item: il::DataItem::Undef, count: 1 },

    ];

    set package.program = il::Program { data: retainData(&[item]), fns: &[] };

    try rejected(&package, LIMITS);

    set item.values = &[];

    for alignment in &[0, 3] {

        set item.alignment = alignment;

        set package.program = il::Program { data: retainData(&[item]), fns: &[] };

        try rejected(&package, LIMITS);

    }

    set package.program = il::Program { data: &[], fns: &[] };

    set package.symbols = &["p", "p"];

    try rejected(&package, LIMITS);

    set package.symbols = &["p", ""];

    try rejected(&package, LIMITS);

}

/// Initializer extents include every item kind and cumulative size boundaries.

@test unsafe fn initializerExtents() throws (testing::TestError) {

    for typ in [il::Type::W8, il::Type::W16, il::Type::W32, il::Type::W64] {

        try checkInitializerExtents(il::DataItem::Val { typ, val: 0 }, il::typeSize(typ));

    }

    try checkInitializerExtents(il::DataItem::Sym("p"), 8);

    try checkInitializerExtents(il::DataItem::Fn("p"), 8);

    try checkInitializerExtents(il::DataItem::Str("abc"), 3);

    try checkInitializerExtents(il::DataItem::Str(""), 0);

    try checkInitializerExtents(il::DataItem::Undef, 1);

}

/// Test one repeated item followed by a byte at exact-fit and shorter sizes.

unsafe fn checkInitializerExtents(item: il::DataItem, width: u32) throws (testing::TestError) {

    /// Stable initialized values retained by the fixture's data definition.

    static values: [il::DataValue; 2] = [il::DataValue { item: il::DataItem::Undef, count: 1 }; 2];

    for count in [0 as u32, 1, 3, 0xffffffff] {

        set values[0] = il::DataValue { item, count };

        let extent = width as u64 * count as u64 + 1;

        let size = extent as u32 if extent <= 0xffffffff else 0xffffffff;

        for declared in [size, size - 1] {

            let definition = il::Data {

                name: "p", size: declared, alignment: 1, readOnly: false, isZeroInit: false,

                values: &values[..],

            };

            let package = binary::Package {

                symbols: &["p"], name: "p", dependencies: &[], exports: &[], entry: nil,

                program: il::Program { data: retainData(&[definition]), fns: &[] },

            };

            let mut bytes: [u8; 256] = [0; 256];

            let length = try program::encode(&mut bytes[..], &package) catch { throw testing::TestError::Failed; };

            let mut arena = alloc::new(&mut MEMORY[..]);

            set arena.offset = 8;

            let mut failed = false;

            try program::decode(&bytes[..length], &mut arena, LIMITS) catch err {

                assert err == binary::Error::Invalid;

                assert arena.offset == 8;

                set failed = true;

            };

            assert failed == (extent > declared as u64);

        }

    }

}

/// Check function block limits, parameter indices, and predecessor indices.

@test unsafe fn invalidFunctions() throws (testing::TestError) {

    let mut instrs = [il::Instr::Ret { val: nil }];

    let mut block = il::Block {

        label: "entry", params: &[], instrs: &mut instrs[..], locs: &[], preds: &[], loopDepth: 0,

    };

    let mut func = il::Fn {

        name: "p", params: &[], returnType: il::Type::W64,

        isExtern: false, isLeaf: true, blocks: &[block],

    };

    let package = binary::Package {

        symbols: &["p"], name: "p", dependencies: &[], exports: &[], entry: nil,

        program: il::Program { data: &[], fns: &[&func] },

    };

    try rejected(&package, binary::Limits { registers: 16, blocks: 0 });

    set func.isExtern = true;

    try rejected(&package, LIMITS);

    set func.isExtern = false;

    set func.params = &[il::Param { value: il::Reg { n: 16 }, type: il::Type::W64 }];

    try rejected(&package, LIMITS);

    set func.params = &[];

    set block.params = &[il::Param { value: il::Reg { n: 16 }, type: il::Type::W32 }];

    set func.blocks = &[block];

    try rejected(&package, LIMITS);

    set block.params = &[];

    set block.preds = &[1];

    set func.blocks = &[block];

    try rejected(&package, LIMITS);

}

/// Reject unknown initializer tags and widths before reading their payloads.

@test unsafe fn malformedInitializers() throws (testing::TestError) {

    let memory = &mut MEMORY[..8];

    let mut arena = alloc::new(&mut memory[..]);

    let fixtures: [*[u8]; 2] = [&[255], &[0, 3]];

    for bytes in &fixtures[..] {

        let namesTable: [*[u8]; 0] = [];

        let source: 'input = &bytes[..], names = &namesTable[..] in {

            let mut input = reader::new(source, &mut arena, names);

            let mut failed = false;

            try reader::dataValue(&mut input) catch err {

                try testing::expect(err == binary::Error::Invalid);

                set failed = true;

            };

            try testing::expect(failed);

        }

    }

}

/// Check symbol collection capacity and package ownership failures.

@test unsafe fn collectionBounds() throws (testing::TestError) {

    let mut symbols: [*[u8]; 8] = [""; 8];

    let mut dependencies: [*[u8]; 1] = [""; 1];

    let empty = il::Program { data: &[], fns: &[] };

    let symbolTable: 'empty = &mut symbols[..0], dependencyTable = &mut dependencies[..] in {

        let mut names = collect::new(symbolTable, dependencyTable);

        let mut failed = false;

        try collect::package(&mut names, "p", empty, &[], nil) catch err {

            try testing::expect(err == binary::Error::Capacity);

            set failed = true;

        };

        try testing::expect(failed);

    }

    let item = il::Data {

        name: "p::data", size: 8, alignment: 8, readOnly: false, isZeroInit: false,

        values: &[il::DataValue { item: il::DataItem::Fn("dep::fn"), count: 1 }],

    };

    let local = il::Program { data: retainData(&[item]), fns: &[] };

    let symbolTable: 'capacity = &mut symbols[..], dependencyTable = &mut dependencies[..0] in {

        let mut names = collect::new(symbolTable, dependencyTable);

        let mut failed = false;

        try collect::package(&mut names, "p", local, &[], nil) catch err {

            try testing::expect(err == binary::Error::Capacity);

            set failed = true;

        };

        try testing::expect(failed);

    }

    let symbolTable: 'owner = &mut symbols[..], dependencyTable = &mut dependencies[..] in {

        let mut names = collect::new(symbolTable, dependencyTable);

        let mut failed = false;

        try collect::package(&mut names, "other", local, &[], nil) catch err {

            try testing::expect(err == binary::Error::Invalid);

            set failed = true;

        };

        try testing::expect(failed);

    }

    let symbolTable: 'valid = &mut symbols[..], dependencyTable = &mut dependencies[..] in {

        let mut names = collect::new(symbolTable, dependencyTable);

        let package = try collect::package(&mut names, "p", local, &[], nil) catch {

            throw testing::TestError::Failed;

        };

        try testing::expect(package.dependencies.len == 1);

        try testing::expectBytesEq(package.dependencies[0], "dep");

        try testing::expect(package.symbols.len == 4);

    }

}

/// Fixed instruction operands retain symbol order and bounded table writes.

@test unsafe fn fixedInstructionCollection() throws (testing::TestError) {

    let r = il::Reg { n: 0 };

    let a = il::Val::DataSym("z::data");

    let b = il::Val::FnAddr("a::fn");

    let c = il::Val::DataSym("c::data");

    let d = il::Val::FnAddr("d::fn");

    let e = il::Val::DataSym("e::data");

    let single: [*[u8]; 2] = ["z::data", "z"];

    let pair: [*[u8]; 4] = ["z::data", "z", "a::fn", "a"];

    for instr in [

        il::Instr::Reserve { dst: r, size: a, alignment: 8 },

        il::Instr::Blit { dst: r, src: r, size: a },

        il::Instr::Store { typ: il::Type::W64, src: a, dst: r, offset: 0 },

        il::Instr::Copy { dst: r, val: a },

        il::Instr::Zext { typ: il::Type::W8, dst: r, val: a },

        il::Instr::Sext { typ: il::Type::W8, dst: r, val: a },

        il::Instr::UnOp { op: il::UnOp::Neg, typ: il::Type::W64, dst: r, a },

        il::Instr::Ret { val: a },

        il::Instr::BinOp { op: il::BinOp::Add, typ: il::Type::W64, dst: r, a, b: a },

    ] { try checkInstructionNames(instr, &single[..]); }

    for instr in [

        il::Instr::BinOp { op: il::BinOp::Add, typ: il::Type::W64, dst: r, a, b },

        il::Instr::DeviceRead { typ: il::Type::W8, dst: r, handle: a, offset: b },

    ] { try checkInstructionNames(instr, &pair[..]); }

    try checkInstructionNames(il::Instr::Ecall { dst: r, num: a, a0: b, a1: c, a2: d, a3: e },

        &["z::data", "z", "a::fn", "a", "c::data", "c", "d::fn", "d", "e::data", "e"]);

    try checkInstructionNames(il::Instr::DeviceWrite { typ: il::Type::W8, handle: a, offset: b, value: c },

        &["z::data", "z", "a::fn", "a", "c::data", "c"]);

    for instr in [

        il::Instr::Load { typ: il::Type::W8, dst: r, src: r, offset: 0 },

        il::Instr::Sload { typ: il::Type::W8, dst: r, src: r, offset: 0 },

        il::Instr::Ret { val: nil },

        il::Instr::Copy { dst: r, val: il::Val::Imm(9) },

        il::Instr::Unreachable, il::Instr::Ebreak, il::Instr::MemoryFence,

    ] { try checkInstructionNames(instr, &[]); }

}

/// Variable operand groups retain first-use order and deduplicate names.

@test unsafe fn variableInstructionCollection() throws (testing::TestError) {

    let r = il::Reg { n: 0 };

    let a = il::Val::DataSym("z::data");

    let b = il::Val::FnAddr("a::fn");

    let c = il::Val::DataSym("c::data");

    let imm = il::Val::Imm(0);

    let mut args = [imm, a, a, b];

    let mut fallback = [c, a];

    try checkInstructionNames(il::Instr::Call { retTy: il::Type::W64, dst: r,

        func: b, args: &args[..] }, &["a::fn", "a", "z::data", "z"]);

    try checkInstructionNames(il::Instr::Call { retTy: il::Type::W64, dst: nil,

        func: il::Val::Reg(r), args: &[] }, &[]);

    try checkInstructionNames(il::Instr::Jmp { target: 0, args: &mut args[..] },

        &["z::data", "z", "a::fn", "a"]);

    try checkInstructionNames(il::Instr::Br { op: il::CmpOp::Eq, typ: il::Type::W64,

        a, b: imm, thenTarget: 0, thenArgs: &mut [], elseTarget: 0, elseArgs: &mut args[..] },

        &["z::data", "z", "a::fn", "a"]);

    try checkInstructionNames(il::Instr::Br { op: il::CmpOp::Eq, typ: il::Type::W64,

        a: imm, b: imm, thenTarget: 0, thenArgs: &mut args[..], elseTarget: 0, elseArgs: &mut fallback[..] },

        &["z::data", "z", "a::fn", "a", "c::data", "c"]);

    let mut cases = [il::SwitchCase { value: 0, target: 0, args: &mut [] },

        il::SwitchCase { value: 1, target: 0, args: &mut args[..] }];

    try checkInstructionNames(il::Instr::Switch { val: b, defaultTarget: 0,

        defaultArgs: &mut fallback[..], cases: &mut cases[..] },

        &["a::fn", "a", "c::data", "c", "z::data", "z"]);

    try checkInstructionNames(il::Instr::Switch { val: imm, defaultTarget: 0,

        defaultArgs: &mut [], cases: &mut [] }, &[]);

}

/// Collect one instruction at exact-fit and every shorter symbol capacity.

unsafe fn checkInstructionNames(instr: il::Instr, expected: &[*[u8]]) throws (testing::TestError) {

    let mut body = [instr];

    let function = il::Fn {

        name: "p::f", params: &[], returnType: il::Type::W64, isExtern: false, isLeaf: true,

        blocks: &[il::Block { label: "entry", params: &[], instrs: &mut body[..], locs: &[], preds: &[], loopDepth: 0 }],

    };

    let local = il::Program { data: &[], fns: &[&function] };

    for capacity in 0..expected.len + 3 {

        let mut symbols: [*[u8]; 16] = [""; 16];

        let mut dependencies: [*[u8]; 5] = [""; 5];

        let symbolTable: 'tables = &mut symbols[..capacity], dependencyTable = &mut dependencies[..] in {

            let mut names = collect::new(symbolTable, dependencyTable);

            let mut failed = false;

            try collect::package(&mut names, "p", local, &[], nil) catch err {

                assert err == binary::Error::Capacity;

                set failed = true;

            };

            assert failed == (capacity < expected.len + 2);

            assert names.symbolCount <= capacity;

            if not failed {

                assert names.symbolCount == expected.len + 2;

                try testing::expectBytesEq(names.symbols[0], "p");

                try testing::expectBytesEq(names.symbols[1], "p::f");

                for name, i in expected { try testing::expectBytesEq(names.symbols[i + 2], name); }

                assert names.dependencyCount == expected.len / 2;

            }

        }

        for i in capacity..symbols.len { assert symbols[i].len == 0; }

    }

}

/// Function definitions precede their block references in table order.

@test unsafe fn functionCollectionOrder() throws (testing::TestError) {

    let external = il::Fn { name: "p::external", params: &[], returnType: il::Type::W64,

        isExtern: true, isLeaf: true, blocks: &[] };

    let mut first = [il::Instr::Copy { dst: il::Reg { n: 0 }, val: il::Val::DataSym("z::data") }];

    let mut second = [il::Instr::Ret { val: il::Val::FnAddr("a::fn") }];

    let blocks = [

        il::Block { label: "first", params: &[], instrs: &mut first[..], locs: &[], preds: &[], loopDepth: 0 },

        il::Block { label: "empty", params: &[], instrs: &mut [], locs: &[], preds: &[], loopDepth: 0 },

        il::Block { label: "second", params: &[], instrs: &mut second[..], locs: &[], preds: &[], loopDepth: 0 },

    ];

    let function = il::Fn { name: "p::main", params: &[], returnType: il::Type::W64,

        isExtern: false, isLeaf: true, blocks: &blocks[..] };

    let local = il::Program { data: &[], fns: &[&external, &function] };

    let expected: [*[u8]; 7] = ["p", "p::external", "p::main", "z::data", "z", "a::fn", "a"];

    for capacity in 0..expected.len + 1 {

        let mut symbols: [*[u8]; 8] = [""; 8];

        let mut dependencies: [*[u8]; 2] = [""; 2];

        let symbolTable: 'tables = &mut symbols[..capacity], dependencyTable = &mut dependencies[..] in {

            let mut names = collect::new(symbolTable, dependencyTable);

            let mut failed = false;

            try collect::package(&mut names, "p", local, &[], nil) catch err {

                assert err == binary::Error::Capacity;

                set failed = true;

            };

            assert failed == (capacity < expected.len);

            assert names.symbolCount <= capacity;

            if not failed {

                assert names.symbolCount == expected.len;

                for name, i in expected { try testing::expectBytesEq(names.symbols[i], name); }

                assert names.dependencyCount == 2;

                try testing::expectBytesEq(names.dependencies[0], "z");

                try testing::expectBytesEq(names.dependencies[1], "a");

            }

        }

        for i in capacity..symbols.len { assert symbols[i].len == 0; }

    }

}

/// Exports precede the entry name, and entry definitions belong to the package.

@test unsafe fn entryCollectionOrder() throws (testing::TestError) {

    let local = il::Program { data: &[], fns: &[] };

    let exports = [

        binary::Export { name: "p::second", kind: binary::ExportKind::Function },

        binary::Export { name: "p::first", kind: binary::ExportKind::Function },

        binary::Export { name: "p::second", kind: binary::ExportKind::Function },

    ];

    let entries: [?*[u8]; 5] = [nil, "p::first", "p::start", "other::start", "p::"];

    for entry, index in entries {

        let mut symbols: [*[u8]; 4] = [""; 4];

        let mut dependencies: [*[u8]; 1] = [""; 1];

        let symbolTable: 'tables = &mut symbols[..], dependencyTable = &mut dependencies[..] in {

            let mut names = collect::new(symbolTable, dependencyTable);

            let package = try collect::package(&mut names, "p", local, &exports[..], entry) catch err {

                assert index >= 3;

                assert err == binary::Error::Invalid;

                continue;

            };

            assert index < 3;

            assert package.symbols.len == (4 if index == 2 else 3);

            for name, i in ["p", "p::second", "p::first"] {

                try testing::expectBytesEq(package.symbols[i], name);

            }

            if index == 2 { try testing::expectBytesEq(package.symbols[3], "p::start"); }

            assert package.dependencies.len == 0;

            assert package.exports.len == 3;

            assert package.entry == entry;

        }

    }

}

/// Data collection retains first-use order and unique dependencies.

@test unsafe fn dataCollectionOrder() throws (testing::TestError) {

    let item = il::Data {

        name: "p::data", size: 64, alignment: 8, readOnly: true, isZeroInit: false,

        values: &[

            il::DataValue { item: il::DataItem::Fn("z::fn"), count: 1 },

            il::DataValue { item: il::DataItem::Sym("a::data"), count: 1 },

            il::DataValue { item: il::DataItem::Fn("z::fn"), count: 1 },

            il::DataValue { item: il::DataItem::Sym("p::data"), count: 1 },

            il::DataValue { item: il::DataItem::Str("not::a::symbol"), count: 1 },

            il::DataValue { item: il::DataItem::Val { typ: il::Type::W16, val: 9 }, count: 2 },

        ],

    };

    let zero = il::Data {

        name: "p::zero", size: 32, alignment: 8, readOnly: false, isZeroInit: true, values: &[],

    };

    let local = il::Program { data: retainData(&[item, zero]), fns: &[] };