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

//! This mod contains everything related to types and collections of types (type tables).
//!
//! # Content
//! * [Variant] is a trait representing the variant of an abstract type that will be inferred during the type checking procedure.
//! * [Constructable]: A variant is constructable if it can be transformed into a concrete type, i.e., [Constructable::Type].
//! * [TypeTable] and [PreliminaryTypeTable] are mappings from a [TcKey] to a concrete [Constructable::Type] or [Preliminary] type.

use std::{collections::HashMap, fmt::Debug};

use crate::TcKey;

/// A variant that will be inferred during the type checking procedure.
///
/// # Requirements
/// 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
/// possible.
/// ## Refinement
/// The top value needs to be provided by the [Variant::top()] function.  Types will be refined
/// successively using the fallible [Variant::meet()] function.  If the types are incompatible, i.e., would result in a contradictory
/// type, the meet needs to return a [Variant::Err]. Note that [Variant::meet()] needs to follow the rules of abstract meets.
/// Intuitively, these are:
/// * The result of a meet needs to be more or equally concrete than either argument.
/// * 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.
/// This especially entails that meeting any type `T` with an unconstrained type returns `T`.
/// 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.
/// 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
/// a sub-type because it will be later determined to be an "Option" or "Tuple" type.  More details in the next section.
///
/// ## Arity
/// Type can be recursive, i.e., they have a number of subtypes, their "children".
/// 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.
/// 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.
/// Hence, its least arity is initially 0 and potentially increases when more information was collected.
///
/// The type checking procedure keeps track of types and their potential children.
/// For this, it requires some guarantees when it comes to the arity:
///
/// ### Arity Stability
/// 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.
/// It may, however, result in a variant with variable arity.
///
/// # Example
/// For a full example of an abstract type system, refer to the [crate documentation](../index.html) and the examples.
///
pub trait Variant: Sized + Clone + Debug + Eq {
    /// Result of a meet of two incompatible type, i.e., it represents a type contradiction.
    /// May contain information regarding why the meet failed.  The error will be wrapped into a [crate::TcErr] providing contextual information.
    type Err: Debug;

    /// Returns the unconstrained, most abstract type.
    fn top() -> Self;

    /// Determines whether or not `self` is the unconstrained type.
    fn is_top(&self) -> bool {
        self == &Self::top()
    }

    /// Attempts to meet two variants respecting their currently-determined potentially variable arity.
    /// Refer to [Variant] for the responsibilities of this function.
    /// In particular: `usize::max(lhs.least_arity, rhs.least_arity) <= result.least_arity`
    /// In the successful case, the variant and arity of the partial have to match, i.e., if the [Arity]
    /// is fixed with value `n`, then [Partial::least_arity] needs to be `n` as well.
    fn meet(lhs: Partial<Self>, rhs: Partial<Self>) -> Result<Partial<Self>, Self::Err>;

    /// Indicates whether the variant has a fixed arity.  Note that this values does not have to be constant over all instances of the variant.
    /// 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.
    /// The pair and triple are both represented by the same type variant and have a fixed, non-specific arity.  Before obtaining this information,
    /// the tuple has a variable arity and potentially a different variant.
    fn arity(&self) -> Arity;
}
/// Represents the arity of a [Variant].
#[derive(Debug, Clone, Copy)]
pub enum Arity {
    /// The arity is variable, i.e., it does not have a specific value.
    Variable,
    /// The arity has a fixed value.
    Fixed(usize),
}

impl Arity {
    pub(crate) fn to_opt(self) -> Option<usize> {
        match self {
            Arity::Variable => None,
            Arity::Fixed(n) => Some(n),
        }
    }
}

/// Partial is a container for a [Variant] and the least arity a particular instance of this variant currently has. Only used for [Variant::meet()].
///
/// The `least_arity` indicates how many children this instance of the variance has according to the current state of the type checker.
/// The value might increase in the future but never decrease.
#[derive(Debug, Clone)]
pub struct Partial<V: Variant> {
    /// The variant represented by this `Partial`.
    pub variant: V,
    ///The least number of children the variant will have after completing the type check.
    pub least_arity: usize,
}

/// Represents a preliminary output of the type check.  Mainly used if [Variant] does not implement [Constructable].
#[derive(Debug, Clone)]
pub struct Preliminary<V: Variant> {
    /// The type variant of the entity represented by this `Preliminary`.
    pub variant: V,
    /// The [TcKey]s of the children of this variant.
    pub children: Vec<Option<TcKey>>,
}

/// A type table containing a [Preliminary] type for each [TcKey].  Mainly used if [Variant] does not implement [Constructable].
pub type PreliminaryTypeTable<V> = HashMap<TcKey, Preliminary<V>>;
/// A type table containing the constructed type of the inferred [Variant] for each [TcKey].  Requires [Variant] to implement [Constructable].
pub type TypeTable<V> = HashMap<TcKey, <V as Constructable>::Type>;

/// A type implementing this trait can potentially be transformed into a concrete representation. This transformation can fail.
pub trait Constructable: Variant {
    /// The result type of the attempted construction.
    type Type: Clone + Debug;
    /// Attempts to transform `self` into an more concrete `Self::Type`.
    /// Returns a [Variant::Err] if the transformation fails.  This error will be wrapped into a [crate::TcErr] to enrich it with contextual information.
    fn construct(&self, children: &[Self::Type]) -> Result<Self::Type, <Self as Variant>::Err>;
}