local LogicParser = {}

function LogicParser:functionNames()
    local result = {}
    for k in pairs(LogicLibrary.functions) do
        result[#result + 1] = k
    end
    for k in pairs(LogicLibrary.constants) do
        result[#result + 1] = k
    end
    return result
end

local numberPattern1 = '^[%d%.]+'
local numberPattern2 = '^[eE][%+%-]?%d+'

local function readnumber(input, start)
    local _, last = string.find(input, numberPattern1, start)
    if last then
        local _, elast = string.find(input, numberPattern2, last + 1)
        if elast then
            last = elast
        end
    end
    local result
    if last then
        result = tonumber(string.sub(input, start, last))
    end
    return result, last
end

local stringPattern1 = '^"'
local stringPattern2 = '([\\"])'

local function readstring(input, start)
    local result
    local full = false
    local _, last = string.find(input, stringPattern1, start)
    if last then
        result = ''
        while true do
            local searchStart = last + 1
            local match
            _, last, match = string.find(input, stringPattern2, searchStart)
            if match then
                result = result .. string.sub(input, searchStart, last - 1)
                if match == '\\' then
                    result = result .. string.sub(input, last + 1, last + 1)
                    last = last + 1
                elseif match == '"' then
                    full = true
                    break
                end
            else
                last = #input
                break
            end
        end
    end
    return result, last, full
end

local breakPattern = '([%s%+%-%*/%^%%&<=>%(%)%[%]%$#,])'
local comparatorPattern = '^([<=>][<=>]?)'
local comparators = { ['='] = true, ['<'] = true, ['>'] = true, ['<>'] = true, ['<='] = true, ['>='] = true }
local types = {
    ['+'] = 'operator', ['-'] = 'operator', ['*'] = 'operator', ['/'] = 'operator', ['^'] = 'operator', ['%'] = 'operator', ['&'] = 'operator',
    ['='] = 'operator', ['<'] = 'operator', ['>'] = 'operator', ['<>'] = 'operator', ['<='] = 'operator', ['>='] = 'operator',
    ['('] = 'leftparen', [')'] = 'rightparen', ['['] = 'leftbracket', [']'] = 'rightbracket', [','] = 'comma', ['$'] = 'lookup', ['#'] = 'index',
}

function LogicParser:tokenize(input)
    local result = {input = input}
    local start = 1
    while input do
        local numberValue, stringValue, loc, last, match, full
        numberValue, last = readnumber(input, start)
        if numberValue and last then
            result[#result + 1] = {start = start, last = last, type = 'number', value = numberValue, input = input:sub(start, last)}
            start = last + 1
        end
        stringValue, last, full = readstring(input, start)
        if stringValue and last then
            local fullType = {[false] = 'partial', [true] = 'string'}
            result[#result + 1] = {start = start, last = last, type = fullType[full], value = stringValue, input = input:sub(start, last):gsub('[\n\t]', ' ')}
            start = last + 1
        end
        loc, last, match = string.find(input, breakPattern, start)
        if loc then
            local comparatorLoc, comparatorLast, comparatorMatch = string.find(input, comparatorPattern, loc)
            if comparatorLoc and comparators[comparatorMatch] then
                last = comparatorLast
                match = comparatorMatch
            end
        else
            loc = #input + 1
        end
        local identifier = string.sub(input, start, loc - 1)
        if identifier ~= '' then
            result[#result + 1] = {start = start, last = loc - 1, type = 'identifier', value = identifier, input = identifier}
        end
        if not match then
            break
        end
        if not string.find(match, '%s') then
            result[#result + 1] = {start = loc, last = last, type = types[match], value = match, input = match}
        end
        start = last + 1
    end
    return result
end

local function execTree(node)
    if node.operation then
        local arguments = {}
        for index = 1, #node.values do
            arguments[index] = execTree(node.values[index])
        end
        return node.operation(unpack(arguments))
    else
        return unpack(node)
    end
end

local push, pop, peek
do
    push = function(stack, item)
        stack[#stack + 1] = item
    end
    pop = function(stack)
        local result = stack[#stack]
        stack[#stack] = nil
        return result
    end
    peek = function(stack, skip)
        return stack[#stack - (skip or 0)]
    end
end

local newNode
do
    newNode = function(token, operationFunction, values)
        return {
            token = token,
            operation = operationFunction,
            values = values,
        }
    end
end

local newOperation, newFunction
do
    local unarySymbol = {
        ['-'] = 'U-',
    }
    local precedence = {
        ['U-'] = 5,
        ['^'] = 5,
        ['%'] = 4,
        ['/'] = 4,
        ['*'] = 4,
        ['-'] = 3,
        ['+'] = 3,
        ['&'] = 2,
        ['='] = 1,
        ['<>'] = 1,
        ['>'] = 1,
        ['<'] = 1,
        ['>='] = 1,
        ['<='] = 1,
        ['('] = 0,
        [')'] = 0,
        ['['] = 0,
        [']'] = 0,
        [','] = 0,
    }
    local func = {
        ['U-'] = Sequence.__unm,
        ['^'] = Sequence.__pow,
        ['%'] = Sequence.__mod,
        ['/'] = Sequence.__div,
        ['*'] = Sequence.__mul,
        ['-'] = Sequence.__sub,
        ['+'] = Sequence.__add,
        ['&'] = Sequence.__concat,
        ['='] = Sequence.____eq,
        ['<>'] = Sequence.____ne,
        ['>'] = Sequence.____gt,
        ['<'] = Sequence.____lt,
        ['>='] = Sequence.____ge,
        ['<='] = Sequence.____le,
    }
    local rightAssociativity = {
        ['U-'] = true,
        ['^'] = true,
    }
    newOperation = function(token, symbol, isUnary)
        local operands = 2
        if isUnary then
            symbol = unarySymbol[symbol]
            operands = 1
        end
        if symbol then
            return {
                token = token,
                symbol = symbol,
                func = func[symbol] or symbol,
                operands = operands,
                precedence = precedence[symbol],
                rightAssociative = rightAssociativity[symbol],
            }
        end
    end
    newFunction = function(token, func, operands)
        return {
            token = token,
            symbol = 'func',
            func = func,
            operands = operands,
            precedence = 0,
            rightAssociative = false,
        }
    end
end

function LogicParser:build(tokens, errorFunction)
    local lookupNodes = {}
    local indexNodes = {}
    local dependencies = {}
    local valueStack = {}
    local operationStack = {}
    local unravelLoop = function(terminationTest)
        while #operationStack > 0 do
            if terminationTest() then
                return true
            end
            local stackOperation = pop(operationStack)
            local values = {}
            for index = stackOperation.operands, 1, -1 do
                values[index] = pop(valueStack)
            end
            local operationFunction = stackOperation.func or function(_) return _ end
            push(valueStack, newNode(stackOperation.token, operationFunction, values))
        end
    end
    local loopResult
    local expectingBinaryOp = false
    local index = 1
    local expectBinaryOp = function(token)
        expectingBinaryOp = true
        local nextToken = tokens[index]
        if nextToken and not (nextToken.type == 'operator' or nextToken.type == 'comma' or nextToken.type == 'rightparen' or nextToken.type == 'rightbracket') then
            errorFunction("Symbol expected between " .. token.input .. " and " .. nextToken.input, nextToken)
            return false
        end
        return true
    end
    while index <= #tokens do
        local token = tokens[index]
        index = index + 1
        local type = token.type
        local value = token.value
        local nextToken = tokens[index]
        if type == 'partial' then
            errorFunction("String not closed: " .. token.input, token)
            return
        elseif type == 'identifier' then
            local key = string.upper(value)
            if LogicLibrary.constants[key] then
                push(valueStack, { LogicLibrary.constants[key] })
                if not expectBinaryOp(token) then
                    return
                end
            elseif LogicLibrary.functions[key] then
                local operation = newFunction(token, LogicLibrary.functions[key], #valueStack)
                push(operationStack, operation)
                expectingBinaryOp = false
                if not nextToken or nextToken.type ~= 'leftparen' then
                    errorFunction("Parentheses expected after function: " .. token.input, token)
                    return
                end
            else
                errorFunction("Constant or function does not exist: " .. token.input, token)
                return
            end
        elseif type == 'lookup' then
            if not nextToken then
                errorFunction("Field name expected.", token)
                return
            end
            index = index + 1
            type = nextToken.type
            value = nextToken.value
            if type == 'number' or type == 'string' then
                local key = Dataset:normalize(value)
                lookupNodes[#lookupNodes + 1] = newNode(nextToken, true, { { key } })
                push(valueStack, lookupNodes[#lookupNodes])
                dependencies[key] = nextToken
            elseif type == 'partial' then
                errorFunction("Field name string not closed: " .. nextToken.input, nextToken)
                return
            else
                errorFunction("Field name expected before " .. nextToken.input, token)
                return
            end
            if not expectBinaryOp(nextToken) then
                return
            end
        elseif type == 'leftparen' or type == 'leftbracket' then
            if type == 'leftbracket' then
                local operation = newFunction(token, LogicLibrary.functions.SEQUENCE, #valueStack)
                push(operationStack, operation)
            end
            local operation = newOperation(token, value, false)
            push(operationStack, operation)
            expectingBinaryOp = false
        elseif type == 'rightparen' or type == 'rightbracket' then
            local loopError
            loopResult = unravelLoop(function()
                local stackOperation = peek(operationStack)
                local stackType = stackOperation.token.type
                if (stackType == 'leftparen' and type == 'rightparen') or (stackType == 'leftbracket' and type == 'rightbracket') then
                    pop(operationStack)
                    if #operationStack > 0 then
                        stackOperation = peek(operationStack)
                        if stackOperation.symbol == 'func' then
                            pop(operationStack)
                            local values = {}
                            while #valueStack > stackOperation.operands do
                                local index = #valueStack - stackOperation.operands
                                values[index] = pop(valueStack)
                            end
                            push(valueStack, newNode(stackOperation.token, stackOperation.func, values))
                        end
                    end
                    return true
                elseif (stackType == 'leftparen' and type ~= 'rightparen') or (stackType == 'leftbracket' and type ~= 'rightbracket') then
                    loopError = true
                end
            end)
            if loopError or not loopResult then
                if type == 'rightparen' then
                    errorFunction("Mismatched parenthesis.", token)
                else
                    errorFunction("Mismatched bracket.", token)
                end
                return
            end
            if not expectBinaryOp(token) then
                return
            end
        elseif type == 'comma' then
            local loopError
            loopResult = unravelLoop(function()
                local stackOperation = peek(operationStack)
                if stackOperation.token.type == 'leftparen' or stackOperation.token.type == 'leftbracket' then
                    stackOperation = peek(operationStack, 1)
                    if not (stackOperation and stackOperation.symbol == 'func') then
                        loopError = true
                    end
                    return true
                end
            end)
            if loopError or not loopResult then
                errorFunction("Comma outside of sequence or function argument list.", token)
                return
            end
            expectingBinaryOp = false
        elseif type == 'operator' then
            local operation = newOperation(token, value, not expectingBinaryOp)
            if not operation then
                errorFunction("Value expected before " .. token.input, token)
                return
            end
            unravelLoop(function()
                local stackOperation = peek(operationStack)
                if operation.precedence > stackOperation.precedence or (operation.precedence == stackOperation.precedence and operation.rightAssociative) then
                    return true
                end
            end)
            push(operationStack, operation)
            expectingBinaryOp = false
            if not nextToken or (nextToken.type == 'rightparen' or nextToken.type == 'rightbracket') then
                errorFunction("Value expected after " .. token.input, token)
                return
            end
        elseif type == 'number' or type == 'string' then
            push(valueStack, { Sequence:newWithScalar(value) })
            if not expectBinaryOp(token) then
                return
            end
        elseif type == 'index' then
            indexNodes[#indexNodes + 1] = newNode(nextToken, true, {})
            push(valueStack, indexNodes[#indexNodes])
            if not expectBinaryOp(token) then
                return
            end
        end
    end
    loopResult = unravelLoop(function()
        local stackOperation = peek(operationStack)
        if stackOperation.token.type == 'leftparen' then
            errorFunction("Mismatched parenthesis.", stackOperation.token)
            return true
        end
        if stackOperation.token.type == 'leftbracket' then
            errorFunction("Mismatched bracket.", stackOperation.token)
            return true
        end
    end)
    if loopResult then
        return
    end
    local syntaxTree = pop(valueStack) or { Sequence:newWithScalar(nil) }
    return function(dataset)
        local lookupOperation = function(key) return KeyArtifact.applicatorFunction(key)(dataset) end
        local indexOperation = function() return IndexArtifact.applicatorFunction()(dataset) end
        for index = 1, #lookupNodes do
            lookupNodes[index].operation = lookupOperation
        end
        for index = 1, #indexNodes do
            indexNodes[index].operation = indexOperation
        end
        return execTree(syntaxTree)
    end, dependencies
end

return LogicParser
