local unique_name = require"bon".unique_name

local function do_everything(Tokens, Skeleton)
    local TokensIdx = 1
    local IdxStack = {}

    local function gettoken()
        local r = Tokens[TokensIdx]
        if r then
            TokensIdx = TokensIdx + 1
        end
        return table.unpack(r)
    end
    local function peektoken()
        local r = Tokens[TokensIdx]
        if r then
            return table.unpack(Tokens[TokensIdx])
        end
    end
    local function maybe(t)
        local a, b, c, d = peektoken()
        if a == t then return gettoken() end
        return nil
    end
    local function pushlexi()
        table.insert(IdxStack, TokensIdx)
    end
    local function poplexi()
        TokensIdx = table.remove(IdxStack)
    end
    local function forgetlexi()
        table.remove(IdxStack)
    end

    local function expect(t)
        local a, b, c, d = gettoken()
        if t ~= a then
            error(string.format("%i:%i expected %s, got %s", c, d, t, a))
        end
        return a, b, c, d
    end

    local parse_chunk

    local function new_parse_context(parent)
        return setmetatable({["the parent"] = parent}, {
            __index = function(self, key)
                while true do
                    local r = rawget(self, key)
                    if r then
                        return r
                    end
                    self = rawget(self, "the parent")
                    if not self then
                        return
                    end
                end
            end,
            __newindex = function(self, key, value)
                local z = self
                local r = nil
                while true do
                    r = rawget(z, key)
                    if r then break end
                    z = rawget(z, "the parent")
                    if not z then break end
                end
                rawset(z or self, key, value)
            end,
        })
    end

    local ParseContext, ParseContextTypes

    local function push_parse_context()
        ParseContext = new_parse_context(ParseContext)
        ParseContextTypes = new_parse_context(ParseContextTypes)
    end

    local function pop_parse_context()
        ParseContext = rawget(ParseContext, "the parent")
        ParseContextTypes = rawget(ParseContextTypes, "the parent")
    end

    local Types = {}
    function Types.castable(this, to)
        return not to or (this and this.type == to.type)
    end
    function Types.is_number(this)
        return not this or this.type == 'number' or this.type == 'integer'
    end
    function Types.can_do_arith(this)
        return Types.is_number(this)
    end
    function Types.is_callable(this)
        return not this or this.type == 'function'
    end
    function Types.is_indexable(this)
        return not this or this.type == 'list'
    end
    function Types.has_field(this, field)
        if not this then
            return true, nil
        end
        
        if this.type == 'list' and field == 'pop' then
            return true, {type = 'function', ret = false, args = {this}}
        end
        
        if this.type ~= 'structure' then
            return false, nil
        end
        
        for k, v in ipairs(this.members) do
            if v.name == field then
                return true, v.et
            end
        end
        
        return false, nil
    end

    local function parse_et()
        local A
        
        if peektoken() == "id" then
            local name = select(2, gettoken())
            if name == "number" then
                A = {type = 'number'}
            elseif name == "integer" then
                A = {type = 'integer'}
            elseif name == "string" then
                A = {type = 'string'}
            elseif name == "boolean" then
                A = {type = 'boolean'}
            elseif name == "list" then
                A = {type = 'list'}
            elseif name == "dict" then
                A = {type = 'dict'}
            else
                A = ParseContextTypes[name]
            end
        end
        
        if not A then
            error("Invalid type description")
        end
        
        if maybe("[") then
            A.parametrization = {parse_et()}
            
            expect("]")
        end
        
        return A
    end

    local parse_function

    local function parse_function_arg()
        local name = select(2, expect("id"))
        local et
        if maybe(":") then
            et = parse_et()
        end
        return name, et
    end

    local function parse_type()
        expect("type")
        
        local name = select(2, expect("id"))
        
        local ret = {type = 'structure', members = {}, name = name}
        
        while true do
            if maybe("end") then
                break
            end
            
            if peektoken() == "constr" or peektoken() == "func" then
                local isConstr = gettoken() == "constr"
                local fname
                
                if isConstr then
                    fname = "__call"
                else
                    fname = select(2, expect("id"))
                end
                
                local argnames = {}
                local argets = {}
                
                if not isConstr then
                    table.insert(argnames, "self")
                    table.insert(argets, ret)
                end
                
                push_parse_context()
                rawset(ParseContext, "self", {et = ret, name = "self"})
                
                if maybe("(") then
                    if not maybe(")") then
                        
                        while true do
                            local name, et = parse_function_arg()
                            
                            table.insert(argnames, name)
                            argets[#argnames] = et
                            
                            rawset(ParseContext, name, {et = et, name = name})
                            
                            if maybe(")") then
                                break
                            else
                                expect(",")
                            end
                        end
                    end
                end
                
                local fret
                if isConstr then
                    fret = ret
                else
                    if maybe(":") then
                        fret = parse_et()
                    end
                end
                
                local chu = parse_chunk(false)
                
                local et = {type = "function", args = argets, ret = fret}
                
                table.insert(ret.members, {
                    type = "static",
                    name = fname,
                    et = et,
                    value = {type = "function", et = et, args = argnames, chunk = chu, is_constructor = isConstr},
                })
                
                pop_parse_context()
                
                expect("end")
            else
                local membname = select(2, expect("id"))
                
                expect(":")
                
                local et = parse_et()
                
                table.insert(ret.members, {type = "field", name = membname, et = et})
            end
        end
        
        return name, ret
    end

    parse_function = function()
        expect("func")
        
        local name = select(2, maybe("id"))
        
        push_parse_context()
        
        local argnames = {}
        local argets = {}
        
        if maybe("(") then
            if not maybe(")") then
                while true do
                    local name, et = parse_function_arg()
                    
                    table.insert(argnames, name)
                    argets[#argnames] = et
                    
                    rawset(ParseContext, name, {et = et, name = name})
                    
                    if maybe(")") then
                        break
                    else
                        expect(",")
                    end
                end
            end
        end
        
        local retet
        if maybe(":") then
            retet = parse_et()
        end
        
        rawset(ParseContext, "the function name", name)
        rawset(ParseContextTypes, "the function return type", retet)
        
        local ret = {
            type = "function",
            et = {type = "function", args = argets, ret = retet},
            chunk = parse_chunk(false),
            args = argnames
        }
        
        pop_parse_context()
        
        expect("end")
        
        return ret, name
    end

    local active_stmt_list_stack = {}

    BINOP_LEVELS = {["+"] = 3, ["-"] = 3, ["=="] = 4, ["/"] = 2, ["*"] = 2, ["%"] = 2, ["**"] = 1}
    local function parse_expr(level)
        level = level or 4
        
        if level == 4 then
            local A = parse_expr(level - 1)
            
            if peektoken() == "==" then
                local op = gettoken()
                
                local B = parse_expr(level - 1)
                
                A = {type = "binop", level = level, et = {type = 'boolean'}, op = op, a = A, b = B}
            end
            
            return A
        elseif level == 3 then
            local A = parse_expr(level - 1)
            
            if peektoken() == "+" or peektoken() == "-" then
                local op = gettoken()
                
                local B = parse_expr(level - 1)
                
                if not Types.can_do_arith(A.et) or not Types.can_do_arith(B.et) then
                    error(op .. " operator not supported for non-number types")
                end
                
                A = {type = "binop", level = level, et = A.et, op = op, a = A, b = B}
            end
            
            return A
        elseif level == 2 then
            local A = parse_expr(level - 1)
            
            if peektoken() == "*" or peektoken() == "/" or peektoken() == "%" then
                local op = gettoken()
                
                local B = parse_expr(level - 1)
                
                if not Types.can_do_arith(A.et) or not Types.can_do_arith(B.et) then
                    error(op .. " operator not supported for non-number types")
                end
                
                A = {type = "binop", level = level, et = A.et, op = op, a = A, b = B}
            end
            
            return A
        elseif level == 1 then
            local A = parse_expr(level - 1)
            
            if peektoken() == "**" then
                local op = gettoken()
                
                local B = parse_expr(level - 1)
                
                if not Types.can_do_arith(A.et) or not Types.can_do_arith(B.et) then
                    error(op .. " operator not supported for non-number types")
                end
                
                A = {type = "binop", level = level, et = A.et, op = op, a = A, b = B}
            end
            
            return A
        elseif level == 0 then
            local A
            
            if maybe("#") then
                A = {type = 'lengthof', et = {type = 'integer'}, sub = parse_expr(level)}
                
                if A.sub.et and A.sub.et.type ~= 'list' then
                    error("# requires a list")
                end
            elseif maybe("(") then
                A = parse_expr()
                expect(")")
            elseif peektoken() == "func" then
                A = parse_function()
            elseif peektoken() == "num" then
                local lit = select(2, gettoken())
                A = {type = "num", et = lit:find("%.") and {type = 'number'} or {type = 'integer'}, value = tonumber(lit)}
            elseif peektoken() == "id" then
                local name = select(2, gettoken())
                local v = ParseContext[name]
                if not v then
                    error(string.format("No value with name %s exists.", name))
                end
                A = {type = "var", which = v, et = v.et}
            elseif maybe("{") then
                A = {type = "dict", et = {type = "dict", parametrization = {}}, mappings = {}}
                expect("}")
            elseif maybe("[") then
                A = {type = "list", et = {type = "list", parametrization = {}}, values = {}}
                expect("]")
            elseif peektoken() == "string" then
                A = {type = "string", et = {type = 'string'}, value = select(2, gettoken())}
            elseif maybe("nil") then
                A = {type = 'null', et = {type = 'null'}}
            else
                error("Unexpected token " .. select(2, peektoken()))
            end
            
            while peektoken() == "[" or peektoken() == "(" or peektoken() == "." do
                if maybe("[") then
                    if A.et and A.et.type ~= 'list' and A.et.type ~= 'dict' and A.et.type ~= 'string' then
                        error("Indexed value is not a list nor dict.")
                    end
                    
                    local newet
                    if A.et.type == 'list' then
                        newet = A.et.parametrization and A.et.parametrization[1]
                    elseif A.et.type == 'dict' then
                        newet = A.et.parametrization and A.et.parametrization[2]
                    elseif A.et.type == 'string' then
                        newet = A.et
                    else
                        error()
                    end
                    
                    local idx = parse_expr()
                    
                    if A.et.type == 'string' then
                        local temp = {name = unique_name(), et = nil}
                        
                        table.insert(active_stmt_list_stack[#active_stmt_list_stack], {
                            type = 'let',
                            var = temp,
                            expr = {type = 'binop', level = BINOP_LEVELS['+'], op = '+', a = idx, b = {type = 'num', value = 1, et = {type = 'integer'}}}
                        })
                        
                        A = {
                            type = 'call',
                            what = {type = 'dot', colon = true, a = A, b = 'sub', et = nil},
                            args = {
                                {type = 'var', which = temp, et = temp.et},
                                {type = 'var', which = temp, et = temp.et}
                            }
                        }
                    else
                        if A.et.type == 'list' then
                            -- Switch to 1-based indexing
                            idx = {type = 'binop', level = BINOP_LEVELS['+'], op = '+', a = idx, b = {type = 'num', value = 1, et = {type = 'integer'}}}
                        end
                        
                        A = {type = 'index', what = A, idx = idx, et = newet}
                    end
                    
                    expect("]")
                elseif maybe("(") then
                    if not Types.is_callable(A.et) then
                        error("Called value is not a function.")
                    end
                    
                    local args = {}
                    
                    if not maybe(")") then
                        while true do
                            table.insert(args, parse_expr())
                            
                            if maybe(")") then break end
                            
                            expect(",")
                        end
                    end
                    
                    A = {type = 'call', what = A, et = A.et and A.et.ret or nil, args = args}
                elseif maybe(".") then
                    local B = select(2, expect("id"))
                    
                    local has_field, field_type = Types.has_field(A.et, B)
                    
                    if not has_field then
                        error(string.format("No such field %s", B))
                    end
                    
                    A = {type = 'dot', a = A, b = B, et = field_type}
                end
            end
            
            return A
        end
        
        error("Invalid expression")
    end

    local function parse_stmt()
        if maybe("let") then
            local name = select(2, expect("id"))
            
            local et
            if maybe(":") then
                et = parse_et()
            end
            
            local expr
            if maybe("=") then
                expr = parse_expr()
            end
            
            if not et and not expr then
                error(string.format("Cannot create name %s without a given type", name))
            end
            
            if not et then
                et = expr.et
            elseif expr and not Types.castable(expr.et, et) then
                error(string.format("Cannot cast expression to type %s", et.type))
            end
            
            local newvar = {et = et, name = name}
            
            ParseContext[name] = newvar
            
            return {type = "let", var = newvar, expr = expr}
        elseif maybe("if") then
            local ret = {type = "if"}
            
            while true do
                local expr = parse_expr()
                if not et and not Types.castable(expr.et, {type = 'boolean'}) then
                    error("If predicate must be castable to boolean")
                end
                
                expect("then")
                
                local chu = parse_chunk(false)
                
                table.insert(ret, {pred = expr, chu = chu})
                
                if maybe("else") then
                    ret.elsa = parse_chunk(false)
                    
                    expect("end")
                    
                    break
                end
                
                if maybe("end") then
                    break
                end
                
                expect("elseif")
            end
            
            return ret
        elseif maybe("for") then
            local varname = select(2, expect("id"))
            
            expect("=")
            
            local from = parse_expr()
            
            expect(",")
            
            local to = parse_expr()
            
            expect("do")
            
            push_parse_context()
            
            rawset(ParseContext, varname, {et = {type = 'integer'}, name = varname})
            
            local chu = parse_chunk(false)
            
            pop_parse_context()
            
            expect("end")
            
            return {type = "fori", varname = varname, from = from, to = to, chu = chu}
        elseif maybe("loop") then
            push_parse_context()
            local chu = parse_chunk(false)
            pop_parse_context()
            expect("end")
            
            return {type = "loop", chu = chu}
        elseif maybe("break") then
            return {type = "break"}
        elseif maybe("return") then
            local expr = parse_expr()
            
            if expr.et and not Types.castable(expr.et, ParseContextTypes["the function return type"]) then
                error(string.format("Function %s returns different type.", ParseContext["the function name"]))
            end
            
            return {type = "return", expr = expr}
        else
            local e = parse_expr()
            
            if maybe("=") then
                local src = parse_expr()
                
                if not Types.castable(src.et, e.et) then
                    error("Cannot cast for assignment")
                end
                
                return {type = "assign", dest = e, src = src}
            else
                if e.type ~= "call" then
                    error("Expected statement.")
                end
                
                return e
            end
        end
        
        error(string.format("Unexpected token %s", (select(2, peektoken()))))
    end

    local SAFE_MODE = true

    parse_chunk = function(toplevel)
        push_parse_context()
        
        local ast = {type = "chunk", types = {}, vars = {}, stmts = {}, imports = {}, toplevel = toplevel}
        
        table.insert(active_stmt_list_stack, ast.stmts)
        
        while true do
            local tt, ts, tr, tc = peektoken()
            
            if tt == "end" or tt == "else" or tt == "elseif" then
                if toplevel then
                    error("Unexpected end in top-level chunk")
                end
                
                break
            elseif tt == nil then
                if not toplevel then
                    error("Unexpected EOF in non top-level chunk")
                end
                
                break
            end
            
            if toplevel and tt == "import" then
                gettoken()
                
                local path = {}
                
                while true do
                    local part = select(2, expect("id"))
                    table.insert(path, part)
                    
                    if not maybe(".") then
                        break
                    end
                end
                
                
                
                rawset(ParseContext, path[#path], {et = nil, name = path[#path]})
                
                table.insert(ast.imports, path)
            elseif tt == "type" then
                local name, t = parse_type()
                ast.types[name] = t
                rawset(ParseContextTypes, name, t)
            elseif tt == "func" then
                local expr, name = parse_function()
                ast.vars[name] = expr
                rawset(ParseContext, name, {et = expr.et, name = name})
            elseif not toplevel then
                table.insert(ast.stmts, parse_stmt())
            else
                error(string.format("Unexpected %s in top-level chunk", tt))
            end
        end
        
        table.remove(active_stmt_list_stack)
        
        pop_parse_context()
        
        return ast
    end
    
    return parse_chunk(true)
end

--local chu = parse_chunk(true)
--pass_destandardify(chu)
--compile(chu)
--print()

return do_everything