Skip to main content

decl_lang/
infer.rs

1//! Expression-level static analysis — a port of the reference
2//! implementation's infer.ts: type inference, assignability (§3.18,
3//! strict S ⊑ T), the absence discipline (§4.10) with its two narrowing
4//! rules, and the `match` static checks (§4.7). Inference is
5//! conservative: a form whose type cannot be determined yields `unknown`
6//! (rt None) and suppresses downstream judgments rather than guessing.
7use crate::ast::*;
8use crate::semantics::*;
9use crate::subsume::subsumes;
10use num_bigint::BigInt;
11use std::cell::RefCell;
12use std::collections::{HashMap, HashSet};
13use std::rc::Rc;
14
15#[derive(Clone)]
16/// an inferred type: what is known of an expression's type, and whether it may be absent
17pub struct Ty {
18    /// the type, when known
19    pub rt: Option<RT>,
20    /// the expression may be absent (an optional member read without `?.` or `??`)
21    pub abs: bool,
22}
23/// The unknown type.
24pub fn unk() -> Ty {
25    Ty {
26        rt: None,
27        abs: false,
28    }
29}
30/// A present type.
31pub fn tyv(rt: Option<RT>) -> Ty {
32    Ty { rt, abs: false }
33}
34/// A primitive type by name.
35pub fn prim(name: &str) -> RT {
36    ty(RTk::Prim(name.to_string()))
37}
38fn bool_ty() -> Ty {
39    tyv(Some(prim("bool")))
40}
41
42/// receives a finding: its code and its message
43pub type Report = Rc<dyn Fn(&str, String)>;
44
45#[derive(Clone)]
46/// the inference context: the environment, the local variables, the narrowing
47/// guards in force, the reporter
48pub struct Ctx {
49    /// the environment names resolve in
50    pub env: Rc<Env>,
51    /// where findings go
52    pub report: Report,
53    /// the local variables in scope, with their types
54    pub vars: HashMap<String, Ty>,
55    /// the names bound by the expression itself — function and lambda parameters,
56    /// comprehension variables, match bindings: they shadow a record's members (§4.3)
57    pub locals: HashSet<String>,
58    /// the paths a guard proved present
59    pub present: HashSet<String>,
60    /// the paths a guard proved non-null
61    pub nonnull: HashSet<String>,
62    /// the constants' inferred types, memoized
63    pub const_memo: Rc<RefCell<HashMap<String, Ty>>>,
64    /// the expression under inference (shared by child contexts): what a report is anchored to
65    pub pos: Rc<RefCell<Option<Rc<Expr>>>>,
66    /// Phase 6 foundations: every inferred node's type, and every name's resolution (the language server's tables)
67    pub record: Option<Rc<dyn Fn(&Rc<Expr>, &Ty)>>,
68    /// called with every name's resolution (the language server's navigation)
69    pub resolve_hook: Option<Rc<dyn Fn(&Rc<Expr>, Option<Target>)>>,
70    /// the expression's value is bound at evaluation — an output, an input's
71    /// fallback, a member's default or derived expression, and every position
72    /// inside a literal there: an object whose entries the static type does not
73    /// fix is validated then, not rejected here (§3.18, D31 amended, v0.4.4)
74    pub binding: bool,
75}
76
77/// what a name denotes: the declaration behind it, imports followed to their module
78#[derive(Clone)]
79pub struct Target {
80    /// what the name is: var, const, func, output, input, namespace, type, diagnostic, export
81    pub kind: &'static str, // var | const | func | output | input | namespace | type | diagnostic | export
82    /// the environment declaring it; none for a local
83    pub env: Option<Rc<Env>>,
84    /// its name
85    pub name: String,
86}
87/// Resolve a name in the context: a local variable first, then the environment and its imports.
88pub fn resolve_name(cx: &Ctx, name: &str) -> Option<Target> {
89    if cx.vars.contains_key(name) {
90        return Some(Target {
91            kind: "var",
92            env: None,
93            name: name.to_string(),
94        });
95    }
96    resolve_in(&cx.env, name)
97}
98/// Resolve a name in an environment: its declarations, then its imports.
99pub fn resolve_in(env: &Rc<Env>, name: &str) -> Option<Target> {
100    let t = |kind: &'static str| {
101        Some(Target {
102            kind,
103            env: Some(env.clone()),
104            name: name.to_string(),
105        })
106    };
107    if env.consts.borrow().contains_key(name) {
108        return t("const");
109    }
110    if env.funcs.borrow().contains_key(name) {
111        return t("func");
112    }
113    if env.outputs.borrow().iter().any(|(o, _, _)| o == name) {
114        return t("output");
115    }
116    if env.inputs.borrow().contains_key(name) {
117        return t("input");
118    }
119    let im = env.imports.borrow().get(name).cloned();
120    if let Some(im) = im {
121        return resolve_in(&im.env, &im.name).or(Some(Target {
122            kind: "export",
123            env: Some(im.env.clone()),
124            name: im.name.clone(),
125        }));
126    }
127    if env.namespaces.borrow().contains_key(name) {
128        return t("namespace");
129    }
130    if env.type_asts.borrow().contains_key(name) {
131        return t("type");
132    }
133    if env.diags.borrow().contains_key(name) {
134        return t("diagnostic");
135    }
136    None
137}
138impl Ctx {
139    /// Report a finding.
140    pub fn report(&self, code: &str, msg: String) {
141        (self.report)(code, msg)
142    }
143    /// A child context: the same environment and reporter, its own variables.
144    pub fn child(&self) -> Ctx {
145        self.clone()
146    }
147    /// The context over another environment (an imported module's).
148    pub fn with_env(&self, env: Rc<Env>) -> Ctx {
149        let mut c = self.clone();
150        c.env = env;
151        c
152    }
153}
154// ---------------- §9.3: cycles visible in the type structure ----------------
155/// the record type a nested literal binds to, when the expected type says: an element, a map value
156fn elem_rt(rt: Option<&RT>) -> Option<RT> {
157    match rt.map(|r| &r.k) {
158        Some(RTk::Arr { elem, .. }) => Some(elem.clone()),
159        Some(RTk::Map { val, .. }) => Some(val.clone()),
160        _ => None,
161    }
162}
163/// The sibling members an expression names bare. Lambda parameters,
164/// comprehension variables, and match bindings shadow them; so do the
165/// members of a nested construction (its declared members when the
166/// expected type is known, always its keys); a navigation names no sibling.
167pub fn sibling_reads(
168    e: &Expr,
169    siblings: &HashSet<String>,
170    bound: &HashSet<String>,
171    out: &mut Vec<String>,
172    rt: Option<&RT>,
173) {
174    let with_vars = |vs: &[String], b: &HashSet<String>| -> HashSet<String> {
175        let mut b2 = b.clone();
176        for v in vs {
177            b2.insert(v.clone());
178        }
179        b2
180    };
181    match e {
182        Expr::Name(n) => {
183            if !bound.contains(n) && siblings.contains(n) && !out.contains(n) {
184                out.push(n.clone());
185            }
186        }
187        Expr::Template(parts) => {
188            for p in parts {
189                if let TPart::Expr(x) = p {
190                    sibling_reads(x, siblings, bound, out, None);
191                }
192            }
193        }
194        Expr::Obj(entries) => {
195            let rec = match rt.map(|r| &r.k) {
196                Some(RTk::Rec(r)) => Some(r),
197                _ => None,
198            };
199            let mut keys: Vec<String> = entries.iter().map(|(k, _)| k.clone()).collect();
200            if let Some(r) = &rec {
201                keys.extend(r.members.borrow().iter().map(|m| m.name.clone()));
202            }
203            let inner = with_vars(&keys, bound);
204            for (k, v) in entries {
205                if let Expr::Spread(x) = &**v {
206                    sibling_reads(x, siblings, bound, out, None);
207                    continue;
208                }
209                let mt: Option<RT> = match (&rec, rt.map(|r| &r.k)) {
210                    (Some(r), _) => r
211                        .members
212                        .borrow()
213                        .iter()
214                        .find(|m| m.name == *k)
215                        .and_then(|m| m.ty.clone()),
216                    (None, Some(RTk::Map { val, .. })) => Some(val.clone()),
217                    _ => None,
218                };
219                sibling_reads(v, siblings, &inner, out, mt.as_ref());
220            }
221        }
222        Expr::Spread(x) => sibling_reads(x, siblings, bound, out, None),
223        Expr::Arr(items) => {
224            for (spread, x) in items {
225                let t = if *spread { rt.cloned() } else { elem_rt(rt) };
226                sibling_reads(x, siblings, bound, out, t.as_ref());
227            }
228        }
229        Expr::Comp { head, clauses }
230        | Expr::MapComp {
231            val: head, clauses, ..
232        } => {
233            let mut b = bound.clone();
234            for cl in clauses {
235                sibling_reads(&cl.iter, siblings, &b, out, None);
236                b.insert(cl.v.clone());
237                for f in &cl.filters {
238                    sibling_reads(f, siblings, &b, out, None);
239                }
240            }
241            if let Expr::MapComp { key, .. } = e {
242                sibling_reads(key, siblings, &b, out, None);
243            }
244            let t = elem_rt(rt);
245            sibling_reads(head, siblings, &b, out, t.as_ref());
246        }
247        Expr::Bin { l, r, .. } => {
248            sibling_reads(l, siblings, bound, out, None);
249            sibling_reads(r, siblings, bound, out, None);
250        }
251        Expr::Un { x, .. } => sibling_reads(x, siblings, bound, out, None),
252        Expr::Paren(x) => sibling_reads(x, siblings, bound, out, rt),
253        Expr::If { c, t, f } => {
254            sibling_reads(c, siblings, bound, out, None);
255            sibling_reads(t, siblings, bound, out, rt);
256            sibling_reads(f, siblings, bound, out, rt);
257        }
258        Expr::Lambda { params, body } => {
259            sibling_reads(body, siblings, &with_vars(params, bound), out, None)
260        }
261        Expr::Call { fun, args } => {
262            sibling_reads(fun, siblings, bound, out, None);
263            for a in args {
264                sibling_reads(a, siblings, bound, out, None);
265            }
266        }
267        Expr::Member { x, .. } => sibling_reads(x, siblings, bound, out, None),
268        Expr::Index { x, i } => {
269            sibling_reads(x, siblings, bound, out, None);
270            sibling_reads(i, siblings, bound, out, None);
271        }
272        Expr::With { base, patch } => {
273            sibling_reads(base, siblings, bound, out, rt);
274            sibling_reads(patch, siblings, bound, out, rt);
275        }
276        Expr::Match { subject, arms } => {
277            sibling_reads(subject, siblings, bound, out, None);
278            for a in arms {
279                sibling_reads(
280                    &a.body,
281                    siblings,
282                    &with_vars(std::slice::from_ref(&a.v), bound),
283                    out,
284                    rt,
285                );
286            }
287        }
288        _ => {} // Lit, UnitLit, Ctx, Referrers, Pattern
289    }
290}
291/// A dependency cycle among a record's members through bare sibling names
292/// (§9.3, E4113): the members' default and derived expressions, with a
293/// construction's entries in place of the members it supplies (the
294/// construction's own members shadow the names bound around it, `bound`).
295/// The cycle, or None.
296pub fn member_cycle(
297    rt: &RT,
298    entries: Option<&Vec<(String, Rc<Expr>)>>,
299    bound: &HashSet<String>,
300) -> Option<Vec<String>> {
301    let RTk::Rec(rec) = &rt.k else { return None };
302    let members = rec.members.borrow().clone();
303    let siblings: HashSet<String> = members.iter().map(|m| m.name.clone()).collect();
304    let mut exprs: Vec<(String, Rc<Expr>, bool)> = vec![];
305    let mut member_type: HashMap<String, Option<RT>> = HashMap::new();
306    for m in members.iter() {
307        member_type.insert(m.name.clone(), m.ty.clone());
308        let x = match m.kind {
309            MKind::Der => m.expr.clone(),
310            MKind::Dflt => m.dflt.clone(),
311            _ => None,
312        };
313        if let Some(x) = x {
314            exprs.push((m.name.clone(), x, false));
315        }
316    }
317    if let Some(es) = entries {
318        for (k, v) in es {
319            if matches!(&**v, Expr::Spread(_)) || !siblings.contains(k) {
320                continue;
321            }
322            exprs.retain(|(n, _, _)| n != k);
323            exprs.push((k.clone(), v.clone(), true));
324        }
325    }
326    let empty = HashSet::new();
327    let mut edges: HashMap<String, Vec<String>> = HashMap::new();
328    let order: Vec<String> = exprs.iter().map(|(n, _, _)| n.clone()).collect();
329    for (name, x, supplied) in &exprs {
330        let mut out = vec![];
331        // a supplied entry was written where `bound` is in scope; a declared
332        // expression sees only what the type binds
333        let b = if *supplied { bound } else { &empty };
334        let mt = member_type.get(name).cloned().flatten();
335        sibling_reads(x, &siblings, b, &mut out, mt.as_ref());
336        edges.insert(name.clone(), out);
337    }
338    fn visit(
339        n: &str,
340        edges: &HashMap<String, Vec<String>>,
341        state: &mut HashMap<String, u8>,
342        stack: &mut Vec<String>,
343    ) -> Option<Vec<String>> {
344        match state.get(n) {
345            Some(2) => return None,
346            Some(1) => {
347                let i = stack.iter().position(|s| s == n).unwrap_or(0);
348                let mut c: Vec<String> = stack[i..].to_vec();
349                c.push(n.to_string());
350                return Some(c);
351            }
352            _ => {}
353        }
354        state.insert(n.to_string(), 1);
355        stack.push(n.to_string());
356        if let Some(ms) = edges.get(n) {
357            for m in ms {
358                if let Some(c) = visit(m, edges, state, stack) {
359                    return Some(c);
360                }
361            }
362        }
363        stack.pop();
364        state.insert(n.to_string(), 2);
365        None
366    }
367    let mut state = HashMap::new();
368    let mut stack = vec![];
369    for n in &order {
370        if let Some(c) = visit(n, &edges, &mut state, &mut stack) {
371            return Some(c);
372        }
373    }
374    None
375}
376
377/// A fresh context over an environment.
378pub fn make_ctx(env: Rc<Env>, report: Report) -> Ctx {
379    Ctx {
380        env,
381        report,
382        vars: HashMap::new(),
383        locals: HashSet::new(),
384        present: HashSet::new(),
385        nonnull: HashSet::new(),
386        const_memo: Rc::new(RefCell::new(HashMap::new())),
387        pos: Rc::new(RefCell::new(None)),
388        record: None,
389        resolve_hook: None,
390        binding: false,
391    }
392}
393
394// ---------------- JS-faithful helpers ----------------
395/// The value's JavaScript type name, as the reference tags it.
396pub fn js_typeof(v: &Value) -> &'static str {
397    match v {
398        Value::Bool(_) => "boolean",
399        Value::Int(_) => "bigint",
400        Value::Float(_) => "number",
401        Value::Str(_) => "string",
402        _ => "object",
403    }
404}
405/// The value's text as JavaScript would print it.
406pub fn js_str(v: &Value) -> String {
407    match v {
408        Value::Null => "null".into(),
409        Value::Bool(b) => {
410            if *b {
411                "true".into()
412            } else {
413                "false".into()
414            }
415        }
416        Value::Int(i) => i.to_string(),
417        Value::Float(f) => js_num_str(*f),
418        Value::Str(s) => s.to_string(),
419        other => format!("{other:?}"),
420    }
421}
422/// A resolved type's kind, as a word.
423pub fn tag(rt: &RT) -> &'static str {
424    match &rt.k {
425        RTk::Prim(_) => "prim",
426        RTk::Lit(_) => "lit",
427        RTk::Range { .. } => "range",
428        RTk::Pattern { .. } => "pattern",
429        RTk::Arr { .. } => "arr",
430        RTk::Map { .. } => "map",
431        RTk::Union(_) => "union",
432        RTk::IsectN(_) => "isectN",
433        RTk::Rec(_) => "rec",
434        RTk::Pred { .. } => "pred",
435        RTk::Ref(_) => "ref",
436        RTk::Quantity(_) => "quantity",
437        RTk::Func { .. } => "func",
438        RTk::Any => "any",
439    }
440}
441/// a function's unknown result is carried as `any`
442fn ret_of(rt: &RT) -> Option<RT> {
443    if matches!(rt.k, RTk::Any) {
444        None
445    } else {
446        Some(rt.clone())
447    }
448}
449/// A member's type, from its annotation or its conjunction.
450pub fn member_ty(m: &Member) -> Option<RT> {
451    match &m.conj {
452        Some(c) => Some(ty(RTk::IsectN(c.clone()))),
453        None => m.ty.clone(),
454    }
455}
456fn find_member<'a>(members: &'a [Member], name: &str) -> Option<&'a Member> {
457    members.iter().find(|m| m.name == name)
458}
459
460// ---------------- type utilities ----------------
461fn is_null_lit(t: &RT) -> bool {
462    matches!(&t.k, RTk::Lit(Value::Null)) || matches!(&t.k, RTk::Prim(n) if n == "null")
463}
464/// Whether a type admits null.
465pub fn has_null(rt: Option<&RT>) -> bool {
466    match rt {
467        None => false,
468        Some(t) => {
469            is_null_lit(t)
470                || matches!(&t.k, RTk::Union(arms) if arms.borrow().iter().any(|a| has_null(Some(a))))
471        }
472    }
473}
474fn strip_null(rt: &RT) -> RT {
475    if let RTk::Union(arms) = &rt.k {
476        let kept: Vec<RT> = arms
477            .borrow()
478            .iter()
479            .filter(|a| !is_null_lit(a))
480            .cloned()
481            .collect();
482        return if kept.len() == 1 {
483            kept[0].clone()
484        } else {
485            ty(RTk::Union(RefCell::new(kept)))
486        };
487    }
488    rt.clone()
489}
490fn same_rt(a: &RT, b: &RT) -> bool {
491    if Rc::ptr_eq(a, b) {
492        return true;
493    }
494    match (&a.k, &b.k) {
495        (RTk::Prim(x), RTk::Prim(y)) => x == y,
496        (RTk::Lit(x), RTk::Lit(y)) => js_typeof(x) == js_typeof(y) && value_eq(x, y),
497        _ => false,
498    }
499}
500/// The union of the arms, flattened; none when any arm is unknown.
501pub fn mk_union(arms: Vec<Option<RT>>) -> Option<RT> {
502    if arms.iter().any(|a| a.is_none()) {
503        return None;
504    }
505    let mut flat: Vec<RT> = vec![];
506    for a in arms.into_iter().flatten() {
507        match &a.k {
508            RTk::Union(xs) => flat.extend(xs.borrow().iter().cloned()),
509            _ => flat.push(a),
510        }
511    }
512    let mut uniq: Vec<RT> = vec![];
513    for a in flat {
514        if !uniq.iter().any(|b| same_rt(&a, b)) {
515            uniq.push(a);
516        }
517    }
518    Some(if uniq.len() == 1 {
519        uniq[0].clone()
520    } else {
521        ty(RTk::Union(RefCell::new(uniq)))
522    })
523}
524/// The numeric kind of a type — int, float, quantity — when it has one.
525pub fn num_kind(rt: Option<&RT>) -> Option<String> {
526    let rt = rt?;
527    match &rt.k {
528        RTk::Prim(n) => {
529            if ["int", "float", "string", "bool"].contains(&n.as_str()) {
530                Some(n.clone())
531            } else {
532                None
533            }
534        }
535        RTk::Lit(v) => match v {
536            Value::Bool(_) => Some("bool".into()),
537            Value::Int(_) => Some("int".into()),
538            Value::Float(_) => Some("float".into()),
539            Value::Str(_) => Some("string".into()),
540            _ => None,
541        },
542        RTk::Range { base, .. } => Some(base.clone()),
543        RTk::Pattern { .. } => Some("string".into()),
544        RTk::Pred { base, .. } => num_kind(Some(base)),
545        RTk::Quantity(_) => Some("quantity".into()),
546        RTk::Union(arms) => {
547            let ks: Vec<Option<String>> = arms.borrow().iter().map(|a| num_kind(Some(a))).collect();
548            match ks.first() {
549                Some(Some(k0)) if ks.iter().all(|k| k.as_ref() == Some(k0)) => Some(k0.clone()),
550                _ => None,
551            }
552        }
553        _ => None,
554    }
555}
556fn is_boolish(rt: Option<&RT>) -> bool {
557    rt.is_none() || num_kind(rt).as_deref() == Some("bool")
558}
559/// structural view: unwrap ref/pred and select the arm of an intersection
560/// that has the wanted shape (merged `&` members carry conj arms)
561fn arm_of(rt: Option<&RT>, t: &str) -> Option<RT> {
562    let rt = rt?;
563    match &rt.k {
564        RTk::Ref(target) if t != "ref" => return arm_of(Some(target), t),
565        RTk::Pred { base, .. } => return arm_of(Some(base), t),
566        _ => {}
567    }
568    if tag(rt) == t {
569        return Some(rt.clone());
570    }
571    if let RTk::IsectN(arms) = &rt.k {
572        for x in arms {
573            if let Some(v) = arm_of(Some(x), t) {
574                return Some(v);
575            }
576        }
577    }
578    if let RTk::Union(arms) = &rt.k {
579        let arms = arms.borrow();
580        let sub: Vec<RT> = arms.iter().filter_map(|x| arm_of(Some(x), t)).collect();
581        if sub.len() == arms.len() && !sub.is_empty() {
582            if t == "arr" {
583                let elems: Vec<RT> = sub
584                    .iter()
585                    .filter_map(|a| {
586                        if let RTk::Arr { elem, .. } = &a.k {
587                            Some(elem.clone())
588                        } else {
589                            None
590                        }
591                    })
592                    .collect();
593                return Some(ty(RTk::Arr {
594                    elem: ty(RTk::Union(RefCell::new(elems))),
595                    lo: None,
596                    hi: None,
597                }));
598            }
599            return Some(sub[0].clone());
600        }
601    }
602    None
603}
604
605// ---------------- navigation paths & narrowing ----------------
606/// The key of an expression as a guard path (`a.b.c`), when it is one.
607pub fn path_key(e: &Expr) -> Option<String> {
608    match e {
609        Expr::Name(n) => Some(n.clone()),
610        Expr::Ctx(n) => Some(n.clone()),
611        Expr::Paren(x) => path_key(x),
612        Expr::Member { x, name, safe } => {
613            if *safe {
614                return None;
615            }
616            path_key(x).map(|b| format!("{b}.{name}"))
617        }
618        Expr::Index { x, i } => {
619            let b = path_key(x)?;
620            let k = path_key(i)?;
621            Some(format!("{b}[{k}]"))
622        }
623        // a literal key spelled as its value (a string key `m["a"]` keys as `a`,
624        // matching an `in` guard) — the conflation the index case always had
625        Expr::Lit(v) => Some(js_str(v)),
626        // a call is keyed by its callee and argument keys: a Decl function is
627        // pure, so `f(x) in m` narrows `m[f(x)]` (§4.10, the guard rule)
628        Expr::Call { fun, args } => {
629            let c = path_key(fun)?;
630            let mut parts = Vec::with_capacity(args.len());
631            for a in args {
632                parts.push(path_key(a)?);
633            }
634            Some(format!("{c}({})", parts.join(",")))
635        }
636        _ => None,
637    }
638}
639#[derive(Default)]
640/// what a condition proves when it holds: the paths present, the paths non-null
641pub struct Guards {
642    /// the paths proved present
643    pub present: Vec<String>,
644    /// the paths proved non-null
645    pub nonnull: Vec<String>,
646}
647fn merge(mut a: Guards, b: Guards) -> Guards {
648    a.present.extend(b.present);
649    a.nonnull.extend(b.nonnull);
650    a
651}
652/// The guards a condition establishes on the branch where it holds (`polarity`).
653pub fn guards_of(e: &Expr, polarity: bool) -> Guards {
654    match e {
655        Expr::Paren(x) => guards_of(x, polarity),
656        Expr::Un { op, x } => {
657            if op == "!" {
658                guards_of(x, !polarity)
659            } else {
660                Guards::default()
661            }
662        }
663        Expr::Bin { op, l, r } => {
664            if op == "&&" && polarity {
665                return merge(guards_of(l, true), guards_of(r, true));
666            }
667            if op == "||" && !polarity {
668                return merge(guards_of(l, false), guards_of(r, false));
669            }
670            if op == "in" && polarity {
671                let Some(b) = path_key(r) else {
672                    return Guards::default();
673                };
674                return match &**l {
675                    Expr::Lit(Value::Str(s)) => Guards {
676                        present: vec![format!("{b}.{s}"), format!("{b}[{s}]")],
677                        nonnull: vec![],
678                    },
679                    _ => match path_key(l) {
680                        Some(k) => Guards {
681                            present: vec![format!("{b}[{k}]")],
682                            nonnull: vec![],
683                        },
684                        None => Guards::default(),
685                    },
686                };
687            }
688            let null_side = if matches!(&**l, Expr::Lit(Value::Null)) {
689                Some(r)
690            } else if matches!(&**r, Expr::Lit(Value::Null)) {
691                Some(l)
692            } else {
693                None
694            };
695            if let Some(side) = null_side {
696                if let Some(p) = path_key(side) {
697                    if (op == "!=" && polarity) || (op == "==" && !polarity) {
698                        return Guards {
699                            present: vec![],
700                            nonnull: vec![p],
701                        };
702                    }
703                }
704            }
705            Guards::default()
706        }
707        _ => Guards::default(),
708    }
709}
710/// is a name already taken here? (locals or the module namespace — the
711/// no-shadowing rule E3019 spans both)
712fn name_bound(cx: &Ctx, n: &str) -> bool {
713    cx.vars.contains_key(n)
714        || cx.env.consts.borrow().contains_key(n)
715        || cx.env.funcs.borrow().contains_key(n)
716        || cx.env.type_asts.borrow().contains_key(n)
717        || cx.env.inputs.borrow().contains_key(n)
718        || cx.env.outputs.borrow().iter().any(|(o, _, _)| o == n)
719}
720/// A context with the guards in force.
721pub fn apply_guards(cx: &Ctx, g: Guards) -> Ctx {
722    let mut c2 = cx.child();
723    c2.present.extend(g.present);
724    c2.nonnull.extend(g.nonnull);
725    c2
726}
727
728// ---------------- stdlib signatures (arity + result) ----------------
729/// the return type of a std function, by shape
730#[derive(Clone, Copy)]
731pub enum StdRet {
732    /// unknown
733    Unknown,
734    /// an integer
735    Int,
736    /// a boolean
737    Bool,
738    /// a string
739    Str,
740    /// a float
741    Float,
742    /// an array of strings
743    ArrStr,
744    /// a predicate function
745    PredFn,
746}
747/// the std functions (§13.1: names not listed do not exist): name, arity, return
748pub const STD: &[(&str, usize, StdRet)] = &[
749    ("array.count", 1, StdRet::Int),
750    ("array.all", 2, StdRet::Bool),
751    ("array.any", 2, StdRet::Bool),
752    ("array.filter", 2, StdRet::Unknown),
753    ("array.all_distinct", 1, StdRet::Bool),
754    ("array.sum", 1, StdRet::Unknown),
755    ("array.fold", 3, StdRet::Unknown),
756    ("array.sort", 1, StdRet::Unknown),
757    ("array.sort_by", 2, StdRet::Unknown),
758    ("array.unique", 1, StdRet::Unknown),
759    ("array.reverse", 1, StdRet::Unknown),
760    ("map.keys", 1, StdRet::ArrStr),
761    ("map.values", 1, StdRet::Unknown),
762    ("string.length", 1, StdRet::Int),
763    ("string.of", 1, StdRet::Str),
764    ("string.join", 2, StdRet::Str),
765    ("string.starts_with", 2, StdRet::Bool),
766    ("string.ends_with", 2, StdRet::Bool),
767    ("string.contains", 2, StdRet::Bool),
768    ("string.split", 2, StdRet::ArrStr),
769    ("map.entries", 1, StdRet::Unknown),
770    ("ref.path", 1, StdRet::Str),
771    ("math.abs", 1, StdRet::Unknown),
772    ("math.min", 2, StdRet::Unknown),
773    ("math.max", 2, StdRet::Unknown),
774    ("math.clog2", 1, StdRet::Int),
775    ("math.floor", 1, StdRet::Int),
776    ("math.ceil", 1, StdRet::Int),
777    ("math.round", 1, StdRet::Int),
778    ("int.of", 1, StdRet::Int),
779    ("int.at_least", 1, StdRet::PredFn),
780    ("int.at_most", 1, StdRet::PredFn),
781    ("float.of", 1, StdRet::Float),
782    ("object.merge", 2, StdRet::Unknown),
783];
784/// the std function names, in table order (completion)
785pub fn std_names() -> impl Iterator<Item = &'static str> {
786    STD.iter().map(|e| e.0)
787}
788fn std_sig(name: &str) -> Option<(usize, Option<RT>)> {
789    let e = STD.iter().find(|e| e.0 == name)?;
790    let ret = match e.2 {
791        StdRet::Unknown => None,
792        StdRet::Int => Some(prim("int")),
793        StdRet::Bool => Some(prim("bool")),
794        StdRet::Str => Some(prim("string")),
795        StdRet::Float => Some(prim("float")),
796        StdRet::ArrStr => Some(ty(RTk::Arr {
797            elem: prim("string"),
798            lo: None,
799            hi: None,
800        })),
801        StdRet::PredFn => Some(ty(RTk::Func {
802            params: vec![prim("int")],
803            ret: prim("bool"),
804        })),
805    };
806    Some((e.1, ret))
807}
808
809// ---------------- type text ----------------
810// the static type as inference sees it, spelled in the language's own
811// type syntax where it has one (`:type` in the REPL, hover in the editor)
812/// The text of a type as the language spells it: `int`, `1..10`, `int[3..3]`,
813/// `(1 | 2)[]`, `quantity<Length>`.
814pub fn type_text(rt: Option<&RT>) -> String {
815    text(rt, &[])
816}
817
818fn text(rt: Option<&RT>, seen: &[usize]) -> String {
819    let Some(rt) = rt else {
820        return "unknown".into();
821    };
822    let lit = |v: &Value| match v {
823        Value::Str(s) => crate::semantics::json_str(s),
824        other => js_str(other),
825    };
826    let is_null_arm = |a: &RT| {
827        matches!(&a.k, RTk::Prim(n) if n == "null") || matches!(&a.k, RTk::Lit(Value::Null))
828    };
829    match &rt.k {
830        RTk::Any => "any".into(),
831        RTk::Prim(n) => n.clone(),
832        RTk::Lit(v) => lit(v),
833        RTk::Range { lo, hi, excl, .. } => {
834            format!("{}..{}{}", lit(lo), if *excl { "<" } else { "" }, lit(hi))
835        }
836        RTk::Pattern { src, .. } => format!("/{src}/"),
837        RTk::Quantity(dim) => format!("quantity<{dim}>"),
838        RTk::Ref(t) => format!("ref<{}>", text(Some(t), seen)),
839        RTk::Map { key, val } => {
840            format!("map<{}, {}>", text(Some(key), seen), text(Some(val), seen))
841        }
842        RTk::Arr { elem, lo, hi } => {
843            let b = if lo.is_some() || hi.is_some() {
844                format!(
845                    "[{}..{}]",
846                    lo.map(|x| x.to_string()).unwrap_or_default(),
847                    hi.map(|x| x.to_string()).unwrap_or_default()
848                )
849            } else {
850                "[]".into()
851            };
852            let e = text(Some(elem), seen);
853            // a compound element type is parenthesized (`(1 | 2)[]`, `(1..8)[]`), as the grammar's paren_type spells it
854            let wrap = matches!(
855                &elem.k,
856                RTk::Union(_) | RTk::Func { .. } | RTk::Pred { .. } | RTk::Range { .. }
857            );
858            format!("{}{b}", if wrap { format!("({e})") } else { e })
859        }
860        RTk::Union(arms) => {
861            // a recursive alias prints its name rather than unfolding
862            if seen.contains(&(Rc::as_ptr(rt) as usize)) {
863                return rt.name.borrow().clone().unwrap_or_else(|| "…".into());
864            }
865            let mut inner = seen.to_vec();
866            inner.push(Rc::as_ptr(rt) as usize);
867            let arms = arms.borrow();
868            let nn: Vec<&RT> = arms.iter().filter(|a| !is_null_arm(a)).collect();
869            if nn.len() + 1 == arms.len() && nn.len() == 1 {
870                return format!("{}?", text(Some(nn[0]), &inner));
871            }
872            arms.iter()
873                .map(|a| text(Some(a), &inner))
874                .collect::<Vec<_>>()
875                .join(" | ")
876        }
877        RTk::Pred { base, .. } => format!("{} where …", type_text(Some(base))),
878        RTk::Func { params, ret } => format!(
879            "({}) => {}",
880            params
881                .iter()
882                .map(|p| type_text(Some(p)))
883                .collect::<Vec<_>>()
884                .join(", "),
885            type_text(Some(ret))
886        ),
887        RTk::Rec(r) => {
888            if let Some(n) = rt.name.borrow().as_ref() {
889                if !n.starts_with('{') {
890                    return n.clone();
891                }
892            }
893            let ms: Vec<String> = r
894                .members
895                .borrow()
896                .iter()
897                .map(|m| {
898                    format!(
899                        "{}{}{}{}",
900                        m.name,
901                        if m.kind == MKind::Opt { "?" } else { "" },
902                        m.ty.as_ref()
903                            .map(|t| format!(": {}", type_text(Some(t))))
904                            .unwrap_or_default(),
905                        if matches!(m.kind, MKind::Der | MKind::Dflt) {
906                            " = …"
907                        } else {
908                            ""
909                        }
910                    )
911                })
912                .collect();
913            let open = if r.open.get() {
914                if ms.is_empty() {
915                    "..."
916                } else {
917                    ", ..."
918                }
919            } else {
920                ""
921            };
922            format!("{{ {}{open} }}", ms.join(", "))
923        }
924        RTk::IsectN(_) => "?".into(),
925    }
926}
927/// The `std.module.function` path an expression spells, when it does.
928pub fn std_path(e: &Expr) -> Option<String> {
929    match e {
930        Expr::Member {
931            x,
932            name,
933            safe: false,
934        } => {
935            let b = std_path(x)?;
936            Some(if b.is_empty() {
937                name.clone()
938            } else {
939                format!("{b}.{name}")
940            })
941        }
942        Expr::Name(n) if n == "std" => Some(String::new()),
943        _ => None,
944    }
945}
946
947// ---------------- the judgment ----------------
948/// Resolve a type annotation; none when it is absent or fails.
949pub fn try_resolve(env: &Rc<Env>, ast: Option<&TypeAst>) -> Option<RT> {
950    env.resolve(ast?, None).ok()
951}
952/// A named type's annotation, without arguments.
953pub fn named(name: &str) -> TypeAst {
954    TypeAst::Named {
955        name: name.to_string(),
956        args: vec![],
957        preds: None,
958        ext: None,
959        loc: None,
960    }
961}
962
963/// Require a value-typed expression where a type or a namespace would be an error.
964/// The operand of an object spread (§4.2) must be object-valued: a record, a
965/// map, an intersection of records, or a union of those; the type is handed
966/// back so a construction can count the members a record-typed spread supplies.
967fn spread_ty(cx: &Ctx, e: &Rc<Expr>) -> Ty {
968    let Expr::Spread(inner) = &**e else {
969        return infer(cx, e);
970    };
971    let t = require_val(cx, inner, infer(cx, inner), "as a spread");
972    let rt = match t.rt {
973        Some(r) if matches!(r.k, RTk::Ref(_)) => match &r.k {
974            RTk::Ref(target) => Some(target.clone()),
975            _ => None,
976        },
977        other => other,
978    };
979    if let Some(r) = &rt {
980        if !matches!(
981            r.k,
982            RTk::Rec(_) | RTk::Map { .. } | RTk::IsectN(_) | RTk::Union(_) | RTk::Any
983        ) {
984            cx.report("E4001", "spread of a non-object value".into());
985        }
986    }
987    Ty { rt, abs: false }
988}
989
990/// The type of an expression used as a value: a maybe-absent one is refused (§4.10).
991pub fn require_val(cx: &Ctx, e: &Expr, ty: Ty, what: &str) -> Ty {
992    if ty.abs {
993        let k = path_key(e);
994        if !k.map(|k| cx.present.contains(&k)).unwrap_or(false) {
995            cx.report(
996                "E4050",
997                format!("maybe-absent expression consumed {what} (use ?. / ?? or an `in` guard)"),
998            );
999        }
1000    }
1001    ty
1002}
1003
1004/// Infer an expression's type (§4), reporting findings through the context.
1005pub fn infer(cx: &Ctx, e: &Rc<Expr>) -> Ty {
1006    let prev = cx.pos.replace(Some(e.clone()));
1007    let t = infer0(cx, e);
1008    if let Some(r) = &cx.record {
1009        r(e, &t);
1010    }
1011    if let Some(h) = &cx.resolve_hook {
1012        if let Expr::Name(n) = &**e {
1013            h(e, resolve_name(cx, n));
1014        }
1015    }
1016    *cx.pos.borrow_mut() = prev;
1017    t
1018}
1019fn infer0(cx: &Ctx, e: &Rc<Expr>) -> Ty {
1020    match &**e {
1021        Expr::Lit(v) => tyv(Some(ty(RTk::Lit(v.clone())))),
1022        Expr::Pattern(src) => match pattern_error(src) {
1023            Some(bad) => {
1024                cx.report("E4119", format!("malformed pattern /{src}/: {bad}"));
1025                unk()
1026            }
1027            None => match compile_pattern(src) {
1028                Ok(re) => tyv(Some(ty(RTk::Pattern {
1029                    src: src.clone(),
1030                    re,
1031                }))),
1032                Err(_) => unk(),
1033            },
1034        },
1035        Expr::UnitLit { unit, .. } => match cx.env.unit_info(unit) {
1036            Ok((key, _)) => tyv(Some(ty(RTk::Quantity(key)))),
1037            Err(msg) => {
1038                cx.report("E4073", msg);
1039                unk()
1040            }
1041        },
1042        Expr::Template(parts) => {
1043            for p in parts {
1044                if let TPart::Expr(x) = p {
1045                    require_val(cx, x, infer(cx, x), "in a template");
1046                }
1047            }
1048            tyv(Some(prim("string")))
1049        }
1050        Expr::Name(name) => {
1051            if let Some(t) = cx.vars.get(name) {
1052                return t.clone();
1053            }
1054            let env = &cx.env;
1055            if env.consts.borrow().contains_key(name) {
1056                return const_ty(cx, name);
1057            }
1058            if env.funcs.borrow().contains_key(name) {
1059                return tyv(Some(func_rt(cx, name)));
1060            }
1061            if name == "std" {
1062                return unk();
1063            }
1064            let out = env
1065                .outputs
1066                .borrow()
1067                .iter()
1068                .find(|(o, _, _)| o == name)
1069                .map(|(_, t, _)| t.clone());
1070            if let Some(t) = out {
1071                return tyv(try_resolve(env, Some(&t)));
1072            }
1073            let inp = env.inputs.borrow().get(name).map(|(t, _)| t.clone());
1074            if let Some(t) = inp {
1075                return tyv(try_resolve(env, Some(&t)));
1076            }
1077            let im = env.imports.borrow().get(name).cloned();
1078            if let Some(im) = im {
1079                return imported_ty(cx, &im);
1080            }
1081            if env.namespaces.borrow().contains_key(name) {
1082                cx.report("E3008", format!("namespace name {name} used as a value"));
1083                return unk();
1084            }
1085            if env.type_asts.borrow().contains_key(name) {
1086                cx.report(
1087                    "E3008",
1088                    format!("type/namespace name {name} used as a value"),
1089                );
1090                return unk();
1091            }
1092            cx.report("E3003", format!("unknown name {name}"));
1093            unk()
1094        }
1095        Expr::Ctx(n) => cx.vars.get(n).cloned().unwrap_or_else(unk),
1096        Expr::Referrers { ty: tn, .. } => {
1097            let rt = try_resolve(&cx.env, Some(&named(tn)));
1098            match &rt {
1099                None => cx.report("E4091", format!("$referrers: unknown record type {tn}")),
1100                Some(r) if !is_rec(r) => {
1101                    cx.report("E4091", format!("$referrers: {tn} is not a record type"))
1102                }
1103                _ => {}
1104            }
1105            tyv(rt.filter(is_rec).map(|r| {
1106                ty(RTk::Arr {
1107                    elem: ty(RTk::Ref(r)),
1108                    lo: None,
1109                    hi: None,
1110                })
1111            }))
1112        }
1113        Expr::Obj(entries) => {
1114            for (_, v) in entries {
1115                if matches!(&**v, Expr::Spread(_)) {
1116                    spread_ty(cx, v);
1117                } else {
1118                    require_val(cx, v, infer(cx, v), "as a construction member");
1119                }
1120            }
1121            unk() // literals are typed by their checked position (§3.18)
1122        }
1123        Expr::Spread(_) => spread_ty(cx, e),
1124        Expr::Arr(items) => {
1125            let ts: Vec<Option<RT>> = items
1126                .iter()
1127                .map(|(spread, x)| {
1128                    let t = require_val(cx, x, infer(cx, x), "as an array element");
1129                    if *spread {
1130                        t.rt.and_then(|r| {
1131                            if let RTk::Arr { elem, .. } = &r.k {
1132                                Some(elem.clone())
1133                            } else {
1134                                None
1135                            }
1136                        })
1137                    } else {
1138                        t.rt
1139                    }
1140                })
1141                .collect();
1142            tyv(mk_union(ts).map(|elem| {
1143                ty(RTk::Arr {
1144                    elem,
1145                    lo: None,
1146                    hi: None,
1147                })
1148            }))
1149        }
1150        Expr::Comp { head, clauses } => {
1151            let c2 = bind_clauses(cx, clauses);
1152            let h = require_val(&c2, head, infer(&c2, head), "as a comprehension element");
1153            tyv(h.rt.map(|elem| {
1154                ty(RTk::Arr {
1155                    elem,
1156                    lo: None,
1157                    hi: None,
1158                })
1159            }))
1160        }
1161        Expr::MapComp { key, val, clauses } => {
1162            let c2 = bind_clauses(cx, clauses);
1163            let k = require_val(&c2, key, infer(&c2, key), "as a map key");
1164            if k.rt.is_some() && num_kind(k.rt.as_ref()).as_deref() != Some("string") {
1165                cx.report("E4001", "map-comprehension key is not a string".into());
1166            }
1167            let v = require_val(&c2, val, infer(&c2, val), "as a map value");
1168            tyv(v.rt.map(|val| {
1169                ty(RTk::Map {
1170                    key: prim("string"),
1171                    val,
1172                })
1173            }))
1174        }
1175        Expr::Bin { .. } => infer_bin(cx, e),
1176        Expr::Un { op, x } => {
1177            let t = require_val(cx, x, infer(cx, x), &format!("as `{op}` operand"));
1178            if op == "!" {
1179                if t.rt.is_some() && !is_boolish(t.rt.as_ref()) {
1180                    cx.report("E4071", "`!` on a non-bool operand".into());
1181                }
1182                return bool_ty();
1183            }
1184            if op == "~" {
1185                if t.rt.is_some() && num_kind(t.rt.as_ref()).as_deref() != Some("int") {
1186                    cx.report("E4071", "`~` on a non-int operand".into());
1187                }
1188                return tyv(Some(prim("int")));
1189            }
1190            let k = num_kind(t.rt.as_ref());
1191            if t.rt.is_some()
1192                && !matches!(k.as_deref(), Some("int") | Some("float") | Some("quantity"))
1193            {
1194                cx.report("E4071", "unary `-` on a non-numeric operand".into());
1195            }
1196            tyv(match k.as_deref() {
1197                Some("int") => Some(prim("int")),
1198                Some("float") => Some(prim("float")),
1199                _ => None,
1200            })
1201        }
1202        Expr::Paren(x) => infer(cx, x),
1203        Expr::If { c, t, f } => {
1204            let ct = require_val(cx, c, infer(cx, c), "as a condition");
1205            if ct.rt.is_some() && !is_boolish(ct.rt.as_ref()) {
1206                cx.report("E4001", "`if` condition is not bool".into());
1207            }
1208            let tt = infer(&apply_guards(cx, guards_of(c, true)), t);
1209            let ft = infer(&apply_guards(cx, guards_of(c, false)), f);
1210            Ty {
1211                rt: mk_union(vec![tt.rt, ft.rt]),
1212                abs: tt.abs || ft.abs,
1213            }
1214        }
1215        Expr::Lambda { params, body } => {
1216            let mut c2 = cx.child();
1217            for p in params {
1218                if name_bound(&c2, p) {
1219                    cx.report(
1220                        "E3019",
1221                        format!("lambda parameter {p} shadows an enclosing name"),
1222                    );
1223                }
1224                c2.vars.insert(p.clone(), unk());
1225                c2.locals.insert(p.clone());
1226            }
1227            infer(&c2, body);
1228            unk()
1229        }
1230        Expr::Call { .. } => infer_call(cx, e),
1231        Expr::Member { .. } => infer_member(cx, e),
1232        Expr::Index { x, .. } => {
1233            let b = require_val(cx, x, infer(cx, x), "for indexing");
1234            index_core(cx, b, e)
1235        }
1236        Expr::With { base, patch } => {
1237            let b = require_val(cx, base, infer(cx, base), "as `with` base");
1238            let brt = match &b.rt {
1239                Some(r) => match &r.k {
1240                    RTk::Ref(t) => Some(t.clone()),
1241                    _ => Some(r.clone()),
1242                },
1243                None => None,
1244            };
1245            if let Some(r) = &brt {
1246                if !is_rec(r) {
1247                    cx.report("E4080", "`with` on a non-record base".into());
1248                    return unk();
1249                }
1250            }
1251            if let (Expr::Obj(entries), Some(r)) = (&**patch, &brt) {
1252                let RTk::Rec(rec) = &r.k else { unreachable!() };
1253                let members = rec.members.borrow();
1254                for (k, _) in entries {
1255                    match find_member(&members, k) {
1256                        None if !rec.open.get() => {
1257                            cx.report("E4080", format!("`with` updates unknown member {k}"))
1258                        }
1259                        Some(m) if m.kind == MKind::Der => {
1260                            cx.report("E4080", format!("`with` updates derived member {k}"))
1261                        }
1262                        _ => {}
1263                    }
1264                }
1265            }
1266            if let Expr::Obj(entries) = &**patch {
1267                for (_, v) in entries {
1268                    require_val(cx, v, infer(cx, v), "as a `with` update");
1269                }
1270            } else {
1271                infer(cx, patch);
1272            }
1273            tyv(brt)
1274        }
1275        Expr::Match { .. } => infer_match(cx, e, None),
1276    }
1277}
1278
1279fn bind_clauses(cx: &Ctx, clauses: &[ForClause]) -> Ctx {
1280    let mut c2 = cx.child();
1281    for cl in clauses {
1282        let vt = iter_var_ty(&c2, &cl.iter);
1283        if name_bound(&c2, &cl.v) {
1284            cx.report(
1285                "E3019",
1286                format!("comprehension variable {} shadows an enclosing name", cl.v),
1287            );
1288        }
1289        c2.vars.insert(cl.v.clone(), vt);
1290        c2.locals.insert(cl.v.clone());
1291        for f in &cl.filters {
1292            require_val(&c2, f, infer(&c2, f), "as a filter");
1293            c2 = apply_guards(&c2, guards_of(f, true));
1294        }
1295    }
1296    c2
1297}
1298
1299fn iter_var_ty(cx: &Ctx, it: &Rc<Expr>) -> Ty {
1300    let t = require_val(cx, it, infer(cx, it), "as an iterable");
1301    if let Expr::Bin { op, l, r } = &**it {
1302        if op == ".." || op == "..<" {
1303            let lo = if let Expr::Lit(v) = &**l {
1304                Some(v.clone())
1305            } else {
1306                None
1307            };
1308            let hi = if let Expr::Lit(v) = &**r {
1309                Some(v.clone())
1310            } else {
1311                None
1312            };
1313            if matches!(lo, Some(Value::Float(_))) || matches!(hi, Some(Value::Float(_))) {
1314                cx.report("E4115", "comprehension over a float range".into());
1315                return unk();
1316            }
1317            if let (Some(lo), Some(hi)) = (lo, hi) {
1318                return tyv(Some(ty(RTk::Range {
1319                    lo,
1320                    hi,
1321                    excl: op == "..<",
1322                    base: "int".into(),
1323                })));
1324            }
1325            return tyv(Some(prim("int")));
1326        }
1327    }
1328    let Some(rt) = &t.rt else { return unk() };
1329    if let Some(a) = arm_of(Some(rt), "arr") {
1330        if let RTk::Arr { elem, .. } = &a.k {
1331            return tyv(Some(elem.clone()));
1332        }
1333    }
1334    let what = if arm_of(Some(rt), "map").is_some() {
1335        "map (use std.map.keys/values)"
1336    } else {
1337        "value"
1338    };
1339    cx.report("E4115", format!("comprehension over a non-iterable {what}"));
1340    unk()
1341}
1342
1343fn q_dim(rt: Option<&RT>) -> Option<String> {
1344    match rt.map(|r| &r.k) {
1345        Some(RTk::Quantity(d)) => Some(d.clone()),
1346        Some(RTk::Pred { base, .. }) => match &base.k {
1347            RTk::Quantity(d) => Some(d.clone()),
1348            _ => None,
1349        },
1350        _ => None,
1351    }
1352}
1353
1354fn infer_bin(cx: &Ctx, e: &Rc<Expr>) -> Ty {
1355    let Expr::Bin { op, l, r } = &**e else {
1356        return unk();
1357    };
1358    let op = op.as_str();
1359    if op == "|>" {
1360        // first-argument insertion (§4.9)
1361        let call = match &**r {
1362            Expr::Call { fun, args } => {
1363                let mut a = vec![l.clone()];
1364                a.extend(args.iter().cloned());
1365                Expr::Call {
1366                    fun: fun.clone(),
1367                    args: a,
1368                }
1369            }
1370            _ => Expr::Call {
1371                fun: r.clone(),
1372                args: vec![l.clone()],
1373            },
1374        };
1375        return infer_call(cx, &Rc::new(call));
1376    }
1377    if op == "??" {
1378        let lt = infer(cx, l); // absence/null on the left is the point
1379        let rt = require_val(cx, r, infer(cx, r), "as `??` fallback");
1380        return tyv(match (lt.rt, rt.rt) {
1381            (Some(a), Some(b)) => mk_union(vec![Some(strip_null(&a)), Some(b)]),
1382            _ => None,
1383        });
1384    }
1385    if op == "&&" || op == "||" {
1386        let lt = require_val(cx, l, infer(cx, l), &format!("as `{op}` operand"));
1387        if lt.rt.is_some() && !is_boolish(lt.rt.as_ref()) {
1388            cx.report("E4071", format!("`{op}` on a non-bool operand"));
1389        }
1390        let c2 = apply_guards(cx, guards_of(l, op == "&&"));
1391        let rt = require_val(&c2, r, infer(&c2, r), &format!("as `{op}` operand"));
1392        if rt.rt.is_some() && !is_boolish(rt.rt.as_ref()) {
1393            cx.report("E4071", format!("`{op}` on a non-bool operand"));
1394        }
1395        return bool_ty();
1396    }
1397    if op == "in" {
1398        require_val(cx, l, infer(cx, l), "as `in` key");
1399        let rt = require_val(cx, r, infer(cx, r), "as `in` container");
1400        let rrt = rt.rt.map(|x| match &x.k {
1401            RTk::Ref(t) => t.clone(),
1402            _ => x,
1403        });
1404        if let (Some(rr), Expr::Lit(Value::Str(key))) = (&rrt, &**l) {
1405            if let RTk::Rec(rec) = &rr.k {
1406                let members = rec.members.borrow();
1407                match find_member(&members, key) {
1408                    Some(m) if m.kind != MKind::Opt => cx.report(
1409                        "E4054",
1410                        format!("`in` on member {key}, which is not optional"),
1411                    ),
1412                    None if !rec.open.get() => cx.report(
1413                        "E4054",
1414                        format!("`in` on undeclared member {key} of a closed record"),
1415                    ),
1416                    _ => {}
1417                }
1418            }
1419        }
1420        return bool_ty();
1421    }
1422    if op == ".." || op == "..<" {
1423        require_val(cx, l, infer(cx, l), "as a range endpoint");
1424        require_val(cx, r, infer(cx, r), "as a range endpoint");
1425        return unk(); // a range value: iterable / membership container only
1426    }
1427    let lt = require_val(cx, l, infer(cx, l), &format!("as `{op}` operand"));
1428    let rt = require_val(cx, r, infer(cx, r), &format!("as `{op}` operand"));
1429    if op == "matches" {
1430        if lt.rt.is_some() && num_kind(lt.rt.as_ref()).as_deref() != Some("string") {
1431            cx.report("E4071", "`matches` needs a string left operand".into());
1432        }
1433        return bool_ty();
1434    }
1435    if op == "==" || op == "!=" {
1436        return bool_ty();
1437    }
1438    let lk = num_kind(lt.rt.as_ref());
1439    let rk = num_kind(rt.rt.as_ref());
1440    let cmp = ["<", "<=", ">", ">="].contains(&op);
1441    let (lks, rks) = (lk.as_deref(), rk.as_deref());
1442    if lks == Some("quantity") || rks == Some("quantity") {
1443        // §3.16: +/-/compare need equal dimensions; * and / compose them;
1444        // a bare int/float scales; a cancelled vector is a plain number
1445        if op == "+" || op == "-" || cmp {
1446            if lt.rt.is_some() && rt.rt.is_some() {
1447                if lks != Some("quantity") || rks != Some("quantity") {
1448                    let other = if lks == Some("quantity") { rks } else { lks };
1449                    cx.report(
1450                        "E4071",
1451                        format!("`{op}` mixes quantity and {}", other.unwrap_or("null")),
1452                    );
1453                } else {
1454                    let (a, b) = (q_dim(lt.rt.as_ref()), q_dim(rt.rt.as_ref()));
1455                    if let (Some(a), Some(b)) = (&a, &b) {
1456                        if a != b {
1457                            let one = |s: &str| {
1458                                if s.is_empty() {
1459                                    "1".to_string()
1460                                } else {
1461                                    s.to_string()
1462                                }
1463                            };
1464                            cx.report(
1465                                "E4072",
1466                                format!(
1467                                    "`{op}` on quantities of different dimensions ({} vs {})",
1468                                    one(a),
1469                                    one(b)
1470                                ),
1471                            );
1472                        }
1473                    }
1474                }
1475            }
1476            return if cmp {
1477                bool_ty()
1478            } else {
1479                tyv(if lks == Some("quantity") {
1480                    lt.rt.clone()
1481                } else {
1482                    rt.rt.clone()
1483                })
1484            };
1485        }
1486        if op == "*" || op == "/" {
1487            let (Some(_), Some(_)) = (&lt.rt, &rt.rt) else {
1488                return unk();
1489            };
1490            let (lv, rv) = (q_dim(lt.rt.as_ref()), q_dim(rt.rt.as_ref()));
1491            let numeric = |k: Option<&str>| matches!(k, Some("int") | Some("float"));
1492            if (lv.is_none() && !numeric(lks)) || (rv.is_none() && !numeric(rks)) {
1493                cx.report("E4071", format!("`{op}` on a non-numeric operand"));
1494                return unk();
1495            }
1496            let key = key_of_vec(&vec_combine(
1497                &lv.as_deref().map(vec_of_key).unwrap_or_default(),
1498                &rv.as_deref().map(vec_of_key).unwrap_or_default(),
1499                if op == "*" { 1 } else { -1 },
1500            ));
1501            return tyv(Some(if key.is_empty() {
1502                prim("float")
1503            } else {
1504                ty(RTk::Quantity(key))
1505            }));
1506        }
1507        cx.report("E4071", format!("`{op}` on quantity operands"));
1508        return unk();
1509    }
1510    if let (Some(_), Some(_), Some(a), Some(b)) = (&lt.rt, &rt.rt, lks, rks) {
1511        if a != b {
1512            cx.report("E4071", format!("`{op}` mixes {a} and {b} operands"));
1513        }
1514    }
1515    if cmp {
1516        return bool_ty();
1517    }
1518    if ["&", "^", "<<", ">>"].contains(&op) {
1519        if (lt.rt.is_some() && lks != Some("int")) || (rt.rt.is_some() && rks != Some("int")) {
1520            cx.report("E4071", format!("`{op}` on non-int operands"));
1521        }
1522        return tyv(Some(prim("int")));
1523    }
1524    if op == "|" {
1525        // bitwise on ints (type-level | never reaches expressions)
1526        if (lt.rt.is_some() && lks != Some("int")) || (rt.rt.is_some() && rks != Some("int")) {
1527            cx.report("E4071", "`|` on non-int operands".into());
1528        }
1529        return tyv(Some(prim("int")));
1530    }
1531    // + - * / %
1532    if op == "+" && lks == Some("string") && rks == Some("string") {
1533        return tyv(Some(prim("string")));
1534    }
1535    if let (Some(lrt), Some(rrt), Some(a), Some(_)) = (&lt.rt, &rt.rt, lks, rks) {
1536        if !["int", "float", "quantity"].contains(&a) {
1537            cx.report("E4071", format!("`{op}` on {a} operands"));
1538        }
1539        if a == "int" && ["+", "-", "*"].contains(&op) {
1540            // interval arithmetic keeps range-typed operands range-typed, so
1541            // `9000 + i` with i: 0..<3 stays assignable where 1..65535 is expected
1542            if let (Some(x), Some(y)) = (as_ival(lrt), as_ival(rrt)) {
1543                let cands: Vec<BigInt> = match op {
1544                    "+" => vec![&x.0 + &y.0, &x.1 + &y.1],
1545                    "-" => vec![&x.0 - &y.1, &x.1 - &y.0],
1546                    _ => vec![&x.0 * &y.0, &x.0 * &y.1, &x.1 * &y.0, &x.1 * &y.1],
1547                };
1548                let lo = cands.iter().min().unwrap().clone();
1549                let hi = cands.iter().max().unwrap().clone();
1550                return tyv(Some(ty(RTk::Range {
1551                    lo: Value::Int(Num::from(lo)),
1552                    hi: Value::Int(Num::from(hi)),
1553                    excl: false,
1554                    base: "int".into(),
1555                })));
1556            }
1557        }
1558        return tyv(if a == "int" || a == "float" {
1559            Some(prim(a))
1560        } else {
1561            None
1562        });
1563    }
1564    unk()
1565}
1566
1567fn as_ival(rt: &RT) -> Option<(BigInt, BigInt)> {
1568    match &rt.k {
1569        RTk::Lit(Value::Int(i)) => Some((i.to_big(), i.to_big())),
1570        RTk::Range {
1571            lo: Value::Int(lo),
1572            hi: Value::Int(hi),
1573            excl,
1574            base,
1575        } if base == "int" => Some((
1576            lo.to_big(),
1577            if *excl {
1578                (hi - 1).to_big()
1579            } else {
1580                hi.to_big()
1581            },
1582        )),
1583        RTk::Union(arms) => {
1584            let ivs: Vec<Option<(BigInt, BigInt)>> = arms.borrow().iter().map(as_ival).collect();
1585            if !ivs.is_empty() && ivs.iter().all(|v| v.is_some()) {
1586                let ivs: Vec<(BigInt, BigInt)> = ivs.into_iter().flatten().collect();
1587                let lo = ivs.iter().map(|v| v.0.clone()).min().unwrap();
1588                let hi = ivs.iter().map(|v| v.1.clone()).max().unwrap();
1589                return Some((lo, hi));
1590            }
1591            None
1592        }
1593        RTk::Pred { base, .. } => as_ival(base),
1594        _ => None,
1595    }
1596}
1597
1598fn index_core(cx: &Ctx, b: Ty, e: &Rc<Expr>) -> Ty {
1599    let Expr::Index { i, .. } = &**e else {
1600        return unk();
1601    };
1602    let it = require_val(cx, i, infer(cx, i), "as an index");
1603    let Some(brt) = &b.rt else { return unk() };
1604    if let Some(a) = arm_of(Some(brt), "arr") {
1605        if it.rt.is_some() && num_kind(it.rt.as_ref()).as_deref() != Some("int") {
1606            cx.report("E4071", "array index is not an int".into());
1607        }
1608        if let RTk::Arr { elem, .. } = &a.k {
1609            return tyv(Some(elem.clone()));
1610        }
1611    }
1612    if let Some(m) = arm_of(Some(brt), "map") {
1613        let k = path_key(e);
1614        if let RTk::Map { val, .. } = &m.k {
1615            return Ty {
1616                rt: Some(val.clone()),
1617                abs: !k.map(|k| cx.present.contains(&k)).unwrap_or(false),
1618            };
1619        }
1620    }
1621    if arm_of(Some(brt), "rec").is_some() {
1622        return unk(); // dynamic member access
1623    }
1624    cx.report("E4071", "indexing a non-collection".into());
1625    unk()
1626}
1627
1628/// a name imported from another module, typed in that module's scope
1629fn imported_ty(cx: &Ctx, ex: &Export) -> Ty {
1630    let t = &ex.env;
1631    let name = &ex.name;
1632    let c = t.consts.borrow().get(name).cloned();
1633    if let Some(c) = c {
1634        // an imported constant is typed as a local one: its annotation, else
1635        // its expression inferred silently in the exporting module
1636        return match try_resolve(t, c.ty.as_ref()) {
1637            Some(a) => tyv(Some(a)),
1638            None => infer(&make_ctx(t.clone(), Rc::new(|_, _| {})), &c.expr),
1639        };
1640    }
1641    let f = t.funcs.borrow().get(name).cloned();
1642    if let Some(f) = f {
1643        return tyv(Some(func_rt_of(t, &f)));
1644    }
1645    let out = t
1646        .outputs
1647        .borrow()
1648        .iter()
1649        .find(|(o, _, _)| o == name)
1650        .map(|(_, ty, _)| ty.clone());
1651    if let Some(o) = out {
1652        return tyv(try_resolve(t, Some(&o)));
1653    }
1654    let inp = t.inputs.borrow().get(name).map(|(ty, _)| ty.clone());
1655    if let Some(i) = inp {
1656        return tyv(try_resolve(t, Some(&i)));
1657    }
1658    if t.type_asts.borrow().contains_key(name) {
1659        cx.report("E3008", format!("type name {name} used as a value"));
1660        return unk();
1661    }
1662    unk()
1663}
1664
1665fn infer_member(cx: &Ctx, e: &Rc<Expr>) -> Ty {
1666    let Expr::Member { x, name, safe } = &**e else {
1667        return unk();
1668    };
1669    if std_path(e).is_some() {
1670        return unk(); // std.* namespace path (typed at the call)
1671    }
1672    if let Expr::Name(xn) = &**x {
1673        if !cx.vars.contains_key(xn) {
1674            let ns = cx.env.namespaces.borrow().get(xn).map(|(_, ex)| ex.clone());
1675            if let Some(exports) = ns {
1676                let ex = exports.borrow().get(name).cloned();
1677                let Some(ex) = ex else {
1678                    cx.report("E3005", format!("namespace {xn} has no export {name}"));
1679                    return unk();
1680                };
1681                return imported_ty(cx, &ex);
1682            }
1683        }
1684    }
1685    let b = infer(cx, x);
1686    let key = path_key(x);
1687    if !*safe {
1688        let present = key
1689            .as_ref()
1690            .map(|k| cx.present.contains(k))
1691            .unwrap_or(false);
1692        let nonnull = key
1693            .as_ref()
1694            .map(|k| cx.nonnull.contains(k))
1695            .unwrap_or(false);
1696        if b.abs && !present {
1697            cx.report(
1698                "E4050",
1699                "member access on a maybe-absent expression (use ?. or an `in` guard)".into(),
1700            );
1701        }
1702        if has_null(b.rt.as_ref()) && !nonnull {
1703            cx.report(
1704                "E4051",
1705                format!("member .{name} on a possibly-null expression without ?."),
1706            );
1707        }
1708    }
1709    member_core(cx, b, e)
1710}
1711
1712fn member_core(cx: &Ctx, b: Ty, e: &Rc<Expr>) -> Ty {
1713    let Expr::Member { name, safe, .. } = &**e else {
1714        return unk();
1715    };
1716    let mut brt = b.rt.as_ref().map(strip_null);
1717    if let Some(RTk::Ref(t)) = brt.as_ref().map(|r| &r.k) {
1718        brt = Some(t.clone());
1719    }
1720    if let Some(RTk::Pred { base, .. }) = brt.as_ref().map(|r| &r.k) {
1721        brt = Some(base.clone());
1722    }
1723    if let Some(r) = &brt {
1724        if matches!(r.k, RTk::IsectN(_)) {
1725            brt = arm_of(Some(r), "rec")
1726                .or_else(|| arm_of(Some(r), "map"))
1727                .or_else(|| Some(r.clone()));
1728        }
1729    }
1730    let mk_abs = |t: Ty| {
1731        if *safe {
1732            Ty {
1733                rt: t.rt,
1734                abs: true,
1735            }
1736        } else {
1737            t
1738        }
1739    };
1740    let Some(brt) = brt else { return mk_abs(unk()) };
1741    match &brt.k {
1742        RTk::Rec(rec) => {
1743            let members = rec.members.borrow();
1744            let Some(m) = find_member(&members, name) else {
1745                if !rec.open.get() {
1746                    cx.report(
1747                        "E4003",
1748                        format!(
1749                            "member {name} is not declared on {}",
1750                            brt.name
1751                                .borrow()
1752                                .clone()
1753                                .unwrap_or_else(|| "this record".into())
1754                        ),
1755                    );
1756                }
1757                return mk_abs(unk());
1758            };
1759            let rt = member_ty(m);
1760            let present = path_key(e)
1761                .map(|k| cx.present.contains(&k))
1762                .unwrap_or(false);
1763            Ty {
1764                rt,
1765                abs: *safe || (m.kind == MKind::Opt && !present),
1766            }
1767        }
1768        RTk::Map { val, .. } => {
1769            let present = path_key(e)
1770                .map(|k| cx.present.contains(&k))
1771                .unwrap_or(false);
1772            Ty {
1773                rt: Some(val.clone()),
1774                abs: *safe || !present,
1775            }
1776        }
1777        RTk::Union(arms) => {
1778            let parts: Vec<Option<RT>> = arms
1779                .borrow()
1780                .iter()
1781                .map(|a| match &a.k {
1782                    RTk::Rec(rec) => {
1783                        find_member(&rec.members.borrow(), name).and_then(|m| m.ty.clone())
1784                    }
1785                    _ => None,
1786                })
1787                .collect();
1788            mk_abs(tyv(mk_union(parts)))
1789        }
1790        RTk::Quantity(_) if name == "value" || name == "unit" => {
1791            mk_abs(tyv(Some(prim(if name == "value" {
1792                "float"
1793            } else {
1794                "string"
1795            }))))
1796        }
1797        _ => mk_abs(unk()),
1798    }
1799}
1800
1801fn func_rt_of(env: &Rc<Env>, f: &FuncEntry) -> RT {
1802    ty(RTk::Func {
1803        params: f
1804            .params
1805            .iter()
1806            .map(|p| try_resolve(env, p.ty.as_ref()).unwrap_or_else(|| ty(RTk::Any)))
1807            .collect(),
1808        ret: try_resolve(env, f.ret.as_ref()).unwrap_or_else(|| ty(RTk::Any)),
1809    })
1810}
1811fn func_rt(cx: &Ctx, name: &str) -> RT {
1812    let f = cx.env.funcs.borrow().get(name).cloned().unwrap();
1813    func_rt_of(&cx.env, &f)
1814}
1815fn const_ty(cx: &Ctx, name: &str) -> Ty {
1816    if let Some(t) = cx.const_memo.borrow().get(name) {
1817        return t.clone();
1818    }
1819    cx.const_memo.borrow_mut().insert(name.to_string(), unk()); // cycle guard
1820    let c = cx.env.consts.borrow().get(name).cloned().unwrap();
1821    let anno = try_resolve(&cx.env, c.ty.as_ref());
1822    let t = match anno {
1823        Some(a) => tyv(Some(a)),
1824        None => infer(&make_ctx(cx.env.clone(), Rc::new(|_, _| {})), &c.expr), // silent module-scope inference
1825    };
1826    cx.const_memo
1827        .borrow_mut()
1828        .insert(name.to_string(), t.clone());
1829    t
1830}
1831
1832fn infer_call(cx: &Ctx, e: &Rc<Expr>) -> Ty {
1833    let Expr::Call { fun, args } = &**e else {
1834        return unk();
1835    };
1836    if let Some(sp) = std_path(fun) {
1837        let sig = std_sig(&sp);
1838        if sig.is_none() {
1839            cx.report(
1840                "E3003",
1841                format!("std.{sp} does not exist (§13.1: names not listed do not exist)"),
1842            );
1843        }
1844        if let Some((arity, _)) = &sig {
1845            if args.len() != *arity {
1846                cx.report(
1847                    "E4062",
1848                    format!("std.{sp} expects {arity} argument(s), got {}", args.len()),
1849                );
1850            }
1851        }
1852        for a in args {
1853            if matches!(&**a, Expr::Lambda { .. }) {
1854                infer(cx, a);
1855                continue;
1856            }
1857            require_val(cx, a, infer(cx, a), "as an argument");
1858        }
1859        return tyv(sig.and_then(|(_, r)| r));
1860    }
1861    let f = infer(cx, fun);
1862    let frt = f.rt.filter(|r| matches!(r.k, RTk::Func { .. }));
1863    let (params, ret): (Vec<RT>, Option<RT>) = match frt.as_ref().map(|r| &r.k) {
1864        Some(RTk::Func { params, ret }) => (params.clone(), ret_of(ret)),
1865        _ => (vec![], None),
1866    };
1867    if frt.is_some() && args.len() != params.len() {
1868        cx.report(
1869            "E4062",
1870            format!(
1871                "call expects {} argument(s), got {}",
1872                params.len(),
1873                args.len()
1874            ),
1875        );
1876    }
1877    for (i, a) in args.iter().enumerate() {
1878        let expected: Option<RT> =
1879            if frt.is_some() && i < params.len() && !matches!(params[i].k, RTk::Any) {
1880                Some(params[i].clone())
1881            } else {
1882                None
1883            };
1884        if let (Expr::Lambda { .. }, Some(ex)) = (&**a, &expected) {
1885            if matches!(ex.k, RTk::Func { .. }) {
1886                check_lambda(cx, a, ex);
1887                continue;
1888            }
1889        }
1890        if matches!(&**a, Expr::Lambda { .. }) {
1891            infer(cx, a);
1892            continue;
1893        }
1894        let at = require_val(cx, a, infer(cx, a), "as an argument");
1895        if let (Some(art), Some(ex)) = (&at.rt, &expected) {
1896            if !subsumes(&cx.env, art, ex) && !deferrable(art, ex) {
1897                cx.report(
1898                    "E4001",
1899                    format!("argument {} is not assignable to its parameter", i + 1),
1900                );
1901            }
1902        }
1903    }
1904    tyv(if frt.is_some() { ret } else { None })
1905}
1906
1907fn check_lambda(cx: &Ctx, e: &Rc<Expr>, expected: &RT) {
1908    let (Expr::Lambda { params, body }, RTk::Func { params: eps, ret }) = (&**e, &expected.k)
1909    else {
1910        return;
1911    };
1912    if params.len() != eps.len() {
1913        cx.report(
1914            "E4062",
1915            "lambda arity differs from expected function type".into(),
1916        );
1917        return;
1918    }
1919    let mut c2 = cx.child();
1920    for (i, p) in params.iter().enumerate() {
1921        if name_bound(&c2, p) {
1922            cx.report(
1923                "E3019",
1924                format!("lambda parameter {p} shadows an enclosing name"),
1925            );
1926        }
1927        c2.vars.insert(
1928            p.clone(),
1929            tyv(if matches!(eps[i].k, RTk::Any) {
1930                None
1931            } else {
1932                Some(eps[i].clone())
1933            }),
1934        );
1935        c2.locals.insert(p.clone());
1936    }
1937    let b = require_val(&c2, body, infer(&c2, body), "as a lambda result");
1938    if let (Some(brt), Some(r)) = (&b.rt, ret_of(ret)) {
1939        if !subsumes(&cx.env, brt, &r) && !deferrable(brt, &r) {
1940            cx.report(
1941                "E4001",
1942                "lambda body is not assignable to the expected result type".into(),
1943            );
1944        }
1945    }
1946}
1947
1948// ---------------- match (§4.7) ----------------
1949fn infer_match(cx: &Ctx, e: &Rc<Expr>, expected: Option<&RT>) -> Ty {
1950    let Expr::Match { subject, arms } = &**e else {
1951        return unk();
1952    };
1953    let s = require_val(cx, subject, infer(cx, subject), "as a match subject");
1954    let mut variants: Option<Vec<RT>> = None;
1955    if let Some(srt0) = &s.rt {
1956        // a match subject is a value position: a reference denotes its target's
1957        // value (§4.7, §7.4's mirror rule), which is what the runtime inspects
1958        let val: &RT = match &srt0.k {
1959            RTk::Ref(t) => t,
1960            _ => srt0,
1961        };
1962        let srt = strip_null(val);
1963        if let RTk::Union(vs) = &srt.k {
1964            let mut v = vs.borrow().clone();
1965            if has_null(Some(val)) {
1966                v.push(ty(RTk::Lit(Value::Null)));
1967            }
1968            variants = Some(v);
1969        } else {
1970            cx.report(
1971                "E4103",
1972                "`match` subject is not a discriminable union".into(),
1973            );
1974        }
1975    }
1976    let mut covered: HashSet<usize> = HashSet::new();
1977    let mut catch_alls = 0;
1978    let mut results: Vec<Option<RT>> = vec![];
1979    for arm in arms {
1980        let mut c2 = cx.child();
1981        if name_bound(&c2, &arm.v) {
1982            cx.report(
1983                "E3019",
1984                format!("match binding {} shadows an enclosing name", arm.v),
1985            );
1986        }
1987        let mut arm_ty: Option<RT> = None;
1988        if let Some(t) = &arm.ty {
1989            arm_ty = try_resolve(&cx.env, Some(t));
1990            if arm_ty.is_none() {
1991                cx.report("E3003", "unknown type in match arm".into());
1992            }
1993            if let (Some(vs), Some(at)) = (&variants, &arm_ty) {
1994                for (i, v) in vs.iter().enumerate() {
1995                    if subsumes(&cx.env, v, at) {
1996                        if covered.contains(&i) {
1997                            cx.report("E4100", "match arms overlap on a variant".into());
1998                        }
1999                        covered.insert(i);
2000                    }
2001                }
2002            }
2003        } else {
2004            catch_alls += 1;
2005            if let Some(vs) = &variants {
2006                let rest: Vec<Option<RT>> = vs
2007                    .iter()
2008                    .enumerate()
2009                    .filter(|(i, _)| !covered.contains(i))
2010                    .map(|(_, v)| Some(v.clone()))
2011                    .collect();
2012                if rest.is_empty() {
2013                    cx.report(
2014                        "E4102",
2015                        "match catch-all is dead (typed arms are exhaustive)".into(),
2016                    );
2017                }
2018                arm_ty = mk_union(rest);
2019            }
2020        }
2021        c2.vars.insert(arm.v.clone(), tyv(arm_ty));
2022        c2.locals.insert(arm.v.clone());
2023        let bt = match expected {
2024            Some(ex) => check_expr(&c2, &arm.body, Some(ex)),
2025            None => infer(&c2, &arm.body),
2026        };
2027        let b = require_val(&c2, &arm.body, bt, "as a match result");
2028        results.push(b.rt);
2029    }
2030    if catch_alls > 1 {
2031        cx.report("E4100", "more than one match catch-all arm".into());
2032    }
2033    if let Some(vs) = &variants {
2034        if catch_alls == 0 && covered.len() < vs.len() {
2035            cx.report(
2036                "E4101",
2037                "`match` is not exhaustive over the subject union".into(),
2038            );
2039        }
2040    }
2041    tyv(mk_union(results))
2042}
2043
2044// ---------------- bidirectional checking (§3.18) ----------------
2045/// a navigation expression in a ref<T> position denotes a place (§7.4):
2046/// the absence discipline does not apply along the spine — whether the
2047/// place holds a value is reference integrity (§7.5), checked at binding
2048fn place_ty(cx: &Ctx, e: &Rc<Expr>) -> Ty {
2049    match &**e {
2050        Expr::Paren(x) => place_ty(cx, x),
2051        Expr::Member { x, name, .. } => {
2052            let base = place_ty(cx, x);
2053            // a hidden member's value is not part of any document: no reference
2054            // can target it (§7.5, D34)
2055            let rec = base.rt.as_ref().map(|t| match &t.k {
2056                RTk::Ref(target) => target.clone(),
2057                _ => t.clone(),
2058            });
2059            if let Some(rec) = rec {
2060                if let RTk::Rec(r) = &rec.k {
2061                    if r.members
2062                        .borrow()
2063                        .iter()
2064                        .any(|m| m.name == *name && m.hidden)
2065                    {
2066                        cx.report("E4093", format!("`ref` position navigates hidden member {name} — not part of the value (§7.5)"));
2067                    }
2068                }
2069            }
2070            member_core(cx, base, e)
2071        }
2072        Expr::Index { x, .. } => index_core(cx, place_ty(cx, x), e),
2073        Expr::If { c, t, f } => {
2074            // a conditional between places is a place: each branch is read in
2075            // the ref position, the condition as an ordinary value (§7.4)
2076            let ct = require_val(cx, c, infer(cx, c), "as a condition");
2077            if ct.rt.is_some() && !is_boolish(ct.rt.as_ref()) {
2078                cx.report("E4001", "`if` condition is not bool".into());
2079            }
2080            let tt = place_ty(&apply_guards(cx, guards_of(c, true)), t);
2081            let ft = place_ty(&apply_guards(cx, guards_of(c, false)), f);
2082            Ty {
2083                rt: mk_union(vec![tt.rt, ft.rt]),
2084                abs: tt.abs || ft.abs,
2085            }
2086        }
2087        Expr::Name(n) if !cx.vars.contains_key(n) && cx.env.consts.borrow().contains_key(n) => {
2088            // the spine root must be a root-derived place, never a module const (§7.5, D32)
2089            cx.report(
2090                "E4093",
2091                format!(
2092                    "`ref` position navigates module const {n} — not a root-derived place (§7.5)"
2093                ),
2094            );
2095            infer(cx, e)
2096        }
2097        _ => infer(cx, e),
2098    }
2099}
2100
2101/// Check an expression against an expected type (§3.18, D31), or infer it when
2102/// none is expected.
2103pub fn check_expr(cx: &Ctx, e: &Rc<Expr>, expected: Option<&RT>) -> Ty {
2104    let Some(expected) = expected else {
2105        return infer(cx, e);
2106    };
2107    if let RTk::Ref(_) = &expected.k {
2108        place_ty(cx, e);
2109        return tyv(Some(expected.clone())); // place, not value (§7.4)
2110    }
2111    if let RTk::Pred { base, .. } = &expected.k {
2112        return check_expr(cx, e, Some(base));
2113    }
2114    if let RTk::IsectN(arms) = &expected.k {
2115        if matches!(
2116            &**e,
2117            Expr::Obj(_) | Expr::Arr(_) | Expr::Comp { .. } | Expr::MapComp { .. }
2118        ) {
2119            for arm in arms {
2120                check_expr(cx, e, Some(arm)); // a literal must satisfy every arm
2121            }
2122            return tyv(Some(expected.clone()));
2123        }
2124    }
2125    match (&**e, &expected.k) {
2126        (Expr::Comp { head, clauses }, RTk::Arr { elem, .. }) => {
2127            let c2 = bind_clauses(cx, clauses);
2128            check_expr(&c2, head, Some(elem));
2129            return tyv(Some(expected.clone()));
2130        }
2131        (Expr::MapComp { key, val, clauses }, RTk::Map { val: ev, .. }) => {
2132            let c2 = bind_clauses(cx, clauses);
2133            let k = require_val(&c2, key, infer(&c2, key), "as a map key");
2134            if k.rt.is_some() && num_kind(k.rt.as_ref()).as_deref() != Some("string") {
2135                cx.report("E4001", "map-comprehension key is not a string".into());
2136            }
2137            check_expr(&c2, val, Some(ev));
2138            return tyv(Some(expected.clone()));
2139        }
2140        (Expr::Paren(x), _) => return check_expr(cx, x, Some(expected)),
2141        (Expr::If { c, t, f }, _) => {
2142            let ct = require_val(cx, c, infer(cx, c), "as a condition");
2143            if ct.rt.is_some() && !is_boolish(ct.rt.as_ref()) {
2144                cx.report("E4001", "`if` condition is not bool".into());
2145            }
2146            check_expr(&apply_guards(cx, guards_of(c, true)), t, Some(expected));
2147            check_expr(&apply_guards(cx, guards_of(c, false)), f, Some(expected));
2148            return tyv(Some(expected.clone()));
2149        }
2150        (Expr::Match { .. }, _) => return infer_match(cx, e, Some(expected)),
2151        (Expr::Obj(entries), RTk::Rec(rec)) => {
2152            // entries see the record's members (siblings + inherited scope chain)
2153            let members = rec.members.borrow().clone();
2154            let mut cx_r = cx.child();
2155            for m in members.iter() {
2156                cx_r.vars.insert(
2157                    m.name.clone(),
2158                    Ty {
2159                        rt: member_ty(m),
2160                        abs: m.kind == MKind::Opt,
2161                    },
2162                );
2163            }
2164            // a spread (§4.2) contributes the value members of a record-typed operand;
2165            // an operand of unknown or map type may contribute anything, so the
2166            // required-member check stands down for that literal
2167            let mut provided: Vec<String> = vec![];
2168            let mut dynamic = false;
2169            for (k, v) in entries {
2170                if matches!(&**v, Expr::Spread(_)) {
2171                    let st = spread_ty(&cx_r, v).rt;
2172                    match st.as_ref().map(|t| &t.k) {
2173                        Some(RTk::Rec(sr)) => {
2174                            for sm in sr.members.borrow().iter() {
2175                                if sm.hidden {
2176                                    continue;
2177                                }
2178                                provided.push(sm.name.clone());
2179                                if !rec.open.get() && find_member(&members, &sm.name).is_none() {
2180                                    cx.report(
2181                                        "E4003",
2182                                        format!(
2183                                            "member {} (spread) is not declared on {}",
2184                                            sm.name,
2185                                            expected
2186                                                .name
2187                                                .borrow()
2188                                                .clone()
2189                                                .unwrap_or_else(|| "the record".into())
2190                                        ),
2191                                    );
2192                                }
2193                            }
2194                        }
2195                        _ => dynamic = true,
2196                    }
2197                    continue;
2198                }
2199                let Some(m) = find_member(&members, k) else {
2200                    if !rec.open.get() {
2201                        cx.report(
2202                            "E4003",
2203                            format!(
2204                                "member {k} is not declared on {}",
2205                                expected
2206                                    .name
2207                                    .borrow()
2208                                    .clone()
2209                                    .unwrap_or_else(|| "the record".into())
2210                            ),
2211                        );
2212                    }
2213                    require_val(&cx_r, v, infer(&cx_r, v), "as a construction member");
2214                    continue;
2215                };
2216                let mt = member_ty(m);
2217                let t = check_expr(&cx_r, v, mt.as_ref());
2218                require_val(&cx_r, v, t, "as a construction member");
2219            }
2220            if !dynamic {
2221                for m in members.iter() {
2222                    if m.kind == MKind::Req
2223                        && !provided.contains(&m.name)
2224                        && !entries.iter().any(|(k, _)| *k == m.name)
2225                    {
2226                        cx.report(
2227                            "E4002",
2228                            format!("required member {} missing in the construction", m.name),
2229                        );
2230                    }
2231                }
2232            }
2233            // §9.3: a cycle the construction closes (one through the type alone is the type's report)
2234            if let Some(cyc) = member_cycle(expected, Some(entries), &cx.locals) {
2235                if cyc.iter().any(|n| entries.iter().any(|(k, _)| k == n)) {
2236                    cx.report(
2237                        "E4113",
2238                        format!(
2239                            "construction of {}: dependency cycle {} — a bare name inside the literal is its own member (§9.3)",
2240                            expected.name.borrow().clone().unwrap_or_else(|| "the record".into()),
2241                            cyc.join(" -> ")
2242                        ),
2243                    );
2244                }
2245            }
2246            return tyv(Some(expected.clone()));
2247        }
2248        (Expr::Obj(entries), RTk::Map { val, .. }) => {
2249            for (_, v) in entries {
2250                if matches!(&**v, Expr::Spread(_)) {
2251                    spread_ty(cx, v);
2252                    continue;
2253                }
2254                let t = check_expr(cx, v, Some(val));
2255                require_val(cx, v, t, "as a map value");
2256            }
2257            return tyv(Some(expected.clone()));
2258        }
2259        (Expr::Obj(_), RTk::Union(_)) => {
2260            infer(cx, e);
2261            return tyv(Some(expected.clone())); // discriminated at binding
2262        }
2263        (Expr::Obj(_), _) => {
2264            infer(cx, e);
2265            cx.report(
2266                "E4001",
2267                format!("object literal where {} is expected", tag(expected)),
2268            );
2269            return tyv(Some(expected.clone()));
2270        }
2271        (Expr::Arr(items), RTk::Arr { elem, .. }) => {
2272            for (spread, x) in items {
2273                if *spread {
2274                    require_val(cx, x, infer(cx, x), "as a spread");
2275                    continue;
2276                }
2277                let t = check_expr(cx, x, Some(elem));
2278                require_val(cx, x, t, "as an array element");
2279            }
2280            return tyv(Some(expected.clone()));
2281        }
2282        (Expr::Lambda { .. }, RTk::Func { .. }) => {
2283            check_lambda(cx, e, expected);
2284            return tyv(Some(expected.clone()));
2285        }
2286        _ => {}
2287    }
2288    let t = require_val(cx, e, infer(cx, e), "as a value");
2289    if let Some(rt) = &t.rt {
2290        if !subsumes(&cx.env, rt, expected)
2291            && !deferrable(rt, expected)
2292            && !(cx.binding && deferrable_object(&cx.env, rt, expected))
2293        {
2294            cx.report(
2295                "E4001",
2296                "expression type does not satisfy the expected type".into(),
2297            );
2298        }
2299    }
2300    t
2301}
2302
2303/// at a binding site, an object whose entries the static type does not fix —
2304/// a map, or a union with a map or array arm (the interchange type `Json`) —
2305/// against a record, map, or array type it could take is validated when the
2306/// value is bound, as a document is (§3.18, v0.4.4); a record's shape is
2307/// known, so a record stays a static judgment, and a scalar where an object
2308/// is expected is still a kind mismatch
2309fn deferrable_object(env: &Rc<Env>, s: &RT, t: &RT) -> bool {
2310    match &t.k {
2311        RTk::Pred { base, .. } => return deferrable_object(env, s, base),
2312        RTk::Union(arms) => return arms.borrow().iter().any(|a| deferrable_object(env, s, a)),
2313        _ => {}
2314    }
2315    if let RTk::Union(arms) = &s.k {
2316        return arms.borrow().iter().any(|a| deferrable_object(env, a, t));
2317    }
2318    let fits =
2319        |a: &RT, b: &RT| subsumes(env, a, b) || deferrable(a, b) || deferrable_object(env, a, b);
2320    match (&s.k, &t.k) {
2321        (RTk::Map { .. }, RTk::Rec(_)) => true,
2322        (RTk::Map { val: sv, .. }, RTk::Map { val: tv, .. }) => fits(sv, tv),
2323        (RTk::Arr { elem: se, .. }, RTk::Arr { elem: te, .. }) => fits(se, te),
2324        _ => false,
2325    }
2326}
2327
2328/// a same-kind refinement target (pattern, range, literal set) whose
2329/// membership the static type cannot prove is validated at binding, not
2330/// rejected here — the corpus (guide, benchmarks) relies on this split;
2331/// kind-level mismatches still fail statically
2332fn deferrable(s: &RT, t: &RT) -> bool {
2333    let Some(k) = num_kind(Some(s)) else {
2334        return false;
2335    };
2336    match &t.k {
2337        RTk::Pattern { .. } => k == "string",
2338        RTk::Range { base, .. } => &k == base,
2339        RTk::Lit(_) => Some(k) == num_kind(Some(t)),
2340        RTk::Union(arms) => arms.borrow().iter().any(|a| deferrable(s, a)),
2341        RTk::Pred { base, .. } => deferrable(s, base),
2342        _ => false,
2343    }
2344}