blr-lang 0.1.0

//! Crust s-expr formatter and parser.
//!
//! Implements `ToSExpr` and `FromSExpr` for crust layer types.

use std::collections::{BTreeMap, BTreeSet};

use super::NodeId;
use crate::compiler::sexpr::{FromSExpr, ParseError, SExpr, ToSExpr, expect_n};

/// Supplies fresh NodeId values during parsing.
#[derive(Default)]
struct NodeIdSupply {
    next_node_id: u32,
}

impl NodeIdSupply {
    /// Allocate a fresh NodeId.
    pub fn alloc(&mut self) -> NodeId {
        let id = NodeId(self.next_node_id);
        self.next_node_id += 1;
        id
    }
}

/// Configuration that controls what details are included in s-expr output.
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub struct SExprConfig {
    /// Include NodeId in output (e.g., `(unt 0)` vs `(unt)`).
    pub node_ids: bool,
    /// Include type annotations in typed variables (e.g., `(var 0 int)` vs `(var 0)`).
    pub types: bool,
    /// How much metadata to include (e.g., unbound type/row vars, evidence).
    pub detail: SerializationDetail,
}

/// Controls the verbosity of serialization.
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub enum SerializationDetail {
    /// Basic fields only (type, no metadata).
    Minimal,
    /// All fields (unbound vars, evidence, external_type, etc.).
    Full,
}

impl Default for SExprConfig {
    fn default() -> Self {
        Self {
            node_ids: false,
            types: false,
            detail: SerializationDetail::Minimal,
        }
    }
}

use super::{
    ClosedRow, Evidence, Expr, ExternalItem, ExternalType, Item, ItemId, ItemWrapper, Module,
    NativeItem, Row, RowVar, Symbol, Type, TypeScheme, TypeVar, TypedItem, TypedModule,
    TypedNativeItem, TypedVar, Var, external_type,
};
use external_type::FunctionType;

// ── ToSExpr Implementations ────────────────────────────────────────────

impl ToSExpr<SExprConfig> for Symbol {
    fn to_sexpr(&self, _config: &SExprConfig) -> SExpr {
        SExpr::List(vec![
            SExpr::Atom("symbol".into()),
            SExpr::Atom(self.module.clone()),
            SExpr::Atom(self.field.clone()),
        ])
    }
}

// ── FromSExpr Implementations ──────────────────────────────────────────

impl FromSExpr<NodeIdSupply> for Symbol {
    fn from_sexp(s: &SExpr, _ctx: &mut NodeIdSupply) -> Result<Self, ParseError> {
        let args: &[SExpr; 2] = expect_n("symbol", s.args())?;
        let module = match &args[0] {
            SExpr::Atom(s) => s.clone(),
            _ => {
                return Err(ParseError::ExpectedTag {
                    expected: "symbol module",
                    found: args[0].tag().map(|s| s.to_string()),
                });
            }
        };
        let field = match &args[1] {
            SExpr::Atom(s) => s.clone(),
            _ => {
                return Err(ParseError::ExpectedTag {
                    expected: "symbol field",
                    found: args[1].tag().map(|s| s.to_string()),
                });
            }
        };
        Ok(Symbol { module, field })
    }
}

// ── TypedVar ───────────────────────────────────────────────────────────

impl ToSExpr<SExprConfig> for TypedVar {
    fn to_sexpr(&self, config: &SExprConfig) -> SExpr {
        if config.types {
            SExpr::List(vec![
                SExpr::Atom("var".into()),
                SExpr::Atom(self.0.0.to_string()),
                self.1.to_sexpr(config),
            ])
        } else {
            SExpr::List(vec![
                SExpr::Atom("var".into()),
                SExpr::Atom(self.0.0.to_string()),
            ])
        }
    }
}

// ── ItemId ─────────────────────────────────────────────────────────────

impl ToSExpr<SExprConfig> for ItemId {
    fn to_sexpr(&self, _config: &SExprConfig) -> SExpr {
        SExpr::List(vec![
            SExpr::Atom("id".into()),
            SExpr::Atom(self.0.to_string()),
        ])
    }
}

impl FromSExpr<NodeIdSupply> for ItemId {
    fn from_sexp(s: &SExpr, _ctx: &mut NodeIdSupply) -> Result<Self, ParseError> {
        let args: &[SExpr; 1] = expect_n("id", s.args())?;
        let n = match &args[0] {
            SExpr::Atom(s) => s.parse::<usize>().map_err(|_| ParseError::ParseValue {
                type_name: "usize",
                reason: s.clone(),
            })?,
            _ => {
                return Err(ParseError::ExpectedTag {
                    expected: "id value",
                    found: args[0].tag().map(|s| s.to_string()),
                });
            }
        };
        Ok(ItemId(n))
    }
}

// ── Type ───────────────────────────────────────────────────────────────

impl ToSExpr<SExprConfig> for Type {
    fn to_sexpr(&self, _config: &SExprConfig) -> SExpr {
        match self {
            Type::Unit => SExpr::List(vec![SExpr::Atom("unit".into())]),
            Type::Int => SExpr::List(vec![SExpr::Atom("int".into())]),
            Type::Float => SExpr::List(vec![SExpr::Atom("float".into())]),
            Type::String => SExpr::List(vec![SExpr::Atom("string".into())]),
            Type::DataFrame => SExpr::List(vec![SExpr::Atom("dataframe".into())]),
            Type::Unifier(v) => SExpr::List(vec![
                SExpr::Atom("uvar".into()),
                SExpr::Atom(v.id.to_string()),
            ]),
            Type::Var(v) => SExpr::List(vec![
                SExpr::Atom("tvar".into()),
                SExpr::Atom(v.0.to_string()),
            ]),
            Type::Abs(arg, ret) => SExpr::List(vec![
                SExpr::Atom("fn".into()),
                arg.to_sexpr(&SExprConfig::default()),
                ret.to_sexpr(&SExprConfig::default()),
            ]),
            Type::Prod(row) => SExpr::List(vec![
                SExpr::Atom("prd".into()),
                row.to_sexpr(&SExprConfig::default()),
            ]),
            Type::Sum(row) => SExpr::List(vec![
                SExpr::Atom("sum".into()),
                row.to_sexpr(&SExprConfig::default()),
            ]),
            Type::Label(lbl, typ) => SExpr::List(vec![
                SExpr::Atom("lbl".into()),
                SExpr::Atom(lbl.clone()),
                typ.to_sexpr(&SExprConfig::default()),
            ]),
        }
    }
}

impl FromSExpr<NodeIdSupply> for Type {
    fn from_sexp(s: &SExpr, _ctx: &mut NodeIdSupply) -> Result<Self, ParseError> {
        match s.tag() {
            Some("unit") => Ok(Type::Unit),
            Some("int") => Ok(Type::Int),
            Some("float") => Ok(Type::Float),
            Some("string") => Ok(Type::String),
            Some("dataframe") => Ok(Type::DataFrame),
            Some("uvar") => {
                let args: &[SExpr; 1] = expect_n("uvar", s.args())?;
                let id = match &args[0] {
                    SExpr::Atom(s) => s.parse::<u32>().map_err(|_| ParseError::ParseValue {
                        type_name: "u32",
                        reason: s.clone(),
                    })?,
                    _ => {
                        return Err(ParseError::ExpectedTag {
                            expected: "uvar id",
                            found: args[0].tag().map(|s| s.to_string()),
                        });
                    }
                };
                use super::ty::TypeUniVar;
                Ok(Type::Unifier(TypeUniVar { id }))
            }
            Some("tvar") => {
                let args: &[SExpr; 1] = expect_n("tvar", s.args())?;
                let id = match &args[0] {
                    SExpr::Atom(s) => s.parse::<u32>().map_err(|_| ParseError::ParseValue {
                        type_name: "u32",
                        reason: s.clone(),
                    })?,
                    _ => {
                        return Err(ParseError::ExpectedTag {
                            expected: "tvar id",
                            found: args[0].tag().map(|s| s.to_string()),
                        });
                    }
                };
                Ok(Type::Var(TypeVar(id)))
            }
            Some("fn") => {
                let args: &[SExpr; 2] = expect_n("fn", s.args())?;
                let arg = Type::from_sexp(&args[0], _ctx)?;
                let ret = Type::from_sexp(&args[1], _ctx)?;
                Ok(Type::Abs(Box::new(arg), Box::new(ret)))
            }
            Some("prd") => {
                let args: &[SExpr; 1] = expect_n("prd", s.args())?;
                let row = Row::from_sexp(&args[0], _ctx)?;
                Ok(Type::Prod(row))
            }
            Some("sum") => {
                let args: &[SExpr; 1] = expect_n("sum", s.args())?;
                let row = Row::from_sexp(&args[0], _ctx)?;
                Ok(Type::Sum(row))
            }
            Some("lbl") => {
                let args: &[SExpr; 2] = expect_n("lbl", s.args())?;
                let lbl = match &args[0] {
                    SExpr::Atom(s) => s.clone(),
                    _ => {
                        return Err(ParseError::ExpectedTag {
                            expected: "lbl label",
                            found: args[0].tag().map(|s| s.to_string()),
                        });
                    }
                };
                let typ = Type::from_sexp(&args[1], _ctx)?;
                Ok(Type::Label(lbl, Box::new(typ)))
            }
            _ => Err(ParseError::ExpectedTag {
                expected: "type tag",
                found: s.tag().map(|s| s.to_string()),
            }),
        }
    }
}

// ── Row ────────────────────────────────────────────────────────────────

impl ToSExpr<SExprConfig> for Row {
    fn to_sexpr(&self, _config: &SExprConfig) -> SExpr {
        match self {
            Row::Unifier(v) => SExpr::List(vec![
                SExpr::Atom("rvar".into()),
                SExpr::Atom(v.id.to_string()),
            ]),
            Row::Open(v) => SExpr::List(vec![
                SExpr::Atom("opn".into()),
                SExpr::Atom(v.0.to_string()),
            ]),
            Row::Closed(row) => row.to_sexpr(_config),
        }
    }
}

impl FromSExpr<NodeIdSupply> for Row {
    fn from_sexp(s: &SExpr, _ctx: &mut NodeIdSupply) -> Result<Self, ParseError> {
        match s.tag() {
            Some("rvar") => {
                let args: &[SExpr; 1] = expect_n("rvar", s.args())?;
                let id = match &args[0] {
                    SExpr::Atom(s) => s.parse::<u32>().map_err(|_| ParseError::ParseValue {
                        type_name: "u32",
                        reason: s.clone(),
                    })?,
                    _ => {
                        return Err(ParseError::ExpectedTag {
                            expected: "rvar id",
                            found: args[0].tag().map(|s| s.to_string()),
                        });
                    }
                };
                use super::ty::RowUniVar;
                Ok(Row::Unifier(RowUniVar { id }))
            }
            Some("opn") => {
                let args: &[SExpr; 1] = expect_n("opn", s.args())?;
                let id = match &args[0] {
                    SExpr::Atom(s) => s.parse::<u32>().map_err(|_| ParseError::ParseValue {
                        type_name: "u32",
                        reason: s.clone(),
                    })?,
                    _ => {
                        return Err(ParseError::ExpectedTag {
                            expected: "opn id",
                            found: args[0].tag().map(|s| s.to_string()),
                        });
                    }
                };
                Ok(Row::Open(RowVar(id)))
            }
            Some("cld") => ClosedRow::from_sexp(s, _ctx).map(Row::Closed),
            _ => Err(ParseError::ExpectedTag {
                expected: "row tag",
                found: s.tag().map(|s| s.to_string()),
            }),
        }
    }
}

// ── ClosedRow ──────────────────────────────────────────────────────────

impl ToSExpr<SExprConfig> for ClosedRow {
    fn to_sexpr(&self, _config: &SExprConfig) -> SExpr {
        let mut elements = vec![SExpr::Atom("cld".into())];
        for (field, value) in self.fields.iter().zip(self.values.iter()) {
            elements.push(SExpr::Atom(field.clone()));
            elements.push(value.to_sexpr(_config));
        }
        SExpr::List(elements)
    }
}

impl FromSExpr<NodeIdSupply> for ClosedRow {
    fn from_sexp(s: &SExpr, _ctx: &mut NodeIdSupply) -> Result<Self, ParseError> {
        let args = s.args().ok_or(ParseError::ExpectedTag {
            expected: "cld",
            found: None,
        })?;
        if args.len() % 2 != 0 {
            return Err(ParseError::ParseValue {
                type_name: "ClosedRow",
                reason: format!(
                    "expected even number of fields and types, found {}",
                    args.len()
                ),
            });
        }
        let mut fields = Vec::new();
        let mut values = Vec::new();
        let mut iter = args.iter();
        while let Some(field) = iter.next() {
            let value = iter.next().ok_or(ParseError::ParseValue {
                type_name: "ClosedRow",
                reason: "expected even number of fields and types".into(),
            })?;
            let field_str = match field {
                SExpr::Atom(s) => s.clone(),
                _ => {
                    return Err(ParseError::ExpectedTag {
                        expected: "field name",
                        found: field.tag().map(|s| s.to_string()),
                    });
                }
            };
            let typ = Type::from_sexp(value, _ctx)?;
            fields.push(field_str);
            values.push(typ);
        }
        Ok(ClosedRow { fields, values })
    }
}

// ── Evidence ───────────────────────────────────────────────────────────

impl ToSExpr<SExprConfig> for Evidence {
    fn to_sexpr(&self, _config: &SExprConfig) -> SExpr {
        match self {
            Evidence::RowEquation { left, right, goal } => SExpr::List(vec![
                SExpr::Atom("equation".into()),
                left.to_sexpr(&SExprConfig::default()),
                right.to_sexpr(&SExprConfig::default()),
                goal.to_sexpr(&SExprConfig::default()),
            ]),
        }
    }
}

impl FromSExpr<NodeIdSupply> for Evidence {
    fn from_sexp(s: &SExpr, _ctx: &mut NodeIdSupply) -> Result<Self, ParseError> {
        let args: &[SExpr; 3] = expect_n("equation", s.args())?;
        let left = Row::from_sexp(&args[0], _ctx)?;
        let right = Row::from_sexp(&args[1], _ctx)?;
        let goal = Row::from_sexp(&args[2], _ctx)?;
        Ok(Evidence::RowEquation { left, right, goal })
    }
}

// ── TypeScheme ─────────────────────────────────────────────────────────

impl ToSExpr<SExprConfig> for TypeScheme {
    fn to_sexpr(&self, config: &SExprConfig) -> SExpr {
        let mut elements = vec![SExpr::Atom("tsh".into()), self.typ.to_sexpr(config)];
        match config.detail {
            SerializationDetail::Minimal | SerializationDetail::Full => {
                elements.push(SExpr::Atom("row".into()));
                for row_var in &self.unbound_rows {
                    elements.push(SExpr::List(vec![
                        SExpr::Atom("rvar".into()),
                        SExpr::Atom(row_var.0.to_string()),
                    ]));
                }
                elements.push(SExpr::Atom("typ".into()));
                for ty_var in &self.unbound_tys {
                    elements.push(SExpr::List(vec![
                        SExpr::Atom("tvar".into()),
                        SExpr::Atom(ty_var.0.to_string()),
                    ]));
                }
                for evidence in &self.evidence {
                    elements.push(evidence.to_sexpr(config));
                }
            }
        }
        SExpr::List(elements)
    }
}

impl FromSExpr<NodeIdSupply> for TypeScheme {
    fn from_sexp(s: &SExpr, _ctx: &mut NodeIdSupply) -> Result<Self, ParseError> {
        let args = s.args().ok_or(ParseError::ExpectedTag {
            expected: "tsh",
            found: None,
        })?;
        if args.is_empty() {
            return Err(ParseError::ExpectedArgs {
                expected: 1,
                found: 0,
            });
        }
        let typ = Type::from_sexp(&args[0], _ctx)?;
        let mut unbound_rows = BTreeSet::new();
        let mut unbound_tys = BTreeSet::new();
        let mut evidence = Vec::new();
        let mut i = 1;
        while i < args.len() {
            match (&args[i], args[i].tag()) {
                (SExpr::Atom(s), _) if *s == "row" => {
                    i += 1;
                    while i < args.len() {
                        if let Some(list) = args[i].elements()
                            && let Some(SExpr::Atom(s)) = list.first()
                            && s == "rvar"
                            && list.len() >= 2
                            && let SExpr::Atom(ref id_str) = list[1]
                        {
                            // rvar format: (rvar <id>), elements = [rvar, id]
                            let row_var = RowVar(id_str.parse::<u32>().map_err(|_| {
                                ParseError::ParseValue {
                                    type_name: "u32",
                                    reason: id_str.clone(),
                                }
                            })?);
                            unbound_rows.insert(row_var);
                            i += 1;
                        } else {
                            break;
                        }
                    }
                }
                (SExpr::Atom(s), _) if *s == "typ" => {
                    i += 1;
                    while i < args.len() {
                        if let Some(list) = args[i].elements()
                            && let Some(SExpr::Atom(s)) = list.first()
                            && s == "tvar"
                            && list.len() >= 2
                            && let SExpr::Atom(ref id_str) = list[1]
                        {
                            // tvar format: (tvar <id>), elements = [tvar, id]
                            let ty_var = TypeVar(id_str.parse::<u32>().map_err(|_| {
                                ParseError::ParseValue {
                                    type_name: "u32",
                                    reason: id_str.clone(),
                                }
                            })?);
                            unbound_tys.insert(ty_var);
                            i += 1;
                        } else {
                            break;
                        }
                    }
                }
                (_, Some("equation")) => {
                    evidence.push(Evidence::from_sexp(&args[i], _ctx)?);
                    i += 1;
                }
                _ => {
                    i += 1;
                }
            }
        }
        Ok(TypeScheme {
            unbound_rows,
            unbound_tys,
            evidence,
            typ,
        })
    }
}

// ── ExternalType (for ExternalItem.external_type) ──────────────────────

impl ToSExpr<SExprConfig> for ExternalType {
    fn to_sexpr(&self, _config: &SExprConfig) -> SExpr {
        match self {
            ExternalType::Unit => SExpr::List(vec![SExpr::Atom("unit".into())]),
            ExternalType::Int => SExpr::List(vec![SExpr::Atom("int".into())]),
            ExternalType::Float => SExpr::List(vec![SExpr::Atom("float".into())]),
            ExternalType::String => SExpr::List(vec![SExpr::Atom("string".into())]),
            ExternalType::Resource(name) => SExpr::List(vec![
                SExpr::Atom("resource".into()),
                SExpr::Atom(name.clone()),
            ]),
            ExternalType::Fun(ft) => ft.to_sexpr(_config),
            ExternalType::Record(name, fields) => {
                let mut elements = vec![SExpr::Atom("record".into()), SExpr::Atom(name.clone())];
                for (field_name, field_type) in fields {
                    elements.push(SExpr::Atom(field_name.clone()));
                    elements.push(field_type.to_sexpr(_config));
                }
                SExpr::List(elements)
            }
        }
    }
}

impl ToSExpr<SExprConfig> for FunctionType {
    fn to_sexpr(&self, _config: &SExprConfig) -> SExpr {
        let mut elements = vec![SExpr::Atom("fn".into())];
        if self.parameter_names.is_empty() {
            elements.push(SExpr::List(vec![]));
        } else {
            let mut param_list = Vec::new();
            for (name, typ) in self.parameter_names.iter().zip(self.parameter_typs.iter()) {
                param_list.push(SExpr::List(vec![
                    SExpr::Atom(name.clone()),
                    ExternalType::to_sexpr(typ, _config),
                ]));
            }
            elements.push(SExpr::List(param_list));
        }
        elements.push(ExternalType::to_sexpr(self.ret.as_ref(), _config));
        SExpr::List(elements)
    }
}

// ── ExternalItem ───────────────────────────────────────────────────────

impl ToSExpr<SExprConfig> for ExternalItem {
    fn to_sexpr(&self, config: &SExprConfig) -> SExpr {
        SExpr::List(vec![
            SExpr::Atom("pub".into()),
            SExpr::Atom("ext".into()),
            SExpr::Atom(self.symbol.module.clone()),
            SExpr::Atom(self.symbol.field.clone()),
            self.scheme.to_sexpr(config),
            self.external_type.to_sexpr(config),
        ])
    }
}

impl FromSExpr<NodeIdSupply> for ExternalItem {
    fn from_sexp(s: &SExpr, _ctx: &mut NodeIdSupply) -> Result<Self, ParseError> {
        let args: &[SExpr; 5] = expect_n("pub", s.args())?;
        if let SExpr::Atom(tag) = &args[0] {
            if tag != "ext" {
                return Err(ParseError::ExpectedTag {
                    expected: "ext",
                    found: Some(tag.clone()),
                });
            }
        } else {
            return Err(ParseError::ExpectedTag {
                expected: "ext",
                found: args[0].tag().map(|s| s.to_string()),
            });
        }
        let module = match &args[1] {
            SExpr::Atom(s) => s.clone(),
            _ => {
                return Err(ParseError::ExpectedTag {
                    expected: "module",
                    found: args[1].tag().map(|s| s.to_string()),
                });
            }
        };
        let field = match &args[2] {
            SExpr::Atom(s) => s.clone(),
            _ => {
                return Err(ParseError::ExpectedTag {
                    expected: "field",
                    found: args[2].tag().map(|s| s.to_string()),
                });
            }
        };
        let scheme = TypeScheme::from_sexp(&args[3], _ctx)?;
        let external_type = FunctionType::from_sexp(&args[4], &mut ())?;
        Ok(ExternalItem {
            symbol: Symbol { module, field },
            scheme,
            external_type,
        })
    }
}

// ── NativeItem<Var> ────────────────────────────────────────────────────

impl ToSExpr<SExprConfig> for NativeItem<Var> {
    fn to_sexpr(&self, config: &SExprConfig) -> SExpr {
        SExpr::List(vec![
            SExpr::Atom("pub".into()),
            SExpr::Atom(self.symbol.field.clone()),
            self.abstraction.to_sexpr(config),
            self.typ.to_sexpr(config),
        ])
    }
}

impl FromSExpr<NodeIdSupply> for NativeItem<Var> {
    fn from_sexp(s: &SExpr, _ctx: &mut NodeIdSupply) -> Result<Self, ParseError> {
        let args: &[SExpr; 3] = expect_n("pub", s.args())?;
        let field = match &args[0] {
            SExpr::Atom(s) => s.clone(),
            _ => {
                return Err(ParseError::ExpectedTag {
                    expected: "field",
                    found: args[0].tag().map(|s| s.to_string()),
                });
            }
        };
        let abstraction = Expr::from_sexp(&args[1], _ctx)?;
        let typ = TypeScheme::from_sexp(&args[2], _ctx)?;
        Ok(NativeItem {
            symbol: Symbol {
                module: String::new(),
                field,
            },
            abstraction,
            typ,
        })
    }
}

// ── Item<Var> ──────────────────────────────────────────────────────────

impl ToSExpr<SExprConfig> for Item<Var> {
    fn to_sexpr(&self, config: &SExprConfig) -> SExpr {
        match self {
            Item::Native(item) => item.to_sexpr(config),
            Item::External(item) => item.to_sexpr(config),
        }
    }
}

impl FromSExpr<NodeIdSupply> for Item<Var> {
    fn from_sexp(s: &SExpr, _ctx: &mut NodeIdSupply) -> Result<Self, ParseError> {
        match s.tag() {
            Some("pub") => {
                let args = s.args().ok_or(ParseError::ExpectedTag {
                    expected: "pub",
                    found: None,
                })?;
                if args.is_empty() {
                    return Err(ParseError::ExpectedArgs {
                        expected: 1,
                        found: 0,
                    });
                }
                // Check if this is (pub ext ...) or (pub <field> ...)
                if let SExpr::Atom(first) = &args[0] {
                    if first == "ext" {
                        // Parse as ExternalItem: (pub ext <module> <field> <scheme> <ext_type>)
                        let all_args: &[SExpr; 5] = expect_n("pub", s.args())?;
                        let module = match &all_args[1] {
                            SExpr::Atom(s) => s.clone(),
                            _ => {
                                return Err(ParseError::ExpectedTag {
                                    expected: "module",
                                    found: all_args[1].tag().map(|s| s.to_string()),
                                });
                            }
                        };
                        let field = match &all_args[2] {
                            SExpr::Atom(s) => s.clone(),
                            _ => {
                                return Err(ParseError::ExpectedTag {
                                    expected: "field",
                                    found: all_args[2].tag().map(|s| s.to_string()),
                                });
                            }
                        };
                        let scheme = TypeScheme::from_sexp(&all_args[3], _ctx)?;
                        let external_type = FunctionType::from_sexp(&all_args[4], &mut ())?;
                        Ok(Item::External(ExternalItem {
                            symbol: Symbol { module, field },
                            scheme,
                            external_type,
                        }))
                    } else {
                        // Parse as NativeItem
                        NativeItem::from_sexp(s, _ctx).map(Item::Native)
                    }
                } else {
                    // Parse as NativeItem
                    NativeItem::from_sexp(s, _ctx).map(Item::Native)
                }
            }
            _ => Err(ParseError::ExpectedTag {
                expected: "pub",
                found: s.tag().map(|s| s.to_string()),
            }),
        }
    }
}

// ── Module<Var> ────────────────────────────────────────────────────────

impl ToSExpr<SExprConfig> for Module<Var> {
    fn to_sexpr(&self, config: &SExprConfig) -> SExpr {
        let mut elements = vec![SExpr::Atom("mod".into())];
        for item in self.items.values() {
            elements.push(item.to_sexpr(config));
        }
        SExpr::List(elements)
    }
}

impl FromSExpr<NodeIdSupply> for Module<Var> {
    fn from_sexp(s: &SExpr, _ctx: &mut NodeIdSupply) -> Result<Self, ParseError> {
        let args = s.args().ok_or(ParseError::ExpectedTag {
            expected: "mod",
            found: None,
        })?;
        let mut items = BTreeMap::new();
        for arg in args {
            let item = Item::from_sexp(arg, _ctx)?;
            let id = match &item {
                Item::Native(native) => {
                    // Use a simple hash of the symbol as the ItemId
                    let hash = native.symbol.field.len();
                    ItemId(hash)
                }
                Item::External(ext) => {
                    let hash = ext.symbol.field.len();
                    ItemId(hash)
                }
            };
            items.insert(id, item);
        }
        Ok(Module { items })
    }
}

impl ToSExpr<SExprConfig> for Expr<Var> {
    fn to_sexpr(&self, config: &SExprConfig) -> SExpr {
        match self {
            Expr::Unit(_) => {
                if config.node_ids {
                    SExpr::List(vec![
                        SExpr::Atom("unt".into()),
                        SExpr::Atom(self.id().0.to_string()),
                    ])
                } else {
                    SExpr::List(vec![SExpr::Atom("unt".into())])
                }
            }
            Expr::Integer(_, n) => {
                if config.node_ids {
                    SExpr::List(vec![
                        SExpr::Atom("i".into()),
                        SExpr::Atom(n.to_string()),
                        SExpr::Atom(self.id().0.to_string()),
                    ])
                } else {
                    SExpr::List(vec![SExpr::Atom("i".into()), SExpr::Atom(n.to_string())])
                }
            }
            Expr::Float(_, n) => {
                let s = if n.round() == *n {
                    format!("{}.0", n)
                } else {
                    n.to_string()
                };
                if config.node_ids {
                    SExpr::List(vec![
                        SExpr::Atom("f".into()),
                        SExpr::Atom(s),
                        SExpr::Atom(self.id().0.to_string()),
                    ])
                } else {
                    SExpr::List(vec![SExpr::Atom("f".into()), SExpr::Atom(s)])
                }
            }
            Expr::String(_, s) => {
                if config.node_ids {
                    SExpr::List(vec![
                        SExpr::Atom("s".into()),
                        SExpr::Atom(s.clone()),
                        SExpr::Atom(self.id().0.to_string()),
                    ])
                } else {
                    SExpr::List(vec![SExpr::Atom("s".into()), SExpr::Atom(s.clone())])
                }
            }
            Expr::Variable(_, v) => {
                if config.node_ids {
                    SExpr::List(vec![
                        SExpr::Atom("var".into()),
                        SExpr::Atom(v.0.to_string()),
                        SExpr::Atom(self.id().0.to_string()),
                    ])
                } else {
                    SExpr::List(vec![
                        SExpr::Atom("var".into()),
                        SExpr::Atom(v.0.to_string()),
                    ])
                }
            }
            Expr::Application { .. } => {
                // Flatten curried applications: (app (app (app f a) b) c) -> (app f a b c)
                let mut args = Vec::new();
                let mut current = self;
                while let Expr::Application {
                    abstraction: a,
                    parameter: p,
                    ..
                } = current
                {
                    args.push(p);
                    current = a;
                }
                args.reverse();
                let mut elements = vec![SExpr::Atom("app".into()), current.to_sexpr(config)];
                for arg in args {
                    elements.push(arg.to_sexpr(config));
                }
                SExpr::List(elements)
            }
            Expr::Abstraction { .. } => {
                // Flatten curried abstractions: (abs x (abs y (abs z body))) -> (abs x y z body)
                let mut params = Vec::new();
                let mut current = self;
                while let Expr::Abstraction {
                    parameter: p,
                    body: b,
                    ..
                } = current
                {
                    params.push(*p);
                    current = b.as_ref();
                }
                let mut elements = vec![SExpr::Atom("abs".into())];
                for param in params {
                    elements.push(SExpr::Atom(param.0.to_string()));
                }
                elements.push(current.to_sexpr(config));
                SExpr::List(elements)
            }
            Expr::Label { label, expr, .. } => SExpr::List(vec![
                SExpr::Atom("lbl".into()),
                SExpr::Atom(label.clone()),
                expr.to_sexpr(config),
            ]),
            Expr::Unlabel { expr, label, .. } => SExpr::List(vec![
                SExpr::Atom("ulb".into()),
                SExpr::Atom(label.clone()),
                expr.to_sexpr(config),
            ]),
            Expr::Project(_, expr) => {
                SExpr::List(vec![SExpr::Atom("prj".into()), expr.to_sexpr(config)])
            }
            Expr::Concatenate { .. } => {
                // Flatten cascading concatenations: (cat (cat a b) c) -> (cat a b c)
                let mut fields = Vec::new();
                let mut current = self;
                while let Expr::Concatenate {
                    left: l, right: r, ..
                } = current
                {
                    fields.push(r);
                    current = l;
                }
                fields.reverse();
                let mut elements = vec![SExpr::Atom("cat".into()), current.to_sexpr(config)];
                for field in fields {
                    elements.push(field.to_sexpr(config));
                }
                SExpr::List(elements)
            }
            Expr::Item(_, id, symbol) => SExpr::List(vec![
                SExpr::Atom("itm".into()),
                id.to_sexpr(config),
                symbol.to_sexpr(config),
            ]),
            Expr::Inject(id, expr) => SExpr::List(vec![
                SExpr::Atom("inj".into()),
                SExpr::Atom(id.0.to_string()),
                expr.to_sexpr(config),
            ]),
            Expr::Branch { id, left, right } => SExpr::List(vec![
                SExpr::Atom("branch".into()),
                SExpr::Atom(id.0.to_string()),
                left.to_sexpr(config),
                right.to_sexpr(config),
            ]),
        }
    }
}

impl FromSExpr<NodeIdSupply> for Expr<Var> {
    fn from_sexp(s: &SExpr, ctx: &mut NodeIdSupply) -> Result<Self, ParseError> {
        match s.tag() {
            Some("unt") => Ok(Expr::Unit(ctx.alloc())),
            Some("i") => {
                let args = s.args().ok_or(ParseError::ExpectedTag {
                    expected: "i",
                    found: None,
                })?;
                let n = match &args[0] {
                    SExpr::Atom(s) => s.parse::<i64>().map_err(|_| ParseError::ParseValue {
                        type_name: "i64",
                        reason: s.clone(),
                    })?,
                    _ => {
                        return Err(ParseError::ExpectedTag {
                            expected: "integer value",
                            found: args[0].tag().map(|s| s.to_string()),
                        });
                    }
                };
                Ok(Expr::Integer(ctx.alloc(), n))
            }
            Some("f") => {
                let args = s.args().ok_or(ParseError::ExpectedTag {
                    expected: "f",
                    found: None,
                })?;
                let n = match &args[0] {
                    SExpr::Atom(s) => s.parse::<f64>().map_err(|_| ParseError::ParseValue {
                        type_name: "f64",
                        reason: s.clone(),
                    })?,
                    _ => {
                        return Err(ParseError::ExpectedTag {
                            expected: "float value",
                            found: args[0].tag().map(|s| s.to_string()),
                        });
                    }
                };
                Ok(Expr::Float(ctx.alloc(), n))
            }
            Some("s") => {
                let args = s.args().ok_or(ParseError::ExpectedTag {
                    expected: "s",
                    found: None,
                })?;
                let s = match &args[0] {
                    SExpr::Atom(s) => s.clone(),
                    _ => {
                        return Err(ParseError::ExpectedTag {
                            expected: "string value",
                            found: args[0].tag().map(|s| s.to_string()),
                        });
                    }
                };
                Ok(Expr::String(ctx.alloc(), s))
            }
            Some("var") => {
                let args = s.args().ok_or(ParseError::ExpectedTag {
                    expected: "var",
                    found: None,
                })?;
                let v = match &args[0] {
                    SExpr::Atom(s) => s.parse::<usize>().map_err(|_| ParseError::ParseValue {
                        type_name: "usize",
                        reason: s.clone(),
                    })?,
                    _ => {
                        return Err(ParseError::ExpectedTag {
                            expected: "variable index",
                            found: args[0].tag().map(|s| s.to_string()),
                        });
                    }
                };
                Ok(Expr::Variable(ctx.alloc(), Var(v)))
            }
            Some("app") => {
                let args = s.args().ok_or(ParseError::ExpectedTag {
                    expected: "app",
                    found: None,
                })?;
                if args.is_empty() {
                    return Err(ParseError::ExpectedArgs {
                        expected: 2,
                        found: 0,
                    });
                }
                let function = Expr::from_sexp(&args[0], ctx)?;
                let mut parameters = Vec::new();
                for arg in &args[1..] {
                    parameters.push(Expr::from_sexp(arg, ctx)?);
                }
                // Fold parameters into curried applications
                let mut result = function;
                for param in parameters {
                    result = Expr::Application {
                        id: ctx.alloc(),
                        abstraction: Box::new(result),
                        parameter: Box::new(param),
                    };
                }
                Ok(result)
            }
            Some("abs") => {
                let args = s.args().ok_or(ParseError::ExpectedTag {
                    expected: "abs",
                    found: None,
                })?;
                if args.is_empty() {
                    return Err(ParseError::ExpectedArgs {
                        expected: 2,
                        found: 0,
                    });
                }
                // Parse parameters (all but last) and body (last)
                let body = Expr::from_sexp(&args[args.len() - 1], ctx)?;
                let mut params = Vec::new();
                for arg in &args[..args.len() - 1] {
                    let v = match arg {
                        SExpr::Atom(s) => {
                            s.parse::<usize>().map_err(|_| ParseError::ParseValue {
                                type_name: "usize",
                                reason: s.clone(),
                            })?
                        }
                        _ => {
                            return Err(ParseError::ExpectedTag {
                                expected: "parameter index",
                                found: arg.tag().map(|s| s.to_string()),
                            });
                        }
                    };
                    params.push(Var(v));
                }
                // Build curried abstraction from params in reverse order
                let mut result = body;
                for param in params.into_iter().rev() {
                    result = Expr::Abstraction {
                        id: ctx.alloc(),
                        parameter: param,
                        body: Box::new(result),
                    };
                }
                Ok(result)
            }
            Some("lbl") => {
                let args: &[SExpr; 2] = expect_n("lbl", s.args())?;
                let label = match &args[0] {
                    SExpr::Atom(s) => s.clone(),
                    _ => {
                        return Err(ParseError::ExpectedTag {
                            expected: "label",
                            found: args[0].tag().map(|s| s.to_string()),
                        });
                    }
                };
                let expr = Expr::from_sexp(&args[1], ctx)?;
                Ok(Expr::Label {
                    id: ctx.alloc(),
                    label,
                    expr: Box::new(expr),
                })
            }
            Some("ulb") => {
                let args: &[SExpr; 2] = expect_n("ulb", s.args())?;
                let label = match &args[0] {
                    SExpr::Atom(s) => s.clone(),
                    _ => {
                        return Err(ParseError::ExpectedTag {
                            expected: "label",
                            found: args[0].tag().map(|s| s.to_string()),
                        });
                    }
                };
                let expr = Expr::from_sexp(&args[1], ctx)?;
                Ok(Expr::Unlabel {
                    id: ctx.alloc(),
                    expr: Box::new(expr),
                    label,
                })
            }
            Some("prj") => {
                let args: &[SExpr; 1] = expect_n("prj", s.args())?;
                let expr = Expr::from_sexp(&args[0], ctx)?;
                Ok(Expr::Project(ctx.alloc(), Box::new(expr)))
            }
            Some("cat") => {
                let args = s.args().ok_or(ParseError::ExpectedTag {
                    expected: "cat",
                    found: None,
                })?;
                if args.is_empty() {
                    return Err(ParseError::ExpectedArgs {
                        expected: 2,
                        found: 0,
                    });
                }
                let mut fields = Vec::new();
                for arg in args {
                    fields.push(Expr::from_sexp(arg, ctx)?);
                }
                // Fold fields into cascading concatenations
                let mut result = fields.remove(0);
                for field in fields {
                    result = Expr::Concatenate {
                        id: ctx.alloc(),
                        left: Box::new(result),
                        right: Box::new(field),
                    };
                }
                Ok(result)
            }
            Some("itm") => {
                let args: &[SExpr; 2] = expect_n("itm", s.args())?;
                let id = ItemId::from_sexp(&args[0], ctx)?;
                let symbol = Symbol::from_sexp(&args[1], ctx)?;
                Ok(Expr::Item(ctx.alloc(), id, symbol))
            }
            _ => Err(ParseError::ExpectedTag {
                expected: "expr tag",
                found: s.tag().map(|s| s.to_string()),
            }),
        }
    }
}

// ── Expr<TypedVar> ─────────────────────────────────────────────────────

impl ToSExpr<SExprConfig> for Expr<TypedVar> {
    fn to_sexpr(&self, config: &SExprConfig) -> SExpr {
        match self {
            Expr::Unit(_) => {
                if config.node_ids {
                    SExpr::List(vec![
                        SExpr::Atom("unt".into()),
                        SExpr::Atom(self.id().0.to_string()),
                    ])
                } else {
                    SExpr::List(vec![SExpr::Atom("unt".into())])
                }
            }
            Expr::Integer(_, n) => {
                if config.node_ids {
                    SExpr::List(vec![
                        SExpr::Atom("i".into()),
                        SExpr::Atom(n.to_string()),
                        SExpr::Atom(self.id().0.to_string()),
                    ])
                } else {
                    SExpr::List(vec![SExpr::Atom("i".into()), SExpr::Atom(n.to_string())])
                }
            }
            Expr::Float(_, n) => {
                let s = if n.round() == *n {
                    format!("{}.0", n)
                } else {
                    n.to_string()
                };
                if config.node_ids {
                    SExpr::List(vec![
                        SExpr::Atom("f".into()),
                        SExpr::Atom(s),
                        SExpr::Atom(self.id().0.to_string()),
                    ])
                } else {
                    SExpr::List(vec![SExpr::Atom("f".into()), SExpr::Atom(s)])
                }
            }
            Expr::String(_, s) => {
                if config.node_ids {
                    SExpr::List(vec![
                        SExpr::Atom("s".into()),
                        SExpr::Atom(s.clone()),
                        SExpr::Atom(self.id().0.to_string()),
                    ])
                } else {
                    SExpr::List(vec![SExpr::Atom("s".into()), SExpr::Atom(s.clone())])
                }
            }
            Expr::Variable(_, v) => {
                if config.types {
                    if config.node_ids {
                        SExpr::List(vec![
                            SExpr::Atom("var".into()),
                            SExpr::Atom(v.0.0.to_string()),
                            v.1.to_sexpr(config),
                            SExpr::Atom(self.id().0.to_string()),
                        ])
                    } else {
                        SExpr::List(vec![
                            SExpr::Atom("var".into()),
                            SExpr::Atom(v.0.0.to_string()),
                            v.1.to_sexpr(config),
                        ])
                    }
                } else if config.node_ids {
                    SExpr::List(vec![
                        SExpr::Atom("var".into()),
                        SExpr::Atom(v.0.0.to_string()),
                        SExpr::Atom(self.id().0.to_string()),
                    ])
                } else {
                    SExpr::List(vec![
                        SExpr::Atom("var".into()),
                        SExpr::Atom(v.0.0.to_string()),
                    ])
                }
            }
            Expr::Application { .. } => {
                // Flatten curried applications: (app (app f a) b) -> (app f a b)
                let mut args = Vec::new();
                let mut current = self;
                while let Expr::Application {
                    abstraction: a,
                    parameter: p,
                    ..
                } = current
                {
                    args.push(p);
                    current = a;
                }
                args.reverse();
                let mut elements = vec![SExpr::Atom("app".into()), current.to_sexpr(config)];
                for arg in args {
                    elements.push(arg.to_sexpr(config));
                }
                SExpr::List(elements)
            }
            Expr::Abstraction { .. } => {
                // Flatten curried abstractions: (abs x (abs y body)) -> (abs x y body)
                let mut params = Vec::new();
                let mut current = self;
                while let Expr::Abstraction {
                    parameter: p,
                    body: b,
                    ..
                } = current
                {
                    params.push(p.clone());
                    current = b.as_ref();
                }
                let mut elements = vec![SExpr::Atom("abs".into())];
                for param in params {
                    elements.push(param.to_sexpr(config));
                }
                elements.push(current.to_sexpr(config));
                SExpr::List(elements)
            }
            Expr::Label { label, expr, .. } => SExpr::List(vec![
                SExpr::Atom("lbl".into()),
                SExpr::Atom(label.clone()),
                expr.to_sexpr(config),
            ]),
            Expr::Unlabel { expr, label, .. } => SExpr::List(vec![
                SExpr::Atom("ulb".into()),
                SExpr::Atom(label.clone()),
                expr.to_sexpr(config),
            ]),
            Expr::Project(_, expr) => {
                SExpr::List(vec![SExpr::Atom("prj".into()), expr.to_sexpr(config)])
            }
            Expr::Concatenate { .. } => {
                // Flatten cascading concatenations: (cat (cat a b) c) -> (cat a b c)
                let mut fields = Vec::new();
                let mut current = self;
                while let Expr::Concatenate {
                    left: l, right: r, ..
                } = current
                {
                    fields.push(r);
                    current = l;
                }
                fields.reverse();
                let mut elements = vec![SExpr::Atom("cat".into()), current.to_sexpr(config)];
                for field in fields {
                    elements.push(field.to_sexpr(config));
                }
                SExpr::List(elements)
            }
            Expr::Item(_, id, symbol) => SExpr::List(vec![
                SExpr::Atom("itm".into()),
                id.to_sexpr(config),
                symbol.to_sexpr(config),
            ]),
            Expr::Inject(id, expr) => SExpr::List(vec![
                SExpr::Atom("inj".into()),
                SExpr::Atom(id.0.to_string()),
                expr.to_sexpr(config),
            ]),
            Expr::Branch { id, left, right } => SExpr::List(vec![
                SExpr::Atom("branch".into()),
                SExpr::Atom(id.0.to_string()),
                left.to_sexpr(config),
                right.to_sexpr(config),
            ]),
        }
    }
}

impl FromSExpr<NodeIdSupply> for Expr<TypedVar> {
    fn from_sexp(s: &SExpr, ctx: &mut NodeIdSupply) -> Result<Self, ParseError> {
        match s.tag() {
            Some("unt") => Ok(Expr::Unit(ctx.alloc())),
            Some("i") => {
                let args = s.args().ok_or(ParseError::ExpectedTag {
                    expected: "i",
                    found: None,
                })?;
                let n = match &args[0] {
                    SExpr::Atom(s) => s.parse::<i64>().map_err(|_| ParseError::ParseValue {
                        type_name: "i64",
                        reason: s.clone(),
                    })?,
                    _ => {
                        return Err(ParseError::ExpectedTag {
                            expected: "integer value",
                            found: args[0].tag().map(|s| s.to_string()),
                        });
                    }
                };
                Ok(Expr::Integer(ctx.alloc(), n))
            }
            Some("f") => {
                let args = s.args().ok_or(ParseError::ExpectedTag {
                    expected: "f",
                    found: None,
                })?;
                let n = match &args[0] {
                    SExpr::Atom(s) => s.parse::<f64>().map_err(|_| ParseError::ParseValue {
                        type_name: "f64",
                        reason: s.clone(),
                    })?,
                    _ => {
                        return Err(ParseError::ExpectedTag {
                            expected: "float value",
                            found: args[0].tag().map(|s| s.to_string()),
                        });
                    }
                };
                Ok(Expr::Float(ctx.alloc(), n))
            }
            Some("s") => {
                let args = s.args().ok_or(ParseError::ExpectedTag {
                    expected: "s",
                    found: None,
                })?;
                let s = match &args[0] {
                    SExpr::Atom(s) => s.clone(),
                    _ => {
                        return Err(ParseError::ExpectedTag {
                            expected: "string value",
                            found: args[0].tag().map(|s| s.to_string()),
                        });
                    }
                };
                Ok(Expr::String(ctx.alloc(), s))
            }
            Some("var") => {
                let args = s.args().ok_or(ParseError::ExpectedTag {
                    expected: "var",
                    found: None,
                })?;
                if args.is_empty() {
                    return Err(ParseError::ExpectedArgs {
                        expected: 1,
                        found: 0,
                    });
                }
                let v = match &args[0] {
                    SExpr::Atom(s) => s.parse::<usize>().map_err(|_| ParseError::ParseValue {
                        type_name: "usize",
                        reason: s.clone(),
                    })?,
                    _ => {
                        return Err(ParseError::ExpectedTag {
                            expected: "variable index",
                            found: args[0].tag().map(|s| s.to_string()),
                        });
                    }
                };
                let typ = if args.len() > 1 {
                    Type::from_sexp(&args[1], ctx)?
                } else {
                    Type::Unit
                };
                Ok(Expr::Variable(ctx.alloc(), TypedVar(Var(v), typ)))
            }
            Some("app") => {
                let args = s.args().ok_or(ParseError::ExpectedTag {
                    expected: "app",
                    found: None,
                })?;
                if args.is_empty() {
                    return Err(ParseError::ExpectedArgs {
                        expected: 2,
                        found: 0,
                    });
                }
                let function = Expr::from_sexp(&args[0], ctx)?;
                let mut parameters = Vec::new();
                for arg in &args[1..] {
                    parameters.push(Expr::from_sexp(arg, ctx)?);
                }
                let mut result = function;
                for param in parameters {
                    result = Expr::Application {
                        id: ctx.alloc(),
                        abstraction: Box::new(result),
                        parameter: Box::new(param),
                    };
                }
                Ok(result)
            }
            Some("abs") => {
                let args = s.args().ok_or(ParseError::ExpectedTag {
                    expected: "abs",
                    found: None,
                })?;
                if args.is_empty() {
                    return Err(ParseError::ExpectedArgs {
                        expected: 2,
                        found: 0,
                    });
                }
                let body = Expr::from_sexp(&args[args.len() - 1], ctx)?;
                let mut params = Vec::new();
                for arg in &args[..args.len() - 1] {
                    let v = match arg {
                        SExpr::Atom(s) => {
                            s.parse::<usize>().map_err(|_| ParseError::ParseValue {
                                type_name: "usize",
                                reason: s.clone(),
                            })?
                        }
                        _ => {
                            // Try parsing as typed variable (var <index> <type>)
                            if let Some(tagged) = arg.args()
                                && !tagged.is_empty()
                                && let SExpr::Atom(idx) = &tagged[0]
                            {
                                let idx =
                                    idx.parse::<usize>().map_err(|_| ParseError::ParseValue {
                                        type_name: "usize",
                                        reason: idx.clone(),
                                    })?;
                                let typ = if tagged.len() > 1 {
                                    Type::from_sexp(&tagged[1], ctx)?
                                } else {
                                    Type::Unit
                                };
                                params.push(TypedVar(Var(idx), typ));
                                continue;
                            }
                            return Err(ParseError::ExpectedTag {
                                expected: "parameter",
                                found: arg.tag().map(|s| s.to_string()),
                            });
                        }
                    };
                    params.push(TypedVar(Var(v), Type::Unit));
                }
                let mut result = body;
                for param in params.into_iter().rev() {
                    result = Expr::Abstraction {
                        id: ctx.alloc(),
                        parameter: param,
                        body: Box::new(result),
                    };
                }
                Ok(result)
            }
            Some("lbl") => {
                let args: &[SExpr; 2] = expect_n("lbl", s.args())?;
                let label = match &args[0] {
                    SExpr::Atom(s) => s.clone(),
                    _ => {
                        return Err(ParseError::ExpectedTag {
                            expected: "label",
                            found: args[0].tag().map(|s| s.to_string()),
                        });
                    }
                };
                let expr = Expr::from_sexp(&args[1], ctx)?;
                Ok(Expr::Label {
                    id: ctx.alloc(),
                    label,
                    expr: Box::new(expr),
                })
            }
            Some("ulb") => {
                let args: &[SExpr; 2] = expect_n("ulb", s.args())?;
                let label = match &args[0] {
                    SExpr::Atom(s) => s.clone(),
                    _ => {
                        return Err(ParseError::ExpectedTag {
                            expected: "label",
                            found: args[0].tag().map(|s| s.to_string()),
                        });
                    }
                };
                let expr = Expr::from_sexp(&args[1], ctx)?;
                Ok(Expr::Unlabel {
                    id: ctx.alloc(),
                    expr: Box::new(expr),
                    label,
                })
            }
            Some("prj") => {
                let args: &[SExpr; 1] = expect_n("prj", s.args())?;
                let expr = Expr::from_sexp(&args[0], ctx)?;
                Ok(Expr::Project(ctx.alloc(), Box::new(expr)))
            }
            Some("cat") => {
                let args = s.args().ok_or(ParseError::ExpectedTag {
                    expected: "cat",
                    found: None,
                })?;
                if args.is_empty() {
                    return Err(ParseError::ExpectedArgs {
                        expected: 2,
                        found: 0,
                    });
                }
                let mut fields = Vec::new();
                for arg in args {
                    fields.push(Expr::from_sexp(arg, ctx)?);
                }
                let mut result = fields.remove(0);
                for field in fields {
                    result = Expr::Concatenate {
                        id: ctx.alloc(),
                        left: Box::new(result),
                        right: Box::new(field),
                    };
                }
                Ok(result)
            }
            Some("itm") => {
                let args: &[SExpr; 2] = expect_n("itm", s.args())?;
                let id = ItemId::from_sexp(&args[0], ctx)?;
                let symbol = Symbol::from_sexp(&args[1], ctx)?;
                Ok(Expr::Item(ctx.alloc(), id, symbol))
            }
            _ => Err(ParseError::ExpectedTag {
                expected: "expr tag",
                found: s.tag().map(|s| s.to_string()),
            }),
        }
    }
}

impl ToSExpr<SExprConfig> for ItemWrapper {
    fn to_sexpr(&self, config: &SExprConfig) -> SExpr {
        let mut elements = vec![SExpr::Atom("wrapper".into())];
        for ty in &self.types {
            elements.push(ty.to_sexpr(config));
        }
        for row in &self.rows {
            elements.push(row.to_sexpr(config));
        }
        for evidence in &self.evidence {
            elements.push(evidence.to_sexpr(config));
        }
        SExpr::List(elements)
    }
}

impl ToSExpr<SExprConfig> for TypedNativeItem {
    fn to_sexpr(&self, config: &SExprConfig) -> SExpr {
        let mut elements = vec![
            SExpr::Atom("pub".into()),
            SExpr::Atom(self.symbol.field.clone()),
            self.typed_expr.to_sexpr(config),
            self.scheme.to_sexpr(config),
        ];
        elements.push(SExpr::Atom("row_to_ev".into()));
        for (node_id, evidence) in &self.row_to_ev {
            elements.push(SExpr::List(vec![
                SExpr::List(vec![
                    SExpr::Atom("nid".into()),
                    SExpr::Atom(node_id.0.to_string()),
                ]),
                evidence.to_sexpr(config),
            ]));
        }
        elements.push(SExpr::Atom("branch_to_ret".into()));
        for (node_id, ty) in &self.branch_to_ret_typ {
            elements.push(SExpr::List(vec![
                SExpr::List(vec![
                    SExpr::Atom("nid".into()),
                    SExpr::Atom(node_id.0.to_string()),
                ]),
                ty.to_sexpr(config),
            ]));
        }
        elements.push(SExpr::Atom("wrappers".into()));
        for (node_id, wrapper) in &self.item_wrappers {
            elements.push(SExpr::List(vec![
                SExpr::List(vec![
                    SExpr::Atom("nid".into()),
                    SExpr::Atom(node_id.0.to_string()),
                ]),
                wrapper.to_sexpr(config),
            ]));
        }
        SExpr::List(elements)
    }
}

impl ToSExpr<SExprConfig> for TypedItem {
    fn to_sexpr(&self, config: &SExprConfig) -> SExpr {
        match self {
            TypedItem::Native(item) => item.to_sexpr(config),
            TypedItem::External(item) => item.to_sexpr(config),
        }
    }
}

impl ToSExpr<SExprConfig> for TypedModule {
    fn to_sexpr(&self, config: &SExprConfig) -> SExpr {
        let mut elements = vec![SExpr::Atom("typed_mod".into())];
        for (id, item) in &self.items {
            elements.push(SExpr::List(vec![
                id.to_sexpr(config),
                item.to_sexpr(config),
            ]));
        }
        SExpr::List(elements)
    }
}

// ── Debug / Display Implementations ────────────────────────────────────

impl std::fmt::Debug for Module<Var> {
    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
        write!(f, "{}", self.to_sexpr(&SExprConfig::default()))
    }
}

impl std::fmt::Display for Module<Var> {
    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
        write!(f, "{}", self.to_sexpr(&SExprConfig::default()))
    }
}

impl std::fmt::Debug for Expr<Var> {
    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
        write!(f, "{}", self.to_sexpr(&SExprConfig::default()))
    }
}

impl std::fmt::Debug for Expr<TypedVar> {
    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
        write!(f, "{}", self.to_sexpr(&SExprConfig::default()))
    }
}

impl std::fmt::Display for Expr<TypedVar> {
    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
        write!(f, "{}", self.to_sexpr(&SExprConfig::default()))
    }
}

impl std::fmt::Debug for TypedModule {
    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
        write!(f, "{}", self.to_sexpr(&SExprConfig::default()))
    }
}

impl std::fmt::Debug for TypedNativeItem {
    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
        write!(f, "{}", self.to_sexpr(&SExprConfig::default()))
    }
}

// ── Parse Functions ────────────────────────────────────────────────────

/// Parse an s-expr string into a `Module<Var>`.
pub fn parse_module(src: &str) -> Result<Module<Var>, ParseError> {
    let sexpr = crate::compiler::sexpr::parse_one(src)?;
    let mut ctx = NodeIdSupply::default();
    Module::from_sexp(&sexpr, &mut ctx)
}

/// Parse an s-expr string into an `Expr<Var>`.
pub fn parse_expr(src: &str) -> Result<Expr<Var>, ParseError> {
    let sexpr = crate::compiler::sexpr::parse_one(src)?;
    let mut ctx = NodeIdSupply::default();
    Expr::from_sexp(&sexpr, &mut ctx)
}

#[cfg(test)]
mod tests {
    use super::super::NodeId;
    use super::*;
    use crate::compiler::sexpr::parse_one;
    use expect_test::expect;

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

    #[test]
    fn to_sexpr_symbol() {
        let symbol = Symbol {
            module: "std".into(),
            field: "io".into(),
        };
        let s = symbol.to_sexpr(&SExprConfig::default());
        let output = s.to_string();
        expect!["(symbol std io)"].assert_eq(&output);
    }

    #[test]
    fn from_sexp_symbol() {
        let s = SExpr::List(vec![
            SExpr::Atom("symbol".into()),
            SExpr::Atom("std".into()),
            SExpr::Atom("io".into()),
        ]);
        let result = Symbol::from_sexp(&s, &mut NodeIdSupply::default()).unwrap();
        assert_eq!(result.module, "std");
        assert_eq!(result.field, "io");
    }

    #[test]
    fn symbol_roundtrip() {
        roundtrip::<Symbol>(expect!["(symbol std io)"]);
    }

    #[test]
    fn symbol_roundtrip_empty_module() {
        roundtrip::<Symbol>(expect!["(symbol \"\" main)"]);
    }

    // ── ItemId Tests ─────────────────────────────────────────────────────

    #[test]
    fn to_sexpr_item_id() {
        let item_id = ItemId(42);
        let s = item_id.to_sexpr(&SExprConfig::default());
        let output = s.to_string();
        expect!["(id 42)"].assert_eq(&output);
    }

    #[test]
    fn from_sexp_item_id() {
        let s = SExpr::List(vec![SExpr::Atom("id".into()), SExpr::Atom("42".into())]);
        let result = ItemId::from_sexp(&s, &mut NodeIdSupply::default()).unwrap();
        assert_eq!(result.0, 42);
    }

    #[test]
    fn item_id_roundtrip() {
        roundtrip::<ItemId>(expect!["(id 123)"]);
    }

    // ── Type Tests ────────────────────────────────────────────────────────

    #[test]
    fn to_sexpr_type_unit() {
        let ty = Type::Unit;
        let s = ty.to_sexpr(&SExprConfig::default());
        let output = s.to_string();
        expect!["(unit)"].assert_eq(&output);
    }

    #[test]
    fn to_sexpr_type_int() {
        let ty = Type::Int;
        let s = ty.to_sexpr(&SExprConfig::default());
        let output = s.to_string();
        expect!["(int)"].assert_eq(&output);
    }

    #[test]
    fn to_sexpr_type_float() {
        let ty = Type::Float;
        let s = ty.to_sexpr(&SExprConfig::default());
        let output = s.to_string();
        expect!["(float)"].assert_eq(&output);
    }

    #[test]
    fn to_sexpr_type_string() {
        let ty = Type::String;
        let s = ty.to_sexpr(&SExprConfig::default());
        let output = s.to_string();
        expect!["(string)"].assert_eq(&output);
    }

    #[test]
    fn to_sexpr_type_dataframe() {
        let ty = Type::DataFrame;
        let s = ty.to_sexpr(&SExprConfig::default());
        let output = s.to_string();
        expect!["(dataframe)"].assert_eq(&output);
    }

    #[test]
    fn to_sexpr_type_var() {
        let ty = Type::Var(TypeVar(5));
        let s = ty.to_sexpr(&SExprConfig::default());
        let output = s.to_string();
        expect!["(tvar 5)"].assert_eq(&output);
    }

    #[test]
    fn to_sexpr_type_abs() {
        let ty = Type::Abs(Box::new(Type::Int), Box::new(Type::Float));
        let s = ty.to_sexpr(&SExprConfig::default());
        let output = s.to_string();
        expect!["(fn (int) (float))"].assert_eq(&output);
    }

    #[test]
    fn to_sexpr_type_prod() {
        let ty = Type::Prod(Row::Closed(ClosedRow {
            fields: vec!["x".into(), "y".into()],
            values: vec![Type::Int, Type::Float],
        }));
        let s = ty.to_sexpr(&SExprConfig::default());
        let output = s.to_string();
        expect!["(prd (cld x (int) y (float)))"].assert_eq(&output);
    }

    #[test]
    fn to_sexpr_type_label() {
        let ty = Type::Label("foo".into(), Box::new(Type::Int));
        let s = ty.to_sexpr(&SExprConfig::default());
        let output = s.to_string();
        expect!["(lbl foo (int))"].assert_eq(&output);
    }

    #[test]
    fn from_sexp_type_unit() {
        let s = SExpr::List(vec![SExpr::Atom("unit".into())]);
        let result = Type::from_sexp(&s, &mut NodeIdSupply::default()).unwrap();
        assert_eq!(result, Type::Unit);
    }

    #[test]
    fn from_sexp_type_int() {
        let s = SExpr::List(vec![SExpr::Atom("int".into())]);
        let result = Type::from_sexp(&s, &mut NodeIdSupply::default()).unwrap();
        assert_eq!(result, Type::Int);
    }

    #[test]
    fn from_sexp_type_abs() {
        let s = SExpr::List(vec![
            SExpr::Atom("fn".into()),
            SExpr::List(vec![SExpr::Atom("int".into())]),
            SExpr::List(vec![SExpr::Atom("float".into())]),
        ]);
        let result = Type::from_sexp(&s, &mut NodeIdSupply::default()).unwrap();
        assert_eq!(
            result,
            Type::Abs(Box::new(Type::Int), Box::new(Type::Float))
        );
    }

    #[test]
    fn type_roundtrip_unit() {
        roundtrip::<Type>(expect!["(unit)"]);
    }

    #[test]
    fn type_roundtrip_abs() {
        roundtrip::<Type>(expect!["(fn (int) (float))"]);
    }

    #[test]
    fn type_roundtrip_prod() {
        roundtrip::<Type>(expect!["(prd (cld x (int) y (float)))"]);
    }

    // ── Row Tests ─────────────────────────────────────────────────────────

    #[test]
    fn to_sexpr_row_closed() {
        let row = Row::Closed(ClosedRow {
            fields: vec!["x".into()],
            values: vec![Type::Int],
        });
        let s = row.to_sexpr(&SExprConfig::default());
        let output = s.to_string();
        expect!["(cld x (int))"].assert_eq(&output);
    }

    #[test]
    fn from_sexp_row_closed() {
        let s = SExpr::List(vec![
            SExpr::Atom("cld".into()),
            SExpr::Atom("x".into()),
            SExpr::List(vec![SExpr::Atom("int".into())]),
        ]);
        let result = Row::from_sexp(&s, &mut NodeIdSupply::default()).unwrap();
        assert!(matches!(result, Row::Closed(_)));
        if let Row::Closed(row) = result {
            assert_eq!(row.fields, vec![String::from("x")]);
            assert_eq!(row.values, vec![Type::Int]);
        }
    }

    #[test]
    fn row_roundtrip_closed() {
        roundtrip::<Row>(expect!["(cld x (int) y (float))"]);
    }

    // ── ClosedRow Tests ───────────────────────────────────────────────────

    #[test]
    fn to_sexpr_closed_row() {
        let row = ClosedRow {
            fields: vec!["a".into(), "b".into()],
            values: vec![Type::Int, Type::String],
        };
        let s = row.to_sexpr(&SExprConfig::default());
        let output = s.to_string();
        expect!["(cld a (int) b (string))"].assert_eq(&output);
    }

    #[test]
    fn from_sexp_closed_row() {
        let s = SExpr::List(vec![
            SExpr::Atom("cld".into()),
            SExpr::Atom("a".into()),
            SExpr::List(vec![SExpr::Atom("int".into())]),
            SExpr::Atom("b".into()),
            SExpr::List(vec![SExpr::Atom("string".into())]),
        ]);
        let result = ClosedRow::from_sexp(&s, &mut NodeIdSupply::default()).unwrap();
        assert_eq!(result.fields, vec![String::from("a"), String::from("b")]);
        assert_eq!(result.values, vec![Type::Int, Type::String]);
    }

    #[test]
    fn closed_row_roundtrip() {
        roundtrip::<ClosedRow>(expect!["(cld x (int) y (float) z (string))"]);
    }

    // ── TypeScheme Tests ──────────────────────────────────────────────────

    #[test]
    fn to_sexpr_type_scheme_minimal() {
        let scheme = TypeScheme {
            unbound_rows: BTreeSet::new(),
            unbound_tys: BTreeSet::new(),
            evidence: Vec::new(),
            typ: Type::Int,
        };
        let s = scheme.to_sexpr(&SExprConfig {
            node_ids: false,
            types: false,
            detail: SerializationDetail::Minimal,
        });
        let output = s.to_string();
        expect!["(tsh (int) row typ)"].assert_eq(&output);
    }

    #[test]
    fn to_sexpr_type_scheme_full() {
        let mut unbound_rows = BTreeSet::new();
        unbound_rows.insert(RowVar(0));
        let mut unbound_tys = BTreeSet::new();
        unbound_tys.insert(TypeVar(1));
        let scheme = TypeScheme {
            unbound_rows,
            unbound_tys,
            evidence: Vec::new(),
            typ: Type::Int,
        };
        let s = scheme.to_sexpr(&SExprConfig {
            node_ids: false,
            types: false,
            detail: SerializationDetail::Full,
        });
        let output = s.to_string();
        expect!["(tsh (int) row (rvar 0) typ (tvar 1))"].assert_eq(&output);
    }

    #[test]
    fn from_sexp_type_scheme_minimal() {
        let s = SExpr::List(vec![
            SExpr::Atom("typ".into()),
            SExpr::List(vec![SExpr::Atom("int".into())]),
        ]);
        let result = TypeScheme::from_sexp(&s, &mut NodeIdSupply::default()).unwrap();
        assert_eq!(result.typ, Type::Int);
        assert!(result.unbound_rows.is_empty());
        assert!(result.unbound_tys.is_empty());
        assert!(result.evidence.is_empty());
    }

    #[test]
    fn type_scheme_roundtrip_minimal() {
        roundtrip::<TypeScheme>(expect!["(tsh (int) row typ)"]);
    }

    #[test]
    fn type_scheme_roundtrip_full() {
        roundtrip::<TypeScheme>(expect![
            "(tsh (int) row (rvar 2) (rvar 5) typ (tvar 1) (tvar 3))"
        ]);
    }

    // ── ExternalItem Tests ────────────────────────────────────────────────

    #[test]
    fn to_sexpr_external_item() {
        let item = ExternalItem {
            symbol: Symbol {
                module: "std".into(),
                field: "io".into(),
            },
            scheme: TypeScheme {
                unbound_rows: BTreeSet::new(),
                unbound_tys: BTreeSet::new(),
                evidence: Vec::new(),
                typ: Type::Int,
            },
            external_type: FunctionType {
                parameter_names: vec!["x".into()],
                parameter_typs: vec![ExternalType::Int],
                ret: Box::new(ExternalType::Unit),
            },
        };
        let s = item.to_sexpr(&SExprConfig::default());
        let output = s.to_string();
        expect!["(pub ext std io (tsh (int) row typ) (fn ((x (int))) (unit)))"].assert_eq(&output);
    }

    #[test]
    fn from_sexp_external_item() {
        let s = SExpr::List(vec![
            SExpr::Atom("pub".into()),
            SExpr::Atom("ext".into()),
            SExpr::Atom("std".into()),
            SExpr::Atom("io".into()),
            SExpr::List(vec![
                SExpr::Atom("typ".into()),
                SExpr::List(vec![SExpr::Atom("int".into())]),
            ]),
            SExpr::List(vec![
                SExpr::Atom("fn".into()),
                SExpr::List(vec![SExpr::List(vec![
                    SExpr::Atom("x".into()),
                    SExpr::List(vec![SExpr::Atom("int".into())]),
                ])]),
                SExpr::List(vec![SExpr::Atom("unit".into())]),
            ]),
        ]);
        let result = ExternalItem::from_sexp(&s, &mut NodeIdSupply::default()).unwrap();
        assert_eq!(result.symbol.module, "std");
        assert_eq!(result.symbol.field, "io");
        assert_eq!(result.scheme.typ, Type::Int);
    }

    // ── Expr<Var> Tests ───────────────────────────────────────────────────

    #[test]
    fn to_sexpr_expr_unit() {
        let expr: Expr<Var> = Expr::Unit(NodeId(0));
        let s = expr.to_sexpr(&SExprConfig::default());
        let output = s.to_string();
        expect!["(unt)"].assert_eq(&output);
    }

    #[test]
    fn to_sexpr_expr_integer() {
        let expr: Expr<Var> = Expr::Integer(NodeId(1), 42);
        let s = expr.to_sexpr(&SExprConfig::default());
        let output = s.to_string();
        expect!["(i 42)"].assert_eq(&output);
    }

    #[test]
    fn to_sexpr_expr_variable() {
        let expr: Expr<Var> = Expr::Variable(NodeId(2), Var(0));
        let s = expr.to_sexpr(&SExprConfig::default());
        let output = s.to_string();
        expect!["(var 0)"].assert_eq(&output);
    }

    #[test]
    fn to_sexpr_expr_application() {
        let expr: Expr<Var> = Expr::Application {
            id: NodeId(3),
            abstraction: Box::new(Expr::Item(
                NodeId(4),
                ItemId(0),
                Symbol {
                    module: "std".into(),
                    field: "add".into(),
                },
            )),
            parameter: Box::new(Expr::Integer(NodeId(5), 1)),
        };
        let s = expr.to_sexpr(&SExprConfig::default());
        let output = s.to_string();
        expect!["(app (itm (id 0) (symbol std add)) (i 1))"].assert_eq(&output);
    }

    #[test]
    fn to_sexpr_expr_abstraction() {
        let expr: Expr<Var> = Expr::Abstraction {
            id: NodeId(6),
            parameter: Var(0),
            body: Box::new(Expr::Variable(NodeId(7), Var(0))),
        };
        let s = expr.to_sexpr(&SExprConfig::default());
        let output = s.to_string();
        expect!["(abs 0 (var 0))"].assert_eq(&output);
    }

    #[test]
    fn to_sexpr_expr_label() {
        let expr: Expr<Var> = Expr::Label {
            id: NodeId(8),
            label: "foo".into(),
            expr: Box::new(Expr::Integer(NodeId(9), 1)),
        };
        let s = expr.to_sexpr(&SExprConfig::default());
        let output = s.to_string();
        expect!["(lbl foo (i 1))"].assert_eq(&output);
    }

    #[test]
    fn to_sexpr_expr_concatenate() {
        let expr: Expr<Var> = Expr::Concatenate {
            id: NodeId(10),
            left: Box::new(Expr::Label {
                id: NodeId(11),
                label: "a".into(),
                expr: Box::new(Expr::Integer(NodeId(12), 1)),
            }),
            right: Box::new(Expr::Label {
                id: NodeId(13),
                label: "b".into(),
                expr: Box::new(Expr::Integer(NodeId(14), 2)),
            }),
        };
        let s = expr.to_sexpr(&SExprConfig::default());
        let output = s.to_string();
        expect!["(cat (lbl a (i 1)) (lbl b (i 2)))"].assert_eq(&output);
    }

    #[test]
    fn from_sexp_expr_unit() {
        let s = SExpr::List(vec![SExpr::Atom("unt".into())]);
        let result = Expr::<Var>::from_sexp(&s, &mut NodeIdSupply::default()).unwrap();
        assert!(matches!(result, Expr::Unit(_)));
    }

    #[test]
    fn from_sexp_expr_integer() {
        let s = SExpr::List(vec![SExpr::Atom("i".into()), SExpr::Atom("42".into())]);
        let result = Expr::<Var>::from_sexp(&s, &mut NodeIdSupply::default()).unwrap();
        assert!(matches!(result, Expr::Integer(_, 42)));
    }

    #[test]
    fn from_sexp_expr_application() {
        let s = SExpr::List(vec![
            SExpr::Atom("app".into()),
            SExpr::List(vec![SExpr::Atom("var".into()), SExpr::Atom("0".into())]),
            SExpr::List(vec![SExpr::Atom("i".into()), SExpr::Atom("1".into())]),
        ]);
        let result = Expr::<Var>::from_sexp(&s, &mut NodeIdSupply::default()).unwrap();
        assert!(matches!(result, Expr::Application { .. }));
    }

    #[test]
    fn expr_var_roundtrip_unit() {
        roundtrip::<Expr<Var>>(expect!["(unt)"]);
    }

    #[test]
    fn expr_var_roundtrip_integer() {
        roundtrip::<Expr<Var>>(expect!["(i 42)"]);
    }

    #[test]
    fn expr_var_roundtrip_application() {
        roundtrip::<Expr<Var>>(expect!["(app (var 0) (i 1))"]);
    }

    // ── Expr<TypedVar> Tests ──────────────────────────────────────────────

    #[test]
    fn to_sexpr_typed_expr_variable_with_type() {
        let expr = Expr::Variable(NodeId(0), TypedVar(Var(0), Type::Int));
        let s = expr.to_sexpr(&SExprConfig {
            node_ids: false,
            types: true,
            detail: SerializationDetail::Minimal,
        });
        let output = s.to_string();
        expect!["(var 0 (int))"].assert_eq(&output);
    }

    #[test]
    fn from_sexp_typed_expr_variable_with_type() {
        let s = SExpr::List(vec![
            SExpr::Atom("var".into()),
            SExpr::Atom("0".into()),
            SExpr::List(vec![SExpr::Atom("int".into())]),
        ]);
        let result = Expr::<TypedVar>::from_sexp(&s, &mut NodeIdSupply::default()).unwrap();
        assert!(matches!(
            result,
            Expr::Variable(_, TypedVar(Var(0), Type::Int))
        ));
    }

    #[test]
    fn typed_expr_roundtrip_variable_with_type() {
        roundtrip::<Expr<TypedVar>>(expect!["(var 0)"]);
    }

    #[test]
    fn expr_var_roundtrip_abstraction() {
        roundtrip::<Expr<Var>>(expect!["(abs 0 (var 0))"]);
    }

    #[test]
    fn expr_var_roundtrip_concatenate() {
        roundtrip::<Expr<Var>>(expect!["(cat (lbl a (i 1)) (lbl b (i 2)))"]);
    }

    // ── Module-level Tests ────────────────────────────────────────────────

    #[test]
    fn to_sexpr_native_item() {
        let item = NativeItem {
            symbol: Symbol {
                module: String::new(),
                field: "main".into(),
            },
            abstraction: Expr::Abstraction {
                id: NodeId(0),
                parameter: Var(0),
                body: Box::new(Expr::Variable(NodeId(1), Var(0))),
            },
            typ: TypeScheme {
                unbound_rows: BTreeSet::new(),
                unbound_tys: BTreeSet::new(),
                evidence: Vec::new(),
                typ: Type::Unit,
            },
        };
        let s = item.to_sexpr(&SExprConfig::default());
        let output = s.to_string();
        expect!["(pub main (abs 0 (var 0)) (tsh (unit) row typ))"].assert_eq(&output);
    }

    #[test]
    fn from_sexp_native_item() {
        let s = SExpr::List(vec![
            SExpr::Atom("pub".into()),
            SExpr::Atom("main".into()),
            SExpr::List(vec![
                SExpr::Atom("abs".into()),
                SExpr::Atom("0".into()),
                SExpr::List(vec![SExpr::Atom("var".into()), SExpr::Atom("0".into())]),
            ]),
            SExpr::List(vec![
                SExpr::Atom("tsh".into()),
                SExpr::List(vec![SExpr::Atom("unit".into())]),
                SExpr::Atom("row".into()),
                SExpr::Atom("typ".into()),
            ]),
        ]);
        let result = NativeItem::<Var>::from_sexp(&s, &mut NodeIdSupply::default()).unwrap();
        assert_eq!(result.symbol.field, "main");
    }

    #[test]
    fn to_sexpr_item_native() {
        let item = Item::Native(NativeItem {
            symbol: Symbol {
                module: String::new(),
                field: "main".into(),
            },
            abstraction: Expr::Abstraction {
                id: NodeId(0),
                parameter: Var(0),
                body: Box::new(Expr::Variable(NodeId(1), Var(0))),
            },
            typ: TypeScheme {
                unbound_rows: BTreeSet::new(),
                unbound_tys: BTreeSet::new(),
                evidence: Vec::new(),
                typ: Type::Unit,
            },
        });
        let s = item.to_sexpr(&SExprConfig::default());
        let output = s.to_string();
        expect!["(pub main (abs 0 (var 0)) (tsh (unit) row typ))"].assert_eq(&output);
    }

    #[test]
    fn from_sexp_item_native() {
        let s = SExpr::List(vec![
            SExpr::Atom("pub".into()),
            SExpr::Atom("main".into()),
            SExpr::List(vec![
                SExpr::Atom("abs".into()),
                SExpr::Atom("0".into()),
                SExpr::List(vec![SExpr::Atom("var".into()), SExpr::Atom("0".into())]),
            ]),
            SExpr::List(vec![
                SExpr::Atom("tsh".into()),
                SExpr::List(vec![SExpr::Atom("unit".into())]),
                SExpr::Atom("row".into()),
                SExpr::Atom("typ".into()),
            ]),
        ]);
        let result = Item::<Var>::from_sexp(&s, &mut NodeIdSupply::default()).unwrap();
        assert!(matches!(result, Item::Native(_)));
    }

    #[test]
    fn to_sexpr_module() {
        let mut items = BTreeMap::new();
        items.insert(
            ItemId(0),
            Item::Native(NativeItem {
                symbol: Symbol {
                    module: String::new(),
                    field: "main".into(),
                },
                abstraction: Expr::Abstraction {
                    id: NodeId(0),
                    parameter: Var(0),
                    body: Box::new(Expr::Variable(NodeId(1), Var(0))),
                },
                typ: TypeScheme {
                    unbound_rows: BTreeSet::new(),
                    unbound_tys: BTreeSet::new(),
                    evidence: Vec::new(),
                    typ: Type::Unit,
                },
            }),
        );
        let module = Module { items };
        let s = module.to_sexpr(&SExprConfig::default());
        let output = s.to_string();
        expect!["(mod (pub main (abs 0 (var 0)) (tsh (unit) row typ)))"].assert_eq(&output);
    }

    #[test]
    fn from_sexp_module() {
        let s = SExpr::List(vec![
            SExpr::Atom("mod".into()),
            SExpr::List(vec![
                SExpr::Atom("pub".into()),
                SExpr::Atom("main".into()),
                SExpr::List(vec![
                    SExpr::Atom("abs".into()),
                    SExpr::Atom("0".into()),
                    SExpr::List(vec![SExpr::Atom("var".into()), SExpr::Atom("0".into())]),
                ]),
                SExpr::List(vec![
                    SExpr::Atom("tsh".into()),
                    SExpr::List(vec![SExpr::Atom("unit".into())]),
                    SExpr::Atom("row".into()),
                    SExpr::Atom("typ".into()),
                ]),
            ]),
        ]);
        let result = Module::<Var>::from_sexp(&s, &mut NodeIdSupply::default()).unwrap();
        assert_eq!(result.items.len(), 1);
    }

    // ── Additional Round-trip Tests ──────────────────────────────────────

    #[test]
    fn type_roundtrip_int() {
        roundtrip::<Type>(expect!["(int)"]);
    }

    #[test]
    fn type_roundtrip_float() {
        roundtrip::<Type>(expect!["(float)"]);
    }

    #[test]
    fn type_roundtrip_string() {
        roundtrip::<Type>(expect!["(string)"]);
    }

    #[test]
    fn type_roundtrip_dataframe() {
        roundtrip::<Type>(expect!["(dataframe)"]);
    }

    #[test]
    fn type_roundtrip_label() {
        roundtrip::<Type>(expect!["(lbl foo (int))"]);
    }

    #[test]
    fn native_item_roundtrip() {
        roundtrip::<NativeItem<Var>>(expect!["(pub main (abs 0 (var 0)) (tsh (unit) row typ))"]);
    }

    #[test]
    fn item_roundtrip_native() {
        roundtrip::<Item<Var>>(expect!["(pub main (abs 0 (var 0)) (tsh (unit) row typ))"]);
    }

    #[test]
    fn module_roundtrip() {
        roundtrip::<Module<Var>>(expect![
            "(mod (pub main (abs 0 (var 0)) (tsh (unit) row typ)))"
        ]);
    }

    // ── Row Open Roundtrip ────────────────────────────────────────────────

    #[test]
    fn row_roundtrip_open() {
        roundtrip::<Row>(expect!["(opn 0)"]);
    }

    // ── Evidence Roundtrip ────────────────────────────────────────────────

    #[test]
    fn evidence_roundtrip() {
        roundtrip::<Evidence>(expect![
            "(equation (cld a (int)) (cld b (float)) (cld c (string)))"
        ]);
    }

    // ── ExternalItem Roundtrip ────────────────────────────────────────────

    #[test]
    fn external_item_roundtrip() {
        roundtrip::<ExternalItem>(expect![
            r#"(pub ext std add (tsh (int) row typ) (fn ((x (int))) (string)))"#
        ]);
    }

    // ── Expr<Var> Missing Variants ────────────────────────────────────────

    #[test]
    fn expr_var_roundtrip_float() {
        roundtrip::<Expr<Var>>(expect!["(f 3.14)"]);
    }

    #[test]
    fn expr_var_roundtrip_float_whole() {
        roundtrip::<Expr<Var>>(expect!["(f 5.0)"]);
    }

    #[test]
    fn expr_var_roundtrip_string() {
        roundtrip::<Expr<Var>>(expect!["(s hello)"]);
    }

    #[test]
    fn expr_var_roundtrip_variable() {
        roundtrip::<Expr<Var>>(expect!["(var 0)"]);
    }

    #[test]
    fn expr_var_roundtrip_label() {
        roundtrip::<Expr<Var>>(expect!["(lbl a (i 1))"]);
    }

    #[test]
    fn expr_var_roundtrip_unlabel() {
        roundtrip::<Expr<Var>>(expect!["(ulb a (i 1))"]);
    }

    #[test]
    fn expr_var_roundtrip_project() {
        roundtrip::<Expr<Var>>(expect!["(prj (i 1))"]);
    }

    #[test]
    fn expr_var_roundtrip_item() {
        roundtrip::<Expr<Var>>(expect!["(itm (id 0) (symbol std add))"]);
    }

    // ── Expr<TypedVar> Missing Variants ───────────────────────────────────

    #[test]
    fn typed_expr_roundtrip_unit() {
        roundtrip::<Expr<TypedVar>>(expect!["(unt)"]);
    }

    #[test]
    fn typed_expr_roundtrip_integer() {
        roundtrip::<Expr<TypedVar>>(expect!["(i 42)"]);
    }

    #[test]
    fn typed_expr_roundtrip_float() {
        roundtrip::<Expr<TypedVar>>(expect!["(f 3.14)"]);
    }

    #[test]
    fn typed_expr_roundtrip_string() {
        roundtrip::<Expr<TypedVar>>(expect!["(s hello)"]);
    }

    #[test]
    fn typed_expr_roundtrip_application() {
        roundtrip::<Expr<TypedVar>>(expect!["(app (var 0) (i 1))"]);
    }

    #[test]
    fn typed_expr_roundtrip_abstraction() {
        roundtrip::<Expr<TypedVar>>(expect!["(abs (var 0) (var 0))"]);
    }

    #[test]
    fn typed_expr_roundtrip_label() {
        roundtrip::<Expr<TypedVar>>(expect!["(lbl a (i 1))"]);
    }

    #[test]
    fn typed_expr_roundtrip_unlabel() {
        roundtrip::<Expr<TypedVar>>(expect!["(ulb a (i 1))"]);
    }

    #[test]
    fn typed_expr_roundtrip_project() {
        roundtrip::<Expr<TypedVar>>(expect!["(prj (i 1))"]);
    }

    #[test]
    fn typed_expr_roundtrip_concatenate() {
        roundtrip::<Expr<TypedVar>>(expect!["(cat (lbl a (i 1)) (lbl b (i 2)))"]);
    }

    #[test]
    fn typed_expr_roundtrip_item() {
        roundtrip::<Expr<TypedVar>>(expect!["(itm (id 0) (symbol std add))"]);
    }
}