lex_types/
stdlib_spec.rs

1//! Declarative stdlib builtin catalogue (#778).
2//!
3//! One [`BuiltinDef`] per builtin is the single source for everything
4//! the toolchain knows about it: the type-checker's module scope
5//! ([`module_record`]), the runtime's purity answer and dispatch table
6//! (`lex-runtime` keys its implementations by the same `(module, name)`
7//! and a test there asserts the two sets agree), and the generated
8//! stdlib reference in `docs/AGENT.md` (`lex docs --stdlib-spec`).
9//!
10//! Signatures are written in Lex type syntax and parsed by the real
11//! parser, so the catalogue cannot drift from what `lex check` accepts.
12//! Type variables are single lowercase letters (`a`, `b`); an open
13//! effect row is written `[| E]` exactly as in user code, and the same
14//! `E` on a closure parameter and on the result ties the two rows
15//! together (`list.map`'s closure effects flow to the call).
16//!
17//! Modules migrate here one at a time; `builtins::module_scope` still
18//! holds the hand-written signatures for the rest. Adding a builtin to a
19//! migrated module means one entry here plus one implementation in the
20//! runtime table, and nothing else.
21
22use crate::env::ty_from_canon;
23use crate::types::{EffectSet, Ty};
24use indexmap::IndexMap;
25use std::collections::HashMap;
26use std::sync::OnceLock;
27
28/// Which index convention a builtin's integer positions use. Recorded
29/// so the stdlib reference states it and a runtime test checks it;
30/// it is documentation, not a semantic switch (#778).
31#[derive(Debug, Clone, Copy, PartialEq, Eq)]
32pub enum IndexConvention {
33    /// No integer positions in the signature.
34    None,
35    /// Positions and lengths count UTF-8 bytes.
36    Byte,
37    /// Positions and lengths count Unicode scalar values.
38    Codepoint,
39}
40
41/// How a builtin is executed.
42#[derive(Debug, Clone, Copy, PartialEq, Eq)]
43pub enum BuiltinKind {
44    /// Effect-free; dispatched through the runtime's pure table with
45    /// owned arguments.
46    Pure,
47    /// Effect-free but lowered by the compiler / VM (the list
48    /// higher-order functions); the runtime table has no entry.
49    VmNative,
50    /// Dispatched through the effect handler under the runtime policy.
51    Effect,
52}
53
54#[derive(Debug, Clone, Copy)]
55pub struct BuiltinDef {
56    pub module: &'static str,
57    pub name: &'static str,
58    /// Lex type syntax, e.g. `(Str, Str, Int) -> Option[Int]`.
59    pub ty: &'static str,
60    pub kind: BuiltinKind,
61    pub index: IndexConvention,
62    /// One or two sentences for the reference; states edge cases.
63    pub doc: &'static str,
64    /// Cost as a function of the inputs, when it is not obvious.
65    pub complexity: Option<&'static str>,
66}
67
68const fn pure(
69    module: &'static str,
70    name: &'static str,
71    ty: &'static str,
72    index: IndexConvention,
73    doc: &'static str,
74    complexity: Option<&'static str>,
75) -> BuiltinDef {
76    BuiltinDef { module, name, ty, kind: BuiltinKind::Pure, index, doc, complexity }
77}
78
79const fn native(
80    module: &'static str,
81    name: &'static str,
82    ty: &'static str,
83    doc: &'static str,
84    complexity: Option<&'static str>,
85) -> BuiltinDef {
86    BuiltinDef {
87        module,
88        name,
89        ty,
90        kind: BuiltinKind::VmNative,
91        index: IndexConvention::None,
92        doc,
93        complexity,
94    }
95}
96
97use IndexConvention::{Byte, Codepoint, None as NoIndex};
98
99/// Every declared builtin, in the order the stdlib reference lists them
100/// (module order, then declaration order within a module).
101pub const BUILTINS: &[BuiltinDef] = &[
102    // ── std.str ─────────────────────────────────────────────────────
103    pure("str", "is_empty", "(Str) -> Bool", NoIndex,
104        "`true` when the string has no bytes.", None),
105    pure("str", "to_int", "(Str) -> Option[Int]", NoIndex,
106        "Parse a decimal integer (optional leading `-`); `None` on any other input.", None),
107    pure("str", "to_float", "(Str) -> Option[Float]", NoIndex,
108        "Parse a float literal; `None` on any other input.", None),
109    pure("str", "concat", "(Str, Str) -> Str", NoIndex,
110        "Concatenate two strings; `a + b` is the same operation.", None),
111    pure("str", "len", "(Str) -> Int", Byte,
112        "Length in UTF-8 bytes, not characters: `str.len(\"é\")` is 2.", Some("O(1)")),
113    pure("str", "char_at", "(Str, Int) -> Str", Byte,
114        "The byte at a byte index as a one-character string for ASCII bytes; `\"\"` for a non-ASCII byte or an index out of range. Never fails.",
115        Some("O(1)")),
116    pure("str", "split", "(Str, Str) -> List[Str]", NoIndex,
117        "Split on a separator; an empty separator splits into characters.", None),
118    pure("str", "join", "(List[Str], Str) -> Str", NoIndex,
119        "Join the elements with a separator; fails if an element is not a `Str`.", None),
120    pure("str", "starts_with", "(Str, Str) -> Bool", NoIndex,
121        "`true` when the first string begins with the second.", None),
122    pure("str", "ends_with", "(Str, Str) -> Bool", NoIndex,
123        "`true` when the first string ends with the second.", None),
124    pure("str", "contains", "(Str, Str) -> Bool", NoIndex,
125        "`true` when the second string occurs anywhere in the first.", None),
126    pure("str", "cmp", "(Str, Str) -> Int", NoIndex,
127        "Three-way byte-order comparison: `-1`, `0` or `1`. Use the comparison operators for a `Bool` (#440).", None),
128    pure("str", "replace", "(Str, Str, Str) -> Str", NoIndex,
129        "Replace every non-overlapping occurrence of the second string with the third.", None),
130    pure("str", "trim", "(Str) -> Str", NoIndex,
131        "Strip leading and trailing Unicode whitespace.", None),
132    pure("str", "to_upper", "(Str) -> Str", NoIndex,
133        "Unicode uppercase.", None),
134    pure("str", "to_lower", "(Str) -> Str", NoIndex,
135        "Unicode lowercase.", None),
136    pure("str", "strip_prefix", "(Str, Str) -> Option[Str]", NoIndex,
137        "The remainder after a prefix, or `None` when the prefix is absent.", None),
138    pure("str", "strip_suffix", "(Str, Str) -> Option[Str]", NoIndex,
139        "The remainder before a suffix, or `None` when the suffix is absent.", None),
140    pure("str", "slice", "(Str, Int, Int) -> Str", Codepoint,
141        "Half-open range of codepoint indices `[lo, hi)`; indices clamp to the codepoint count and a reversed range fails (#620).",
142        Some("O(distance from the previous slice or find on the same string) (#764)")),
143    pure("str", "is_ascii", "(Str) -> Bool", NoIndex,
144        "`true` when every byte is below 128; one native pass (#768).", Some("O(len)")),
145    pure("str", "find", "(Str, Str, Int) -> Option[Int]", Codepoint,
146        "Codepoint index of the first occurrence of the needle at or after `from`; `from` clamps to the string and an empty needle matches at `from` (#764).",
147        Some("O(distance scanned)")),
148    pure("str", "find_any", "(Str, Str, Int) -> Option[Int]", Codepoint,
149        "Codepoint index of the first character at or after `from` that occurs in the set string (#764).",
150        Some("O(distance scanned)")),
151    // ── std.list ────────────────────────────────────────────────────
152    native("list", "map", "(List[a], (a) -> [| E] b) -> [| E] List[b]",
153        "Apply the closure to every element; the closure's effects flow to the call.", None),
154    native("list", "par_map", "(List[a], (a) -> [| E] b) -> [| E] List[b]",
155        "`map` on a worker pool capped by `LEX_PAR_MAX_CONCURRENCY` (#305).", None),
156    native("list", "sort_by", "(List[a], (a) -> [| E] b) -> [| E] List[a]",
157        "Stable sort by the key the closure derives; `Int`, `Float` and `Str` keys order natively, other shapes keep their input order (#338).",
158        Some("O(n log n)")),
159    native("list", "filter", "(List[a], (a) -> [| E] Bool) -> [| E] List[a]",
160        "Keep the elements the closure accepts.", None),
161    native("list", "fold", "(List[a], b, (b, a) -> [| E] b) -> [| E] b",
162        "Left fold from the initial accumulator.", None),
163    pure("list", "len", "(List[a]) -> Int", NoIndex,
164        "Number of elements.", Some("O(1)")),
165    pure("list", "is_empty", "(List[a]) -> Bool", NoIndex,
166        "`true` when the list has no elements.", Some("O(1)")),
167    pure("list", "range", "(Int, Int) -> List[Int]", NoIndex,
168        "Integers from `lo` up to but excluding `hi`; empty when `hi <= lo`.", None),
169    pure("list", "head", "(List[a]) -> Option[a]", NoIndex,
170        "The first element, or `None` for an empty list.", Some("O(1)")),
171    pure("list", "tail", "(List[a]) -> List[a]", NoIndex,
172        "Every element but the first; empty for an empty list.", Some("O(1) when the list is uniquely owned, otherwise O(n) (#774)")),
173    pure("list", "concat", "(List[a], List[a]) -> List[a]", NoIndex,
174        "The first list followed by the second.", None),
175    pure("list", "reverse", "(List[a]) -> List[a]", NoIndex,
176        "Elements in reverse order.", None),
177    pure("list", "cons", "(a, List[a]) -> List[a]", NoIndex,
178        "Prepend one element (#334).", Some("amortised O(1)")),
179    pure("list", "enumerate", "(List[a]) -> List[(Int, a)]", NoIndex,
180        "Pair every element with its zero-based index.", None),
181];
182
183/// Modules whose signatures come from this catalogue rather than from
184/// the hand-written tables in `builtins::module_scope`.
185pub fn declared_modules() -> Vec<&'static str> {
186    let mut out: Vec<&'static str> = Vec::new();
187    for d in BUILTINS {
188        if !out.contains(&d.module) {
189            out.push(d.module);
190        }
191    }
192    out
193}
194
195pub fn is_declared_module(module: &str) -> bool {
196    BUILTINS.iter().any(|d| d.module == module)
197}
198
199/// The definitions of one module, in declaration order.
200pub fn defs_for(module: &str) -> Vec<&'static BuiltinDef> {
201    BUILTINS.iter().filter(|d| d.module == module).collect()
202}
203
204pub fn lookup(module: &str, name: &str) -> Option<&'static BuiltinDef> {
205    BUILTINS.iter().find(|d| d.module == module && d.name == name)
206}
207
208/// Effect-row variable ids handed to declared builtins. Kept clear of
209/// the type-variable ids (`0..`) so a module scheme never has a type
210/// variable and a row variable sharing an id, and unique per builtin
211/// so two higher-order functions in one module never share a row.
212const EFF_VAR_BASE: u32 = 1000;
213
214/// Parse one signature into a [`Ty`]. `eff_var` is the row-variable
215/// id to use for the definition's open row, if it has one.
216pub fn parse_signature(def: &BuiltinDef, eff_var: u32) -> Result<Ty, String> {
217    let src = format!("type Sig = {}\n", def.ty);
218    let program = lex_syntax::parse_source(&src)
219        .map_err(|e| format!("{}.{}: cannot parse `{}`: {e:?}", def.module, def.name, def.ty))?;
220    let stages = lex_ast::canonicalize_program(&program);
221    let te = stages
222        .iter()
223        .find_map(|s| match s {
224            lex_ast::Stage::TypeDecl(td) => Some(&td.definition),
225            _ => None,
226        })
227        .ok_or_else(|| format!("{}.{}: no type in `{}`", def.module, def.name, def.ty))?;
228    if !matches!(te, lex_ast::TypeExpr::Function { .. }) {
229        return Err(format!("{}.{}: `{}` is not a function type", def.module, def.name, def.ty));
230    }
231    let mut params: Vec<String> = Vec::new();
232    collect_type_vars(te, &mut params);
233    let first_row = params.len();
234    collect_row_vars(te, &mut params);
235    let mut ty = ty_from_canon(te, &params);
236    if params.len() > first_row + 1 {
237        return Err(format!(
238            "{}.{}: `{}` names more than one effect row variable",
239            def.module, def.name, def.ty
240        ));
241    }
242    if params.len() == first_row + 1 {
243        remap_eff_var(&mut ty, first_row as u32, eff_var);
244    }
245    Ok(ty)
246}
247
248/// Single lowercase letters are type variables; everything else is a
249/// named type.
250fn is_type_var(name: &str) -> bool {
251    let mut cs = name.chars();
252    matches!((cs.next(), cs.next()), (Some(c), None) if c.is_ascii_lowercase())
253}
254
255fn collect_type_vars(te: &lex_ast::TypeExpr, out: &mut Vec<String>) {
256    use lex_ast::TypeExpr as T;
257    match te {
258        T::Named { name, args } => {
259            if args.is_empty() && is_type_var(name) && !out.contains(name) {
260                out.push(name.clone());
261            }
262            for a in args {
263                collect_type_vars(a, out);
264            }
265        }
266        T::Function { params, ret, .. } => {
267            for p in params {
268                collect_type_vars(p, out);
269            }
270            collect_type_vars(ret, out);
271        }
272        T::Tuple { items } => {
273            for i in items {
274                collect_type_vars(i, out);
275            }
276        }
277        T::Record { fields } | T::RecordWithSpreads { fields, .. } => {
278            for f in fields {
279                collect_type_vars(&f.ty, out);
280            }
281        }
282        T::Union { variants } => {
283            for v in variants {
284                if let Some(p) = &v.payload {
285                    collect_type_vars(p, out);
286                }
287            }
288        }
289        T::Refined { base, .. } => collect_type_vars(base, out),
290    }
291}
292
293fn collect_row_vars(te: &lex_ast::TypeExpr, out: &mut Vec<String>) {
294    use lex_ast::TypeExpr as T;
295    match te {
296        T::Function { params, effect_row_var, ret, .. } => {
297            if let Some(v) = effect_row_var {
298                if !out.contains(v) {
299                    out.push(v.clone());
300                }
301            }
302            for p in params {
303                collect_row_vars(p, out);
304            }
305            collect_row_vars(ret, out);
306        }
307        T::Named { args, .. } => {
308            for a in args {
309                collect_row_vars(a, out);
310            }
311        }
312        T::Tuple { items } => {
313            for i in items {
314                collect_row_vars(i, out);
315            }
316        }
317        T::Record { fields } | T::RecordWithSpreads { fields, .. } => {
318            for f in fields {
319                collect_row_vars(&f.ty, out);
320            }
321        }
322        T::Union { variants } => {
323            for v in variants {
324                if let Some(p) = &v.payload {
325                    collect_row_vars(p, out);
326                }
327            }
328        }
329        T::Refined { base, .. } => collect_row_vars(base, out),
330    }
331}
332
333fn remap_eff_var(ty: &mut Ty, from: u32, to: u32) {
334    match ty {
335        Ty::Function { params, effects, ret } => {
336            if effects.var == Some(from) {
337                *effects = EffectSet { concrete: effects.concrete.clone(), var: Some(to) };
338            }
339            for p in params {
340                remap_eff_var(p, from, to);
341            }
342            remap_eff_var(ret, from, to);
343        }
344        Ty::List(inner) => remap_eff_var(inner, from, to),
345        Ty::Tuple(items) => {
346            for i in items {
347                remap_eff_var(i, from, to);
348            }
349        }
350        Ty::Record(fields) => {
351            for v in fields.values_mut() {
352                remap_eff_var(v, from, to);
353            }
354        }
355        Ty::Con(_, args) => {
356            for a in args {
357                remap_eff_var(a, from, to);
358            }
359        }
360        Ty::Var(_) | Ty::Prim(_) | Ty::Unit | Ty::Never => {}
361    }
362}
363
364/// The value-level scope of a declared module: a record of its builtins
365/// in declaration order, exactly what `builtins::module_scope` returns
366/// for the hand-written modules. Parsed once per process.
367///
368/// Panics if a signature does not parse; the catalogue is checked by
369/// `lex-types`' tests, so this is a build-time invariant, not a
370/// runtime condition.
371pub fn module_record(module: &str) -> Option<Ty> {
372    static CACHE: OnceLock<HashMap<&'static str, Ty>> = OnceLock::new();
373    let cache = CACHE.get_or_init(|| {
374        let mut out = HashMap::new();
375        for m in declared_modules() {
376            let mut fields = IndexMap::new();
377            for (i, def) in defs_for(m).into_iter().enumerate() {
378                let ty = parse_signature(def, EFF_VAR_BASE + i as u32)
379                    .unwrap_or_else(|e| panic!("stdlib_spec: {e}"));
380                fields.insert(def.name.to_string(), ty);
381            }
382            out.insert(m, Ty::Record(fields));
383        }
384        out
385    });
386    cache.get(module).cloned()
387}
lex_types/stdlib_spec.rs

lex_types/
stdlib_spec.rs
