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

use crate::parser::typing::TypeEnv;
use crate::types::Type;
use std::collections::BTreeSet;

/// Same as chase_actor, with seen set as part of the type. Used for chasing type names from type definitions.
pub fn chase_type<'a>(
    seen: &mut BTreeSet<&'a str>,
    res: &mut Vec<&'a str>,
    env: &'a TypeEnv,
    t: &'a Type,
) -> crate::Result<()> {
    use Type::*;
    match t {
        Var(id) => {
            if seen.insert(id) {
                let t = env.find_type(id)?;
                chase_type(seen, res, env, t)?;
                res.push(id);
            }
        }
        Opt(ty) | Vec(ty) => chase_type(seen, res, env, ty)?,
        Record(fs) | Variant(fs) => {
            for f in fs.iter() {
                chase_type(seen, res, env, &f.ty)?;
            }
        }
        Func(f) => {
            for ty in f.args.iter().chain(f.rets.iter()) {
                chase_type(seen, res, env, ty)?;
            }
        }
        Service(ms) => {
            for (_, ty) in ms.iter() {
                chase_type(seen, res, env, ty)?;
            }
        }
        Class(args, t) => {
            for arg in args.iter() {
                chase_type(seen, res, env, arg)?;
            }
            chase_type(seen, res, env, t)?;
        }
        _ => (),
    }
    Ok(())
}

/// Gather type definitions mentioned in actor, return the non-recursive type names in topological order.
/// Recursive types can appear in any order.
pub fn chase_actor<'a>(env: &'a TypeEnv, actor: &'a Type) -> crate::Result<Vec<&'a str>> {
    let mut seen = BTreeSet::new();
    let mut res = Vec::new();
    chase_type(&mut seen, &mut res, env, actor)?;
    Ok(res)
}

pub fn chase_types<'a>(env: &'a TypeEnv, tys: &'a [Type]) -> crate::Result<Vec<&'a str>> {
    let mut seen = BTreeSet::new();
    let mut res = Vec::new();
    for t in tys.iter() {
        chase_type(&mut seen, &mut res, env, t)?;
    }
    Ok(res)
}

/// Given a `def_list` produced by the `chase_actor` function, infer which types are recursive
pub fn infer_rec<'a>(
    env: &'a TypeEnv,
    def_list: &'a [&'a str],
) -> crate::Result<BTreeSet<&'a str>> {
    let mut seen = BTreeSet::new();
    let mut res = BTreeSet::new();
    fn go<'a>(
        seen: &mut BTreeSet<&'a str>,
        res: &mut BTreeSet<&'a str>,
        env: &'a TypeEnv,
        t: &'a Type,
    ) -> crate::Result<()> {
        use Type::*;
        match t {
            Var(id) => {
                if seen.insert(id) {
                    res.insert(id);
                }
            }
            Opt(ty) | Vec(ty) => go(seen, res, env, ty)?,
            Record(fs) | Variant(fs) => {
                for f in fs.iter() {
                    go(seen, res, env, &f.ty)?;
                }
            }
            Func(f) => {
                for ty in f.args.iter().chain(f.rets.iter()) {
                    go(seen, res, env, ty)?;
                }
            }
            Service(ms) => {
                for (_, ty) in ms.iter() {
                    go(seen, res, env, ty)?;
                }
            }
            Class(args, t) => {
                for arg in args.iter() {
                    go(seen, res, env, arg)?;
                }
                go(seen, res, env, t)?;
            }
            _ => (),
        }
        Ok(())
    }
    for var in def_list.iter() {
        let t = env.0.get(*var).unwrap();
        go(&mut seen, &mut res, env, t)?;
        seen.insert(var);
    }
    Ok(res)
}