rusttyc/types.rs
1//! This mod contains everything related to types and collections of types (type tables).
2//!
3//! # Content
4//! * [Variant] is a trait representing the variant of an abstract type that will be inferred during the type checking procedure.
5//! * [Constructable]: A variant is constructable if it can be transformed into a concrete type, i.e., [Constructable::Type].
6//! * [TypeTable] and [PreliminaryTypeTable] are mappings from a [TcKey] to a concrete [Constructable::Type] or [Preliminary] type.
7
8use std::{collections::HashMap, fmt::Debug};
9
10use crate::TcKey;
11
12/// A variant that will be inferred during the type checking procedure.
13///
14/// # Requirements
15/// The variant needs to follow a [lattice structure](https://en.wikipedia.org/wiki/Lattice_(order)) where the top element is the least constrained, most abstract type variant
16/// possible.
17/// ## Refinement
18/// The top value needs to be provided by the [Variant::top()] function. Types will be refined
19/// successively using the fallible [Variant::meet()] function. If the types are incompatible, i.e., would result in a contradictory
20/// type, the meet needs to return a [Variant::Err]. Note that [Variant::meet()] needs to follow the rules of abstract meets.
21/// Intuitively, these are:
22/// * The result of a meet needs to be more or equally concrete than either argument.
23/// * Meeting two variants returns the greatest upper bound, i.e., the type variant that is more or equally concrete to either argument _and_ there is no other, less concrete type meeting this requirement.
24/// This especially entails that meeting any type `T` with an unconstrained type returns `T`.
25/// The arguments of the meet functions are [Partial], i.e., the combination of a variant and the least number of children the respective type has.
26/// This is of particular interest for types that are not fully resolved and thus do not have a fixed arity, yet. An unconstained type variant could have
27/// a sub-type because it will be later determined to be an "Option" or "Tuple" type. More details in the next section.
28///
29/// ## Arity
30/// Type can be recursive, i.e., they have a number of subtypes, their "children".
31/// An integer, for example, has no children and is thus 0-ary. An optional type on the other hand is 1-ary, tuples might have an arbitrary arity.
32/// During the inference process, the arity might be undetermined: the unconstrained type will resolve to something with an arity, but the value is not clear, yet.
33/// Hence, its least arity is initially 0 and potentially increases when more information was collected.
34///
35/// The type checking procedure keeps track of types and their potential children.
36/// For this, it requires some guarantees when it comes to the arity:
37///
38/// ### Arity Stability
39/// The meet of two variants must not _reduce_ its arity. For example, meeting a pair with fixed arity 2 and a triple with fixed arity 3 may not result in a variant with fixed arity 1.
40/// It may, however, result in a variant with variable arity.
41///
42/// # Example
43/// For a full example of an abstract type system, refer to the [crate documentation](../index.html) and the examples.
44///
45/// # Context
46/// If the variant requires a context for the meet and/or equality operation, refer to [ContextSensitiveVariant].
47/// Each [Variant] automatically implements [ContextSensitiveVariant].
48///
49pub trait Variant: Sized + Clone + Debug + Eq {
50 /// Result of a meet of two incompatible type, i.e., it represents a type contradiction.
51 /// May contain information regarding why the meet failed. The error will be wrapped into a [crate::TcErr] providing contextual information.
52 type Err: Debug;
53
54 /// Returns the unconstrained, most abstract type.
55 fn top() -> Self;
56
57 /// Attempts to meet two variants respecting their currently-determined potentially variable arity.
58 /// Refer to [Variant] for the responsibilities of this function.
59 /// In particular: `usize::max(lhs.least_arity, rhs.least_arity) <= result.least_arity`
60 /// In the successful case, the variant and arity of the partial have to match, i.e., if the [Arity]
61 /// is fixed with value `n`, then [Partial::least_arity] needs to be `n` as well.
62 fn meet(lhs: Partial<Self>, rhs: Partial<Self>) -> Result<Partial<Self>, Self::Err>;
63
64 /// Indicates whether the variant has a fixed arity. Note that this values does not have to be constant over all instances of the variant.
65 /// A tuple, for example, might have a variable arity until the inferrence reaches a point where it is determined to be a pair or a triple.
66 /// The pair and triple are both represented by the same type variant and have a fixed, non-specific arity. Before obtaining this information,
67 /// the tuple has a variable arity and potentially a different variant.
68 fn arity(&self) -> Arity;
69}
70
71/// A [Variant] which requires a context for meet operations and equality checks.
72///
73/// See [Variant] for general information and requirements on the implementation.
74/// The context will ever only be borrowed without further requirements on it, in particular,
75/// it does not have to implement [Clone].
76pub trait ContextSensitiveVariant: Sized + Clone + Debug {
77 /// Result of a meet of two incompatible type, i.e., it represents a type contradiction.
78 /// May contain information regarding why the meet failed. The error will be wrapped into a [crate::TcErr] providing contextual information.
79 type Err: Debug;
80
81 /// Represents the meet- and equality context.
82 type Context: Debug;
83
84 /// Returns the unconstrained, most abstract type.
85 fn top() -> Self;
86
87 /// Attempts to meet two variants respecting their currently-determined potentially variable arity.
88 /// Refer to [Variant] for the responsibilities of this function.
89 /// In particular: `usize::max(lhs.least_arity, rhs.least_arity) <= result.least_arity`
90 /// In the successful case, the variant and arity of the partial have to match, i.e., if the [Arity]
91 /// is fixed with value `n`, then [Partial::least_arity] needs to be `n` as well.
92 fn meet(lhs: Partial<Self>, rhs: Partial<Self>, ctx: &Self::Context) -> Result<Partial<Self>, Self::Err>;
93
94 /// Indicates whether the variant has a fixed arity. Note that this values does not have to be constant over all instances of the variant.
95 /// A tuple, for example, might have a variable arity until the inferrence reaches a point where it is determined to be a pair or a triple.
96 /// The pair and triple are both represented by the same type variant and have a fixed, non-specific arity. Before obtaining this information,
97 /// the tuple has a variable arity and potentially a different variant.
98 fn arity(&self, ctx: &Self::Context) -> Arity;
99
100 /// Context-sensitive version of [Eq]. All rules apply.
101 fn equal(this: &Self, that: &Self, ctx: &Self::Context) -> bool;
102}
103
104impl<V: Variant> ContextSensitiveVariant for V {
105 type Err = V::Err;
106
107 type Context = ();
108
109 fn top() -> Self {
110 V::top()
111 }
112
113 fn meet(lhs: Partial<Self>, rhs: Partial<Self>, _ctx: &Self::Context) -> Result<Partial<Self>, Self::Err> {
114 V::meet(lhs, rhs)
115 }
116
117 fn arity(&self, _ctx: &Self::Context) -> Arity {
118 self.arity()
119 }
120
121 fn equal(this: &Self, that: &Self, _ctx: &Self::Context) -> bool {
122 this == that
123 }
124}
125
126/// Represents the arity of a [Variant] or [ContextSensitiveVariant].
127#[derive(Debug, Clone, Copy)]
128pub enum Arity {
129 /// The arity is variable, i.e., it does not have a specific value.
130 Variable,
131 /// The arity has a fixed value.
132 Fixed(usize),
133}
134
135impl Arity {
136 /// Transform `self` into an option, i.e., it will yield a `Some` with its arity if defined and `None` otherwise.
137 pub(crate) fn to_opt(self) -> Option<usize> {
138 match self {
139 Arity::Variable => None,
140 Arity::Fixed(n) => Some(n),
141 }
142 }
143}
144
145/// Partial is a container for a [ContextSensitiveVariant] and the least arity a particular instance of this variant currently has. Only used for [ContextSensitiveVariant::meet()].
146///
147/// The `least_arity` indicates how many children this instance of the variance has according to the current state of the type checker.
148/// The value might increase in the future but never decrease.
149#[derive(Debug, Clone)]
150pub struct Partial<V: Sized> {
151 /// The variant represented by this `Partial`.
152 pub variant: V,
153 ///The least number of children the variant will have after completing the type check.
154 pub least_arity: usize,
155}
156
157/// Represents a preliminary output of the type check. Mainly used if [Variant] does not implement [Constructable].
158#[derive(Debug, Clone)]
159pub struct Preliminary<V: ContextSensitiveVariant> {
160 /// The type variant of the entity represented by this `Preliminary`.
161 pub variant: V,
162 /// The [TcKey]s of the children of this variant.
163 pub children: Vec<Option<TcKey>>,
164}
165
166/// A type table containing a [Preliminary] type for each [TcKey]. Mainly used if [ContextSensitiveVariant] does not implement [Constructable].
167pub type PreliminaryTypeTable<V> = HashMap<TcKey, Preliminary<V>>;
168/// A type table containing the constructed type of the inferred [ContextSensitiveVariant] for each [TcKey]. Requires [ContextSensitiveVariant] to implement [Constructable].
169pub type TypeTable<V> = HashMap<TcKey, <V as Constructable>::Type>;
170
171/// A type implementing this trait can potentially be transformed into a concrete representation. This transformation can fail.
172pub trait Constructable: ContextSensitiveVariant {
173 /// The result type of the attempted construction.
174 type Type: Clone + Debug;
175 /// Attempts to transform `self` into an more concrete `Self::Type`.
176 /// Returns a [ContextSensitiveVariant::Err] if the transformation fails. This error will be wrapped into a [crate::TcErr] to enrich it with contextual information.
177 fn construct(&self, children: &[Self::Type]) -> Result<Self::Type, <Self as ContextSensitiveVariant>::Err>;
178}