1#![allow(
91 clippy::too_many_arguments,
92 clippy::too_many_lines,
93 clippy::many_single_char_names,
94 reason = "each rule ports one TLC method and is kept together for comparison, with the short names of the TLC code"
95)]
96
97use std::sync::Arc;
98
99use dive_ir::actions::{ActionName, ActionTree, Split, label};
100use dive_ir::{Arg, BuiltinOp, DefId, DefScope, Expr, ExprId, JunctionKind, OpRef, QuantKind};
101use dive_value::Value;
102
103use crate::core::{Core, is_enumerable};
104use crate::env::{Env, Ev, OpVal, St, StateRef, Sv, Thunk, control};
105use crate::error::{Ec, ErrorClass, EvalError, Result};
106pub use crate::scope::Scope;
107use crate::{ConstBinding, Evaluator};
108
109mod cdot;
110
111pub type StateVals = Arc<[Option<Value>]>;
113
114#[derive(Clone, Copy, Debug, PartialEq, Eq)]
116pub enum Flow {
117 Continue,
119 Stop,
122}
123
124#[derive(Clone, Debug)]
128pub struct Action {
129 pub(crate) expr: ExprId,
130 pub(crate) env: Env,
131 owner: Arc<dive_ir::Ir>,
132 names: Arc<dive_value::Interner>,
133 context: std::sync::Weak<crate::core::Core>,
134 name: ActionName,
135 params: Vec<(String, Value)>,
136 label: String,
137 id: usize,
138}
139
140impl Action {
141 #[must_use]
143 pub fn expr(&self) -> ExprId {
144 self.expr
145 }
146
147 #[must_use]
150 pub fn scope(&self) -> Scope {
151 Scope {
152 env: self.env.clone(),
153 owner: self.owner.clone(),
154 names: self.names.clone(),
155 context: self.context.clone(),
156 wrapper: None,
157 }
158 }
159
160 #[must_use]
162 pub fn name(&self) -> ActionName {
163 self.name
164 }
165
166 #[must_use]
169 pub fn params(&self) -> &[(String, Value)] {
170 &self.params
171 }
172
173 #[must_use]
176 pub fn label(&self) -> &str {
177 &self.label
178 }
179
180 #[must_use]
183 pub fn id(&self) -> usize {
184 self.id
185 }
186}
187
188#[derive(Debug)]
190pub struct Successor<'a> {
191 pub state: &'a [Option<Value>],
194 pub action: &'a Action,
196 pub ordinal: u64,
199}
200
201impl Successor<'_> {
202 #[must_use]
206 pub fn complete(&self) -> bool {
207 self.state.iter().all(Option::is_some)
208 }
209
210 #[must_use]
212 pub fn unassigned(&self) -> Vec<usize> {
213 self.state
214 .iter()
215 .enumerate()
216 .filter_map(|(i, v)| v.is_none().then_some(i))
217 .collect()
218 }
219}
220
221#[derive(Clone, Copy, Debug, PartialEq, Eq)]
223pub struct Outcome {
224 pub emitted: u64,
226 pub intermediate: u64,
232 pub stopped: bool,
234}
235
236#[derive(Clone, Debug)]
239pub struct NextError {
240 pub error: EvalError,
242 pub emitted: u64,
244 pub intermediate: u64,
247 pub action: Option<usize>,
249}
250
251impl std::fmt::Display for NextError {
252 fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
253 write!(f, "{} (after {} states)", self.error, self.emitted)
254 }
255}
256
257impl std::error::Error for NextError {}
258
259impl Evaluator {
264 pub fn init_predicate(&self, def: DefId, id: usize) -> Result<Action> {
271 let d = self.admit_def(def)?;
272 if !d.params.is_empty() {
273 return Err(EvalError::bug(format!("{} takes arguments", d.name)));
274 }
275 self.predicate(def, d.body, ActionName::Def(def), id)
276 }
277
278 pub fn predicate(
285 &self,
286 frame: DefId,
287 expr: ExprId,
288 name: ActionName,
289 id: usize,
290 ) -> Result<Action> {
291 self.predicate_in(&self.scope(frame)?, expr, name, id)
292 }
293
294 pub fn predicate_in(
299 &self,
300 scope: &Scope,
301 expr: ExprId,
302 name: ActionName,
303 id: usize,
304 ) -> Result<Action> {
305 self.validate_scope(scope)?;
306 self.admit_scoped_expr(scope, expr)?;
307 if let ActionName::Def(d) = name {
308 self.admit_def(d)?;
309 }
310 Ok(Action {
311 owner: self.core.ir.clone(),
312 names: self.core.names.clone(),
313 context: Arc::downgrade(&self.core),
314 expr,
315 env: scope.env.clone(),
316 name,
317 params: Vec::new(),
318 label: label(&self.core.ir, name, &[], scope.wrapper.unwrap_or(expr)),
319 id,
320 })
321 }
322
323 pub fn actions(&self, split: &Split, frame: DefId, first_id: usize) -> Result<Vec<Action>> {
334 self.actions_in(&self.scope(frame)?, split, first_id)
335 }
336
337 pub fn actions_in(&self, scope: &Scope, split: &Split, first_id: usize) -> Result<Vec<Action>> {
345 self.validate_scope(scope)?;
346 self.admit_split(split)?;
347 let env = scope.env.clone();
348 let mut x = Expander {
349 core: &self.core,
350 split,
351 out: Vec::new(),
352 stack: Vec::new(),
353 first_id,
354 };
355 let r = on_stack(move || x.expand(&split.root, &env).map(|()| x.out));
357 match r {
358 Ok(Ok(v)) => Ok(v),
359 Ok(Err(Split1::Throw(e))) => Err(EvalError::unsupported(format!(
360 "a next-state relation TLC cannot split ({})",
361 e.message().lines().next().unwrap_or("")
362 ))),
363 Ok(Err(Split1::Fatal(e))) | Err(e) => Err(e),
364 }
365 }
366
367 fn admit_split(&self, split: &Split) -> Result<()> {
368 let mut work = vec![&split.root];
369 for (&def, tree) in &split.defs {
370 self.admit_def(def)?;
371 work.push(tree);
372 }
373 let mut remaining = 65_536_usize;
374 while let Some(tree) = work.pop() {
375 remaining = remaining
376 .checked_sub(1)
377 .ok_or_else(|| EvalError::resource_limit("action split admission"))?;
378 let (expr, name) = match tree {
379 ActionTree::Disj { expr, children } => {
380 work.extend(children);
381 (*expr, None)
382 }
383 ActionTree::Exists { expr, name, body } => {
384 work.push(body);
385 (*expr, Some(*name))
386 }
387 ActionTree::Scope { expr, body } => {
388 work.push(body);
389 (*expr, None)
390 }
391 ActionTree::Inline { expr, def, .. } => {
392 self.admit_def(*def)?;
393 (*expr, None)
394 }
395 ActionTree::Leaf { expr, name } | ActionTree::Configured { expr, name } => {
396 (*expr, Some(*name))
397 }
398 ActionTree::Throws { expr } => (*expr, None),
399 };
400 self.admit_expr(expr)?;
401 if let Some(ActionName::Def(def)) = name {
402 self.admit_def(def)?;
403 }
404 if work.len() > remaining {
405 return Err(EvalError::resource_limit("action split admission"));
406 }
407 }
408 Ok(())
409 }
410
411 pub fn eval_action(&self, action: &Action, st: &St) -> Result<Value> {
418 self.validate_scope(&action.scope())?;
419 self.validate_state_context(st)?;
420 let ev = self.core.eval(&mut action.env.clone(), st, action.expr)?;
421 self.core.force_fcn(ev)
422 }
423
424 #[must_use]
427 pub fn action_shares_side_effects(&self, action: &Action) -> bool {
428 self.scope_shares_side_effects(&action.scope())
429 }
430
431 pub fn init_states(
440 &self,
441 inits: &[Action],
442 sink: &mut dyn FnMut(&Successor<'_>) -> Flow,
443 ) -> std::result::Result<Outcome, NextError> {
444 self.init_states_mode(inits, sink, false)
445 }
446
447 pub fn init_states_diagnostic(
454 &self,
455 inits: &[Action],
456 sink: &mut dyn FnMut(&Successor<'_>) -> Flow,
457 ) -> std::result::Result<Outcome, NextError> {
458 self.init_states_mode(inits, sink, true)
459 }
460
461 fn init_states_mode(
462 &self,
463 inits: &[Action],
464 sink: &mut dyn FnMut(&Successor<'_>) -> Flow,
465 diagnostic: bool,
466 ) -> std::result::Result<Outcome, NextError> {
467 for action in inits {
468 self.validate_scope(&action.scope())
469 .map_err(|error| NextError {
470 error,
471 emitted: 0,
472 intermediate: 0,
473 action: None,
474 })?;
475 }
476 let Some(first) = inits.first() else {
477 return Ok(Outcome {
478 emitted: 0,
479 intermediate: 0,
480 stopped: false,
481 });
482 };
483 let nvars = self.core.ir.vars().len();
484 let mut acts: Acts = None;
485 for a in inits[1..].iter().rev() {
486 acts = cons(&acts, Kind::Pred, a.expr, &a.env);
487 }
488 let mut g = Gen {
489 core: &self.core,
490 init: true,
491 diagnostic,
492 s0: StateRef::Empty,
493 s1: vec![None; nvars].into(),
494 action: first,
495 ordinal: 0,
496 emitted: 0,
497 intermediate: 0,
498 sink,
499 choices: None,
500 };
501 let r = g.step(first.expr, &acts, &first.env);
502 g.finish(r, None)
503 }
504
505 pub fn next_states(
514 &self,
515 action: &Action,
516 s0: &StateVals,
517 ordinal: u64,
518 sink: &mut dyn FnMut(&Successor<'_>) -> Flow,
519 ) -> std::result::Result<Outcome, NextError> {
520 self.next_states_mode(action, s0, ordinal, sink, false, None)
521 }
522
523 pub fn next_states_generation(
533 &self,
534 action: &Action,
535 s0: &StateVals,
536 ordinal: u64,
537 choose: &mut dyn FnMut(u64) -> u64,
538 sink: &mut dyn FnMut(&Successor<'_>) -> Flow,
539 ) -> std::result::Result<Outcome, NextError> {
540 self.next_states_mode(action, s0, ordinal, sink, false, Some(choose))
541 }
542
543 pub fn next_states_diagnostic(
561 &self,
562 action: &Action,
563 s0: &StateVals,
564 ordinal: u64,
565 sink: &mut dyn FnMut(&Successor<'_>) -> Flow,
566 ) -> std::result::Result<Outcome, NextError> {
567 self.next_states_mode(action, s0, ordinal, sink, true, None)
568 }
569
570 fn next_states_mode(
571 &self,
572 action: &Action,
573 s0: &StateVals,
574 ordinal: u64,
575 sink: &mut dyn FnMut(&Successor<'_>) -> Flow,
576 diagnostic: bool,
577 choices: Option<&mut dyn FnMut(u64) -> u64>,
578 ) -> std::result::Result<Outcome, NextError> {
579 self.validate_scope(&action.scope())
580 .map_err(|error| NextError {
581 error,
582 emitted: 0,
583 intermediate: 0,
584 action: Some(action.id),
585 })?;
586 let mut g = Gen {
587 core: &self.core,
588 init: false,
589 diagnostic,
590 s0: StateRef::Vals(s0.clone()),
591 s1: vec![None; s0.len()].into(),
592 action,
593 ordinal,
594 emitted: 0,
595 intermediate: 0,
596 sink,
597 choices,
598 };
599 let r = g.step(action.expr, &None, &action.env);
600 g.finish(r, Some(action.id))
601 }
602
603 pub fn successors(
609 &self,
610 actions: &[Action],
611 s0: &StateVals,
612 sink: &mut dyn FnMut(&Successor<'_>) -> Flow,
613 ) -> std::result::Result<Outcome, NextError> {
614 let mut total = 0u64;
615 let mut intermediate = 0u64;
616 for a in actions {
617 match self.next_states(a, s0, total, sink) {
618 Ok(o) => {
619 total += o.emitted;
620 intermediate += o.intermediate;
621 if o.stopped {
622 return Ok(Outcome {
623 emitted: total,
624 intermediate,
625 stopped: true,
626 });
627 }
628 }
629 Err(mut e) => {
630 e.emitted += total;
631 e.intermediate += intermediate;
632 return Err(e);
633 }
634 }
635 }
636 Ok(Outcome {
637 emitted: total,
638 intermediate,
639 stopped: false,
640 })
641 }
642}
643
644fn on_stack<T: Send>(f: impl FnOnce() -> T + Send) -> Result<T> {
647 std::thread::scope(|s| {
648 std::thread::Builder::new()
649 .stack_size(crate::RECOMMENDED_STACK)
650 .spawn_scoped(s, f)
651 .map_err(|e| EvalError::resource_limit(format!("cannot start a thread: {e}")))?
652 .join()
653 .map_err(|_| EvalError::bug("action expansion panicked"))
654 })
655}
656
657#[derive(Clone, Copy, Debug, PartialEq, Eq)]
662enum Kind {
663 Pred,
665 Unchanged,
667 Changed,
669}
670
671#[derive(Debug)]
672struct Item {
673 kind: Kind,
674 expr: ExprId,
675 env: Env,
676 next: Acts,
677}
678
679type Acts = Option<Arc<Item>>;
681
682#[allow(
683 clippy::unnecessary_wraps,
684 reason = "a cons cell is a non-empty list, used where lists are expected"
685)]
686fn cons(acts: &Acts, kind: Kind, expr: ExprId, env: &Env) -> Acts {
687 Some(Arc::new(Item {
688 kind,
689 expr,
690 env: env.clone(),
691 next: acts.clone(),
692 }))
693}
694
695struct Gen<'a, 's, 'c> {
701 core: &'a Arc<Core>,
702 init: bool,
703 diagnostic: bool,
704 s0: StateRef,
706 s1: StateVals,
708 action: &'a Action,
709 ordinal: u64,
710 emitted: u64,
711 intermediate: u64,
713 sink: &'s mut dyn FnMut(&Successor<'_>) -> Flow,
714 choices: Option<&'c mut dyn FnMut(u64) -> u64>,
717}
718
719impl Gen<'_, '_, '_> {
720 fn finish(
721 &self,
722 r: Result<Flow>,
723 action: Option<usize>,
724 ) -> std::result::Result<Outcome, NextError> {
725 match r {
726 Ok(flow) => Ok(Outcome {
727 emitted: self.emitted,
728 intermediate: self.intermediate,
729 stopped: flow == Flow::Stop,
730 }),
731 Err(error) => Err(NextError {
732 error,
733 emitted: self.emitted,
734 intermediate: self.intermediate,
735 action,
736 }),
737 }
738 }
739
740 fn st(&self) -> St {
742 if self.init {
743 St {
745 s0: StateRef::Vals(self.s1.clone()),
746 s1: StateRef::Empty,
747 control: control::INIT
748 | if self.diagnostic {
749 control::DIAGNOSTIC
750 } else {
751 0
752 },
753 }
754 } else {
755 St {
756 s0: self.s0.clone(),
757 s1: StateRef::Vals(self.s1.clone()),
758 control: if self.diagnostic {
759 control::DIAGNOSTIC
760 } else {
761 control::CLEAR
762 },
763 }
764 }
765 }
766
767 fn st_cache(&self) -> St {
770 if self.init {
771 St {
772 s0: StateRef::Vals(self.s1.clone()),
773 s1: StateRef::Null,
774 control: control::CLEAR,
775 }
776 } else {
777 self.st()
778 }
779 }
780
781 fn what(&self) -> &'static str {
782 if self.init {
783 "initial states"
784 } else {
785 "next states"
786 }
787 }
788
789 fn bind(&mut self, var: usize, v: Value) {
790 if let Some(slot) = Arc::make_mut(&mut self.s1).get_mut(var) {
791 *slot = Some(v);
792 }
793 }
794
795 fn unbind(&mut self, var: usize) {
796 if let Some(slot) = Arc::make_mut(&mut self.s1).get_mut(var) {
797 *slot = None;
798 }
799 }
800
801 fn all_assigned(&self) -> bool {
802 self.s1.iter().all(Option::is_some)
803 }
804
805 fn emit(&mut self) -> Flow {
806 let succ = Successor {
807 state: &self.s1,
808 action: self.action,
809 ordinal: self.ordinal,
810 };
811 let flow = (self.sink)(&succ);
812 self.ordinal += 1;
813 self.emitted += 1;
814 flow
815 }
816
817 fn eval(&self, env: &Env, e: ExprId) -> Result<Ev> {
818 self.core.eval(&mut env.clone(), &self.st(), e)
819 }
820
821 fn eval_v(&self, env: &Env, e: ExprId) -> Result<Value> {
822 self.core.eval_v(&mut env.clone(), &self.st(), e)
823 }
824
825 fn cont(&mut self, acts: &Acts) -> Result<Flow> {
828 let Some(item) = acts else {
829 return Ok(self.emit());
830 };
831 if self.init {
832 if self.all_assigned() {
833 return self.init_all_assigned(acts);
834 }
835 return self.step(item.expr, &item.next, &item.env);
836 }
837 if self.core.opts.warnings && self.all_assigned() {
838 return self.next_all_assigned(acts);
839 }
840 match item.kind {
841 Kind::Pred => self.step(item.expr, &item.next, &item.env),
842 Kind::Unchanged => self.unchanged(item.expr, &item.next, &item.env),
843 Kind::Changed => {
844 if self.changed(item)? {
845 self.cont(&item.next)
846 } else {
847 Ok(Flow::Continue)
848 }
849 }
850 }
851 }
852
853 fn changed(&self, item: &Item) -> Result<bool> {
855 let s0 = St {
856 s0: self.s0.clone(),
857 s1: StateRef::Empty,
858 control: control::CLEAR,
859 };
860 let s1 = St {
861 s0: StateRef::Vals(self.s1.clone()),
862 s1: StateRef::Empty,
863 control: control::CLEAR,
864 };
865 let v1 = self.core.eval_v(&mut item.env.clone(), &s0, item.expr)?;
866 let v2 = self.core.eval_v(&mut item.env.clone(), &s1, item.expr)?;
867 Ok(!self.core.equals(&v1, &v2)?)
868 }
869
870 fn init_all_assigned(&mut self, acts: &Acts) -> Result<Flow> {
873 let mut cur = acts.clone();
874 while let Some(item) = cur.take() {
875 let v = self.eval(&item.env, item.expr)?;
876 match v {
877 Ev::V(Value::Bool(true)) => {}
878 Ev::V(Value::Bool(false)) => {
879 return Ok(Flow::Continue);
880 }
881 other => return Err(self.expected_bool(&other, item.expr)),
882 }
883 cur.clone_from(&item.next);
884 }
885 Ok(self.emit())
886 }
887
888 fn next_all_assigned(&mut self, acts: &Acts) -> Result<Flow> {
890 let mut cur = acts.clone();
891 while let Some(item) = cur.take() {
892 match item.kind {
893 Kind::Pred => {
894 let v = self.eval(&item.env, item.expr)?;
895 match v {
896 Ev::V(Value::Bool(true)) => {}
897 Ev::V(Value::Bool(false)) => return Ok(Flow::Continue),
898 other => return Err(self.expected_bool(&other, item.expr)),
899 }
900 }
901 Kind::Unchanged => return self.unchanged(item.expr, &item.next, &item.env),
902 Kind::Changed => {
903 if !self.changed(&item)? {
904 return Ok(Flow::Continue);
905 }
906 }
907 }
908 cur.clone_from(&item.next);
909 }
910 Ok(self.emit())
911 }
912
913 fn expected_bool(&self, v: &Ev, at: ExprId) -> EvalError {
915 EvalError::coded(
916 Ec::ExpectedExpressionInComputing,
917 format!(
918 "In computing {}, TLC expected a boolean expression,\nbut instead found {}.\n{}",
919 self.what(),
920 self.core.ev_string(v),
921 self.core.loc(at)
922 ),
923 )
924 }
925
926 fn after_bool(&mut self, v: &Ev, acts: &Acts, at: ExprId) -> Result<Flow> {
928 match v {
929 Ev::V(Value::Bool(true)) => self.cont(acts),
930 Ev::V(Value::Bool(false)) => Ok(Flow::Continue),
931 other => Err(self.expected_bool(other, at)),
932 }
933 }
934
935 fn default_rule(&mut self, e: ExprId, acts: &Acts, env: &Env) -> Result<Flow> {
937 let v = self.eval(env, e)?;
938 match v {
939 Ev::V(Value::Bool(true)) => self.cont(acts),
940 Ev::V(Value::Bool(false)) => Ok(Flow::Continue),
941 other if self.init => Err(EvalError::general(format!(
942 "In computing initial states, TLC expected a boolean expression,\nbut instead found {}.\n{}",
943 self.core.ev_string(&other),
944 self.core.loc(e)
945 ))),
946 _ if matches!(self.core.ir.expr(e), Expr::Num(_) | Expr::Str(_)) => {
947 Err(EvalError::general(format!(
948 "The next state relation is not a boolean expression.\n{}",
949 self.core.loc(e)
950 )))
951 }
952 other => Err(self.expected_bool(&other, e)),
953 }
954 }
955
956 fn step(&mut self, e: ExprId, acts: &Acts, env: &Env) -> Result<Flow> {
959 self.step_inner(e, acts, env).map_err(|error| error.at(e))
960 }
961
962 fn step_inner(&mut self, e: ExprId, acts: &Acts, env: &Env) -> Result<Flow> {
963 let core = self.core;
964 let _g = core.enter(e)?;
965 let node = core.ir.node(e);
966 match &node.expr {
967 Expr::Junction { kind, items, .. } => match kind {
968 JunctionKind::And => {
969 let mut acts1 = acts.clone();
971 for &i in items.iter().skip(1).rev() {
972 acts1 = cons(&acts1, Kind::Pred, i, env);
973 }
974 match items.first() {
975 Some(&first) => self.step(first, &acts1, env),
976 None => self.cont(acts),
977 }
978 }
979 JunctionKind::Or => {
980 if let Some(choose) = self.choices.as_deref_mut() {
982 let len = u64::try_from(items.len()).map_err(|_| {
983 EvalError::resource_limit("generation disjunction size")
984 })?;
985 let mut order = crate::generation::IndexOrder::new(len, choose)?;
986 while let Some(index) = order.current() {
987 let index = usize::try_from(index).map_err(|_| {
988 EvalError::resource_limit("generation branch index")
989 })?;
990 if self.step(items[index], acts, env)? == Flow::Stop {
991 return Ok(Flow::Stop);
992 }
993 if !order.advance() {
994 break;
995 }
996 }
997 return Ok(Flow::Continue);
998 }
999 for &i in items {
1000 if self.step(i, acts, env)? == Flow::Stop {
1001 return Ok(Flow::Stop);
1002 }
1003 }
1004 Ok(Flow::Continue)
1005 }
1006 },
1007 Expr::Quant {
1008 kind: QuantKind::Exists,
1009 bounds,
1010 body,
1011 } if bounds.iter().all(|b| b.domain.is_some()) => {
1012 let st = self.st();
1014 if let Some(choose) = self.choices.as_deref_mut() {
1015 let mut inner = env.clone();
1016 let mut contexts =
1017 core.generation_contexts(&mut inner, &st, bounds, e, choose)?;
1018 while contexts.bind(core, &mut inner)? {
1019 if self.step(*body, acts, &inner)? == Flow::Stop {
1020 return Ok(Flow::Stop);
1021 }
1022 contexts.advance();
1023 }
1024 return Ok(Flow::Continue);
1025 }
1026 let mut flow = Flow::Continue;
1027 let mut err: Option<EvalError> = None;
1028 let body = *body;
1029 core.for_each_context(&mut env.clone(), &st, bounds, e, &mut |_, env1| match self
1030 .step(body, acts, env1)
1031 {
1032 Ok(Flow::Continue) => Ok(true),
1033 Ok(Flow::Stop) => {
1034 flow = Flow::Stop;
1035 Ok(false)
1036 }
1037 Err(x) => {
1038 err = Some(x);
1039 Ok(false)
1040 }
1041 })?;
1042 match err {
1043 Some(x) => Err(x),
1044 None => Ok(flow),
1045 }
1046 }
1047 Expr::Quant {
1048 kind: QuantKind::Forall,
1049 bounds,
1050 body,
1051 } if bounds.iter().all(|b| b.domain.is_some()) => {
1052 let st = self.st();
1054 let mut envs: Vec<Env> = Vec::new();
1055 core.for_each_context(&mut env.clone(), &st, bounds, e, &mut |_, env1| {
1056 envs.push(env1.clone());
1057 Ok(true)
1058 })?;
1059 let Some((first, rest)) = envs.split_first() else {
1060 return self.cont(acts);
1061 };
1062 let mut acts1 = acts.clone();
1063 for c2 in rest {
1064 acts1 = cons(&acts1, Kind::Pred, *body, c2);
1065 }
1066 self.step(*body, &acts1, first)
1067 }
1068 Expr::If { cond, then, other } => {
1069 let g = self.eval(env, *cond)?;
1071 let b = match g {
1072 Ev::V(Value::Bool(b)) => b,
1073 other => {
1074 let kind = core.kind_of(&other);
1075 return Err(EvalError::general(if self.init {
1076 format!(
1077 "In computing initial states, a non-boolean expression ({kind}) was used as the condition of an IF.\n{}",
1078 core.loc(e)
1079 )
1080 } else {
1081 format!(
1082 "In computing next states, a non-boolean expression ({kind}) was used as the condition of an IF.{}",
1083 core.loc(e)
1084 )
1085 }));
1086 }
1087 };
1088 self.step(if b { *then } else { *other }, acts, env)
1089 }
1090 Expr::Case { arms, other } => {
1091 if self.choices.is_some() {
1092 return Err(EvalError::unsupported(
1093 "constructive generation of CASE actions",
1094 ));
1095 }
1096 for arm in arms {
1098 match self.eval(env, arm.guard)? {
1099 Ev::V(Value::Bool(true)) => return self.step(arm.value, acts, env),
1100 Ev::V(Value::Bool(false)) => {}
1101 other => {
1102 return Err(EvalError::general(format!(
1103 "In computing {}, a non-boolean expression ({}) was used as a guard condition of a CASE.\n{}",
1104 self.what(),
1105 core.kind_of(&other),
1106 core.loc(arm.value)
1107 )));
1108 }
1109 }
1110 }
1111 match other {
1112 Some(o) => self.step(*o, acts, env),
1113 None => Err(EvalError::general(format!(
1114 "In computing {}, TLC encountered a CASE with no conditions true.\n{}",
1115 self.what(),
1116 core.loc(e)
1117 ))),
1118 }
1119 }
1120 Expr::Implies(a, b) => {
1121 match self.eval(env, *a)? {
1123 Ev::V(Value::Bool(true)) => self.step(*b, acts, env),
1124 Ev::V(Value::Bool(false)) => self.cont(acts),
1125 other => {
1126 let kind = core.kind_of(&other);
1127 Err(EvalError::general(if self.init {
1128 format!(
1129 "In computing initial states of a predicate of form P => Q, P was {kind}\n.{}",
1130 core.loc(e)
1131 )
1132 } else {
1133 format!(
1134 "In computing next states of a predicate of the form P => Q, P was\n{kind}.\n{}",
1135 core.loc(e)
1136 )
1137 }))
1138 }
1139 }
1140 }
1141 Expr::Builtin {
1142 op: op @ (BuiltinOp::Eq | BuiltinOp::In | BuiltinOp::Subseteq),
1143 args,
1144 } if args.len() == 2 => self.assign(*op, args[0], args[1], e, acts, env),
1145 Expr::Unchanged(a) if !self.init => self.unchanged(*a, acts, env),
1146 Expr::Cdot(a, b) if !self.init => self.cdot(*a, *b, acts, env, e),
1147 Expr::StepBox { action, sub } if !self.init => {
1148 if self.step(*action, acts, env)? == Flow::Stop {
1150 return Ok(Flow::Stop);
1151 }
1152 self.unchanged(*sub, acts, env)
1153 }
1154 Expr::StepAngle { action, sub } if !self.init => {
1155 let acts1 = cons(acts, Kind::Changed, *sub, env);
1157 self.step(*action, &acts1, env)
1158 }
1159 Expr::Let { defs, body } => {
1160 let env1 = core.bind_let_uncached(env, defs);
1163 self.step(*body, acts, &env1)
1164 }
1165 Expr::Subst { bindings, body } => {
1166 let env1 = core.bind_subst(env, &self.st(), bindings, false)?;
1168 self.step(*body, acts, &env1)
1169 }
1170 Expr::Label { body, .. } | Expr::Selected(body) => self.step(*body, acts, env),
1171 Expr::FcnApply { fcn, arg } => self.fcn_apply(*fcn, *arg, e, acts, env),
1172 Expr::Def(_)
1173 | Expr::Apply { .. }
1174 | Expr::Local(_)
1175 | Expr::Const(_)
1176 | Expr::SubstRef { primed: false, .. } => self.user_op(e, acts, env),
1177 _ => self.default_rule(e, acts, env),
1178 }
1179 }
1180
1181 fn assign(
1184 &mut self,
1185 op: BuiltinOp,
1186 lhs: ExprId,
1187 rhs: ExprId,
1188 e: ExprId,
1189 acts: &Acts,
1190 env: &Env,
1191 ) -> Result<Flow> {
1192 let core = self.core;
1193 let var = if self.init {
1194 core.var_of(env, lhs, false)?
1195 } else {
1196 core.primed_var(env, lhs, false)?
1197 };
1198 let Some(var) = var else {
1199 let v = self.eval(env, e)?;
1200 return match v {
1201 Ev::V(Value::Bool(true)) => self.cont(acts),
1202 Ev::V(Value::Bool(false)) => Ok(Flow::Continue),
1203 _ => Err(EvalError::bug("=, \\in or \\subseteq not boolean")),
1204 };
1205 };
1206 let lval = self.s1.get(var).cloned().flatten();
1207 match op {
1208 BuiltinOp::Eq => {
1209 let rval = core.embed(self.eval(env, rhs)?)?;
1210 match lval {
1211 None => {
1212 self.bind(var, rval);
1213 let flow = self.cont(acts);
1214 self.unbind(var);
1215 flow
1216 }
1217 Some(l) => {
1218 if core.equals(&l, &rval)? {
1219 self.cont(acts)
1220 } else {
1221 Ok(Flow::Continue)
1222 }
1223 }
1224 }
1225 }
1226 BuiltinOp::In => {
1227 let rval = self.eval_v(env, rhs)?;
1228 match lval {
1229 None => {
1230 let Value::Set(s) = &rval else {
1231 return Err(self.not_enumerable_in(e));
1232 };
1233 if !is_enumerable(&rval) {
1234 return Err(self.not_enumerable_in(e));
1235 }
1236 if let Some((lo, hi)) = s.as_interval() {
1237 return self.bind_interval(var, lo, hi, acts);
1243 }
1244 if let Some(elements) = core.in_element_stream(s)? {
1245 for value in elements.with_owner(rval) {
1246 let value = value?;
1247 if self.bind_value(var, value, acts)? == Flow::Stop {
1248 return Ok(Flow::Stop);
1249 }
1250 }
1251 return Ok(Flow::Continue);
1252 }
1253 let elems = core.in_elements(s)?;
1254 self.bind_each(var, &elems, acts)
1255 }
1256 Some(l) => {
1257 if core.member(&l, &rval)? {
1258 self.cont(acts)
1259 } else {
1260 Ok(Flow::Continue)
1261 }
1262 }
1263 }
1264 }
1265 _ => {
1266 let rset = self.eval_v(env, rhs)?;
1267 if !matches!(rset, Value::Set(_)) {
1268 return Err(EvalError::unsupported(format!(
1269 "x' \\subseteq S where S is not a set ({})",
1270 core.loc(e)
1271 )));
1272 }
1273 let rval = Value::subset(rset, core.ctx);
1274 match lval {
1275 None => {
1276 let Value::Set(s) = &rval else {
1277 return Err(EvalError::bug("SUBSET is not a set"));
1278 };
1279 let elems = core.explore(s)?;
1280 self.bind_each(var, &elems, acts)
1281 }
1282 Some(l) => {
1283 if core.member(&l, &rval)? {
1284 self.cont(acts)
1285 } else {
1286 Ok(Flow::Continue)
1287 }
1288 }
1289 }
1290 }
1291 }
1292 }
1293
1294 fn not_enumerable_in(&self, e: ExprId) -> EvalError {
1295 EvalError::general(format!(
1296 "In computing {}, the right side of \\IN is not enumerable.\n{}",
1297 self.what(),
1298 self.core.loc(e)
1299 ))
1300 }
1301
1302 fn bind_each(&mut self, var: usize, elems: &[Value], acts: &Acts) -> Result<Flow> {
1303 for x in elems {
1304 if self.bind_value(var, x.clone(), acts)? == Flow::Stop {
1305 return Ok(Flow::Stop);
1306 }
1307 }
1308 Ok(Flow::Continue)
1309 }
1310
1311 fn bind_value(&mut self, var: usize, value: Value, acts: &Acts) -> Result<Flow> {
1312 self.core.loop_work()?;
1315 self.bind(var, value);
1316 let flow = self.cont(acts);
1317 self.unbind(var);
1318 flow
1319 }
1320
1321 fn bind_interval(
1322 &mut self,
1323 var: usize,
1324 lo: &dive_value::Int,
1325 hi: &dive_value::Int,
1326 acts: &Acts,
1327 ) -> Result<Flow> {
1328 if let (Some(lo), Some(hi)) = (lo.to_i64(), hi.to_i64()) {
1329 for value in lo..=hi {
1330 if self.bind_value(var, Value::Int(value), acts)? == Flow::Stop {
1331 return Ok(Flow::Stop);
1332 }
1333 }
1334 } else {
1335 let mut value = lo.clone();
1336 while value <= *hi {
1337 if self.bind_value(var, Value::int(value.clone()), acts)? == Flow::Stop {
1338 return Ok(Flow::Stop);
1339 }
1340 if value == *hi {
1341 break;
1342 }
1343 value = value.add(&dive_value::Int::ONE, dive_value::IntMode::Big)?;
1344 }
1345 }
1346 Ok(Flow::Continue)
1347 }
1348
1349 fn unchanged(&mut self, e: ExprId, acts: &Acts, env: &Env) -> Result<Flow> {
1351 let core = self.core;
1352 let _g = core.enter(e)?;
1353 if let Some(var) = core.var_of(env, e, false)? {
1354 let name = &core.ir.decl(core.ir.vars()[var]).name;
1355 let Some(val0) = core.state_variable(&self.s0, name, Some(var))?.cloned() else {
1356 return Err(EvalError::bug(
1357 "UNCHANGED of a variable the current state lacks",
1358 ));
1359 };
1360 return match self.s1.get(var).cloned().flatten() {
1361 None => {
1362 self.bind(var, val0);
1363 let flow = self.cont(acts);
1364 self.unbind(var);
1365 flow
1366 }
1367 Some(val1) => {
1368 if core.equals(&val0, &val1)? {
1369 self.cont(acts)
1370 } else {
1371 core.unchanged_warning(var, e);
1372 Ok(Flow::Continue)
1373 }
1374 }
1375 };
1376 }
1377 match &core.ir.node(e).expr {
1378 Expr::Tuple(items) => {
1379 let Some((&first, rest)) = items.split_first() else {
1380 return self.cont(acts);
1381 };
1382 let mut acts1 = acts.clone();
1383 for &i in rest.iter().rev() {
1384 acts1 = cons(&acts1, Kind::Unchanged, i, env);
1385 }
1386 self.unchanged(first, &acts1, env)
1387 }
1388 _ => match core.zero_arity_target(env, e)? {
1389 Target::Body(env1, body) => self.unchanged(body, acts, &env1),
1390 Target::Value => self.verify_unchanged(e, acts, env),
1391 },
1392 }
1393 }
1394
1395 fn verify_unchanged(&mut self, e: ExprId, acts: &Acts, env: &Env) -> Result<Flow> {
1397 let st0 = St {
1398 s0: self.s0.clone(),
1399 s1: StateRef::Empty,
1400 control: control::CLEAR,
1401 };
1402 let st1 = St {
1403 s0: StateRef::Vals(self.s1.clone()),
1404 s1: StateRef::Null,
1405 control: control::CLEAR,
1406 };
1407 let v0 = self.core.eval_v(&mut env.clone(), &st0, e)?;
1408 let v1 = self.core.eval_v(&mut env.clone(), &st1, e)?;
1409 if self.core.equals(&v0, &v1)? {
1410 self.cont(acts)
1411 } else {
1412 Ok(Flow::Continue)
1413 }
1414 }
1415
1416 fn fcn_apply(
1418 &mut self,
1419 fcn: ExprId,
1420 arg: ExprId,
1421 e: ExprId,
1422 acts: &Acts,
1423 env: &Env,
1424 ) -> Result<Flow> {
1425 let core = self.core;
1426 let st = if self.init {
1427 self.st()
1428 } else {
1429 self.st().keep_lazy()
1430 };
1431 let f = core.eval(&mut env.clone(), &st, fcn)?;
1432 let fv = match f {
1433 Ev::F(lf) => {
1434 if let Some(v) = lf.materialized.get(core.host.cache_domain()) {
1435 v
1436 } else {
1437 let a = self.eval_v(env, arg)?;
1439 let env1 = core.fcn_context(&lf, &a, e)?;
1440 return self.step(lf.body, acts, &env1);
1441 }
1442 }
1443 Ev::V(v) => v,
1444 };
1445 let Value::Fcn(fv) = fv else {
1446 return Err(EvalError::general(format!(
1447 "In computing {}, a non-function ({}) was applied as a function.\n{}",
1448 self.what(),
1449 crate::core::kind_string(&fv),
1450 core.loc(e)
1451 )));
1452 };
1453 let a = self.eval_v(env, arg)?;
1454 match core.apply_fcn(&fv, &a)? {
1455 Value::Bool(true) => self.cont(acts),
1456 Value::Bool(false) => Ok(Flow::Continue),
1457 _ => Err(EvalError::coded(
1458 Ec::ExpectedExpressionInComputing2,
1459 format!(
1460 "In computing {}, TLC expected a boolean expression,\nbut didn't find one.\n{}",
1461 self.what(),
1462 core.loc(e)
1463 ),
1464 )),
1465 }
1466 }
1467
1468 fn user_op(&mut self, e: ExprId, acts: &Acts, env: &Env) -> Result<Flow> {
1472 let core = self.core;
1473 let st = self.st();
1474 match core.op_target(env, &st, e)? {
1475 OpTarget::Body(env1, body) => self.step(body, acts, &env1),
1476 OpTarget::Thunk(t) => {
1477 if let Some(v) = t.cached(&self.st_cache(), core.host.cache_domain()) {
1478 return self.user_bool(&v, acts, e);
1479 }
1480 self.step(t.expr, acts, &t.env)
1481 }
1482 OpTarget::Value(v) => self.user_bool(&v, acts, e),
1483 }
1484 }
1485
1486 fn user_bool(&mut self, v: &Ev, acts: &Acts, e: ExprId) -> Result<Flow> {
1487 self.after_bool(v, acts, e)
1488 }
1489}
1490
1491pub(crate) enum Target {
1497 Body(Env, ExprId),
1499 Value,
1501}
1502
1503pub(crate) enum OpTarget {
1505 Body(Env, ExprId),
1507 Thunk(Arc<Thunk>),
1509 Value(Ev),
1511}
1512
1513impl Core {
1514 pub(crate) fn op_target(self: &Arc<Self>, env: &Env, st: &St, e: ExprId) -> Result<OpTarget> {
1519 let node = self.ir.node(e);
1520 let mut env = env.clone();
1521 match &node.expr {
1522 Expr::Def(d) => self.def_target(&mut env, st, *d, &[], e),
1523 Expr::Apply { callee, args } => match callee {
1524 OpRef::Def(d) => self.def_target(&mut env, st, *d, args, e),
1525 OpRef::Std(op) => Ok(OpTarget::Value(self.eval_std(&mut env, st, *op, args, e)?)),
1526 _ => {
1527 let op = self.op_value(&env, callee)?;
1528 self.opval_target(&mut env, st, &op, args, e)
1529 }
1530 },
1531 Expr::Local(lr) => match self.slot(&env, *lr)?.clone() {
1532 Sv::Thunk(t) => Ok(OpTarget::Thunk(t)),
1533 Sv::Op(op) => self.opval_target(&mut env, st, &op, &[], e),
1534 Sv::Unset => Err(EvalError::bug("read of an unbound slot")),
1535 sv => Ok(OpTarget::Value(self.force(&mut env, &sv, st, e)?)),
1536 },
1537 Expr::Const(c) => match self.consts.get(c.index()).and_then(Option::as_ref) {
1538 Some(ConstBinding::Def(d)) => self.def_target(&mut env, st, *d, &[], e),
1539 _ => Ok(OpTarget::Value(self.eval(&mut env, st, e)?)),
1540 },
1541 Expr::SubstRef {
1542 decl,
1543 primed: false,
1544 } => match env.dynamic.lookup(*decl).cloned() {
1545 Some(Sv::Thunk(t)) => Ok(OpTarget::Thunk(t)),
1546 Some(Sv::Op(op)) => self.opval_target(&mut env, st, &op, &[], e),
1547 Some(_) => Ok(OpTarget::Value(self.eval(&mut env, st, e)?)),
1548 None => {
1549 let bound = self
1550 .ir
1551 .decl(*decl)
1552 .constant
1553 .and_then(|c| self.consts.get(c.index()).and_then(Option::as_ref));
1554 match bound {
1555 Some(ConstBinding::Def(d)) => self.def_target(&mut env, st, *d, &[], e),
1556 _ => Ok(OpTarget::Value(self.eval(&mut env, st, e)?)),
1557 }
1558 }
1559 },
1560 _ => Err(EvalError::bug("op_target on a non-operator")),
1561 }
1562 }
1563
1564 fn def_target(
1565 self: &Arc<Self>,
1566 env: &mut Env,
1567 st: &St,
1568 d: DefId,
1569 args: &[Arg],
1570 e: ExprId,
1571 ) -> Result<OpTarget> {
1572 let d = self.redirect(d);
1573 if let Some(v) = self.def_values.get(&d) {
1574 return Ok(OpTarget::Value(Ev::V(v.clone())));
1575 }
1576 let def = self.ir.def(d);
1577 if let Some(op) = def.std {
1578 return Ok(OpTarget::Value(self.eval_std(env, st, op, args, e)?));
1579 }
1580 if args.is_empty() && self.cacheable(d) {
1581 if let Some(v) = self.def_cache[d.index()].get() {
1584 return Ok(OpTarget::Value(Ev::V(v.clone())));
1585 }
1586 let mut fresh = Env::new(
1587 d,
1588 def.depth,
1589 def.frame.len(),
1590 None,
1591 crate::env::Dyn::default(),
1592 );
1593 match self.eval(&mut fresh, &St::constant(), def.body) {
1594 Ok(Ev::V(v)) => {
1595 let _ = self.def_cache[d.index()].set(v.clone());
1596 return Ok(OpTarget::Value(Ev::V(v)));
1597 }
1598 Ok(ev) => return Ok(OpTarget::Value(ev)),
1599 Err(err) if err.class() == ErrorClass::Eval => {}
1600 Err(err) => return Err(err),
1601 }
1602 }
1603 let env1 = self.callee_env(env, st, d, None, args)?;
1604 Ok(OpTarget::Body(env1, def.body))
1605 }
1606
1607 fn opval_target(
1608 self: &Arc<Self>,
1609 env: &mut Env,
1610 st: &St,
1611 op: &OpVal,
1612 args: &[Arg],
1613 e: ExprId,
1614 ) -> Result<OpTarget> {
1615 match op {
1616 OpVal::Def {
1617 def,
1618 parent,
1619 dynamic,
1620 } => {
1621 if self.ir.def(*def).std.is_some() {
1622 return Ok(OpTarget::Value(self.apply_op(op, env, st, args, e)?));
1623 }
1624 let mut caller = env.clone();
1627 if let Some(d) = dynamic {
1628 caller.dynamic = d.clone();
1629 }
1630 let env1 = self.callee_env(&mut caller, st, *def, parent.clone(), args)?;
1631 Ok(OpTarget::Body(env1, self.ir.def(*def).body))
1632 }
1633 OpVal::Const(c) => match self.consts.get(c.index()).and_then(Option::as_ref) {
1634 Some(ConstBinding::Def(d)) => self.def_target(env, st, *d, args, e),
1635 _ => Ok(OpTarget::Value(self.apply_op(op, env, st, args, e)?)),
1636 },
1637 OpVal::Builtin(b) => match b {
1638 BuiltinOp::Eq
1639 | BuiltinOp::In
1640 | BuiltinOp::Subseteq
1641 | BuiltinOp::And
1642 | BuiltinOp::Or
1643 | BuiltinOp::Implies
1644 | BuiltinOp::Unchanged
1645 | BuiltinOp::Prime
1646 | BuiltinOp::Enabled
1647 | BuiltinOp::Cdot => Err(EvalError::unsupported(format!(
1648 "the built-in operator {b:?} passed as an operator argument and applied in an action ({})",
1649 self.loc(e)
1650 ))),
1651 _ => Ok(OpTarget::Value(self.apply_op(op, env, st, args, e)?)),
1652 },
1653 OpVal::Std(_) | OpVal::Unbound(_) => {
1654 Ok(OpTarget::Value(self.apply_op(op, env, st, args, e)?))
1655 }
1656 }
1657 }
1658
1659 pub(crate) fn zero_arity_target(self: &Arc<Self>, env: &Env, e: ExprId) -> Result<Target> {
1663 match &self.ir.node(e).expr {
1664 Expr::Def(d) => Ok(self
1665 .def_follow(env, *d)
1666 .map_or(Target::Value, |(env1, body)| Target::Body(env1, body))),
1667 Expr::Local(lr) => match self.slot(env, *lr)? {
1668 Sv::Thunk(t) => Ok(Target::Body(t.env.clone(), t.expr)),
1669 _ => Ok(Target::Value),
1670 },
1671 Expr::Const(c) => match self.consts.get(c.index()).and_then(Option::as_ref) {
1672 Some(ConstBinding::Def(d)) => Ok(self
1673 .def_follow(env, *d)
1674 .map_or(Target::Value, |(env1, body)| Target::Body(env1, body))),
1675 _ => Ok(Target::Value),
1676 },
1677 Expr::SubstRef {
1678 decl,
1679 primed: false,
1680 } => match env.dynamic.lookup(*decl) {
1681 Some(Sv::Thunk(t)) => Ok(Target::Body(t.env.clone(), t.expr)),
1682 _ => Ok(Target::Value),
1683 },
1684 _ => Ok(Target::Value),
1685 }
1686 }
1687
1688 fn def_follow(&self, env: &Env, d: DefId) -> Option<(Env, ExprId)> {
1691 let d = self.redirect(d);
1692 let def = self.ir.def(d);
1693 if self.def_values.contains_key(&d)
1694 || def.std.is_some()
1695 || (self.cacheable(d) && self.def_cache[d.index()].get().is_some())
1696 || !def.params.is_empty()
1697 {
1698 return None;
1699 }
1700 let parent = match def.scope {
1701 DefScope::Local { .. } | DefScope::Inline { .. } => {
1702 Some(env.frame_at_depth(def.depth.saturating_sub(1))?.clone())
1703 }
1704 _ => None,
1705 };
1706 Some((
1707 Env::new(d, def.depth, def.frame.len(), parent, env.dynamic.clone()),
1708 def.body,
1709 ))
1710 }
1711
1712 pub(crate) fn var_of(
1716 self: &Arc<Self>,
1717 env: &Env,
1718 e: ExprId,
1719 cutoff: bool,
1720 ) -> Result<Option<usize>> {
1721 Ok(self
1722 .var_lookup(env, e, VariableLookup::Root(cutoff), false, 0)?
1723 .and_then(|decl| self.ir.decl(decl).var)
1724 .map(dive_ir::VarId::index))
1725 }
1726
1727 pub(crate) fn primed_var(
1729 self: &Arc<Self>,
1730 env: &Env,
1731 e: ExprId,
1732 cutoff: bool,
1733 ) -> Result<Option<usize>> {
1734 Ok(self
1735 .var_lookup(env, e, VariableLookup::Root(cutoff), true, 0)?
1736 .and_then(|decl| self.ir.decl(decl).var)
1737 .map(dive_ir::VarId::index))
1738 }
1739
1740 fn var_lookup(
1741 self: &Arc<Self>,
1742 env: &Env,
1743 e: ExprId,
1744 mode: VariableLookup,
1745 primed: bool,
1746 depth: u32,
1747 ) -> Result<Option<dive_ir::DeclId>> {
1748 if depth > 256 {
1749 return Err(EvalError::resource_limit(format!(
1750 "following definitions to a variable more than 256 levels deep ({})",
1751 self.loc(e)
1752 )));
1753 }
1754 let next = |core: &Arc<Self>, env: &Env, e: ExprId| {
1755 core.var_lookup(env, e, mode, primed, depth + 1)
1756 };
1757 match &self.ir.node(e).expr {
1758 Expr::Subst { bindings, body } => {
1759 let env1 = self.bind_subst(env, &St::default(), bindings, false)?;
1760 next(self, &env1, *body)
1761 }
1762 Expr::Let { defs, body } => {
1763 let env1 = self.bind_let_uncached(env, defs);
1764 next(self, &env1, *body)
1765 }
1766 Expr::Label { body, .. } => next(self, env, *body),
1767 Expr::Var { var, primed: p } => {
1768 Ok((*p == primed).then_some(self.ir.vars()[var.index()]))
1769 }
1770 Expr::Prime(a) if primed => self.var_lookup(env, *a, mode, false, depth + 1),
1771 Expr::SubstRef { decl, primed: p } => {
1772 if *p && !primed {
1773 return Ok(None);
1774 }
1775 let as_primed = primed && !*p;
1777 let d = self.ir.decl(*decl);
1778 let cut = mode.cutoff() && d.variable;
1779 match env.dynamic.lookup_cut(*decl, cut) {
1780 Some(Sv::Thunk(t)) => {
1781 self.var_lookup(&t.env, t.expr, mode, as_primed, depth + 1)
1782 }
1783 Some(_) => Ok(None),
1784 None if d.variable && !as_primed => {
1785 if d.var.is_some() || matches!(mode, VariableLookup::Enabled) {
1786 return Ok(Some(*decl));
1787 }
1788 match self.root_var_named(&d.name) {
1789 Some(v) => Ok(Some(self.ir.vars()[v])),
1790 None => Err(EvalError::unsupported(format!(
1791 "a variable of an instantiated module, hidden by ENABLED, with no root variable of its name ({})",
1792 self.loc(e)
1793 ))),
1794 }
1795 }
1796 None => match d.constant {
1797 Some(c) => match self.consts.get(c.index()).and_then(Option::as_ref) {
1798 Some(ConstBinding::Def(t)) => match self.def_follow(env, *t) {
1799 Some((env1, body)) => {
1800 self.var_lookup(&env1, body, mode, as_primed, depth + 1)
1801 }
1802 None => Ok(None),
1803 },
1804 _ => Ok(None),
1805 },
1806 None => Ok(None),
1807 },
1808 }
1809 }
1810 Expr::Def(d) => match self.def_follow(env, *d) {
1811 Some((env1, body)) => next(self, &env1, body),
1812 None => Ok(None),
1813 },
1814 Expr::Local(lr) => match self.slot(env, *lr)? {
1815 Sv::Thunk(t) => self.var_lookup(&t.env, t.expr, mode, primed, depth + 1),
1816 _ => Ok(None),
1817 },
1818 Expr::Const(c) => match self.consts.get(c.index()).and_then(Option::as_ref) {
1819 Some(ConstBinding::Def(t)) => match self.def_follow(env, *t) {
1820 Some((env1, body)) => next(self, &env1, body),
1821 None => Ok(None),
1822 },
1823 _ => Ok(None),
1824 },
1825 _ => Ok(None),
1826 }
1827 }
1828
1829 pub(crate) fn bind_let_uncached(self: &Arc<Self>, env: &Env, defs: &[DefId]) -> Env {
1833 self.bind_let(env, defs, false)
1834 }
1835
1836 fn bind_let(self: &Arc<Self>, env: &Env, defs: &[DefId], cachable: bool) -> Env {
1837 let mut env1 = env.clone();
1838 for &d in defs {
1839 let def = self.ir.def(d);
1840 if let DefScope::LetValue { slot, .. } = def.scope {
1841 let t = Thunk::new(def.body, env1.clone(), cachable);
1842 env1.bind(slot.index(), Sv::Thunk(t));
1843 }
1844 }
1845 env1
1846 }
1847
1848 pub(crate) fn fcn_context(
1855 self: &Arc<Self>,
1856 f: &Arc<crate::lazy::LazyFcn>,
1857 arg: &Value,
1858 e: ExprId,
1859 ) -> Result<Env> {
1860 let refuse = |what: &str| {
1861 Err(EvalError::unsupported(format!(
1862 "applying a lazily evaluated function (TLC's FcnLambdaValue) as an action, {what} ({})",
1863 self.loc(e)
1864 )))
1865 };
1866 if !f.excepts.is_empty() {
1867 return refuse("with EXCEPTs pending");
1868 }
1869 let mut env = f.body_env();
1870 if f.bounds.len() == 1 {
1871 let b = &f.bounds[0];
1872 if !self.member(arg, &b.domain)? {
1873 return refuse("to an argument outside its domain");
1874 }
1875 if b.tuple {
1876 match arg {
1877 Value::Fcn(t) if t.as_tuple().is_some_and(|t| t.len() == b.slots.len()) => {
1878 self.bind_one(&mut env, &b.slots, true, arg, e)?;
1879 }
1880 _ => return refuse("to an argument that does not match its tuple parameter"),
1881 }
1882 } else if let Some(&s) = b.slots.first() {
1883 env.bind(s, Sv::Val(arg.clone()));
1884 }
1885 return Ok(env);
1886 }
1887 let Some(elems) = (match arg {
1888 Value::Fcn(t) => t.as_tuple(),
1889 _ => None,
1890 }) else {
1891 return refuse("to an argument that is not a tuple");
1892 };
1893 let mut k = 0;
1894 for b in &f.bounds {
1895 let n = if b.tuple { 1 } else { b.slots.len() };
1896 for j in 0..n {
1897 let Some(x) = elems.get(k) else {
1898 return refuse("to too few arguments");
1899 };
1900 if !self.member(x, &b.domain)? {
1901 return refuse("to an argument outside its domain");
1902 }
1903 if b.tuple {
1904 match x {
1905 Value::Fcn(t) if t.as_tuple().is_some_and(|t| t.len() == b.slots.len()) => {
1906 self.bind_one(&mut env, &b.slots, true, x, e)?;
1907 }
1908 _ => {
1909 return refuse(
1910 "to an argument that does not match its tuple parameter",
1911 );
1912 }
1913 }
1914 } else {
1915 env.bind(b.slots[j], Sv::Val(x.clone()));
1916 }
1917 k += 1;
1918 }
1919 }
1920 Ok(env)
1921 }
1922
1923 pub(crate) fn ev_string(self: &Arc<Self>, v: &Ev) -> String {
1925 match v {
1926 Ev::V(v) => dive_value::print::to_tlc_string_lenient(v, self.ctx),
1927 Ev::F(f) => match self.materialize(f) {
1928 Ok(v) => dive_value::print::to_tlc_string_lenient(&v, self.ctx),
1929 Err(_) => "a function".to_owned(),
1930 },
1931 }
1932 }
1933
1934 pub(crate) fn unchanged_warning(&self, var: usize, e: ExprId) {
1936 let name = self
1937 .ir
1938 .vars()
1939 .get(var)
1940 .map_or("?", |&d| self.ir.decl(d).name.as_str());
1941 self.unchanged_named_warning(name, e);
1942 }
1943
1944 fn unchanged_named_warning(&self, name: &str, e: ExprId) {
1945 self.warn(
1946 2143,
1947 &format!(
1948 "The variable {name} was changed while it is specified as UNCHANGED at\n{}",
1949 self.loc(e)
1950 ),
1951 );
1952 }
1953}
1954
1955enum Split1 {
1961 Throw(EvalError),
1964 Fatal(EvalError),
1966}
1967
1968impl From<EvalError> for Split1 {
1969 fn from(e: EvalError) -> Self {
1970 if e.class() == ErrorClass::Eval {
1971 Self::Throw(e)
1972 } else {
1973 Self::Fatal(e)
1974 }
1975 }
1976}
1977
1978struct Expander<'a> {
1979 core: &'a Arc<Core>,
1980 split: &'a Split,
1981 out: Vec<Action>,
1982 stack: Vec<(DefId, Vec<(String, Value)>)>,
1985 first_id: usize,
1986}
1987
1988impl Expander<'_> {
1989 fn push(&mut self, expr: ExprId, env: &Env, name: ActionName) {
1990 let params = match name {
1991 ActionName::Def(d) => self
1992 .stack
1993 .iter()
1994 .rev()
1995 .find(|(s, _)| *s == d)
1996 .map(|(_, p)| p.clone())
1997 .unwrap_or_default(),
1998 _ => Vec::new(),
1999 };
2000 let values: Vec<String> = params
2001 .iter()
2002 .map(|(_, v)| dive_value::print::to_tlc_string_lenient(v, self.core.ctx))
2003 .collect();
2004 let id = self.first_id + self.out.len();
2005 self.out.push(Action {
2006 owner: self.core.ir.clone(),
2007 names: self.core.names.clone(),
2008 context: Arc::downgrade(self.core),
2009 expr,
2010 env: env.clone(),
2011 name,
2012 label: label(&self.core.ir, name, &values, expr),
2013 params,
2014 id,
2015 });
2016 }
2017
2018 fn expand(&mut self, t: &ActionTree, env: &Env) -> std::result::Result<(), Split1> {
2019 let core = self.core;
2020 let st = St {
2021 s0: StateRef::Empty,
2022 s1: StateRef::Empty,
2023 control: control::CLEAR,
2024 };
2025 match t {
2026 ActionTree::Leaf { expr, name } => {
2027 self.push(*expr, env, *name);
2028 Ok(())
2029 }
2030 ActionTree::Throws { expr } => Err(Split1::Throw(EvalError::general(format!(
2031 "TLC cannot split the next-state relation at {}",
2032 core.loc(*expr)
2033 )))),
2034 ActionTree::Disj { children, .. } => {
2035 for c in children {
2036 self.expand(c, env)?;
2037 }
2038 Ok(())
2039 }
2040 ActionTree::Scope { expr, body } => {
2041 let env1 = match &core.ir.node(*expr).expr {
2042 Expr::Let { defs, .. } => core.bind_let_uncached(env, defs),
2043 _ => env.clone(),
2044 };
2045 self.expand(body, &env1)
2046 }
2047 ActionTree::Exists {
2048 expr,
2049 name: n,
2050 body,
2051 } => {
2052 let cnt = self.out.len();
2053 let Expr::Quant { bounds, .. } = &core.ir.node(*expr).expr else {
2054 return Err(Split1::Fatal(EvalError::bug(
2055 "Exists node is not a quantifier",
2056 )));
2057 };
2058 let mut calls = 0usize;
2059 let mut failed: Option<Split1> = None;
2060 let r =
2061 core.for_each_context(&mut env.clone(), &st, bounds, *expr, &mut |_, env1| {
2062 calls += 1;
2063 match self.expand(body, env1) {
2064 Ok(()) => Ok(true),
2065 Err(x) => {
2066 failed = Some(x);
2067 Ok(false)
2068 }
2069 }
2070 });
2071 let outcome = match (r, failed) {
2072 (Err(e), _) => Split1::from(e),
2073 (Ok(()), Some(x)) => x,
2074 (Ok(()), None) => {
2075 if calls == 0 {
2076 self.push(*expr, env, *n);
2078 }
2079 return Ok(());
2080 }
2081 };
2082 match outcome {
2083 Split1::Throw(_) => {
2084 self.out.truncate(cnt);
2085 self.push(*expr, env, *n);
2086 Ok(())
2087 }
2088 fatal @ Split1::Fatal(_) => Err(fatal),
2089 }
2090 }
2091 ActionTree::Inline {
2092 expr,
2093 def,
2094 constant_args,
2095 } => self.inline(*expr, *def, *constant_args, env),
2096 ActionTree::Configured { expr, name: n } => {
2097 let node = &core.ir.node(*expr).expr;
2098 let (c, args): (Option<dive_ir::ConstId>, &[Arg]) = match node {
2099 Expr::Const(c) => (Some(*c), &[]),
2100 Expr::Apply {
2101 callee: OpRef::Const(c),
2102 args,
2103 } => (Some(*c), args),
2104 _ => (None, &[]),
2105 };
2106 let Some(c) = c else {
2107 return Err(Split1::Fatal(EvalError::unsupported(format!(
2108 "an instance substitution used as an action of the next-state relation ({})",
2109 core.loc(*expr)
2110 ))));
2111 };
2112 match core.consts.get(c.index()).and_then(Option::as_ref) {
2113 Some(ConstBinding::Def(d)) => {
2114 let constant = args.iter().all(|a| match a {
2115 Arg::Expr { expr, .. } => {
2116 core.ir.node(*expr).level == dive_ir::Level::Constant
2117 }
2118 Arg::Op { level, .. } => *level == dive_ir::Level::Constant,
2119 });
2120 let _ = n;
2121 self.inline(*expr, *d, constant, env)
2122 }
2123 _ => Err(Split1::Throw(EvalError::general(format!(
2124 "TLC cannot split the next-state relation at {}",
2125 core.loc(*expr)
2126 )))),
2127 }
2128 }
2129 }
2130 }
2131
2132 fn inline(
2135 &mut self,
2136 expr: ExprId,
2137 def: DefId,
2138 constant_args: bool,
2139 env: &Env,
2140 ) -> std::result::Result<(), Split1> {
2141 let core = self.core;
2142 let name = ActionName::Def(def);
2143 if !constant_args {
2144 self.push(expr, env, name);
2145 return Ok(());
2146 }
2147 let Some(body) = self.split.defs.get(&def) else {
2148 return Err(Split1::Fatal(EvalError::bug(
2149 "inlined definition without a tree",
2150 )));
2151 };
2152 let args: Vec<Arg> = match &core.ir.node(expr).expr {
2153 Expr::Apply { args, .. } => args.to_vec(),
2154 _ => Vec::new(),
2155 };
2156 let st = St {
2157 s0: StateRef::Empty,
2158 s1: StateRef::Empty,
2159 control: control::CLEAR,
2160 };
2161 let attempt = (|| -> std::result::Result<(), Split1> {
2162 let d = core.ir.def(def);
2163 let mut vals = Vec::with_capacity(args.len());
2165 for a in &args {
2166 vals.push(match a {
2167 Arg::Expr { expr, .. } => Sv::from(core.eval(&mut env.clone(), &st, *expr)?),
2168 Arg::Op { op, .. } => Sv::op(core.op_value(env, op)?),
2169 });
2170 }
2171 let parent = match d.scope {
2172 DefScope::Local { .. } | DefScope::Inline { .. } => Some(
2173 env.frame_at_depth(d.depth.saturating_sub(1))
2174 .cloned()
2175 .ok_or_else(|| Split1::Fatal(EvalError::bug("no enclosing frame")))?,
2176 ),
2177 DefScope::LetValue { .. } | DefScope::TopLevel => None,
2178 };
2179 let mut env1 = match d.scope {
2180 DefScope::LetValue { .. } => env.clone(),
2182 _ => Env::new(def, d.depth, d.frame.len(), parent, env.dynamic.clone()),
2183 };
2184 let mut params = Vec::new();
2185 for (i, sv) in vals.into_iter().enumerate() {
2186 if let (Sv::Val(v), Some(p)) = (&sv, d.params.get(i)) {
2187 params.push((p.name.clone(), v.clone()));
2188 }
2189 env1.bind(i, sv);
2190 }
2191 self.stack.push((def, params));
2192 let r = self.expand(body, &env1);
2193 self.stack.pop();
2194 r
2195 })();
2196 match attempt {
2197 Ok(()) => Ok(()),
2198 Err(Split1::Throw(_)) => {
2199 self.push(expr, env, name);
2202 Ok(())
2203 }
2204 Err(fatal) => Err(fatal),
2205 }
2206 }
2207}
2208
2209impl Evaluator {
2214 pub fn enabled_scoped(
2235 &self,
2236 scope: &Scope,
2237 action: ExprId,
2238 sub: Option<ExprId>,
2239 state: StateVals,
2240 ) -> Result<bool> {
2241 self.validate_scope(scope)?;
2242 self.admit_scoped_expr(scope, action)?;
2243 if let Some(sub) = sub {
2244 self.admit_scoped_expr(scope, sub)?;
2245 }
2246 if state.len() != self.core.ir.vars().len() || state.iter().any(Option::is_none) {
2247 return Err(EvalError::general(
2248 "ENABLED requires a complete current state",
2249 ));
2250 }
2251 let mut env = scope.env.clone();
2252 env.dynamic.branch();
2253 let acts = sub.and_then(|sub| cons(&None, Kind::Changed, sub, &env));
2254 let en = Enab {
2255 core: self.core.clone(),
2256 s0: StateRef::Vals(state),
2257 };
2258 let successor = crate::NamedState::empty(&self.core);
2259 Ok(en.enabled(action, &acts, &env, successor)?.is_some())
2260 }
2261}
2262
2263impl Core {
2264 pub(crate) fn eval_enabled_native(
2267 self: &Arc<Self>,
2268 env: &mut Env,
2269 st: &St,
2270 a: ExprId,
2271 _e: ExprId,
2272 ) -> Result<Ev> {
2273 let mut env1 = env.clone();
2274 env1.dynamic.branch();
2275 let s1 = crate::NamedState::empty(self);
2276 let en = Enab {
2277 core: self.clone(),
2278 s0: st.s0.clone(),
2279 };
2280 let found = en.enabled(a, &None, &env1, s1)?;
2281 Ok(Ev::V(Value::Bool(found.is_some())))
2282 }
2283}
2284
2285#[derive(Clone, Copy)]
2286enum VariableLookup {
2287 Root(bool),
2288 Enabled,
2289}
2290
2291impl VariableLookup {
2292 fn cutoff(self) -> bool {
2293 match self {
2294 Self::Root(cutoff) => cutoff,
2295 Self::Enabled => true,
2296 }
2297 }
2298}
2299
2300type EnabledState = Arc<crate::NamedState>;
2301
2302struct Enab {
2303 core: Arc<Core>,
2304 s0: StateRef,
2305}
2306
2307impl Enab {
2308 fn st(&self, s1: &EnabledState) -> St {
2309 St {
2310 s0: self.s0.clone(),
2311 s1: StateRef::Named(s1.clone()),
2312 control: control::ENABLED,
2313 }
2314 }
2315
2316 fn eval(&self, env: &Env, s1: &EnabledState, e: ExprId) -> Result<Ev> {
2317 self.core.eval(&mut env.clone(), &self.st(s1), e)
2318 }
2319
2320 fn with(&self, s1: &EnabledState, var: dive_ir::DeclId, v: Value) -> EnabledState {
2321 s1.with(&self.core.ir.decl(var).name, v)
2322 }
2323
2324 fn loc(&self, e: ExprId) -> String {
2325 self.core.loc(e)
2326 }
2327
2328 fn cont(&self, acts: &Acts, s1: EnabledState) -> Result<Option<EnabledState>> {
2330 let Some(item) = acts else {
2331 return Ok(Some(s1));
2332 };
2333 match item.kind {
2334 Kind::Pred => self.enabled(item.expr, &item.next, &item.env, s1),
2335 Kind::Unchanged => self.unchanged(item.expr, &item.next, &item.env, s1),
2336 Kind::Changed => {
2337 let st0 = St {
2338 s0: self.s0.clone(),
2339 s1: StateRef::Empty,
2340 control: control::ENABLED,
2341 };
2342 let st1 = St {
2343 s0: StateRef::Named(s1.clone()),
2344 s1: StateRef::Null,
2345 control: control::PRIMED,
2346 };
2347 let v1 = self.core.eval_v(&mut item.env.clone(), &st0, item.expr)?;
2348 let v2 = self.core.eval_v(&mut item.env.clone(), &st1, item.expr)?;
2349 if self.core.equals(&v1, &v2)? {
2350 return Ok(None);
2351 }
2352 self.cont(&item.next, s1)
2353 }
2354 }
2355 }
2356
2357 fn after_bool(
2358 &self,
2359 v: &Ev,
2360 acts: &Acts,
2361 s1: EnabledState,
2362 e: ExprId,
2363 ) -> Result<Option<EnabledState>> {
2364 match v {
2365 Ev::V(Value::Bool(true)) => self.cont(acts, s1),
2366 Ev::V(Value::Bool(false)) => Ok(None),
2367 other => Err(EvalError::coded(
2368 Ec::ExpectedExpressionInComputing,
2369 format!(
2370 "In computing ENABLED, TLC expected a boolean expression,\nbut instead found {}.\n{}",
2371 self.core.ev_string(other),
2372 self.loc(e)
2373 ),
2374 )),
2375 }
2376 }
2377
2378 fn wrong(&self, what: &str, e: ExprId) -> EvalError {
2379 EvalError::coded(
2380 Ec::EnabledWrongFormula,
2381 format!(
2382 "In computing ENABLED, TLC encountered a temporal formula ({what}).\n{}",
2383 self.loc(e)
2384 ),
2385 )
2386 }
2387
2388 fn enabled(
2390 &self,
2391 e: ExprId,
2392 acts: &Acts,
2393 env: &Env,
2394 s1: EnabledState,
2395 ) -> Result<Option<EnabledState>> {
2396 let core = &self.core;
2397 let _g = core.enter(e)?;
2398 match &core.ir.node(e).expr {
2399 Expr::Let { defs, body } => {
2400 let env1 = core.bind_let(env, defs, true);
2401 self.enabled(*body, acts, &env1, s1)
2402 }
2403 Expr::Subst { bindings, body } => {
2404 let env1 = core.bind_subst(env, &self.st(&s1), bindings, false)?;
2405 self.enabled(*body, acts, &env1, s1)
2406 }
2407 Expr::Label { body, .. } | Expr::Selected(body) => self.enabled(*body, acts, env, s1),
2408 Expr::Def(_)
2409 | Expr::Apply { .. }
2410 | Expr::Local(_)
2411 | Expr::Const(_)
2412 | Expr::SubstRef { primed: false, .. } => {
2413 match core.op_target(env, &self.st(&s1), e)? {
2414 OpTarget::Body(env1, body) => self.enabled(body, acts, &env1, s1),
2415 OpTarget::Thunk(t) => self.enabled(t.expr, acts, &t.env, s1),
2416 OpTarget::Value(v) => self.after_bool(&v, acts, s1, e),
2417 }
2418 }
2419 Expr::StepAngle { action, sub } => {
2420 let acts1 = cons(acts, Kind::Changed, *sub, env);
2421 self.enabled(*action, &acts1, env, s1)
2422 }
2423 Expr::Quant {
2424 kind: QuantKind::Exists,
2425 bounds,
2426 body,
2427 } if bounds.iter().all(|b| b.domain.is_some()) => {
2428 let st = self.st(&s1);
2429 let mut found = None;
2430 let mut err = None;
2431 core.for_each_context(&mut env.clone(), &st, bounds, e, &mut |_, env1| match self
2432 .enabled(*body, acts, env1, s1.clone())
2433 {
2434 Ok(Some(s)) => {
2435 found = Some(s);
2436 Ok(false)
2437 }
2438 Ok(None) => Ok(true),
2439 Err(x) => {
2440 err = Some(x);
2441 Ok(false)
2442 }
2443 })?;
2444 match err {
2445 Some(x) => Err(x),
2446 None => Ok(found),
2447 }
2448 }
2449 Expr::Quant {
2450 kind: QuantKind::Forall,
2451 bounds,
2452 body,
2453 } if bounds.iter().all(|b| b.domain.is_some()) => {
2454 let st = self.st(&s1);
2455 let mut envs: Vec<Env> = Vec::new();
2456 core.for_each_context(&mut env.clone(), &st, bounds, e, &mut |_, env1| {
2457 envs.push(env1.clone());
2458 Ok(true)
2459 })?;
2460 let Some((first, rest)) = envs.split_first() else {
2461 return self.cont(acts, s1);
2462 };
2463 let mut acts1 = acts.clone();
2464 for c2 in rest {
2465 acts1 = cons(&acts1, Kind::Pred, *body, c2);
2466 }
2467 self.enabled(*body, &acts1, first, s1)
2468 }
2469 Expr::Quant { kind, .. } => Err(EvalError::general(match kind {
2470 QuantKind::Choose => format!(
2471 "In computing ENABLED, TLC encountered unbounded CHOOSE. Make sure that the expression is of form CHOOSE x \\in S: P(x).\n{}",
2472 self.loc(e)
2473 ),
2474 QuantKind::Exists => format!(
2475 "In computing ENABLED, TLC encountered unbounded quantifier. Make sure that the expression is of form \\E x \\in S: P(x).\n{}",
2476 self.loc(e)
2477 ),
2478 QuantKind::Forall => format!(
2479 "In computing ENABLED, TLC encountered unbounded quantifier. Make sure that the expression is of form \\A x \\in S: P(x).\n{}",
2480 self.loc(e)
2481 ),
2482 })),
2483 Expr::Case { arms, other } => {
2484 for arm in arms {
2485 match self.eval(env, &s1, arm.guard)? {
2486 Ev::V(Value::Bool(true)) => return self.enabled(arm.value, acts, env, s1),
2487 Ev::V(Value::Bool(false)) => {}
2488 other => {
2489 return Err(EvalError::general(format!(
2490 "In computing ENABLED, a non-boolean expression({}) was used as a guard condition of a CASE.\n{}",
2491 core.kind_of(&other),
2492 self.loc(arm.value)
2493 )));
2494 }
2495 }
2496 }
2497 match other {
2498 Some(o) => self.enabled(*o, acts, env, s1),
2499 None => Err(EvalError::general(format!(
2500 "In computing ENABLED, TLC encountered a CASE with no conditions true.\n{}",
2501 self.loc(e)
2502 ))),
2503 }
2504 }
2505 Expr::Junction { kind, items, .. } => match kind {
2506 JunctionKind::And => {
2507 let mut acts1 = acts.clone();
2508 for &i in items.iter().skip(1).rev() {
2509 acts1 = cons(&acts1, Kind::Pred, i, env);
2510 }
2511 match items.first() {
2512 Some(&f) => self.enabled(f, &acts1, env, s1),
2513 None => self.cont(acts, s1),
2514 }
2515 }
2516 JunctionKind::Or => {
2517 for &i in items {
2518 if let Some(s) = self.enabled(i, acts, env, s1.clone())? {
2519 return Ok(Some(s));
2520 }
2521 }
2522 Ok(None)
2523 }
2524 },
2525 Expr::FcnApply { fcn, arg } => {
2526 let st = St {
2527 control: control::ENABLED | control::KEEP_LAZY,
2528 ..self.st(&s1)
2529 };
2530 let f = core.eval(&mut env.clone(), &st, *fcn)?;
2531 let fv = match f {
2532 Ev::F(lf) => {
2533 if let Some(v) = lf.materialized.get(core.host.cache_domain()) {
2534 v
2535 } else {
2536 let a = core.force_fcn(self.eval(env, &s1, *arg)?)?;
2537 let env1 = core.fcn_context(&lf, &a, e)?;
2538 return self.enabled(lf.body, acts, &env1, s1);
2539 }
2540 }
2541 Ev::V(v) => v,
2542 };
2543 let Value::Fcn(fv) = fv else {
2544 return Err(EvalError::general(format!(
2545 "In computing ENABLED, a non-function ({}) was applied as a function.\n{}",
2546 crate::core::kind_string(&fv),
2547 self.loc(e)
2548 )));
2549 };
2550 let a = core.force_fcn(self.eval(env, &s1, *arg)?)?;
2551 match core.apply_fcn(&fv, &a)? {
2552 Value::Bool(true) => self.cont(acts, s1),
2553 Value::Bool(false) => Ok(None),
2554 _ => Err(EvalError::coded(
2555 Ec::ExpectedExpressionInComputing2,
2556 format!(
2557 "In computing ENABLED, TLC expected a boolean expression,\nbut didn't find one.\n{}",
2558 self.loc(e)
2559 ),
2560 )),
2561 }
2562 }
2563 Expr::If { cond, then, other } => match self.eval(env, &s1, *cond)? {
2564 Ev::V(Value::Bool(b)) => {
2565 self.enabled(if b { *then } else { *other }, acts, env, s1)
2566 }
2567 other => Err(EvalError::general(format!(
2568 "In computing ENABLED, a non-boolean expression({}) was used as the guard condition of an IF.\n{}",
2569 core.kind_of(&other),
2570 self.loc(e)
2571 ))),
2572 },
2573 Expr::StepBox { action, sub } => {
2574 if let Some(s) = self.enabled(*action, acts, env, s1.clone())? {
2575 return Ok(Some(s));
2576 }
2577 self.unchanged(*sub, acts, env, s1)
2578 }
2579 Expr::TemporalQuant { .. } => Err(EvalError::general(format!(
2580 "In computing ENABLED, TLC encountered temporal quantifier.\n{}",
2581 self.loc(e)
2582 ))),
2583 Expr::Sf { .. } => Err(self.wrong("SF", e)),
2584 Expr::Wf { .. } => Err(self.wrong("WF", e)),
2585 Expr::Always(_) => Err(self.wrong("[]", e)),
2586 Expr::Eventually(_) => Err(self.wrong("<>", e)),
2587 Expr::LeadsTo(..) => Err(EvalError::general(format!(
2588 "In computing ENABLED, TLC encountered a temporal formula (a ~> b).\n{}",
2589 self.loc(e)
2590 ))),
2591 Expr::WhilePlus(..) => Err(EvalError::general(format!(
2592 "In computing ENABLED, TLC encountered a temporal formula (a -+-> formula).\n{}",
2593 self.loc(e)
2594 ))),
2595 Expr::Unchanged(a) => self.unchanged(*a, acts, env, s1),
2596 Expr::Implies(a, b) => match self.eval(env, &s1, *a)? {
2597 Ev::V(Value::Bool(true)) => self.enabled(*b, acts, env, s1),
2598 Ev::V(Value::Bool(false)) => self.cont(acts, s1),
2599 other => Err(EvalError::general(format!(
2600 "While computing ENABLED of an expression of the form P => Q, P was {}.\n{}",
2601 core.kind_of(&other),
2602 self.loc(e)
2603 ))),
2604 },
2605 Expr::Cdot(a, b) => self.cdot(*a, *b, acts, env, &s1, e),
2606 Expr::Builtin {
2607 op: op @ (BuiltinOp::Eq | BuiltinOp::In | BuiltinOp::Subseteq),
2608 args,
2609 } if args.len() == 2 => self.assign(*op, args[0], args[1], e, acts, env, s1),
2610 _ => {
2611 let v = self.eval(env, &s1, e)?;
2612 self.after_bool(&v, acts, s1, e)
2613 }
2614 }
2615 }
2616
2617 fn bind_value(
2618 &self,
2619 var: dive_ir::DeclId,
2620 value: Value,
2621 acts: &Acts,
2622 s1: &EnabledState,
2623 ) -> Result<Option<EnabledState>> {
2624 self.core.loop_work()?;
2626 self.cont(acts, self.with(s1, var, value))
2627 }
2628
2629 fn bind_interval(
2630 &self,
2631 var: dive_ir::DeclId,
2632 lo: &dive_value::Int,
2633 hi: &dive_value::Int,
2634 acts: &Acts,
2635 s1: &EnabledState,
2636 ) -> Result<Option<EnabledState>> {
2637 if let (Some(lo), Some(hi)) = (lo.to_i64(), hi.to_i64()) {
2640 for value in lo..=hi {
2641 if let Some(found) = self.bind_value(var, Value::Int(value), acts, s1)? {
2642 return Ok(Some(found));
2643 }
2644 }
2645 } else {
2646 let mut value = lo.clone();
2647 while value <= *hi {
2648 if let Some(found) = self.bind_value(var, Value::int(value.clone()), acts, s1)? {
2649 return Ok(Some(found));
2650 }
2651 if value == *hi {
2652 break;
2653 }
2654 value = value.add(&dive_value::Int::ONE, dive_value::IntMode::Big)?;
2655 }
2656 }
2657 Ok(None)
2658 }
2659
2660 fn assign(
2661 &self,
2662 op: BuiltinOp,
2663 lhs: ExprId,
2664 rhs: ExprId,
2665 e: ExprId,
2666 acts: &Acts,
2667 env: &Env,
2668 s1: EnabledState,
2669 ) -> Result<Option<EnabledState>> {
2670 let core = &self.core;
2671 let Some(var) = core.var_lookup(env, lhs, VariableLookup::Enabled, true, 0)? else {
2672 return match self.eval(env, &s1, e)? {
2673 Ev::V(Value::Bool(true)) => self.cont(acts, s1),
2674 Ev::V(Value::Bool(false)) => Ok(None),
2675 _ => Err(EvalError::bug("=, \\in or \\subseteq not boolean")),
2676 };
2677 };
2678 let lval = s1.get(&core.ir.decl(var).name).cloned();
2679 match op {
2680 BuiltinOp::Eq => {
2681 let rval = core.embed(self.eval(env, &s1, rhs)?)?;
2682 match lval {
2683 None => {
2684 let s2 = s1.with_owned(&core.ir.decl(var).name, rval);
2685 self.cont(acts, s2)
2686 }
2687 Some(l) => {
2688 if core.equals(&l, &rval)? {
2689 self.cont(acts, s1)
2690 } else {
2691 Ok(None)
2692 }
2693 }
2694 }
2695 }
2696 BuiltinOp::In => {
2697 let rval = core.force_fcn(self.eval(env, &s1, rhs)?)?;
2698 match lval {
2699 None => {
2700 let elems = match &rval {
2701 Value::Set(set) if is_enumerable(&rval) => {
2702 if let Some((lo, hi)) = set.as_interval() {
2703 return self.bind_interval(var, lo, hi, acts, &s1);
2704 }
2705 if let Some(elements) = core.in_element_stream(set)? {
2706 for value in elements.with_owner(rval) {
2707 let value = value?;
2708 if let Some(found) =
2709 self.bind_value(var, value, acts, &s1)?
2710 {
2711 return Ok(Some(found));
2712 }
2713 }
2714 return Ok(None);
2715 }
2716 core.in_elements(set)?
2717 }
2718 _ => {
2719 return Err(EvalError::general(format!(
2720 "The right side of \\IN is not enumerable.\n{}",
2721 self.loc(e)
2722 )));
2723 }
2724 };
2725 for x in elems.iter() {
2726 if let Some(s) = self.bind_value(var, x.clone(), acts, &s1)? {
2727 return Ok(Some(s));
2728 }
2729 }
2730 Ok(None)
2731 }
2732 Some(l) => {
2733 if core.member(&l, &rval)? {
2734 self.cont(acts, s1)
2735 } else {
2736 Ok(None)
2737 }
2738 }
2739 }
2740 }
2741 _ => {
2742 let rset = core.force_fcn(self.eval(env, &s1, rhs)?)?;
2743 if !matches!(rset, Value::Set(_)) {
2744 return Err(EvalError::unsupported(format!(
2745 "x' \\subseteq S where S is not a set ({})",
2746 self.loc(e)
2747 )));
2748 }
2749 let rval = Value::subset(rset, core.ctx);
2750 match lval {
2751 None => {
2752 let Value::Set(s) = &rval else {
2753 return Err(EvalError::bug("SUBSET is not a set"));
2754 };
2755 for x in core.explore(s)?.iter() {
2756 let s2 = self.with(&s1, var, x.clone());
2757 if let Some(s) = self.cont(acts, s2)? {
2758 return Ok(Some(s));
2759 }
2760 }
2761 Ok(None)
2762 }
2763 Some(l) => {
2764 if core.member(&l, &rval)? {
2765 self.cont(acts, s1)
2766 } else {
2767 Ok(None)
2768 }
2769 }
2770 }
2771 }
2772 }
2773 }
2774
2775 fn unchanged(
2777 &self,
2778 e: ExprId,
2779 acts: &Acts,
2780 env: &Env,
2781 s1: EnabledState,
2782 ) -> Result<Option<EnabledState>> {
2783 let core = &self.core;
2784 let _g = core.enter(e)?;
2785 if let Some(var) = core.var_lookup(env, e, VariableLookup::Enabled, false, 0)? {
2786 let v0 = core.force_fcn(self.eval(env, &s1, e)?)?;
2787 return match s1.get(&core.ir.decl(var).name).cloned() {
2788 None => {
2789 let s2 = s1.with_owned(&core.ir.decl(var).name, v0);
2790 self.cont(acts, s2)
2791 }
2792 Some(v1) => {
2793 if core.equals(&v1, &v0)? {
2794 self.cont(acts, s1)
2795 } else {
2796 core.unchanged_named_warning(&core.ir.decl(var).name, e);
2797 Ok(None)
2798 }
2799 }
2800 };
2801 }
2802 match &core.ir.node(e).expr {
2803 Expr::Tuple(items) => {
2804 let Some((&first, rest)) = items.split_first() else {
2805 return self.cont(acts, s1);
2806 };
2807 let mut acts1 = acts.clone();
2810 for &i in rest {
2811 acts1 = cons(&acts1, Kind::Unchanged, i, env);
2812 }
2813 self.unchanged(first, &acts1, env, s1)
2814 }
2815 Expr::Def(_)
2816 | Expr::Local(_)
2817 | Expr::Const(_)
2818 | Expr::SubstRef { primed: false, .. } => {
2819 match core.zero_arity_target(env, e)? {
2820 Target::Body(env1, body) => self.unchanged(body, acts, &env1, s1),
2821 Target::Value => self.cont(acts, s1),
2823 }
2824 }
2825 _ => {
2826 let st0 = St {
2827 s0: self.s0.clone(),
2828 s1: StateRef::Empty,
2829 control: control::ENABLED,
2830 };
2831 let st1 = St {
2832 s0: StateRef::Named(s1.clone()),
2833 s1: StateRef::Empty,
2834 control: control::PRIMED,
2835 };
2836 let v0 = core.eval_v(&mut env.clone(), &st0, e)?;
2837 let v1 = core.eval_v(&mut env.clone(), &st1, e)?;
2838 if core.equals(&v0, &v1)? {
2839 self.cont(acts, s1)
2840 } else {
2841 Ok(None)
2842 }
2843 }
2844 }
2845 }
2846}