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.
212/// `pub(crate)` so [`crate::checker::module_record_from_fields`] can base
213/// a resolved dependency module's effect rows at the same offset (#930).
214pub(crate) const EFF_VAR_BASE: u32 = 1000;
215
216/// Parse one signature into a [`Ty`]. `eff_var` is the row-variable
217/// id to use for the definition's open row, if it has one.
218pub fn parse_signature(def: &BuiltinDef, eff_var: u32) -> Result<Ty, String> {
219    let src = format!("type Sig = {}\n", def.ty);
220    let program = lex_syntax::parse_source(&src)
221        .map_err(|e| format!("{}.{}: cannot parse `{}`: {e:?}", def.module, def.name, def.ty))?;
222    let stages = lex_ast::canonicalize_program(&program);
223    let te = stages
224        .iter()
225        .find_map(|s| match s {
226            lex_ast::Stage::TypeDecl(td) => Some(&td.definition),
227            _ => None,
228        })
229        .ok_or_else(|| format!("{}.{}: no type in `{}`", def.module, def.name, def.ty))?;
230    if !matches!(te, lex_ast::TypeExpr::Function { .. }) {
231        return Err(format!("{}.{}: `{}` is not a function type", def.module, def.name, def.ty));
232    }
233    let mut params: Vec<String> = Vec::new();
234    collect_type_vars(te, &mut params);
235    let first_row = params.len();
236    collect_row_vars(te, &mut params);
237    let mut ty = ty_from_canon(te, &params);
238    if params.len() > first_row + 1 {
239        return Err(format!(
240            "{}.{}: `{}` names more than one effect row variable",
241            def.module, def.name, def.ty
242        ));
243    }
244    if params.len() == first_row + 1 {
245        remap_eff_var(&mut ty, first_row as u32, eff_var);
246    }
247    Ok(ty)
248}
249
250/// Single lowercase letters are type variables; everything else is a
251/// named type.
252fn is_type_var(name: &str) -> bool {
253    let mut cs = name.chars();
254    matches!((cs.next(), cs.next()), (Some(c), None) if c.is_ascii_lowercase())
255}
256
257fn collect_type_vars(te: &lex_ast::TypeExpr, out: &mut Vec<String>) {
258    use lex_ast::TypeExpr as T;
259    match te {
260        T::Named { name, args } => {
261            if args.is_empty() && is_type_var(name) && !out.contains(name) {
262                out.push(name.clone());
263            }
264            for a in args {
265                collect_type_vars(a, out);
266            }
267        }
268        T::Function { params, ret, .. } => {
269            for p in params {
270                collect_type_vars(p, out);
271            }
272            collect_type_vars(ret, out);
273        }
274        T::Tuple { items } => {
275            for i in items {
276                collect_type_vars(i, out);
277            }
278        }
279        T::Record { fields } | T::RecordWithSpreads { fields, .. } => {
280            for f in fields {
281                collect_type_vars(&f.ty, out);
282            }
283        }
284        T::Union { variants } => {
285            for v in variants {
286                if let Some(p) = &v.payload {
287                    collect_type_vars(p, out);
288                }
289            }
290        }
291        T::Refined { base, .. } => collect_type_vars(base, out),
292    }
293}
294
295fn collect_row_vars(te: &lex_ast::TypeExpr, out: &mut Vec<String>) {
296    use lex_ast::TypeExpr as T;
297    match te {
298        T::Function { params, effect_row_var, ret, .. } => {
299            if let Some(v) = effect_row_var {
300                if !out.contains(v) {
301                    out.push(v.clone());
302                }
303            }
304            for p in params {
305                collect_row_vars(p, out);
306            }
307            collect_row_vars(ret, out);
308        }
309        T::Named { args, .. } => {
310            for a in args {
311                collect_row_vars(a, out);
312            }
313        }
314        T::Tuple { items } => {
315            for i in items {
316                collect_row_vars(i, out);
317            }
318        }
319        T::Record { fields } | T::RecordWithSpreads { fields, .. } => {
320            for f in fields {
321                collect_row_vars(&f.ty, out);
322            }
323        }
324        T::Union { variants } => {
325            for v in variants {
326                if let Some(p) = &v.payload {
327                    collect_row_vars(p, out);
328                }
329            }
330        }
331        T::Refined { base, .. } => collect_row_vars(base, out),
332    }
333}
334
335fn remap_eff_var(ty: &mut Ty, from: u32, to: u32) {
336    match ty {
337        Ty::Function { params, effects, ret } => {
338            if effects.var == Some(from) {
339                *effects = EffectSet { concrete: effects.concrete.clone(), var: Some(to) };
340            }
341            for p in params {
342                remap_eff_var(p, from, to);
343            }
344            remap_eff_var(ret, from, to);
345        }
346        Ty::List(inner) => remap_eff_var(inner, from, to),
347        Ty::Tuple(items) => {
348            for i in items {
349                remap_eff_var(i, from, to);
350            }
351        }
352        Ty::Record(fields) => {
353            for v in fields.values_mut() {
354                remap_eff_var(v, from, to);
355            }
356        }
357        Ty::Con(_, args) => {
358            for a in args {
359                remap_eff_var(a, from, to);
360            }
361        }
362        Ty::Var(_) | Ty::Prim(_) | Ty::Unit | Ty::Never => {}
363    }
364}
365
366/// The value-level scope of a declared module: a record of its builtins
367/// in declaration order, exactly what `builtins::module_scope` returns
368/// for the hand-written modules. Parsed once per process.
369///
370/// Panics if a signature does not parse; the catalogue is checked by
371/// `lex-types`' tests, so this is a build-time invariant, not a
372/// runtime condition.
373pub fn module_record(module: &str) -> Option<Ty> {
374    static CACHE: OnceLock<HashMap<&'static str, Ty>> = OnceLock::new();
375    let cache = CACHE.get_or_init(|| {
376        let mut out = HashMap::new();
377        for m in declared_modules() {
378            let mut fields = IndexMap::new();
379            for (i, def) in defs_for(m).into_iter().enumerate() {
380                let ty = parse_signature(def, EFF_VAR_BASE + i as u32)
381                    .unwrap_or_else(|e| panic!("stdlib_spec: {e}"));
382                fields.insert(def.name.to_string(), ty);
383            }
384            out.insert(m, Ty::Record(fields));
385        }
386        out
387    });
388    cache.get(module).cloned()
389}
lex_types/stdlib_spec.rs

lex_types/
stdlib_spec.rs
