/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()
                .map(|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(|| self.clone()),
            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()
                    .map(|(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!(*arg, MonoType::Var(_)));
                assert!(matches!(*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-08 21: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	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		}