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}