//! OpenUI Lang's syntax: a lexer and a parser for the subset of v0.5 the app
//! renders. A program is one statement per line, `name = Expression`, with
//! `$name = default` declaring state. Lines inside brackets may wrap, since
//! models like to spread long arrays over several.
//!
//! Spec: <https://www.openui.com/docs/openui-lang/specification-v05>.

use std::fmt;

/// More statements than this is a program no answer should hold.
pub const MAX_STATEMENTS: usize = 500;

#[derive(Clone, Debug, PartialEq)]
pub enum Expr {
    Null,
    Bool(bool),
    Number(f64),
    String(String),
    Array(Vec<Expr>),
    Object(Vec<(String, Expr)>),
    /// Another statement, or a loop variable inside `@Each`.
    Ref(String),
    /// `$name`.
    State(String),
    /// `Type(args...)`: a component, or `Action([...])`.
    Call(String, Vec<Expr>),
    /// `@Name(args...)`.
    Builtin(String, Vec<Expr>),
    /// `a.b`, which plucks `b` from every element when `a` is an array.
    Member(Box<Expr>, String),
    Unary(UnaryOp, Box<Expr>),
    Binary(BinaryOp, Box<Expr>, Box<Expr>),
    Ternary(Box<Expr>, Box<Expr>, Box<Expr>),
}

#[derive(Clone, Copy, Debug, PartialEq, Eq)]
pub enum UnaryOp {
    Not,
    Neg,
}

#[derive(Clone, Copy, Debug, PartialEq, Eq)]
pub enum BinaryOp {
    Add,
    Sub,
    Mul,
    Div,
    Rem,
    Eq,
    Ne,
    Gt,
    Lt,
    Ge,
    Le,
    And,
    Or,
}

#[derive(Clone, Debug, PartialEq)]
pub struct Statement {
    pub name: String,
    /// Declared as `$name = default`.
    pub state: bool,
    pub expr: Expr,
    /// 1-based, for error messages.
    pub line: usize,
}

#[derive(Clone, Debug, Default, PartialEq)]
pub struct Program {
    pub statements: Vec<Statement>,
    /// Statements that didn't parse, as "Line 3: ..." messages. They're left
    /// out of `statements`, so the rest still renders.
    pub errors: Vec<String>,
}

impl Program {
    /// The statement the UI starts from: `root` if there is one, else the
    /// first that isn't a state declaration.
    pub fn root(&self) -> Option<&Statement> {
        self.statements
            .iter()
            .find(|statement| !statement.state && statement.name == "root")
            .or_else(|| self.statements.iter().find(|statement| !statement.state))
    }

    /// Names referenced but never defined, in order of first use. `@Each`
    /// loop variables count as defined everywhere, which is loose but keeps
    /// this a simple walk.
    pub fn undefined(&self) -> Vec<String> {
        fn walk<'a>(expr: &'a Expr, refs: &mut Vec<&'a str>, locals: &mut Vec<&'a str>) {
            match expr {
                Expr::Ref(name) => refs.push(name),
                Expr::Builtin(name, args) if name == "Each" => {
                    if let Some(Expr::String(local) | Expr::Ref(local)) = args.get(1) {
                        locals.push(local);
                    }
                    for (ix, arg) in args.iter().enumerate() {
                        if ix != 1 {
                            walk(arg, refs, locals);
                        }
                    }
                }
                Expr::Array(items) | Expr::Call(_, items) | Expr::Builtin(_, items) => {
                    items.iter().for_each(|item| walk(item, refs, locals))
                }
                Expr::Object(fields) => fields.iter().for_each(|(_, value)| walk(value, refs, locals)),
                Expr::Member(target, _) | Expr::Unary(_, target) => walk(target, refs, locals),
                Expr::Binary(_, left, right) => {
                    walk(left, refs, locals);
                    walk(right, refs, locals);
                }
                Expr::Ternary(a, b, c) => {
                    walk(a, refs, locals);
                    walk(b, refs, locals);
                    walk(c, refs, locals);
                }
                Expr::Null | Expr::Bool(_) | Expr::Number(_) | Expr::String(_) | Expr::State(_) => {}
            }
        }
        let (mut refs, mut locals) = (Vec::new(), Vec::new());
        for statement in &self.statements {
            walk(&statement.expr, &mut refs, &mut locals);
        }
        let mut missing: Vec<String> = Vec::new();
        for name in refs {
            let defined = locals.contains(&name) || self.statements.iter().any(|statement| !statement.state && statement.name == name);
            if !defined && !missing.iter().any(|known| known == name) {
                missing.push(name.to_string());
            }
        }
        missing
    }

    pub fn state_default(&self, name: &str) -> Option<&Expr> {
        self.statements.iter().rev().find(|statement| statement.state && statement.name == name).map(|statement| &statement.expr)
    }
}

#[derive(Clone, Debug, PartialEq)]
enum Token {
    Ident(String),
    State(String),
    Builtin(String),
    String(String),
    Number(f64),
    Punct(&'static str),
    /// A line break outside any brackets, which ends a statement.
    Newline,
}

impl fmt::Display for Token {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        match self {
            Token::Ident(name) => write!(f, "`{name}`"),
            Token::State(name) => write!(f, "`${name}`"),
            Token::Builtin(name) => write!(f, "`@{name}`"),
            Token::String(_) => write!(f, "a string"),
            Token::Number(number) => write!(f, "`{number}`"),
            Token::Punct(punct) => write!(f, "`{punct}`"),
            Token::Newline => write!(f, "the end of the line"),
        }
    }
}

/// Punctuation, longest first so `==` wins over `=`.
const PUNCTS: [&str; 24] = [
    "==", "!=", ">=", "<=", "&&", "||", "(", ")", "[", "]", "{", "}", ",", ":", ".", "?", "+", "-", "*", "/", "%", ">", "<",
    "!",
];

/// Splits source into tokens with their line numbers. A lexing error ends
/// the token stream there, with the error at that position.
fn lex(source: &str) -> (Vec<(Token, usize)>, Option<(String, usize)>) {
    let mut tokens = Vec::new();
    let mut chars = source.char_indices().peekable();
    let mut line = 1;
    let mut depth = 0usize;
    while let Some(&(at, c)) = chars.peek() {
        match c {
            '\n' => {
                chars.next();
                if depth == 0 && !matches!(tokens.last(), Some((Token::Newline, _)) | None) {
                    tokens.push((Token::Newline, line));
                }
                line += 1;
            }
            c if c.is_whitespace() => {
                chars.next();
            }
            '/' if source[at..].starts_with("//") => {
                while chars.next_if(|&(_, c)| c != '\n').is_some() {}
            }
            '"' | '\'' => {
                chars.next();
                let quote = c;
                let mut text = String::new();
                loop {
                    match chars.next() {
                        None => return (tokens, Some(("unterminated string".into(), line))),
                        Some((_, '\n')) if quote == '\'' => return (tokens, Some(("unterminated string".into(), line))),
                        Some((_, '\n')) => {
                            line += 1;
                            text.push('\n');
                        }
                        Some((_, c)) if c == quote => break,
                        Some((_, '\\')) => match chars.next() {
                            Some((_, 'n')) => text.push('\n'),
                            Some((_, 't')) => text.push('\t'),
                            Some((_, 'r')) => text.push('\r'),
                            Some((_, 'u')) => {
                                let hex: String = (0..4).filter_map(|_| chars.next_if(|(_, c)| c.is_ascii_hexdigit())).map(|(_, c)| c).collect();
                                match u32::from_str_radix(&hex, 16).ok().and_then(char::from_u32) {
                                    Some(c) => text.push(c),
                                    None => return (tokens, Some(("bad \\u escape".into(), line))),
                                }
                            }
                            Some((_, c)) => text.push(c),
                            None => return (tokens, Some(("unterminated string".into(), line))),
                        },
                        Some((_, c)) => text.push(c),
                    }
                }
                tokens.push((Token::String(text), line));
            }
            c if c.is_ascii_digit() => {
                let mut end = at;
                // After `.` a number is an index, so `rows.0.1` is two of them.
                let mut seen_dot = matches!(tokens.last(), Some((Token::Punct("."), _)));
                while let Some(&(ix, c)) = chars.peek() {
                    let digit_follows = source[ix + 1..].starts_with(|c: char| c.is_ascii_digit());
                    if c.is_ascii_digit() || c == '_' || (c == '.' && !seen_dot && digit_follows) {
                        seen_dot |= c == '.';
                        end = ix + c.len_utf8();
                        chars.next();
                    } else {
                        break;
                    }
                }
                let text = source[at..end].replace('_', "");
                match text.parse::<f64>() {
                    Ok(number) => tokens.push((Token::Number(number), line)),
                    Err(_) => return (tokens, Some((format!("bad number {text}"), line))),
                }
            }
            '$' | '@' => {
                chars.next();
                let name = ident(&mut chars);
                if name.is_empty() {
                    return (tokens, Some((format!("expected a name after `{c}`"), line)));
                }
                tokens.push((if c == '$' { Token::State(name) } else { Token::Builtin(name) }, line));
            }
            c if c.is_alphabetic() || c == '_' => {
                let name = ident(&mut chars);
                tokens.push((Token::Ident(name), line));
            }
            _ => {
                let Some(punct) = PUNCTS.iter().find(|punct| source[at..].starts_with(**punct)) else {
                    // `=` alone only separates a statement's name from its value.
                    if c == '=' {
                        chars.next();
                        tokens.push((Token::Punct("="), line));
                        continue;
                    }
                    return (tokens, Some((format!("unexpected `{c}`"), line)));
                };
                for _ in 0..punct.len() {
                    chars.next();
                }
                match *punct {
                    "(" | "[" | "{" => depth += 1,
                    ")" | "]" | "}" => depth = depth.saturating_sub(1),
                    _ => {}
                }
                tokens.push((Token::Punct(punct), line));
            }
        }
    }
    (tokens, None)
}

fn ident(chars: &mut std::iter::Peekable<std::str::CharIndices>) -> String {
    let mut name = String::new();
    while let Some((_, c)) = chars.next_if(|&(_, c)| c.is_alphanumeric() || c == '_') {
        name.push(c);
    }
    name
}

/// Parses a program. Statements that fail are skipped and reported in
/// `errors`; the rest are kept, so one bad line doesn't blank the UI.
pub fn parse(source: &str) -> Program {
    let (tokens, lex_error) = lex(source);
    let mut parser = Parser { tokens, pos: 0 };
    let mut program = Program::default();
    // A lexing error cuts the stream short, so the statement it hit is
    // incomplete. Drop it rather than report a misleading parse error.
    let lex_error_line = lex_error.as_ref().map(|(_, line)| *line);
    while parser.skip_newlines() {
        let start_line = parser.line();
        match parser.statement() {
            Ok(statement) => {
                if program.statements.len() >= MAX_STATEMENTS {
                    program.errors.push(format!("More than {MAX_STATEMENTS} statements"));
                    break;
                }
                program.statements.push(statement);
            }
            Err((message, line)) => {
                if parser.at_end() && lex_error_line.is_some() {
                    break;
                }
                program.errors.push(format!("Line {line}: {message}"));
                parser.skip_statement(start_line);
            }
        }
    }
    if let Some((message, line)) = lex_error {
        program.errors.push(format!("Line {line}: {message}"));
    }
    program
}

type ParseResult<T> = Result<T, (String, usize)>;

struct Parser {
    tokens: Vec<(Token, usize)>,
    pos: usize,
}

impl Parser {
    fn peek(&self) -> Option<&Token> {
        self.tokens.get(self.pos).map(|(token, _)| token)
    }

    fn line(&self) -> usize {
        self.tokens.get(self.pos).or(self.tokens.last()).map(|(_, line)| *line).unwrap_or(1)
    }

    fn at_end(&self) -> bool {
        self.pos >= self.tokens.len()
    }

    fn next(&mut self) -> Option<Token> {
        let token = self.tokens.get(self.pos).map(|(token, _)| token.clone());
        self.pos += 1;
        token
    }

    fn error<T>(&self, message: impl Into<String>) -> ParseResult<T> {
        Err((message.into(), self.line()))
    }

    fn unexpected<T>(&self, wanted: &str) -> ParseResult<T> {
        match self.peek() {
            Some(token) => self.error(format!("expected {wanted}, found {token}")),
            None => self.error(format!("expected {wanted}, found the end")),
        }
    }

    fn eat(&mut self, punct: &str) -> bool {
        if matches!(self.peek(), Some(Token::Punct(p)) if *p == punct) {
            self.pos += 1;
            true
        } else {
            false
        }
    }

    fn expect(&mut self, punct: &str) -> ParseResult<()> {
        if self.eat(punct) { Ok(()) } else { self.unexpected(&format!("`{punct}`")) }
    }

    /// Skips blank lines; returns whether a statement follows.
    fn skip_newlines(&mut self) -> bool {
        while matches!(self.peek(), Some(Token::Newline)) {
            self.pos += 1;
        }
        !self.at_end()
    }

    /// After an error, moves on to the next line after the statement's start.
    fn skip_statement(&mut self, start_line: usize) {
        while let Some((token, line)) = self.tokens.get(self.pos) {
            if *token == Token::Newline && *line >= start_line {
                break;
            }
            self.pos += 1;
        }
    }

    fn statement(&mut self) -> ParseResult<Statement> {
        let line = self.line();
        let (name, state) = match self.next() {
            Some(Token::Ident(name)) => (name, false),
            Some(Token::State(name)) => (name, true),
            _ => {
                self.pos -= 1;
                return self.unexpected("a statement like `name = ...`");
            }
        };
        self.expect("=")?;
        let expr = self.expr()?;
        match self.peek() {
            None | Some(Token::Newline) => Ok(Statement { name, state, expr, line }),
            Some(_) => self.unexpected("the end of the line"),
        }
    }

    fn expr(&mut self) -> ParseResult<Expr> {
        let condition = self.binary(0)?;
        if self.eat("?") {
            let then = self.expr()?;
            self.expect(":")?;
            let otherwise = self.expr()?;
            return Ok(Expr::Ternary(Box::new(condition), Box::new(then), Box::new(otherwise)));
        }
        Ok(condition)
    }

    /// Binary operators by precedence climbing, loosest first, as in C and JS.
    fn binary(&mut self, level: usize) -> ParseResult<Expr> {
        const LEVELS: [&[(&str, BinaryOp)]; 6] = [
            &[("||", BinaryOp::Or)],
            &[("&&", BinaryOp::And)],
            &[("==", BinaryOp::Eq), ("!=", BinaryOp::Ne)],
            &[(">=", BinaryOp::Ge), ("<=", BinaryOp::Le), (">", BinaryOp::Gt), ("<", BinaryOp::Lt)],
            &[("+", BinaryOp::Add), ("-", BinaryOp::Sub)],
            &[("*", BinaryOp::Mul), ("/", BinaryOp::Div), ("%", BinaryOp::Rem)],
        ];
        let Some(ops) = LEVELS.get(level) else {
            return self.unary();
        };
        let mut left = self.binary(level + 1)?;
        'outer: loop {
            for (punct, op) in *ops {
                if self.eat(punct) {
                    let right = self.binary(level + 1)?;
                    left = Expr::Binary(*op, Box::new(left), Box::new(right));
                    continue 'outer;
                }
            }
            return Ok(left);
        }
    }

    fn unary(&mut self) -> ParseResult<Expr> {
        if self.eat("!") {
            return Ok(Expr::Unary(UnaryOp::Not, Box::new(self.unary()?)));
        }
        if self.eat("-") {
            return Ok(match self.unary()? {
                Expr::Number(number) => Expr::Number(-number),
                expr => Expr::Unary(UnaryOp::Neg, Box::new(expr)),
            });
        }
        self.postfix()
    }

    fn postfix(&mut self) -> ParseResult<Expr> {
        let mut expr = self.primary()?;
        while self.eat(".") {
            let field = match self.next() {
                Some(Token::Ident(field)) => field,
                Some(Token::Number(index)) if index.fract() == 0. && index >= 0. => format!("{index}"),
                _ => {
                    self.pos -= 1;
                    return self.unexpected("a field name after `.`");
                }
            };
            expr = Expr::Member(Box::new(expr), field);
        }
        Ok(expr)
    }

    fn primary(&mut self) -> ParseResult<Expr> {
        let Some(token) = self.next() else {
            return self.error("expected a value, found the end");
        };
        Ok(match token {
            Token::Number(number) => Expr::Number(number),
            Token::String(text) => Expr::String(text),
            Token::State(name) => Expr::State(name),
            Token::Ident(name) => match name.as_str() {
                "true" => Expr::Bool(true),
                "false" => Expr::Bool(false),
                "null" => Expr::Null,
                _ if self.eat("(") => Expr::Call(name, self.list(")")?),
                _ => Expr::Ref(name),
            },
            Token::Builtin(name) => {
                self.expect("(")?;
                Expr::Builtin(name, self.list(")")?)
            }
            Token::Punct("[") => Expr::Array(self.list("]")?),
            Token::Punct("{") => Expr::Object(self.object()?),
            Token::Punct("(") => {
                let expr = self.expr()?;
                self.expect(")")?;
                expr
            }
            token => {
                self.pos -= 1;
                return self.error(format!("expected a value, found {token}"));
            }
        })
    }

    /// Comma-separated expressions up to `close`, allowing a trailing comma.
    fn list(&mut self, close: &str) -> ParseResult<Vec<Expr>> {
        let mut items = Vec::new();
        loop {
            if self.eat(close) {
                return Ok(items);
            }
            items.push(self.expr()?);
            if !self.eat(",") {
                self.expect(close)?;
                return Ok(items);
            }
        }
    }

    fn object(&mut self) -> ParseResult<Vec<(String, Expr)>> {
        let mut fields = Vec::new();
        loop {
            if self.eat("}") {
                return Ok(fields);
            }
            let key = match self.next() {
                Some(Token::Ident(key) | Token::String(key)) => key,
                _ => {
                    self.pos -= 1;
                    return self.unexpected("a key");
                }
            };
            self.expect(":")?;
            fields.push((key, self.expr()?));
            if !self.eat(",") {
                self.expect("}")?;
                return Ok(fields);
            }
        }
    }
}

#[cfg(test)]
mod tests {
    use super::{BinaryOp, Expr, parse};

    fn single(source: &str) -> Expr {
        let program = parse(source);
        assert!(program.errors.is_empty(), "{source}: {:?}", program.errors);
        program.statements.into_iter().next().map(|statement| statement.expr).unwrap_or(Expr::Null)
    }

    fn call(name: &str, args: Vec<Expr>) -> Expr {
        Expr::Call(name.into(), args)
    }

    fn string(text: &str) -> Expr {
        Expr::String(text.into())
    }

    #[::core::prelude::v1::test]
    fn syntax_page_example() {
        let program = parse(
            r#"root = Stack([title, form])
title = TextContent("Sign up", "large-heavy")
form = Form("signup", [nameField, emailField], actions)
nameField = FormControl("Name", Input("name", "Your name", "text", ["required"]))
emailField = FormControl("Email", Input("email", "you@example.com", "email", ["required", "email"]))
actions = Buttons([submitBtn, cancelBtn], "row")
submitBtn = Button("Submit", "submit:signup", "primary")
cancelBtn = Button("Cancel", "action:cancel", "secondary")"#,
        );
        assert!(program.errors.is_empty(), "{:?}", program.errors);
        assert_eq!(program.statements.len(), 8);
        assert_eq!(program.root().map(|root| root.name.as_str()), Some("root"));
        assert_eq!(
            program.statements[1].expr,
            call("TextContent", vec![string("Sign up"), string("large-heavy")])
        );
    }

    #[::core::prelude::v1::test]
    fn spec_examples() {
        for source in [
            r#"header = CardHeader("Title")"#,
            r#"$days = "7""#,
            r#"data = Query("tool", {}, {rows: []})"#,
            r#"kpi = TextContent("" + data.total)"#,
            r#"tbl = Table([Col("Title", data.rows.title)])   // plucks title from each row"#,
            r#"submitBtn = Button("Create", Action([@Run(mutation), @Run(query), @Reset($title)]))"#,
            r#"x = $show ? form : null"#,
            r#"result = Mutation("tool_name", {title: $title})"#,
            r#"data = Query("tool_name", {arg: value}, {rows: []}, 30)"#,
            r#"s = Select("days", $days, ["7", "30"])"#,
            "n = @Count(data.rows)",
        ] {
            single(source);
        }
        let program = parse(
            r#"root = Card([header, form])
header = CardHeader("Deploy", "Pick a target")
form = Form("deploy", [FormControl("Environment", Select("env", ["staging", "production"]))], Buttons([Button("Deploy", "submit:deploy", "primary")]))"#,
        );
        assert!(program.errors.is_empty(), "{:?}", program.errors);
        assert_eq!(program.statements.len(), 3);
    }

    #[::core::prelude::v1::test]
    fn precedence() {
        use BinaryOp::*;
        let n = Expr::Number;
        let bin = |op, a, b| Expr::Binary(op, Box::new(a), Box::new(b));
        assert_eq!(single("x = 1 + 2 * 3"), bin(Add, n(1.), bin(Mul, n(2.), n(3.))));
        assert_eq!(single("x = (1 + 2) * 3"), bin(Mul, bin(Add, n(1.), n(2.)), n(3.)));
        assert_eq!(single("x = 1 - 2 - 3"), bin(Sub, bin(Sub, n(1.), n(2.)), n(3.)));
        assert_eq!(
            single("x = 1 < 2 == true && !false || null"),
            bin(
                Or,
                bin(And, bin(Eq, bin(Lt, n(1.), n(2.)), Expr::Bool(true)), Expr::Unary(super::UnaryOp::Not, Box::new(Expr::Bool(false)))),
                Expr::Null
            )
        );
        assert_eq!(
            single("x = a ? b : c ? d : e"),
            Expr::Ternary(
                Box::new(Expr::Ref("a".into())),
                Box::new(Expr::Ref("b".into())),
                Box::new(Expr::Ternary(Box::new(Expr::Ref("c".into())), Box::new(Expr::Ref("d".into())), Box::new(Expr::Ref("e".into()))))
            )
        );
        assert_eq!(single("x = -5"), n(-5.));
        assert_eq!(single("x = 10 % 3 * 2"), bin(Mul, bin(Rem, n(10.), n(3.)), n(2.)));
    }

    #[::core::prelude::v1::test]
    fn strings_comments_and_wrapping() {
        assert_eq!(single(r#"x = "say \"hi\"\nnow""#), string("say \"hi\"\nnow"));
        assert_eq!(single("x = 'single'"), string("single"));
        assert_eq!(single(r#"x = "http://example.com" // a comment"#), string("http://example.com"));
        let program = parse("// heading\n\nroot = Stack([\n  a,\n  b,\n])\n\na = Tag(\"x\")\nb = Tag(\"y\")\n");
        assert!(program.errors.is_empty(), "{:?}", program.errors);
        assert_eq!(program.statements.len(), 3);
        assert_eq!(program.statements[1].line, 8);
    }

    #[::core::prelude::v1::test]
    fn bad_lines_are_skipped() {
        let program = parse("root = Stack([a])\na = Tag(\"x\" \"y\")\nb = Tag(\"z\")\nc = = 1");
        assert_eq!(program.statements.iter().map(|s| s.name.as_str()).collect::<Vec<_>>(), ["root", "b"]);
        assert_eq!(program.errors.len(), 2);
        assert!(program.errors[0].starts_with("Line 2:"), "{:?}", program.errors);
    }

    #[::core::prelude::v1::test]
    fn partial_last_line() {
        let program = parse("root = Stack([title])\ntitle = TextContent(\"Sig");
        assert_eq!(program.statements.len(), 1);
        let program = parse("root = Stack([title])\ntitle = TextContent(\"Sign up\", ");
        assert_eq!(program.statements.len(), 1);
        assert_eq!(program.errors.len(), 1);
    }

    #[::core::prelude::v1::test]
    fn undefined_references() {
        let program = parse("root = Stack([a, b, @Each(rows, \"r\", Tag(r.name)), b])\na = Tag(\"x\")\n$s = 1");
        assert_eq!(program.undefined(), ["b", "rows"]);
    }

    #[::core::prelude::v1::test]
    fn statement_cap() {
        let source: String = (0..600).map(|ix| format!("s{ix} = {ix}\n")).collect();
        let program = parse(&source);
        assert_eq!(program.statements.len(), super::MAX_STATEMENTS);
        assert!(!program.errors.is_empty());
    }
}