kodept_inference/
traits.rs

1use std::borrow::Cow;
2use std::collections::HashSet;
3use std::fmt::Debug;
4use std::hash::Hash;
5
6use Constraint::{ExplicitInstance, ImplicitInstance};
7use MonomorphicType::{Constant, Pointer, Primitive, Tuple, Var};
8
9use crate::constraint::{Constraint, EqConstraint};
10use crate::constraint::Constraint::Eq;
11use crate::r#type::{MonomorphicType, PolymorphicType, TVar};
12use crate::r#type::MonomorphicType::Fn;
13use crate::substitution::Substitutions;
14
15pub(crate) trait Substitutable {
16    type Output;
17
18    fn substitute(&self, subst: &Substitutions) -> Self::Output;
19}
20
21pub(crate) trait FreeTypeVars {
22    fn free_types(self) -> HashSet<TVar>;
23}
24
25pub(crate) trait ActiveTVars {
26    fn active_vars(self) -> HashSet<TVar>;
27}
28
29pub trait EnvironmentProvider<Key: Hash + std::cmp::Eq> {
30    type Error;
31    
32    #[deprecated]
33    fn get(&self, key: &Key) -> Option<Cow<PolymorphicType>> where Self::Error: Debug {
34        self.maybe_get(key).unwrap()
35    }
36    
37    fn maybe_get(&self, key: &Key) -> Result<Option<Cow<PolymorphicType>>, Self::Error>; 
38}
39
40// -------------------------------------------------------------------------------------------------
41
42impl Substitutable for TVar {
43    type Output = HashSet<TVar>;
44
45    fn substitute(&self, subst: &Substitutions) -> Self::Output {
46        subst.get(self).unwrap_or(&Var(*self)).free_types()
47    }
48}
49
50impl Substitutable for MonomorphicType {
51    type Output = Self;
52
53    fn substitute(&self, subst: &Substitutions) -> MonomorphicType {
54        match self {
55            Primitive(_) | Constant(_) => self.clone(),
56            Var(x) => subst.get(x).unwrap_or(self).clone(),
57            Fn(input, output) => Fn(
58                Box::new(input.substitute(subst)),
59                Box::new(output.substitute(subst)),
60            ),
61            Tuple(inner) => Tuple(crate::r#type::Tuple(inner.0.substitute(subst))),
62            Pointer(inner) => Pointer(Box::new(inner.substitute(subst))),
63        }
64    }
65}
66
67impl Substitutable for PolymorphicType {
68    type Output = Self;
69
70    fn substitute(&self, subst: &Substitutions) -> PolymorphicType {
71        let mut s = subst.clone();
72        self.bindings.iter().for_each(|it| s.remove(it));
73        Self {
74            bindings: self.bindings.clone(),
75            binding_type: self.binding_type.substitute(&s),
76        }
77    }
78}
79
80impl Substitutable for Constraint {
81    type Output = Self;
82
83    fn substitute(&self, subst: &Substitutions) -> Constraint {
84        match self {
85            Eq(EqConstraint { t1, t2 }) => Eq(EqConstraint {
86                t1: t1.substitute(subst),
87                t2: t2.substitute(subst),
88            }),
89            ExplicitInstance { t, s } => ExplicitInstance {
90                t: t.substitute(subst),
91                s: s.substitute(subst),
92            },
93            ImplicitInstance { t1, ctx, t2 } => ImplicitInstance {
94                t1: t1.substitute(subst),
95                ctx: ctx.substitute(subst),
96                t2: t2.substitute(subst),
97            },
98        }
99    }
100}
101
102impl<T: Substitutable> Substitutable for &T {
103    type Output = T::Output;
104
105    fn substitute(&self, subst: &Substitutions) -> Self::Output {
106        (*self).substitute(subst)
107    }
108}
109
110impl<T: Substitutable> Substitutable for [T] {
111    type Output = Vec<T::Output>;
112
113    fn substitute(&self, subst: &Substitutions) -> Self::Output {
114        self.iter().map(|it| it.substitute(subst)).collect()
115    }
116}
117
118impl<T: Substitutable<Output = HashSet<T>>> Substitutable for HashSet<T>
119where
120    T: Hash + std::cmp::Eq,
121{
122    type Output = HashSet<T>;
123
124    fn substitute(&self, subst: &Substitutions) -> Self::Output {
125        self.iter()
126            .flat_map(|it| it.substitute(subst))
127            .collect()
128    }
129}
130
131// -------------------------------------------------------------------------------------------------
132
133impl FreeTypeVars for &TVar {
134    fn free_types(self) -> HashSet<TVar> {
135        HashSet::from([*self])
136    }
137}
138
139impl FreeTypeVars for &MonomorphicType {
140    fn free_types(self) -> HashSet<TVar> {
141        match self {
142            Primitive(_) | Constant(_) => HashSet::new(),
143            Var(x) => HashSet::from([*x]),
144            Fn(input, output) => &input.free_types() | &output.free_types(),
145            Tuple(crate::r#type::Tuple(vec)) => vec.free_types(),
146            Pointer(x) => x.free_types(),
147        }
148    }
149}
150
151impl FreeTypeVars for &PolymorphicType {
152    fn free_types(self) -> HashSet<TVar> {
153        let mut free = self.binding_type.free_types();
154        self.bindings.iter().for_each(|it| {
155            free.remove(it);
156        });
157        free
158    }
159}
160
161impl<T: FreeTypeVars, I: IntoIterator<Item = T>> FreeTypeVars for I {
162    fn free_types(self) -> HashSet<TVar> {
163        self.into_iter()
164            .fold(HashSet::new(), |acc, next| &acc | &next.free_types())
165    }
166}
167
168// -------------------------------------------------------------------------------------------------
169
170impl ActiveTVars for &Constraint {
171    fn active_vars(self) -> HashSet<TVar> {
172        match self {
173            Eq(EqConstraint { t1, t2 }) => [t1.clone(), t2.clone()].free_types(),
174            ExplicitInstance { t, s } => &t.free_types() | &s.free_types(),
175            ImplicitInstance { t1, ctx, t2 } => {
176                let set = &ctx.free_types() & &t2.free_types();
177                &t1.free_types() | &set
178            }
179        }
180    }
181}
182
183impl<T: ActiveTVars, I: IntoIterator<Item = T>> ActiveTVars for I {
184    fn active_vars(self) -> HashSet<TVar> {
185        self.into_iter()
186            .fold(HashSet::new(), |acc, next| &acc | &next.active_vars())
187    }
188}
kodept_inference/traits.rs

kodept_inference/
traits.rs
