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

    Line
    Count
    Source
    1
    //! Unification algorithm for type inference
    2
    3
    use crate::middleend::types::{MonoType, Substitution, TyVar};
    4
    use anyhow::{bail, Result};
    5
    use std::collections::HashMap;
    6
    7
    /// Unification engine for type inference
    8
    pub struct Unifier {
    9
        subst: Substitution,
    10
    }
    11
    12
    impl Unifier {
    13
        #[must_use]
    14
    0
        pub fn new() -> Self {
    15
    0
            Unifier {
    16
    0
                subst: HashMap::new(),
    17
    0
            }
    18
    0
        }
    19
    20
        /// Get the current substitution
    21
        #[must_use]
    22
    0
        pub fn substitution(&self) -> &Substitution {
    23
    0
            &self.subst
    24
    0
        }
    25
    26
        /// Apply current substitution to a type
    27
        #[must_use]
    28
    0
        pub fn apply(&self, ty: &MonoType) -> MonoType {
    29
    0
            ty.substitute(&self.subst)
    30
    0
        }
    31
    32
        /// Unify two types, updating the substitution
    33
        ///
    34
        /// # Errors
    35
        ///
    36
        /// Returns an error if the types cannot be unified (type mismatch or occurs check failure)
    37
        /// # Errors
    38
        ///
    39
        /// Returns an error if the operation fails
    40
    0
        pub fn unify(&mut self, t1: &MonoType, t2: &MonoType) -> Result<()> {
    41
    0
            let t1 = self.apply(t1);
    42
    0
            let t2 = self.apply(t2);
    43
    44
    0
            match (t1, t2) {
    45
    0
                (MonoType::Var(v1), MonoType::Var(v2)) if v1 == v2 => Ok(()),
    46
    0
                (MonoType::Var(v), t) | (t, MonoType::Var(v)) => self.bind(&v, &t),
    47
                (MonoType::Int, MonoType::Int)
    48
                | (MonoType::Float, MonoType::Float)
    49
                | (MonoType::Bool, MonoType::Bool)
    50
                | (MonoType::String, MonoType::String)
    51
    0
                | (MonoType::Unit, MonoType::Unit) => Ok(()),
    52
    0
                (MonoType::Named(n1), MonoType::Named(n2)) if n1 == n2 => Ok(()),
    53
    0
                (MonoType::Function(a1, r1), MonoType::Function(a2, r2)) => {
    54
    0
                    self.unify(&a1, &a2)?;
    55
    0
                    self.unify(&r1, &r2)
    56
                }
    57
    0
                (MonoType::List(e1), MonoType::List(e2)) => self.unify(&e1, &e2),
    58
    0
                (MonoType::Optional(i1), MonoType::Optional(i2)) => self.unify(&i1, &i2),
    59
    0
                (MonoType::Result(ok1, err1), MonoType::Result(ok2, err2)) => {
    60
    0
                    self.unify(&ok1, &ok2)?;
    61
    0
                    self.unify(&err1, &err2)
    62
                }
    63
    0
                (MonoType::DataFrame(cols1), MonoType::DataFrame(cols2)) => {
    64
                    // DataFrames unify if they have the same columns with the same types
    65
    0
                    if cols1.len() != cols2.len() {
    66
    0
                        bail!("Cannot unify DataFrames with different column counts");
    67
    0
                    }
    68
    0
                    for ((name1, ty1), (name2, ty2)) in cols1.iter().zip(cols2.iter()) {
    69
    0
                        if name1 != name2 {
    70
    0
                            bail!(
    71
    0
                                "Cannot unify DataFrames with different column names: {} vs {}",
    72
                                name1,
    73
                                name2
    74
                            );
    75
    0
                        }
    76
    0
                        self.unify(ty1, ty2)?;
    77
                    }
    78
    0
                    Ok(())
    79
                }
    80
    0
                (MonoType::Series(ty1), MonoType::Series(ty2)) => self.unify(&ty1, &ty2),
    81
    0
                (t1, t2) => bail!("Cannot unify {} with {}", t1, t2),
    82
            }
    83
    0
        }
    84
    85
        /// Bind a type variable to a type
    86
    0
        fn bind(&mut self, var: &TyVar, ty: &MonoType) -> Result<()> {
    87
            // Occurs check: ensure var doesn't occur in ty
    88
    0
            if Self::occurs(var, ty) {
    89
    0
                bail!("Infinite type: {} occurs in {}", var, ty);
    90
    0
            }
    91
    92
            // Apply the binding
    93
    0
            self.subst.insert(var.clone(), ty.clone());
    94
    95
            // Update existing substitutions
    96
    0
            let updated: Substitution = self
    97
    0
                .subst
    98
    0
                .iter()
    99
    0
                .map(|(k, v)| {
    100
    0
                    if k == var {
    101
    0
                        (k.clone(), ty.clone())
    102
                    } else {
    103
    0
                        (k.clone(), v.substitute(&[(var.clone(), ty.clone())].into()))
    104
                    }
    105
    0
                })
    106
    0
                .collect();
    107
    0
            self.subst = updated;
    108
    109
    0
            Ok(())
    110
    0
        }
    111
    112
        /// Check if a type variable occurs in a type (occurs check)
    113
    0
        fn occurs(var: &TyVar, ty: &MonoType) -> bool {
    114
    0
            match ty {
    115
    0
                MonoType::Var(v) => v == var,
    116
    0
                MonoType::Function(arg, ret) => Self::occurs(var, arg) || Self::occurs(var, ret),
    117
    0
                MonoType::List(elem) => Self::occurs(var, elem),
    118
    0
                MonoType::Optional(inner) | MonoType::Series(inner) | MonoType::Reference(inner) => {
    119
    0
                    Self::occurs(var, inner)
    120
                }
    121
    0
                MonoType::Result(ok, err) => Self::occurs(var, ok) || Self::occurs(var, err),
    122
    0
                MonoType::DataFrame(columns) => {
    123
    0
                    columns.iter().any(|(_, col_ty)| Self::occurs(var, col_ty))
    124
                }
    125
    0
                MonoType::Tuple(types) => types.iter().any(|ty| Self::occurs(var, ty)),
    126
    0
                _ => false,
    127
            }
    128
    0
        }
    129
    130
        /// Solve a type variable to its final type
    131
        #[must_use]
    132
    0
        pub fn solve(&self, var: &TyVar) -> MonoType {
    133
    0
            self.subst
    134
    0
                .get(var)
    135
    0
                .map_or_else(|| MonoType::Var(var.clone()), |ty| self.apply(ty))
    136
    0
        }
    137
    }
    138
    139
    impl Default for Unifier {
    140
    0
        fn default() -> Self {
    141
    0
            Self::new()
    142
    0
        }
    143
    }
    144
    145
    #[cfg(test)]
    146
    #[allow(clippy::unwrap_used, clippy::panic)]
    147
    mod tests {
    148
        use super::*;
    149
    150
        #[test]
    151
        fn test_unify_same_types() {
    152
            let mut unifier = Unifier::new();
    153
            assert!(unifier.unify(&MonoType::Int, &MonoType::Int).is_ok());
    154
            assert!(unifier.unify(&MonoType::Bool, &MonoType::Bool).is_ok());
    155
            assert!(unifier.unify(&MonoType::String, &MonoType::String).is_ok());
    156
        }
    157
    158
        #[test]
    159
        fn test_unify_different_types() {
    160
            let mut unifier = Unifier::new();
    161
            assert!(unifier.unify(&MonoType::Int, &MonoType::Bool).is_err());
    162
            assert!(unifier.unify(&MonoType::String, &MonoType::Int).is_err());
    163
        }
    164
    165
        #[test]
    166
        fn test_unify_with_var() {
    167
            let mut unifier = Unifier::new();
    168
            let var = TyVar(0);
    169
    170
            assert!(unifier
    171
                .unify(&MonoType::Var(var.clone()), &MonoType::Int)
    172
                .is_ok());
    173
            assert_eq!(unifier.solve(&var), MonoType::Int);
    174
        }
    175
    176
        #[test]
    177
        fn test_unify_functions() {
    178
            let mut unifier = Unifier::new();
    179
            let var = TyVar(0);
    180
    181
            let f1 = MonoType::Function(
    182
                Box::new(MonoType::Int),
    183
                Box::new(MonoType::Var(var.clone())),
    184
            );
    185
            let f2 = MonoType::Function(Box::new(MonoType::Int), Box::new(MonoType::Bool));
    186
    187
            assert!(unifier.unify(&f1, &f2).is_ok());
    188
            assert_eq!(unifier.solve(&var), MonoType::Bool);
    189
        }
    190
    191
        #[test]
    192
        fn test_unify_lists() {
    193
            let mut unifier = Unifier::new();
    194
            let var = TyVar(0);
    195
    196
            let l1 = MonoType::List(Box::new(MonoType::Var(var.clone())));
    197
            let l2 = MonoType::List(Box::new(MonoType::String));
    198
    199
            assert!(unifier.unify(&l1, &l2).is_ok());
    200
            assert_eq!(unifier.solve(&var), MonoType::String);
    201
        }
    202
    203
        #[test]
    204
        fn test_occurs_check() {
    205
            let mut unifier = Unifier::new();
    206
            let var = TyVar(0);
    207
    208
            // Try to unify τ0 with [τ0] - should fail (infinite type)
    209
            let infinite = MonoType::List(Box::new(MonoType::Var(var.clone())));
    210
            assert!(unifier.unify(&MonoType::Var(var), &infinite).is_err());
    211
        }
    212
    213
        #[test]
    214
        fn test_transitive_unification() {
    215
            let mut unifier = Unifier::new();
    216
            let var1 = TyVar(0);
    217
            let var2 = TyVar(1);
    218
    219
            // τ0 = τ1
    220
            assert!(unifier
    221
                .unify(&MonoType::Var(var1.clone()), &MonoType::Var(var2.clone()))
    222
                .is_ok());
    223
    224
            // τ1 = Int
    225
            assert!(unifier
    226
                .unify(&MonoType::Var(var2.clone()), &MonoType::Int)
    227
                .is_ok());
    228
    229
            // Now τ0 should also be Int
    230
            assert_eq!(unifier.solve(&var1), MonoType::Int);
    231
            assert_eq!(unifier.solve(&var2), MonoType::Int);
    232
        }
    233
    }