//! Recoverable backend capacity and relocation checks.

use std::testing;

use std::io;

use std::lang::alloc;

use std::lang::il;

use std::lang::gen::data;

use std::lang::gen::labels;

use std::lang::gen::bitset;

use std::lang::gen::regalloc;

use std::collections::dict;

use super::emit;

use super::encode;

/// Reusable emitter allocation storage.

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

/// Function and liveness test storage.

static SCRATCH: [u8; 65536] = [0; 65536];

/// Code output with guard words for instruction selection checks.

static SELECTION_WORDS: [u32; 130] = [0; 130];

/// Dictionary storage for bounded map tests.

unsafe static ENTRIES: [dict::Entry; 4] = undefined;

/// Build a non-debug generator with a fixed code address.

unsafe fn generator(arena: &mut alloc::Arena) -> super::Generator {

    return try! super::beginProgram(super::ProgramOptions {

        entryPatch: super::EntryPatch::None, debug: false,

        placement: super::image::Placement::Physical {

            code: 0x80000000, roData: 0x80001000, rwData: 0x80002000, entry: 0x80000000,

        },

    }, arena);

}

/// Exhaust each emitter storage class and ensure writes stop at the first error.

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

    for kind in 0..8 {

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

        let mut e = try! emit::emitter(&mut arena, false);

        match kind {

            case 0 => {

                set e.code = &mut e.code[..0];

                emit::emit(&mut e, encode::nop());

            },

            case 1 => {

                set e.pendingBranchesLen = e.pendingBranches.len;

                emit::recordBranch(&mut e, 0, emit::BranchKind::Jump);

            },

            case 2 => {

                set e.pendingCallsLen = e.pendingCalls.len;

                emit::recordCall(&mut e, "p::call");

            },

            case 3 => {

                set e.pendingJumpsLen = e.pendingJumps.len;

                emit::recordJumpAt(&mut e, "p::jump", super::ZERO, 0);

            },

            case 4 => {

                set e.pendingAddrLoadsLen = e.pendingAddrLoads.len;

                emit::recordDataAddrLoad(&mut e, "p::data", super::A0);

            },

            case 5 => {

                set e.funcsLen = e.funcs.len;

                emit::recordFunc(&mut e, "p::call");

            },

            case 6 => {

                let entries = &mut ENTRIES[..2];

                set e.labels.funcs = dict::init(&mut entries[..]);

                emit::recordFuncOffset(&mut e, "p::first");

                emit::recordFuncOffset(&mut e, "p::second");

            },

            else => {

                emit::recordSrcLoc(&mut e, il::SrcLoc { moduleId: 0, offset: 0 });

            },

        }

        try testing::expect(e.error == super::Error::Capacity);

        let count = e.codeLen;

        emit::emit(&mut e, encode::ebreak());

        try testing::expect(e.codeLen == count);

        let mut rejected = false;

        try emit::check(&e) catch err {

            try testing::expect(err == super::Error::Capacity); set rejected = true;

        };

        try testing::expect(rejected);

    }

}

/// Missing labels and long jumps return errors without corrupting instructions.

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

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

    let mut e = try! emit::emitter(&mut arena, false);

    emit::recordCall(&mut e, "missing");

    emit::patchCalls(&mut e);

    try check(e.error == super::Error::Symbol, "missing function");

    alloc::reset(&mut arena);

    set e = try! emit::emitter(&mut arena, false);

    emit::recordBranch(&mut e, 0, emit::BranchKind::Jump);

    labels::recordBlock(&mut e.labels, 0, 0x200000);

    emit::patchLocalBranches(&mut e);

    try check(e.error == super::Error::Relocation, "long branch");

    try check(e.code[0] == encode::nop(), "rejected branch unchanged");

    alloc::reset(&mut arena);

    set e = try! emit::emitter(&mut arena, false);

    let blockCount = e.labels.blockOffsets.len;

    emit::recordBlock(&mut e, blockCount);

    try check(e.error == super::Error::Capacity, "block capacity");

}

/// Arena setup and per-function failures restore their saved offsets for reuse.

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

    let small = &mut SCRATCH[..64];

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

    set arena.offset = 8;

    let mut failed = false;

    try super::beginProgram(super::ProgramOptions {

        entryPatch: super::EntryPatch::None, debug: false, placement: super::image::Placement::Hosted,

    }, &mut arena) catch err {

        try check(err == super::Error::Allocation, "generator allocation"); set failed = true;

    };

    try check(failed and arena.offset == 8, "generator arena restored");

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

    let mut gen = generator(&mut code);

    let mut instructions = [

        il::Instr::Copy { dst: il::Reg { n: 0 }, val: il::Val::Imm(1) },

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

    ];

    let func = il::Fn {

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

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

    };

    super::generateFunction(&mut gen, &func, &mut arena);

    try check(gen.e.error == super::Error::Allocation and arena.offset == 8, "function arena restored");

    alloc::reset(&mut code);

    set gen = generator(&mut code);

    let mut scratch = alloc::new(&mut SCRATCH[..]);

    set scratch.offset = 16;

    super::generateFunction(&mut gen, &func, &mut scratch);

    try check(gen.e.error == nil and gen.e.codeLen > 0 and scratch.offset == 16, "function retry");

    alloc::reset(&mut code);

    set gen = generator(&mut code);

    set instructions[0] = il::Instr::Copy { dst: il::Reg { n: 8192 }, val: il::Val::Imm(1) };

    super::generateFunction(&mut gen, &func, &mut scratch);

    try check(gen.e.error == super::Error::Allocation and scratch.offset == 16, "SSA capacity");

}

/// Spill candidate storage fails explicitly when too many values are live.

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

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

    use arena as bits in {

        let liveSet = try! bitset::allocate(&bits, 257);

        for i in 0..257 {

            bitset::put(liveSet, i);

        }

        let live = regalloc::liveness::LiveInfo 'bits {

            liveIn: &liveSet[..0], liveOut: &liveSet[..],

            defs: &liveSet[..0], uses: &liveSet[..0],

            words: bitset::wordsFor(257), blockCount: 1, maxReg: 257,

        };

        let func = il::Fn {

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

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

        };

        let mut failed = false;

        try regalloc::spill::analyze(&func, &live, 23, 11, 8, &bits) catch {

            set failed = true;

        };

        try testing::expect(failed);

    }

}

/// Data output and symbol maps reject insufficient or ambiguous storage.

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

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

    let e = try! emit::emitter(&mut arena, false);

    let syms = &[data::DataSym { name: "p::data", addr: 0x80002000 }];

    let entries = &mut ENTRIES[..2];

    let map = try! data::buildMap(syms, &mut entries[..]);

    let items = &[il::Data {

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

        values: &[il::DataValue { item: il::DataItem::Val { typ: il::Type::W64, val: 1 }, count: 1 }],

    }];

    let mut bytes: [u8; 8] = [255; 8];

    let mut failed: u32 = 0;

    try data::emitSection(items, &map, &e.labels, 0x80000000, &mut bytes[..7], false) catch err {

        try testing::expect(err == data::Error::Capacity); set failed += 1;

    };

    try data::buildMap(syms, &mut entries[..1]) catch err {

        try testing::expect(err == data::Error::Capacity); set failed += 1;

    };

    let larger = &mut ENTRIES[..4];

    unsafe static duplicate: [data::DataSym; 2] = undefined;

    set duplicate = [syms[0], syms[0]];

    try data::buildMap(&duplicate[..], &mut larger[..]) catch err {

        try testing::expect(err == data::Error::Symbol); set failed += 1;

    };

    try testing::expect(failed == 3);

    let length = try data::emitSection(items, &map, &e.labels, 0x80000000, &mut bytes[..], false)

        catch {

            throw testing::TestError::Failed;

        };

    try testing::expect(length == 8 and bytes[0] == 1);

}

/// Inline instruction selection respects every shorter output capacity.

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

    let dst = il::Reg { n: 3 };

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

    let second = il::Reg { n: 1 };

    let a = il::Val::Reg(first);

    let b = il::Val::Reg(second);

    let instructions = [

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

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

        il::Instr::Load { typ: il::Type::W8, dst, src: first, offset: 4096 },

        il::Instr::Sload { typ: il::Type::W16, dst, src: first, offset: -4096 },

        il::Instr::Store { typ: il::Type::W32, src: a, dst: second, offset: 4096 },

        il::Instr::Copy { dst, val: il::Val::Imm(0x123456789abcdef) },

        il::Instr::Reserve { dst, size: il::Val::Imm(32), alignment: 16 },

        il::Instr::Reserve { dst, size: a, alignment: 16 },

        il::Instr::Blit { dst: first, src: second, size: il::Val::Imm(0) },

        il::Instr::Blit { dst: first, src: second, size: il::Val::Imm(8) },

        il::Instr::Blit { dst: first, src: second, size: il::Val::Imm(40) },

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

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

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

        il::Instr::Unreachable,

        il::Instr::Ecall { dst, num: a, a0: b, a1: a, a2: b, a3: a },

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

        il::Instr::DeviceWrite { typ: il::Type::W8, handle: a, offset: b, value: a },

        il::Instr::Ebreak,

        il::Instr::MemoryFence,

    ];

    for instr in instructions {

        try checkSelectionCapacity(instr, nil);

    }

}

/// Direct and indirect calls check argument and output capacities.

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

    let a = il::Val::Reg(il::Reg { n: 0 });

    let b = il::Val::Reg(il::Reg { n: 1 });

    let args = [b, a, b, a, il::Val::Imm(7), a, b, a, a];

    for callee in [il::Val::FnAddr("p::callee"), a] {

        for dst in [nil as ?il::Reg, il::Reg { n: 3 }] {

            for count in [0 as u32, 8, 9] {

                let instr = il::Instr::Call {

                    retTy: il::Type::W64, dst, func: callee, args: &args[..count],

                };

                let expected: ?super::Error = super::Error::Capacity if count == 9 else nil;

                try checkSelectionCapacity(instr, expected);

            }

        }

    }

}

/// Switch cases and default edges respect every shorter output capacity.

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

    for count in 0..3 {

        for argumentMask in 0..8 {

            try checkSwitchCapacity(count, argumentMask);

        }

    }

}

/// Build a switch with independently selected case and default arguments.

unsafe fn checkSwitchCapacity(count: u32, argumentMask: u32) throws (testing::TestError) {

    let params = [il::Param { value: il::Reg { n: 0 }, type: il::Type::W64 }];

    let firstParams = [il::Param { value: il::Reg { n: 1 }, type: il::Type::W64 }];

    let secondParams = [il::Param { value: il::Reg { n: 2 }, type: il::Type::W64 }];

    let defaultParams = [il::Param { value: il::Reg { n: 3 }, type: il::Type::W64 }];

    let firstCount: u32 = 1 if argumentMask & 1 <> 0 else 0;

    let secondCount: u32 = 1 if argumentMask & 2 <> 0 else 0;

    let defaultCount: u32 = 1 if argumentMask & 4 <> 0 else 0;

    let mut firstArgs = [il::Val::Imm(11)];

    let mut secondArgs = [il::Val::Imm(22)];

    let mut defaultArgs = [il::Val::Reg(il::Reg { n: 0 })];

    let mut cases = [

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

        il::SwitchCase { value: 0x123456789abcdef, target: 2, args: &mut secondArgs[..secondCount] },

    ];

    let mut entry = [il::Instr::Switch {

        val: il::Val::Reg(il::Reg { n: 0 }), defaultTarget: 3,

        defaultArgs: &mut defaultArgs[..defaultCount], cases: &mut cases[..count],

    }];

    let mut first = [il::Instr::Ret {

        val: il::Val::Reg(il::Reg { n: 1 }) if firstCount > 0 else il::Val::Imm(11),

    }];

    let mut second = [il::Instr::Ret {

        val: il::Val::Reg(il::Reg { n: 2 }) if secondCount > 0 else il::Val::Imm(22),

    }];

    let mut fallback = [il::Instr::Ret {

        val: il::Val::Reg(il::Reg { n: 3 }) if defaultCount > 0 else il::Val::Imm(33),

    }];

    let predecessors = [0 as u32];

    let blocks = [

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

        il::Block {

            label: "first", params: &firstParams[..firstCount], instrs: &mut first[..],

            locs: &[], preds: &predecessors[..1 if count > 0 else 0], loopDepth: 0,

        },

        il::Block {

            label: "second", params: &secondParams[..secondCount], instrs: &mut second[..],

            locs: &[], preds: &predecessors[..1 if count > 1 else 0], loopDepth: 0,

        },

        il::Block {

            label: "default", params: &defaultParams[..defaultCount], instrs: &mut fallback[..],

            locs: &[], preds: &predecessors[..], loopDepth: 0,

        },

    ];

    let func = il::Fn {

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

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

    };

    try checkFunctionCapacity(&func, nil);

}

/// Jumps preserve argument moves and capacity checks in both block layouts.

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

    for target in [1 as u32, 2] {

        for count in 0..3 {

            let params = [

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

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

            ];

            let targetParams = [

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

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

            ];

            let mut args = [il::Val::Reg(il::Reg { n: 1 }), il::Val::Reg(il::Reg { n: 0 })];

            let mut entry = [il::Instr::Jmp { target, args: &mut args[..count] }];

            let mut body = [il::Instr::Ret {

                val: il::Val::Reg(il::Reg { n: count + 1 }) if count > 0 else il::Val::Imm(7),

            }];

            let mut unused = [il::Instr::Ret { val: il::Val::Imm(0) }];

            let destination = il::Block {

                label: "destination", params: &targetParams[..count], instrs: &mut body[..],

                locs: &[], preds: &[0], loopDepth: 0,

            };

            let other = il::Block {

                label: "other", params: &[], instrs: &mut unused[..],

                locs: &[], preds: &[], loopDepth: 0,

            };

            let blocks = [

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

                destination if target == 1 else other,

                other if target == 1 else destination,

            ];

            let func = il::Fn {

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

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

            };

            try checkFunctionCapacity(&func, nil);

        }

    }

}

/// Conditional edges preserve capacity checks for each comparison and layout.

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

    for op in [il::CmpOp::Eq, il::CmpOp::Ne, il::CmpOp::Slt, il::CmpOp::Ult] {

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

            for layout in 0..2 {

                for argumentSide in 0..3 {

                    try checkBranchCapacity(op, typ, layout, argumentSide);

                }

            }

        }

    }

}

/// Build a branch with no arguments or arguments on exactly one edge.

unsafe fn checkBranchCapacity(op: il::CmpOp, typ: il::Type, layout: u32, argumentSide: u32)

    throws (testing::TestError)

{

    let a = il::Val::Reg(il::Reg { n: 0 });

    let b = il::Val::Reg(il::Reg { n: 1 });

    let params = [

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

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

    ];

    let thenParams = [il::Param { value: il::Reg { n: 2 }, type: il::Type::W64 }];

    let elseParams = [il::Param { value: il::Reg { n: 3 }, type: il::Type::W64 }];

    let thenCount: u32 = 1 if argumentSide == 1 else 0;

    let elseCount: u32 = 1 if argumentSide == 2 else 0;

    let mut thenArgs = [b];

    let mut elseArgs = [a];

    let mut entry = [il::Instr::Br {

        op, typ, a, b: il::Val::Imm(0) if argumentSide == 1 else b,

        thenTarget: 1 if layout == 0 else 2, thenArgs: &mut thenArgs[..thenCount],

        elseTarget: 2 if layout == 0 else 1, elseArgs: &mut elseArgs[..elseCount],

    }];

    let mut thenBody = [il::Instr::Ret {

        val: il::Val::Reg(il::Reg { n: 2 }) if thenCount > 0 else il::Val::Imm(10),

    }];

    let mut elseBody = [il::Instr::Ret {

        val: il::Val::Reg(il::Reg { n: 3 }) if elseCount > 0 else il::Val::Imm(20),

    }];

    let thenBlock = il::Block {

        label: "then", params: &thenParams[..thenCount], instrs: &mut thenBody[..],

        locs: &[], preds: &[0], loopDepth: 0,

    };

    let elseBlock = il::Block {

        label: "else", params: &elseParams[..elseCount], instrs: &mut elseBody[..],

        locs: &[], preds: &[0], loopDepth: 0,

    };

    let blocks = [

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

        thenBlock if layout == 0 else elseBlock,

        elseBlock if layout == 0 else thenBlock,

    ];

    let func = il::Fn {

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

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

    };

    try checkFunctionCapacity(&func, nil);

}

/// Verify instruction errors, exact-fit output, and shorter-buffer canaries.

unsafe fn checkSelectionCapacity(instr: il::Instr, expectedError: ?super::Error) throws (testing::TestError) {

    let mut body = [instr, il::Instr::Ret { val: il::Val::Imm(0) }];

    let mut count: u32 = 2;

    if let case il::Instr::Ret { .. } = instr {

        set count = 1;

    }

    let params = [

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

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

    ];

    let func = il::Fn {

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

        isExtern: false, isLeaf: not il::isCall(instr),

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

    };

    try checkFunctionCapacity(&func, expectedError);

}

/// Verify function output capacity and failure propagation with guard words.

unsafe fn checkFunctionCapacity(func: &il::Fn, expectedError: ?super::Error) throws (testing::TestError) {

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

    let mut gen = generator(&mut arena);

    let mut scratch = alloc::new(&mut SCRATCH[..]);

    super::generateFunction(&mut gen, func, &mut scratch);

    assert gen.e.error == expectedError;

    if expectedError <> nil {

        let count = gen.e.codeLen;

        emit::emit(&mut gen.e, encode::nop());

        assert gen.e.codeLen == count;

        return;

    }

    let length = gen.e.codeLen;

    let mut expected: [u32; 128] = [0; 128];

    assert length > 0 and length <= expected.len;

    for i in 0..length {

        set expected[i] = gen.e.code[i];

    }

    for capacity in 0..(length + 1) {

        let words = &mut SELECTION_WORDS[..];

        for i in 0..words.len {

            set words[i] = 0xdeadbeef;

        }

        alloc::reset(&mut arena);

        set gen = generator(&mut arena);

        set gen.e.code = &mut words[1..capacity + 1];

        super::generateFunction(&mut gen, func, &mut scratch);

        assert gen.e.codeLen <= capacity;

        assert words[0] == 0xdeadbeef;

        for i in (capacity + 1)..words.len {

            assert words[i] == 0xdeadbeef;

        }

        if capacity == length {

            assert gen.e.error == nil;

            assert gen.e.codeLen == length;

            for i in 0..length {

                assert words[i + 1] == expected[i];

            }

        } else {

            assert gen.e.error == super::Error::Capacity;

        }

    }

}

/// Name the failed invariant before returning to the test runner.

fn check(condition: bool, name: *[u8]) throws (testing::TestError) {

    if not condition {

        io::printLn(name);

        throw testing::TestError::Failed;

    }

}