1use crate::{ConstBinding, EvalError, Evaluator, Scope, SlotView, St};
5use dive_ir::{Arg, BuiltinOp, ConstId, DefScope, Effects, Expr, ExprId, Level, OpRef, StdOp};
6
7impl Evaluator {
8 #[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 #[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 *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
126struct Guard<'a> {
129 evaluator: &'a Evaluator,
130 limit: usize,
131 visits: usize,
132 configured_depth: usize,
133 query_allowed: bool,
134}
135
136#[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 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 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 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 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 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 self.native_storage(Some(captured), None)?;
452 self.walk_data(captured, *body, depth + 1)?;
453 }
454 Ok(())
455 }
456
457 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 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 #[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 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 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 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 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 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}