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/// A single effect entry. Bare `[net]` is the wildcard form
45/// (`arg = None`); parameterized `[net("wttr.in")]` carries an arg
46/// (#207). Sort order matches the `String` ordering of `(name, arg)`
47/// so `BTreeSet<EffectKind>` keeps a canonical iteration order.
48#[derive(Debug, Clone, PartialEq, Eq, PartialOrd, Ord)]
49pub struct EffectKind {
50    pub name: String,
51    pub arg: Option<EffectArg>,
52}
53
54/// Mirror of `lex-ast::EffectArg`. Type-level effects use this so
55/// the checker, lex-vcs ChangeEffectSig, and the runtime gate all
56/// reason about the same shape (#207).
57#[derive(Debug, Clone, PartialEq, Eq, PartialOrd, Ord)]
58pub enum EffectArg {
59    Str(String),
60    Int(i64),
61    Ident(String),
62}
63
64impl EffectKind {
65    /// Bare `[name]` — the wildcard form. Matches anything with the
66    /// same name regardless of arg.
67    pub fn bare(name: impl Into<String>) -> Self {
68        Self { name: name.into(), arg: None }
69    }
70    /// Parameterized `[name("value")]`.
71    pub fn with_str(name: impl Into<String>, arg: impl Into<String>) -> Self {
72        Self { name: name.into(), arg: Some(EffectArg::Str(arg.into())) }
73    }
74    /// Returns true iff `self` is at least as permissive as `other` —
75    /// i.e., a context declaring `self` can satisfy a callee
76    /// requiring `other`. Bare absorbs specific (`[mcp]` accepts
77    /// `[mcp(ocpp)]`); specifics match only themselves (`[mcp(ocpp)]`
78    /// does not accept `[mcp(other)]`); names must match either way.
79    pub fn subsumes(&self, other: &EffectKind) -> bool {
80        if self.name != other.name { return false; }
81        match (&self.arg, &other.arg) {
82            (None, _) => true,             // bare wildcard absorbs anything
83            (Some(_), None) => false,      // specific can't grant bare
84            (Some(a), Some(b)) => a == b,  // specifics match only themselves
85        }
86    }
87    /// Render for diagnostics. `[name]` for bare, `[name("arg")]`
88    /// for string args, `[name(arg)]` for int/ident.
89    pub fn pretty(&self) -> String {
90        match &self.arg {
91            None => self.name.clone(),
92            Some(EffectArg::Str(s)) => format!("{}(\"{}\")", self.name, s),
93            Some(EffectArg::Int(n)) => format!("{}({})", self.name, n),
94            Some(EffectArg::Ident(s)) => format!("{}({})", self.name, s),
95        }
96    }
97}
98
99#[derive(Debug, Clone, Default, PartialEq, Eq)]
100pub struct EffectSet {
101    pub concrete: BTreeSet<EffectKind>,
102    pub var: Option<u32>,
103}
104
105impl EffectSet {
106    pub fn empty() -> Self { Self::default() }
107    /// Backwards-compatible constructor — produces a bare `[name]`
108    /// effect. New code that wants parameterized effects builds an
109    /// `EffectKind` directly and inserts it into `concrete`, or uses
110    /// `EffectSet::singleton_arg`.
111    pub fn singleton(s: impl Into<String>) -> Self {
112        let mut bs = BTreeSet::new();
113        bs.insert(EffectKind::bare(s));
114        Self { concrete: bs, var: None }
115    }
116    /// Parameterized singleton, e.g. `[net("wttr.in")]`.
117    pub fn singleton_arg(name: impl Into<String>, arg: impl Into<String>) -> Self {
118        let mut bs = BTreeSet::new();
119        bs.insert(EffectKind::with_str(name, arg));
120        Self { concrete: bs, var: None }
121    }
122    /// An open effect set: just a row variable, no concrete lower
123    /// bound. Used by stdlib HOF signatures (list.map, list.filter,
124    /// list.fold, option.map, result.map, result.and_then).
125    pub fn open_var(id: u32) -> Self {
126        Self { concrete: BTreeSet::new(), var: Some(id) }
127    }
128    pub fn union(&self, other: &EffectSet) -> EffectSet {
129        EffectSet {
130            concrete: self.concrete.union(&other.concrete).cloned().collect(),
131            var: self.var.or(other.var),
132        }
133    }
134    /// `self` is a subset of `other` iff every entry in `self` is
135    /// subsumed by *some* entry in `other`. Per #207 this honors
136    /// bare-wildcard absorption: `{[mcp(ocpp)]} ⊆ {[mcp]}` holds.
137    pub fn is_subset(&self, other: &EffectSet) -> bool {
138        self.concrete.iter().all(|need| {
139            other.concrete.iter().any(|have| have.subsumes(need))
140        })
141    }
142    pub fn extend(&mut self, other: &EffectSet) {
143        self.concrete.extend(other.concrete.iter().cloned());
144        if self.var.is_none() { self.var = other.var; }
145    }
146    pub fn is_open(&self) -> bool { self.var.is_some() }
147}
148
149impl Ty {
150    pub fn int() -> Self { Ty::Prim(Prim::Int) }
151    pub fn float() -> Self { Ty::Prim(Prim::Float) }
152    pub fn bool() -> Self { Ty::Prim(Prim::Bool) }
153    pub fn str() -> Self { Ty::Prim(Prim::Str) }
154    pub fn bytes() -> Self { Ty::Prim(Prim::Bytes) }
155    pub fn function(params: Vec<Ty>, effects: EffectSet, ret: Ty) -> Self {
156        Ty::Function { params, effects, ret: Box::new(ret) }
157    }
158    pub fn pretty(&self) -> String {
159        match self {
160            Ty::Var(v) => format!("?{}", v),
161            Ty::Prim(p) => match p {
162                Prim::Int => "Int", Prim::Float => "Float", Prim::Bool => "Bool",
163                Prim::Str => "Str", Prim::Bytes => "Bytes",
164            }.into(),
165            Ty::Unit => "Unit".into(),
166            Ty::Never => "Never".into(),
167            Ty::List(t) => format!("List[{}]", t.pretty()),
168            Ty::Tuple(items) => {
169                let parts: Vec<_> = items.iter().map(|t| t.pretty()).collect();
170                format!("({})", parts.join(", "))
171            }
172            Ty::Record(fields) => {
173                let parts: Vec<_> = fields.iter().map(|(k, t)| format!("{} :: {}", k, t.pretty())).collect();
174                format!("{{ {} }}", parts.join(", "))
175            }
176            Ty::Con(name, args) => {
177                if args.is_empty() {
178                    name.clone()
179                } else {
180                    let parts: Vec<_> = args.iter().map(|t| t.pretty()).collect();
181                    format!("{}[{}]", name, parts.join(", "))
182                }
183            }
184            Ty::Function { params, effects, ret } => {
185                let parts: Vec<_> = params.iter().map(|t| t.pretty()).collect();
186                let eff = if effects.concrete.is_empty() && effects.var.is_none() {
187                    String::new()
188                } else {
189                    let mut es: Vec<String> = effects.concrete.iter().map(EffectKind::pretty).collect();
190                    if let Some(v) = effects.var { es.push(format!("?e{}", v)); }
191                    format!("[{}] ", es.join(", "))
192                };
193                format!("({}) -> {}{}", parts.join(", "), eff, ret.pretty())
194            }
195        }
196    }
197}
198
199/// A polymorphic scheme: type with universally-quantified type
200/// variables and effect-row variables.
201#[derive(Debug, Clone)]
202pub struct Scheme {
203    pub vars: Vec<TyVarId>,
204    pub eff_vars: Vec<u32>,
205    pub ty: Ty,
206}
lex_types/types.rs

lex_types/
types.rs
