Skip to main content

decl_lang/qengine/
programs.rs

1//! Executable expressions shared by syntax identity. Operations receive their
2//! engine and lexical frame at execution time; none capture a record instance.
3use crate::ast::*;
4use crate::engine::{to_index, Engine};
5#[cfg(feature = "runtime-diagnostics")]
6use crate::expression_diagnostics as expr_diag;
7use crate::semantics::*;
8use rustc_hash::FxHashMap;
9use std::cell::{Cell, RefCell};
10use std::rc::{Rc, Weak};
11
12/// One shared expression, supplied with an engine and runtime scope.
13pub type Op = Rc<dyn Fn(&Engine, &Scope) -> R<Value>>;
14type Cache = RefCell<FxHashMap<usize, (Rc<Expr>, Op)>>;
15
16#[cfg(test)]
17#[path = "../../tests/private/member_compute_test.rs"]
18mod member_compute_tests;
19
20pub(crate) struct MemberPlan {
21    pub name: Rc<str>,
22    pub types: Rc<Vec<RT>>,
23    pub expression: Option<Op>,
24    pub fallback: Option<Op>,
25    pub deferred: bool,
26    // One recent descriptor, tied to this exact declaration/source snapshot.
27    // Weak storage never keeps its expression/environment captures alive.
28    recent_compute: RefCell<Weak<Compute>>,
29}
30
31impl MemberPlan {
32    pub(crate) fn reusable_compute(
33        &self,
34        kind: MKind,
35        root_name: Rc<str>,
36        menv: Option<Rc<Env>>,
37        create: impl FnOnce(Rc<str>, Option<Rc<Env>>) -> Compute,
38    ) -> Rc<Compute> {
39        let cached = self.recent_compute.borrow().upgrade();
40        if let Some(compute) = cached {
41            let context = match (kind, &*compute) {
42                (
43                    MKind::Dflt,
44                    Compute::Default {
45                        root_name, menv, ..
46                    },
47                )
48                | (
49                    MKind::Der,
50                    Compute::Derived {
51                        supplied: None,
52                        root_name,
53                        menv,
54                        ..
55                    },
56                ) => Some((root_name, menv)),
57                _ => None,
58            };
59            if let Some((old_root, old_env)) = context {
60                let same_env = match (old_env, &menv) {
61                    (None, None) => true,
62                    (Some(a), Some(b)) => Rc::ptr_eq(a, b),
63                    _ => false,
64                };
65                if Rc::ptr_eq(old_root, &root_name) && same_env {
66                    return compute;
67                }
68            }
69            drop(compute);
70        }
71        // Neither descriptor destruction nor construction runs under the
72        // cache borrow. Native COW dissociates a lone owner's cached Weak.
73        let compute = Rc::new(create(root_name, menv));
74        let old = self.recent_compute.replace(Rc::downgrade(&compute));
75        drop(old);
76        compute
77    }
78}
79
80pub(crate) struct Schema {
81    source: Rc<Vec<Member>>,
82    pub members: Vec<MemberPlan>,
83    pub names: FxHashMap<Rc<str>, usize>,
84    // One weak recent input shape per compiled schema: no record/value owners,
85    // and no unbounded cache of arbitrary document keys or order permutations.
86    entry_order: RefCell<Weak<Vec<String>>>,
87}
88
89/// Executable expressions and schema plans shared for one module universe.
90#[derive(Default)]
91pub struct Programs {
92    expressions: Cache,
93    callees: Cache,
94    navigations: Cache,
95    schemas: RefCell<FxHashMap<usize, (RT, Rc<Schema>)>>,
96    /// Number of distinct expression programs compiled.
97    pub compiled: Cell<usize>,
98    /// Number of distinct schema plans compiled.
99    pub compiled_schemas: Cell<usize>,
100}
101
102impl Programs {
103    pub(crate) fn entry_order(&self, rt: &RT, entries: &[(String, Value)]) -> Rc<Vec<String>> {
104        let schemas = self.schemas.borrow();
105        let schema = schemas
106            .get(&(Rc::as_ptr(rt) as usize))
107            .map(|(_, schema)| schema);
108        if let Some(order) = schema.and_then(|schema| schema.entry_order.borrow().upgrade()) {
109            if order.len() == entries.len()
110                && order
111                    .iter()
112                    .zip(entries)
113                    .all(|(name, (key, _))| name == key)
114            {
115                return order;
116            }
117        }
118        let order = Rc::new(entries.iter().map(|(key, _)| key.clone()).collect());
119        if let Some(schema) = schema {
120            *schema.entry_order.borrow_mut() = Rc::downgrade(&order);
121        }
122        order
123    }
124
125    pub(crate) fn schema(&self, rt: &RT) -> Rc<Schema> {
126        let id = Rc::as_ptr(rt) as usize;
127        let source = rec_members(rt);
128        if let Some((_, hit)) = self.schemas.borrow().get(&id) {
129            if Rc::ptr_eq(&hit.source, &source) {
130                return hit.clone();
131            }
132        }
133        let members: Vec<MemberPlan> = source
134            .iter()
135            .map(|m| MemberPlan {
136                name: Rc::from(m.name.as_str()),
137                types: Rc::new(
138                    m.conj
139                        .clone()
140                        .unwrap_or_else(|| m.ty.iter().cloned().collect()),
141                ),
142                expression: m.expr.as_ref().map(|e| self.get(e)),
143                fallback: m.dflt.as_ref().map(|e| self.get(e)),
144                deferred: m.expr.as_ref().is_some_and(|e| mentions_referrers(e)),
145                recent_compute: RefCell::new(Weak::new()),
146            })
147            .collect();
148        let names = members
149            .iter()
150            .enumerate()
151            .map(|(index, member)| (member.name.clone(), index))
152            .collect();
153        let schema = Rc::new(Schema {
154            source,
155            members,
156            names,
157            entry_order: RefCell::new(Weak::new()),
158        });
159        self.schemas
160            .borrow_mut()
161            .insert(id, (rt.clone(), schema.clone()));
162        self.compiled_schemas.set(self.compiled_schemas.get() + 1);
163        schema
164    }
165
166    pub(crate) fn get(&self, e: &Rc<Expr>) -> Op {
167        let id = Rc::as_ptr(e) as usize;
168        if let Some((_, op)) = self.expressions.borrow().get(&id) {
169            return op.clone();
170        }
171        let op = self.compile(e);
172        self.expressions
173            .borrow_mut()
174            .insert(id, (e.clone(), op.clone()));
175        self.compiled.set(self.compiled.get() + 1);
176        op
177    }
178
179    pub(crate) fn callee(&self, e: &Rc<Expr>) -> Op {
180        let id = Rc::as_ptr(e) as usize;
181        if let Some((_, op)) = self.callees.borrow().get(&id) {
182            return op.clone();
183        }
184        let op: Op = if let Expr::Member { x, name, .. } = &**e {
185            let base = self.callee(x);
186            let name = name.clone();
187            Rc::new(move |eng, sc| {
188                let x = base(eng, sc)?;
189                match &x {
190                    Value::Std(p) => {
191                        let mut p = (**p).clone();
192                        p.push(name.clone());
193                        Ok(Value::Std(Rc::new(p)))
194                    }
195                    Value::NsRef(ns) => eng.ns_value(ns, &name, sc),
196                    _ => eng.access(&eng.deref(x)?, &name),
197                }
198            })
199        } else {
200            self.get(e)
201        };
202        self.callees
203            .borrow_mut()
204            .insert(id, (e.clone(), op.clone()));
205        op
206    }
207
208    pub(crate) fn nav(&self, e: &Rc<Expr>) -> Op {
209        let id = Rc::as_ptr(e) as usize;
210        if let Some((_, op)) = self.navigations.borrow().get(&id) {
211            return op.clone();
212        }
213        let op: Op = match &**e {
214            Expr::Paren(x) => self.nav(x),
215            Expr::If { c, t, f } => {
216                let (c, t, f) = (self.get(c), self.nav(t), self.nav(f));
217                Rc::new(move |eng, sc| {
218                    if eng.truthy(&c(eng, sc)?)? {
219                        t(eng, sc)
220                    } else {
221                        f(eng, sc)
222                    }
223                })
224            }
225            Expr::Member { x, name, .. } => {
226                let (base, name) = (self.nav(x), name.clone());
227                Rc::new(move |eng, sc| {
228                    let raw = base(eng, sc)?;
229                    if let Value::Segs(p) = raw {
230                        let mut p = (*p).clone();
231                        p.push(Seg::Name(name.as_str().into()));
232                        return Ok(Value::Segs(Rc::new(p)));
233                    }
234                    let x = eng.deref(raw)?;
235                    let v = eng.access(&x, &name)?;
236                    if v.is_absent() {
237                        if let Value::Rec(r) = x {
238                            let mut p = r.borrow().path.to_vec();
239                            p.push(Seg::Name(name.as_str().into()));
240                            return Ok(Value::Segs(Rc::new(p)));
241                        }
242                    }
243                    Ok(v)
244                })
245            }
246            Expr::Index { x, i } => {
247                let (base, index, ordinary) = (self.nav(x), self.get(i), self.get(e));
248                Rc::new(move |eng, sc| {
249                    let raw = base(eng, sc)?;
250                    let i = index(eng, sc)?;
251                    if let Value::Segs(p) = raw {
252                        let mut p = (*p).clone();
253                        p.push(match &i {
254                            Value::Str(k) => Seg::Key(k.to_rc()),
255                            _ => Seg::Idx(to_index(&i)?.max(0) as usize),
256                        });
257                        return Ok(Value::Segs(Rc::new(p)));
258                    }
259                    let x = eng.deref(raw)?;
260                    match &x {
261                        Value::Arr(a) => {
262                            let n = to_index(&i)?;
263                            let b = a.borrow();
264                            if n >= 0 && (n as usize) < b.items.len() {
265                                Ok(b.items[n as usize].clone())
266                            } else {
267                                let mut p = b.path.to_vec();
268                                p.push(Seg::Idx(n.max(0) as usize));
269                                Ok(Value::Segs(Rc::new(p)))
270                            }
271                        }
272                        Value::Map(m) => {
273                            let Value::Str(k) = &i else {
274                                return err("map index needs a string");
275                            };
276                            let b = m.borrow();
277                            match b.get(k) {
278                                Some(v) => Ok(v.clone()),
279                                None => {
280                                    let mut p = b.path.to_vec();
281                                    p.push(Seg::Key(k.to_rc()));
282                                    Ok(Value::Segs(Rc::new(p)))
283                                }
284                            }
285                        }
286                        Value::Rec(r) => {
287                            let Value::Str(k) = &i else {
288                                return err("index on record needs a string");
289                            };
290                            let v = eng.access(&x, k)?;
291                            if v.is_absent() {
292                                let mut p = r.borrow().path.to_vec();
293                                p.push(Seg::Name(k.to_rc()));
294                                Ok(Value::Segs(Rc::new(p)))
295                            } else {
296                                Ok(v)
297                            }
298                        }
299                        _ => ordinary(eng, sc),
300                    }
301                })
302            }
303            _ => self.get(e),
304        };
305        self.navigations
306            .borrow_mut()
307            .insert(id, (e.clone(), op.clone()));
308        op
309    }
310
311    fn compile(&self, e: &Rc<Expr>) -> Op {
312        match &**e {
313            Expr::Lit(v) => {
314                let v = v.clone();
315                Rc::new(move |_, _| Ok(v.clone()))
316            }
317            Expr::Pattern(s) => {
318                let s = SharedText::from(s.as_str());
319                Rc::new(move |_, _| Ok(Value::Pat(s.clone())))
320            }
321            Expr::UnitLit { num, unit } => {
322                let (num, unit) = (*num, unit.clone());
323                Rc::new(move |eng, _| {
324                    let (key, to_base) = eng.env.unit_info(&unit).or_else(err)?;
325                    Ok(Value::quantity(key, num * to_base))
326                })
327            }
328            Expr::Paren(x) => self.get(x),
329            Expr::Name(n) => {
330                let n = n.clone();
331                Rc::new(move |eng, sc| eng.name_value(&n, sc))
332            }
333            Expr::Ctx(n) => {
334                let n = n.clone();
335                Rc::new(move |eng, sc| eng.context_value(&n, sc))
336            }
337            Expr::Referrers { ty, member } => {
338                let (ty, member) = (ty.clone(), member.clone());
339                Rc::new(move |eng, sc| eng.referrers(&ty, &member, sc))
340            }
341            Expr::Spread(_) => Rc::new(|_, _| err("spread outside an object literal")),
342            Expr::Obj(entries) => {
343                let entries = entries.clone();
344                Rc::new(move |_, sc| {
345                    Ok(Value::PreObj(Rc::new(
346                        entries
347                            .iter()
348                            .map(|(k, e)| (k.clone(), pre(e, sc)))
349                            .collect(),
350                    )))
351                })
352            }
353            Expr::Arr(items) => {
354                let items = items.clone();
355                Rc::new(move |_, sc| {
356                    Ok(Value::PreArr(Rc::new(
357                        items.iter().map(|(sp, e)| (*sp, pre(e, sc))).collect(),
358                    )))
359                })
360            }
361            Expr::Template(parts) => {
362                let parts: Vec<_> = parts
363                    .iter()
364                    .map(|p| match p {
365                        TPart::Text(s) => Ok(s.clone()),
366                        TPart::Expr(e) => Err(self.get(e)),
367                    })
368                    .collect();
369                Rc::new(move |eng, sc| {
370                    let mut out = String::new();
371                    for p in &parts {
372                        match p {
373                            Ok(s) => out.push_str(s),
374                            Err(op) => out.push_str(&eng.to_str(&op(eng, sc)?)?),
375                        }
376                    }
377                    Ok(Value::Str(out.into()))
378                })
379            }
380            Expr::If { c, t, f } => {
381                let (c, t, f) = (self.get(c), self.get(t), self.get(f));
382                Rc::new(move |eng, sc| {
383                    if eng.truthy(&c(eng, sc)?)? {
384                        t(eng, sc)
385                    } else {
386                        f(eng, sc)
387                    }
388                })
389            }
390            Expr::Un { op, x } => {
391                let (op, x) = (op.clone(), self.get(x));
392                Rc::new(move |eng, sc| {
393                    let x = x(eng, sc)?;
394                    match op.as_str() {
395                        "!" => Ok(Value::Bool(!eng.truthy(&x)?)),
396                        "-" => match x {
397                            Value::Absent => err("absent consumed"),
398                            Value::Q(mut q) => {
399                                q.value = -q.value;
400                                Ok(Value::Q(q))
401                            }
402                            Value::Int(i) => Ok(Value::Int(-i)),
403                            Value::Float(f) => Ok(Value::Float(-f)),
404                            _ => err("bad operand for unary -"),
405                        },
406                        "~" => match x {
407                            Value::Int(i) => Ok(Value::Int(&(-i) - 1)),
408                            _ => err("bad operand for ~"),
409                        },
410                        _ => err("un"),
411                    }
412                })
413            }
414            Expr::Bin { op, l, r } => {
415                if op == "|>" {
416                    let (fun, mut args) = match &**r {
417                        Expr::Call { fun, args } => (fun.clone(), args.clone()),
418                        _ => (r.clone(), vec![]),
419                    };
420                    args.insert(0, l.clone());
421                    return self.get(&Rc::new(Expr::Call { fun, args }));
422                }
423                let (op, l, r) = (op.clone(), self.get(l), self.get(r));
424                match op.as_str() {
425                    "&&" => Rc::new(move |eng, sc| {
426                        Ok(Value::Bool(
427                            eng.truthy(&l(eng, sc)?)? && eng.truthy(&r(eng, sc)?)?,
428                        ))
429                    }),
430                    "||" => Rc::new(move |eng, sc| {
431                        Ok(Value::Bool(
432                            eng.truthy(&l(eng, sc)?)? || eng.truthy(&r(eng, sc)?)?,
433                        ))
434                    }),
435                    "??" => Rc::new(move |eng, sc| {
436                        let v = l(eng, sc)?;
437                        if matches!(v, Value::Absent | Value::Null) {
438                            r(eng, sc)
439                        } else {
440                            Ok(v)
441                        }
442                    }),
443                    _ => Rc::new(move |eng, sc| eng.apply_bin(&op, l(eng, sc)?, r(eng, sc)?)),
444                }
445            }
446            Expr::Member { x, name, safe } => {
447                let (base, name, safe) = (self.get(x), name.clone(), *safe);
448                Rc::new(move |eng, sc| {
449                    let x = base(eng, sc)?;
450                    if let Value::NsRef(ns) = &x {
451                        return eng.ns_value(ns, &name, sc);
452                    }
453                    if safe && matches!(x, Value::Null | Value::Absent) {
454                        return Ok(Value::Absent);
455                    }
456                    eng.access(&eng.deref(x)?, &name)
457                })
458            }
459            Expr::Index { x, i } => {
460                let (base, index) = (self.get(x), self.get(i));
461                Rc::new(move |eng, sc| {
462                    let x = eng.mat_val(base(eng, sc)?)?;
463                    let i = index(eng, sc)?;
464                    match &x {
465                        Value::Arr(a) => {
466                            let n = to_index(&i)?;
467                            let a = a.borrow();
468                            if n < 0 || n as usize >= a.items.len() {
469                                return err_code(format!("index {n} out of bounds"), "E5005");
470                            }
471                            Ok(a.items[n as usize].clone())
472                        }
473                        Value::Map(m) => match &i {
474                            Value::Str(k) => {
475                                Ok(m.borrow().get(k).cloned().unwrap_or(Value::Absent))
476                            }
477                            _ => Ok(Value::Absent),
478                        },
479                        Value::Rec(_) => match &i {
480                            Value::Str(k) => eng.access(&x, k),
481                            _ => err("index on record needs a string"),
482                        },
483                        _ => err("index on non-collection"),
484                    }
485                })
486            }
487            Expr::Call { fun, args } => {
488                let (fun, args) = (
489                    self.callee(fun),
490                    args.iter().map(|a| self.get(a)).collect::<Vec<_>>(),
491                );
492                Rc::new(move |eng, sc| {
493                    let args = args.iter().map(|a| a(eng, sc)).collect::<R<Vec<_>>>()?;
494                    eng.call(&fun(eng, sc)?, args, sc)
495                })
496            }
497            Expr::Lambda { params, body } => {
498                self.get(body);
499                let (params, body) = (params.clone(), body.clone());
500                Rc::new(move |_, sc| {
501                    Ok(Value::Clo(Rc::new(Closure {
502                        params: params.clone(),
503                        body: body.clone(),
504                        scope: sc.clone(),
505                    })))
506                })
507            }
508            Expr::With { base, patch } => {
509                let (base, patch) = (self.get(base), self.get(patch));
510                Rc::new(move |eng, sc| {
511                    let v = eng.deref(base(eng, sc)?)?;
512                    if !matches!(v, Value::PreObj(_) | Value::Map(_) | Value::Rec(_)) {
513                        return err("with on non-record");
514                    }
515                    eng.with_value(v, patch(eng, sc)?)
516                })
517            }
518            Expr::Match { subject, arms } => {
519                let subject = self.get(subject);
520                let arms: Vec<_> = arms
521                    .iter()
522                    .map(|a| (a.v.clone(), a.ty.clone(), self.get(&a.body)))
523                    .collect();
524                Rc::new(move |eng, sc| {
525                    let v = eng.deref(subject(eng, sc)?)?;
526                    let run = |name: &str, op: &Op| {
527                        op(eng, &sc.with_locals(sc.locals.with(name.into(), v.clone())))
528                    };
529                    let mut fallback = None;
530                    for (name, ty, op) in &arms {
531                        let Some(ty) = ty else {
532                            fallback = Some((name, op));
533                            continue;
534                        };
535                        let menv = sc.menv.as_ref().unwrap_or(&eng.env);
536                        let rt = menv.resolve(ty, None).or_else(err)?;
537                        if eng.member_of(&v, &rt, sc) {
538                            return run(name, op);
539                        }
540                    }
541                    if let Some((name, op)) = fallback {
542                        return run(name, op);
543                    }
544                    err("match: no arm matched")
545                })
546            }
547            Expr::Comp { head, clauses } => {
548                self.get(head);
549                #[cfg(feature = "runtime-diagnostics")]
550                let site = expr_diag::selected(e, true);
551                let (head, clauses) = (head.clone(), self.clauses(clauses));
552                Rc::new(move |eng, sc| {
553                    #[cfg(feature = "runtime-diagnostics")]
554                    let mut attempt = expr_diag::Attempt::begin(site, eng.phase.get());
555                    let evaluate = || {
556                        let mut items = vec![];
557                        visit(
558                            eng,
559                            sc,
560                            &clauses,
561                            &mut |scope| {
562                                items.push((false, pre(&head, scope)));
563                                Ok(())
564                            },
565                            #[cfg(feature = "runtime-diagnostics")]
566                            attempt.handle().map(|h| (h, 0)),
567                        )?;
568                        Ok(Value::PreArr(Rc::new(items)))
569                    };
570                    let result = evaluate();
571                    #[cfg(feature = "runtime-diagnostics")]
572                    attempt.finish(&result);
573                    result
574                })
575            }
576            Expr::MapComp { key, val, clauses } => {
577                let (key, val, clauses) = (self.get(key), self.get(val), self.clauses(clauses));
578                Rc::new(move |eng, sc| {
579                    let mut entries = vec![];
580                    let mut seen = KeysSeen::default();
581                    visit(
582                        eng,
583                        sc,
584                        &clauses,
585                        &mut |scope| {
586                            let Value::Str(k) = key(eng, scope)? else {
587                                return err("map key must be string");
588                            };
589                            let k = k.to_string();
590                            if !seen.admits(&entries, &k) {
591                                return err_code(format!("duplicate key {k}"), "E5004");
592                            }
593                            entries.push((k, val(eng, scope)?));
594                            Ok(())
595                        },
596                        #[cfg(feature = "runtime-diagnostics")]
597                        None,
598                    )?;
599                    Ok(Value::PreObj(Rc::new(entries)))
600                })
601            }
602        }
603    }
604
605    fn clauses(&self, clauses: &[ForClause]) -> Vec<Clause> {
606        clauses
607            .iter()
608            .map(|c| Clause {
609                name: c.v.as_str().into(),
610                iter: self.get(&c.iter),
611                filters: c.filters.iter().map(|f| self.get(f)).collect(),
612            })
613            .collect()
614    }
615}
616
617fn pre(expr: &Rc<Expr>, scope: &Scope) -> Value {
618    Value::PreVal(Rc::new(PreValV {
619        expr: {
620            #[cfg(feature = "runtime-diagnostics")]
621            crate::retention_diagnostics::preval(5);
622            expr.clone()
623        },
624        scope: scope.clone(),
625    }))
626}
627
628struct Clause {
629    name: Rc<str>,
630    iter: Op,
631    filters: Vec<Op>,
632}
633
634fn visit(
635    eng: &Engine,
636    sc: &Scope,
637    clauses: &[Clause],
638    emit: &mut dyn FnMut(&Scope) -> R<()>,
639    #[cfg(feature = "runtime-diagnostics")] trace: Option<(expr_diag::Handle, usize)>,
640) -> R<()> {
641    let Some(c) = clauses.first() else {
642        emit(sc)?;
643        #[cfg(feature = "runtime-diagnostics")]
644        expr_diag::emitted(trace.map(|(h, _)| h));
645        return Ok(());
646    };
647    #[cfg(feature = "runtime-diagnostics")]
648    if let Some((h, i)) = trace {
649        expr_diag::clause(Some(h), i, 0);
650    }
651    for item in eng.iterate(&(c.iter)(eng, sc)?)? {
652        #[cfg(feature = "runtime-diagnostics")]
653        if let Some((h, i)) = trace {
654            expr_diag::clause(Some(h), i, 1);
655        }
656        let next = sc.with_locals(sc.locals.with(c.name.clone(), item));
657        let mut keep = true;
658        for f in &c.filters {
659            #[cfg(feature = "runtime-diagnostics")]
660            if let Some((h, i)) = trace {
661                expr_diag::clause(Some(h), i, 2);
662            }
663            if !eng.truthy(&f(eng, &next)?)? {
664                #[cfg(feature = "runtime-diagnostics")]
665                if let Some((h, i)) = trace {
666                    expr_diag::clause(Some(h), i, 3);
667                }
668                keep = false;
669                break;
670            }
671        }
672        if keep {
673            #[cfg(feature = "runtime-diagnostics")]
674            if let Some((h, i)) = trace {
675                expr_diag::clause(Some(h), i, 4);
676            }
677            visit(
678                eng,
679                &next,
680                &clauses[1..],
681                emit,
682                #[cfg(feature = "runtime-diagnostics")]
683                trace.map(|(h, i)| (h, i + 1)),
684            )?;
685        }
686    }
687    Ok(())
688}