muon/

tree.rs

//! The Muon tree and its JSON serialization.
//!
//! `to_json` emits a compact, tagged JSON dump used by the golden tests so they
//! read close to `muon-spec.md`. It is deliberately not Muon: other-language
//! implementations can compare against it with their own JSON parser (see the
//! language-agnostic-suite item in `docs/TODO.md`).

use alloc::boxed::Box;
use alloc::format;
use alloc::string::String;
use alloc::vec::Vec;
use core::mem;

/// A single visually-atomic entity in a chain (`<item>` in the spec).
#[derive(Debug, Clone, PartialEq, Eq)]
pub enum Item<'a> {
    /// A comment, stored raw *including* its `//` or `/* */` delimiters.
    Comm(&'a str),
    /// A string literal; the inner slice, *between* the quotes, undecoded
    /// (escapes are validated but not expanded — see the crate `open` note).
    Str(&'a str),
    /// A symbol: a maximal run of symchars (identifier, number, operator, …).
    Sym(&'a str),
    /// Punctuation: a maximal run of punctchars standing between items (`:`).
    Punct(&'a str),
    /// A parenthesis-wrapped sequence.
    Tuple(Seq<'a>),
    /// A bracket-wrapped sequence.
    List(Seq<'a>),
    /// A brace-wrapped sequence.
    Block(Seq<'a>),
    /// An item marked with a leading sigil (`&` is the only one so far).
    Prefixed { sigil: char, item: Box<Item<'a>> },
}

/// A chain: one or more juxtaposed items (`<chain>`). Never empty.
#[derive(Debug, Clone, PartialEq, Eq)]
pub struct Chain<'a>(pub Vec<Item<'a>>);

/// A sequence: zero or more chains delimited by separators (`<seq>`).
#[derive(Debug, Clone, PartialEq, Eq)]
pub struct Seq<'a>(pub Vec<Chain<'a>>);

/// Tear the tree down iteratively, so dropping a deeply-nested tree (the parser
/// bounds nesting only by memory) can't overflow the stack the way the default
/// recursive `Drop` would. `Item` itself has no `Drop`, so leaves — the vast
/// majority of nodes — drop trivially; the cost falls only on the nesting nodes
/// walked here. The two recursion points are containers (a nested `Seq`) and
/// `Prefixed` (a boxed inner `Item`); both are drained onto a heap worklist
/// before the node holding them drops, so no `Drop` call nests.
impl Drop for Seq<'_> {
    fn drop(&mut self) {
        // Leaves — the vast majority of nodes — drop in place as `collect_nesting`
        // iterates; only the nesting nodes reach `work`, so a flat tree never
        // allocates one and a deep tree is torn down a level at a time.
        let mut work: Vec<Item> = Vec::new();
        collect_nesting(self, &mut work);
        while let Some(mut item) = work.pop() {
            match &mut item {
                Item::Tuple(seq) | Item::List(seq) | Item::Block(seq) => {
                    collect_nesting(seq, &mut work);
                }
                Item::Prefixed { item, .. } => {
                    let inner = mem::replace(item.as_mut(), Item::Sym(""));
                    if inner.nests() {
                        work.push(inner);
                    }
                }
                _ => {}
            }
            // `item` drops here with its nesting already moved out: a container's
            // inner `Seq` is empty and a `Prefixed`'s box now holds a leaf, so
            // neither recurses.
        }
    }
}

/// Drop `seq`'s leaves in place and move its nesting items onto `work`, leaving
/// `seq` empty.
fn collect_nesting<'a>(seq: &mut Seq<'a>, work: &mut Vec<Item<'a>>) {
    for chain in mem::take(&mut seq.0) {
        for item in chain.0 {
            if item.nests() {
                work.push(item);
            }
            // else: a leaf, dropped here as the loop advances.
        }
    }
}

impl Seq<'_> {
    /// Serialize the tree to compact, tagged JSON.
    pub fn to_json(&self) -> String {
        let mut out = String::new();
        self.write_json(&mut out);
        out
    }

    fn write_json(&self, out: &mut String) {
        out.push_str("{\"seq\":[");
        for (i, chain) in self.0.iter().enumerate() {
            if i > 0 {
                out.push(',');
            }
            chain.write_json(out);
        }
        out.push_str("]}");
    }
}

impl Chain<'_> {
    fn write_json(&self, out: &mut String) {
        out.push_str("{\"chain\":[");
        for (i, item) in self.0.iter().enumerate() {
            if i > 0 {
                out.push(',');
            }
            item.write_json(out);
        }
        out.push_str("]}");
    }
}

impl Item<'_> {
    /// Whether this item owns nested items (a container's `Seq` or a `Prefixed`'s
    /// boxed item) — the nodes the iterative `Drop for Seq` must walk.
    fn nests(&self) -> bool {
        matches!(
            self,
            Item::Tuple(_) | Item::List(_) | Item::Block(_) | Item::Prefixed { .. }
        )
    }

    fn write_json(&self, out: &mut String) {
        match self {
            Item::Comm(s) => {
                out.push_str("{\"comm\":");
                json_str(s, out);
                out.push('}');
            }
            Item::Str(s) => {
                out.push_str("{\"str\":");
                json_str(s, out);
                out.push('}');
            }
            Item::Sym(s) => {
                out.push_str("{\"sym\":");
                json_str(s, out);
                out.push('}');
            }
            Item::Punct(s) => {
                out.push_str("{\"punct\":");
                json_str(s, out);
                out.push('}');
            }
            Item::Tuple(seq) => {
                out.push_str("{\"tuple\":");
                seq.write_json(out);
                out.push('}');
            }
            Item::List(seq) => {
                out.push_str("{\"list\":");
                seq.write_json(out);
                out.push('}');
            }
            Item::Block(seq) => {
                out.push_str("{\"block\":");
                seq.write_json(out);
                out.push('}');
            }
            Item::Prefixed { sigil, item } => {
                out.push_str("{\"pre\":");
                let mut buf = [0u8; 4];
                json_str(sigil.encode_utf8(&mut buf), out);
                out.push_str(",\"item\":");
                item.write_json(out);
                out.push('}');
            }
        }
    }
}

/// Write `s` as a JSON string literal (quoted and escaped).
fn json_str(s: &str, out: &mut String) {
    out.push('"');
    for ch in s.chars() {
        match ch {
            '"' => out.push_str("\\\""),
            '\\' => out.push_str("\\\\"),
            '\n' => out.push_str("\\n"),
            '\r' => out.push_str("\\r"),
            '\t' => out.push_str("\\t"),
            c if (c as u32) < 0x20 => out.push_str(&format!("\\u{:04x}", c as u32)),
            c => out.push(c),
        }
    }
    out.push('"');
}