Skip to main content

decl_lang/
semantics.rs

1//! Value model, environment, and type resolution — a port of the
2//! reference implementation's semantics.ts.
3use crate::ast::*;
4use indexmap::IndexMap;
5use num_bigint::{BigInt, Sign};
6use num_traits::{FromPrimitive, Signed, ToPrimitive};
7use regex::Regex;
8use rustc_hash::{FxBuildHasher, FxHashMap};
9use std::cell::{Cell, RefCell};
10use std::collections::{BTreeMap, HashMap, HashSet};
11use std::fmt;
12use std::rc::Rc;
13use std::sync::LazyLock;
14
15pub(crate) mod lifetime;
16pub use lifetime::collect_cycles;
17
18mod shared_text;
19pub use shared_text::SharedText;
20
21mod map_entries;
22pub(crate) use map_entries::{KeysSeen, MapShapePool};
23pub use map_entries::{
24    MapEntries, MapEntriesIntoIter, MapEntriesIter, MapEntriesIterMut, MapEntriesKeys,
25    MapEntriesValues, MapEntriesValuesMut,
26};
27
28mod prefix_path;
29#[cfg(feature = "runtime-diagnostics")]
30pub use lifetime::{take_gc_diagnostics, GcDiagnostics, GcTrigger};
31pub use prefix_path::{
32    prefix_path_diagnostics, prefix_path_layouts, PrefixPath, PrefixPathDiagnostics,
33    PrefixPathIter, PrefixPathLayouts, PrefixPathPool, PrefixPathPoolStats,
34};
35
36/// an integer value (§4.5): a machine word when it fits, arbitrary precision
37/// otherwise. The reference and Python hold every integer as a big integer;
38/// here the common small values avoid a heap allocation and a deep copy on
39/// clone, which dominate at scale (F21). Always normalized — a `Big` never
40/// holds a value that fits in `i64` — so equality and ordering are the
41/// machine-word comparison whenever both operands are small, and a `Small`
42/// never equals a `Big`.
43#[derive(Clone, Debug)]
44pub enum Num {
45    /// fits a machine word
46    Small(i64),
47    /// out of `i64` range
48    Big(Rc<BigInt>),
49}
50impl Num {
51    /// zero.
52    pub fn zero() -> Num {
53        Num::Small(0)
54    }
55    /// a big integer, demoted to `Small` when it fits a word.
56    pub fn from_big(b: BigInt) -> Num {
57        match b.to_i64() {
58            Some(n) => Num::Small(n),
59            None => Num::Big(Rc::new(b)),
60        }
61    }
62    /// its value as a big integer.
63    pub fn to_big(&self) -> BigInt {
64        match self {
65            Num::Small(n) => BigInt::from(*n),
66            Num::Big(b) => (**b).clone(),
67        }
68    }
69    /// its value as `f64` (§4.5), `None` only for a non-finite big integer.
70    pub fn to_f64(&self) -> Option<f64> {
71        match self {
72            Num::Small(n) => Some(*n as f64),
73            Num::Big(b) => b.to_f64(),
74        }
75    }
76    /// its value as `i64` when it fits.
77    pub fn to_i64(&self) -> Option<i64> {
78        match self {
79            Num::Small(n) => Some(*n),
80            Num::Big(b) => b.to_i64(),
81        }
82    }
83    /// its value as `usize` when it fits and is non-negative.
84    pub fn to_usize(&self) -> Option<usize> {
85        match self {
86            Num::Small(n) => usize::try_from(*n).ok(),
87            Num::Big(b) => b.to_usize(),
88        }
89    }
90    /// whether it is zero.
91    pub fn is_zero(&self) -> bool {
92        matches!(self, Num::Small(0))
93    }
94    /// whether it is negative.
95    pub fn is_negative(&self) -> bool {
96        match self {
97            Num::Small(n) => *n < 0,
98            Num::Big(b) => b.sign() == Sign::Minus,
99        }
100    }
101    /// its absolute value.
102    pub fn abs(&self) -> Num {
103        match self {
104            Num::Small(n) => n
105                .checked_abs()
106                .map(Num::Small)
107                .unwrap_or_else(|| Num::from_big(BigInt::from(*n).abs())),
108            Num::Big(b) => Num::from_big(b.abs()),
109        }
110    }
111    /// the number of bits in its absolute value (as `BigInt::bits`).
112    pub fn bits(&self) -> u64 {
113        match self {
114            Num::Small(n) => BigInt::from(*n).bits(),
115            Num::Big(b) => b.bits(),
116        }
117    }
118    /// a float rounded toward zero to an integer, `None` if non-finite.
119    pub fn from_f64(x: f64) -> Option<Num> {
120        BigInt::from_f64(x).map(Num::from_big)
121    }
122    /// parse a decimal (or signed) integer literal.
123    pub fn parse_str(s: &str) -> Option<Num> {
124        s.parse::<BigInt>().ok().map(Num::from_big)
125    }
126}
127impl From<i64> for Num {
128    fn from(n: i64) -> Num {
129        Num::Small(n)
130    }
131}
132impl From<i32> for Num {
133    fn from(n: i32) -> Num {
134        Num::Small(n as i64)
135    }
136}
137impl From<u32> for Num {
138    fn from(n: u32) -> Num {
139        Num::Small(n as i64)
140    }
141}
142impl From<usize> for Num {
143    fn from(n: usize) -> Num {
144        i64::try_from(n)
145            .map(Num::Small)
146            .unwrap_or_else(|_| Num::from_big(BigInt::from(n)))
147    }
148}
149impl From<u64> for Num {
150    fn from(n: u64) -> Num {
151        i64::try_from(n)
152            .map(Num::Small)
153            .unwrap_or_else(|_| Num::from_big(BigInt::from(n)))
154    }
155}
156impl From<BigInt> for Num {
157    fn from(b: BigInt) -> Num {
158        Num::from_big(b)
159    }
160}
161impl fmt::Display for Num {
162    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
163        match self {
164            Num::Small(n) => write!(f, "{n}"),
165            Num::Big(b) => write!(f, "{b}"),
166        }
167    }
168}
169impl PartialEq for Num {
170    fn eq(&self, o: &Num) -> bool {
171        match (self, o) {
172            (Num::Small(a), Num::Small(b)) => a == b,
173            (Num::Big(a), Num::Big(b)) => a == b,
174            _ => false, // normalized: a Small and a Big are never equal
175        }
176    }
177}
178impl Eq for Num {}
179impl Ord for Num {
180    fn cmp(&self, o: &Num) -> std::cmp::Ordering {
181        match (self, o) {
182            (Num::Small(a), Num::Small(b)) => a.cmp(b),
183            _ => self.to_big().cmp(&o.to_big()),
184        }
185    }
186}
187impl PartialOrd for Num {
188    fn partial_cmp(&self, o: &Num) -> Option<std::cmp::Ordering> {
189        Some(self.cmp(o))
190    }
191}
192impl std::ops::Neg for &Num {
193    type Output = Num;
194    fn neg(self) -> Num {
195        match self {
196            Num::Small(n) => n
197                .checked_neg()
198                .map(Num::Small)
199                .unwrap_or_else(|| Num::from_big(-BigInt::from(*n))),
200            Num::Big(b) => Num::from_big(-&**b),
201        }
202    }
203}
204macro_rules! num_binop {
205    ($tr:ident, $m:ident, $checked:ident, $op:tt) => {
206        impl std::ops::$tr for &Num {
207            type Output = Num;
208            fn $m(self, rhs: &Num) -> Num {
209                if let (Num::Small(a), Num::Small(b)) = (self, rhs) {
210                    if let Some(r) = a.$checked(*b) {
211                        return Num::Small(r);
212                    }
213                }
214                Num::from_big(self.to_big() $op rhs.to_big())
215            }
216        }
217    };
218}
219num_binop!(Add, add, checked_add, +);
220num_binop!(Sub, sub, checked_sub, -);
221num_binop!(Mul, mul, checked_mul, *);
222num_binop!(Div, div, checked_div, /);
223num_binop!(Rem, rem, checked_rem, %);
224macro_rules! num_bitop {
225    ($tr:ident, $m:ident, $op:tt) => {
226        impl std::ops::$tr for &Num {
227            type Output = Num;
228            fn $m(self, rhs: &Num) -> Num {
229                if let (Num::Small(a), Num::Small(b)) = (self, rhs) {
230                    return Num::Small(a $op b);
231                }
232                Num::from_big(self.to_big() $op rhs.to_big())
233            }
234        }
235    };
236}
237num_bitop!(BitAnd, bitand, &);
238num_bitop!(BitOr, bitor, |);
239num_bitop!(BitXor, bitxor, ^);
240impl std::ops::Shl<usize> for &Num {
241    type Output = Num;
242    fn shl(self, n: usize) -> Num {
243        Num::from_big(self.to_big() << n)
244    }
245}
246impl std::ops::Shr<usize> for &Num {
247    type Output = Num;
248    fn shr(self, n: usize) -> Num {
249        Num::from_big(self.to_big() >> n)
250    }
251}
252impl std::ops::Neg for Num {
253    type Output = Num;
254    fn neg(self) -> Num {
255        -&self
256    }
257}
258// small-literal arithmetic on the counters and bounds a range walk uses
259impl std::ops::Add<i64> for &Num {
260    type Output = Num;
261    fn add(self, n: i64) -> Num {
262        self + &Num::Small(n)
263    }
264}
265impl std::ops::Sub<i64> for &Num {
266    type Output = Num;
267    fn sub(self, n: i64) -> Num {
268        self - &Num::Small(n)
269    }
270}
271impl std::ops::AddAssign<i64> for Num {
272    fn add_assign(&mut self, n: i64) {
273        *self = &*self + n;
274    }
275}
276
277// the pattern-interpolation grammar (§3.6): compiled once
278static PATTERN_HOLE: LazyLock<Regex> = LazyLock::new(|| Regex::new(r"\$\{([^}]*)\}").unwrap());
279static PATTERN_STR_LIT: LazyLock<Regex> =
280    LazyLock::new(|| Regex::new(r#"^"((?:[^"\\]|\\.)*)"$"#).unwrap());
281static PATTERN_INT_RANGE: LazyLock<Regex> =
282    LazyLock::new(|| Regex::new(r"^(-?[0-9]+)\.\.(<?)(-?[0-9]+)$").unwrap());
283static PATTERN_INT_LIT: LazyLock<Regex> = LazyLock::new(|| Regex::new(r"^-?[0-9]+$").unwrap());
284static PATTERN_IDENT: LazyLock<Regex> =
285    LazyLock::new(|| Regex::new(r"^[A-Za-z_][A-Za-z0-9_.]*$").unwrap());
286
287// ---------------- paths ----------------
288#[derive(Clone, Debug, PartialEq, Eq, Hash)]
289/// a segment of a canonical path (§7.2)
290pub enum Seg {
291    /// a record member by name: dotted when the dot can spell it (§7.2)
292    Name(Rc<str>),
293    /// an array index
294    Idx(usize),
295    /// a map key: always bracketed (§7.2)
296    Key(Rc<str>),
297}
298/// a canonical path
299pub type SegPath = Vec<Seg>;
300/// A segment's text as the path spells it.
301pub fn seg_text(s: &Seg) -> String {
302    match s {
303        Seg::Name(n) | Seg::Key(n) => n.to_string(),
304        Seg::Idx(i) => i.to_string(),
305    }
306}
307/// dot-spellable (§3.11, §4.3): identifier-shaped and not a literal keyword
308pub fn dot_spellable(name: &str) -> bool {
309    let mut cs = name.chars();
310    let head = matches!(cs.next(), Some(c) if c == '_' || c.is_ascii_alphabetic());
311    head && cs.all(|c| c == '_' || c.is_ascii_alphanumeric())
312        && !matches!(name, "true" | "false" | "null")
313}
314
315// ---------------- values ----------------
316#[derive(Clone)]
317/// a runtime value (§9): the scalars, quantities, references, and instances,
318/// and the engine's intermediate forms
319pub enum Value {
320    /// an integer
321    Int(Num),
322    /// a float
323    Float(f64),
324    /// a string
325    Str(SharedText),
326    /// a boolean
327    Bool(bool),
328    /// null
329    Null,
330    /// an absent optional member (§4.6)
331    Absent,
332    /// not yet computed
333    Undef,
334    /// a quantity
335    Q(Box<QuantityValue>),
336    /// a reference, by canonical path
337    Ref(Rc<SegPath>),
338    /// a record instance
339    Rec(Rc<RefCell<RecInst>>),
340    /// an array
341    Arr(Rc<RefCell<ArrV>>),
342    /// a map
343    Map(Rc<RefCell<MapV>>),
344    /// a range value
345    Range(Box<RangeValue>),
346    /// a closure
347    Clo(Rc<Closure>),
348    /// a native function
349    Nat(NatFn),
350    /// a standard-library path, partially spelled
351    Std(Rc<Vec<String>>),
352    /// a namespace
353    NsRef(Rc<NsRefV>),
354    /// a pattern
355    Pat(SharedText),
356    /// a record literal not yet bound
357    PreObj(Rc<Vec<(String, Value)>>),
358    /// an array literal not yet bound: (spread, item)
359    PreArr(Rc<Vec<(bool, Value)>>),
360    /// an expression not yet evaluated, with its scope
361    PreVal(Rc<PreValV>),
362    /// a JSON object, as read
363    JObj(Rc<Vec<(String, Value)>>),
364    /// a JSON array, as read
365    JArr(Rc<Vec<Value>>),
366    /// a path value
367    Segs(Rc<SegPath>),
368}
369
370/// A uniquely owned quantity magnitude and its shared dimension key.
371/// Cloning preserves independent magnitude mutation and dimension copy-on-write.
372#[derive(Clone)]
373pub struct QuantityValue {
374    /// The shared dimension key; use quantity_dimension_mut for copy-on-write.
375    pub dim: Rc<String>,
376    /// The magnitude in the base unit.
377    pub value: f64,
378}
379
380/// Uniquely owned range endpoints. Cloning a range clones its endpoint Values;
381/// sharing the payload would change native mutation and collector edge counts.
382#[derive(Clone)]
383pub struct RangeValue {
384    /// The lower bound.
385    pub lo: Value,
386    /// The upper bound.
387    pub hi: Value,
388    /// Whether the upper bound is excluded.
389    pub excl: bool,
390}
391
392impl fmt::Debug for Value {
393    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
394        match self {
395            Value::Int(i) => write!(f, "{i}"),
396            Value::Float(x) => write!(f, "{x}"),
397            Value::Str(s) => write!(f, "{s:?}"),
398            Value::Bool(b) => write!(f, "{b}"),
399            Value::Null => write!(f, "null"),
400            Value::Absent => write!(f, "ABSENT"),
401            Value::Undef => write!(f, "UNDEF"),
402            Value::Q(q) => write!(f, "{}<{}>", q.value, q.dim),
403            other => write!(f, "<{}>", other.tag()),
404        }
405    }
406}
407
408impl Value {
409    /// Construct a quantity with a base-unit magnitude and a dimension key.
410    /// Display units remain properties of the environment, not this value.
411    pub fn quantity(dim: impl Into<String>, value: f64) -> Self {
412        Self::Q(Box::new(QuantityValue {
413            dim: Rc::new(dim.into()),
414            value,
415        }))
416    }
417    /// Borrow the dimension and read the independently stored magnitude.
418    pub fn as_quantity(&self) -> Option<(&str, f64)> {
419        match self {
420            Self::Q(q) => Some((q.dim.as_str(), q.value)),
421            _ => None,
422        }
423    }
424    /// Mutate a dimension without changing a retained clone's dimension.
425    pub fn quantity_dimension_mut(&mut self) -> Option<&mut String> {
426        match self {
427            Self::Q(q) => Some(Rc::make_mut(&mut q.dim)),
428            _ => None,
429        }
430    }
431    /// Mutate this quantity's independently owned magnitude or dimension owner.
432    pub fn as_quantity_mut(&mut self) -> Option<&mut QuantityValue> {
433        match self {
434            Self::Q(q) => Some(q),
435            _ => None,
436        }
437    }
438    /// Construct a range without evaluating or restricting its endpoints.
439    /// Iteration and membership retain their existing validation boundaries.
440    pub fn range(lo: Value, hi: Value, excl: bool) -> Self {
441        Self::Range(Box::new(RangeValue { lo, hi, excl }))
442    }
443    /// Borrow a range's uniquely owned endpoints and exclusion flag.
444    pub fn as_range(&self) -> Option<&RangeValue> {
445        match self {
446            Self::Range(range) => Some(range),
447            _ => None,
448        }
449    }
450    /// Mutate this range's endpoints; ordinary Value clone rules still apply
451    /// to containers or native captures stored inside those endpoints.
452    pub fn as_range_mut(&mut self) -> Option<&mut RangeValue> {
453        match self {
454            Self::Range(range) => Some(range),
455            _ => None,
456        }
457    }
458    /// Construct pattern text. Pattern equality remains non-reflexive.
459    pub fn pattern(src: impl Into<Rc<str>>) -> Self {
460        Self::Pat(SharedText::from_rc(src.into()))
461    }
462    /// Borrow pattern text without exposing its shared storage.
463    pub fn as_pattern(&self) -> Option<&str> {
464        match self {
465            Self::Pat(src) => Some(src),
466            _ => None,
467        }
468    }
469    /// Share one native callable and its captures across Value clones.
470    pub fn native<F>(f: F) -> Self
471    where
472        F: Fn(&[Value]) -> R<Value> + 'static,
473    {
474        Self::Nat(Rc::new(Box::new(f)))
475    }
476    /// The value's kind, as a word.
477    pub fn tag(&self) -> &'static str {
478        match self {
479            Value::Int(_) => "int",
480            Value::Float(_) => "float",
481            Value::Str(_) => "string",
482            Value::Bool(_) => "bool",
483            Value::Null => "null",
484            Value::Absent => "absent",
485            Value::Undef => "undef",
486            Value::Q(_) => "quantity",
487            Value::Ref(_) => "ref",
488            Value::Rec(_) => "record",
489            Value::Arr(_) => "array",
490            Value::Map(_) => "map",
491            Value::Range(_) => "range",
492            Value::Clo(_) => "closure",
493            Value::Nat(_) => "native",
494            Value::Std(_) => "std",
495            Value::NsRef(_) => "namespace",
496            Value::Pat(_) => "pattern",
497            Value::PreObj(_) => "pre-obj",
498            Value::PreArr(_) => "pre-arr",
499            Value::PreVal(_) => "pre-val",
500            Value::JObj(_) => "json-obj",
501            Value::JArr(_) => "json-arr",
502            Value::Segs(_) => "segs",
503        }
504    }
505    /// Whether the value is not yet computed.
506    pub fn is_undef(&self) -> bool {
507        matches!(self, Value::Undef)
508    }
509    /// Whether the value is absent.
510    pub fn is_absent(&self) -> bool {
511        matches!(self, Value::Absent)
512    }
513    /// The canonical path the value sits at or refers to, when it has one.
514    pub fn place(&self) -> Option<SegPath> {
515        match self {
516            Value::Ref(p) => Some((**p).clone()),
517            Value::Rec(r) => Some(r.borrow().path.to_vec()),
518            Value::Arr(a) => Some(a.borrow().path.to_vec()),
519            Value::Map(m) => Some(m.borrow().path.to_vec()),
520            _ => None,
521        }
522    }
523}
524
525/// a native function
526pub type NatFn = Rc<Box<dyn Fn(&[Value]) -> R<Value>>>;
527
528/// a function value: its parameters, its body, the scope it closed over
529pub struct Closure {
530    /// the parameters
531    pub params: Vec<String>,
532    /// the body
533    pub body: Rc<Expr>,
534    /// the scope
535    pub scope: Scope,
536}
537/// a namespace's exports
538pub struct NsRefV {
539    /// the exports, by name
540    pub exports: Rc<RefCell<HashMap<String, Export>>>,
541}
542/// an expression waiting to be evaluated in its scope
543pub struct PreValV {
544    /// the expression
545    pub expr: Rc<Expr>,
546    /// the scope
547    pub scope: Scope,
548}
549/// an array value
550pub struct ArrV {
551    /// the items
552    pub items: Vec<Value>,
553    /// its canonical path
554    pub path: PrefixPath,
555}
556/// An insertion-ordered table with indexed lookup. Iteration retains language
557/// order while reference navigation and member access avoid linear scans.
558pub type OrderedMap<T> = IndexMap<String, T, FxBuildHasher>;
559
560/// a map value
561pub struct MapV {
562    /// the entries, in order
563    pub entries: MapEntries,
564    /// its canonical path
565    pub path: PrefixPath,
566}
567impl MapV {
568    /// The value at a key.
569    pub fn get(&self, k: &str) -> Option<&Value> {
570        self.entries.get(k)
571    }
572    /// Whether the key is present.
573    pub fn has(&self, k: &str) -> bool {
574        self.entries.contains_key(k)
575    }
576    /// Set a key's value.
577    pub fn set(&mut self, k: String, v: Value) {
578        self.entries.insert(k, v);
579    }
580}
581
582#[derive(Clone, Copy, PartialEq, Debug)]
583/// a member's kind (§5)
584pub enum MKind {
585    /// required
586    Req,
587    /// optional
588    Opt,
589    /// defaulted
590    Dflt,
591    /// derived
592    Der,
593}
594#[derive(Clone, Copy, PartialEq, Debug)]
595/// the state of a slot
596pub enum SlotState {
597    /// not forced yet
598    Unforced,
599    /// the computation reached `$referrers` before the universe was complete: not attempted again
600    /// until phase 2 (a demand meanwhile defers at once)
601    Deferred,
602    /// being forced
603    Forcing,
604    /// forced, with a value
605    Ok,
606    /// an error invalidated it
607    Invalid,
608    /// absent
609    Absent,
610}
611
612#[derive(Clone)]
613/// how a slot computes its value
614pub enum Compute {
615    /// a supplied value checked against the types
616    Check {
617        /// the value supplied
618        raw: Value,
619        /// the types to check against
620        types: Rc<Vec<RT>>,
621        /// the member
622        name: Rc<str>,
623        /// the root
624        root_name: Rc<str>,
625        /// the module environment
626        menv: Option<Rc<Env>>,
627    },
628    /// a default expression
629    Default {
630        /// the expression
631        expr: Rc<Expr>,
632        /// the shared executable program, when queries are enabled
633        op: Option<crate::qengine::programs::Op>,
634        /// the types to check against
635        types: Rc<Vec<RT>>,
636        /// the member
637        name: Rc<str>,
638        /// the root
639        root_name: Rc<str>,
640        /// the module environment
641        menv: Option<Rc<Env>>,
642    },
643    /// a derived expression
644    Derived {
645        /// the expression
646        expr: Rc<Expr>,
647        /// the shared executable program, when queries are enabled
648        op: Option<crate::qengine::programs::Op>,
649        /// the declared type
650        ty: Option<RT>,
651        /// the value the document supplied, to compare (§10.5)
652        supplied: Option<Value>,
653        /// the member
654        name: Rc<str>,
655        /// the root
656        root_name: Rc<str>,
657        /// the module environment
658        menv: Option<Rc<Env>>,
659    },
660    /// a query-engine slot: forcing it runs the given thunk, which reads the
661    /// value through the incremental database (qengine). Lets the value layer
662    /// force a query-graph slot uniformly (§7.5 navigation, §6 asserts).
663    Bridge(Rc<dyn Fn() -> R<Value>>),
664}
665
666/// a member's slot in an instance
667pub struct Slot {
668    /// the member's kind
669    pub kind: MKind,
670    /// `x$ = e`: computed, never part of the value (D34)
671    pub hidden: bool,
672    /// its state
673    pub state: SlotState,
674    /// its value, once forced
675    pub value: Value,
676    /// Binding-time computation metadata. Shared snapshots are immutable;
677    /// use `computation_mut` for an isolated copy-on-write mutation.
678    pub compute: Option<Rc<Compute>>,
679}
680
681impl Slot {
682    /// Inspect the descriptor captured when this slot was bound.
683    pub fn computation(&self) -> Option<&Compute> {
684        self.compute.as_deref()
685    }
686
687    /// Retain an immutable descriptor snapshot, including its captured owners.
688    pub fn computation_snapshot(&self) -> Option<Rc<Compute>> {
689        self.compute.clone()
690    }
691
692    /// Mutate this slot's descriptor without changing an outstanding snapshot.
693    /// As with direct field replacement, this does not reset the slot state or
694    /// invalidate retained queries; the caller still owns that policy.
695    pub fn computation_mut(&mut self) -> Option<&mut Compute> {
696        self.compute.as_mut().map(Rc::make_mut)
697    }
698
699    /// Replace or remove captured metadata. This does not change state/value.
700    pub fn set_computation(&mut self, compute: Option<Compute>) {
701        self.compute = compute.map(Rc::new);
702    }
703}
704
705/// a record instance: its type, its path, its slots
706pub struct RecInst {
707    /// the type's name, when named
708    pub type_name: Option<String>,
709    /// the type
710    pub rt: RT,
711    /// its canonical path
712    pub path: Rc<SegPath>,
713    /// cached path_str(path) for the slot key (F21); path is immutable
714    pub ps: RefCell<Option<String>>,
715    /// the enclosing instance
716    pub parent: Option<Rc<RefCell<RecInst>>>,
717    // declaration order matters (forcing order drives diagnostic order)
718    /// the slots, in declaration order
719    pub slots: Vec<(Rc<str>, Slot)>,
720    /// the order the document supplied the members
721    pub entry_order: Rc<Vec<String>>,
722    /// members of an open record beyond its type
723    pub extras: Vec<(String, Value)>,
724    /// the module environment
725    pub menv: Option<Rc<Env>>,
726}
727
728/// Allocate an instance and track its lifetime without retaining it.
729pub(crate) fn record_instance(record: RecInst) -> Rc<RefCell<RecInst>> {
730    let record = Rc::new(RefCell::new(record));
731    lifetime::track_record(&record);
732    record
733}
734impl RecInst {
735    /// Borrow the member order captured from the input document.
736    pub fn entry_order(&self) -> &[String] {
737        &self.entry_order
738    }
739    /// Retain the current order independently of later record mutation.
740    pub fn entry_order_snapshot(&self) -> Rc<Vec<String>> {
741        self.entry_order.clone()
742    }
743    /// Edit this record's order without changing other records or snapshots.
744    pub fn entry_order_mut(&mut self) -> &mut Vec<String> {
745        Rc::make_mut(&mut self.entry_order)
746    }
747    /// An extra member's value.
748    pub fn extra(&self, n: &str) -> Option<&Value> {
749        self.extras.iter().find(|(k, _)| k == n).map(|(_, v)| v)
750    }
751    /// Set an extra member.
752    pub fn set_extra(&mut self, n: &str, v: Value) {
753        if let Some(e) = self.extras.iter_mut().find(|(k, _)| k == n) {
754            e.1 = v;
755        } else {
756            self.extras.push((n.to_string(), v));
757        }
758    }
759    /// A slot by name.
760    pub fn slot(&self, n: &str) -> Option<&Slot> {
761        self.slots
762            .iter()
763            .find(|(k, _)| k.as_ref() == n)
764            .map(|(_, s)| s)
765    }
766    /// A slot by name, mutably.
767    pub fn slot_mut(&mut self, n: &str) -> Option<&mut Slot> {
768        self.slots
769            .iter_mut()
770            .find(|(k, _)| k.as_ref() == n)
771            .map(|(_, s)| s)
772    }
773    /// Whether the slot exists.
774    pub fn has_slot(&self, n: &str) -> bool {
775        self.slots.iter().any(|(k, _)| k.as_ref() == n)
776    }
777}
778
779/// the local variables of a scope: a persistent chain of (name, value)
780/// frames (F21 perf: extending a scope with one binding — the hot path in a
781/// comprehension iterated over thousands of items — allocates one small frame
782/// instead of cloning a whole map; the depth is a handful of loop/parameter
783/// names, so a linear lookup is cheap). This is a Rust-only representation; the
784/// reference keeps a map (see AGENTS.md, the performance layer).
785#[derive(Clone, Default)]
786pub struct Locals(Option<Rc<LocalFrame>>);
787/// one binding in a `Locals` chain
788pub struct LocalFrame {
789    name: Rc<str>,
790    value: Value,
791    next: Option<Rc<LocalFrame>>,
792}
793impl Locals {
794    /// Visible bindings, for comparing captured scopes between Session edits.
795    pub(crate) fn entries(&self) -> FxHashMap<Rc<str>, Value> {
796        let mut out = FxHashMap::default();
797        let mut current = &self.0;
798        while let Some(frame) = current {
799            out.entry(frame.name.clone())
800                .or_insert_with(|| frame.value.clone());
801            current = &frame.next;
802        }
803        out
804    }
805    /// The empty scope.
806    pub fn new() -> Locals {
807        Locals(None)
808    }
809    /// The scope with one more binding, shadowing any earlier one of the name.
810    pub fn with(&self, name: Rc<str>, value: Value) -> Locals {
811        #[cfg(feature = "runtime-diagnostics")]
812        crate::retention_diagnostics::local_frame();
813        Locals(Some(Rc::new(LocalFrame {
814            name,
815            value,
816            next: self.0.clone(),
817        })))
818    }
819    /// The value bound to a name, innermost first.
820    pub fn get(&self, name: &str) -> Option<&Value> {
821        let mut cur = &self.0;
822        while let Some(f) = cur {
823            if &*f.name == name {
824                return Some(&f.value);
825            }
826            cur = &f.next;
827        }
828        None
829    }
830    /// Build a scope from a map's entries (used off the hot path, e.g. rendering).
831    pub fn from_map(m: &FxHashMap<String, Value>) -> Locals {
832        let mut l = Locals::new();
833        for (k, v) in m {
834            l = l.with(Rc::from(k.as_str()), v.clone());
835        }
836        l
837    }
838}
839
840#[derive(Clone)]
841/// an evaluation scope: the enclosing instance, the local variables, the root, the module environment
842pub struct Scope {
843    /// the enclosing instance
844    pub inst: Option<Rc<RefCell<RecInst>>>,
845    /// the local variables
846    pub locals: Locals,
847    /// the root
848    pub root_name: Rc<str>,
849    /// the module environment
850    pub menv: Option<Rc<Env>>,
851}
852impl Scope {
853    /// A scope at a root.
854    pub fn new(root_name: &str, menv: Option<Rc<Env>>) -> Scope {
855        Scope {
856            inst: None,
857            locals: Locals::new(),
858            root_name: Rc::from(root_name),
859            menv,
860        }
861    }
862    /// The scope with local variables.
863    pub fn with_locals(&self, locals: Locals) -> Scope {
864        Scope {
865            inst: self.inst.clone(),
866            locals,
867            root_name: self.root_name.clone(),
868            menv: self.menv.clone(),
869        }
870    }
871    /// The scope inside an instance.
872    pub fn with_inst(&self, inst: Option<Rc<RefCell<RecInst>>>) -> Scope {
873        Scope {
874            inst,
875            locals: self.locals.clone(),
876            root_name: self.root_name.clone(),
877            menv: self.menv.clone(),
878        }
879    }
880    /// The scope in a module environment.
881    pub fn with_menv(&self, menv: Option<Rc<Env>>) -> Scope {
882        Scope {
883            inst: self.inst.clone(),
884            locals: self.locals.clone(),
885            root_name: self.root_name.clone(),
886            menv,
887        }
888    }
889}
890
891// ---------------- failures & diagnostics ----------------
892/// an evaluation error, with its code when it has one
893pub struct EvalErr {
894    /// the message
895    pub msg: String,
896    /// the code
897    pub code: Option<String>,
898}
899/// why an evaluation stopped
900pub enum Fail {
901    /// it read an invalid value
902    Taint,
903    /// it must wait for phase 2
904    Defer,
905    /// an error
906    Eval(EvalErr),
907}
908/// an evaluation's outcome
909pub type R<T> = Result<T, Fail>;
910/// An evaluation error without a code.
911pub fn err<T>(msg: impl Into<String>) -> R<T> {
912    Err(Fail::Eval(EvalErr {
913        msg: msg.into(),
914        code: None,
915    }))
916}
917/// An evaluation error with a code.
918pub fn err_code<T>(msg: impl Into<String>, code: &str) -> R<T> {
919    Err(Fail::Eval(EvalErr {
920        msg: msg.into(),
921        code: Some(code.to_string()),
922    }))
923}
924
925#[derive(Clone, Debug)]
926/// a diagnostic (§6, §12)
927pub struct Diag {
928    /// `error`, `warn`, or `info`
929    pub severity: String,
930    /// the constraint's stable id, for an assertion
931    pub id: Option<String>,
932    /// the message, rendered
933    pub message: String,
934    /// the canonical path
935    pub path: String,
936    /// the code (§12)
937    pub code: Option<String>,
938    /// the source range the checker reported at (the declaration, or the expression under inference)
939    pub loc: Option<Loc>,
940    /// the evaluation step that produced it (a slot, a root, an assert): dependency tracking's tag
941    pub by: Option<String>,
942}
943impl Diag {
944    /// An error diagnostic at a path.
945    pub fn error(message: impl Into<String>, path: String, code: Option<&str>) -> Diag {
946        Diag {
947            severity: "error".into(),
948            id: None,
949            message: message.into(),
950            path,
951            code: code.map(|c| c.to_string()),
952            loc: None,
953            by: None,
954        }
955    }
956    /// The diagnostic as a JSON object in the report's field order (§12.2), with the file when given.
957    pub fn to_json(&self, file: Option<&str>) -> String {
958        let mut parts = Vec::new();
959        // the report's field order (§12.2): file, code, id, severity,
960        // message, path — absent fields omitted (byte-identical across
961        // implementations)
962        if let Some(f) = file {
963            parts.push(format!("\"file\":{}", json_str(f)));
964        }
965        if let Some(c) = &self.code {
966            parts.push(format!("\"code\":{}", json_str(c)));
967        }
968        if let Some(id) = &self.id {
969            parts.push(format!("\"id\":{}", json_str(id)));
970        }
971        parts.push(format!("\"severity\":{}", json_str(&self.severity)));
972        parts.push(format!("\"message\":{}", json_str(&self.message)));
973        parts.push(format!("\"path\":{}", json_str(&self.path)));
974        // §12.2: a source span, 1-based, for compile-time diagnostics
975        if let (Some(f), Some(l)) = (file, &self.loc) {
976            parts.push(format!(
977                "\"location\":{{\"file\":{},\"line\":{},\"col\":{}}}",
978                json_str(f),
979                l.sl + 1,
980                l.sc + 1
981            ));
982        }
983        format!("{{{}}}", parts.join(","))
984    }
985}
986
987// ---------------- resolved types ----------------
988/// a resolved type, shared
989pub type RT = Rc<Ty>;
990
991/// a resolved type: its kind, its name when named, its `else` tail
992pub struct Ty {
993    /// the kind
994    pub k: RTk,
995    /// the name, for a named type
996    pub name: RefCell<Option<String>>,
997    /// the `else` tail
998    pub tail: RefCell<Option<Tail>>,
999}
1000/// A resolved type of a kind.
1001pub fn ty(k: RTk) -> RT {
1002    let rt = Rc::new(Ty {
1003        k,
1004        name: RefCell::new(None),
1005        tail: RefCell::new(None),
1006    });
1007    lifetime::track_type(&rt);
1008    rt
1009}
1010
1011/// the kinds of resolved types (§3)
1012pub enum RTk {
1013    /// a primitive
1014    Prim(String),
1015    /// a literal
1016    Lit(Value),
1017    /// a numeric range
1018    Range {
1019        /// the lower bound
1020        lo: Value,
1021        /// the upper bound
1022        hi: Value,
1023        /// whether the upper bound is excluded
1024        excl: bool,
1025        /// int or float
1026        base: String,
1027    },
1028    /// a string pattern
1029    Pattern {
1030        /// its text
1031        src: String,
1032        /// compiled
1033        re: Regex,
1034    },
1035    /// an array
1036    Arr {
1037        /// the element type
1038        elem: RT,
1039        /// the lower size bound
1040        lo: Option<i64>,
1041        /// the upper size bound
1042        hi: Option<i64>,
1043    },
1044    /// a map
1045    Map {
1046        /// the key type
1047        key: RT,
1048        /// the value type
1049        val: RT,
1050    },
1051    /// a union; its arms are filled after the node exists when an alias names
1052    /// itself through one of them (§3.1)
1053    Union(RefCell<Vec<RT>>),
1054    /// an intersection not yet merged
1055    IsectN(Vec<RT>),
1056    /// a record
1057    Rec(RecType),
1058    /// a predicate refinement
1059    Pred {
1060        /// the base type
1061        base: RT,
1062        /// the predicates
1063        preds: Vec<Rc<Expr>>,
1064    },
1065    /// a reference type
1066    Ref(RT),
1067    /// a quantity of a dimension
1068    Quantity(String),
1069    /// a function type
1070    Func {
1071        /// the parameter types
1072        params: Vec<RT>,
1073        /// the return type
1074        ret: RT,
1075    },
1076    /// any value
1077    Any,
1078}
1079
1080/// a record type's shape
1081pub struct RecType {
1082    /// whether it is open
1083    pub open: Cell<bool>,
1084    /// Its members, shared after resolution. Recursive type construction uses
1085    /// copy-on-write so an earlier snapshot never changes underneath a reader.
1086    pub members: RefCell<Rc<Vec<Member>>>,
1087    /// its assertions and guarded groups
1088    pub asserts: RefCell<Vec<AssertItem>>,
1089    /// `context $parent: ref<T>` declarations (D30), checked at embedding sites
1090    pub ctx_decls: RefCell<Vec<(String, RT)>>,
1091    /// still being filled; extensions of it wait in `pending` (§3.14)
1092    pub filling: Cell<bool>,
1093    /// extensions not yet merged (recursive types)
1094    pub pending: RefCell<Vec<(RT, RT)>>,
1095}
1096/// An empty record type.
1097pub fn rec_type(open: bool) -> RecType {
1098    RecType {
1099        open: Cell::new(open),
1100        members: RefCell::new(Rc::new(vec![])),
1101        asserts: RefCell::new(vec![]),
1102        ctx_decls: RefCell::new(vec![]),
1103        filling: Cell::new(false),
1104        pending: RefCell::new(vec![]),
1105    }
1106}
1107
1108#[derive(Clone)]
1109/// a member of a resolved record type
1110pub struct Member {
1111    /// the kind
1112    pub kind: MKind,
1113    /// the name
1114    pub name: String,
1115    /// a hidden member (D34): computed, never part of the value
1116    pub hidden: bool,
1117    /// the type
1118    pub ty: Option<RT>,
1119    /// the types a conjunction contributed
1120    pub conj: Option<Vec<RT>>,
1121    /// the default
1122    pub dflt: Option<Rc<Expr>>,
1123    /// the derived expression
1124    pub expr: Option<Rc<Expr>>,
1125    /// the module environment
1126    pub menv: Option<Rc<Env>>,
1127}
1128
1129#[derive(Clone)]
1130/// an assertion or a guarded group of a record type
1131pub struct AssertItem {
1132    /// whether it is a `when` group
1133    pub when: bool,
1134    /// the name
1135    pub name: String,
1136    /// the condition
1137    pub cond: Rc<Expr>,
1138    /// the `else` tail
1139    pub tail: Option<Tail>,
1140    /// the members, for a group
1141    pub body: Vec<MemberAst>,
1142    /// the type declaring it, for the id
1143    pub origin: Option<String>,
1144    /// the module environment
1145    pub menv: Option<Rc<Env>>,
1146}
1147
1148/// The members of a record type; empty for any other type.
1149pub fn rec_members(t: &RT) -> Rc<Vec<Member>> {
1150    match &t.k {
1151        RTk::Rec(r) => r.members.borrow().clone(),
1152        _ => Rc::new(vec![]),
1153    }
1154}
1155/// Whether the type is a record.
1156pub fn is_rec(t: &RT) -> bool {
1157    matches!(t.k, RTk::Rec(_))
1158}
1159/// The leaf record types of a (possibly nested) union — unions are associative
1160/// (§3.12), so `A | (B | C)` yields the same leaves as `A | B | C`.
1161pub fn leaf_recs(t: &RT) -> Vec<RT> {
1162    match &t.k {
1163        RTk::Rec(_) => vec![t.clone()],
1164        RTk::Union(arms) => arms.borrow().iter().flat_map(leaf_recs).collect(),
1165        _ => vec![],
1166    }
1167}
1168
1169// ---------------- dimension vectors ----------------
1170/// a dimension as base dimensions with exponents
1171pub type DimVec = BTreeMap<String, i32>;
1172/// The dimension's key (`Length*Time^-1`).
1173pub fn key_of_vec(v: &DimVec) -> String {
1174    v.iter()
1175        .filter(|(_, e)| **e != 0)
1176        .map(|(n, e)| {
1177            if *e == 1 {
1178                n.clone()
1179            } else {
1180                format!("{n}^{e}")
1181            }
1182        })
1183        .collect::<Vec<_>>()
1184        .join("*")
1185}
1186/// A dimension from its key.
1187pub fn vec_of_key(key: &str) -> DimVec {
1188    let mut v = DimVec::new();
1189    if key.is_empty() {
1190        return v;
1191    }
1192    for p in key.split('*') {
1193        let (n, e) = match p.split_once('^') {
1194            Some((n, e)) => (n.to_string(), e.parse::<i32>().unwrap_or(1)),
1195            None => (p.to_string(), 1),
1196        };
1197        *v.entry(n).or_insert(0) += e;
1198    }
1199    v
1200}
1201/// Two dimensions multiplied (`sign` 1) or divided (`sign` -1).
1202pub fn vec_combine(a: &DimVec, b: &DimVec, sign: i32) -> DimVec {
1203    let mut out = a.clone();
1204    for (n, e) in b {
1205        *out.entry(n.clone()).or_insert(0) += sign * e;
1206    }
1207    out
1208}
1209
1210// ---------------- environment ----------------
1211/// an exported name: the environment declaring it
1212pub struct Export {
1213    /// the environment
1214    pub env: Rc<Env>,
1215    /// the name there
1216    pub name: String,
1217}
1218impl Clone for Export {
1219    fn clone(&self) -> Self {
1220        Export {
1221            env: self.env.clone(),
1222            name: self.name.clone(),
1223        }
1224    }
1225}
1226/// a constant's declaration and memoized value
1227pub struct ConstEntry {
1228    /// the expression
1229    pub expr: Rc<Expr>,
1230    /// the annotation
1231    pub ty: Option<TypeAst>,
1232    /// whether the value is computed
1233    pub state: Cell<bool>,
1234    /// the value
1235    pub value: RefCell<Value>,
1236}
1237/// a function's declaration
1238pub struct FuncEntry {
1239    /// the parameters
1240    pub params: Vec<Param>,
1241    /// the return type
1242    pub ret: Option<TypeAst>,
1243    /// the body
1244    pub body: Rc<Expr>,
1245}
1246/// a type's declaration
1247pub struct TypeEntry {
1248    /// the type
1249    pub ast: TypeAst,
1250    /// its `else` tail
1251    pub tail: Option<Tail>,
1252    /// the type parameters
1253    pub params: Vec<Param>,
1254}
1255/// a diagnostic template's declaration
1256pub struct DiagDecl {
1257    /// the parameters
1258    pub params: Vec<Param>,
1259    /// the severity
1260    pub severity: String,
1261    /// the template
1262    pub template: Vec<TPart>,
1263}
1264/// a unit's declaration
1265pub struct UnitDecl {
1266    /// its dimension
1267    pub dim: Option<String>,
1268    /// its factor
1269    pub factor: Option<Rc<Expr>>,
1270    /// its base unit
1271    pub base: Option<String>,
1272}
1273/// evaluates a constant by name (the engine's)
1274pub type ConstEval = Rc<dyn Fn(&str) -> R<Value>>;
1275/// evaluates an expression (the engine's)
1276pub type ExprEval = Rc<dyn Fn(&Rc<Expr>) -> R<Value>>;
1277
1278/// the environment of a module: its declarations, its imports, its roots and
1279/// diagnostics, the unit space
1280pub struct Env {
1281    /// the type declarations
1282    pub type_asts: RefCell<HashMap<String, Rc<TypeEntry>>>,
1283    /// resolved types, memoized
1284    pub type_memo: RefCell<HashMap<String, RT>>,
1285    /// the non-record aliases being resolved, to catch a reference back to one
1286    pub resolving: RefCell<HashSet<String>>,
1287    /// the placeholder an alias's inner reference took (§3.1)
1288    pub cyclic: RefCell<HashMap<String, RT>>,
1289    // names being spliced into a pattern right now, across nested
1290    // resolutions — a mutually recursive pair is a cycle, not a stack overflow
1291    /// the named types being resolved (recursion)
1292    pub pattern_visiting: RefCell<Vec<String>>,
1293    /// the constants
1294    pub consts: RefCell<HashMap<String, Rc<ConstEntry>>>,
1295    /// the functions
1296    pub funcs: RefCell<HashMap<String, Rc<FuncEntry>>>,
1297    /// names declared twice
1298    pub duplicates: RefCell<Vec<String>>,
1299    /// the outputs: name, type, expression
1300    pub outputs: RefCell<Vec<(String, TypeAst, Rc<Expr>)>>,
1301    /// the inputs: type, fallback
1302    pub inputs: RefCell<HashMap<String, (TypeAst, Option<Rc<Expr>>)>>,
1303    /// the diagnostic templates
1304    pub diags: RefCell<HashMap<String, Rc<DiagDecl>>>,
1305    /// every instance bound
1306    pub registry: RefCell<Rc<RefCell<Vec<Rc<RefCell<RecInst>>>>>>,
1307    /// the roots' values, by name
1308    pub roots: RefCell<Rc<RefCell<Vec<(String, Value)>>>>,
1309    /// the diagnostics raised
1310    pub diagnostics: RefCell<Rc<RefCell<Vec<Diag>>>>,
1311    /// >0: a frozen round is being read (`Engine::muted`) — its reports are not this evaluation's
1312    pub muted: Cell<u32>,
1313    /// the constant evaluator, once an engine is wired in
1314    pub const_eval: RefCell<Option<ConstEval>>,
1315    /// the expression evaluator, once an engine is wired in
1316    pub expr_eval: RefCell<Option<ExprEval>>,
1317    /// the imported names
1318    pub imports: RefCell<HashMap<String, Export>>,
1319    /// the namespace imports
1320    pub namespaces: RefCell<HashMap<String, (Rc<Env>, Rc<RefCell<HashMap<String, Export>>>)>>,
1321    const_diag_seen: RefCell<HashSet<String>>,
1322    /// the dimension declarations
1323    pub dim_decls: RefCell<HashMap<String, Option<Vec<(String, i32)>>>>,
1324    /// dimensions resolved, memoized
1325    pub dim_memo: RefCell<HashMap<String, DimVec>>,
1326    /// the unit declarations
1327    pub unit_decls: RefCell<HashMap<String, UnitDecl>>,
1328    /// units resolved to (dimension, factor), memoized
1329    pub unit_memo: RefCell<HashMap<String, (String, f64)>>,
1330    /// the base unit of each dimension
1331    pub base_unit_of: RefCell<HashMap<String, String>>,
1332    /// the unit space's diagnostics (E4073 and friends)
1333    pub space_diags: RefCell<Vec<Diag>>,
1334    /// declaration order (HashMaps do not keep it; diagnostics follow it)
1335    pub type_order: RefCell<Vec<String>>,
1336    /// the units in declaration order
1337    pub unit_order: RefCell<Vec<String>>,
1338    /// installed by the checker: constant-evaluation errors go here instead of the report
1339    pub const_diag_sink: RefCell<Option<Rc<RefCell<Vec<Diag>>>>>,
1340    /// installed by the engine: the evaluation step a report is attributed to
1341    pub tagger: RefCell<Option<Rc<dyn Fn() -> Option<String>>>>,
1342}
1343
1344/// §6.7: evaluation- and validation-time diagnostics sort by (path, id), path in canonical order; stable
1345pub fn sort_diags(diags: Vec<Diag>) -> Vec<Diag> {
1346    let segs_of = |p: &str| -> SegPath {
1347        if p.is_empty() {
1348            return vec![];
1349        }
1350        parse_path(p, "").unwrap_or_else(|_| vec![Seg::Name(Rc::from(p.to_string()))])
1351    };
1352    let mut keyed: Vec<(usize, SegPath, Diag)> = diags
1353        .into_iter()
1354        .enumerate()
1355        .map(|(i, d)| (i, segs_of(&d.path), d))
1356        .collect();
1357    keyed.sort_by(|a, b| {
1358        cmp_path(&a.1, &b.1)
1359            .then_with(|| {
1360                a.2.id
1361                    .as_deref()
1362                    .unwrap_or("")
1363                    .cmp(b.2.id.as_deref().unwrap_or(""))
1364            })
1365            .then_with(|| a.0.cmp(&b.0))
1366    });
1367    keyed.into_iter().map(|(_, _, d)| d).collect()
1368}
1369
1370const SI_PREFIXES: [(&str, f64); 20] = [
1371    ("y", 1e-24),
1372    ("z", 1e-21),
1373    ("a", 1e-18),
1374    ("f", 1e-15),
1375    ("p", 1e-12),
1376    ("n", 1e-9),
1377    ("u", 1e-6),
1378    ("m", 1e-3),
1379    ("c", 1e-2),
1380    ("d", 1e-1),
1381    ("da", 1e1),
1382    ("h", 1e2),
1383    ("k", 1e3),
1384    ("M", 1e6),
1385    ("G", 1e9),
1386    ("T", 1e12),
1387    ("P", 1e15),
1388    ("E", 1e18),
1389    ("Z", 1e21),
1390    ("Y", 1e24),
1391];
1392
1393impl Env {
1394    /// An empty environment.
1395    pub fn new() -> Rc<Env> {
1396        let env = Env {
1397            type_asts: RefCell::new(HashMap::new()),
1398            type_memo: RefCell::new(HashMap::new()),
1399            resolving: RefCell::new(HashSet::new()),
1400            cyclic: RefCell::new(HashMap::new()),
1401            pattern_visiting: RefCell::new(vec![]),
1402            consts: RefCell::new(HashMap::new()),
1403            funcs: RefCell::new(HashMap::new()),
1404            duplicates: RefCell::new(vec![]),
1405            outputs: RefCell::new(vec![]),
1406            inputs: RefCell::new(HashMap::new()),
1407            diags: RefCell::new(HashMap::new()),
1408            registry: RefCell::new(Rc::new(RefCell::new(vec![]))),
1409            roots: RefCell::new(Rc::new(RefCell::new(vec![]))),
1410            diagnostics: RefCell::new(Rc::new(RefCell::new(vec![]))),
1411            muted: Cell::new(0),
1412            const_eval: RefCell::new(None),
1413            expr_eval: RefCell::new(None),
1414            imports: RefCell::new(HashMap::new()),
1415            namespaces: RefCell::new(HashMap::new()),
1416            const_diag_seen: RefCell::new(HashSet::new()),
1417            dim_decls: RefCell::new(HashMap::new()),
1418            dim_memo: RefCell::new(HashMap::new()),
1419            unit_decls: RefCell::new(HashMap::new()),
1420            unit_memo: RefCell::new(HashMap::new()),
1421            base_unit_of: RefCell::new(HashMap::new()),
1422            space_diags: RefCell::new(vec![]),
1423            type_order: RefCell::new(vec![]),
1424            unit_order: RefCell::new(vec![]),
1425            const_diag_sink: RefCell::new(None),
1426            tagger: RefCell::new(None),
1427        };
1428        env.seed_units();
1429        let env = Rc::new(env);
1430        lifetime::track_env(&env);
1431        env
1432    }
1433
1434    // std.units — the SI catalog generated from the §13.10 prefix rule (D15)
1435    fn seed_units(&self) {
1436        let unit = |sym: &str, dim: Option<&str>, factor: f64, base: &str| {
1437            let mut m = self.unit_decls.borrow_mut();
1438            if m.contains_key(sym) {
1439                return;
1440            }
1441            self.unit_order.borrow_mut().push(sym.to_string());
1442            m.insert(
1443                sym.to_string(),
1444                match dim {
1445                    Some(d) => UnitDecl {
1446                        dim: Some(d.to_string()),
1447                        factor: None,
1448                        base: None,
1449                    },
1450                    None => UnitDecl {
1451                        dim: None,
1452                        factor: Some(Rc::new(Expr::Lit(Value::Float(factor)))),
1453                        base: Some(base.to_string()),
1454                    },
1455                },
1456            );
1457        };
1458        let bases = [
1459            ("Time", "s"),
1460            ("Length", "m"),
1461            ("Mass", "kg"),
1462            ("Current", "A"),
1463            ("Temperature", "K"),
1464            ("Amount", "mol"),
1465            ("LuminousIntensity", "cd"),
1466        ];
1467        for (d, _) in bases {
1468            self.dim_decls.borrow_mut().insert(d.to_string(), None);
1469        }
1470        let t = |n: &str, e: i32| (n.to_string(), e);
1471        let derived: Vec<(&str, Option<Vec<(String, i32)>>, &str)> = vec![
1472            ("Frequency", Some(vec![t("Time", -1)]), "Hz"),
1473            (
1474                "Force",
1475                Some(vec![t("Mass", 1), t("Length", 1), t("Time", -2)]),
1476                "N",
1477            ),
1478            (
1479                "Pressure",
1480                Some(vec![t("Mass", 1), t("Length", -1), t("Time", -2)]),
1481                "Pa",
1482            ),
1483            (
1484                "Energy",
1485                Some(vec![t("Mass", 1), t("Length", 2), t("Time", -2)]),
1486                "J",
1487            ),
1488            (
1489                "Power",
1490                Some(vec![t("Mass", 1), t("Length", 2), t("Time", -3)]),
1491                "W",
1492            ),
1493            ("Charge", Some(vec![t("Current", 1), t("Time", 1)]), "C"),
1494            (
1495                "Voltage",
1496                Some(vec![
1497                    t("Mass", 1),
1498                    t("Length", 2),
1499                    t("Time", -3),
1500                    t("Current", -1),
1501                ]),
1502                "V",
1503            ),
1504            (
1505                "Resistance",
1506                Some(vec![
1507                    t("Mass", 1),
1508                    t("Length", 2),
1509                    t("Time", -3),
1510                    t("Current", -2),
1511                ]),
1512                "Ohm",
1513            ),
1514            (
1515                "Capacitance",
1516                Some(vec![
1517                    t("Mass", -1),
1518                    t("Length", -2),
1519                    t("Time", 4),
1520                    t("Current", 2),
1521                ]),
1522                "F",
1523            ),
1524            ("DataSize", None, "bit"),
1525        ];
1526        for (d, terms, _) in &derived {
1527            self.dim_decls
1528                .borrow_mut()
1529                .insert(d.to_string(), terms.clone());
1530        }
1531        for (d, s) in bases {
1532            unit(s, Some(d), 1.0, "");
1533        }
1534        for (d, _, s) in &derived {
1535            unit(s, Some(d), 1.0, "");
1536        }
1537        unit("B", None, 8.0, "bit");
1538        unit("g", None, 1e-3, "kg");
1539        let mut prefixable: Vec<&str> = bases
1540            .iter()
1541            .map(|(_, s)| *s)
1542            .filter(|s| *s != "kg")
1543            .collect();
1544        prefixable.extend(derived.iter().map(|(_, _, s)| *s).filter(|s| *s != "bit"));
1545        prefixable.push("g");
1546        for u0 in prefixable {
1547            for (p, f) in SI_PREFIXES {
1548                unit(&format!("{p}{u0}"), None, f, u0);
1549            }
1550        }
1551        for u0 in ["bit", "B"] {
1552            for (p, f) in [
1553                ("Ki", 1024f64),
1554                ("Mi", 1024f64.powi(2)),
1555                ("Gi", 1024f64.powi(3)),
1556                ("Ti", 1024f64.powi(4)),
1557                ("Pi", 1024f64.powi(5)),
1558                ("Ei", 1024f64.powi(6)),
1559            ] {
1560                unit(&format!("{p}{u0}"), None, f, u0);
1561            }
1562            for (p, f) in SI_PREFIXES {
1563                if ["k", "M", "G", "T", "P", "E"].contains(&p) {
1564                    unit(&format!("{p}{u0}"), None, f, u0);
1565                }
1566            }
1567        }
1568    }
1569
1570    /// Load declarations into the environment (§5, §8).
1571    pub fn load(&self, decls: &[Decl]) {
1572        let mut seen: HashSet<String> = HashSet::new();
1573        for d in decls {
1574            if let Some(n) = d.name() {
1575                if !matches!(d.body, DeclBody::Unit { .. } | DeclBody::Dimension { .. })
1576                    && !seen.insert(n.to_string())
1577                {
1578                    self.duplicates.borrow_mut().push(n.to_string());
1579                }
1580            }
1581            match &d.body {
1582                DeclBody::Dimension { name, terms } => {
1583                    if self.dim_decls.borrow().contains_key(name) {
1584                        self.space_diags.borrow_mut().push(Diag::error(
1585                            format!("dimension {name} redeclared"),
1586                            String::new(),
1587                            Some("E3001"),
1588                        ));
1589                    } else {
1590                        self.dim_decls
1591                            .borrow_mut()
1592                            .insert(name.clone(), terms.clone());
1593                    }
1594                }
1595                DeclBody::Unit {
1596                    name,
1597                    dim,
1598                    factor,
1599                    base,
1600                } => {
1601                    if self.unit_decls.borrow().contains_key(name) {
1602                        self.space_diags.borrow_mut().push(Diag::error(
1603                            format!("unit {name} redeclared"),
1604                            String::new(),
1605                            Some("E4073"),
1606                        ));
1607                    } else {
1608                        self.unit_order.borrow_mut().push(name.clone());
1609                        self.unit_decls.borrow_mut().insert(
1610                            name.clone(),
1611                            UnitDecl {
1612                                dim: dim.clone(),
1613                                factor: factor.clone(),
1614                                base: base.clone(),
1615                            },
1616                        );
1617                    }
1618                }
1619                DeclBody::Type {
1620                    name,
1621                    params,
1622                    ty,
1623                    tail,
1624                } => {
1625                    if !self.type_asts.borrow().contains_key(name) {
1626                        self.type_order.borrow_mut().push(name.clone());
1627                    }
1628                    self.type_asts.borrow_mut().insert(
1629                        name.clone(),
1630                        Rc::new(TypeEntry {
1631                            ast: ty.clone(),
1632                            tail: tail.clone(),
1633                            params: params.clone(),
1634                        }),
1635                    );
1636                }
1637                DeclBody::Const { name, ty, expr } => {
1638                    self.consts.borrow_mut().insert(
1639                        name.clone(),
1640                        Rc::new(ConstEntry {
1641                            expr: expr.clone(),
1642                            ty: ty.clone(),
1643                            state: Cell::new(false),
1644                            value: RefCell::new(Value::Null),
1645                        }),
1646                    );
1647                }
1648                DeclBody::Func {
1649                    name,
1650                    params,
1651                    ret,
1652                    body,
1653                } => {
1654                    self.funcs.borrow_mut().insert(
1655                        name.clone(),
1656                        Rc::new(FuncEntry {
1657                            params: params.clone(),
1658                            ret: ret.clone(),
1659                            body: body.clone(),
1660                        }),
1661                    );
1662                }
1663                DeclBody::Output { name, ty, expr } => {
1664                    self.outputs
1665                        .borrow_mut()
1666                        .push((name.clone(), ty.clone(), expr.clone()))
1667                }
1668                DeclBody::Input { name, ty, fallback } => {
1669                    self.inputs
1670                        .borrow_mut()
1671                        .insert(name.clone(), (ty.clone(), fallback.clone()));
1672                }
1673                DeclBody::Diagnostic {
1674                    name,
1675                    params,
1676                    severity,
1677                    template,
1678                } => {
1679                    self.diags.borrow_mut().insert(
1680                        name.clone(),
1681                        Rc::new(DiagDecl {
1682                            params: params.clone(),
1683                            severity: severity.clone(),
1684                            template: template.clone(),
1685                        }),
1686                    );
1687                }
1688                _ => {}
1689            }
1690        }
1691    }
1692
1693    /// Raise a diagnostic.
1694    pub fn report(&self, d: Diag) {
1695        if self.muted.get() > 0 {
1696            return;
1697        }
1698        let by = self.tagger.borrow().as_ref().and_then(|t| t());
1699        let mut d = d;
1700        if by.is_some() {
1701            d.by = by;
1702        }
1703        self.diagnostics.borrow().borrow_mut().push(d);
1704    }
1705    /// replace every diagnostic (the run entry points sort them, §6.7)
1706    pub fn diag_set(&self, diags: Vec<Diag>) {
1707        let rc = self.diagnostics.borrow().clone();
1708        *rc.borrow_mut() = diags;
1709    }
1710    /// Forget a root.
1711    pub fn remove_root(&self, name: &str) {
1712        let rc = self.roots.borrow().clone();
1713        rc.borrow_mut().retain(|(n, _)| n != name);
1714    }
1715    /// The roots' names, in order.
1716    pub fn root_names(&self) -> Vec<String> {
1717        self.roots
1718            .borrow()
1719            .borrow()
1720            .iter()
1721            .map(|(n, _)| n.clone())
1722            .collect()
1723    }
1724    /// Keep the instances a predicate accepts.
1725    pub fn registry_retain(&self, mut pred: impl FnMut(&Rc<RefCell<RecInst>>) -> bool) {
1726        let rc = self.registry.borrow().clone();
1727        rc.borrow_mut().retain(|i| pred(i));
1728    }
1729    /// Count registered instances without copying their shared handles.
1730    pub(crate) fn registry_len(&self) -> usize {
1731        self.registry.borrow().borrow().len()
1732    }
1733    /// Preserve the existing prefix and retain only the tail a predicate accepts.
1734    pub(crate) fn registry_retain_from(
1735        &self,
1736        start: usize,
1737        mut pred: impl FnMut(&Rc<RefCell<RecInst>>) -> bool,
1738    ) {
1739        let rc = self.registry.borrow().clone();
1740        let mut registry = rc.borrow_mut();
1741        let start = start.min(registry.len());
1742        for _ in registry.extract_if(start.., |inst| !pred(inst)) {}
1743    }
1744    /// The diagnostics raised so far.
1745    pub fn diagnostics_vec(&self) -> Vec<Diag> {
1746        self.diagnostics.borrow().borrow().clone()
1747    }
1748    /// How many diagnostics were raised.
1749    pub fn diag_len(&self) -> usize {
1750        self.diagnostics.borrow().borrow().len()
1751    }
1752    /// Forget the diagnostics after the first `n`.
1753    pub fn diag_truncate(&self, n: usize) {
1754        self.diagnostics.borrow().borrow_mut().truncate(n);
1755    }
1756    /// A root's value.
1757    pub fn root(&self, name: &str) -> Option<Value> {
1758        self.roots
1759            .borrow()
1760            .borrow()
1761            .iter()
1762            .find(|(n, _)| n == name)
1763            .map(|(_, v)| v.clone())
1764    }
1765    /// Set a root's value.
1766    pub fn set_root(&self, name: &str, v: Value) {
1767        let rc = self.roots.borrow().clone();
1768        let mut roots = rc.borrow_mut();
1769        if let Some(e) = roots.iter_mut().find(|(n, _)| n == name) {
1770            e.1 = v;
1771        } else {
1772            roots.push((name.to_string(), v));
1773        }
1774    }
1775    /// The roots' values, in order.
1776    pub fn root_values(&self) -> Vec<Value> {
1777        self.roots
1778            .borrow()
1779            .borrow()
1780            .iter()
1781            .map(|(_, v)| v.clone())
1782            .collect()
1783    }
1784    /// Register an instance.
1785    pub fn registry_push(&self, inst: Rc<RefCell<RecInst>>) {
1786        self.registry.borrow().borrow_mut().push(inst);
1787    }
1788    /// Forget every instance (a round starts over).
1789    pub fn registry_clear(&self) {
1790        self.registry.borrow().borrow_mut().clear();
1791    }
1792    /// Forget every root (a round starts over).
1793    pub fn roots_clear(&self) {
1794        self.roots.borrow().borrow_mut().clear();
1795    }
1796    /// The roots with their names, in order.
1797    pub fn roots_vec(&self) -> Vec<(String, Value)> {
1798        self.roots.borrow().borrow().clone()
1799    }
1800    /// The instances registered so far.
1801    pub fn registry_snapshot(&self) -> Vec<Rc<RefCell<RecInst>>> {
1802        self.registry.borrow().borrow().clone()
1803    }
1804
1805    // §4.13: a named endpoint in a constant position evaluates at elaboration time
1806    /// A numeric constant's value where a type expects a number (a size, a bound).
1807    pub fn const_num(&self, v: &Value) -> Value {
1808        let name = match v {
1809            Value::Str(s) => s.to_string(),
1810            other => return other.clone(),
1811        };
1812        let ce = self.const_eval.borrow().clone();
1813        let Some(ce) = ce else { return v.clone() };
1814        if !self.consts.borrow().contains_key(&name) {
1815            return v.clone();
1816        }
1817        let diag = |code: &str, message: String| {
1818            let key = format!("{name}{code}");
1819            if self.const_diag_seen.borrow().contains(&key) {
1820                return;
1821            }
1822            self.const_diag_seen.borrow_mut().insert(key);
1823            let d = Diag::error(message, String::new(), Some(code));
1824            match &*self.const_diag_sink.borrow() {
1825                Some(sink) => sink.borrow_mut().push(d),
1826                None => self.report(d),
1827            }
1828        };
1829        match ce(&name) {
1830            Ok(Value::Int(i)) => Value::Int(i),
1831            Ok(Value::Float(f)) => Value::Float(f),
1832            Ok(Value::Undef) | Ok(Value::Null) => v.clone(),
1833            Ok(_) => {
1834                diag(
1835                    "E4021",
1836                    format!("constant {name} is not numeric in a constant position"),
1837                );
1838                v.clone()
1839            }
1840            Err(Fail::Eval(e)) => {
1841                let code = if e.msg.contains("zero") {
1842                    "E5001"
1843                } else if e.msg.contains("NaN") || e.msg.contains("Infinity") {
1844                    "E5002"
1845                } else {
1846                    "E5001"
1847                };
1848                diag(code, format!("evaluating constant {name}: {}", e.msg));
1849                v.clone()
1850            }
1851            Err(_) => v.clone(),
1852        }
1853    }
1854
1855    // ---- unit / dimension name spaces ----
1856    /// Resolve a dimension by name to its base dimensions.
1857    pub fn resolve_dim(&self, name: &str, visiting: &mut Vec<String>) -> Result<DimVec, String> {
1858        if let Some(v) = self.dim_memo.borrow().get(name) {
1859            return Ok(v.clone());
1860        }
1861        if visiting.iter().any(|v| v == name) {
1862            return Err(format!("circular dimension {name}"));
1863        }
1864        let decl = self
1865            .dim_decls
1866            .borrow()
1867            .get(name)
1868            .cloned()
1869            .ok_or_else(|| format!("unknown dimension {name}"))?;
1870        let mut vec = DimVec::new();
1871        match decl {
1872            None => {
1873                vec.insert(name.to_string(), 1);
1874            }
1875            Some(terms) => {
1876                visiting.push(name.to_string());
1877                for (tn, te) in terms {
1878                    let sub = self.resolve_dim(&tn, visiting)?;
1879                    for (n, e) in sub {
1880                        *vec.entry(n).or_insert(0) += e * te;
1881                    }
1882                }
1883                visiting.pop();
1884            }
1885        }
1886        self.dim_memo
1887            .borrow_mut()
1888            .insert(name.to_string(), vec.clone());
1889        Ok(vec)
1890    }
1891    /// A unit's dimension key and factor against the base unit.
1892    pub fn unit_info(&self, sym: &str) -> Result<(String, f64), String> {
1893        self.unit_info_v(sym, &mut vec![])
1894    }
1895    /// §3.16 unit/dimension-space findings for the checker: the load-time
1896    /// redeclarations plus unresolvable units and duplicate base units
1897    pub fn finalize_unit_space(&self) -> Vec<Diag> {
1898        let mut out = self.space_diags.borrow().clone();
1899        let mut base_seen: HashMap<String, String> = HashMap::new();
1900        let syms = self.unit_order.borrow().clone();
1901        for sym in syms {
1902            let has_dim = self
1903                .unit_decls
1904                .borrow()
1905                .get(&sym)
1906                .map(|u| u.dim.is_some())
1907                .unwrap_or(false);
1908            match self.unit_info(&sym) {
1909                Ok((key, _)) => {
1910                    if has_dim {
1911                        if let Some(prev) = base_seen.get(&key) {
1912                            out.push(Diag::error(
1913                                format!(
1914                                    "second base unit {sym} for dimension {key} (base is {prev})"
1915                                ),
1916                                String::new(),
1917                                Some("E4073"),
1918                            ));
1919                        } else {
1920                            base_seen.insert(key, sym.clone());
1921                        }
1922                    }
1923                }
1924                Err(msg) => {
1925                    let code = if msg.contains("unknown dimension")
1926                        || msg.contains("circular dimension")
1927                    {
1928                        "E3003"
1929                    } else {
1930                        "E4073"
1931                    };
1932                    out.push(Diag::error(msg, String::new(), Some(code)));
1933                }
1934            }
1935        }
1936        out
1937    }
1938    fn unit_info_v(&self, sym: &str, visiting: &mut Vec<String>) -> Result<(String, f64), String> {
1939        if let Some(v) = self.unit_memo.borrow().get(sym) {
1940            return Ok(v.clone());
1941        }
1942        if visiting.iter().any(|v| v == sym) {
1943            return Err(format!("circular unit {sym}"));
1944        }
1945        let (dim, factor, base) = {
1946            let m = self.unit_decls.borrow();
1947            let u = m.get(sym).ok_or_else(|| format!("unknown unit {sym}"))?;
1948            (u.dim.clone(), u.factor.clone(), u.base.clone())
1949        };
1950        let info = if let Some(d) = dim {
1951            let key = key_of_vec(&self.resolve_dim(&d, &mut vec![])?);
1952            self.base_unit_of
1953                .borrow_mut()
1954                .entry(key.clone())
1955                .or_insert_with(|| sym.to_string());
1956            (key, 1.0)
1957        } else {
1958            visiting.push(sym.to_string());
1959            let b = self.unit_info_v(base.as_deref().unwrap_or(""), visiting)?;
1960            visiting.pop();
1961            let mut f: Option<f64> = match factor.as_deref() {
1962                Some(Expr::Lit(Value::Float(x))) => Some(*x),
1963                Some(Expr::Lit(Value::Int(i))) => i.to_f64(),
1964                _ => None,
1965            };
1966            if f.is_none() {
1967                if let (Some(fx), Some(ee)) = (factor.clone(), self.expr_eval.borrow().clone()) {
1968                    f = match ee(&fx) {
1969                        Ok(Value::Float(x)) => Some(x),
1970                        Ok(Value::Int(i)) => i.to_f64(),
1971                        _ => None,
1972                    };
1973                }
1974            }
1975            let f = f.ok_or_else(|| format!("unit {sym}: factor is not a numeric constant"))?;
1976            (b.0, f * b.1)
1977        };
1978        self.unit_memo
1979            .borrow_mut()
1980            .insert(sym.to_string(), info.clone());
1981        Ok(info)
1982    }
1983
1984    // ---- type resolution ----
1985    /// Resolve a type annotation to a resolved type (§3), memoized under `name` for a named type.
1986    pub fn resolve(self: &Rc<Env>, ast: &TypeAst, name: Option<&str>) -> Result<RT, String> {
1987        Ok(match ast {
1988            TypeAst::Prim { name: n, .. } => ty(RTk::Prim(n.clone())),
1989            TypeAst::Lit { v, .. } => ty(RTk::Lit(v.clone())),
1990            TypeAst::Range { lo, hi, excl, .. } => {
1991                let lo = self.const_num(lo);
1992                let hi = self.const_num(hi);
1993                let is_f = matches!(lo, Value::Float(_)) || matches!(hi, Value::Float(_));
1994                ty(RTk::Range {
1995                    lo,
1996                    hi,
1997                    excl: *excl,
1998                    base: if is_f { "float".into() } else { "int".into() },
1999                })
2000            }
2001            TypeAst::Pattern { re: src, .. } => {
2002                let expanded = self.expand_pattern(src)?;
2003                if let Some(bad) = pattern_error(&expanded) {
2004                    return Err(format!("malformed pattern /{src}/: {bad}"));
2005                }
2006                let re = compile_pattern(&expanded)
2007                    .map_err(|e| format!("malformed pattern /{src}/: {e}"))?;
2008                ty(RTk::Pattern { src: expanded, re })
2009            }
2010            TypeAst::Map { key, val, .. } => ty(RTk::Map {
2011                key: self.resolve(key, None)?,
2012                val: self.resolve(val, None)?,
2013            }),
2014            TypeAst::Array {
2015                elem, lo, hi, excl, ..
2016            } => {
2017                let lo = lo.as_ref().map(|v| self.const_num(v));
2018                let hi0 = hi.as_ref().map(|v| self.const_num(v));
2019                let to_i = |v: &Value| match v {
2020                    Value::Int(i) => i.to_i64(),
2021                    Value::Float(f) => Some(*f as i64),
2022                    _ => None,
2023                };
2024                let lo_i = lo.as_ref().and_then(&to_i);
2025                let hi_i = hi0
2026                    .as_ref()
2027                    .and_then(to_i)
2028                    .map(|h| if *excl { h - 1 } else { h });
2029                ty(RTk::Arr {
2030                    elem: self.resolve(elem, None)?,
2031                    lo: lo_i,
2032                    hi: hi_i,
2033                })
2034            }
2035            TypeAst::Union { arms, .. } => ty(RTk::Union(RefCell::new(
2036                arms.iter()
2037                    .map(|a| self.resolve(a, None))
2038                    .collect::<Result<_, _>>()?,
2039            ))),
2040            TypeAst::Isect { arms, .. } => {
2041                let arms: Vec<RT> = arms
2042                    .iter()
2043                    .map(|a| self.resolve(a, None))
2044                    .collect::<Result<_, _>>()?;
2045                if arms.iter().all(is_rec) {
2046                    self.merge_isect(&arms, name)
2047                } else {
2048                    ty(RTk::IsectN(arms))
2049                }
2050            }
2051            TypeAst::Record { members, open, .. } => {
2052                let rt = ty(RTk::Rec(rec_type(*open)));
2053                *rt.name.borrow_mut() = name.map(|s| s.to_string());
2054                self.fill_record(&rt, members)?;
2055                rt
2056            }
2057            TypeAst::Func { params, ret, .. } => ty(RTk::Func {
2058                params: params
2059                    .iter()
2060                    .map(|p| self.resolve(p, None))
2061                    .collect::<Result<_, _>>()?,
2062                ret: self.resolve(ret, None)?,
2063            }),
2064            TypeAst::Named {
2065                name: n,
2066                args,
2067                preds,
2068                ext,
2069                ..
2070            } => {
2071                if let Some(preds) = preds {
2072                    if !preds.is_empty() {
2073                        let base = self.resolve(
2074                            &TypeAst::Named {
2075                                name: n.clone(),
2076                                args: args.clone(),
2077                                preds: None,
2078                                ext: ext.clone(),
2079                                loc: None,
2080                            },
2081                            name,
2082                        )?;
2083                        return Ok(ty(RTk::Pred {
2084                            base,
2085                            preds: preds.clone(),
2086                        }));
2087                    }
2088                }
2089                if n == "quantity" {
2090                    let dn = match args.first() {
2091                        Some(TypeAst::Named { name, .. }) | Some(TypeAst::Prim { name, .. }) => {
2092                            name.clone()
2093                        }
2094                        _ => return Err("quantity needs a dimension".into()),
2095                    };
2096                    return Ok(ty(RTk::Quantity(key_of_vec(
2097                        &self.resolve_dim(&dn, &mut vec![])?,
2098                    ))));
2099                }
2100                if n == "map" && args.len() == 2 {
2101                    return Ok(ty(RTk::Map {
2102                        key: self.resolve(&args[0], None)?,
2103                        val: self.resolve(&args[1], None)?,
2104                    }));
2105                }
2106                if n == "ref" {
2107                    return Ok(ty(RTk::Ref(self.resolve(&args[0], None)?)));
2108                }
2109                if ["int", "float", "bool", "string"].contains(&n.as_str())
2110                    && args.is_empty()
2111                    && ext.is_none()
2112                {
2113                    return Ok(ty(RTk::Prim(n.clone())));
2114                }
2115                let decl = self.type_asts.borrow().get(n).cloned();
2116                let Some(decl) = decl else {
2117                    let im = self.imports.borrow().get(n).cloned();
2118                    if let Some(im) = im {
2119                        return im.env.resolve(
2120                            &TypeAst::Named {
2121                                name: im.name.clone(),
2122                                args: args.clone(),
2123                                preds: None,
2124                                ext: ext.clone(),
2125                                loc: None,
2126                            },
2127                            name,
2128                        );
2129                    }
2130                    if let Some((ns, rest)) = n.split_once('.') {
2131                        let ex = self
2132                            .namespaces
2133                            .borrow()
2134                            .get(ns)
2135                            .and_then(|(_, exports)| exports.borrow().get(rest).cloned());
2136                        if let Some(ex) = ex {
2137                            return ex.env.resolve(
2138                                &TypeAst::Named {
2139                                    name: ex.name.clone(),
2140                                    args: args.clone(),
2141                                    preds: None,
2142                                    ext: ext.clone(),
2143                                    loc: None,
2144                                },
2145                                name,
2146                            );
2147                        }
2148                    }
2149                    return Err(format!("unknown type {n}"));
2150                };
2151                let memo = self.type_memo.borrow().get(n).cloned();
2152                let base = if !decl.params.is_empty() {
2153                    self.instantiate(n, args, &decl)?
2154                } else if let Some(b) = memo {
2155                    b
2156                } else {
2157                    match &decl.ast {
2158                        TypeAst::Record { members, open, .. } => {
2159                            let rt = ty(RTk::Rec(rec_type(*open)));
2160                            *rt.name.borrow_mut() = Some(n.clone());
2161                            *rt.tail.borrow_mut() = decl.tail.clone();
2162                            self.type_memo.borrow_mut().insert(n.clone(), rt.clone());
2163                            // a member that fails to resolve must not leave a half-filled
2164                            // record memoized (later lookups would miss its later members)
2165                            if let Err(e) = self.fill_record(&rt, members) {
2166                                self.type_memo.borrow_mut().remove(n);
2167                                return Err(e);
2168                            }
2169                            rt
2170                        }
2171                        TypeAst::Named {
2172                            name: pn,
2173                            args: pa,
2174                            preds: pp,
2175                            ext: Some(body),
2176                            ..
2177                        } => {
2178                            // an extension declaration (§3.14) is memoized before its parent
2179                            // resolves: in a recursive family — `type Base = { kids: { [string]:
2180                            // Kid } }`, `type Kid = Base { … }` — the parent's body names this
2181                            // type, and every reference must share the one final record rather
2182                            // than a snapshot of the parent's members taken mid-fill
2183                            let rt = ty(RTk::Rec(rec_type(false)));
2184                            if let RTk::Rec(r) = &rt.k {
2185                                r.filling.set(true);
2186                            }
2187                            *rt.name.borrow_mut() = Some(n.clone());
2188                            *rt.tail.borrow_mut() = decl.tail.clone();
2189                            self.type_memo.borrow_mut().insert(n.clone(), rt.clone());
2190                            let parent_ast = TypeAst::Named {
2191                                name: pn.clone(),
2192                                args: pa.clone(),
2193                                preds: pp.clone(),
2194                                ext: None,
2195                                loc: None,
2196                            };
2197                            let filled = self.resolve(&parent_ast, None).and_then(|parent| {
2198                                let extr = self.resolve(body, None)?;
2199                                self.extend_into(&rt, &parent, &extr);
2200                                Ok(())
2201                            });
2202                            if let Err(e) = filled {
2203                                self.type_memo.borrow_mut().remove(n);
2204                                return Err(e);
2205                            }
2206                            rt
2207                        }
2208                        other => {
2209                            // an alias that names itself through an array, a map, or a
2210                            // union (`type Json = … | Json[] | { [string]: Json }`, §3.1)
2211                            // is entered once: the inner reference gets a placeholder
2212                            // union that the outer resolution fills — so every reference
2213                            // shares the one node; a pattern's interpolation cycle is the
2214                            // pattern code's own diagnostic
2215                            let guard = !matches!(other, TypeAst::Pattern { .. });
2216                            if guard && self.resolving.borrow().contains(n) {
2217                                let ph = self.cyclic.borrow().get(n).cloned();
2218                                return Ok(match ph {
2219                                    Some(ph) => ph,
2220                                    None => {
2221                                        let ph = ty(RTk::Union(RefCell::new(vec![])));
2222                                        *ph.name.borrow_mut() = Some(n.clone());
2223                                        *ph.tail.borrow_mut() = decl.tail.clone();
2224                                        self.cyclic.borrow_mut().insert(n.clone(), ph.clone());
2225                                        ph
2226                                    }
2227                                });
2228                            }
2229                            if guard {
2230                                self.resolving.borrow_mut().insert(n.clone());
2231                            }
2232                            let resolved = self.resolve(other, Some(n));
2233                            if guard {
2234                                self.resolving.borrow_mut().remove(n);
2235                            }
2236                            let mut rt = resolved?;
2237                            let ph = self.cyclic.borrow_mut().remove(n);
2238                            if let Some(ph) = ph {
2239                                let arms: Vec<RT> = match &rt.k {
2240                                    RTk::Union(a) => a.borrow().clone(),
2241                                    _ => vec![rt.clone()],
2242                                };
2243                                if arms.iter().any(|a| Rc::ptr_eq(a, &ph)) {
2244                                    return Err(format!(
2245                                        "recursive type alias {n} names itself as an arm"
2246                                    ));
2247                                }
2248                                if let RTk::Union(pa) = &ph.k {
2249                                    *pa.borrow_mut() = arms;
2250                                }
2251                                rt = ph;
2252                            }
2253                            if matches!(rt.k, RTk::Rec(_) | RTk::Union(_)) {
2254                                *rt.name.borrow_mut() = Some(n.clone());
2255                            }
2256                            if rt.tail.borrow().is_none() {
2257                                *rt.tail.borrow_mut() = decl.tail.clone();
2258                            }
2259                            self.type_memo.borrow_mut().insert(n.clone(), rt.clone());
2260                            rt
2261                        }
2262                    }
2263                };
2264                if let Some(ext) = ext {
2265                    // an inline extension in a type position: anonymous, never memoized
2266                    let extr = self.resolve(ext, None)?;
2267                    if !is_rec(&base) {
2268                        return Ok(base);
2269                    }
2270                    let merged = ty(RTk::Rec(rec_type(false)));
2271                    if let RTk::Rec(r) = &merged.k {
2272                        r.filling.set(true);
2273                    }
2274                    *merged.name.borrow_mut() = base.name.borrow().clone();
2275                    self.extend_into(&merged, &base, &extr);
2276                    return Ok(merged);
2277                }
2278                base
2279            }
2280        })
2281    }
2282
2283    // §3.14: fill `target` as `base` extended by the override body `ext` —
2284    // base members copied, overrides replacing or adding, asserts appended,
2285    // and a context declaration narrowed by the extension replacing the
2286    // inherited one (§7.3). A base still being filled (the recursive-family
2287    // case above) defers the merge until it completes; `target` stays marked
2288    // filling meanwhile, so an extension of an extension waits in turn.
2289    fn extend_into(&self, target: &RT, base: &RT, extr: &RT) {
2290        let (RTk::Rec(tr), RTk::Rec(br), RTk::Rec(er)) = (&target.k, &base.k, &extr.k) else {
2291            if let RTk::Rec(tr) = &target.k {
2292                tr.filling.set(false);
2293            }
2294            return;
2295        };
2296        if br.filling.get() {
2297            br.pending.borrow_mut().push((target.clone(), extr.clone()));
2298            return;
2299        }
2300        tr.open.set(br.open.get());
2301        if let Some(t) = base.tail.borrow().clone() {
2302            *target.tail.borrow_mut() = Some(t);
2303        }
2304        let mut members: Vec<Member> = (**br.members.borrow()).clone();
2305        for om in er.members.borrow().iter() {
2306            if let Some(i) = members.iter().position(|m| m.name == om.name) {
2307                members[i] = om.clone();
2308            } else {
2309                members.push(om.clone());
2310            }
2311        }
2312        let mut asserts = br.asserts.borrow().clone();
2313        asserts.extend(er.asserts.borrow().iter().cloned());
2314        let mut ctx_decls: Vec<(String, RT)> = br.ctx_decls.borrow().clone();
2315        for cd in er.ctx_decls.borrow().iter() {
2316            if let Some(i) = ctx_decls.iter().position(|(v, _)| *v == cd.0) {
2317                ctx_decls[i] = cd.clone();
2318            } else {
2319                ctx_decls.push(cd.clone());
2320            }
2321        }
2322        *tr.members.borrow_mut() = Rc::new(members);
2323        *tr.asserts.borrow_mut() = asserts;
2324        *tr.ctx_decls.borrow_mut() = ctx_decls;
2325        self.complete_record(target);
2326    }
2327
2328    // a record's members are final: extensions that waited on it merge now
2329    fn complete_record(&self, rt: &RT) {
2330        let RTk::Rec(r) = &rt.k else { return };
2331        r.filling.set(false);
2332        let pending: Vec<(RT, RT)> = std::mem::take(&mut *r.pending.borrow_mut());
2333        for (target, extr) in pending {
2334            self.extend_into(&target, rt, &extr);
2335        }
2336    }
2337
2338    // §3.6: `${T}` inside a pattern splices another type — a string-shaped
2339    // T (pattern, string literal, union of those) as its regular language,
2340    // an integer-shaped T (int literal, int range, union) as the decimal
2341    // representations of its members
2342    fn expand_pattern(self: &Rc<Env>, re: &str) -> Result<String, String> {
2343        let hole: &Regex = &PATTERN_HOLE;
2344        let mut out = String::new();
2345        let mut last = 0;
2346        for m in hole.captures_iter(re) {
2347            let whole = m.get(0).unwrap();
2348            out.push_str(&re[last..whole.start()]);
2349            last = whole.end();
2350            let text = m.get(1).unwrap().as_str().trim().to_string();
2351            // the spliced type: a union of string literals, int literals, int
2352            // ranges, and named types — the type-expression subset that fits
2353            // inside a pattern token
2354            let arms: Vec<String> = text.split('|').map(|a| a.trim().to_string()).collect();
2355            let mut frags: Vec<String> = vec![];
2356            let str_lit: &Regex = &PATTERN_STR_LIT;
2357            let int_range: &Regex = &PATTERN_INT_RANGE;
2358            let int_lit: &Regex = &PATTERN_INT_LIT;
2359            let ident: &Regex = &PATTERN_IDENT;
2360            for arm in &arms {
2361                if str_lit.is_match(arm) {
2362                    let v = crate::parse::json_unquote(arm)?;
2363                    frags.push(self.pattern_fragment(&ty(RTk::Lit(Value::Str(v.into()))), &text)?);
2364                    continue;
2365                }
2366                if let Some(c) = int_range.captures(arm) {
2367                    let lo = c[1].parse::<BigInt>().map_err(|e| e.to_string())?;
2368                    let hi = c[3].parse::<BigInt>().map_err(|e| e.to_string())?;
2369                    let rt = ty(RTk::Range {
2370                        lo: Value::Int(Num::from(lo)),
2371                        hi: Value::Int(Num::from(hi)),
2372                        excl: &c[2] == "<",
2373                        base: "int".into(),
2374                    });
2375                    frags.push(self.pattern_fragment(&rt, &text)?);
2376                    continue;
2377                }
2378                if int_lit.is_match(arm) {
2379                    let v = arm.parse::<BigInt>().map_err(|e| e.to_string())?;
2380                    frags.push(
2381                        self.pattern_fragment(&ty(RTk::Lit(Value::Int(Num::from(v)))), &text)?,
2382                    );
2383                    continue;
2384                }
2385                if !ident.is_match(arm) {
2386                    return Err(format!(
2387                        "pattern interpolation of {text}: not a type (§3.6)"
2388                    ));
2389                }
2390                if self.pattern_visiting.borrow().iter().any(|v| v == arm) {
2391                    return Err(format!("pattern interpolation of {arm} is circular"));
2392                }
2393                self.pattern_visiting.borrow_mut().push(arm.clone());
2394                let resolved = self.resolve(
2395                    &TypeAst::Named {
2396                        name: arm.clone(),
2397                        args: vec![],
2398                        preds: None,
2399                        ext: None,
2400                        loc: None,
2401                    },
2402                    None,
2403                );
2404                self.pattern_visiting.borrow_mut().retain(|v| v != arm);
2405                let rt = match resolved {
2406                    Ok(rt) => rt,
2407                    Err(e) => {
2408                        if e.starts_with("unknown type") {
2409                            return Err(format!("pattern interpolation of {arm}: unknown type"));
2410                        }
2411                        return Err(e);
2412                    }
2413                };
2414                frags.push(self.pattern_fragment(&rt, arm)?);
2415            }
2416            if frags.len() == 1 {
2417                out.push_str(&frags[0]);
2418            } else {
2419                out.push_str(&format!("(?:{})", frags.join("|")));
2420            }
2421        }
2422        out.push_str(&re[last..]);
2423        Ok(out)
2424    }
2425    fn pattern_fragment(self: &Rc<Env>, rt: &RT, name: &str) -> Result<String, String> {
2426        let esc = |s: &str| -> String {
2427            let mut o = String::with_capacity(s.len());
2428            for c in s.chars() {
2429                if ".*+?^${}()|[]\\/".contains(c) {
2430                    o.push('\\');
2431                }
2432                o.push(c);
2433            }
2434            o
2435        };
2436        let bad = || {
2437            Err(format!("pattern interpolation of {name}: type is neither string- nor integer-shaped (§3.6)"))
2438        };
2439        match &rt.k {
2440            RTk::Pattern { src, .. } => Ok(format!("(?:{src})")),
2441            RTk::Lit(Value::Str(s)) => Ok(esc(s)),
2442            RTk::Lit(Value::Int(i)) => Ok(i.to_string()),
2443            RTk::Lit(_) => bad(),
2444            RTk::Range { lo, hi, excl, base } => {
2445                let (Value::Int(lo), Value::Int(hi)) = (lo, hi) else {
2446                    return bad();
2447                };
2448                if base != "int" {
2449                    return bad();
2450                }
2451                let hi = if *excl { hi - 1 } else { hi.clone() };
2452                if &hi - lo >= Num::from(65536) {
2453                    return Err(format!(
2454                        "pattern interpolation of {name}: range too large (limit 65536 values)"
2455                    ));
2456                }
2457                let mut alts: Vec<String> = vec![];
2458                let mut v = lo.clone();
2459                while v <= hi {
2460                    alts.push(v.to_string());
2461                    v += 1;
2462                }
2463                Ok(format!("(?:{})", alts.join("|")))
2464            }
2465            RTk::Union(arms) => {
2466                let parts = arms
2467                    .borrow()
2468                    .iter()
2469                    .map(|a| self.pattern_fragment(a, name))
2470                    .collect::<Result<Vec<_>, _>>()?;
2471                Ok(format!("(?:{})", parts.join("|")))
2472            }
2473            RTk::Pred { base, .. } => self.pattern_fragment(base, name),
2474            RTk::Prim(n) if n == "string" => Ok(".*".into()),
2475            RTk::Prim(n) if n == "int" => Ok("-?[0-9]+".into()),
2476            _ => bad(),
2477        }
2478    }
2479
2480    // §3.15 generics
2481    fn instantiate(
2482        self: &Rc<Env>,
2483        name: &str,
2484        args: &[TypeAst],
2485        decl: &Rc<TypeEntry>,
2486    ) -> Result<RT, String> {
2487        let ps = &decl.params;
2488        if args.len() != ps.len() {
2489            return Err(format!(
2490                "generic arity: {name} expects {} argument(s), got {}",
2491                ps.len(),
2492                args.len()
2493            ));
2494        }
2495        let mut types: HashMap<String, TypeAst> = HashMap::new();
2496        let mut values: HashMap<String, Value> = HashMap::new();
2497        let mut label = Vec::new();
2498        for (p, a) in ps.iter().zip(args) {
2499            if let Some(pty) = &p.ty {
2500                let v = match a {
2501                    TypeAst::Lit { v, .. } => v.clone(),
2502                    TypeAst::Named {
2503                        name: an,
2504                        args: aa,
2505                        ext: None,
2506                        preds: None,
2507                        ..
2508                    } if aa.is_empty() => {
2509                        let v = self.const_num(&Value::Str(an.clone().into()));
2510                        if matches!(v, Value::Str(_)) {
2511                            return Err(format!(
2512                                "non-constant value argument {an} for {} of {name}",
2513                                p.name
2514                            ));
2515                        }
2516                        v
2517                    }
2518                    _ => {
2519                        return Err(format!(
2520                            "generic arity: parameter {} of {name} takes a constant value",
2521                            p.name
2522                        ))
2523                    }
2524                };
2525                let bound = self.resolve(&subst_type(pty, &types, &values), None)?;
2526                if !crate::subsume::subsumes(self, &ty(RTk::Lit(v.clone())), &bound) {
2527                    return Err(format!(
2528                        "value argument {v:?} outside parameter {}'s type in {name}",
2529                        p.name
2530                    ));
2531                }
2532                label.push(format!("{v:?}"));
2533                values.insert(p.name.clone(), v);
2534            } else {
2535                label.push(match a {
2536                    TypeAst::Named { name, .. } | TypeAst::Prim { name, .. } => name.clone(),
2537                    _ => "type".into(),
2538                });
2539                types.insert(p.name.clone(), a.clone());
2540            }
2541        }
2542        let key = format!(
2543            "{name}<{}>",
2544            args.iter().map(type_key).collect::<Vec<_>>().join(",")
2545        );
2546        if let Some(rt) = self.type_memo.borrow().get(&key).cloned() {
2547            return Ok(rt);
2548        }
2549        let shown = format!("{name}<{}>", label.join(", "));
2550        let body = subst_type(&decl.ast, &types, &values);
2551        let rt = match &body {
2552            TypeAst::Record { members, open, .. } => {
2553                let rt = ty(RTk::Rec(rec_type(*open)));
2554                *rt.name.borrow_mut() = Some(shown);
2555                *rt.tail.borrow_mut() = decl.tail.clone();
2556                self.type_memo.borrow_mut().insert(key.clone(), rt.clone());
2557                if let Err(e) = self.fill_record(&rt, members) {
2558                    self.type_memo.borrow_mut().remove(&key);
2559                    return Err(e);
2560                }
2561                rt
2562            }
2563            other => {
2564                let rt = self.resolve(other, Some(&shown))?;
2565                if matches!(rt.k, RTk::Rec(_) | RTk::Union(_)) {
2566                    *rt.name.borrow_mut() = Some(shown);
2567                }
2568                if rt.tail.borrow().is_none() {
2569                    *rt.tail.borrow_mut() = decl.tail.clone();
2570                }
2571                self.type_memo.borrow_mut().insert(key, rt.clone());
2572                rt
2573            }
2574        };
2575        Ok(rt)
2576    }
2577
2578    fn fill_record(self: &Rc<Env>, rt: &RT, members: &[MemberAst]) -> Result<(), String> {
2579        let RTk::Rec(r) = &rt.k else { return Ok(()) };
2580        let origin = rt.name.borrow().clone();
2581        r.filling.set(true);
2582        for m in members {
2583            match m {
2584                MemberAst::Value {
2585                    name,
2586                    opt,
2587                    ty: t,
2588                    dflt,
2589                    ..
2590                } => Rc::make_mut(&mut r.members.borrow_mut()).push(Member {
2591                    kind: if dflt.is_some() {
2592                        MKind::Dflt
2593                    } else if *opt {
2594                        MKind::Opt
2595                    } else {
2596                        MKind::Req
2597                    },
2598                    name: name.clone(),
2599                    hidden: false,
2600                    ty: Some(self.resolve(t, None)?),
2601                    conj: None,
2602                    dflt: dflt.clone(),
2603                    expr: None,
2604                    menv: Some(self.clone()),
2605                }),
2606                MemberAst::Derived {
2607                    name,
2608                    ty: t,
2609                    expr,
2610                    hidden,
2611                    ..
2612                } => Rc::make_mut(&mut r.members.borrow_mut()).push(Member {
2613                    kind: MKind::Der,
2614                    name: name.clone(),
2615                    hidden: *hidden,
2616                    ty: match t {
2617                        Some(t) => Some(self.resolve(t, None)?),
2618                        None => None,
2619                    },
2620                    conj: None,
2621                    dflt: None,
2622                    expr: Some(expr.clone()),
2623                    menv: Some(self.clone()),
2624                }),
2625                MemberAst::Assert {
2626                    name, cond, tail, ..
2627                } => r.asserts.borrow_mut().push(AssertItem {
2628                    when: false,
2629                    name: name.clone(),
2630                    cond: cond.clone(),
2631                    tail: tail.clone(),
2632                    body: vec![],
2633                    origin: origin.clone(),
2634                    menv: Some(self.clone()),
2635                }),
2636                MemberAst::When { cond, body, .. } => r.asserts.borrow_mut().push(AssertItem {
2637                    when: true,
2638                    name: String::new(),
2639                    cond: cond.clone(),
2640                    tail: None,
2641                    body: body.clone(),
2642                    origin: origin.clone(),
2643                    menv: Some(self.clone()),
2644                }),
2645                MemberAst::Context {
2646                    variable, ty: t, ..
2647                } => r
2648                    .ctx_decls
2649                    .borrow_mut()
2650                    .push((variable.clone(), self.resolve(t, None)?)),
2651            }
2652        }
2653        self.complete_record(rt);
2654        Ok(())
2655    }
2656
2657    fn merge_isect(&self, arms: &[RT], name: Option<&str>) -> RT {
2658        let mut members: Vec<Member> = vec![];
2659        let mut asserts: Vec<AssertItem> = vec![];
2660        let mut open = true;
2661        for a in arms {
2662            let RTk::Rec(r) = &a.k else { continue };
2663            open = open && r.open.get();
2664            for m in r.members.borrow().iter() {
2665                if let Some(i) = members.iter().position(|x| x.name == m.name) {
2666                    let prev = members[i].clone();
2667                    let mut conj = prev
2668                        .conj
2669                        .clone()
2670                        .unwrap_or_else(|| prev.ty.iter().cloned().collect());
2671                    if let Some(t) = &m.ty {
2672                        conj.push(t.clone());
2673                    }
2674                    members[i] = Member {
2675                        conj: Some(conj),
2676                        kind: if m.kind == MKind::Req {
2677                            MKind::Req
2678                        } else {
2679                            prev.kind
2680                        },
2681                        ..prev
2682                    };
2683                } else {
2684                    members.push(m.clone());
2685                }
2686            }
2687            asserts.extend(r.asserts.borrow().iter().map(|x| AssertItem {
2688                origin: x.origin.clone().or_else(|| a.name.borrow().clone()),
2689                ..x.clone()
2690            }));
2691        }
2692        let rec = rec_type(open);
2693        *rec.members.borrow_mut() = Rc::new(members);
2694        *rec.asserts.borrow_mut() = asserts;
2695        let rt = ty(RTk::Rec(rec));
2696        *rt.name.borrow_mut() = name.map(|s| s.to_string());
2697        rt
2698    }
2699}
2700
2701fn type_key(t: &TypeAst) -> String {
2702    match t {
2703        TypeAst::Prim { name: n, .. } => format!("p:{n}"),
2704        TypeAst::Lit { v, .. } => format!("l:{v:?}"),
2705        TypeAst::Named { name, args, .. } => format!(
2706            "n:{name}<{}>",
2707            args.iter().map(type_key).collect::<Vec<_>>().join(",")
2708        ),
2709        TypeAst::Range { lo, hi, excl, .. } => format!("r:{lo:?}..{excl}{hi:?}"),
2710        TypeAst::Array { elem, lo, hi, .. } => format!("a:{}[{lo:?},{hi:?}]", type_key(elem)),
2711        TypeAst::Union { arms: a, .. } => {
2712            format!("u:{}", a.iter().map(type_key).collect::<Vec<_>>().join("|"))
2713        }
2714        TypeAst::Isect { arms: a, .. } => {
2715            format!("i:{}", a.iter().map(type_key).collect::<Vec<_>>().join("&"))
2716        }
2717        TypeAst::Map { key, val, .. } => format!("m:{}:{}", type_key(key), type_key(val)),
2718        TypeAst::Pattern { re: p, .. } => format!("pat:{p}"),
2719        TypeAst::Record { members, .. } => format!("rec:{}", members.len()),
2720        TypeAst::Func { params, ret, .. } => format!("f:{}->{}", params.len(), type_key(ret)),
2721    }
2722}
2723
2724// ---------------- generic substitution ----------------
2725/// Substitute a generic type's parameters (§3.15).
2726pub fn subst_type(
2727    ast: &TypeAst,
2728    types: &HashMap<String, TypeAst>,
2729    values: &HashMap<String, Value>,
2730) -> TypeAst {
2731    let t = |a: &TypeAst| subst_type(a, types, values);
2732    match ast {
2733        TypeAst::Named {
2734            name,
2735            args,
2736            preds,
2737            ext,
2738            loc,
2739        } => {
2740            let plain = args.is_empty() && ext.is_none() && preds.is_none();
2741            if plain {
2742                if let Some(x) = types.get(name) {
2743                    return x.clone();
2744                }
2745                if let Some(v) = values.get(name) {
2746                    return TypeAst::Lit {
2747                        v: v.clone(),
2748                        loc: *loc,
2749                    };
2750                }
2751            }
2752            TypeAst::Named {
2753                name: name.clone(),
2754                args: args.iter().map(t).collect(),
2755                preds: preds
2756                    .as_ref()
2757                    .map(|ps| ps.iter().map(|p| subst_expr(p, values)).collect()),
2758                ext: ext.as_ref().map(|e| Box::new(t(e))),
2759                loc: *loc,
2760            }
2761        }
2762        TypeAst::Range { lo, hi, excl, loc } => {
2763            let sub = |v: &Value| match v {
2764                Value::Str(s) if values.contains_key(&**s) => values[&**s].clone(),
2765                other => other.clone(),
2766            };
2767            TypeAst::Range {
2768                lo: sub(lo),
2769                hi: sub(hi),
2770                excl: *excl,
2771                loc: *loc,
2772            }
2773        }
2774        TypeAst::Array {
2775            elem,
2776            lo,
2777            hi,
2778            excl,
2779            loc,
2780        } => {
2781            let sub = |v: &Value| match v {
2782                Value::Str(s) if values.contains_key(&**s) => values[&**s].clone(),
2783                other => other.clone(),
2784            };
2785            TypeAst::Array {
2786                elem: Box::new(t(elem)),
2787                lo: lo.as_ref().map(sub),
2788                hi: hi.as_ref().map(sub),
2789                excl: *excl,
2790                loc: *loc,
2791            }
2792        }
2793        TypeAst::Record { members, open, loc } => TypeAst::Record {
2794            members: members
2795                .iter()
2796                .map(|m| subst_member(m, types, values))
2797                .collect(),
2798            open: *open,
2799            loc: *loc,
2800        },
2801        TypeAst::Map { key, val, loc } => TypeAst::Map {
2802            key: Box::new(t(key)),
2803            val: Box::new(t(val)),
2804            loc: *loc,
2805        },
2806        TypeAst::Union { arms: a, loc } => TypeAst::Union {
2807            arms: a.iter().map(t).collect(),
2808            loc: *loc,
2809        },
2810        TypeAst::Isect { arms: a, loc } => TypeAst::Isect {
2811            arms: a.iter().map(t).collect(),
2812            loc: *loc,
2813        },
2814        TypeAst::Func { params, ret, loc } => TypeAst::Func {
2815            params: params.iter().map(t).collect(),
2816            ret: Box::new(t(ret)),
2817            loc: *loc,
2818        },
2819        other => other.clone(),
2820    }
2821}
2822fn subst_member(
2823    m: &MemberAst,
2824    types: &HashMap<String, TypeAst>,
2825    values: &HashMap<String, Value>,
2826) -> MemberAst {
2827    let t = |a: &TypeAst| subst_type(a, types, values);
2828    match m {
2829        MemberAst::Value {
2830            name,
2831            opt,
2832            ty,
2833            dflt,
2834            annotations,
2835            loc,
2836        } => MemberAst::Value {
2837            name: name.clone(),
2838            opt: *opt,
2839            ty: t(ty),
2840            dflt: dflt.as_ref().map(|d| subst_expr(d, values)),
2841            annotations: annotations.clone(),
2842            loc: *loc,
2843        },
2844        MemberAst::Derived {
2845            name,
2846            ty,
2847            expr,
2848            hidden,
2849            annotations,
2850            loc,
2851        } => MemberAst::Derived {
2852            name: name.clone(),
2853            ty: ty.as_ref().map(t),
2854            expr: subst_expr(expr, values),
2855            hidden: *hidden,
2856            annotations: annotations.clone(),
2857            loc: *loc,
2858        },
2859        MemberAst::Context {
2860            variable,
2861            ty,
2862            annotations,
2863            loc,
2864        } => MemberAst::Context {
2865            variable: variable.clone(),
2866            ty: t(ty),
2867            annotations: annotations.clone(),
2868            loc: *loc,
2869        },
2870        MemberAst::Assert {
2871            name,
2872            cond,
2873            tail,
2874            annotations,
2875            loc,
2876        } => MemberAst::Assert {
2877            name: name.clone(),
2878            cond: subst_expr(cond, values),
2879            tail: tail.clone(),
2880            annotations: annotations.clone(),
2881            loc: *loc,
2882        },
2883        MemberAst::When {
2884            cond,
2885            body,
2886            annotations,
2887            loc,
2888        } => MemberAst::When {
2889            cond: subst_expr(cond, values),
2890            body: body
2891                .iter()
2892                .map(|b| subst_member(b, types, values))
2893                .collect(),
2894            annotations: annotations.clone(),
2895            loc: *loc,
2896        },
2897    }
2898}
2899/// Substitute values for names in an expression.
2900pub fn subst_expr(e: &Rc<Expr>, values: &HashMap<String, Value>) -> Rc<Expr> {
2901    if values.is_empty() {
2902        return e.clone();
2903    }
2904    let s = |x: &Rc<Expr>| subst_expr(x, values);
2905    let cls = |c: &ForClause| ForClause {
2906        v: c.v.clone(),
2907        iter: s(&c.iter),
2908        filters: c.filters.iter().map(s).collect(),
2909    };
2910    let out = Rc::new(match &**e {
2911        Expr::Name(n) if values.contains_key(n) => Expr::Lit(values[n].clone()),
2912        Expr::Template(parts) => Expr::Template(
2913            parts
2914                .iter()
2915                .map(|p| match p {
2916                    TPart::Expr(x) => TPart::Expr(s(x)),
2917                    other => other.clone(),
2918                })
2919                .collect(),
2920        ),
2921        Expr::Obj(es) => Expr::Obj(es.iter().map(|(k, v)| (k.clone(), s(v))).collect()),
2922        Expr::Arr(items) => Expr::Arr(items.iter().map(|(sp, v)| (*sp, s(v))).collect()),
2923        Expr::Comp { head, clauses } => Expr::Comp {
2924            head: s(head),
2925            clauses: clauses.iter().map(cls).collect(),
2926        },
2927        Expr::MapComp { key, val, clauses } => Expr::MapComp {
2928            key: s(key),
2929            val: s(val),
2930            clauses: clauses.iter().map(cls).collect(),
2931        },
2932        Expr::Bin { op, l, r } => Expr::Bin {
2933            op: op.clone(),
2934            l: s(l),
2935            r: s(r),
2936        },
2937        Expr::Un { op, x } => Expr::Un {
2938            op: op.clone(),
2939            x: s(x),
2940        },
2941        Expr::Paren(x) => Expr::Paren(s(x)),
2942        Expr::If { c, t, f } => Expr::If {
2943            c: s(c),
2944            t: s(t),
2945            f: s(f),
2946        },
2947        Expr::Lambda { params, body } => Expr::Lambda {
2948            params: params.clone(),
2949            body: s(body),
2950        },
2951        Expr::Call { fun, args } => Expr::Call {
2952            fun: s(fun),
2953            args: args.iter().map(s).collect(),
2954        },
2955        Expr::Member { x, name, safe } => Expr::Member {
2956            x: s(x),
2957            name: name.clone(),
2958            safe: *safe,
2959        },
2960        Expr::Index { x, i } => Expr::Index { x: s(x), i: s(i) },
2961        Expr::With { base, patch } => Expr::With {
2962            base: s(base),
2963            patch: s(patch),
2964        },
2965        Expr::Match { subject, arms } => Expr::Match {
2966            subject: s(subject),
2967            arms: arms
2968                .iter()
2969                .map(|a| MatchArm {
2970                    v: a.v.clone(),
2971                    ty: a.ty.clone(),
2972                    body: s(&a.body),
2973                })
2974                .collect(),
2975        },
2976        other => other.clone(),
2977    });
2978    // a substituted node keeps the source range of the node it replaces (the reference copies `loc`)
2979    if let Some(l) = expr_loc(e) {
2980        set_expr_loc(&out, l);
2981    }
2982    out
2983}
2984
2985// ---------------- helpers ----------------
2986// ---------------- patterns: the portable core (§3.6) ----------------
2987// A pattern body is validated against the specification's regular-
2988// expression core with one fixed set of messages, so every implementation
2989// reports the same text whatever engine runs the accepted patterns.
2990// Returns the reason a body is outside the core, or None when it is inside.
2991const PATTERN_PUNCT: &str = "\\/.*+?()[]{}|^$-";
2992fn pattern_escape(cs: &[char], i: &mut usize) -> Result<i64, String> {
2993    if *i + 1 >= cs.len() {
2994        return Err("trailing backslash".into());
2995    }
2996    let e = cs[*i + 1];
2997    *i += 2;
2998    if "dwsDWS".contains(e) {
2999        return Ok(-1);
3000    }
3001    match e {
3002        'n' => return Ok(10),
3003        't' => return Ok(9),
3004        'r' => return Ok(13),
3005        _ => {}
3006    }
3007    if PATTERN_PUNCT.contains(e) {
3008        return Ok(e as i64);
3009    }
3010    if e.is_ascii_digit() {
3011        return Err(format!("backreference \\{e} is not supported"));
3012    }
3013    Err(format!("unsupported escape \\{e}"))
3014}
3015/// Why a pattern body is outside the §3.6 core (E4119), when it is.
3016pub fn pattern_error(src: &str) -> Option<String> {
3017    let cs: Vec<char> = src.chars().collect();
3018    let n = cs.len();
3019    let (mut i, mut depth, mut can_repeat) = (0usize, 0i32, false);
3020    while i < n {
3021        match cs[i] {
3022            '\\' => {
3023                if let Err(r) = pattern_escape(&cs, &mut i) {
3024                    return Some(r);
3025                }
3026                can_repeat = true;
3027            }
3028            '[' => {
3029                i += 1;
3030                if i < n && cs[i] == '^' {
3031                    i += 1;
3032                }
3033                let mut items = 0;
3034                loop {
3035                    if i >= n {
3036                        return Some("unterminated character class".into());
3037                    }
3038                    if cs[i] == ']' {
3039                        i += 1;
3040                        break;
3041                    }
3042                    let lo = if cs[i] == '\\' {
3043                        match pattern_escape(&cs, &mut i) {
3044                            Ok(v) => v,
3045                            Err(r) => return Some(r),
3046                        }
3047                    } else {
3048                        let v = cs[i] as i64;
3049                        i += 1;
3050                        v
3051                    };
3052                    if i < n && cs[i] == '-' && i + 1 < n && cs[i + 1] != ']' {
3053                        i += 1;
3054                        let hi = if cs[i] == '\\' {
3055                            match pattern_escape(&cs, &mut i) {
3056                                Ok(v) => v,
3057                                Err(r) => return Some(r),
3058                            }
3059                        } else {
3060                            let v = cs[i] as i64;
3061                            i += 1;
3062                            v
3063                        };
3064                        if lo < 0 || hi < 0 || lo > hi {
3065                            return Some("invalid range in character class".into());
3066                        }
3067                    }
3068                    items += 1;
3069                }
3070                if items == 0 {
3071                    return Some("empty character class".into());
3072                }
3073                can_repeat = true;
3074            }
3075            ']' => return Some("unbalanced bracket".into()),
3076            '(' => {
3077                i += 1;
3078                if i < n && cs[i] == '?' {
3079                    if i + 1 < n && cs[i + 1] == ':' {
3080                        i += 2;
3081                    } else {
3082                        return Some("unsupported construct (?".into());
3083                    }
3084                }
3085                depth += 1;
3086                can_repeat = false;
3087            }
3088            ')' => {
3089                if depth == 0 {
3090                    return Some("unbalanced parenthesis".into());
3091                }
3092                depth -= 1;
3093                i += 1;
3094                can_repeat = true;
3095            }
3096            '|' => {
3097                i += 1;
3098                can_repeat = false;
3099            }
3100            '*' | '+' | '?' => {
3101                if !can_repeat {
3102                    return Some("nothing to repeat".into());
3103                }
3104                i += 1;
3105                can_repeat = false;
3106            }
3107            '{' => {
3108                if !can_repeat {
3109                    return Some("nothing to repeat".into());
3110                }
3111                let mut j = i + 1;
3112                let start = j;
3113                while j < n && cs[j].is_ascii_digit() {
3114                    j += 1;
3115                }
3116                if j == start {
3117                    return Some("malformed repetition".into());
3118                }
3119                let m: String = cs[start..j].iter().collect();
3120                let mut hi: Option<String> = None;
3121                if j < n && cs[j] == ',' {
3122                    j += 1;
3123                    let s2 = j;
3124                    while j < n && cs[j].is_ascii_digit() {
3125                        j += 1;
3126                    }
3127                    if j > s2 {
3128                        hi = Some(cs[s2..j].iter().collect());
3129                    }
3130                }
3131                if j >= n || cs[j] != '}' {
3132                    return Some("malformed repetition".into());
3133                }
3134                if let Some(h) = hi {
3135                    if h.parse::<BigInt>().unwrap_or_default()
3136                        < m.parse::<BigInt>().unwrap_or_default()
3137                    {
3138                        return Some("malformed repetition".into());
3139                    }
3140                }
3141                i = j + 1;
3142                can_repeat = false;
3143            }
3144            '}' => return Some("malformed repetition".into()),
3145            '^' | '$' => {
3146                i += 1;
3147                can_repeat = false;
3148            }
3149            _ => {
3150                i += 1;
3151                can_repeat = true;
3152            }
3153        }
3154    }
3155    if depth > 0 {
3156        Some("unbalanced parenthesis".into())
3157    } else {
3158        None
3159    }
3160}
3161/// Compile a pattern body to a regular expression.
3162pub fn compile_pattern(src: &str) -> Result<Regex, String> {
3163    Regex::new(&format!("^(?:{src})$")).map_err(|e| e.to_string())
3164}
3165
3166/// A canonical path's text, relative to `rel_root` (`$.…`) when given.
3167pub fn path_str(segs: &[Seg], rel_root: Option<&str>) -> String {
3168    path_str_iter(segs.iter(), rel_root)
3169}
3170
3171/// Format borrowed canonical segments without requiring a contiguous vector.
3172pub fn path_str_iter<'a>(
3173    segs: impl IntoIterator<Item = &'a Seg>,
3174    rel_root: Option<&str>,
3175) -> String {
3176    let mut out = String::new();
3177    for (i, s) in segs.into_iter().enumerate() {
3178        write_path_segment(&mut out, s, i == 0, rel_root);
3179    }
3180    out
3181}
3182
3183/// Format once and retain UTF-8 byte boundaries for each complete path prefix.
3184/// Offsets follow segments, including roots whose bare text contains delimiters.
3185/// The spelling is appended to `text` and the prefix lengths, counted from
3186/// where it starts, to `ends`: many paths without an allocation each. `None`
3187/// when a length outgrows 32 bits.
3188pub(crate) fn path_str_ends_into(
3189    segs: &[Seg],
3190    text: &mut String,
3191    ends: &mut Vec<u32>,
3192) -> Option<()> {
3193    let start = text.len();
3194    for (i, s) in segs.iter().enumerate() {
3195        write_path_segment(text, s, i == 0, None);
3196        ends.push(u32::try_from(text.len() - start).ok()?);
3197    }
3198    Some(())
3199}
3200
3201fn write_path_segment(out: &mut String, s: &Seg, first: bool, rel_root: Option<&str>) {
3202    use std::fmt::Write;
3203    // The root segment is bare; later segments use canonical member/bracket
3204    // spelling. Both ordinary formatting and prefix indexing share this writer.
3205    if first {
3206        match s {
3207            Seg::Name(n) | Seg::Key(n) => {
3208                if rel_root == Some(&**n) {
3209                    out.push('$');
3210                } else {
3211                    out.push_str(n);
3212                }
3213            }
3214            Seg::Idx(k) => {
3215                let t = k.to_string();
3216                if rel_root == Some(t.as_str()) {
3217                    out.push('$');
3218                } else {
3219                    out.push_str(&t);
3220                }
3221            }
3222        }
3223        return;
3224    }
3225    match s {
3226        Seg::Idx(k) => {
3227            let _ = write!(out, "[{k}]");
3228        }
3229        Seg::Key(n) => {
3230            let _ = write!(out, "[{}]", json_str(n));
3231        }
3232        Seg::Name(n) if dot_spellable(n) => {
3233            out.push('.');
3234            out.push_str(n);
3235        }
3236        Seg::Name(n) => {
3237            let _ = write!(out, "[{}]", json_str(n));
3238        }
3239    }
3240}
3241
3242/// A path string from a document: `.name` is a member, `["…"]` a bracketed
3243/// segment (a map key, or a member the dot cannot spell — the canonical walk,
3244/// §7.5, decides which is legal where), `[n]` an index.
3245pub fn parse_path(s: &str, root_name: &str) -> R<SegPath> {
3246    let id_re = Regex::new(r"^[_A-Za-z][_A-Za-z0-9]*").unwrap();
3247    let mut segs = vec![];
3248    let mut i = if s.starts_with('$') {
3249        segs.push(Seg::Name(Rc::from(root_name.to_string())));
3250        1
3251    } else {
3252        let m = id_re
3253            .find(s)
3254            .ok_or(())
3255            .or_else(|_| err(format!("bad path {s}")))?;
3256        segs.push(Seg::Name(Rc::from(m.as_str())));
3257        m.end()
3258    };
3259    while i < s.len() {
3260        let rest = &s[i..];
3261        if let Some(r) = rest.strip_prefix('.') {
3262            let m = id_re
3263                .find(r)
3264                .ok_or(())
3265                .or_else(|_| err(format!("bad path {s}")))?;
3266            segs.push(Seg::Name(Rc::from(m.as_str())));
3267            i += 1 + m.end();
3268        } else if rest.starts_with('[') {
3269            let j = rest
3270                .find(']')
3271                .ok_or(())
3272                .or_else(|_| err(format!("bad path {s}")))?;
3273            let inner = &rest[1..j];
3274            if inner.starts_with('"') {
3275                segs.push(Seg::Key(Rc::from(
3276                    crate::parse::json_unquote(inner).unwrap_or_default(),
3277                )));
3278            } else {
3279                segs.push(Seg::Idx(inner.parse().unwrap_or(0)));
3280            }
3281            i += j + 1;
3282        } else {
3283            return err(format!("bad path {s}"));
3284        }
3285    }
3286    Ok(segs)
3287}
3288
3289/// Canonical path order (§7.2): segment-wise, indices numerically, names and
3290/// keys lexicographically, a prefix first.
3291pub fn cmp_path(a: &[Seg], b: &[Seg]) -> std::cmp::Ordering {
3292    use std::cmp::Ordering;
3293    for (x, y) in a.iter().zip(b) {
3294        // by the segment's path text (§7.2), as `seg_text` spells it, but
3295        // without allocating a String per comparison (F21): two name/key
3296        // segments compare their `Rc<str>` directly, two indices compare
3297        // numerically; only a rare index-vs-name pair falls back to the text
3298        let ord = match (x, y) {
3299            (Seg::Idx(i), Seg::Idx(j)) => i.cmp(j),
3300            (Seg::Name(p) | Seg::Key(p), Seg::Name(q) | Seg::Key(q)) => (**p).cmp(&**q),
3301            _ => seg_text(x).cmp(&seg_text(y)),
3302        };
3303        if ord != Ordering::Equal {
3304            return ord;
3305        }
3306    }
3307    a.len().cmp(&b.len())
3308}
3309
3310/// Structural equality of two values (§4.5).
3311pub fn value_eq(a: &Value, b: &Value) -> bool {
3312    // Only reference equality uses places. Structural comparisons must not
3313    // export retained container paths that they will immediately discard.
3314    if matches!(a, Value::Ref(_)) || matches!(b, Value::Ref(_)) {
3315        let (pa, pb) = (a.place(), b.place());
3316        if let (Some(pa), Some(pb)) = (&pa, &pb) {
3317            return cmp_path(pa, pb) == std::cmp::Ordering::Equal;
3318        }
3319    }
3320    match (a, b) {
3321        (Value::Int(x), Value::Int(y)) => x == y,
3322        (Value::Float(x), Value::Float(y)) => x == y,
3323        (Value::Str(x), Value::Str(y)) => x == y,
3324        (Value::Bool(x), Value::Bool(y)) => x == y,
3325        (Value::Null, Value::Null) => true,
3326        // two unforced slots compare equal, as in the reference (undefined === undefined)
3327        (Value::Undef, Value::Undef) => true,
3328        (Value::Q(a), Value::Q(b)) => a.dim == b.dim && a.value == b.value,
3329        (Value::Arr(x), Value::Arr(y)) => {
3330            let (x, y) = (x.borrow(), y.borrow());
3331            x.items.len() == y.items.len()
3332                && x.items.iter().zip(&y.items).all(|(p, q)| value_eq(p, q))
3333        }
3334        (Value::Map(x), Value::Map(y)) => {
3335            let (x, y) = (x.borrow(), y.borrow());
3336            x.entries.len() == y.entries.len()
3337                && x.entries
3338                    .iter()
3339                    .all(|(k, v)| y.get(k).map(|w| value_eq(v, w)).unwrap_or(false))
3340        }
3341        (Value::Rec(x), Value::Rec(y)) => {
3342            if Rc::ptr_eq(x, y) {
3343                return true;
3344            }
3345            let (x, y) = (x.borrow(), y.borrow());
3346            for (n, s) in &x.slots {
3347                if s.hidden {
3348                    continue; // a hidden member is not part of the value (D34)
3349                }
3350                let v1 = if s.state == SlotState::Absent {
3351                    Value::Absent
3352                } else {
3353                    s.value.clone()
3354                };
3355                let v2 = match y.slot(n) {
3356                    Some(s2) if s2.state != SlotState::Absent => s2.value.clone(),
3357                    _ => Value::Absent,
3358                };
3359                match (&v1, &v2) {
3360                    (Value::Absent, Value::Absent) => continue,
3361                    (Value::Absent, _) | (_, Value::Absent) => return false,
3362                    _ => {
3363                        if !value_eq(&v1, &v2) {
3364                            return false;
3365                        }
3366                    }
3367                }
3368            }
3369            true
3370        }
3371        _ => false,
3372    }
3373}
3374
3375// ---------------- lexical JSON (int/float by lexeme) ----------------
3376/// Read a JSON document (§10.2): objects keep their key order, integers stay
3377/// exact; trailing characters are an error.
3378pub fn read_json(src: &str) -> R<Value> {
3379    let b = src.as_bytes();
3380    let mut i = 0usize;
3381    fn ws(b: &[u8], i: &mut usize) {
3382        while *i < b.len() && matches!(b[*i], b' ' | b'\t' | b'\r' | b'\n') {
3383            *i += 1;
3384        }
3385    }
3386    fn string(src: &str, b: &[u8], i: &mut usize) -> R<String> {
3387        let mut j = *i + 1;
3388        let mut out = String::new();
3389        while j < b.len() && b[j] != b'"' {
3390            if b[j] == b'\\' {
3391                let e = b[j + 1] as char;
3392                match e {
3393                    'n' => out.push('\n'),
3394                    't' => out.push('\t'),
3395                    'r' => out.push('\r'),
3396                    'b' => out.push('\u{8}'),
3397                    'f' => out.push('\u{c}'),
3398                    'u' => {
3399                        let cp = u32::from_str_radix(&src[j + 2..j + 6], 16).unwrap_or(0xfffd);
3400                        out.push(char::from_u32(cp).unwrap_or('\u{fffd}'));
3401                        j += 4;
3402                    }
3403                    other => out.push(other),
3404                }
3405                j += 2;
3406            } else {
3407                let ch = src[j..].chars().next().unwrap();
3408                out.push(ch);
3409                j += ch.len_utf8();
3410            }
3411        }
3412        *i = j + 1;
3413        Ok(out)
3414    }
3415    fn val(src: &str, b: &[u8], i: &mut usize) -> R<Value> {
3416        ws(b, i);
3417        if *i >= b.len() {
3418            return err("bad JSON: unexpected end");
3419        }
3420        match b[*i] {
3421            b'{' => {
3422                *i += 1;
3423                let mut entries = vec![];
3424                ws(b, i);
3425                if b[*i] == b'}' {
3426                    *i += 1;
3427                    return Ok(Value::JObj(Rc::new(entries)));
3428                }
3429                loop {
3430                    ws(b, i);
3431                    let k = string(src, b, i)?;
3432                    ws(b, i);
3433                    *i += 1;
3434                    let v = val(src, b, i)?;
3435                    entries.push((k, v));
3436                    ws(b, i);
3437                    if b[*i] == b',' {
3438                        *i += 1;
3439                        continue;
3440                    }
3441                    *i += 1;
3442                    return Ok(Value::JObj(Rc::new(entries)));
3443                }
3444            }
3445            b'[' => {
3446                *i += 1;
3447                let mut items = vec![];
3448                ws(b, i);
3449                if b[*i] == b']' {
3450                    *i += 1;
3451                    return Ok(Value::JArr(Rc::new(items)));
3452                }
3453                loop {
3454                    items.push(val(src, b, i)?);
3455                    ws(b, i);
3456                    if b[*i] == b',' {
3457                        *i += 1;
3458                        continue;
3459                    }
3460                    *i += 1;
3461                    return Ok(Value::JArr(Rc::new(items)));
3462                }
3463            }
3464            b'"' => Ok(Value::Str(string(src, b, i)?.into())),
3465            _ => {
3466                let rest = &src[*i..];
3467                if rest.starts_with("true") {
3468                    *i += 4;
3469                    return Ok(Value::Bool(true));
3470                }
3471                if rest.starts_with("false") {
3472                    *i += 5;
3473                    return Ok(Value::Bool(false));
3474                }
3475                if rest.starts_with("null") {
3476                    *i += 4;
3477                    return Ok(Value::Null);
3478                }
3479                static NUMBER: LazyLock<Regex> = LazyLock::new(|| {
3480                    Regex::new(r"^-?(?:0|[1-9][0-9]*)(\.[0-9]+)?([eE][-+]?[0-9]+)?").unwrap()
3481                });
3482                let m = NUMBER
3483                    .captures(rest)
3484                    .ok_or(())
3485                    .or_else(|_| err(format!("bad JSON at {i}")))?;
3486                let whole = m.get(0).unwrap().as_str();
3487                *i += whole.len();
3488                if m.get(1).is_some() || m.get(2).is_some() {
3489                    Ok(Value::Float(whole.parse::<f64>().unwrap_or(0.0)))
3490                } else {
3491                    Ok(Value::Int(Num::parse_str(whole).unwrap_or_else(Num::zero)))
3492                }
3493            }
3494        }
3495    }
3496    let v = val(src, b, &mut i)?;
3497    ws(b, &mut i);
3498    if i < b.len() {
3499        return err("bad JSON: trailing characters");
3500    }
3501    Ok(v)
3502}
3503
3504// ---------------- JS-compatible number printing ----------------
3505/// ECMAScript Number::toString for finite doubles (shortest round trip)
3506pub fn js_num_str(x: f64) -> String {
3507    if x == 0.0 {
3508        return "0".into();
3509    }
3510    let sci = format!("{:e}", x.abs());
3511    let (mant, exp) = sci.split_once('e').unwrap();
3512    let exp: i32 = exp.parse().unwrap();
3513    let digits: String = mant.chars().filter(|c| *c != '.').collect();
3514    let digits = digits.trim_end_matches('0');
3515    let digits = if digits.is_empty() { "0" } else { digits };
3516    let k = digits.len() as i32;
3517    let n = exp + 1;
3518    let body = if k <= n && n <= 21 {
3519        format!("{digits}{}", "0".repeat((n - k) as usize))
3520    } else if 0 < n && n <= 21 {
3521        format!("{}.{}", &digits[..n as usize], &digits[n as usize..])
3522    } else if -6 < n && n <= 0 {
3523        format!("0.{}{digits}", "0".repeat((-n) as usize))
3524    } else {
3525        let e = n - 1;
3526        let mant = if k > 1 {
3527            format!("{}.{}", &digits[..1], &digits[1..])
3528        } else {
3529            digits.to_string()
3530        };
3531        format!("{mant}e{}{}", if e > 0 { "+" } else { "-" }, e.abs())
3532    };
3533    if x < 0.0 {
3534        format!("-{body}")
3535    } else {
3536        body
3537    }
3538}
3539
3540/// A string as JSON text, escaped.
3541pub fn json_str(s: &str) -> String {
3542    let mut out = String::with_capacity(s.len() + 2);
3543    write_json_str(&mut out, s);
3544    out
3545}
3546
3547/// Append JSON string text without allocating an intermediate quoted string.
3548pub(crate) fn write_json_str(out: &mut String, s: &str) {
3549    const HEX: &[u8; 16] = b"0123456789abcdef";
3550    out.push('"');
3551    let mut start = 0;
3552    for (i, byte) in s.bytes().enumerate() {
3553        if byte >= 0x20 && byte != b'"' && byte != b'\\' {
3554            continue;
3555        }
3556        // Escapes occur only at ASCII bytes, hence at UTF-8 boundaries.
3557        // Copy the intervening text as a slice, including non-ASCII scalars.
3558        out.push_str(&s[start..i]);
3559        match byte {
3560            b'"' => out.push_str("\\\""),
3561            b'\\' => out.push_str("\\\\"),
3562            b'\n' => out.push_str("\\n"),
3563            b'\r' => out.push_str("\\r"),
3564            b'\t' => out.push_str("\\t"),
3565            8 => out.push_str("\\b"),
3566            12 => out.push_str("\\f"),
3567            _ => {
3568                out.push_str("\\u00");
3569                out.push(HEX[(byte >> 4) as usize] as char);
3570                out.push(HEX[(byte & 15) as usize] as char);
3571            }
3572        }
3573        start = i + 1;
3574    }
3575    out.push_str(&s[start..]);
3576    out.push('"');
3577}
3578
3579#[cfg(test)]
3580#[path = "../tests/private/path_format_test.rs"]
3581mod path_format_tests;
3582
3583#[cfg(test)]
3584#[path = "../tests/private/slot_compute_test.rs"]
3585mod slot_compute_tests;
3586
3587#[cfg(test)]
3588#[path = "../tests/private/value_storage_test.rs"]
3589mod value_storage_tests;