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

use std::borrow::Cow;

use fnv::FnvMap;
use symbol::Symbol;
use types::{AliasRef, ArcType, Type, TypeEnv};

quick_error! {
    #[derive(Debug)]
    pub enum Error {
        UndefinedType(id: Symbol) {
            description("undefined type")
            display("Type `{}` does not exist.", id)
        }
        SelfRecursiveAlias(id: Symbol) {
            description("undefined type")
            display("Tried to remove self recursive alias `{}`.", id)
        }
    }
}

#[derive(Debug, Default)]
pub struct AliasRemover {
    reduced_aliases: Vec<Symbol>,
}

impl AliasRemover {
    pub fn new() -> AliasRemover {
        Self::default()
    }

    pub fn len(&self) -> usize {
        self.reduced_aliases.len()
    }

    pub fn reset(&mut self, to: usize) {
        self.reduced_aliases.truncate(to)
    }

    pub fn remove_aliases(&mut self, env: &TypeEnv, mut typ: ArcType) -> Result<ArcType, Error> {
        loop {
            typ = match self.remove_alias(env, &typ)? {
                Some(typ) => typ,
                None => return Ok(typ),
            };
        }
    }

    pub fn remove_alias(&mut self, env: &TypeEnv, typ: &ArcType) -> Result<Option<ArcType>, Error> {
        let typ = typ.skolemize(&mut FnvMap::default());
        match peek_alias(env, &typ)? {
            Some(alias) => {
                if self.reduced_aliases.iter().any(|name| *name == alias.name) {
                    return Err(Error::SelfRecursiveAlias(alias.name.clone()));
                }
                self.reduced_aliases.push(alias.name.clone());
                // Opaque types should only exist as the alias itself
                if **alias.unresolved_type().remove_forall() == Type::Opaque {
                    return Ok(None);
                }
                Ok(alias.typ().apply_args(&typ.unapplied_args()))
            }
            None => Ok(None),
        }
    }
}

/// Removes type aliases from `typ` until it is an actual type
pub fn remove_aliases(env: &TypeEnv, mut typ: ArcType) -> ArcType {
    while let Ok(Some(new)) = remove_alias(env, &typ) {
        typ = new;
    }
    typ
}

pub fn remove_aliases_cow<'t>(env: &TypeEnv, typ: &'t ArcType) -> Cow<'t, ArcType> {
    match remove_alias(env, typ) {
        Ok(Some(typ)) => Cow::Owned(remove_aliases(env, typ)),
        _ => Cow::Borrowed(typ),
    }
}

/// Resolves aliases until `canonical` returns `true` for an alias in which case it returns the
/// type that directly contains that alias
pub fn canonical_alias<'t, F>(env: &TypeEnv, typ: &'t ArcType, mut canonical: F) -> Cow<'t, ArcType>
where
    F: FnMut(&AliasRef<Symbol, ArcType>) -> bool,
{
    match peek_alias(env, typ) {
        Ok(Some(alias)) => if canonical(alias) {
            Cow::Borrowed(typ)
        } else {
            alias
                .typ()
                .apply_args(&typ.unapplied_args())
                .map(|typ| Cow::Owned(canonical_alias(env, &typ, canonical).into_owned()))
                .unwrap_or(Cow::Borrowed(typ))
        },
        _ => Cow::Borrowed(typ),
    }
}

/// Expand `typ` if it is an alias that can be expanded and return the expanded type.
/// Returns `None` if the type is not an alias or the alias could not be expanded.
pub fn remove_alias(env: &TypeEnv, typ: &ArcType) -> Result<Option<ArcType>, Error> {
    let typ = typ.skolemize(&mut FnvMap::default());
    Ok(peek_alias(env, &typ)?.and_then(|alias| {
        // Opaque types should only exist as the alias itself
        if **alias.unresolved_type().remove_forall() == Type::Opaque {
            return None;
        }
        alias.typ().apply_args(&typ.unapplied_args())
    }))
}

pub fn peek_alias<'t>(
    env: &'t TypeEnv,
    typ: &'t ArcType,
) -> Result<Option<&'t AliasRef<Symbol, ArcType>>, Error> {
    fn extract_alias(
        typ: &ArcType,
        given_arguments_count: usize,
    ) -> Option<&AliasRef<Symbol, ArcType>> {
        match **typ {
            Type::Alias(ref alias) if alias.params().len() == given_arguments_count => Some(alias),
            Type::App(ref alias, ref args) => {
                extract_alias(alias, args.len() + given_arguments_count)
            }
            _ => None,
        }
    }

    let maybe_alias = extract_alias(typ, 0);

    match typ.alias_ident() {
        Some(id) => {
            let alias = match maybe_alias {
                Some(alias) => alias,
                None => env
                    .find_type_info(id)
                    .ok_or_else(|| Error::UndefinedType(id.clone()))?,
            };
            Ok(Some(alias))
        }
        None => Ok(None),
    }
}