/// The parser converts a stream of tokens generated by a lexer into an
/// abstract syntax tree that will be used by later stages of the 
/// compilation process.
///
/// It generates and operates the lexer internally
open class Parser {

    /// The lexer that converts the source code into tokens
    private var lexer: Lexer!

    /// The token that shall be parsed next
    public var nextToken: Token!

    /// The last token that was parsed
    private var lastToken: Token?

    public init() {
    }

    /// Parse the sourceCode of this parser into an abstract syntax tree (AST)
    ///
    /// - Parameter sourceFile: The source file to parse
    /// - Returns: The parsed abstract syntax tree
    /// - Throws: A CompilationError if compilation failed
    public static func parse(sourceFile: SwiftFile) throws -> ASTRoot {
        let parser = Parser()
        return try parser.parse(sourceFile: sourceFile)
    }

    /// Parse the sourceCode of this parser into an abstract syntax tree (AST)
    ///
    /// - Parameter sourceFile: The source file to parse
    /// - Returns: The parsed abstract syntax tree
    /// - Throws: A CompilationError if compilation failed
    public func parse(sourceFile: SwiftFile) throws -> ASTRoot {
        self.lexer = Lexer(sourceCode: sourceFile.sourceCode)

        self.nextToken = try lexer.nextToken()
        let startLoc = self.nextToken.sourceRange.start

        var statements: [Statement] = []
        while nextToken.payload != .endOfFile {
            statements.append(try parseStatement())
        }

        let endLoc = self.nextToken.sourceRange.start

        return ASTRoot(statements: statements,
                       sourceRange: SourceRange(start: startLoc, end: endLoc))
    }

    /// Create a source range starting at the given location and ending at the curren 
    /// position
    ///
    /// - Parameter startingAt: The source location where the range shall start
    /// - Returns: A range starting at the given location and ending at the current token
    public func range(startingAt: SourceLoc) -> SourceRange {
        if let lastToken = lastToken {
            return SourceRange(start: startingAt, end: lastToken.sourceRange.end)
        } else {
            return SourceRange(start: startingAt, end: nextToken.sourceRange.start)
        }
    }

    /// Consume the next token and fill the nextToken variable with
    /// the upcoming token from the lexer
    ///
    /// - Returns: The token that has just been consumed
    /// - Throws: A CompilationError if the lexer failed to return the next token
    @discardableResult
    public func consumeToken() throws -> Token? {
        lastToken = nextToken
        nextToken = try self.lexer.nextToken()
        return lastToken
    }

    /// Consume the current token if it is of the given TokenKind
    ///
    /// - Parameter token: The type of the token that shall be consume if possible
    /// - Returns: Whether or not a token has been consumed
    /// - Throws: A CompilationError if the lexer failed to return the next token
    @discardableResult
    func consumeIf(_ token: TokenKind) throws -> Bool {
        if nextToken.payload == token {
            try consumeToken()
            return true
        } else {
            return false
        }
    }


    /// Parse the base of an expression, i.e. expressions that cannot contain nested expressions
    /// This currently only includes literals and identifiers (for variables)
    ///
    /// - Returns: The parsed expression
    /// - Throws: A CompilationError if compilation failed
    private func parseBaseExpression() throws -> Expression {
        switch nextToken.payload {
        case .integer(let value):
            let sourceRange = nextToken.sourceRange
            try consumeToken()
            return IntegerLiteralExpression(value: value, sourceRange: sourceRange)
        case .stringLiteral(let value):
            let sourceRange = nextToken.sourceRange
            try consumeToken()
            return StringLiteralExpression(value: value, sourceRange: sourceRange)
        case .identifier(let name):
            let identifierRange = nextToken.sourceRange
            try consumeToken()
            if try consumeIf(.leftParen) {
                var arguments: [Expression] = []
                while true {
                    if try consumeIf(.rightParen) {
                        break
                    }
                    arguments.append(try parseExpression())
                    if !(try consumeIf(.comma)) {
                        if !(try consumeIf(.rightParen)) {
                            throw CompilationError(sourceRange: nextToken.sourceRange, errorMessage: "Expected ')' to terminate function call")
                        }
                        break
                    }
                }

                return FunctionCallExpression(functionName: name,
                                              arguments: arguments,
                                              functionNameRange: identifierRange,
                                              sourceRange: range(startingAt: identifierRange.start))
            } else {
                return IdentifierReferenceExpression(name: name, sourceRange: range(startingAt: identifierRange.start))
            }
        default:
            throw CompilationError(sourceRange: nextToken.sourceRange,
                                   errorMessage: "Expected expression but found '\(nextToken.payload.sourceCodeRepresentation)'")
        }
    }

    /// Parse an expression including nested expressions. Takes an optional argument to specify
    /// that restrict the operators in order to parse to parse expressions with binary operators
    /// of different precedences correctly
    ///
    /// - Parameter precedenceGreaterOrEqualThan: Only parse binary operator expressions if their
    ///   operator's precedence is greater or equal to the value
    /// - Returns: The parsed expression
    /// - Throws: A CompilationError if compilation failed
    public func parseExpression(precedenceGreaterOrEqualThan: Int = 0) throws -> Expression {
        var workingExpression = try parseBaseExpression()

        while case .operator(let name) = nextToken.payload {
            let binOpRange = nextToken.sourceRange
            let binOperator: BinaryOperatorExpression.Operator
            switch name {
            case "+":
                binOperator = .add
            case "-":
                binOperator = .sub
            case "==":
                binOperator = .equal
            case "<=":
                binOperator = .lessOrEqual
            default:
                try consumeToken()
                throw CompilationError(sourceRange: binOpRange,
                                       errorMessage: "Unknown operator '\(name)'")
            }
            if binOperator.precedence < precedenceGreaterOrEqualThan {
                break
            }

            try consumeToken()

            let rhs = try parseExpression(precedenceGreaterOrEqualThan: binOperator.precedence)
            workingExpression = BinaryOperatorExpression(lhs: workingExpression,
                                                         rhs: rhs,
                                                         operator: binOperator)
        }
        return workingExpression
    }


    /// Parses a single statement
    ///
    /// - Returns: The parsed expression
    /// - Throws: A CompilationError if compilation failed
    private func parseStatement() throws -> Statement {
        switch nextToken.payload {
        case .if:
            return try parseIfStatement()
        case .func:
            return try parseFunctionDeclaration()
        case .return:
            let returnRange = nextToken.sourceRange
            try consumeToken()
            let expr = try parseExpression()
            return ReturnStatement(expression: expr, sourceRange: range(startingAt: returnRange.start))
        default:
            return try parseExpression()
        }
    }

    private func parseFunctionDeclaration() throws -> FunctionDeclaration {
        guard nextToken.payload == .func else {
            throw CompilationError(sourceRange: nextToken.sourceRange, errorMessage: "Expected 'func' but saw \(nextToken!)")
        }
        let funcKeywordRange = nextToken.sourceRange
        try consumeToken()
        guard case .identifier(let funcName) = nextToken.payload else {
            throw CompilationError(sourceRange: nextToken.sourceRange, errorMessage: "Expected identifier after 'func' keyword but saw \(nextToken!)")
        }
        try consumeToken()
        guard try consumeIf(.leftParen) else {
            throw CompilationError(sourceRange: nextToken.sourceRange, errorMessage: "Expeced '(' to start the functions parameter list but saw \(nextToken!)")
        }

        var parameters: [VariableDeclaration] = []

        while true {
            if try consumeIf(.rightParen) {
                break
            }
            guard try consumeIf(.underscore) else {
                throw CompilationError(sourceRange: nextToken.sourceRange,
                                       errorMessage: "Named parameters are not supported yet")
            }
            parameters.append(try parseVariableDeclaration())
            if !(try consumeIf(.comma)) {
                if !(try consumeIf(.rightParen)) {
                    throw CompilationError(sourceRange: nextToken.sourceRange, errorMessage: "Expeced ')' to end the functions parameter list but saw \(nextToken!)")
                }
                break
            }
        }

        var returnTypeName = "Void"
        if try consumeIf(.arrow) {
            guard case .identifier(let returnTypeName2) = nextToken.payload else {
                throw CompilationError(sourceRange: nextToken.sourceRange, errorMessage: "Expeced the function's return type but saw \(nextToken!)")
            }
            try consumeToken()
            returnTypeName = returnTypeName2
        }

        let body = try parseBraceStatement()

        guard let returnType = Type.fromString(returnTypeName) else {
            throw CompilationError(sourceRange: nextToken.sourceRange, errorMessage: "Unknown type '\(returnTypeName)'")
        }

        return FunctionDeclaration(name: funcName, parameters: parameters, returnType: returnType, body: body, sourceRange: range(startingAt: funcKeywordRange.start))
    }

    private func parseVariableDeclaration() throws -> VariableDeclaration {
        let startLoc = nextToken.sourceRange.start
        guard case .identifier(let paramName) = nextToken.payload else {
            throw CompilationError(sourceRange: nextToken.sourceRange, errorMessage: "Expected identifier to specify the parameter's name but saw \(nextToken!)")
        }
        try consumeToken()
        guard try consumeIf(.colon) else {
            throw CompilationError(sourceRange: nextToken.sourceRange, errorMessage: "Expected ':' to seperate the parameter's name and type but saw \(nextToken!)")
        }
        guard case .identifier(let paramTypeName) = nextToken.payload else {
            throw CompilationError(sourceRange: nextToken.sourceRange, errorMessage: "Expected identifier to specify the parameter's type but saw \(nextToken!)")
        }
        guard let paramType = Type.fromString(paramTypeName) else {
            throw CompilationError(sourceRange: nextToken.sourceRange, errorMessage: "Unknown type '\(paramTypeName)'")
        }
        try consumeToken()
        return VariableDeclaration(name: paramName, type: paramType, sourceRange: range(startingAt: startLoc))
    }

    open func parseIfStatement() throws -> Statement {
        guard nextToken == .if else {
            throw CompilationError(sourceRange: nextToken.sourceRange, errorMessage: "Expected 'if' but saw \(nextToken!)")
        }
        let ifRange = nextToken.sourceRange
        try consumeToken()
        let condition = try parseExpression()
        let body = try parseBraceStatement()
        var elseBody: BraceStatement? = nil
        var elseRange: SourceRange? = nil
        if nextToken == .else {
            elseRange = nextToken.sourceRange
            try consumeToken()
            elseBody = try parseBraceStatement()
        }
        return IfStatement(condition: condition,
                           body: body,
                           elseBody: elseBody,
                           ifRange: ifRange,
                           elseRange: elseRange,
                           sourceRange: range(startingAt: ifRange.start))
    }


    /// Parse a brace statement including its braces '{' and '}'
    ///
    /// - Returns: The parsed expression
    /// - Throws: A CompilationError if compilation failed
    public func parseBraceStatement() throws -> BraceStatement {
        let startLoc = nextToken.sourceRange.start
        if !(try consumeIf(.leftBrace)) {
            throw CompilationError(location: nextToken.sourceRange.start,
                                   errorMessage: "Missing '{' to start body of brace statement")
        }
        var body: [Statement] = []
        while self.nextToken.payload != .rightBrace {
            let stmt = try parseStatement()
            body.append(stmt)
        }
        assert(nextToken.payload == .rightBrace)
        try consumeToken()

        return BraceStatement(body: body, sourceRange: range(startingAt: startLoc))
    }
}
