//
//  Interpreter.swift
//  ShapeScript
//
//  Created by Nick Lockwood on 26/09/2018.
//  Copyright © 2018 Nick Lockwood. All rights reserved.
//

import Euclid
import Foundation

// MARK: Public interface

public let version = "1.6.13"

public protocol EvaluationDelegate: AnyObject {
    func resolveURL(for path: String) -> URL
    func importGeometry(for url: URL) throws -> Geometry?
    func debugLog(_ values: [AnyHashable])
}

public func evaluate(
    _ program: Program,
    delegate: EvaluationDelegate?,
    cache: GeometryCache? = GeometryCache(),
    isCancelled: @escaping () -> Bool = { false }
) throws -> Scene {
    let context = EvaluationContext(
        source: program.source,
        delegate: delegate,
        isCancelled: isCancelled
    )
    try program.evaluate(in: context)
    return Scene(
        background: context.background ?? .color(.clear),
        children: context.children.compactMap { $0.value as? Geometry },
        cache: cache
    )
}

public enum RuntimeErrorType: Error, Equatable {
    case unknownSymbol(String, options: [String])
    case unknownMember(String, of: String, options: [String])
    case unknownFont(String, options: [String])
    case typeMismatch(for: String, index: Int, expected: String, got: String)
    case forwardReference(String)
    case unexpectedArgument(for: String, max: Int)
    case missingArgument(for: String, index: Int, type: String)
    case unusedValue(type: String)
    case assertionFailure(String)
    case fileNotFound(for: String, at: URL?)
    case fileTimedOut(for: String, at: URL)
    case fileAccessRestricted(for: String, at: URL)
    case fileTypeMismatch(for: String, at: URL, expected: String?)
    case fileParsingError(for: String, at: URL, message: String)
    case circularImport(for: URL)
    indirect case importError(ProgramError, for: URL?, in: String)
}

public struct RuntimeError: Error, Equatable {
    public let type: RuntimeErrorType
    public let range: SourceRange

    public init(_ type: RuntimeErrorType, at range: SourceRange) {
        self.type = type
        self.range = range
    }
}

public extension RuntimeError {
    var message: String {
        switch type {
        case let .unknownSymbol(name, _):
            if Keyword(rawValue: name) == nil, Symbols.all[name] == nil, name != "option" {
                return "Unknown symbol '\(name)'"
            }
            return "Unexpected symbol '\(name)'"
        case let .unknownMember(name, type, _):
            return "Unknown \(type) member property '\(name)'"
        case let .unknownFont(name, _):
            return name.isEmpty ? "Font name cannot be blank" : "Unknown font '\(name)'"
        case .typeMismatch:
            return "Type mismatch"
        case .forwardReference:
            return "Forward reference"
        case .unexpectedArgument:
            return "Unexpected argument"
        case .missingArgument:
            return "Missing argument"
        case .unusedValue:
            return "Unused value"
        case .assertionFailure:
            return "Assertion failure"
        case let .fileNotFound(for: name, _):
            guard !name.isEmpty else {
                return "Empty file name"
            }
            return "File '\(name)' not found"
        case let .fileTimedOut(for: name, _):
            return "File '\(name)' timed out"
        case let .fileAccessRestricted(for: name, _):
            return "Unable to access file '\(name)'"
        case let .fileParsingError(for: name, _, _),
             let .fileTypeMismatch(for: name, _, _):
            return "Unable to open file '\(name)'"
        case .circularImport:
            return "Circular import"
        case let .importError(error, for: url, _):
            if case let .runtimeError(error) = error, case .importError = error.type {
                return error.message
            }
            let name = url.map { " '\($0.lastPathComponent)'" } ?? ""
            let error = error.range.map { _ in ": \(error.message)" } ?? ""
            return "Error in imported file\(name)\(error)"
        }
    }

    var suggestion: String? {
        switch type {
        case let .unknownSymbol(name, options), let .unknownMember(name, _, options):
            let alternative = Self.alternatives[name.lowercased()]?
                .first(where: { options.contains($0) || Keyword(rawValue: $0) != nil })
            if Symbols.all[name] != nil {
                return alternative
            }
            return alternative ?? name.bestMatches(in: options).first
        case let .unknownFont(name, options):
            return name.bestMatches(in: options).first
        case .typeMismatch,
             .forwardReference,
             .unexpectedArgument,
             .missingArgument,
             .unusedValue,
             .assertionFailure,
             .fileNotFound,
             .fileTimedOut,
             .fileAccessRestricted,
             .fileTypeMismatch,
             .fileParsingError,
             .circularImport,
             .importError:
            return nil
        }
    }

    var hint: String? {
        func nthArgument(_ index: Int) -> String {
            switch index {
            case 0 ..< String.ordinals.count:
                return "\(String.ordinals[index]) argument"
            default:
                return "argument"
            }
        }
        func theSymbol(_ name: String) -> String {
            if name.components(separatedBy: " ").count == 2 {
                return "The \(name)"
            } else if name.isEmpty {
                return "Symbol"
            } else if let symbol = Symbols.all[name] {
                return "The \(name) \(symbol.errorDescription)"
            }
            return "The \(name) symbol"
        }
        func formatMessage(_ message: String) -> String? {
            guard let last = message.last else {
                return nil
            }
            if ".?!".contains(last) {
                return message
            }
            return "\(message)."
        }
        switch type {
        case let .unknownSymbol(name, _):
            var hint = ""
            if let symbol = Symbols.all[name] {
                hint = "The \(name) \(symbol.errorDescription) is not available in this context."
            } else if Keyword(rawValue: name) != nil || name == "option" {
                hint = "The \(name) command is not available in this context."
            }
            if let suggestion = suggestion {
                hint += (hint.isEmpty ? "" : " ") + "Did you mean '\(suggestion)'?"
            }
            return hint
        case .unknownMember:
            return suggestion.map { "Did you mean '\($0)'?" }
        case .unknownFont:
            if let suggestion = suggestion {
                return "Did you mean '\(suggestion)'?"
            }
            return ""
        case let .typeMismatch(for: name, index: i, expected: type, got: got):
            let name = [
                "if condition",
                "loop bounds",
                "step value",
            ].contains(name) ? name : "\(nthArgument(i)) for \(name)"
            let got = got.contains(",") ? got : aOrAn(got)
            return "The \(name) should be \(aOrAn(type)), not \(got)."
        case let .forwardReference(name):
            return "The symbol '\(name)' was used before it was defined."
        case let .unexpectedArgument(for: name, max: max):
            if max == 0 {
                return "\(theSymbol(name)) does not expect any arguments."
            } else if max == 1 {
                return "\(theSymbol(name)) expects only a single argument."
            } else {
                return "\(theSymbol(name)) expects a maximum of \(max) arguments."
            }
        case let .missingArgument(for: name, index: i, type: type):
            let type = (type == ValueType.any.errorDescription) ? "" : " of type \(type)"
            return "\(theSymbol(name)) expects \(aOrAn(nthArgument(i > 0 ? i : -1)))\(type)."
        case let .unusedValue(type: type):
            return "\(aOrAn(type, capitalized: true)) value was not expected in this context."
        case let .assertionFailure(message):
            return formatMessage(message)
        case let .fileNotFound(for: name, at: url):
            guard let url = url else {
                return nil
            }
            if name == url.path {
                return "Check that the file exists and is located here."
            }
            return "ShapeScript expected to find the file at '\(url.path)'."
                + " Check that it exists and is located here."
        case let .fileTimedOut(for: _, at: url):
            return "ShapeScript was unable to download the file at '\(url.path)'."
                + " Check your network settings."
        case let .fileAccessRestricted(for: _, at: url):
            return "ShapeScript cannot read the file due to \(Self.osName) security restrictions."
                + " Please open the directory at '\(url.path)' to grant access."
        case let .fileParsingError(for: _, at: _, message: message):
            return formatMessage(message)
        case let .fileTypeMismatch(for: _, at: url, expected: type):
            guard let type = type else {
                return "The type of file at '\(url.path)' is not supported."
            }
            return "The file at '\(url.path)' is not \(aOrAn(type)) file."
        case .circularImport:
            return "Files cannot import themselves."
        case let .importError(error, for: _, in: _):
            if error.range == nil {
                return error.message
            }
            return error.hint
        }
    }

    var accessErrorURL: URL? {
        switch type {
        case let .fileAccessRestricted(for: _, at: url):
            return url
        case let .importError(error, _, _):
            return error.accessErrorURL
        case .typeMismatch,
             .forwardReference,
             .unexpectedArgument,
             .missingArgument,
             .unusedValue,
             .assertionFailure,
             .fileNotFound,
             .fileTimedOut,
             .fileTypeMismatch,
             .fileParsingError,
             .circularImport,
             .unknownSymbol,
             .unknownMember,
             .unknownFont:
            return nil
        }
    }

    static func wrap<T>(_ fn: @autoclosure () throws -> T, at range: SourceRange) throws -> T {
        do {
            return try fn()
        } catch let error as RuntimeErrorType {
            throw RuntimeError(error, at: range)
        }
    }
}

// MARK: Implementation

private struct EvaluationCancelled: Error {}

private func aOrAn(_ string: String, capitalized: Bool = false) -> String {
    guard let first = string.first else {
        return capitalized ? "An" : "an"
    }
    let beginsWithVowel = "AEIOUaeiou".contains(first)
    let prefix = beginsWithVowel ? "an" : "a"
    return "\(capitalized ? prefix.capitalized : prefix) \(string)"
}

private extension Array where Element == String {
    var typesDescription: String {
        var types = Set(self).sorted()
        if let index = types.firstIndex(of: "block") {
            types.append(types.remove(at: index))
        }
        switch types.count {
        case 1:
            return types[0]
        case 2:
            return "\(types[0]) or \(types[1])"
        default:
            return "\(types.dropLast().joined(separator: ", ")), or \(types.last!)"
        }
    }
}

extension RuntimeErrorType {
    static func typeMismatch(
        for symbol: String,
        expected: String,
        got: String
    ) -> RuntimeErrorType {
        .typeMismatch(for: symbol, index: -1, expected: expected, got: got)
    }

    static func typeMismatch(
        for symbol: String,
        index: Int = -1,
        expected types: [String],
        got: String
    ) -> RuntimeErrorType {
        let expected = types.typesDescription
        return .typeMismatch(for: symbol, index: index, expected: expected, got: got)
    }

    static func typeMismatch(
        for name: String,
        index: Int = -1,
        expected: ValueType,
        got: ValueType
    ) -> RuntimeErrorType {
        let typeDescription: String
        switch expected {
        case let .list(type):
            typeDescription = type.errorDescription
        case let .tuple(types) where !types.isEmpty:
            typeDescription = types[0].errorDescription
        default:
            typeDescription = expected.errorDescription
        }
        return typeMismatch(
            for: name,
            index: index,
            expected: typeDescription,
            got: got.errorDescription
        )
    }

    static func missingArgument(
        for symbol: String,
        type: String
    ) -> RuntimeErrorType {
        .missingArgument(for: symbol, index: 0, type: type)
    }

    static func missingArgument(
        for symbol: String,
        index: Int = 0,
        types: [String]
    ) -> RuntimeErrorType {
        let expected = types.typesDescription
        return .missingArgument(for: symbol, index: index, type: expected)
    }

    static func missingArgument(
        for name: String,
        index: Int = 0,
        type: ValueType
    ) -> RuntimeErrorType {
        let typeDescription: String
        switch type {
        case let .list(type):
            typeDescription = type.errorDescription
        case let .tuple(types) where !types.isEmpty:
            typeDescription = types[0].errorDescription
        default:
            typeDescription = type.errorDescription
        }
        return missingArgument(for: name, index: index, type: typeDescription)
    }

    static func unusedValue(type: ValueType) -> RuntimeErrorType {
        let typeDescription: String
        switch type {
        case let .list(type):
            typeDescription = type.errorDescription
        default:
            typeDescription = type.errorDescription
        }
        return unusedValue(type: typeDescription)
    }
}

private extension RuntimeError {
    static let alternatives: [String: [String]] = [
        "box": ["cube"],
        "rect": ["square"],
        "rectangle": ["square"],
        "triangle": ["polygon"],
        "ellipse": ["circle"],
        "elipse": ["circle"],
        "squircle": ["roundrect"],
        "rotate": ["orientation"],
        "rotation": ["orientation"],
        "orientation": ["rotate"],
        "translate": ["position"],
        "translation": ["position"],
        "position": ["translate", "bounds", "center"],
        "faces": ["polygons"],
        "triangles": ["polygons"],
        "vertices": ["points"],
        "scale": ["size"],
        "size": ["scale", "bounds"],
        "width": ["size", "x"],
        "height": ["size", "y"],
        "depth": ["size", "z"],
        "length": ["size", "count"],
        "magnitude": ["length"],
        "norm": ["length"],
        "radius": ["size"],
        "sine": ["sin"],
        "cosine": ["cos"],
        "x": ["width", "position"],
        "y": ["height", "position"],
        "z": ["depth", "position"],
        "option": ["define"],
        "subtract": ["difference"],
        "subtraction": ["difference"],
        "sweep": ["extrude"],
        "head": ["first"],
        "tail": ["last", "allButFirst"],
        "rest": ["allButFirst"],
        "rands": ["rnd", "seed"],
        "rand": ["rnd"],
        "random": ["rnd"],
        "noise": ["rnd"],
        "signum": ["sign"],
        "echo": ["print"],
    ].merging(ParserError.alternatives.mapValues { [$0] }) { $1 }

    static let osName: String = {
        #if os(macOS) || targetEnvironment(macCatalyst)
        return "macOS"
        #elseif os(tvOS)
        return "tvOS"
        #elseif os(iOS)
        return "iOS"
        #else
        return "system"
        #endif
    }()
}

extension Program {
    func evaluate(in context: EvaluationContext) throws {
        let oldSource = context.source
        let oldSourceIndex = context.sourceIndex
        context.source = source
        context.sourceIndex = nil
        defer {
            context.source = oldSource
            context.sourceIndex = oldSourceIndex
        }
        statements.gatherDefinitions(in: context)
        do {
            try statements.forEach { try $0.evaluate(in: context) }
        } catch is EvaluationCancelled {}
    }
}

private func evaluateParameters(
    _ parameters: [Expression],
    in context: EvaluationContext
) throws -> [(index: Int, value: Value)] {
    var values = [(Int, Value)]()
    loop: for (i, param) in parameters.enumerated() {
        guard i < parameters.count - 1, case let .identifier(name) = param.type,
              let symbol = context.symbol(for: name)
        else {
            try values.append((i, param.evaluate(in: context)))
            continue
        }
        switch symbol {
        case let .function((parameterType, _), fn) where parameterType != .void:
            let identifier = Identifier(name: name, range: param.range)
            let range = parameters[i + 1].range.lowerBound ..< parameters.last!.range.upperBound
            let param = Expression(type: .tuple(Array(parameters[(i + 1)...])), range: range)
            let arg = try evaluateParameter(param, as: parameterType, for: identifier, in: context)
            try RuntimeError.wrap({
                do {
                    switch try fn(arg, context) {
                    case let .tuple(tuple):
                        values += tuple.map { (i, $0) }
                    case let value:
                        values.append((i, value))
                    }
                } catch let RuntimeErrorType.unexpectedArgument(for: "", max: max) {
                    throw RuntimeErrorType.unexpectedArgument(for: name, max: max)
                } catch let RuntimeErrorType.missingArgument(for: "", index: index, type: type) {
                    throw RuntimeErrorType.missingArgument(for: name, index: index, type: type)
                }
            }(), at: range)
            break loop
        case let .block(type, fn) where type.childTypes != .void:
            let parameters = Array(parameters[(i + 1)...])
            let childContext = context.push(type)
            childContext.userSymbols.removeAll()
            let identifier = Identifier(name: name, range: param.range)
            try evaluateBlockParameters(
                parameters, for: identifier,
                type: type, in: context, childContext
            )
            try RuntimeError.wrap(values.append((i, fn(childContext))), at: param.range)
            break loop
        case .function, .block, .property, .constant, .option, .placeholder:
            try values.append((i, param.evaluate(in: context)))
        }
    }
    return values
}

private func evaluateBlockParameters(
    _ parameters: [Expression],
    for identifier: Identifier,
    type: BlockType,
    in context: EvaluationContext,
    _ childContext: EvaluationContext
) throws {
    guard let first = parameters.first, let last = parameters.last else {
        return
    }
    let range = first.range.lowerBound ..< last.range.upperBound
    let children: [(Int, Value)]
    if type.childTypes.subtypes.contains(.text) {
        let param = Expression(type: .tuple(parameters), range: range)
        do {
            children = try [(0, param.evaluate(as: .text, for: identifier.name, in: context))]
        } catch {
            children = try evaluateParameters(parameters, in: context)
        }
    } else {
        children = try evaluateParameters(parameters, in: context)
    }
    for (j, child) in children {
        do {
            try childContext.addValue(child)
        } catch {
            var types = type.childTypes.subtypes.map { $0.errorDescription }
            if j == 0 {
                types.append("block")
            }
            throw RuntimeError(
                .typeMismatch(
                    for: identifier.name,
                    index: j > 0 ? j : -1,
                    expected: types,
                    got: child.type.errorDescription
                ),
                at: j < parameters.count ? parameters[j].range : range
            )
        }
    }
}

// TODO: find a better way to encapsulate this
private func evaluateParameter(_ parameter: Expression?,
                               as type: ValueType,
                               for identifier: Identifier,
                               in context: EvaluationContext) throws -> Value
{
    let (name, range) = (identifier.name, identifier.range)
    guard let parameter = parameter else {
        if type == .void {
            return .void
        }
        throw RuntimeError(
            .missingArgument(for: name, type: type),
            at: range.upperBound ..< range.upperBound
        )
    }
    return try parameter.evaluate(as: type, for: identifier.name, in: context)
}

extension Definition {
    func evaluate(in context: EvaluationContext) throws -> Symbol {
        switch type {
        case let .expression(expression):
            let context = context.pushDefinition()
            let value = try expression.evaluate(in: context)
            switch value {
            case .tuple:
                return .constant(value)
            default:
                // Wrap all definitions as a single-value tuple
                // so that ordinal access and looping will work
                return .constant(.tuple([value]))
            }
        case let .function(names, block):
            let declarationContext = context
            let returnType: ValueType
            var params = Dictionary(uniqueKeysWithValues: names.map {
                ($0.name, ValueType.any)
            })
            do {
                let context = context.push(.custom(.all, [:], .any, .any))
                block.inferTypes(for: &params, in: context)
                for (name, type) in params {
                    context.define(name, as: .placeholder(type))
                }
                returnType = try block.staticType(in: context)
            }
            let paramTypes = names.map { params[$0.name] ?? .any }
            return .function(.tuple(paramTypes), returnType) { value, context in
                do {
                    let oldChildren = context.children
                    let oldChildTypes = context.childTypes
                    let oldSymbols = context.userSymbols
                    let oldSource = context.source
                    let oldBaseURL = context.baseURL
                    context.children = []
                    context.childTypes = .any
                    context.source = declarationContext.source
                    context.baseURL = declarationContext.baseURL
                    context.userSymbols = declarationContext.userSymbols
                    context.stackDepth += 1
                    defer {
                        context.children = oldChildren
                        context.childTypes = oldChildTypes
                        context.source = oldSource
                        context.baseURL = oldBaseURL
                        context.userSymbols = oldSymbols
                        context.stackDepth -= 1
                    }
                    if context.stackDepth > 25 {
                        throw RuntimeErrorType.assertionFailure("Too much recursion")
                    }
                    let values: [Value]
                    if case let .tuple(_values) = value {
                        values = _values
                    } else {
                        values = [value]
                    }
                    assert(values.count == names.count)
                    for (identifier, value) in zip(names, values) {
                        context.define(identifier.name, as: .constant(value))
                    }
                    try block.evaluate(in: context)
                    if context.children.count == 1 {
                        return context.children[0]
                    }
                    return .tuple(context.children)
                } catch {
                    if declarationContext.baseURL == context.baseURL {
                        throw error
                    }
                    throw RuntimeErrorType.importError(
                        ProgramError(error),
                        for: declarationContext.baseURL,
                        in: declarationContext.source
                    )
                }
            }
        case let .block(block):
            var options: Options? = [:]
            let returnType: ValueType
            do {
                let context = context.push(.custom(.definition, [:], .void, .any))
                returnType = try block.staticType(in: context, options: &options)
            } catch var error as RuntimeError {
                if case let .unknownSymbol(name, options: options) = error.type {
                    // TODO: find a less hacky way to limit the scope of option keyword
                    error = RuntimeError(
                        .unknownSymbol(name, options: options + ["option"]),
                        at: error.range
                    )
                }
                throw error
            }
            let source = context.source
            let sourceIndex = context.sourceIndex
            let baseURL = context.baseURL
            return .block(.custom(.user, options ?? [:], .void, returnType)) { _context in
                do {
                    let context = context.pushDefinition()
                    context.stackDepth = _context.stackDepth + 1
                    if context.stackDepth > 25 {
                        throw RuntimeErrorType.assertionFailure("Too much recursion")
                    }
                    for (name, symbol) in _context.userSymbols {
                        switch symbol {
                        case .option:
                            // Only options are copied from call scope
                            context.define(name, as: symbol)
                        case .block, .function, .property, .constant, .placeholder:
                            break
                        }
                    }
                    context.children += _context.children
                    context.name = _context.name
                    context.material = _context.material
                    context.font = _context.font
                    context.transform = _context.transform
                    context.opacity = _context.opacity
                    context.detail = _context.detail
                    context.smoothing = _context.smoothing
                    context.baseURL = baseURL
                    context.source = source
                    context.sourceIndex = sourceIndex
                    block.statements.gatherDefinitions(in: context)
                    for statement in block.statements {
                        if case let .option(identifier, expression) = statement.type {
                            if case .option? = context.symbol(for: identifier.name) {
                                // Ignore default
                            } else {
                                try context.define(
                                    identifier.name,
                                    as: .constant(expression.evaluate(in: context))
                                )
                            }
                        } else {
                            try statement.evaluate(in: context)
                        }
                    }
                    let children = context.children
                    if children.count == 1, let value = children.first {
                        switch value {
                        case let .path(path):
                            guard context.name.isEmpty else {
                                return .mesh(Geometry(
                                    type: .path(path),
                                    name: context.name,
                                    transform: context.transform,
                                    material: .default,
                                    smoothing: nil,
                                    children: [],
                                    sourceLocation: context.sourceLocation
                                ))
                            }
                            return .path(path.transformed(by: context.transform))
                        case let .mesh(geometry):
                            return .mesh(Geometry(
                                type: geometry.type,
                                name: context.name,
                                transform: geometry.transform * context.transform,
                                material: geometry.material,
                                smoothing: geometry.smoothing,
                                children: geometry.children,
                                sourceLocation: context.sourceLocation,
                                debug: geometry.debug
                            ))
                        case let .polygon(polygon):
                            return .polygon(polygon.transformed(by: context.transform))
                        default:
                            if context.name.isEmpty {
                                return value
                            }
                            throw RuntimeErrorType.assertionFailure(
                                "Blocks that return \(aOrAn(value.errorDescription)) " +
                                    "value cannot be assigned a name"
                            )
                        }
                    } else if context.name.isEmpty,
                              // Manage backwards compatibility for blocks that return
                              // multiple meshes to be used inside difference block
                              !children.contains(where: { $0.type == .mesh }) ||
                              children.contains(where: { ![.mesh, .path].contains($0.type) })
                    {
                        return .tuple(children.map {
                            switch $0 {
                            case let .path(path):
                                return .path(path.transformed(by: context.transform))
                            case let .mesh(geometry):
                                return .mesh(geometry.transformed(by: context.transform))
                            default:
                                return $0
                            }
                        })
                    }
                    return try .mesh(Geometry(
                        type: .group,
                        name: context.name,
                        transform: context.transform,
                        material: .default,
                        smoothing: context.smoothing,
                        children: children.map {
                            switch $0 {
                            case let .path(path):
                                return Geometry(
                                    type: .path(path),
                                    name: nil,
                                    transform: .identity,
                                    material: .default,
                                    smoothing: nil,
                                    children: [],
                                    sourceLocation: context.sourceLocation
                                )
                            case let .mesh(geometry):
                                return geometry
                            default:
                                throw RuntimeErrorType.assertionFailure(
                                    "Blocks that return \(aOrAn($0.errorDescription)) " +
                                        "value cannot be assigned a name"
                                )
                            }
                        },
                        sourceLocation: context.sourceLocation
                    ))
                } catch var error {
                    if let e = error as? RuntimeError,
                       case let .unknownSymbol(name, options: options) = e.type
                    {
                        // TODO: find a less hacky way to limit the scope of option keyword
                        error = RuntimeError(
                            .unknownSymbol(name, options: options + ["option"]),
                            at: e.range
                        )
                    }
                    if baseURL == _context.baseURL {
                        throw error
                    }
                    throw RuntimeErrorType.importError(
                        ProgramError(error),
                        for: baseURL,
                        in: source
                    )
                }
            }
        }
    }
}

extension EvaluationContext {
    func addValue(_ value: Value) throws {
        if let value = try value.as(childTypes, in: self) {
            switch value {
            case let .mesh(m):
                children.append(.mesh(m.transformed(by: childTransform)))
            case let .vector(v):
                children.append(.vector(v.transformed(by: childTransform)))
            case let .point(p):
                children.append(.point(p.transformed(by: childTransform)))
            case let .polygon(p):
                children.append(.polygon(p
                        .transformed(by: childTransform)
                        .with(material: material)
                ))
            case let .path(path):
                children.append(.path(path.transformed(by: childTransform)))
            case _ where childTypes.subtypes.contains(.text):
                children.append(.text(TextValue(
                    string: value.stringValue,
                    font: self.value(for: "font")?.stringValue ?? font,
                    color: material.color,
                    linespacing: self.value(for: "linespacing")?.doubleValue
                )))
            case .void:
                break
            default:
                children.append(value)
            }
        } else if case let .tuple(values) = value {
            try values.forEach(addValue)
        } else {
            throw RuntimeErrorType.unusedValue(type: value.type)
        }
    }
}

extension Block {
    func evaluate(in context: EvaluationContext) throws {
        statements.gatherDefinitions(in: context)
        try statements.forEach { try $0.evaluate(in: context) }
    }
}

extension Statement {
    func evaluate(in context: EvaluationContext) throws {
        let sourceIndex = context.sourceIndex
        context.sourceIndex = range.lowerBound
        defer {
            context.sourceIndex = sourceIndex
        }
        switch type {
        case let .command(identifier, parameter):
            var name = identifier.name
            if let type = context.options[name] ?? {
                if name == "colour", let type = context.options["color"] {
                    name = "color"
                    return type
                }
                return nil
            }() {
                return try context.define(name, as: .option(
                    evaluateParameter(parameter,
                                      as: type,
                                      for: identifier,
                                      in: context)
                ))
            }
            guard let symbol = context.symbol(for: name) else {
                throw RuntimeError(
                    .unknownSymbol(name, options: context.commandSymbols),
                    at: identifier.range
                )
            }
            switch symbol {
            case let .function((parameterType, _), fn):
                let argument = try evaluateParameter(parameter,
                                                     as: parameterType,
                                                     for: identifier,
                                                     in: context)
                try RuntimeError.wrap(context.addValue(fn(argument, context)), at: range)
            case let .property(type, setter, getter):
                if parameter == nil {
                    let value = try RuntimeError.wrap(getter(context), at: range)
                    do {
                        return try RuntimeError.wrap(context.addValue(value), at: range)
                    } catch let error as RuntimeError {
                        guard case .unusedValue = error.type else {
                            throw error
                        }
                    }
                }
                let argument = try evaluateParameter(parameter,
                                                     as: type,
                                                     for: identifier,
                                                     in: context)
                try RuntimeError.wrap(setter(argument, context), at: range)
            case let .block(type, fn):
                if let parameter = parameter {
                    let parameters: [Expression]
                    if case let .tuple(expressions) = parameter.type {
                        parameters = expressions
                    } else {
                        parameters = [parameter]
                    }
                    let childContext = context.push(type)
                    childContext.userSymbols.removeAll()
                    try evaluateBlockParameters(
                        parameters, for: identifier, type: type,
                        in: context, childContext
                    )
                    try RuntimeError.wrap(context.addValue(fn(childContext)), at: range)
                } else if !type.childTypes.isOptional {
                    throw RuntimeError(.missingArgument(
                        for: name,
                        types: type.childTypes.subtypes.map { $0.errorDescription } + ["block"]
                    ), at: range.upperBound ..< range.upperBound)
                } else {
                    let childContext = context.push(type)
                    childContext.userSymbols.removeAll()
                    try RuntimeError.wrap(context.addValue(fn(childContext)), at: range)
                }
            case let .constant(value), let .option(value):
                var value = value
                if let parameter = parameter {
                    value = try .tuple([value, parameter.evaluate(in: context)])
                }
                try RuntimeError.wrap(context.addValue(value), at: range)
            case .placeholder:
                throw RuntimeError(.forwardReference(name), at: identifier.range)
            }
        case let .expression(expression):
            try RuntimeError.wrap(context.addValue(expression.evaluate(in: context)), at: range)
        case let .define(identifier, definition):
            switch definition.type {
            case let .function(names, _):
                // In case of recursion
                let parameterType: ValueType = names.count == 1 ?
                    .any : .tuple(names.map { _ in .any })
                context.define(identifier.name, as: .function((parameterType, .any)) { _, _ in .void })
            case .block:
                // In case of recursion
                context.define(identifier.name, as: .block(.custom([:], [:], .void, .any)) { _ in .void })
            case .expression:
                break
            }
            try context.define(identifier.name, as: definition.evaluate(in: context))
        case .option:
            throw RuntimeError(.unknownSymbol("option", options: []), at: range)
        case let .forloop(identifier, in: expression, block):
            let value = try expression.evaluate(in: context)
            // TODO: evaluate(as: .sequence, ...) should be enough to make the below check
            // unneccessary, however because <type> can always be cast to .list(<type>)
            // it isn't. Need to find a static solution for this (or abandon this check)
            guard let sequence = value.sequenceValue else {
                throw RuntimeError(
                    .typeMismatch(
                        for: "loop bounds",
                        expected: .sequence,
                        got: value.type
                    ),
                    at: expression.range
                )
            }
            for value in sequence {
                if context.isCancelled() {
                    throw EvaluationCancelled()
                }
                try context.pushScope { context in
                    if let name = identifier?.name {
                        context.define(name, as: .constant(value))
                    }
                    try block.evaluate(in: context)
                }
            }
        case let .ifelse(condition, body, else: elseBody):
            let value = try condition.evaluate(
                as: .boolean,
                for: "if condition",
                in: context
            )
            try context.pushScope { context in
                if value.boolValue {
                    try body.evaluate(in: context)
                } else if let elseBody = elseBody {
                    try elseBody.evaluate(in: context)
                }
            }
        case let .import(expression):
            let pathValue = try expression.evaluate(
                as: .string,
                for: Keyword.import.rawValue,
                in: context
            )
            let path = pathValue.stringValue
            context.sourceIndex = expression.range.lowerBound
            try RuntimeError.wrap(context.importFile(at: path), at: expression.range)
        }
    }
}

extension Expression {
    func evaluate(in context: EvaluationContext) throws -> Value {
        switch type {
        case let .number(number):
            return .number(number)
        case let .string(string):
            return .string(string)
        case let .color(color):
            return .color(color)
        case let .identifier(name):
            guard let symbol = context.symbol(for: name) else {
                throw RuntimeError(
                    .unknownSymbol(name, options: context.expressionSymbols),
                    at: range
                )
            }
            switch symbol {
            case let .function((.void, _), fn):
                return try RuntimeError.wrap(fn(.void, context), at: range)
            case let .function((parameterType, _), _):
                // Functions with parameters can't be called without arguments
                throw RuntimeError(.missingArgument(
                    for: name,
                    type: parameterType
                ), at: range.upperBound ..< range.upperBound)
            case let .property(_, _, getter):
                return try RuntimeError.wrap(getter(context), at: range)
            case let .block(type, fn):
                guard type.childTypes.isOptional else {
                    // Blocks that require children can't be called without arguments
                    throw RuntimeError(.missingArgument(
                        for: name,
                        types: type.childTypes.subtypes.map { $0.errorDescription } + ["block"]
                    ), at: range.upperBound ..< range.upperBound)
                }
                return try RuntimeError.wrap(fn(context.push(type)), at: range)
            case let .constant(value), let .option(value):
                return value
            case .placeholder:
                throw RuntimeError(.forwardReference(name), at: range)
            }
        case let .block(identifier, block):
            let (name, range) = (identifier.name, identifier.range)
            guard let symbol = context.symbol(for: name) else {
                throw RuntimeError(
                    .unknownSymbol(name, options: context.expressionSymbols),
                    at: range
                )
            }
            switch symbol {
            case let .block(type, fn):
                if context.isCancelled() {
                    throw EvaluationCancelled()
                }
                let newContext = context.push(type)
                defer {
                    // TODO: find better solution for this
                    context.background = newContext.background
                }
                try newContext.pushScope { newContext in
                    block.statements.gatherDefinitions(in: newContext)
                    for statement in block.statements {
                        try statement.evaluate(in: newContext)
                    }
                }
                return try RuntimeError.wrap(fn(newContext), at: range)
            case let .constant(value), let .option(value):
                guard let value = value.as(.list(.path)) ?? value.as(.list(.mesh)),
                      case let .tuple(values) = value
                else {
                    fallthrough
                }
                let sourceIndex = context.sourceIndex
                let newContext = context.push(.custom(.transform, [:], .mesh, value.type))
                block.statements.gatherDefinitions(in: newContext)
                for statement in block.statements {
                    try statement.evaluate(in: newContext)
                }
                newContext.sourceIndex = sourceIndex
                if values.first?.type == .path {
                    return .tuple(values.map {
                        .path(($0.value as! Path).transformed(by: newContext.transform))
                    })
                }
                return .tuple(values.map {
                    .mesh(($0.value as! Geometry).transformed(by: newContext.transform))
                })
            case .property, .function((.void, _), _):
                throw RuntimeError(
                    .unexpectedArgument(for: name, max: 0),
                    at: block.range
                )
            case let .function((type, _), _):
                throw RuntimeError(.typeMismatch(
                    for: name,
                    expected: type.errorDescription,
                    got: "block"
                ), at: block.range)
            case .placeholder:
                throw RuntimeError(.forwardReference(name), at: identifier.range)
            }
        case let .tuple(expressions):
            guard let identifier = expressions.first,
                  case let .identifier(name) = identifier.type,
                  let type = context.options[name],
                  expressions.count > 1
            else {
                return try .tuple(evaluateParameters(expressions, in: context).map { $0.value })
            }
            let params = Array(expressions.dropFirst())
            let param = Expression(
                type: .tuple(params),
                range: params[0].range.lowerBound ..< params.last!.range.upperBound
            )
            let value = try param.evaluate(as: type, for: name, in: context)
            context.define(name, as: .option(value))
            return .void
        case let .prefix(op, expression):
            let value = try expression.evaluate(
                as: .union([.number, .list(.number)]),
                for: String(op.rawValue),
                in: context
            )
            switch op {
            case .minus:
                switch value {
                case let .tuple(values):
                    return .tuple(values.map { .number(-$0.doubleValue) })
                case let .number(value):
                    return .number(-value)
                default:
                    assertionFailure()
                    return value
                }
            case .plus:
                return value
            }
        case let .infix(lhs, .to, rhs):
            let start = try lhs.evaluate(as: .number, for: "start value", in: context)
            let end = try rhs.evaluate(as: .number, for: "end value", in: context)
            return .range(RangeValue(from: start.doubleValue, to: end.doubleValue))
        case let .infix(lhs, .step, rhs):
            let rangeValue = try lhs.evaluate(as: .range, for: "range value", in: context)
            let stepValue = try rhs.evaluate(as: .number, for: "step value", in: context)
            let range = rangeValue.value as! RangeValue
            guard let value = RangeValue(
                from: range.start,
                to: range.end,
                step: stepValue.doubleValue
            ) else {
                throw RuntimeError(
                    .assertionFailure("Step value must be nonzero"),
                    at: rhs.range
                )
            }
            return .range(value)
        case let .infix(lhs, .equal, rhs):
            let lhs = try lhs.evaluate(in: context)
            let rhs = try rhs.evaluate(in: context)
            return .boolean(lhs.value == rhs.value)
        case let .infix(lhs, .unequal, rhs):
            let lhs = try lhs.evaluate(in: context)
            let rhs = try rhs.evaluate(in: context)
            return .boolean(lhs.value != rhs.value)
        case let .infix(lhs, .and, rhs):
            return try .boolean(lhs.evaluate(
                as: .boolean,
                for: InfixOperator.and.rawValue,
                index: 0,
                in: context
            ).boolValue && rhs.evaluate(
                as: .boolean,
                for: InfixOperator.and.rawValue,
                index: 1,
                in: context
            ).boolValue)
        case let .infix(lhs, .or, rhs):
            return try .boolean(lhs.evaluate(
                as: .boolean,
                for: InfixOperator.or.rawValue,
                index: 0,
                in: context
            ).boolValue || rhs.evaluate(
                as: .boolean,
                for: InfixOperator.or.rawValue,
                index: 1,
                in: context
            ).boolValue)
        case let .infix(lhs, op, rhs):
            func doubleValue(_ exp: Expression, index: Int = 0) throws -> Double {
                try exp.evaluate(
                    as: .number,
                    for: String(op.rawValue),
                    index: index,
                    in: context
                ).doubleValue
            }
            func tupleValue(_ exp: Expression, index: Int = 0) throws -> Value {
                try exp.evaluate(
                    as: .union([.number, .list(.number)]),
                    for: String(op.rawValue),
                    index: index,
                    in: context
                )
            }
            func apply(
                _ lhs: Value,
                _ rhs: Value,
                _ fn: (Double, Double) -> Double
            ) -> Value {
                switch (lhs, rhs) {
                case let (.number(lhs), .number(rhs)):
                    return .number(fn(lhs, rhs))
                case let (.tuple(lhs), _) where lhs.count == 1:
                    return apply(lhs[0], rhs, fn)
                case let (_, .tuple(rhs)) where rhs.count == 1:
                    return apply(lhs, rhs[0], fn)
                case let (.tuple(lhs), .tuple(rhs)):
                    return .tuple(zip(lhs, rhs).map { apply($0, $1, fn) })
                case let (.tuple(lhs), .number):
                    return .tuple(lhs.map { apply($0, rhs, fn) })
                case let (.number, .tuple(rhs)):
                    return .tuple(rhs.map { apply(lhs, $0, fn) })
                default:
                    assertionFailure()
                    return .number(0)
                }
            }
            func tupleApply(
                _ fn: (Double, Double) -> Double,
                widen: Bool
            ) throws -> Value {
                let lhs = try tupleValue(lhs)
                let rhs = try tupleValue(rhs, index: 1)
                switch (apply(lhs, rhs, fn), lhs) {
                case let (.tuple(values), .tuple(lhs)) where widen:
                    return .tuple(values + lhs[values.count...])
                case let (value, _):
                    return value
                }
            }
            switch op {
            case .minus:
                return try tupleApply(-, widen: true)
            case .plus:
                return try tupleApply(+, widen: true)
            case .times:
                return try tupleApply(*, widen: false)
            case .divide:
                return try tupleApply(/, widen: false)
            case .modulo:
                return try tupleApply(fmod, widen: false)
            case .lt:
                return try .boolean(doubleValue(lhs) < doubleValue(rhs, index: 1))
            case .gt:
                return try .boolean(doubleValue(lhs) > doubleValue(rhs, index: 1))
            case .lte:
                return try .boolean(doubleValue(lhs) <= doubleValue(rhs, index: 1))
            case .gte:
                return try .boolean(doubleValue(lhs) >= doubleValue(rhs, index: 1))
            case .to, .step, .equal, .unequal, .and, .or:
                throw RuntimeErrorType
                    .assertionFailure("\(op.rawValue) should be handled by earlier case")
            }
        case let .member(expression, member):
            var value = try expression.evaluate(in: context)
            if let memberValue = value[member.name, context.isCancelled] {
                assert(value.members.contains(member.name),
                       "\(value.errorDescription) does not have member '\(member.name)'")
                return memberValue
            }
            // TODO: find less hacky way to do this unwrap
            if case let .tuple(values) = value, values.count == 1 {
                value = values[0]
            }
            assert(!value.members.contains(member.name),
                   "\(value.errorDescription) should have member '\(member.name)'")
            throw RuntimeError(.unknownMember(
                member.name,
                of: value.errorDescription,
                options: value.members
            ), at: member.range)
        }
    }

    func evaluate(as type: ValueType, for name: String, index: Int = -1, in context: EvaluationContext) throws -> Value {
        let value: Value, values: [(index: Int, value: Value)]
        do {
            if case let .tuple(expressions) = self.type {
                values = try evaluateParameters(expressions, in: context)
                if case let .tuple(types) = type, types.count == values.count {
                    return try .tuple(zip(values, types).map {
                        do {
                            if let value = try $0.value.as($1, in: context) {
                                return value
                            }
                            throw RuntimeErrorType.typeMismatch(
                                for: name,
                                index: $0.index,
                                expected: $1,
                                got: $0.value.type
                            )
                        } catch let error as RuntimeErrorType {
                            throw RuntimeError(error, at: expressions[$0.index].range)
                        }
                    })
                }
                value = .tuple(values.map { $0.value })
            } else {
                value = try evaluate(in: context)
                values = []
            }
        } catch var error as RuntimeError {
            if case .unknownSymbol(let name, var options) = error.type {
                options += InfixOperator.allCases.map { $0.rawValue }
                error = RuntimeError(.unknownSymbol(name, options: options), at: error.range)
            }
            throw error
        }
        if let value = try RuntimeError.wrap(value.as(type, in: context), at: range) {
            return value
        }
        switch (self.type, type) {
        case let (.tuple(expressions), .tuple(types)):
            if values.count > types.count {
                throw RuntimeError(.unexpectedArgument(
                    for: name,
                    max: types.count
                ), at: expressions[values[types.count].index].range)
            }
            let upperBound = expressions.last?.range.upperBound ?? range.upperBound
            throw RuntimeError(.missingArgument(
                for: name,
                index: values.count,
                type: types[values.count]
            ), at: upperBound ..< upperBound)
        case let (.tuple(expressions), .list(type)):
            return try .tuple(expressions.enumerated().map {
                try $1.evaluate(as: type, for: name, index: $0, in: context)
            })
        case let (.tuple(expressions), _) where expressions.count == 1:
            return try expressions[0].evaluate(as: type, for: name, in: context)
        case let (.tuple(expressions), type) where
            ValueType.color.isSubtype(of: type) && expressions.count > 4:
            throw RuntimeError(
                .unexpectedArgument(for: name, max: 4),
                at: expressions[4].range
            )
        case let (.tuple(expressions), type) where
            (ValueType.vector.isSubtype(of: type) ||
                ValueType.size.isSubtype(of: type) ||
                ValueType.rotation.isSubtype(of: type)) && expressions.count > 3:
            throw RuntimeError(
                .unexpectedArgument(for: name, max: 3),
                at: expressions[3].range
            )
        case let (.tuple(expressions), type) where ValueType.rotation.isSubtype(of: type):
            if let index = values.firstIndex(where: {
                !$0.value.isConvertible(to: .halfturns)
            }) {
                throw RuntimeError(.typeMismatch(
                    for: name,
                    index: index,
                    expected: .halfturns,
                    got: values[index].value.type
                ), at: expressions[index].range)
            }
            throw RuntimeError(.typeMismatch(
                for: name,
                index: index,
                expected: type,
                got: value.type
            ), at: range)
        case let (.tuple(expressions), type) where expressions.count > 1:
            var value = value
            if InfixOperator(rawValue: name) == nil,
               PrefixOperator(rawValue: name) == nil
            {
                value = try expressions[0].evaluate(in: context)
                if value.isConvertible(to: type) {
                    var i = 0
                    var values = [value]
                    while value.isConvertible(to: type), i < expressions.count - 1 {
                        i += 1
                        try values.append(expressions[i].evaluate(in: context))
                        value = .tuple(values)
                    }
                    throw RuntimeError(
                        .unexpectedArgument(for: name, max: i),
                        at: expressions[i].range
                    )
                }
            }
            throw RuntimeError(.typeMismatch(
                for: name,
                index: index,
                expected: type,
                got: value.type
            ), at: range)
        case let (_, .tuple(types)) where types.count > 1 && !types[1].isOptional:
            throw RuntimeError(
                .missingArgument(for: name, index: 1, type: types[1]),
                at: range.upperBound ..< range.upperBound
            )
        case (_, .void):
            throw RuntimeError(.unexpectedArgument(for: name, max: 0), at: range)
        default:
            throw RuntimeError(.typeMismatch(
                for: name,
                index: index,
                expected: type,
                got: value.type
            ), at: range)
        }
    }
}
