type_lang/
ty.rs

1//! The type term: variables, constructors, and their application.
2
3use alloc::vec::Vec;
4use core::fmt;
5
6/// An inference variable — a placeholder for a type not yet known.
7///
8/// A `TyVar` is a 32-bit handle minted by [`Unifier::fresh`](crate::Unifier::fresh)
9/// and stable for the life of that unifier. It is deliberately opaque: there is no
10/// public constructor, so a variable can only come from the unifier that tracks
11/// it, and that unifier always knows how to resolve it.
12///
13/// A variable starts life unbound — it stands for "some type" — and unification
14/// may bind it to a concrete type or to another variable. Use
15/// [`Unifier::resolve`](crate::Unifier::resolve) to read back what a variable has
16/// become; a variable that is still unbound resolves to itself.
17///
18/// # Examples
19///
20/// ```
21/// use type_lang::Unifier;
22///
23/// let mut unifier = Unifier::new();
24/// let a = unifier.fresh();
25/// let b = unifier.fresh();
26///
27/// // Variables are minted in order and stay distinct.
28/// assert_eq!(a.to_u32(), 0);
29/// assert_eq!(b.to_u32(), 1);
30/// assert_ne!(a, b);
31/// ```
32#[cfg_attr(feature = "serde", derive(serde::Serialize, serde::Deserialize))]
33#[derive(Clone, Copy, Debug, PartialEq, Eq, PartialOrd, Ord, Hash)]
34pub struct TyVar(u32);
35
36impl TyVar {
37    /// Wraps a raw index. Internal: only a [`Unifier`](crate::Unifier) mints
38    /// variables, so that every variable in circulation belongs to a unifier that
39    /// can resolve it.
40    #[inline]
41    pub(crate) const fn from_index(index: u32) -> Self {
42        Self(index)
43    }
44
45    /// Returns the raw index this variable wraps.
46    ///
47    /// The value is the variable's creation order, starting at `0`. It is useful as
48    /// a dense key into a side table of per-variable data; prefer passing the
49    /// opaque `TyVar` itself wherever a handle will do.
50    ///
51    /// # Examples
52    ///
53    /// ```
54    /// use type_lang::Unifier;
55    ///
56    /// let mut unifier = Unifier::new();
57    /// let v = unifier.fresh();
58    /// assert_eq!(v.to_u32(), 0);
59    /// ```
60    #[inline]
61    #[must_use]
62    pub const fn to_u32(self) -> u32 {
63        self.0
64    }
65}
66
67/// A type constructor — the name a concrete type is built from.
68///
69/// A `TyCon` is an opaque 32-bit tag that the *consumer* assigns meaning to. This
70/// crate stores and compares constructors but never interprets them, so a language
71/// front-end is free to map its own primitives and type formers onto whatever tags
72/// it likes:
73///
74/// ```
75/// use type_lang::TyCon;
76///
77/// const INT: TyCon = TyCon::new(0);
78/// const BOOL: TyCon = TyCon::new(1);
79/// const FUNCTION: TyCon = TyCon::new(2);
80/// const LIST: TyCon = TyCon::new(3);
81/// ```
82///
83/// Two constructors are the same type former when their tags are equal, so keeping
84/// the tag assignment stable across a compilation is the caller's responsibility —
85/// a `const` table, as above, is the usual way.
86#[cfg_attr(feature = "serde", derive(serde::Serialize, serde::Deserialize))]
87#[derive(Clone, Copy, Debug, PartialEq, Eq, PartialOrd, Ord, Hash)]
88pub struct TyCon(u32);
89
90impl TyCon {
91    /// Creates a constructor from a tag.
92    ///
93    /// The tag identifies the type former; the caller chooses the numbering and is
94    /// responsible for keeping it consistent. Equal tags are treated as the same
95    /// constructor during unification.
96    ///
97    /// # Examples
98    ///
99    /// ```
100    /// use type_lang::TyCon;
101    ///
102    /// let int = TyCon::new(0);
103    /// assert_eq!(int.to_u32(), 0);
104    /// ```
105    #[inline]
106    #[must_use]
107    pub const fn new(tag: u32) -> Self {
108        Self(tag)
109    }
110
111    /// Returns the raw tag this constructor wraps.
112    #[inline]
113    #[must_use]
114    pub const fn to_u32(self) -> u32 {
115        self.0
116    }
117}
118
119/// A type term: either an inference variable or a constructor applied to arguments.
120///
121/// This is the structural core every concrete type is expressed in. A type is one
122/// of two shapes:
123///
124/// - [`Var`](Self::Var) — an inference [`TyVar`], possibly still unbound.
125/// - [`App`](Self::App) — a [`TyCon`] applied to zero or more argument types. A
126///   primitive like `int` is the zero-argument case; a `List<int>` is `List`
127///   applied to `int`; a function `(A) -> B` is some `->` constructor applied to
128///   `A` and `B`.
129///
130/// The same two shapes describe primitives, generics, functions, tuples, and any
131/// other first-order type former — the meaning of each constructor is the
132/// consumer's to define. Build terms with the [`var`](Self::var),
133/// [`con`](Self::con), and [`app`](Self::app) constructors.
134///
135/// # Examples
136///
137/// ```
138/// use type_lang::{TyCon, Type, Unifier};
139///
140/// const INT: TyCon = TyCon::new(0);
141/// const LIST: TyCon = TyCon::new(1);
142///
143/// let mut unifier = Unifier::new();
144/// let element = unifier.fresh();
145///
146/// // List<?element>
147/// let list_of = Type::app(LIST, [Type::var(element)]);
148/// // List<int>
149/// let list_int = Type::app(LIST, [Type::con(INT)]);
150///
151/// unifier.unify(&list_of, &list_int).expect("same constructor");
152/// assert_eq!(unifier.resolve(&Type::var(element)), Type::con(INT));
153/// ```
154#[cfg_attr(feature = "serde", derive(serde::Serialize, serde::Deserialize))]
155#[derive(Clone, Debug, PartialEq, Eq, Hash)]
156pub enum Type {
157    /// An inference variable.
158    Var(TyVar),
159    /// A constructor applied to its arguments. The argument list is empty for a
160    /// nullary constructor such as a primitive.
161    App(TyCon, Vec<Type>),
162}
163
164impl Type {
165    /// Builds a variable type from a [`TyVar`].
166    ///
167    /// # Examples
168    ///
169    /// ```
170    /// use type_lang::{Type, Unifier};
171    ///
172    /// let mut unifier = Unifier::new();
173    /// let v = unifier.fresh();
174    /// let ty = Type::var(v);
175    /// assert_eq!(ty.as_var(), Some(v));
176    /// ```
177    #[inline]
178    #[must_use]
179    pub const fn var(var: TyVar) -> Self {
180        Self::Var(var)
181    }
182
183    /// Builds a nullary constructor type, such as a primitive.
184    ///
185    /// This is the zero-argument case of [`app`](Self::app); `Type::con(c)` and
186    /// `Type::app(c, [])` are the same term.
187    ///
188    /// # Examples
189    ///
190    /// ```
191    /// use type_lang::{TyCon, Type};
192    ///
193    /// const UNIT: TyCon = TyCon::new(0);
194    /// let ty = Type::con(UNIT);
195    /// assert_eq!(ty.head(), Some(UNIT));
196    /// assert!(ty.args().is_empty());
197    /// ```
198    #[inline]
199    #[must_use]
200    pub const fn con(head: TyCon) -> Self {
201        Self::App(head, Vec::new())
202    }
203
204    /// Builds a constructor applied to a list of argument types.
205    ///
206    /// Accepts anything that turns into a `Vec<Type>` — an array, a `Vec`, or any
207    /// iterator's `collect()` — so a fixed-arity type reads naturally:
208    ///
209    /// ```
210    /// use type_lang::{TyCon, Type, Unifier};
211    ///
212    /// const FUNCTION: TyCon = TyCon::new(0);
213    /// const INT: TyCon = TyCon::new(1);
214    ///
215    /// let mut unifier = Unifier::new();
216    /// let result = unifier.fresh();
217    ///
218    /// // (int) -> ?result
219    /// let signature = Type::app(FUNCTION, [Type::con(INT), Type::var(result)]);
220    /// assert_eq!(signature.head(), Some(FUNCTION));
221    /// assert_eq!(signature.args().len(), 2);
222    /// ```
223    #[inline]
224    #[must_use]
225    pub fn app(head: TyCon, args: impl Into<Vec<Type>>) -> Self {
226        Self::App(head, args.into())
227    }
228
229    /// Returns the variable if this is a [`Var`](Self::Var), otherwise `None`.
230    ///
231    /// # Examples
232    ///
233    /// ```
234    /// use type_lang::{TyCon, Type, Unifier};
235    ///
236    /// let mut unifier = Unifier::new();
237    /// let v = unifier.fresh();
238    /// assert_eq!(Type::var(v).as_var(), Some(v));
239    /// assert_eq!(Type::con(TyCon::new(0)).as_var(), None);
240    /// ```
241    #[inline]
242    #[must_use]
243    pub const fn as_var(&self) -> Option<TyVar> {
244        match self {
245            Self::Var(v) => Some(*v),
246            Self::App(..) => None,
247        }
248    }
249
250    /// Returns the head constructor if this is an [`App`](Self::App), otherwise
251    /// `None` (a variable has no constructor).
252    ///
253    /// # Examples
254    ///
255    /// ```
256    /// use type_lang::{TyCon, Type, Unifier};
257    ///
258    /// const INT: TyCon = TyCon::new(0);
259    /// let mut unifier = Unifier::new();
260    ///
261    /// assert_eq!(Type::con(INT).head(), Some(INT));
262    /// assert_eq!(Type::var(unifier.fresh()).head(), None);
263    /// ```
264    #[inline]
265    #[must_use]
266    pub const fn head(&self) -> Option<TyCon> {
267        match self {
268            Self::App(head, _) => Some(*head),
269            Self::Var(_) => None,
270        }
271    }
272
273    /// Returns the argument types of an [`App`](Self::App), or an empty slice for a
274    /// variable or a nullary constructor.
275    ///
276    /// # Examples
277    ///
278    /// ```
279    /// use type_lang::{TyCon, Type};
280    ///
281    /// const PAIR: TyCon = TyCon::new(0);
282    /// const INT: TyCon = TyCon::new(1);
283    ///
284    /// let pair = Type::app(PAIR, [Type::con(INT), Type::con(INT)]);
285    /// assert_eq!(pair.args().len(), 2);
286    /// assert!(Type::con(INT).args().is_empty());
287    /// ```
288    #[inline]
289    #[must_use]
290    pub fn args(&self) -> &[Type] {
291        match self {
292            Self::App(_, args) => args,
293            Self::Var(_) => &[],
294        }
295    }
296
297    /// Returns `true` if this term is an inference variable.
298    #[inline]
299    #[must_use]
300    pub const fn is_var(&self) -> bool {
301        matches!(self, Self::Var(_))
302    }
303}
304
305impl fmt::Display for Type {
306    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
307        match self {
308            Self::Var(v) => write!(f, "?{}", v.to_u32()),
309            Self::App(head, args) => {
310                write!(f, "#{}", head.to_u32())?;
311                if let [first, rest @ ..] = args.as_slice() {
312                    write!(f, "({first}")?;
313                    for arg in rest {
314                        write!(f, ", {arg}")?;
315                    }
316                    write!(f, ")")?;
317                }
318                Ok(())
319            }
320        }
321    }
322}
323
324#[cfg(test)]
325mod tests {
326    extern crate alloc;
327    use alloc::string::ToString;
328    use alloc::vec;
329
330    use super::*;
331
332    const INT: TyCon = TyCon::new(0);
333    const PAIR: TyCon = TyCon::new(5);
334
335    #[test]
336    fn test_con_is_app_with_no_arguments() {
337        assert_eq!(Type::con(INT), Type::app(INT, vec![]));
338    }
339
340    #[test]
341    fn test_accessors_split_var_from_app() {
342        let v = TyVar::from_index(2);
343        assert_eq!(Type::var(v).as_var(), Some(v));
344        assert_eq!(Type::var(v).head(), None);
345        assert!(Type::var(v).is_var());
346
347        let pair = Type::app(PAIR, vec![Type::con(INT), Type::var(v)]);
348        assert_eq!(pair.as_var(), None);
349        assert_eq!(pair.head(), Some(PAIR));
350        assert_eq!(pair.args().len(), 2);
351        assert!(!pair.is_var());
352    }
353
354    #[test]
355    fn test_display_renders_structure() {
356        assert_eq!(Type::var(TyVar::from_index(4)).to_string(), "?4");
357        assert_eq!(Type::con(INT).to_string(), "#0");
358        let nested = Type::app(PAIR, vec![Type::con(INT), Type::var(TyVar::from_index(1))]);
359        assert_eq!(nested.to_string(), "#5(#0, ?1)");
360    }
361}
type_lang/ty.rs

type_lang/
ty.rs
