/home/noah/src/ruchy/src/middleend/types.rs

Source
//! Type system representation for Ruchy

use std::collections::HashMap;
use std::fmt;

/// Type variable for unification
#[derive(Debug, Clone, PartialEq, Eq, Hash)]
pub struct TyVar(pub u32);

impl fmt::Display for TyVar {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        write!(f, "τ{}", self.0)
    }
}

/// Monomorphic types in the Hindley-Milner system
#[derive(Debug, Clone, PartialEq)]
pub enum MonoType {
    /// Type variable (unknown type to be inferred)
    Var(TyVar),
    /// Primitive integer type
    Int,
    /// Primitive float type
    Float,
    /// Primitive boolean type
    Bool,
    /// String type
    String,
    /// Character type
    Char,
    /// Unit type ()
    Unit,
    /// Function type: T1 -> T2
    Function(Box<MonoType>, Box<MonoType>),
    /// List type: [T]
    List(Box<MonoType>),
    /// Tuple type: (T1, T2, ...)
    Tuple(Vec<MonoType>),
    /// Optional type: T?
    Optional(Box<MonoType>),
    /// Result type: Result<T, E>
    Result(Box<MonoType>, Box<MonoType>),
    /// Named type (user-defined or gradual typing 'Any')
    Named(String),
    /// Reference type: &T
    Reference(Box<MonoType>),
    /// `DataFrame` type with column names and their types
    DataFrame(Vec<(String, MonoType)>),
    /// Series type with element type
    Series(Box<MonoType>),
}

impl fmt::Display for MonoType {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        match self {
            MonoType::Var(v) => write!(f, "{v}"),
            MonoType::Int => write!(f, "i32"),
            MonoType::Float => write!(f, "f64"),
            MonoType::Bool => write!(f, "bool"),
            MonoType::String => write!(f, "String"),
            MonoType::Char => write!(f, "char"),
            MonoType::Unit => write!(f, "()"),
            MonoType::Function(arg, ret) => write!(f, "({arg} -> {ret})"),
            MonoType::List(elem) => write!(f, "[{elem}]"),
            MonoType::Optional(inner) => write!(f, "{inner}?"),
            MonoType::Result(ok, err) => write!(f, "Result<{ok}, {err}>"),
            MonoType::Tuple(types) => {
                write!(f, "(")?;
                for (i, ty) in types.iter().enumerate() {
                    if i > 0 {
                        write!(f, ", ")?;
                    }
                    write!(f, "{ty}")?;
                }
                write!(f, ")")
            }
            MonoType::Named(name) => write!(f, "{name}"),
            MonoType::Reference(inner) => write!(f, "&{inner}"),
            MonoType::DataFrame(columns) => {
                write!(f, "DataFrame[")?;
                for (i, (name, ty)) in columns.iter().enumerate() {
                    if i > 0 {
                        write!(f, ", ")?;
                    }
                    write!(f, "{name}: {ty}")?;
                }
                write!(f, "]")
            }
            MonoType::Series(dtype) => write!(f, "Series<{dtype}>"),
        }
    }
}

/// Polymorphic type scheme: ∀α₁...αₙ. τ
#[derive(Debug, Clone)]
pub struct TypeScheme {
    /// Quantified type variables
    pub vars: Vec<TyVar>,
    /// The monomorphic type
    pub ty: MonoType,
}

impl TypeScheme {
    /// Create a monomorphic type scheme (no quantified variables)
    #[must_use]
    pub fn mono(ty: MonoType) -> Self {
        TypeScheme {
            vars: Vec::new(),
            ty,
        }
    }

    /// Instantiate a type scheme with fresh type variables
    pub fn instantiate(&self, gen: &mut TyVarGenerator) -> MonoType {
        if self.vars.is_empty() {
            self.ty.clone()
        } else {
            let subst: HashMap<TyVar, MonoType> = self
                .vars
                .iter()
                .map6(|v| (v.clone(), MonoType::Var(gen.fresh())))
                .collect();
            self.ty.substitute(&subst)
        }
    }
}

impl fmt::Display for TypeScheme {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        if self.vars.is_empty() {
            write!(f, "{}", self.ty)
        } else {
            write!(f, "∀")?;
            for (i, var) in self.vars.iter().enumerate() {
                if i > 0 {
                    write!(f, ",")?;
                }
                write!(f, "{var}")?;
            }
            write!(f, ". {}", self.ty)
        }
    }
}

/// Type variable generator for fresh variables
pub struct TyVarGenerator {
    next: u32,
}

impl TyVarGenerator {
    #[must_use]
    pub fn new() -> Self {
        TyVarGenerator { next: 0 }
    }

    pub fn fresh(&mut self) -> TyVar {
        let var = TyVar(self.next);
        self.next += 1;
        var
    }
}

impl Default for TyVarGenerator {
    fn default() -> Self {
        Self::new()
    }
}

/// Substitution mapping from type variables to types
pub type Substitution = HashMap<TyVar, MonoType>;

impl MonoType {
    /// Apply a substitution to this type
    #[must_use]
    pub fn substitute(&self, subst: &Substitution) -> MonoType {
        match self {
            MonoType::Var(v) => subst.get(v).cloned().unwrap_or_else(|| self70.clone70()),
            MonoType::Function(arg, ret) => MonoType::Function(
                Box::new(arg.substitute(subst)),
                Box::new(ret.substitute(subst)),
            ),
            MonoType::List(elem) => MonoType::List(Box::new(elem.substitute(subst))),
            MonoType::Optional(inner) => MonoType::Optional(Box::new(inner.substitute(subst))),
            MonoType::Result(ok, err) => MonoType::Result(
                Box::new(ok.substitute(subst)),
                Box::new(err.substitute(subst)),
            ),
            MonoType::DataFrame(columns) => MonoType::DataFrame(
                columns
                    .iter()
                    .map3(|(name, ty)| (name.clone(), ty.substitute(subst)))
                    .collect(),
            ),
            MonoType::Series(dtype) => MonoType::Series(Box::new(dtype.substitute(subst))),
            MonoType::Reference(inner) => MonoType::Reference(Box::new(inner.substitute(subst))),
            MonoType::Tuple(types) => {
                MonoType::Tuple(types.iter().map(|ty| ty.substitute(subst)).collect())
            }
            _ => self.clone(),
        }
    }

    /// Get free type variables in this type
    #[must_use]
    pub fn free_vars(&self) -> Vec<TyVar> {
        use std::collections::HashSet;

        fn collect_vars(ty: &MonoType, vars: &mut HashSet<TyVar>) {
            match ty {
                MonoType::Var(v) => {
                    vars.insert(v.clone());
                }
                MonoType::Function(arg, ret) => {
                    collect_vars(arg, vars);
                    collect_vars(ret, vars);
                }
                MonoType::List(elem) => collect_vars(elem, vars),
                MonoType::Optional(inner)
                | MonoType::Series(inner)
                | MonoType::Reference(inner) => {
                    collect_vars(inner, vars);
                }
                MonoType::Result(ok, err) => {
                    collect_vars(ok, vars);
                    collect_vars(err, vars);
                }
                MonoType::DataFrame(columns) => {
                    for (_, ty) in columns {
                        collect_vars(ty, vars);
                    }
                }
                MonoType::Tuple(types) => {
                    for ty in types {
                        collect_vars(ty, vars);
                    }
                }
                _ => {}
            }
        }

        let mut vars = HashSet::new();
        collect_vars(self, &mut vars);
        vars.into_iter().collect()
    }
}

#[cfg(test)]
#[allow(clippy::unwrap_used, clippy::panic, clippy::expect_used)]
#[allow(clippy::unwrap_used, clippy::panic)]
mod tests {
    use super::*;

    #[test]
    fn test_type_display() {
        assert_eq!(MonoType::Int.to_string(), "i32");
        assert_eq!(MonoType::Bool.to_string(), "bool");
        assert_eq!(
            MonoType::Function(Box::new(MonoType::Int), Box::new(MonoType::Bool)).to_string(),
            "(i32 -> bool)"
        );
        assert_eq!(MonoType::List(Box::new(MonoType::Int)).to_string(), "[i32]");
    }

    #[test]
    fn test_type_scheme_instantiation() {
        let mut gen = TyVarGenerator::new();
        let var = gen.fresh();

        let scheme = TypeScheme {
            vars: vec![var.clone()],
            ty: MonoType::Function(
                Box::new(MonoType::Var(var.clone())),
                Box::new(MonoType::Var(var)),
            ),
        };

        let instantiated = scheme.instantiate(&mut gen);
        match instantiated {
            MonoType::Function(arg, ret) => {
                assert!(matches!0(*arg, MonoType::Var(_)));
                assert!(matches!0(*ret, MonoType::Var(_)));
            }
            _ => panic!("Expected function type"),
        }
    }

    #[test]
    fn test_substitution() {
        let mut subst = HashMap::new();
        let var = TyVar(0);
        subst.insert(var.clone(), MonoType::Int);

        let ty = MonoType::List(Box::new(MonoType::Var(var)));
        let result = ty.substitute(&subst);

        assert_eq!(result, MonoType::List(Box::new(MonoType::Int)));
    }

    #[test]
    fn test_free_vars() {
        let var1 = TyVar(0);
        let var2 = TyVar(1);

        let ty = MonoType::Function(
            Box::new(MonoType::Var(var1.clone())),
            Box::new(MonoType::List(Box::new(MonoType::Var(var2.clone())))),
        );

        let free = ty.free_vars();
        assert_eq!(free.len(), 2);
        assert!(free.contains(&var1));
        assert!(free.contains(&var2));

        // Test that duplicate variables are deduplicated
        let ty_dup = MonoType::Function(
            Box::new(MonoType::Var(var1.clone())),
            Box::new(MonoType::Var(var1.clone())),
        );
        let free_dup = ty_dup.free_vars();
        assert_eq!(free_dup.len(), 1);
        assert!(free_dup.contains(&var1));
    }
}

Coverage Report

Created: 2025-09-05 15:26

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	2	fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
12	2	write!(f, "τ{}", self.0)
13	2	}
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	19	fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
55	19	match self {
56	1	MonoType::Var(v) => write!(f, "{v}"),
57	8	MonoType::Int => write!(f, "i32"),
58	0	MonoType::Float => write!(f, "f64"),
59	6	MonoType::Bool => write!(f, "bool"),
60	1	MonoType::String => write!(f, "String"),
61	0	MonoType::Char => write!(f, "char"),
62	0	MonoType::Unit => write!(f, "()"),
63	1	MonoType::Function(arg, ret) => write!(f, "({arg} -> {ret})"),
64	2	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	19	}
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	196	pub fn mono(ty: MonoType) -> Self {
107	196	TypeScheme {
108	196	vars: Vec::new(),
109	196	ty,
110	196	}
111	196	}
112
113		/// Instantiate a type scheme with fresh type variables
114	31	pub fn instantiate(&self, gen: &mut TyVarGenerator) -> MonoType {
115	31	if self.vars.is_empty() {
116	25	self.ty.clone()
117		} else {
118	6	let subst: HashMap<TyVar, MonoType> = self
119	6	.vars
120	6	.iter()
121	9	. map6 (\|v\| (v.clone(), MonoType::Var(gen.fresh())))
122	6	.collect();
123	6	self.ty.substitute(&subst)
124		}
125	31	}
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	42	pub fn new() -> Self {
153	42	TyVarGenerator { next: 0 }
154	42	}
155
156	33	pub fn fresh(&mut self) -> TyVar {
157	33	let var = TyVar(self.next);
158	33	self.next += 1;
159	33	var
160	33	}
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	426	pub fn substitute(&self, subst: &Substitution) -> MonoType {
176	426	match self {
177	117	MonoType::Var(v) => subst.get(v).cloned().unwrap_or_else(\|\| self70 . clone70 ()),
178	64	MonoType::Function(arg, ret) => MonoType::Function(
179	64	Box::new(arg.substitute(subst)),
180	64	Box::new(ret.substitute(subst)),
181	64	),
182	12	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	3	MonoType::DataFrame(columns) => MonoType::DataFrame(
189	3	columns
190	3	.iter()
191	4	. map3 (\|(name, ty)\| (name.clone(), ty.substitute(subst)))
192	3	.collect(),
193		),
194	1	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	229	_ => self.clone(),
200		}
201	426	}
202
203		/// Get free type variables in this type
204		#[must_use]
205	69	pub fn free_vars(&self) -> Vec<TyVar> {
206		use std::collections::HashSet;
207
208	244	fn collect_vars(ty: &MonoType, vars: &mut HashSet<TyVar>) {
209	244	match ty {
210	31	MonoType::Var(v) => {
211	31	vars.insert(v.clone());
212	31	}
213	87	MonoType::Function(arg, ret) => {
214	87	collect_vars(arg, vars);
215	87	collect_vars(ret, vars);
216	87	}
217	1	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	125	_ => {}
238		}
239	244	}
240
241	69	let mut vars = HashSet::new();
242	69	collect_vars(self, &mut vars);
243	69	vars.into_iter().collect()
244	69	}
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	1	fn test_type_display() {
255	1	assert_eq!(MonoType::Int.to_string(), "i32");
256	1	assert_eq!(MonoType::Bool.to_string(), "bool");
257	1	assert_eq!(
258	1	MonoType::Function(Box::new(MonoType::Int), Box::new(MonoType::Bool)).to_string(),
259		"(i32 -> bool)"
260		);
261	1	assert_eq!(MonoType::List(Box::new(MonoType::Int)).to_string(), "[i32]");
262	1	}
263
264		#[test]
265	1	fn test_type_scheme_instantiation() {
266	1	let mut gen = TyVarGenerator::new();
267	1	let var = gen.fresh();
268
269	1	let scheme = TypeScheme {
270	1	vars: vec![var.clone()],
271	1	ty: MonoType::Function(
272	1	Box::new(MonoType::Var(var.clone())),
273	1	Box::new(MonoType::Var(var)),
274	1	),
275	1	};
276
277	1	let instantiated = scheme.instantiate(&mut gen);
278	1	match instantiated {
279	1	MonoType::Function(arg, ret) => {
280	1	assert!( matches!0 (*arg, MonoType::Var(_)));
281	1	assert!( matches!0 (*ret, MonoType::Var(_)));
282		}
283	0	_ => panic!("Expected function type"),
284		}
285	1	}
286
287		#[test]
288	1	fn test_substitution() {
289	1	let mut subst = HashMap::new();
290	1	let var = TyVar(0);
291	1	subst.insert(var.clone(), MonoType::Int);
292
293	1	let ty = MonoType::List(Box::new(MonoType::Var(var)));
294	1	let result = ty.substitute(&subst);
295
296	1	assert_eq!(result, MonoType::List(Box::new(MonoType::Int)));
297	1	}
298
299		#[test]
300	1	fn test_free_vars() {
301	1	let var1 = TyVar(0);
302	1	let var2 = TyVar(1);
303
304	1	let ty = MonoType::Function(
305	1	Box::new(MonoType::Var(var1.clone())),
306	1	Box::new(MonoType::List(Box::new(MonoType::Var(var2.clone())))),
307	1	);
308
309	1	let free = ty.free_vars();
310	1	assert_eq!(free.len(), 2);
311	1	assert!(free.contains(&var1));
312	1	assert!(free.contains(&var2));
313
314		// Test that duplicate variables are deduplicated
315	1	let ty_dup = MonoType::Function(
316	1	Box::new(MonoType::Var(var1.clone())),
317	1	Box::new(MonoType::Var(var1.clone())),
318	1	);
319	1	let free_dup = ty_dup.free_vars();
320	1	assert_eq!(free_dup.len(), 1);
321	1	assert!(free_dup.contains(&var1));
322	1	}
323		}