gluon_base/
resolve.rs

1use std::{borrow::Cow, iter::FromIterator};
2
3use crate::{
4    fnv::FnvMap,
5    symbol::Symbol,
6    types::{AliasData, AliasRef, Generic, Type, TypeContext, TypeEnv, TypeExt},
7};
8
9quick_error! {
10    #[derive(Debug, PartialEq)]
11    pub enum Error {
12        UndefinedType(id: Symbol) {
13            display("Type `{}` does not exist.", id)
14        }
15        SelfRecursiveAlias(id: Symbol) {
16            display("Tried to remove self recursive alias `{}`.", id)
17        }
18    }
19}
20
21#[derive(Debug)]
22pub struct AliasRemover<T> {
23    reduced_aliases: Vec<Symbol>,
24    pub named_variables: FnvMap<Symbol, T>,
25}
26
27impl<T> Default for AliasRemover<T> {
28    fn default() -> Self {
29        AliasRemover {
30            reduced_aliases: Default::default(),
31            named_variables: Default::default(),
32        }
33    }
34}
35
36impl<T> AliasRemover<T> {
37    pub fn new() -> Self {
38        Self::default()
39    }
40
41    pub fn len(&self) -> usize {
42        self.reduced_aliases.len()
43    }
44
45    pub fn is_empty(&self) -> bool {
46        self.reduced_aliases.is_empty()
47    }
48
49    pub fn reset(&mut self, to: usize) {
50        self.reduced_aliases.truncate(to)
51    }
52
53    pub fn clear(&mut self) {
54        self.reduced_aliases.clear();
55        self.named_variables.clear();
56    }
57}
58
59impl<T> AliasRemover<T>
60where
61    T: TypeExt<Id = Symbol, SpannedId = Symbol> + Clone + ::std::fmt::Display,
62    T::Types: Clone + Default + Extend<T> + FromIterator<T>,
63    T::Generics: Clone + FromIterator<Generic<Symbol>>,
64    T::Fields: Clone,
65{
66    pub fn canonical_alias<'t, F>(
67        &mut self,
68        env: &(dyn TypeEnv<Type = T> + '_),
69        interner: &mut impl TypeContext<Symbol, T>,
70        typ: &'t T,
71        mut canonical: F,
72    ) -> Result<Cow<'t, T>, Error>
73    where
74        F: FnMut(&AliasRef<Symbol, T>) -> bool,
75    {
76        Ok(match peek_alias(env, typ) {
77            Ok(Some(alias)) => {
78                if self.reduced_aliases.contains(&alias.name) {
79                    return Err(Error::SelfRecursiveAlias(alias.name.clone()));
80                }
81                self.reduced_aliases.push(alias.name.clone());
82
83                if canonical(&alias) {
84                    Cow::Borrowed(typ)
85                } else {
86                    match alias.typ(interner).apply_args(
87                        alias.params(),
88                        &typ.unapplied_args(),
89                        interner,
90                        &mut self.named_variables,
91                    ) {
92                        Some(typ) => Cow::Owned(
93                            self.canonical_alias(env, interner, &typ, canonical)?
94                                .into_owned(),
95                        ),
96                        None => Cow::Borrowed(typ),
97                    }
98                }
99            }
100            _ => Cow::Borrowed(typ),
101        })
102    }
103
104    pub fn remove_aliases_to_concrete<'a>(
105        &mut self,
106        env: &(dyn TypeEnv<Type = T> + '_),
107        interner: &mut impl TypeContext<Symbol, T>,
108        mut typ: T,
109    ) -> Result<T, Error> {
110        loop {
111            typ = match self.remove_alias_to_concrete(env, interner, &typ, |_| true)? {
112                Some((typ, args)) => match *typ {
113                    Type::Builtin(..)
114                    | Type::Function(..)
115                    | Type::Record(..)
116                    | Type::Variant(..)
117                    | Type::Effect(..)
118                    | Type::EmptyRow
119                    | Type::ExtendRow { .. }
120                    | Type::ExtendTypeRow { .. }
121                        if args.is_empty() =>
122                    {
123                        return Ok(typ)
124                    }
125                    _ => {
126                        let typ = typ
127                            .replace_generics(interner, &mut self.named_variables)
128                            .unwrap_or_else(|| typ);
129
130                        interner.app(typ, args.iter().cloned().collect())
131                    }
132                },
133                None => return Ok(typ),
134            };
135        }
136    }
137
138    pub fn remove_aliases(
139        &mut self,
140        env: &(dyn TypeEnv<Type = T> + '_),
141        interner: &mut impl TypeContext<Symbol, T>,
142        typ: T,
143    ) -> Result<T, Error> {
144        self.remove_aliases_predicate(env, interner, typ, |_| true)
145    }
146
147    pub fn remove_aliases_predicate(
148        &mut self,
149        env: &(dyn TypeEnv<Type = T> + '_),
150        interner: &mut impl TypeContext<Symbol, T>,
151        mut typ: T,
152        mut predicate: impl FnMut(&AliasData<Symbol, T>) -> bool,
153    ) -> Result<T, Error> {
154        loop {
155            typ = match self.remove_alias(env, interner, &typ, &mut predicate)? {
156                Some(typ) => typ,
157                None => return Ok(typ),
158            };
159        }
160    }
161
162    pub fn remove_alias(
163        &mut self,
164        env: &(dyn TypeEnv<Type = T> + '_),
165        interner: &mut impl TypeContext<Symbol, T>,
166        typ: &T,
167        predicate: impl FnOnce(&AliasData<Symbol, T>) -> bool,
168    ) -> Result<Option<T>, Error> {
169        Ok(self
170            .remove_alias_to_concrete(env, interner, typ, predicate)?
171            .map(|(non_replaced_type, unapplied_args)| {
172                let non_replaced_type = non_replaced_type
173                    .replace_generics(interner, &mut self.named_variables)
174                    .unwrap_or_else(|| non_replaced_type.clone());
175
176                interner.app(non_replaced_type, unapplied_args.iter().cloned().collect())
177            }))
178    }
179
180    pub fn remove_alias_to_concrete<'a>(
181        &mut self,
182        env: &'a (dyn TypeEnv<Type = T> + '_),
183        interner: &mut impl TypeContext<Symbol, T>,
184        typ: &'a T,
185        predicate: impl FnOnce(&AliasData<Symbol, T>) -> bool,
186    ) -> Result<Option<(T, Cow<'a, [T]>)>, Error> {
187        match peek_alias(env, &typ)? {
188            Some(ref alias) if predicate(alias) => {
189                self.remove_alias_to_concrete_inner(interner, typ, alias)
190            }
191            _ => Ok(None),
192        }
193    }
194
195    fn remove_alias_to_concrete_inner<'a>(
196        &mut self,
197        interner: &mut impl TypeContext<Symbol, T>,
198        typ: &'a T,
199        alias: &AliasRef<Symbol, T>,
200    ) -> Result<Option<(T, Cow<'a, [T]>)>, Error> {
201        if self.reduced_aliases.iter().any(|name| *name == alias.name) {
202            return Err(Error::SelfRecursiveAlias(alias.name.clone()));
203        }
204        self.reduced_aliases.push(alias.name.clone());
205        // Opaque types should only exist as the alias itself
206        if let Type::Opaque = **alias.unresolved_type() {
207            return Ok(None);
208        }
209
210        let unapplied_args = typ.unapplied_args();
211
212        let opt = alias.typ(interner).arg_application(
213            alias.params(),
214            &unapplied_args,
215            interner,
216            &mut self.named_variables,
217        );
218        match opt {
219            Some((t, a)) => {
220                let l = unapplied_args.len() - a.len();
221                Ok(Some((
222                    t,
223                    match unapplied_args {
224                        Cow::Borrowed(slice) => Cow::Borrowed(&slice[l..]),
225                        Cow::Owned(mut vec) => {
226                            vec.drain(l..);
227                            Cow::Owned(vec)
228                        }
229                    },
230                )))
231            }
232            None => Ok(None),
233        }
234    }
235}
236
237/// Removes type aliases from `typ` until it is an actual type
238pub fn remove_aliases<T>(
239    env: &(dyn TypeEnv<Type = T> + '_),
240    interner: &mut impl TypeContext<Symbol, T>,
241    mut typ: T,
242) -> T
243where
244    T: TypeExt<Id = Symbol, SpannedId = Symbol> + Clone + ::std::fmt::Display,
245    T::Types: Clone + Default + Extend<T> + FromIterator<T>,
246    T::Generics: Clone + FromIterator<Generic<Symbol>>,
247    T::Fields: Clone,
248{
249    while let Ok(Some(new)) = remove_alias(env, interner, &typ) {
250        typ = new;
251    }
252    typ
253}
254
255pub fn remove_aliases_cow<'t, T>(
256    env: &(dyn TypeEnv<Type = T> + '_),
257    interner: &mut impl TypeContext<Symbol, T>,
258    typ: &'t T,
259) -> Cow<'t, T>
260where
261    T: TypeExt<Id = Symbol, SpannedId = Symbol> + Clone + ::std::fmt::Display,
262    T::Types: Clone + Default + Extend<T> + FromIterator<T>,
263    T::Generics: Clone + FromIterator<Generic<Symbol>>,
264    T::Fields: Clone,
265{
266    match remove_alias(env, interner, typ) {
267        Ok(Some(typ)) => Cow::Owned(remove_aliases(env, interner, typ)),
268        _ => Cow::Borrowed(typ),
269    }
270}
271
272/// Resolves aliases until `canonical` returns `true` for an alias in which case it returns the
273/// type that directly contains that alias
274pub fn canonical_alias<'t, F, T>(
275    env: &(dyn TypeEnv<Type = T> + '_),
276    interner: &mut impl TypeContext<Symbol, T>,
277    typ: &'t T,
278    mut canonical: F,
279) -> Cow<'t, T>
280where
281    F: FnMut(&AliasRef<Symbol, T>) -> bool,
282    T: TypeExt<Id = Symbol, SpannedId = Symbol> + Clone + ::std::fmt::Display,
283    T::Types: Clone + Default + Extend<T> + FromIterator<T>,
284    T::Generics: Clone + FromIterator<Generic<Symbol>>,
285    T::Fields: Clone,
286{
287    match peek_alias(env, typ) {
288        Ok(Some(alias)) => {
289            if canonical(&alias) {
290                Cow::Borrowed(typ)
291            } else {
292                alias
293                    .typ(interner)
294                    .apply_args(
295                        alias.params(),
296                        &typ.unapplied_args(),
297                        interner,
298                        &mut Default::default(),
299                    )
300                    .map(|typ| {
301                        Cow::Owned(canonical_alias(env, interner, &typ, canonical).into_owned())
302                    })
303                    .unwrap_or_else(|| Cow::Borrowed(typ))
304            }
305        }
306        _ => Cow::Borrowed(typ),
307    }
308}
309
310/// Expand `typ` if it is an alias that can be expanded and return the expanded type.
311/// Returns `None` if the type is not an alias or the alias could not be expanded.
312pub fn remove_alias<T>(
313    env: &(dyn TypeEnv<Type = T> + '_),
314    interner: &mut impl TypeContext<Symbol, T>,
315    typ: &T,
316) -> Result<Option<T>, Error>
317where
318    T: TypeExt<Id = Symbol, SpannedId = Symbol> + Clone + ::std::fmt::Display,
319    T::Types: Clone + Default + Extend<T> + FromIterator<T>,
320    T::Generics: Clone + FromIterator<Generic<Symbol>>,
321    T::Fields: Clone,
322{
323    Ok(peek_alias(env, &typ)?.and_then(|alias| {
324        // Opaque types should only exist as the alias itself
325        if let Type::Opaque = **alias.unresolved_type() {
326            return None;
327        }
328        alias.typ(interner).apply_args(
329            alias.params(),
330            &typ.unapplied_args(),
331            interner,
332            &mut Default::default(),
333        )
334    }))
335}
336
337pub fn peek_alias<'t, T>(
338    env: &(dyn TypeEnv<Type = T> + '_),
339    typ: &'t T,
340) -> Result<Option<AliasRef<Symbol, T>>, Error>
341where
342    T: TypeExt<Id = Symbol, SpannedId = Symbol> + Clone + ::std::fmt::Display,
343    T::Types: Clone + Default + Extend<T>,
344    T::Generics: Clone + FromIterator<Generic<Symbol>>,
345    T::Fields: Clone,
346{
347    let maybe_alias = typ.applied_alias();
348
349    match typ.alias_ident() {
350        Some(id) => {
351            let alias = match maybe_alias {
352                Some(alias) => Some(alias.clone()),
353                None => env.find_type_info(id).map(|a| (*a).clone()),
354            };
355            Ok(alias)
356        }
357        None => Ok(None),
358    }
359}
gluon_base/resolve.rs

gluon_base/
resolve.rs
