path: root/src/frontend/parse.rs

use crate::frontend::lex::*;
use crate::frontend::ast::*;
use crate::frontend::ast::Binding::*;
use crate::frontend::ast::Control::*;
use crate::frontend::ast::Pattern::*;
use Token::*;
use Literal::*;
use Punctuation::*;

struct Input(std::iter::Peekable<std::vec::IntoIter<Token>>);

impl Input {
    /// Map input.next() to return Results for use with the propagation operator
    fn next(&mut self) -> Result<Token> {
        self.0.next().ok_or("end of input".into())
    }

    /// Map input.peek() to return Results for use with the propagation operator
    fn peek(&mut self) -> Result<&Token> {
        self.0.peek().ok_or("end of input".into())
    }

    /// Asserts the next character to be a known token
    fn then(&mut self, expected: Token) -> Result<()> {
        match self.next()? {
            token if expected == token => Ok(()),
            token => Err(format!("expected token {} but found {}", expected, token).into())
        }
    }
}

/// Convert a basic TokenStream into an AbstractSyntaxTree
pub fn astify(input: TokenStream, name: &str) -> Result<Expr> {
    let mut input = Input(input.into_iter().peekable());
    let body = parse_body(&mut input)?;
    Ok(Expr::Binding(Module{ id: name.to_string(), body }))
}

/// Parse a series of Exprs, for ex. the body of a function.
/// Body ::= Expr | ('{' Expr (';' Expr)* '}')
fn parse_body(input: &mut Input) -> Result<Vec<Expr>> {
    let mut res = Vec::new();
    if input.peek()? != &Sep(ScopeLeftBrace) {
        res.push(parse_expr(input)?);
        return Ok(res);
    }
    input.then(Sep(ScopeLeftBrace))?;
    while input.peek()? != &Sep(ScopeRightBrace) {
        res.push(parse_expr(input)?);
        if input.peek()? == &Sep(Semicolon) {
            input.next()?;
        }
    }
    input.then(Sep(ScopeRightBrace))?;
    Ok(res)
}

/// Expr ::= Let | Var | Const | Func | Type | Mod | Import |
///   Block | Static | For | While | Loop | If | When | Try | Match
fn parse_expr(input: &mut Input) -> Result<Expr> {
    use Keyword::*;
    match input.next()? {
        Key(word) => match word {
            Pub => {
                match input.next()? {
                    Key(word) => match word {
                        Const => parse_const(input, true),
                        Func => parse_funcdecl(input, true),
                        Type => parse_typedecl(input, true),
                        Mod => parse_mod(input, true),
                        _ => return Err("unrecognized keyword following pub".into()),
                    }
                    _ => return Err("unrecognized thing following pub".into()),
                }
            },
            Let => parse_let(input),
            Var => parse_var(input),
            Const => parse_const(input, false),
            Func => parse_funcdecl(input, false),
            Type => parse_typedecl(input, false),
            Mod => parse_mod(input, false),
            From => parse_import(input, true), // todo: probably rework imports
            Import => parse_import(input, false),
            Block => parse_block(input),
            Static => parse_static(input),
            For => parse_for(input),
            While => parse_while(input),
            Loop => parse_loop(input),
            If => parse_if(input),
            When => parse_when(input),
            Try => parse_try(input),
            Match => parse_match(input),
            _ => return Err("invalid keyword starting expression".into()),
        },
        _ => todo!(), // what can i do with this?? match line here
    }
}

/// Let ::= 'let' Pattern Annotation? '=' Expr
fn parse_let(input: &mut Input) -> Result<Expr> {
    let id = parse_pattern(input)?;
    let kind = parse_annotation(input)?;
    input.then(Sep(Equals))?;
    let value = Box::new(parse_expr(input)?);
    Ok(Expr::Binding(Let { id, kind, value }))
}

/// Var ::= 'var' Pattern Annotation? ('=' Expr)?
fn parse_var(input: &mut Input) -> Result<Expr> {
    let id = parse_pattern(input)?;
    let kind = parse_annotation(input)?;
    let mut value = None;
    if input.next()? != Sep(Equals) {
        value = Some(Box::new(parse_expr(input)?));
    }
    Ok(Expr::Binding(Var { id, kind, value }))
}

/// Const ::= 'pub'? 'const' Pattern Annotation? '=' Expr
fn parse_const(input: &mut Input, public: bool) -> Result<Expr> {
    let id = parse_pattern(input)?;
    let kind = parse_annotation(input)?;
    input.then(Sep(Equals))?;
    let value = Box::new(parse_expr(input)?);
    Ok(Expr::Binding(Const { public, id, kind, value }))
}

/// Annotation ::= (':' TypeDesc)?
fn parse_annotation(input: &mut Input) -> Result<Option<Type>> {
    let mut kind = None;
    if input.peek()? == &Sep(Colon) {
        input.next()?;
        kind = Some(parse_type(input)?);
    }
    Ok(kind)
}

/// Func ::= 'pub'? 'func' Ident Generics? Parameters? (':' TypeDesc) '=' Body
fn parse_funcdecl(input: &mut Input, public: bool) -> Result<Expr> { todo!() }

/// TypeDecl ::= 'pub'? 'type' Pattern Generics? '=' 'distinct'? 'ref'? TypeDesc
fn parse_typedecl(input: &mut Input, public: bool) -> Result<Expr> {
    let pattern = parse_pattern(input)?;
    todo!()
}

/// Mod ::= 'pub'? 'mod' Ident ':' Body
fn parse_mod(input: &mut Input, public: bool) -> Result<Expr> {
    match input.next()? {
        Word(id) => {
            match input.next()? {
                Sep(Colon) => {
                    let body = parse_body(input)?;
                    Ok(Expr::Binding(Module { id, body }))
                },
                _ => return Err("unexpected token following mod label".into()),
            }
        },
        _ => return Err("unexpected thing following mod keyword".into()),
    }
}

/// Import ::= ('from' Ident)? 'import' Ident (',' Ident)* ('as' Ident)?
fn parse_import(input: &mut Input, from_scope: bool) -> Result<Expr> {
    let mut from = None;
    if from_scope {
        match input.next()? {
            Word(id) => from = Some(id),
            _ => return Err("identifier not following from keyword".into())
        }
        input.then(Key(Keyword::Import))?;
    }
    todo!()
}

/// Block ::= 'block' Ident? ':' Body
fn parse_block(input: &mut Input) -> Result<Expr> { // todo: body + offset
    match input.next()? {
        Sep(Colon) => {
            let id = None;
            let body = parse_body(input)?;
            Ok(Expr::Control(Block { id, body }))
        },
        Word(label) => {
            match input.next()? {
                Sep(Colon) => {
                    let id = Some(label);
                    let body = parse_body(input)?;
                    Ok(Expr::Control(Block { id, body }))
                },
                _ => return Err("unexpected token following block label".into()),
            }
        },
        _ => return Err("unexpected thing following block keyword".into()),
    }
}

/// Static ::= 'static' ':' Body
fn parse_static(input: &mut Input) -> Result<Expr> {
    input.then(Sep(Colon))?;
    let body = parse_body(input)?;
    Ok(Expr::Control(Static { body }))
}

/// For ::= 'for' Pattern 'in' Expr ':' Body
fn parse_for(input: &mut Input) -> Result<Expr> {
    let binding = parse_pattern(input)?;
    input.then(Key(Keyword::In))?;
    let range = Box::new(parse_expr(input)?);
    input.then(Sep(Colon))?;
    let body = parse_body(input)?;
    Ok(Expr::Control(For { binding, range, body }))
}

/// While ::= 'while' Expr ':' Body
fn parse_while(input: &mut Input) -> Result<Expr> {
    let cond = Box::new(parse_expr(input)?);
    input.then(Sep(Colon))?;
    let body = parse_body(input)?;
    Ok(Expr::Control(While { cond, body }))
}

/// Loop ::= 'loop' ':' Body
fn parse_loop(input: &mut Input) -> Result<Expr> {
    input.then(Sep(Colon))?;
    let body = parse_body(input)?;
    Ok(Expr::Control(Loop { body }))
}

/// If ::= 'if' CondBranch ('elif' CondBranch)* ('else' ':' Body)?
fn parse_if(input: &mut Input) -> Result<Expr> {
    let mut branches = Vec::new();
    branches.push(parse_cond_branch(input)?);
    while input.peek()? == &Key(Keyword::Elif) {
        input.next()?;
        branches.push(parse_cond_branch(input)?);
    }
    let mut else_body = None;
    if input.peek()? == &Key(Keyword::Else) {
        input.next()?;
        else_body = Some(parse_body(input)?);
    }
    Ok(Expr::Control(If { branches, else_body }))
}

// When ::= 'when' CondBranch ('elif' CondBranch)* ('else' ':' Body)?
fn parse_when(input: &mut Input) -> Result<Expr> {
    let mut branches = Vec::new();
    branches.push(parse_cond_branch(input)?);
    while input.peek()? == &Key(Keyword::Elif) {
        input.next()?;
        branches.push(parse_cond_branch(input)?);
    }
    let mut else_body = None;
    if input.peek()? == &Key(Keyword::Else) {
        input.next()?;
        input.then(Sep(Colon))?;
        else_body = Some(parse_body(input)?);
    }
    let mut body = Vec::new();
    body.push(Expr::Control(If { branches, else_body }));
    Ok(Expr::Control(Static { body }))
}

/// CondBranch ::= Expr ':' Body
fn parse_cond_branch(input: &mut Input) -> Result<CondBranch> {
    let cond = parse_expr(input)?;
    input.then(Sep(Colon))?;
    let body = parse_body(input)?;
    Ok(CondBranch { cond, body })
}

/// Try ::= 'try' ':' Body ('except' Ident (',' Ident)* ':' Body) ('finally' ':' Body)?
fn parse_try(input: &mut Input) -> Result<Expr> {
    input.then(Sep(Colon))?;
    let body = parse_body(input)?;
    let mut catches = Vec::new();
    while input.peek()? == &Key(Keyword::Catch) {
        input.next()?;
        todo!();
    }
    let mut finally = None;
    if input.peek()? == &Key(Keyword::Finally) {
        input.next()?;
        input.then(Sep(Colon))?;
        finally = Some(parse_body(input)?);
    }
    Ok(Expr::Control(Try { body, catches, finally }))
}

/// Match ::= 'match' Expr ('of' Pattern (',' Pattern)* ('where' Expr)? ':' Body)+
fn parse_match(input: &mut Input) -> Result<Expr> {
    let item = parse_pattern(input)?; // fixme
    let mut branches = Vec::new();
    while input.peek()? == &Key(Keyword::Of) {
        input.next()?;
        todo!();
    }
    Ok(Expr::Control(Match { item, branches }))
}

/// Type ::=
///   ('ref' | 'ptr' | 'mut' | 'static' | 'struct' | 'tuple' | 'enum' | 'union' | 'interface' | 'concept') |
///   ('ref' WrappedType) | ('ptr' WrappedType) | ('mut' WrappedType) | ('static' WrappedType) | ('distinct' WrappedType) |
///   StructType | TupleType | EnumType | UnionType | InterfaceType
/// The input stream must be normalized before attempting to parse types, because otherwise it's just a little bit hellish.
/// In particular: ref, ptr, mut, static, distinct must wrap their parameters in '[' ']' and all type declarations must be on one line.
fn parse_type(input: &mut Input) -> Result<Type> {
    use Type::*;
    match input.next()? {
        Key(word) => {
            match input.peek()? { // todo: check if the type is a special typeclass
                Sep(GenericLeftBracket) => (),
                _ => todo!() // ref, ptr, mut, static, struct, tuple, enum, union, interface, concept
            }
            match word {
                Keyword::Distinct => Ok(Distinct(Box::new(parse_wrapped_type(input)?))),
                Keyword::Ref => Ok(Reference(Box::new(parse_wrapped_type(input)?))),
                Keyword::Ptr => Ok(Pointer(Box::new(parse_wrapped_type(input)?))),
                Keyword::Var => Ok(Mutable(Box::new(parse_wrapped_type(input)?))),
                Keyword::Const => Ok(Static(Box::new(parse_wrapped_type(input)?))),
                Keyword::Struct => parse_struct_type(input),
                Keyword::Tuple => parse_tuple_type(input),
                Keyword::Enum => parse_enum_type(input),
                Keyword::Union => parse_union_type(input),
                Keyword::Interface => parse_interface(input),
                _ => return Err("invalid keyword present in type!".into())
            }
        },
        Word(id) => {
            let mut generics = Vec::new();
            if input.peek()? == &Sep(GenericLeftBracket) {
                generics = parse_generics(input)?;
            }
            Ok(Alias { id, generics })
        },
        _ => return Err("error".into())
    }
}

/// `StructType ::= ('struct' '[' Ident ':' Type (',' Ident ':' Type)* ']'`
fn parse_struct_type(input: &mut Input) -> Result<Type> { todo!() }
/// `TupleType ::= 'tuple' '[' (Ident ':')? Type (',' (Ident ':')? Type)* ']'`
fn parse_tuple_type(input: &mut Input) -> Result<Type> { todo!() }
/// `EnumType ::= 'enum' '[' Ident ('=' Pattern)? (Ident ('=' Pattern)?)* ']'`
fn parse_enum_type(input: &mut Input) -> Result<Type> { todo!() }
/// `UnionType ::= 'union' '[' Ident (':' Type)? (',' Ident (':' Type)?)* ']'`
fn parse_union_type(input: &mut Input) -> Result<Type> { todo!() }
/// `Interface ::= 'interface' '[' Signature (',' Signature)* ']'`
fn parse_interface(input: &mut Input) -> Result<Type> { todo!() }
/// `Signature ::= Ident ('[' Ident (':' Type)? (',' Ident (':' Type)?)* ']')? ('(' Type (',' Type)* ')')? (':' Type)?`
fn parse_signature(input: &mut Input) -> Result<Sig> { todo!() }

/// `WrappedType ::= Type | ('[' Type ']')`
fn parse_wrapped_type(input: &mut Input) -> Result<Type> {
    if input.next()? == Sep(GenericLeftBracket) {
        let result = parse_type(input)?;
        input.then(Sep(GenericRightBracket))?;
        Ok(result)
    } else {
        parse_type(input)
    }
}

/// `GenericType ::= '[' Type (',' Type)* ']'`
fn parse_generics(input: &mut Input) -> Result<Vec<Type>> { todo!() }

/// Pattern ::= Literal | Ident | '(' Pattern (',' Pattern)* ')' | Ident '(' Pattern (',' Pattern)* ')'
fn parse_pattern(input: &mut Input) -> Result<Pattern> { todo!() }

/// Literal ::= Char | String | Number | Float
fn parse_literal(input: &mut Input) -> Result<Pattern> { todo!() }