konjure_lang/

parser.rs

//! Bounded lexer and parser for Konjure source modules.
//!
//! The parser deliberately keeps syntax errors portable: every error is tied to
//! a byte span in the named input module and malformed input never panics.
use crate::ast::*;
use std::collections::BTreeMap;

const MAX_SOURCE_BYTES: usize = 1 << 20;
const MAX_TOKENS: usize = 100_000;
const MAX_NESTING: usize = 64;

/// A source token intended for editors and other language tooling.
#[derive(Clone, Debug, PartialEq, Eq, serde::Serialize, serde::Deserialize)]
pub struct Token {
    /// Lexical category: keyword, identifier, number, string, punctuation, or comment.
    pub kind: String,
    /// Exact source spelling, including delimiters for string literals.
    pub text: String,
    /// Token source location using UTF-8 byte offsets.
    pub span: Span,
}

#[derive(Clone, Debug)]
struct LexToken {
    token: Token,
    value: Option<String>,
}

/// Tokenizes source without discarding comments.  Spans are UTF-8 byte offsets.
pub fn tokenize(source: &str, module: &str) -> Result<Vec<Token>, Vec<Diagnostic>> {
    lex(source, module).map(|tokens| tokens.into_iter().map(|token| token.token).collect())
}

/// Parses a complete source module into its top-level items.
pub fn parse(source: &str, module: &str) -> Result<Vec<Item>, Vec<Diagnostic>> {
    if source.len() > MAX_SOURCE_BYTES {
        return Err(vec![Diagnostic::new(
            "E_LIMIT",
            "source exceeds the 1 MiB limit",
            Span::new(module, 0, source.len()),
        )]);
    }
    let tokens = lex(source, module)?
        .into_iter()
        .filter(|token| token.token.kind != "comment")
        .collect();
    let mut parser = Parser {
        tokens,
        at: 0,
        module: module.into(),
        source_len: source.len(),
        nesting: 0,
    };
    parser.module_items()
}

fn lex(source: &str, module: &str) -> Result<Vec<LexToken>, Vec<Diagnostic>> {
    if source.len() > MAX_SOURCE_BYTES {
        return Err(vec![Diagnostic::new(
            "E_LIMIT",
            "source exceeds the 1 MiB limit",
            Span::new(module, 0, source.len()),
        )]);
    }
    let mut tokens = Vec::new();
    let mut at = 0;
    while at < source.len() {
        let start = at;
        let ch = source[at..].chars().next().expect("valid UTF-8 boundary");
        if ch.is_whitespace() {
            at += ch.len_utf8();
            continue;
        }
        let (kind, text_end, value) = if source[at..].starts_with("//") {
            let end = source[at..]
                .find('\n')
                .map_or(source.len(), |offset| at + offset);
            ("comment", end, None)
        } else if ch == '"' {
            at += 1;
            let mut value = String::new();
            let mut closed = false;
            while at < source.len() {
                let current = source[at..].chars().next().expect("valid UTF-8 boundary");
                if current == '"' {
                    at += 1;
                    closed = true;
                    break;
                }
                if current == '\\' {
                    let escape_at = at;
                    at += 1;
                    let Some(escaped) = source[at..].chars().next() else {
                        return Err(vec![diagnostic(
                            module,
                            "E_LEX",
                            "unterminated string",
                            start,
                            source.len(),
                        )]);
                    };
                    match escaped {
                        'n' => value.push('\n'),
                        'r' => value.push('\r'),
                        't' => value.push('\t'),
                        '"' => value.push('"'),
                        '\\' => value.push('\\'),
                        _ => {
                            return Err(vec![diagnostic(
                                module,
                                "E_LEX",
                                "unsupported string escape",
                                escape_at,
                                at + escaped.len_utf8(),
                            )]);
                        }
                    };
                    at += escaped.len_utf8();
                } else {
                    value.push(current);
                    at += current.len_utf8();
                }
            }
            if !closed {
                return Err(vec![diagnostic(
                    module,
                    "E_LEX",
                    "unterminated string",
                    start,
                    source.len(),
                )]);
            }
            ("string", at, Some(value))
        } else if ch.is_ascii_digit() {
            at += 1;
            while source.as_bytes().get(at).is_some_and(u8::is_ascii_digit) {
                at += 1;
            }
            if source.as_bytes().get(at) == Some(&b'.')
                && source
                    .as_bytes()
                    .get(at + 1)
                    .is_some_and(u8::is_ascii_digit)
            {
                at += 1;
                while source.as_bytes().get(at).is_some_and(u8::is_ascii_digit) {
                    at += 1;
                }
            }
            ("number", at, None)
        } else if ch.is_ascii_alphabetic() || ch == '_' {
            at += ch.len_utf8();
            while let Some(next) = source[at..].chars().next() {
                if next.is_ascii_alphanumeric() || next == '_' {
                    at += next.len_utf8();
                } else {
                    break;
                }
            }
            let word = &source[start..at];
            (
                if is_keyword(word) {
                    "keyword"
                } else {
                    "identifier"
                },
                at,
                None,
            )
        } else if source[at..].starts_with("&&") || source[at..].starts_with("||") {
            let legacy = &source[at..at + 2];
            let replacement = if legacy == "&&" { "and" } else { "or" };
            return Err(vec![diagnostic(
                module,
                "E_PARSE",
                &format!("`{legacy}` is no longer supported; use `{replacement}`"),
                start,
                start + legacy.len(),
            )]);
        } else if let Some(punctuation) = punctuation_at(source, at) {
            at += punctuation.len();
            ("punctuation", at, None)
        } else {
            return Err(vec![diagnostic(
                module,
                "E_LEX",
                "unexpected character",
                start,
                start + ch.len_utf8(),
            )]);
        };
        let text = source[start..text_end].to_owned();
        tokens.push(LexToken {
            token: Token {
                kind: kind.into(),
                text,
                span: Span::new(module, start, text_end),
            },
            value,
        });
        if tokens.len() > MAX_TOKENS {
            return Err(vec![diagnostic(
                module,
                "E_LIMIT",
                "token count exceeds the 100000 limit",
                start,
                text_end,
            )]);
        }
        at = text_end;
    }
    Ok(tokens)
}

fn punctuation_at(source: &str, at: usize) -> Option<&'static str> {
    for punctuation in [
        "...", "->", "=>", "==", "!=", "<=", ">=", "{", "}", "(", ")", "[", "]", ",", ";", ":",
        ".", "=", "+", "-", "*", "/", "%", "@", "<", ">", "!", "?",
    ] {
        if source[at..].starts_with(punctuation) {
            return Some(punctuation);
        }
    }
    None
}

fn is_keyword(word: &str) -> bool {
    matches!(
        word,
        "class"
            | "type"
            | "enum"
            | "match"
            | "func"
            | "trait"
            | "impl"
            | "for"
            | "system"
            | "of"
            | "import"
            | "export"
            | "let"
            | "mut"
            | "if"
            | "else"
            | "while"
            | "in"
            | "ret"
            | "return"
            | "break"
            | "continue"
            | "true"
            | "false"
            | "and"
            | "or"
    )
}

fn diagnostic(module: &str, code: &str, message: &str, start: usize, end: usize) -> Diagnostic {
    Diagnostic::new(code, message, Span::new(module, start, end))
}

struct Parser {
    tokens: Vec<LexToken>,
    at: usize,
    module: String,
    source_len: usize,
    nesting: usize,
}

impl Parser {
    fn module_items(&mut self) -> Result<Vec<Item>, Vec<Diagnostic>> {
        let mut items = Vec::new();
        while !self.eof() {
            let item = match self.text() {
                Some("type") => Item::Class(self.class()?),
                Some("class") => {
                    return self
                        .error("`class` has been renamed to `type`; migrate this declaration");
                }
                Some("enum") => Item::Enum(self.enum_item()?),
                Some("func") => Item::Function(self.function(false)?),
                Some("trait") => Item::Trait(self.trait_item()?),
                Some("impl") => Item::Implementation(self.implementation()?),
                Some("system") => Item::System(self.system()?),
                Some("import") => self.import()?,
                Some("export") => self.export()?,
                _ => Item::Statement(self.statement()?),
            };
            items.push(item);
            self.optional(";");
        }
        Ok(items)
    }

    fn class(&mut self) -> Result<Class, Vec<Diagnostic>> {
        let start = self.expect("type")?.span.start;
        let (name, _) = self.identifier()?;
        self.expect("{")?;
        let mut fields = Vec::new();
        let mut methods = Vec::new();
        while !self.check("}") {
            if self.eof() {
                return self.error("expected `}` to close class");
            }
            if self.check("func") {
                methods.push(self.function(false)?);
                self.separator();
                continue;
            }
            let (field_name, field_span) = self.identifier()?;
            self.expect(":")?;
            let ty = self.ty()?;
            let default = if self.optional("=") {
                Some(self.expression(0)?)
            } else {
                None
            };
            let end = default
                .as_ref()
                .map_or(field_span.end, |expr| expr.span.end);
            fields.push(Field {
                name: field_name,
                ty,
                default,
                span: Span::new(&self.module, field_span.start, end),
            });
            self.separator();
        }
        let end = self.expect("}")?.span.end;
        Ok(Class {
            name,
            fields,
            methods,
            span: Span::new(&self.module, start, end),
        })
    }

    fn enum_item(&mut self) -> Result<Enum, Vec<Diagnostic>> {
        let start = self.expect("enum")?.span.start;
        let (name, _) = self.identifier()?;
        self.expect("{")?;
        let mut cases = Vec::new();
        while !self.check("}") {
            if self.eof() {
                return self.error("expected `}` to close enum");
            }
            let (case_name, case_span) = self.identifier()?;
            let mut payload = Vec::new();
            let end = if self.optional("(") {
                while !self.check(")") {
                    payload.push(self.ty()?);
                    if !self.optional(",") {
                        break;
                    }
                }
                self.expect(")")?.span.end
            } else {
                case_span.end
            };
            cases.push(EnumCase {
                name: case_name,
                payload,
                span: Span::new(&self.module, case_span.start, end),
            });
            self.separator();
        }
        let end = self.expect("}")?.span.end;
        Ok(Enum {
            name,
            cases,
            span: Span::new(&self.module, start, end),
        })
    }

    fn function(&mut self, signature_only: bool) -> Result<Function, Vec<Diagnostic>> {
        let start = self.expect("func")?.span.start;
        let (name, _) = self.identifier()?;
        self.expect("(")?;
        let mut parameters = Vec::new();
        while !self.check(")") {
            let (parameter_name, parameter_span) = self.identifier()?;
            self.expect(":")?;
            let ty = self.ty()?;
            parameters.push(Parameter {
                name: parameter_name,
                ty,
                span: parameter_span,
            });
            if !self.optional(",") {
                break;
            }
        }
        self.expect(")")?;
        self.expect("->")?;
        let returns = self.ty()?;
        let body = if signature_only {
            if !self.optional(";") {
                return self.error("trait methods require a signature ending in `;`; default method bodies are not supported");
            }
            Vec::new()
        } else {
            if self.check(";") {
                return self
                    .error("functions require a body; only trait method signatures end in `;`");
            }
            self.block()?
        };
        let end = body
            .last()
            .map_or_else(|| self.previous_end(), |statement| statement.span.end);
        Ok(Function {
            name,
            parameters,
            returns,
            body,
            span: Span::new(&self.module, start, end),
        })
    }

    fn trait_item(&mut self) -> Result<Trait, Vec<Diagnostic>> {
        let start = self.expect("trait")?.span.start;
        let (name, _) = self.identifier()?;
        self.expect("{")?;
        let mut methods = Vec::new();
        while !self.check("}") {
            if self.eof() {
                return self.error("expected `}` to close trait");
            }
            if !self.check("func") {
                return self.error("expected trait method signature");
            }
            methods.push(self.function(true)?);
            self.separator();
        }
        let end = self.expect("}")?.span.end;
        Ok(Trait {
            name,
            methods,
            span: Span::new(&self.module, start, end),
        })
    }

    fn implementation(&mut self) -> Result<Implementation, Vec<Diagnostic>> {
        let start = self.expect("impl")?.span.start;
        let (first, _) = self.qualified_identifier()?;
        let (trait_name, class) = if self.optional("for") {
            let (class, _) = self.qualified_identifier()?;
            (Some(first), class)
        } else {
            (None, first)
        };
        self.expect("{")?;
        let mut methods = Vec::new();
        while !self.check("}") {
            if self.eof() {
                return self.error("expected `}` to close impl");
            }
            if !self.check("func") {
                return self.error("expected implementation method");
            }
            methods.push(self.function(false)?);
            self.separator();
        }
        let end = self.expect("}")?.span.end;
        Ok(Implementation {
            trait_name,
            class,
            methods,
            span: Span::new(&self.module, start, end),
        })
    }

    fn system(&mut self) -> Result<System, Vec<Diagnostic>> {
        let start = self.expect("system")?.span.start;
        let (name, _) = self.identifier()?;
        self.expect("of")?;
        let mut bindings = Vec::new();
        if self.optional("(") {
            while !self.check(")") {
                let (binding_name, span) = self.identifier()?;
                self.expect(":")?;
                let ty = self.ty()?;
                bindings.push(Parameter {
                    name: binding_name,
                    ty,
                    span,
                });
                if !self.optional(",") {
                    break;
                }
            }
            self.expect(")")?;
        } else {
            let (component, span) = self.qualified_identifier()?;
            bindings.push(Parameter {
                name: "self".into(),
                ty: Type::named(component),
                span,
            });
        }
        self.expect("{")?;
        let mut callbacks = Vec::new();
        while !self.check("}") {
            if !self.check("func") {
                return self.error(
                    "systems declare lifecycle functions: func frame(dt: Number) -> Unit { ... }",
                );
            }
            callbacks.push(self.function(false)?);
            self.separator();
        }
        let end = self.expect("}")?.span.end;
        Ok(System {
            name,
            bindings,
            callbacks,
            span: Span::new(&self.module, start, end),
        })
    }

    fn import(&mut self) -> Result<Item, Vec<Diagnostic>> {
        let start = self.expect("import")?.span.start;
        let (mut module, _) = self.identifier()?;
        while self.optional(".") {
            let (part, _) = self.identifier()?;
            module.push('.');
            module.push_str(&part);
        }
        let end = self.previous_end();
        Ok(Item::Import {
            module,
            span: Span::new(&self.module, start, end),
        })
    }
    fn export(&mut self) -> Result<Item, Vec<Diagnostic>> {
        let start = self.expect("export")?.span.start;
        let (name, span) = self.identifier()?;
        Ok(Item::Export {
            name,
            span: Span::new(&self.module, start, span.end),
        })
    }

    fn block(&mut self) -> Result<Vec<Stmt>, Vec<Diagnostic>> {
        self.enter()?;
        self.expect("{")?;
        let mut body = Vec::new();
        while !self.check("}") {
            if self.eof() {
                self.leave();
                return self.error("expected `}` to close block");
            }
            body.push(self.statement()?);
            self.optional(";");
        }
        self.expect("}")?;
        self.leave();
        Ok(body)
    }

    fn statement(&mut self) -> Result<Stmt, Vec<Diagnostic>> {
        self.enter()?;
        let result = self.statement_inner();
        self.leave();
        result
    }
    fn statement_inner(&mut self) -> Result<Stmt, Vec<Diagnostic>> {
        let start = self.current_start();
        match self.text() {
            Some("let") => {
                self.advance();
                let mutable = self.optional("mut");
                let (name, _) = self.identifier()?;
                let ty = if self.optional(":") {
                    Some(self.ty()?)
                } else {
                    None
                };
                self.expect("=")?;
                let value = self.expression(0)?;
                let end = value.span.end;
                Ok(Stmt {
                    kind: StmtKind::Let {
                        name,
                        ty,
                        mutable,
                        value,
                    },
                    span: Span::new(&self.module, start, end),
                })
            }
            Some("ret") | Some("return") => {
                self.advance();
                let value = if self.check(";") || self.check("}") || self.eof() {
                    None
                } else {
                    Some(self.expression(0)?)
                };
                let end = value
                    .as_ref()
                    .map_or_else(|| self.previous_end(), |expr| expr.span.end);
                Ok(Stmt {
                    kind: StmtKind::Return(value),
                    span: Span::new(&self.module, start, end),
                })
            }
            Some("if") => {
                self.advance();
                let condition = self.expression(0)?;
                let then_body = self.block()?;
                let else_body = if self.optional("else") {
                    if self.check("if") {
                        vec![self.statement()?]
                    } else {
                        self.block()?
                    }
                } else {
                    Vec::new()
                };
                Ok(Stmt {
                    kind: StmtKind::If {
                        condition,
                        then_body,
                        else_body,
                    },
                    span: Span::new(&self.module, start, self.previous_end()),
                })
            }
            Some("while") => {
                self.advance();
                let condition = self.expression(0)?;
                let body = self.block()?;
                Ok(Stmt {
                    kind: StmtKind::While { condition, body },
                    span: Span::new(&self.module, start, self.previous_end()),
                })
            }
            Some("for") => {
                self.advance();
                let (name, _) = self.identifier()?;
                self.expect("in")?;
                let collection = self.expression(0)?;
                let body = self.block()?;
                Ok(Stmt {
                    kind: StmtKind::For {
                        name,
                        collection,
                        body,
                    },
                    span: Span::new(&self.module, start, self.previous_end()),
                })
            }
            Some("break") => {
                let end = self.advance().token.span.end;
                Ok(Stmt {
                    kind: StmtKind::Break,
                    span: Span::new(&self.module, start, end),
                })
            }
            Some("continue") => {
                let end = self.advance().token.span.end;
                Ok(Stmt {
                    kind: StmtKind::Continue,
                    span: Span::new(&self.module, start, end),
                })
            }
            _ => {
                let target = self.expression(0)?;
                if self.optional("=") {
                    let value = self.expression(0)?;
                    let end = value.span.end;
                    Ok(Stmt {
                        kind: StmtKind::Assign { target, value },
                        span: Span::new(&self.module, start, end),
                    })
                } else {
                    let end = target.span.end;
                    Ok(Stmt {
                        kind: StmtKind::Expr(target),
                        span: Span::new(&self.module, start, end),
                    })
                }
            }
        }
    }

    fn ty(&mut self) -> Result<Type, Vec<Diagnostic>> {
        self.enter()?;
        if self.optional("func") {
            self.expect("(")?;
            let mut parameters = Vec::new();
            while !self.check(")") {
                parameters.push(self.ty()?);
                if !self.optional(",") {
                    break;
                }
            }
            self.expect(")")?;
            self.expect("->")?;
            let returns = self.ty()?;
            self.leave();
            return Ok(Type::function(parameters, returns));
        }
        let (name, _) = self.qualified_identifier()?;
        if self.optional("[") {
            let mut arguments = Vec::new();
            while !self.check("]") {
                arguments.push(self.ty()?);
                if !self.optional(",") {
                    break;
                }
            }
            self.expect("]")?;
            self.leave();
            Ok(match name.as_str() {
                "List" if arguments.len() == 1 => Type::List(Box::new(arguments.remove(0))),
                "ComponentReference" if arguments.len() == 1 => {
                    Type::ComponentReference(Box::new(arguments.remove(0)))
                }
                "Tensor" if arguments.len() == 1 => Type::Tensor(Box::new(arguments.remove(0))),
                _ => Type::Applied { name, arguments },
            })
        } else {
            self.leave();
            Ok(Type::named(name))
        }
    }

    fn expression(&mut self, min_binding_power: u8) -> Result<Expr, Vec<Diagnostic>> {
        self.enter()?;
        let mut left = self.prefix()?;
        let mut chain_length = 0;
        loop {
            chain_length += 1;
            if chain_length > MAX_NESTING {
                return self.error("expression operator chain exceeds nesting limit");
            }
            if let Some((left_power, right_power)) = self.infix_binding_power() {
                if left_power < min_binding_power {
                    break;
                }
                let op = self.advance().token.text;
                let right = self.expression(right_power)?;
                let span = Span::new(&self.module, left.span.start, right.span.end);
                left = Expr {
                    kind: ExprKind::Binary {
                        op,
                        left: Box::new(left),
                        right: Box::new(right),
                    },
                    span,
                };
            } else {
                break;
            }
        }
        self.leave();
        Ok(left)
    }

    fn prefix(&mut self) -> Result<Expr, Vec<Diagnostic>> {
        let token = self.current().cloned().ok_or_else(|| {
            vec![diagnostic(
                &self.module,
                "E_PARSE",
                "expected expression",
                self.source_len,
                self.source_len,
            )]
        })?;
        match token.token.kind.as_str() {
            "number" => {
                self.advance();
                self.postfix(Expr {
                    kind: ExprKind::Number(token.token.text),
                    span: token.token.span,
                })
            }
            "string" => {
                self.advance();
                self.postfix(Expr {
                    kind: ExprKind::Text(token.value.unwrap_or_default()),
                    span: token.token.span,
                })
            }
            "identifier" | "keyword"
                if token.token.text == "true" || token.token.text == "false" =>
            {
                self.advance();
                self.postfix(Expr {
                    kind: ExprKind::Bool(token.token.text == "true"),
                    span: token.token.span,
                })
            }
            "identifier" => {
                self.advance();
                let mut expr = Expr {
                    kind: ExprKind::Name(token.token.text.clone()),
                    span: token.token.span.clone(),
                };
                if is_uppercase_name(&token.token.text) && self.check("{") {
                    expr = self.record(token.token.text, expr.span.start)?;
                }
                self.postfix(expr)
            }
            "keyword" if token.token.text == "match" => self.match_expression(),
            "punctuation" if token.token.text == "-" || token.token.text == "!" => {
                self.advance();
                let value = if token.token.text == "-"
                    && self
                        .current()
                        .is_some_and(|next| next.token.kind == "number")
                {
                    let number = self.advance().token;
                    Expr {
                        kind: ExprKind::Number(number.text),
                        span: number.span,
                    }
                } else {
                    self.expression(13)?
                };
                let span = Span::new(&self.module, token.token.span.start, value.span.end);
                self.postfix(Expr {
                    kind: ExprKind::Unary {
                        op: token.token.text,
                        value: Box::new(value),
                    },
                    span,
                })
            }
            "punctuation" if token.token.text == "(" => {
                self.advance();
                if self.optional(")") {
                    self.postfix(Expr {
                        kind: ExprKind::Unit,
                        span: Span::new(&self.module, token.token.span.start, self.previous_end()),
                    })
                } else {
                    let target = self.expression(0)?;
                    let expr = if self.optional("=") {
                        let value = self.expression(0)?;
                        Expr {
                            span: Span::new(&self.module, target.span.start, value.span.end),
                            kind: ExprKind::Assign {
                                target: Box::new(target),
                                value: Box::new(value),
                            },
                        }
                    } else {
                        target
                    };
                    self.expect(")")?;
                    self.postfix(expr)
                }
            }
            "punctuation" if token.token.text == "[" => self.list(),
            _ => self.error("expected expression"),
        }
    }

    fn match_expression(&mut self) -> Result<Expr, Vec<Diagnostic>> {
        let start = self.expect("match")?.span.start;
        let value = self.expression(0)?;
        self.expect("{")?;
        let mut arms = Vec::new();
        while !self.check("}") {
            if self.eof() {
                return self.error("expected `}` to close match");
            }
            let pattern_start = self.current_start();
            let pattern = self.pattern()?;
            self.expect("=>")?;
            let arm_value = self.expression(0)?;
            let arm_span = Span::new(&self.module, pattern_start, arm_value.span.end);
            arms.push(MatchArm {
                pattern,
                value: arm_value,
                span: arm_span,
            });
            if !self.optional(",") {
                break;
            }
        }
        let end = self.expect("}")?.span.end;
        self.postfix(Expr {
            kind: ExprKind::Match {
                value: Box::new(value),
                arms,
            },
            span: Span::new(&self.module, start, end),
        })
    }

    fn pattern(&mut self) -> Result<Pattern, Vec<Diagnostic>> {
        let token = self.current().cloned().ok_or_else(|| {
            vec![diagnostic(
                &self.module,
                "E_PARSE",
                "expected pattern",
                self.source_len,
                self.source_len,
            )]
        })?;
        match token.token.kind.as_str() {
            "number" => {
                self.advance();
                Ok(Pattern::Literal(Box::new(Expr {
                    kind: ExprKind::Number(token.token.text),
                    span: token.token.span,
                })))
            }
            "string" => {
                self.advance();
                Ok(Pattern::Literal(Box::new(Expr {
                    kind: ExprKind::Text(token.value.unwrap_or_default()),
                    span: token.token.span,
                })))
            }
            "keyword" if token.token.text == "true" || token.token.text == "false" => {
                self.advance();
                Ok(Pattern::Literal(Box::new(Expr {
                    kind: ExprKind::Bool(token.token.text == "true"),
                    span: token.token.span,
                })))
            }
            "punctuation" if token.token.text == "(" => {
                let start = self.advance().token.span.start;
                self.expect(")")?;
                Ok(Pattern::Literal(Box::new(Expr {
                    kind: ExprKind::Unit,
                    span: Span::new(&self.module, start, self.previous_end()),
                })))
            }
            "identifier" => {
                let (name, _) = self.qualified_identifier()?;
                if name == "_" {
                    return Ok(Pattern::Wildcard);
                }
                if self.check("{") {
                    return self.record_pattern(name);
                }
                if self.optional("(") {
                    let mut payload = Vec::new();
                    while !self.check(")") {
                        payload.push(self.pattern()?);
                        if !self.optional(",") {
                            break;
                        }
                    }
                    self.expect(")")?;
                    return Ok(Pattern::Case { name, payload });
                }
                if name.contains('.') || matches!(name.as_str(), "None" | "Some" | "Ok" | "Err") {
                    Ok(Pattern::Case {
                        name,
                        payload: Vec::new(),
                    })
                } else {
                    Ok(Pattern::Binding(name))
                }
            }
            _ => self.error("expected pattern"),
        }
    }

    fn record_pattern(&mut self, class: String) -> Result<Pattern, Vec<Diagnostic>> {
        self.expect("{")?;
        let mut fields = BTreeMap::new();
        while !self.check("}") {
            if self.eof() {
                return self.error("expected `}` to close record pattern");
            }
            let (name, _) = self.identifier()?;
            let pattern = if self.optional(":") {
                self.pattern()?
            } else {
                Pattern::Binding(name.clone())
            };
            if fields.insert(name.clone(), pattern).is_some() {
                return self.error(&format!("duplicate record pattern field `{name}`"));
            }
            if !self.optional(",") {
                break;
            }
        }
        self.expect("}")?;
        Ok(Pattern::Record { class, fields })
    }

    fn typed_intrinsic_ahead(&self, expr: &Expr) -> bool {
        let Some(name) = expression_path(expr) else {
            return false;
        };
        if !matches!(
            name.strip_prefix("builtin.").unwrap_or(&name),
            "get" | "has" | "query" | "bind" | "tensor"
        ) || !self.check("[")
        {
            return false;
        }
        let mut depth = 1usize;
        // Speculate only over type-shaped tokens. `get < 1` remains an ordinary
        // comparison when a lexical value happens to use an intrinsic's name.
        for (offset, token) in self.tokens.iter().skip(self.at + 1).enumerate() {
            if offset > MAX_NESTING * 4 {
                return false;
            }
            match token.token.text.as_str() {
                "[" => {
                    depth += 1;
                    if depth > MAX_NESTING {
                        return false;
                    }
                }
                "]" => {
                    depth -= 1;
                    if depth == 0 {
                        return self.tokens.get(self.at + offset + 2).is_none_or(|token| {
                            matches!(
                                token.token.text.as_str(),
                                "(" | ";"
                                    | ")"
                                    | ","
                                    | "]"
                                    | "}"
                                    | "."
                                    | "=="
                                    | "!="
                                    | "["
                                    | "<="
                                    | ">"
                                    | ">="
                                    | "+"
                                    | "-"
                                    | "*"
                                    | "/"
                                    | "%"
                                    | "@"
                                    | "and"
                                    | "or"
                            )
                        });
                    }
                }
                "." => (),
                _ if token.token.kind == "identifier" => (),
                _ => return false,
            }
        }
        false
    }

    fn typed_literal_ahead(&self, expr: &Expr) -> bool {
        let numeric = matches!(&expr.kind, ExprKind::Number(_))
            || matches!(&expr.kind, ExprKind::Unary { op, value }
                if op == "-" && matches!(value.kind, ExprKind::Number(_)));
        numeric
            && self.check(":")
            && self.tokens.get(self.at + 1).is_some_and(|token| {
                token.token.kind == "identifier"
                    && crate::data::named_dtype(&token.token.text).is_some()
            })
    }

    fn postfix(&mut self, mut expr: Expr) -> Result<Expr, Vec<Diagnostic>> {
        let mut chain_length = 0;
        loop {
            chain_length += 1;
            if chain_length > MAX_NESTING {
                return self.error("expression access chain exceeds nesting limit");
            }
            if self.typed_intrinsic_ahead(&expr) {
                self.expect("[")?;
                let ty = self.ty()?;
                self.expect("]")?;
                let name = expression_path(&expr).expect("typed intrinsic name checked above");
                if self.optional("(") {
                    let mut arguments = Vec::new();
                    while !self.check(")") {
                        arguments.push(self.expression(0)?);
                        if !self.optional(",") {
                            break;
                        }
                    }
                    let end = self.expect(")")?.span.end;
                    expr = Expr {
                        span: Span::new(&self.module, expr.span.start, end),
                        kind: ExprKind::TypedCall {
                            name,
                            ty,
                            arguments,
                        },
                    };
                } else {
                    expr = Expr {
                        span: Span::new(&self.module, expr.span.start, self.previous_end()),
                        kind: ExprKind::TypedFunction { name, ty },
                    };
                }
            } else if self.typed_literal_ahead(&expr) {
                let start = expr.span.start;
                self.expect(":")?;
                let ty = self.ty()?;
                let end = self.previous_end();
                expr = Expr {
                    kind: ExprKind::TypedLiteral {
                        value: Box::new(expr),
                        ty,
                    },
                    span: Span::new(&self.module, start, end),
                };
            } else if self.optional("(") {
                let mut arguments = Vec::new();
                while !self.check(")") {
                    arguments.push(self.expression(0)?);
                    if !self.optional(",") {
                        break;
                    }
                }
                let end = self.expect(")")?.span.end;
                let start = expr.span.start;
                expr = Expr {
                    kind: ExprKind::Call {
                        callee: Box::new(expr),
                        arguments,
                    },
                    span: Span::new(&self.module, start, end),
                };
            } else if self.optional(".") {
                let (field, field_span) = self.identifier()?;
                let start = expr.span.start;
                if field == "convert" && self.optional("[") {
                    let ty = self.ty()?;
                    let end = self.expect("]")?.span.end;
                    expr = Expr {
                        kind: ExprKind::TypedMethod {
                            object: Box::new(expr),
                            method: field,
                            ty,
                        },
                        span: Span::new(&self.module, start, end),
                    };
                    continue;
                }
                // A qualified class path is the one ambiguous `name.name {` form.
                // Restrict it to a plain leading name, leaving ordinary field access
                // such as `object.field` and native `builtin.sin()` unchanged.
                if is_uppercase_name(&field) && self.check("{") {
                    if let Some(prefix) = expression_path(&expr) {
                        expr = self.record(format!("{prefix}.{field}"), start)?;
                    } else {
                        expr = Expr {
                            kind: ExprKind::Field {
                                object: Box::new(expr),
                                field,
                            },
                            span: Span::new(&self.module, start, field_span.end),
                        };
                    }
                } else {
                    expr = Expr {
                        kind: ExprKind::Field {
                            object: Box::new(expr),
                            field,
                        },
                        span: Span::new(&self.module, start, field_span.end),
                    };
                }
            } else if self.optional("[") {
                let indices = self.indices()?;
                let end = self.expect("]")?.span.end;
                let start = expr.span.start;
                expr = Expr {
                    kind: ExprKind::Index {
                        object: Box::new(expr),
                        indices,
                    },
                    span: Span::new(&self.module, start, end),
                };
            } else if self.optional("?") {
                let start = expr.span.start;
                expr = Expr {
                    kind: ExprKind::Propagate(Box::new(expr)),
                    span: Span::new(&self.module, start, self.previous_end()),
                };
            } else {
                break;
            }
        }
        Ok(expr)
    }

    fn indices(&mut self) -> Result<Vec<IndexExpr>, Vec<Diagnostic>> {
        let mut indices = Vec::new();
        while !self.check("]") {
            if self.eof() {
                return self.error("expected `]` to close index");
            }
            indices.push(self.index_expr()?);
            if !self.optional(",") {
                break;
            }
        }
        if indices.is_empty() {
            return self.error("index requires at least one selector");
        }
        Ok(indices)
    }

    fn index_expr(&mut self) -> Result<IndexExpr, Vec<Diagnostic>> {
        if self.optional("...") {
            return Ok(IndexExpr::Ellipsis);
        }
        if matches!(self.text(), Some("None") | Some("newaxis")) {
            self.advance();
            return Ok(IndexExpr::NewAxis);
        }
        let start = if self.check(":") {
            None
        } else {
            Some(self.expression(0)?)
        };
        if !self.optional(":") {
            return Ok(IndexExpr::Index(
                start.expect("index expression is present"),
            ));
        }
        let stop = if self.check(":") || self.check(",") || self.check("]") {
            None
        } else {
            Some(self.expression(0)?)
        };
        let step = if self.optional(":") {
            if self.check(",") || self.check("]") {
                None
            } else {
                Some(self.expression(0)?)
            }
        } else {
            None
        };
        Ok(IndexExpr::Slice {
            start: start.map(Box::new),
            stop: stop.map(Box::new),
            step: step.map(Box::new),
        })
    }

    fn list(&mut self) -> Result<Expr, Vec<Diagnostic>> {
        let start = self.expect("[")?.span.start;
        let mut items = Vec::new();
        while !self.check("]") {
            if self.eof() {
                return self.error("expected `]` to close list");
            }
            items.push(self.expression(0)?);
            if !self.optional(",") {
                break;
            }
        }
        let end = self.expect("]")?.span.end;
        let expr = if self.optional(":") {
            let dtype = self.ty()?;
            Expr {
                kind: ExprKind::TensorLiteral {
                    values: items,
                    dtype,
                },
                span: Span::new(&self.module, start, self.previous_end()),
            }
        } else {
            Expr {
                kind: ExprKind::List(items),
                span: Span::new(&self.module, start, end),
            }
        };
        self.postfix(expr)
    }

    fn record(&mut self, class: String, start: usize) -> Result<Expr, Vec<Diagnostic>> {
        self.expect("{")?;
        let mut fields = BTreeMap::new();
        while !self.check("}") {
            if self.eof() {
                return self.error("expected `}` to close constructor");
            }
            let (name, _) = self.identifier()?;
            self.expect(":")?;
            let value = self.expression(0)?;
            if fields.insert(name.clone(), value).is_some() {
                return self.error(&format!("duplicate constructor field `{name}`"));
            }
            if !self.optional(",") {
                break;
            }
        }
        let end = self.expect("}")?.span.end;
        Ok(Expr {
            kind: ExprKind::Record { class, fields },
            span: Span::new(&self.module, start, end),
        })
    }

    fn infix_binding_power(&self) -> Option<(u8, u8)> {
        Some(match self.text()? {
            "or" => (1, 2),
            "and" => (3, 4),
            "==" | "!=" => (5, 6),
            "<" | "<=" | ">" | ">=" => (7, 8),
            "+" | "-" => (9, 10),
            "*" | "/" | "%" | "@" => (11, 12),
            _ => return None,
        })
    }
    fn separator(&mut self) {
        if !self.optional(";") {
            self.optional(",");
        }
    }
    fn enter(&mut self) -> Result<(), Vec<Diagnostic>> {
        self.nesting += 1;
        if self.nesting > MAX_NESTING {
            self.nesting -= 1;
            self.error("nesting exceeds the 64 level limit")
        } else {
            Ok(())
        }
    }
    fn leave(&mut self) {
        self.nesting = self.nesting.saturating_sub(1);
    }
    fn qualified_identifier(&mut self) -> Result<(String, Span), Vec<Diagnostic>> {
        let (mut name, mut span) = self.identifier()?;
        while self.optional(".") {
            let (part, next) = self.identifier()?;
            name.push('.');
            name.push_str(&part);
            span.end = next.end;
        }
        Ok((name, span))
    }
    fn identifier(&mut self) -> Result<(String, Span), Vec<Diagnostic>> {
        let token = self.current().cloned().ok_or_else(|| {
            vec![diagnostic(
                &self.module,
                "E_PARSE",
                "expected identifier",
                self.source_len,
                self.source_len,
            )]
        })?;
        if token.token.kind == "identifier" {
            self.advance();
            Ok((token.token.text, token.token.span))
        } else {
            self.error("expected identifier")
        }
    }
    fn expect(&mut self, expected: &str) -> Result<Token, Vec<Diagnostic>> {
        if self.check(expected) {
            Ok(self.advance().token)
        } else {
            self.error(&format!("expected `{expected}`"))
        }
    }
    fn optional(&mut self, text: &str) -> bool {
        if self.check(text) {
            self.advance();
            true
        } else {
            false
        }
    }
    fn check(&self, text: &str) -> bool {
        self.text() == Some(text)
    }
    fn text(&self) -> Option<&str> {
        self.current().map(|token| token.token.text.as_str())
    }
    fn current(&self) -> Option<&LexToken> {
        self.tokens.get(self.at)
    }
    fn current_start(&self) -> usize {
        self.current()
            .map_or(self.source_len, |token| token.token.span.start)
    }
    fn previous_end(&self) -> usize {
        self.tokens
            .get(self.at.saturating_sub(1))
            .map_or(self.source_len, |token| token.token.span.end)
    }
    fn advance(&mut self) -> LexToken {
        let token = self.tokens[self.at].clone();
        self.at += 1;
        token
    }
    fn eof(&self) -> bool {
        self.at >= self.tokens.len()
    }
    fn error<T>(&self, message: &str) -> Result<T, Vec<Diagnostic>> {
        let span = self.current().map_or_else(
            || Span::new(&self.module, self.source_len, self.source_len),
            |token| token.token.span.clone(),
        );
        Err(vec![Diagnostic::new("E_PARSE", message, span)])
    }
}

fn is_uppercase_name(name: &str) -> bool {
    name.as_bytes().first().is_some_and(u8::is_ascii_uppercase)
}

fn expression_path(expr: &Expr) -> Option<String> {
    match &expr.kind {
        ExprKind::Name(n) => Some(n.clone()),
        ExprKind::Field { object, field } => {
            Some(format!("{}.{}", expression_path(object)?, field))
        }
        _ => None,
    }
}

#[cfg(test)]
mod tests {
    use super::parse;
    use crate::ast::{ExprKind, IndexExpr, Item, StmtKind, Type};

    fn let_value(source: &str) -> crate::ast::Expr {
        let items = parse(source, "parser-test").expect("source parses");
        let Item::Statement(statement) = items.into_iter().next().expect("one item") else {
            panic!("expected statement");
        };
        let StmtKind::Let { value, .. } = statement.kind else {
            panic!("expected let statement");
        };
        value
    }

    #[test]
    fn parses_square_generics_and_typed_intrinsics_without_consuming_indexes() {
        let items = parse(
            "type Holder { values: List[Tensor[f64]]; ref: ComponentReference[Str]; } let getter = get[Holder]; let element = values[0];",
            "parser-test",
        )
        .expect("source parses");
        let Item::Class(class) = &items[0] else {
            panic!("expected class");
        };
        assert_eq!(
            class.fields[0].ty,
            Type::List(Box::new(Type::Tensor(Box::new(Type::named("f64")))))
        );
        assert_eq!(
            class.fields[1].ty,
            Type::ComponentReference(Box::new(Type::named("Str")))
        );
        let Item::Statement(statement) = &items[1] else {
            panic!("expected typed intrinsic binding");
        };
        assert!(matches!(
            statement.kind,
            StmtKind::Let {
                value: crate::ast::Expr {
                    kind: ExprKind::TypedFunction { ref name, .. },
                    ..
                },
                ..
            } if name == "get"
        ));
        let Item::Statement(statement) = &items[2] else {
            panic!("expected indexed binding");
        };
        assert!(matches!(
            statement.kind,
            StmtKind::Let {
                value: crate::ast::Expr { kind: ExprKind::Index { ref indices, .. }, .. },
                ..
            } if matches!(indices.as_slice(), [IndexExpr::Index(_)])
        ));
    }

    #[test]
    fn preserves_raw_numbers_matrix_multiply_and_numpy_selectors() {
        let value = let_value(
            "let result = tensor[184467440737095516160000, :, -2::-1, None, ...] @ other;",
        );
        let ExprKind::Binary { op, left, .. } = value.kind else {
            panic!("expected binary expression");
        };
        assert_eq!(op, "@");
        let ExprKind::Index { indices, .. } = left.kind else {
            panic!("expected index expression");
        };
        assert!(matches!(
            &indices[0],
            IndexExpr::Index(crate::ast::Expr { kind: ExprKind::Number(raw), .. })
                if raw == "184467440737095516160000"
        ));
        assert!(matches!(
            &indices[1],
            IndexExpr::Slice {
                start: None,
                stop: None,
                step: None
            }
        ));
        assert!(matches!(
            &indices[2],
            IndexExpr::Slice {
                start: Some(_),
                stop: None,
                step: Some(_)
            }
        ));
        assert!(matches!(&indices[3], IndexExpr::NewAxis));
        assert!(matches!(&indices[4], IndexExpr::Ellipsis));
    }

    #[test]
    fn rejects_angle_bracket_generics() {
        assert!(parse("let values: List<Number> = [];", "parser-test").is_err());
    }

    #[test]
    fn parses_algebraic_types_matches_propagation_and_tensors() {
        let items = parse(
            "type Point { x: f32, y: f32 } enum State { Idle, Moving(f32) } let result: Res[f32, Str] = match state { State.Idle => 0, State.Moving(speed) => speed, }; let point = match value { Point { x, y: _ } => x, }; let matrix = [[1, 2], [3, 4]]:f32; let propagated = result?;",
            "parser-test",
        )
        .expect("source parses");
        assert!(matches!(items[0], Item::Class(_)));
        assert!(matches!(items[1], Item::Enum(_)));
        let Item::Statement(statement) = &items[2] else {
            panic!("expected match binding");
        };
        assert!(matches!(
            statement.kind,
            StmtKind::Let {
                ty: Some(Type::Applied { ref name, ref arguments }),
                value: crate::ast::Expr { kind: ExprKind::Match { ref arms, .. }, .. },
                ..
            } if name == "Res" && arguments.len() == 2 && arms.len() == 2
        ));
        let Item::Statement(statement) = &items[4] else {
            panic!("expected tensor binding");
        };
        assert!(matches!(
            statement.kind,
            StmtKind::Let {
                value: crate::ast::Expr { kind: ExprKind::TensorLiteral { ref values, ref dtype }, .. },
                ..
            } if values.len() == 2 && *dtype == Type::named("f32")
        ));
        let Item::Statement(statement) = &items[5] else {
            panic!("expected propagation binding");
        };
        assert!(matches!(
            statement.kind,
            StmtKind::Let {
                value: crate::ast::Expr {
                    kind: ExprKind::Propagate(_),
                    ..
                },
                ..
            }
        ));

        let method = let_value("let converted = (a + b).convert[f32](matrix);");
        assert!(matches!(
            method.kind,
            ExprKind::Call { ref callee, .. }
                if matches!(callee.kind, ExprKind::TypedMethod { ref method, ref ty, .. }
                    if method == "convert" && *ty == Type::named("f32"))
        ));
    }

    #[test]
    fn rejects_legacy_class_declarations_with_migration_message() {
        let error = parse("class Point { x: f32 }", "parser-test").expect_err("class is retired");
        assert!(error[0].message.contains("renamed to `type`"));
    }

    #[test]
    fn parses_parenthesized_assignment_as_a_result_expression() {
        let value = let_value("let outcome = (matrix[:, 1:] = values)?;");
        let ExprKind::Propagate(assign) = value.kind else {
            panic!("expected propagated assignment");
        };
        assert!(matches!(assign.kind, ExprKind::Assign { .. }));
    }

    #[test]
    fn parses_typed_numeric_literals_without_consuming_slice_colons() {
        let positive = let_value("let value = 1:f32;");
        assert!(matches!(
            positive.kind,
            ExprKind::TypedLiteral { ref ty, .. } if *ty == Type::named("f32")
        ));
        let negative = let_value("let value = -128:i8;");
        assert!(matches!(
            negative.kind,
            ExprKind::TypedLiteral { ref value, ref ty }
                if *ty == Type::named("i8")
                    && matches!(value.kind, ExprKind::Unary { ref op, .. } if op == "-")
        ));
        let indexed = let_value("let value = rows[0:2];");
        assert!(matches!(indexed.kind, ExprKind::Index { .. }));
    }
}