
import maybe.*;
import parsing.combinators.wrapper.*;
import clay.common.*;
import clay.v0_0.lexer.*;
import clay.v0_0.ast.*;
import clay.diagnostics.*;



//
// parser input
//

record ParserInput(
    tokens : SourceTokens,
    current : SizeT,
    maxCurrent : SizeT,
);

overload ParserInput(tokens : SourceTokens) =
    ParserInput(tokens, SizeT(0), SizeT(0));

overload iterator(x:ParserInput) = x;

overload hasNext?(x:ParserInput) =
    (x.current < size(x.tokens.vector));

overload next(x:ParserInput) {
    ref token = x.tokens.vector[x.current];
    x.current += 1;
    return ref token;
}

overload assign(ref dest:ParserInput, ref src:ParserInput) {
    if (dest.tokens == src.tokens) {
        var destMax = max(dest.maxCurrent, dest.current);
        var srcMax = max(src.maxCurrent, src.current);
        dest.maxCurrent = max(destMax, srcMax);
        dest.current = src.current;
    }
    else {
        dest.tokens = src.tokens;
        dest.current = src.current;
        dest.maxCurrent = src.maxCurrent;
    }
}



//
// combinator specialization
//

private var combinators = Combinators[ParserInput]();

private var Parser? = combinators.Parser?;
private var Parsers? = combinators.Parsers?;
private var ParseResult = combinators.ParseResult;

private var nextToken = combinators.nextToken;

private var condition = combinators.condition;
private var literal = combinators.literal;
private var literalString = combinators.literalString;
private var optional = combinators.optional;
private var choice = combinators.choice;
private var sequence = combinators.sequence;
private var sequenceAs = combinators.sequenceAs;
private var modify = combinators.modify;
private var repeated = combinators.repeated;
private var repeatedAs = combinators.repeatedAs;
private var zeroOrMore = combinators.zeroOrMore;
private var oneOrMore = combinators.oneOrMore;
private var zeroOrMoreAs = combinators.zeroOrMoreAs;
private var oneOrMoreAs = combinators.oneOrMoreAs;
private var separatedList = combinators.separatedList;
private var optSeparatedList = combinators.optSeparatedList;
private var separatedListStrict = combinators.separatedListStrict;

private commaList(forward parser) = separatedList(punc(#","), parser);
private optCommaList(forward parser) = optSeparatedList(punc(#","), parser);

private commaListStrict(forward parser) =
    separatedListStrict(punc(#","), parser);

private optCommaListStrict(forward parser) =
    optSeparatedListStrict(punc(#","), parser);



//
// variadicList combinator
//

private commaAndItem(item) = modify(x => move(x.1), sequence(punc(#","), item));

[Item, VariadicItem | Parsers?(Item, VariadicItem)]
private variadicList(item:Item, variadicItem:VariadicItem) {
    alias T = ParseResult(Item);
    return choice(
        modify(
            x => VariadicList(move(x.0), move(x.1)),
            sequence(
                commaListStrict(item), optional(commaAndItem(variadicItem))
            ),
        ),
        modify(
            x => VariadicList(Vector[T](), move(x)),
            optional(variadicItem),
        ),
    );
}



//
// bounds combinator
//

[Parser]
private bounds(parser:Parser) {
    return input => {
        alias T = ParseResult(Parser);
        var start = input.current;
        return maybe(parser(input),
            x -> {
                x.tokens = TokenRange(start, input.current);
                x.mainToken = start;
                return Maybe(move(x));
            },
            () => nothing(T),
        );
    };
}



//
// keywords
//

private keyword(s) {
    var i = keywordIndex(s);
    assert(i >= 0, "invalid keyword");
    var pred = (x => ((x.kind == KEYWORD) and (x.subKind == i)));
    return modify(x => [], condition(pred));
}

private var kw_public = keyword("public");
private var kw_private = keyword("private");
private var kw_import = keyword("import");
private var kw_as = keyword("as");
private var kw_record = keyword("record");
private var kw_variant = keyword("variant");
private var kw_instance = keyword("instance");
private var kw_procedure = keyword("procedure");
private var kw_overload = keyword("overload");
private var kw_external = keyword("external");
private var kw_alias = keyword("alias");
private var kw_static = keyword("static");
private var kw_callbyname = keyword("callbyname");
private var kw_lvalue = keyword("lvalue");
private var kw_rvalue = keyword("rvalue");
private var kw_inline = keyword("inline");
private var kw_enum = keyword("enum");
private var kw_var = keyword("var");
private var kw_ref = keyword("ref");
private var kw_forward = keyword("forward");
private var kw_and = keyword("and");
private var kw_or = keyword("or");
private var kw_not = keyword("not");
private var kw_new = keyword("new");
private var kw_if = keyword("if");
private var kw_else = keyword("else");
private var kw_goto = keyword("goto");
private var kw_return = keyword("return");
private var kw_while = keyword("while");
private var kw_switch = keyword("switch");
private var kw_case = keyword("case");
private var kw_default = keyword("default");
private var kw_break = keyword("break");
private var kw_continue = keyword("continue");
private var kw_for = keyword("for");
private var kw_in = keyword("in");
private var kw_true = keyword("true");
private var kw_false = keyword("false");
private var kw_try = keyword("try");
private var kw_catch = keyword("catch");
private var kw_throw = keyword("throw");
private var kw_FILE = keyword("__FILE__");
private var kw_LINE = keyword("__LINE__");
private var kw_COLUMN = keyword("__COLUMN__");



//
// punctuations
//

private punctuationParser(Ident) {
    var i = punctuationIndex(StaticName(Ident));
    assert(i >= 0, "invalid punctuation");
    var pred = (x => ((x.kind == PUNCTUATION) and (x.subKind == i)));
    return modify(x => [], condition(pred));
}

private var punctuationParserTable[Ident] = punctuationParser(Ident);

[Ident]
private punc(static Ident) = punctuationParserTable[Ident];



//
// token parser
//

private token(tokenKind) = condition(x => (x.kind == tokenKind));

private tokenData(tokenKind) {
    var parser = token(tokenKind);
    return input => {
        ref data = input.tokens.file.data;
        return maybe(parser(input),
            x -> Maybe(sliced(data, x.range.begin, x.range.end)),
            () -> nothing(Type(sliced(data, SizeT(0), SizeT(0)))),
        );
    };
}



//
// identifier
//

private var identifier = bounds(modify(Identifier, tokenData(IDENTIFIER)));
private var identifierList = commaList(identifier);



//
// exprParser combinator
//

private exprParser(forward modifier, forward parser) = modify(
    x => Expr(move(x)),
    bounds(modify(modifier, parser)),
);



//
// literals
//

private var boolTrue  = modify(x => true,  kw_true);
private var boolFalse = modify(x => false, kw_false);

private var boolLiteral = exprParser(
    BoolLiteral,
    choice(boolTrue, boolFalse),
);

private var identStr = modify(String, tokenData(IDENTIFIER));

private var intLiteral = exprParser(
    x => IntLiteral(String(x.0), x.1),
    sequence(tokenData(INT_LITERAL), optional(identStr)),
);

private var floatLiteral = exprParser(
    x => FloatLiteral(String(x.0), x.1),
    sequence(tokenData(FLOAT_LITERAL), optional(identStr)),
);

private var charLiteral = exprParser(
    x => CharLiteral(String(x)),
    tokenData(CHAR_LITERAL),
);

private var stringLiteral = exprParser(
    x => StringLiteral(String(x)),
    tokenData(STRING_LITERAL),
);

private var identifierLiteral = exprParser(
    x => IdentifierLiteral(String(x.1)),
    sequence(punc(#"#"), choice(
        tokenData(IDENTIFIER), tokenData(STRING_LITERAL)
    )),
);

private var fileLiteral = exprParser(x => FILELiteral(), kw_FILE);
private var lineLiteral = exprParser(x => LINELiteral(), kw_LINE);
private var columnLiteral = exprParser(x => COLUMNLiteral(), kw_COLUMN);

private var literalExpr = choice(
    boolLiteral, intLiteral, floatLiteral,
    charLiteral, stringLiteral, identifierLiteral,
    fileLiteral, lineLiteral, columnLiteral
);



//
// atomic expr
//

private var arrayExpr = exprParser(
    x => ArrayExpr(move(x.1)),
    sequence(punc(#"["), exprList, punc(#"]")),
);

private var tupleExpr = exprParser(
    x => TupleExpr(move(x.1)),
    sequence(punc(#"("), optExprList, punc(#")")),
);

private var nameRef = exprParser(
    x => NameRef(move(x)),
    identifier,
);

private var atomicExpr = choice(arrayExpr, tupleExpr, nameRef, literalExpr);



//
// setBase, foldTail
//

private exprTokens(x) = ref fieldRef(*x, #tokens);

private setBase2(root, field, base) {
    fieldRef(root, field) = base;
    root.tokens.begin = exprTokens(base).begin;
}
private setBase(x, y) { assert(false, "baseless expression!"); }
overload setBase(x:Indexing,       y) { setBase2(x, #expr, y); }
overload setBase(x:Call,           y) { setBase2(x, #expr, y); }
overload setBase(x:FieldRef,       y) { setBase2(x, #expr, y); }
overload setBase(x:StaticIndexing, y) { setBase2(x, #expr, y); }
overload setBase(x:UnaryOp,        y) { setBase2(x, #expr, y); }
overload setBase(x:BinaryOp,       y) { setBase2(x, #expr1, y); }
overload setBase(x:And,            y) { setBase2(x, #expr1, y); }
overload setBase(x:Or,             y) { setBase2(x, #expr1, y); }

private foldTail(x) {
    var result = x.0;
    for (y in x.1) {
        setBase(*y, result);
        result = y;
    }
    return result;
}



//
// suffix expr
//

private var indexingSuffix = exprParser(
    x => Indexing(Expr(), move(x.1)),
    sequence(punc(#"["), optExprList, punc(#"]")),
);

private var callSuffix = exprParser(
    x => Call(Expr(), move(x.1)),
    sequence(punc(#"("), optExprList, punc(#")")),
);

private var fieldRefSuffix = exprParser(
    x => FieldRef(Expr(), x.1),
    sequence(punc(#"."), identifier),
);

private var staticIndexingSuffix = exprParser(
    x => StaticIndexing(Expr(), String(x.1)),
    sequence(punc(#"."), tokenData(INT_LITERAL)),
);

private var dereferenceSuffix = exprParser(
    x => UnaryOp(DEREFERENCE, Expr()),
    punc(#"^"),
);

private var suffix = choice(
    indexingSuffix, callSuffix, fieldRefSuffix,
    staticIndexingSuffix, dereferenceSuffix,
);

private var suffixExpr = modify(
    foldTail,
    sequence(atomicExpr, zeroOrMore(suffix)),
);



//
// prefix expr
//

private var addressOfExpr = exprParser(
    x => UnaryOp(ADDRESS_OF, x.1),
    sequence(punc(#"&"), suffixExpr),
);

private var plusOrMinus = choice(
    modify(x => PLUS,  punc(#"+")),
    modify(x => MINUS, punc(#"-")),
);

private var signExpr = exprParser(
    x => UnaryOp(x.0, x.1),
    sequence(plusOrMinus, suffixExpr),
);

private var dispatchExpr = exprParser(
    x => DispatchExpr(x.1),
    sequence(punc(#"*"), suffixExpr),
);

private var prefixExpr = choice(
    signExpr, addressOfExpr, dispatchExpr, suffixExpr
);



//
// binary ops
//

private binaryOp(op, term) = modify(
    foldTail,
    sequence(term, zeroOrMore(exprParser(
        x => BinaryOp(x.0, Expr(), x.1),
        sequence(op, term),
    ))),
);

private var mulDivOp = choice(
    modify(x => MULTIPLY,  punc(#"*")),
    modify(x => DIVIDE,    punc(#"/")),
    modify(x => REMAINDER, punc(#"%")),
);
private var mulDivExpr = binaryOp(mulDivOp, prefixExpr);

private var addSubOp = choice(
    modify(x => ADD,      punc(#"+")),
    modify(x => SUBTRACT, punc(#"-")),
);
private var addSubExpr = binaryOp(addSubOp, mulDivExpr);

private var compareOp = choice(
    modify(x => LESSER,         punc(#"<")),
    modify(x => LESSER_EQUALS,  punc(#"<=")),
    modify(x => GREATER,        punc(#">")),
    modify(x => GREATER_EQUALS, punc(#">=")),
);
private var compareExpr = binaryOp(compareOp, addSubExpr);

private var equalOp = choice(
    modify(x => EQUALS,     punc(#"==")),
    modify(x => NOT_EQUALS, punc(#"!=")),
);
private var equalExpr = binaryOp(equalOp, compareExpr);



//
// not, and, or
//

private var notExpr = choice(
    exprParser(
        x => UnaryOp(NOT, x.1),
        sequence(kw_not, equalExpr),
    ),
    equalExpr,
);

private andOrOp(node, op, term) = modify(
    foldTail,
    sequence(term, zeroOrMore(exprParser(
        x => node(Expr(), x.1),
        sequence(op, term),
    ))),
);

private var andExpr = andOrOp(And, kw_and, notExpr);
private var orExpr = andOrOp(Or, kw_or, andExpr);



//
// if expr, unpack expr, new expr, static expr, pair expr
//

private var ifExpr = exprParser(
    x => IfExpr(x.2, x.4, x.6),
    sequence(kw_if, punc(#"("), expr, punc(#")"), expr, kw_else, expr),
);

private var unpackExpr = exprParser(
    x => Unpack(x.1),
    sequence(punc(#"..."), expr),
);

private var newExpr = exprParser(
    x => New(x.1),
    sequence(kw_new, expr),
);

private var staticExpr = exprParser(
    x => StaticExpr(x.1),
    sequence(kw_static, expr),
);

private var pairExpr = exprParser(
    x => PairExpr(move(x.0), move(x.2)),
    sequence(identifier, punc(#":"), expr),
);



//
// return kind
//

private var returnKind = choice(
    modify(x => RETURN_REF, kw_ref),
    modify(x => RETURN_FORWARD, kw_forward),
    input => Maybe(RETURN_VALUE),
);



//
// lambda expr
//

private var lambdaArgs = choice(
    modify(
        x => VariadicList(Vector[Identifier](move(x)), nothing(Identifier)),
        identifier,
    ),
    modify(
        x => move(x.1),
        sequence(
            punc(#"("),
            variadicList(
                identifier,
                modify(x => x.1, sequence(punc(#"..."), identifier)),
            ),
            punc(#")")
        ),
    ),
);

private var lambdaArrow = choice(
    modify(x => true, sequence(kw_ref, punc(#"=>"))),
    modify(x => true, punc(#"->")),
    modify(x => false, punc(#"=>")),
);

private var lambdaBody = choice(
    block,
    statementParser(
        x => Return(x.0, Vector[Expr](x.1)),
        sequence(returnKind, expr),
    ),
);

private var lambdaExpr = exprParser(
    x => LambdaExpr(x.1, move(x.0), move(x.2)),
    sequence(lambdaArgs, lambdaArrow, lambdaBody),
);



//
// expr
//

private var expr2 = choice(
    lambdaExpr, pairExpr, orExpr, ifExpr, unpackExpr, newExpr, staticExpr,
);

private var caseExpr = choice(
    lambdaExpr, orExpr, ifExpr, unpackExpr, newExpr, staticExpr,
);

private expr(input) : Maybe[Expr] { return expr2(input); }

private var exprList = commaList(expr);
private var optExprList = optCommaList(expr);



//
// pattern
//

private var dottedNamedRef = modify(
    foldTail,
    sequence(nameRef, zeroOrMore(fieldRefSuffix)),
);

private var atomicPattern = choice(dottedNamedRef, intLiteral);

private var pattern = modify(
    foldTail,
    sequence(atomicPattern, zeroOrMore(indexingSuffix)),
);



//
// patternTypeSpec, typeSpec
//

private var patternTypeSpec = modify(x => x.1, sequence(punc(#":"), pattern));
private var typeSpec = modify(x => x.1, sequence(punc(#":"), expr));



//
// statementParser combinator
//

private statementParser(forward modifier, forward parser) = modify(
    x => Statement(move(x)),
    bounds(modify(modifier, parser)),
);



//
// statements
//

private var labelDef = statementParser(
    x => Label(x.0),
    sequence(identifier, punc(#":")),
);

private var bindingKind = choice(
    modify(x => VAR,   kw_var),
    modify(x => REF,   kw_ref),
    modify(x => ALIAS, kw_alias),
);

private var localBinding = statementParser(
    x => Binding(x.0, move(x.1), move(x.3)),
    sequence(bindingKind, identifierList, punc(#"="), exprList, punc(#";")),
);

private var blockItem = choice(labelDef, localBinding, statement);

private var block = statementParser(
    x => Block(move(x.1)),
    sequence(punc(#"{"), zeroOrMore(blockItem), punc(#"}")),
);

private var assignment = statementParser(
    x => Assignment(move(x.0), move(x.2)),
    sequence(exprList, punc(#"="), exprList, punc(#";")),
);

private var initAssignment = statementParser(
    x => InitAssignment(move(x.0), move(x.2)),
    sequence(exprList, punc(#"<--"), exprList, punc(#";")),
);

private var updateOp = choice(
    modify(x => UPDATE_ADD,       punc(#"+=")),
    modify(x => UPDATE_SUBTRACT,  punc(#"-=")),
    modify(x => UPDATE_MULTIPLY,  punc(#"*=")),
    modify(x => UPDATE_DIVIDE,    punc(#"/=")),
    modify(x => UPDATE_REMAINDER, punc(#"%=")),
);

private var updateAssignment = statementParser(
    x => UpdateAssignment(x.1, x.0, x.2),
    sequence(expr, updateOp, expr, punc(#";")),
);

private var gotoStatement = statementParser(
    x => Goto(x.1),
    sequence(kw_goto, identifier, punc(#";")),
);

private var returnStatement = statementParser(
    x => Return(x.1, move(x.2)),
    sequence(kw_return, returnKind, optExprList, punc(#";")),
);

private var ifStatement = statementParser(
    x => If(x.2, x.4, x.5),
    sequence(
        kw_if, punc(#"("), expr, punc(#")"), statement,
        optional(modify(
            x => x.1,
            sequence(kw_else, statement),
        )),
    ),
);

private var caseLabel = modify(
    x => x.1,
    sequence(kw_case, caseExpr, punc(#":")),
);

private var caseBody = statementParser(CaseBody, oneOrMore(statement));

private var caseBlock = bounds(modify(
    x => CaseBlock(move(x.0), move(x.1)),
    sequence(oneOrMore(caseLabel), caseBody),
));

private var defaultCase = modify(
    x => x.2,
    sequence(kw_default, punc(#":"), caseBody),
);

private var switchStatement = statementParser(
    x => Switch(x.2, move(x.5), x.6),
    sequence(
        kw_switch, punc(#"("), expr, punc(#")"), punc(#"{"),
        zeroOrMore(caseBlock), optional(defaultCase), punc(#"}"),
    ),
);

private var exprStatement = statementParser(
    x => ExprStatement(x.0),
    sequence(expr, punc(#";")),
);

private var whileStatement = statementParser(
    x => While(x.2, x.4),
    sequence(kw_while, punc(#"("), expr, punc(#")"), statement),
);

private var breakStatement = statementParser(
    x => Break(0),
    sequence(kw_break, punc(#";")),
);

private var continueStatement = statementParser(
    x => Continue(0),
    sequence(kw_continue, punc(#";")),
);

private var forStatement = statementParser(
    x => For(move(x.2), x.4, x.6),
    sequence(
        kw_for, punc(#"("), identifierList, kw_in, expr, punc(#")"),
        statement
    ),
);

private var catchBlock = bounds(modify(
    x => Catch(x.2, x.3, x.5),
    sequence(
        kw_catch, punc(#"("), identifier, optional(typeSpec), punc(#")"), block,
    ),
));

private var tryStatement = statementParser(
    x => Try(x.1, move(x.2)),
    sequence(kw_try, block, oneOrMore(catchBlock)),
);

private var throwStatement = statementParser(
    x => Throw(x.1),
    sequence(kw_throw, expr, punc(#";")),
);

private var staticForStatement = statementParser(
    x => StaticFor(x.3, move(x.5), x.7),
    sequence(
        kw_static, kw_for, punc(#"("), identifier, kw_in,
        exprList, punc(#")"), statement,
    ),
);

private var statement2 = choice(
    block, assignment, initAssignment, updateAssignment, ifStatement,
    gotoStatement, switchStatement, returnStatement, exprStatement,
    whileStatement, breakStatement, continueStatement, forStatement,
    tryStatement, throwStatement, staticForStatement,
);

private statement(input) : Maybe[Statement] = statement2(input);



//
// parsing parts of code definitions
//

private var patternVar = bounds(modify(
    x => PatternVar(not nothing?(x.0), x.1),
    sequence(optional(punc(#"...")), identifier),
));

private var optPredicate = optional(modify(
    x => x.1,
    sequence(punc(#"|"), expr),
));

private var patternVarsWithPredicate2 = modify(
    x => [move(x.1), x.2],
    sequence(punc(#"["), optCommaList(patternVar), optPredicate, punc(#"]")),
);

private var patternVarsWithPredicate = modify(
    x => maybe(move(x), move, () => [Vector[PatternVar](), nothing(Expr)]),
    optional(patternVarsWithPredicate2),
);

private var argumentKind = choice(
    modify(x => ARG_LVALUE,  kw_lvalue),
    modify(x => ARG_RVALUE,  kw_rvalue),
    modify(x => ARG_FORWARD, kw_forward),
    input => Maybe(ARG_DEFAULT),
);

private var argument = choice(
    modify(Argument, bounds(modify(
        x => NormalArgument(x.0, x.1, x.2),
        sequence(argumentKind, identifier, optional(patternTypeSpec)),
    ))),
    modify(Argument, bounds(modify(
        x => StaticArgument(x.1),
        sequence(kw_static, orExpr),
    ))),
);

private var variadicArgument = modify(Argument, bounds(modify(
    x => NormalArgument(x.0, x.2, x.3),
    sequence(argumentKind, punc(#"..."), identifier, optional(patternTypeSpec)),
)));

private var arguments = variadicList(argument, variadicArgument);

private var namedReturn = modify(
    x => x.0,
    sequence(identifier, punc(#":"))
);

private var returnSpec = bounds(modify(
    x => ReturnSpec(not nothing?(x.0), x.1, x.2),
    sequence(optional(punc(#"...")), optional(namedReturn), orExpr),
));

private var returnSpecs = optCommaList(returnSpec);

private var clayBody = choice(
    block,
    statementParser(
        x => Return(x.1, move(x.2)),
        sequence(punc(#"="), returnKind, optExprList, punc(#";")),
    ),
);

private var llvmBody = bounds(modify(
    x => LLVMBody(String(x)),
    tokenData(LLVM),
));

private var noBody = bounds(modify(
    x => NoBody(),
    punc(#";"),
));

private var codeBody = choice(
    modify(CodeBody, clayBody),
    modify(CodeBody, llvmBody),
    modify(CodeBody, noBody),
);



//
// top level items
//

private topLevelItemParser(forward modifier, forward parser) = modify(
    x => TopLevelItem(move(x)),
    bounds(modify(modifier, parser)),
);

private var visibility = choice(
    modify(x => PUBLIC,  kw_public),
    modify(x => PRIVATE, kw_private),
);

private var recordField = bounds(modify(
    x => RecordField(x.0, x.1),
    sequence(identifier, typeSpec),
));

private var declaredRecordBody = bounds(modify(
    x => DeclaredRecordBody(move(x.1)),
    sequence(punc(#"("), optCommaList(recordField), punc(#")"), punc(#";")),
));

private var computedRecordBody = bounds(modify(
    x => ComputedRecordBody(move(x.1)),
    sequence(punc(#"="), optExprList, punc(#";")),
));

private var recordBody = choice(
    modify(RecordBody, declaredRecordBody),
    modify(RecordBody, computedRecordBody),
);

private var staticParams = modify(
    x => move(x.1),
    sequence(
        punc(#"["),
        variadicList(
            identifier,
            modify(x => x.1, sequence(punc(#"..."), identifier)),
        ),
        punc(#"]"),
    ),
);

private var optStaticParams = modify(
    x => maybe(move(x), move, () => VariadicList[Identifier]()),
    optional(staticParams),
);

private var recordDef = topLevelItemParser(
    x => Record(x.0, x.2, x.3, x.4),
    sequence(
        optional(visibility), kw_record, identifier, optStaticParams,
        recordBody,
    ),
);


private var defaultInstances = choice(
    modify(
        x => Vector[Expr](),
        punc(#";"),
    ),
    modify(
        x => move(x.1),
        sequence(punc(#"="), separatedList(punc(#"|"), expr), punc(#";")),
    ),
);

private var variantDef = topLevelItemParser(
    x => Variant(x.0, x.2, x.3, x.4),
    sequence(
        optional(visibility), kw_variant, identifier, optStaticParams,
        defaultInstances
    ),
);

private var instanceDef = topLevelItemParser(
    x => Instance((x.0).0, (x.0).1, x.2, x.4),
    sequence(
        patternVarsWithPredicate, kw_instance, pattern,
        punc(#"="), expr, punc(#";"),
    ),
);

private var optCallByName = modify(
    x => not nothing?(x),
    optional(kw_callbyname),
);

private var optInline = modify(
    x => not nothing?(x),
    optional(kw_inline),
);

private var procedureWithBody = topLevelItemParser(
    x => Procedure(x.1, x.5, Maybe(
        Code(x.2, x.3, (x.0).0, (x.0).1, x.7, x.9, x.10)
    )),
    sequence(
        patternVarsWithPredicate, optional(visibility), optCallByName,
        optInline, optional(kw_procedure), identifier,
        punc(#"("), arguments, punc(#")"), returnSpecs, codeBody,
    ),
);

private var procedureWithoutBody = topLevelItemParser(
    x => Procedure(x.0, x.2, nothing(Code)),
    sequence(optional(visibility), kw_procedure, identifier, punc(#";")),
);

private var overloadDef = topLevelItemParser(
    x => Overload(x.4, Code(x.1, x.2, (x.0).0, (x.0).1, x.6, x.8, x.9)),
    sequence(
        patternVarsWithPredicate, optCallByName, optInline, kw_overload,
        pattern, punc(#"("), arguments, punc(#")"), returnSpecs, codeBody,
    ),
);

private var enumDef = topLevelItemParser(
    x => Enum(x.0, x.2, x.4),
    sequence(
        optional(visibility), kw_enum, identifier,
        punc(#"{"), identifierList, punc(#"}")
    ),
);

private var globalVariableDef = topLevelItemParser(
    x => GlobalVariable(x.0, x.2, x.3, x.5),
    sequence(
        optional(visibility), kw_var, identifier, optStaticParams,
        punc(#"="), expr, punc(#";"),
    ),
);

private var globalAliasDef = topLevelItemParser(
    x => GlobalAlias(x.0, x.2, x.3, x.5),
    sequence(
        optional(visibility), kw_alias, identifier, optStaticParams,
        punc(#"="), expr, punc(#";"),
    ),
);

private var externalAttributes2 = modify(
    x => x.1,
    sequence(punc(#"("), exprList, punc(#")")),
);

private var externalAttributes = modify(
    x => maybe(move(x), move, () => Vector[Expr]()),
    optional(externalAttributes2),
);

private var externalArg = bounds(modify(
    x => ExternalArg(x.0, x.2),
    sequence(identifier, punc(#":"), expr),
));

private var variadicExternalArg = bounds(modify(
    x => ExternalArg(Identifier(), Expr()),
    punc(#"..."),
));

private var externalArgs = modify(
    x => [move(x.items), not nothing?(x.variadicItem)],
    variadicList(externalArg, variadicExternalArg),
);

private var externalBody = choice(
    modify(x => Maybe(x), clayBody),
    modify(x => nothing(Statement), punc(#";")),
);

private var externalProcedure = topLevelItemParser(
    x => ExternalProcedure(x.0, x.3, x.2, (x.5).0, (x.5).1, x.7, x.8),
    sequence(
        optional(visibility), kw_external, externalAttributes, identifier,
        punc(#"("), externalArgs, punc(#")"), optional(expr), externalBody,
    ),
);

private var externalVariable = topLevelItemParser(
    x => ExternalVariable(x.0, x.3, x.2, x.4),
    sequence(
        optional(visibility), kw_external, externalAttributes,
        identifier, typeSpec, punc(#";"),
    ),
);

private var toplevelLLVMBody = topLevelItemParser(
    x => x,
    llvmBody
);

private var topLevelItem = choice(
    recordDef, variantDef, instanceDef, procedureWithBody,
    procedureWithoutBody, overloadDef, enumDef,
    globalVariableDef, globalAliasDef,
    externalProcedure, externalVariable,
    toplevelLLVMBody
);



//
// imports
//

private var moduleName = bounds(modify(
    DottedName,
    separatedListStrict(punc(#"."), identifier),
));

private var optAlias = optional(modify(
    x => x.1,
    sequence(kw_as, identifier),
));

private importParser(forward modifier, forward parser) = modify(
    x => Import(move(x)),
    bounds(modify(modifier, parser)),
);

private var importModule = importParser(
    x => ImportModule(x.0, x.2, x.3),
    sequence(
        optional(visibility), kw_import, moduleName, optAlias, punc(#";")
    ),
);

private var importStar = importParser(
    x => ImportStar(x.0, x.2),
    sequence(
        optional(visibility), kw_import, moduleName,
        punc(#"."), punc(#"*"), punc(#";"),
    ),
);

private var importedMember = bounds(modify(
    x => ImportedMember(x.0, x.1),
    sequence(identifier, optAlias),
));

private var importMembers = importParser(
    x => ImportMembers(x.0, x.2, x.5),
    sequence(
        optional(visibility), kw_import, moduleName, punc(#"."),
        punc(#"("), commaList(importedMember), punc(#")"), punc(#";"),
    ),
);

private var importDef = choice(
    importModule, importStar, importMembers,
);



//
// ParserError
//

record ParserError(
    tokens: SourceTokens,
    where: SizeT,
);

instance ClayError (ParserError);

overload displayError(e:ParserError) {
    var offset = e.tokens.vector[e.where].range.begin;
    errorWithLocation(e.tokens.file, offset, "parse error");
}



//
// parseExpr, parse
//

private var parseExpr2 = modify(
    x => x.0,
    sequence(expr, token(SENTINEL)),
);

parseExpr(tokens:SourceTokens) {
    var input = ParserInput(tokens);
    var result = parseExpr2(input);
    if (nothing?(result))
        throw ParserError(tokens, input.maxCurrent);
    return require(move(result));
}

private var parse2 = modify(
    x => SourceAST(SourceTokens(), x.0, x.1),
    sequence(
        zeroOrMore(importDef), zeroOrMore(topLevelItem), token(SENTINEL)
    ),
);

parse(tokens:SourceTokens) {
    var input = ParserInput(tokens);
    var ast = parse2(input);
    if (nothing?(ast))
        throw ParserError(tokens, input.maxCurrent);
    var ast2 = require(move(ast));
    ast2.tokens = tokens;
    return move(ast2);
}
