muon/

parse.rs

//! Scannerless parser driven by an explicit heap stack.
//!
//! Nesting (tuples, lists, blocks, and prefixed items) is walked with an explicit
//! `Vec` of open frames rather than Rust recursion, so nesting depth is bounded
//! only by available memory — no call-stack growth, no overflow on adversarial
//! input, and no depth cap.
//!
//! Newlines are significant: ` `, `\r`, `\t` are whitespace, but `\n` and `,`
//! are separators (`<sep>`). A `\r\n` therefore reads as whitespace `\r`
//! followed by a `\n` separator, so `\r\n` and `\n` parse identically.

use alloc::boxed::Box;
use alloc::vec::Vec;

use crate::tree::{Chain, Group, Item, Seq, Span};

/// Parse a whole Muon file: a top-level `<seq>` up to end of input.
pub fn parse(input: &str) -> Result<Seq<'_>, ParseError> {
    // Spans hold `u32` offsets.
    if u32::try_from(input.len()).is_err() {
        return Err(ParseError {
            offset: 0,
            kind: ErrorKind::InputTooLong,
        });
    }
    let mut p = Parser {
        src: input,
        bytes: input.as_bytes(),
        pos: 0,
    };

    // The container being built is kept in the local `cur` so the hot path (a
    // chain of leaves) touches it as a register-resident value, not through the
    // stack. `stack` holds only the *suspended* enclosing containers, pushed on
    // an opener and resumed on the matching closer. `pending` holds sigils read
    // but not yet attached to their item (see `<prefixed>`).
    let mut cur = Frame::top();
    let mut stack: Vec<Frame> = Vec::new();
    // Sigils read but not yet attached to their item, plus the byte offset of the
    // first one (the start of the atom being built — a run glues to the previous
    // atom only when this start touches its end).
    let mut pending: Vec<char> = Vec::new();
    let mut pending_start: Option<usize> = None;

    // A `#!` at byte offset 0 is a shebang: a `<comm>` running to the end of its
    // line, stored raw with its `#!`. This is the notation's one position-
    // dependent rule — anywhere else `#` is the `<prefixed>` sigil. The trailing
    // `\n` (if any) is left for the loop to read as a `<sep>`, exactly as for a
    // `//` line comment.
    if p.bytes.starts_with(b"#!") {
        let start = p.pos;
        while let Some(c) = p.peek() {
            if c == b'\n' {
                break;
            }
            p.bump();
        }
        cur.push_break(Item::Comm(&p.src[start..p.pos]));
    }

    loop {
        p.skip_ws();
        match p.peek() {
            // End of input: an open container is unclosed; the top level is done.
            None => {
                if let Some(t) = cur.term {
                    return Err(p.err(Parser::unclosed(t)));
                }
                cur.flush_chain();
                break;
            }
            // The closer we were waiting for: finish this container, wrap it in any
            // sigils it carried, resume the parent, and attach it to its chain —
            // gluing it into a run if it touches the parent's previous atom.
            Some(c) if Some(c) == cur.term => {
                p.bump(); // consume the terminator
                cur.flush_chain();
                let start = cur.start;
                let group = Group {
                    seq: Seq(core::mem::take(&mut cur.chains)),
                    span: Span {
                        offset: cur.open as u32,
                        length: (p.pos - cur.open) as u32,
                    },
                };
                let item = wrap(build_container(c, group), &cur.sigils);
                cur = stack.pop().expect("a closer implies an open parent");
                cur.push_atom(item, start, p.pos);
            }
            // A separator ends the current chain (empty slots collapse to nothing).
            Some(c) if Parser::is_sep(c) => {
                p.bump();
                cur.flush_chain();
            }
            // A closer that isn't our terminator: stray, or a mismatched bracket.
            Some(c) if Parser::is_close(c) => {
                return Err(p.err(Parser::unexpected_close(c)));
            }
            // `&` / `#` sigils: each must glue to an item, else it dangles.
            Some(s @ (b'&' | b'#')) => {
                let sig = p.pos;
                p.bump(); // consume the sigil
                match p.peek() {
                    Some(c) if Parser::opens_glued_item(c) => {
                        if pending.is_empty() {
                            pending_start = Some(sig);
                        }
                        pending.push(s as char);
                    }
                    _ => return Err(p.err(ErrorKind::DanglingSigil)),
                }
            }
            // `.`: a sigil when right-glued to an item, else a standalone `<punct>`.
            Some(b'.') => match p.at(1) {
                Some(c) if Parser::opens_glued_item(c) => {
                    let sig = p.pos;
                    p.bump(); // consume '.'
                    if pending.is_empty() {
                        pending_start = Some(sig);
                    }
                    pending.push('.');
                }
                _ => {
                    let start = p.pos;
                    p.bump(); // consume '.'
                              // A punct ends a run; any pending sigils still wrap it (`..`).
                    let item = wrap(Item::Punct(&p.src[start..p.pos]), &pending);
                    pending.clear();
                    pending_start = None;
                    cur.push_break(item);
                }
            },
            // An opener suspends the current container and starts a fresh one,
            // inheriting any pending sigils so they wrap it once it closes. The
            // atom's start (sigil or opener) rides the child frame to its close.
            Some(c @ (b'(' | b'[' | b'{')) => {
                let open = p.pos;
                let start = pending_start.take().unwrap_or(open);
                p.bump(); // consume the opener
                let term = match c {
                    b'(' => b')',
                    b'[' => b']',
                    _ => b'}',
                };
                let sigils = core::mem::take(&mut pending);
                let child = Frame {
                    term: Some(term),
                    sigils,
                    start,
                    open,
                    chains: Vec::new(),
                    items: Vec::new(),
                    last_end: None,
                };
                stack.push(core::mem::replace(&mut cur, child));
            }
            // Leaves: parse in place (they never nest) and attach with any sigils,
            // gluing into a run when they touch the previous atom.
            Some(b'"') => {
                let start = pending_start.take().unwrap_or(p.pos);
                let item = wrap(p.parse_str()?, &pending);
                pending.clear();
                cur.push_atom(item, start, p.pos);
            }
            // A comment ends a run; any pending sigils still wrap it (`.//c`).
            Some(b'/') => {
                let item = wrap(p.parse_comment()?, &pending);
                pending.clear();
                pending_start = None;
                cur.push_break(item);
            }
            Some(c) if Parser::is_symchar(c) => {
                let start = pending_start.take().unwrap_or(p.pos);
                let item = wrap(p.parse_sym(), &pending);
                pending.clear();
                cur.push_atom(item, start, p.pos);
            }
            Some(c) if Parser::is_punctchar(c) => {
                // A punct ends a run; any pending sigils still wrap it (`&:`).
                let item = wrap(p.parse_punct(), &pending);
                pending.clear();
                pending_start = None;
                cur.push_break(item);
            }
            _ => return Err(p.err(ErrorKind::UnexpectedChar)),
        }
    }

    Ok(Seq(cur.chains))
}

/// One open container on the parse stack: the `<seq>` being built inside it, plus
/// the sigils (if any) that will wrap it once it closes.
struct Frame<'a> {
    /// The closing byte to stop at (`)`/`]`/`}`), or `None` for the top level.
    term: Option<u8>,
    /// Sigils to wrap this container's `Item` on close; empty at top level.
    sigils: Vec<char>,
    /// Byte offset where this container's atom begins (its sigil, or its opener),
    /// used to glue it into a run when it closes. Unused for the top frame.
    start: usize,
    /// Byte offset of this container's opening bracket, where its span starts.
    /// Unused for the top frame.
    open: usize,
    /// Completed chains of the seq.
    chains: Vec<Chain<'a>>,
    /// Items of the in-progress chain, flushed into `chains` at a separator/close.
    items: Vec<Item<'a>>,
    /// Byte offset just past the last atom pushed to the in-progress chain, or
    /// `None` when the chain is empty or its last item was a punct/comment (a run
    /// never spans those). An atom whose start touches this glues into a run.
    last_end: Option<usize>,
}

impl<'a> Frame<'a> {
    fn top() -> Self {
        Frame {
            term: None,
            sigils: Vec::new(),
            start: 0,
            open: 0,
            chains: Vec::new(),
            items: Vec::new(),
            last_end: None,
        }
    }

    /// End the in-progress chain, if any. A `<chain>` is never empty, so a run of
    /// separators (or a container that opened and closed empty) adds no chain.
    fn flush_chain(&mut self) {
        if !self.items.is_empty() {
            self.chains.push(Chain(core::mem::take(&mut self.items)));
        }
        self.last_end = None;
    }

    /// Attach an atom (`start`..`end`) to the current chain. If it touches the
    /// previous atom (`last_end == Some(start)`) the two glue into a `Run`,
    /// extending an existing run in place or starting a fresh two-member one;
    /// otherwise it is a bare item. Records `end` as the new run anchor.
    fn push_atom(&mut self, item: Item<'a>, start: usize, end: usize) {
        if self.last_end == Some(start) {
            match self.items.last_mut() {
                Some(Item::Run(members)) => members.push(item),
                _ => {
                    let prev = self.items.pop().expect("glue implies a previous atom");
                    let mut members = Vec::with_capacity(4);
                    members.push(prev);
                    members.push(item);
                    self.items.push(Item::Run(members));
                }
            }
        } else {
            self.items.push(item);
        }
        self.last_end = Some(end);
    }

    /// Attach an item that ends any run in progress and joins none — a `<punct>`
    /// or a `<comm>`. The next atom cannot glue onto it.
    fn push_break(&mut self, item: Item<'a>) {
        self.items.push(item);
        self.last_end = None;
    }
}

/// Wrap `item` in `sigils` outermost-first: the first sigil read (index 0) ends up
/// the outermost `Prefixed`, so `&.x` is `&(.(x))`.
fn wrap<'a>(mut item: Item<'a>, sigils: &[char]) -> Item<'a> {
    for &sigil in sigils.iter().rev() {
        item = Item::Prefixed {
            sigil,
            item: Box::new(item),
        };
    }
    item
}

/// Build the container `Item` for a group from the closer that ended it.
fn build_container(term: u8, group: Group<'_>) -> Item<'_> {
    match term {
        b')' => Item::Parens(group),
        b']' => Item::Brackets(group),
        _ => Item::Braces(group),
    }
}

/// A parse failure, with the byte offset into the input where it was detected.
#[derive(Debug, Clone, PartialEq, Eq)]
pub struct ParseError {
    pub offset: usize,
    pub kind: ErrorKind,
}

#[derive(Debug, Clone, PartialEq, Eq)]
pub enum ErrorKind {
    /// A character that cannot begin an item (e.g. a lone `/`).
    UnexpectedChar,
    /// A `)` with no matching `(`.
    UnexpectedCloseParen,
    /// A `]` with no matching `[`.
    UnexpectedCloseBracket,
    /// A `}` with no matching `{`.
    UnexpectedCloseBrace,
    /// A `(` whose `)` never arrived before end of input.
    UnclosedParens,
    /// A `[` whose `]` never arrived before end of input.
    UnclosedBrackets,
    /// A `{` whose `}` never arrived before end of input.
    UnclosedBraces,
    /// A `"` whose closing `"` never arrived before end of input.
    UnclosedString,
    /// A `/*` whose `*/` never arrived before end of input.
    UnclosedComment,
    /// A `\` followed by a character other than `" n t r \ / b f`, or a `\u`
    /// not followed by exactly four hex digits.
    BadEscape,
    /// A literal newline inside a string literal.
    RawNewlineInString,
    /// A `&` or `#` sigil not immediately followed by an item.
    DanglingSigil,
    /// An input of `u32::MAX` bytes or more, past what a [`Span`] can locate.
    InputTooLong,
}

struct Parser<'a> {
    src: &'a str,
    bytes: &'a [u8],
    pos: usize,
}

impl<'a> Parser<'a> {
    fn peek(&self) -> Option<u8> {
        self.bytes.get(self.pos).copied()
    }

    fn at(&self, off: usize) -> Option<u8> {
        self.bytes.get(self.pos + off).copied()
    }

    fn bump(&mut self) {
        self.pos += 1;
    }

    fn err(&self, kind: ErrorKind) -> ParseError {
        ParseError {
            offset: self.pos,
            kind,
        }
    }

    /// Skip inline whitespace only: ` `, `\r`, `\t`. Never `\n` (a separator).
    fn skip_ws(&mut self) {
        while let Some(c) = self.peek() {
            if c == b' ' || c == b'\r' || c == b'\t' {
                self.pos += 1;
            } else {
                break;
            }
        }
    }

    pub(crate) fn is_symchar(c: u8) -> bool {
        matches!(c,
            b'0'..=b'9' | b'A'..=b'Z' | b'a'..=b'z'
            | b'_' | b'-' | b'+')
    }

    /// Punctchars stand between items (never inside a literal): `:`, `=`, `|`,
    /// `>`, `<`. (`>` lets `|>` and a future `=>` munch as one `<punct>`; `<`/`>`
    /// give Elly the ordering-pattern operators `< e` / `> e`.)
    fn is_punctchar(c: u8) -> bool {
        c == b':' || c == b'=' || c == b'|' || c == b'>' || c == b'<'
    }

    fn is_sep(c: u8) -> bool {
        c == b',' || c == b'\n'
    }

    fn is_close(c: u8) -> bool {
        c == b')' || c == b']' || c == b'}'
    }

    /// True when `c`, sitting directly after a sigil, opens a glued item — i.e.
    /// it is not whitespace, a `<sep>`, or a closer. Used to tell a `<prefixed>`
    /// from a dangling sigil.
    fn opens_glued_item(c: u8) -> bool {
        c != b' ' && c != b'\r' && c != b'\t' && !Self::is_sep(c) && !Self::is_close(c)
    }

    /// The error for a closing bracket with no matching opener (or a mismatch).
    fn unexpected_close(c: u8) -> ErrorKind {
        match c {
            b')' => ErrorKind::UnexpectedCloseParen,
            b']' => ErrorKind::UnexpectedCloseBracket,
            _ => ErrorKind::UnexpectedCloseBrace,
        }
    }

    /// The error for an opener (whose closer is `term`) that never arrived.
    fn unclosed(term: u8) -> ErrorKind {
        match term {
            b')' => ErrorKind::UnclosedParens,
            b']' => ErrorKind::UnclosedBrackets,
            _ => ErrorKind::UnclosedBraces,
        }
    }

    fn parse_sym(&mut self) -> Item<'a> {
        let start = self.pos;
        while let Some(c) = self.peek() {
            if Self::is_symchar(c) {
                self.pos += 1;
            } else {
                break;
            }
        }
        Item::Sym(&self.src[start..self.pos])
    }

    /// A maximal run of punctchars, e.g. `:`, `::`, `=`, `==`, `:=`, `|>`.
    fn parse_punct(&mut self) -> Item<'a> {
        let start = self.pos;
        while let Some(c) = self.peek() {
            if Self::is_punctchar(c) {
                self.pos += 1;
            } else {
                break;
            }
        }
        Item::Punct(&self.src[start..self.pos])
    }

    /// A `//` line comment or a `/* */` block comment (non-nesting), stored raw
    /// with its delimiters. Newlines inside a block comment are not separators.
    fn parse_comment(&mut self) -> Result<Item<'a>, ParseError> {
        let start = self.pos;
        self.bump(); // consume '/'
        match self.peek() {
            Some(b'/') => {
                self.bump();
                while let Some(c) = self.peek() {
                    if c == b'\n' {
                        break;
                    }
                    self.pos += 1;
                }
                Ok(Item::Comm(&self.src[start..self.pos]))
            }
            Some(b'*') => {
                self.bump();
                loop {
                    match self.peek() {
                        None => {
                            return Err(ParseError {
                                offset: start,
                                kind: ErrorKind::UnclosedComment,
                            })
                        }
                        Some(b'*') if self.at(1) == Some(b'/') => {
                            self.pos += 2;
                            break;
                        }
                        Some(_) => self.pos += 1,
                    }
                }
                Ok(Item::Comm(&self.src[start..self.pos]))
            }
            // A lone '/' is not a symchar, so it can only open a comment.
            _ => Err(self.err(ErrorKind::UnexpectedChar)),
        }
    }

    fn parse_str(&mut self) -> Result<Item<'a>, ParseError> {
        let open = self.pos;
        self.bump(); // opening quote
        let start = self.pos;
        loop {
            match self.peek() {
                None => {
                    return Err(ParseError {
                        offset: open,
                        kind: ErrorKind::UnclosedString,
                    })
                }
                Some(b'"') => {
                    let inner = &self.src[start..self.pos];
                    self.bump(); // closing quote
                    return Ok(Item::Str(inner));
                }
                Some(b'\n') => return Err(self.err(ErrorKind::RawNewlineInString)),
                Some(b'\\') => match self.at(1) {
                    // Single-character escapes: Muon's own plus JSON's `\/ \b \f`.
                    Some(b'"') | Some(b'n') | Some(b't') | Some(b'r') | Some(b'\\')
                    | Some(b'/') | Some(b'b') | Some(b'f') => {
                        self.pos += 2;
                    }
                    // `\uXXXX` — validate exactly four hex digits, nothing more.
                    // Combining surrogate pairs and decoding the code point is a
                    // higher-layer job (see docs/todo/elly-json.md); the notation
                    // layer only accepts the escape *grammar* and stores it raw.
                    Some(b'u') => {
                        for off in 2..6 {
                            match self.at(off) {
                                Some(c) if c.is_ascii_hexdigit() => {}
                                _ => return Err(self.err(ErrorKind::BadEscape)),
                            }
                        }
                        self.pos += 6;
                    }
                    _ => return Err(self.err(ErrorKind::BadEscape)),
                },
                Some(_) => self.pos += 1,
            }
        }
    }
}

/// Whether `s` is a single Muon `<sym>`: non-empty, every byte a symchar
/// (`0-9`, `A-Z`, `a-z`, `_`, `-`, `+`).
pub fn is_sym(s: &str) -> bool {
    !s.is_empty() && s.bytes().all(Parser::is_symchar)
}