somni_parser/

parser.rs

//! Grammar parser.
//!
//! This module parses the following grammar (minus comments, which are ignored):
//!
//! ```text
//! program -> item* EOF;
//! item -> function | global | extern_fn | struct_def; // TODO types.
//!
//! extern_fn -> 'extern' 'fn' identifier '(' function_argument ( ',' function_argument )* ','? ')' return_decl? ;
//! global -> 'var' identifier ':' type '=' static_initializer ';' ;
//!
//! struct_def -> 'struct' identifier '{' ( struct_field ( ',' struct_field )* ','? )? '}' ;
//! struct_field -> identifier ':' type ;
//!
//! static_initializer -> right_hand_expression ; // The language does not currently support function calls.
//!
//! function -> 'fn' identifier '(' function_argument ( ',' function_argument )* ','? ')' return_decl? body ;
//! function_argument -> identifier ':' '&'? type ;
//! return_decl -> '->' type ;
//! type -> identifier ;
//!
//! body -> '{' statement '}' ;
//! statement -> 'var' identifier (':' type)? '=' right_hand_expression ';' (statement)?
//!            | 'return' right_hand_expression? ';' (statement)?
//!            | 'break' ';' (statement)?
//!            | 'continue' ';' (statement)?
//!            | 'if' condition body ( 'else' body )? (statement)?
//!            | 'loop' body (statement)?
//!            | 'while' condition body (statement)?
//!            | 'for' identifier ( ':' type )? 'in' condition body (statement)?
//!            | body (statement)?
//!            | expression ';' (statement)?
//!            | right_hand_expression // implicit return statmenet
//!
//! expression -> (left_hand_expression '=')? right_hand_expression ;
//!
//! // A place: a variable, a whole-value dereference, or a path of field accesses.
//! left_hand_expression -> '*' identifier
//!                       | identifier ( '.' identifier )* ; // Should be a valid expression, too.
//!
//! // `condition` (used by `if`/`while`/`for`) is identical to `right_hand_expression`
//! // except a *top-level* struct literal is not allowed, so a `{` unambiguously begins
//! // the following block. Struct literals remain reachable inside parentheses.
//! right_hand_expression -> binary2 ( '||' binary2 )* ;
//! condition             -> right_hand_expression ; // minus a top-level struct_literal in `primary`
//! binary2 -> binary3 ( '&&' binary3 )* ;
//! binary3 -> binary4 ( ( '<' | '<=' | '>' | '>=' | '==' | '!=' ) binary4 )* ;
//! binary4 -> binary5 ( '|' binary5 )* ;
//! binary5 -> binary6 ( '^' binary6 )* ;
//! binary6 -> binary7 ( '&' binary7 )* ;
//! binary7 -> binary8 ( ( '<<' | '>>' ) binary8 )* ;
//! binary8 -> binary9 ( ( '+' | '-' ) binary9 )* ;
//! binary9 -> unary ( ( '*' | '/', '%' ) unary )* ;
//! unary -> ('!' | '-' | '&' | '*' )* postfix ;
//! postfix -> primary ( '.' identifier )* ; // field access binds tighter than any unary prefix
//! primary -> literal
//!          | identifier struct_literal        // only where struct literals are allowed (see `condition`)
//!          | identifier ( '(' call_arguments ')' )?
//!          | '(' right_hand_expression ')' ;
//! struct_literal -> '{' ( struct_literal_field ( ',' struct_literal_field )* ','? )? '}' ;
//! struct_literal_field -> identifier ':' right_hand_expression ;
//! call_arguments -> right_hand_expression ( ',' right_hand_expression )* ','? ;
//! literal -> NUMBER | STRING | 'true' | 'false' ;
//! ```
//!
//! `NUMBER`: Non-negative integers (binary, decimal, hexadecimal) and floats.
//! `STRING`: Double-quoted strings with escape sequences.

use std::{
    fmt::{Debug, Display},
    num::{ParseFloatError, ParseIntError},
    ops::ControlFlow,
};

use crate::{
    Error, Location,
    ast::{
        Body, Break, Continue, Else, EmptyReturn, Expression, ExternalFunction, For, Function,
        FunctionArgument, GlobalVariable, If, Item, LeftHandExpression, Literal, LiteralValue,
        Loop, Program, ReturnDecl, ReturnWithValue, RightHandExpression, Statement, StructDef,
        StructField, StructLiteralField, TypeHint, VariableDefinition,
    },
    lexer::{Token, TokenKind, Tokenizer},
    parser::private::Sealed,
};

mod private {
    pub trait Sealed {}

    impl Sealed for u32 {}
    impl Sealed for u64 {}
    impl Sealed for u128 {}
    impl Sealed for f32 {}
    impl Sealed for f64 {}
}

/// Parse literals into Somni integers.
pub trait IntParser: Sized + Sealed {
    fn parse(str: &str, radix: u32) -> Result<Self, ParseIntError>;
}

impl IntParser for u32 {
    fn parse(str: &str, radix: u32) -> Result<Self, ParseIntError> {
        u32::from_str_radix(str, radix)
    }
}
impl IntParser for u64 {
    fn parse(str: &str, radix: u32) -> Result<Self, ParseIntError> {
        u64::from_str_radix(str, radix)
    }
}
impl IntParser for u128 {
    fn parse(str: &str, radix: u32) -> Result<Self, ParseIntError> {
        u128::from_str_radix(str, radix)
    }
}

/// Parse literals into Somni floats.
pub trait FloatParser: Sized + Sealed {
    fn parse(str: &str) -> Result<Self, ParseFloatError>;
}

impl FloatParser for f32 {
    fn parse(str: &str) -> Result<Self, ParseFloatError> {
        str.parse::<f32>()
    }
}
impl FloatParser for f64 {
    fn parse(str: &str) -> Result<Self, ParseFloatError> {
        str.parse::<f64>()
    }
}

/// Defines the numeric types used in the parser.
pub trait TypeSet: Debug + Default {
    type Integer: IntParser + Clone + Copy + PartialEq + Debug;
    type Float: FloatParser + Clone + Copy + PartialEq + Debug;
}

/// Use 64-bit integers and 64-bit floats (default).
#[derive(Debug, Default)]
pub struct DefaultTypeSet;
impl Sealed for DefaultTypeSet {}

impl TypeSet for DefaultTypeSet {
    type Integer = u64;
    type Float = f64;
}

/// Use 32-bit integers and floats.
#[derive(Debug, Default)]
pub struct TypeSet32;
impl Sealed for TypeSet32 {}
impl TypeSet for TypeSet32 {
    type Integer = u32;
    type Float = f32;
}

/// Use 128-bit integers and 64-bit floats.
#[derive(Debug, Default)]
pub struct TypeSet128;
impl Sealed for TypeSet128 {}
impl TypeSet for TypeSet128 {
    type Integer = u128;
    type Float = f64;
}

impl<T> Program<T>
where
    T: TypeSet,
{
    fn parse(stream: &mut TokenStream<'_, impl Tokenizer>) -> Result<Self, Error> {
        let mut items = Vec::new();

        while !stream.end()? {
            items.push(Item::parse(stream)?);
        }

        Ok(Program { items })
    }
}

impl<T> Item<T>
where
    T: TypeSet,
{
    fn parse(stream: &mut TokenStream<'_, impl Tokenizer>) -> Result<Self, Error> {
        if let Some(struct_def) = StructDef::try_parse(stream)? {
            return Ok(Item::Struct(struct_def));
        }
        if let Some(global_var) = GlobalVariable::try_parse(stream)? {
            return Ok(Item::GlobalVariable(global_var));
        }
        if let Some(function) = ExternalFunction::try_parse(stream)? {
            return Ok(Item::ExternFunction(function));
        }
        if let Some(function) = Function::try_parse(stream)? {
            return Ok(Item::Function(function));
        }

        Err(stream.error("Expected global variable, function, or struct definition"))
    }
}

impl StructDef {
    fn try_parse(stream: &mut TokenStream<'_, impl Tokenizer>) -> Result<Option<Self>, Error> {
        let Some(struct_token) = stream.take_match(TokenKind::Identifier, &["struct"])? else {
            return Ok(None);
        };

        let name = stream.expect_match(TokenKind::Identifier, &[])?;
        let opening_brace = stream.expect_match(TokenKind::Symbol, &["{"])?;

        let mut fields = Vec::new();
        while let Some(field_name) = stream.take_match(TokenKind::Identifier, &[])? {
            let colon = stream.expect_match(TokenKind::Symbol, &[":"])?;
            let field_type = TypeHint::parse(stream)?;

            fields.push(StructField {
                name: field_name,
                colon,
                field_type,
            });

            if stream.take_match(TokenKind::Symbol, &[","])?.is_none() {
                break;
            }
        }

        let closing_brace = stream.expect_match(TokenKind::Symbol, &["}"])?;

        Ok(Some(StructDef {
            struct_token,
            name,
            opening_brace,
            fields,
            closing_brace,
        }))
    }
}

impl<T> GlobalVariable<T>
where
    T: TypeSet,
{
    fn try_parse(stream: &mut TokenStream<'_, impl Tokenizer>) -> Result<Option<Self>, Error> {
        let Some(decl_token) = stream.take_match(TokenKind::Identifier, &["var"])? else {
            return Ok(None);
        };

        let identifier = stream.expect_match(TokenKind::Identifier, &[])?;
        let colon = stream.expect_match(TokenKind::Symbol, &[":"])?;
        let type_token = TypeHint::parse(stream)?;
        let equals_token = stream.expect_match(TokenKind::Symbol, &["="])?;
        let initializer = Expression::Expression {
            expression: RightHandExpression::parse(stream)?,
        };
        let semicolon = stream.expect_match(TokenKind::Symbol, &[";"])?;

        Ok(Some(GlobalVariable {
            decl_token,
            identifier,
            colon,
            type_token,
            equals_token,
            initializer,
            semicolon,
        }))
    }
}

impl ExternalFunction {
    fn try_parse(stream: &mut TokenStream<'_, impl Tokenizer>) -> Result<Option<Self>, Error> {
        let Some(extern_fn_token) = stream.take_match(TokenKind::Identifier, &["extern"])? else {
            return Ok(None);
        };
        let Some(fn_token) = stream.take_match(TokenKind::Identifier, &["fn"])? else {
            return Ok(None);
        };

        let name = stream.expect_match(TokenKind::Identifier, &[])?;
        let opening_paren = stream.expect_match(TokenKind::Symbol, &["("])?;

        let mut arguments = Vec::new();
        while let Some(arg_name) = stream.take_match(TokenKind::Identifier, &[])? {
            let colon = stream.expect_match(TokenKind::Symbol, &[":"])?;
            let reference_token = stream.take_match(TokenKind::Symbol, &["&"])?;
            let type_token = TypeHint::parse(stream)?;

            arguments.push(FunctionArgument {
                name: arg_name,
                colon,
                reference_token,
                arg_type: type_token,
            });

            if stream.take_match(TokenKind::Symbol, &[","])?.is_none() {
                break;
            }
        }

        let closing_paren = stream.expect_match(TokenKind::Symbol, &[")"])?;

        let return_decl =
            if let Some(return_token) = stream.take_match(TokenKind::Symbol, &["->"])? {
                Some(ReturnDecl {
                    return_token,
                    return_type: TypeHint::parse(stream)?,
                })
            } else {
                None
            };

        let semicolon = stream.expect_match(TokenKind::Symbol, &[";"])?;

        Ok(Some(ExternalFunction {
            extern_fn_token,
            fn_token,
            name,
            opening_paren,
            arguments,
            closing_paren,
            return_decl,
            semicolon,
        }))
    }
}

impl<T> Function<T>
where
    T: TypeSet,
{
    fn try_parse(stream: &mut TokenStream<'_, impl Tokenizer>) -> Result<Option<Self>, Error> {
        let Some(fn_token) = stream.take_match(TokenKind::Identifier, &["fn"])? else {
            return Ok(None);
        };

        let name = stream.expect_match(TokenKind::Identifier, &[])?;
        let opening_paren = stream.expect_match(TokenKind::Symbol, &["("])?;

        let mut arguments = Vec::new();
        while let Some(arg_name) = stream.take_match(TokenKind::Identifier, &[])? {
            let colon = stream.expect_match(TokenKind::Symbol, &[":"])?;
            let reference_token = stream.take_match(TokenKind::Symbol, &["&"])?;
            let type_token = TypeHint::parse(stream)?;

            arguments.push(FunctionArgument {
                name: arg_name,
                colon,
                reference_token,
                arg_type: type_token,
            });

            if stream.take_match(TokenKind::Symbol, &[","])?.is_none() {
                break;
            }
        }

        let closing_paren = stream.expect_match(TokenKind::Symbol, &[")"])?;

        let return_decl =
            if let Some(return_token) = stream.take_match(TokenKind::Symbol, &["->"])? {
                Some(ReturnDecl {
                    return_token,
                    return_type: TypeHint::parse(stream)?,
                })
            } else {
                None
            };

        let body = Body::parse(stream)?;

        Ok(Some(Function {
            fn_token,
            name,
            opening_paren,
            arguments,
            closing_paren,
            return_decl,
            body,
        }))
    }
}

impl<T> Body<T>
where
    T: TypeSet,
{
    fn parse(stream: &mut TokenStream<'_, impl Tokenizer>) -> Result<Self, Error> {
        let opening_brace = stream.expect_match(TokenKind::Symbol, &["{"])?;

        let mut body = Vec::new();
        while Statement::<T>::matches(stream)? {
            let (statement, stop) = match Statement::parse(stream)? {
                ControlFlow::Continue(statement) => (statement, false),
                ControlFlow::Break(statement) => (statement, true),
            };
            body.push(statement);
            if stop {
                break;
            }
        }

        let closing_brace = stream.expect_match(TokenKind::Symbol, &["}"])?;

        Ok(Body {
            opening_brace,
            statements: body,
            closing_brace,
        })
    }
}

impl TypeHint {
    fn parse(stream: &mut TokenStream<'_, impl Tokenizer>) -> Result<Self, Error> {
        let type_name = stream.expect_match(TokenKind::Identifier, &[])?;

        Ok(TypeHint { type_name })
    }
}

impl<T> Statement<T>
where
    T: TypeSet,
{
    fn matches(stream: &mut TokenStream<'_, impl Tokenizer>) -> Result<bool, Error> {
        stream
            .peek_match(TokenKind::Symbol, &["}"])
            .map(|t| t.is_none())
    }

    fn parse(
        stream: &mut TokenStream<'_, impl Tokenizer>,
    ) -> Result<ControlFlow<Self, Self>, Error> {
        if let Some(return_token) = stream.take_match(TokenKind::Identifier, &["return"])? {
            let return_kind =
                if let Some(semicolon) = stream.take_match(TokenKind::Symbol, &[";"])? {
                    // Continue, parsing unreachable code is allowed
                    Statement::EmptyReturn(EmptyReturn {
                        return_token,
                        semicolon,
                    })
                } else {
                    let expr = RightHandExpression::parse(stream)?;
                    let semicolon = stream.expect_match(TokenKind::Symbol, &[";"])?;
                    Statement::Return(ReturnWithValue {
                        return_token,
                        expression: expr,
                        semicolon,
                    })
                };

            // Continue, parsing unreachable code is allowed
            return Ok(ControlFlow::Continue(return_kind));
        }

        if let Some(decl_token) = stream.take_match(TokenKind::Identifier, &["var"])? {
            let identifier = stream.expect_match(TokenKind::Identifier, &[])?;

            let type_token = if stream.take_match(TokenKind::Symbol, &[":"])?.is_some() {
                Some(TypeHint::parse(stream)?)
            } else {
                None
            };

            let equals_token = stream.expect_match(TokenKind::Symbol, &["="])?;
            let expression = RightHandExpression::parse(stream)?;
            let semicolon = stream.expect_match(TokenKind::Symbol, &[";"])?;

            return Ok(ControlFlow::Continue(Statement::VariableDefinition(
                VariableDefinition {
                    decl_token,
                    identifier,
                    type_token,
                    equals_token,
                    initializer: expression,
                    semicolon,
                },
            )));
        }

        if let Some(if_token) = stream.take_match(TokenKind::Identifier, &["if"])? {
            let condition = RightHandExpression::parse_no_struct(stream)?;
            let body = Body::parse(stream)?;

            let else_branch =
                if let Some(else_token) = stream.take_match(TokenKind::Identifier, &["else"])? {
                    let else_body = Body::parse(stream)?;

                    Some(Else {
                        else_token,
                        else_body,
                    })
                } else {
                    None
                };

            return Ok(ControlFlow::Continue(Statement::If(If {
                if_token,
                condition,
                body,
                else_branch,
            })));
        }

        if let Some(loop_token) = stream.take_match(TokenKind::Identifier, &["loop"])? {
            let body = Body::parse(stream)?;
            return Ok(ControlFlow::Continue(Statement::Loop(Loop {
                loop_token,
                body,
            })));
        }

        if let Some(while_token) = stream.take_match(TokenKind::Identifier, &["while"])? {
            // Desugar while into loop { if condition { loop_body; } else { break; } }
            let condition = RightHandExpression::parse_no_struct(stream)?;
            let body = Body::parse(stream)?;
            return Ok(ControlFlow::Continue(Statement::Loop(Loop {
                loop_token: while_token,
                body: Body {
                    opening_brace: body.opening_brace,
                    closing_brace: body.closing_brace,
                    statements: vec![Statement::If(If {
                        if_token: while_token,
                        condition: condition.clone(),
                        body: body.clone(),
                        else_branch: Some(Else {
                            else_token: while_token,
                            else_body: Body {
                                opening_brace: body.opening_brace,
                                closing_brace: body.closing_brace,
                                statements: vec![Statement::Break(Break {
                                    break_token: while_token,
                                    semicolon: while_token,
                                })],
                            },
                        }),
                    })],
                },
            })));
        }

        if let Some(for_token) = stream.take_match(TokenKind::Identifier, &["for"])? {
            let variable = stream.expect_match(TokenKind::Identifier, &[])?;
            // The `: type` annotation is optional; when omitted the loop
            // variable's type is inferred from its usage in the body.
            let var_type = match stream.take_match(TokenKind::Symbol, &[":"])? {
                Some(_) => Some(TypeHint::parse(stream)?),
                None => None,
            };
            let in_token = stream.expect_match(TokenKind::Identifier, &["in"])?;
            let iterable = RightHandExpression::parse_no_struct(stream)?;
            let body = Body::parse(stream)?;

            return Ok(ControlFlow::Continue(Statement::For(For {
                for_token,
                variable,
                var_type,
                in_token,
                iterable,
                body,
            })));
        }

        if let Some(break_token) = stream.take_match(TokenKind::Identifier, &["break"])? {
            let semicolon = stream.expect_match(TokenKind::Symbol, &[";"])?;
            // Continue, unreachable code is allowed
            return Ok(ControlFlow::Continue(Statement::Break(Break {
                break_token,
                semicolon,
            })));
        }
        if let Some(continue_token) = stream.take_match(TokenKind::Identifier, &["continue"])? {
            let semicolon = stream.expect_match(TokenKind::Symbol, &[";"])?;
            // Continue, unreachable code is allowed
            return Ok(ControlFlow::Continue(Statement::Continue(Continue {
                continue_token,
                semicolon,
            })));
        }

        if let Ok(Some(_)) = stream.peek_match(TokenKind::Symbol, &["{"]) {
            return Ok(ControlFlow::Continue(Statement::Scope(Body::parse(
                stream,
            )?)));
        }

        let save = stream.clone();
        let expression = Expression::parse(stream)?;
        match stream.take_match(TokenKind::Symbol, &[";"])? {
            Some(semicolon) => Ok(ControlFlow::Continue(Statement::Expression {
                expression,
                semicolon,
            })),
            None => {
                // No semicolon, re-parse as a right-hand expression
                *stream = save;
                let expression = RightHandExpression::parse(stream)?;

                Ok(ControlFlow::Break(Statement::ImplicitReturn(expression)))
            }
        }
    }
}

impl<T> Literal<T>
where
    T: TypeSet,
{
    fn parse(stream: &mut TokenStream<'_, impl Tokenizer>) -> Result<Self, Error> {
        let token = stream.peek_expect()?;

        let token_source = stream.source(token.location);
        let location = token.location;

        let literal_value = match token.kind {
            TokenKind::BinaryInteger => {
                let token_source = token_source.replace("_", "");
                Self::parse_integer_literal(&token_source[2..], 2)
                    .map_err(|_| stream.error("Invalid binary integer literal"))?
            }
            TokenKind::DecimalInteger => {
                let token_source = token_source.replace("_", "");
                Self::parse_integer_literal(&token_source, 10)
                    .map_err(|_| stream.error("Invalid integer literal"))?
            }
            TokenKind::HexInteger => {
                let token_source = token_source.replace("_", "");
                Self::parse_integer_literal(&token_source[2..], 16)
                    .map_err(|_| stream.error("Invalid hexadecimal integer literal"))?
            }
            TokenKind::Float => {
                let token_source = token_source.replace("_", "");
                <T::Float as FloatParser>::parse(&token_source)
                    .map(LiteralValue::Float)
                    .map_err(|_| stream.error("Invalid float literal"))?
            }
            TokenKind::String => match unescape(&token_source[1..token_source.len() - 1]) {
                Ok(string) => LiteralValue::String(string),
                Err(offset) => {
                    return Err(Error {
                        error: String::from("Invalid escape sequence in string literal")
                            .into_boxed_str(),
                        location: Location {
                            start: token.location.start + offset,
                            end: token.location.start + offset + 1,
                        },
                    });
                }
            },
            TokenKind::Identifier if token_source == "true" => LiteralValue::Boolean(true),
            TokenKind::Identifier if token_source == "false" => LiteralValue::Boolean(false),
            _ => return Err(stream.error("Expected literal (number, string, or boolean)")),
        };

        stream.expect_match(token.kind, &[])?;
        Ok(Self {
            value: literal_value,
            location,
        })
    }

    fn parse_integer_literal(
        token_source: &str,
        radix: u32,
    ) -> Result<LiteralValue<T>, ParseIntError> {
        <T::Integer as IntParser>::parse(token_source, radix).map(LiteralValue::Integer)
    }
}

fn unescape(s: &str) -> Result<String, usize> {
    let mut result = String::new();
    let mut escaped = false;
    for (i, c) in s.char_indices().peekable() {
        if escaped {
            match c {
                'n' => result.push('\n'),
                't' => result.push('\t'),
                '\\' => result.push('\\'),
                '"' => result.push('"'),
                '\'' => result.push('\''),
                _ => return Err(i), // Invalid escape sequence
            }
            escaped = false;
        } else if c == '\\' {
            escaped = true;
        } else {
            result.push(c);
        }
    }

    Ok(result)
}

impl LeftHandExpression {
    fn parse<T: TypeSet>(stream: &mut TokenStream<'_, impl Tokenizer>) -> Result<Self, Error> {
        const UNARY_OPERATORS: &[&str] = &["*"];
        if let Some(operator) = stream.take_match(TokenKind::Symbol, UNARY_OPERATORS)? {
            // `*name` — a whole-value dereference target. Field paths through a
            // dereference are not valid lvalues (reference fields are unsupported).
            return Ok(Self::Deref {
                operator,
                name: Self::parse_name::<T>(stream)?,
            });
        }

        // A place path: `name` followed by zero or more `.field` accesses.
        let mut expr = Self::Name {
            variable: Self::parse_name::<T>(stream)?,
        };
        while let Some(dot) = stream.take_match(TokenKind::Symbol, &["."])? {
            let field = stream.expect_match(TokenKind::Identifier, &[])?;
            expr = Self::Field {
                base: Box::new(expr),
                dot,
                field,
            };
        }

        Ok(expr)
    }

    fn parse_name<T: TypeSet>(
        stream: &mut TokenStream<'_, impl Tokenizer>,
    ) -> Result<Token, Error> {
        let token = stream.peek_expect()?;
        match token.kind {
            TokenKind::Identifier => {
                // true, false?
                match Literal::<T>::parse(stream) {
                    Ok(_) => Err(Error {
                        error: "Parse error: Literals are not valid on the left-hand side"
                            .to_string()
                            .into_boxed_str(),
                        location: token.location,
                    }),
                    _ => stream
                        .take_match(TokenKind::Identifier, &[])
                        .map(|v| v.unwrap()),
                }
            }
            _ => Err(stream.error("Expected variable name or deref operator")),
        }
    }
}

impl<T> Expression<T>
where
    T: TypeSet,
{
    fn parse(stream: &mut TokenStream<'_, impl Tokenizer>) -> Result<Self, Error> {
        let save = stream.clone();

        let expression = RightHandExpression::<T>::parse(stream)?;

        if let Ok(Some(operator)) = stream.take_match(TokenKind::Symbol, &["="]) {
            // Re-parse as an assignment
            *stream = save;
            let left_expr = LeftHandExpression::parse::<T>(stream)?;
            stream.expect_match(TokenKind::Symbol, &["="])?;
            let right_expr = RightHandExpression::parse(stream)?;

            Ok(Self::Assignment {
                left_expr,
                operator,
                right_expr,
            })
        } else {
            Ok(Self::Expression { expression })
        }
    }
}

impl<T> RightHandExpression<T>
where
    T: TypeSet,
{
    fn parse(stream: &mut TokenStream<'_, impl Tokenizer>) -> Result<Self, Error> {
        Self::parse_inner(stream, true)
    }

    /// Parses a right-hand expression that does not permit a *top-level* struct
    /// literal. Used for control-flow conditions and iterables, where a bare
    /// `Name { ... }` would be ambiguous with the following block. Struct literals
    /// remain reachable within parentheses.
    fn parse_no_struct(stream: &mut TokenStream<'_, impl Tokenizer>) -> Result<Self, Error> {
        Self::parse_inner(stream, false)
    }

    fn parse_inner(
        stream: &mut TokenStream<'_, impl Tokenizer>,
        allow_struct: bool,
    ) -> Result<Self, Error> {
        // We define the binary operators from the lowest precedence to the highest.
        // Each recursive call to `parse_binary` will handle one level of precedence, and pass
        // the rest to the inner calls of `parse_binary`.
        let operators: &[&[&str]] = &[
            &["||"],
            &["&&"],
            &["<", "<=", ">", ">=", "==", "!="],
            &["|"],
            &["^"],
            &["&"],
            &["<<", ">>"],
            &["+", "-"],
            &["*", "/", "%"],
        ];

        Self::parse_binary(stream, operators, allow_struct)
    }

    fn parse_binary(
        stream: &mut TokenStream<'_, impl Tokenizer>,
        binary_operators: &[&[&str]],
        allow_struct: bool,
    ) -> Result<Self, Error> {
        let Some((current, higher)) = binary_operators.split_first() else {
            unreachable!("At least one operator set is expected");
        };

        let mut expr = if higher.is_empty() {
            Self::parse_unary(stream, allow_struct)?
        } else {
            Self::parse_binary(stream, higher, allow_struct)?
        };

        while let Some(operator) = stream.take_match(TokenKind::Symbol, current)? {
            let rhs = if higher.is_empty() {
                Self::parse_unary(stream, allow_struct)?
            } else {
                Self::parse_binary(stream, higher, allow_struct)?
            };

            expr = Self::BinaryOperator {
                name: operator,
                operands: Box::new([expr, rhs]),
            };
        }

        Ok(expr)
    }

    fn parse_unary(
        stream: &mut TokenStream<'_, impl Tokenizer>,
        allow_struct: bool,
    ) -> Result<Self, Error> {
        const UNARY_OPERATORS: &[&str] = &["!", "-", "&", "*"];
        if let Some(operator) = stream.take_match(TokenKind::Symbol, UNARY_OPERATORS)? {
            let operand = Self::parse_unary(stream, allow_struct)?;
            Ok(Self::UnaryOperator {
                name: operator,
                operand: Box::new(operand),
            })
        } else {
            Self::parse_postfix(stream, allow_struct)
        }
    }

    /// Parses a primary followed by zero or more `.field` accesses. Field access
    /// is a postfix operator binding tighter than any unary prefix.
    fn parse_postfix(
        stream: &mut TokenStream<'_, impl Tokenizer>,
        allow_struct: bool,
    ) -> Result<Self, Error> {
        let mut expr = Self::parse_primary(stream, allow_struct)?;

        while let Some(dot) = stream.take_match(TokenKind::Symbol, &["."])? {
            let field = stream.expect_match(TokenKind::Identifier, &[])?;
            expr = Self::FieldAccess {
                base: Box::new(expr),
                dot,
                field,
            };
        }

        Ok(expr)
    }

    fn parse_primary(
        stream: &mut TokenStream<'_, impl Tokenizer>,
        allow_struct: bool,
    ) -> Result<Self, Error> {
        let token = stream.peek_expect()?;

        match token.kind {
            TokenKind::Identifier => {
                // true, false?
                if let Ok(literal) = Literal::<T>::parse(stream) {
                    return Ok(Self::Literal { value: literal });
                }

                // A struct literal `Name { ... }` — only when permitted in this
                // position, and only when an identifier is directly followed by `{`.
                if allow_struct {
                    let name = stream.expect_match(TokenKind::Identifier, &[])?;
                    if stream.peek_match(TokenKind::Symbol, &["{"])?.is_some() {
                        return Self::parse_struct_literal(stream, name);
                    }
                    return Self::parse_call_tail(stream, name);
                }

                Self::parse_call(stream)
            }
            TokenKind::Symbol if stream.source(token.location) == "(" => {
                stream.take_match(token.kind, &[])?;
                // Inside parentheses, struct literals are always allowed again.
                let expr = Self::parse(stream)?;
                stream.expect_match(TokenKind::Symbol, &[")"])?;
                Ok(expr)
            }
            TokenKind::HexInteger
            | TokenKind::DecimalInteger
            | TokenKind::BinaryInteger
            | TokenKind::Float
            | TokenKind::String => Literal::<T>::parse(stream).map(|value| Self::Literal { value }),
            _ => Err(stream.error("Expected variable, literal, or '('")),
        }
    }

    fn parse_struct_literal(
        stream: &mut TokenStream<'_, impl Tokenizer>,
        name: Token,
    ) -> Result<Self, Error> {
        let opening_brace = stream.expect_match(TokenKind::Symbol, &["{"])?;

        let mut fields = Vec::new();
        while let Some(field_name) = stream.take_match(TokenKind::Identifier, &[])? {
            let colon = stream.expect_match(TokenKind::Symbol, &[":"])?;
            // Field values are full expressions; struct literals are allowed here.
            let value = Self::parse(stream)?;

            fields.push(StructLiteralField {
                name: field_name,
                colon,
                value,
            });

            if stream.take_match(TokenKind::Symbol, &[","])?.is_none() {
                break;
            }
        }

        let closing_brace = stream.expect_match(TokenKind::Symbol, &["}"])?;

        Ok(Self::StructLiteral {
            name,
            opening_brace,
            fields,
            closing_brace,
        })
    }

    fn parse_call(stream: &mut TokenStream<'_, impl Tokenizer>) -> Result<Self, Error> {
        let token = stream.expect_match(TokenKind::Identifier, &[])?;
        Self::parse_call_tail(stream, token)
    }

    /// Parses the tail of a call/variable reference after the leading identifier
    /// has already been consumed.
    fn parse_call_tail(
        stream: &mut TokenStream<'_, impl Tokenizer>,
        token: Token,
    ) -> Result<Self, Error> {
        if stream.take_match(TokenKind::Symbol, &["("])?.is_none() {
            return Ok(Self::Variable { variable: token });
        };

        let mut arguments = Vec::new();
        while stream.peek_match(TokenKind::Symbol, &[")"])?.is_none() {
            let arg = Self::parse(stream)?;
            arguments.push(arg);

            if stream.take_match(TokenKind::Symbol, &[","])?.is_none() {
                break;
            }
        }
        stream.expect_match(TokenKind::Symbol, &[")"])?;

        Ok(Self::FunctionCall {
            name: token,
            arguments: arguments.into_boxed_slice(),
        })
    }
}

#[derive(Clone)]
struct TokenStream<'s, I>
where
    I: Tokenizer,
{
    source: &'s str,
    tokens: I,
}

impl<'s, I> TokenStream<'s, I>
where
    I: Tokenizer,
{
    fn new(source: &'s str, tokens: I) -> Self {
        TokenStream { source, tokens }
    }

    /// Fast-forwards the token iterator past comments.
    fn skip_comments(&mut self) -> Result<(), Error> {
        let mut peekable = self.tokens.clone();
        while let Some(token) = peekable.next() {
            if token?.kind == TokenKind::Comment {
                self.tokens = peekable.clone();
            } else {
                break;
            }
        }

        Ok(())
    }

    fn end(&mut self) -> Result<bool, Error> {
        self.skip_comments()?;

        Ok(self.tokens.clone().next().is_none())
    }

    fn peek(&mut self) -> Result<Option<Token>, Error> {
        self.skip_comments()?;

        match self.tokens.clone().next() {
            Some(Ok(token)) => Ok(Some(token)),
            Some(Err(error)) => Err(error),
            None => Ok(None),
        }
    }

    fn peek_expect(&mut self) -> Result<Token, Error> {
        self.peek()?.ok_or_else(|| Error {
            location: Location {
                start: self.source.len(),
                end: self.source.len(),
            },
            error: String::from("Unexpected end of input").into_boxed_str(),
        })
    }

    fn peek_match(
        &mut self,
        token_kind: TokenKind,
        source: &[&str],
    ) -> Result<Option<Token>, Error> {
        let Some(token) = self.peek()? else {
            return Ok(None);
        };

        let peeked = if token.kind == token_kind
            && (source.is_empty() || source.contains(&self.source(token.location)))
        {
            Some(token)
        } else {
            None
        };

        Ok(peeked)
    }

    fn take_match(
        &mut self,
        token_kind: TokenKind,
        source: &[&str],
    ) -> Result<Option<Token>, Error> {
        self.peek_match(token_kind, source).map(|token| {
            if let Some(token) = token {
                self.tokens.next();
                Some(token)
            } else {
                None
            }
        })
    }

    /// Takes the next token if it matches the expected kind and source.
    /// Returns an error if the token does not match.
    ///
    /// If `source` is empty, it only checks the token kind.
    /// If `source` is not empty, it checks if the token's source matches any of the provided strings.
    fn expect_match(&mut self, token_kind: TokenKind, source: &[&str]) -> Result<Token, Error> {
        if let Some(token) = self.take_match(token_kind, source)? {
            Ok(token)
        } else {
            let token = self.peek()?;
            let found = if let Some(token) = token {
                if token.kind == token_kind {
                    format!("found '{}'", self.source(token.location))
                } else {
                    format!("found {:?}", token.kind)
                }
            } else {
                "reached end of input".to_string()
            };
            match source {
                [] => Err(self.error(format_args!("Expected {token_kind:?}, {found}"))),
                [s] => Err(self.error(format_args!("Expected '{s}', {found}"))),
                _ => Err(self.error(format_args!("Expected one of {source:?}, {found}"))),
            }
        }
    }

    fn error(&self, message: impl Display) -> Error {
        Error {
            error: format!("Parse error: {message}").into_boxed_str(),
            location: if let Some(Ok(token)) = self.tokens.clone().next() {
                token.location
            } else {
                Location {
                    start: self.source.len(),
                    end: self.source.len(),
                }
            },
        }
    }

    fn source(&self, location: Location) -> &'s str {
        location.extract(self.source)
    }
}

pub fn parse<T>(source: &str) -> Result<Program<T>, Error>
where
    T: TypeSet,
{
    let tokens = crate::lexer::tokenize(source);
    let mut stream = TokenStream::new(source, tokens);

    Program::<T>::parse(&mut stream)
}

pub fn parse_expression<T>(source: &str) -> Result<Expression<T>, Error>
where
    T: TypeSet,
{
    let tokens = crate::lexer::tokenize(source);
    let mut stream = TokenStream::new(source, tokens);

    Expression::<T>::parse(&mut stream)
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn test_unescape() {
        assert_eq!(unescape(r#"Hello\nWorld\t!"#).unwrap(), "Hello\nWorld\t!");
        assert_eq!(unescape(r#"Hello\\World"#).unwrap(), "Hello\\World");
        assert_eq!(unescape(r#"Hello\zWorld"#), Err(6)); // Invalid escape sequence
    }

    fn parse_ok(source: &str) {
        parse::<DefaultTypeSet>(source)
            .unwrap_or_else(|e| panic!("expected `{source}` to parse, got: {e}"));
    }

    fn parse_err(source: &str) {
        assert!(
            parse::<DefaultTypeSet>(source).is_err(),
            "expected `{source}` to fail parsing"
        );
    }

    #[test]
    fn test_parse_struct_definition() {
        parse_ok("struct Point { x: int, y: int }");
        parse_ok("struct Point { x: int, y: int, }"); // trailing comma
        parse_ok("struct Empty {}");
        parse_ok("struct Line { start: Point, end: Point }"); // nested struct field
    }

    #[test]
    fn test_parse_field_access_and_struct_literal() {
        parse_ok("fn f() -> int { var p = Point { x: 1, y: 2 }; return p.x; }");
        parse_ok("fn f() -> int { return foo.x.y; }"); // chained
        parse_ok("fn f() -> int { return get().x; }"); // on a call result
        parse_ok("fn f() -> int { return &p.x; }"); // & binds looser than .
    }

    #[test]
    fn test_parse_field_assignment() {
        parse_ok("fn f() { p.x = 1; }");
        parse_ok("fn f() { p.x.y = 1; }"); // nested write
    }

    #[test]
    fn test_struct_literal_forbidden_in_condition() {
        // A bare struct literal in an `if` condition would be ambiguous with the block.
        parse_err("fn f() { if Point { x: 1 } { return; } }");
        // Parenthesizing makes it explicit and legal.
        parse_ok("fn f() { if (Point { x: 1 }) == p { return; } }");
    }

    #[test]
    fn test_out_of_range_literal() {
        let source = "0x100000000";

        let result = parse_expression::<TypeSet32>(source).expect_err("Parsing should fail");
        assert_eq!(
            "Parse error: Invalid hexadecimal integer literal",
            result.error.as_ref()
        );
    }

    #[test]
    fn test_grouped_numeric_literal() {
        let source = "1_000_000";

        let result = parse_expression::<TypeSet32>(source).unwrap();

        assert_eq!(source, result.location().extract(source));
    }

    #[test]
    fn test_parse_strings() {
        type LitVal = LiteralValue<TypeSet32>;

        let test_data = [
            (r#""hel_lo""#, Ok(LitVal::String(r#"hel_lo"#.to_string()))),
            ("1_000", Ok(LitVal::Integer(1000))),
            ("true", Ok(LitVal::Boolean(true))),
            ("false", Ok(LitVal::Boolean(false))),
            (
                "fal_se",
                Err("Parse error: Expected literal (number, string, or boolean)"),
            ),
        ];

        for (source, expected) in test_data {
            let tokens = crate::lexer::tokenize(source);
            let mut stream = TokenStream::new(source, tokens);

            let lit = match Literal::<TypeSet32>::parse(&mut stream) {
                Ok(lit) => lit,
                Err(err) => {
                    let Err(expected_err) = expected else {
                        panic!(
                            "Expected parsing to succeed, but it failed with error: {}",
                            err
                        );
                    };
                    assert_eq!(expected_err, err.to_string());
                    continue;
                }
            };

            let Ok(expected) = expected else {
                panic!("Expected error, but `{source}` was parsed successfully");
            };

            match (lit.value, expected) {
                (LitVal::Integer(a), LitVal::Integer(b)) => assert_eq!(a, b),
                (LitVal::Float(a), LitVal::Float(b)) => assert_eq!(a, b),
                (LitVal::String(a), LitVal::String(b)) => assert_eq!(a, b),
                (LitVal::Boolean(a), LitVal::Boolean(b)) => assert_eq!(a, b),
                _ => panic!("Unexpected literal type"),
            }
        }
    }
}