meta_language/grammar/import/

antlr.rs

mod char_set;
mod commands;
mod lexer;

use char_set::{has_case, lower_char_set, negate_expr, with_case_variants};
use commands::{apply_retypes, command_channel, command_type};
use lexer::{Lexer, Token, TokenKind};

use super::{GrammarImportError, parse_error, unsupported_error};
use crate::grammar::feature::{FeatureExpr, FeatureForm, FieldValue, class_expression};
use crate::grammar::{
    Grammar, GrammarExpr, GrammarFormat, GrammarRule, RuleAttributes, RuleKind, UnicodeClassItem,
};

const FORMAT: GrammarFormat = GrammarFormat::Antlr;

/// Parses ANTLR v4 `.g4` grammar text into the grammar IR.
///
/// The importer is a clean-room parser for the structural ANTLR grammar subset
/// needed by the grammar IR. ANTLR alternatives are lowered as unordered CFG
/// choices, while lexer commands and dropped target-language actions are
/// preserved in rule documentation; `-> skip` and `-> channel(NAME)` also put
/// the rule on that channel, which makes it trivia. `EOF` is the end of the
/// input, and character sets read `\uXXXX`, `\u{X...}` and `\p{NAME}` for a
/// general category or script.
///
/// # Errors
///
/// Returns [`GrammarImportError`] when the source cannot be parsed as the
/// supported ANTLR subset or when a parsed prelude construct is recognized but
/// not yet representable.
pub fn import_antlr(text: &str) -> Result<Grammar, GrammarImportError> {
    Parser::new(Lexer::new(text).tokenize()?).parse_grammar()
}

#[derive(Clone, Debug)]
struct Parser {
    tokens: Vec<Token>,
    cursor: usize,
    pending_comments: Vec<String>,
    // `options { caseInsensitive = true; }` of the current grammar, and of
    // the current rule, which may override it.
    case_insensitive: bool,
    rule_case_insensitive: bool,
}

impl Parser {
    const fn new(tokens: Vec<Token>) -> Self {
        Self {
            tokens,
            cursor: 0,
            pending_comments: Vec::new(),
            case_insensitive: false,
            rule_case_insensitive: false,
        }
    }

    fn parse_grammar(&mut self) -> Result<Grammar, GrammarImportError> {
        let mut grammar = Grammar::new().with_source_format(FORMAT);
        let mut rules = Vec::new();
        while !self.is_end() {
            self.collect_comments();
            if self.is_end() {
                break;
            }
            if self.parse_header()? || self.parse_skipped_directive()? {
                continue;
            }
            rules.push(self.parse_rule()?);
        }
        for rule in apply_retypes(rules) {
            grammar.add_rule(rule);
        }

        let Some(start) = grammar
            .rules()
            .iter()
            .find(|rule| rule.kind() == RuleKind::Normal)
            .or_else(|| grammar.rules().first())
            .map(|rule| rule.name.clone())
        else {
            return Err(parse_error(FORMAT, "ANTLR grammar does not contain rules"));
        };
        grammar.set_start(start);
        Ok(grammar)
    }

    fn parse_header(&mut self) -> Result<bool, GrammarImportError> {
        let matched = if self.check_keyword("grammar") {
            self.advance();
            true
        } else if (self.check_keyword("lexer") || self.check_keyword("parser"))
            && self.check_next_keyword("grammar")
        {
            self.advance();
            self.advance();
            true
        } else {
            false
        };

        if !matched {
            return Ok(false);
        }
        self.expect_ident("grammar name")?;
        self.expect_semicolon()?;
        self.pending_comments.clear();
        self.case_insensitive = false;
        Ok(true)
    }

    fn parse_skipped_directive(&mut self) -> Result<bool, GrammarImportError> {
        if self.check_any_keyword(&["options", "tokens", "channels"]) {
            let is_options = self.check_keyword("options");
            self.advance();
            if let Some(TokenKind::Action(options)) = self.peek_kind() {
                if is_options {
                    self.case_insensitive = parse_options(options)
                        .iter()
                        .rev()
                        .find(|(key, _)| key == "caseInsensitive")
                        .is_some_and(|(_, value)| value == "true");
                }
                self.advance();
                self.try_consume_semicolon();
                self.pending_comments.clear();
                return Ok(true);
            }
            self.skip_until_semicolon()?;
            self.pending_comments.clear();
            return Ok(true);
        }

        if self.check_any_keyword(&["import", "mode"]) {
            self.advance();
            self.skip_until_semicolon()?;
            self.pending_comments.clear();
            return Ok(true);
        }

        Ok(false)
    }

    /// A rule and the token type its `-> type(NAME)` command gives it.
    fn parse_rule(&mut self) -> Result<(GrammarRule, Option<String>), GrammarImportError> {
        let comments = std::mem::take(&mut self.pending_comments);
        let fragment = self.try_consume_keyword("fragment");
        let name = self.expect_ident("rule name")?;
        // A comment between the name and its ':' documents the rule too.
        self.collect_comments();
        let mut comments = comments;
        comments.append(&mut self.pending_comments);
        let mut notes = Vec::new();
        self.parse_rule_prelude(&mut notes)?;
        self.expect_colon()?;

        let alternatives = self.parse_alternatives(&mut notes)?;
        let expr = precedence_climbing(&name, alternatives);
        let command = if self.try_consume_arrow() {
            Some(self.parse_lexer_command()?)
        } else {
            None
        };
        self.expect_semicolon()?;

        let kind = if fragment {
            RuleKind::Silent
        } else if name.chars().next().is_some_and(char::is_uppercase) {
            RuleKind::Token
        } else {
            RuleKind::Normal
        };

        let channel = command.as_deref().and_then(command_channel);
        let retype = if channel.is_none() {
            command.as_deref().and_then(command_type)
        } else {
            None
        };
        let mut rule = GrammarRule::new(name, expr).with_kind(kind);
        if channel.is_some() {
            rule = rule.with_attributes(RuleAttributes {
                channel,
                ..RuleAttributes::default()
            });
        }
        if let Some(doc) = rule_doc(comments, notes, command) {
            rule = rule.with_doc(doc);
        }
        Ok((rule, retype))
    }

    // `returns [...]`, `throws ...` and `locals [...]` declare target-language
    // values, which join the rule's doc like actions. `options {...}` may set
    // `caseInsensitive` for the rule; other options join the doc.
    fn parse_rule_prelude(&mut self, notes: &mut Vec<String>) -> Result<(), GrammarImportError> {
        self.rule_case_insensitive = self.case_insensitive;
        if matches!(self.peek_kind(), Some(TokenKind::CharSet(_))) {
            return Err(unsupported_error(FORMAT, "rule arguments"));
        }
        while !self.check_colon() {
            if (self.check_keyword("returns") || self.check_keyword("locals"))
                && let Some(TokenKind::CharSet(text)) = self.peek_next_kind()
            {
                let note = format!(
                    "dropped {} [{text}]",
                    self.peek().map(Token::text).unwrap_or_default()
                );
                self.advance();
                self.advance();
                notes.push(note);
            } else if self.check_keyword("throws") {
                self.advance();
                let mut names = vec![self.expect_ident("exception name")?];
                while matches!(self.peek_kind(), Some(TokenKind::Comma)) {
                    self.advance();
                    names.push(self.expect_ident("exception name")?);
                }
                notes.push(format!("dropped throws {}", names.join(", ")));
            } else if self.check_keyword("options")
                && let Some(TokenKind::Action(text)) = self.peek_next_kind()
            {
                let options = parse_options(text);
                self.advance();
                self.advance();
                for (key, value) in options {
                    if key == "caseInsensitive" {
                        self.rule_case_insensitive = value == "true";
                    } else {
                        notes.push(format!("rule option {key}={value}"));
                    }
                }
            } else {
                return Err(self.expected("':' before rule body"));
            }
            self.skip_inline_comments();
        }
        Ok(())
    }

    fn parse_choice(&mut self, notes: &mut Vec<String>) -> Result<GrammarExpr, GrammarImportError> {
        let mut alternatives = Vec::new();
        for (expr, _) in self.parse_alternatives(notes)? {
            push_choice_alternative(&mut alternatives, expr);
        }
        Ok(finish_choice(alternatives))
    }

    fn parse_alternatives(
        &mut self,
        notes: &mut Vec<String>,
    ) -> Result<Vec<(GrammarExpr, &'static str)>, GrammarImportError> {
        let mut alternatives = vec![self.parse_alternative(notes)?];
        while self.try_consume_pipe() {
            alternatives.push(self.parse_alternative(notes)?);
        }
        Ok(alternatives)
    }

    // An alternative with its `<key = value, ...>` options and its `# Label`,
    // which names the context class ANTLR generates for it, not syntax: the
    // label joins the rule's doc. `assoc` is kept for the precedence of a
    // left-recursive rule; any other option joins the doc.
    fn parse_alternative(
        &mut self,
        notes: &mut Vec<String>,
    ) -> Result<(GrammarExpr, &'static str), GrammarImportError> {
        self.skip_inline_comments();
        let options = if matches!(self.peek_kind(), Some(TokenKind::LAngle)) {
            self.advance();
            self.parse_element_options()?
        } else {
            Vec::new()
        };
        let mut assoc = None;
        for (key, value) in options {
            if key == "assoc" {
                assoc = Some(value);
            } else {
                notes.push(format!("alternative option {key}={value}"));
            }
        }
        let sequence = self.parse_sequence(notes)?;
        if matches!(self.peek_kind(), Some(TokenKind::Hash)) {
            self.advance();
            let label = self.expect_ident("alternative label")?;
            notes.push(format!("alternative {label}"));
            self.skip_inline_comments();
        }
        let associativity = match assoc.as_deref() {
            None | Some("left") => "left",
            Some("right") => "right",
            Some(other) => {
                return Err(unsupported_error(FORMAT, format!("associativity {other}")));
            }
        };
        Ok((sequence, associativity))
    }

    fn parse_element_options(&mut self) -> Result<Vec<(String, String)>, GrammarImportError> {
        let mut options: Vec<(String, String)> = Vec::new();
        loop {
            let key = self.expect_ident("element option")?;
            let mut value = "true".to_owned();
            if matches!(self.peek_kind(), Some(TokenKind::Equal)) {
                self.advance();
                value = match self.peek_kind() {
                    Some(TokenKind::Ident(text) | TokenKind::String(text)) => text.clone(),
                    _ => return Err(self.expected("element option value")),
                };
                self.advance();
            }
            options.retain(|(existing, _)| *existing != key);
            options.push((key, value));
            if matches!(self.peek_kind(), Some(TokenKind::Comma)) {
                self.advance();
            } else {
                break;
            }
        }
        if !matches!(self.peek_kind(), Some(TokenKind::RAngle)) {
            return Err(self.expected("'>'"));
        }
        self.advance();
        Ok(options)
    }

    fn parse_sequence(
        &mut self,
        notes: &mut Vec<String>,
    ) -> Result<GrammarExpr, GrammarImportError> {
        let mut items = Vec::new();
        loop {
            self.skip_inline_comments();
            if self.is_sequence_end() {
                break;
            }
            push_sequence_item(&mut items, self.parse_element(notes)?);
        }
        Ok(finish_sequence(items))
    }

    fn parse_element(
        &mut self,
        notes: &mut Vec<String>,
    ) -> Result<GrammarExpr, GrammarImportError> {
        self.skip_inline_comments();
        if matches!(self.peek_kind(), Some(TokenKind::Action(_))) {
            return Ok(self.parse_action(notes));
        }

        if let Some(label) = self.label_ahead() {
            self.advance();
            self.advance();
            let expr = self.parse_prefixed(notes)?;
            return Ok(GrammarExpr::capture(label, expr));
        }

        self.parse_prefixed(notes)
    }

    fn parse_prefixed(
        &mut self,
        notes: &mut Vec<String>,
    ) -> Result<GrammarExpr, GrammarImportError> {
        self.skip_inline_comments();
        let expr = if self.try_consume_tilde() {
            negate_expr(self.parse_atom(notes)?)
        } else {
            self.parse_atom(notes)?
        };
        self.parse_suffixes(expr)
    }

    fn parse_atom(&mut self, notes: &mut Vec<String>) -> Result<GrammarExpr, GrammarImportError> {
        self.skip_inline_comments();
        let Some(token) = self.peek().cloned() else {
            return Err(self.expected("expression element"));
        };

        match token.kind {
            TokenKind::Ident(name) => {
                self.advance();
                // ANTLR reserves EOF for the end of the input.
                if name == "EOF" {
                    return Ok(GrammarExpr::Not(Box::new(GrammarExpr::AnyChar)));
                }
                Ok(GrammarExpr::NonTerminal(name))
            }
            TokenKind::String(value) => {
                self.advance();
                if self.try_consume_range() {
                    let end = self.expect_string("range end")?;
                    let start = single_char(&value, "range start", token.offset)?;
                    let end = single_char(&end, "range end", token.offset)?;
                    if start > end {
                        return Err(error_at(token.offset, "literal range start exceeds end"));
                    }
                    if self.rule_case_insensitive {
                        let items = with_case_variants(&[UnicodeClassItem::Range(start, end)]);
                        if items.len() > 1 {
                            return Ok(class_expression(false, items));
                        }
                    }
                    Ok(GrammarExpr::CharRange(start, end))
                } else if self.rule_case_insensitive && has_case(&value) {
                    Ok(GrammarExpr::TerminalInsensitive(value))
                } else {
                    Ok(GrammarExpr::Terminal(value))
                }
            }
            TokenKind::CharSet(content) => {
                self.advance();
                lower_char_set(&content, token.offset, self.rule_case_insensitive)
            }
            TokenKind::Dot => {
                self.advance();
                Ok(GrammarExpr::AnyChar)
            }
            TokenKind::LParen => {
                self.advance();
                let expr = self.parse_choice(notes)?;
                self.expect_rparen()?;
                Ok(expr)
            }
            TokenKind::Action(_) => Ok(self.parse_action(notes)),
            _ => Err(self.expected("expression element")),
        }
    }

    fn parse_action(&mut self, notes: &mut Vec<String>) -> GrammarExpr {
        self.advance();
        if self.try_consume_question() {
            notes.push("dropped predicate".to_string());
        } else {
            notes.push("dropped action".to_string());
        }
        GrammarExpr::Empty
    }

    fn parse_suffixes(&mut self, mut expr: GrammarExpr) -> Result<GrammarExpr, GrammarImportError> {
        loop {
            let Some(suffix) = self.consume_suffix() else {
                return Ok(expr);
            };
            expr = match suffix {
                Suffix::Optional => GrammarExpr::optional(expr),
                Suffix::ZeroOrMore => GrammarExpr::zero_or_more(expr),
                Suffix::OneOrMore => GrammarExpr::one_or_more(expr),
            };
            if self.try_consume_question() {
                expr = GrammarExpr::capture("non_greedy", expr);
            }
        }
    }

    fn parse_lexer_command(&mut self) -> Result<String, GrammarImportError> {
        let mut tokens = Vec::new();
        while !self.is_end() && !self.check_semicolon() {
            if matches!(self.peek_kind(), Some(TokenKind::Comment(_))) {
                self.advance();
            } else {
                tokens.push(self.advance().clone());
            }
        }
        if tokens.is_empty() {
            return Err(self.expected("lexer command"));
        }
        Ok(format_command(&tokens))
    }

    fn skip_until_semicolon(&mut self) -> Result<(), GrammarImportError> {
        while !self.is_end() {
            if self.try_consume_semicolon() {
                return Ok(());
            }
            self.advance();
        }
        Err(self.expected("';' after directive"))
    }

    fn collect_comments(&mut self) {
        while let Some(TokenKind::Comment(comment)) = self.peek_kind() {
            self.pending_comments.push(comment.clone());
            self.advance();
        }
    }

    fn skip_inline_comments(&mut self) {
        while matches!(self.peek_kind(), Some(TokenKind::Comment(_))) {
            self.advance();
        }
    }

    fn label_ahead(&self) -> Option<String> {
        let label = self.peek()?.ident()?;
        if matches!(
            self.tokens.get(self.cursor + 1).map(|token| &token.kind),
            Some(TokenKind::Equal | TokenKind::PlusEqual)
        ) {
            Some(label.to_string())
        } else {
            None
        }
    }

    fn consume_suffix(&mut self) -> Option<Suffix> {
        match self.peek_kind() {
            Some(TokenKind::Question) => {
                self.advance();
                Some(Suffix::Optional)
            }
            Some(TokenKind::Star) => {
                self.advance();
                Some(Suffix::ZeroOrMore)
            }
            Some(TokenKind::Plus) => {
                self.advance();
                Some(Suffix::OneOrMore)
            }
            _ => None,
        }
    }

    fn is_sequence_end(&self) -> bool {
        self.is_end()
            || matches!(
                self.peek_kind(),
                Some(
                    TokenKind::Pipe
                        | TokenKind::Semicolon
                        | TokenKind::Arrow
                        | TokenKind::RParen
                        | TokenKind::Hash
                )
            )
    }

    fn expect_ident(&mut self, role: &str) -> Result<String, GrammarImportError> {
        let Some(token) = self.peek().cloned() else {
            return Err(self.expected(role));
        };
        match token.kind {
            TokenKind::Ident(value) => {
                self.advance();
                Ok(value)
            }
            _ => Err(self.expected(role)),
        }
    }

    fn expect_string(&mut self, role: &str) -> Result<String, GrammarImportError> {
        let Some(token) = self.peek().cloned() else {
            return Err(self.expected(role));
        };
        match token.kind {
            TokenKind::String(value) => {
                self.advance();
                Ok(value)
            }
            _ => Err(self.expected(role)),
        }
    }

    fn expect_colon(&mut self) -> Result<(), GrammarImportError> {
        if self.check_colon() {
            self.advance();
            Ok(())
        } else {
            Err(self.expected("':'"))
        }
    }

    fn expect_semicolon(&mut self) -> Result<(), GrammarImportError> {
        if self.check_semicolon() {
            self.advance();
            Ok(())
        } else {
            Err(self.expected("';'"))
        }
    }

    fn expect_rparen(&mut self) -> Result<(), GrammarImportError> {
        if matches!(self.peek_kind(), Some(TokenKind::RParen)) {
            self.advance();
            Ok(())
        } else {
            Err(self.expected("')'"))
        }
    }

    fn expected(&self, expected: &str) -> GrammarImportError {
        let offset = self.peek().map_or(0, |token| token.offset);
        error_at(offset, format!("expected {expected}"))
    }

    fn try_consume_keyword(&mut self, keyword: &str) -> bool {
        if self.check_keyword(keyword) {
            self.advance();
            true
        } else {
            false
        }
    }

    fn try_consume_arrow(&mut self) -> bool {
        if matches!(self.peek_kind(), Some(TokenKind::Arrow)) {
            self.advance();
            true
        } else {
            false
        }
    }

    fn try_consume_pipe(&mut self) -> bool {
        if matches!(self.peek_kind(), Some(TokenKind::Pipe)) {
            self.advance();
            true
        } else {
            false
        }
    }

    fn try_consume_question(&mut self) -> bool {
        if matches!(self.peek_kind(), Some(TokenKind::Question)) {
            self.advance();
            true
        } else {
            false
        }
    }

    fn try_consume_tilde(&mut self) -> bool {
        if matches!(self.peek_kind(), Some(TokenKind::Tilde)) {
            self.advance();
            true
        } else {
            false
        }
    }

    fn try_consume_range(&mut self) -> bool {
        if matches!(self.peek_kind(), Some(TokenKind::Range)) {
            self.advance();
            true
        } else {
            false
        }
    }

    fn try_consume_semicolon(&mut self) -> bool {
        if self.check_semicolon() {
            self.advance();
            true
        } else {
            false
        }
    }

    fn check_keyword(&self, keyword: &str) -> bool {
        self.peek().is_some_and(|token| token.is_keyword(keyword))
    }

    fn check_next_keyword(&self, keyword: &str) -> bool {
        self.tokens
            .get(self.cursor + 1)
            .is_some_and(|token| token.is_keyword(keyword))
    }

    fn check_any_keyword(&self, keywords: &[&str]) -> bool {
        self.peek()
            .and_then(Token::ident)
            .is_some_and(|value| keywords.contains(&value))
    }

    fn check_colon(&self) -> bool {
        matches!(self.peek_kind(), Some(TokenKind::Colon))
    }

    fn check_semicolon(&self) -> bool {
        matches!(self.peek_kind(), Some(TokenKind::Semicolon))
    }

    const fn is_end(&self) -> bool {
        self.cursor >= self.tokens.len()
    }

    fn peek(&self) -> Option<&Token> {
        self.tokens.get(self.cursor)
    }

    fn peek_kind(&self) -> Option<&TokenKind> {
        self.peek().map(|token| &token.kind)
    }

    fn peek_next_kind(&self) -> Option<&TokenKind> {
        self.tokens.get(self.cursor + 1).map(|token| &token.kind)
    }

    fn advance(&mut self) -> &Token {
        let token = &self.tokens[self.cursor];
        self.cursor += 1;
        token
    }
}

#[derive(Clone, Copy, Debug, PartialEq, Eq)]
enum Suffix {
    Optional,
    ZeroOrMore,
    OneOrMore,
}

/// The `key = value;` pairs of an `options {...}` block.
fn parse_options(text: &str) -> Vec<(String, String)> {
    // Like the JavaScript importer, a pair counts only when `;` ends it.
    let pairs = text.rsplit_once(';').map_or("", |(pairs, _)| pairs);
    pairs
        .split(';')
        .filter_map(|part| {
            let (key, value) = part.split_once('=')?;
            let key = key.trim_end();
            let start = key
                .rfind(|character: char| !(character.is_ascii_alphanumeric() || character == '_'))
                .map_or(0, |index| index + 1);
            let key = &key[start..];
            is_identifier(key).then(|| (key.to_owned(), value.trim().to_owned()))
        })
        .collect()
}

fn is_identifier(text: &str) -> bool {
    let mut chars = text.chars();
    chars
        .next()
        .is_some_and(|first| first.is_ascii_alphabetic() || first == '_')
        && chars.all(|next| next.is_ascii_alphanumeric() || next == '_')
}

// A numbered channel such as `channel(2)`; channel 0 is the default one.
fn is_channel_number(text: &str) -> bool {
    !text.starts_with('0') && !text.is_empty() && text.chars().all(|digit| digit.is_ascii_digit())
}

// In a left-recursive rule, ANTLR gives each alternative that starts or ends
// with the rule a precedence: earlier alternatives bind tighter, and
// `<assoc=right>` makes one right-associative.
fn precedence_climbing(name: &str, alternatives: Vec<(GrammarExpr, &'static str)>) -> GrammarExpr {
    let left_recursive = alternatives
        .iter()
        .any(|(expr, _)| edge_ref(expr, Edge::Left) == Some(name));
    let count = alternatives.len();
    let mut choice = Vec::new();
    for (index, (expr, associativity)) in alternatives.into_iter().enumerate() {
        let climbs = left_recursive
            && (edge_ref(&expr, Edge::Left) == Some(name)
                || edge_ref(&expr, Edge::Right) == Some(name));
        let expr = if climbs {
            let level = i64::try_from(count - index).unwrap_or(i64::MAX);
            GrammarExpr::feature(FeatureExpr::Form(FeatureForm::new(
                "precedence",
                vec![
                    FieldValue::Integer(level),
                    FieldValue::Word(associativity.into()),
                    FieldValue::Expression(expr),
                ],
            )))
        } else {
            expr
        };
        push_choice_alternative(&mut choice, expr);
    }
    finish_choice(choice)
}

#[derive(Clone, Copy)]
enum Edge {
    Left,
    Right,
}

fn edge_ref(expr: &GrammarExpr, edge: Edge) -> Option<&str> {
    match expr {
        GrammarExpr::NonTerminal(name) => Some(name),
        GrammarExpr::Capture { expr, .. } => edge_ref(expr, edge),
        GrammarExpr::Sequence(items) => match edge {
            Edge::Left => items.first(),
            Edge::Right => items.last(),
        }
        .and_then(|item| edge_ref(item, edge)),
        _ => None,
    }
}

fn finish_sequence(items: Vec<GrammarExpr>) -> GrammarExpr {
    match items.len() {
        0 => GrammarExpr::Empty,
        1 => items.into_iter().next().expect("one sequence item exists"),
        _ => GrammarExpr::Sequence(items),
    }
}

fn push_sequence_item(items: &mut Vec<GrammarExpr>, item: GrammarExpr) {
    match item {
        GrammarExpr::Empty => {}
        GrammarExpr::Sequence(nested) => {
            for item in nested {
                push_sequence_item(items, item);
            }
        }
        item => items.push(item),
    }
}

fn finish_choice(alternatives: Vec<GrammarExpr>) -> GrammarExpr {
    if alternatives.iter().all(|expr| expr == &GrammarExpr::Empty) {
        return GrammarExpr::Empty;
    }
    match alternatives.len() {
        0 => GrammarExpr::Empty,
        1 => alternatives
            .into_iter()
            .next()
            .expect("one alternative exists"),
        _ => GrammarExpr::Choice {
            ordered: false,
            alternatives,
        },
    }
}

fn push_choice_alternative(alternatives: &mut Vec<GrammarExpr>, alternative: GrammarExpr) {
    match alternative {
        GrammarExpr::Choice {
            ordered: false,
            alternatives: nested,
        } => alternatives.extend(nested),
        alternative => alternatives.push(alternative),
    }
}

fn single_char(value: &str, role: &str, offset: usize) -> Result<char, GrammarImportError> {
    let mut chars = value.chars();
    let Some(character) = chars.next() else {
        return Err(error_at(
            offset,
            format!("{role} must contain one character"),
        ));
    };
    if chars.next().is_some() {
        return Err(error_at(
            offset,
            format!("{role} {value:?} must contain one character"),
        ));
    }
    Ok(character)
}

fn rule_doc(comments: Vec<String>, notes: Vec<String>, command: Option<String>) -> Option<String> {
    let mut parts = Vec::new();
    parts.extend(comments.into_iter().filter(|comment| !comment.is_empty()));
    parts.extend(notes);
    parts.extend(command);
    if parts.is_empty() {
        None
    } else {
        Some(parts.join("; "))
    }
}

fn format_command(tokens: &[Token]) -> String {
    let mut output = "->".to_string();
    for token in tokens {
        match token.kind {
            TokenKind::LParen => output.push('('),
            TokenKind::RParen => output.push(')'),
            TokenKind::Comma => output.push_str(", "),
            _ => {
                if output == "->" || (!output.ends_with('(') && !output.ends_with(", ")) {
                    output.push(' ');
                }
                output.push_str(&token.text());
            }
        }
    }
    output
}

fn error_at(offset: usize, message: impl Into<String>) -> GrammarImportError {
    parse_error(FORMAT, format!("{} at byte {offset}", message.into()))
}