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

    Line
    Count
    Source
    1
    //! Type system representation for Ruchy
    2
    3
    use std::collections::HashMap;
    4
    use std::fmt;
    5
    6
    /// Type variable for unification
    7
    #[derive(Debug, Clone, PartialEq, Eq, Hash)]
    8
    pub struct TyVar(pub u32);
    9
    10
    impl fmt::Display for TyVar {
    11
    0
        fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
    12
    0
            write!(f, "τ{}", self.0)
    13
    0
        }
    14
    }
    15
    16
    /// Monomorphic types in the Hindley-Milner system
    17
    #[derive(Debug, Clone, PartialEq)]
    18
    pub enum MonoType {
    19
        /// Type variable (unknown type to be inferred)
    20
        Var(TyVar),
    21
        /// Primitive integer type
    22
        Int,
    23
        /// Primitive float type
    24
        Float,
    25
        /// Primitive boolean type
    26
        Bool,
    27
        /// String type
    28
        String,
    29
        /// Character type
    30
        Char,
    31
        /// Unit type ()
    32
        Unit,
    33
        /// Function type: T1 -> T2
    34
        Function(Box<MonoType>, Box<MonoType>),
    35
        /// List type: `[T]`
    36
        List(Box<MonoType>),
    37
        /// Tuple type: (T1, T2, ...)
    38
        Tuple(Vec<MonoType>),
    39
        /// Optional type: T?
    40
        Optional(Box<MonoType>),
    41
        /// Result type: Result<T, E>
    42
        Result(Box<MonoType>, Box<MonoType>),
    43
        /// Named type (user-defined or gradual typing 'Any')
    44
        Named(String),
    45
        /// Reference type: &T
    46
        Reference(Box<MonoType>),
    47
        /// `DataFrame` type with column names and their types
    48
        DataFrame(Vec<(String, MonoType)>),
    49
        /// Series type with element type
    50
        Series(Box<MonoType>),
    51
    }
    52
    53
    impl fmt::Display for MonoType {
    54
    0
        fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
    55
    0
            match self {
    56
    0
                MonoType::Var(v) => write!(f, "{v}"),
    57
    0
                MonoType::Int => write!(f, "i32"),
    58
    0
                MonoType::Float => write!(f, "f64"),
    59
    0
                MonoType::Bool => write!(f, "bool"),
    60
    0
                MonoType::String => write!(f, "String"),
    61
    0
                MonoType::Char => write!(f, "char"),
    62
    0
                MonoType::Unit => write!(f, "()"),
    63
    0
                MonoType::Function(arg, ret) => write!(f, "({arg} -> {ret})"),
    64
    0
                MonoType::List(elem) => write!(f, "[{elem}]"),
    65
    0
                MonoType::Optional(inner) => write!(f, "{inner}?"),
    66
    0
                MonoType::Result(ok, err) => write!(f, "Result<{ok}, {err}>"),
    67
    0
                MonoType::Tuple(types) => {
    68
    0
                    write!(f, "(")?;
    69
    0
                    for (i, ty) in types.iter().enumerate() {
    70
    0
                        if i > 0 {
    71
    0
                            write!(f, ", ")?;
    72
    0
                        }
    73
    0
                        write!(f, "{ty}")?;
    74
                    }
    75
    0
                    write!(f, ")")
    76
                }
    77
    0
                MonoType::Named(name) => write!(f, "{name}"),
    78
    0
                MonoType::Reference(inner) => write!(f, "&{inner}"),
    79
    0
                MonoType::DataFrame(columns) => {
    80
    0
                    write!(f, "DataFrame[")?;
    81
    0
                    for (i, (name, ty)) in columns.iter().enumerate() {
    82
    0
                        if i > 0 {
    83
    0
                            write!(f, ", ")?;
    84
    0
                        }
    85
    0
                        write!(f, "{name}: {ty}")?;
    86
                    }
    87
    0
                    write!(f, "]")
    88
                }
    89
    0
                MonoType::Series(dtype) => write!(f, "Series<{dtype}>"),
    90
            }
    91
    0
        }
    92
    }
    93
    94
    /// Polymorphic type scheme: ∀α₁...αₙ. τ
    95
    #[derive(Debug, Clone)]
    96
    pub struct TypeScheme {
    97
        /// Quantified type variables
    98
        pub vars: Vec<TyVar>,
    99
        /// The monomorphic type
    100
        pub ty: MonoType,
    101
    }
    102
    103
    impl TypeScheme {
    104
        /// Create a monomorphic type scheme (no quantified variables)
    105
        #[must_use]
    106
    0
        pub fn mono(ty: MonoType) -> Self {
    107
    0
            TypeScheme {
    108
    0
                vars: Vec::new(),
    109
    0
                ty,
    110
    0
            }
    111
    0
        }
    112
    113
        /// Instantiate a type scheme with fresh type variables
    114
    0
        pub fn instantiate(&self, gen: &mut TyVarGenerator) -> MonoType {
    115
    0
            if self.vars.is_empty() {
    116
    0
                self.ty.clone()
    117
            } else {
    118
    0
                let subst: HashMap<TyVar, MonoType> = self
    119
    0
                    .vars
    120
    0
                    .iter()
    121
    0
                    .map(|v| (v.clone(), MonoType::Var(gen.fresh())))
    122
    0
                    .collect();
    123
    0
                self.ty.substitute(&subst)
    124
            }
    125
    0
        }
    126
    }
    127
    128
    impl fmt::Display for TypeScheme {
    129
    0
        fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
    130
    0
            if self.vars.is_empty() {
    131
    0
                write!(f, "{}", self.ty)
    132
            } else {
    133
    0
                write!(f, "∀")?;
    134
    0
                for (i, var) in self.vars.iter().enumerate() {
    135
    0
                    if i > 0 {
    136
    0
                        write!(f, ",")?;
    137
    0
                    }
    138
    0
                    write!(f, "{var}")?;
    139
                }
    140
    0
                write!(f, ". {}", self.ty)
    141
            }
    142
    0
        }
    143
    }
    144
    145
    /// Type variable generator for fresh variables
    146
    pub struct TyVarGenerator {
    147
        next: u32,
    148
    }
    149
    150
    impl TyVarGenerator {
    151
        #[must_use]
    152
    0
        pub fn new() -> Self {
    153
    0
            TyVarGenerator { next: 0 }
    154
    0
        }
    155
    156
    0
        pub fn fresh(&mut self) -> TyVar {
    157
    0
            let var = TyVar(self.next);
    158
    0
            self.next += 1;
    159
    0
            var
    160
    0
        }
    161
    }
    162
    163
    impl Default for TyVarGenerator {
    164
    0
        fn default() -> Self {
    165
    0
            Self::new()
    166
    0
        }
    167
    }
    168
    169
    /// Substitution mapping from type variables to types
    170
    pub type Substitution = HashMap<TyVar, MonoType>;
    171
    172
    impl MonoType {
    173
        /// Apply a substitution to this type
    174
        #[must_use]
    175
    0
        pub fn substitute(&self, subst: &Substitution) -> MonoType {
    176
    0
            match self {
    177
    0
                MonoType::Var(v) => subst.get(v).cloned().unwrap_or_else(|| self.clone()),
    178
    0
                MonoType::Function(arg, ret) => MonoType::Function(
    179
    0
                    Box::new(arg.substitute(subst)),
    180
    0
                    Box::new(ret.substitute(subst)),
    181
    0
                ),
    182
    0
                MonoType::List(elem) => MonoType::List(Box::new(elem.substitute(subst))),
    183
    0
                MonoType::Optional(inner) => MonoType::Optional(Box::new(inner.substitute(subst))),
    184
    0
                MonoType::Result(ok, err) => MonoType::Result(
    185
    0
                    Box::new(ok.substitute(subst)),
    186
    0
                    Box::new(err.substitute(subst)),
    187
    0
                ),
    188
    0
                MonoType::DataFrame(columns) => MonoType::DataFrame(
    189
    0
                    columns
    190
    0
                        .iter()
    191
    0
                        .map(|(name, ty)| (name.clone(), ty.substitute(subst)))
    192
    0
                        .collect(),
    193
                ),
    194
    0
                MonoType::Series(dtype) => MonoType::Series(Box::new(dtype.substitute(subst))),
    195
    0
                MonoType::Reference(inner) => MonoType::Reference(Box::new(inner.substitute(subst))),
    196
    0
                MonoType::Tuple(types) => {
    197
    0
                    MonoType::Tuple(types.iter().map(|ty| ty.substitute(subst)).collect())
    198
                }
    199
    0
                _ => self.clone(),
    200
            }
    201
    0
        }
    202
    203
        /// Get free type variables in this type
    204
        #[must_use]
    205
    0
        pub fn free_vars(&self) -> Vec<TyVar> {
    206
            use std::collections::HashSet;
    207
    208
    0
            fn collect_vars(ty: &MonoType, vars: &mut HashSet<TyVar>) {
    209
    0
                match ty {
    210
    0
                    MonoType::Var(v) => {
    211
    0
                        vars.insert(v.clone());
    212
    0
                    }
    213
    0
                    MonoType::Function(arg, ret) => {
    214
    0
                        collect_vars(arg, vars);
    215
    0
                        collect_vars(ret, vars);
    216
    0
                    }
    217
    0
                    MonoType::List(elem) => collect_vars(elem, vars),
    218
    0
                    MonoType::Optional(inner)
    219
    0
                    | MonoType::Series(inner)
    220
    0
                    | MonoType::Reference(inner) => {
    221
    0
                        collect_vars(inner, vars);
    222
    0
                    }
    223
    0
                    MonoType::Result(ok, err) => {
    224
    0
                        collect_vars(ok, vars);
    225
    0
                        collect_vars(err, vars);
    226
    0
                    }
    227
    0
                    MonoType::DataFrame(columns) => {
    228
    0
                        for (_, ty) in columns {
    229
    0
                            collect_vars(ty, vars);
    230
    0
                        }
    231
                    }
    232
    0
                    MonoType::Tuple(types) => {
    233
    0
                        for ty in types {
    234
    0
                            collect_vars(ty, vars);
    235
    0
                        }
    236
                    }
    237
    0
                    _ => {}
    238
                }
    239
    0
            }
    240
    241
    0
            let mut vars = HashSet::new();
    242
    0
            collect_vars(self, &mut vars);
    243
    0
            vars.into_iter().collect()
    244
    0
        }
    245
    }
    246
    247
    #[cfg(test)]
    248
    #[allow(clippy::unwrap_used, clippy::panic, clippy::expect_used)]
    249
    #[allow(clippy::unwrap_used, clippy::panic)]
    250
    mod tests {
    251
        use super::*;
    252
    253
        #[test]
    254
        fn test_type_display() {
    255
            assert_eq!(MonoType::Int.to_string(), "i32");
    256
            assert_eq!(MonoType::Bool.to_string(), "bool");
    257
            assert_eq!(
    258
                MonoType::Function(Box::new(MonoType::Int), Box::new(MonoType::Bool)).to_string(),
    259
                "(i32 -> bool)"
    260
            );
    261
            assert_eq!(MonoType::List(Box::new(MonoType::Int)).to_string(), "[i32]");
    262
        }
    263
    264
        #[test]
    265
        fn test_type_scheme_instantiation() {
    266
            let mut gen = TyVarGenerator::new();
    267
            let var = gen.fresh();
    268
    269
            let scheme = TypeScheme {
    270
                vars: vec![var.clone()],
    271
                ty: MonoType::Function(
    272
                    Box::new(MonoType::Var(var.clone())),
    273
                    Box::new(MonoType::Var(var)),
    274
                ),
    275
            };
    276
    277
            let instantiated = scheme.instantiate(&mut gen);
    278
            match instantiated {
    279
                MonoType::Function(arg, ret) => {
    280
                    assert!(matches!(*arg, MonoType::Var(_)));
    281
                    assert!(matches!(*ret, MonoType::Var(_)));
    282
                }
    283
                _ => panic!("Expected function type"),
    284
            }
    285
        }
    286
    287
        #[test]
    288
        fn test_substitution() {
    289
            let mut subst = HashMap::new();
    290
            let var = TyVar(0);
    291
            subst.insert(var.clone(), MonoType::Int);
    292
    293
            let ty = MonoType::List(Box::new(MonoType::Var(var)));
    294
            let result = ty.substitute(&subst);
    295
    296
            assert_eq!(result, MonoType::List(Box::new(MonoType::Int)));
    297
        }
    298
    299
        #[test]
    300
        fn test_free_vars() {
    301
            let var1 = TyVar(0);
    302
            let var2 = TyVar(1);
    303
    304
            let ty = MonoType::Function(
    305
                Box::new(MonoType::Var(var1.clone())),
    306
                Box::new(MonoType::List(Box::new(MonoType::Var(var2.clone())))),
    307
            );
    308
    309
            let free = ty.free_vars();
    310
            assert_eq!(free.len(), 2);
    311
            assert!(free.contains(&var1));
    312
            assert!(free.contains(&var2));
    313
    314
            // Test that duplicate variables are deduplicated
    315
            let ty_dup = MonoType::Function(
    316
                Box::new(MonoType::Var(var1.clone())),
    317
                Box::new(MonoType::Var(var1.clone())),
    318
            );
    319
            let free_dup = ty_dup.free_vars();
    320
            assert_eq!(free_dup.len(), 1);
    321
            assert!(free_dup.contains(&var1));
    322
        }
    323
    }