LiL

local LIL_VERSION = "0.1"

local LUACEPTION_LEVEL = (os._LUACEPTION_LEVEL or 0) + 1

-- Yields if necessary
local yield

-- pullQueuedEvent([filter]) - like os.pullEvent but can return events previously queued by yield
local pullQueuedEvent
do
    local event_queue = {}
    local lastYield
    local key = "dummy "..tostring({})
    local function doYield()
        lastYield = os.clock()
        os.queueEvent(key)
        while true do
            local evt = {os.pullEvent()}
            if evt[1] ~= key then
                table.insert(event_queue, evt)
                while #event_queue > 100 do
                    table.remove(event_queue, 1)
                end
            else
                break
            end
        end
    end
    function yield()
        if lastYield < os.clock() - 0.1 then
            doYield()
        end
    end
    doYield()

    function pullQueuedEvent(filter)
        if filter ~= nil then
            while #event_queue > 0 and event_queue[1][1] ~= filter do
                table.remove(event_queue, 1)
            end
        end
        if #event_queue > 0 then
            return table.remove(event_queue, 1)
        else
            return {os.pullEvent(filter)}
        end
    end
end

local function tokenize(c, locprefix)
    local tokens = {}

    locprefix = locprefix or "[string]"

    local pos = 1

    local line = 1
    local char = 1

    local lasttok
    local function accept(regex)
        --print(regex, " ", pos)
        --yield()
        local r = c:match("^"..regex, pos)
        if r == nil then return false end
        lasttok = r
        pos = pos + #lasttok

        for k=1,#r do
            if r:sub(k,k) == "\n" then
                line = line + 1
                char = 1
            else
                char = char + 1
            end
        end

        return true
    end

    local function getContext()
        return {prefix=locprefix, line=line, char=char}
        --return c:sub(pos, pos+100)
    end

    local keywords = {"do","end","function","while","repeat","until","if","then","elseif","then","else","for","in","local","return","break",
    "nil","false","true",
    "%.%.%.","==","~=","%.%.","<=",">=","and","or","not",
    "[-+;.:+*/,=%[%]%(%)%<%>%^%%#{}]"}
    local function tokenise1()
        accept("[ \r\n\t]+")
        if accept("%-%-%[%[") then
            while not accept("%]%]") do
                if not accept("[^%]]+") then accept(".") end
            end
            return tokenise1()
        end
        if accept("%-%-[^\n]*\n") then return tokenise1() end
        if accept("[a-zA-Z_][a-zA-Z_0-9]*") then
            for k,v in ipairs(keywords) do
                if lasttok == v then return v end
            end
            return "id"
        end
        for k,v in ipairs(keywords) do if accept(v) then return lasttok end end
        if accept("[0-9]+%.[0-9]*") or accept("[0-9]+") then return "num" end
        if accept("\"") or accept("%[%[") then
            local s = ""
            local long = lasttok == "[["
            local _end = long and "%]%]" or "\""
            while not accept(_end) do
                if accept("\\") then
                        if accept("a") then s=s.."\a"
                    elseif accept("b") then s=s.."\b"
                    elseif accept("f") then s=s.."\f"
                    elseif accept("n") then s=s.."\n"
                    elseif accept("r") then s=s.."\r"
                    elseif accept("t") then s=s.."\t"
                    elseif accept("v") then s=s.."\v"
                    elseif accept("\\") then s=s.."\\"
                    elseif accept("\"") then s=s.."\""
                    elseif accept("'") then s=s.."\'"
                    elseif accept("%[") then s=s.."["
                    elseif accept("%]") then s=s.."]"
                    elseif accept("[0-9][0-9][0-9]") or accept("[0-9][0-9]") or accept("[0-9]") then s=s..string.char(tonumber(lasttok))
                    end
                elseif accept(long and "[^%]\\]+" or "[^\n\"\\]+") then s=s..lasttok
                else error("unfinished string")
                end
            end
            lasttok = s
            return "str"
        end
        if pos > #c then lasttok="" return "<eof>" end
        error("Unknown token near "..c:sub(pos-50,pos+100))
        return nil
    end

    while pos <= #c do
        local t = tokenise1()
        if t == nil then --[[print(c:sub(pos,pos+100))]] break end
        table.insert(tokens, {t, lasttok, getContext()})
    end

    do
        local f = fs.open("tokens.txt", "w")
        for k,v in ipairs(tokens) do
            if v[1] == v[2] then
                f.write(v[1].."\n")
            else
                f.write(v[1].." : "..v[2].."\n")
            end
        end
        f.close()
    end

    return tokens
end

local function tokenizeFile(fn)
    local f = fs.open(fn,"r")
    local c = f.readAll()
    f.close()
    return tokenize(c, fn)
end

local function parse(tokens)
    local ntok = 1
    local tdata, context = nil, tokens[1][3]
    local function accept(name)
        if ntok > #tokens then return false end
        if tokens[ntok][1] == name then
            ntok = ntok + 1
            tdata = tokens[ntok-1][2]
            context = tokens[ntok-1][3]
            --print("accepted "..name)
            return true
        end
        return false
    end

    local function peek(name)
        return ntok <= #tokens and tokens[ntok][1] == name
    end

    local function expect(name)
        if not accept(name) then error("expected "..name.." near "..tokens[ntok][3],2) end
        return tdata
    end

    local function assert(a, b)
        if a == nil then error(b.." near "..tokens[ntok][3],2) end
        return a
    end

    local block, stat, laststat, funcname, varlist, var, namelist, explist, exp, prefixexp, functioncall, args, function_, funcbody
    local parlist, tableconstructor, fieldlist, field, fieldsep, binop, unop

    function block()
        local r = {}
        local s
        repeat
            s = stat()
            table.insert(r, s)
            accept(";")
        until s == nil
        table.insert(r, laststat())
        accept(";")
        return r
    end

    function stat()
        local nt = ntok
        do
            local vl = varlist()
            if vl ~= nil then
                expect("=")
                local al = explist()
                if al == nil then return nil end
                return {"=", vl, al, context=context}
            end
        end

        ntok = nt
        do
            local fc = prefixexp()
            if fc ~= nil and (fc[1] == "call" or fc[1] == ":call") then return fc end
        end

        local ctx = context

        ntok = nt
        if accept("do") then
            local b = assert(block(), "expected block")
            expect("end")
            return {"block", b}
        elseif accept("while") then
            local e = exp()
            if e == nil then error("expected expression") end
            expect("do")
            local b = assert(block(), "expected block")
            expect("end")
            return {"while", e, b, context=ctx}
        elseif accept("repeat") then
            local b = block()
            expect("until")
            local e = exp()
            if e == nil then error("expected expression") end
            return {"repeat", b, e, context=ctx}
        elseif accept("if") then
            local r = {"if", context=ctx}
            table.insert(r, assert(exp(), "expected expression"))
            expect("then")
            table.insert(r, block())
            while accept("elseif") do
                table.insert(r, assert(exp(), "expected expression"))
                expect("then")
                table.insert(r, block())
            end
            if accept("else") then
                table.insert(r, block())
            end
            expect("end")
            return r
        elseif accept("for") then
            nt = ntok
            local nl = namelist()
            if nl == nil or not accept("in") then
                ntok = nt
                -- numeric for
                expect("id")
                local id = tdata
                expect("=")
                local start = assert(exp(), "expected expression")
                expect(",")
                local stop = assert(exp(), "expected expression")
                local step = {"con", 1}
                if accept(",") then
                    step = assert(exp(), "expected expression")
                end
                expect("do")
                local b = block()
                expect("end")
                return {"nfor", id, start, stop, step, b, context=ctx}
            else
                -- generic for
                local el = explist()
                expect("do")
                local b = block()
                expect("end")
                return {"gfor", nl, el, b, context=ctx}
            end
        elseif accept("function") then
            local fn = assert(funcname(), "expected funcname")
            local fb = funcbody()
            return {"funcst", fn, fb, context=ctx}
        elseif accept("local") then
            if accept("function") then
                local id = expect("id")
                local fb = funcbody()
                return {"lfunc", id, fb, context=ctx}
            else
                local nl, el = assert(namelist(), "expected namelist")
                if accept("=") then
                    el = assert(explist(), "expected explist")
                end
                return {"local", nl, el, context=ctx}
            end
        else
            return nil
        end
    end

    function laststat()
        if accept("return") then
            local nt = ntok
            local el = explist()
            if el == nil then ntok = nt end
            return {"return", el, context=context}
        elseif accept("break") then
            return {"break", context=context}
        else
            return nil
        end
    end

    function funcname()
        local n = {".", expect("id")}
        while accept(".") do
            table.insert(n, expect("id"))
        end
        if accept(":") then
            n[1] = ":"
            table.insert(n, expect("id"))
        end
        return n
    end

    function varlist()
        local l = {}
        repeat
            local v = var()
            if v == nil then
                return nil
            end
            table.insert(l, v)
        until not accept(",")
        return l
    end

    function var()
        local nt = ntok
        local pe = prefixexp()
        if pe == nil or (pe[1] ~= "[]" and pe[1] ~= "." and pe[1] ~= "var") then
            ntok = nt
            return nil
        end
        return pe
    end

    function namelist()
        local l = {expect("id")}
        while accept(",") do
            table.insert(l, expect("id"))
        end
        return l
    end

    function explist()
        local l = {exp()}
        if l[1] == nil then return {} end
        while accept(",") do
            table.insert(l, assert(exp(), "expected expression"))
        end
        return l
    end

    local function exp0()
        if accept("nil") then return {"con", nil, context=context} end
        if accept("true") then return {"con", true, context=context} end
        if accept("false") then return {"con", false, context=context} end
        if accept("num") then return {"con", tonumber(tdata), context=context} end
        if accept("str") then return {"con", tdata, context=context} end
        if accept("...") then return {"...", context=context} end
        if accept("function") then return {"func", funcbody(), context=context} end
        if accept("-") then return {"negate", exp0(), context=context} end
        if accept("not") then return {"not", exp0(), context=context} end
        if accept("#") then return {"#", exp0(), context=context} end
        if peek("{") then return {"tcon", tableconstructor(), context=context} end
        do
            local nt = ntok
            local pe = prefixexp()
            if pe ~= nil then
                return pe
            end
            ntok = nt
        end
        if accept("(") then
            local e = assert(exp(), "expected expression")
            expect(")")
            return e
        end
        return nil
    end

    local function exp1()
        local e = exp0()
        if e == nil then return nil end
        -- right associative
        -- {"^", a, {"^", b, {"^", c, d}}}
        if accept("^") then
            e = {"^", e, assert(exp0(), "expected expression"), context=context}
            local last = e
            while accept("^") do
                last[3] = {"^", last[3], assert(exp0(), "expected expression"), context=context}
                last = last[3]
            end
        end
        return e
    end

    local function exp1_5()
        local e = exp1()
        if e == nil then return nil end
        while accept("%") do e={"%", e, assert(exp1(), "expected expression"), context=context} end
        return e
    end

    local function exp2()
        local e = exp1_5()
        if e == nil then return nil end
        while accept("/") do e={"/", e, assert(exp1_5(), "expected expression"), context=context} end
        return e
    end

    local function exp3()
        local e = exp2()
        if e == nil then return nil end
        while accept("*") do e={"*", e, assert(exp2(), "expected expression"), context=context} end
        return e
    end

    local function exp4()
        local e = exp3()
        if e == nil then return nil end
        while accept("-") do e={"-", e, assert(exp3(), "expected expression"), context=context} end
        return e
    end

    local function exp5()
        local e = exp4()
        if e == nil then return nil end
        while accept("+") do e={"+", e, assert(exp4(), "expected expression"), context=context} end
        return e
    end

    local function exp6()
        local e = exp5()
        if e == nil then return nil end
        -- right associative
        -- {"^", a, {"^", b, {"^", c, d}}}
        if accept("..") then
            e = {"..", e, assert(exp5(), "expected expression")}
            local last = e
            while accept("..") do
                last[3] = {"..", last[3], assert(exp5(), "expected expression"), context=context}
                last = last[3]
            end
        end
        return e
    end

    local function exp7()
        local e = exp6()
        if e == nil then return nil end
        while accept(">") or accept(">=") or accept("<") or accept("<=") or accept("==") or accept("~=") do
            e = {tdata, e, assert(exp6(), "expected expression"), context=context}
        end
        return e
    end

    local function exp8()
        local e = exp7()
        if e == nil then return nil end
        while accept("and") do e={"and", e, assert(exp7(), "expected expression"), context=context} end
        return e
    end

    local function exp9()
        local e = exp8()
        if e == nil then return nil end
        while accept("or") do e={"or", e, assert(exp8(), "expected expression"), context=context} end
        return e
    end

    function exp()
        return exp9()
    end

    function prefixexp()
        -- prefixexp = Name | prefixexp [ exp ] | prefixexp . Name | prefixexp : Name args | prefixexp args | ( exp )
        local r
        if accept("id") then
            r = {"var", tdata, context=context}
        elseif accept("(") then
            local e = assert(exp(), "expression expected")
            expect(")")
            r = {"()", e, context=context}
        else
            return nil
        end
        while true do
            if accept(".") then
                local e = expect("id")
                r = {".", r, e, context=context}
            elseif accept("[") then
                local e = assert(exp(), "expression expected")
                expect("]")
                r = {"[]", r, e, context=context}
            elseif peek("(") or peek("{") or peek("str") then
                local e = args()
                r = {"call", r, e, context=context}
            elseif accept(":") then
                local i = expect("id")
                local e = args()
                r = {":call", r, i, e, context=context}
            else
                break
            end
        end
        return r
    end

    function funcbody()
        local p, b
        expect("(")
        if not accept(")") then
            p = parlist()
            expect(")")
        else
            p = {}
        end
        b = block()
        expect("end")
        return {p, b}
    end

    function parlist()
        if accept("...") then return {"..."} end
        local l = {expect("id")}
        while accept(",") do
            if accept("...") then
                table.insert(l, "...")
                break
            else
                table.insert(l, expect("id"))
            end
        end
        return l
    end

    function tableconstructor()
        expect("{")
        local fl = fieldlist()
        expect("}")
        return fl
    end

    function fieldlist()
        local fl = {}
        while true do
            local f = field()
            if f == nil then break end
            table.insert(fl, f)
            if not accept(";") and not accept(",") then break end
        end
        return fl
    end

    function field()
        if accept("[") then
            local e = assert(exp(), "expression expected")
            expect("]")
            expect("=")
            return {e, assert(exp(), "expression expected")}
        end
        local nt = ntok
        if accept("id") then
            local e = {"con", tdata}
            if accept("=") then
                return {e, assert(exp(), "expression expected")}
            else
                ntok = nt
            end
        end
        local e = exp()
        if e == nil then return nil end
        return {"auto", e}
    end

    function args()
        if peek("{") then return {{"tcons", tableconstructor(), context=context}} end
        if accept("str") then return {{"con", tdata, context=context}} end
        expect("(")
        local el = explist()
        expect(")")
        return el
    end

    return block()
end

local function interpret(ast_list)
    local DEFAULT_GLOBAL_ENV = {} -- initialized later

    local log
    local DISABLE_LOG = true
    local logfile = nil
    if not DISABLE_LOG then
        logfile = fs.open("log.txt", "w")
        log = function(s)
            logfile.write(s.."\n")
        end
    else
        log = function() end
    end

    local expr, callfunc, block, stmt, funcdef

    local function assert(test, message, level)
        if not test then error(message or "assertion failed!", (level or 1)+1) end
        return test
    end

    -- Allow throwing of non-string errors
    local oldError, oldPcall = error, pcall
    local error, pcall
    do
        local err
        function error(x, level)
            err = x
            if (level or 1) == 0 then
                oldError("exterr", 0)
            else
                if type(x) == "table" then x.lualoc = scope.context end
                oldError("exterr", (level or 1) + 1)
            end
        end
        function pcall(f, ...)
            local rv = {oldPcall(f, ...)}
            if rv[1] then
                -- no error
                return unpack(rv)
            end
            -- error
            local err2 = rv[2]
            if err2 and err2:len() >= 6 and err2:sub(-6) == "exterr" then
                -- thrown with the overridden error()
                local location = err2:sub(1, -7)
                if type(err) == "string" then
                    return false, location..err
                elseif type(err) == "table" then
                    if location ~= "" then err.location = location end
                    return false, err
                else
                    return false, err
                end
            else
                -- normal error
                return false, err2
            end
        end
    end

    local scope = {env=DEFAULT_GLOBAL_ENV}
    local scopeStack = {scope}
    local function pushScope(sc)
        scope = sc or setmetatable({context="", vars = setmetatable({}, {__index=scope.vars})}, {__index=scope})
        table.insert(scopeStack, scope)
        --log("pushScope "..(#scopeStack-1).." -> "..#scopeStack)
    end
    local function popScope()
        --log("popScope "..(#scopeStack).." -> "..(#scopeStack-1))
        table.remove(scopeStack, #scopeStack)
        scope = scopeStack[#scopeStack]
    end
    local function addLocal(name, val)
        if val == nil then error({"interp", "expected two arguments"}, 2) end
        if val.type == nil then error({"interp", "corrupt table"}, 2) end
        scope.vars[name] = {val=val}
    end
    -- Returns the highest scope of the (n-1)'th function call
    -- Eg if scopes 5 and 12 correspond to new functions, getStackLevel(2) returns scope 11 and getStackLevel(3) returns scope 4
    -- getStackLevel(1) always returns the top scope
    local function getStackLevel(n)
        if n ~= math.floor(n) or n < 0 then
            error{"lua", "expected non-negative integer"}
        end
        if n == 0 then n = 1 end
        local pos = #scopeStack
        for k=2,n do
            while not pos.fn do
                pos = pos - 1
                if pos <= 0 then
                    error{"lua", "invalid level"}
                end
            end
            pos = pos - 1
            if pos <= 0 then
                error{"lua", "invalid level"}
            end
        end
        return scopeStack[pos]
    end
    local function interp_rawget(t, name)
        if name == nil or name.type == "nil" then return nil end
        if t.type == nil then error("corrupt table",2) end
        if t.type ~= "table" then error({"lua", "attempt to index " .. t.type .. " value"}) end
        if t.val[name.type] ~= nil then
            local tt = t.val[name.type]
            if tt[name.val] then
                return tt[name.val]
            else
                return {type="nil"}
            end
        else
            return {type="nil"}
        end
    end
    local function interp_rawset(t, name, value)
        if name == nil or name.type == "nil" then error({"lua", "expected table index; got nil"}) end
        if t.type ~= "table" then error({"lua", "attempt to index " .. t.type .. " value"}, 2) end
        assert(type(t.val) == "table", "corrupted table", 2)
        assert(type(name) == "table", "typeof name ~= table", 2)
        if t.val[name.type] == nil then t.val[name.type] = {} end
        assert(type(t.val[name.type]) == "table", "corrupted table", 2)
        if value.type == "nil" then
            t.val[name.type][name.val] = nil
            if next(t.val[name.type]) == nil then
                t.val[name.type] = nil
            end
        else
            t.val[name.type][name.val] = value
        end
    end
    local function getInTable(t, name, prev)
        prev = prev or {}
        if prev[t] then error({"lua", "loop in gettable"}) end
        prev[t] = true

        if type(name) == "string" or type(name)=="number" then name = {type=type(name), val=name} end

        assert(type(t) == "table", "typeof t ~= table")
        assert(type(name) == "table", "typeof name ~= table")
        assert(name.type, "corrupt table", 2)

        -- try the table first
        local rgr = t.type == "table" and interp_rawget(t, name)
        if rgr and rgr.type ~= "nil" then return rgr end

        -- then try __index
        local index = t.metatable and interp_rawget(t.metatable, {type="string",val="__index"})
        if index and index.type ~= "nil" then
            if index.type == "function" then
                return expr({"call", {"quote", index}, {{"quote", t}, {"quote", name}}})[1]
            else
                return getInTable(index, name, prev)
            end
        end

        -- then return nil
        return {type="nil"}
    end
    local function setInTable(t, name, value, prev)
        prev = prev or {}
        if prev[t] then error({"lua", "loop in settable"}) end
        prev[t] = true

        assert(type(t) == "table", "typeof t ~= table", 2)
        assert(type(name) == "table", "typeof name ~= table", 2)

        if name == nil or name.type == "nil" then error({"lua", "expected table index; got nil"}) end

        -- first, if the key already exists in the table, set it and return
        if t.type == "table" and interp_rawget(t, name).type ~= "nil" then
            return interp_rawset(t, name, value)
        end

        -- then try __newindex
        local newindex = t.metatable and interp_rawget(t.metatable, {type="string",val="__newindex"})
        if newindex and newindex.type ~= "nil" then
            if newindex.type == "function" then
                return expr({"call", {"quote", newindex}, {{"quote", t}, {"quote", name}, {"quote", value}}})[1]
            else
                return setInTable(newindex, name, value, prev)
            end
        end

        -- then create a new key if it's a table
        if t.type == "table" then
            return interp_rawset(t, name, value)
        end

        -- then fail
        error({"lua", "cannot index "..t.type})
    end
    local function getValue(name)
        if type(name) == "string" then
            local v = scope.vars[name]
            if v ~= nil then
                return v.val
            else
                return getInTable(scope.env, {type="string",val=name})
            end
        elseif type(name) == "table" then
            if name[1] == "." then
                if #name == 2 then
                    return setValue(name[2], value)
                end
                local t = getValue(name[2])
                for k=3,#name do
                    t = getInTable(t, {type="string",val=name[2]})
                end
                return t
            elseif name[1] == "var" then
                return getValue(name[2])
            else
                error({"interp", "invalid name operation "..name[1]})
            end
        else
            error({"interp", "invalid name type "..type(name)})
        end
    end
    local function setValue(name, value)
        if value == nil then value = {type="nil"} end
        if value.type == nil then error({"interp", "corrupt table"}, 2) end
        if type(name) == "string" then
            local v = scope.vars[name]
            if v ~= nil then
                v.val = value
            else
                setInTable(scope.env, {type="string",val=name}, value)
            end
        elseif type(name) == "table" then
            if name[1] == "." then
                if #name == 2 then
                    return setValue(name[2], value)
                end
                local t = getValue(name[2])
                for k=3,#name-1 do
                    t = getInTable(t, {type="string",val=name[k]})
                end

                setInTable(t, {type="string",val=name[#name]}, value)
            elseif name[1] == "[]" then
                local tbl = expr(name[2])[1]
                local key = expr(name[3])[1]
                setInTable(tbl, key, value)
            elseif name[1] == "var" then
                setValue(name[2], value)
            else
                error({"interp", "invalid name operation " .. name[1]})
            end
        else
            error({"interp", "invalid name type " .. type(name)})
        end
    end
    local function isTrue(val)
        if val.type == "nil" or (val.type == "boolean" and val.val == false) then
            return false
        else
            return true
        end
    end
    local function getcomphandler(a, b, event)
        if a.type ~= b.type then return nil end
        if a.metatable == nil or b.metatable == nil then return nil end
        local af = interp_rawget(a.metatable, {type="string",val=event})
        local bf = interp_rawget(b.metatable, {type="string",val=event})
        if af == nil or bf == nil or af.type ~= bf.type then return nil end
        if af.val == bf.val then
            return af
        else
            return nil
        end
    end
    local function explist(l)
        local r = {}
        if l == nil then error({"interp","table expected, got nil"},2) end
        for k,v in ipairs(l) do
            local sh = #scopeStack
            for k2,v2 in ipairs(expr(v)) do
                table.insert(r, v2)
            end
            if sh ~= #scopeStack then error({"interp", "scope stack imbalance in expression list, type: "..v[1]}) end
        end
        return r
    end

    local function getmetamethod(obj, name)
        if obj.metatable == nil then return nil end
        return obj.metatable.val.string and obj.metatable.val.string[name]
    end

    local function getbinhandler(a, b, name)
        return getmetamethod(a, name) or getmetamethod(b, name)
    end

    local function callmetamethod(obj, name, args, default)
        local mm = getmetamethod(obj, name)
        if mm == nil then return default end
        return callfunc(mm, args)
    end

    -- initialize DEFAULT_GLOBAL_ENV
    do
        local env = {}

        -- helper function
        -- if o.type ~= t, throw an error, then return t.val
        -- if o == nil and allowNil, return nil
        local function checkType(o, t, allowNil)
            if t == nil then error({"interp", "expected string, got nil"}) end
            if o == nil or o.type == "nil" and allowNil then return nil end
            if o == nil then error({"lua", "expected "..t..", got nil"}, 2) end
            if o.type == nil then error({"interp", "corrupt table"},3) end
            if o.type ~= t then error({"lua", "expected "..t..", got "..o.type}, 2) end
            return o.val
        end

        local function wrapObj(o)
            if type(o) == "number" or type(o) == "string" or type(o) == "boolean" or type(o) == "nil" then
                return {type=type(o),val=o}
            else
                error({"lua", "invalid type "..type(o).." - expected number, string, boolean or nil"})
            end
        end
        local function unwrapObj(o)
            if o.type == "number" or o.type == "string" or o.type == "boolean" or o.type == "nil" then
                return o.val
            else
                error({"interp", "invalid type "..o.type.." - expected number, string, boolean or nil"})
            end
        end


        -- wraps a native function into a virtualized function
        -- can only handle types: number, string, boolean, nil
        -- eg: wrapFunc(math.pow)({type="number",val=2},{type="number",val=5}) -> {type="number",val=32}
        local function wrapFunc(fn)
            return function(...)
                local args = {...}
                for k,v in ipairs(args) do
                    args[k] = unwrapObj(v)
                end
                local ret = {fn(unpack(args))}
                for k,v in pairs(ret) do
                    ret[k] = wrapObj(v)
                end
                if #ret == 0 then ret[1] = {type="nil"} end
                return unpack(ret)
            end
        end

        -- like wrapFunc, for functions that return either nil or a list of wrappable types
        local function wrapListReturningFunc(fn)
            return function(...)
                local args = {...}
                for k,v in pairs(args) do
                    args[k] = unwrapObj(v)
                end
                local ok, ret = pcall(fn, unpack(args))
                if not ok then error({"lua", ret}) end
                if ret == nil then return {type="nil"} end
                local r = {type="table",val={number={}}}
                for k,v in ipairs(ret) do
                    r.val.number[k] = wrapObj(v)
                end
                return r
            end
        end

        env.math = {
            huge = {type="number",val=math.huge},
            pi = {type="number",val=math.pi},
        }

        for k,v in ipairs({"abs", "acos", "asin", "atan", "atan2", "ceil", "cos", "cosh", "deg", "exp", "floor", "fmod", "frexp", "ldexp", "log", "log10", "max", "min", "modf", "pow", "rad", "random", "randomseed", "sin", "sinh", "sqrt", "tanh", "tan"}) do
            env.math[v] = wrapFunc(math[v])
        end

        env.string = {
            byte = wrapFunc(string.byte),
            char = wrapFunc(string.char),
            find = wrapFunc(string.find),
            format = wrapFunc(string.format),
            len = wrapFunc(string.len),
            lower = wrapFunc(string.lower),
            match = wrapFunc(string.match),
            rep = wrapFunc(string.rep),
            reverse = wrapFunc(string.reverse),
            sub = wrapFunc(string.sub),
            upper = wrapFunc(string.upper),

            gmatch = function(str, ptn)
                str = checkType(str, "string")
                ptn = checkType(ptn, "string")
                local f, s, v = string.gmatch(str, ptn)
                return {type="function", val=function()
                    v = f(s, v)
                    return wrapObj(v)
                end}
            end,

            -- todo: gsub
        }

        local event_table_map = {}
        setmetatable(event_table_map, {__mode="k"})

        local function native_pullEventRaw(filter)
            filter = checkType(filter, "string", true)
            local valid, t
            repeat
                valid = true
                t = pullQueuedEvent()
                for k,v in ipairs(t) do
                    if type(v) == "table" then
                        if event_table_map[v] then
                            t[k] = event_table_map[v]
                        else
                            -- ignore this event
                            valid = false
                        end
                    else
                        t[k] = wrapObj(v)
                    end
                end
            until valid
            if #t == 0 then return {type="nil"} end
            return unpack(t)
        end

        env.os = {
            queueEvent = wrapFunc(os.queueEvent),
            pullEventRaw = native_pullEventRaw,
            getComputerLabel = wrapFunc(os.getComputerLabel),
            shutdown = wrapFunc(os.shutdown),
            setAlarm = function(time)
                local t = os.setAlarm(checkType(time, "number"))
                event_table_map[t] = {type="table", val={}}
                return event_table_map[t]
            end,
            clock = wrapFunc(os.clock),
            reboot = wrapFunc(os.reboot),
            setComputerLabel = wrapFunc(os.setComputerLabel),
            time = wrapFunc(os.time),
            startTimer = function(delay)
                local t = os.startTimer(checkType(delay, "number"))
                event_table_map[t] = {type="table", val={}}
                return event_table_map[t]
            end
        }

        env.fs = {
            list = wrapListReturningFunc(fs.list),
            isDir = wrapFunc(fs.isDir),
            exists = wrapFunc(fs.exists),
            isReadOnly = wrapFunc(fs.isReadOnly),
            getName = wrapFunc(fs.getName),
            getSize = wrapFunc(fs.getSize),
            getDrive = wrapFunc(fs.getDrive),
            makeDir = wrapFunc(fs.makeDir),
            move = wrapFunc(fs.move),
            copy = wrapFunc(fs.copy),
            delete = wrapFunc(fs.delete),
            combine = wrapFunc(fs.combine),
            open = function(path, mode)
                path = checkType(path, "string")
                mode = checkType(mode, "string")
                local native = fs.open(path, mode)
                if native == nil then return {type="nil"} end

                local rt = {type="table",val={}}
                for k,v in pairs(native) do
                    if type(k) == "string" and type(v) == "function" then
                        setInTable(rt, wrapObj(k), {type="function",val=wrapFunc(v)})
                    end
                end
                return rt
            end
        }

        --[[env.coroutine = {
            yield = function(...)
                local oss = scopeStack
                local rv = {coroutine.yield(...)}
                scopeStack = oss
                if #rv == 0 then return {type="nil"} end
                return unpack(rv)
            end,
            create = function(fn)
                local cr_scopeStack = {scope}
                local cr = coroutine.create(function(...)
                    scopeStack = cr_scopeStack
                    local rv = {pcall(callfunc, fn, ...)}
                    if table.remove(rv, 1) then
                        -- no error
                        return unpack(rv)
                    end
                    -- error
                    local err = rv[1]
                    if type(err) ~= "table" or err[1] ~= "lua" then
                        if type(err) == "table" then
                            print("Internal error in coroutine: "..err.location..err[2])
                        else
                            print("Internal error in coroutine: "..tostring(err))
                        end
                        error(err, 0)
                    end
                    print("Lua coroutine error: "..err.location..err[2])
                    error(err, 0)
                end)
                return {type="thread", val={cr=cr, scopeStack=cr_scopeStack}}
            end,
            resume = function(c, ...)
                local oss = scopeStack
                local rv = {coroutine.resume(checkType(c, "thread").cr, ...)}
                scopeStack = oss
                rv[1] = wrapObj(rv[1])
                return unpack(rv)
            end,
            status = function(c)
                return wrapObj(coroutine.status(checkType(c, "thread").cr))
            end,
        }]]

        env.peripheral = {
            isPresent = wrapFunc(peripheral.isPresent),
            getType = wrapFunc(peripheral.getType),
            getMethods = wrapListReturningFunc(peripheral.getMethods),
            call = wrapFunc(peripheral.call)
        }

        env.term = {
            setCursorBlink = wrapFunc(term.setCursorBlink),
            getSize = wrapFunc(term.getSize),
            getCursorPos = wrapFunc(term.getCursorPos),
            setCursorPos = wrapFunc(term.setCursorPos),
            write = wrapFunc(term.write),
            clear = wrapFunc(term.clear),
            clearLine = wrapFunc(term.clearLine),
            scroll = wrapFunc(term.scroll)
        }

        env.table = {}

        function env.loadstring(str, prefix)
            str = checkType(str, "string")
            prefix = checkType(prefix, "string", true) or "[string]"
            local ok, tokens, ast = pcall(tokenize, str, prefix)
            if not ok then error({"lua", tokens}, 2) end
            ok, ast = pcall(parse, tokens)
            if not ok then error({"lua", ast}, 2) end

            return funcdef({{"..."},ast})
        end

        function env.error(message, level)
            message = checkType(message, "string")
            level = checkType(level, "number", true) or 1
            if level == 0 then
                error({"lua", message}, 0)
            else
                local sc = getStackLevel(level)
                error({"lua", sc.context.prefix..":"..sc.context.line..": "..message}, 0)
            end
        end

        function env.rawequal(a, b)
            if a == nil or b == nil then return a == b end
            return a.type == b.type and a.val == b.val
        end

        function env.rawget(tbl, key)
            return interp_rawget(tbl or {type="nil"}, key or {type="nil"})
        end

        function env.rawset(tbl, key, value)
            interp_rawset(tbl or {type="nil"}, key or {type="nil"}, value or {type="nil"})
            return {type="nil"}
        end

        function env.select(...)
            local args = {...}
            local n = args[1]
            if n == nil then error{"lua", "expected at least one argument"} end
            if n.type == "string" and n.val == "#" then
                return {type="number", val=(#args-1)}
            end
            n = checkType(n, "number")
            return args[n+1] or {type="nil"}
        end

        function env.setfenv(fn, tbl)
            if fn == nil then fn = {type="nil"} end
            checkType(tbl, "table")
            if fn.type == "number" then
                local scope = getStackLevel(fn.val)
                scope.fn.val.scope.env = tbl
            else
                checkType(fn, "function")
                fn.val.scope.env = tbl
            end
            return fn
        end

        function env.getfenv(fn)
            if fn == nil then fn = {type="nil"} end
            if fn.type == "number" then
                local scope = getStackLevel(fn.val)
                return scope.fn.scope.env
            elseif fn.type == "nil" then
                return scope.env
            else
                checkType(fn, "function")
                return fn.val.scope.env
            end
        end

        function env.setmetatable(tbl, meta)
            tbl = tbl or {type="nil"}
            if tbl.type ~= "table" then
                error{"lua", "cannot set metatable of "..tbl.type.." value"}
            end
            if meta and meta.type == "nil" then meta = nil end
            tbl.metatable = meta
            return {type="nil"}
        end

        function env.getmetatable(tbl)
            return tbl.metatable or {type="nil"}
        end

        function env.unpack(tbl, start)
            checkType(tbl, "table")
            start = checkType(start, "number", true)
            if #tbl.val.number < (start or 1) then return {type="nil"} end
            return unpack(tbl.val.number, start or 1)
        end

        function env.xpcall(...)
            error("todo xpcall")
        end

        function env.pcall(fn, ...)
            local rv = {pcall(callfunc, fn, {...})}
            local ok = rv[1]
            if ok then
                rv[1] = wrapObj(rv[1])
                return unpack(rv)
            else
                if type(rv[2]) ~= "table" then
                    error(rv[2], 0)
                elseif rv[2][1] == "lua" then
                    return {type="boolean", val=false}, {type="string", val=(rv[2].lualoc or "")..rv[2][2]}
                else
                    error(rv[2], 0)
                end
            end
        end

        env.redstone = {}
        for _,k in ipairs({"setBundledOutput","getBundledInput","testBundledInput","getInput","getBundledOutput","getOutput","setOutput"}) do
            env.redstone[k] = wrapFunc(redstone[k])
        end

--[[
rednet = TODO ??????
coroutine = TODO NATIVE
 status = status
 resume = resume
 create = create
 yield = yield
 wrap = wrap
 running = running
string
 gsub = TODO NATIVE
]]

        function env.tonumber(a)
            if a == nil or a.type ~= "string" then return wrapObj(nil) end
            return wrapObj(tonumber(a.val))
        end

        function env.tostring(a)
            if a == nil or a.type == "nil" then return wrapObj("nil") end
            local rv = callmetamethod(a, "__tostring", {a}, wrapObj(tostring(a.val)))
            return rv
        end

        function env.read(ch)
            return wrapObj(read(unwrapObj(ch)))
        end

        function env.print(...)
            local s = ""
            for k,v in ipairs({...}) do
                s = s..tostring(v.val)
            end
            log(s)
            return wrapObj(print(s))
        end

        function env.table.insert(tbl, pos, val)
            if tbl == nil then error({"lua", "expected table, got nil"}) end
            if tbl.type ~= "table" then error({"lua", "expected table, got "..tbl.type}) end
            if val ~= nil then
                if pos.type ~= "number" then
                    error({"lua", "expected number, got "..pos.type})
                end
                pos = unwrapObj(pos)
            else
                val, pos = pos, nil
            end
            tbl.val.number = tbl.val.number or {}
            table.insert(tbl.val.number, val)
            return {type="nil"}
        end

        function env.table.remove(tbl, pos)
            pos = checkType(pos, "number", true)
            checkType(tbl, "table")
            table.remove(tbl.val.number, pos)
            return {type="nil"}
        end

        function env.next(tbl, key)
            if tbl == nil then tbl = {type="nil"} end
            if key == nil then key = {type="nil"} end
            if tbl.type == nil then error({"interp", "corrupt table"}, 2) end
            if tbl.type ~= "table" then error({"lua", "table expected, got "..tbl.type}) end
            if key.type == "nil" then
                for k,v in pairs(tbl.val) do
                    for k2,v2 in pairs(v) do
                        return {type=k,val=k2}, v2
                    end
                end
                return {type="nil"}
            end
            if tbl.val[key.type] == nil then error({"lua", "invalid key to next"}) end

            -- try next key of the same type
            local r = next(tbl.val[key.type], key.val)
            if r ~= nil then
                return {type=key.type,val=r}, tbl.val[key.type][r]
            end

            -- try next type
            local nt = next(tbl.val, key.type)
            if nt == nil then return {type="nil"},{type="nil"} end

            -- get first key of next type, or nil if none left
            local r = next(tbl.val[nt])
            if r == nil then return {type="nil"},{type="nil"} end
            return {type=nt, val=r}
        end

        function env.type(o)
            return {type="string", val=(o and o.type or "nil")}
        end

        -- converts a native object into a virtualized object
        -- does not wrap functions
        -- eg: wrap({"test", hi=5}) -> {type="table", val={string={hi={type="number",val=5}}, number={1={type="string",val="test"}}}}
        local function wrap(o, n)
            if type(o) == "table" then
                local t = {type="table", val={}}
                for k,v in pairs(o) do
                    interp_rawset(t, wrap(k), wrap(v, n.."."..k))
                end
                return t
            else
                return {type=type(o), val=o, name=n}
            end
        end

        local new = wrap(env, "_G")
        for k,v in pairs(new) do
            DEFAULT_GLOBAL_ENV[k] = v
        end
        interp_rawset(DEFAULT_GLOBAL_ENV, {type="string", val="_G"}, DEFAULT_GLOBAL_ENV)
    end

    local function logicalNot(e)
        return {type="boolean", val=not isTrue(e)}
    end

    -- example: makeArithFunction(function(a,b) return a+b end, "__add")
    local function makeArithFunction(direct, meta)
        return function(t)
            local a = expr(t[2])[1]
            local b = expr(t[3])[1]
            if (a.type == "string" or a.type == "number") and (b.type == "string" or b.type == "number") then
                return {type="number", val=direct(a.val,b.val)}
            end
            local mm = getbinhandler(a, b, meta)
            return mm and callfunc(mm, {a, b}) or error({"lua", "attempt to "..meta.." "..a.type.." with "..b.type})
        end
    end

    expr = {
        tcon = function(t)
            local r = {number={}}
            local rv = {type="table", val=r}
            local auto = 1
            for k,v in ipairs(t[2]) do
                if v[1] == "auto" then
                    for k2,v2 in ipairs(expr(v[2])) do
                        if v2 ~= nil and v2.type ~= "nil" then
                            r.number[auto] = v2
                            auto = auto + 1
                        end
                    end
                else
                    -- name=value or [expr]=value
                    local k2 = expr(v[1])[1]
                    r[k2.type] = r[k2.type] or {}
                    r[k2.type][k2.val] = expr(v[2])[1]
                end
            end
            return rv
        end,
        con = function(t)
            --print(tostring(t[2]))
            return {type=type(t[2]), val=t[2]}
        end,
        quote = function(t) -- never generated by the parser
            return t[2]
        end,
        ["[]"] = function(t)
            local t2 = expr(t[2])[1]
            local i = expr(t[3])[1]
            local rv = getInTable(t2, i)
            return rv
        end,
        ["."] = function(t)
            local t2 = expr(t[2])[1]
            local rv = getInTable(t2, {type="string",val=t[3]})
            return rv
        end,
        var = function(t)
            --print("var "..t[2])
            return getValue(t[2]) or {type="nil"}
        end,
        call = function(t)
            local fn = expr(t[2])[1]
            local args = explist(t[3])
            local rv = {callfunc(fn, args)}
            return unpack(rv)
        end,
        ["=="] = function(t)
            local a = expr(t[2])[1]
            local b = expr(t[3])[1]
            local rv = true
            if a == b then
                rv=true
            elseif a.type ~= b.type then
                rv=false
            elseif a.val == b.val then
                rv=true
            else
                local ch = getcomphandler(a, b, "__eq")
                if ch == nil then
                    rv = false
                else
                    return callfunc(ch, {a, b})
                end
            end
            return {type="boolean",val=rv}
        end,
        ["<="] = function(t)
            local a = expr(t[2])[1]
            local b = expr(t[3])[1]
            if a.type == "number" and b.type == "number" then
                return {type="boolean", val=(a.val <= b.val)}
            elseif a.type == "string" and b.type == "string" then
                return {type="boolean", val=(a.val <= b.val)}
            else
                local f = getcomphandler(a, b, "__le")
                if f ~= nil then
                    return callfunc(f, {a, b})
                else
                    f = getcomphandler(a, b, "__lt")
                    if f ~= nil then
                        return logicalNot(callfunc(f, {b, a}))
                    else
                        error({"lua", "attempt to compare "..a.type.." and "..b.type})
                    end
                end
            end
        end,
        ["<"] = function(t)
            return logicalNot(expr({"<=", t[3], t[2]})[1])
        end,
        [">="] = function(t)
            return expr({"<=", t[3], t[2]})[1]
        end,
        [">"] = function(t)
            return expr({"<", t[3], t[2]})[1]
        end,
        ["~="] = function(t)
            return expr({"not", {"==", t[2], t[3]}})[1]
        end,
        ["not"] = function(t)
            local a = expr(t[2])[1]
            return {type="boolean", val=not isTrue(a)}
        end,
        ["and"] = function(t)
            local a = expr(t[2])[1]
            if not isTrue(a) then
                return a
            else
                local b = expr(t[3])[1]
                return b
            end
        end,
        ["or"] = function(t)
            local a = expr(t[2])[1]
            if isTrue(a) then
                return a
            else
                local b = expr(t[3])[1]
                return b
            end
        end,
        [".."] = function(t)
            local a = expr(t[2])[1]
            local b = expr(t[3])[1]
            if (a.type == "string" or a.type == "number") and (b.type == "string" or b.type == "number") then
                return {type="string", val=tostring(a.val)..tostring(b.val)}
            end
            local mm = getbinhandler(a, b, "__concat")
            return mm and callfunc(mm, {a, b}) or error({"lua", "attempt to concatenate "..a.type.." with "..b.type})
        end,
        ["+"] = makeArithFunction(function(a,b) return a+b end, "__add"),
        ["-"] = makeArithFunction(function(a,b) return a-b end, "__sub"),
        ["*"] = makeArithFunction(function(a,b) return a*b end, "__mul"),
        ["^"] = makeArithFunction(function(a,b) return a^b end, "__pow"),
        ["/"] = makeArithFunction(function(a,b) return a/b end, "__div"),
        ["%"] = makeArithFunction(function(a,b) return a%b end, "__mod"),
        negate = function(t)
            local a = expr(t[2])[1]
            if a.type == "number" then
                return {type="number",val=-a.val}
            end
            local mm = getmetamethod(a, "__unm")
            if mm == nil then
                error({"lua", "attempt to negate "..a.type})
            else
                return callfunc(mm, {a})
            end
        end,
        ["#"] = function(t)
            local e = expr(t[2])[1]
            if e.type == "string" then
                return {type="number", val=#e.val}
            elseif e.type == "table" then
                local default = (e.val.number and #e.val.number or 0)
                return callmetamethod(e, "__len", {e}, {type="number",val=default})
            else
                error({"lua", "attempt to get length of "..e.type})
            end
        end,
        ["()"] = function(t)
            return expr(t[2])[1]
        end,
        func = function(t)
            return funcdef(t[2])
        end,
        ["..."] = function()
            if #scope.dotdotdot == 0 then return {type="nil"} end
            return unpack(scope.dotdotdot)
        end
    }
    setmetatable(expr, {__call = function(t, a)
        scope.context = a.context or scope.context
        local et = a[1]
        assert(type(et) == "string", "expected string, got "..type(et), 2)
        --print(et)
        local f = t[et]
        if f == nil then error("unimplemented expression type: " .. et) end
        --log("begin "..et)
        local rv = {f(a)}
        --log("end "..et)
        yield()
        assert(#rv > 0, "Expression type " .. et .. " returned no values")
        for k,v in ipairs(rv) do
            assert(type(v) == "table", "Expression type " .. et .. " returned " .. type(v) .. " value")
        end
        return rv
    end})
    function funcdef(t)
        pushScope()
        local f = {}
        f.argnames = t[1]
        f.body = t[2]
        f.scope = scope
        local fval = {type="function",val=f}
        f.scope.func = fval
        popScope()
        return fval
    end

    -- holds the return value when throwing a "return" error
    local retval

    -- calls block(code), catching "break" errors and returning normally
    -- return value: true if loop was broken, otherwise false
    local function catchBreak(code)
        local sh = #scopeStack
        local ok, status = pcall(block, code)
        if ok then
            if #scopeStack ~= sh then error({"interp", "Scope stack imbalance after loop!"}) end
            return false
        end
        while #scopeStack > sh do popScope() end
        if status == "break" then return true end
        error(status, 0)
    end

    stmt = {
        ["local"] = function(t)
            local names = t[2]
            if names[1] == "BIOS_CODE" then print(textutils.serialize(t[3])) end
            local vals = explist(t[3] or {})
            for k=1,#names do
                addLocal(names[k], vals[k] or {type="nil"})
            end
        end,
        lfunc = function(t)
            --log("LFUNC "..t[2])
            addLocal(t[2], funcdef(t[3]))
        end,
        funcst = function(t)
            setValue(t[2], funcdef(t[3]))
        end,
        call = function(t)
            expr(t)
        end,
        ["return"] = function(t)
            retval = explist(t[2])
            if #retval == 0 then retval = {{type="nil"}} end
            error("return", -1)
        end,
        ["="] = function(t)
            local names = t[2]
            local values = explist(t[3])
            scope.context = t.context or scope.context
            for k=1,#names do
                --log("assign "..tostring(names[k]))
                setValue(names[k], values[k] or {type="nil"})
            end
        end,
        ["if"] = function(t)
            -- "if" {cond block} [block]
            --log("tryExit is "..getValue("tryExit").type)
            for k = 2, #t-1, 2 do
                --print(k)
                local test = expr(t[k])[1]
                --print(test.type, " ", tostring(test.val))
                if isTrue(test) then
                    block(t[k+1])
                    return
                end
            end
            if ((#t)%2) == 0 then
                block(t[#t])
            end
            --print(getValue("tryExit").type)

        end,

        -- generic for
        gfor = function(t)
            local el = explist(t[3]) -- expression list
            local names = t[2] -- name list
            local f, s, var = el[1], el[2], el[3]
            f = f or {type="nil"}
            s = s or {type="nil"}
            var = var or {type="nil"}
            while true do
                local vals = {callfunc(f, {s, var})}
                var = vals[1]
                if var == nil or var.type == "nil" then break end

                -- reset scope and assign local variables
                pushScope()
                -- assign local variables
                for k=1,#names do
                    addLocal(names[k], vals[k] or {type="nil"})
                end

                if catchBreak(t[4]) then popScope() break end

                popScope()
            end
        end,

        nfor = function(t)
            local name = t[2]
            local start = expr(t[3])[1]
            local stop = expr(t[4])[1]
            local step = expr(t[5])[1]
            if start.type ~= "number" or stop.type ~= "number" or step.type ~= "number" then
                error({"lua","expected number"})
            end
            for var=start.val,stop.val,step.val do
                pushScope()
                addLocal(name, {type="number",val=var})

                if catchBreak(t[6]) then popScope() break end

                popScope()
            end
        end,

        ["while"] = function(t)
            local cond = t[2]
            local code = t[3]

            while isTrue(expr(cond)[1]) do
                pushScope()
--              print(getValue("tCommandHistory").type.." test")
                if catchBreak(code) then popScope() break end
                popScope()
            end
        end,

        ["repeat"] = function(t)
            local code = t[2]
            local cond = t[3]

            while true do
                pushScope()
                if catchBreak(code) then popScope() break end
                if not isTrue(expr(cond)[1]) then popScope() break end
                popScope()
            end
        end,

        block = function(t)
            block(t[2])
        end,

        ["break"] = function(t)
            error("break", 0)
        end,
    }
    -- allows us to call stmt(t) to run the statement in table t
    setmetatable(stmt, {__call = function(t, a)
        if type(a) ~= "table" then error({"interp", "expected table, got "..type(a)},2) end
        local st = a[1]
        scope.context = a.context or scope.context
        --log("stmt "..st)
        yield()
        if type(st) == "table" then
            log("Statement type is table, WTF???")
            for k,v in pairs(st) do log(k," ",v) end
        end
        if t[st] == nil then error("unimplemented statement type: " .. tostring(st)) end

        local sh = #scopeStack
        t[st](a)
        if sh ~= #scopeStack then error({"interp", "scope stack imbalance after stmt "..st}) end
    end})
    function block(t)
        pushScope()
        for k,v in ipairs(t) do
            stmt(v)
        end
        popScope()
    end
    function callfunc(fn, args)
        if fn.type~="function" then error({"lua","attempt to call "..fn.type}) end
        local name = fn.name
        fn = fn.val
        if type(fn)=="function" then
            -- "C" function (actually written in Lua; but a native function)
            local rv = {pcall(fn, unpack(args))}
            if not table.remove(rv, 1) then
                if type(rv[1]) == "string" then
                    error({"lua", "Native function error in "..tostring(name)..": "..tostring(rv[1])}, 2)
                else
                    error(rv[1], 0)
                end
            end
            if #rv == 0 then
                error({"interp","Native function "..tostring(name).." returned no values"})
            end
            for k,v in ipairs(rv) do
                if type(v) ~= "table" then
                    error({"interp","Native function "..tostring(name).." returned "..type(v).." value"})
                end
            end
            return unpack(rv)
        end
        pushScope(fn.scope)
        if fn.scope.env.string and fn.scope.env.string.shell then
            print(getInTable(fn.scope.env,"shell").type)
        end
        pushScope()
        scope.allArgs = {}
        for k,v in pairs(args) do
            scope.allArgs[k]=v
        end
        assert(type(fn.argnames)=="table", "corrupt function",2)
        for k,v in ipairs(fn.argnames) do
            if v == "..." then
                scope.dotdotdot = {}
                for n=k,#args do
                    scope.dotdotdot[n-k+1] = args[n]
                end
            else
                addLocal(v, args[k] or {type="nil"})
            end
        end

        -- run code, catching returns and breaks
        local nScopes = #scopeStack
        local ok, status = pcall(block, fn.body)
        if not ok then
            while #scopeStack > nScopes do
                popScope()
            end
        end
        if #scopeStack ~= nScopes then
            error({"interp", "Scope stack imbalance after function call!"})
        end
        popScope()
        popScope()
        if not ok then
            if status == "return" then
                return unpack(retval)
            elseif status == "break" then
                error({"lua", "break outside of loop"})
            else
                error(status, -1)
            end
        end

        return {type="nil"}
    end
    for _,ast in ipairs(ast_list) do
        local ok, err = pcall(block, ast)
        if not ok then
            if err == "break" then
                err = {"lua", "break outside of loop"}
            end
            if err == "return" then
            elseif type(err) == "string" then
                if logfile then logfile.close() end
                print(context)
                oldError(err, 0)
            elseif type(err) == "table" then
                if err[1] == "lua" then
                    print("Lua error: "..err)
                else
                    print(context)
                    print(err.location.."Internal error: " .. table.concat(err, ": "))
                end
                break
            elseif err == nil then -- terminated
                print("Terminating LiL interpreter")
            else
                print("Caught a "..type(err).." error???")
                break
            end
        end
    end
    if logfile then logfile.close() end
end

local function serializeInt(i)
    local s = ""
    repeat
        s = s .. string.char((i % 128) + ((i >= 128) and 128 or 0))
        i = math.floor(i / 128)
    until i == 0
    return s
end
-- returns int, next position
local function deserializeInt(s,pos)
    local k = pos
    local i = 0
    local m = 1
    while true do
        local b = string.byte(s:sub(k,k))
        i = i + m * (b % 128)
        m = m * 128
        k = k + 1
        if b < 128 then break end
    end
    return i, k
end

local nextid_key = {}
local function serializeInternal(obj, seen)
    if obj ~= nil and seen[obj] then
        return "\06" .. serializeInt(seen[obj])
    end
    if type(obj) == "table" then
        local id = seen[nextid_key]
        seen[nextid_key] = id + 1
        seen[obj] = id

        local s = "\05"
        local ikeys = {}
        for k,v in ipairs(obj) do
            ikeys[k] = v
            s = s .. serializeInternal(v, seen)
        end
        s = s .. serializeInternal(nil, seen)
        for k,v in pairs(obj) do
            if ikeys[k] == nil then
                s = s .. serializeInternal(k, seen) .. serializeInternal(v, seen)
            end
        end
        s = s .. serializeInternal(nil, seen)
        return s
    elseif type(obj) == "number" then
        local ns = tostring(obj)
        return "\04" .. serializeInt(ns:len()) .. ns
    elseif type(obj) == "string" then
        return "\03" .. serializeInt(obj:len()) .. obj
    elseif type(obj) == "boolean" then
        if obj then
            return "\01"
        else
            return "\x02"
        end
    elseif type(obj) == "nil" then
        return "\00"
    elseif type(obj) == "userdata" then
        error("cannot serialize userdata")
    elseif type(obj) == "thread" then
        error("cannot serialize threads")
    elseif type(obj) == "function" then
        error("cannot serialize functions")
    else
        error("unknown type: " .. type(obj))
    end
end
function serialize(obj)
    return serializeInternal(obj, {[nextid_key] = 0})
end
function deserialize(s)
    local pos = 1
    local seen = {}
    local nextid = 0
    local function internal()
        local tch = s:sub(pos,pos)
        local len
        pos = pos + 1
        if tch == "\00" then
            return nil
        elseif tch == "\01" then
            return true
        elseif tch == "\02" then
            return false
        elseif tch == "\03" then
            len, pos = deserializeInt(s, pos)
            local rv = s:sub(pos, pos+len-1)
            pos = pos + len
            return rv
        elseif tch == "\04" then
            len, pos = deserializeInt(s, pos)
            local rv = s:sub(pos, pos+len-1)
            pos = pos + len
            return tonumber(rv)
        elseif tch == "\05" then
            local id = nextid
            nextid = id + 1
            local t = {}
            seen[id] = t

            local k = 1
            while true do
                local v = internal()
                if v == nil then break end
                t[k] = v
                k = k + 1
            end

            while true do
                local k = internal()
                if k == nil then break end
                local v = internal()
                if v == nil then break end
                t[k] = v
            end
            return t
        elseif tch == "\06" then
            local id
            id, pos = deserializeInt(s, pos)
            return seen[id]
        else
            return nil
        end
    end
    return internal()
end


local function parseFile(filename)
    local file = fs.open(filename, "r")
    local code = file.readAll()
    file.close()
    return parse(tokenize(code))
end

local function cachedAST(file, cacheFile)
    if fs.exists(cacheFile) then
        local f = fs.open(cacheFile, "r")
        local s = f.readAll()
        f.close()
        return deserialize(s)
    end
    local ast = parseFile(file)
    local f = fs.open(cacheFile, "w")
    f.write(serialize(ast))
    f.close()
    return ast
end

local function dumpAST(code, dumpFile)
    local ast = parse(tokenize(code))
    local f = fs.open(dumpFile, "w")
    f.write(serialize(ast))
    f.close()
    return ast
end

local BIOS_CODE = [[
------ Standard CC Lua functions ------
function loadfile(fn)
    local f = fs.open(fn, "r")
    if f == nil then return nil, "Failed to open file" end
    local code = f.readAll()
    f.close()

    return loadstring(code, fn)
end

function __inext(tbl, key)
    key = key + 1
    if tbl[key] ~= nil then
        return key, tbl[key]
    else
        return nil, nil
    end
end

function ipairs(tbl)
    return __inext, tbl, 0
end

function pairs(tbl)
    return next, tbl, nil
end

function assert(expr, message)
    if not expr then
        error(message, 2)
    else
        return expr
    end
end

_VERSION = "LiL ]]..LIL_VERSION..[["

function table.foreachi(tbl, fn)
    for k,v in ipairs(tbl) do
        -- LuaJ truncates this to one result, so emulate that
        local rv = fn(k, v)
        if rv ~= nil then
            return rv
        end
    end
end

function table.foreach(tbl, fn)
    for k,v in pairs(tbl) do
        -- LuaJ truncates this to one result, so emulate that
        local rv = fn(k, v)
        if rv ~= nil then
            return rv
        end
    end
end

function table.concat(tbl, sep)
    local s = ""
    for k,v in ipairs(tbl) do
        if k > 1 then s = s .. sep end
        s = s .. v
    end
    return s
end

function table.maxn(tbl)
    local k = 1
    while tbl[k] ~= nil do
        k = k + 1
    end
    return k - 1
end

function table.getn(tbl)
    return tbl.n or table.maxn(tbl)
end

-- I'm sure all these table constructors are horrible for performance.
-- Especially inside LiL.
-- Oh well. (TODO: Make table.sort a native function)
local function mergesort(tbl, start, _end, comp)
    if start == _end then return {tbl[start]} end
    if start == _end - 1 then
        if not comp(tbl[start], tbl[_end]) then
            return {tbl[_end], tbl[start]}
        else
            return {tbl[start], tbl[_end]}
        end
    end
    local midp = math.floor((_end + start)/2)
    local left = mergesort(tbl, start, midp, comp)
    local right = mergesort(tbl, midp + 1, _end, comp)

    -- merge left and right
    local result = {}
    while #left > 0 and #right > 0 do
        if not comp(left[1], right[1]) then
            table.insert(result, table.remove(right, 1))
        else
            table.insert(result, table.remove(left, 1))
        end
    end
    for k,v in ipairs(left) do table.insert(result, v) end
    for k,v in ipairs(right) do table.insert(result, v) end
    return result
end

function table.sort(tbl, comp)
    comp = comp or function(a, b)
        if a == nil then return false end
        if b == nil then return true end
        return a < b
    end
    local result = mergesort(tbl, 1, #tbl, comp)
    for k,v in ipairs(result) do
        tbl[k] = result[k]
    end
end


------ IO library ------
io = {}
function io.write(str)
    write(str)
end
function io.read(fmt)
    if fmt ~= nil and fmt ~= "*l" then error("Unsupported format") end
    return read()
end
function io.open(fn, mode)
    local f = fs.open(fn, mode)
    if f == nil then return nil end

    local rv = {
        close = function(self)
            if self.bClosed then return end
            f.close()
            self.bClosed = true
            f = nil
        end,
        bFileHandle = true,
        bClosed = false
    }

    if mode == "r" then
        rv.read = function(self, fmt)
            if fmt == nil or fmt == "*l" then return f.readLine() end
            if fmt == "*a" then return f.readAll() end
            error("Unsupported format")
            local rv = {}
            for _,f in ipairs({...}) do
            end
            return unpack(rv)
        end
        rv.lines = function(self)
            return function()
                local line = self:read()
                if line == nil then self:close() end
                return line
            end
        end
    elseif mode == "rb" then
        rv.read = function(self)
            return f.read()
        end
    elseif mode == "w" or mode == "a" or mode == "wb" or mode == "ab" then
        rv.write = function(self, data)
            return f.write(data)
        end
    else
        f.close()
        error("Unsupported mode")
    end

    return rv
end
function io.type(f)
    if type(f) == "table" and f.bFileHandle == true then
        return f.bClosed and "closed file" or "file"
    end
    return nil
end


------ Standard CC functions ------
function redstone.getSides()
    return {"top","bottom","front","back","left","right"}
end

function os.computerID()
    return ]]..os.computerID()..[[
end
os.getComputerID = os.computerID
os.computerLabel = os.getComputerLabel

function os.version()
    if turtle then
        return "LiL ]]..LIL_VERSION..[[/TurtleOS 1.3"
    end
    return "LiL ]]..LIL_VERSION..[[/CraftOS 1.3"
end

function os.pullEvent(filter)
    -- bios.lua limits this to 5 arguments, so we do too
    local evt, a, b, c, d, e = os.pullEventRaw(filter)
    if evt == "terminate" then
        print("Terminated")
        error()
    end
    return evt, a, b, c, d, e
end

function sleep(seconds)
    local timer = os.startTimer(seconds)
    repeat
        local sEvent, param = os.pullEvent( "timer" )
    until param == timer
end

-- From bios.lua
function write( sText )
    local w,h = term.getSize()
    local x,y = term.getCursorPos()

    local nLinesPrinted = 0
    local function newLine()
        if y + 1 <= h then
            term.setCursorPos(1, y + 1)
        else
            term.scroll(1)
            term.setCursorPos(1, h)
        end
        x, y = term.getCursorPos()
        nLinesPrinted = nLinesPrinted + 1
    end

    -- Print the line with proper word wrapping
    while string.len(sText) > 0 do
        local whitespace = string.match( sText, "^[ \t]+" )
        if whitespace then
            -- Print whitespace
            term.write( whitespace )
            x,y = term.getCursorPos()
            sText = string.sub( sText, string.len(whitespace) + 1 )
        end

        local newline = string.match( sText, "^\n" )
        if newline then
            -- Print newlines
            newLine()
            sText = string.sub( sText, 2 )
        end

        local text = string.match( sText, "^[^ \t\n]+" )
        if text then
            sText = string.sub( sText, string.len(text) + 1 )
            if string.len(text) > w then
                -- Print a multiline word
                while string.len( text ) > 0 do
                    if x > w then
                        newLine()
                    end
                    term.write( text )
                    text = string.sub( text, (w-x) + 2 )
                    x,y = term.getCursorPos()
                end
            else
                -- Print a word normally
                if x + string.len(text) > w then
                    newLine()
                end
                term.write( text )
                x,y = term.getCursorPos()
            end
        end
    end

    return nLinesPrinted
end

os._LUACEPTION_LEVEL = ]]..LUACEPTION_LEVEL..[[

function print(...)
    local s = ""
    for k,v in ipairs({...}) do
        s = s .. tostring(v)
    end
    return write(s .. "\n")
end

-- From bios.lua
function read( _sReplaceChar, _tHistory )
    term.setCursorBlink( true )

    local sLine = ""
    local nHistoryPos = nil
    local nPos = 0
    if _sReplaceChar then
        _sReplaceChar = string.sub( _sReplaceChar, 1, 1 )
    end

    local w, h = term.getSize()
    local sx, sy = term.getCursorPos()
    local function redraw()
        local nScroll = 0
        if sx + nPos >= w then
            nScroll = (sx + nPos) - w
        end

        term.setCursorPos( sx, sy )
        term.write( string.rep(" ", w - sx + 1) )
        term.setCursorPos( sx, sy )
        if _sReplaceChar then
            term.write( string.rep(_sReplaceChar, string.len(sLine) - nScroll) )
        else
            term.write( string.sub( sLine, nScroll + 1 ) )
        end
        term.setCursorPos( sx + nPos - nScroll, sy )
    end

    while true do
        local sEvent, param = os.pullEvent()
        if sEvent == "char" then
            sLine = string.sub( sLine, 1, nPos ) .. param .. string.sub( sLine, nPos + 1 )
            nPos = nPos + 1
            redraw()

        elseif sEvent == "key" then
            if param == 28 then
                -- Enter
                break

            elseif param == 203 then
                -- Left
                if nPos > 0 then
                    nPos = nPos - 1
                    redraw()
                end

            elseif param == 205 then
                -- Right
                if nPos < string.len(sLine) then
                    nPos = nPos + 1
                    redraw()
                end

            elseif param == 200 or param == 208 then
                -- Up or down
                if _tHistory then
                    if param == 200 then
                        -- Up
                        if nHistoryPos == nil then
                            if #_tHistory > 0 then
                                nHistoryPos = #_tHistory
                            end
                        elseif nHistoryPos > 1 then
                            nHistoryPos = nHistoryPos - 1
                        end
                    else
                        -- Down
                        if nHistoryPos == #_tHistory then
                            nHistoryPos = nil
                        elseif nHistoryPos ~= nil then
                            nHistoryPos = nHistoryPos + 1
                        end
                    end

                    if nHistoryPos then
                        sLine = _tHistory[nHistoryPos]
                        nPos = string.len( sLine )
                    else
                        sLine = ""
                        nPos = 0
                    end
                    redraw()
                end
            elseif param == 14 then
                -- Backspace
                if nPos > 0 then
                    sLine = string.sub( sLine, 1, nPos - 1 ) .. string.sub( sLine, nPos + 1 )
                    nPos = nPos - 1
                    redraw()
                end
            end
        end
    end

    term.setCursorBlink( false )
    term.setCursorPos( w + 1, sy )
    print()

    return sLine
end

dofile = function(path)
    local func, err = loadfile(path)
    if func ~= nil then
        setfenv(f, getfenv(2))
        func() -- and bios.lua doesn't return the result? we can't either for compatibility
    else
        error(err)
    end
end

-- Install the rest of the OS api
function os.run( _tEnv, _sPath, ... )
    local tArgs = { ... }
    local fnFile, err = loadfile( _sPath )
    if fnFile then
        local tEnv = _tEnv
        setmetatable( tEnv, { __index = _G } )
        setfenv( fnFile, tEnv )
        local ok, err = pcall( function()
            fnFile( unpack( tArgs ) )
        end )
        if not ok then
            if err and err ~= "" then
                print( err )
            end
            return false
        end
        return true
    end
    if err and err ~= "" then
        print( err )
    end
    return false
end

local bProtected = true
local function protect( _t )
    local meta = getmetatable( _t )
    if meta == "Protected" then
        -- already protected
        return
    end

    setmetatable( _t, {
        __newindex = function( t, k, v )
            if bProtected then
                error( "Attempt to write to global" )
            else
                rawset( t, k, v )
            end
        end,
        __metatable = "Protected",
    } )
end

local tAPIsLoading = {}
function os.loadAPI( _sPath )
    local sName = fs.getName( _sPath )
    if tAPIsLoading[sName] == true then
        print( "API "..sName.." is already being loaded" )
        return false
    end
    tAPIsLoading[sName] = true

    local tEnv = {}
    setmetatable( tEnv, { __index = _G } )
    local fnAPI, err = loadfile( _sPath )
    if fnAPI then
        setfenv( fnAPI, tEnv )
        fnAPI()
    else
        print( err )
        return false
    end

    local tAPI = {}
    for k,v in pairs( tEnv ) do
        tAPI[k] =  v
    end
    protect( tAPI )

    bProtected = false
    _G[sName] = tAPI
    bProtected = true

    tAPIsLoading[sName] = nil
    return true
end

function os.unloadAPI( _sName )
    if _sName ~= "_G" and type(_G[_sName] == "table") then
        bProtected = false
        _G[sName] = nil
        bProtected = true
    end
end

os.sleep = sleep

-- Install the lua part of the HTTP api (if enabled)
if http then
    http.get = function( _url )
        local requestID = http.request( _url )
        while true do
            local event, param1, param2 = os.pullEvent()
            if event == "http_success" and param1 == _url then
                return param2
            elseif event == "http_failure" and param1 == _url then
                return nil
            end
        end
    end
end

-- Install the lua part of the peripheral api
peripheral.wrap = function( _sSide )
    if peripheral.isPresent( _sSide ) then
        local tMethods = peripheral.getMethods( _sSide )
        local tResult = {}
        for n,sMethod in ipairs( tMethods ) do
            tResult[sMethod] = function( ... )
                return peripheral.call( _sSide, sMethod, ... )
            end
        end
        return tResult
    end
    return nil
end

-- Protect the global table against modifications
protect( _G )
for k,v in pairs( _G ) do
    if type(v) == "table" then
        protect( v )
    end
end

-- Load APIs
local tApis = fs.list( "rom/apis" )
for n,sFile in ipairs( tApis ) do
    if string.sub( sFile, 1, 1 ) ~= "." then
        local sPath = fs.combine( "rom/apis", sFile )
        if not fs.isDir( sPath ) and (sFile ~= "parallel" or coroutine) then
            print("Loading API "..sFile)
            os.loadAPI( sPath )
        end
    end
end

-- don't allow programs to shut down or reboot the computer
os.shutdown = function() end
os.reboot = function() end

if turtle then
    local tApis = fs.list( "rom/apis/turtle" )
    for n,sFile in ipairs( tApis ) do
        if string.sub( sFile, 1, 1 ) ~= "." then
            local sPath = fs.combine( "rom/apis/turtle", sFile )
            if not fs.isDir( sPath ) then
                print("Loading API "..sFile)
                os.loadAPI( sPath )
            end
        end
    end
end
]]

local MAIN_CODE = [[
local ok, err = pcall(os.run, {}, "rom/programs/shell")
if not ok then print(err) end
]]

print(">>> LUACEPTION LEVEL "..(LUACEPTION_LEVEL))

local astList = {
    dumpAST(BIOS_CODE, "bios.ast.txt"),
    --cachedAST("lil", "lil.ast.txt"),
    parse(tokenize(MAIN_CODE)),
    --cachedAST("/rom/programs/computer/adventure", "ast.txt")
}

local status, err = pcall(interpret, astList)
if not status and type(err) == "table" then
    print(err[1], ": ", err[2])
else
    print(err)
end

print("<<< LUACEPTION LEVEL "..(LUACEPTION_LEVEL - 1))