// See also: file:///usr/share/doc/python/html/reference/grammar.html?highlight=grammar
// See also: https://github.com/antlr/grammars-v4/blob/master/python3/Python3.g4
// See also: file:///usr/share/doc/python/html/reference/compound_stmts.html#function-definitions
// See also: https://greentreesnakes.readthedocs.io/en/latest/nodes.html#keyword

use std::iter::FromIterator;

use crate::ast;
use crate::fstring::parse_fstring;
use crate::lexer;

use num_bigint::BigInt;

grammar;

// This is a hack to reduce the amount of lalrpop tables generated:
// For each public entry point, a full parse table is generated.
// By having only a single pub function, we reduce this to one.
pub Top: ast::Top = {
    StartProgram <p:Program> => ast::Top::Program(p),
    StartStatement <s:Statement> => ast::Top::Statement(s),
    StartExpression <e:Expression> => ast::Top::Expression(e),
};

Program: ast::Program = {
    <lines:FileLine*> => ast::Program {
        statements: Vec::from_iter(lines.into_iter().flatten())
    },
};

// A file line either has a declaration, or an empty newline:
FileLine: Vec<ast::LocatedStatement> = {
    Statement,
    "\n" => vec![],
};

Suite: Vec<ast::LocatedStatement> = {
    SimpleStatement,
    "\n" indent <s:Statement+> dedent => s.into_iter().flatten().collect(),
};

Statement: Vec<ast::LocatedStatement> = {
    SimpleStatement,
    <s:CompoundStatement> => vec![s],
};

SimpleStatement: Vec<ast::LocatedStatement> = {
    <s1:SmallStatement> <s2:(";" SmallStatement)*> ";"? "\n" => {
        let mut statements = vec![s1];
        statements.extend(s2.into_iter().map(|e| e.1));
        statements
    }
};

SmallStatement: ast::LocatedStatement = {
    ExpressionStatement,
    PassStatement,
    DelStatement,
    FlowStatement,
    ImportStatement,
    GlobalStatement,
    NonlocalStatement,
    AssertStatement,
};

PassStatement: ast::LocatedStatement = {
    <loc:@L> "pass" => {
        ast::LocatedStatement {
            location: loc,
            node: ast::Statement::Pass,
        }
    },
};

DelStatement: ast::LocatedStatement = {
    <loc:@L> "del" <e:ExpressionList2> => {
        ast::LocatedStatement {
            location: loc,
            node: ast::Statement::Delete { targets: e },
        }
    },
};

ExpressionStatement: ast::LocatedStatement = {
    <loc:@L> <expr:TestOrStarExprList> <suffix:AssignSuffix*> => {
        // Just an expression, no assignment:
        if suffix.is_empty() {
            ast::LocatedStatement {
                location: loc.clone(),
                node: ast::Statement::Expression { expression: expr }
            }
        } else {
          let mut targets = vec![expr];
          let mut values = suffix;

          while values.len() > 1 {
                targets.push(values.remove(0));
          }

          let value = values.into_iter().next().unwrap();

          ast::LocatedStatement {
            location: loc.clone(),
            node: ast::Statement::Assign { targets, value },
          }
        }
    },
    <loc:@L> <expr:TestOrStarExprList> <op:AugAssign> <rhs:TestList> => {
        ast::LocatedStatement {
            location: loc,
            node: ast::Statement::AugAssign {
                target: Box::new(expr),
                op,
                value: Box::new(rhs)
            },
        }
    },
};

AssignSuffix: ast::Expression = {
    "=" <e:TestList> => e,
    "=" <e:YieldExpr> => e,
};

TestOrStarExprList: ast::Expression = {
    <elements:OneOrMore<TestOrStarExpr>> <comma:","?> => {
        if elements.len() == 1 && comma.is_none() {
            elements.into_iter().next().unwrap()
        } else {
            ast::Expression::Tuple { elements }
        }
    }
};

TestOrStarExpr: ast::Expression = {
    Test,
    StarExpr,
};

AugAssign: ast::Operator = {
    "+=" => ast::Operator::Add,
    "-=" => ast::Operator::Sub,
    "*=" => ast::Operator::Mult,
    "@=" => ast::Operator::MatMult,
    "/=" => ast::Operator::Div,
    "%=" => ast::Operator::Mod,
    "&=" => ast::Operator::BitAnd,
    "|=" => ast::Operator::BitOr,
    "^=" => ast::Operator::BitXor,
    "<<=" => ast::Operator::LShift,
    ">>=" => ast::Operator::RShift,
    "**=" => ast::Operator::Pow,
    "//=" => ast::Operator::FloorDiv,
};

FlowStatement: ast::LocatedStatement = {
    <loc:@L> "break" => {
        ast::LocatedStatement {
            location: loc,
            node: ast::Statement::Break,
        }
    },
    <loc:@L> "continue" => {
        ast::LocatedStatement {
            location: loc,
            node: ast::Statement::Continue,
        }
    },
    <loc:@L> "return" <t:TestList?> => {
        ast::LocatedStatement {
            location: loc,
            node: ast::Statement::Return { value: t.map(Box::new) },
        }
    },
    <loc:@L> <y:YieldExpr> => {
        ast::LocatedStatement {
            location: loc,
            node: ast::Statement::Expression { expression: y },
        }
    },
    RaiseStatement,
};

RaiseStatement: ast::LocatedStatement = {
    <loc:@L> "raise" => {
        ast::LocatedStatement {
            location: loc,
            node: ast::Statement::Raise { exception: None, cause: None },
        }
    },
    <loc:@L> "raise" <t:Test> <c:("from" Test)?> => {
        ast::LocatedStatement {
            location: loc,
            node: ast::Statement::Raise { exception: Some(t), cause: c.map(|x| x.1) },
        }
    },
};

ImportStatement: ast::LocatedStatement = {
  <loc:@L> "import" <i: Comma<ImportPart<<DottedName>>>> => {
    ast::LocatedStatement {
      location: loc,
      node: ast::Statement::Import {
        import_parts: i
            .iter()
            .map(|(n, a)|
                ast::SingleImport {
                    module: n.to_string(),
                    symbols: vec![],
                    alias: a.clone(),
                    level: 0,
                })
            .collect()
      },
    }
  },
  <loc:@L> "from" <n:ImportFromLocation> "import" <i: ImportAsNames> => {
    ast::LocatedStatement {
      location: loc,
      node: ast::Statement::Import {
        import_parts: vec![
            ast::SingleImport {
                module: n.0.to_string(),
                symbols: i.iter()
                    .map(|(i, a)|
                        ast::ImportSymbol {
                            symbol: i.to_string(),
                            alias: a.clone(),
                        })
                    .collect(),
                alias: None,
                level: n.1
        }]
      },
    }
  },
};

ImportFromLocation: (String, usize) = {
    <dots: "."*> <name:DottedName> => {
       (name, dots.len())
    },
    <dots: "."+> => {
       ("".to_string(), dots.len())
    },
};

ImportAsNames: Vec<(String, Option<String>)> = {
    <i:Comma<ImportPart<Identifier>>> => i,
    "(" <i:Comma<ImportPart<Identifier>>> ")" => i,
    "*" => {
        // Star import all
        vec![("*".to_string(), None)]
    },
};


#[inline]
ImportPart<I>: (String, Option<String>) = {
    <i:I> <a: ("as" Identifier)?> => (i, a.map(|a| a.1)),
};

// A name like abc or abc.def.ghi
DottedName: String = {
    <n:name> => n,
    <n:name> <n2: ("." Identifier)+>  => {
        let mut r = n.to_string();
        for x in n2 {
            r.push_str(".");
            r.push_str(&x.1);
        }
        r
    },
};

GlobalStatement: ast::LocatedStatement = {
    <loc:@L> "global" <names:OneOrMore<Identifier>> => {
        ast::LocatedStatement {
            location: loc,
            node: ast::Statement::Global { names }
        }
    },
};

NonlocalStatement: ast::LocatedStatement = {
    <loc:@L> "nonlocal" <names:OneOrMore<Identifier>> => {
        ast::LocatedStatement {
            location: loc,
            node: ast::Statement::Nonlocal { names }
        }
    },
};

AssertStatement: ast::LocatedStatement = {
    <loc:@L> "assert" <test:Test> <msg: ("," Test)?> => {
        ast::LocatedStatement {
          location: loc,
          node: ast::Statement::Assert {
            test, msg: msg.map(|e| e.1)
          }
        }
    },
};

CompoundStatement: ast::LocatedStatement = {
    IfStatement,
    WhileStatement,
    ForStatement,
    TryStatement,
    WithStatement,
    FuncDef,
    ClassDef,
};

IfStatement: ast::LocatedStatement = {
    <loc:@L> "if" <test:Test> ":" <s1:Suite> <s2:(@L "elif" Test ":" Suite)*> <s3:("else" ":" Suite)?> => {
        // Determine last else:
        let mut last = s3.map(|s| s.2);

        // handle elif:
        for i in s2.into_iter().rev() {
          let x = ast::LocatedStatement {
            location: i.0,
            node: ast::Statement::If { test: i.2, body: i.4, orelse: last },
          };
          last = Some(vec![x]);
        }

        ast::LocatedStatement {
            location: loc,
            node: ast::Statement::If { test, body: s1, orelse: last }
        }
    },
};

WhileStatement: ast::LocatedStatement = {
    <loc:@L> "while" <test:Test> ":" <body:Suite> <s2:("else" ":" Suite)?> => {
        let or_else = s2.map(|s| s.2);
        ast::LocatedStatement {
            location: loc,
            node: ast::Statement::While { test, body, orelse: or_else },
        }
    },
};

ForStatement: ast::LocatedStatement = {
    <loc:@L> <is_async:"async"?> "for" <target:ExpressionList> "in" <iter:TestList> ":" <body:Suite> <s2:("else" ":" Suite)?> => {
        let orelse = s2.map(|s| s.2);
        ast::LocatedStatement {
            location: loc,
            node: if is_async.is_some() {
                ast::Statement::AsyncFor { target, iter, body, orelse }
            } else {
                ast::Statement::For { target, iter, body, orelse }
            },
        }
    },
};

TryStatement: ast::LocatedStatement = {
    <loc:@L> "try" ":" <body:Suite> <handlers:ExceptClause*> <else_suite:("else" ":" Suite)?> <finally:("finally" ":" Suite)?> => {
        let or_else = else_suite.map(|s| s.2);
        let finalbody = finally.map(|s| s.2);
        ast::LocatedStatement {
            location: loc,
            node: ast::Statement::Try {
                body: body,
                handlers: handlers,
                orelse: or_else,
                finalbody: finalbody,
            },
        }
    },
};

ExceptClause: ast::ExceptHandler = {
    "except" <typ:Test?> ":" <body:Suite> => {
        ast::ExceptHandler {
            typ: typ,
            name: None,
            body: body,
        }
    },
    "except" <x:(Test "as" Identifier)> ":" <body:Suite> => {
        ast::ExceptHandler {
            typ: Some(x.0),
            name: Some(x.2),
            body: body,
        }
    },
};

WithStatement: ast::LocatedStatement = {
    <loc:@L> "with" <items:OneOrMore<WithItem>> ":" <s:Suite> => {
        ast::LocatedStatement {
            location: loc,
            node: ast::Statement::With { items: items, body: s },
        }
    },
};

WithItem: ast::WithItem = {
    <t:Test> <n:("as" Expression)?> => {
        let optional_vars = n.map(|val| val.1);
        ast::WithItem { context_expr: t, optional_vars }
    },
};

FuncDef: ast::LocatedStatement = {
    <d:Decorator*> <loc:@L> <is_async:"async"?> "def" <i:Identifier> <a:Parameters> <r:("->" Test)?> ":" <s:Suite> => {
        ast::LocatedStatement {
            location: loc,
            node: if is_async.is_some() {
                    ast::Statement::AsyncFunctionDef {
                        name: i,
                        args: a,
                        body: s,
                        decorator_list: d,
                        returns: r.map(|x| x.1),
                    }
                } else {
                    ast::Statement::FunctionDef {
                        name: i,
                        args: a,
                        body: s,
                        decorator_list: d,
                        returns: r.map(|x| x.1),
                    }
                }
        }
    },
};

Parameters: ast::Parameters = {
    "(" <a: (ParameterList<TypedParameter>)?> ")" => a.unwrap_or_else(Default::default),
};

// Note that this is a macro which is used once for function defs, and
// once for lambda defs.
ParameterList<ArgType>: ast::Parameters = {
    <param1:ParameterDefs<ArgType>> <args2:("," ParameterListStarArgs<ArgType>)?> ","? => {
        let (names, default_elements) = param1;

        // Now gather rest of parameters:
        let (vararg, kwonlyargs, kw_defaults, kwarg) = args2.map_or((None, vec![], vec![], None), |x| x.1);

        ast::Parameters {
            args: names,
            kwonlyargs: kwonlyargs,
            vararg: vararg.into(),
            kwarg: kwarg.into(),
            defaults: default_elements,
            kw_defaults: kw_defaults,
        }
    },
    <param1:ParameterDefs<ArgType>> <kw:("," KwargParameter<ArgType>)> ","? => {
        let (names, default_elements) = param1;

        // Now gather rest of parameters:
        let vararg = None;
        let kwonlyargs = vec![];
        let kw_defaults = vec![];
        let kwarg = Some(kw.1);

        ast::Parameters {
            args: names,
            kwonlyargs: kwonlyargs,
            vararg: vararg.into(),
            kwarg: kwarg.into(),
            defaults: default_elements,
            kw_defaults: kw_defaults,
        }
    },
    <params:ParameterListStarArgs<ArgType>> ","? => {
        let (vararg, kwonlyargs, kw_defaults, kwarg) = params;
        ast::Parameters {
            args: vec![],
            kwonlyargs: kwonlyargs,
            vararg: vararg.into(),
            kwarg: kwarg.into(),
            defaults: vec![],
            kw_defaults: kw_defaults,
        }
    },
    <kw:KwargParameter<ArgType>> ","? => {
        ast::Parameters {
            args: vec![],
            kwonlyargs: vec![],
            vararg: ast::Varargs::None,
            kwarg: Some(kw).into(),
            defaults: vec![],
            kw_defaults: vec![],
        }
    },
};

// Use inline here to make sure the "," is not creating an ambiguity.
#[inline]
ParameterDefs<ArgType>: (Vec<ast::Parameter>, Vec<ast::Expression>) = {
    <param1:ParameterDef<ArgType>> <param2:("," ParameterDef<ArgType>)*> => {
        // Combine first parameters:
        let mut args = vec![param1];
        args.extend(param2.into_iter().map(|x| x.1));

        let mut names = vec![];
        let mut default_elements = vec![];

        for (name, default) in args.into_iter() {
            if let Some(default) = default {
                default_elements.push(default);
            } else {
                if default_elements.len() > 0 {
                    // Once we have started with defaults, all remaining arguments must
                    // have defaults
                    panic!(
                        "non-default argument follows default argument: {}",
                        &name.arg
                    );
                }
            }
            names.push(name);
        }

        (names, default_elements)
    }
};

ParameterDef<ArgType>: (ast::Parameter, Option<ast::Expression>) = {
    <i:ArgType> => (i, None),
    <i:ArgType> "=" <e:Test> => (i, Some(e)),
};

UntypedParameter: ast::Parameter = {
    <i:Identifier> => ast::Parameter { arg: i, annotation: None },
};

TypedParameter: ast::Parameter = {
    <arg:Identifier> <a:(":" Test)?>=> {
        let annotation = a.map(|x| Box::new(x.1));
        ast::Parameter { arg, annotation }
    },
};

// Use inline here to make sure the "," is not creating an ambiguity.
// TODO: figure out another grammar that makes this inline no longer required.
#[inline]
ParameterListStarArgs<ArgType>: (Option<Option<ast::Parameter>>, Vec<ast::Parameter>, Vec<Option<ast::Expression>>, Option<Option<ast::Parameter>>) = {
    "*" <va:ArgType?> <kw:("," ParameterDef<ArgType>)*> <kwarg:("," KwargParameter<ArgType>)?> => {
        // Extract keyword arguments:
        let mut kwonlyargs = vec![];
        let mut kw_defaults = vec![];
        for (name, value) in kw.into_iter().map(|x| x.1) {
            kwonlyargs.push(name);
            kw_defaults.push(value);
        }

        let kwarg = kwarg.map(|n| n.1);

        (Some(va), kwonlyargs, kw_defaults, kwarg)
    }
};

KwargParameter<ArgType>: Option<ast::Parameter> = {
    "**" <kwarg:ArgType?> => {
        kwarg
    }
};

ClassDef: ast::LocatedStatement = {
    <d:Decorator*> <loc:@L> "class" <n:Identifier> <a:("(" ArgumentList ")")?> ":" <s:Suite> => {
        let (bases, keywords) = match a {
            Some((_, args, _)) => args,
            None => (vec![], vec![]),
        };
        ast::LocatedStatement {
            location: loc,
            node: ast::Statement::ClassDef {
              name: n,
              bases: bases,
              keywords: keywords,
              body: s,
              decorator_list: d,
            },
        }
    },
};

Path: ast::Expression = {
    <n:Identifier> => ast::Expression::Identifier { name: n },
    <p:Path> "." <n:name> => {
        ast::Expression::Attribute {
            value: Box::new(p),
            name: n,
        }
    },
};

// Decorators:
Decorator: ast::Expression = {
    "@" <p:Path> <a: ("(" ArgumentList ")")?> "\n" => {
        match a {
            Some((_, args, _)) => ast::Expression::Call {
                function: Box::new(p),
                args: args.0,
                keywords: args.1,
            },
            None => p,
        }
    },
};

YieldExpr: ast::Expression = {
    "yield" <value:TestList?> => ast::Expression::Yield { value: value.map(Box::new) },
    "yield" "from" <e:Test> => ast::Expression::YieldFrom { value: Box::new(e) },
};

Test: ast::Expression = {
    <expr:OrTest> <condition: ("if" OrTest "else" Test)?> => {
        if let Some(c) = condition {
            ast::Expression::IfExpression {
                test: Box::new(c.1),
                body: Box::new(expr),
                orelse: Box::new(c.3),
            }
        } else {
            expr
        }
    },
    LambdaDef,
};

LambdaDef: ast::Expression = {
    "lambda" <p:ParameterList<UntypedParameter>?> ":" <body:Test> =>
        ast::Expression::Lambda {
            args: p.unwrap_or(Default::default()),
            body: Box::new(body)
       }
}

OrTest: ast::Expression = {
    AndTest,
    <e1:OrTest> "or" <e2:AndTest> => ast::Expression::BoolOp { a: Box::new(e1), op: ast::BooleanOperator::Or, b: Box::new(e2) },
};

AndTest: ast::Expression = {
    NotTest,
    <e1:AndTest> "and" <e2:NotTest> => ast::Expression::BoolOp { a: Box::new(e1), op: ast::BooleanOperator::And, b: Box::new(e2) },
};

NotTest: ast::Expression = {
    "not" <e:NotTest> => ast::Expression::Unop { a: Box::new(e), op: ast::UnaryOperator::Not },
    Comparison,
};

Comparison: ast::Expression = {
    <e:Expression> <comparisons:(CompOp Expression)+> => {
        let mut vals = vec![e];
        let mut ops = vec![];
        for x in comparisons {
            ops.push(x.0);
            vals.push(x.1);
        }
        ast::Expression::Compare { vals, ops }
    },
    Expression,
};

CompOp: ast::Comparison = {
    "==" => ast::Comparison::Equal,
    "!=" => ast::Comparison::NotEqual,
    "<" => ast::Comparison::Less,
    "<=" => ast::Comparison::LessOrEqual,
    ">" => ast::Comparison::Greater,
    ">=" => ast::Comparison::GreaterOrEqual,
    "in" => ast::Comparison::In,
    "not" "in" => ast::Comparison::NotIn,
    "is" => ast::Comparison::Is,
    "is" "not" => ast::Comparison::IsNot,
};

Expression: ast::Expression = {
    <e1:Expression> "|" <e2:XorExpression> => ast::Expression::Binop { a: Box::new(e1), op: ast::Operator::BitOr, b: Box::new(e2) },
    XorExpression,
};

XorExpression: ast::Expression = {
    <e1:XorExpression> "^" <e2:AndExpression> => ast::Expression::Binop { a: Box::new(e1), op: ast::Operator::BitXor, b: Box::new(e2) },
    AndExpression,
};

AndExpression: ast::Expression = {
    <e1:AndExpression> "&" <e2:ShiftExpression> => ast::Expression::Binop { a: Box::new(e1), op: ast::Operator::BitAnd, b: Box::new(e2) },
    ShiftExpression,
};

ShiftExpression: ast::Expression = {
    <e1:ShiftExpression> <op:ShiftOp> <e2:ArithmaticExpression> => ast::Expression::Binop { a: Box::new(e1), op: op, b: Box::new(e2) },
    ArithmaticExpression,
};

ShiftOp: ast::Operator = {
    "<<" => ast::Operator::LShift,
    ">>" => ast::Operator::RShift,
};

ArithmaticExpression: ast::Expression = {
    <a:ArithmaticExpression> <op:AddOp> <b:Term> => ast::Expression::Binop { a: Box::new(a), op: op, b: Box::new(b) },
    Term,
};

AddOp: ast::Operator = {
    "+" => ast::Operator::Add,
    "-" => ast::Operator::Sub,
};

Term: ast::Expression = {
    <a:Term> <op:MulOp> <b:Factor> => ast::Expression::Binop { a: Box::new(a), op: op, b: Box::new(b) },
    Factor,
};

MulOp: ast::Operator = {
    "*" => ast::Operator::Mult,
    "/" => ast::Operator::Div,
    "//" => ast::Operator::FloorDiv,
    "%" => ast::Operator::Mod,
    "@" => ast::Operator::MatMult,
};

Factor: ast::Expression = {
    "+" <e:Factor> => ast::Expression::Unop { a: Box::new(e), op: ast::UnaryOperator::Pos },
    "-" <e:Factor> => ast::Expression::Unop { a: Box::new(e), op: ast::UnaryOperator::Neg },
    "~" <e:Factor> => ast::Expression::Unop { a: Box::new(e), op: ast::UnaryOperator::Inv },
    Power,
};

Power: ast::Expression = {
    <e:AtomExpr> <e2:("**" Factor)?> => {
        match e2 {
            None => e,
            Some(x) => ast::Expression::Binop { a: Box::new(e), op: ast::Operator::Pow, b: Box::new(x.1) },
        }
    }
};

AtomExpr: ast::Expression = {
    <is_await:"await"?> <atom:AtomExpr2> => {
        if is_await.is_some() {
            ast::Expression::Await { value: Box::new(atom) }
        } else {
            atom
        }
    }
}

AtomExpr2: ast::Expression = {
    Atom,
    <f:AtomExpr2> "(" <a:ArgumentList> ")" => ast::Expression::Call { function: Box::new(f), args: a.0, keywords: a.1 },
    <e:AtomExpr2> "[" <s:SubscriptList> "]" => ast::Expression::Subscript { a: Box::new(e), b: Box::new(s) },
    <e:AtomExpr2> "." <n:Identifier> => ast::Expression::Attribute { value: Box::new(e), name: n },
};

SubscriptList: ast::Expression = {
    <s1:Subscript> <s2:("," Subscript)*> ","? => {
        if s2.is_empty() {
            s1
        } else {
            let mut dims = vec![s1];
            for x in s2 {
                dims.push(x.1)
            }
            ast::Expression::Tuple { elements: dims }
        }
    }
};

Subscript: ast::Expression = {
    Test,
    <e1:Test?> ":" <e2:Test?> <e3:SliceOp?>  => {
        let s1 = e1.unwrap_or(ast::Expression::None);
        let s2 = e2.unwrap_or(ast::Expression::None);
        let s3 = e3.unwrap_or(ast::Expression::None);
        ast::Expression::Slice { elements: vec![s1, s2, s3] }
    }
};

SliceOp: ast::Expression = {
    ":" <e:Test?> => e.unwrap_or(ast::Expression::None)
}

Atom: ast::Expression = {
    <value:StringGroup> => ast::Expression::String { value },
    <value:Bytes> => ast::Expression::Bytes { value },
    <value:Number> => ast::Expression::Number { value },
    <name:Identifier> => ast::Expression::Identifier { name },
    "[" <e:TestListComp?> "]" => {
        let elements = e.unwrap_or(Vec::new());
        ast::Expression::List { elements }
    },
    "[" <e:TestListComp2> "]" => e,
    "(" <elements:TestList?> ")" => {
         elements.unwrap_or(ast::Expression::Tuple { elements: Vec::new() })
    },
    "(" <e:Test> <c:CompFor> ")" => {
        ast::Expression::Comprehension {
            kind: Box::new(ast::ComprehensionKind::GeneratorExpression { element: e }),
            generators: c,
        }
    },
    "{" <e:TestDict?> "}" => ast::Expression::Dict { elements: e.unwrap_or(Vec::new()) },
    "{" <e:TestDictComp> "}" => e,
    "{" <e:TestSet> "}" => ast::Expression::Set { elements: e },
    "{" <e:TestSetComp> "}" => e,
    "True" => ast::Expression::True,
    "False" => ast::Expression::False,
    "None" => ast::Expression::None,
    "..." => ast::Expression::Ellipsis,
};

TestListComp: Vec<ast::Expression> = {
    <e:OneOrMore<TestOrStarExpr>> <_trailing_comma:","?> => e,
};

TestListComp2: ast::Expression = {
    <e:TestOrStarExpr> <c:CompFor> => {
        ast::Expression::Comprehension {
            kind: Box::new(ast::ComprehensionKind::List { element: e }),
            generators: c,
        }
    },
};

TestDict: Vec<(Option<ast::Expression>, ast::Expression)> = {
    <elements:OneOrMore<DictElement>> <_trailing_comma:","?> => elements,
};

TestDictComp: ast::Expression = {
    <e1:DictEntry> <c:CompFor> => {
        ast::Expression::Comprehension {
            kind: Box::new(ast::ComprehensionKind::Dict { key: e1.0, value: e1.1 }),
            generators: c,
        }
    }
};

DictEntry: (ast::Expression, ast::Expression) = {
    <e1: Test> ":" <e2: Test> => (e1, e2),
};

DictElement: (Option<ast::Expression>, ast::Expression) = {
    <e:DictEntry> => (Some(e.0), e.1),
    "**" <e:Expression> => (None, e),
};

TestSet: Vec<ast::Expression> = {
    <e1:OneOrMore<Test>> ","? => e1
};

TestSetComp: ast::Expression = {
    <e1:Test> <c:CompFor> => {
        ast::Expression::Comprehension {
            kind: Box::new(ast::ComprehensionKind::Set { element: e1 }),
            generators: c,
        }
    }
};

ExpressionOrStarExpression = {
    Expression,
    StarExpr
};

ExpressionList: ast::Expression = {
    <elements: OneOrMore<ExpressionOrStarExpression>> <trailing_comma:","?> => {
        if elements.len() == 1 && trailing_comma.is_none() {
            elements.into_iter().next().unwrap()
        } else {
            ast::Expression::Tuple { elements }
        }
    },
};

ExpressionList2: Vec<ast::Expression> = {
    <elements:OneOrMore<Expression>> ","? => elements,
};

// A test list is one of:
// - a list of expressions
// - a single expression
// - a single expression followed by a trailing comma
TestList: ast::Expression = {
    <elements:OneOrMore<Test>> <trailing_comma: ","?> => {
        if elements.len() == 1 && trailing_comma.is_none() {
            elements.into_iter().next().unwrap()
        } else {
            ast::Expression::Tuple { elements }
        }
    }
};

// Test
StarExpr: ast::Expression = {
    "*" <e:Expression> => ast::Expression::Starred { value: Box::new(e) },
};

// Comprehensions:
CompFor: Vec<ast::Comprehension> = <c:SingleForComprehension+> => c;

SingleForComprehension: ast::Comprehension = {
    "for" <target:ExpressionList> "in" <iter:OrTest> <c2:ComprehensionIf*> => {
        ast::Comprehension { target, iter, ifs: c2 }
    }
};

ExpressionNoCond: ast::Expression = OrTest;
ComprehensionIf: ast::Expression = "if" <c:ExpressionNoCond> => c;

ArgumentList: (Vec<ast::Expression>, Vec<ast::Keyword>) = {
    <e: Comma<FunctionArgument>> => {
        let mut args = vec![];
        let mut keywords = vec![];
        for (name, value) in e {
            match name {
                Some(n) => {
                    keywords.push(ast::Keyword { name: n, value: value });
                },
                None => {
                    // Allow starred args after keyword arguments.
                    let is_starred = if let ast::Expression::Starred { .. } = &value {
                        true
                    } else {
                        false
                    };

                    if keywords.len() > 0 && !is_starred {
                        panic!("positional argument follows keyword argument {:?}", keywords);
                    };
                    args.push(value);
                },
            }
        }
        (args, keywords)
    }
};

FunctionArgument: (Option<Option<String>>, ast::Expression) = {
    <e:Test> <c:CompFor?> => {
        let expr = match c {
            Some(c) => ast::Expression::Comprehension {
                kind: Box::new(ast::ComprehensionKind::GeneratorExpression { element: e }),
                generators: c,
            },
            None => e,
        };
        (None, expr)
    },
    <i:Identifier> "=" <e:Test> => (Some(Some(i.clone())), e),
    "*" <e:Test> => (None, ast::Expression::Starred { value: Box::new(e) }),
    "**" <e:Test> => (Some(None), e),
};

Comma<T>: Vec<T> = {
    <items: (<T> ",")*> <last: T?> => {
        let mut items = items;
        items.extend(last);
        items
    }
};

#[inline]
OneOrMore<T>: Vec<T> = {
    <i1: T> <i2:("," T)*> => {
        let mut items = vec![i1];
        items.extend(i2.into_iter().map(|e| e.1));
        items
    }
};

Number: ast::Number = {
    <value:int> => { ast::Number::Integer { value } },
    <value:float> => { ast::Number::Float { value } },
    <s:complex> => { ast::Number::Complex { real: s.0, imag: s.1 } },
};

StringGroup: ast::StringGroup = {
    <s:string+> =>? {
        let mut values = vec![];
        for (value, is_fstring) in s {
            values.push(if is_fstring {
                parse_fstring(&value)?
            } else {
                ast::StringGroup::Constant { value }
            })
        }

        Ok(if values.len() > 1 {
            ast::StringGroup::Joined { values }
        } else {
            values.into_iter().next().unwrap()
        })
    },
};

Bytes: Vec<u8> = {
    <s:bytes+> => {
        s.into_iter().flatten().collect::<Vec<u8>>()
    },
};

Identifier: String = <s:name> => s;

// Hook external lexer:
extern {
    type Location = lexer::Location;
    type Error = lexer::LexicalError;

    enum lexer::Tok {
        indent => lexer::Tok::Indent,
        dedent => lexer::Tok::Dedent,
        StartProgram => lexer::Tok::StartProgram,
        StartStatement => lexer::Tok::StartStatement,
        StartExpression => lexer::Tok::StartExpression,
        "+" => lexer::Tok::Plus,
        "-" => lexer::Tok::Minus,
        "~" => lexer::Tok::Tilde,
        ":" => lexer::Tok::Colon,
        "." => lexer::Tok::Dot,
        "..." => lexer::Tok::Ellipsis,
        "," => lexer::Tok::Comma,
        "*" => lexer::Tok::Star,
        "**" => lexer::Tok::DoubleStar,
        "&" => lexer::Tok::Amper,
        "@" => lexer::Tok::At,
        "%" => lexer::Tok::Percent,
        "//" => lexer::Tok::DoubleSlash,
        "^" => lexer::Tok::CircumFlex,
        "|" => lexer::Tok::Vbar,
        "<<" => lexer::Tok::LeftShift,
        ">>" => lexer::Tok::RightShift,
        "/" => lexer::Tok::Slash,
        "(" => lexer::Tok::Lpar,
        ")" => lexer::Tok::Rpar,
        "[" => lexer::Tok::Lsqb,
        "]" => lexer::Tok::Rsqb,
        "{" => lexer::Tok::Lbrace,
        "}" => lexer::Tok::Rbrace,
        "=" => lexer::Tok::Equal,
        "+=" => lexer::Tok::PlusEqual,
        "-=" => lexer::Tok::MinusEqual,
        "*=" => lexer::Tok::StarEqual,
        "@=" => lexer::Tok::AtEqual,
        "/=" => lexer::Tok::SlashEqual,
        "%=" => lexer::Tok::PercentEqual,
        "&=" => lexer::Tok::AmperEqual,
        "|=" => lexer::Tok::VbarEqual,
        "^=" => lexer::Tok::CircumflexEqual,
        "<<=" => lexer::Tok::LeftShiftEqual,
        ">>=" => lexer::Tok::RightShiftEqual,
        "**=" => lexer::Tok::DoubleStarEqual,
        "//=" => lexer::Tok::DoubleSlashEqual,
        "==" => lexer::Tok::EqEqual,
        "!=" => lexer::Tok::NotEqual,
        "<" => lexer::Tok::Less,
        "<=" => lexer::Tok::LessEqual,
        ">" => lexer::Tok::Greater,
        ">=" => lexer::Tok::GreaterEqual,
        "->" => lexer::Tok::Rarrow,
        "and" => lexer::Tok::And,
        "as" => lexer::Tok::As,
        "assert" => lexer::Tok::Assert,
        "async" => lexer::Tok::Async,
        "await" => lexer::Tok::Await,
        "break" => lexer::Tok::Break,
        "class" => lexer::Tok::Class,
        "continue" => lexer::Tok::Continue,
        "def" => lexer::Tok::Def,
        "del" => lexer::Tok::Del,
        "elif" => lexer::Tok::Elif,
        "else" => lexer::Tok::Else,
        "except" => lexer::Tok::Except,
        "finally" => lexer::Tok::Finally,
        "for" => lexer::Tok::For,
        "from" => lexer::Tok::From,
        "global" => lexer::Tok::Global,
        "if" => lexer::Tok::If,
        "in" => lexer::Tok::In,
        "is" => lexer::Tok::Is,
        "import" => lexer::Tok::Import,
        "from" => lexer::Tok::From,
        "lambda" => lexer::Tok::Lambda,
        "nonlocal" => lexer::Tok::Nonlocal,
        "not" => lexer::Tok::Not,
        "or" => lexer::Tok::Or,
        "pass" => lexer::Tok::Pass,
        "raise" => lexer::Tok::Raise,
        "return" => lexer::Tok::Return,
        "try" => lexer::Tok::Try,
        "while" => lexer::Tok::While,
        "with" => lexer::Tok::With,
        "yield" => lexer::Tok::Yield,
        "True" => lexer::Tok::True,
        "False" => lexer::Tok::False,
        "None" => lexer::Tok::None,
        int => lexer::Tok::Int { value: <BigInt> },
        float => lexer::Tok::Float { value: <f64> },
        complex => lexer::Tok::Complex { real: <f64>, imag: <f64> },
        string => lexer::Tok::String { value: <String>, is_fstring: <bool> },
        bytes => lexer::Tok::Bytes { value: <Vec<u8>> },
        name => lexer::Tok::Name { name: <String> },
        "\n" => lexer::Tok::Newline,
        ";" => lexer::Tok::Semi,
    }
}