hidane-rules 0.2.0

//! The parser, with the official compiler's syntax errors.
//!
//! The official compiler is generated by ANTLR. Its messages come from three places, and this
//! parser reproduces each where the fixture (`tests/fixtures/rules_compile.json` in the
//! `hidane` crate) shows them:
//!
//! - ANTLR's own recovery: "mismatched input 'x' expecting {…}" and "missing 'x' at 'y'"
//!   (which put the parser in recovery mode: no other syntax error is reported until a token
//!   is matched), and "Unexpected 'x'." where ANTLR would say "extraneous input" or "no viable
//!   alternative". After an error the parser skips to a token that can follow, as ANTLR does.
//! - Error alternatives in the grammar, reported as they are parsed: "Missing 'if' before
//!   conditional expression.", "The 'match' body must contain at least one declaration.",
//!   "Forward slash '/' found where identifier or binding expected.", …
//! - The lexer's "token recognition error at: 'x'". The official compiler parses twice (a fast
//!   pass that stops at the first syntax error, then a pass with recovery) and reuses the
//!   tokens of the first, so a lexer error before the first syntax error is not reported when
//!   there is one.
//!
//! Lines after the first error do not always match: they depend on ANTLR's prediction, which
//! is not reproduced (`docs/parity-exceptions.md`).

use std::collections::HashMap;

use crate::{
    ast::*,
    diag::Diag,
    lexer::{self, Tok, Token},
};

/// A file as parsed: the declarations, before any check.
#[derive(Debug, Default)]
pub(crate) struct FileAst {
    pub version: Option<VersionDecl>,
    pub imports: Vec<Import>,
    pub functions: Vec<Function>,
    pub services: Vec<Service>,
    /// The parentheses around expressions, by the expression's byte range: the opening ones,
    /// outermost first. The AST leaves them out; they count towards an expression's depth.
    pub parens: HashMap<(usize, usize), Vec<Span>>,
}

#[derive(Debug)]
pub(crate) struct VersionDecl {
    pub value: String,
    /// The `rules_version` keyword.
    pub span: Span,
}

#[derive(Debug)]
pub(crate) struct Import {
    pub module: String,
    pub span: Span,
}

pub(crate) struct Parsed {
    pub file: FileAst,
    /// Syntax errors, the grammar's own errors and the lexer's, unsorted.
    pub diags: Vec<Diag>,
    /// Whether ANTLR's first pass would have stopped: later checks do not run.
    pub syntax_error: bool,
}

/// The type names `is` accepts.
const IS_TYPES: &[&str] = &[
    "bool",
    "bytes",
    "constraint",
    "duration",
    "float",
    "int",
    "latlng",
    "list",
    "vector",
    "set",
    "number",
    "map",
    "string",
    "timestamp",
    "path",
    "map_diff",
];

/// The tokens an expression starts with, in ANTLR's order.
const EXPRESSION_START: &str = "{'--', '++', '{', '[', '(', '-', '!', '/', 'false', 'null', \
     'true', PATH_SEGMENT, IDENTIFIER, NUM_INT, NUM_FLOAT, UNPAIRED_DOUBLE_QUOTE, \
     UNPAIRED_SINGLE_QUOTE, STRING, BYTES}";
/// What may follow `-`.
const NEGATION_OPERAND: &str = "{'{', '[', '(', '/', 'false', 'null', 'true', PATH_SEGMENT, \
     IDENTIFIER, NUM_INT, NUM_FLOAT, UNPAIRED_DOUBLE_QUOTE, UNPAIRED_SINGLE_QUOTE, STRING, BYTES}";
/// What may follow a segment of a `match` path.
const PATH_CONTINUATION: &str = "{'{', '/', PATH_SEGMENT}";
/// What may follow the value of a `let`.
const LET_VALUE_FOLLOW: &str = "{'&&', '.', '==', '>', '>=', '[', '<', '<=', '-', '%', '!=', \
     '||', '+', ';', '/', '*', '?', 'in', 'is'}";

/// Where a declaration is: what it may contain and where recovery stops.
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
enum Place {
    Service,
    Match,
}

impl Place {
    /// The tokens a declaration starts with here.
    fn starts(self, t: Tok) -> bool {
        matches!(
            t,
            Tok::Function | Tok::Match | Tok::PathSegment | Tok::Slash
        ) || (self == Self::Match && t == Tok::Allow)
    }

    /// Where skipping after an error stops: what can follow a declaration here or in an
    /// enclosing scope.
    fn stops(self, t: Tok) -> bool {
        self.starts(t) || matches!(t, Tok::RBrace | Tok::Import | Tok::Service | Tok::Eof)
    }
}

/// How deep `match` bodies may nest before the parser gives up (the compiler refuses more than
/// 10 levels, after parsing).
const MAX_BODY_DEPTH: usize = 1000;
/// How deep expressions may nest, and how long a chain of operators or of member accesses may
/// be, before the parser stops reading the statement. The compiler refuses nesting deeper than
/// 99 after parsing ("Expression is too complex to evaluate safely."); these bounds keep the
/// parser and the checks within their stack.
const MAX_NESTING: usize = 1_000;
const MAX_OPERATORS: usize = 100_000;
const MAX_ACCESSES: usize = 2_000;
const TOO_COMPLEX: &str = "Expression is too complex to evaluate safely.";

pub(crate) fn parse(src: &str) -> Parsed {
    let lexed = lexer::lex(src);
    let mut parser = Parser {
        src,
        toks: lexed.tokens,
        i: 0,
        diags: Vec::new(),
        recovering: false,
        failure: None,
        syntax_error: false,
        depth: 0,
        nesting: 0,
        abort: false,
        nest: 0,
        gave_up: false,
        parens: HashMap::new(),
    };
    let mut file = parser.file();
    file.parens = std::mem::take(&mut parser.parens);
    // Lexer errors are reported if ANTLR's first pass did not stop, or if they come after the
    // token it stopped at (the second pass lexes them).
    let frontier = parser.failure.map(|i| parser.toks[i].end);
    for error in lexed.errors {
        if frontier.is_none_or(|end| error.start >= end) {
            let span = Span {
                start: error.start,
                end: error.start + error.text.len(),
                line: error.line,
                column: error.column,
            };
            parser.diags.push(Diag::error(
                span,
                format!("token recognition error at: '{}'", error.text),
            ));
        }
    }
    Parsed {
        file,
        diags: parser.diags,
        syntax_error: parser.syntax_error,
    }
}

struct Parser<'a> {
    src: &'a str,
    toks: Vec<Token>,
    i: usize,
    diags: Vec<Diag>,
    /// ANTLR's error recovery mode: set by a reported mismatch, cleared by a matched token.
    recovering: bool,
    /// The first token a syntax error was found at.
    failure: Option<usize>,
    syntax_error: bool,
    depth: usize,
    /// How many brackets of an expression are open.
    nesting: usize,
    /// Unwinding to the statement after an error inside brackets, as ANTLR's prediction fails
    /// for the whole statement there, or after an expression too deep to read.
    abort: bool,
    /// How deep the expression being read is nested.
    nest: usize,
    /// Whether the parser stopped reading (declarations nested too deep): no more syntax errors.
    gave_up: bool,
    /// The parentheses around each expression, by its byte range: the opening ones, outermost
    /// first. They count towards an expression's depth.
    parens: HashMap<(usize, usize), Vec<Span>>,
}

impl Parser<'_> {
    // ----- tokens

    /// The kind of the `k`-th token from here (1 is the current one).
    fn la(&self, k: usize) -> Tok {
        self.token(k).kind
    }

    fn token(&self, k: usize) -> Token {
        let last = self.toks.len() - 1;
        self.toks[(self.i + k - 1).min(last)]
    }

    fn text(&self, token: Token) -> &str {
        if token.kind == Tok::Eof {
            "<EOF>"
        } else {
            &self.src[token.start..token.end]
        }
    }

    /// The token as ANTLR quotes it in messages.
    fn quoted(&self, token: Token) -> String {
        let text = self
            .text(token)
            .replace('\n', "\\n")
            .replace('\r', "\\r")
            .replace('\t', "\\t");
        format!("'{text}'")
    }

    /// Matches the current token.
    fn bump(&mut self) -> Token {
        let token = self.token(1);
        if token.kind != Tok::Eof {
            self.i += 1;
        }
        self.recovering = false;
        token
    }

    /// Skips the current token while recovering.
    fn skip(&mut self) {
        if self.la(1) != Tok::Eof {
            self.i += 1;
        }
    }

    fn skip_until(&mut self, stop: impl Fn(Tok) -> bool) {
        while !stop(self.la(1)) && self.la(1) != Tok::Eof {
            self.i += 1;
        }
    }

    fn span_of(token: Token) -> Span {
        Span {
            start: token.start,
            end: token.end,
            line: token.line,
            column: token.column,
        }
    }

    /// From the start of `first` to the end of the last token matched.
    fn span_from(&self, first: Span) -> Span {
        let end = if self.i == 0 {
            first.end
        } else {
            self.toks[self.i - 1].end.max(first.end)
        };
        Span { end, ..first }
    }

    // ----- errors

    fn fail_at(&mut self, k: usize) {
        if self.gave_up {
            return;
        }
        let at = (self.i + k - 1).min(self.toks.len() - 1);
        self.failure = Some(self.failure.map_or(at, |f| f.min(at)));
        self.syntax_error = true;
    }

    fn syntax(&mut self, token: Token, message: String) {
        if self.gave_up {
            return;
        }
        self.diags.push(Diag::error(Self::span_of(token), message));
    }

    /// "Unexpected 'x'." where ANTLR deletes an extraneous token or skips one in a loop: it
    /// does not enter recovery mode.
    fn unexpected(&mut self, k: usize) {
        self.fail_at(k);
        if !self.recovering {
            let token = self.token(k);
            let message = format!("Unexpected {}.", self.quoted(token));
            self.syntax(token, message);
        }
    }

    /// "Unexpected 'x'." where ANTLR finds no viable alternative.
    fn no_viable(&mut self, k: usize) {
        self.unexpected(k);
        self.recovering = true;
    }

    fn mismatch(&mut self, k: usize, expecting: &str) {
        self.fail_at(k);
        if !self.recovering {
            let token = self.token(k);
            let message = format!(
                "mismatched input {} expecting {expecting}",
                self.quoted(token)
            );
            self.syntax(token, message);
        }
        self.recovering = true;
    }

    fn missing(&mut self, expected: &str) {
        self.fail_at(1);
        if !self.recovering {
            let token = self.token(1);
            let message = format!("missing {expected} at {}", self.quoted(token));
            self.syntax(token, message);
        }
        self.recovering = true;
    }

    /// An error of the grammar itself, reported whatever the recovery state.
    fn grammar_error(&mut self, token: Token, message: &str) {
        self.diags
            .push(Diag::error(Self::span_of(token), message.to_owned()));
    }

    /// "Missing 'match' keyword before path.": the official compiler reports it for any syntax
    /// error in a path, at the path's start. It stops later checks.
    fn missing_match(&mut self, path_start: Token) {
        self.syntax_error = true;
        self.grammar_error(path_start, "Missing 'match' keyword before path.");
    }

    /// ANTLR's inline recovery for a single expected token: deletes one extraneous token,
    /// or conjures the expected one when the current token can follow it.
    fn expect(&mut self, kind: Tok, follows: impl Fn(Tok) -> bool) -> Result<Option<Token>, ()> {
        if self.la(1) == kind {
            return Ok(Some(self.bump()));
        }
        if self.la(2) == kind && self.la(1) != Tok::Eof {
            self.unexpected(1);
            self.skip();
            return Ok(Some(self.bump()));
        }
        if follows(self.la(1)) {
            self.missing(kind.display());
            return Ok(None);
        }
        self.mismatch(1, kind.display());
        Err(())
    }

    // ----- declarations

    fn file(&mut self) -> FileAst {
        let mut file = FileAst::default();
        if self.la(1) == Tok::RulesVersion {
            file.version = self.version();
        }
        let expecting = if self.toks[0].kind == Tok::RulesVersion {
            "{'function', 'import', 'service'}"
        } else {
            "{'function', 'import', 'service', 'rules_version'}"
        };
        let top = |t: Tok| matches!(t, Tok::Function | Tok::Import | Tok::Service | Tok::Eof);
        let mut first = true;
        loop {
            match self.la(1) {
                Tok::Function => {
                    if let Some(f) = self.function(None) {
                        file.functions.push(f);
                    }
                }
                Tok::Import => {
                    if let Some(i) = self.import() {
                        file.imports.push(i);
                    }
                }
                Tok::Service => {
                    if let Some(s) = self.service() {
                        file.services.push(s);
                    }
                }
                Tok::Eof => {
                    if first {
                        self.mismatch(1, expecting);
                    }
                    break;
                }
                _ if first => {
                    if top(self.la(2)) && self.la(2) != Tok::Eof {
                        self.unexpected(1);
                        self.skip();
                        continue;
                    }
                    self.mismatch(1, expecting);
                    self.skip_until(|_| false);
                    break;
                }
                _ => {
                    self.unexpected(1);
                    self.skip();
                    self.skip_until(top);
                    continue;
                }
            }
            first = false;
        }
        file
    }

    fn version(&mut self) -> Option<VersionDecl> {
        let keyword = Self::span_of(self.bump());
        let top = |t: Tok| matches!(t, Tok::Function | Tok::Import | Tok::Service | Tok::Eof);
        let ok = self
            .expect(Tok::Assign, |t| t == Tok::String)
            .and_then(|_| self.expect(Tok::String, |t| t == Tok::Semi || top(t)));
        let value = match ok {
            Ok(Some(token)) => {
                String::from_utf8_lossy(&lexer::unquote(self.text(token))).into_owned()
            }
            Ok(None) => String::new(),
            Err(()) => {
                self.skip_until(top);
                return None;
            }
        };
        if self.la(1) == Tok::Semi {
            self.bump();
        }
        Some(VersionDecl {
            value,
            span: keyword,
        })
    }

    fn import(&mut self) -> Option<Import> {
        let keyword = Self::span_of(self.bump());
        let top = |t: Tok| matches!(t, Tok::Function | Tok::Import | Tok::Service | Tok::Eof);
        if self.la(1) != Tok::String {
            self.no_viable(1);
            self.skip_until(top);
            return None;
        }
        let token = self.bump();
        let module = String::from_utf8_lossy(&lexer::unquote(self.text(token))).into_owned();
        if self.la(1) == Tok::Semi {
            self.bump();
        }
        Some(Import {
            module,
            span: keyword,
        })
    }

    fn service(&mut self) -> Option<Service> {
        let keyword = Self::span_of(self.bump());
        let top = |t: Tok| matches!(t, Tok::Function | Tok::Import | Tok::Service | Tok::Eof);
        if self.la(1) != Tok::Ident {
            self.no_viable(1);
            self.skip_until(top);
            return None;
        }
        let first = Self::span_of(self.token(1));
        let token = self.bump();
        let mut name = self.text(token).to_owned();
        while self.la(1) == Tok::Dot && self.la(2) == Tok::Ident {
            self.bump();
            let token = self.bump();
            name.push('.');
            name.push_str(self.text(token));
        }
        let name_span = self.span_from(first);
        // Which alternative: a body with declarations, or an empty one.
        if self.la(1) != Tok::LBrace {
            self.no_viable(1);
            self.skip_until(top);
            return None;
        }
        let mut body = Body::default();
        match self.la(2) {
            Tok::RBrace => {
                self.bump();
                let close = self.bump();
                self.grammar_error(
                    close,
                    "The 'service' body must contain at least one declaration.",
                );
            }
            t if Place::Service.starts(t) => {
                self.bump();
                body = self.body(Place::Service);
            }
            _ => {
                self.no_viable(2);
                self.skip_until(top);
                return None;
            }
        }
        Some(Service {
            name,
            name_span,
            body,
            span: self.span_from(keyword),
        })
    }

    /// The declarations of a service or match body after its `{`, up to and including `}`.
    fn body(&mut self, place: Place) -> Body {
        let mut body = Body::default();
        self.depth += 1;
        loop {
            if self.depth > MAX_BODY_DEPTH {
                // Far deeper than the compiler accepts, which the check of the `match`
                // hierarchy reports: the rest of the file is not read.
                self.gave_up = true;
                self.skip_until(|_| false);
                break;
            }
            match self.la(1) {
                Tok::Function => {
                    if let Some(f) = self.function(Some(place)) {
                        body.functions.push(f);
                    }
                }
                Tok::Match => {
                    if let Some(m) = self.match_declaration(place) {
                        body.matches.push(m);
                    }
                }
                Tok::PathSegment | Tok::Slash => self.match_without_keyword(place),
                Tok::Allow if place == Place::Match => {
                    if let Some(a) = self.allow() {
                        body.allows.push(a);
                    }
                }
                Tok::RBrace => {
                    self.bump();
                    break;
                }
                _ => {
                    self.unexpected(1);
                    self.skip();
                    self.skip_until(|t| place.stops(t));
                    if matches!(self.la(1), Tok::Eof | Tok::Import | Tok::Service) {
                        // The closing brace is missing.
                        let follows = |t: Tok| {
                            place == Place::Service
                                && matches!(
                                    t,
                                    Tok::Eof | Tok::Import | Tok::Service | Tok::Function
                                )
                        };
                        let _ = self.expect(Tok::RBrace, follows);
                        break;
                    }
                }
            }
        }
        self.depth -= 1;
        body
    }

    /// `match path { … }`.
    fn match_declaration(&mut self, place: Place) -> Option<Match> {
        let keyword = Self::span_of(self.bump());
        if !matches!(self.la(1), Tok::PathSegment | Tok::Slash) {
            self.no_viable(1);
            self.skip_until(|t| place.stops(t));
            return None;
        }
        let path_start = self.token(1);
        let path = self.match_path();
        let empty = |path| Match {
            path,
            body: Body::default(),
            span: keyword,
        };
        match self.la(1) {
            Tok::LBrace => match self.la(2) {
                t if Place::Match.starts(t) => {
                    self.bump();
                    let body = self.body(Place::Match);
                    Some(Match {
                        path,
                        body,
                        span: keyword,
                    })
                }
                Tok::RBrace => {
                    self.bump();
                    let close = self.bump();
                    self.grammar_error(
                        close,
                        "The 'match' body must contain at least one declaration.",
                    );
                    Some(empty(path))
                }
                _ => {
                    self.missing_match(path_start);
                    self.bump();
                    self.unexpected(1);
                    if self.la(1) != Tok::Eof && self.la(2) == Tok::RBrace {
                        self.unexpected(1);
                        self.skip();
                        self.bump();
                        return Some(empty(path));
                    }
                    self.mismatch(1, PATH_CONTINUATION);
                    self.skip_until(|t| place.stops(t));
                    None
                }
            },
            Tok::RBrace => {
                self.missing_match(path_start);
                self.unexpected(1);
                self.missing("'{'");
                self.bump();
                Some(empty(path))
            }
            _ => {
                self.missing_match(path_start);
                self.unexpected(1);
                self.mismatch(1, PATH_CONTINUATION);
                self.skip_until(|t| place.stops(t));
                None
            }
        }
    }

    /// A path where a declaration is expected: the official grammar takes it as a `match`
    /// without its keyword, followed by `{` and `}`.
    fn match_without_keyword(&mut self, place: Place) {
        let path_start = self.token(1);
        self.missing_match(path_start);
        self.match_path();
        if self.la(1) != Tok::LBrace {
            self.mismatch(1, PATH_CONTINUATION);
            self.skip_until(|t| place.stops(t));
            return;
        }
        self.bump();
        if self.la(1) == Tok::RBrace {
            self.bump();
        } else if self.la(1) != Tok::Eof && self.la(2) == Tok::RBrace {
            self.unexpected(1);
            self.skip();
            self.bump();
        } else if place.starts(self.la(1)) || self.la(1) == Tok::RBrace {
            self.missing("'}'");
        } else {
            self.mismatch(1, "'}'");
            self.skip_until(|t| place.stops(t));
        }
    }

    /// The segments of a `match` path: `/literal`, `/{var}`, `/{var=*}`, `/{var=**}`.
    fn match_path(&mut self) -> Vec<Segment> {
        let mut segments = Vec::new();
        loop {
            match self.la(1) {
                Tok::PathSegment => {
                    let token = self.bump();
                    let span = Self::span_of(token);
                    segments.push(Segment {
                        kind: SegmentKind::Literal(self.src[token.start + 1..token.end].to_owned()),
                        span,
                        name_span: span,
                    });
                }
                Tok::Slash => {
                    let slash = self.bump();
                    match self.binding() {
                        Some((kind, name_span)) => segments.push(Segment {
                            kind,
                            span: self.span_from(Self::span_of(slash)),
                            name_span,
                        }),
                        None => self.grammar_error(
                            slash,
                            "Forward slash '/' found where identifier or binding expected.",
                        ),
                    }
                }
                _ => return segments,
            }
        }
    }

    /// `{var}`, `{var=*}` or `{var=**}` after a slash.
    fn binding(&mut self) -> Option<(SegmentKind, Span)> {
        if self.la(1) != Tok::LBrace || self.la(2) != Tok::Ident {
            return None;
        }
        let length = match (self.la(3), self.la(4), self.la(5), self.la(6)) {
            (Tok::RBrace, ..) => 3,
            (Tok::Assign, Tok::Star, Tok::RBrace, _) => 5,
            (Tok::Assign, Tok::Star, Tok::Star, Tok::RBrace) => 6,
            _ => return None,
        };
        let name_token = self.token(2);
        let name = self.text(name_token).to_owned();
        for _ in 0..length {
            self.bump();
        }
        let kind = if length == 6 {
            SegmentKind::Recursive(name)
        } else {
            SegmentKind::Wildcard(name)
        };
        Some((kind, Self::span_of(name_token)))
    }

    /// `allow methods: if condition;`, with the grammar's own errors for the common mistakes.
    fn allow(&mut self) -> Option<Allow> {
        let keyword = Self::span_of(self.bump());
        let stops = |t: Tok| Place::Match.stops(t);
        if self.la(1) != Tok::Ident {
            if matches!(self.la(1), Tok::Colon | Tok::If) {
                let token = self.token(1);
                self.grammar_error(token, "Expected at least one 'operation' after 'allow'.");
            }
            self.no_viable(1);
            self.skip_until(stops);
            return None;
        }
        let mut methods = Vec::new();
        loop {
            let token = self.bump();
            let name = self.text(token).to_owned();
            methods.push(MethodName {
                method: Method::from_name(&name),
                name,
                span: Self::span_of(token),
            });
            if self.la(1) != Tok::Comma {
                break;
            }
            if self.la(2) != Tok::Ident {
                self.no_viable(1);
                self.skip_until(stops);
                return None;
            }
            self.bump();
        }
        let condition = match self.la(1) {
            Tok::Colon => {
                self.bump();
                match self.la(1) {
                    Tok::If => {
                        self.bump();
                        self.condition()
                    }
                    t if starts_expression(t) => {
                        let token = self.token(1);
                        self.grammar_error(token, "Missing 'if' before conditional expression.");
                        Some(self.statement(stops))
                    }
                    _ => {
                        self.no_viable(1);
                        self.skip_until(stops);
                        return None;
                    }
                }
            }
            Tok::If => {
                let token = self.token(1);
                self.grammar_error(token, "Missing ':' before 'if' condition.");
                self.bump();
                self.condition()
            }
            t if t == Tok::Semi || stops(t) => None,
            _ => {
                self.no_viable(1);
                self.skip_until(stops);
                return None;
            }
        };
        if self.la(1) == Tok::Semi {
            self.bump();
        }
        Some(Allow {
            methods,
            condition,
            span: keyword,
        })
    }

    /// The expression after `if`.
    fn condition(&mut self) -> Option<Expr> {
        if starts_expression(self.la(1)) {
            Some(self.statement(|t| Place::Match.stops(t)))
        } else {
            let token = self.token(1);
            self.grammar_error(token, "Missing conditional expression after 'if'.");
            None
        }
    }

    /// `function name(params) { let …; return …; }`. `place` is `None` at the top level.
    fn function(&mut self, place: Option<Place>) -> Option<Function> {
        let keyword = Self::span_of(self.bump());
        let stops = move |t: Tok| match place {
            Some(place) => place.stops(t),
            None => matches!(t, Tok::Function | Tok::Import | Tok::Service | Tok::Eof),
        };
        // The grammar's errors for a missing name (before a parameter list) or parameter list;
        // the rest is parsed.
        let name = match self.la(1) {
            Tok::Ident => self.ident(),
            Tok::LParen => {
                let token = self.token(1);
                self.grammar_error(token, "Missing 'function' id");
                Ident {
                    name: String::new(),
                    span: Self::span_of(token),
                }
            }
            _ => {
                self.no_viable(1);
                self.skip_until(stops);
                return None;
            }
        };
        let mut params = Vec::new();
        if self.la(1) != Tok::LParen {
            let token = self.token(1);
            self.grammar_error(token, "Missing 'function' signature");
        } else if self.la(2) == Tok::RParen {
            self.bump();
            self.bump();
        } else {
            self.bump();
            loop {
                if self.la(1) != Tok::Ident {
                    self.no_viable(1);
                    self.skip_until(stops);
                    return None;
                }
                params.push(self.ident());
                match self.la(1) {
                    Tok::Comma => {
                        self.bump();
                    }
                    Tok::RParen => {
                        self.bump();
                        break;
                    }
                    _ => {
                        self.no_viable(1);
                        self.skip_until(stops);
                        return None;
                    }
                }
            }
        }
        if self.la(1) != Tok::LBrace {
            self.no_viable(1);
            self.skip_until(stops);
            return None;
        }
        self.bump();
        let placeholder = |span| Expr {
            kind: ExprKind::Null,
            span,
        };
        if self.la(1) == Tok::RBrace {
            let close = self.bump();
            self.grammar_error(close, "Missing 'function' body");
            return Some(Function {
                name,
                params,
                lets: Vec::new(),
                result: placeholder(Self::span_of(close)),
                span: keyword,
            });
        }
        let mut lets = Vec::new();
        while self.la(1) == Tok::Let {
            lets.push(self.let_binding());
        }
        if self.la(1) == Tok::RBrace && !lets.is_empty() {
            // As measured: the brace is reported twice, the second time as if a `let` value
            // went on, and closes the function.
            self.unexpected(1);
            self.mismatch(1, LET_VALUE_FOLLOW);
            let close = self.bump();
            return Some(Function {
                name,
                params,
                lets,
                result: placeholder(Self::span_of(close)),
                span: keyword,
            });
        }
        if self.la(1) != Tok::Return {
            self.no_viable(1);
            self.skip_until(stops);
            return None;
        }
        self.bump();
        let result = if starts_expression(self.la(1)) {
            self.statement(stops)
        } else {
            self.missing_operand(EXPRESSION_START)
        };
        if self.la(1) == Tok::Semi {
            self.bump();
        }
        if self.la(1) == Tok::RBrace {
            self.bump();
        } else if self.la(1) != Tok::Eof && self.la(2) == Tok::RBrace {
            self.unexpected(1);
            self.skip();
            self.bump();
        } else {
            self.mismatch(1, "'}'");
            self.skip_until(stops);
        }
        Some(Function {
            name,
            params,
            lets,
            result,
            span: keyword,
        })
    }

    fn ident(&mut self) -> Ident {
        let token = self.bump();
        Ident {
            name: self.text(token).to_owned(),
            span: Self::span_of(token),
        }
    }

    /// `let name = value;`.
    fn let_binding(&mut self) -> Let {
        let span = Self::span_of(self.bump());
        let name = if self.la(1) == Tok::Ident {
            self.ident()
        } else {
            let token = self.token(1);
            self.mismatch(1, Tok::Ident.display());
            Ident {
                name: String::new(),
                span: Self::span_of(token),
            }
        };
        let _ = self.expect(Tok::Assign, starts_expression);
        let value = if starts_expression(self.la(1)) {
            self.statement(|t| {
                matches!(
                    t,
                    Tok::Let | Tok::Return | Tok::RBrace | Tok::Semi | Tok::Eof
                )
            })
        } else {
            self.missing_operand(EXPRESSION_START)
        };
        let _ = self.expect(Tok::Semi, |t| matches!(t, Tok::Let | Tok::Return));
        Let { name, value, span }
    }

    // ----- expressions

    /// The expression of a statement; after an error inside brackets, skips to `stops`.
    fn statement(&mut self, stops: impl Fn(Tok) -> bool) -> Expr {
        let e = self.expression();
        if self.abort {
            self.abort = false;
            self.skip_until(stops);
        }
        e
    }

    fn expression(&mut self) -> Expr {
        self.nested(Self::ternary)
    }

    /// Parses with `parse` one level deeper. Past [`MAX_NESTING`] the statement is given up
    /// (the check of the expression's depth then reports it).
    fn nested(&mut self, parse: fn(&mut Self) -> Expr) -> Expr {
        if self.nest >= MAX_NESTING {
            self.abort = true;
            return self.placeholder();
        }
        self.nest += 1;
        let e = parse(self);
        self.nest -= 1;
        e
    }

    /// Gives the statement up: an expression too long to keep.
    fn too_complex(&mut self) {
        let token = self.token(1);
        self.grammar_error(token, TOO_COMPLEX);
        self.abort = true;
    }

    fn placeholder(&self) -> Expr {
        Expr {
            kind: ExprKind::Null,
            span: Self::span_of(self.token(1)),
        }
    }

    fn ternary(&mut self) -> Expr {
        let condition = self.or();
        if self.abort || self.la(1) != Tok::Question {
            return condition;
        }
        let question = Self::span_of(self.bump());
        // Unlike CEL, the branch may itself be a conditional without parentheses.
        let then = self.expression();
        if self.la(1) == Tok::Colon {
            self.bump();
        } else if starts_expression(self.la(1)) {
            self.missing(Tok::Colon.display());
        } else {
            self.mismatch(
                1,
                "{'&&', ':', '.', '==', '>', '>=', '[', '<', '<=', '-', '%', '!=', '||', '+', \
                 '/', '*', '?', 'in', 'is'}",
            );
            return condition;
        }
        let otherwise = self.expression();
        let span = Span {
            end: otherwise.span.end.max(condition.span.end),
            ..condition.span
        };
        Expr {
            kind: ExprKind::Ternary {
                condition: Box::new(condition),
                question,
                then: Box::new(then),
                otherwise: Box::new(otherwise),
            },
            span,
        }
    }

    fn binary_loop(&mut self, ops: &[(Tok, BinaryOp)], next: fn(&mut Self) -> Expr) -> Expr {
        let mut left = next(self);
        let mut count = 0;
        while let Some(&(_, op)) = ops.iter().find(|(t, _)| *t == self.la(1) && !self.abort) {
            count += 1;
            if count > MAX_OPERATORS {
                // Far deeper than the compiler accepts; the depth check reports it.
                self.abort = true;
                break;
            }
            let op_span = Self::span_of(self.bump());
            let right = self.operand(next);
            left = binary(op, op_span, left, right);
        }
        left
    }

    /// An operand after an operator: if the token cannot start one but the next can, the
    /// token is extraneous.
    fn operand(&mut self, next: fn(&mut Self) -> Expr) -> Expr {
        if starts_expression(self.la(1)) {
            return next(self);
        }
        if self.la(1) != Tok::Eof && starts_expression(self.la(2)) {
            self.unexpected(1);
            self.skip();
            return next(self);
        }
        self.missing_operand(EXPRESSION_START)
    }

    /// No operand where one is required. Inside brackets the official compiler fails the
    /// whole statement ("Unexpected"); elsewhere it expects an expression.
    fn missing_operand(&mut self, expecting: &str) -> Expr {
        let placeholder = self.placeholder();
        if self.nesting > 0 {
            self.no_viable(1);
            self.abort = true;
            return placeholder;
        }
        self.mismatch(1, expecting);
        self.skip_until(|t| {
            matches!(
                t,
                Tok::Semi
                    | Tok::RBrace
                    | Tok::RParen
                    | Tok::RBracket
                    | Tok::Comma
                    | Tok::Colon
                    | Tok::Allow
                    | Tok::Match
                    | Tok::Function
                    | Tok::Let
                    | Tok::Return
                    | Tok::Eof
            ) || binary_op(t).is_some()
        });
        placeholder
    }

    fn or(&mut self) -> Expr {
        self.binary_loop(&[(Tok::OrOr, BinaryOp::Or)], Self::and)
    }

    fn and(&mut self) -> Expr {
        self.binary_loop(&[(Tok::AndAnd, BinaryOp::And)], Self::relation)
    }

    fn relation(&mut self) -> Expr {
        let mut left = self.additive();
        for count in 0.. {
            if self.abort {
                break;
            }
            if count >= MAX_OPERATORS {
                self.abort = true;
                break;
            }
            let op = match self.la(1) {
                Tok::EqEq => BinaryOp::Eq,
                Tok::Ne => BinaryOp::Ne,
                Tok::Lt => BinaryOp::Lt,
                Tok::Le => BinaryOp::Le,
                Tok::Gt => BinaryOp::Gt,
                Tok::Ge => BinaryOp::Ge,
                Tok::In => BinaryOp::In,
                Tok::Is => {
                    left = self.is(left);
                    continue;
                }
                _ => return left,
            };
            let op_span = Self::span_of(self.bump());
            let right = self.operand(Self::additive);
            left = binary(op, op_span, left, right);
        }
        left
    }

    /// `value is type`. An unknown type is the grammar's error, reported at the token after it.
    fn is(&mut self, value: Expr) -> Expr {
        let keyword = Self::span_of(self.bump());
        let type_token = self.token(1);
        let type_name = match self.la(1) {
            Tok::Ident => {
                self.bump();
                self.text(type_token).to_owned()
            }
            t if !starts_expression(t) || t == Tok::Eof => {
                self.missing(Tok::Ident.display());
                "<missing IDENTIFIER>".to_owned()
            }
            _ => {
                self.mismatch(1, Tok::Ident.display());
                self.skip();
                self.text(type_token).to_owned()
            }
        };
        if !IS_TYPES.contains(&type_name.as_str()) {
            let after = self.token(1);
            self.grammar_error(
                after,
                &format!(
                    "An unsupported type identifier was used with the 'is' operator. Received \
                     {type_name}. Expected one of {}",
                    IS_TYPES.join(",")
                ),
            );
        }
        let span = self.span_from(value.span);
        Expr {
            kind: ExprKind::Is {
                value: Box::new(value),
                keyword,
                type_name: Ident {
                    name: type_name,
                    span: Self::span_of(type_token),
                },
            },
            span,
        }
    }

    fn additive(&mut self) -> Expr {
        self.binary_loop(
            &[(Tok::Plus, BinaryOp::Add), (Tok::Minus, BinaryOp::Sub)],
            Self::multiplicative,
        )
    }

    fn multiplicative(&mut self) -> Expr {
        self.binary_loop(
            &[
                (Tok::Star, BinaryOp::Mul),
                (Tok::Slash, BinaryOp::Div),
                (Tok::Percent, BinaryOp::Mod),
            ],
            Self::unary,
        )
    }

    fn unary(&mut self) -> Expr {
        let start = Self::span_of(self.token(1));
        match self.la(1) {
            Tok::Not => {
                self.bump();
                let operand = self.nested(|p| p.operand(Self::unary));
                Expr {
                    span: self.span_from(start),
                    kind: ExprKind::Unary {
                        op: UnaryOp::Not,
                        operand: Box::new(operand),
                    },
                }
            }
            Tok::Minus => {
                self.bump();
                // -9223372036854775808 is a literal, not the negation of one out of range.
                if self.la(1) == Tok::Int
                    && self.text(self.token(1)) == "9223372036854775808"
                    && !matches!(self.la(2), Tok::Dot | Tok::LBracket)
                {
                    self.bump();
                    return Expr {
                        kind: ExprKind::Int(i64::MIN),
                        span: self.span_from(start),
                    };
                }
                let operand = if starts_primary(self.la(1)) {
                    self.postfix()
                } else {
                    self.missing_operand(NEGATION_OPERAND)
                };
                Expr {
                    span: self.span_from(start),
                    kind: ExprKind::Unary {
                        op: UnaryOp::Neg,
                        operand: Box::new(operand),
                    },
                }
            }
            Tok::Dec | Tok::Inc => {
                self.bump();
                let valid = starts_primary(self.la(1));
                // Inside brackets that then fail to parse, ANTLR's prediction fails before the
                // grammar's error is reached.
                if valid || self.nesting == 0 {
                    let after = self.token(1);
                    self.grammar_error(
                        after,
                        "Increment (++) and decrement (--) operators are not supported.",
                    );
                }
                if !valid {
                    self.no_viable(1);
                    return self.placeholder();
                }
                self.postfix()
            }
            _ => self.postfix(),
        }
    }

    fn postfix(&mut self) -> Expr {
        let mut e = self.primary();
        for count in 0.. {
            if self.abort {
                return e;
            }
            if count >= MAX_ACCESSES && matches!(self.la(1), Tok::Dot | Tok::LBracket) {
                // The compiler sets no limit here, and fails far later (a 500 at about 6,500).
                self.too_complex();
                return e;
            }
            match self.la(1) {
                Tok::Dot => {
                    // A field may be named by any word but `rules_version`; a method only by
                    // an identifier.
                    if !self.la(2).is_word() || self.la(2) == Tok::RulesVersion {
                        self.bump();
                        self.no_viable(1);
                        return e;
                    }
                    self.bump();
                    if self.la(1) != Tok::Ident && self.la(2) == Tok::LParen {
                        // ANTLR fails at the parenthesis before matching the keyword, and
                        // recovery may then take it for a declaration (`function`).
                        self.no_viable(2);
                        return e;
                    }
                    let name = self.ident();
                    if self.la(1) == Tok::LParen {
                        self.bump();
                        let args = self.list(Tok::RParen);
                        let span = self.span_from(e.span);
                        e = Expr {
                            kind: ExprKind::Call {
                                callee: Callee::Method {
                                    receiver: Box::new(e),
                                    name,
                                },
                                args,
                            },
                            span,
                        };
                    } else {
                        let span = self.span_from(e.span);
                        e = Expr {
                            kind: ExprKind::Member {
                                object: Box::new(e),
                                field: name,
                            },
                            span,
                        };
                    }
                }
                Tok::LBracket => {
                    self.bump();
                    self.nesting += 1;
                    let index = self.operand(Self::expression);
                    let end = if self.la(1) == Tok::Colon && !self.abort {
                        self.bump();
                        Some(self.operand(Self::expression))
                    } else {
                        None
                    };
                    self.close(Tok::RBracket);
                    self.nesting -= 1;
                    let span = self.span_from(e.span);
                    let kind = match end {
                        Some(end) => ExprKind::Slice {
                            object: Box::new(e),
                            start: Box::new(index),
                            end: Box::new(end),
                        },
                        None => ExprKind::Index {
                            object: Box::new(e),
                            index: Box::new(index),
                        },
                    };
                    e = Expr { kind, span };
                }
                _ => return e,
            }
        }
        e
    }

    /// A closing token: an extraneous token before it is deleted; otherwise its absence is
    /// "Unexpected" (ANTLR finds no viable alternative there).
    fn close(&mut self, kind: Tok) {
        if self.abort {
            return;
        }
        if self.la(1) == kind {
            self.bump();
        } else if self.la(1) != Tok::Eof && self.la(2) == kind {
            self.unexpected(1);
            self.skip();
            self.bump();
        } else {
            self.no_viable(1);
        }
    }

    /// Comma-separated expressions up to `close` (a trailing comma is allowed), after the
    /// opening token.
    fn list(&mut self, close: Tok) -> Vec<Expr> {
        self.nesting += 1;
        let items = self.items(close);
        self.nesting -= 1;
        items
    }

    fn items(&mut self, close: Tok) -> Vec<Expr> {
        let mut items = Vec::new();
        while self.la(1) != close {
            items.push(self.operand(Self::expression));
            if self.la(1) == Tok::Comma && !self.abort {
                self.bump();
            } else {
                break;
            }
        }
        self.close(close);
        items
    }

    fn primary(&mut self) -> Expr {
        let token = self.token(1);
        let start = Self::span_of(token);
        let kind = match token.kind {
            Tok::Null => {
                self.bump();
                ExprKind::Null
            }
            Tok::True | Tok::False => {
                self.bump();
                ExprKind::Bool(token.kind == Tok::True)
            }
            Tok::Int => {
                self.bump();
                let text = self.text(token);
                text.parse()
                    .map_or_else(|_| ExprKind::IntOverflow(text.to_owned()), ExprKind::Int)
            }
            Tok::Float => {
                self.bump();
                ExprKind::Float(self.text(token).parse().unwrap_or(f64::NAN))
            }
            Tok::String => {
                self.bump();
                ExprKind::String(
                    String::from_utf8_lossy(&lexer::unquote(self.text(token))).into_owned(),
                )
            }
            Tok::Bytes => {
                self.bump();
                ExprKind::Bytes(lexer::unquote(self.text(token)))
            }
            Tok::UnpairedSingle | Tok::UnpairedDouble => {
                self.bump();
                // Inside brackets, which an unclosed string cannot close, ANTLR's prediction
                // fails first and the grammar's error is not reached.
                if self.nesting == 0 {
                    let quote = if token.kind == Tok::UnpairedSingle {
                        '\''
                    } else {
                        '"'
                    };
                    let after = self.token(1);
                    self.grammar_error(after, &format!("Missing a closing {quote}"));
                }
                ExprKind::String(String::new())
            }
            Tok::Ident => return self.identifier(),
            Tok::LParen => {
                // The expression keeps its own span: diagnostics point inside the parentheses,
                // which are kept aside for the depth check.
                self.bump();
                self.nesting += 1;
                let inner = self.operand(Self::expression);
                self.close(Tok::RParen);
                self.nesting -= 1;
                self.parens
                    .entry((inner.span.start, inner.span.end))
                    .or_default()
                    .insert(0, start);
                return inner;
            }
            Tok::LBracket => {
                self.bump();
                ExprKind::List(self.list(Tok::RBracket))
            }
            Tok::LBrace => {
                self.bump();
                ExprKind::Map(self.map())
            }
            Tok::PathSegment | Tok::Slash => return self.path(),
            _ => return self.missing_operand(EXPRESSION_START),
        };
        Expr {
            kind,
            span: self.span_from(start),
        }
    }

    /// A name: a variable, a call, or a call in a namespace (`math.abs(x)`).
    fn identifier(&mut self) -> Expr {
        let name = self.ident();
        if self.la(1) == Tok::LParen {
            self.bump();
            let args = self.list(Tok::RParen);
            return Expr {
                span: self.span_from(name.span),
                kind: ExprKind::Call {
                    callee: Callee::Global(name),
                    args,
                },
            };
        }
        if is_package(&name.name)
            && self.la(1) == Tok::Dot
            && self.la(2) == Tok::Ident
            && self.la(3) == Tok::LParen
        {
            self.bump();
            let function = self.ident();
            self.bump();
            let args = self.list(Tok::RParen);
            return Expr {
                span: self.span_from(name.span),
                kind: ExprKind::Call {
                    callee: Callee::Namespaced {
                        namespace: name,
                        name: function,
                    },
                    args,
                },
            };
        }
        Expr {
            span: name.span,
            kind: ExprKind::Ident(name.name),
        }
    }

    /// `{key: value, …}` after the `{`.
    fn map(&mut self) -> Vec<(Expr, Expr)> {
        self.nesting += 1;
        let entries = self.entries();
        self.nesting -= 1;
        entries
    }

    fn entries(&mut self) -> Vec<(Expr, Expr)> {
        let mut entries = Vec::new();
        while self.la(1) != Tok::RBrace {
            let key = self.operand(Self::expression);
            if self.abort {
                return entries;
            }
            if self.la(1) == Tok::Colon {
                self.bump();
            } else if self.la(1) != Tok::Eof && self.la(2) == Tok::Colon {
                self.unexpected(1);
                self.skip();
                self.bump();
            } else {
                self.no_viable(1);
                self.abort = true;
                return entries;
            }
            let value = self.operand(Self::expression);
            entries.push((key, value));
            if self.la(1) == Tok::Comma && !self.abort {
                self.bump();
            } else {
                break;
            }
        }
        self.close(Tok::RBrace);
        entries
    }

    /// A path literal: `/segment` and `/$(expr)` parts.
    fn path(&mut self) -> Expr {
        let start_token = self.token(1);
        let start = Self::span_of(start_token);
        let mut parts = Vec::new();
        loop {
            match self.la(1) {
                Tok::PathSegment => {
                    let token = self.bump();
                    parts.push(PathPart::Segment(
                        self.src[token.start + 1..token.end].to_owned(),
                    ));
                }
                Tok::Slash if self.la(2) == Tok::Dollar && self.la(3) == Tok::LParen => {
                    self.bump();
                    self.bump();
                    self.bump();
                    self.nesting += 1;
                    let e = self.operand(Self::expression);
                    self.nesting -= 1;
                    if self.abort {
                        parts.push(PathPart::Expr(e));
                        break;
                    } else if self.la(1) == Tok::RParen {
                        self.bump();
                    } else {
                        self.missing_match(start_token);
                        self.no_viable(1);
                        break;
                    }
                    parts.push(PathPart::Expr(e));
                }
                Tok::Slash => {
                    let slash = self.bump();
                    self.grammar_error(
                        slash,
                        "Forward slash '/' found where identifier or binding expected.",
                    );
                }
                _ => break,
            }
        }
        Expr {
            kind: ExprKind::Path(parts),
            span: self.span_from(start),
        }
    }
}

fn binary(op: BinaryOp, op_span: Span, left: Expr, right: Expr) -> Expr {
    let span = Span {
        end: right.span.end.max(left.span.end),
        ..left.span
    };
    Expr {
        kind: ExprKind::Binary {
            op,
            op_span,
            left: Box::new(left),
            right: Box::new(right),
        },
        span,
    }
}

fn binary_op(t: Tok) -> Option<BinaryOp> {
    Some(match t {
        Tok::OrOr => BinaryOp::Or,
        Tok::AndAnd => BinaryOp::And,
        Tok::EqEq => BinaryOp::Eq,
        Tok::Ne => BinaryOp::Ne,
        Tok::Lt => BinaryOp::Lt,
        Tok::Le => BinaryOp::Le,
        Tok::Gt => BinaryOp::Gt,
        Tok::Ge => BinaryOp::Ge,
        Tok::In => BinaryOp::In,
        Tok::Plus => BinaryOp::Add,
        Tok::Minus => BinaryOp::Sub,
        Tok::Star => BinaryOp::Mul,
        Tok::Slash => BinaryOp::Div,
        Tok::Percent => BinaryOp::Mod,
        _ => return None,
    })
}

/// Whether an expression can start with `t`.
pub(crate) fn starts_expression(t: Tok) -> bool {
    matches!(t, Tok::Dec | Tok::Inc | Tok::Minus | Tok::Not) || starts_primary(t)
}

fn starts_primary(t: Tok) -> bool {
    matches!(
        t,
        Tok::LBrace
            | Tok::LBracket
            | Tok::LParen
            | Tok::Slash
            | Tok::False
            | Tok::Null
            | Tok::True
            | Tok::PathSegment
            | Tok::Ident
            | Tok::Int
            | Tok::Float
            | Tok::UnpairedDouble
            | Tok::UnpairedSingle
            | Tok::String
            | Tok::Bytes
    )
}

/// The namespaces of global functions: `math.abs(x)`. They are not variables.
pub(crate) fn is_package(name: &str) -> bool {
    matches!(
        name,
        "math" | "duration" | "timestamp" | "latlng" | "hashing"
    )
}

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

    fn file(src: &str) -> FileAst {
        let parsed = parse(src);
        assert!(parsed.diags.is_empty(), "{:?}", parsed.diags);
        parsed.file
    }

    /// The condition of the first `allow` of the first `match` in the first service.
    fn condition(expr: &str) -> Expr {
        let src = format!("service s {{ match /a {{ allow read: if {expr}; }} }}");
        let mut f = file(&src);
        f.services
            .remove(0)
            .body
            .matches
            .remove(0)
            .body
            .allows
            .remove(0)
            .condition
            .unwrap()
    }

    /// The expression's shape, with its operators.
    fn shape(e: &Expr) -> String {
        match &e.kind {
            ExprKind::Null => "null".into(),
            ExprKind::Bool(b) => b.to_string(),
            ExprKind::Int(i) => i.to_string(),
            ExprKind::IntOverflow(s) => format!("overflow {s}"),
            ExprKind::Float(f) => format!("{f:?}"),
            ExprKind::String(s) => format!("{s:?}"),
            ExprKind::Bytes(b) => format!("b{b:?}"),
            ExprKind::Ident(n) => n.clone(),
            ExprKind::List(items) => format!(
                "[{}]",
                items.iter().map(shape).collect::<Vec<_>>().join(", ")
            ),
            ExprKind::Map(entries) => format!(
                "{{{}}}",
                entries
                    .iter()
                    .map(|(k, v)| format!("{}: {}", shape(k), shape(v)))
                    .collect::<Vec<_>>()
                    .join(", ")
            ),
            ExprKind::Path(parts) => parts
                .iter()
                .map(|p| match p {
                    PathPart::Segment(s) => format!("/{s}"),
                    PathPart::Expr(e) => format!("/$({})", shape(e)),
                })
                .collect(),
            ExprKind::Member { object, field } => format!("{}.{}", shape(object), field.name),
            ExprKind::Index { object, index } => format!("{}[{}]", shape(object), shape(index)),
            ExprKind::Slice { object, start, end } => {
                format!("{}[{}:{}]", shape(object), shape(start), shape(end))
            }
            ExprKind::Call { callee, args } => {
                let args = args.iter().map(shape).collect::<Vec<_>>().join(", ");
                match callee {
                    Callee::Global(n) => format!("{}({args})", n.name),
                    Callee::Namespaced { namespace, name } => {
                        format!("{}.{}({args})", namespace.name, name.name)
                    }
                    Callee::Method { receiver, name } => {
                        format!("{}.{}({args})", shape(receiver), name.name)
                    }
                }
            }
            ExprKind::Unary { op, operand } => format!("({op:?} {})", shape(operand)),
            ExprKind::Binary {
                op, left, right, ..
            } => {
                format!("({} {op:?} {})", shape(left), shape(right))
            }
            ExprKind::Is {
                value, type_name, ..
            } => {
                format!("({} is {})", shape(value), type_name.name)
            }
            ExprKind::Ternary {
                condition,
                then,
                otherwise,
                ..
            } => {
                format!(
                    "({} ? {} : {})",
                    shape(condition),
                    shape(then),
                    shape(otherwise)
                )
            }
        }
    }

    #[test]
    fn precedence() {
        for (expr, expected) in [
            (
                "a || b && c == d + e * f",
                "(a Or (b And (c Eq (d Add (e Mul f)))))",
            ),
            ("1 == 1 == true", "((1 Eq 1) Eq true)"),
            ("!a.b(c)[0]", "(Not a.b(c)[0])"),
            ("-1 - -2.5 % 3", "((Neg 1) Sub ((Neg 2.5) Mod 3))"),
            ("a ? b : c ? d : e", "(a ? b : (c ? d : e))"),
            (
                "x is string && y in [1, 2,]",
                "((x is string) And (y In [1, 2]))",
            ),
            ("(a || b) && c", "((a Or b) And c)"),
            ("-9223372036854775808", "-9223372036854775808"),
            ("9223372036854775808", "overflow 9223372036854775808"),
        ] {
            assert_eq!(shape(&condition(expr)), expected, "{expr}");
        }
    }

    #[test]
    fn primaries() {
        for (expr, expected) in [
            (
                "/databases/$(database)/documents/(default)",
                "/databases/$(database)/documents/(default)",
            ),
            (
                "math.abs(1) + duration.value(1, 's')",
                "(math.abs(1) Add duration.value(1, \"s\"))",
            ),
            ("get(/a/b).data.x", "get(/a/b).data.x"),
            ("'abc'[1:2] == b'\\x01'", "(\"abc\"[1:2] Eq b[1])"),
            ("{'a': [1, {}], 'b': null}", "{\"a\": [1, {}], \"b\": null}"),
            ("request.resource.data.if", "request.resource.data.if"),
            ("$x.y", "$x.y"),
        ] {
            assert_eq!(shape(&condition(expr)), expected, "{expr}");
        }
    }

    #[test]
    fn declarations() {
        let f = file(
            "rules_version = '2';\n\
             function top() { return true; }\n\
             service cloud.firestore {\n\
               match /databases/{database}/documents {\n\
                 function f(a, b) { let c = a; return c == b; }\n\
                 match /users/{user}/{rest=**} {\n\
                   allow read, write: if f(user, 'x');\n\
                   allow get;\n\
                 }\n\
               }\n\
             }",
        );
        assert_eq!(f.version.as_ref().map(|v| v.value.as_str()), Some("2"));
        assert_eq!(f.functions[0].name.name, "top");
        let service = &f.services[0];
        assert_eq!(service.name, "cloud.firestore");
        assert_eq!((service.name_span.line, service.name_span.column), (3, 9));
        let documents = &service.body.matches[0];
        let kinds: Vec<_> = documents.path.iter().map(|s| s.kind.clone()).collect();
        assert_eq!(
            kinds,
            vec![
                SegmentKind::Literal("databases".into()),
                SegmentKind::Wildcard("database".into()),
                SegmentKind::Literal("documents".into()),
            ]
        );
        let function = &documents.body.functions[0];
        assert_eq!(function.params.len(), 2);
        assert_eq!(function.lets[0].name.name, "c");
        let users = &documents.body.matches[0];
        assert_eq!(users.path[2].kind, SegmentKind::Recursive("rest".into()));
        // The string continues its lines without their indentation.
        assert_eq!((users.span.line, users.span.column), (6, 1));
        let allow = &users.body.allows[0];
        let methods: Vec<_> = allow.methods.iter().map(|m| m.method).collect();
        assert_eq!(methods, vec![Some(Method::Read), Some(Method::Write)]);
        let c = allow.condition.as_ref().unwrap();
        assert_eq!((c.span.line, c.span.column), (7, 23));
        assert!(users.body.allows[1].condition.is_none());
    }

    /// The first line of the diagnostics, as the error message would print them.
    fn first(src: &str) -> String {
        let mut diags = parse(src).diags;
        crate::diag::sort(&mut diags);
        let d = &diags[0];
        let span = d.span.unwrap();
        format!("L{}:{} {}", span.line, span.column, d.message)
    }

    #[test]
    fn syntax_errors() {
        let wrap = |body: &str| {
            format!("rules_version = '2';\nservice s {{\n  match /a {{\n    {body}\n  }}\n}}\n")
        };
        for (body, expected) in [
            (
                "allow read: true;",
                "L4:17 Missing 'if' before conditional expression.",
            ),
            (
                "allow read: if ;",
                "L4:20 Missing conditional expression after 'if'.",
            ),
            (
                "allow read if true;",
                "L4:16 Missing ':' before 'if' condition.",
            ),
            (
                "allow read: if true &&;",
                "L4:27 mismatched input ';' expecting {'--', '++', '{', '[', '(', '-', '!', '/', \
                 'false', 'null', 'true', PATH_SEGMENT, IDENTIFIER, NUM_INT, NUM_FLOAT, \
                 UNPAIRED_DOUBLE_QUOTE, UNPAIRED_SINGLE_QUOTE, STRING, BYTES}",
            ),
            ("allow read: if f(,);", "L4:22 Unexpected ','."),
            (
                "allow read: if --1 == 1;",
                "L4:22 Increment (++) and decrement (--) operators are not supported.",
            ),
            (
                "allow read: if 1 is foo;",
                "L4:28 An unsupported type identifier was used with the 'is' operator. Received \
                 foo. Expected one of bool,bytes,constraint,duration,float,int,latlng,list,\
                 vector,set,number,map,string,timestamp,path,map_diff",
            ),
            (
                "match /b {}",
                "L4:15 The 'match' body must contain at least one declaration.",
            ),
            (
                "match /b/ { allow read; }",
                "L4:13 Forward slash '/' found where identifier or binding expected.",
            ),
            (
                "match /b allow read;",
                "L4:11 Missing 'match' keyword before path.",
            ),
            (
                "/b { allow read; }",
                "L4:5 Missing 'match' keyword before path.",
            ),
            (
                "function f() { return true; let x = 1; }",
                "L4:33 mismatched input 'let' expecting '}'",
            ),
        ] {
            assert_eq!(first(&wrap(body)), expected, "{body}");
        }
        assert_eq!(
            first(""),
            "L1:1 mismatched input '<EOF>' expecting {'function', 'import', 'service', 'rules_version'}"
        );
        assert_eq!(
            first("rules_version = 2;"),
            "L1:17 mismatched input '2' expecting STRING"
        );
        assert_eq!(
            first("service s {\n}"),
            "L2:1 The 'service' body must contain at least one declaration."
        );
        assert_eq!(
            first("service s { match /a { allow read; } }\n}"),
            "L2:1 Unexpected '}'."
        );
    }

    #[test]
    fn lexer_errors_before_the_first_syntax_error_are_dropped() {
        let src = "service s {\n\u{a0}match /a { allow read: if true &&; }\n}\n#";
        let lines: Vec<_> = {
            let mut diags = parse(src).diags;
            crate::diag::sort(&mut diags);
            diags.iter().map(|d| d.message.clone()).collect()
        };
        assert_eq!(lines.len(), 2, "{lines:?}");
        assert!(lines[0].starts_with("mismatched input ';'"));
        assert_eq!(lines[1], "token recognition error at: '#'");
        // Without a syntax error, every one is.
        let parsed = parse("service s {\n\u{a0}match /a { allow read; }\n}\n#");
        assert_eq!(parsed.diags.len(), 2);
        assert!(!parsed.syntax_error);
    }
}