1use std::sync::Arc;
18
19use dive_ir::{Arg, DefId, DefScope, Expr, ExprId, LocalRef, OpRef, Pass, Slot};
20use dive_value::Value;
21
22use crate::Evaluator;
23use crate::env::{Dyn, Env, Ev, St, Sv, Thunk};
24use crate::error::{EvalError, Result};
25
26pub(crate) type BindingColumn = (Vec<usize>, bool, Arc<[Value]>);
27
28#[derive(Clone, Debug)]
30pub struct Scope {
31 pub(crate) env: Env,
32 pub(crate) owner: Arc<dive_ir::Ir>,
33 pub(crate) names: Arc<dive_value::Interner>,
34 pub(crate) context: std::sync::Weak<crate::core::Core>,
35 pub(crate) wrapper: Option<ExprId>,
38}
39
40impl Scope {
41 #[must_use]
45 pub fn has_substitutions(&self) -> bool {
46 self.env.dynamic.subst.is_some()
47 }
48
49 #[must_use]
63 pub fn same_analysis_context(&self, other: &Self) -> bool {
64 let same_substitution = match (&self.env.dynamic.subst, &other.env.dynamic.subst) {
65 (None, None) => true,
66 (Some(left), Some(right)) => Arc::ptr_eq(left, right),
67 _ => false,
68 };
69 self.env.dynamic.at.is_none()
70 && other.env.dynamic.at.is_none()
71 && self.context.ptr_eq(&other.context)
72 && Arc::ptr_eq(&self.owner, &other.owner)
73 && Arc::ptr_eq(&self.names, &other.names)
74 && Arc::ptr_eq(&self.env.frame, &other.env.frame)
75 && same_substitution
76 && self.env.dynamic.cut == other.env.dynamic.cut
77 && self.wrapper == other.wrapper
78 }
79
80 #[must_use]
82 pub fn def(&self) -> DefId {
83 self.env.frame.def
84 }
85}
86
87#[derive(Clone, Debug)]
89pub enum SlotView {
90 Unset,
92 Value(Value),
94 AnalysisBound,
97 AnalysisConstant,
101 Lazy(ExprId, Scope),
104 Function(Arc<crate::LazyFcn>),
107 Other,
109}
110
111impl Evaluator {
112 pub fn scope_operator_analysis(
129 &self,
130 scope: &Scope,
131 operator: &OpRef,
132 ) -> Result<Option<(DefId, Scope)>> {
133 self.validate_scope(scope)?;
134 let value = match operator {
135 OpRef::Def(def) => {
136 self.admit_def(*def)?;
137 let target = self.core.redirect(*def);
138 self.admit_def(target)?;
139 self.admit_parent(scope, target)?;
140 self.core.op_value(&scope.env, operator)?
141 }
142 OpRef::Param(local) => {
143 let Some(frame) = scope.env.frame_up(local.up) else {
144 return Ok(None);
145 };
146 let Some(Sv::Op(value)) = frame.slots.get(local.slot.index()) else {
147 return Ok(None);
148 };
149 (**value).clone()
150 }
151 _ => return Ok(None),
152 };
153 self.operator_value_analysis(scope, value)
154 }
155
156 pub fn scope_native_operator_analysis(
170 &self,
171 scope: &Scope,
172 operator: &OpRef,
173 work: &mut usize,
174 ) -> Result<Option<dive_ir::StdOp>> {
175 self.validate_scope(scope)?;
176 Self::operator_capture_step(work)?;
177 let value = match operator {
178 OpRef::Def(def) => {
179 self.admit_def(*def)?;
180 let target = self.core.redirect(*def);
181 self.admit_def(target)?;
182 self.admit_parent(scope, target)?;
183 self.core.op_value(&scope.env, operator)?
184 }
185 OpRef::Std(op) => crate::env::OpVal::Std(*op),
186 OpRef::Param(local) => {
187 let Some(frame) = scope.env.frame_up(local.up) else {
188 return Ok(None);
189 };
190 let Some(Sv::Op(value)) = frame.slots.get(local.slot.index()) else {
191 return Ok(None);
192 };
193 (**value).clone()
194 }
195 _ => return Ok(None),
196 };
197 self.native_operator_value(&value, work)
198 }
199
200 fn native_operator_value(
201 &self,
202 value: &crate::env::OpVal,
203 work: &mut usize,
204 ) -> Result<Option<dive_ir::StdOp>> {
205 use dive_ir::StdOp;
206 let native = match value {
207 crate::env::OpVal::Std(op) => *op,
208 crate::env::OpVal::Def {
209 def,
210 parent,
211 dynamic,
212 } => {
213 if parent.is_some() || dynamic.is_some() {
216 return Ok(None);
217 }
218 Self::operator_capture_step(work)?;
219 let target = self.admit_def(*def)?;
220 if self.is_value_override(*def) {
221 return Ok(None);
222 }
223 let Some(op) = target.std else {
224 return Ok(None);
225 };
226 op
227 }
228 _ => return Ok(None),
229 };
230 if !matches!(
231 native,
232 StdOp::SequencesLen
233 | StdOp::SequencesHead
234 | StdOp::SequencesAppend
235 | StdOp::FiniteSetsCardinality
236 ) {
237 return Ok(None);
238 }
239 for binding in &self.core.consts {
241 Self::operator_capture_step(work)?;
242 if let Some(crate::ConstBinding::Def(bound)) = binding {
243 let target = self.admit_def(self.core.redirect(*bound))?;
244 if target.std == Some(native) {
245 return Ok(None);
246 }
247 }
248 }
249 for (index, target) in self.core.ir.defs().iter().enumerate() {
250 Self::operator_capture_step(work)?;
251 if target.std == Some(native) {
252 let def =
253 DefId(u32::try_from(index).map_err(|_| {
254 EvalError::resource_limit("native operator definition index")
255 })?);
256 if self.is_value_override(def) || self.core.redirect(def) != def {
257 return Ok(None);
258 }
259 }
260 }
261 Ok(Some(native))
262 }
263
264 pub(crate) fn operator_value_analysis(
265 &self,
266 scope: &Scope,
267 value: crate::env::OpVal,
268 ) -> Result<Option<(DefId, Scope)>> {
269 let crate::env::OpVal::Def {
270 def,
271 parent,
272 dynamic,
273 } = value
274 else {
275 return Ok(None);
276 };
277 let target = self.admit_def(def)?;
278 if self.core.consts.iter().flatten().any(|binding| {
281 matches!(binding, crate::ConstBinding::Def(bound) if self.core.redirect(*bound) == def)
282 }) {
283 return Ok(None);
284 }
285 if target.recursive
286 || target.std.is_some()
287 || self.is_value_override(def)
288 || target.params.iter().any(|param| param.arity != 0)
289 {
290 return Ok(None);
291 }
292 let mut env = Env::new(
293 def,
294 target.depth,
295 target.frame.len(),
296 parent,
297 dynamic.unwrap_or_else(|| scope.env.dynamic.clone()),
298 );
299 for i in 0..target.params.len() {
300 env.bind(i, Sv::AnalysisBound);
301 }
302 Ok(Some((
303 def,
304 Scope {
305 owner: self.core.ir.clone(),
306 names: self.core.names.clone(),
307 context: Arc::downgrade(&self.core),
308 env,
309 wrapper: scope.wrapper,
310 },
311 )))
312 }
313
314 pub(crate) fn selectseq_value_analysis(
315 &self,
316 scope: &Scope,
317 value: crate::env::OpVal,
318 work: &mut usize,
319 ) -> Result<Option<(DefId, Scope)>> {
320 self.validate_scope(scope)?;
321 *work = work
322 .checked_sub(self.core.consts.len().saturating_add(1))
323 .ok_or_else(|| EvalError::resource_limit("SelectSeq target work"))?;
324 let crate::env::OpVal::Def {
325 def,
326 parent,
327 dynamic: None,
328 } = &value
329 else {
330 return Err(EvalError::unsupported(
331 "SelectSeq retained dynamic/native callback",
332 ));
333 };
334 let definition = self.admit_def(*def)?;
335 match definition.scope {
336 DefScope::Local { parent: owner } | DefScope::Inline { parent: owner }
337 if parent.as_ref().is_none_or(|frame| {
338 frame.def != owner || frame.depth != definition.depth.saturating_sub(1)
339 }) =>
340 {
341 return Err(EvalError::unsupported(
342 "SelectSeq incompatible lexical callback owner",
343 ));
344 }
345 DefScope::TopLevel if parent.is_some() => {
346 return Err(EvalError::unsupported(
347 "SelectSeq unexpected lexical callback owner",
348 ));
349 }
350 _ => {}
351 }
352 self.operator_value_analysis(scope, value)
353 }
354
355 pub fn scope_operator_captures(
369 &self,
370 scope: &Scope,
371 work: &mut usize,
372 ) -> Result<Option<Vec<(ExprId, Scope)>>> {
373 self.operator_captures(scope, work, false)
374 }
375
376 pub(crate) fn operator_captures(
377 &self,
378 scope: &Scope,
379 work: &mut usize,
380 selectseq: bool,
381 ) -> Result<Option<Vec<(ExprId, Scope)>>> {
382 self.validate_scope(scope)?;
383 Self::operator_capture_step(work)?;
384 let mut captures = Vec::new();
385 let mut todo = vec![(scope.env.clone(), 0_usize)];
386 let mut frames = std::collections::HashSet::new();
387 let mut links = std::collections::HashSet::new();
388 let mut owners = Vec::new();
391 while let Some((env, depth)) = todo.pop() {
392 if depth > 128 {
393 return Err(EvalError::resource_limit("operator capture context depth"));
394 }
395 if env.dynamic.at.is_some() {
396 return Ok(None); }
398 Self::operator_capture_step(work)?;
399 owners.push(env.clone());
400 let context_scope = Scope {
401 env: env.clone(),
402 ..scope.clone()
403 };
404 let mut slots = Vec::new();
405 let dynamic_key = (
406 env.dynamic
407 .subst
408 .as_ref()
409 .map_or(0, |head| Arc::as_ptr(head) as usize),
410 env.dynamic.cut,
411 );
412 let frame_key = (Arc::as_ptr(&env.frame) as usize, dynamic_key);
413 if !frames.contains(&frame_key) {
414 Self::operator_capture_step(work)?;
415 frames.insert(frame_key);
416 for slot in &env.frame.slots {
417 Self::operator_capture_step(work)?;
418 slots.push(slot);
419 }
420 if let Some(parent) = &env.frame.parent {
421 Self::operator_capture_step(work)?;
422 todo.push((
423 Env {
424 frame: parent.clone(),
425 dynamic: env.dynamic.clone(),
426 },
427 depth + 1,
428 ));
429 }
430 }
431 let mut link = env.dynamic.subst.as_deref();
432 while let Some(binding) = link {
433 let link_key = (std::ptr::from_ref(binding) as usize, dynamic_key);
434 if links.contains(&link_key) {
435 break;
436 }
437 Self::operator_capture_step(work)?;
438 links.insert(link_key);
439 slots.push(&binding.val);
440 link = binding.next.as_deref();
441 }
442 for slot in slots {
443 Self::operator_capture_step(work)?;
444 let (expr, source) = match slot {
445 Sv::Thunk(thunk) => {
446 self.admit_expr(thunk.expr)?;
447 (
448 thunk.expr,
449 Scope {
450 env: thunk.env.clone(),
451 ..scope.clone()
452 },
453 )
454 }
455 Sv::Op(operator) => {
456 if selectseq
457 && !matches!(&**operator, crate::env::OpVal::Def { dynamic: None, .. })
458 {
459 return Ok(None);
460 }
461 if !selectseq && self.native_operator_value(operator, work)?.is_some() {
462 continue;
465 }
466 let resolved = if selectseq {
467 self.selectseq_value_analysis(&context_scope, *operator.clone(), work)?
468 } else {
469 self.operator_value_analysis(&context_scope, *operator.clone())?
470 };
471 let Some((def, source)) = resolved else {
472 return Ok(None);
473 };
474 (self.core.ir.def(def).body, source)
475 }
476 Sv::Fcn(_) => return Ok(None),
477 Sv::Unset | Sv::Val(_) | Sv::AnalysisBound | Sv::AnalysisConstant => continue,
478 };
479 self.validate_scope(&source)?;
480 Self::operator_capture_step(work)?;
481 todo.push((source.env.clone(), depth + 1));
482 captures.push((expr, source));
483 }
484 }
485 Ok(Some(captures))
486 }
487
488 fn operator_capture_step(work: &mut usize) -> Result<()> {
489 *work = work
490 .checked_sub(1)
491 .ok_or_else(|| EvalError::resource_limit("operator capture work"))?;
492 Ok(())
493 }
494
495 pub fn scope_apply(&self, scope: &Scope, def: DefId, args: &[Arg]) -> Result<Scope> {
503 self.validate_scope(scope)?;
504 self.admit_args(scope, def, args)?;
505 let core = &self.core;
506 let d = self.admit_def(def)?;
507 if args.len() != d.params.len() {
508 return Err(EvalError::bug(format!(
509 "{} applied to {} arguments, expects {}",
510 d.name,
511 args.len(),
512 d.params.len()
513 )));
514 }
515 let parent = self.admit_parent(scope, def)?;
516 let mut callee = Env::new(
517 def,
518 d.depth,
519 d.frame.len(),
520 parent,
521 scope.env.dynamic.clone(),
522 );
523 for (i, a) in args.iter().enumerate() {
524 let sv = match a {
525 Arg::Expr { expr, .. } => Sv::Thunk(Thunk::new(*expr, scope.env.clone(), true)),
526 Arg::Op { op, .. } => Sv::op(core.op_value(&scope.env, op)?),
527 };
528 callee.bind(i, sv);
529 }
530 Ok(Scope {
531 owner: self.core.ir.clone(),
532 names: self.core.names.clone(),
533 context: Arc::downgrade(&self.core),
534 env: callee,
535 wrapper: scope.wrapper,
536 })
537 }
538
539 #[must_use]
547 pub fn scope_apply_param(
548 &self,
549 scope: &Scope,
550 r: LocalRef,
551 args: &[Arg],
552 ) -> Option<Result<(DefId, Scope)>> {
553 if let Err(e) = self.validate_scope(scope) {
554 return Some(Err(e));
555 }
556 let core = &self.core;
557 let frame = scope.env.frame_up(r.up)?;
558 let Some(Sv::Op(op)) = frame.slots.get(r.slot.index()) else {
559 return None;
560 };
561 let crate::env::OpVal::Def {
562 def,
563 parent,
564 dynamic,
565 } = &**op
566 else {
567 return None;
568 };
569 let def = *def;
570 if let Err(e) = self.admit_args(scope, def, args) {
571 return Some(Err(e));
572 }
573 let d = core.ir.def(def);
574 if args.len() != d.params.len() || core.ir.def(def).std.is_some() {
575 return None;
576 }
577 let parent = match d.scope {
578 DefScope::Local { .. } | DefScope::Inline { .. } => parent.clone(),
579 _ => None,
580 };
581 let mut callee = Env::new(
582 def,
583 d.depth,
584 d.frame.len(),
585 parent,
586 dynamic.clone().unwrap_or_else(|| scope.env.dynamic.clone()),
587 );
588 for (i, a) in args.iter().enumerate() {
589 let sv = match a {
590 Arg::Expr { expr, .. } => Sv::Thunk(Thunk::new(*expr, scope.env.clone(), true)),
591 Arg::Op { op, .. } => match core.op_value(&scope.env, op) {
592 Ok(v) => Sv::op(v),
593 Err(e) => return Some(Err(e)),
594 },
595 };
596 callee.bind(i, sv);
597 }
598 Some(Ok((
599 def,
600 Scope {
601 owner: self.core.ir.clone(),
602 names: self.core.names.clone(),
603 context: Arc::downgrade(&self.core),
604 env: callee,
605 wrapper: scope.wrapper,
606 },
607 )))
608 }
609
610 pub fn scope_unbound(&self, scope: &Scope, def: DefId) -> Result<Scope> {
619 self.validate_scope(scope)?;
620 let d = self.admit_def(def)?;
621 let parent = self.admit_parent(scope, def)?;
622 Ok(match d.scope {
623 DefScope::LetValue { .. } => scope.clone(),
624 DefScope::TopLevel => return self.scope(def),
625 DefScope::Local { .. } | DefScope::Inline { .. } => Scope {
626 owner: self.core.ir.clone(),
627 names: self.core.names.clone(),
628 context: Arc::downgrade(&self.core),
629 env: Env::new(
630 def,
631 d.depth,
632 d.frame.len(),
633 parent,
634 scope.env.dynamic.clone(),
635 ),
636 wrapper: scope.wrapper,
637 },
638 })
639 }
640
641 pub fn scope_call_values(
648 &self,
649 scope: &Scope,
650 def: DefId,
651 values: Vec<Value>,
652 ) -> Result<Scope> {
653 self.validate_scope(scope)?;
654 let d = self.admit_def(def)?;
655 if d.params.iter().any(|p| p.arity != 0) {
656 return Err(crate::ContextError::new(
657 crate::ContextErrorKind::Arity,
658 "operator parameter requires an operator binding",
659 )
660 .into());
661 }
662 if values.len() != d.params.len() {
663 return Err(crate::ContextError::new(
664 crate::ContextErrorKind::Arity,
665 "value argument count",
666 )
667 .into());
668 }
669 let mut s = match d.scope {
670 DefScope::LetValue { .. } => return Ok(scope.clone()),
671 _ => self.scope_unbound(scope, def)?,
672 };
673 if matches!(d.scope, DefScope::TopLevel) {
674 s.env.dynamic = scope.env.dynamic.clone();
675 }
676 for (i, v) in values.into_iter().enumerate() {
677 s.env.bind(i, Sv::Val(v));
678 }
679 Ok(s)
680 }
681
682 pub fn scope_enter(&self, scope: &Scope, def: DefId) -> Result<Scope> {
689 self.validate_scope(scope)?;
690 if matches!(self.admit_def(def)?.scope, DefScope::LetValue { .. }) {
691 self.admit_parent(scope, def)?;
692 return Ok(scope.clone());
693 }
694 self.scope_apply(scope, def, &[])
695 }
696
697 pub fn scope(&self, def: DefId) -> Result<Scope> {
703 let d = self.admit_def(def)?;
704 if d.scope != DefScope::TopLevel {
705 return Err(crate::ContextError::new(
706 crate::ContextErrorKind::Structure,
707 "definition requires an enclosing lexical frame",
708 )
709 .into());
710 }
711 Ok(Scope {
712 owner: self.core.ir.clone(),
713 names: self.core.names.clone(),
714 context: Arc::downgrade(&self.core),
715 env: Env::new(def, d.depth, d.frame.len(), None, Dyn::default()),
716 wrapper: None,
717 })
718 }
719
720 pub fn scope_subst(&self, scope: &Scope, subst: ExprId) -> Result<Scope> {
731 self.admit_scoped_expr(scope, subst)?;
732 self.validate_scope(scope)?;
733 let Expr::Subst { bindings, .. } = &self.core.ir.node(subst).expr else {
734 return Err(EvalError::bug(
735 "scope_subst on a node that is not a substitution",
736 ));
737 };
738 let env = self
739 .core
740 .bind_subst(&scope.env, &St::default(), bindings, false)?;
741 Ok(Scope {
742 owner: self.core.ir.clone(),
743 names: self.core.names.clone(),
744 context: Arc::downgrade(&self.core),
745 env,
746 wrapper: Some(subst),
747 })
748 }
749
750 pub fn scope_call(&self, scope: &Scope, apply: ExprId) -> Result<(Scope, DefId)> {
759 self.admit_scoped_expr(scope, apply)?;
760 self.validate_scope(scope)?;
761 let (d, args): (&DefId, &[Arg]) = match &self.core.ir.node(apply).expr {
762 Expr::Apply {
763 callee: OpRef::Def(d),
764 args,
765 } => (d, args),
766 Expr::Def(d) => (d, &[]),
767 _ => return Err(EvalError::bug("scope_call on a node that is not a call")),
768 };
769 let d = self.core.redirect(*d);
770 self.admit_args(scope, d, args)?;
771 let def = self.admit_def(d)?;
772 let parent = self.admit_parent(scope, d)?;
773 let mut env = Env::new(
774 d,
775 def.depth,
776 def.frame.len(),
777 parent,
778 scope.env.dynamic.clone(),
779 );
780 for (i, a) in args.iter().enumerate() {
781 let sv = match a {
782 Arg::Expr { expr, pass } => match pass {
783 Pass::Strict => Sv::from(self.core.eval(
784 &mut scope.env.clone(),
785 &St::constant(),
786 *expr,
787 )?),
788 Pass::Lazy | Pass::Direct => {
789 Sv::Thunk(Thunk::new(*expr, scope.env.clone(), false))
790 }
791 },
792 Arg::Op { op, .. } => Sv::op(self.core.op_value(&scope.env, op)?),
793 };
794 env.bind(i, sv);
795 }
796 Ok((
797 Scope {
798 owner: self.core.ir.clone(),
799 names: self.core.names.clone(),
800 context: Arc::downgrade(&self.core),
801 env,
802 wrapper: scope.wrapper,
803 },
804 d,
805 ))
806 }
807
808 pub fn scope_let(&self, scope: &Scope, let_expr: ExprId) -> Result<Scope> {
818 self.scope_let_mode(scope, let_expr, false)
819 }
820
821 pub fn scope_eval_let(&self, scope: &Scope, let_expr: ExprId) -> Result<Scope> {
828 self.scope_let_mode(scope, let_expr, true)
829 }
830
831 fn scope_let_mode(&self, scope: &Scope, let_expr: ExprId, cachable: bool) -> Result<Scope> {
832 self.admit_scoped_expr(scope, let_expr)?;
833 self.validate_scope(scope)?;
834 let core = &self.core;
835 let Expr::Let { defs, .. } = core.ir.expr(let_expr) else {
836 return Err(EvalError::bug("scope_let on a node that is not a LET"));
837 };
838 let mut env = scope.env.clone();
839 for &d in defs {
840 if let DefScope::LetValue { slot, .. } = core.ir.def(d).scope {
841 let body = core.ir.def(d).body;
842 env.bind(
843 slot.index(),
844 Sv::Thunk(Thunk::new(body, env.clone(), cachable)),
845 );
846 }
847 }
848 Ok(Scope {
849 owner: self.core.ir.clone(),
850 names: self.core.names.clone(),
851 context: Arc::downgrade(&self.core),
852 env,
853 wrapper: scope.wrapper,
854 })
855 }
856
857 pub fn scope_without_substs(&self, scope: &Scope) -> Result<Scope> {
864 self.validate_scope(scope)?;
865 let mut env = scope.env.clone();
866 env.dynamic.subst = None;
867 Ok(Scope {
868 owner: self.core.ir.clone(),
869 names: self.core.names.clone(),
870 context: Arc::downgrade(&self.core),
871 env,
872 wrapper: scope.wrapper,
873 })
874 }
875
876 pub fn scope_bind(&self, scope: &Scope, slot: Slot, v: Value) -> Result<Scope> {
883 self.validate_scope(scope)?;
884 if slot.index() >= scope.env.frame.slots.len() {
885 return Err(crate::ContextError::new(
886 crate::ContextErrorKind::UnknownId,
887 "scope binding slot",
888 )
889 .into());
890 }
891 if self
892 .admit_def(scope.def())?
893 .params
894 .get(slot.index())
895 .is_some_and(|p| p.arity != 0)
896 {
897 return Err(crate::ContextError::new(
898 crate::ContextErrorKind::Arity,
899 "operator parameter requires an operator binding",
900 )
901 .into());
902 }
903 let mut env = scope.env.clone();
904 env.bind(slot.index(), Sv::Val(v));
905 Ok(Scope {
906 owner: self.core.ir.clone(),
907 names: self.core.names.clone(),
908 context: Arc::downgrade(&self.core),
909 env,
910 wrapper: scope.wrapper,
911 })
912 }
913
914 #[must_use]
919 pub fn scope_params(&self, scope: &Scope, def: DefId) -> Vec<Option<Value>> {
920 if self.validate_scope(scope).is_err() {
921 return Vec::new();
922 }
923 let Some(d) = self.core.ir.defs().get(def.index()) else {
924 return Vec::new();
925 };
926 let n = d.params.len();
927 let mut f = Some(&scope.env.frame);
928 while let Some(frame) = f {
929 if frame.def == def {
930 return (0..n)
931 .map(|i| match frame.slots.get(i) {
932 Some(Sv::Val(v)) => Some(v.clone()),
933 _ => None,
934 })
935 .collect();
936 }
937 f = frame.parent.as_ref();
938 }
939 vec![None; n]
940 }
941
942 pub fn scope_enabled(&self, scope: &Scope) -> Result<Scope> {
948 self.validate_scope(scope)?;
949 let mut result = scope.clone();
950 result.env.dynamic.branch();
951 Ok(result)
952 }
953
954 pub fn scope_substitution(
962 &self,
963 scope: &Scope,
964 decl: dive_ir::DeclId,
965 st: &St,
966 primed: bool,
967 ) -> Result<Option<SlotView>> {
968 self.validate_scope(scope)?;
969 self.validate_state_context(st)?;
970 let declaration = self.core.ir.decls().get(decl.index()).ok_or_else(|| {
971 crate::ContextError::new(
972 crate::ContextErrorKind::UnknownId,
973 "substitution declaration",
974 )
975 })?;
976 let cutoff = declaration.variable
977 && (st.is(crate::env::control::PRIMED)
978 || (primed && st.is(crate::env::control::ENABLED)));
979 Ok(scope
980 .env
981 .dynamic
982 .lookup_cut(decl, cutoff)
983 .map(|slot| match slot {
984 Sv::Unset => SlotView::Unset,
985 Sv::Val(value) => SlotView::Value(value.clone()),
986 Sv::AnalysisBound => SlotView::AnalysisBound,
987 Sv::AnalysisConstant => SlotView::AnalysisConstant,
988 Sv::Thunk(thunk) => SlotView::Lazy(
989 thunk.expr,
990 Scope {
991 owner: self.core.ir.clone(),
992 names: self.core.names.clone(),
993 context: Arc::downgrade(&self.core),
994 env: thunk.env.clone(),
995 wrapper: scope.wrapper,
996 },
997 ),
998 Sv::Fcn(function) if function.rec_slot.is_some() && function.excepts.is_empty() => {
999 SlotView::Function(function.clone())
1000 }
1001 Sv::Fcn(_) | Sv::Op(_) => SlotView::Other,
1002 }))
1003 }
1004
1005 pub fn scope_subst_operator(
1015 &self,
1016 scope: &Scope,
1017 decl: dive_ir::DeclId,
1018 ) -> Result<Option<DefId>> {
1019 self.validate_scope(scope)?;
1020 let declaration = self.core.ir.decls().get(decl.index()).ok_or_else(|| {
1021 crate::ContextError::new(
1022 crate::ContextErrorKind::UnknownId,
1023 "substitution declaration",
1024 )
1025 })?;
1026 let Some(Sv::Op(operator)) = scope.env.dynamic.lookup(decl) else {
1027 return Ok(None);
1028 };
1029 let crate::env::OpVal::Def {
1030 def,
1031 parent: None,
1032 dynamic: None,
1033 } = &**operator
1034 else {
1035 return Ok(None);
1036 };
1037 let target = self.admit_def(*def)?;
1038 if target.scope != DefScope::TopLevel || target.std.is_some() {
1039 return Ok(None);
1040 }
1041 if target.params.len() != declaration.arity as usize {
1042 return Err(crate::ContextError::new(
1043 crate::ContextErrorKind::Arity,
1044 "substituted operator argument count",
1045 )
1046 .into());
1047 }
1048 Ok(Some(*def))
1049 }
1050
1051 #[must_use]
1053 pub fn scope_subst_slot(&self, scope: &Scope, decl: dive_ir::DeclId) -> SlotView {
1054 if self.validate_scope(scope).is_err() {
1055 return SlotView::Other;
1056 }
1057 match scope.env.dynamic.lookup(decl) {
1058 None | Some(Sv::Unset) => SlotView::Unset,
1059 Some(Sv::Val(v)) => SlotView::Value(v.clone()),
1060 Some(Sv::AnalysisBound) => SlotView::AnalysisBound,
1061 Some(Sv::AnalysisConstant) => SlotView::AnalysisConstant,
1062 Some(Sv::Thunk(t)) => SlotView::Lazy(
1063 t.expr,
1064 Scope {
1065 owner: self.core.ir.clone(),
1066 names: self.core.names.clone(),
1067 context: Arc::downgrade(&self.core),
1068 env: t.env.clone(),
1069 wrapper: scope.wrapper,
1070 },
1071 ),
1072 Some(_) => SlotView::Other,
1073 }
1074 }
1075
1076 #[must_use]
1078 pub fn scope_slot(&self, scope: &Scope, r: LocalRef) -> SlotView {
1079 if self.validate_scope(scope).is_err() {
1080 return SlotView::Other;
1081 }
1082 let Some(frame) = scope.env.frame_up(r.up) else {
1083 return SlotView::Unset;
1084 };
1085 match frame.slots.get(r.slot.index()) {
1086 None | Some(Sv::Unset) => SlotView::Unset,
1087 Some(Sv::Val(v)) => SlotView::Value(v.clone()),
1088 Some(Sv::AnalysisBound) => SlotView::AnalysisBound,
1089 Some(Sv::AnalysisConstant) => SlotView::AnalysisConstant,
1090 Some(Sv::Thunk(t)) => SlotView::Lazy(
1091 t.expr,
1092 Scope {
1093 owner: self.core.ir.clone(),
1094 names: self.core.names.clone(),
1095 context: Arc::downgrade(&self.core),
1096 env: t.env.clone(),
1097 wrapper: scope.wrapper,
1098 },
1099 ),
1100 Some(Sv::Fcn(function))
1101 if function.rec_slot.is_some() && function.excepts.is_empty() =>
1102 {
1103 SlotView::Function(function.clone())
1104 }
1105 Some(_) => SlotView::Other,
1106 }
1107 }
1108
1109 pub fn scope_bindings(&self, scope: &Scope, quant: ExprId, st: &St) -> Result<Vec<Scope>> {
1117 self.admit_scoped_expr(scope, quant)?;
1118 self.validate_scope(scope)?;
1119 self.validate_state_context(st)?;
1120 let core = &self.core;
1121 let Expr::Quant { bounds, .. } = core.ir.expr(quant) else {
1122 return Err(EvalError::bug(
1123 "scope_bindings on a node that is not a quantifier",
1124 ));
1125 };
1126 let mut env = scope.env.clone();
1127 let mut out = Vec::new();
1128 core.for_each_context(&mut env, st, bounds, quant, &mut |_, env| {
1129 out.push(Scope {
1130 owner: self.core.ir.clone(),
1131 names: self.core.names.clone(),
1132 context: Arc::downgrade(&self.core),
1133 env: env.clone(),
1134 wrapper: scope.wrapper,
1135 });
1136 Ok(true)
1137 })?;
1138 Ok(out)
1139 }
1140
1141 pub fn scope_bindings_bounded(
1155 &self,
1156 scope: &Scope,
1157 quant: ExprId,
1158 st: &St,
1159 limit: usize,
1160 ) -> Result<Vec<Scope>> {
1161 let columns = self.bounded_binding_columns(scope, quant, st, limit)?;
1162 self.bounded_body_contexts(scope, quant, &columns, limit)
1163 }
1164
1165 fn bounded_binding_columns(
1168 &self,
1169 scope: &Scope,
1170 quant: ExprId,
1171 st: &St,
1172 limit: usize,
1173 ) -> Result<Vec<BindingColumn>> {
1174 self.admit_scoped_expr(scope, quant)?;
1175 self.validate_scope(scope)?;
1176 self.validate_state_context(st)?;
1177 let core = &self.core;
1178 let bounds: &[dive_ir::Bound] = match core.ir.expr(quant) {
1179 Expr::Quant { bounds, .. }
1180 | Expr::SetMap { bounds, .. }
1181 | Expr::FcnCons { bounds, .. } => bounds,
1182 Expr::SetFilter { bound, .. } => std::slice::from_ref(bound),
1183 _ => return Err(EvalError::bug("bounded bindings require a finite binder")),
1184 };
1185 let mut columns = Vec::new();
1186 let mut entries = 0_usize;
1187 let mut budget = crate::bounded_domain::Budget::new(limit, core.opts.max_depth, core.ctx);
1188 for b in bounds {
1189 let dom = b
1190 .domain
1191 .ok_or_else(|| EvalError::unsupported("unbounded quantifier"))?;
1192 let Value::Set(set) = self.eval_scoped(scope, dom, st)? else {
1193 return Err(EvalError::unsupported("quantifier domain is not a set"));
1194 };
1195 budget.set(&set, 0)?;
1196 let size = usize::try_from(set.size(core.ctx)?)
1197 .map_err(|_| EvalError::resource_limit("quantifier domain entries"))?;
1198 entries = entries
1199 .checked_add(size)
1200 .filter(|n| *n <= limit)
1201 .ok_or_else(|| EvalError::resource_limit("quantifier domain entries"))?;
1202 let values = core.explore(&set)?;
1203 if b.tuple {
1204 columns.push((
1205 b.vars.iter().map(|slot| slot.index()).collect(),
1206 true,
1207 values,
1208 ));
1209 } else {
1210 for &v in &b.vars {
1211 columns.push((vec![v.index()], false, values.clone()));
1212 }
1213 }
1214 }
1215 Ok(columns)
1216 }
1217
1218 fn bounded_binding_count(columns: &[BindingColumn], limit: usize) -> Result<usize> {
1219 columns
1220 .iter()
1221 .try_fold(1_usize, |n, (_, _, ds)| n.checked_mul(ds.len()))
1222 .filter(|n| *n <= limit)
1223 .ok_or_else(|| EvalError::resource_limit("quantifier bindings"))
1224 }
1225
1226 pub(crate) fn bounded_body_contexts(
1227 &self,
1228 scope: &Scope,
1229 quant: ExprId,
1230 columns: &[BindingColumn],
1231 limit: usize,
1232 ) -> Result<Vec<Scope>> {
1233 let count = Self::bounded_binding_count(columns, limit)?;
1234 let mut result = Vec::with_capacity(count);
1235 for i in 0..count {
1236 let mut scope = scope.clone();
1237 let mut quotient = i;
1238 for (slots, tuple, values) in columns {
1239 let value = &values[quotient % values.len()];
1240 quotient /= values.len();
1241 self.core
1242 .bind_one(&mut scope.env, slots, *tuple, value, quant)?;
1243 }
1244 result.push(scope);
1245 }
1246 Ok(result)
1247 }
1248
1249 pub fn scope_binder_analysis(&self, scope: &Scope, expr: ExprId) -> Result<Scope> {
1259 self.binder_analysis(scope, expr, &Sv::AnalysisBound)
1260 }
1261
1262 pub fn scope_constant_binder_analysis(&self, scope: &Scope, expr: ExprId) -> Result<Scope> {
1276 self.admit_scoped_expr(scope, expr)?;
1277 if matches!(self.core.ir.expr(expr), Expr::RecFcn { .. }) {
1278 return Err(EvalError::bug(
1279 "constant binder analysis of a recursive function",
1280 ));
1281 }
1282 self.binder_analysis(scope, expr, &Sv::AnalysisConstant)
1283 }
1284
1285 fn binder_analysis(&self, scope: &Scope, expr: ExprId, unknown: &Sv) -> Result<Scope> {
1286 self.admit_scoped_expr(scope, expr)?;
1287 self.validate_scope(scope)?;
1288 let bounds: &[dive_ir::Bound] = match self.core.ir.expr(expr) {
1289 Expr::Quant { bounds, .. }
1290 | Expr::SetMap { bounds, .. }
1291 | Expr::FcnCons { bounds, .. }
1292 | Expr::RecFcn { bounds, .. } => bounds,
1293 Expr::SetFilter { bound, .. } => std::slice::from_ref(bound),
1294 _ => return Err(EvalError::bug("analysis scope requires a finite binder")),
1295 };
1296 let mut result = scope.clone();
1297 if let Expr::RecFcn { name, .. } = self.core.ir.expr(expr) {
1298 result.env.bind(name.index(), Sv::AnalysisBound);
1299 }
1300 for bound in bounds {
1301 if bound.domain.is_none() {
1302 return Err(EvalError::unsupported("unbounded analysis domain"));
1303 }
1304 for slot in &bound.vars {
1305 result.env.bind(slot.index(), unknown.clone());
1306 }
1307 }
1308 Ok(result)
1309 }
1310
1311 pub fn eval_scoped(&self, scope: &Scope, expr: ExprId, st: &St) -> Result<Value> {
1316 self.admit_scoped_expr(scope, expr)?;
1317 self.validate_scope(scope)?;
1318 self.validate_state_context(st)?;
1319 let mut env = scope.env.clone();
1320 let ev = self.core.eval(&mut env, st, expr)?;
1321 self.core.force_fcn(ev)
1322 }
1323
1324 pub fn eval_arg(&self, scope: &Scope, arg: &Arg, st: &St) -> Result<Value> {
1331 self.validate_scope(scope)?;
1332 self.validate_state_context(st)?;
1333 match arg {
1334 Arg::Expr { expr, .. } => self.eval_scoped(scope, *expr, st),
1335 Arg::Op { .. } => Err(EvalError::unsupported(
1336 "an operator argument where TLC expects a value",
1337 )),
1338 }
1339 }
1340
1341 pub fn precompute(&self, def: DefId) -> Result<Option<Value>> {
1358 let core = &self.core;
1359 let d = self.admit_def(def)?;
1360 let mut env = Env::new(def, d.depth, d.frame.len(), None, Dyn::default());
1361 let st = St::constant()
1362 .with_control(crate::env::control::CONST | crate::env::control::PRECOMPUTE);
1363 let lock = || {
1366 core.startup_calls
1367 .lock()
1368 .unwrap_or_else(std::sync::PoisonError::into_inner)
1369 };
1370 *lock() = Some(crate::startup_calls::StartupCalls::default());
1371 let ev = core.eval(&mut env, &st, d.body);
1372 if let Some(calls) = lock().take() {
1373 core.startup_call_hits
1374 .fetch_add(calls.hits, std::sync::atomic::Ordering::Relaxed);
1375 }
1376 let ev = ev?;
1377 let Ev::V(v) = ev else {
1378 return Ok(None);
1379 };
1380 if let Some(cell) = core.startup.get(def.index()) {
1381 let _ = cell.set(v.clone());
1382 }
1383 Ok(Some(v))
1384 }
1385
1386 #[must_use]
1388 pub fn precomputed(&self, def: DefId) -> Option<Value> {
1389 self.core
1390 .startup
1391 .get(def.index())
1392 .and_then(|c| c.get())
1393 .cloned()
1394 }
1395}
1396
1397impl crate::core::Core {
1398 pub(crate) fn bind_subst(
1401 self: &Arc<Self>,
1402 env: &Env,
1403 st: &St,
1404 bindings: &[dive_ir::SubstBinding],
1405 cachable: bool,
1406 ) -> Result<Env> {
1407 let outer = env.clone();
1408 let mut env1 = env.clone();
1409 for b in bindings {
1410 let val = match &b.value {
1411 Arg::Expr { expr, pass } => match pass {
1412 Pass::Strict => Sv::from(self.eval(&mut outer.clone(), st, *expr)?),
1413 Pass::Lazy | Pass::Direct => {
1414 Sv::Thunk(Thunk::new(*expr, outer.clone(), cachable))
1415 }
1416 },
1417 Arg::Op { op, .. } => Sv::op(self.op_value(&outer, op)?),
1418 };
1419 env1.dynamic.push(b.decl, val);
1420 }
1421 Ok(env1)
1422 }
1423}
1424
1425#[cfg(test)]
1426#[allow(clippy::expect_used, reason = "owned capture-identity fixtures")]
1427mod operator_capture_tests {
1428 use super::*;
1429 use crate::env::OpVal;
1430
1431 #[test]
1432 fn split_operator_metadata_rejects_foreign_and_captured_contexts() {
1433 let analysis = dive_sema::analyze_source(
1434 "SplitOperator.tla",
1435 "---- MODULE SplitOperator ----\nCONSTANT F(_)\nTarget(v)==v\nRoot==TRUE\n====\n",
1436 &dive_sema::Options::default(),
1437 );
1438 assert!(analysis.accepted());
1439 let ir = Arc::new(dive_ir::lower(&analysis).expect("lower"));
1440 let ev = Evaluator::new(crate::Model::new(ir.clone()), crate::Options::default())
1441 .expect("evaluator");
1442 let def = ir.root_def("Target").expect("Target");
1443 let root = ir.root_def("Root").expect("Root");
1444 let decl = ir.consts()[0];
1445 let mut scope = ev.scope(root).expect("scope");
1446 scope.env.dynamic.push(
1447 decl,
1448 Sv::op(OpVal::Def {
1449 def,
1450 parent: None,
1451 dynamic: None,
1452 }),
1453 );
1454 assert_eq!(
1455 ev.scope_subst_operator(&scope, decl).expect("metadata"),
1456 Some(def)
1457 );
1458 let other = Evaluator::new(crate::Model::new(ir.clone()), crate::Options::default())
1459 .expect("other evaluator");
1460 assert!(other.scope_subst_operator(&scope, decl).is_err());
1461 assert!(
1462 ev.scope_subst_operator(&scope, dive_ir::DeclId(u32::MAX))
1463 .is_err()
1464 );
1465 for (parent, dynamic) in [
1466 (Some(scope.env.frame.clone()), None),
1467 (None, Some(Dyn::default())),
1468 ] {
1469 let mut retained = scope.clone();
1470 retained.env.dynamic.push(
1471 decl,
1472 Sv::op(OpVal::Def {
1473 def,
1474 parent,
1475 dynamic,
1476 }),
1477 );
1478 assert!(
1479 ev.scope_subst_operator(&retained, decl)
1480 .expect("captured metadata")
1481 .is_none()
1482 );
1483 }
1484 }
1485
1486 #[test]
1487 fn same_lexical_frame_is_inspected_under_each_dynamic_context() {
1488 let analysis = dive_sema::analyze_source(
1489 "CaptureIdentity.tla",
1490 "---- MODULE CaptureIdentity ----\nEXTENDS TLC\nCONSTANT A(_)\nGood(v)==v\nEvil(v)==PrintT(v)\nProbe(v)==A(v)\nHolder(F(_),saved)==TRUE\nRoot(a,b)==TRUE\n====\n",
1491 &dive_sema::Options::default(),
1492 );
1493 assert!(analysis.accepted());
1494 let ir = Arc::new(dive_ir::lower(&analysis).expect("lower"));
1495 let ev = Evaluator::new(crate::Model::new(ir.clone()), crate::Options::default())
1496 .expect("evaluator");
1497 let def = |name| ir.root_def(name).expect("definition");
1498 let operator = |def| {
1499 Sv::op(OpVal::Def {
1500 def,
1501 parent: None,
1502 dynamic: None,
1503 })
1504 };
1505 let mut shared = ev.scope(def("Holder")).expect("holder").env;
1506 shared.bind(0, operator(def("Probe")));
1507 shared.bind(1, Sv::AnalysisBound);
1508 let decl = ir
1509 .decls()
1510 .iter()
1511 .position(|d| d.name.as_str() == "A")
1512 .map(|i| dive_ir::DeclId(u32::try_from(i).expect("decl")))
1513 .expect("A");
1514 let contexts: Vec<_> = ["Good", "Evil"]
1515 .into_iter()
1516 .map(|name| {
1517 let mut env = shared.clone();
1518 env.dynamic.push(decl, operator(def(name)));
1519 env
1520 })
1521 .collect();
1522 assert!(Arc::ptr_eq(&contexts[0].frame, &contexts[1].frame));
1523 let mut scope = ev.scope(def("Root")).expect("root");
1524 for (i, env) in contexts.into_iter().enumerate() {
1525 scope.env.bind(
1526 i,
1527 Sv::Thunk(Thunk::new(ir.def(def("Root")).body, env, false)),
1528 );
1529 }
1530 let projected = ev
1531 .scope_operator_captures(&scope, &mut 1_000)
1532 .expect("ownership and work")
1533 .expect("known user targets");
1534 assert!(
1535 projected
1536 .iter()
1537 .any(|(expr, _)| *expr == ir.def(def("Evil")).body)
1538 );
1539 let probe_contexts: Vec<_> = projected
1540 .iter()
1541 .filter(|(expr, _)| *expr == ir.def(def("Probe")).body)
1542 .collect();
1543 assert_eq!(probe_contexts.len(), 2);
1544 let bindings: Vec<_> = probe_contexts
1545 .iter()
1546 .map(
1547 |(_, context)| match context.env.dynamic.lookup(decl).expect("substitution") {
1548 Sv::Op(op) => match &**op {
1549 OpVal::Def { def, .. } => *def,
1550 _ => def("Root"),
1551 },
1552 _ => def("Root"),
1553 },
1554 )
1555 .collect();
1556 assert!(bindings.contains(&def("Good")) && bindings.contains(&def("Evil")));
1557 let mut at = scope.clone();
1558 at.env.dynamic.at = Some(true.into());
1559 assert!(
1560 ev.scope_operator_captures(&at, &mut 1_000)
1561 .expect("at refusal")
1562 .is_none()
1563 );
1564 assert_eq!(ev.take_output(), Vec::<String>::new());
1565 }
1566}
1567
1568#[cfg(test)]
1569mod bounded_count_tests {
1570 use super::*;
1571
1572 #[test]
1573 fn no_columns_is_one_binding_but_empty_domain_is_zero_even_at_zero_limit() {
1574 assert_eq!(Evaluator::bounded_binding_count(&[], 1), Ok(1));
1575 assert_eq!(
1576 Evaluator::bounded_binding_count(&[], 0),
1577 Err(EvalError::resource_limit("quantifier bindings"))
1578 );
1579 let columns = vec![(vec![0], false, Arc::<[Value]>::from([]))];
1580 assert_eq!(Evaluator::bounded_binding_count(&columns, 0), Ok(0));
1581 }
1582}