tecta_peg/

lib.rs

use std::{
    collections::BTreeMap,
    fmt::{Debug, Display},
};

use tecta_lex::{Delimiter as GroupDelimiter, Span, pat_ident_body, pat_ident_start, pat_punct};

/// A delimiter of a group in a token tree, or a sequence.
#[derive(Clone, Copy, Debug, Hash, PartialEq, Eq, PartialOrd, Ord)]
pub enum AnyDelimiter {
    /// `()`
    Parenthesis,
    /// `[]`
    Bracket,
    /// `{}`
    Brace,
    /// `<>`,
    AngleBrackets,
}
impl AnyDelimiter {
    pub fn to_group(&self) -> Option<GroupDelimiter> {
        match self {
            Self::Parenthesis => Some(GroupDelimiter::Parenthesis),
            Self::Bracket => Some(GroupDelimiter::Bracket),
            Self::Brace => Some(GroupDelimiter::Brace),
            Self::AngleBrackets => None,
        }
    }
    pub fn opener(&self) -> char {
        match self {
            Self::Parenthesis => '(',
            Self::Bracket => '[',
            Self::Brace => '{',
            Self::AngleBrackets => '<',
        }
    }
    pub fn closer(&self) -> char {
        match self {
            Self::Parenthesis => ')',
            Self::Bracket => ']',
            Self::Brace => '}',
            Self::AngleBrackets => '>',
        }
    }
}
impl From<GroupDelimiter> for AnyDelimiter {
    fn from(value: GroupDelimiter) -> Self {
        match value {
            GroupDelimiter::Parenthesis => Self::Parenthesis,
            GroupDelimiter::Bracket => Self::Bracket,
            GroupDelimiter::Brace => Self::Brace,
        }
    }
}

/// A transient control rule; cleared by other control characters.
#[derive(Clone, Copy, Debug, Hash, PartialEq, Eq, PartialOrd, Ord)]
pub struct Control(pub ControlKind, pub Span);

/// A specific variant of control rule.
#[derive(Clone, Copy, Debug, Hash, PartialEq, Eq, PartialOrd, Ord)]
pub enum ControlKind {
    /// Start of a sequence rule, beginning with `<` and ending with `>`.
    SequenceStart,
    /// Start of a group rule, beginning with one of `(`, `[`, or `{`, and ending with, respectively, `)`, `]`, or `}`.
    GroupStart(GroupDelimiter),
}

/// At least some number of times.
#[derive(Clone, Copy, Debug, Hash, PartialEq, Eq, PartialOrd, Ord)]
pub enum AtLeast {
    /// Matches a rule zero or more times. Delimited by `*`.
    Zero,
    /// Matches a rule one or more times. Delimited by `+`.
    One,
}
impl Display for AtLeast {
    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
        match self {
            Self::One => write!(f, "+"),
            Self::Zero => write!(f, "*"),
        }
    }
}

/// Repeats a rule a number of times, the repetition choice being decided by the operator used:
/// - `*` repeats zero or more times
/// - `+` repeats one or more times
///
/// The first operand is the element and the second is the separator.
/// For example, `"x" ',' *` matches multiple instances of the keyword `x`, separated by commas.
/// Trailing is enabled with the `~` modifier.
#[derive(Clone, Debug, Hash, PartialEq, Eq, PartialOrd, Ord)]
pub struct RepeatRule {
    pub element: Box<Rule>,
    pub separator: Box<Rule>,
    pub at_least: AtLeast,
    pub allow_trailing: bool,
}

/// A grammar rule.
#[derive(Clone, Hash, PartialEq, Eq, PartialOrd, Ord)]
pub struct Rule(pub RuleKind, pub Span);
impl Rule {
    pub fn sequence(rules: Vec<Rule>, span: Span) -> Self {
        Self(RuleKind::Sequence(rules), span)
    }
    pub fn choice(rules: Vec<Rule>, span: Span) -> Self {
        Self(RuleKind::Choice(rules), span)
    }
    pub fn group(delimiter: GroupDelimiter, rule: Rule, span: Span) -> Self {
        Self(RuleKind::Group(delimiter, Box::new(rule)), span)
    }

    pub fn repeat(element: Rule, separator: Rule, at_least: AtLeast, span: Span) -> Self {
        Self(
            RuleKind::Repeat(RepeatRule {
                element: Box::new(element),
                separator: Box::new(separator),
                at_least,
                allow_trailing: false,
            }),
            span,
        )
    }
    pub fn optional(rule: Rule, span: Span) -> Self {
        Self(RuleKind::Optional(Box::new(rule)), span)
    }

    pub fn punctuation(repr: String, span: Span) -> Self {
        Self(RuleKind::Punctuation(repr), span)
    }
    pub fn keyword(repr: String, span: Span) -> Self {
        Self(RuleKind::Keyword(repr), span)
    }
    pub fn other(repr: String, span: Span) -> Self {
        Self(RuleKind::Other(repr), span)
    }
    pub fn builtin(repr: String, span: Span) -> Self {
        Self(RuleKind::Builtin(repr), span)
    }

    pub fn peg(self) -> Peg {
        Peg::Rule(self)
    }
}
impl Debug for Rule {
    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
        write!(f, "{:?} @{}", self.0, self.1)
    }
}
impl Display for Rule {
    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
        write!(f, "{}", self.0)
    }
}

/// A specific grammar rule variant.
#[derive(Clone, Debug, Hash, PartialEq, Eq, PartialOrd, Ord)]
pub enum RuleKind {
    /// Matches a sequence of rules, one after another.
    Sequence(Vec<Rule>),
    /// Begins all rules at the same point, using the first one that matches.
    Choice(Vec<Rule>),
    /// Matches inside a token group.
    Group(GroupDelimiter, Box<Rule>),

    /// A [repeating rule][`RepeatRule`], delimited with `*` or `+`.
    Repeat(RepeatRule),

    /// Makes a rule optional (allowed to fail). Delimited with `?`.
    Optional(Box<Rule>),

    /// Matches a punctuation token.
    Punctuation(String),
    /// Matches a keyword token.
    Keyword(String),

    /// Matches a different rule.
    Other(String),
    /// Matches a built-in rule (denoted with `@`).
    Builtin(String),
}
impl RuleKind {
    pub fn with(self, span: impl Into<Span>) -> Rule {
        Rule(self, span.into())
    }
}
impl Display for RuleKind {
    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
        match self {
            RuleKind::Sequence(rules) => match &rules[..] {
                [] => write!(f, "<>"),
                [most @ .., last] => {
                    write!(f, "<")?;
                    for rule in most {
                        write!(f, "{rule} ")?;
                    }
                    write!(f, "{last}>")
                }
            },
            RuleKind::Choice(rules) => match &rules[..] {
                [] => write!(f, "!"),
                [most @ .., last] => {
                    for rule in most {
                        write!(f, "{rule} | ")?;
                    }
                    write!(f, "{last}")
                }
            },
            RuleKind::Group(delimiter, inner) => {
                write!(f, "{}{}{}", delimiter.opener(), inner, delimiter.closer())
            }
            RuleKind::Repeat(RepeatRule {
                element,
                separator,
                at_least,
                allow_trailing,
            }) => write!(
                f,
                "{} {} {}{}",
                element,
                separator,
                at_least,
                if *allow_trailing { "~" } else { "" }
            ),
            RuleKind::Optional(rule) => write!(f, "{rule}?"),
            RuleKind::Punctuation(punct) => write!(f, "'{punct}'"),
            RuleKind::Keyword(kw) => write!(f, "\"{kw}\""),
            RuleKind::Other(name) => write!(f, "{name}"),
            RuleKind::Builtin(builtin) => write!(f, "@{builtin}"),
        }
    }
}

/// An element of a PEG grammar stack.
#[derive(Debug, Clone, Hash, PartialEq, Eq, PartialOrd, Ord)]
pub enum Peg {
    /// A control element. Should not appear on the stack by the end of parsing.
    Control(Control),
    /// A grammar rule element.
    Rule(Rule),
}
impl Peg {
    pub fn sequence_start(span: Span) -> Self {
        Self::Control(Control(ControlKind::SequenceStart, span))
    }
    pub fn group_start(delimiter: GroupDelimiter, span: Span) -> Self {
        Self::Control(Control(ControlKind::GroupStart(delimiter), span))
    }

    pub fn try_as_rule(self) -> Result<Rule> {
        match self {
            Peg::Rule(rule) => Ok(rule),
            Peg::Control(control) => Err(ErrorKind::StrayControl(control.0).with(control.1)),
        }
    }
    pub fn try_as_mut_rule(&mut self) -> Result<&mut Rule> {
        match self {
            Peg::Rule(rule) => Ok(rule),
            Peg::Control(control) => Err(ErrorKind::StrayControl(control.0).with(control.1)),
        }
    }
    pub fn span(&self) -> Span {
        let (Peg::Control(Control(_, span)) | Peg::Rule(Rule(_, span))) = self;
        *span
    }
}

/// A PEG grammar stack.
pub struct PegStack(pub Vec<Peg>);
impl PegStack {
    pub fn raw_pop_rule(&mut self, operator_span: Span) -> Result<Rule> {
        match self.0.pop() {
            Some(Peg::Rule(rule)) => Ok(rule),
            Some(Peg::Control(control)) => Err(ErrorKind::StrayControl(control.0).with(control.1)),
            None => Err(ErrorKind::StackEmpty("expected rule".into()).with(operator_span)),
        }
    }
    pub fn take_rule(&mut self, operator_span: Span) -> Result<Rule> {
        match self.0.pop() {
            Some(Peg::Rule(Rule(RuleKind::Choice(mut choices), span))) if !choices.is_empty() => {
                let rule = choices
                    .pop()
                    .expect("internal parser error: choices was in fact empty");
                self.0
                    .push(Peg::Rule(Rule(RuleKind::Choice(choices), span)));
                Ok(rule)
            }
            Some(Peg::Rule(other_rule)) => Ok(other_rule),
            Some(Peg::Control(control)) => Err(ErrorKind::StrayControl(control.0).with(control.1)),
            None => Err(ErrorKind::StackEmpty("expected rule".into()).with(operator_span)),
        }
    }
    pub fn add_rule(&mut self, rule: Rule) {
        match self.0.pop() {
            Some(Peg::Rule(Rule(RuleKind::Choice(mut variants), span))) => {
                if let Some(old_last_variant) = variants.pop() {
                    let total_span = old_last_variant.1 + span;
                    if let RuleKind::Sequence(mut sequence) = old_last_variant.0 {
                        sequence.push(rule);
                        variants.push(Rule(RuleKind::Sequence(sequence), total_span));
                    } else {
                        variants.push(Rule::sequence(vec![old_last_variant, rule], total_span));
                    }
                } else {
                    variants.push(rule);
                }
                self.0.push(Rule::choice(variants, span).peg());
            }
            Some(other) => {
                self.0.push(other);
                self.0.push(rule.peg());
            }
            None => {
                self.0.push(rule.peg());
            }
        }
    }
    pub fn add_rule_kind(&mut self, kind: RuleKind, span: Span) {
        self.add_rule(Rule(kind, span));
    }
}

/// Input to a PEG parsing function.
#[derive(Clone, Copy, Debug, Default, Hash, PartialEq, Eq, PartialOrd, Ord)]
pub struct ParseInput<I: Iterator<Item = (Span, char)>> {
    chars: I,
    end_span: Span,
}
impl<I: Iterator<Item = (Span, char)>> ParseInput<I> {
    pub fn new(chars: I, end_span: Span) -> Self {
        Self { chars, end_span }
    }
    pub fn current_span(&self) -> Span
    where
        I: Clone,
    {
        match self.chars.clone().next() {
            Some((span, _)) => span,
            None => self.end_span,
        }
    }
    fn eof(&self) -> Error {
        Error::eof(self.end_span)
    }
}
impl<I: Iterator<Item = (Span, char)>> Iterator for ParseInput<I> {
    type Item = (Span, char);
    fn next(&mut self) -> Option<Self::Item> {
        self.chars.next()
    }
}

/// Wraps a character iterator, adding span information to each character.
#[derive(Clone, Copy, Debug, Default, Hash, PartialEq, Eq, PartialOrd, Ord)]
pub struct SpannedChars<I: Iterator<Item = char>> {
    iterator: I,
    current_line: usize,
    current_column: usize,
}
impl<I: Iterator<Item = char>> SpannedChars<I> {
    pub fn new(iterator: I) -> Self {
        SpannedChars {
            iterator,
            current_line: 1,
            current_column: 1,
        }
    }
}
impl<I: Iterator<Item = char>> Iterator for SpannedChars<I> {
    type Item = (Span, char);
    fn next(&mut self) -> Option<Self::Item> {
        let next = self.iterator.next()?;
        let span = Span {
            start_line: self.current_line,
            end_line: self.current_line,
            start_column: self.current_column,
            end_column: self.current_column,
        };
        if next == '\n' {
            self.current_line += 1;
            self.current_column = 1;
        } else {
            self.current_column += 1;
        }
        Some((span, next))
    }
}

macro_rules! parse_input {
    () => {
        ParseInput<impl Iterator<Item = (Span, char)> + Clone>
    };
}

#[derive(Clone, Debug, PartialEq, Eq, PartialOrd, Ord)]
enum ErrorKind {
    ExpectedFound(String, String),
    StackEmpty(String),
    StrayControl(ControlKind),
    EOF,
    InvalidCloser {
        expected: AnyDelimiter,
        got: AnyDelimiter,
    },
    ExistingPreamble(String),
}
impl ErrorKind {
    fn with(self, span: impl Into<Span>) -> Error {
        Error(self, span.into())
    }
}
impl Display for ErrorKind {
    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
        match self {
            ErrorKind::ExpectedFound(expected, found) => {
                write!(f, "expected {expected}, found {found}")
            }
            ErrorKind::StackEmpty(expected) => write!(f, "stack empty; {expected}"),
            ErrorKind::StrayControl(control) => {
                write!(f, "expected a rule, got a control ({control:?})")
            }
            ErrorKind::EOF => write!(f, "unexpected end of file"),
            ErrorKind::InvalidCloser { expected, got } => write!(
                f,
                "expected {} to match {}, got {}",
                expected.closer(),
                expected.opener(),
                got.closer()
            ),
            ErrorKind::ExistingPreamble(preamble) => {
                write!(f, "preamble #{preamble} already exists")
            }
        }
    }
}
impl core::error::Error for ErrorKind {}

/// The error type.
#[derive(Clone, Debug, PartialEq, Eq, PartialOrd, Ord)]
pub struct Error(ErrorKind, Span);
impl Error {
    pub fn span(&self) -> Span {
        self.1
    }
    fn eof(end_span: Span) -> Self {
        ErrorKind::EOF.with(end_span)
    }
}
impl Display for Error {
    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
        write!(f, "{} (at {})", self.0, self.1)
    }
}
impl core::error::Error for Error {}
pub type Result<T> = core::result::Result<T, Error>;

/// Skips over as many whitespace characters as possible.
///
/// Used between many parsing functions.
pub fn skip_ws(input: &mut parse_input!()) {
    while let Some((_, ch)) = input.clone().next() {
        if !ch.is_whitespace() {
            return;
        }
        input.next();
    }
}

/// Attempts to parse an identifier. If already at EOF, `Ok(None)` is returned.
pub fn expect_identifier(input: &mut parse_input!()) -> Result<Option<(Span, String)>> {
    let (mut span, ch) = match input.next() {
        Some((span, ch @ pat_ident_start!())) => (span, ch),
        Some((span, other)) => {
            return Err(ErrorKind::ExpectedFound(
                "identifier".to_owned(),
                format!("character `{other}`"),
            )
            .with(span));
        }
        None => return Ok(None),
    };
    let mut output = String::from(ch);
    consume_identifier_rest(input, &mut span, &mut output);
    Ok(Some((span, output)))
}

/// Similar to `expect_identifier`, but errors on EOF.
pub fn identifier_or_eof(input: &mut parse_input!()) -> Result<(Span, String)> {
    expect_identifier(input)?.ok_or(input.eof())
}

/// After parsing the first character of an identifier, this can be used to parse the rest of the characters.
pub fn consume_identifier_rest(
    input: &mut parse_input!(),
    into_span: &mut Span,
    into: &mut String,
) {
    while let Some((span, ch @ pat_ident_body!())) = input.clone().next() {
        input.next();
        *into_span += span;
        into.push(ch);
    }
}

/// Expects some literal text content to appear in the character stream.
pub fn expect_exactly(input: &mut parse_input!(), string: &str) -> Result<Span> {
    let mut collected = String::new();
    let mut acc_span = input.current_span();
    for ch in string.chars() {
        let next = input.next();
        if let Some((span, test_ch)) = next {
            acc_span += span;
            collected.push(test_ch);
            if test_ch != ch {
                return Err(ErrorKind::ExpectedFound(
                    format!("`{string}`"),
                    format!("`{collected}`"),
                )
                .with(span));
            }
        } else {
            return Err(input.eof());
        }
    }
    Ok(acc_span)
}

/// Whether or not rule parsing should continue.
pub enum RuleStatus {
    Continue,
    End,
}

/// Parses the next rule, modifying the stack accordingly. Returns whether or not rule parsing should continue.
pub fn next_rule(input: &mut parse_input!(), stack: &mut PegStack) -> Result<RuleStatus> {
    let (mut peg_span, ch) = input.next().ok_or(input.eof())?;
    match ch {
        '"' => {
            let mut keyword = String::new();
            loop {
                let (span, ch) = input.next().ok_or(input.eof())?;
                peg_span += span;
                if ch == '"' {
                    break;
                }
                keyword.push(ch);
            }
            stack.add_rule(Rule::keyword(keyword, peg_span));
        }

        '\'' => {
            let mut punct = String::new();
            loop {
                let (span, ch) = input.next().ok_or(input.eof())?;
                if ch == '\'' {
                    peg_span += span;
                    break;
                }
                if !matches!(ch, pat_punct!()) {
                    return Err(ErrorKind::ExpectedFound(
                        "punctuation".to_owned(),
                        format!("character `{ch}`"),
                    )
                    .with(span));
                }
                peg_span += span;
                punct.push(ch);
            }
            stack.add_rule(Rule::punctuation(punct, peg_span));
        }

        '*' => {
            let separator = stack.raw_pop_rule(peg_span)?;
            let element = stack.take_rule(peg_span)?;
            let other_span = element.1 + separator.1;
            stack.add_rule(Rule::repeat(
                element,
                separator,
                AtLeast::Zero,
                peg_span + other_span,
            ));
        }
        '+' => {
            let separator = stack.raw_pop_rule(peg_span)?;
            let element = stack.take_rule(peg_span)?;
            let other_span = element.1 + separator.1;
            stack.add_rule(Rule::repeat(
                element,
                separator,
                AtLeast::One,
                peg_span + other_span,
            ));
        }
        '~' => {
            let Rule(kind, span) = stack.take_rule(peg_span)?;
            let RuleKind::Repeat(mut repeat) = kind else {
                return Err(ErrorKind::ExpectedFound(
                    "repetition rule".to_owned(),
                    "other rule".to_owned(),
                )
                .with(peg_span));
            };
            repeat.allow_trailing = true;
            stack.add_rule_kind(RuleKind::Repeat(repeat), peg_span + span);
        }
        '?' => {
            let element = stack.take_rule(peg_span)?;
            let element_span = element.1;
            stack.add_rule(Rule::optional(element, peg_span + element_span));
        }

        '.' => stack.add_rule(Rule::sequence(vec![], peg_span)),
        '<' => stack.0.push(Peg::sequence_start(peg_span)),
        '(' => stack
            .0
            .push(Peg::group_start(GroupDelimiter::Parenthesis, peg_span)),
        '[' => stack
            .0
            .push(Peg::group_start(GroupDelimiter::Bracket, peg_span)),
        '{' => stack
            .0
            .push(Peg::group_start(GroupDelimiter::Brace, peg_span)),
        '>' => {
            let mut sequence = vec![];
            let mut total_span = peg_span;
            loop {
                let peg = stack.0.pop().ok_or(
                    ErrorKind::StackEmpty("missing start control".to_owned()).with(peg_span),
                )?;
                total_span += peg.span();
                match peg {
                    Peg::Rule(rule) => {
                        total_span += rule.1;
                        sequence.push(rule);
                    }
                    Peg::Control(Control(ControlKind::GroupStart(delimiter), span)) => {
                        return Err(ErrorKind::ExpectedFound(
                            "sequence start control (`<`)".into(),
                            format!("group start control ({})", delimiter.opener()),
                        )
                        .with(span));
                    }
                    Peg::Control(Control(ControlKind::SequenceStart, span)) => {
                        sequence.reverse();
                        stack.add_rule(Rule::sequence(sequence, total_span + span));
                        break;
                    }
                }
            }
        }
        ch @ (')' | ']' | '}') => {
            let closer = match ch {
                ')' => GroupDelimiter::Parenthesis,
                ']' => GroupDelimiter::Bracket,
                '}' => GroupDelimiter::Brace,
                _ => unreachable!(),
            };
            let mut sequence = vec![];
            let mut inner_span = Span::default();
            loop {
                let peg = stack.0.pop().ok_or(
                    ErrorKind::StackEmpty("missing start control".to_owned()).with(peg_span),
                )?;
                peg_span += peg.span();
                match peg {
                    Peg::Rule(rule) => {
                        inner_span += rule.1;
                        sequence.push(rule);
                    }
                    Peg::Control(Control(ControlKind::GroupStart(opener), span)) => {
                        peg_span += span + inner_span;
                        if opener == closer {
                            sequence.reverse();
                            stack.add_rule(Rule::group(
                                opener,
                                if sequence.len() == 1 {
                                    sequence.pop().unwrap()
                                } else {
                                    Rule::sequence(sequence, inner_span)
                                },
                                peg_span,
                            ));
                            break;
                        } else {
                            return Err(ErrorKind::InvalidCloser {
                                expected: opener.into(),
                                got: closer.into(),
                            }
                            .with(span));
                        }
                    }
                    Peg::Control(Control(ControlKind::SequenceStart, span)) => {
                        return Err(ErrorKind::InvalidCloser {
                            expected: AnyDelimiter::AngleBrackets,
                            got: closer.into(),
                        }
                        .with(span));
                    }
                }
            }
        }

        '|' => {
            let after = parse_single_grammar(input)?;
            let first = stack.raw_pop_rule(peg_span)?;
            let rule = match first {
                Rule(RuleKind::Choice(mut choices), span) => {
                    choices.push(after);
                    Rule::choice(choices, peg_span + span)
                }
                other => {
                    let mut first_variant_span = other.1;
                    let mut first_variant_sequence = vec![other];
                    while let Some(peg) = stack.0.pop() {
                        match peg {
                            Peg::Control(control) => {
                                stack.0.push(Peg::Control(control));
                                peg_span += control.1;
                                break;
                            }
                            Peg::Rule(rule) => {
                                first_variant_span += rule.1;
                                first_variant_sequence.push(rule);
                            }
                        }
                    }
                    first_variant_sequence.reverse();
                    let first_variant_rule = if first_variant_sequence.len() == 1 {
                        first_variant_sequence.pop().unwrap()
                    } else {
                        Rule::sequence(first_variant_sequence, first_variant_span)
                    };
                    let after_span = after.1;
                    Rule::choice(
                        vec![first_variant_rule, after],
                        first_variant_span + peg_span + after_span,
                    )
                }
            };
            stack.add_rule(rule);
        }

        '@' => {
            let (span, builtin) = expect_identifier(input)?.ok_or(ErrorKind::EOF.with(peg_span))?;
            stack.add_rule(Rule::builtin(builtin, span));
        }
        ';' => return Ok(RuleStatus::End),

        ch @ pat_ident_start!() => {
            let mut rule_name = String::from(ch);
            consume_identifier_rest(input, &mut peg_span, &mut rule_name);
            stack.add_rule(Rule::other(rule_name, peg_span));
        }

        other => {
            return Err(ErrorKind::ExpectedFound(
                "rule".to_owned(),
                format!("character `{other}`"),
            )
            .with(peg_span));
        }
    }
    Ok(RuleStatus::Continue)
}

/// Parses a full grammar;
/// creates a new stack and calls `next_rule` repeatedly until no control grammars are on the stack and the stack is not empty.
pub fn parse_single_grammar(input: &mut parse_input!()) -> Result<Rule> {
    let mut stack = PegStack(vec![]);
    while stack.0.is_empty()
        || stack
            .0
            .iter()
            .any(|peg: &Peg| matches!(&peg, Peg::Control(_)))
    {
        skip_ws(input);
        if let RuleStatus::End = next_rule(input, &mut stack)? {
            return Err(input.eof());
        }
    }
    Ok(stack.0.pop().unwrap().try_as_rule()?)
}

/// A `#keywords` preamble.
#[derive(Clone, Debug, Default, Hash, PartialEq, Eq, PartialOrd, Ord)]
pub struct Keywords {
    pub soft: Vec<(Span, String)>,
    pub hard: Vec<(Span, String)>,
}
impl Display for Keywords {
    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
        if let [most @ .., last] = &self.soft[..] {
            write!(f, "#keywords soft ")?;
            for (_, word) in most {
                write!(f, "{word} ")?;
            }
            writeln!(f, "{};", last.1)?;
        }
        if let [most @ .., last] = &self.hard[..] {
            write!(f, "#keywords hard ")?;
            for (_, word) in most {
                write!(f, "{word} ")?;
            }
            writeln!(f, "{};", last.1)?;
        }
        Ok(())
    }
}

/// The set of preambles.
#[derive(Clone, Debug, Default, Hash, PartialEq, Eq, PartialOrd, Ord)]
pub struct Preambles {
    pub keywords: Keywords,
}
impl Display for Preambles {
    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
        writeln!(f, "{}", self.keywords)
    }
}

/// A TECTA PEG module.
#[derive(Clone, Debug, Default, Hash, PartialEq, Eq, PartialOrd, Ord)]
pub struct TectaPegModule {
    pub preambles: Preambles,
    pub rules: BTreeMap<String, Vec<Rule>>,
}
impl Display for TectaPegModule {
    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
        write!(f, "{}", self.preambles)?;
        for (rule_name, rules) in &self.rules {
            write!(f, "{rule_name} =")?;
            for rule in rules {
                write!(f, " {rule}")?;
            }
            writeln!(f, ";")?;
        }
        Ok(())
    }
}

/// Parses a list of identifiers.
pub fn parse_basic_identifier_list(input: &mut parse_input!()) -> Result<Vec<(Span, String)>> {
    let mut identifiers = vec![];
    loop {
        skip_ws(input);
        if let Some((_, ';')) = input.clone().next() {
            return Ok(identifiers);
        }
        identifiers.push(identifier_or_eof(input)?);
    }
}

/// Parses a TECTA PEG module; a set of preambles and rule definitions.
pub fn parse_module_inner(input: &mut parse_input!()) -> Result<TectaPegModule> {
    let mut module = TectaPegModule::default();
    loop {
        skip_ws(input);
        // TODO: split preamble into function
        if let Some((_, '#')) = input.clone().next() {
            input.next();
            let (span, name) = identifier_or_eof(input)?;
            match &name[..] {
                "keywords" => {
                    skip_ws(input);
                    let (span, name) = identifier_or_eof(input)?;
                    let is_hard = match &name[..] {
                        "hard" => true,
                        "soft" => false,
                        other => {
                            return Err(ErrorKind::ExpectedFound(
                                "keyword hardness".into(),
                                format!("`{other}`"),
                            )
                            .with(span));
                        }
                    };

                    let colon_span = expect_exactly(input, ":")?;
                    let specified_keywords = parse_basic_identifier_list(input)?;

                    if specified_keywords.is_empty() {
                        return Err(ErrorKind::ExpectedFound(
                            "non-empty keyword list".into(),
                            "empty list".into(),
                        )
                        .with(colon_span));
                    }

                    let target_keyword_set = if is_hard {
                        &mut module.preambles.keywords.hard
                    } else {
                        &mut module.preambles.keywords.soft
                    };
                    if !target_keyword_set.is_empty() {
                        return Err(ErrorKind::ExistingPreamble(format!(
                            "keywords {}",
                            if is_hard { "hard" } else { "soft" }
                        ))
                        .with(colon_span));
                    }

                    *target_keyword_set = specified_keywords;
                }
                other => {
                    return Err(
                        ErrorKind::ExpectedFound("preamble".into(), format!("`{other}`"))
                            .with(span),
                    );
                }
            }
            expect_exactly(input, ";")?;
        } else if let Some((_, rule_name)) = expect_identifier(input)? {
            skip_ws(input);
            let _eq_span = expect_exactly(input, "=")?;
            skip_ws(input);

            let mut peg_stack = PegStack(vec![]);
            while let RuleStatus::Continue = next_rule(input, &mut peg_stack)? {
                skip_ws(input);
            }
            skip_ws(input);

            let sequence = peg_stack
                .0
                .into_iter()
                .map(Peg::try_as_rule)
                .collect::<Result<Vec<_>>>()?;
            module.rules.insert(rule_name, sequence);
        } else {
            break;
        }
    }
    Ok(module)
}

/// Parses a TECTA PEG module from a string. See [`parse_module`].
pub fn parse_module(str: &str) -> Result<TectaPegModule> {
    let end_span = match str.lines().enumerate().last() {
        Some((index, line)) => Span {
            start_line: index + 1,
            end_line: index + 1,
            start_column: line.len(),
            end_column: line.len(),
        },
        None => Span::default(),
    };
    parse_module_inner(&mut ParseInput {
        chars: SpannedChars::new(str.chars()),
        end_span,
    })
}