lex_types/
types.rs

1//! Internal type representation used by the inferencer/checker.
2//!
3//! We model types as either ground constructors (Int, List[T], ...) or
4//! unification variables. The `unifier` module handles solving.
5
6use indexmap::IndexMap;
7use std::collections::BTreeSet;
8
9pub type TyVarId = u32;
10
11#[derive(Debug, Clone, PartialEq)]
12pub enum Ty {
13    Var(TyVarId),
14    Prim(Prim),
15    Unit,
16    Never,
17    List(Box<Ty>),
18    Tuple(Vec<Ty>),
19    /// Sorted alphabetically by field name.
20    Record(IndexMap<String, Ty>),
21    /// e.g. `Result[Int, Str]` or `Option[T]`. Resolved against the type env.
22    Con(String, Vec<Ty>),
23    Function {
24        params: Vec<Ty>,
25        effects: EffectSet,
26        ret: Box<Ty>,
27    },
28}
29
30#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
31pub enum Prim { Int, Float, Bool, Str, Bytes }
32
33/// Effect set with an optional row variable.
34///
35/// `concrete` is the closed lower bound — effect kinds the function
36/// definitely uses. `var` is an open extension point used for effect
37/// polymorphism on stdlib higher-order functions: `list.map[T, U, E]`
38/// declares its callback as `(T) -> [E] U` where `E` is `var: Some(id)`.
39/// At call sites the variable unifies with whatever effect set the
40/// actual closure carries, then propagates to the result.
41///
42/// All call sites that compare or merge concrete-only sets continue to
43/// work via the helper methods, which delegate to `concrete`.
44#[derive(Debug, Clone, Default, PartialEq, Eq)]
45pub struct EffectSet {
46    pub concrete: BTreeSet<String>,
47    pub var: Option<u32>,
48}
49
50impl EffectSet {
51    pub fn empty() -> Self { Self::default() }
52    pub fn singleton(s: impl Into<String>) -> Self {
53        let mut bs = BTreeSet::new();
54        bs.insert(s.into());
55        Self { concrete: bs, var: None }
56    }
57    /// An open effect set: just a row variable, no concrete lower
58    /// bound. Used by stdlib HOF signatures (list.map, list.filter,
59    /// list.fold, option.map, result.map, result.and_then).
60    pub fn open_var(id: u32) -> Self {
61        Self { concrete: BTreeSet::new(), var: Some(id) }
62    }
63    pub fn union(&self, other: &EffectSet) -> EffectSet {
64        EffectSet {
65            concrete: self.concrete.union(&other.concrete).cloned().collect(),
66            var: self.var.or(other.var),
67        }
68    }
69    pub fn is_subset(&self, other: &EffectSet) -> bool {
70        self.concrete.is_subset(&other.concrete)
71    }
72    pub fn extend(&mut self, other: &EffectSet) {
73        self.concrete.extend(other.concrete.iter().cloned());
74        if self.var.is_none() { self.var = other.var; }
75    }
76    pub fn is_open(&self) -> bool { self.var.is_some() }
77}
78
79impl Ty {
80    pub fn int() -> Self { Ty::Prim(Prim::Int) }
81    pub fn float() -> Self { Ty::Prim(Prim::Float) }
82    pub fn bool() -> Self { Ty::Prim(Prim::Bool) }
83    pub fn str() -> Self { Ty::Prim(Prim::Str) }
84    pub fn bytes() -> Self { Ty::Prim(Prim::Bytes) }
85    pub fn function(params: Vec<Ty>, effects: EffectSet, ret: Ty) -> Self {
86        Ty::Function { params, effects, ret: Box::new(ret) }
87    }
88    pub fn pretty(&self) -> String {
89        match self {
90            Ty::Var(v) => format!("?{}", v),
91            Ty::Prim(p) => match p {
92                Prim::Int => "Int", Prim::Float => "Float", Prim::Bool => "Bool",
93                Prim::Str => "Str", Prim::Bytes => "Bytes",
94            }.into(),
95            Ty::Unit => "Unit".into(),
96            Ty::Never => "Never".into(),
97            Ty::List(t) => format!("List[{}]", t.pretty()),
98            Ty::Tuple(items) => {
99                let parts: Vec<_> = items.iter().map(|t| t.pretty()).collect();
100                format!("({})", parts.join(", "))
101            }
102            Ty::Record(fields) => {
103                let parts: Vec<_> = fields.iter().map(|(k, t)| format!("{} :: {}", k, t.pretty())).collect();
104                format!("{{ {} }}", parts.join(", "))
105            }
106            Ty::Con(name, args) => {
107                if args.is_empty() {
108                    name.clone()
109                } else {
110                    let parts: Vec<_> = args.iter().map(|t| t.pretty()).collect();
111                    format!("{}[{}]", name, parts.join(", "))
112                }
113            }
114            Ty::Function { params, effects, ret } => {
115                let parts: Vec<_> = params.iter().map(|t| t.pretty()).collect();
116                let eff = if effects.concrete.is_empty() && effects.var.is_none() {
117                    String::new()
118                } else {
119                    let mut es: Vec<String> = effects.concrete.iter().cloned().collect();
120                    if let Some(v) = effects.var { es.push(format!("?e{}", v)); }
121                    format!("[{}] ", es.join(", "))
122                };
123                format!("({}) -> {}{}", parts.join(", "), eff, ret.pretty())
124            }
125        }
126    }
127}
128
129/// A polymorphic scheme: type with universally-quantified type
130/// variables and effect-row variables.
131#[derive(Debug, Clone)]
132pub struct Scheme {
133    pub vars: Vec<TyVarId>,
134    pub eff_vars: Vec<u32>,
135    pub ty: Ty,
136}
lex_types/types.rs

lex_types/
types.rs
