Skip to main content

dive_eval/
context.rs

1//! Admission of public evaluator inputs, without executing expressions or callbacks.
2
3use std::collections::HashSet;
4use std::fmt;
5use std::sync::Arc;
6
7use dive_ir::{Arg, DefId, DefScope, Expr, ExprId, OpRef};
8use dive_value::Interner;
9
10use crate::{ConstBinding, EvalError, Evaluator, Model, Scope};
11
12/// A malformed public evaluator input. Numeric IDs are relative to the supplied IR;
13/// equal indices alone cannot establish which IR a caller obtained them from.
14#[derive(Clone, Debug, PartialEq, Eq)]
15pub struct ContextError {
16    kind: ContextErrorKind,
17    detail: String,
18}
19
20/// Stable classifications for context admission failures.
21#[derive(Clone, Copy, Debug, PartialEq, Eq)]
22#[non_exhaustive]
23pub enum ContextErrorKind {
24    /// An arena ID does not exist in the supplied IR.
25    UnknownId,
26    /// A definition, constant or operator argument has inconsistent arity.
27    Arity,
28    /// An override chain contains a nontrivial cycle.
29    RedirectCycle,
30    /// A captured scope or deferred value belongs to another IR or name table.
31    ForeignContext,
32    /// The IR or its binding table has an inconsistent shape.
33    Structure,
34}
35
36impl ContextError {
37    pub(crate) fn new(kind: ContextErrorKind, detail: impl Into<String>) -> Self {
38        Self {
39            kind,
40            detail: detail.into(),
41        }
42    }
43    /// The typed failure category.
44    #[must_use]
45    pub const fn kind(&self) -> ContextErrorKind {
46        self.kind
47    }
48    /// A stable diagnostic code independent of the message text.
49    #[must_use]
50    pub const fn code(&self) -> &'static str {
51        match self.kind {
52            ContextErrorKind::UnknownId => "DIVE-EVAL-C001",
53            ContextErrorKind::Arity => "DIVE-EVAL-C002",
54            ContextErrorKind::RedirectCycle => "DIVE-EVAL-C003",
55            ContextErrorKind::ForeignContext => "DIVE-EVAL-C004",
56            ContextErrorKind::Structure => "DIVE-EVAL-C005",
57        }
58    }
59    /// What failed admission, without formatting or evaluating user values.
60    #[must_use]
61    pub fn detail(&self) -> &str {
62        &self.detail
63    }
64}
65impl fmt::Display for ContextError {
66    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
67        write!(f, "{}: {}", self.code(), self.detail)
68    }
69}
70impl std::error::Error for ContextError {}
71impl From<ContextError> for EvalError {
72    fn from(error: ContextError) -> Self {
73        Self::unsupported(format!("invalid evaluator context ({error})"))
74    }
75}
76
77type CResult<T> = Result<T, ContextError>;
78
79/// Admits a public IR arena without creating an evaluator, interning literals,
80/// evaluating expressions or invoking caller code. Uses the same structural
81/// authority as evaluator construction with empty constant/override bindings.
82///
83/// # Errors
84/// A typed malformed arena or bounded structural admission refusal. Numeric IDs
85/// remain relative to this arena; this does not certify their foreign provenance.
86///
87/// ```
88/// use std::sync::Arc;
89/// let analysis = dive_sema::analyze_source("M.tla",
90///     "---- MODULE M ----\nVARIABLE x\nInit == x = TRUE\n====\n", &Default::default());
91/// let ir = Arc::new(dive_ir::lower(&analysis).expect("IR"));
92/// dive_eval::validate_ir(&ir).expect("well-formed arena");
93/// ```
94pub fn validate_ir(ir: &Arc<dive_ir::Ir>) -> CResult<()> {
95    validate(&mut Model::new(ir.clone()))
96}
97
98fn unknown(what: impl Into<String>) -> ContextError {
99    ContextError::new(ContextErrorKind::UnknownId, what)
100}
101
102#[allow(
103    clippy::too_many_lines,
104    reason = "the ordered admission checks are reviewed together before any interning or callback"
105)]
106pub(crate) fn validate(model: &mut Model) -> CResult<()> {
107    let ir = &model.ir;
108    if ir.modules().get(ir.root().index()).is_none() {
109        return Err(unknown("root module"));
110    }
111    for module in ir.modules() {
112        if module
113            .parent
114            .is_some_and(|p| p.index() >= ir.modules().len())
115            || module
116                .extends
117                .iter()
118                .any(|p| p.index() >= ir.modules().len())
119            || module
120                .assumptions
121                .iter()
122                .chain(&module.theorems)
123                .any(|p| p.index() >= ir.defs().len())
124            || module
125                .tlc_constants
126                .iter()
127                .any(|p| p.index() >= ir.decls().len())
128            || module.context.iter().any(|(_, s)| match s {
129                dive_ir::Symbol::Def(d) => d.index() >= ir.defs().len(),
130                dive_ir::Symbol::Decl(d) => d.index() >= ir.decls().len(),
131                dive_ir::Symbol::Instance => false,
132            })
133        {
134            return Err(unknown("module references"));
135        }
136    }
137    for decl in ir.decls() {
138        if decl.module.index() >= ir.modules().len()
139            || decl.var.is_some_and(|v| v.index() >= ir.vars().len())
140            || decl
141                .constant
142                .is_some_and(|c| c.index() >= ir.consts().len())
143        {
144            return Err(unknown("declaration references"));
145        }
146    }
147    if ir.tlc_var_order().len() != ir.vars().len()
148        || ir
149            .tlc_var_order()
150            .iter()
151            .map(|v| v.index())
152            .collect::<HashSet<_>>()
153            .len()
154            != ir.vars().len()
155        || ir
156            .tlc_var_order()
157            .iter()
158            .any(|v| v.index() >= ir.vars().len())
159    {
160        return Err(ContextError::new(
161            ContextErrorKind::Structure,
162            "TLC variable order",
163        ));
164    }
165    for def in ir.defs() {
166        if def.params.len() > def.frame.len() {
167            return Err(ContextError::new(
168                ContextErrorKind::Arity,
169                "parameters exceed frame slots",
170            ));
171        }
172        let parent = match def.scope {
173            DefScope::TopLevel => None,
174            DefScope::Local { parent }
175            | DefScope::Inline { parent }
176            | DefScope::LetValue { parent, .. } => Some(parent),
177        };
178        if parent.is_some_and(|d| d.index() >= ir.defs().len())
179            || def.source.is_some_and(|d| d.index() >= ir.defs().len())
180            || def.frame.iter().any(|slot| matches!(slot.kind, dive_ir::SlotKind::LetValue(d) if d.index() >= ir.defs().len()))
181        { return Err(unknown("definition frame references")); }
182        if def.recursive && matches!(def.scope, DefScope::Inline { .. }) {
183            return Err(ContextError::new(
184                ContextErrorKind::Structure,
185                "recursive inline frame",
186            ));
187        }
188    }
189    // Reject malformed trees before the existing frame-aware structural walk.
190    for (i, node) in ir.nodes().iter().enumerate() {
191        if let Expr::Apply { callee, args } = &node.expr {
192            let expected = match callee {
193                OpRef::Def(d) => Some(
194                    ir.defs()
195                        .get(d.index())
196                        .ok_or_else(|| unknown("application definition"))?
197                        .params
198                        .len(),
199                ),
200                OpRef::Const(c) => Some(
201                    ir.consts()
202                        .get(c.index())
203                        .and_then(|d| ir.decls().get(d.index()))
204                        .ok_or_else(|| unknown("application constant"))?
205                        .arity as usize,
206                ),
207                OpRef::Subst(d) => Some(
208                    ir.decls()
209                        .get(d.index())
210                        .ok_or_else(|| unknown("application substitution"))?
211                        .arity as usize,
212                ),
213                _ => None,
214            };
215            if expected.is_some_and(|n| n != args.len()) {
216                return Err(ContextError::new(
217                    ContextErrorKind::Arity,
218                    "IR application argument count",
219                ));
220            }
221        }
222        if node
223            .expr
224            .try_for_each_child(|e| if e.index() >= i { Err(()) } else { Ok(()) })
225            .is_err()
226        {
227            return Err(ContextError::new(
228                ContextErrorKind::Structure,
229                "expression child is not older than its parent",
230            ));
231        }
232    }
233    // Duplicate child references can turn a finite arena into an exponential
234    // walk. Admit tree ownership before walking any lexical frame expansion.
235    let mut parents = vec![false; ir.nodes().len()];
236    let mut claim = |expr: ExprId| -> CResult<()> {
237        let parent = parents
238            .get_mut(expr.index())
239            .ok_or_else(|| unknown("expression body or child"))?;
240        if std::mem::replace(parent, true) {
241            return Err(ContextError::new(
242                ContextErrorKind::Structure,
243                "expression has multiple parents",
244            ));
245        }
246        Ok(())
247    };
248    for def in ir.defs() {
249        claim(def.body)?;
250    }
251    for node in ir.nodes() {
252        node.expr.try_for_each_child(&mut claim)?;
253    }
254    frame_expansion(ir)?;
255    let (owners, _) = frame_metadata(ir);
256    for (i, node) in ir.nodes().iter().enumerate() {
257        let frame = ir
258            .defs()
259            .get(owners[i].index())
260            .ok_or_else(|| unknown("expression frame"))?;
261        let bounds: &[dive_ir::Bound] = match &node.expr {
262            Expr::Quant { bounds, .. }
263            | Expr::SetMap { bounds, .. }
264            | Expr::FcnCons { bounds, .. }
265            | Expr::RecFcn { bounds, .. } => bounds,
266            Expr::SetFilter { bound, .. } => std::slice::from_ref(bound),
267            _ => &[],
268        };
269        if bounds
270            .iter()
271            .flat_map(|b| b.vars.iter())
272            .any(|s| s.index() >= frame.frame.len())
273            || matches!(&node.expr, Expr::TemporalQuant { vars, .. } if vars.iter().any(|s| s.index() >= frame.frame.len()))
274            || matches!(&node.expr, Expr::RecFcn { name, .. } if name.index() >= frame.frame.len())
275        {
276            return Err(unknown("binder frame slot"));
277        }
278    }
279    let violations = dive_ir::validate::check(ir);
280    if let Some(first) = violations.first() {
281        return Err(ContextError::new(ContextErrorKind::Structure, first));
282    }
283    if model.constants.len() != ir.consts().len() {
284        return Err(ContextError::new(
285            ContextErrorKind::Structure,
286            "constant binding table length",
287        ));
288    }
289    for (&source, &target) in &model.redirects {
290        let a = ir
291            .defs()
292            .get(source.index())
293            .ok_or_else(|| unknown("redirect source"))?;
294        let b = ir
295            .defs()
296            .get(target.index())
297            .ok_or_else(|| unknown("redirect target"))?;
298        if a.params
299            .iter()
300            .map(|p| p.arity)
301            .ne(b.params.iter().map(|p| p.arity))
302        {
303            return Err(ContextError::new(
304                ContextErrorKind::Arity,
305                "redirect signature",
306            ));
307        }
308    }
309    let mut normalized = std::collections::HashMap::new();
310    for &source in model.redirects.keys() {
311        let mut seen = HashSet::new();
312        let mut target = source;
313        while let Some(&next) = model.redirects.get(&target) {
314            if next == target {
315                break;
316            }
317            if !seen.insert(target) {
318                return Err(ContextError::new(
319                    ContextErrorKind::RedirectCycle,
320                    "definition redirect cycle",
321                ));
322            }
323            target = next;
324        }
325        normalized.insert(source, target);
326    }
327    for (i, binding) in model.constants.iter().enumerate() {
328        match binding {
329            Some(ConstBinding::Def(d)) => {
330                let def = ir
331                    .defs()
332                    .get(d.index())
333                    .ok_or_else(|| unknown("constant definition binding"))?;
334                if def.params.len() != ir.decl(ir.consts()[i]).arity as usize {
335                    return Err(ContextError::new(
336                        ContextErrorKind::Arity,
337                        "constant definition arity",
338                    ));
339                }
340            }
341            Some(ConstBinding::Value(_)) if ir.decl(ir.consts()[i]).arity != 0 => {
342                return Err(ContextError::new(
343                    ContextErrorKind::Arity,
344                    "parameterized constant bound to a value",
345                ));
346            }
347            Some(ConstBinding::Value(_)) | None => {}
348        }
349    }
350    for &d in model.def_values.keys() {
351        let def = ir
352            .defs()
353            .get(d.index())
354            .ok_or_else(|| unknown("definition value binding"))?;
355        if !def.params.is_empty() {
356            return Err(ContextError::new(
357                ContextErrorKind::Arity,
358                "parameterized definition bound to a value",
359            ));
360        }
361    }
362    model.redirects = normalized;
363    Ok(())
364}
365
366impl Evaluator {
367    pub(crate) fn admit_def(&self, d: DefId) -> crate::Result<&dive_ir::Def> {
368        self.core
369            .ir
370            .defs()
371            .get(d.index())
372            .ok_or_else(|| unknown("definition ID").into())
373    }
374    pub(crate) fn admit_expr(&self, e: ExprId) -> crate::Result<()> {
375        if self.core.ir.nodes().get(e.index()).is_none() {
376            return Err(unknown("expression ID").into());
377        }
378        Ok(())
379    }
380    /// Verifies that a scope was created by this evaluator.
381    ///
382    /// # Errors
383    /// A scope created by another evaluator, even one over an equal IR.
384    pub fn validate_scope(&self, scope: &Scope) -> crate::Result<()> {
385        if !Arc::ptr_eq(&self.core.ir, &scope.owner)
386            || !Arc::ptr_eq(&self.core.names, &scope.names)
387            || !std::sync::Weak::ptr_eq(&scope.context, &Arc::downgrade(&self.core))
388        {
389            return Err(ContextError::new(
390                ContextErrorKind::ForeignContext,
391                "scope belongs to another evaluator",
392            )
393            .into());
394        }
395        Ok(())
396    }
397    pub(crate) fn admit_parent(
398        &self,
399        scope: &Scope,
400        def: DefId,
401    ) -> crate::Result<Option<Arc<crate::env::Frame>>> {
402        let d = self.admit_def(def)?;
403        let (parent, depth) = match d.scope {
404            DefScope::TopLevel => return Ok(None),
405            DefScope::Local { parent } | DefScope::Inline { parent } => {
406                (parent, d.depth.saturating_sub(1))
407            }
408            DefScope::LetValue { parent, .. } => (parent, d.depth),
409        };
410        let frame = scope
411            .env
412            .frame_at_depth(depth)
413            .filter(|f| f.def == parent)
414            .ok_or_else(|| {
415                ContextError::new(
416                    ContextErrorKind::Structure,
417                    "missing or incompatible enclosing frame",
418                )
419            })?;
420        Ok(Some(frame.clone()))
421    }
422    pub(crate) fn admit_args(&self, scope: &Scope, def: DefId, args: &[Arg]) -> crate::Result<()> {
423        self.validate_scope(scope)?;
424        let d = self.admit_def(def)?;
425        if args.len() != d.params.len() {
426            return Err(
427                ContextError::new(ContextErrorKind::Arity, "operator argument count").into(),
428            );
429        }
430        for (arg, param) in args.iter().zip(&d.params) {
431            let arity = match arg {
432                Arg::Expr { expr, .. } => {
433                    self.admit_scoped_expr(scope, *expr)?;
434                    0
435                }
436                Arg::Op { op, .. } => match op {
437                    OpRef::Def(d) => {
438                        self.admit_parent(scope, *d)?;
439                        self.admit_def(*d)?.params.len()
440                    }
441                    OpRef::Const(c) => {
442                        self.core
443                            .ir
444                            .consts()
445                            .get(c.index())
446                            .and_then(|d| self.core.ir.decls().get(d.index()))
447                            .ok_or_else(|| unknown("operator constant"))?
448                            .arity as usize
449                    }
450                    OpRef::Subst(d) => {
451                        self.core
452                            .ir
453                            .decls()
454                            .get(d.index())
455                            .ok_or_else(|| unknown("substituted operator"))?
456                            .arity as usize
457                    }
458                    OpRef::Param(r) => {
459                        let frame = scope
460                            .env
461                            .frame_up(r.up)
462                            .ok_or_else(|| unknown("operator parameter frame"))?;
463                        let owner = self.admit_def(frame.def)?;
464                        if !matches!(frame.slots.get(r.slot.index()), Some(crate::env::Sv::Op(_))) {
465                            return Err(ContextError::new(
466                                ContextErrorKind::Structure,
467                                "operator parameter is not bound to an operator",
468                            )
469                            .into());
470                        }
471                        owner
472                            .params
473                            .get(r.slot.index())
474                            .ok_or_else(|| unknown("operator parameter slot"))?
475                            .arity as usize
476                    }
477                    OpRef::Std(op) => usize::try_from(op.java_arity()).map_err(|_| {
478                        ContextError::new(
479                            ContextErrorKind::Arity,
480                            "variadic standard operator argument",
481                        )
482                    })?,
483                    OpRef::Builtin(op) => {
484                        use dive_ir::BuiltinOp::{
485                            Always, BigUnion, Boolean, Domain, Enabled, Eventually, Not, PowerSet,
486                            Prime, String, Unchanged,
487                        };
488                        match op {
489                            Boolean | String => 0,
490                            PowerSet | BigUnion | Domain | Not | Prime | Enabled | Unchanged
491                            | Always | Eventually => 1,
492                            _ => 2,
493                        }
494                    }
495                    OpRef::Unbound(_) => {
496                        return Err(ContextError::new(
497                            ContextErrorKind::UnknownId,
498                            "unbound operator argument",
499                        )
500                        .into());
501                    }
502                },
503            };
504            if arity != param.arity as usize {
505                return Err(ContextError::new(
506                    ContextErrorKind::Arity,
507                    "operator argument signature",
508                )
509                .into());
510            }
511        }
512        Ok(())
513    }
514}
515
516fn frame_expansion(ir: &dive_ir::Ir) -> CResult<()> {
517    let mut incoming = vec![0_usize; ir.defs().len()];
518    let mut edges = vec![Vec::new(); ir.defs().len()];
519    for (i, def) in ir.defs().iter().enumerate() {
520        let mut work = vec![def.body];
521        while let Some(e) = work.pop() {
522            let node = ir
523                .nodes()
524                .get(e.index())
525                .ok_or_else(|| unknown("definition body"))?;
526            let mut add = |d: DefId| -> CResult<()> {
527                let count = incoming
528                    .get_mut(d.index())
529                    .ok_or_else(|| unknown("frame expansion definition"))?;
530                *count += 1;
531                edges[i].push(d.index());
532                Ok(())
533            };
534            if let Expr::Let { defs, .. } = &node.expr {
535                for &d in defs {
536                    add(d)?;
537                }
538            }
539            let inline = |d: DefId| {
540                ir.defs()
541                    .get(d.index())
542                    .is_some_and(|d| matches!(d.scope, DefScope::Inline { .. }))
543            };
544            if let Expr::Def(d) = &node.expr
545                && inline(*d)
546            {
547                add(*d)?;
548            }
549            for op in node.expr.op_refs() {
550                if let OpRef::Def(d) = op
551                    && inline(*d)
552                {
553                    add(*d)?;
554                }
555            }
556            node.expr.for_each_child(|child| work.push(child));
557        }
558    }
559    let mut ready: Vec<_> = incoming
560        .iter()
561        .enumerate()
562        .filter_map(|(i, &n)| (n == 0).then_some(i))
563        .collect();
564    let mut count = 0;
565    while let Some(i) = ready.pop() {
566        count += 1;
567        for &to in &edges[i] {
568            incoming[to] -= 1;
569            if incoming[to] == 0 {
570                ready.push(to);
571            }
572        }
573    }
574    if count != incoming.len() {
575        return Err(ContextError::new(
576            ContextErrorKind::Structure,
577            "cyclic lexical frame expansion",
578        ));
579    }
580    Ok(())
581}
582
583pub(crate) fn frame_metadata(ir: &dive_ir::Ir) -> (Vec<DefId>, Vec<bool>) {
584    let mut owners = vec![DefId(0); ir.nodes().len()];
585    for (i, def) in ir.defs().iter().enumerate() {
586        let mut owner = DefId(u32::try_from(i).unwrap_or(u32::MAX));
587        for _ in 0..ir.defs().len() {
588            match ir.defs().get(owner.index()).map(|d| d.scope) {
589                Some(DefScope::LetValue { parent, .. }) if parent != owner => owner = parent,
590                _ => break,
591            }
592        }
593        let mut work = vec![def.body];
594        while let Some(e) = work.pop() {
595            if let Some(o) = owners.get_mut(e.index()) {
596                *o = owner;
597            }
598            if let Some(node) = ir.nodes().get(e.index()) {
599                node.expr.for_each_child(|child| work.push(child));
600            }
601        }
602    }
603    let mut required = vec![false; ir.nodes().len()];
604    for (i, node) in ir.nodes().iter().enumerate() {
605        let local_def = |d: DefId| {
606            ir.defs()
607                .get(d.index())
608                .is_some_and(|d| d.scope != DefScope::TopLevel)
609        };
610        let local = matches!(
611            node.expr,
612            Expr::Local(_)
613                | Expr::Let { .. }
614                | Expr::Quant { .. }
615                | Expr::SetFilter { .. }
616                | Expr::SetMap { .. }
617                | Expr::FcnCons { .. }
618                | Expr::RecFcn { .. }
619                | Expr::TemporalQuant { .. }
620        ) || matches!(node.expr, Expr::Def(d) if local_def(d))
621            || node.expr.op_refs().iter().any(|op| {
622                matches!(op, OpRef::Param(_)) || matches!(op, OpRef::Def(d) if local_def(*d))
623            });
624        required[i] = local
625            || node
626                .expr
627                .try_for_each_child(|e| {
628                    if required.get(e.index()).copied().unwrap_or(true) {
629                        Err(())
630                    } else {
631                        Ok(())
632                    }
633                })
634                .is_err();
635    }
636    (owners, required)
637}
638
639impl Evaluator {
640    /// Whether `expr` may be evaluated in `scope`: the scope was created by
641    /// this evaluator and, when the expression needs a lexical frame, the
642    /// scope is that frame's.
643    ///
644    /// ```no_run
645    /// # fn check(ev: &dive_eval::Evaluator, scope: &dive_eval::Scope, e: dive_ir::ExprId) {
646    /// if !ev.admits_scoped_expr(scope, e) {
647    ///     // a foreign or mismatched scope
648    /// }
649    /// # }
650    /// ```
651    #[must_use]
652    pub fn admits_scoped_expr(&self, scope: &Scope, expr: ExprId) -> bool {
653        self.admit_scoped_expr(scope, expr).is_ok()
654    }
655
656    pub(crate) fn admit_scoped_expr(&self, scope: &Scope, expr: ExprId) -> crate::Result<()> {
657        self.validate_scope(scope)?;
658        self.admit_expr(expr)?;
659        if self.core.frame_required[expr.index()]
660            && scope.def() != self.core.frame_owners[expr.index()]
661        {
662            return Err(ContextError::new(
663                ContextErrorKind::Structure,
664                "expression requires another lexical frame",
665            )
666            .into());
667        }
668        Ok(())
669    }
670}
671
672impl Evaluator {
673    /// Checks that public model metadata still describes this evaluator's IR
674    /// and name table. Cloning the same Arcs is valid; substituting another arena
675    /// is not a certified binding, even when its numeric IDs happen to match.
676    ///
677    /// # Errors
678    /// A foreign IR or name table.
679    pub fn validate_model_context(
680        &self,
681        ir: &Arc<dive_ir::Ir>,
682        names: &Arc<Interner>,
683    ) -> CResult<()> {
684        if !Arc::ptr_eq(ir, &self.core.ir) || !Arc::ptr_eq(names, &self.core.names) {
685            return Err(ContextError::new(
686                ContextErrorKind::ForeignContext,
687                "model metadata belongs to another evaluator context",
688            ));
689        }
690        Ok(())
691    }
692    /// Admits a predicate's ID and lexical frame before interpreting it.
693    /// Closed expressions can be reused in any scope from the same IR.
694    ///
695    /// # Errors
696    /// A foreign scope, missing expression or incompatible lexical frame.
697    pub fn validate_predicate(&self, scope: &Scope, expr: ExprId) -> crate::Result<()> {
698        self.admit_scoped_expr(scope, expr)
699    }
700}