## Coverage Report

#### Created: 2025-09-08 21:26

next uncovered line (L), next uncovered region (R), next uncovered branch (B)

    /home/noah/src/ruchy/src/transpiler/canonical_ast.rs

    Line
    Count
    Source
    1
    //! Canonical AST Normalization
    2
    //!
    3
    //! Implements the extreme quality engineering approach from docs/ruchy-transpiler-docs.md
    4
    //! This module eliminates syntactic ambiguity by converting all surface syntax to a
    5
    //! normalized core form before transpilation.
    6
    7
    #![allow(clippy::panic)] // Panics represent genuine errors in normalization
    8
    #![allow(clippy::panic)]
    9
    use crate::frontend::ast::{Expr, ExprKind, Literal};
    10
    11
    /// De Bruijn index for variables - eliminates variable capture bugs
    12
    #[derive(Debug, Clone, PartialEq, Eq, Hash)]
    13
    pub struct DeBruijnIndex(pub usize);
    14
    15
    /// Core expression language - minimal, unambiguous representation
    16
    #[derive(Debug, Clone, PartialEq)]
    17
    pub enum CoreExpr {
    18
        /// Variable reference using De Bruijn index
    19
        Var(DeBruijnIndex),
    20
        /// Lambda abstraction (parameter name for debugging only)
    21
        Lambda {
    22
            param_name: Option<String>, // For debugging
    23
            body: Box<CoreExpr>,
    24
        },
    25
        /// Function application
    26
        App(Box<CoreExpr>, Box<CoreExpr>),
    27
        /// Let binding (name for debugging only)
    28
        Let {
    29
            name: Option<String>, // For debugging
    30
            value: Box<CoreExpr>,
    31
            body: Box<CoreExpr>,
    32
        },
    33
        /// Literal values
    34
        Literal(CoreLiteral),
    35
        /// Primitive operations
    36
        Prim(PrimOp, Vec<CoreExpr>),
    37
    }
    38
    39
    /// Core literal values
    40
    #[derive(Debug, Clone, PartialEq)]
    41
    pub enum CoreLiteral {
    42
        Integer(i64),
    43
        Float(f64),
    44
        String(String),
    45
        Bool(bool),
    46
        Char(char),
    47
        Unit,
    48
    }
    49
    50
    /// Primitive operations - all operators desugared to these
    51
    #[derive(Debug, Clone, PartialEq)]
    52
    pub enum PrimOp {
    53
        // Arithmetic
    54
        Add,
    55
        Sub,
    56
        Mul,
    57
        Div,
    58
        Mod,
    59
        Pow,
    60
        // Comparison
    61
        Eq,
    62
        Ne,
    63
        Lt,
    64
        Le,
    65
        Gt,
    66
        Ge,
    67
        // Logical
    68
        And,
    69
        Or,
    70
        Not,
    71
        NullCoalesce,
    72
        // String
    73
        Concat,
    74
        // Array
    75
        ArrayNew,
    76
        ArrayIndex,
    77
        ArrayLen,
    78
        // Control flow
    79
        If,
    80
    }
    81
    82
    /// Context for De Bruijn conversion
    83
    #[derive(Debug, Clone)]
    84
    struct DeBruijnContext {
    85
        /// Maps variable names to their De Bruijn indices
    86
        bindings: Vec<String>,
    87
    }
    88
    89
    impl DeBruijnContext {
    90
    0
        fn new() -> Self {
    91
    0
            Self {
    92
    0
                bindings: Vec::new(),
    93
    0
            }
    94
    0
        }
    95
    96
    0
        fn push(&mut self, name: String) {
    97
    0
            self.bindings.push(name);
    98
    0
        }
    99
    100
    0
        fn pop(&mut self) {
    101
    0
            self.bindings.pop();
    102
    0
        }
    103
    104
    0
        fn lookup(&self, name: &str) -> Option<DeBruijnIndex> {
    105
    0
            self.bindings
    106
    0
                .iter()
    107
    0
                .rev()
    108
    0
                .position(|n| n == name)
    109
    0
                .map(DeBruijnIndex)
    110
    0
        }
    111
    }
    112
    113
    /// AST Normalizer - converts surface syntax to canonical core form
    114
    pub struct AstNormalizer {
    115
        context: DeBruijnContext,
    116
    }
    117
    118
    impl Default for AstNormalizer {
    119
    0
        fn default() -> Self {
    120
    0
            Self::new()
    121
    0
        }
    122
    }
    123
    124
    impl AstNormalizer {
    125
        #[must_use]
    126
    0
        pub fn new() -> Self {
    127
    0
            Self {
    128
    0
                context: DeBruijnContext::new(),
    129
    0
            }
    130
    0
        }
    131
    132
        /// Main entry point: normalize an AST to core form
    133
    0
        pub fn normalize(&mut self, expr: &Expr) -> CoreExpr {
    134
    0
            self.desugar_and_convert(expr)
    135
    0
        }
    136
    137
        /// Desugar surface syntax and convert to core form with De Bruijn indices
    138
        #[allow(clippy::too_many_lines)] // Complex but necessary for complete desugaring
    139
    0
        fn desugar_and_convert(&mut self, expr: &Expr) -> CoreExpr {
    140
    0
            match &expr.kind {
    141
    0
                ExprKind::Literal(lit) => Self::convert_literal(lit),
    142
    143
    0
                ExprKind::Identifier(name) => {
    144
    0
                    if let Some(idx) = self.context.lookup(name) {
    145
    0
                        CoreExpr::Var(idx)
    146
                    } else {
    147
                        // Free variable - this shouldn't happen in well-formed programs
    148
                        // For REPL, we might want to handle this differently
    149
    0
                        panic!("Unbound variable: {name}");
    150
                    }
    151
                }
    152
    153
    0
                ExprKind::Binary { left, op, right } => {
    154
                    use crate::frontend::ast::BinaryOp;
    155
    156
    0
                    let l = self.desugar_and_convert(left);
    157
    0
                    let r = self.desugar_and_convert(right);
    158
    159
    0
                    let prim = match op {
    160
    0
                        BinaryOp::Add => PrimOp::Add,
    161
    0
                        BinaryOp::Subtract => PrimOp::Sub,
    162
    0
                        BinaryOp::Multiply => PrimOp::Mul,
    163
    0
                        BinaryOp::Divide => PrimOp::Div,
    164
    0
                        BinaryOp::Modulo => PrimOp::Mod,
    165
    0
                        BinaryOp::Power => PrimOp::Pow,
    166
    0
                        BinaryOp::Equal => PrimOp::Eq,
    167
    0
                        BinaryOp::NotEqual => PrimOp::Ne,
    168
    0
                        BinaryOp::Less => PrimOp::Lt,
    169
    0
                        BinaryOp::LessEqual => PrimOp::Le,
    170
    0
                        BinaryOp::Greater => PrimOp::Gt,
    171
    0
                        BinaryOp::GreaterEqual => PrimOp::Ge,
    172
    0
                        BinaryOp::And => PrimOp::And,
    173
    0
                        BinaryOp::Or => PrimOp::Or,
    174
    0
                        BinaryOp::NullCoalesce => PrimOp::NullCoalesce,
    175
                        // Bitwise operations not yet in core language
    176
                        BinaryOp::BitwiseAnd
    177
                        | BinaryOp::BitwiseOr
    178
                        | BinaryOp::BitwiseXor
    179
                        | BinaryOp::LeftShift => {
    180
    0
                            panic!("Bitwise operations not yet supported in core language")
    181
                        }
    182
                    };
    183
    184
    0
                    CoreExpr::Prim(prim, vec![l, r])
    185
                }
    186
    187
                ExprKind::Let {
    188
    0
                    name, value, body, ..
    189
                } => {
    190
    0
                    let val = self.desugar_and_convert(value);
    191
    192
                    // Push binding for body evaluation
    193
    0
                    self.context.push(name.clone());
    194
    0
                    let bod = self.desugar_and_convert(body);
    195
    0
                    self.context.pop();
    196
    197
    0
                    CoreExpr::Let {
    198
    0
                        name: Some(name.clone()),
    199
    0
                        value: Box::new(val),
    200
    0
                        body: Box::new(bod),
    201
    0
                    }
    202
                }
    203
    204
    0
                ExprKind::Lambda { params, body } => {
    205
                    // Desugar multi-param lambda to nested single-param lambdas
    206
                    // \x y z -> body becomes \x -> \y -> \z -> body
    207
    0
                    let mut result = self.desugar_and_convert(body);
    208
    209
    0
                    for param in params.iter().rev() {
    210
    0
                        self.context.push(param.name());
    211
    0
                        result = CoreExpr::Lambda {
    212
    0
                            param_name: Some(param.name()),
    213
    0
                            body: Box::new(result),
    214
    0
                        };
    215
    0
                        // Note: We don't pop here because we're building inside-out
    216
    0
                    }
    217
    218
                    // Pop all the params we pushed
    219
    0
                    for _ in params {
    220
    0
                        self.context.pop();
    221
    0
                    }
    222
    223
    0
                    result
    224
                }
    225
    226
                ExprKind::Function {
    227
    0
                    name, params, body, ..
    228
                } => {
    229
                    // Functions become let-bound lambdas
    230
                    // fun f(x, y) { body } becomes let f = \x y -> body
    231
    232
                    // First, add all parameters to the context
    233
    0
                    for param in params {
    234
    0
                        self.context.push(param.name());
    235
    0
                    }
    236
    237
                    // Process the body with parameters in scope
    238
    0
                    let body_core = self.desugar_and_convert(body);
    239
    240
                    // Remove parameters from context
    241
    0
                    for _ in params {
    242
    0
                        self.context.pop();
    243
    0
                    }
    244
    245
                    // Create nested lambdas for each parameter
    246
    0
                    let mut lambda_body = body_core;
    247
    0
                    for param in params.iter().rev() {
    248
    0
                        lambda_body = CoreExpr::Lambda {
    249
    0
                            param_name: Some(param.name()),
    250
    0
                            body: Box::new(lambda_body),
    251
    0
                        };
    252
    0
                    }
    253
    254
                    // Wrap in a let binding
    255
                    // For REPL context, we might want to handle this differently
    256
    0
                    CoreExpr::Let {
    257
    0
                        name: Some(name.clone()),
    258
    0
                        value: Box::new(lambda_body),
    259
    0
                        body: Box::new(CoreExpr::Literal(CoreLiteral::Unit)), // Empty body for top-level
    260
    0
                    }
    261
                }
    262
    263
    0
                ExprKind::Call { func, args } => {
    264
                    // Desugar multi-arg call to nested applications
    265
                    // f(a, b, c) becomes (((f a) b) c)
    266
    0
                    let mut result = self.desugar_and_convert(func);
    267
    268
    0
                    for arg in args {
    269
    0
                        let arg_core = self.desugar_and_convert(arg);
    270
    0
                        result = CoreExpr::App(Box::new(result), Box::new(arg_core));
    271
    0
                    }
    272
    273
    0
                    result
    274
                }
    275
    276
                ExprKind::If {
    277
    0
                    condition,
    278
    0
                    then_branch,
    279
    0
                    else_branch,
    280
                } => {
    281
    0
                    let cond = self.desugar_and_convert(condition);
    282
    0
                    let then_b = self.desugar_and_convert(then_branch);
    283
    0
                    let else_b = else_branch
    284
    0
                        .as_ref()
    285
    0
                        .map_or(CoreExpr::Literal(CoreLiteral::Unit), |e| {
    286
    0
                            self.desugar_and_convert(e)
    287
    0
                        });
    288
    289
    0
                    CoreExpr::Prim(PrimOp::If, vec![cond, then_b, else_b])
    290
                }
    291
    292
    0
                ExprKind::List(elements) => {
    293
                    // Desugar list to array operations
    294
    0
                    let mut result = CoreExpr::Prim(PrimOp::ArrayNew, vec![]);
    295
    296
    0
                    for elem in elements {
    297
    0
                        let elem_core = self.desugar_and_convert(elem);
    298
    0
                        // Each element becomes an append operation
    299
    0
                        // This is simplified; real implementation would be more efficient
    300
    0
                        result = CoreExpr::Prim(PrimOp::ArrayNew, vec![result, elem_core]);
    301
    0
                    }
    302
    303
    0
                    result
    304
                }
    305
    306
    0
                ExprKind::Block(exprs) => {
    307
                    // For a block, we evaluate all expressions but return only the last one
    308
                    // This is a simplification - a full implementation would handle statements
    309
    0
                    if exprs.is_empty() {
    310
    0
                        CoreExpr::Literal(CoreLiteral::Unit)
    311
    0
                    } else if exprs.len() == 1 {
    312
    0
                        self.desugar_and_convert(&exprs[0])
    313
                    } else {
    314
                        // For now, just return the last expression
    315
                        // A complete implementation would handle side effects
    316
    0
                        if let Some(last) = exprs.last() {
    317
    0
                            self.desugar_and_convert(last)
    318
                        } else {
    319
    0
                            CoreExpr::Literal(CoreLiteral::Unit)
    320
                        }
    321
                    }
    322
                }
    323
    324
                _ => {
    325
                    // For now, panic on unsupported constructs
    326
                    // In production, we'd handle all cases
    327
    0
                    panic!("Unsupported expression kind in normalizer: {:?}", expr.kind);
    328
                }
    329
            }
    330
    0
        }
    331
    332
    0
        fn convert_literal(lit: &Literal) -> CoreExpr {
    333
    0
            CoreExpr::Literal(match lit {
    334
    0
                Literal::Integer(i) => CoreLiteral::Integer(*i),
    335
    0
                Literal::Float(f) => CoreLiteral::Float(*f),
    336
    0
                Literal::String(s) => CoreLiteral::String(s.clone()),
    337
    0
                Literal::Bool(b) => CoreLiteral::Bool(*b),
    338
    0
                Literal::Char(c) => CoreLiteral::Char(*c),
    339
    0
                Literal::Unit => CoreLiteral::Unit,
    340
            })
    341
    0
        }
    342
    }
    343
    344
    /// Invariant checking
    345
    impl CoreExpr {
    346
        /// Check that the expression is in normal form
    347
        #[must_use]
    348
    0
        pub fn is_normalized(&self) -> bool {
    349
    0
            match self {
    350
    0
                CoreExpr::Var(_) | CoreExpr::Literal(_) => true,
    351
    0
                CoreExpr::Lambda { body, .. } => body.is_normalized(),
    352
    0
                CoreExpr::App(f, x) => f.is_normalized() && x.is_normalized(),
    353
    0
                CoreExpr::Let { value, body, .. } => value.is_normalized() && body.is_normalized(),
    354
    0
                CoreExpr::Prim(_, args) => args.iter().all(CoreExpr::is_normalized),
    355
            }
    356
    0
        }
    357
    358
        /// Check that all variables are bound (no free variables)
    359
        #[must_use]
    360
    0
        pub fn is_closed(&self) -> bool {
    361
    0
            self.is_closed_at(0)
    362
    0
        }
    363
    364
    0
        fn is_closed_at(&self, depth: usize) -> bool {
    365
    0
            match self {
    366
    0
                CoreExpr::Var(DeBruijnIndex(idx)) => *idx < depth,
    367
    0
                CoreExpr::Lambda { body, .. } => body.is_closed_at(depth + 1),
    368
    0
                CoreExpr::App(f, x) => f.is_closed_at(depth) && x.is_closed_at(depth),
    369
    0
                CoreExpr::Let { value, body, .. } => {
    370
    0
                    value.is_closed_at(depth) && body.is_closed_at(depth + 1)
    371
                }
    372
    0
                CoreExpr::Literal(_) => true,
    373
    0
                CoreExpr::Prim(_, args) => args.iter().all(|a| a.is_closed_at(depth)),
    374
            }
    375
    0
        }
    376
    }
    377
    378
    #[cfg(test)]
    379
    mod tests {
    380
        #![allow(clippy::unwrap_used)]
    381
        use super::*;
    382
        use crate::Parser;
    383
    384
        #[test]
    385
        fn test_normalize_let_statement() {
    386
            let input = "let x = 10 in x + 1";
    387
            let mut parser = Parser::new(input);
    388
            let ast = parser.parse().unwrap();
    389
    390
            let mut normalizer = AstNormalizer::new();
    391
            let core = normalizer.normalize(&ast);
    392
    393
            // Should be: Let { name: "x", value: Literal(10), body: Unit }
    394
            assert!(matches!(core, CoreExpr::Let { .. }));
    395
            assert!(core.is_normalized());
    396
        }
    397
    398
        #[test]
    399
        fn test_normalize_lambda() {
    400
            let input = "fun add(x, y) { x + y }";
    401
            let mut parser = Parser::new(input);
    402
            let ast = parser.parse().unwrap();
    403
    404
            let mut normalizer = AstNormalizer::new();
    405
            let core = normalizer.normalize(&ast);
    406
    407
            // Should be: Let { name: "add", value: Lambda { Lambda { Prim(Add, [Var(1), Var(0)]) } } }
    408
            assert!(matches!(core, CoreExpr::Let { .. }));
    409
            assert!(core.is_normalized());
    410
        }
    411
    412
        #[test]
    413
        fn test_idempotent_normalization() {
    414
            let inputs = vec!["42", "let x = 10 in x + 1", "fun f(x) { x * 2 }"];
    415
    416
            for input in inputs {
    417
                let mut parser = Parser::new(input);
    418
                if let Ok(ast) = parser.parse() {
    419
                    let mut normalizer1 = AstNormalizer::new();
    420
                    let core1 = normalizer1.normalize(&ast);
    421
    422
                    // Normalizing again should produce the same result
    423
                    let mut normalizer2 = AstNormalizer::new();
    424
                    let core2 = normalizer2.normalize(&ast);
    425
    426
                    assert_eq!(core1, core2, "Normalization should be deterministic");
    427
                }
    428
            }
    429
        }
    430
    }