Skip to main content

dive_eval/
finite.rs

1//! Source projection of `SelectSeq` callbacks for the liveness planner and the
2//! trace validator's temporal lowering. Nothing here evaluates a callback.
3
4use crate::{ConstBinding, EvalError, Evaluator, Scope, SlotView, St};
5use dive_ir::{Arg, BuiltinOp, ConstId, DefScope, Effects, Expr, ExprId, Level, OpRef, StdOp};
6
7impl Evaluator {
8    /// Inspects an authoritative `SelectSeq` call without evaluating its sequence
9    /// or predicate. Returns the original sequence and callback/capture bodies
10    /// in their lexical scopes. Pure supported unary user callbacks qualify.
11    /// Callers independently check purity and scoped levels on every body.
12    ///
13    /// # Errors
14    /// Invalid ownership, unsupported callback contexts or exhausted work.
15    #[allow(
16        clippy::type_complexity,
17        reason = "original sequence plus lexical body projections; no opaque certificate"
18    )]
19    pub fn scope_selectseq_call(
20        &self,
21        scope: &Scope,
22        operator: &OpRef,
23        args: &[Arg],
24        work: &mut usize,
25    ) -> crate::Result<Option<(ExprId, Vec<(ExprId, Scope)>)>> {
26        let Some((sequence, bodies)) = self.selectseq_projection(scope, operator, args, work)?
27        else {
28            return Ok(None);
29        };
30        let initial = *work;
31        let mut guard = Guard {
32            evaluator: self,
33            limit: initial.div_ceil(64),
34            visits: 0,
35            configured_depth: 0,
36            query_allowed: true,
37        };
38        let result = guard.callback_sources(&bodies, 0);
39        *work = initial.saturating_sub(guard.visits);
40        if guard.visits > initial {
41            return Err(EvalError::resource_limit("SelectSeq callback work"));
42        }
43        result?;
44        Ok(Some((sequence, bodies)))
45    }
46
47    // Metadata only. Nested selection is inspected by the caller's same Guard,
48    // so neither a new callback nor a captured selector resets its work budget.
49    #[allow(
50        clippy::type_complexity,
51        reason = "same source projection as the public wrapper"
52    )]
53    fn selectseq_projection(
54        &self,
55        scope: &Scope,
56        operator: &OpRef,
57        args: &[Arg],
58        work: &mut usize,
59    ) -> crate::Result<Option<(ExprId, Vec<(ExprId, Scope)>)>> {
60        self.validate_scope(scope)?;
61        let standard = match operator {
62            OpRef::Std(s) => Some(*s),
63            OpRef::Def(d) => {
64                self.admit_def(*d)?;
65                if self.redirected(*d) != *d || self.is_value_override(*d) {
66                    return Ok(None);
67                }
68                self.ir().def(*d).std
69            }
70            _ => None,
71        };
72        if standard != Some(StdOp::SequencesSelectSeq) {
73            return Ok(None);
74        }
75        if self
76            .core
77            .std_redirects
78            .contains_key(&StdOp::SequencesSelectSeq)
79        {
80            return Err(EvalError::unsupported(
81                "SelectSeq configured standard target",
82            ));
83        }
84        let [Arg::Expr { expr: sequence, .. }, Arg::Op { op, .. }] = args else {
85            return Err(EvalError::unsupported(
86                "SelectSeq sequence/operator argument shape",
87            ));
88        };
89        self.admit_scoped_expr(scope, *sequence)?;
90        // Validate the reference before looking up the value. The existing
91        // resolver performs all definition/lexical/configured-origin checks.
92        *work = work
93            .checked_sub(self.core.consts.len().saturating_add(1))
94            .ok_or_else(|| EvalError::resource_limit("SelectSeq reference work"))?;
95        let Some(_) = self.scope_operator_analysis(scope, op)? else {
96            return Err(EvalError::unsupported("SelectSeq user callback target"));
97        };
98        let value = self.core.op_value(&scope.env, op)?;
99        let bodies = self.selectseq_sources(scope, value, work)?;
100        Ok(Some((*sequence, bodies)))
101    }
102
103    fn selectseq_sources(
104        &self,
105        scope: &Scope,
106        value: crate::env::OpVal,
107        work: &mut usize,
108    ) -> crate::Result<Vec<(ExprId, Scope)>> {
109        let (def, called) = self
110            .selectseq_value_analysis(scope, value, work)?
111            .ok_or_else(|| EvalError::unsupported("SelectSeq user callback target"))?;
112        if self.ir().def(def).params.len() != 1 {
113            return Err(EvalError::unsupported("SelectSeq unary value callback"));
114        }
115        let mut bodies = self
116            .operator_captures(&called, work, true)?
117            .ok_or_else(|| EvalError::unsupported("SelectSeq opaque/dynamic callback capture"))?;
118        *work = work
119            .checked_sub(1)
120            .ok_or_else(|| EvalError::resource_limit("SelectSeq body work"))?;
121        bodies.push((self.ir().def(def).body, called));
122        Ok(bodies)
123    }
124}
125
126/// Walks `SelectSeq` callback sources without evaluating values or domains.
127/// Effects, priming and opaque runtime providers remain explicit refusals.
128struct Guard<'a> {
129    evaluator: &'a Evaluator,
130    limit: usize,
131    visits: usize,
132    configured_depth: usize,
133    query_allowed: bool,
134}
135
136/// A successful-result kind, independent of effects, validity or finiteness.
137#[derive(Clone, Copy, PartialEq, Eq)]
138enum ResultKind {
139    NonString,
140    Unknown,
141}
142
143impl Guard<'_> {
144    fn kind_step(&mut self, depth: usize, work: usize) -> crate::Result<()> {
145        self.visits = self.visits.saturating_add(work);
146        if depth > 256 || self.visits > self.limit.saturating_mul(64).min(100_000) {
147            return Err(EvalError::resource_limit("finite binding traversal"));
148        }
149        Ok(())
150    }
151
152    // Only the actual unmodified native target can use Concat's result-kind
153    // rule. Operator parameters/configured/native-value admission stays separate.
154    fn concat_without_names(
155        &mut self,
156        scope: &Scope,
157        operator: &OpRef,
158        args: &[Arg],
159        depth: usize,
160    ) -> crate::Result<bool> {
161        self.kind_step(depth, 1)?;
162        let ev = self.evaluator;
163        ev.validate_scope(scope)?;
164        if ev.core.std_redirects.contains_key(&StdOp::SequencesConcat) {
165            return Ok(false);
166        }
167        // A native reference does not carry a configured-constant origin.
168        // Keep the existing conservative authority boundary without extending
169        // the separate operator-actual whitelist or inspecting stored values.
170        for binding in &ev.core.consts {
171            self.kind_step(depth, 1)?;
172            if let Some(ConstBinding::Def(def)) = binding
173                && ev.admit_def(ev.redirected(*def))?.std == Some(StdOp::SequencesConcat)
174            {
175                return Ok(false);
176            }
177        }
178        for def in ev.core.def_values.keys() {
179            self.kind_step(depth, 1)?;
180            if ev.admit_def(*def)?.std == Some(StdOp::SequencesConcat) {
181                return Ok(false);
182            }
183        }
184        let [Arg::Expr { expr: left, .. }, Arg::Expr { expr: right, .. }] = args else {
185            return Ok(false);
186        };
187        match operator {
188            OpRef::Std(StdOp::SequencesConcat) => {}
189            OpRef::Def(source) => {
190                let target = ev.admit_def(*source)?;
191                if ev.redirected(*source) != *source
192                    || ev.is_value_override(*source)
193                    || target.std != Some(StdOp::SequencesConcat)
194                    || target.scope != DefScope::TopLevel
195                    || target.recursive
196                    || target.params.len() != 2
197                    || target.params.iter().any(|parameter| parameter.arity != 0)
198                {
199                    return Ok(false);
200                }
201                ev.admit_args(scope, *source, args)?;
202            }
203            _ => return Ok(false),
204        }
205        ev.admit_scoped_expr(scope, *left)?;
206        ev.admit_scoped_expr(scope, *right)?;
207        let mut active = Vec::new();
208        if self.result_kind(scope, *left, depth + 1, &mut active)? == ResultKind::NonString {
209            return Ok(true);
210        }
211        Ok(self.result_kind(scope, *right, depth + 1, &mut active)? == ResultKind::NonString)
212    }
213
214    // Every retained owner remains live on the active path. Comparing only
215    // context identities never hashes a Value or consults a thunk result cache.
216    fn result_kind(
217        &mut self,
218        scope: &Scope,
219        expr: ExprId,
220        depth: usize,
221        active: &mut Vec<(ExprId, Scope)>,
222    ) -> crate::Result<ResultKind> {
223        self.kind_step(depth, active.len().saturating_add(1))?;
224        self.evaluator.admit_scoped_expr(scope, expr)?;
225        if scope.env.dynamic.at.is_some()
226            || active.iter().any(|(prior, captured)| {
227                *prior == expr
228                    && std::sync::Arc::ptr_eq(&captured.env.frame, &scope.env.frame)
229                    && captured.env.dynamic.cut == scope.env.dynamic.cut
230                    && match (&captured.env.dynamic.subst, &scope.env.dynamic.subst) {
231                        (None, None) => true,
232                        (Some(left), Some(right)) => std::sync::Arc::ptr_eq(left, right),
233                        _ => false,
234                    }
235            })
236        {
237            return Ok(ResultKind::Unknown);
238        }
239        let saved = active.len();
240        active.push((expr, scope.clone()));
241        let result = self.result_kind_inner(scope, expr, depth, active);
242        active.truncate(saved);
243        result.map_err(|error| error.at(expr))
244    }
245
246    // Constructor/result families are type facts even when their descendants
247    // would fail or have effects. The independent full Guard walk MUST remain.
248    fn result_kind_inner(
249        &mut self,
250        scope: &Scope,
251        expr: ExprId,
252        depth: usize,
253        active: &mut Vec<(ExprId, Scope)>,
254    ) -> crate::Result<ResultKind> {
255        let ev = self.evaluator;
256        match &ev.ir().node(expr).expr {
257            Expr::Bool(_)
258            | Expr::Num(_)
259            | Expr::Not(_)
260            | Expr::Junction { .. }
261            | Expr::Implies(_, _)
262            | Expr::Equiv(_, _)
263            | Expr::SetEnum(_)
264            | Expr::Tuple(_)
265            | Expr::Record(_)
266            | Expr::RecordSet(_)
267            | Expr::FcnSet { .. }
268            | Expr::FcnCons { .. }
269            | Expr::RecFcn { .. }
270            | Expr::SetMap { .. }
271            | Expr::SetFilter { .. }
272            | Expr::Cartesian(_)
273            | Expr::Quant {
274                kind: dive_ir::QuantKind::Forall | dive_ir::QuantKind::Exists,
275                ..
276            } => Ok(ResultKind::NonString),
277            Expr::Builtin { op, .. } if non_string_builtin(*op) => Ok(ResultKind::NonString),
278            Expr::If { then, other, .. } => {
279                let left = self.result_kind(scope, *then, depth + 1, active)?;
280                let right = self.result_kind(scope, *other, depth + 1, active)?;
281                Ok(join_kind(left, right))
282            }
283            Expr::Case { arms, other } => {
284                let mut result = ResultKind::NonString;
285                if arms.is_empty() {
286                    return Ok(ResultKind::Unknown);
287                }
288                for arm in arms {
289                    result = join_kind(
290                        result,
291                        self.result_kind(scope, arm.value, depth + 1, active)?,
292                    );
293                }
294                if let Some(other) = other {
295                    result = join_kind(result, self.result_kind(scope, *other, depth + 1, active)?);
296                }
297                Ok(result)
298            }
299            Expr::Label { body, .. } | Expr::Selected(body) => {
300                self.result_kind(scope, *body, depth + 1, active)
301            }
302            _ => self.result_context_kind(scope, expr, depth, active),
303        }
304    }
305
306    fn result_context_kind(
307        &mut self,
308        scope: &Scope,
309        expr: ExprId,
310        depth: usize,
311        active: &mut Vec<(ExprId, Scope)>,
312    ) -> crate::Result<ResultKind> {
313        let ev = self.evaluator;
314        match &ev.ir().node(expr).expr {
315            Expr::Let { body, defs } => {
316                self.kind_step(
317                    depth,
318                    defs.len().saturating_add(scope.env.frame.slots.len()),
319                )?;
320                self.result_kind(&ev.scope_let(scope, expr)?, *body, depth + 1, active)
321            }
322            Expr::Subst { body, bindings } => {
323                self.kind_step(depth, bindings.len())?;
324                if bindings.iter().any(|binding| {
325                    matches!(
326                        binding.value,
327                        Arg::Expr {
328                            pass: dive_ir::Pass::Strict,
329                            ..
330                        }
331                    )
332                }) {
333                    return Ok(ResultKind::Unknown);
334                }
335                self.result_kind(&ev.scope_subst(scope, expr)?, *body, depth + 1, active)
336            }
337            Expr::Local(local) => {
338                let frames = usize::try_from(local.up)
339                    .map_err(|_| EvalError::resource_limit("finite binding traversal"))?;
340                self.kind_step(depth, frames.saturating_add(1))?;
341                self.slot_kind(ev.scope_slot(scope, *local), depth, active)
342            }
343            Expr::Const(constant) => self.constant_kind(scope, *constant, depth, active),
344            Expr::SubstRef {
345                decl,
346                primed: false,
347            } => self.substitution_kind(scope, *decl, depth, active),
348            Expr::Def(def) => self.call_kind(scope, *def, &[], depth, active),
349            Expr::Apply {
350                callee: OpRef::Def(def),
351                args,
352            } => self.call_kind(scope, *def, args, depth, active),
353            _ => Ok(ResultKind::Unknown),
354        }
355    }
356
357    fn slot_kind(
358        &mut self,
359        slot: SlotView,
360        depth: usize,
361        active: &mut Vec<(ExprId, Scope)>,
362    ) -> crate::Result<ResultKind> {
363        match slot {
364            SlotView::Value(value) => Ok(value_kind(&value)),
365            SlotView::Lazy(body, source) => self.result_kind(&source, body, depth + 1, active),
366            _ => Ok(ResultKind::Unknown),
367        }
368    }
369
370    fn constant_kind(
371        &mut self,
372        scope: &Scope,
373        constant: ConstId,
374        depth: usize,
375        active: &mut Vec<(ExprId, Scope)>,
376    ) -> crate::Result<ResultKind> {
377        self.kind_step(depth, 1)?;
378        match self.evaluator.constant_binding(constant) {
379            Some(ConstBinding::Value(value)) => Ok(value_kind(&value)),
380            // Staying conservative about configured definition values avoids
381            // confusing direct-value lookup with redirected body evaluation.
382            Some(ConstBinding::Def(def)) => self.call_kind(scope, def, &[], depth, active),
383            None => Ok(ResultKind::Unknown),
384        }
385    }
386
387    fn substitution_kind(
388        &mut self,
389        scope: &Scope,
390        declaration: dive_ir::DeclId,
391        depth: usize,
392        active: &mut Vec<(ExprId, Scope)>,
393    ) -> crate::Result<ResultKind> {
394        self.kind_step(
395            depth,
396            scope
397                .env
398                .dynamic
399                .subst
400                .as_ref()
401                .map_or(1, |head| head.depth.saturating_add(1)),
402        )?;
403        match self.evaluator.scope_subst_slot(scope, declaration) {
404            SlotView::Unset => match self.evaluator.ir().decl(declaration).constant {
405                Some(constant) => self.constant_kind(scope, constant, depth, active),
406                None => Ok(ResultKind::Unknown),
407            },
408            slot => self.slot_kind(slot, depth, active),
409        }
410    }
411
412    fn call_kind(
413        &mut self,
414        scope: &Scope,
415        def: dive_ir::DefId,
416        args: &[Arg],
417        depth: usize,
418        active: &mut Vec<(ExprId, Scope)>,
419    ) -> crate::Result<ResultKind> {
420        self.kind_step(depth, 1)?;
421        let ev = self.evaluator;
422        let target = ev.admit_def(def)?;
423        if ev.redirected(def) != def
424            || ev.is_value_override(def)
425            || target.recursive
426            || target.std.is_some()
427        {
428            return Ok(ResultKind::Unknown);
429        }
430        self.kind_step(
431            depth,
432            target
433                .frame
434                .len()
435                .saturating_add(args.len())
436                .saturating_add(target.params.len()),
437        )?;
438        if target.params.iter().any(|parameter| parameter.arity != 0)
439            || args.iter().any(|arg| matches!(arg, Arg::Op { .. }))
440        {
441            return Ok(ResultKind::Unknown);
442        }
443        let called = ev.scope_apply(scope, def, args)?;
444        self.result_kind(&called, target.body, depth + 1, active)
445    }
446
447    fn callback_sources(&mut self, bodies: &[(ExprId, Scope)], depth: usize) -> crate::Result<()> {
448        for (body, captured) in bodies {
449            // Read original stored slots, never thunk result caches or provider
450            // methods. Captures are checked even when their source is unused.
451            self.native_storage(Some(captured), None)?;
452            self.walk_data(captured, *body, depth + 1)?;
453        }
454        Ok(())
455    }
456
457    // Direct configured origin is still available here; captured operator
458    // resolution deliberately does not acquire this route. Projection and
459    // unused-actual inspection do not evaluate values or binder domains.
460    fn configured_call(
461        &mut self,
462        scope: &Scope,
463        constant: ConstId,
464        args: &[Arg],
465        depth: usize,
466    ) -> crate::Result<(dive_ir::DefId, Scope)> {
467        let ev = self.evaluator;
468        let Some(ConstBinding::Def(def)) = ev.constant_binding(constant) else {
469            return Err(EvalError::unsupported(
470                "unbound/value-bound finite operator",
471            ));
472        };
473        let def = ev.redirected(def);
474        let target = ev.admit_def(def)?;
475        if ev
476            .ir()
477            .node(target.body)
478            .effects
479            .contains(Effects::USES_ENABLED)
480        {
481            return Err(EvalError::unsupported("configured ENABLED target"));
482        }
483        if target.scope != DefScope::TopLevel
484            || target.recursive
485            || target.std.is_some()
486            || ev.is_value_override(def)
487            || target.level > Level::Action
488            || target.params.iter().any(|p| p.arity != 0)
489        {
490            return Err(EvalError::unsupported("configured finite operator target"));
491        }
492        if args.len() > self.limit {
493            return Err(EvalError::resource_limit(
494                "configured finite operator arguments",
495            ));
496        }
497        let called = ev.scope_apply(scope, def, args)?;
498        let saved = (self.configured_depth, self.query_allowed);
499        self.configured_depth += 1;
500        self.query_allowed = false;
501        let result = (|| {
502            for arg in args {
503                let Arg::Expr { expr, .. } = arg else {
504                    return Err(EvalError::unsupported(
505                        "higher-order configured finite argument",
506                    ));
507                };
508                self.walk(scope, *expr, depth + 1)?;
509            }
510            // Source-only configured inspection includes the target, not just its actuals.
511            self.walk(&called, target.body, depth + 1)?;
512            Ok((def, called))
513        })();
514        (self.configured_depth, self.query_allowed) = saved;
515        result
516    }
517
518    fn operator_context(
519        &mut self,
520        scope: &Scope,
521        operator: &OpRef,
522        depth: usize,
523    ) -> crate::Result<()> {
524        let ceiling = self.limit.saturating_mul(64).min(100_000);
525        let mut remaining = ceiling.saturating_sub(self.visits);
526        let value = self.evaluator.core.op_value(&scope.env, operator)?;
527        let resolved = self
528            .evaluator
529            .selectseq_value_analysis(scope, value, &mut remaining);
530        self.visits = ceiling - remaining;
531        let (def, analysis) = resolved?.ok_or_else(|| {
532            EvalError::unsupported("SelectSeq higher-order/native callback context")
533        })?;
534        let saved = self.query_allowed;
535        self.query_allowed = false;
536        let result: crate::Result<()> = (|| {
537            let ceiling = self.limit.saturating_mul(64).min(100_000);
538            let mut remaining = ceiling.saturating_sub(self.visits);
539            let captures = self
540                .evaluator
541                .operator_captures(&analysis, &mut remaining, true);
542            self.visits = ceiling - remaining;
543            let captures = captures?
544                .ok_or_else(|| EvalError::unsupported("opaque finite operator context"))?;
545            for (body, captured) in captures {
546                self.walk(&captured, body, depth + 1)?;
547            }
548            self.walk(&analysis, self.evaluator.ir().def(def).body, depth + 1)
549        })();
550        self.query_allowed = saved;
551        result
552    }
553
554    // Newly admitted native formals may read cached lexical values. Source
555    // purity is insufficient to admit a deferred provider. Inspect storage,
556    // names and order before native evaluation.
557    #[allow(
558        clippy::too_many_lines,
559        reason = "bounded callback-free stored representation traversal"
560    )]
561    fn native_storage(
562        &mut self,
563        scope: Option<&Scope>,
564        value: Option<&dive_value::Value>,
565    ) -> crate::Result<()> {
566        use crate::env::{Dyn, Frame, OpVal, Sv};
567        use std::sync::Arc;
568        enum Work {
569            Frame(Arc<Frame>, usize),
570            Dynamic(Dyn, usize),
571            Slot(Sv, usize),
572            Value(dive_value::Value, usize),
573        }
574        let cap = self.limit.saturating_mul(64).min(50_000);
575        let mut work = Vec::new();
576        if let Some(scope) = scope {
577            work.push(Work::Frame(scope.env.frame.clone(), 0));
578            work.push(Work::Dynamic(scope.env.dynamic.clone(), 0));
579        }
580        if let Some(value) = value {
581            work.push(Work::Value(value.clone(), 0));
582        }
583        while let Some(item) = work.pop() {
584            self.visits = self.visits.saturating_add(1);
585            if self.visits > cap {
586                return Err(EvalError::resource_limit("native stored input work"));
587            }
588            let depth = match &item {
589                Work::Frame(_, d) | Work::Dynamic(_, d) | Work::Slot(_, d) | Work::Value(_, d) => {
590                    *d
591                }
592            };
593            if depth > 128 {
594                return Err(EvalError::resource_limit("native stored input depth"));
595            }
596            let room = |pending: usize, count: usize| -> crate::Result<()> {
597                if pending.saturating_add(count) > cap.saturating_sub(self.visits) {
598                    Err(EvalError::resource_limit("native stored input work"))
599                } else {
600                    Ok(())
601                }
602            };
603            match item {
604                Work::Frame(frame, _) => {
605                    room(
606                        work.len(),
607                        frame
608                            .slots
609                            .len()
610                            .saturating_add(usize::from(frame.parent.is_some())),
611                    )?;
612                    work.extend(
613                        frame
614                            .slots
615                            .iter()
616                            .cloned()
617                            .map(|v| Work::Slot(v, depth + 1)),
618                    );
619                    if let Some(parent) = &frame.parent {
620                        work.push(Work::Frame(parent.clone(), depth + 1));
621                    }
622                }
623                Work::Dynamic(dynamic, _) => {
624                    if dynamic.at.is_some() {
625                        return Err(EvalError::unsupported("native captured @ context"));
626                    }
627                    let mut link = dynamic.subst;
628                    while let Some(binding) = link.take() {
629                        self.visits = self.visits.saturating_add(1);
630                        if self.visits >= cap || work.len() >= cap.saturating_sub(self.visits) {
631                            return Err(EvalError::resource_limit("native stored input work"));
632                        }
633                        work.push(Work::Slot(binding.val.clone(), depth + 1));
634                        link.clone_from(&binding.next);
635                    }
636                }
637                Work::Slot(Sv::Val(v), _) => {
638                    room(work.len(), 1)?;
639                    work.push(Work::Value(v, depth + 1));
640                }
641                Work::Slot(Sv::Thunk(thunk), _) => {
642                    // The thunk's environment is inspected; its cached result
643                    // is not read.
644                    room(work.len(), 3)?;
645                    work.push(Work::Frame(thunk.env.frame.clone(), depth + 1));
646                    work.push(Work::Dynamic(thunk.env.dynamic.clone(), depth + 1));
647                }
648                Work::Slot(Sv::Op(op), _) => {
649                    let OpVal::Def {
650                        parent, dynamic, ..
651                    } = *op
652                    else {
653                        continue;
654                    };
655                    if dynamic.is_some() {
656                        return Err(EvalError::unsupported(
657                            "SelectSeq retained dynamic callback",
658                        ));
659                    }
660                    room(work.len(), usize::from(parent.is_some()))?;
661                    if let Some(parent) = parent {
662                        work.push(Work::Frame(parent, depth + 1));
663                    }
664                }
665                Work::Slot(Sv::Fcn(_), _) => {
666                    return Err(EvalError::unsupported("native captured opaque function"));
667                }
668                Work::Slot(_, _) => {}
669                Work::Value(value, _) => match value {
670                    dive_value::Value::Str(atom) | dive_value::Value::Model(atom) => {
671                        if self
672                            .evaluator
673                            .core
674                            .names
675                            .resolve(atom.tok())
676                            .is_none_or(|owned| owned.as_str() != atom.as_str())
677                        {
678                            return Err(EvalError::unsupported("native stored input namespace"));
679                        }
680                    }
681                    dive_value::Value::Fcn(function) => {
682                        if function.kind() != dive_value::FcnKind::Tuple
683                            && function.order() != self.evaluator.options().ctx.order
684                        {
685                            return Err(EvalError::unsupported("native stored input order"));
686                        }
687                        room(work.len(), function.len().saturating_mul(2))?;
688                        for (key, value) in function.iter() {
689                            work.push(Work::Value(key, depth + 1));
690                            work.push(Work::Value(value.clone(), depth + 1));
691                        }
692                    }
693                    dive_value::Value::Set(set) => {
694                        if set.order() != self.evaluator.options().ctx.order {
695                            return Err(EvalError::unsupported("native stored input order"));
696                        }
697                        let Some(elements) = set.stored_elements() else {
698                            return Err(EvalError::unsupported("native opaque/deferred input set"));
699                        };
700                        room(work.len(), elements.len())?;
701                        work.extend(elements.iter().cloned().map(|v| Work::Value(v, depth + 1)));
702                    }
703                    _ => {}
704                },
705            }
706        }
707        Ok(())
708    }
709
710    fn walk_data(&mut self, scope: &Scope, expr: ExprId, depth: usize) -> crate::Result<()> {
711        let saved = self.query_allowed;
712        self.query_allowed = false;
713        let result = self.walk(scope, expr, depth);
714        self.query_allowed = saved;
715        result
716    }
717
718    // Preserve the innermost inspected source, including a lazy actual or an
719    // INSTANCE body reached through a different lexical scope. This does not
720    // evaluate the expression or change the admission/work policy.
721    fn walk(&mut self, scope: &Scope, expr: ExprId, depth: usize) -> crate::Result<()> {
722        self.walk_inner(scope, expr, depth).map_err(|error| {
723            if self.evaluator.ir().nodes().get(expr.index()).is_some() {
724                error.at(expr)
725            } else {
726                error
727            }
728        })
729    }
730
731    #[allow(
732        clippy::too_many_lines,
733        reason = "explicit lexical binding and callback shape rules"
734    )]
735    fn walk_inner(&mut self, scope: &Scope, expr: ExprId, depth: usize) -> crate::Result<()> {
736        self.visits = self.visits.saturating_add(1);
737        if depth > 256 || self.visits > self.limit.saturating_mul(64).min(100_000) {
738            return Err(EvalError::resource_limit("finite binding traversal"));
739        }
740        let ev = self.evaluator;
741        ev.admit_expr(expr)?;
742        let node = ev.ir().node(expr);
743        if node.effects.intersects(Effects::IMPURE | Effects::TEMPORAL)
744            || ev.scope_shares_side_effects(scope)
745        {
746            return Err(EvalError::unsupported(
747                "effects in finite binding preflight",
748            ));
749        }
750        if node.effects.contains(Effects::USES_ENABLED)
751            && (!self.query_allowed
752                || !matches!(
753                    node.expr,
754                    Expr::StepBox { .. }
755                        | Expr::StepAngle { .. }
756                        | Expr::Enabled(_)
757                        | Expr::Not(_)
758                        | Expr::Junction { .. }
759                        | Expr::Def(_)
760                        | Expr::Apply {
761                            callee: OpRef::Def(_),
762                            ..
763                        }
764                        | Expr::Let { .. }
765                        | Expr::Local(_)
766                        | Expr::Subst { .. }
767                        | Expr::SubstRef { .. }
768                        | Expr::Quant {
769                            kind: dive_ir::QuantKind::Forall | dive_ir::QuantKind::Exists,
770                            ..
771                        }
772                        | Expr::Label { .. }
773                        | Expr::Selected(_)
774                ))
775        {
776            return Err(EvalError::unsupported(
777                "ENABLED outside the Boolean spine or under priming",
778            ));
779        }
780        if matches!(
781            node.expr,
782            Expr::Prime(_)
783                | Expr::Var { primed: true, .. }
784                | Expr::SubstRef { primed: true, .. }
785                | Expr::Builtin {
786                    op: BuiltinOp::Prime,
787                    ..
788                }
789                | Expr::Apply {
790                    callee: OpRef::Builtin(BuiltinOp::Prime),
791                    ..
792                }
793        ) {
794            return Err(EvalError::unsupported(
795                "SelectSeq primed callback outside a query",
796            ));
797        }
798        if matches!(
799            node.expr,
800            Expr::Builtin {
801                op: BuiltinOp::PowerSet
802                    | BuiltinOp::Times
803                    | BuiltinOp::String
804                    | BuiltinOp::Unchanged
805                    | BuiltinOp::Cdot
806                    | BuiltinOp::Enabled
807                    | BuiltinOp::Always
808                    | BuiltinOp::Eventually
809                    | BuiltinOp::LeadsTo
810                    | BuiltinOp::WhilePlus,
811                ..
812            } | Expr::Apply {
813                callee: OpRef::Builtin(
814                    BuiltinOp::PowerSet
815                        | BuiltinOp::Times
816                        | BuiltinOp::String
817                        | BuiltinOp::Unchanged
818                        | BuiltinOp::Cdot
819                        | BuiltinOp::Enabled
820                        | BuiltinOp::Always
821                        | BuiltinOp::Eventually
822                        | BuiltinOp::LeadsTo
823                        | BuiltinOp::WhilePlus
824                ),
825                ..
826            } | Expr::Enabled(_)
827                | Expr::Always(_)
828                | Expr::Eventually(_)
829                | Expr::LeadsTo(_, _)
830                | Expr::WhilePlus(_, _)
831                | Expr::Wf { .. }
832                | Expr::Sf { .. }
833                | Expr::TemporalQuant { .. }
834                | Expr::StepBox { .. }
835                | Expr::StepAngle { .. }
836                | Expr::Cdot(_, _)
837                | Expr::Unchanged(_)
838        ) {
839            return Err(EvalError::unsupported(
840                "SelectSeq binder/provider/action callback",
841            ));
842        }
843        match &node.expr {
844            Expr::Quant { body, bounds, .. }
845            | Expr::FcnCons { body, bounds, .. }
846            | Expr::RecFcn { body, bounds, .. }
847            | Expr::SetMap {
848                expr: body, bounds, ..
849            } => {
850                for bound in bounds {
851                    let domain = bound.domain.ok_or_else(|| {
852                        EvalError::unsupported("unbounded SelectSeq callback domain")
853                    })?;
854                    self.walk_data(scope, domain, depth + 1)?;
855                }
856                let analysis = ev.scope_binder_analysis(scope, expr)?;
857                return self.walk_data(&analysis, *body, depth + 1);
858            }
859            Expr::SetFilter { bound, pred } => {
860                let domain = bound
861                    .domain
862                    .ok_or_else(|| EvalError::unsupported("unbounded SelectSeq callback domain"))?;
863                self.walk_data(scope, domain, depth + 1)?;
864                let analysis = ev.scope_binder_analysis(scope, expr)?;
865                return self.walk_data(&analysis, *pred, depth + 1);
866            }
867            _ => {}
868        }
869        match &node.expr {
870            Expr::Not(body) | Expr::Selected(body) | Expr::Label { body, .. } => {
871                return self.walk(scope, *body, depth + 1);
872            }
873            Expr::Junction { items, .. } => {
874                for item in items {
875                    self.walk(scope, *item, depth + 1)?;
876                }
877                return Ok(());
878            }
879            Expr::Let { body, .. } => {
880                return self.walk(&ev.scope_let(scope, expr)?, *body, depth + 1);
881            }
882            Expr::Subst { body, bindings } => {
883                if bindings.iter().any(|binding| {
884                    matches!(
885                        binding.value,
886                        Arg::Expr {
887                            pass: dive_ir::Pass::Strict,
888                            ..
889                        }
890                    )
891                }) {
892                    return Err(EvalError::unsupported(
893                        "eager substitution in finite analysis",
894                    ));
895                }
896                return self.walk(&ev.scope_subst(scope, expr)?, *body, depth + 1);
897            }
898            Expr::Local(local) => {
899                return match ev.scope_slot(scope, *local) {
900                    SlotView::Value(_) | SlotView::AnalysisBound | SlotView::AnalysisConstant => {
901                        Ok(())
902                    }
903                    SlotView::Function(_) if self.configured_depth != 0 => Err(
904                        EvalError::unsupported("recursive function in configured finite context"),
905                    ),
906                    SlotView::Lazy(body, sc) => self.walk(&sc, body, depth + 1),
907                    _ => Err(EvalError::unsupported("opaque finite binding context")),
908                };
909            }
910            Expr::SubstRef { decl, .. } => {
911                return match ev.scope_substitution(scope, *decl, &St::constant(), false)? {
912                    Some(SlotView::Value(value)) => self.native_storage(None, Some(&value)),
913                    Some(SlotView::Lazy(body, sc)) => self.walk(&sc, body, depth + 1),
914                    Some(SlotView::AnalysisBound | SlotView::AnalysisConstant) => Ok(()),
915                    None if ev.ir().decl(*decl).variable => Ok(()),
916                    None => match ev
917                        .ir()
918                        .decl(*decl)
919                        .constant
920                        .and_then(|c| ev.constant_binding(c))
921                    {
922                        Some(ConstBinding::Value(value)) => self.native_storage(None, Some(&value)),
923                        Some(ConstBinding::Def(def)) => {
924                            let def = ev.redirected(def);
925                            self.walk(
926                                &ev.scope_enter(scope, def)?,
927                                ev.ir().def(def).body,
928                                depth + 1,
929                            )
930                        }
931                        None => Err(EvalError::unsupported(
932                            "unbound substituted finite declaration",
933                        )),
934                    },
935                    _ => Err(EvalError::unsupported("opaque substituted finite binding")),
936                };
937            }
938            Expr::Const(c) => {
939                return match ev.constant_binding(*c) {
940                    Some(ConstBinding::Value(value)) => self.native_storage(None, Some(&value)),
941                    Some(ConstBinding::Def(d)) => {
942                        let d = ev.redirected(d);
943                        self.walk_data(&ev.scope_enter(scope, d)?, ev.ir().def(d).body, depth + 1)
944                    }
945                    None => Err(EvalError::unsupported("unbound finite binding constant")),
946                };
947            }
948            _ => {}
949        }
950        let call = match &node.expr {
951            Expr::Def(d) => Some((OpRef::Def(*d), &[][..])),
952            Expr::Apply { callee, args } => Some((callee.clone(), args.as_ref())),
953            _ => None,
954        };
955        if let Some((op, args)) = call {
956            let standard = match op {
957                OpRef::Def(source) => {
958                    let d = ev.redirected(source);
959                    // Direct uses may read the stored override; redirected uses
960                    // execute its target body instead. Neither source may vanish
961                    // from this proof merely because the target has a value.
962                    if ev.is_value_override(d) {
963                        return Err(EvalError::unsupported(
964                            "SelectSeq overridden definition source",
965                        ));
966                    }
967                    let leaf = ev.recursive_leaf(source);
968                    let def = ev.ir().def(d);
969                    if def.recursive
970                        && self.configured_depth == 0
971                        && !scope.has_substitutions()
972                        && leaf
973                    {
974                        // A state-level recursive operator is an evaluation
975                        // leaf (`Evaluator::recursive_leaf`): its actuals are
976                        // walked in this scope, its body is not projected.
977                        for arg in args {
978                            let Arg::Expr { expr, .. } = arg else {
979                                return Err(EvalError::unsupported(
980                                    "recursive/higher-order finite binding",
981                                ));
982                            };
983                            self.walk_data(scope, *expr, depth + 1)?;
984                        }
985                        return Ok(());
986                    }
987                    if def.recursive {
988                        return Err(EvalError::unsupported(
989                            "recursive/higher-order finite binding",
990                        ));
991                    }
992                    if !ev.is_value_override(d) && def.std.is_none() {
993                        for arg in args {
994                            if self.configured_depth != 0 {
995                                let Arg::Expr { expr, .. } = arg else {
996                                    return Err(EvalError::unsupported(
997                                        "higher-order configured finite argument",
998                                    ));
999                                };
1000                                // Unused helper actuals retain configured origin too.
1001                                // Inspect their caller scope before entering the body.
1002                                self.walk(scope, *expr, depth + 1)?;
1003                            } else if let Arg::Op { op, .. } = arg {
1004                                self.operator_context(scope, op, depth + 1)?;
1005                            }
1006                        }
1007                        return self.walk(&ev.scope_apply(scope, d, args)?, def.body, depth + 1);
1008                    }
1009                    def.std
1010                }
1011                OpRef::Std(s) => Some(s),
1012                OpRef::Param(local) => {
1013                    let ceiling = self.limit.saturating_mul(64).min(100_000);
1014                    let mut remaining = ceiling.saturating_sub(self.visits);
1015                    let native = ev.scope_native_operator_analysis(
1016                        scope,
1017                        &OpRef::Param(local),
1018                        &mut remaining,
1019                    );
1020                    self.visits = ceiling - remaining;
1021                    let native = native?;
1022                    if native
1023                        .is_some_and(|op| i32::try_from(args.len()).ok() != Some(op.java_arity()))
1024                    {
1025                        return Err(EvalError::unsupported(
1026                            "native finite binding argument arity",
1027                        ));
1028                    }
1029                    self.operator_context(scope, &OpRef::Param(local), depth + 1)?;
1030                    for arg in args {
1031                        let Arg::Expr { expr, .. } = arg else {
1032                            return Err(EvalError::unsupported(
1033                                "higher-order finite binding actual",
1034                            ));
1035                        };
1036                        self.walk_data(scope, *expr, depth + 1)?;
1037                    }
1038                    if native.is_some() {
1039                        return Ok(());
1040                    }
1041                    let (def, called) =
1042                        ev.scope_apply_param(scope, local, args).ok_or_else(|| {
1043                            EvalError::unsupported("opaque finite binding operator")
1044                        })??;
1045                    return self.walk_data(&called, ev.ir().def(def).body, depth + 1);
1046                }
1047                OpRef::Const(constant) => {
1048                    let (def, called) = self.configured_call(scope, constant, args, depth + 1)?;
1049                    return self.walk_data(&called, ev.ir().def(def).body, depth + 1);
1050                }
1051                OpRef::Subst(_) => {
1052                    return Err(EvalError::unsupported("dynamic finite binding operator"));
1053                }
1054                _ => None,
1055            };
1056            let concat_without_names = standard == Some(StdOp::SequencesConcat)
1057                && self.concat_without_names(scope, &op, args, depth + 1)?;
1058            if standard.is_some_and(|s| {
1059                s.impure()
1060                    || (s.creates_runtime_names() && !concat_without_names)
1061                    || matches!(
1062                        s.support(),
1063                        dive_ir::StdSupport::Io | dive_ir::StdSupport::Introspection
1064                    )
1065                    || matches!(
1066                        s,
1067                        StdOp::SequencesSeq | StdOp::NaturalsNat | StdOp::IntegersInt
1068                    )
1069            }) {
1070                return Err(EvalError::unsupported(
1071                    "SelectSeq effect/provider/native callback",
1072                ));
1073            }
1074            if standard == Some(StdOp::SequencesSelectSeq) {
1075                let ceiling = self.limit.saturating_mul(64).min(100_000);
1076                let mut remaining = ceiling.saturating_sub(self.visits);
1077                let projected = ev.selectseq_projection(scope, &op, args, &mut remaining);
1078                self.visits = ceiling - remaining;
1079                let Some((sequence, bodies)) = projected? else {
1080                    return Err(EvalError::unsupported("SelectSeq nested target"));
1081                };
1082                self.walk_data(scope, sequence, depth + 1)?;
1083                return self.callback_sources(&bodies, depth + 1);
1084            }
1085            if standard.is_some() && args.iter().any(|a| matches!(a, Arg::Op { .. })) {
1086                return Err(EvalError::unsupported(
1087                    "higher-order finite standard argument",
1088                ));
1089            }
1090            if standard == Some(StdOp::TlcTLCGet) {
1091                return Err(EvalError::unsupported(
1092                    "effectful/checker finite binding operator",
1093                ));
1094            }
1095        }
1096        for child in node.expr.children() {
1097            self.walk_data(scope, child, depth + 1)?;
1098        }
1099        Ok(())
1100    }
1101}
1102
1103fn join_kind(left: ResultKind, right: ResultKind) -> ResultKind {
1104    if left == ResultKind::NonString && right == ResultKind::NonString {
1105        ResultKind::NonString
1106    } else {
1107        ResultKind::Unknown
1108    }
1109}
1110
1111fn value_kind(value: &dive_value::Value) -> ResultKind {
1112    match value {
1113        dive_value::Value::Str(_) => ResultKind::Unknown,
1114        dive_value::Value::Bool(_)
1115        | dive_value::Value::Int(_)
1116        | dive_value::Value::BigInt(_)
1117        | dive_value::Value::Model(_)
1118        | dive_value::Value::Set(_)
1119        | dive_value::Value::Fcn(_) => ResultKind::NonString,
1120    }
1121}
1122
1123fn non_string_builtin(op: BuiltinOp) -> bool {
1124    matches!(
1125        op,
1126        BuiltinOp::Eq
1127            | BuiltinOp::Neq
1128            | BuiltinOp::In
1129            | BuiltinOp::NotIn
1130            | BuiltinOp::Subseteq
1131            | BuiltinOp::Cup
1132            | BuiltinOp::Cap
1133            | BuiltinOp::SetMinus
1134            | BuiltinOp::PowerSet
1135            | BuiltinOp::BigUnion
1136            | BuiltinOp::Domain
1137            | BuiltinOp::Times
1138            | BuiltinOp::Boolean
1139            | BuiltinOp::String
1140            | BuiltinOp::Not
1141            | BuiltinOp::And
1142            | BuiltinOp::Or
1143            | BuiltinOp::Implies
1144            | BuiltinOp::Equiv
1145    )
1146}
1147
1148#[cfg(test)]
1149#[allow(
1150    clippy::expect_used,
1151    clippy::panic,
1152    reason = "private result-kind contract assertions"
1153)]
1154mod result_kind_tests {
1155    use super::{Guard, ResultKind};
1156    use crate::{Evaluator, Model, Options};
1157    use dive_ir::{Arg, OpRef, Pass, StdOp};
1158    use std::sync::Arc;
1159
1160    fn fixture(expression: &str) -> (Arc<dive_ir::Ir>, Evaluator) {
1161        let source =
1162            format!("---- MODULE Kind ----\nEXTENDS TLC, Sequences\nD=={expression}\n====\n");
1163        let analysis =
1164            dive_sema::analyze_source("Kind.tla", &source, &dive_sema::Options::default());
1165        assert!(analysis.accepted(), "{:?}", analysis.diagnostics());
1166        let ir = Arc::new(dive_ir::lower(&analysis).expect("IR"));
1167        let evaluator = Evaluator::new(Model::new(ir.clone()), Options::tlc()).expect("evaluator");
1168        (ir, evaluator)
1169    }
1170
1171    fn guard(evaluator: &Evaluator) -> Guard<'_> {
1172        Guard {
1173            evaluator,
1174            limit: 1_000,
1175            visits: 0,
1176            configured_depth: 0,
1177            query_allowed: false,
1178        }
1179    }
1180
1181    #[test]
1182    fn a_constructor_type_fact_is_positive_without_executing_its_effectful_child() {
1183        let (ir, evaluator) = fixture("<<PrintT(0)>>");
1184        let def = ir.root_def("D").expect("D");
1185        assert!(matches!(
1186            guard(&evaluator)
1187                .result_kind(
1188                    &evaluator.scope(def).expect("scope"),
1189                    ir.def(def).body,
1190                    0,
1191                    &mut Vec::new()
1192                )
1193                .expect("result-kind metadata"),
1194            ResultKind::NonString
1195        ));
1196        assert_eq!(evaluator.take_output(), [] as [std::string::String; 0]);
1197    }
1198
1199    #[test]
1200    fn active_owned_context_cycle_is_unknown_without_discarding_its_owner() {
1201        let (ir, evaluator) = fixture("<<0>>");
1202        let def = ir.root_def("D").expect("D");
1203        let scope = evaluator.scope(def).expect("scope");
1204        let expr = ir.def(def).body;
1205        let mut active = vec![(expr, scope.clone())];
1206        assert!(matches!(
1207            guard(&evaluator)
1208                .result_kind(&scope, expr, 0, &mut active)
1209                .expect("bounded cycle"),
1210            ResultKind::Unknown
1211        ));
1212        assert_eq!(active.len(), 1);
1213        assert!(matches!(
1214            guard(&evaluator)
1215                .result_kind(&scope, expr, 0, &mut Vec::new())
1216                .expect("fresh source"),
1217            ResultKind::NonString
1218        ));
1219    }
1220
1221    #[test]
1222    fn malformed_native_actual_shapes_never_gain_the_concat_exemption() {
1223        let (ir, evaluator) = fixture("TRUE");
1224        let def = ir.root_def("D").expect("D");
1225        let scope = evaluator.scope(def).expect("scope");
1226        let actual = Arg::Expr {
1227            expr: ir.def(def).body,
1228            pass: Pass::Direct,
1229        };
1230        for args in [
1231            Vec::new(),
1232            vec![actual.clone()],
1233            vec![actual.clone(); 3],
1234            vec![
1235                Arg::Op {
1236                    op: OpRef::Std(StdOp::SequencesConcat),
1237                    level: dive_ir::Level::Constant
1238                };
1239                2
1240            ],
1241        ] {
1242            assert!(
1243                !guard(&evaluator)
1244                    .concat_without_names(&scope, &OpRef::Std(StdOp::SequencesConcat), &args, 0)
1245                    .expect("metadata shape refusal")
1246            );
1247        }
1248        assert_eq!(evaluator.take_output(), [] as [std::string::String; 0]);
1249    }
1250}