## 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/middleend/environment.rs

    Line
    Count
    Source
    1
    //! Type environment for type inference
    2
    3
    use crate::middleend::types::{MonoType, TyVarGenerator, TypeScheme};
    4
    use std::collections::HashMap;
    5
    6
    /// Type environment mapping identifiers to type schemes
    7
    #[derive(Debug, Clone)]
    8
    pub struct TypeEnv {
    9
        bindings: HashMap<String, TypeScheme>,
    10
    }
    11
    12
    impl TypeEnv {
    13
        #[must_use]
    14
    0
        pub fn new() -> Self {
    15
    0
            TypeEnv {
    16
    0
                bindings: HashMap::new(),
    17
    0
            }
    18
    0
        }
    19
    20
        /// Create a standard environment with built-in functions
    21
        #[must_use]
    22
    0
        pub fn standard() -> Self {
    23
    0
            let mut env = Self::new();
    24
    25
            // Arithmetic functions
    26
    0
            env.bind(
    27
                "add",
    28
    0
                TypeScheme::mono(MonoType::Function(
    29
    0
                    Box::new(MonoType::Int),
    30
    0
                    Box::new(MonoType::Function(
    31
    0
                        Box::new(MonoType::Int),
    32
    0
                        Box::new(MonoType::Int),
    33
    0
                    )),
    34
    0
                )),
    35
            );
    36
    37
            // IO functions
    38
    0
            env.bind(
    39
                "print",
    40
    0
                TypeScheme::mono(MonoType::Function(
    41
    0
                    Box::new(MonoType::String),
    42
    0
                    Box::new(MonoType::Unit),
    43
    0
                )),
    44
            );
    45
    46
    0
            env.bind(
    47
                "println",
    48
    0
                TypeScheme::mono(MonoType::Function(
    49
    0
                    Box::new(MonoType::String),
    50
    0
                    Box::new(MonoType::Unit),
    51
    0
                )),
    52
            );
    53
    54
            // Comparison functions
    55
    0
            env.bind(
    56
                "eq",
    57
    0
                TypeScheme::mono(MonoType::Function(
    58
    0
                    Box::new(MonoType::Int),
    59
    0
                    Box::new(MonoType::Function(
    60
    0
                        Box::new(MonoType::Int),
    61
    0
                        Box::new(MonoType::Bool),
    62
    0
                    )),
    63
    0
                )),
    64
            );
    65
    66
    0
            env
    67
    0
        }
    68
    69
        /// Bind a name to a type scheme
    70
    0
        pub fn bind(&mut self, name: impl Into<String>, scheme: TypeScheme) {
    71
    0
            self.bindings.insert(name.into(), scheme);
    72
    0
        }
    73
    74
        /// Look up a name in the environment
    75
        #[must_use]
    76
    0
        pub fn lookup(&self, name: &str) -> Option<&TypeScheme> {
    77
    0
            self.bindings.get(name)
    78
    0
        }
    79
    80
        /// Extend the environment with a new binding (functional style)
    81
        #[must_use]
    82
    0
        pub fn extend(&self, name: impl Into<String>, scheme: TypeScheme) -> Self {
    83
    0
            let mut new_env = self.clone();
    84
    0
            new_env.bind(name, scheme);
    85
    0
            new_env
    86
    0
        }
    87
    88
        /// Get free type variables in the environment
    89
        #[must_use]
    90
    0
        pub fn free_vars(&self) -> Vec<crate::middleend::types::TyVar> {
    91
    0
            let mut vars = Vec::new();
    92
    0
            for scheme in self.bindings.values() {
    93
                // Only collect free variables not bound by the scheme
    94
    0
                let scheme_free = scheme.ty.free_vars();
    95
    0
                for var in scheme_free {
    96
    0
                    if !scheme.vars.contains(&var) {
    97
    0
                        vars.push(var);
    98
    0
                    }
    99
                }
    100
            }
    101
    0
            vars
    102
    0
        }
    103
    104
        /// Generalize a monomorphic type to a type scheme
    105
        #[must_use]
    106
    0
        pub fn generalize(&self, ty: MonoType) -> TypeScheme {
    107
    0
            let ty_vars = ty.free_vars();
    108
    0
            let env_vars = self.free_vars();
    109
    110
            // Variables to generalize are those in ty but not in env
    111
    0
            let gen_vars: Vec<_> = ty_vars
    112
    0
                .into_iter()
    113
    0
                .filter(|v| !env_vars.contains(v))
    114
    0
                .collect();
    115
    116
    0
            TypeScheme { vars: gen_vars, ty }
    117
    0
        }
    118
    119
        /// Instantiate a type scheme with fresh variables
    120
    0
        pub fn instantiate(&self, scheme: &TypeScheme, gen: &mut TyVarGenerator) -> MonoType {
    121
    0
            scheme.instantiate(gen)
    122
    0
        }
    123
    }
    124
    125
    impl Default for TypeEnv {
    126
    0
        fn default() -> Self {
    127
    0
            Self::new()
    128
    0
        }
    129
    }
    130
    131
    #[cfg(test)]
    132
    #[allow(clippy::unwrap_used, clippy::panic)]
    133
    mod tests {
    134
        use super::*;
    135
        use crate::middleend::types::TyVar;
    136
    137
        #[test]
    138
        fn test_env_lookup() {
    139
            let mut env = TypeEnv::new();
    140
            env.bind("x", TypeScheme::mono(MonoType::Int));
    141
    142
            assert!(env.lookup("x").is_some());
    143
            assert!(env.lookup("y").is_none());
    144
        }
    145
    146
        #[test]
    147
        fn test_env_extend() {
    148
            let env = TypeEnv::new();
    149
            let env2 = env.extend("x", TypeScheme::mono(MonoType::Bool));
    150
    151
            assert!(env.lookup("x").is_none());
    152
            assert!(env2.lookup("x").is_some());
    153
        }
    154
    155
        #[test]
    156
        fn test_generalization() {
    157
            let env = TypeEnv::new();
    158
            let var = TyVar(0);
    159
    160
            // A type with a free variable
    161
            let ty = MonoType::Function(
    162
                Box::new(MonoType::Var(var.clone())),
    163
                Box::new(MonoType::Var(var.clone())),
    164
            );
    165
    166
            let scheme = env.generalize(ty);
    167
    168
            // The variable should be generalized
    169
            assert_eq!(scheme.vars.len(), 1);
    170
            assert!(scheme.vars.contains(&var));
    171
        }
    172
    173
        #[test]
    174
        fn test_no_generalization_with_env_vars() {
    175
            let mut env = TypeEnv::new();
    176
            let var = TyVar(0);
    177
    178
            // Add a binding with the same variable to the environment
    179
            env.bind("y", TypeScheme::mono(MonoType::Var(var.clone())));
    180
    181
            // Try to generalize a type with the same variable
    182
            let ty = MonoType::Function(Box::new(MonoType::Var(var)), Box::new(MonoType::Int));
    183
    184
            let scheme = env.generalize(ty);
    185
    186
            // The variable should NOT be generalized (it's in the env)
    187
            assert_eq!(scheme.vars.len(), 0);
    188
        }
    189
    190
        #[test]
    191
        fn test_standard_env() {
    192
            let env = TypeEnv::standard();
    193
    194
            assert!(env.lookup("println").is_some());
    195
            assert!(env.lookup("print").is_some());
    196
            assert!(env.lookup("add").is_some());
    197
            assert!(env.lookup("eq").is_some());
    198
        }
    199
    200
        #[test]
    201
        fn test_default_env() {
    202
            let env = TypeEnv::default();
    203
            assert!(env.lookup("nonexistent").is_none());
    204
            assert_eq!(env.bindings.len(), 0);
    205
        }
    206
    207
        #[test]
    208
        fn test_multiple_bindings() {
    209
            let mut env = TypeEnv::new();
    210
            env.bind("x", TypeScheme::mono(MonoType::Int));
    211
            env.bind("y", TypeScheme::mono(MonoType::Bool));
    212
            env.bind("z", TypeScheme::mono(MonoType::String));
    213
    214
            assert!(env.lookup("x").is_some());
    215
            assert!(env.lookup("y").is_some());
    216
            assert!(env.lookup("z").is_some());
    217
            assert!(env.lookup("w").is_none());
    218
        }
    219
    220
        #[test]
    221
        fn test_bind_overwrites() {
    222
            let mut env = TypeEnv::new();
    223
            env.bind("x", TypeScheme::mono(MonoType::Int));
    224
            env.bind("x", TypeScheme::mono(MonoType::Bool));
    225
    226
            let scheme = env.lookup("x").unwrap();
    227
            match &scheme.ty {
    228
                MonoType::Bool => {}, // Expected
    229
                _ => panic!("Expected Bool type after overwrite"),
    230
            }
    231
        }
    232
    233
        #[test]
    234
        fn test_env_clone() {
    235
            let mut env1 = TypeEnv::new();
    236
            env1.bind("x", TypeScheme::mono(MonoType::Int));
    237
    238
            let env2 = env1.clone();
    239
            assert!(env2.lookup("x").is_some());
    240
        }
    241
    242
        #[test]
    243
        fn test_free_vars_empty() {
    244
            let env = TypeEnv::new();
    245
            assert!(env.free_vars().is_empty());
    246
        }
    247
    248
        #[test]
    249
        fn test_free_vars_with_schemes() {
    250
            let mut env = TypeEnv::new();
    251
            let var1 = TyVar(1);
    252
            let var2 = TyVar(2);
    253
    254
            // Add a scheme with a free variable
    255
            let scheme1 = TypeScheme {
    256
                vars: vec![],
    257
                ty: MonoType::Var(var1.clone()),
    258
            };
    259
            env.bind("x", scheme1);
    260
    261
            // Add a scheme with a bound variable
    262
            let scheme2 = TypeScheme {
    263
                vars: vec![var2.clone()],
    264
                ty: MonoType::Var(var2),
    265
            };
    266
            env.bind("y", scheme2);
    267
    268
            let free_vars = env.free_vars();
    269
            assert!(free_vars.contains(&var1));
    270
            assert!(!free_vars.contains(&TyVar(2))); // var2 is bound
    271
        }
    272
    273
        #[test]
    274
        fn test_generalize_empty_env() {
    275
            let env = TypeEnv::new();
    276
            let var = TyVar(5);
    277
            let ty = MonoType::Var(var.clone());
    278
    279
            let scheme = env.generalize(ty);
    280
            assert_eq!(scheme.vars.len(), 1);
    281
            assert!(scheme.vars.contains(&var));
    282
        }
    283
    284
        #[test]
    285
        fn test_generalize_complex_type() {
    286
            let env = TypeEnv::new();
    287
            let var1 = TyVar(10);
    288
            let var2 = TyVar(11);
    289
    290
            let ty = MonoType::Function(
    291
                Box::new(MonoType::Var(var1.clone())),
    292
                Box::new(MonoType::Function(
    293
                    Box::new(MonoType::Var(var2.clone())),
    294
                    Box::new(MonoType::Int),
    295
                )),
    296
            );
    297
    298
            let scheme = env.generalize(ty);
    299
            assert_eq!(scheme.vars.len(), 2);
    300
            assert!(scheme.vars.contains(&var1));
    301
            assert!(scheme.vars.contains(&var2));
    302
        }
    303
    304
        #[test]
    305
        fn test_instantiate_scheme() {
    306
            let env = TypeEnv::new();
    307
            let mut gen = TyVarGenerator::new();
    308
    309
            // Create a polymorphic scheme: forall a. a -> a
    310
            let var = TyVar(20);
    311
            let scheme = TypeScheme {
    312
                vars: vec![var.clone()],
    313
                ty: MonoType::Function(
    314
                    Box::new(MonoType::Var(var.clone())),
    315
                    Box::new(MonoType::Var(var)),
    316
                ),
    317
            };
    318
    319
            let instance = env.instantiate(&scheme, &mut gen);
    320
    321
            // Should get fresh variables
    322
            match instance {
    323
                MonoType::Function(arg, ret) => {
    324
                    match (*arg, *ret) {
    325
                        (MonoType::Var(v1), MonoType::Var(v2)) => {
    326
                            assert_eq!(v1, v2); // Same fresh variable
    327
                            assert_ne!(v1, TyVar(20)); // Different from original
    328
                        }
    329
                        _ => panic!("Expected function with variable types"),
    330
                    }
    331
                }
    332
                _ => panic!("Expected function type"),
    333
            }
    334
        }
    335
    336
        #[test]
    337
        fn test_standard_env_function_types() {
    338
            let env = TypeEnv::standard();
    339
    340
            // Test add function type
    341
            let add_scheme = env.lookup("add").unwrap();
    342
            match &add_scheme.ty {
    343
                MonoType::Function(arg1, rest) => {
    344
                    assert!(matches!(**arg1, MonoType::Int));
    345
                    match rest.as_ref() {
    346
                        MonoType::Function(arg2, ret_type) => {
    347
                            assert!(matches!(**arg2, MonoType::Int));
    348
                            assert!(matches!(**ret_type, MonoType::Int));
    349
                        }
    350
                        _ => panic!("Expected curried function type"),
    351
                    }
    352
                }
    353
                _ => panic!("Expected function type for add"),
    354
            }
    355
    356
            // Test print function type
    357
            let print_scheme = env.lookup("print").unwrap();
    358
            match &print_scheme.ty {
    359
                MonoType::Function(arg, ret) => {
    360
                    assert!(matches!(**arg, MonoType::String));
    361
                    assert!(matches!(**ret, MonoType::Unit));
    362
                }
    363
                _ => panic!("Expected function type for print"),
    364
            }
    365
        }
    366
    }