rue-types 0.10.0

A type system for the Rue programming language.
Documentation 
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

use std::collections::HashMap;

use id_arena::Arena;
use indexmap::IndexMap;
use log::trace;

use crate::{Alias, FunctionType, Pair, Struct, Type, TypeId, Union, stringify_impl};

pub fn substitute(arena: &mut Arena<Type>, id: TypeId) -> TypeId {
    substitute_with_mappings(arena, id, &HashMap::new())
}

pub fn substitute_with_mappings(
    arena: &mut Arena<Type>,
    id: TypeId,
    mappings: &HashMap<TypeId, TypeId>,
) -> TypeId {
    let name = stringify_impl(arena, id, &mut IndexMap::new());
    trace!("Substituting {name}");
    let result = substitute_impl(arena, id, mappings, &mut IndexMap::new());
    let new_name = stringify_impl(arena, result, &mut IndexMap::new());
    trace!("Substitution from {name} yielded {new_name}");
    result
}

fn substitute_impl(
    arena: &mut Arena<Type>,
    mut old_id: TypeId,
    map: &HashMap<TypeId, TypeId>,
    stack: &mut IndexMap<TypeId, TypeId>,
) -> TypeId {
    if let Some(id) = map.get(&old_id) {
        old_id = *id;
    }

    if let Some(id) = stack.get(&old_id) {
        return *id;
    }

    let new_id = arena.alloc(Type::Unresolved);
    stack.insert(old_id, new_id);

    let result = match arena[old_id].clone() {
        Type::Apply(apply) => {
            let mut new_map = apply.generics.clone();

            for arg in new_map.values_mut() {
                *arg = substitute_impl(arena, *arg, map, stack);
            }

            substitute_impl(arena, apply.inner, &new_map, stack)
        }
        Type::Unresolved | Type::Generic(_) | Type::Atom(_) | Type::Never | Type::Any => old_id,
        Type::Ref(id) => substitute_impl(arena, id, map, stack),
        Type::Pair(pair) => {
            let first = substitute_impl(arena, pair.first, map, stack);
            let rest = substitute_impl(arena, pair.rest, map, stack);
            arena.alloc(Type::Pair(Pair::new(first, rest)))
        }
        Type::Struct(ty) => {
            let inner = substitute_impl(arena, ty.inner, map, stack);
            arena.alloc(Type::Struct(Struct { inner, ..ty }))
        }
        Type::Alias(alias) => {
            let inner = substitute_impl(arena, alias.inner, map, stack);
            arena.alloc(Type::Alias(Alias { inner, ..alias }))
        }
        Type::Function(function) => {
            let params = function
                .params
                .iter()
                .map(|(name, id)| (name.clone(), substitute_impl(arena, *id, map, stack)))
                .collect();
            let ret = substitute_impl(arena, function.ret, map, stack);
            arena.alloc(Type::Function(FunctionType {
                params,
                ret,
                ..function
            }))
        }
        Type::Union(union) => {
            let types = union
                .types
                .iter()
                .map(|id| substitute_impl(arena, *id, map, stack))
                .collect();
            arena.alloc(Type::Union(Union::new(types)))
        }
    };

    stack.pop().unwrap();

    *arena.get_mut(new_id).unwrap() = Type::Ref(result);

    result
}