espy-ears 0.2.0

#![doc = include_str!("../README.md")]

use dst_factory::make_dst_factory;
use espy_eyes::{Lexer, Lexigram, Token};
use std::iter::Peekable;

#[cfg(test)]
mod tests;

#[derive(Debug, Eq, PartialEq)]
pub enum Error<'source> {
    /// An invalid token was encountered.
    ///
    /// The ast interprets an erroneous token as `None`,
    /// which may lead to further error diagnostics.
    ///
    /// See: [`espy_eyes::Error`]
    Lexer(espy_eyes::Error<'source>),
    MissingToken {
        /// Must contain at least one element.
        expected: &'static [Lexigram],
        /// A `None` token may have been caused by a Lexer error.
        actual: Option<Token<'source>>,
    },
    /// Occurs when an expression is required,
    /// but a token that ends expression context was immediately encountered.
    ExpectedExpression(Option<Token<'source>>),
    /// Occurs when a "root" [`Block`] encounters something which is not a statement or expression.
    ExpectedStatementOrExpression(Token<'source>),
    /// Occurs when parenthesis in an expression are unbalanced.
    ///
    /// [`Error::IncompleteExpression`] serves as the opening-parenthesis equivalent.
    UnexpectedCloseParen(Token<'source>),
    /// This error should only ever occur on [`Expression`]s,
    /// so positioning can be derived from surrounding context.
    IncompleteExpression,
}

/// Contains a list of the errors encountered by an ast node.
#[derive(Debug, Default, Eq, PartialEq)]
pub struct Diagnostics<'source> {
    pub errors: Vec<Error<'source>>,
}

impl<'source> Diagnostics<'source> {
    fn expect(
        &mut self,
        t: Option<espy_eyes::Result<'source>>,
        expected: &'static [Lexigram],
    ) -> Option<Token<'source>> {
        let actual = self.wrap(t);
        if actual.is_some_and(|actual| expected.contains(&actual.lexigram)) {
            actual
        } else {
            self.errors.push(Error::MissingToken { expected, actual });
            None
        }
    }

    fn expect_expression(
        &mut self,
        lexer: &mut Peekable<Lexer<'source>>,
    ) -> Option<Box<Expression<'source>>> {
        let expression = Expression::new(lexer);
        if expression.is_none() {
            self.errors.push(Error::ExpectedExpression(
                lexer.peek().copied().transpose().ok().flatten(),
            ));
        }
        expression
    }

    fn next_if(
        &mut self,
        lexer: &mut Peekable<Lexer<'source>>,
        expected: &'static [Lexigram],
    ) -> Option<Token<'source>> {
        self.expect(lexer.peek().copied(), expected).inspect(|_| {
            lexer.next();
        })
    }

    fn wrap(&mut self, t: Option<espy_eyes::Result<'source>>) -> Option<Token<'source>> {
        match t? {
            Ok(t) => Some(t),
            Err(e) => {
                let t = if let espy_eyes::Error {
                    origin,
                    kind: espy_eyes::ErrorKind::ReservedSymbol,
                } = e
                {
                    Some(Token {
                        origin,
                        lexigram: Lexigram::Ident,
                    })
                } else {
                    None
                };
                self.errors.push(Error::Lexer(e));
                t
            }
        }
    }
}

/// Components of an expression.
///
/// Expression evalutation is stack-based rather than using a syntax tree.
#[derive(Debug, Eq, PartialEq)]
pub enum Node<'source> {
    Unit(Token<'source>, Token<'source>),
    Bool(bool, Token<'source>),
    Number(Token<'source>),
    String(Token<'source>),
    Variable(Token<'source>),
    Block(Box<Block<'source>>),
    If(Box<If<'source>>),
    Match(Box<Match<'source>>),
    Enum(Box<Enum<'source>>),

    Pipe(Token<'source>),
    Call(Token<'source>),
    Bind(Token<'source>),
    Positive(Token<'source>),
    Negative(Token<'source>),
    Annotation(Box<Annotation<'source>>),
    Deref(Token<'source>),
    Mul(Token<'source>),
    Div(Token<'source>),
    Add(Token<'source>),
    Sub(Token<'source>),
    BitwiseAnd(Token<'source>),
    BitwiseOr(Token<'source>),
    BitwiseXor(Token<'source>),
    EqualTo(Token<'source>),
    NotEqualTo(Token<'source>),
    Greater(Token<'source>),
    GreaterEqual(Token<'source>),
    Lesser(Token<'source>),
    LesserEqual(Token<'source>),
    LogicalAnd(Token<'source>),
    LogicalOr(Token<'source>),
    Name {
        name: Token<'source>,
        colon_token: Token<'source>,
    },
    Field {
        dot_token: Token<'source>,
        index: Token<'source>,
    },
    OptionalField {
        dot_question_token: Token<'source>,
        index: Token<'source>,
    },
    Join(Token<'source>),
    List {
        length: u32,
    },
}

#[derive(Debug, Eq, PartialEq)]
enum Operation<'source> {
    Call(Token<'source>),
    Pipe(Token<'source>),
    Bind(Token<'source>),
    Positive(Token<'source>),
    Negative(Token<'source>),
    Annotation(Box<Annotation<'source>>),
    Deref(Token<'source>),
    Mul(Token<'source>),
    Div(Token<'source>),
    Add(Token<'source>),
    Sub(Token<'source>),
    BitwiseAnd(Token<'source>),
    BitwiseXor(Token<'source>),
    BitwiseOr(Token<'source>),
    EqualTo(Token<'source>),
    NotEqualTo(Token<'source>),
    Greater(Token<'source>),
    GreaterEqual(Token<'source>),
    Lesser(Token<'source>),
    LesserEqual(Token<'source>),
    LogicalAnd(Token<'source>),
    LogicalOr(Token<'source>),
    Name {
        name: Token<'source>,
        colon_token: Token<'source>,
    },
    Field {
        dot_token: Token<'source>,
        index: Token<'source>,
    },
    OptionalField {
        dot_question_token: Token<'source>,
        index: Token<'source>,
    },
    Join(Token<'source>),
}

impl Operation<'_> {
    // NOTE: please keep espybook/precedence.md up to date with this!
    fn precedence(&self) -> usize {
        match self {
            Operation::Field { .. } | Operation::OptionalField { .. } | Operation::Deref(_) => 13,
            Operation::Positive(_) | Operation::Negative(_) | Operation::Annotation(_) => 12,
            Operation::Mul(_) | Operation::Div(_) => 11,
            Operation::Add(_) | Operation::Sub(_) => 10,
            Operation::BitwiseAnd(_) => 9,
            Operation::BitwiseXor(_) => 8,
            Operation::BitwiseOr(_) => 7,
            Operation::EqualTo(_)
            | Operation::NotEqualTo(_)
            | Operation::Greater(_)
            | Operation::GreaterEqual(_)
            | Operation::Lesser(_)
            | Operation::LesserEqual(_) => 6,
            Operation::LogicalAnd(_) => 5,
            Operation::LogicalOr(_) => 4,
            Operation::Name { .. } => 3,
            Operation::Join(_) => 2,
            Operation::Pipe(_) | Operation::Call(_) | Operation::Bind(_) => 1,
        }
    }

    // NOTE: please keep espybook/precedence.md up to date with this!
    fn left_associative(&self) -> bool {
        match self {
            Operation::Field { .. }
            | Operation::OptionalField { .. }
            | Operation::Deref(_)
            | Operation::Mul(_)
            | Operation::Div(_)
            | Operation::Add(_)
            | Operation::Sub(_)
            | Operation::BitwiseAnd(_)
            | Operation::BitwiseXor(_)
            | Operation::BitwiseOr(_)
            | Operation::EqualTo(_)
            | Operation::NotEqualTo(_)
            | Operation::Greater(_)
            | Operation::GreaterEqual(_)
            | Operation::Lesser(_)
            | Operation::LesserEqual(_)
            | Operation::LogicalAnd(_)
            | Operation::LogicalOr(_)
            | Operation::Join(_)
            | Operation::Call(_)
            | Operation::Bind(_)
            | Operation::Pipe(_) => true,
            // Unary operators have to be here to avoid miscompilation
            Operation::Positive(_)
            | Operation::Negative(_)
            | Operation::Annotation(_)
            | Operation::Name { .. } => false,
        }
    }
}

impl<'source> From<Operation<'source>> for Node<'source> {
    fn from(op: Operation<'source>) -> Self {
        match op {
            Operation::Field { dot_token, index } => Node::Field { dot_token, index },
            Operation::OptionalField {
                dot_question_token,
                index,
            } => Node::OptionalField {
                dot_question_token,
                index,
            },
            Operation::Pipe(t) => Node::Pipe(t),
            Operation::Bind(t) => Node::Bind(t),
            Operation::Call(t) => Node::Call(t),
            Operation::Positive(t) => Node::Positive(t),
            Operation::Negative(t) => Node::Negative(t),
            Operation::Annotation(t) => Node::Annotation(t),
            Operation::Deref(t) => Node::Deref(t),
            Operation::Mul(t) => Node::Mul(t),
            Operation::Div(t) => Node::Div(t),
            Operation::Add(t) => Node::Add(t),
            Operation::Sub(t) => Node::Sub(t),
            Operation::BitwiseAnd(t) => Node::BitwiseAnd(t),
            Operation::BitwiseXor(t) => Node::BitwiseXor(t),
            Operation::BitwiseOr(t) => Node::BitwiseOr(t),
            Operation::EqualTo(t) => Node::EqualTo(t),
            Operation::NotEqualTo(t) => Node::NotEqualTo(t),
            Operation::Greater(t) => Node::Greater(t),
            Operation::GreaterEqual(t) => Node::GreaterEqual(t),
            Operation::Lesser(t) => Node::Lesser(t),
            Operation::LesserEqual(t) => Node::LesserEqual(t),
            Operation::LogicalAnd(t) => Node::LogicalAnd(t),
            Operation::LogicalOr(t) => Node::LogicalOr(t),
            Operation::Name { name, colon_token } => Node::Name { name, colon_token },
            Operation::Join(t) => Node::Join(t),
        }
    }
}

/// This type should not contain an incomplete expression so long as there are no error diagnostics.
#[derive(Debug, Eq, PartialEq)]
#[make_dst_factory(pub)]
pub struct Expression<'source> {
    pub first_token: Option<Token<'source>>,
    pub last_token: Option<Token<'source>>,
    pub diagnostics: Diagnostics<'source>,
    pub contents: [Node<'source>],
}

impl<'source> Expression<'source> {
    /// Parse an expression until an unexpected token is upcoming (via peek).
    pub fn new(lexer: &mut Peekable<Lexer<'source>>) -> Option<Box<Self>> {
        Self::new_operatorless(lexer, false)
    }

    /// Parse an expression until an unexpected token is upcoming (via peek).
    pub fn list(lexer: &mut Peekable<Lexer<'source>>) -> Option<Box<Self>> {
        Self::new_operatorless(lexer, true)
    }

    /// Parse an expression until an unexpected token is upcoming (via peek).
    fn new_operatorless(
        lexer: &mut Peekable<Lexer<'source>>,
        list_mode: bool,
    ) -> Option<Box<Self>> {
        fn flush_by_precedence<'source>(
            output: &mut Vec<Node<'source>>,
            stack: &mut Vec<Operation<'source>>,
            operator: &Operation<'source>,
        ) {
            while let Some(op) = stack.pop_if(|x| {
                if operator.left_associative() {
                    x.precedence() >= operator.precedence()
                } else {
                    x.precedence() > operator.precedence()
                }
            }) {
                output.push(op.into());
            }
        }
        fn push_with_precedence<'source>(
            output: &mut Vec<Node<'source>>,
            stack: &mut Vec<Operation<'source>>,
            operator: Operation<'source>,
        ) {
            flush_by_precedence(output, stack, &operator);
            stack.push(operator);
        }
        // List of tokens that imply the unary position.
        // This is probably not the best way to do this.
        const UNARY_POSITION: &[Lexigram] = &[
            Lexigram::Plus,
            Lexigram::Minus,
            Lexigram::Star,
            Lexigram::Slash,
            Lexigram::Ampersand,
            Lexigram::Caret,
            Lexigram::Pipe,
            Lexigram::DoubleEqual,
            Lexigram::BangEqual,
            Lexigram::Greater,
            Lexigram::GreaterEqual,
            Lexigram::Lesser,
            Lexigram::LesserEqual,
            Lexigram::And,
            Lexigram::Or,
            Lexigram::Comma,
            Lexigram::Colon,
            Lexigram::Triangle,
            // This one is used to lie entirely about what the last token is
            // because @anno[tation] and [ list of things ] both use CloseSquare.
            // I should REALLY stop using these for unary position.
            Lexigram::At,
        ];
        // List of tokens which are well-known to end a (sub-)expression.
        // Technically any token not recognized by the match block later in this
        // function are capable of ending an expression, but only the following
        // list will be considered "end of expression" for the purposes of
        // trailing comma detection.
        const EXPRESSION_TERMINATORS: &[Lexigram] = &[
            Lexigram::CloseParen,
            Lexigram::CloseSquare,
            Lexigram::CloseBrace,
            Lexigram::Then,
            Lexigram::End,
            Lexigram::SingleEqual,
            Lexigram::Semicolon,
        ];
        let first_token = lexer.peek().copied().transpose().ok().flatten();
        let mut last_token: Option<Token> = None;
        let mut diagnostics = Diagnostics::default();
        let mut contents = Vec::new();
        let mut stack = Vec::new();
        // It's fine to start this at one because empty expressions always yield unit.
        let mut list_length = list_mode.then_some(1);
        loop {
            let unary_position = last_token.is_none_or(|t| UNARY_POSITION.contains(&t.lexigram));
            let t = diagnostics.wrap(lexer.peek().copied());
            macro_rules! lexi {
                ($($name:ident)? @ $lexi:ident) => {
                    Some($($name @)? Token {
                        lexigram: Lexigram::$lexi,
                        ..
                    })
                };
            }
            macro_rules! op {
                ($op:ident($inner:expr)) => {
                    push_with_precedence(&mut contents, &mut stack, Operation::$op($inner))
                };
            }
            macro_rules! imp_op {
                ($inner:expr) => {
                    if let Some(list_length) = &mut list_length {
                        // This resolves precedence as if a function call were occuring,
                        // even though no instruction will be generated for the list until the end of this function.
                        flush_by_precedence(&mut contents, &mut stack, &Operation::Call($inner));
                        *list_length += 1;
                    } else {
                        push_with_precedence(&mut contents, &mut stack, Operation::Call($inner))
                    }
                };
            }
            match t {
                // Terminals
                //
                // A terminal value outside of unary position implies a function call,
                // so flush the operator stack in this case.
                lexi!(number @ Number) => {
                    if !unary_position {
                        imp_op!(number);
                    }
                    contents.push(Node::Number(number));
                }
                lexi!(string @ String) => {
                    if !unary_position {
                        imp_op!(string);
                    }
                    contents.push(Node::String(string));
                }
                lexi!(ident @ Ident) => {
                    if !unary_position {
                        imp_op!(ident);
                    }
                    last_token = lexer.next().transpose().ok().flatten();
                    if let Some(Ok(
                        colon_token @ Token {
                            lexigram: Lexigram::Colon,
                            ..
                        },
                    )) = lexer.peek().copied()
                    {
                        last_token = lexer.next().transpose().ok().flatten();
                        push_with_precedence(
                            &mut contents,
                            &mut stack,
                            Operation::Name {
                                name: ident,
                                colon_token,
                            },
                        );
                    } else {
                        contents.push(Node::Variable(ident));
                    }
                    continue;
                }
                lexi!(t @ True) => {
                    if !unary_position {
                        imp_op!(t);
                    }
                    contents.push(Node::Bool(true, t));
                }
                lexi!(t @ False) => {
                    if !unary_position {
                        imp_op!(t);
                    }
                    contents.push(Node::Bool(false, t));
                }
                lexi!(t @ OpenParen) => {
                    if !unary_position {
                        imp_op!(t);
                    }
                    lexer.next();
                    if let Some(close) = lexer.peek().copied().transpose().ok().flatten()
                        && close.lexigram == Lexigram::CloseParen
                    {
                        contents.push(Node::Unit(t, close));
                    } else {
                        contents.push(Node::Block(Block::build(
                            BlockResult::Expression(Expression::new(lexer)),
                            Diagnostics::default(),
                            [],
                        )));
                        diagnostics.expect(lexer.peek().copied(), &[Lexigram::CloseParen]);
                    }
                }
                lexi!(t @ OpenSquare) => {
                    if !unary_position {
                        imp_op!(t);
                    }
                    lexer.next();
                    contents.push(Node::Block(Block::build(
                        BlockResult::Expression(Expression::list(lexer)),
                        Diagnostics::default(),
                        [],
                    )));
                    diagnostics.expect(lexer.peek().copied(), &[Lexigram::CloseSquare]);
                }
                lexi!(t @ OpenBrace) => {
                    if !unary_position {
                        imp_op!(t);
                    }
                    lexer.next();
                    contents.push(Node::Block(Block::child(&mut *lexer)));
                    diagnostics.expect(lexer.peek().copied(), &[Lexigram::CloseBrace]);
                }

                // prefix operators
                lexi!(t @ Plus) if unary_position => op!(Positive(t)),
                lexi!(t @ Minus) if unary_position => op!(Negative(t)),
                lexi!(t @ At) if unary_position => {
                    lexer.next();
                    let annotation = Annotation::new(t, lexer);
                    last_token = Some(t);
                    op!(Annotation(Box::new(annotation)));
                    continue;
                }
                // postfix
                lexi!(dot_token @ Dot) if !unary_position => {
                    last_token = lexer.next().transpose().ok().flatten();
                    if let Some(index) =
                        diagnostics.next_if(lexer, &[Lexigram::Ident, Lexigram::Number])
                    {
                        last_token = Some(index);
                        push_with_precedence(
                            &mut contents,
                            &mut stack,
                            Operation::Field { dot_token, index },
                        );
                    }
                    continue;
                }
                lexi!(dot_question_token @ DotQuestion) if !unary_position => {
                    last_token = lexer.next().transpose().ok().flatten();
                    if let Some(index) =
                        diagnostics.next_if(lexer, &[Lexigram::Ident, Lexigram::Number])
                    {
                        last_token = Some(index);
                        push_with_precedence(
                            &mut contents,
                            &mut stack,
                            Operation::OptionalField {
                                dot_question_token,
                                index,
                            },
                        );
                    }
                    continue;
                }
                lexi!(t @ DotStar) if !unary_position => op!(Deref(t)),
                lexi!(t @ Bang) if !unary_position => op!(Bind(t)),
                // infix operators
                lexi!(t @ Plus) if !unary_position => op!(Add(t)),
                lexi!(t @ Minus) if !unary_position => op!(Sub(t)),
                lexi!(t @ Star) if !unary_position => op!(Mul(t)),
                lexi!(t @ Slash) if !unary_position => op!(Div(t)),
                lexi!(t @ Ampersand) if !unary_position => op!(BitwiseAnd(t)),
                lexi!(t @ Caret) if !unary_position => op!(BitwiseXor(t)),
                lexi!(t @ Pipe) if !unary_position => op!(BitwiseOr(t)),
                lexi!(t @ DoubleEqual) if !unary_position => op!(EqualTo(t)),
                lexi!(t @ BangEqual) if !unary_position => op!(NotEqualTo(t)),
                lexi!(t @ Greater) if !unary_position => op!(Greater(t)),
                lexi!(t @ GreaterEqual) if !unary_position => op!(GreaterEqual(t)),
                lexi!(t @ Lesser) if !unary_position => op!(Lesser(t)),
                lexi!(t @ LesserEqual) if !unary_position => op!(LesserEqual(t)),
                lexi!(t @ And) if !unary_position => op!(LogicalAnd(t)),
                lexi!(t @ Or) if !unary_position => op!(LogicalOr(t)),
                lexi!(t @ Triangle) if !unary_position => op!(Pipe(t)),
                lexi!(t @ Comma) if !unary_position => {
                    // this will be ignored if the comma is trailing
                    let potential_last_token = lexer.next().transpose().ok().flatten();
                    if !lexer
                        .peek()
                        .copied()
                        .transpose()
                        .ok()
                        .flatten()
                        .is_none_or(|t| EXPRESSION_TERMINATORS.contains(&t.lexigram))
                    {
                        op!(Join(t));
                        last_token = potential_last_token;
                    }
                    continue;
                }
                lexi!(  @ If) => contents.push(If::from(&mut *lexer).into()),
                lexi!(  @ Match) => contents.push(Match::new(&mut *lexer).into()),
                lexi!(  @ Enum) => contents.push(Enum::from(&mut *lexer).into()),
                _ => {
                    if unary_position {
                        if !contents.is_empty() || !stack.is_empty() {
                            diagnostics.errors.push(Error::IncompleteExpression);
                        }
                    } else {
                        while let Some(op) = stack.pop() {
                            contents.push(op.into());
                        }
                    }
                    if contents.is_empty() && diagnostics.errors.is_empty() {
                        return None;
                    }
                    if let Some(length) = list_length {
                        contents.push(Node::List { length });
                    }
                    return Some(Expression::build(
                        first_token,
                        last_token,
                        diagnostics,
                        contents,
                    ));
                }
            }
            // This is sometimes skipped with a continue!
            last_token = lexer.next().transpose().unwrap_or(None);
        }
    }
}

#[derive(Debug, Eq, PartialEq)]
pub struct Annotation<'source> {
    pub at_sign: Token<'source>,
    pub name: Option<Token<'source>>,
    pub open_square: Option<Token<'source>>,
    pub tokens: Box<[Token<'source>]>,
    pub close_square: Option<Token<'source>>,
    pub diagnostics: Diagnostics<'source>,
}

impl<'source> Annotation<'source> {
    fn new(at_sign: Token<'source>, lexer: &mut Peekable<Lexer<'source>>) -> Self {
        let mut diagnostics = Diagnostics::default();
        let name = diagnostics.next_if(lexer, &[Lexigram::Ident]);
        let open_square = diagnostics.next_if(lexer, &[Lexigram::OpenSquare]);
        let mut tokens = Vec::new();
        let mut square_level = 0;
        loop {
            let token = match diagnostics.wrap(lexer.peek().copied()) {
                Some(
                    token @ Token {
                        lexigram: Lexigram::OpenSquare,
                        ..
                    },
                ) => {
                    square_level += 1;
                    token
                }
                Some(
                    token @ Token {
                        lexigram: Lexigram::CloseSquare,
                        ..
                    },
                ) => {
                    if square_level > 0 {
                        square_level -= 1;
                        token
                    } else {
                        break;
                    }
                }
                Some(token) => token,
                None => break,
            };
            lexer.next();
            tokens.push(token);
        }
        let close_square = diagnostics.next_if(lexer, &[Lexigram::CloseSquare]);
        Self {
            at_sign,
            name,
            open_square,
            tokens: tokens.into_boxed_slice(),
            close_square,
            diagnostics,
        }
    }
}

#[derive(Debug, Eq, PartialEq)]
pub struct If<'source> {
    pub if_token: Token<'source>,
    pub condition: Option<Box<Expression<'source>>>,
    pub then_token: Option<Token<'source>>,
    pub first: Box<Block<'source>>,
    pub else_token: Option<Token<'source>>,
    pub else_kind: Option<Token<'source>>,
    pub second: Box<Block<'source>>,
    pub end_token: Option<Token<'source>>,
    pub diagnostics: Diagnostics<'source>,
}

impl<'source> From<If<'source>> for Node<'source> {
    fn from(if_block: If<'source>) -> Self {
        Self::If(Box::new(if_block))
    }
}

impl<'source> From<&mut Peekable<Lexer<'source>>> for If<'source> {
    fn from(lexer: &mut Peekable<Lexer<'source>>) -> Self {
        let if_token = lexer
            .next()
            .transpose()
            .ok()
            .flatten()
            .expect("caller must have peeked a token");
        let mut diagnostics = Diagnostics::default();
        let condition = diagnostics.expect_expression(lexer);
        let then_token = diagnostics.next_if(lexer, &[Lexigram::Then]);
        let first = Block::child(&mut *lexer);
        let (second, else_token, else_kind) = if let else_token @ Some(Token {
            lexigram: Lexigram::Else,
            ..
        }) = diagnostics.wrap(lexer.peek().copied())
        {
            lexer.next();
            let (second, else_kind) = match diagnostics.wrap(lexer.peek().copied()) {
                else_kind @ Some(Token {
                    lexigram: Lexigram::Then,
                    ..
                }) => {
                    lexer.next();
                    (Block::child(&mut *lexer), else_kind)
                }
                else_kind @ Some(Token {
                    lexigram: Lexigram::If,
                    ..
                }) => (
                    Block::build(
                        Expression::build(
                            None,
                            None,
                            Diagnostics::default(),
                            [Self::from(&mut *lexer).into()],
                        )
                        .into(),
                        Diagnostics::default(),
                        [],
                    ),
                    else_kind,
                ),
                _ => {
                    diagnostics.expect(lexer.peek().copied(), &[Lexigram::Then, Lexigram::If]);
                    (Box::default(), None)
                }
            };
            (second, else_token, else_kind)
        } else {
            (Box::default(), None, None)
        };
        let end_token = diagnostics.expect(lexer.peek().copied(), &[Lexigram::End]);
        Self {
            if_token,
            condition,
            then_token,
            first,
            else_token,
            else_kind,
            second,
            end_token,
            diagnostics,
        }
    }
}

#[derive(Debug, Eq, PartialEq)]
pub struct MatchCase<'source> {
    pub let_token: Option<Token<'source>>,
    pub binding: Option<Binding<'source>>,
    pub equals_token: Option<Token<'source>>,
    pub case: Option<Box<Expression<'source>>>,
    pub arrow_token: Option<Token<'source>>,
    pub expression: Option<Box<Expression<'source>>>,
    pub semicolon_token: Option<Token<'source>>,
}

#[derive(Debug, Eq, PartialEq)]
#[make_dst_factory(pub)]
pub struct Match<'source> {
    pub match_token: Token<'source>,
    pub expression: Option<Box<Expression<'source>>>,
    pub then_token: Option<Token<'source>>,
    pub end_token: Option<Token<'source>>,
    pub diagnostics: Diagnostics<'source>,
    pub cases: [MatchCase<'source>],
}

impl<'source> From<Box<Match<'source>>> for Node<'source> {
    fn from(struct_block: Box<Match<'source>>) -> Self {
        Self::Match(struct_block)
    }
}

impl<'source> Match<'source> {
    /// # Panics
    ///
    /// Panics if the lexer returns `None`.
    ///
    /// This function should only be called after successfully peeking a [`Lexigram::Match`].
    pub fn new(lexer: &mut Peekable<Lexer<'source>>) -> Box<Self> {
        let match_token = lexer
            .next()
            .transpose()
            .ok()
            .flatten()
            .expect("caller must have peeked a token");
        let mut diagnostics = Diagnostics::default();

        let expression = diagnostics.expect_expression(lexer);
        let then_token = diagnostics.next_if(lexer, &[Lexigram::Then]);
        let mut cases = Vec::new();

        // ew
        loop {
            let (let_token, binding, equals_token, case) = if let let_token @ Some(Token {
                lexigram: Lexigram::Let,
                ..
            }) =
                diagnostics.wrap(lexer.peek().copied())
            {
                lexer.next();
                let binding = Binding::new(lexer)
                    .map_err(|e| diagnostics.errors.push(e))
                    .ok();
                let (equal_token, case) = if let equal_token @ Some(Token {
                    lexigram: Lexigram::SingleEqual,
                    ..
                }) = diagnostics.wrap(lexer.peek().copied())
                {
                    lexer.next();
                    let case = diagnostics.expect_expression(lexer);
                    (equal_token, case)
                } else {
                    (None, None)
                };
                (let_token, binding, equal_token, case)
            } else {
                let case = diagnostics.expect_expression(lexer);
                (None, None, None, case)
            };
            let arrow_token = diagnostics.next_if(lexer, &[Lexigram::DoubleArrow]);
            let expression = diagnostics.expect_expression(lexer);
            let semicolon_token = diagnostics.next_if(lexer, &[Lexigram::Semicolon]);
            cases.push(MatchCase {
                let_token,
                binding,
                equals_token,
                case,
                arrow_token,
                expression,
                semicolon_token,
            });
            if semicolon_token.is_none()
                || diagnostics
                    .wrap(lexer.peek().copied())
                    .is_some_and(|t| t.lexigram == Lexigram::End)
            {
                break;
            }
        }
        let end_token = diagnostics.expect(lexer.peek().copied(), &[Lexigram::End]);
        Match::build(
            match_token,
            expression,
            then_token,
            end_token,
            diagnostics,
            cases,
        )
    }
}

#[derive(Debug, Eq, PartialEq)]
pub struct Enum<'source> {
    pub enum_token: Token<'source>,
    pub variants: Option<Box<Expression<'source>>>,
    pub end_token: Option<Token<'source>>,
    pub diagnostics: Diagnostics<'source>,
}

impl<'source> From<Enum<'source>> for Node<'source> {
    fn from(struct_block: Enum<'source>) -> Self {
        Self::Enum(Box::new(struct_block))
    }
}

impl<'source> From<&mut Peekable<Lexer<'source>>> for Enum<'source> {
    fn from(lexer: &mut Peekable<Lexer<'source>>) -> Self {
        let enum_token = lexer
            .next()
            .transpose()
            .ok()
            .flatten()
            .expect("caller must have peeked a token");
        let mut diagnostics = Diagnostics::default();
        let variants = diagnostics.expect_expression(lexer);
        let end_token = diagnostics.expect(lexer.peek().copied(), &[Lexigram::End]);
        Self {
            enum_token,
            variants,
            end_token,
            diagnostics,
        }
    }
}

#[derive(Debug, Eq, PartialEq)]
pub enum Statement<'source> {
    Sequence(Sequence<'source>),
    Let(Let<'source>),
    Rebind(Rebind<'source>),
    Set(Set<'source>),
    Use(Use<'source>),
}

#[derive(Debug, Eq, PartialEq)]
pub struct Let<'source> {
    pub let_token: Token<'source>,
    pub binding: Option<Binding<'source>>,
    pub equals_token: Option<Token<'source>>,
    pub expression: Option<Box<Expression<'source>>>,
    pub semicolon_token: Option<Token<'source>>,
    pub diagnostics: Diagnostics<'source>,
}

impl<'source> Let<'source> {
    /// # Panics
    ///
    /// Panics if the lexer returns `None`.
    ///
    /// This function should only be called after successfully peeking a [`Lexigram::Let`].
    pub fn new(let_token: Token<'source>, lexer: &mut Peekable<Lexer<'source>>) -> Self {
        let mut diagnostics = Diagnostics::default();
        let binding = Binding::new(lexer)
            .map_err(|e| diagnostics.errors.push(e))
            .ok();
        let equals_token = diagnostics.next_if(lexer, &[Lexigram::SingleEqual]);
        let expression = diagnostics.expect_expression(lexer);
        let semicolon_token = diagnostics.next_if(lexer, &[Lexigram::Semicolon]);

        Let {
            let_token,
            binding,
            equals_token,
            expression,
            semicolon_token,
            diagnostics,
        }
    }
}

#[derive(Debug, Eq, PartialEq)]
pub struct RebindSubject<'source> {
    pub ident_token: Option<Token<'source>>,
    pub comma_token: Option<Token<'source>>,
}

#[derive(Debug, Eq, PartialEq)]
pub enum RebindBy<'source> {
    Glob {
        star_token: Token<'source>,
    },
    Identifiers {
        bindings: Box<[RebindSubject<'source>]>,
    },
}

#[derive(Debug, Eq, PartialEq)]
pub struct Rebind<'source> {
    pub let_token: Token<'source>,
    pub caret_token: Token<'source>,
    pub by: RebindBy<'source>,
    pub semicolon_token: Option<Token<'source>>,
    pub diagnostics: Diagnostics<'source>,
}

impl<'source> Rebind<'source> {
    /// # Panics
    ///
    /// Panics if the lexer returns `None`.
    ///
    /// This function should only be called after successfully peeking a [`Lexigram::Caret`].
    pub fn new(let_token: Token<'source>, lexer: &mut Peekable<Lexer<'source>>) -> Self {
        let mut diagnostics = Diagnostics::default();
        let caret_token = lexer
            .next()
            .transpose()
            .ok()
            .flatten()
            .expect("caller must have peeked a token");
        let by = if let Some(
            star_token @ Token {
                lexigram: Lexigram::Star,
                ..
            },
        ) = diagnostics.wrap(lexer.peek().copied())
        {
            lexer.next();
            RebindBy::Glob { star_token }
        } else {
            let mut bindings = Vec::new();
            if let Some(ident_token) = diagnostics.next_if(lexer, &[Lexigram::Ident]) {
                bindings.push(RebindSubject {
                    ident_token: Some(ident_token),
                    comma_token: None,
                });
            }
            while let comma_token @ Some(Token {
                lexigram: Lexigram::Comma,
                ..
            }) = diagnostics.wrap(lexer.peek().copied())
            {
                lexer.next();
                bindings.push(RebindSubject {
                    ident_token: diagnostics.next_if(lexer, &[Lexigram::Ident]),
                    comma_token,
                });
            }
            RebindBy::Identifiers {
                bindings: bindings.into_boxed_slice(),
            }
        };
        let semicolon_token = diagnostics.next_if(lexer, &[Lexigram::Semicolon]);
        Rebind {
            let_token,
            caret_token,
            by,
            semicolon_token,
            diagnostics,
        }
    }
}

#[derive(Debug, Eq, PartialEq)]
pub struct Sequence<'source> {
    pub expression: Option<Box<Expression<'source>>>,
    pub semicolon_token: Token<'source>,
}

impl<'source> Sequence<'source> {
    /// # Errors
    ///
    /// Returns a lone [`Expression`] if no semicolon token was encountered.
    pub fn try_sequence(
        lexer: &mut Peekable<Lexer<'source>>,
    ) -> Result<Self, Option<Box<Expression<'source>>>> {
        let expression = Expression::new(&mut *lexer);
        if let Some(Ok(
            semicolon_token @ Token {
                lexigram: Lexigram::Semicolon,
                ..
            },
        )) = lexer.peek().copied()
        {
            lexer.next();
            Ok(Sequence {
                expression,
                semicolon_token,
            })
        } else {
            Err(expression)
        }
    }
}

#[derive(Debug, Eq, PartialEq)]
pub struct Set<'source> {
    pub set_token: Token<'source>,
    pub target: Option<Box<Expression<'source>>>,
    pub equals_token: Option<Token<'source>>,
    pub expression: Option<Box<Expression<'source>>>,
    pub semicolon_token: Option<Token<'source>>,
    pub diagnostics: Diagnostics<'source>,
}

impl<'source> Set<'source> {
    /// # Panics
    ///
    /// Panics if the lexer returns `None`.
    ///
    /// This function should only be called after successfully peeking a [`Lexigram::Set`].
    pub fn new(lexer: &mut Peekable<Lexer<'source>>) -> Self {
        let mut diagnostics = Diagnostics::default();
        let set_token = lexer
            .next()
            .transpose()
            .ok()
            .flatten()
            .expect("caller must have peeked a token");
        let target = diagnostics.expect_expression(lexer);
        let equals_token = diagnostics.next_if(lexer, &[Lexigram::SingleEqual]);
        let expression = diagnostics.expect_expression(lexer);
        let semicolon_token = diagnostics.next_if(lexer, &[Lexigram::Semicolon]);

        Set {
            set_token,
            target,
            equals_token,
            expression,
            semicolon_token,
            diagnostics,
        }
    }
}

#[derive(Debug, Eq, PartialEq)]
pub struct Use<'source> {
    pub use_token: Token<'source>,
    pub expression: Option<Box<Expression<'source>>>,
    pub semicolon_token: Option<Token<'source>>,
    pub diagnostics: Diagnostics<'source>,
}

impl<'source> Use<'source> {
    /// # Panics
    ///
    /// Panics if the lexer returns `None`.
    ///
    /// This function should only be called after successfully peeking a [`Lexigram::Use`].
    pub fn new(lexer: &mut Peekable<Lexer<'source>>) -> Self {
        let mut diagnostics = Diagnostics::default();
        let use_token = lexer
            .next()
            .transpose()
            .ok()
            .flatten()
            .expect("caller must have peeked a token");
        let expression = diagnostics.expect_expression(lexer);
        let semicolon_token = diagnostics.next_if(lexer, &[Lexigram::Semicolon]);

        Self {
            use_token,
            expression,
            semicolon_token,
            diagnostics,
        }
    }
}

#[derive(Debug, Eq, PartialEq)]
pub struct NumericBinding<'source> {
    pub binding: Binding<'source>,
    pub comma_token: Option<Token<'source>>,
}

#[derive(Debug, Eq, PartialEq)]
pub struct NamedBinding<'source> {
    pub field: Token<'source>,
    pub action: Option<NamedBindingAction<'source>>,
    pub comma_token: Option<Token<'source>>,
}

#[derive(Debug, Eq, PartialEq)]
pub enum NamedBindingAction<'source> {
    Optional(Token<'source>),
    Binding(NamedSubBinding<'source>),
}

#[derive(Debug, Eq, PartialEq)]
pub struct NamedSubBinding<'source> {
    pub colon_token: Token<'source>,
    pub binding: Binding<'source>,
}

#[derive(Debug, Eq, PartialEq)]
pub enum BindingMethod<'source> {
    Single(Token<'source>),
    Numeric {
        open_paren: Token<'source>,
        bindings: Box<[NumericBinding<'source>]>,
        close_paren: Option<Token<'source>>,
    },
    Named {
        open_brace: Token<'source>,
        bindings: Box<[NamedBinding<'source>]>,
        close_brace: Option<Token<'source>>,
    },
}

#[derive(Debug, Eq, PartialEq)]
pub struct Binding<'source> {
    pub method: BindingMethod<'source>,
    pub diagnostics: Diagnostics<'source>,
}

impl<'source> Binding<'source> {
    /// # Errors
    ///
    /// Returns an error if no valid binding token was encountered.
    pub fn new(lexer: &mut Peekable<Lexer<'source>>) -> Result<Self, Error<'source>> {
        match lexer.peek().copied().transpose().map_err(Error::Lexer)? {
            Some(
                t @ Token {
                    lexigram: Lexigram::Ident | Lexigram::Discard,
                    ..
                },
            ) => {
                lexer.next();
                Ok(Binding {
                    method: BindingMethod::Single(t),
                    diagnostics: Diagnostics::default(),
                })
            }
            Some(
                open_paren @ Token {
                    lexigram: Lexigram::OpenParen,
                    ..
                },
            ) => {
                let mut diagnostics = Diagnostics::default();
                let mut bindings = Vec::new();
                lexer.next();
                loop {
                    let t = diagnostics.wrap(lexer.peek().copied());
                    if let Some(Token {
                        lexigram: Lexigram::CloseParen,
                        ..
                    }) = t
                    {
                        break;
                    }
                    if let Ok(binding) = Binding::new(lexer) {
                        let comma_token = diagnostics
                            .wrap(lexer.peek().copied())
                            .filter(|t| t.lexigram == Lexigram::Comma);
                        bindings.push(NumericBinding {
                            binding,
                            comma_token,
                        });
                        if comma_token.is_some() {
                            lexer.next();
                        } else {
                            break;
                        }
                    } else {
                        diagnostics.errors.push(Error::MissingToken {
                            expected: &[
                                Lexigram::Ident,
                                Lexigram::Discard,
                                Lexigram::OpenParen,
                                Lexigram::OpenBrace,
                                Lexigram::CloseParen,
                            ],
                            actual: t,
                        });
                        break;
                    }
                }
                let close_paren = diagnostics.next_if(lexer, &[Lexigram::CloseParen]);
                Ok(Binding {
                    method: BindingMethod::Numeric {
                        open_paren,
                        bindings: bindings.into_boxed_slice(),
                        close_paren,
                    },
                    diagnostics,
                })
            }
            Some(
                open_brace @ Token {
                    lexigram: Lexigram::OpenBrace,
                    ..
                },
            ) => {
                let mut diagnostics = Diagnostics::default();
                let mut bindings = Vec::new();
                lexer.next();
                loop {
                    match diagnostics.wrap(lexer.peek().copied()) {
                        Some(Token {
                            lexigram: Lexigram::CloseBrace,
                            ..
                        }) => break,
                        Some(
                            field @ Token {
                                lexigram: Lexigram::Ident,
                                ..
                            },
                        ) => {
                            lexer.next();
                            match diagnostics.wrap(lexer.peek().copied()) {
                                Some(
                                    question_token @ Token {
                                        lexigram: Lexigram::Question,
                                        ..
                                    },
                                ) => {
                                    lexer.next();
                                    let comma_token = diagnostics
                                        .wrap(lexer.peek().copied())
                                        .filter(|t| t.lexigram == Lexigram::Comma);
                                    bindings.push(NamedBinding {
                                        field,
                                        action: Some(NamedBindingAction::Optional(question_token)),
                                        comma_token,
                                    });
                                    if comma_token.is_some() {
                                        lexer.next();
                                    } else {
                                        break;
                                    }
                                }
                                Some(
                                    colon_token @ Token {
                                        lexigram: Lexigram::Colon,
                                        ..
                                    },
                                ) => {
                                    lexer.next();
                                    match Binding::new(lexer) {
                                        Ok(binding) => {
                                            let comma_token = diagnostics
                                                .wrap(lexer.peek().copied())
                                                .filter(|t| t.lexigram == Lexigram::Comma);
                                            bindings.push(NamedBinding {
                                                field,
                                                action: Some(NamedBindingAction::Binding(
                                                    NamedSubBinding {
                                                        colon_token,
                                                        binding,
                                                    },
                                                )),
                                                comma_token,
                                            });
                                            if comma_token.is_some() {
                                                lexer.next();
                                            } else {
                                                break;
                                            }
                                        }
                                        Err(e) => {
                                            diagnostics.errors.push(e);
                                            break;
                                        }
                                    }
                                }
                                comma_token @ Some(Token {
                                    lexigram: Lexigram::Comma,
                                    ..
                                }) => {
                                    lexer.next();
                                    bindings.push(NamedBinding {
                                        field,
                                        action: None,
                                        comma_token,
                                    });
                                }
                                _ => {
                                    bindings.push(NamedBinding {
                                        field,
                                        action: None,
                                        comma_token: None,
                                    });
                                    break;
                                }
                            }
                        }
                        actual => {
                            diagnostics.errors.push(Error::MissingToken {
                                expected: &[Lexigram::Ident, Lexigram::CloseBrace],
                                actual,
                            });
                            break;
                        }
                    }
                }
                let close_brace = diagnostics.next_if(lexer, &[Lexigram::CloseBrace]);
                Ok(Binding {
                    method: BindingMethod::Named {
                        open_brace,
                        bindings: bindings.into_boxed_slice(),
                        close_brace,
                    },
                    diagnostics,
                })
            }
            actual => Err(Error::MissingToken {
                expected: &[
                    Lexigram::Ident,
                    Lexigram::Discard,
                    Lexigram::OpenParen,
                    Lexigram::OpenBrace,
                ],
                actual,
            }),
        }
    }
}

#[derive(Debug, Eq, PartialEq)]
pub enum FunctionBody<'source> {
    Block(Box<Block<'source>>),
    /// Occurs when with's semicolon is absent.
    ///
    /// Used to name only the type of a function.
    Never,
}

#[derive(Debug, Eq, PartialEq)]
pub struct Function<'source> {
    pub with_token: Token<'source>,
    pub argument: Option<Binding<'source>>,
    pub colon_token: Option<Token<'source>>,
    pub input: Option<Box<Expression<'source>>>,
    pub single_arrow_token: Option<Token<'source>>,
    pub output: Option<Box<Expression<'source>>>,
    pub semicolon_token: Option<Token<'source>>,
    pub body: FunctionBody<'source>,
    pub diagnostics: Diagnostics<'source>,
}

#[derive(Debug, Eq, PartialEq)]
#[expect(
    clippy::large_enum_variant,
    reason = "this is already inside of a (very large) boxed block"
)]
pub enum BlockResult<'source> {
    Expression(Option<Box<Expression<'source>>>),
    Function(Function<'source>),
}

impl BlockResult<'_> {
    #[must_use]
    pub fn is_empty(&self) -> bool {
        match self {
            BlockResult::Expression(expression) => expression.is_none(),
            BlockResult::Function(_) => false,
        }
    }
}

impl Default for BlockResult<'_> {
    fn default() -> Self {
        Self::Expression(None)
    }
}

impl<'source> From<Box<Expression<'source>>> for BlockResult<'source> {
    fn from(expression: Box<Expression<'source>>) -> Self {
        Self::Expression(Some(expression))
    }
}

impl<'source> From<Function<'source>> for BlockResult<'source> {
    fn from(function: Function<'source>) -> Self {
        Self::Function(function)
    }
}

#[derive(Debug, Eq, PartialEq)]
#[make_dst_factory(pub)]
pub struct Block<'source> {
    pub result: BlockResult<'source>,
    pub diagnostics: Diagnostics<'source>,
    pub statements: [Statement<'source>],
}

impl Default for Box<Block<'_>> {
    fn default() -> Self {
        Block::build(BlockResult::Expression(None), Diagnostics::default(), [])
    }
}

impl<'source> Block<'source> {
    pub fn new(lexer: &mut Peekable<Lexer<'source>>) -> Box<Self> {
        Self::parse(lexer, true)
    }

    fn child(lexer: &mut Peekable<Lexer<'source>>) -> Box<Self> {
        Self::parse(lexer, false)
    }

    fn parse(lexer: &mut Peekable<Lexer<'source>>, root: bool) -> Box<Self> {
        let mut diagnostics = Diagnostics::default();
        let mut statements = Vec::new();
        let result = loop {
            let statement = match diagnostics.wrap(lexer.peek().copied()) {
                Some(
                    let_token @ Token {
                        lexigram: Lexigram::Let,
                        ..
                    },
                ) => {
                    lexer.next();
                    if let Some(Ok(Token {
                        lexigram: Lexigram::Caret,
                        ..
                    })) = lexer.peek()
                    {
                        Statement::Rebind(Rebind::new(let_token, lexer))
                    } else {
                        Statement::Let(Let::new(let_token, lexer))
                    }
                }
                Some(Token {
                    lexigram: Lexigram::Set,
                    ..
                }) => Statement::Set(Set::new(lexer)),
                Some(Token {
                    lexigram: Lexigram::Use,
                    ..
                }) => Statement::Use(Use::new(lexer)),
                Some(
                    with_token @ Token {
                        lexigram: Lexigram::With,
                        ..
                    },
                ) => {
                    lexer.next();
                    let mut st_diagnostics = Diagnostics::default();
                    let argument = Binding::new(lexer)
                        .map_err(|e| st_diagnostics.errors.push(e))
                        .ok();
                    let (colon_token, input) = if let Some(
                        t @ Token {
                            lexigram: Lexigram::Colon,
                            ..
                        },
                    ) = st_diagnostics.wrap(lexer.peek().copied())
                    {
                        lexer.next();
                        (Some(t), diagnostics.expect_expression(lexer))
                    } else {
                        (None, None)
                    };
                    let (single_arrow_token, output) = if let Some(
                        t @ Token {
                            lexigram: Lexigram::SingleArrow,
                            ..
                        },
                    ) =
                        st_diagnostics.wrap(lexer.peek().copied())
                    {
                        lexer.next();
                        (Some(t), diagnostics.expect_expression(lexer))
                    } else {
                        (None, None)
                    };
                    let (semicolon_token, body) = if let Some(
                        t @ Token {
                            lexigram: Lexigram::Semicolon,
                            ..
                        },
                    ) = st_diagnostics.wrap(lexer.peek().copied())
                    {
                        lexer.next();
                        (
                            Some(t),
                            FunctionBody::Block(Block::parse(&mut *lexer, root)),
                        )
                    } else {
                        (None, FunctionBody::Never)
                    };

                    break Function {
                        with_token,
                        argument,
                        colon_token,
                        input,
                        single_arrow_token,
                        output,
                        semicolon_token,
                        body,
                        diagnostics: st_diagnostics,
                    }
                    .into();
                }
                _ => match Sequence::try_sequence(&mut *lexer) {
                    Ok(sequence) => Statement::Sequence(sequence),
                    Err(expression) => {
                        break BlockResult::Expression(expression);
                    }
                },
            };
            statements.push(statement);
        };
        if root && let Some(t) = lexer.peek().copied().transpose().ok().flatten() {
            diagnostics
                .errors
                .push(Error::ExpectedStatementOrExpression(t));
        }
        Self::build(result, diagnostics, statements)
    }
}