use std::{str::FromStr, mem};

use itertools::{Either, Itertools};

use crate::base::{
    ast::{self, Alternative, Argument, Array, AstType, Do, Expr, ExprField, KindedIdent, Lambda, Literal, Pattern,
    PatternField, SpannedExpr, SpannedIdent, SpannedPattern, TypeBinding, TypedIdent, ValueBinding, ValueBindings},
    kind::{ArcKind, Kind},
    pos::{self, BytePos, HasSpan, Spanned},
    types::{Alias, AliasData, ArcType, ArgType, BuiltinType, Field, Generic, Type, TypeCache, TypeContext},
    metadata::{Attribute, Metadata, BaseMetadata, Comment},
};

use crate::{ReplLine, Variant, new_ident};
use crate::token::{Token, BorrowedToken, StringLiteral};
use ordered_float::NotNan;

use crate::{Error, ErrorEnv, FieldExpr, MutIdentEnv, TempVecs, TempVecStart, Slice};

grammar<'input, 'env, 'ast, Id>(
    input: &'input dyn crate::ParserSource,
    type_cache: &TypeCache<Id, ArcType<Id>>,
    arena: ast::ArenaRef<'_, 'ast, Id>,
    env: MutIdentEnv<'env, Id>,
    errors: ErrorEnv<'env, 'input>,
    temp_vecs: &mut TempVecs<'ast, Id>,
)
    where Id: Clone + AsRef<str> + std::fmt::Debug;

extern {
    type Location = BytePos;
    type Error = Spanned<Error, BytePos>;

    enum BorrowedToken<'input> {
        "shebang line" => Token::ShebangLine(<&'input str>),
        "identifier" => Token::Identifier(<&'input str>),
        "operator" => Token::Operator(<&'input str>),
        "string literal" => Token::StringLiteral(<StringLiteral<&'input str>>),
        "char literal" => Token::CharLiteral(<char>),
        "int literal" => Token::IntLiteral(<i64>),
        "byte literal" => Token::ByteLiteral(<u8>),
        "float literal" => Token::FloatLiteral(<NotNan<f64>>),
        "documentation comment" => Token::DocComment(<Comment<&'input str>>),

        "rec" => Token::Rec,
        "else" => Token::Else,
        "forall" => Token::Forall,
        "if" => Token::If,
        "in" => Token::In,
        "let" => Token::Let,
        "do" => Token::Do,
        "seq" => Token::Seq,
        "match" => Token::Match,
        "then" => Token::Then,
        "type" => Token::Type,
        "with" => Token::With,

        "@" => Token::At,
        ":" => Token::Colon,
        "," => Token::Comma,
        "." => Token::Dot,
        ".." => Token::DotDot,
        "=" => Token::Equals,
        "\\" => Token::Lambda,
        "|" => Token::Pipe,
        "->" => Token::RArrow,
        "?" => Token::Question,

        "{" => Token::LBrace,
        "[" => Token::LBracket,
        "(" => Token::LParen,

        "}" => Token::RBrace,
        "]" => Token::RBracket,
        ")" => Token::RParen,

        "#[" => Token::AttributeOpen,

        "block open" => Token::OpenBlock,
        "block close" => Token::CloseBlock,
        "block separator" => Token::Semi,
    }
}

// Utils

SingleComma: () = {
    "," => (),
    RecoverError,
};

#[inline]
SepTemp<Rule, Separator>: TempVecStart<Rule> = {
    <start: Many1Vec<(<Rule> Separator)>?> <last: Rule?> => {
        let start = start.unwrap_or_else(|| temp_vecs.start());
        if let Some(last) = last {
            temp_vecs.select().push(last);
        }
        start
    }
};

#[inline]
CommaTemp<Rule>: TempVecStart<Rule> = {
    SepTemp<Rule, SingleComma>
};

#[inline]
SepVec1<Rule, Separator>: TempVecStart<Rule> =
    <start: Many1Vec<(<Rule> Separator)>?> <last: Rule> => {
        let start = match start {
            Some(start) => start,
            None => temp_vecs.start(),
        };
        temp_vecs.select().push(last);
        start
    };

#[inline]
SepSlice1<Rule, Separator>: &'ast mut Slice<Rule> =
    <start: Many1Vec<(<Rule> Separator)>?> <last: Rule> => {
        match start {
            Some(start) => arena.alloc_extend(temp_vecs.drain(start).chain(Some(last))),
            None => arena.alloc_extend(Some(last)),
        }
    };


#[inline]
SepSlice<Rule, Separator>: &'ast mut Slice<Rule> =
    <start: Many1Vec<(<Rule> Separator)>?> <last: Rule?> => {
        match start {
            Some(start) => arena.alloc_extend(temp_vecs.drain(start).chain(last)),
            None => arena.alloc_extend(last),
        }
    };

#[inline]
CommaSlice<Rule>: &'ast mut Slice<Rule> = {
    SepSlice<Rule, SingleComma>
};

#[inline]
Sp<Rule>: Spanned<Rule, BytePos> =
    <l: @L> <rule: Rule> <r: @R> =>
        pos::spanned2(l, r, rule);

IdentStr: &'input str = {
    "identifier" => <>,
    "(" <"operator"> ")" => <>,
};

VecStart<T>: TempVecStart<T> = {
    T => {
        let start = temp_vecs.start();
        temp_vecs.select().push(<>);
        start
    },
};

Many1Rest<T>: () = {
    <T> => temp_vecs.select().push(<>),
    Many1Rest<T> <T> => {
        temp_vecs.select().push(<>);
    }
};

#[inline]
Many1Vec<T>: TempVecStart<T> = {
    <VecStart<T>>,
    <VecStart<T>> Many1Rest<T>,
};

Many<T>: &'ast mut Slice<T> = {
    => &mut [],
    Many1<T>,
};

Many1<T>: &'ast mut Slice<T> = {
    Many1Vec<T> => {
        arena.alloc_extend(temp_vecs.drain(<>))
    }
};

RecoverError: () = {
    <!> => errors.push(<>.error),
};

SkipExtraTokens: () = {
    => (),
    RecoverError,
};

Ident: Id =
    IdentStr => env.from_str(<>);

CtorIdent: Id =
    <ident: Sp<Ident>> => {
        if !env.string(&ident.value).starts_with(char::is_uppercase) {
            errors.push(::lalrpop_util::ParseError::User {
                error: pos::spanned(ident.span, format!("Constructors must start with an uppercase letter").into()),
            });
        }
        ident.value
    };

SpannedIdent: SpannedIdent<Id> =
    <ident: Sp<Ident>> => pos::spanned(ident.span, new_ident(type_cache, ident.value));

Operator: TypedIdent<Id> =
    "operator" => new_ident(type_cache, env.from_str(<>));

DocComment: Comment =
    <comments: "documentation comment"+> => {
        let typ = comments.last().unwrap().typ;
        Comment {
            typ: typ,
            content: comments.into_iter().map(|comment| comment.content).join("\n")
        }
    };

Any: () = {
    <"identifier">,
    <"operator">,
    <"string literal">,
    <"char literal">,
    <"int literal">,
    <"byte literal">,
    <"float literal">,

    <",">,
    <"=">,

    "(" AttributeContents ")",
    "[" AttributeContents "]",
    "{" AttributeContents "}",
};

AttributeContents: () = {
    Any*
};

AttributeArguments: Option<String> = {
    "(" <start: @L> AttributeContents <end: @R> ")" =>
        Some(input.src()[(start.to_usize() - input.start_index().to_usize())..(end.to_usize() - input.start_index().to_usize())].to_string()),
    => None,
};

Attribute: Attribute = {
    "#[" <name: IdentStr> <arguments: AttributeArguments> "]" => Attribute { name: name.into(), arguments, },
};

Metadata: BaseMetadata<'ast> = {
    <comment: DocComment> => BaseMetadata { metadata: Some(arena.alloc(Metadata { comment: Some(comment), .. Metadata::default() })) },
    <comment: DocComment> <attributes: Attribute+> => BaseMetadata { metadata: Some(arena.alloc(Metadata { comment: Some(comment), attributes, .. Metadata::default() })) },
    <attributes: Attribute+> => BaseMetadata { metadata: Some(arena.alloc(Metadata { attributes, .. Metadata::default() })) },
    => BaseMetadata { metadata: None },
};

// Kinds

AtomicKind: ArcKind = {
    <l: @L> <id: "identifier"> <r: @R> =>? {
        use lalrpop_util::ParseError;

        match id {
            "_" => Ok(type_cache.kind_cache.hole()),
            "Type" => Ok(type_cache.kind_cache.typ()),
            "Row" => Ok(type_cache.kind_cache.row()),
            id => Err(ParseError::User {
                error: pos::spanned2(
                    l.into(),
                    r.into(),
                    Error::UnexpectedToken(
                        Token::Identifier(id.into()),
                        ["_", "Row", "Type"].iter().map(|s| s.to_string()).collect())),
            }),
        }
    },

    "(" <kind: Kind> ")" => kind,
};

Kind: ArcKind = {
    AtomicKind,

    <lhs: AtomicKind> "->" <rhs: Kind> =>
        Kind::function(lhs, rhs),
};

// Types

TypeParam: Generic<Id> = {
    <id : Ident> =>
        Generic::new(id, type_cache.kind_cache.hole()),

    "(" <id: Ident> ":" <kind: Kind> ")" =>
        Generic::new(id, kind),
};

GenericIdent: Generic<Id> = {
    Ident => Generic::new(<>, type_cache.kind_cache.hole()),
};

RecordField: Either<Field<Spanned<Id, BytePos>, Alias<Id, AstType<'ast, Id>>>, Field<Spanned<Id, BytePos>, AstType<'ast, Id>>> = {
    <metadata: Metadata> <id: Sp<Ident>> <args: Many<GenericIdent>> <alias: ("=" <Sp<Type_>>)> => {
        Either::Left(Field::new(
            id.clone(),
            Alias::new_with(
                &mut arena.clone(),
                id.value,
                args,
                AstType::with_metadata(arena, metadata, alias),
            ),
        ))
    },
    <metadata: Metadata> <id: Sp<Ident>> => {
        let span = id.span;
        Either::Left(Field::new(
            id.clone(),
            Alias::new_with(
                &mut arena.clone(),
                id.value,
                Default::default(),
                AstType::with_metadata(arena, metadata, pos::spanned(span, Type::Hole)),
            ),
        ))
    },
    <metadata: Metadata> <id: Sp<Ident>> ":" <typ: Sp<Type_>> => {
        if env.string(&id.value).starts_with(char::is_uppercase) {
            errors.push(::lalrpop_util::ParseError::User {
                error: pos::spanned(typ.span, format!("Defining a kind for a type in this location is not supported yet").into()),
            });
            Either::Left(Field::new(
                id.clone(),
                Alias::new_with(
                    &mut arena.clone(),
                    id.value,
                    Default::default(),
                    AstType::with_metadata(arena, metadata, typ),
                ),
            ))
        } else {
            Either::Right(Field::new(
                id,
                AstType::with_metadata(arena, metadata, typ),
            ))
        }
    },
};

VariantField: Variant<'ast, Id> = {
    "|" <Sp<CtorIdent>> <AtomicType*> => Variant::Simple(<>),
    "|" <Sp<CtorIdent>> ":" <Type> => Variant::Gadt(<>)
};

VariantType: (Vec<Id>, Vec<Variant<'ast, Id>>, Option<AstType<'ast, Id>>) = {

    <row: VariantField+> <rest: (".." <AtomicType>)?> => {
        (Vec::new(), row, rest)
    },

    "forall" <args: Ident+> "." "(" <mut ty: VariantType> ")" => {
        ty.0.extend(args);
        ty
    }
};

TypeTop: Either<AstType<'ast, Id>, Spanned<(Vec<Id>, Vec<Variant<'ast, Id>>, Option<AstType<'ast, Id>>), BytePos>> = {
    Type => Either::Left(<>),
    <rest: Sp<(".." <AtomicType>)>> => {
        let Spanned { span, value: rest } = rest;
        Either::Left(
            AstType::new(
                arena,
                pos::spanned(span, Type::Variant(AstType::new(arena, pos::spanned(span, Type::ExtendRow { fields: Default::default(), rest }))))
            ),
        )
    },
    <Sp<VariantType>> => Either::Right(<>),
};

TypeBinding: TypeBinding<'ast, Id> = {
    <metadata: Metadata> "type" <type_name: Sp<Ident>> <params: Many<TypeParam>> "=" <body: TypeTop> => {
        if !env.string(&type_name.value).starts_with(char::is_uppercase) {
            errors.push(::lalrpop_util::ParseError::User {
                error: pos::spanned(type_name.span, format!("A type must start with an uppercase letter").into()),
            });
        }

        let body = match body {
            Either::Left(body) => body,
            Either::Right(Spanned { span, value: (forall_params, variants, rest) }) => {
                let rest: AstType<_> = rest.unwrap_or_else(|| AstType::new(arena, pos::spanned(span, Type::EmptyRow)));
                let row = if variants.is_empty() {
                    rest
                } else {
                    let fields = arena.clone().alloc_extend(
                        variants.into_iter()
                            .map(|variant| match variant {
                                Variant::Gadt(name, mut typ) => {
                                    {
                                        let mut typ = &mut typ;
                                        while let Type::Function(arg_type, _, ret) = &mut **typ {
                                            *arg_type = ArgType::Constructor;
                                            typ = ret;
                                        }
                                    }
                                    Field::new(name, typ)
                                }
                                Variant::Simple(name, types) => Field::new(
                                    name,
                                    arena.clone().function_type(
                                        ArgType::Constructor,
                                        types,
                                        arena.clone().opaque(),
                                    )
                                ),
                            }),
                    );
                    AstType::new(arena, pos::spanned(span, Type::ExtendRow { fields, rest }))
                };

                arena.clone().forall(
                    arena.alloc_extend(forall_params.into_iter().map(|id| Generic::new(id, type_cache.kind_cache.hole()))),
                    AstType::new(arena, pos::spanned(span, Type::Variant(row)))
                )
            }
        };

        TypeBinding {
            metadata,
            name: type_name.clone(),
            alias: pos::spanned(body.span(), AliasData::new(type_name.value.clone(), params, body)),
            finalized_alias: None,
        }
    },
};

Effect: Field<Spanned<Id, BytePos>, AstType<'ast, Id>> = {
    <name: Sp<Ident>> ":" <typ: Type> => Field { <> }
};

AtomicType_: Type<Id, AstType<'ast, Id>> = {
    "(" "->" ")" =>
        Type::Builtin(BuiltinType::Function),

    <ids: (<Ident> ".")*> <last: IdentStr> => {
        if ids.is_empty() {
            if last == "_" {
                Type::Hole
            } else {
                match BuiltinType::from_str(last) {
                    Ok(ty) => Type::Builtin(ty),
                    Err(_) if last.starts_with(char::is_uppercase) => {
                        Type::Ident(KindedIdent { name: env.from_str(last), typ: type_cache.kind_cache.hole() })
                    }
                    Err(_) => {
                        Type::Generic(Generic::new(env.from_str(last), type_cache.kind_cache.hole()))
                    }
                }
            }
        } else {
            let ids = ids
                .iter()
                .cloned()
                .chain(Some(env.from_str(last)))
                .collect();
            Type::Projection(ids)
        }
    },

    "(" <rest: Sp<(".." <AtomicType>)>> ")" => {
        let Spanned { span, value: rest } = rest;
        Type::Variant(AstType::new(arena, pos::spanned(span, Type::ExtendRow { fields: Default::default(), rest })))
    },


    "[" "|" <fields: SepSlice<Effect, ",">> <rest: ("|" <Type>)?> "|" "]" => {
        let rest = rest.unwrap_or_else(|| arena.clone().empty_row());
        Type::Effect(arena.clone().extend_row(fields, rest))
    },

    "(" <elems: CommaTemp<Type>> ")" => {
        let mut elems = temp_vecs.drain(elems);
        match elems.size_hint().0 {
            // Parenthesized type
            1 => mem::take(&mut *elems.next().unwrap()), // TODO Avoid mem take
            _ => arena.clone().tuple_(env, elems),
        }
    },

    "{" <row: CommaTemp<RecordField>> <rest: ("|" <Type>)?> "}" => {
        let mut types = Vec::new();
        let fields = arena.alloc_extend(temp_vecs.drain(row).filter_map(|either| match either {
            Either::Left(l) => {
                types.push(l);
                None
            }
            Either::Right(r) => Some(r),
        }));
        let types = arena.alloc_extend(types);
        Type::Record(arena.clone().extend_full_row(
            types,
            fields,
            rest.unwrap_or_else(|| arena.clone().empty_row()),
        ))
    },
};

AtomicType: AstType<'ast, Id> = {
    <typ: Sp<AtomicType_>> => AstType::new(arena, typ),
};

AppType_ = {
    AtomicType_,

    <ty: AtomicType> <args: Many1<AtomicType>> =>
        Type::App(ty, args),
};

AppType: AstType<'ast, Id> = {
    <typ: Sp<AppType_>> => AstType::new(arena, typ),
};

Type_ = {
    AppType_,
    "forall" <args: Ident+> "." <ty: Type> =>
        Type::Forall(
            arena.alloc_extend(args.into_iter().map(|id| Generic::new(id, type_cache.kind_cache.hole()))),
            ty,
        ),

    <lhs: ArgType> <f: Sp<"->">> <rhs: Type> =>
        Type::Function(
            lhs.0,
            lhs.1,
            rhs,
        )
};

Type: AstType<'ast, Id> = {
    <typ: Sp<Type_>> => AstType::new(arena, typ),
};

ArgType: (ArgType, AstType<'ast, Id>) = {
    <AppType> => (ArgType::Explicit, <>),
    "[" <l: @L> <typ: Type_>  <r: @R> "]" =>
        (ArgType::Implicit, AstType::new(arena, pos::spanned2(l, r, typ))),
};

// Patterns

PatternField : PatternField<'ast, Id> = {
    <name: Sp<Ident>> "=" <body: Sp<Pattern>> =>
        PatternField::Value { name, value: Some(body) },

    <ident: Sp<IdentStr>> => {
        let name = pos::spanned(ident.span, env.from_str(ident.value));
        if ident.value.starts_with(char::is_uppercase) {
            PatternField::Type { name }
        } else {
            PatternField::Value { name, value: None }
        }
    },
};

AtomicPattern: Pattern<'ast, Id> = {
    <l: @L> <id: Ident> <r: @R> "@" <pat: Sp<AtomicPattern>> =>
        Pattern::As(pos::spanned2(l, r, id), arena.alloc(pat)),

    <id: Ident> =>
        if env.string(&id).starts_with(char::is_uppercase) {
            Pattern::Constructor(new_ident(type_cache, id), &mut [])
        } else {
            Pattern::Ident(new_ident(type_cache, id))
        },

    <l: Literal> =>
        Pattern::Literal(l),

    "(" <elems: CommaSlice<Sp<Pattern>>> ")" =>
        match elems {
            // Parenthesized pattern
            [e] => mem::take(&mut e.value),
            _ => Pattern::Tuple { typ: type_cache.hole(), elems },
        },

    "{" <fields: CommaSlice<PatternField>> <implicit_import: Sp<"?"?>> "}" => {
        let implicit_import_span = implicit_import.span;

        Pattern::Record {
            typ: type_cache.hole(),
            fields,
            implicit_import: implicit_import
                .value
                .map(|_| pos::spanned(implicit_import_span, env.from_str(&format!("implicit?{}", implicit_import_span.start())))),
        }
    },
};

NoErrorPattern = {
    AtomicPattern,

    <id: Ident> <args: Many1<Sp<AtomicPattern>>> => {
        let id = new_ident(type_cache, id);

        Pattern::Constructor(id, args)
    },
};

Pattern = {
    NoErrorPattern,
    RecoverError => {
        debug!("Recovering from pattern error");
        Pattern::Error
    },
};

// Expressions

Literal: Literal = {
    "string literal" => Literal::String(<>.unescape()),
    "char literal" => Literal::Char(<>),
    "int literal" => Literal::Int(<>),
    "byte literal" => Literal::Byte(<>),
    "float literal" => Literal::Float(<>),
};

Alternative: () = {
    "|" <pat: Sp<Pattern>> "->" <expr: SpBlockExpr> => {
        temp_vecs.select().push(
            Alternative {
                pattern: pat,
                expr: super::shrink_hidden_spans(expr),
            }
        );
    },
    "|" <pat: Sp<NoErrorPattern>> RecoverError <end: @R>  => {
        let span = pos::Span::new(pat.span.end(), end);
        temp_vecs.select().push(
            Alternative {
                pattern: pat,
                expr: pos::spanned(span, Expr::Error(None)),
            }
        );
    },
    "|" <start: @R> RecoverError <end: @R>  => {
        let span = pos::Span::new(start, end);
        temp_vecs.select().push(
            Alternative {
                pattern: pos::spanned(span, Pattern::Error),
                expr: pos::spanned(span, Expr::Error(None)),
            }
        );
    },
};

FieldExpr: FieldExpr<'ast, Id> = {
    <metadata: Metadata> <id: Sp<Ident>> "=" <body: SpExpr> => {
        FieldExpr::Value(metadata, id, Some(body))
    },

    <metadata: Metadata> <id_str: Sp<IdentStr>> => {
        let id = pos::spanned(id_str.span, env.from_str(id_str.value));
        if id_str.value.starts_with(char::is_uppercase) {
            FieldExpr::Type(metadata, id, None)
        } else {
            FieldExpr::Value(metadata, id, None)
        }
    },
};

ValueArgument: Argument<SpannedIdent<Id>> = {
    <arg_type: "?"?> <name: SpannedIdent> => {
        Argument {
            arg_type: if arg_type.is_some() {
                ArgType::Implicit
            } else {
                ArgType::Explicit
            },
            name,
        }
    }
};

ValueBinding: &'ast mut ValueBinding<'ast, Id> = {
    <metadata: Metadata> "let" <name: Sp<AtomicPattern>> <typ: (":" <Type>)?> "=" <expr: SpExpr> => {
        arena.alloc(ValueBinding {
            metadata,
            name,
            typ,
            resolved_type: type_cache.hole(),
            args: Default::default(),
            expr,
        })
    },

    <metadata: Metadata> "let" <name: Sp<Ident>> <args: Many1<ValueArgument>> <typ: (":" <Type>)?> "=" <expr: SpExpr> =>
        arena.alloc(ValueBinding {
            metadata,
            name: name.map(|name| new_ident(type_cache, name)).map(Pattern::Ident),
            typ,
            resolved_type: type_cache.hole(),
            args,
            expr,
        }),

    // Error recovery

    <metadata: Metadata> "let" <name: Sp<Ident>> => {
        let span = pos::Span::new(name.span.end(), name.span.end());
        errors.push(::lalrpop_util::ParseError::UnrecognizedToken {
            token: (span.start(), Token::In, span.end()),
            expected: ["=", ":"].iter().map(|s| s.to_string()).collect(),
        });
        arena.alloc(ValueBinding {
            metadata,
            name: name.map(|name| new_ident(type_cache, name)).map(Pattern::Ident),
            typ: None,
            resolved_type: type_cache.hole(),
            args: Default::default(),
            expr: pos::spanned(span, Expr::Error(None)),
        })
    }
};

RecursiveValueBinding: () = {
    <metadata: Metadata> "let" <name: Sp<Ident>> <args: Many<ValueArgument>> <typ: (":" <Type>)?> "=" <expr: SpExpr> =>
        temp_vecs.select().push(
            ValueBinding {
                metadata,
                name: name.map(|name| new_ident(type_cache, name)).map(Pattern::Ident),
                typ,
                resolved_type: type_cache.hole(),
                args,
                expr,
            }
        ),
};

RecordExprBase: Option<SpannedExpr<'ast, Id>> = {
    ".." <SpExpr> => Some(<>),
    => None
};

AtomicExpr: Expr<'ast, Id> = {
    <id: Ident> =>
        Expr::Ident(new_ident(type_cache, id)),

    <lit: Literal> =>
        Expr::Literal(lit),

    // TODO: Getters
    // "(" "." <id: Ident> ")" =>
    //     Expr::Getter(id),

    <expr: SpAtomicExpr> "." <id: Ident> =>
        Expr::Projection(arena.alloc(expr), id, type_cache.hole()),

    <expr: SpAtomicExpr> "." RecoverError => {
        Expr::Projection(arena.alloc(expr), env.from_str(""), type_cache.hole())
    },

    "(" <elems: CommaSlice<SpExpr>> ")" =>
        Expr::Tuple { typ: type_cache.hole(), elems },

    "[" <exprs: CommaSlice<SpExpr>> "]" => Expr::Array(Array {
            typ: type_cache.hole(),
            exprs,
        }),

    "{" <fields: CommaTemp<FieldExpr>> <base: RecordExprBase> "}" => {
        let mut types = mem::take(temp_vecs.select());
        let mut values = mem::take(temp_vecs.select());

        for field in temp_vecs.drain(fields) {
            match field {
                FieldExpr::Type(metadata, id, typ) => types.push(ExprField {
                    metadata,
                    name: id,
                    value: typ
                }),
                FieldExpr::Value(metadata, id, expr) => values.push(ExprField {
                    metadata,
                    name: id,
                    value: expr
                }),
            }
        }

        let expr = Expr::Record {
            typ: type_cache.hole(),
            types: arena.alloc_extend(types.drain(..)),
            exprs: arena.alloc_extend(values.drain(..)),
            base: base.map(|e| arena.alloc(e)),
        };
        *temp_vecs.select() = types;
        *temp_vecs.select() = values;
        expr
    },
};

SpAtomicExpr: SpannedExpr<'ast, Id> = {
    <Sp<AtomicExpr>> => super::shrink_hidden_spans(<>)
};

ImplicitArg: SpannedExpr<'ast, Id> = {
    "?" <SpAtomicExpr>,
};

AppExpr = {
    AtomicExpr,

    <expr: SpAtomicExpr> <implicit_args: Many1<ImplicitArg>> =>
        Expr::App { func: arena.alloc(expr), implicit_args, args: &mut [] },

    <expr: SpAtomicExpr> <implicit_args: Many<ImplicitArg>> <args: Many1<SpAtomicExpr>> =>
        Expr::App { func: arena.alloc(expr), implicit_args, args },
};


LambdaArgument: Argument<SpannedIdent<Id>> = {
    <name: SpannedIdent> => {
        Argument::explicit(name)
    }
};

InfixExpr = {
    AppExpr,

    "\\" <args: Many1<LambdaArgument>> "->" <body: SpExpr> =>
        Expr::Lambda(Lambda {
            id: new_ident(type_cache, env.from_str("")),
            args,
            body: arena.alloc(body),
        }),

    <lhs: Sp<AppExpr>> <op: Sp<Operator>> <rhs: Sp<InfixExpr>> =>
        Expr::Infix { lhs: arena.alloc(lhs), op, rhs: arena.alloc(super::shrink_hidden_spans(rhs)), implicit_args: &mut [], },
};


InExpr: SpannedExpr<'ast, Id> = {
    "in" <SpExpr>,
    <err: Sp<RecoverError>> => {
        pos::spanned(err.span, Expr::Error(None))
    }
};

Expr: Expr<'ast, Id> = {
    InfixExpr,

    "if" <pred: SpExpr> "then" <if_true: SpExpr> "else" <if_false: SpExpr> =>
        Expr::IfElse(arena.alloc(pred), arena.alloc(if_true), arena.alloc(if_false)),

    "match" <body: SpExpr> "with" <arms: Alternative+> => {
        let arms: &mut [Alternative<_>] = arena.alloc_extend(temp_vecs.drain_n(arms.len()));
        Expr::Match(arena.alloc(body), arms)
    },

    <binding: ValueBinding> <body: InExpr> => {
        Expr::LetBindings(ValueBindings::Plain(binding), arena.alloc(body))
    },

    <binding: TypeBinding> <body: InExpr> => {
        Expr::TypeBindings(arena.alloc_extend(Some(binding)), arena.alloc(body))
    },

    <metadata: Metadata> "rec" <bindings: RecursiveValueBinding+> <body: InExpr> => {
        let bindings: &mut [ValueBinding<_>] = arena.alloc_extend(temp_vecs.drain_n(bindings.len()));
        bindings[0].metadata.merge(metadata);
        Expr::LetBindings(ValueBindings::Recursive(bindings), arena.alloc(body))
    },

    <metadata: Metadata> "rec" <bindings: Many1<TypeBinding>> <body: InExpr> => {
        bindings[0].metadata.merge(metadata);
        Expr::TypeBindings(bindings, arena.alloc(body))
    },

    DoExpression,

    BlockExpr,

    RecoverError => {
        Expr::Error(None)
    }
};

DoExpression: Expr<'ast, Id> = {
    "do" <bind: DoBinding> <body: SpExpr> => {
        let (id, typ, bound) = *bind;
        Expr::Do(arena.alloc(Do {
            id: Some(id),
            typ,
            bound: arena.alloc(bound),
            body: arena.alloc(body),
            flat_map_id: None,
        }))
    },

    "seq" <bound: SpExpr> <body: InExpr> => {
        Expr::Do(arena.alloc(Do {
            id: None,
            typ: None,
            bound: arena.alloc(bound),
            body: arena.alloc(body),
            flat_map_id: None,
        }))
    },
};


DoBinding: Box<(SpannedPattern<'ast, Id>, Option<AstType<'ast, Id>>, SpannedExpr<'ast, Id>)> = {
    <id: Sp<Pattern>> <typ: (":" <Type>)?>  "=" <bound: SpExpr> "in" => Box::new((id, typ, bound)),

    // Error recovery

    <id: Sp<Pattern>> "in" => {
        let span = pos::Span::new(id.span.end(), id.span.end());
        errors.push(::lalrpop_util::ParseError::UnrecognizedToken {
            token: (span.start(), Token::In, span.end()),
            expected: ["="].iter().map(|s| s.to_string()).collect(),
        });
        Box::new((id, None, pos::spanned(span, Expr::Error(None))))
    },
};

#[inline]
SpBlockExpr: SpannedExpr<'ast, Id> = {
    Sp<BlockExpr> => super::shrink_hidden_spans(<>),
};

BlockExpr: Expr<'ast, Id> = {
    "block open" <exprs: SepVec1<SpExpr, "block separator">> "block close" => {
        let mut iter = temp_vecs.drain(exprs).rev();
        let last = iter.next().unwrap();
        if iter.size_hint().0 == 0 {
            Expr::Block(arena.alloc_extend(Some(last)))
        } else {
            iter.fold(last, |body, expr| {
                pos::spanned2(
                    expr.span.start(),
                    body.span.end(),
                    Expr::Do(arena.alloc(Do { id: None, typ: None, bound: arena.alloc(expr), body: arena.alloc(body), flat_map_id: None })),
                )
            }).value
        }
    },
};

#[inline]
SpExpr: SpannedExpr<'ast, Id> = {
    <expr: Sp<Expr>> => super::shrink_hidden_spans(expr),
};

pub TopExpr: SpannedExpr<'ast, Id> = {
    "shebang line"? <expr: SpExpr> SkipExtraTokens => expr,
};

pub ReplLine: Option<Box<ReplLine<'ast, Id>>> = {
    <TopExpr> => Some(Box::new(ReplLine::Expr(<>))),
    "block open" <ValueBinding> "block close" => Some(Box::new(ReplLine::Let(<>))),
    => None,
};
