blr-lang 0.1.0

//! Shared s-expression parser infrastructure for all compiler layers.
//!
//! Provides a tokenizer, S-Expr AST, parsing trait, and ID supply for synthesizing
//! fresh node/variable/item IDs during parsing.

use std::fmt;

// ── Tokenizer ──────────────────────────────────────────────────────────

#[derive(Debug, Clone, PartialEq)]
pub enum Token {
    LParen,
    RParen,
    Atom(String),
}

fn tokenize(input: &str) -> Result<Vec<Token>, ParseError> {
    let mut tokens = Vec::new();
    let mut chars = input.chars().peekable();

    while let Some(ch) = chars.next() {
        match ch {
            ' ' | '\t' | '\n' | '\r' => {}
            '(' => tokens.push(Token::LParen),
            ')' => tokens.push(Token::RParen),
            '"' => {
                let (string, _) = parse_quoted_string(&mut chars)?;
                tokens.push(Token::Atom(string));
            }
            _ => {
                let mut atom = String::new();
                atom.push(ch);
                while let Some(&next) = chars.peek() {
                    if next == '('
                        || next == ')'
                        || next == ' '
                        || next == '\t'
                        || next == '\n'
                        || next == '\r'
                        || next == '"'
                    {
                        break;
                    }
                    atom.push(next);
                    chars.next();
                }
                tokens.push(Token::Atom(atom));
            }
        }
    }
    Ok(tokens)
}

fn parse_quoted_string(
    chars: &mut std::iter::Peekable<std::str::Chars>,
) -> Result<(String, usize), ParseError> {
    let mut string = String::new();
    let mut pos = 1usize;

    loop {
        match chars.next() {
            Some('"') => return Ok((string, pos)),
            Some('\\') => match chars.next() {
                Some('"') => string.push('"'),
                Some('\\') => string.push('\\'),
                Some('n') => string.push('\n'),
                Some('t') => string.push('\t'),
                Some(c) => {
                    string.push('\\');
                    string.push(c);
                }
                None => return Err(ParseError::UnterminatedString),
            },
            Some(c) => {
                string.push(c);
                pos += 1;
            }
            None => return Err(ParseError::UnterminatedString),
        }
    }
}

// ── S-Expr AST ─────────────────────────────────────────────────────────

#[derive(Debug, Clone, PartialEq)]
pub enum SExpr {
    Atom(String),
    List(Vec<SExpr>),
}

impl SExpr {
    pub fn tag(&self) -> Option<&str> {
        match self {
            SExpr::List(list) => list.first().and_then(|a| match a {
                SExpr::Atom(s) => Some(s.as_str()),
                _ => None,
            }),
            _ => None,
        }
    }

    pub fn args(&self) -> Option<&[SExpr]> {
        match self {
            SExpr::List(list) => {
                if list.len() > 1 {
                    Some(&list[1..])
                } else {
                    Some(&[])
                }
            }
            _ => None,
        }
    }

    pub fn elements(&self) -> Option<&[SExpr]> {
        match self {
            SExpr::List(list) => Some(list),
            _ => None,
        }
    }
}

// ── Parser ─────────────────────────────────────────────────────────────

/// Parse a string of s-expressions into a flat list of `SExpr` values.
pub fn parse(input: &str) -> Result<Vec<SExpr>, ParseError> {
    let tokens = tokenize(input)?;
    let mut parser = Parser { tokens, pos: 0 };
    let mut result = Vec::new();
    while parser.pos < parser.tokens.len() {
        result.push(parser.parse_sexp()?);
    }
    Ok(result)
}

/// Parse a single top-level s-expression.
pub fn parse_one(input: &str) -> Result<SExpr, ParseError> {
    let tokens = tokenize(input)?;
    let mut parser = Parser { tokens, pos: 0 };
    let expr = parser.parse_sexp()?;
    if parser.pos < parser.tokens.len() {
        return Err(ParseError::TrailingTokens {
            remaining: parser.tokens[parser.pos..].to_vec(),
        });
    }
    Ok(expr)
}

struct Parser {
    tokens: Vec<Token>,
    pos: usize,
}

impl Parser {
    fn parse_sexp(&mut self) -> Result<SExpr, ParseError> {
        let token = match self.peek() {
            Some(t) => t.clone(),
            None => return Err(ParseError::UnexpectedEOF),
        };
        match token {
            Token::LParen => {
                self.next();
                let mut elements = Vec::new();
                loop {
                    let next_token = match self.peek() {
                        Some(t) => t.clone(),
                        None => return Err(ParseError::UnmatchedLParen),
                    };
                    match next_token {
                        Token::RParen => {
                            self.next();
                            return Ok(SExpr::List(elements));
                        }
                        _ => elements.push(self.parse_sexp()?),
                    }
                }
            }
            Token::Atom(s) => {
                self.next();
                Ok(SExpr::Atom(s))
            }
            Token::RParen => Err(ParseError::UnmatchedRParen),
        }
    }

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

    fn next(&mut self) -> Option<Token> {
        let token = self.tokens.get(self.pos).cloned();
        self.pos += 1;
        token
    }
}

// ── ParseError ─────────────────────────────────────────────────────────

#[derive(Debug, Clone, PartialEq)]
pub enum ParseError {
    UnexpectedToken {
        expected: &'static str,
        found: String,
    },
    ExpectedTag {
        expected: &'static str,
        found: Option<String>,
    },
    ExpectedArgs {
        expected: usize,
        found: usize,
    },
    ParseValue {
        type_name: &'static str,
        reason: String,
    },
    UnmatchedLParen,
    UnmatchedRParen,
    UnexpectedEOF,
    TrailingTokens {
        remaining: Vec<Token>,
    },
    UnterminatedString,
}

impl fmt::Display for ParseError {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        match self {
            ParseError::UnexpectedToken { expected, found } => {
                write!(f, "expected {expected}, found '{found}'")
            }
            ParseError::ExpectedTag { expected, found } => match found {
                Some(tag) => write!(f, "expected tag '{expected}', found '{tag}'"),
                None => write!(f, "expected tag '{expected}', found non-list"),
            },
            ParseError::ExpectedArgs { expected, found } => {
                write!(f, "expected {expected} arguments, found {found}")
            }
            ParseError::ParseValue { type_name, reason } => {
                write!(f, "failed to parse {type_name}: {reason}")
            }
            ParseError::UnmatchedLParen => write!(f, "unmatched '('"),
            ParseError::UnmatchedRParen => write!(f, "unmatched ')'"),
            ParseError::UnexpectedEOF => write!(f, "unexpected end of input"),
            ParseError::TrailingTokens { .. } => write!(f, "trailing tokens after expression"),
            ParseError::UnterminatedString => write!(f, "unterminated string literal"),
        }
    }
}

impl std::error::Error for ParseError {}

// ── Display ────────────────────────────────────────────────────────────

use pretty::{DocAllocator, RcAllocator};

/// Format an atom for display, adding quotes if necessary.
///
/// An atom needs quoting if it is empty or contains whitespace, parentheses,
/// quotes, or backslashes — characters that would confuse the tokenizer.
fn quote_atom<'a, 'b>(
    s: &'b str,
    allocator: &'a RcAllocator,
) -> pretty::DocBuilder<'a, RcAllocator, ()>
where
    'b: 'a,
{
    let needs_quoting = s.is_empty()
        || s.chars()
            .any(|c| c.is_whitespace() || c == '(' || c == ')' || c == '"' || c == '\\');
    if needs_quoting {
        // Escape backslashes and double quotes inside the string
        let escaped: String = s
            .chars()
            .map(|c| match c {
                '\\' => "\\\\".into(),
                '"' => "\\\"".into(),
                '\n' => "\\n".into(),
                '\t' => "\\t".into(),
                _ => c.to_string(),
            })
            .collect();
        allocator.text(format!("\"{}\"", escaped))
    } else {
        allocator.text(s)
    }
}

impl std::fmt::Display for SExpr {
    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
        let allocator = RcAllocator;
        format_sexpr(self, &allocator).render_fmt(80, f)
    }
}

fn format_sexpr<'a, 'b>(
    s: &'b SExpr,
    allocator: &'a RcAllocator,
) -> pretty::DocBuilder<'a, RcAllocator, ()>
where
    'b: 'a,
{
    match s {
        SExpr::Atom(s) => quote_atom(s, allocator),
        SExpr::List(list) => allocator
            .intersperse(
                list.iter().map(|s| format_sexpr(s, allocator)),
                allocator.line(),
            )
            .nest(2)
            .group()
            .parens(),
    }
}

// ── ToSExpr Trait ──────────────────────────────────────────────────────

/// Convert a type into a structured S-Expr.
///
/// Each layer implements this for their AST types. The returned `SExpr` is
/// structured (not a formatted string), so callers can compose or traverse it.
/// The `config` parameter controls formatting details (e.g., node IDs, type
/// annotations, metadata).
pub trait ToSExpr<C = ()> {
    fn to_sexpr(&self, config: &C) -> SExpr;
}

// ── Format Helpers ─────────────────────────────────────────────────────

/// Format a `ToSExpr` type as a human-readable string.
pub fn format<C>(sexpr: &impl ToSExpr<C>, _config: &C) -> String {
    sexpr.to_sexpr(_config).to_string()
}

/// Format a `ToSExpr` type using box-drawing characters.
pub fn format_box_for<C, S: ToSExpr<C>, W: fmt::Write>(
    sexpr: &S,
    config: &C,
    buffer: &mut W,
) -> fmt::Result {
    format_box(buffer, &sexpr.to_sexpr(config))
}

/// Format a `ToSExpr` type using pretty-printed s-expr (line-wrapping at 80 chars).
pub fn format_sexpr_for<C, S: ToSExpr<C>, W: fmt::Write>(
    sexpr: &S,
    config: &C,
    buffer: &mut W,
) -> fmt::Result {
    let allocator = RcAllocator;
    format_sexpr(&sexpr.to_sexpr(config), &allocator).render_fmt(80, buffer)
}

// ── FromSExpr Trait ────────────────────────────────────────────────────

/// Convert an S-Expr into a type.
///
/// Each layer implements this for their AST types. The `ctx` parameter
/// provides mutable state for parsing — e.g., fresh ID allocation during
/// `from_sexp` for AST nodes.
pub trait FromSExpr<Ctx = ()>: Sized {
    fn from_sexp(s: &SExpr, ctx: &mut Ctx) -> Result<Self, ParseError>;
}

/// Validate that an S-Expr list has exactly N arguments.
pub fn expect_n<'a, const N: usize>(
    tag: &'static str,
    args: Option<&'a [SExpr]>,
) -> Result<&'a [SExpr; N], ParseError> {
    let args = args.ok_or(ParseError::ExpectedTag {
        expected: tag,
        found: None,
    })?;
    args.try_into().map_err(|_| ParseError::ExpectedArgs {
        expected: N,
        found: args.len(),
    })
}

// ── Box-style formatting ──────────────────────────────────────────────────

/// Format an s-expression using box-drawing characters.
///
/// Each child of a list is printed on its own line, indented under the parent.
pub fn format_box<F: fmt::Write>(buffer: &mut F, sexpr: &SExpr) -> fmt::Result {
    let mut fmt = BoxFmt {
        buffer,
        prefixes: Vec::new(),
    };
    fmt.format_root(sexpr)
}

struct BoxFmt<'a, F> {
    buffer: &'a mut F,
    prefixes: Vec<bool>,
}

impl<'a, F: fmt::Write> BoxFmt<'a, F> {
    fn format_root(&mut self, sexpr: &SExpr) -> fmt::Result {
        match sexpr {
            SExpr::List(items) => {
                if let Some(tag) = items.first() {
                    self.write_tag(tag)?;
                    self.buffer.write_str("\n")?;

                    for (i, child) in items.iter().skip(1).enumerate() {
                        let child_is_last = i == items.len() - 2;
                        self.format_child(child, child_is_last)?;
                    }
                } else {
                    self.buffer.write_str("()\n")?;
                }
            }
            SExpr::Atom(s) => {
                self.buffer.write_str(s)?;
                self.buffer.write_str("\n")?;
            }
        }
        Ok(())
    }

    fn format_child(&mut self, sexpr: &SExpr, is_last: bool) -> fmt::Result {
        self.write_prefix()?;

        if is_last {
            self.buffer.write_str("└── ")?;
        } else {
            self.buffer.write_str("├── ")?;
        }

        match sexpr {
            SExpr::List(items) => {
                if let Some(tag) = items.first() {
                    self.write_tag(tag)?;
                    self.buffer.write_str("\n")?;

                    self.prefixes.push(!is_last);

                    for (i, child) in items.iter().skip(1).enumerate() {
                        let child_is_last = i == items.len() - 2;
                        self.format_child(child, child_is_last)?;
                    }

                    self.prefixes.pop();
                } else {
                    self.buffer.write_str("()\n")?;
                    self.prefixes.push(!is_last);
                }
            }
            SExpr::Atom(s) => {
                self.buffer.write_str(s)?;
                self.buffer.write_str("\n")?;
            }
        }
        Ok(())
    }

    fn write_tag(&mut self, tag: &SExpr) -> fmt::Result {
        match tag {
            SExpr::Atom(s) => self.buffer.write_str(s),
            SExpr::List(items) => {
                if let Some(inner_tag) = items.first() {
                    self.write_tag(inner_tag)
                } else {
                    self.buffer.write_str("()")
                }
            }
        }
    }

    fn write_prefix(&mut self) -> fmt::Result {
        for has_sibling in &self.prefixes {
            if *has_sibling {
                self.buffer.write_str("│   ")?;
            } else {
                self.buffer.write_str("    ")?;
            }
        }
        Ok(())
    }
}

// ── Tests ──────────────────────────────────────────────────────────────

#[cfg(test)]
mod tests {
    use super::*;
    use expect_test::{expect, Expect};

    #[track_caller]
    fn assert_tokens(input: &str, expected: &[Token]) {
        let tokens = tokenize(input).unwrap();
        assert_eq!(tokens, expected);
    }

    // ── Tokenizer: basic atoms ──────────────────────────────────────────

    #[test]
    fn tokenize_single_atom() {
        assert_tokens("hello", &[Token::Atom("hello".into())]);
    }

    #[test]
    fn tokenize_digits() {
        assert_tokens("42", &[Token::Atom("42".into())]);
    }

    #[test]
    fn tokenize_multiple_atoms() {
        assert_tokens(
            "hello world",
            &[Token::Atom("hello".into()), Token::Atom("world".into())],
        );
    }

    #[test]
    fn tokenize_mixed() {
        assert_tokens(
            "int 42",
            &[Token::Atom("int".into()), Token::Atom("42".into())],
        );
    }

    // ── Tokenizer: parentheses ──────────────────────────────────────────

    #[test]
    fn tokenize_lparen() {
        assert_tokens("(", &[Token::LParen]);
    }

    #[test]
    fn tokenize_rparen() {
        assert_tokens(")", &[Token::RParen]);
    }

    #[test]
    fn tokenize_paren_pair() {
        assert_tokens("()", &[Token::LParen, Token::RParen]);
    }

    #[test]
    fn tokenize_paren_with_content() {
        assert_tokens(
            "(int 42)",
            &[
                Token::LParen,
                Token::Atom("int".into()),
                Token::Atom("42".into()),
                Token::RParen,
            ],
        );
    }

    // ── Tokenizer: whitespace ───────────────────────────────────────────

    #[test]
    fn tokenize_whitespace_ignored() {
        assert_tokens("  hello  ", &[Token::Atom("hello".into())]);
    }

    #[test]
    fn tokenize_newlines_ignored() {
        assert_tokens(
            "hello\nworld",
            &[Token::Atom("hello".into()), Token::Atom("world".into())],
        );
    }

    #[test]
    fn tokenize_tabs_ignored() {
        assert_tokens(
            "hello\tworld",
            &[Token::Atom("hello".into()), Token::Atom("world".into())],
        );
    }

    #[test]
    fn tokenize_mixed_whitespace() {
        assert_tokens(
            "  ( a  b )  ",
            &[
                Token::LParen,
                Token::Atom("a".into()),
                Token::Atom("b".into()),
                Token::RParen,
            ],
        );
    }

    // ── Tokenizer: quoted strings ───────────────────────────────────────

    #[test]
    fn tokenize_quoted_string() {
        assert_tokens(r#""hello""#, &[Token::Atom("hello".into())]);
    }

    #[test]
    fn tokenize_quoted_string_with_spaces() {
        assert_tokens(r#""hello world""#, &[Token::Atom("hello world".into())]);
    }

    #[test]
    fn tokenize_quoted_string_with_escaped_quote() {
        assert_tokens(r#""say \"hi\"""#, &[Token::Atom(r#"say "hi""#.into())]);
    }

    #[test]
    fn tokenize_quoted_string_with_escaped_backslash() {
        assert_tokens(
            r#""path\\to\\file""#,
            &[Token::Atom(r"path\to\file".into())],
        );
    }

    #[test]
    fn tokenize_quoted_string_with_newline_escape() {
        assert_tokens(r#""line1\nline2""#, &[Token::Atom("line1\nline2".into())]);
    }

    #[test]
    fn tokenize_quoted_string_with_tab_escape() {
        assert_tokens(r#""col1\tcol2""#, &[Token::Atom("col1\tcol2".into())]);
    }

    #[test]
    fn tokenize_quoted_string_bare_parens_inside() {
        assert_tokens(r#""(not a list)""#, &[Token::Atom("(not a list)".into())]);
    }

    #[test]
    fn tokenize_atom_after_quoted_string() {
        assert_tokens(
            r#""hello" world"#,
            &[Token::Atom("hello".into()), Token::Atom("world".into())],
        );
    }

    // ── Tokenizer: unterminated string ──────────────────────────────────

    #[test]
    fn tokenize_unterminated_string() {
        let result = tokenize(r#""hello"#);
        assert_eq!(result, Err(ParseError::UnterminatedString));
    }

    // ── Tokenizer: empty input ──────────────────────────────────────────

    #[test]
    fn tokenize_empty() {
        assert_tokens("", &[]);
    }

    #[test]
    fn tokenize_only_whitespace() {
        assert_tokens("   \n\t  ", &[]);
    }

    // ── Tokenizer: complex expressions ──────────────────────────────────

    #[test]
    fn tokenize_nested_lists() {
        let tokens = tokenize("(a (b c) d)").unwrap();
        assert_eq!(
            tokens,
            vec![
                Token::LParen,
                Token::Atom("a".into()),
                Token::LParen,
                Token::Atom("b".into()),
                Token::Atom("c".into()),
                Token::RParen,
                Token::Atom("d".into()),
                Token::RParen,
            ]
        );
    }

    #[test]
    fn tokenize_deeply_nested() {
        let tokens = tokenize("((a))").unwrap();
        assert_eq!(
            tokens,
            vec![
                Token::LParen,
                Token::LParen,
                Token::Atom("a".into()),
                Token::RParen,
                Token::RParen,
            ]
        );
    }

    #[test]
    fn tokenize_multiple_parens_no_space() {
        let tokens = tokenize("(((a)))").unwrap();
        assert_eq!(
            tokens,
            vec![
                Token::LParen,
                Token::LParen,
                Token::LParen,
                Token::Atom("a".into()),
                Token::RParen,
                Token::RParen,
                Token::RParen,
            ]
        );
    }

    // ── SExpr parsing ───────────────────────────────────────────────────

    #[track_caller]
    fn assert_parse_one(input: &str, expected: SExpr) {
        let result = parse_one(input).unwrap();
        assert_eq!(result, expected);
    }

    #[test]
    fn parse_one_atom() {
        assert_parse_one("hello", SExpr::Atom("hello".into()));
    }

    #[test]
    fn parse_one_int_atom() {
        assert_parse_one("42", SExpr::Atom("42".into()));
    }

    #[test]
    fn parse_one_empty_list() {
        assert_parse_one("()", SExpr::List(vec![]));
    }

    #[test]
    fn parse_one_single_element_list() {
        assert_parse_one("(hello)", SExpr::List(vec![SExpr::Atom("hello".into())]));
    }

    #[test]
    fn parse_one_multi_element_list() {
        assert_parse_one(
            "(int 42)",
            SExpr::List(vec![SExpr::Atom("int".into()), SExpr::Atom("42".into())]),
        );
    }

    #[test]
    fn parse_one_nested_list() {
        assert_parse_one(
            "(a (b c))",
            SExpr::List(vec![
                SExpr::Atom("a".into()),
                SExpr::List(vec![SExpr::Atom("b".into()), SExpr::Atom("c".into())]),
            ]),
        );
    }

    #[test]
    fn parse_one_deeply_nested() {
        assert_parse_one(
            "((a (b)))",
            SExpr::List(vec![SExpr::List(vec![
                SExpr::Atom("a".into()),
                SExpr::List(vec![SExpr::Atom("b".into())]),
            ])]),
        );
    }

    // ── parse (multiple expressions) ────────────────────────────────────

    #[test]
    fn parse_single_expression() {
        let result = parse("(int 42)").unwrap();
        assert_eq!(
            result,
            vec![SExpr::List(vec![
                SExpr::Atom("int".into()),
                SExpr::Atom("42".into())
            ]),]
        );
    }

    #[test]
    fn parse_multiple_expressions() {
        let result = parse("(a) (b) (c)").unwrap();
        assert_eq!(
            result,
            vec![
                SExpr::List(vec![SExpr::Atom("a".into())]),
                SExpr::List(vec![SExpr::Atom("b".into())]),
                SExpr::List(vec![SExpr::Atom("c".into())]),
            ]
        );
    }

    #[test]
    fn parse_multiple_expressions_no_space() {
        let result = parse("(a)(b)(c)").unwrap();
        assert_eq!(
            result,
            vec![
                SExpr::List(vec![SExpr::Atom("a".into())]),
                SExpr::List(vec![SExpr::Atom("b".into())]),
                SExpr::List(vec![SExpr::Atom("c".into())]),
            ]
        );
    }

    // ── parse_one with trailing tokens ──────────────────────────────────

    #[test]
    fn parse_one_trailing_tokens() {
        let result = parse_one("(a) (b)");
        assert!(result.is_err());
        match result {
            Err(ParseError::TrailingTokens { .. }) => {}
            other => panic!("expected TrailingTokens, got {other:?}"),
        }
    }

    // ── Error cases ─────────────────────────────────────────────────────

    #[test]
    fn parse_one_unmatched_lparen() {
        let result = parse_one("(a");
        assert!(matches!(result, Err(ParseError::UnmatchedLParen)));
    }

    #[test]
    fn parse_one_unmatched_rparen() {
        let result = parse_one(")");
        assert!(matches!(result, Err(ParseError::UnmatchedRParen)));
    }

    #[test]
    fn parse_one_unterminated_string() {
        let result = parse_one(r#"(foo "bar"#);
        assert!(matches!(result, Err(ParseError::UnterminatedString)));
    }

    // ── SExpr helper methods ────────────────────────────────────────────

    #[test]
    fn tag_on_list() {
        let s = SExpr::List(vec![SExpr::Atom("int".into()), SExpr::Atom("42".into())]);
        assert_eq!(s.tag(), Some("int"));
    }

    #[test]
    fn tag_on_empty_list() {
        let s = SExpr::List(vec![]);
        assert_eq!(s.tag(), None);
    }

    #[test]
    fn tag_on_single_element_list() {
        let s = SExpr::List(vec![SExpr::Atom("hello".into())]);
        assert_eq!(s.tag(), Some("hello"));
    }

    #[test]
    fn tag_on_atom() {
        let s = SExpr::Atom("hello".into());
        assert_eq!(s.tag(), None);
    }

    #[test]
    fn args_on_list_with_args() {
        let s = SExpr::List(vec![
            SExpr::Atom("int".into()),
            SExpr::Atom("42".into()),
            SExpr::Atom("100".into()),
        ]);
        let args = s.args().unwrap();
        assert_eq!(args.len(), 2);
        assert_eq!(args[0], SExpr::Atom("42".into()));
        assert_eq!(args[1], SExpr::Atom("100".into()));
    }

    #[test]
    fn args_on_list_with_only_tag() {
        let s = SExpr::List(vec![SExpr::Atom("unit".into())]);
        let args = s.args().unwrap();
        assert!(args.is_empty());
    }

    #[test]
    fn args_on_empty_list() {
        let s = SExpr::List(vec![]);
        let args = s.args().unwrap();
        assert!(args.is_empty());
    }

    #[test]
    fn args_on_atom() {
        let s = SExpr::Atom("hello".into());
        assert_eq!(s.args(), None);
    }

    #[test]
    fn elements_on_list() {
        let s = SExpr::List(vec![SExpr::Atom("int".into()), SExpr::Atom("42".into())]);
        let elems = s.elements().unwrap();
        assert_eq!(elems.len(), 2);
        assert_eq!(elems[0], SExpr::Atom("int".into()));
        assert_eq!(elems[1], SExpr::Atom("42".into()));
    }

    #[test]
    fn elements_on_empty_list() {
        let s = SExpr::List(vec![]);
        let elems = s.elements().unwrap();
        assert!(elems.is_empty());
    }

    #[test]
    fn elements_on_atom() {
        let s = SExpr::Atom("hello".into());
        assert_eq!(s.elements(), None);
    }

    // ── Round-trip: tokenize → parse → SExpr structure ──────────────────

    fn roundtrip(expect: Expect) {
        let input = expect.data();
        let parsed = parse_one(input).unwrap();
        expect.assert_eq(&parsed.to_string())
    }

    #[test]
    fn roundtrip_simple() {
        roundtrip(expect!["(int 42)"]);
    }

    #[test]
    fn roundtrip_nested() {
        roundtrip(expect!["(let x (int 42) (var x))"]);
    }

    #[test]
    fn roundtrip_multiline() {
        roundtrip(expect![[r#"
            ((foo 1)
              (bar 2)
              (baz 3)
              (long_tag_to_wrap_to_new_line_012346789_012346789_0123456789 3))"#]]);
    }

    // ── ParseError Display ──────────────────────────────────────────────

    #[test]
    fn error_display_unexpected_token() {
        let err = ParseError::UnexpectedToken {
            expected: "atom",
            found: "list".into(),
        };
        assert_eq!(err.to_string(), "expected atom, found 'list'");
    }

    #[test]
    fn error_display_expected_tag_with_found() {
        let err = ParseError::ExpectedTag {
            expected: "int",
            found: Some("float".into()),
        };
        assert_eq!(err.to_string(), "expected tag 'int', found 'float'");
    }

    #[test]
    fn error_display_expected_tag_without_found() {
        let err = ParseError::ExpectedTag {
            expected: "int",
            found: None,
        };
        assert_eq!(err.to_string(), "expected tag 'int', found non-list");
    }

    #[test]
    fn error_display_expected_args() {
        let err = ParseError::ExpectedArgs {
            expected: 2,
            found: 0,
        };
        assert_eq!(err.to_string(), "expected 2 arguments, found 0");
    }

    #[test]
    fn error_display_parse_value() {
        let err = ParseError::ParseValue {
            type_name: "i64",
            reason: "'abc'".into(),
        };
        assert_eq!(err.to_string(), "failed to parse i64: 'abc'");
    }

    #[test]
    fn error_display_unmatched_lparen() {
        let err = ParseError::UnmatchedLParen;
        assert_eq!(err.to_string(), "unmatched '('");
    }

    #[test]
    fn error_display_unmatched_rparen() {
        let err = ParseError::UnmatchedRParen;
        assert_eq!(err.to_string(), "unmatched ')'");
    }

    #[test]
    fn error_display_unexpected_eof() {
        let err = ParseError::UnexpectedEOF;
        assert_eq!(err.to_string(), "unexpected end of input");
    }

    #[test]
    fn error_display_trailing_tokens() {
        let err = ParseError::TrailingTokens { remaining: vec![] };
        assert_eq!(err.to_string(), "trailing tokens after expression");
    }

    #[test]
    fn error_display_unterminated_string() {
        let err = ParseError::UnterminatedString;
        assert_eq!(err.to_string(), "unterminated string literal");
    }

    // ── Display tests ───────────────────────────────────────────────────

    #[test]
    fn display_atom() {
        let s = SExpr::Atom("hello".into());
        expect!["hello"].assert_eq(&s.to_string());
    }

    #[test]
    fn display_list_single_arg() {
        let s = SExpr::List(vec![SExpr::Atom("int".into()), SExpr::Atom("42".into())]);
        expect!["(int 42)"].assert_eq(&s.to_string());
    }

    #[test]
    fn display_nested_list() {
        let s = SExpr::List(vec![
            SExpr::Atom("abs".into()),
            SExpr::Atom("x".into()),
            SExpr::List(vec![SExpr::Atom("var".into()), SExpr::Atom("y".into())]),
        ]);
        expect!["(abs x (var y))"].assert_eq(&s.to_string());
    }

    #[test]
    fn display_long_list_wraps() {
        let long_list = SExpr::List(vec![
            SExpr::Atom("tag".into()),
            SExpr::Atom("this_is_a_very_long_identifier_name_that_contributes".into()),
            SExpr::Atom("to_the_overall_length_of_the_output_line".into()),
            SExpr::Atom("and_this_is_another_long_identifier".into()),
            SExpr::Atom("making_sure_we_exceed_eighty_characters".into()),
            SExpr::Atom("definitely_should_wrap_by_now".into()),
            SExpr::Atom("final_atom".into()),
        ]);
        expect![[r#"
            (tag
              this_is_a_very_long_identifier_name_that_contributes
              to_the_overall_length_of_the_output_line
              and_this_is_another_long_identifier
              making_sure_we_exceed_eighty_characters
              definitely_should_wrap_by_now
              final_atom)"#]]
        .assert_eq(&long_list.to_string());
    }

    #[test]
    fn display_deeply_nested_wraps() {
        let nested = SExpr::List(vec![
            SExpr::Atom("outer".into()),
            SExpr::List(vec![
                SExpr::Atom("middle".into()),
                SExpr::List(vec![
                    SExpr::Atom("inner".into()),
                    SExpr::List(vec![
                        SExpr::Atom("deep".into()),
                        SExpr::Atom(
                            "this_is_a_very_long_argument_that_helps_trigger_wrapping".into(),
                        ),
                    ]),
                ]),
            ]),
            SExpr::Atom("another_long_argument_to_make_this_even_wider".into()),
        ]);
        expect![[r#"
            (outer
              (middle
                (inner (deep this_is_a_very_long_argument_that_helps_trigger_wrapping)))
              another_long_argument_to_make_this_even_wider)"#]]
        .assert_eq(&nested.to_string());
    }

    #[test]
    fn display_long_list_roundtrip() {
        let long_list = SExpr::List(vec![
            SExpr::Atom("tag".into()),
            SExpr::Atom("first".into()),
            SExpr::Atom("second".into()),
            SExpr::Atom("third".into()),
            SExpr::Atom("fourth".into()),
            SExpr::Atom("fifth".into()),
            SExpr::Atom("sixth".into()),
            SExpr::Atom("seventh".into()),
        ]);
        let output = long_list.to_string();
        let parsed = parse(&output).unwrap();
        assert_eq!(parsed, vec![long_list]);
    }

    #[test]
    fn parse_roundtrip_simple() {
        let input = "(hello world)";
        let parsed = parse_one(input).unwrap();
        let output = parsed.to_string();
        expect!["(hello world)"].assert_eq(&output);
    }

    #[test]
    fn parse_roundtrip_nested() {
        let input = "(outer (inner (deep atom)))";
        let parsed = parse_one(input).unwrap();
        let output = parsed.to_string();
        expect!["(outer (inner (deep atom)))"].assert_eq(&output);
    }

    #[test]
    fn parse_roundtrip_3_args() {
        let input = "(tag arg1 arg2 arg3)";
        let parsed = parse_one(input).unwrap();
        let output = parsed.to_string();
        expect!["(tag arg1 arg2 arg3)"].assert_eq(&output);
    }

    #[test]
    fn parse_nested_list_args() {
        let input = "(module (import \"std::io\") (native main))";
        let parsed = parse_one(input).unwrap();
        assert!(matches!(parsed, SExpr::List(ref items) if items.len() == 3));
        let args = parsed.args().unwrap();
        assert_eq!(args.len(), 2);
    }

    #[test]
    fn parse_wrapped_items() {
        let input = "(module ((import \"std::io\") (native main)))";
        let parsed = parse_one(input).unwrap();
        assert!(matches!(parsed, SExpr::List(ref items) if items.len() == 2));
        let args = parsed.args().unwrap();
        assert_eq!(args.len(), 1);
        match &args[0] {
            SExpr::List(inner) => assert_eq!(inner.len(), 2),
            _ => panic!("expected nested list"),
        }
    }

    // ── Lambda Calculus AST ─────────────────────────────────────────────

    /// Minimal lambda calculus AST for testing ToSExpr / FromSExpr.
    ///
    /// S-Expr format:
    ///   (var x)           → Lambda::Var("x")
    ///   (abs x body)      → Lambda::Abs("x", body)
    ///   (app fun arg)     → Lambda::App(fun, arg)
    #[derive(Debug, Clone, PartialEq)]
    enum Lambda {
        Var(String),
        Abs(String, Box<Lambda>),
        App(Box<Lambda>, Box<Lambda>),
    }

    impl ToSExpr<()> for Lambda {
        fn to_sexpr(&self, _config: &()) -> SExpr {
            match self {
                Lambda::Var(name) => {
                    SExpr::List(vec![SExpr::Atom("var".into()), SExpr::Atom(name.clone())])
                }
                Lambda::Abs(param, body) => SExpr::List(vec![
                    SExpr::Atom("abs".into()),
                    SExpr::Atom(param.clone()),
                    body.to_sexpr(&()),
                ]),
                Lambda::App(fun, arg) => SExpr::List(vec![
                    SExpr::Atom("app".into()),
                    fun.to_sexpr(&()),
                    arg.to_sexpr(&()),
                ]),
            }
        }
    }

    impl FromSExpr<()> for Lambda {
        fn from_sexp(s: &SExpr, _ctx: &mut ()) -> Result<Self, ParseError> {
            match s.tag() {
                Some("var") => {
                    let [arg] = expect_n("var", s.args())?;
                    match arg {
                        SExpr::Atom(name) => Ok(Lambda::Var(name.clone())),
                        _ => Err(ParseError::ExpectedTag {
                            expected: "var name",
                            found: Some("atom".into()),
                        }),
                    }
                }
                Some("abs") => {
                    let [param, body] = expect_n("abs", s.args())?;
                    let param = match param {
                        SExpr::Atom(name) => name.clone(),
                        _ => {
                            return Err(ParseError::ExpectedTag {
                                expected: "param name",
                                found: Some("atom".into()),
                            });
                        }
                    };
                    let body = Lambda::from_sexp(body, &mut ())?;
                    Ok(Lambda::Abs(param, Box::new(body)))
                }
                Some("app") => {
                    let [fun, arg] = expect_n("app", s.args())?;
                    let fun = Lambda::from_sexp(fun, &mut ())?;
                    let arg = Lambda::from_sexp(arg, &mut ())?;
                    Ok(Lambda::App(Box::new(fun), Box::new(arg)))
                }
                other => Err(ParseError::ExpectedTag {
                    expected: "lambda node",
                    found: other.map(|s| s.to_string()),
                }),
            }
        }
    }

    // ── ToSExpr tests ───────────────────────────────────────────────────

    #[test]
    fn to_sexpr_var() {
        let lambda = Lambda::Var("x".into());
        let s = lambda.to_sexpr(&());
        assert_eq!(
            s,
            SExpr::List(vec![SExpr::Atom("var".into()), SExpr::Atom("x".into()),])
        );
    }

    #[test]
    fn to_sexpr_abs() {
        let lambda = Lambda::Abs("x".into(), Box::new(Lambda::Var("y".into())));
        let s = lambda.to_sexpr(&());
        assert_eq!(
            s,
            SExpr::List(vec![
                SExpr::Atom("abs".into()),
                SExpr::Atom("x".into()),
                SExpr::List(vec![SExpr::Atom("var".into()), SExpr::Atom("y".into()),]),
            ])
        );
    }

    #[test]
    fn to_sexpr_app() {
        let lambda = Lambda::App(
            Box::new(Lambda::Var("f".into())),
            Box::new(Lambda::Var("x".into())),
        );
        let s = lambda.to_sexpr(&());
        assert_eq!(
            s,
            SExpr::List(vec![
                SExpr::Atom("app".into()),
                SExpr::List(vec![SExpr::Atom("var".into()), SExpr::Atom("f".into()),]),
                SExpr::List(vec![SExpr::Atom("var".into()), SExpr::Atom("x".into()),]),
            ])
        );
    }

    // ── FromSExpr tests ─────────────────────────────────────────────────

    #[test]
    fn from_sexp_var() {
        let s = SExpr::List(vec![SExpr::Atom("var".into()), SExpr::Atom("x".into())]);
        let lambda = Lambda::from_sexp(&s, &mut ()).unwrap();
        assert_eq!(lambda, Lambda::Var("x".into()));
    }

    #[test]
    fn from_sexp_abs() {
        let s = SExpr::List(vec![
            SExpr::Atom("abs".into()),
            SExpr::Atom("x".into()),
            SExpr::List(vec![SExpr::Atom("var".into()), SExpr::Atom("y".into())]),
        ]);
        let lambda = Lambda::from_sexp(&s, &mut ()).unwrap();
        assert_eq!(
            lambda,
            Lambda::Abs("x".into(), Box::new(Lambda::Var("y".into())))
        );
    }

    #[test]
    fn from_sexp_app() {
        let s = SExpr::List(vec![
            SExpr::Atom("app".into()),
            SExpr::List(vec![SExpr::Atom("var".into()), SExpr::Atom("f".into())]),
            SExpr::List(vec![SExpr::Atom("var".into()), SExpr::Atom("x".into())]),
        ]);
        let lambda = Lambda::from_sexp(&s, &mut ()).unwrap();
        assert_eq!(
            lambda,
            Lambda::App(
                Box::new(Lambda::Var("f".into())),
                Box::new(Lambda::Var("x".into())),
            )
        );
    }

    #[test]
    fn from_sexp_bad_tag() {
        let s = SExpr::List(vec![SExpr::Atom("foo".into()), SExpr::Atom("bar".into())]);
        let result = Lambda::from_sexp(&s, &mut ());
        assert!(matches!(result, Err(ParseError::ExpectedTag { .. })));
    }

    #[test]
    fn from_sexp_bad_args() {
        let s = SExpr::List(vec![SExpr::Atom("var".into())]);
        let result = Lambda::from_sexp(&s, &mut ());
        assert!(matches!(result, Err(ParseError::ExpectedArgs { .. })));
    }

    // ── Round-trip tests ────────────────────────────────────────────────

    fn roundtrip_lambda<T>(expected: Expect)
    where
        T: ToSExpr<()> + FromSExpr<()>,
    {
        let parsed = T::from_sexp(&parse_one(expected.data()).unwrap(), &mut ()).unwrap();
        expected.assert_eq(&parsed.to_sexpr(&()).to_string());
    }

    #[test]
    fn roundtrip_lambda_var() {
        roundtrip_lambda::<Lambda>(expect!["(var x)"]);
    }

    #[test]
    fn roundtrip_lambda_abs() {
        roundtrip_lambda::<Lambda>(expect!["(abs x (var y))"]);
    }

    #[test]
    fn roundtrip_lambda_nested() {
        roundtrip_lambda::<Lambda>(expect!["(abs x (app (var x) (var y)))"]);
    }

    // ── Display tests: Lambda ───────────────────────────────────────────

    #[test]
    fn display_lambda_var() {
        let lambda = Lambda::Var("x".into());
        expect!["(var x)"].assert_eq(&lambda.to_sexpr(&()).to_string());
    }

    #[test]
    fn display_lambda_abs() {
        let lambda = Lambda::Abs("x".into(), Box::new(Lambda::Var("y".into())));
        expect!["(abs x (var y))"].assert_eq(&lambda.to_sexpr(&()).to_string());
    }

    #[test]
    fn display_lambda_app() {
        let lambda = Lambda::App(
            Box::new(Lambda::Var("f".into())),
            Box::new(Lambda::Var("x".into())),
        );
        expect!["(app (var f) (var x))"].assert_eq(&lambda.to_sexpr(&()).to_string());
    }

    #[test]
    fn display_lambda_nested() {
        let lambda = Lambda::Abs(
            "x".into(),
            Box::new(Lambda::App(
                Box::new(Lambda::Var("x".into())),
                Box::new(Lambda::Var("y".into())),
            )),
        );
        expect!["(abs x (app (var x) (var y)))"].assert_eq(&lambda.to_sexpr(&()).to_string());
    }

    #[test]
    fn display_lambda_long_wraps() {
        let lambda = Lambda::Abs(
            "very_long_parameter_name".into(),
            Box::new(Lambda::Abs(
                "another_long_parameter".into(),
                Box::new(Lambda::Abs(
                    "yet_another_param".into(),
                    Box::new(Lambda::App(
                        Box::new(Lambda::App(
                            Box::new(Lambda::Var("very_long_parameter_name".into())),
                            Box::new(Lambda::Var("another_long_parameter".into())),
                        )),
                        Box::new(Lambda::App(
                            Box::new(Lambda::Var("yet_another_param".into())),
                            Box::new(Lambda::Var("x".into())),
                        )),
                    )),
                )),
            )),
        );
        expect![[r#"
            (abs
              very_long_parameter_name
              (abs
                another_long_parameter
                (abs
                  yet_another_param
                  (app
                    (app (var very_long_parameter_name) (var another_long_parameter))
                    (app (var yet_another_param) (var x))))))"#]]
        .assert_eq(&lambda.to_sexpr(&()).to_string());
    }

    #[test]
    fn display_lambda_roundtrip() {
        let lambda = Lambda::Abs(
            "x".into(),
            Box::new(Lambda::App(
                Box::new(Lambda::Var("f".into())),
                Box::new(Lambda::Var("g".into())),
            )),
        );
        let output = lambda.to_sexpr(&()).to_string();
        let parsed = Lambda::from_sexp(&parse_one(&output).unwrap(), &mut ()).unwrap();
        assert_eq!(lambda, parsed);
    }

    // ── Box formatting tests ────────────────────────────────────────────

    #[test]
    fn box_format_simple() {
        let s = SExpr::List(vec![
            SExpr::Atom("let".into()),
            SExpr::Atom("x".into()),
            SExpr::List(vec![SExpr::Atom("int".into()), SExpr::Atom("42".into())]),
            SExpr::List(vec![SExpr::Atom("var".into()), SExpr::Atom("x".into())]),
        ]);

        let mut output = String::new();
        format_box(&mut output, &s).unwrap();

        expect![[r#"
            let
            ├── x
            ├── int
            │   └── 42
            └── var
                └── x
            "#]]
        .assert_eq(&output);
    }

    #[test]
    fn box_format_empty_list() {
        let s = SExpr::List(vec![SExpr::Atom("empty".into()), SExpr::List(vec![])]);

        let mut output = String::new();
        format_box(&mut output, &s).unwrap();

        expect![[r#"
            empty
            └── ()
            "#]]
        .assert_eq(&output);
    }

    #[test]
    fn box_format_atom_only() {
        let s = SExpr::Atom("hello".into());

        let mut output = String::new();
        format_box(&mut output, &s).unwrap();

        expect!["hello\n"].assert_eq(&output);
    }

    #[test]
    fn box_format_module() {
        let s = SExpr::List(vec![
            SExpr::Atom("module".into()),
            SExpr::List(vec![
                SExpr::Atom("import".into()),
                SExpr::Atom("std::io".into()),
            ]),
            SExpr::List(vec![
                SExpr::Atom("native".into()),
                SExpr::List(vec![
                    SExpr::Atom("symbol".into()),
                    SExpr::Atom("".into()),
                    SExpr::Atom("main".into()),
                ]),
                SExpr::List(vec![
                    SExpr::Atom("function".into()),
                    SExpr::Atom("_".into()),
                    SExpr::List(vec![SExpr::Atom("int".into()), SExpr::Atom("0".into())]),
                ]),
                SExpr::List(vec![
                    SExpr::Atom("type".into()),
                    SExpr::Atom("_".into()),
                    SExpr::List(vec![SExpr::Atom("unit".into())]),
                ]),
            ]),
        ]);

        let mut output = String::new();
        format_box(&mut output, &s).unwrap();

        expect![[r#"
            module
            ├── import
            │   └── std::io
            └── native
                ├── symbol
                │   ├── 
                │   └── main
                ├── function
                │   ├── _
                │   └── int
                │       └── 0
                └── type
                    ├── _
                    └── unit
            "#]]
        .assert_eq(&output);
    }
}