parser.lalrpop

use ast::*;
use lalrpop_intern::intern;

grammar;

pub Program: Program = {
    Items => Program { items: <> }
};

Items: Vec<Item> = {
    Item* => <>.into_iter().filter_map(|v| v).collect()
};

Item: Option<Item> = {
    Comment => None,
    StructDefn => Some(Item::StructDefn(<>)),
    TraitDefn => Some(Item::TraitDefn(<>)),
    Impl => Some(Item::Impl(<>)),
    Clause => Some(Item::Clause(<>)),
};

Comment: () = r"//.*";

pub Goal: Box<Goal> = {
    Goal1,
    <g1:Goal1> "," <g2:Goal> => Box::new(Goal::And(g1, g2)),
};

Goal1: Box<Goal> = {
    "forall" "<" <p:Comma<ParameterKind>> ">" "{" <g:Goal> "}" => Box::new(Goal::ForAll(p, g)),
    "exists" "<" <p:Comma<ParameterKind>> ">" "{" <g:Goal> "}" => Box::new(Goal::Exists(p, g)),
    "if" "(" <w:SemiColon<InlineClause>> ")" "{" <g:Goal> "}" => Box::new(Goal::Implies(w, g)),
    "not" "{" <g:Goal> "}" => Box::new(Goal::Not(g)),
    <w:WhereClause> => Box::new(Goal::Leaf(w)),
    "(" <Goal> ")",
};

ExternalKeyword: () = "extern";
AutoKeyword: () = "#" "[" "auto" "]";
MarkerKeyword: () = "#" "[" "marker" "]";
DerefLangItem: () = "#" "[" "lang_deref" "]";

StructDefn: StructDefn = {
    <external:ExternalKeyword?> "struct" <n:Id><p:Angle<ParameterKind>>
        <w:QuantifiedWhereClauses> "{" <f:Fields> "}" => StructDefn
    {
        name: n,
        parameter_kinds: p,
        where_clauses: w,
        fields: f,
        flags: StructFlags {
            external: external.is_some(),
        },
    }
};

TraitDefn: TraitDefn = {
    <external:ExternalKeyword?> <auto:AutoKeyword?> <marker:MarkerKeyword?> <deref:DerefLangItem?> "trait" <n:Id><p:Angle<ParameterKind>>
        <w:QuantifiedWhereClauses> "{" <a:AssocTyDefn*> "}" => TraitDefn
    {
        name: n,
        parameter_kinds: p,
        where_clauses: w,
        assoc_ty_defns: a,
        flags: TraitFlags {
            auto: auto.is_some(),
            marker: marker.is_some(),
            external: external.is_some(),
            deref: deref.is_some(),
        },
    }
};

AssocTyDefn: AssocTyDefn = {
    "type" <name:Id> <p:Angle<ParameterKind>> ";" => AssocTyDefn {
        name: name,
        parameter_kinds: p
    }
};

Impl: Impl = {
    "impl" <p:Angle<ParameterKind>> <mark:"!"?> <t:Id> <a:Angle<Parameter>> "for" <s:Ty>
        <w:QuantifiedWhereClauses> "{" <assoc:AssocTyValue*> "}" =>
    {
        let mut args = vec![Parameter::Ty(s)];
        args.extend(a);
        Impl {
            parameter_kinds: p,
            trait_ref: PolarizedTraitRef::from_bool(mark.is_none(), TraitRef {
                trait_name: t,
                args: args,
            }),
            where_clauses: w,
            assoc_ty_values: assoc,
        }
    },
};

ParameterKind: ParameterKind = {
    Id => ParameterKind::Ty(<>),
    LifetimeId => ParameterKind::Lifetime(<>),
};

AssocTyValue: AssocTyValue = {
    "type" <n:Id> <a:Angle<ParameterKind>> <wc:WhereClauses> "=" <v:Ty> ";" => AssocTyValue {
        name: n,
        parameter_kinds: a,
        value: v,
        where_clauses: wc,
    },
};

pub Ty: Ty = {
    "for" "<" <l:Comma<LifetimeId>> ">" <t:Ty> => Ty::ForAll {
        lifetime_names: l,
        ty: Box::new(t)
    },
    TyWithoutFor,
};

TyWithoutFor: Ty = {
    <n:Id> => Ty::Id { name: n},
    <n:Id> "<" <a:Comma<Parameter>> ">" => Ty::Apply { name: n, args: a },
    <p:ProjectionTy> => Ty::Projection { proj: p },
    <proj:UnselectedProjectionTy> => Ty::UnselectedProjection { <> },
    "(" <Ty> ")",
};

Lifetime: Lifetime = {
    <n:LifetimeId> => Lifetime::Id { name: n },
};

Parameter: Parameter = {
    Ty => Parameter::Ty(<>),
    Lifetime => Parameter::Lifetime(<>),
};

ProjectionTy: ProjectionTy = {
    "<" <t:TraitRef<"as">> ">" "::" <n:Id> <a:Angle<Parameter>> => ProjectionTy {
        trait_ref: t, name: n, args: a
    },
};

UnselectedProjectionTy: UnselectedProjectionTy = {
    <ty:TyWithoutFor> "::" <name:Id> <a:Angle<Parameter>> => {
        let mut args = a;
        args.push(Parameter::Ty(ty));
        UnselectedProjectionTy {
            name: name,
            args: args,
        }
    },
};

Fields: Vec<Field> = {
    <Comma<Field>>,
};

Field: Field = {
    <n:Id> ":" <t: Ty> => Field {
        name: n,
        ty: t,
    }
};

Clause: Clause = {
    "forall" <pk:Angle<ParameterKind>> "{" <wc:WhereClause> "if" <g:Comma<Goal1>> "}" => Clause {
        parameter_kinds: pk,
        consequence: wc,
        conditions: g,
    },

    "forall" <pk:Angle<ParameterKind>> "{" <wc:WhereClause> "}" => Clause {
        parameter_kinds: pk,
        consequence: wc,
        conditions: vec![],
    },
};

InlineClause1: Clause = {
    <wc:WhereClause> => Clause {
        parameter_kinds: vec![],
        consequence: wc,
        conditions: vec![],
    },

    <wc:WhereClause> ":" "-" <g:Comma<Goal1>> => Clause {
        parameter_kinds: vec![],
        consequence: wc,
        conditions: g,
    },
};

InlineClause: Clause = {
    <InlineClause1>,

    "forall" "<" <pk:Comma<ParameterKind>> ">" "{" <c:InlineClause1> "}" => Clause {
        parameter_kinds: pk,
        consequence: c.consequence,
        conditions: c.conditions,
    }
};

WhereClauses: Vec<WhereClause> = {
    "where" <Comma<WhereClause>>,
    () => vec![],
};

QuantifiedWhereClauses: Vec<QuantifiedWhereClause> = {
    "where" <Comma<QuantifiedWhereClause>>,
    () => vec![],
};

WhereClause: WhereClause = {
    <t:TraitRef<":">> => WhereClause::Implemented { trait_ref: t },

    "WellFormed" "(" <t:Ty> ")" => WhereClause::TyWellFormed { ty: t },

    "WellFormed" "(" <t:TraitRef<":">> ")" => WhereClause::TraitRefWellFormed { trait_ref: t },

    "FromEnv" "(" <t:Ty> ")" => WhereClause::TyFromEnv { ty: t },

    "FromEnv" "(" <t:TraitRef<":">> ")" => WhereClause::TraitRefFromEnv { trait_ref: t },

    <a:Ty> "=" <b:Ty> => WhereClause::UnifyTys { a, b },

    <a:Lifetime> "=" <b:Lifetime> => WhereClause::UnifyLifetimes { a, b },

    // `<T as Foo>::U -> Bar` -- a normalization
    "Normalize" "(" <s:ProjectionTy> "->" <t:Ty> ")" => WhereClause::Normalize { projection: s, ty: t },

    // `T: Foo<U = Bar>` -- projection equality
    <s:Ty> ":" <t:Id> "<" <a:(<Comma<Parameter>> ",")?> <name:Id> <a2:Angle<Parameter>>
        "=" <ty:Ty> ">" =>
    {
        let mut args = vec![Parameter::Ty(s)];
        if let Some(a) = a { args.extend(a); }
        let trait_ref = TraitRef { trait_name: t, args: args };
        let projection = ProjectionTy { trait_ref, name, args: a2 };
        WhereClause::ProjectionEq { projection, ty }
    },

    "InScope" "(" <t:Id> ")" => WhereClause::TraitInScope { trait_name: t },
    "Derefs" "(" <source:Ty> "," <target:Ty> ")" => WhereClause::Derefs { source, target },
};

QuantifiedWhereClause: QuantifiedWhereClause = {
    <wc:WhereClause> => QuantifiedWhereClause {
        parameter_kinds: vec![],
        where_clause: wc,
    },

    "forall" "<" <pk:Comma<ParameterKind>> ">" <wc:WhereClause> => QuantifiedWhereClause {
        parameter_kinds: pk,
        where_clause: wc,
    },
};

TraitRef<S>: TraitRef = {
    <s:Ty> S <t:Id> <a:Angle<Parameter>> => {
        let mut args = vec![Parameter::Ty(s)];
        args.extend(a);
        TraitRef {
            trait_name: t,
            args: args,
        }
    },
};

Separator<S, T>: Vec<T> = {
    Separator1<S, T>? => <>.unwrap_or(vec![])
};

Separator1<S, T>: Vec<T> = {
    <t:T> => vec![t],
    <v:Separator<S, T>> S <t:T> => {
        let mut v = v;
        v.push(t);
        v
    }
};

#[inline]
Comma<T>: Vec<T> = {
    <Separator<",", T>>
};

#[inline]
SemiColon<T>: Vec<T> = {
    <Separator<";", T>>
};

Angle<T>: Vec<T> = {
    "<" <Comma<T>> ">",
    () => vec![],
};

Id: Identifier = {
    <l:@L> <s:r"([A-Za-z]|_)([A-Za-z0-9]|_)*"> <r:@R> => Identifier {
        str: intern(s),
        span: Span::new(l, r),
    }
};

LifetimeId: Identifier = {
    <l:@L> <s:r"'([A-Za-z]|_)([A-Za-z0-9]|_)*"> <r:@R> => Identifier {
        str: intern(s),
        span: Span::new(l, r),
    }
};