1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236
//! This mod contains everything related to types and collections of types (type tables). //! //! # Content //! * [`Abstract`](trait.Abstract.html) is a trait representing abstract types that will //! be inferred during the type checking procedure. //! * Reification is the process of transforming an abstract type into a concrete one. //! This process can be fallible or infallible, represented by [`Reifiable`](trait.Reifiable.html), //! [`TryReifiable`](trait.TryReifiable.html), and [`ReificationErr`](enum.ReificationErr.html). //! * Generalization is the infallible process of transforming a concrete type into an abstract one represented by [`Generalizable`](trait.Generalizable.html) //! * [`TypeTable`](trait.TypeTable.html) contains a mapping from a [`TcKey`](../struct.TcKey.html) to an [`Abstract`](trait.Abstract.html) or reified type. use crate::TcKey; use std::collections::HashMap; use std::{fmt::Debug, ops::Index}; /// An abstract type that will be inferred during the type checking procedure. /// /// This trait that needs to be implemented by all (rust-) types that represent a type in the type checking procedure. /// /// # Requirements /// The abstract types need to follow a [lattice structure](https://en.wikipedia.org/wiki/Lattice_(order)) where the top element is the least constrained, most abstract type /// possible. /// ## Refinement /// This value needs to be provided by the `Abstract::unconstrained` function. Types will be refined /// successively using the fallible meet function. If the types are incompatible, i.e., would result in a contradictory /// type, the meet needs to return a `Result::Err`. Otherwise, it returns a `Result::Ok` containing the resulting type. /// The function needs to follow the rules for abstract meets. Intuitively, these are: /// * The result of a meet needs to be more or equally concrete than either argument. /// * Meeting two types returns the greatest upper bound, i.e., the type that is more or equally concrete to either argument _and_ there is no other, less concrete type meeting this requirement. /// This especially entails that meeting any type `T` with an unconstrained type returns `T`. /// /// ## Variants /// Type can have variants. An integer, for example, has the 0-ary variant identifying it as integers. An optional type on the other hand is 1-ary, i.e., it has one sub-type. /// Unconstrained type might not have a variant at all. /// /// The type checking procedure needs to construct and destruct types based on their variant. /// * _Construction_ works over `Abstract::from_tag` taking an array of children, i.e., sub-types, and returning an abstract type. /// * _Destruction_ works over `Abstract::variant` to obtain information about the variant itself plus `Abstract::variant_arity` to get its arity. Access to individual subtypes is not required. /// /// ### Variant Stability /// Not every type has a defined variant. However, it needs to comply with two rules: /// * If a type has a variant, it may not change when turning more concrete. Thus, abstract types with ambiguous variants must not return a variant. /// * A leaf type, i.e., a fully resolved non-contradictory type must provide a variant. /// A consequence is that the meet of two types with different tag will result in an error if both tags are defined. /// /// # Example /// For a full example of an abstract type system, refer to the [crate documentation](../index.html) and the examples. TODO: link! /// pub trait Abstract: Eq + Sized + Clone + Debug { /// Result of a meet of two incompatible type, i.e., it represents a type contradiction. /// May contain information regarding why the meet failed. type Err: Debug; /// A type that represents different possible variants of the abstract type. type VariantTag: Debug + Clone + Copy + PartialEq + Eq; /// Returns the type variant of `self`, if it exists. /// Refer to the documentation of [Abstract](trait.Abstract.html) for the responsibilities of this function. fn variant(&self) -> Option<Self::VariantTag>; /// Returns the unconstrained, most abstract type. fn unconstrained() -> Self; /// Determines whether or not `self` is the unconstrained type. fn is_unconstrained(&self) -> bool { self == &Self::unconstrained() } /// Attempts to meet two abstract types. /// Refer to the documentation of [Abstract](trait.Abstract.html) for the responsibilities of this function. fn meet(&self, other: &Self) -> Result<Self, Self::Err>; /// Provides the arity of a variant. May be 0. fn variant_arity(tag: Self::VariantTag) -> usize; /// Provides the arity of the variant of `self` if it is defined. fn arity(&self) -> Option<usize> { self.variant().map(Self::variant_arity) } /// Creates an abstract type based with the given `tag` and `children`. /// It is guaranteed that `Self::variant_arity(tag) == children.len()`. /// /// # Panics /// May panic if `Self::variant_arity(tag) != children.len()`. fn from_tag(tag: Self::VariantTag, children: Vec<Self>) -> Self; } /// Indicates that an abstract type could not be reified because it is too general or too restrictive. /// /// # Example /// 1. A numeric type cannot be reified into any concrete value because the concrete counterpart could be a natural /// number, integer, floating point number, .... -> `ReificationErr::TooGeneral` /// 2. An integer type cannot be reified into a concrete type with fixed memory layout except a default size is /// defined, e.g. an Int will be reified into an Int32. -> `ReificationErr::TooGeneral` /// 3. An unbounded integer might not have a concrete counterpart because the system requires a concrete bit size. /// -> `ReificationErr::Conflicting` /// /// Note the subtle difference between `ReificationErr::TooGeneral` and `ReificationErr::Conflicting`: /// + In the `Conflicting` case there is no concrete counterpart /// + In the `TooGeneral` case the concrete counterpart is not defined or not unique but could exist. #[derive(Debug, Clone)] pub enum ReificationErr { /// Attempting to reify an abstract type with either no unique concrete counterpart or with no defined default /// reification value results in this error. TooGeneral(String), /// Attempting to reify an abstract type for which no concrete counterpart does exist results in this error. Conflicting(String), } /// A type implementing this trait can be `reified` into a concrete representation. /// This transformation cannot fail. If it is fallible, refer to [`TryReifiable`](trait.TryReifiable.html). pub trait Reifiable { /// The result type of the reification. type Reified; /// Transforms `self` into the more concrete `Self::Reified` type. fn reify(&self) -> Self::Reified; } /// A type implementing this trait can potentially be `reified` into a concrete representation. /// This transformation can fail. If it is infallible, refer to [`Reifiable`](trait.Reifiable.html). pub trait TryReifiable { /// The result type of the attempted reification. type Reified; /// Attempts to transform `self` into an more concrete `Self::Reified` type. /// Returns a [`ReificationErr`](enum.ReificationErr.html) if the transformation fails. fn try_reify(&self) -> Result<Self::Reified, ReificationErr>; } /// A type implementing this trait can be `generalized` into an abstract representation infallibly. pub trait Generalizable { /// The result type of the generalization. type Generalized; /// Generalizes the given concrete type. fn generalize(&self) -> Self::Generalized; } /// A trait representing a type table. /// /// It maps [`TcKey`](../struct.TcKey.html) to `Self::Type` and allows for an automatic transformation into a hashmap. pub trait TypeTable: Index<TcKey> { /// The (rust-) type of the (external-) type stored in this type table. type Type; /// Transforms itself into a hashmap. fn as_hashmap(self) -> HashMap<TcKey, Self::Type>; } /// An implementation of [`TypeTable`](trait.TypeTable.html) for type implementing [`Abstract`](trait.Abstract.html). /// See [`ReifiedTypeTable`](struct.ReifiedTypeTable.html) for an implementation specializing on /// concrete types. /// /// Can automatically be generated from a `HashMap<TcKey, AbsTy>` for `AbsTy: Abstract`. #[derive(Debug, Clone)] pub struct AbstractTypeTable<AbsTy: Abstract> { table: HashMap<TcKey, AbsTy>, } impl<AbsTy: Abstract> Index<TcKey> for AbstractTypeTable<AbsTy> { type Output = AbsTy; fn index(&self, index: TcKey) -> &Self::Output { &self.table[&index] } } impl<AbsTy: Abstract> From<HashMap<TcKey, AbsTy>> for AbstractTypeTable<AbsTy> { fn from(map: HashMap<TcKey, AbsTy>) -> Self { AbstractTypeTable { table: map } } } /// An implementation of [`TypeTable`](trait.TypeTable.html) for concrete types. /// See [`AbstractTypeTable`](struct.AbstractTypeTable.html) for an implementation specializing on /// abstract types. /// /// Can automatically be generated from a `HashMap<TcKey, Concrete>`. #[derive(Debug, Clone)] pub struct ReifiedTypeTable<Concrete> { table: HashMap<TcKey, Concrete>, } impl<Concrete> Index<TcKey> for ReifiedTypeTable<Concrete> { type Output = Concrete; fn index(&self, index: TcKey) -> &Self::Output { &self.table[&index] } } impl<Concrete> From<HashMap<TcKey, Concrete>> for ReifiedTypeTable<Concrete> { fn from(map: HashMap<TcKey, Concrete>) -> Self { ReifiedTypeTable { table: map } } } impl<AbsTy: Abstract> TypeTable for AbstractTypeTable<AbsTy> { type Type = AbsTy; fn as_hashmap(self) -> HashMap<TcKey, Self::Type> { self.table } } impl<Concrete> TypeTable for ReifiedTypeTable<Concrete> { type Type = Concrete; fn as_hashmap(self) -> HashMap<TcKey, Self::Type> { self.table } } impl<AbsTy> AbstractTypeTable<AbsTy> where AbsTy: Abstract + Reifiable, { /// Transforms an [`AbstractTypeTable`](struct.AbstractTypeTable.html) into a [`ReifiedTypeTable`](struct.ReifiedTypeTable.html) /// by reifying all abstract types. pub fn reified(self) -> ReifiedTypeTable<AbsTy::Reified> { ReifiedTypeTable { table: self.table.into_iter().map(|(key, ty)| (key, ty.reify())).collect() } } } impl<AbsTy> AbstractTypeTable<AbsTy> where AbsTy: Abstract + TryReifiable, { /// Attempts to transform an [`AbstractTypeTable`](struct.AbstractTypeTable.html) into a [`ReifiedTypeTable`](struct.ReifiedTypeTable.html) /// by reifying all abstract types. pub fn try_reified(self) -> Result<ReifiedTypeTable<AbsTy::Reified>, ()> { self.table .into_iter() .map(|(key, ty)| ty.try_reify().map(|re| (key, re))) .collect::<Result<HashMap<TcKey, AbsTy::Reified>, ReificationErr>>() .map_err(|_| ()) .map(|table| ReifiedTypeTable { table }) } }