1use std::collections::HashMap;
31use std::sync::Arc;
32
33use dive_ir::{
34 Arg, Bound, BuiltinOp, DefId, DefScope, Expr, ExprId, Ir, JunctionKind, Level, LocalRef, OpRef,
35 QuantKind, Slot, StdOp,
36};
37use dive_value::Value;
38
39use crate::Error;
40use crate::eval::Machine;
41use crate::handle::Handle;
42use crate::memo::{MAX_KEY, Memo};
43use crate::node::Kind;
44use crate::opts::Opts;
45use crate::plan::{
46 Action, Arith, Bind, Check, Cmp, Code, CompileStats, Conjunct, Fun, G, GNode, LibArg, MemoSite,
47 Node, P, Plan, Quant, SetOp, StdFn, Update,
48};
49use crate::store::Store;
50
51#[path = "compile_gen.rs"]
52mod generator;
53
54#[path = "compile_composition.rs"]
55mod composition;
56
57const MAX_NODES: usize = 4_000_000;
59
60pub const FOLD_FUEL: u64 = 1 << 16;
68
69pub const FOLD_BUDGET: u64 = 1 << 22;
73
74pub const SETTLE_FUEL: u64 = 1 << 22;
81
82pub const SETTLE_BUDGET: u64 = 1 << 24;
85
86#[derive(Clone, Debug)]
89pub struct Role {
90 pub name: String,
92 pub expr: ExprId,
94 pub def: DefId,
96 pub slots: Vec<(Slot, Value)>,
99 pub substs: Vec<RoleSubst>,
102}
103
104#[derive(Clone, Debug)]
106pub enum RoleSubst {
107 Operator {
109 decl: dive_ir::DeclId,
111 def: DefId,
113 },
114 Expr {
117 decl: dive_ir::DeclId,
119 expr: ExprId,
121 def: DefId,
123 slots: Vec<(Slot, Value)>,
125 },
126 Value {
128 decl: dive_ir::DeclId,
130 value: Value,
132 },
133}
134
135#[derive(Clone, Debug)]
137pub enum ConstBinding {
138 Value(Value),
140 Def(DefId),
142}
143
144pub trait StartupEvaluator: std::fmt::Debug {
157 fn evaluate(&self, def: DefId) -> Option<Value>;
161}
162
163pub const STARTUP_TRANSIENT_BYTES: usize = 256 << 20;
167
168#[derive(Clone, Debug)]
170pub struct Handoff<'a> {
171 pub ir: &'a Ir,
173 pub ctx: dive_value::Ctx,
175 pub action_composition: bool,
177 pub constants: Vec<Option<ConstBinding>>,
179 pub redirects: HashMap<DefId, DefId>,
181 pub std_redirects: HashMap<StdOp, DefId>,
183 pub precomputed: HashMap<DefId, Value>,
185 pub overrides: std::collections::HashSet<DefId>,
188 pub deferred: std::collections::BTreeSet<DefId>,
196 pub startup_evaluator: Option<Arc<dyn StartupEvaluator>>,
200 pub assumptions: Vec<DefId>,
206 pub init: Vec<Role>,
208 pub next: Vec<Role>,
210 pub invariants: Vec<Role>,
212 pub constraints: Vec<Role>,
214 pub action_constraints: Vec<Role>,
217 pub implied_inits: Vec<Role>,
220 pub implied_actions: Vec<Role>,
223 pub check_deadlock: bool,
225 pub symmetry: Vec<Vec<(String, String)>>,
228 pub view: Option<Role>,
230}
231
232#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash)]
233enum Mode {
234 Plain,
235 Primed,
236}
237
238type RecKey = (DefId, Mode, bool, Option<usize>, Option<u32>);
240
241#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash)]
244enum Cached {
245 Def(DefId, Mode, Option<u32>),
249 Subst(u32, Mode),
250}
251
252#[derive(Clone, Copy, Debug)]
253enum ArgHow {
254 Alias(P),
255 Thunk(u32, P),
256 ByName,
257}
258
259#[derive(Clone, Debug)]
260enum Sb {
261 Unset,
262 Flat(u32),
263 Arg {
264 expr: ExprId,
265 env: usize,
266 how: ArgHow,
267 },
268 LetVal {
269 def: DefId,
270 env: usize,
271 thunk: Option<(u32, P)>,
272 owner: usize,
273 },
274 RecSelf(DefId, u32, Mode),
276 Enclosing {
280 env: usize,
281 slot: usize,
282 },
283 OpArg {
286 op: OpRef,
287 env: usize,
288 },
289}
290
291#[derive(Debug)]
295struct Lift {
296 floor: usize,
298 parent: Option<usize>,
300 fun: u32,
302 caps: Vec<(u32, usize, u32)>,
304 self_calls: Vec<P>,
306 mode: Mode,
309}
310
311#[derive(Clone, Debug)]
314struct SubstEntry {
315 id: u32,
317 decl: dive_ir::DeclId,
318 value: Result<Arg, P>,
320 env: usize,
322 how: ArgHow,
324 depth: usize,
327}
328
329type Saved = Vec<(usize, usize, Sb)>;
331
332#[derive(Clone, Debug)]
333struct EnvFrame {
334 def: DefId,
335 slots: Vec<Sb>,
336 parent: Option<usize>,
337}
338
339fn push_operands(n: &Node, out: &mut Vec<P>) {
342 match n {
343 Node::Const(_)
344 | Node::Slot(_)
345 | Node::Var(_)
346 | Node::Primed(_)
347 | Node::Enabled { .. }
348 | Node::Composition { .. } => {}
349 Node::Lazy { body, .. }
350 | Node::Scope { body, .. }
351 | Node::Memo { body, .. }
352 | Node::SameVars { eq: body, .. }
353 | Node::Spec(body)
354 | Node::Not(body)
355 | Node::Neg(body)
356 | Node::Powerset(body)
357 | Node::BigUnion(body)
358 | Node::Domain(body)
359 | Node::Select(body, _) => out.push(*body),
360 Node::And(xs)
361 | Node::Or(xs)
362 | Node::SetEnum(xs)
363 | Node::Product(xs)
364 | Node::Tuple(xs)
365 | Node::Std(_, xs)
366 | Node::Lib { args: xs, .. }
367 | Node::Call { args: xs, .. } => out.extend(xs.iter().copied()),
368 Node::Implies(a, b)
369 | Node::Equiv(a, b)
370 | Node::Eq(a, b)
371 | Node::Neq(a, b)
372 | Node::In(a, b)
373 | Node::NotIn(a, b)
374 | Node::Subseteq(a, b)
375 | Node::Arith(_, a, b)
376 | Node::Cmp(_, a, b)
377 | Node::Range(a, b)
378 | Node::SetBin(_, a, b)
379 | Node::FcnSet(a, b)
380 | Node::Apply(a, b)
381 | Node::InLazy {
382 elem: a, set: b, ..
383 }
384 | Node::DomCheck {
385 domain: a, body: b, ..
386 } => out.extend([*a, *b]),
387 Node::If(a, b, c)
388 | Node::Beta {
389 chain: a,
390 fc: b,
391 arg: c,
392 } => out.extend([*a, *b, *c]),
393 Node::Case(arms, other) => {
394 for &(g, v) in arms {
395 out.extend([g, v]);
396 }
397 out.extend(*other);
398 }
399 Node::RecSet(fs) | Node::Record(fs) => out.extend(fs.iter().map(|&(_, x)| x)),
400 Node::Filter { bind, pred, subset } => {
401 out.extend([bind.domain, *pred]);
402 out.extend(*subset);
403 }
404 Node::Map { binds, body }
405 | Node::FcnCons { binds, body }
406 | Node::Quant { binds, body, .. } => {
407 out.extend(binds.iter().map(|b| b.domain));
408 out.push(*body);
409 }
410 Node::Except { base, updates } => {
411 out.push(*base);
412 for u in updates {
413 out.extend(u.path.iter().copied());
414 out.push(u.value);
415 }
416 }
417 Node::LibHo(_, args) => out.extend(args.iter().map(|a| match a {
418 LibArg::Value(p) => *p,
419 LibArg::Op { body, .. } => *body,
420 })),
421 }
422}
423
424#[derive(Clone, Debug, Default)]
425#[allow(
426 clippy::struct_excessive_bools,
427 reason = "independent read, effect and budget eligibility facts"
428)]
429struct Info {
430 vars: u64,
431 primed: u64,
432 free: Vec<u32>,
433 calls: bool,
434 nested_query: bool,
437 heavy: bool,
439 effect: bool,
443 red: Red,
447}
448
449#[derive(Clone, Copy, Debug, Default, PartialEq, Eq)]
454enum Red {
455 Yes,
457 No,
459 #[default]
461 Maybe,
462}
463
464const LAZY_SCAN: usize = 4096;
466
467const fn builtin_value_arg(op: BuiltinOp) -> bool {
475 use BuiltinOp as B;
476 matches!(
477 op,
478 B::Eq
479 | B::Neq
480 | B::In
481 | B::NotIn
482 | B::Subseteq
483 | B::Cup
484 | B::Cap
485 | B::SetMinus
486 | B::PowerSet
487 | B::BigUnion
488 | B::Domain
489 | B::Not
490 | B::And
491 | B::Or
492 | B::Implies
493 | B::Equiv
494 )
495}
496
497const fn builtin_arity(op: BuiltinOp) -> Option<usize> {
499 use BuiltinOp as B;
500 match op {
501 B::PowerSet | B::BigUnion | B::Domain | B::Not => Some(1),
502 B::Eq
503 | B::Neq
504 | B::In
505 | B::NotIn
506 | B::Subseteq
507 | B::Cup
508 | B::Cap
509 | B::SetMinus
510 | B::And
511 | B::Or
512 | B::Implies
513 | B::Equiv => Some(2),
514 _ => None,
515 }
516}
517
518fn union(a: &mut Vec<u32>, b: &[u32]) {
519 if b.is_empty() {
520 return;
521 }
522 a.extend_from_slice(b);
523 a.sort_unstable();
524 a.dedup();
525}
526
527fn minus(a: &mut Vec<u32>, b: &[u32]) {
528 a.retain(|x| !b.contains(x));
529}
530
531fn symmetry(h: &Handoff<'_>, m: &Machine) -> Result<Option<crate::symmetry::Symmetry>, Error> {
534 if h.symmetry.is_empty() {
535 return Ok(None);
536 }
537 let strings = m.heap.store().strings();
538 let mut maps = Vec::with_capacity(h.symmetry.len());
539 for perm in &h.symmetry {
540 let mut pairs = Vec::with_capacity(perm.len());
541 for (a, b) in perm {
542 pairs.push((strings.intern(a)?, strings.intern(b)?));
543 }
544 maps.push(pairs);
545 }
546 let sym = crate::symmetry::Symmetry::new(maps);
547 Ok(Some(if h.ctx.order == dive_value::ValueOrder::Tlc {
550 sym.tlc(h.ir.tlc_var_order().iter().map(|v| v.index()).collect())
551 } else {
552 sym
553 }))
554}
555
556#[derive(Clone, Copy, Debug)]
558pub enum BoundTest {
559 Predicate,
561 Enabled(Option<ExprId>),
563 Nonstuttering(ExprId),
565}
566
567pub fn compile_bound_test(
585 h: &Handoff<'_>,
586 store: Arc<Store>,
587 opts: Opts,
588 test: BoundTest,
589) -> Result<Plan, Error> {
590 if h.implied_actions.len() != 1
591 || !h.init.is_empty()
592 || !h.next.is_empty()
593 || !h.invariants.is_empty()
594 || !h.constraints.is_empty()
595 || !h.action_constraints.is_empty()
596 || !h.implied_inits.is_empty()
597 || h.view.is_some()
598 {
599 return Err(Error::unsupported("one bound optional atom is required"));
600 }
601 let opts = Opts {
602 memo: false,
603 step_memo: false,
604 primed_memo: false,
605 fold: false,
606 ..opts
607 };
608 compile_inner(h, store, opts, Some(test), false)
609}
610
611pub fn compile(h: &Handoff<'_>, store: Arc<Store>, opts: Opts) -> Result<Plan, Error> {
617 compile_inner(h, store, opts, None, false)
618}
619
620pub fn compile_debug(h: &Handoff<'_>, store: Arc<Store>, opts: Opts) -> Result<Plan, Error> {
626 if h.ir
627 .files()
628 .iter()
629 .map(|file| file.source.len())
630 .sum::<usize>()
631 > 16 << 20
632 {
633 return Err(Error::unsupported("compiled debugger source capacity"));
634 }
635 compile_inner(h, store, opts, None, true)
636}
637
638#[allow(
639 clippy::too_many_lines,
640 reason = "ordered role compilation and optional source map finalization"
641)]
642fn compile_inner(
643 h: &Handoff<'_>,
644 store: Arc<Store>,
645 opts: Opts,
646 test: Option<BoundTest>,
647 mapped: bool,
648) -> Result<Plan, Error> {
649 let nvars = h.ir.vars().len();
650 if nvars > 64 {
651 return Err(Error::unsupported("more than 64 state variables (M0 core)"));
652 }
653 let mut c = Compiler {
654 h,
655 effects: crate::plan::Effects::default(),
656 ir: h.ir,
657 code: Code {
658 source_map: mapped.then(|| crate::debug::SourceMap {
659 files: h.ir.files().to_vec(),
660 variables: h
661 .ir
662 .vars()
663 .iter()
664 .map(|id| h.ir.decl(*id).name.clone())
665 .collect(),
666 ..crate::debug::SourceMap::default()
667 }),
668 ..Code::default()
669 },
670 debug_current: None,
671 debug_bytes: 0,
672 info: Vec::new(),
673 envs: Vec::new(),
674 m: Machine::new(store, nvars, opts, Memo::default()),
675 consts: HashMap::new(),
676 pre: HashMap::new(),
677 settled: HashMap::new(),
678 settle_fuel: 0,
679 fallback: HashMap::new(),
680 startup_assumptions: Vec::new(),
681 startup_assumption_false: None,
682 next_slot: 0,
683 reset_stack: Vec::new(),
684 at_stack: Vec::new(),
685 init_mode: false,
686 funs: HashMap::new(),
687 recfuns: HashMap::new(),
688 primed_funs: std::collections::HashSet::new(),
689 next_funs: std::collections::HashSet::new(),
690 open_funs: std::collections::HashSet::new(),
691 reentered_funs: std::collections::HashSet::new(),
692 fun_reads: HashMap::new(),
693 recursive_action_predicate: false,
694 instance_query_calls: false,
695 composition: composition::State::Absent,
696 frame: 0,
697 frames: 0,
698 lazies: Vec::new(),
699 compositions: Vec::new(),
700 def_slots: std::collections::HashSet::new(),
701 lifts: Vec::new(),
702 substs: Vec::new(),
703 fun_caps: HashMap::new(),
704 def_cache: HashMap::new(),
705 step: false,
706 subst_ids: 0,
707 effect_thunks: HashMap::new(),
708 leaf: 0,
709 opts,
710 stats: CompileStats::default(),
711 site_names: Vec::new(),
712 role_name: String::new(),
713 bound_preset: test.map(|_| Vec::new()),
714 };
715 c.startup_values();
716 let init = if h.init.is_empty() {
719 Vec::new()
720 } else {
721 vec![c.init_action(&h.init)?]
722 };
723 let mut next = Vec::new();
724 for r in &h.next {
725 next.push(c.action(r, false)?);
726 }
727 let mut invariants = Vec::new();
728 for r in &h.invariants {
729 invariants.push(c.check(r)?);
730 }
731 let view = h.view.as_ref().map(|r| c.view(r)).transpose()?;
732 let mut constraints = Vec::new();
733 for r in &h.constraints {
734 constraints.push(c.check(r)?);
735 }
736 let mut action_constraints = Vec::new();
737 for r in &h.action_constraints {
738 action_constraints.push(c.step_check(r)?);
739 }
740 let mut implied_inits = Vec::new();
741 for r in &h.implied_inits {
742 implied_inits.push(c.check(r)?);
743 }
744 let mut implied_actions = Vec::new();
745 for r in &h.implied_actions {
746 implied_actions.push(if let Some(test) = test {
747 c.bound_test(r, test)?
748 } else {
749 c.step_check(r)?
750 });
751 }
752 if c.recursive_action_predicate
757 && (c.effects.any
758 || c.code.nodes.iter().any(|node| {
759 matches!(node, Node::Call { fun, .. } if c.code.funs.get(*fun as usize).is_none())
760 }))
761 {
762 return Err(Error::unsupported(
763 "recursive Boolean action predicates in a compiled plan with effects or unproved calls",
764 ));
765 }
766 if c.instance_query_calls
770 && (c.effects.any
771 || c.code.nodes.iter().any(|node| {
772 matches!(node, Node::Call { fun, .. } if c.code.funs.get(*fun as usize).is_none())
773 })
774 || c.code.funs.iter().any(|fun| {
775 c.info
776 .get(fun.body as usize)
777 .is_none_or(|info| info.effect || info.nested_query)
778 }))
779 {
780 return Err(Error::unsupported(
781 "ENABLED in an INSTANCE with effects or recursive/nested calls (M1 core)",
782 ));
783 }
784 c.reset_composition_thunks();
785 c.stats.nodes = c.code.nodes.len();
786 c.stats.gnodes = c.code.gnodes.len();
787 let vars =
788 h.ir.vars()
789 .iter()
790 .map(|&d| h.ir.decl(d).name.clone())
791 .collect();
792 if c.m.heap.poisoned() {
793 return Err(Error::internal("a stale handle was read while compiling"));
794 }
795 let symmetry = symmetry(h, &c.m)?;
796 if let Some(map) = &mut c.code.source_map {
797 for check in invariants
798 .iter()
799 .chain(&implied_inits)
800 .chain(&implied_actions)
801 {
802 map.obligations.extend(
803 check
804 .conjuncts
805 .iter()
806 .map(|part| (part.p, check.name.clone())),
807 );
808 }
809 }
810 let mut plan = Plan {
811 code: c.code,
812 vars,
813 init,
814 next,
815 invariants,
816 constraints,
817 action_constraints,
818 implied_inits,
819 implied_actions,
820 check_deadlock: h.check_deadlock,
821 symmetry,
822 effects: c.effects,
823 view,
824 stats: c.stats,
825 bound_preset: c.bound_preset.unwrap_or_default(),
826 startup_assumptions: c.startup_assumptions,
827 startup_assumption_false: c.startup_assumption_false,
828 };
829 if mapped {
830 let executable = crate::debug::reachable(&plan);
831 if let Some(map) = &mut plan.code.source_map {
832 map.executable = executable;
833 }
834 }
835 Ok(plan)
836}
837
838#[allow(
839 clippy::struct_excessive_bools,
840 reason = "independent compile modes and whole-plan proof obligations"
841)]
842struct Compiler<'a> {
843 h: &'a Handoff<'a>,
844 effects: crate::plan::Effects,
846 ir: &'a Ir,
847 code: Code,
848 debug_current: Option<usize>,
849 debug_bytes: usize,
850 info: Vec<Info>,
851 envs: Vec<EnvFrame>,
852 m: Machine,
853 consts: HashMap<usize, Handle>,
854 pre: HashMap<DefId, Handle>,
855 settled: HashMap<DefId, Option<Handle>>,
859 settle_fuel: u64,
861 fallback: HashMap<DefId, Value>,
864 startup_assumptions: Vec<DefId>,
866 startup_assumption_false: Option<DefId>,
868 next_slot: u32,
869 reset_stack: Vec<Vec<u32>>,
870 at_stack: Vec<u32>,
871 init_mode: bool,
872 funs: HashMap<RecKey, u32>,
874 recfuns: HashMap<RecKey, u32>,
877 primed_funs: std::collections::HashSet<u32>,
881 next_funs: std::collections::HashSet<u32>,
887 open_funs: std::collections::HashSet<u32>,
889 reentered_funs: std::collections::HashSet<u32>,
892 fun_reads: HashMap<u32, u64>,
896 recursive_action_predicate: bool,
898 instance_query_calls: bool,
901 composition: composition::State,
903 frame: u32,
906 frames: u32,
908 lazies: Vec<(u32, P)>,
910 compositions: Vec<(u32, composition::Site)>,
912 def_slots: std::collections::HashSet<u32>,
914 lifts: Vec<Lift>,
916 substs: Vec<SubstEntry>,
918 fun_caps: HashMap<u32, Vec<(u32, usize)>>,
921 def_cache: HashMap<Cached, (u32, P)>,
925 step: bool,
930 subst_ids: u32,
932 effect_thunks: HashMap<u32, u32>,
935 leaf: u32,
937 opts: Opts,
938 stats: CompileStats,
939 site_names: Vec<String>,
940 role_name: String,
941 bound_preset: Option<Vec<(u32, Handle)>>,
944}
945
946impl Compiler<'_> {
947 fn debug_context(&mut self, expression: ExprId, env: usize) -> Result<Option<usize>, Error> {
948 let Some(map) = &self.code.source_map else {
949 return Ok(None);
950 };
951 if map.locations.len() >= 65_536 {
952 return Err(Error::unsupported(
953 "compiled debugger instruction context capacity",
954 ));
955 }
956 let frame = self
957 .envs
958 .get(env)
959 .ok_or_else(|| Error::internal("debugger compile environment"))?;
960 let definition = self.ir.def(frame.def);
961 let context_bytes = self
962 .substs
963 .iter()
964 .try_fold(definition.name.len() + 128, |bytes, entry| {
965 bytes.checked_add(self.ir.decl(entry.decl).name.len() + 96)
966 })
967 .ok_or_else(|| Error::unsupported("compiled debugger substitution capacity"))?;
968 let bytes = definition
969 .frame
970 .iter()
971 .try_fold(context_bytes, |bytes, slot| {
972 bytes.checked_add(slot.name.len() + 64)
973 })
974 .and_then(|bytes| self.debug_bytes.checked_add(bytes))
975 .filter(|bytes| *bytes <= 8 << 20)
976 .ok_or_else(|| Error::unsupported("compiled debugger source/local byte capacity"))?;
977 self.debug_bytes = bytes;
978 let locals = definition
979 .frame
980 .iter()
981 .zip(&frame.slots)
982 .map(|(name, slot)| {
983 let binding = match slot {
984 Sb::Flat(slot)
985 | Sb::Arg {
986 how: ArgHow::Thunk(slot, _),
987 ..
988 }
989 | Sb::LetVal {
990 thunk: Some((slot, _)),
991 ..
992 } => crate::debug::Binding::Slot(*slot),
993 Sb::Arg {
994 how: ArgHow::Alias(node),
995 ..
996 } => crate::debug::Binding::Alias(*node),
997 _ => crate::debug::Binding::Unavailable,
998 };
999 crate::debug::Local {
1000 name: name.name.clone(),
1001 binding,
1002 }
1003 })
1004 .collect();
1005 let location = crate::debug::Location {
1006 origin: self.ir.node(expression).origin,
1007 definition: definition.name.clone(),
1008 definition_id: frame.def.index(),
1009 environment_id: env,
1010 locals,
1011 caller: self.debug_current,
1012 substitutions: self
1013 .substs
1014 .iter()
1015 .map(|entry| crate::debug::Substitution {
1016 declaration: self.ir.decl(entry.decl).name.clone(),
1017 actual: match &entry.value {
1018 Ok(Arg::Expr { expr, .. }) => Some(self.ir.node(*expr).origin),
1019 _ => None,
1020 },
1021 identity: entry.id,
1022 })
1023 .collect(),
1024 };
1025 let Some(map) = &mut self.code.source_map else {
1026 return Ok(None);
1027 };
1028 let index = map.locations.len();
1029 map.locations.push(location);
1030 Ok(Some(index))
1031 }
1032
1033 fn new_frame(&mut self) -> u32 {
1035 self.frames += 1;
1036 std::mem::replace(&mut self.frame, self.frames)
1037 }
1038
1039 fn alloc(&mut self) -> u32 {
1040 let s = self.next_slot;
1041 self.next_slot += 1;
1042 s
1043 }
1044
1045 fn redirect(&self, d: DefId) -> DefId {
1046 let mut d = d;
1047 for _ in 0..64 {
1048 match self.h.redirects.get(&d) {
1049 Some(&t) if t != d => d = t,
1050 _ => break,
1051 }
1052 }
1053 d
1054 }
1055
1056 fn convert(&mut self, v: &Value) -> Result<Handle, Error> {
1057 crate::convert::from_value(&mut self.m.heap, v, self.h.ctx)
1058 }
1059
1060 fn has_startup_value(&self, d: DefId) -> bool {
1063 self.h.precomputed.contains_key(&d)
1064 || self.pre.contains_key(&d)
1065 || self.fallback.contains_key(&d)
1066 }
1067
1068 fn precomputed(&mut self, d: DefId) -> Result<Option<Handle>, Error> {
1069 if let Some(&h) = self.pre.get(&d) {
1070 return Ok(Some(h));
1071 }
1072 let v = match self.h.precomputed.get(&d) {
1073 Some(v) => v.clone(),
1074 None => match self.fallback.get(&d) {
1075 Some(v) => v.clone(),
1076 None => return Ok(None),
1077 },
1078 };
1079 let h = match self.convert(&v) {
1083 Ok(h) => h,
1084 Err(e)
1085 if e.kind() == crate::ErrorKind::Unsupported && !self.h.overrides.contains(&d) =>
1086 {
1087 return Ok(None);
1088 }
1089 Err(e) => return Err(e),
1090 };
1091 self.pre.insert(d, h);
1092 Ok(Some(h))
1093 }
1094
1095 fn new_env(&mut self, def: DefId, parent: Option<usize>) -> usize {
1096 let n = self.ir.def(def).frame.len();
1097 self.envs.push(EnvFrame {
1098 def,
1099 slots: vec![Sb::Unset; n],
1100 parent,
1101 });
1102 self.envs.len() - 1
1103 }
1104
1105 fn find_env(&self, env: usize, def: DefId) -> Option<usize> {
1108 let mut e = Some(env);
1109 while let Some(i) = e {
1110 if self.envs[i].def == def {
1111 return Some(i);
1112 }
1113 e = self.envs[i].parent;
1114 }
1115 None
1116 }
1117
1118 fn lexical_parent(&self, d: DefId, env: usize) -> Result<Option<usize>, Error> {
1119 match self.ir.def(d).scope {
1120 DefScope::TopLevel => Ok(None),
1121 DefScope::Local { parent } | DefScope::Inline { parent } => self
1122 .find_env(env, parent)
1123 .map(Some)
1124 .ok_or_else(|| Error::unsupported("a LET operator used outside its LET (M0 core)")),
1125 DefScope::LetValue { .. } => Err(Error::internal("a LET value used as an operator")),
1126 }
1127 }
1128
1129 #[allow(
1134 clippy::too_many_lines,
1135 clippy::many_single_char_names,
1136 reason = "one arm per node kind"
1137 )]
1138 fn info_of(&self, n: &Node) -> Info {
1139 let mut i = Info::default();
1140 let mut add = |p: P, i: &mut Info| {
1141 if let Some(c) = self.info.get(p as usize) {
1142 i.vars |= c.vars;
1143 i.primed |= c.primed;
1144 i.calls |= c.calls;
1145 i.nested_query |= c.nested_query;
1146 i.heavy |= c.heavy;
1147 i.effect |= c.effect;
1148 union(&mut i.free, &c.free);
1149 }
1150 };
1151 let binders =
1152 |binds: &[Bind], body: &[P], i: &mut Info, add: &mut dyn FnMut(P, &mut Info)| {
1153 let mut inner = Info::default();
1154 for &b in body {
1155 add(b, &mut inner);
1156 }
1157 let bound: Vec<u32> = binds.iter().flat_map(|b| b.slots.iter().copied()).collect();
1158 minus(&mut inner.free, &bound);
1159 i.vars |= inner.vars;
1160 i.primed |= inner.primed;
1161 i.calls |= inner.calls;
1162 i.nested_query |= inner.nested_query;
1163 i.heavy |= inner.heavy;
1164 i.effect |= inner.effect;
1165 union(&mut i.free, &inner.free);
1166 for b in binds {
1167 add(b.domain, i);
1168 }
1169 };
1170 match n {
1171 Node::Const(_) => {}
1172 Node::Slot(s) => i.free.push(*s),
1173 Node::Lazy { body, .. }
1174 | Node::Scope { body, .. }
1175 | Node::Memo { body, .. }
1176 | Node::SameVars { eq: body, .. }
1177 | Node::Spec(body) => {
1178 add(*body, &mut i);
1179 }
1180 Node::InLazy { elem, set, .. } => {
1181 add(*elem, &mut i);
1182 add(*set, &mut i);
1183 }
1184 Node::Beta { chain, arg, .. } => {
1185 add(*chain, &mut i);
1186 add(*arg, &mut i);
1187 }
1188 Node::DomCheck { slot, domain, body } => {
1189 add(*domain, &mut i);
1190 add(*body, &mut i);
1191 minus(&mut i.free, &[*slot]);
1192 }
1193 Node::Var(v) => i.vars |= 1u64 << v,
1194 Node::Primed(v) => i.primed |= 1u64 << v,
1195 Node::Not(a)
1196 | Node::Neg(a)
1197 | Node::Powerset(a)
1198 | Node::BigUnion(a)
1199 | Node::Domain(a)
1200 | Node::Select(a, _) => {
1201 add(*a, &mut i);
1202 }
1203 Node::And(xs)
1204 | Node::Or(xs)
1205 | Node::SetEnum(xs)
1206 | Node::Product(xs)
1207 | Node::Tuple(xs)
1208 | Node::Std(_, xs) => {
1209 for &x in xs {
1210 add(x, &mut i);
1211 }
1212 }
1213 Node::Lib { op, args: xs, .. } => {
1214 for &x in xs {
1215 add(x, &mut i);
1216 }
1217 i.effect |= crate::stdlib::effectful(*op);
1218 }
1219 Node::Implies(a, b)
1220 | Node::Equiv(a, b)
1221 | Node::Eq(a, b)
1222 | Node::Neq(a, b)
1223 | Node::In(a, b)
1224 | Node::NotIn(a, b)
1225 | Node::Subseteq(a, b)
1226 | Node::Arith(_, a, b)
1227 | Node::Cmp(_, a, b)
1228 | Node::Range(a, b)
1229 | Node::SetBin(_, a, b)
1230 | Node::FcnSet(a, b)
1231 | Node::Apply(a, b) => {
1232 add(*a, &mut i);
1233 add(*b, &mut i);
1234 }
1235 Node::If(a, b, c) => {
1236 add(*a, &mut i);
1237 add(*b, &mut i);
1238 add(*c, &mut i);
1239 }
1240 Node::Case(arms, other) => {
1241 for &(g, v) in arms {
1242 add(g, &mut i);
1243 add(v, &mut i);
1244 }
1245 if let Some(o) = other {
1246 add(*o, &mut i);
1247 }
1248 }
1249 Node::RecSet(fs) | Node::Record(fs) => {
1250 for &(_, x) in fs {
1251 add(x, &mut i);
1252 }
1253 }
1254 Node::Filter { bind, pred, .. } => {
1255 binders(std::slice::from_ref(bind), &[*pred], &mut i, &mut add);
1256 }
1257 Node::Map { binds, body }
1258 | Node::FcnCons { binds, body }
1259 | Node::Quant { binds, body, .. } => {
1260 binders(binds, &[*body], &mut i, &mut add);
1261 }
1262 Node::Except { base, updates } => {
1263 add(*base, &mut i);
1264 for u in updates {
1265 for &p in &u.path {
1266 add(p, &mut i);
1267 }
1268 let mut inner = Info::default();
1269 add(u.value, &mut inner);
1270 minus(&mut inner.free, &[u.at]);
1271 i.vars |= inner.vars;
1272 i.primed |= inner.primed;
1273 i.calls |= inner.calls;
1274 i.nested_query |= inner.nested_query;
1275 i.heavy |= inner.heavy;
1276 i.effect |= inner.effect;
1277 union(&mut i.free, &inner.free);
1278 }
1279 }
1280 Node::LibHo(_, args) => {
1281 for a in args {
1282 match a {
1283 LibArg::Value(p) => add(*p, &mut i),
1284 LibArg::Op { params, body } => {
1285 let mut inner = Info::default();
1286 add(*body, &mut inner);
1287 minus(&mut inner.free, params);
1288 i.vars |= inner.vars;
1289 i.primed |= inner.primed;
1290 i.calls |= inner.calls;
1291 i.nested_query |= inner.nested_query;
1292 i.heavy |= inner.heavy;
1293 i.effect |= inner.effect;
1294 union(&mut i.free, &inner.free);
1295 }
1296 }
1297 }
1298 }
1299 Node::Call { fun, args } => {
1300 for &a in args {
1301 add(a, &mut i);
1302 }
1303 i.calls = true;
1304 match self.fun_reads.get(fun) {
1308 Some(&vars) if !self.open_funs.contains(fun) => i.vars |= vars,
1309 _ => i.vars = u64::MAX,
1310 }
1311 if self.next_funs.contains(fun) {
1312 i.primed = u64::MAX;
1313 }
1314 }
1315 Node::Enabled { free, .. } => {
1318 union(&mut i.free, free);
1319 i.calls = true;
1320 i.nested_query = true;
1321 i.vars = u64::MAX;
1322 }
1323 Node::Composition { free, .. } => {
1324 union(&mut i.free, free);
1325 i.calls = true;
1326 i.nested_query = true;
1327 i.vars = u64::MAX;
1328 i.primed = u64::MAX;
1329 }
1330 }
1331 i.red = self.red_of(n);
1332 i
1333 }
1334
1335 fn red(&self, p: P) -> Red {
1336 self.info.get(p as usize).map_or(Red::Maybe, |i| i.red)
1337 }
1338
1339 fn red_of(&self, n: &Node) -> Red {
1341 match n {
1342 Node::Const(h) => {
1343 if !h.is_compound() {
1344 return Red::Yes;
1345 }
1346 match self.m.heap.view(*h).kind {
1347 Kind::Product
1348 | Kind::FcnSet
1349 | Kind::RecSet
1350 | Kind::Subset
1351 | Kind::Nat
1352 | Kind::Int
1353 | Kind::SeqSet => Red::No,
1354 _ => Red::Yes,
1355 }
1356 }
1357 Node::SetEnum(..) | Node::Range(..) | Node::Map { .. } => Red::Yes,
1358 Node::Product(_)
1359 | Node::FcnSet(..)
1360 | Node::RecSet(_)
1361 | Node::Powerset(_)
1362 | Node::Std(StdFn::Seq, _) => Red::No,
1363 Node::Filter { bind, .. } => match self.red(bind.domain) {
1364 Red::Yes => Red::Yes,
1365 Red::No => Red::No,
1366 Red::Maybe => Red::Maybe,
1367 },
1368 Node::SetBin(SetOp::Minus, a, _) => self.red(*a),
1371 Node::SetBin(_, a, b) => match (self.red(*a), self.red(*b)) {
1372 (Red::Yes, Red::Yes) => Red::Yes,
1373 (Red::No, Red::No) => Red::No,
1374 _ => Red::Maybe,
1375 },
1376 Node::Spec(b)
1377 | Node::Lazy { body: b, .. }
1378 | Node::Scope { body: b, .. }
1379 | Node::Memo { body: b, .. } => self.red(*b),
1380 _ => Red::Maybe,
1381 }
1382 }
1383
1384 fn subset_rewrite(&mut self, bind: &Bind, pred: P) -> Result<Option<P>, Error> {
1395 let [outer] = *bind.slots else {
1396 return Ok(None);
1397 };
1398 if bind.tuple {
1399 return Ok(None);
1400 }
1401 let base = match self.code.nodes.get(bind.domain as usize) {
1402 Some(Node::Powerset(t)) => *t,
1403 Some(Node::Const(h)) if h.is_compound() => {
1404 let v = self.m.heap.view(*h);
1405 match (v.kind, v.data) {
1406 (Kind::Subset, &[t]) => self.push(Node::Const(t))?,
1407 _ => return Ok(None),
1408 }
1409 }
1410 _ => return Ok(None),
1411 };
1412 let Some(Node::Quant {
1413 kind: Quant::Forall,
1414 binds,
1415 body,
1416 }) = self.code.nodes.get(pred as usize)
1417 else {
1418 return Ok(None);
1419 };
1420 let [inner] = binds.as_ref() else {
1421 return Ok(None);
1422 };
1423 if inner.tuple
1424 || inner.slots.len() != 1
1425 || !matches!(
1426 self.code.nodes.get(inner.domain as usize),
1427 Some(Node::Slot(s)) if *s == outer
1428 )
1429 {
1430 return Ok(None);
1431 }
1432 let (inner, body) = (inner.clone(), *body);
1433 let Some(info) = self.info.get(body as usize) else {
1434 return Ok(None);
1435 };
1436 if info.free.contains(&outer) || info.primed != 0 || info.calls || info.effect {
1437 return Ok(None);
1438 }
1439 let set = self.push(Node::Filter {
1440 bind: Bind {
1441 slots: inner.slots,
1442 tuple: false,
1443 domain: base,
1444 },
1445 pred: body,
1446 subset: None,
1447 })?;
1448 Ok(Some(set))
1449 }
1450
1451 fn push_lazy(&mut self, n: Node) -> Result<P, Error> {
1456 let eager = match &n {
1457 Node::Filter { bind, .. } => self.red(bind.domain) == Red::Yes,
1458 Node::FcnCons { binds, .. } => binds.iter().all(|b| self.red(b.domain) == Red::Yes),
1459 Node::SetBin(SetOp::Minus, a, _) => self.red(*a) == Red::Yes,
1460 Node::SetBin(_, a, b) => self.red(*a) == Red::Yes && self.red(*b) == Red::Yes,
1461 _ => true,
1462 };
1463 let p = self.push(n)?;
1464 if eager {
1465 Ok(p)
1466 } else {
1467 self.stats.speculative += 1;
1468 self.push(Node::Spec(p))
1469 }
1470 }
1471
1472 fn lazy_set(&self, p: P) -> bool {
1476 let p = self.unspec(p);
1477 match self.code.nodes.get(p as usize) {
1478 Some(Node::Filter { .. } | Node::SetBin(..)) => self.red(p) == Red::No,
1479 Some(Node::Lazy { body, .. } | Node::Scope { body, .. }) => self.lazy_set(*body),
1480 Some(Node::Memo { site, body })
1484 if self
1485 .code
1486 .sites
1487 .get(*site as usize)
1488 .is_some_and(|s| s.candidate) =>
1489 {
1490 self.lazy_set(*body)
1491 }
1492 _ => false,
1493 }
1494 }
1495
1496 fn lambda(&self, mut p: P) -> Option<P> {
1499 loop {
1500 match self.code.nodes.get(p as usize)? {
1501 Node::Spec(b) | Node::Lazy { body: b, .. } | Node::Scope { body: b, .. } => p = *b,
1502 Node::FcnCons { .. } => return Some(p),
1503 _ => return None,
1504 }
1505 }
1506 }
1507
1508 fn apply_value(&mut self, f: P, a: P) -> Result<P, Error> {
1517 let Some(fc) = self.lambda(f) else {
1518 return self.push(Node::Apply(f, a));
1519 };
1520 let Some(Node::FcnCons { binds, .. }) = self.code.nodes.get(fc as usize) else {
1521 return self.push(Node::Apply(f, a));
1522 };
1523 let plain = binds.iter().all(|b| !b.tuple && !b.slots.is_empty());
1527 let non_reducible = binds.iter().any(|b| self.red(b.domain) == Red::No);
1528 let mut thunk = false;
1529 let mut p = f;
1530 while let Some(
1531 n @ (Node::Spec(b) | Node::Lazy { body: b, .. } | Node::Scope { body: b, .. }),
1532 ) = self.code.nodes.get(p as usize)
1533 {
1534 if let Node::Lazy { slot, .. } = n {
1535 thunk |= !self.def_slots.contains(slot);
1536 }
1537 p = *b;
1538 }
1539 if !non_reducible && thunk {
1540 return self.push(Node::Apply(f, a));
1543 }
1544 if plain {
1545 self.stats.beta += 1;
1546 return self.push(Node::Beta {
1547 chain: f,
1548 fc,
1549 arg: a,
1550 });
1551 }
1552 let f = if matches!(self.code.nodes.get(f as usize), Some(Node::Spec(_))) {
1553 f
1554 } else {
1555 self.stats.speculative += 1;
1556 self.push(Node::Spec(f))?
1557 };
1558 self.push(Node::Apply(f, a))
1559 }
1560
1561 fn lambda_domain(&mut self, f: P) -> Result<Option<P>, Error> {
1565 let Some(fc) = self.lambda(f) else {
1566 return Ok(None);
1567 };
1568 let Some(Node::FcnCons { binds, .. }) = self.code.nodes.get(fc as usize) else {
1569 return Ok(None);
1570 };
1571 if !binds.iter().any(|b| self.red(b.domain) == Red::No) {
1572 return Ok(None);
1573 }
1574 if binds.len() == 1 && (binds[0].tuple || binds[0].slots.len() == 1) {
1575 return Ok(Some(binds[0].domain));
1576 }
1577 let mut ds = Vec::new();
1578 for b in binds {
1579 if b.tuple {
1580 ds.push(b.domain);
1581 } else {
1582 ds.extend(std::iter::repeat_n(b.domain, b.slots.len()));
1583 }
1584 }
1585 Ok(Some(self.push(Node::Product(ds.into()))?))
1586 }
1587
1588 fn rec_target(
1592 &mut self,
1593 fcn: ExprId,
1594 env: usize,
1595 mode: Mode,
1596 ) -> Result<Option<(DefId, u32)>, Error> {
1597 let (d, call_env) = match &self.ir.node(fcn).expr {
1598 Expr::Local(r) => {
1599 let fe = self.frame_env(env, r.up)?;
1600 match self.envs[fe].slots.get(r.slot.index()).cloned() {
1601 Some(Sb::RecSelf(d, f, defined_mode)) => {
1602 if self.lifts.last().is_some_and(|l| fe < l.floor) {
1603 return Err(Error::unsupported(
1604 "a recursive function used inside a nested recursive definition (M1 core)",
1605 ));
1606 }
1607 if mode != defined_mode {
1608 return Err(Error::unsupported(
1609 "a recursive function with mixed plain and primed self applications (M1 core)",
1610 ));
1611 }
1612 return Ok(Some((d, f)));
1613 }
1614 Some(Sb::LetVal { def, env, .. }) => (def, env),
1615 _ => return Ok(None),
1616 }
1617 }
1618 Expr::Def(d) => (*d, env),
1619 Expr::Apply {
1620 callee: OpRef::Def(d),
1621 args,
1622 } if args.is_empty() => (*d, env),
1623 _ => return Ok(None),
1624 };
1625 let d = self.redirect(d);
1626 if self.precomputed(d)?.is_some() {
1627 return Ok(None);
1628 }
1629 let def = self.ir.def(d);
1630 if !def.params.is_empty() || def.std.is_some() {
1631 return Ok(None);
1632 }
1633 let Expr::RecFcn { .. } = &self.ir.node(def.body).expr else {
1634 return Ok(None);
1635 };
1636 self.recfun(d, call_env, mode).map(|f| Some((d, f)))
1637 }
1638
1639 fn recfun(&mut self, d: DefId, call_env: usize, mode: Mode) -> Result<u32, Error> {
1642 let owner = match self.ir.def(d).scope {
1643 DefScope::LetValue { parent, .. } => {
1644 Some(self.find_env(call_env, parent).ok_or_else(|| {
1645 Error::unsupported(
1646 "a recursive LET function outside its lexical activation (M1 core)",
1647 )
1648 })?)
1649 }
1650 _ => self.lexical_parent(d, call_env)?,
1651 };
1652 let key = (
1653 d,
1654 mode,
1655 self.init_mode,
1656 owner,
1657 self.substs.last().map(|s| s.id),
1658 );
1659 if let Some(&f) = self.recfuns.get(&key) {
1660 return Ok(self.reenter(f));
1661 }
1662 let def = self.ir.def(d);
1663 let Expr::RecFcn { name, bounds, body } = &self.ir.node(def.body).expr else {
1664 return Err(Error::internal("not a recursive function definition"));
1665 };
1666 let (name, body) = (*name, *body);
1667 let [b] = &bounds[..] else {
1668 return Err(Error::unsupported(
1669 "a recursive function of several bound groups (M1 core)",
1670 ));
1671 };
1672 let ([x], false, Some(domain)) = (&b.vars[..], b.tuple, b.domain) else {
1673 return Err(Error::unsupported(
1674 "a recursive function of several arguments or a tuple pattern (M1 core)",
1675 ));
1676 };
1677 let x = *x;
1678 #[allow(clippy::cast_possible_truncation, reason = "bounded")]
1679 let id = self.code.funs.len() as u32;
1680 self.code.funs.push(Fun {
1681 name: def.name.clone(),
1682 params: 1,
1683 frame: 1,
1684 body: 0,
1685 caps: Box::new([]),
1686 });
1687 self.recfuns.insert(key, id);
1688 self.open_fun(id, mode, def.level);
1689 let saved_slot = self.next_slot;
1690 let saved_resets = std::mem::take(&mut self.reset_stack);
1691 let saved_cache = std::mem::take(&mut self.def_cache);
1692 let saved_at = std::mem::take(&mut self.at_stack);
1693 self.next_slot = 1;
1694 let saved_frame = self.new_frame();
1695 let (env, lifted) = match self.begin_recfun(d, id, call_env, owner, mode) {
1696 Ok(x) => x,
1697 Err(e) => {
1698 self.frame = saved_frame;
1699 self.next_slot = saved_slot;
1700 self.reset_stack = saved_resets;
1701 self.def_cache = saved_cache;
1702 self.at_stack = saved_at;
1703 return Err(e);
1704 }
1705 };
1706 if let Some(s) = self.envs[env].slots.get_mut(name.index()) {
1707 *s = Sb::RecSelf(d, id, mode);
1708 }
1709 if let Some(s) = self.envs[env].slots.get_mut(x.index()) {
1710 *s = Sb::Flat(0);
1711 }
1712 let r = self
1713 .p(domain, env, mode)
1714 .and_then(|dom| Ok((dom, self.p(body, env, mode)?)));
1715 let ended = self.end_fun(id, lifted);
1716 self.frame = saved_frame;
1717 let frame = self.next_slot;
1718 self.next_slot = saved_slot;
1719 self.reset_stack = saved_resets;
1720 self.def_cache = saved_cache;
1721 self.at_stack = saved_at;
1722 self.open_funs.remove(&id);
1723 let (dom, b) = r?;
1724 ended?;
1725 self.note_next_reads(id, &[dom, b])?;
1726 if mode == Mode::Primed && (self.info[dom as usize].effect || self.info[b as usize].effect)
1727 {
1728 return Err(Error::unsupported(
1729 "an effectful recursive function under a prime (M1 core)",
1730 ));
1731 }
1732 let checked = self.push(Node::DomCheck {
1733 slot: 0,
1734 domain: dom,
1735 body: b,
1736 })?;
1737 self.complete_fun(id, checked, frame);
1738 Ok(id)
1739 }
1740
1741 fn unspec(&self, mut p: P) -> P {
1743 while let Some(Node::Spec(b)) = self.code.nodes.get(p as usize) {
1744 p = *b;
1745 }
1746 p
1747 }
1748
1749 fn effect_allowed(&self, n: &Node) -> Result<(), Error> {
1756 let inside = |p: P| self.info.get(p as usize).is_some_and(|i| i.effect);
1757 let lazy = match n {
1758 Node::FcnCons { body, .. } | Node::Map { body, .. } => inside(*body),
1759 Node::Filter { pred, .. } => inside(*pred),
1760 Node::Spec(b) => inside(*b),
1761 Node::LibHo(_, args) => args
1762 .iter()
1763 .any(|a| matches!(a, LibArg::Op { body, .. } if inside(*body))),
1764 _ => false,
1765 };
1766 if lazy {
1767 return Err(Error::unsupported(
1768 "Print, PrintT, RandomElement, TLCSet or TLCGet inside a function constructor, set filter, set map or operator argument, which TLC may evaluate lazily or in its own order (M1 core)",
1769 ));
1770 }
1771 Ok(())
1772 }
1773
1774 fn effect_thunk_use(&mut self, slot: u32, body: P) -> Result<(), Error> {
1781 if !self.info.get(body as usize).is_some_and(|i| i.effect) {
1782 return Ok(());
1783 }
1784 let leaf = self.leaf;
1785 if *self.effect_thunks.entry(slot).or_insert(leaf) != leaf {
1786 return Err(Error::unsupported(
1787 "a LET-bound definition or operator argument with an effect (Print, PrintT, RandomElement) used in more than one conjunct, which TLC evaluates again in each (M1 core)",
1788 ));
1789 }
1790 Ok(())
1791 }
1792
1793 fn builds_lazy_set(&self, n: &Node) -> bool {
1796 match n {
1797 Node::Range(..)
1798 | Node::Domain(_)
1799 | Node::Powerset(_)
1800 | Node::FcnSet(..)
1801 | Node::RecSet(_)
1802 | Node::Product(_) => true,
1803 Node::Const(h) => self.holds_lazy_set(*h, &mut 0),
1804 _ => false,
1805 }
1806 }
1807
1808 fn holds_lazy_set(&self, h: Handle, seen: &mut usize) -> bool {
1811 if !h.is_compound() {
1812 return false;
1813 }
1814 *seen += 1;
1815 if *seen > LAZY_SCAN {
1816 return true;
1817 }
1818 let v = self.m.heap.view(h);
1819 if matches!(
1820 v.kind,
1821 Kind::Interval | Kind::Subset | Kind::FcnSet | Kind::RecSet | Kind::Product
1822 ) {
1823 return true;
1824 }
1825 let data = v.data.to_vec();
1826 data.into_iter().any(|d| self.holds_lazy_set(d, seen))
1827 }
1828
1829 fn push(&mut self, n: Node) -> Result<P, Error> {
1830 if self.code.nodes.len() >= MAX_NODES {
1831 return Err(Error::unsupported(
1832 "a plan larger than the M0 core's inlining limit",
1833 ));
1834 }
1835 let info = self.info_of(&n);
1836 if !self.m.heap.store().lazy_sets() && self.builds_lazy_set(&n) {
1837 self.m.heap.store().note_lazy_sets();
1838 }
1839 if info.effect {
1840 self.effect_allowed(&n)?;
1841 self.effects.any = true;
1842 }
1843 if let Node::Lib { op, .. } = &n {
1844 match op {
1845 StdOp::TlcPrint | StdOp::TlcPrintT => self.effects.prints = true,
1846 StdOp::TlcRandomElement => self.effects.draws = true,
1847 StdOp::TlcTLCSet => self.effects.registers = true,
1848 _ => {}
1849 }
1850 }
1851 let foldable = !matches!(
1852 n,
1853 Node::Const(_) | Node::Slot(_) | Node::Var(_) | Node::Primed(_) | Node::Memo { .. }
1854 );
1855 #[allow(clippy::cast_possible_truncation, reason = "bounded by MAX_NODES")]
1856 let id = self.code.nodes.len() as P;
1857 if let Some(map) = &mut self.code.source_map {
1858 let source = self.debug_current.or_else(|| match &n {
1859 Node::Memo { body, .. } | Node::Scope { body, .. } => {
1860 map.values.get(*body as usize).copied().flatten()
1861 }
1862 _ => None,
1863 });
1864 map.values.push(source);
1865 }
1866 if matches!(n, Node::Lazy { .. }) {
1867 self.lazies.push((self.frame, id));
1868 }
1869 self.code.nodes.push(n);
1870 let closed = info.vars == 0
1871 && info.primed == 0
1872 && info.free.is_empty()
1873 && !info.calls
1874 && !info.heavy
1875 && !info.effect;
1876 self.info.push(info);
1877 if self.opts.fold && foldable && closed {
1878 self.fold(id);
1879 }
1880 Ok(id)
1881 }
1882
1883 fn fold(&mut self, id: P) {
1887 let left = FOLD_BUDGET.saturating_sub(self.stats.fold_fuel);
1888 if left == 0 {
1889 self.stats.fold_skipped += 1;
1890 return;
1891 }
1892 let fuel = FOLD_FUEL.min(left);
1893 let started = std::time::Instant::now();
1894 self.m.set_fuel(fuel);
1895 let old = self.m.enter(self.next_slot + 1);
1896 let r = self.m.eval(&self.code, id);
1897 self.m.leave(old);
1898 let spent = fuel - self.m.fuel;
1899 let exhausted = self.m.fuel == 0;
1900 self.m.set_fuel(u64::MAX);
1901 let r = r.and_then(|h| self.m.heap.intern_const(h));
1902 self.m.heap.reset();
1903 self.stats.fold_fuel += spent;
1904 self.stats.fold_nanos += u64::try_from(started.elapsed().as_nanos()).unwrap_or(u64::MAX);
1905 match r {
1906 Ok(h) if !exhausted && !h.is_empty() => {
1907 self.code.nodes[id as usize] = Node::Const(h);
1908 let red = self.info[id as usize].red;
1910 self.info[id as usize] = Info {
1911 red,
1912 ..Info::default()
1913 };
1914 self.stats.folded += 1;
1915 }
1916 _ if exhausted => {
1917 self.info[id as usize].heavy = true;
1918 self.stats.fold_abandoned += 1;
1919 }
1920 _ => {}
1921 }
1922 }
1923
1924 fn startup_values(&mut self) {
1937 if self.h.deferred.is_empty() && self.h.assumptions.is_empty() {
1938 return;
1939 }
1940 let deferred: Vec<DefId> = self.h.deferred.iter().copied().collect();
1941 for d in deferred {
1942 if self.redirect(d) != d || self.h.precomputed.contains_key(&d) {
1943 continue;
1944 }
1945 let def = self.ir.def(d);
1946 let started = std::time::Instant::now();
1947 let skip = !def.params.is_empty()
1948 || def.std.is_some()
1949 || def.recursive
1950 || def.scope != DefScope::TopLevel
1951 || matches!(self.ir.node(def.body).expr, Expr::RecFcn { .. });
1952 let value = if skip { None } else { self.startup_value(d) };
1953 if let Some(h) = value {
1954 self.pre.insert(d, h);
1955 self.stats.startup_values += 1;
1956 } else if let Some(v) = self
1957 .h
1958 .startup_evaluator
1959 .as_ref()
1960 .and_then(|e| e.evaluate(d))
1961 {
1962 self.fallback.insert(d, v);
1963 self.stats.startup_fallbacks += 1;
1964 }
1965 self.stats.startup_nanos +=
1966 u64::try_from(started.elapsed().as_nanos()).unwrap_or(u64::MAX);
1967 }
1968 for a in self.h.assumptions.clone() {
1975 let def = self.ir.def(a);
1976 if !def.params.is_empty() || def.std.is_some() || def.scope != DefScope::TopLevel {
1977 break;
1978 }
1979 let started = std::time::Instant::now();
1980 let value = self.startup_value(a);
1981 self.stats.startup_nanos +=
1982 u64::try_from(started.elapsed().as_nanos()).unwrap_or(u64::MAX);
1983 if value == Some(Handle::TRUE) {
1984 self.startup_assumptions.push(a);
1985 } else {
1986 if value == Some(Handle::FALSE) {
1987 self.startup_assumption_false = Some(a);
1988 }
1989 break;
1990 }
1991 }
1992 self.m.heap.reset();
1995 self.m.heap.arena.release();
1996 }
1997
1998 fn startup_value(&mut self, d: DefId) -> Option<Handle> {
1999 let body = self.ir.def(d).body;
2000 let saved_slot = self.next_slot;
2001 let saved_resets = std::mem::take(&mut self.reset_stack);
2002 let saved_cache = std::mem::take(&mut self.def_cache);
2003 let saved_at = std::mem::take(&mut self.at_stack);
2004 let saved_lifts = self.lifts.len();
2005 let saved_substs = self.substs.len();
2006 let init = std::mem::replace(&mut self.init_mode, false);
2007 let step = std::mem::replace(&mut self.step, false);
2008 let saved_def_slots = std::mem::take(&mut self.def_slots);
2012 let saved_thunks = std::mem::take(&mut self.effect_thunks);
2013 let saved_funs = std::mem::take(&mut self.funs);
2014 let saved_recfuns = std::mem::take(&mut self.recfuns);
2015 self.next_slot = 0;
2016 let saved_frame = self.new_frame();
2017 let env = self.new_env(d, None);
2018 let compiled = self.p(body, env, Mode::Plain);
2019 self.frame = saved_frame;
2020 let frame = self.next_slot;
2021 self.def_slots = saved_def_slots;
2022 self.effect_thunks = saved_thunks;
2023 self.funs = saved_funs;
2024 self.recfuns = saved_recfuns;
2025 self.next_slot = saved_slot;
2026 self.reset_stack = saved_resets;
2027 self.def_cache = saved_cache;
2028 self.at_stack = saved_at;
2029 self.lifts.truncate(saved_lifts);
2030 self.substs.truncate(saved_substs);
2031 self.init_mode = init;
2032 self.step = step;
2033 let p = compiled.ok()?;
2034 let info = self.info.get(p as usize)?;
2035 if (info.vars != 0 && !info.calls)
2039 || info.primed != 0
2040 || !info.free.is_empty()
2041 || info.effect
2042 {
2043 return None;
2044 }
2045 self.m.set_fuel(u64::MAX);
2046 self.m.calls = Some(crate::eval::CallCache::default());
2047 self.m.set_transient_bound(STARTUP_TRANSIENT_BYTES);
2048 let old = self.m.enter(frame + 1);
2049 let r = self.m.eval(&self.code, p);
2050 self.m.leave(old);
2051 self.m.set_transient_bound(usize::MAX);
2052 if let Some(calls) = self.m.calls.take() {
2053 self.stats.startup_call_hits += calls.hits;
2054 }
2055 let r = r.and_then(|h| self.m.heap.intern_const(h));
2056 self.m.heap.reset();
2057 r.ok().filter(|h| !h.is_empty())
2058 }
2059
2060 fn enabled(
2069 &mut self,
2070 a: Option<ExprId>,
2071 sub: Option<ExprId>,
2072 env: usize,
2073 mode: Mode,
2074 ) -> Result<P, Error> {
2075 let a = a.ok_or_else(|| Error::internal("ENABLED without operand"))?;
2076 if mode == Mode::Primed {
2077 return Err(Error::unsupported("a primed ENABLED (M1 core)"));
2078 }
2079 if self.init_mode && !self.substs.is_empty() {
2080 return Err(Error::unsupported(
2081 "ENABLED in an INSTANCE inside an initial predicate (M1 core)",
2082 ));
2083 }
2084 let instance = !self.substs.is_empty();
2085 let first_slot = self.next_slot;
2086 let init = std::mem::replace(&mut self.init_mode, false);
2089 let step = std::mem::replace(&mut self.step, false);
2090 let cache = std::mem::take(&mut self.def_cache);
2091 let g = (|| {
2092 self.enabled_substs()?;
2093 let action = self.g(a, env)?;
2094 if let Some(sub) = sub {
2095 let same = self.changed_test(sub, env)?;
2096 Ok(self.gpush(GNode::StepAngle { action, same }))
2097 } else {
2098 Ok(action)
2099 }
2100 })();
2101 self.init_mode = init;
2102 self.step = step;
2103 self.def_cache = cache;
2104 let g = g?;
2105 let mut free = Vec::new();
2106 self.instance_query_calls |= self.g_free(g, &mut free, 0, instance)?;
2107 free.retain(|&s| s < first_slot);
2108 self.push(Node::Enabled {
2109 g,
2110 free: free.into(),
2111 })
2112 }
2113
2114 fn enabled_substs(&mut self) -> Result<(), Error> {
2117 if self.substs.is_empty() {
2118 return Ok(());
2119 }
2120 let stateful_config = self.h.constants.iter().flatten().any(|binding| {
2124 matches!(binding, ConstBinding::Def(d) if self.ir.def(self.redirect(*d)).level != Level::Constant)
2125 }) || self.h.redirects.values().any(|&d| self.ir.def(d).level != Level::Constant);
2126 if stateful_config {
2127 return Err(Error::unsupported(
2128 "ENABLED in an INSTANCE with a state-dependent configured operator (M1 core)",
2129 ));
2130 }
2131 for subst in self.substs.clone() {
2132 let decl = self.ir.decl(subst.decl);
2133 if !decl.variable {
2134 continue;
2138 }
2139 let root = self
2140 .ir
2141 .vars()
2142 .iter()
2143 .position(|&root| self.ir.decl(root).name == decl.name);
2144 let Some(root) = root else {
2145 return Err(Error::unsupported(
2146 "ENABLED with a hidden INSTANCE variable (B2, B3, B4; M1 core)",
2147 ));
2148 };
2149 let target = match subst.value {
2150 Ok(Arg::Expr { expr, .. }) => {
2151 self.outside(subst.depth, |c| c.target(expr, subst.env, true))?
2152 }
2153 Ok(Arg::Op { .. }) | Err(_) => None,
2154 };
2155 if target.map(usize::from) != Some(root) {
2156 return Err(Error::unsupported(
2157 "ENABLED with a nonidentity INSTANCE variable substitution (B3; M1 core)",
2158 ));
2159 }
2160 }
2161 Ok(())
2162 }
2163
2164 #[allow(clippy::too_many_lines, reason = "one arm per generator rule")]
2170 fn g_free(&self, g: G, out: &mut Vec<u32>, depth: u32, instance: bool) -> Result<bool, Error> {
2171 if depth > 10_000 {
2172 return Err(Error::unsupported("an action nested too deeply (M1 core)"));
2173 }
2174 let mut unproved = false;
2175 let mut calls = false;
2176 let mut inner = false;
2177 let mut p = |p: P, out: &mut Vec<u32>| {
2178 if let Some(i) = self.info.get(p as usize) {
2179 union(out, &i.free);
2180 unproved |= instance && (i.effect || i.nested_query);
2181 calls |= instance && i.calls;
2182 }
2183 };
2184 let unch = |items: &[crate::plan::Unch],
2185 out: &mut Vec<u32>,
2186 p: &mut dyn FnMut(P, &mut Vec<u32>)| {
2187 for u in items {
2188 if let crate::plan::Unch::Verify(x) = u {
2189 p(*x, out);
2190 }
2191 }
2192 };
2193 let Some(node) = self.code.gnodes.get(g as usize) else {
2194 return Err(Error::internal("generator node out of range"));
2195 };
2196 match node {
2197 GNode::Composition { first, then, .. } => {
2198 inner |= self.g_free(*first, out, depth + 1, instance)?;
2199 inner |= self.g_free(*then, out, depth + 1, instance)?;
2200 }
2201 GNode::Conj(items) => {
2202 for &(g, x) in items {
2203 p(x, out);
2204 inner |= self.g_free(g, out, depth + 1, instance)?;
2205 }
2206 }
2207 GNode::Disj(gs) => {
2208 for &g in gs {
2209 inner |= self.g_free(g, out, depth + 1, instance)?;
2210 }
2211 }
2212 GNode::Exists {
2213 binds,
2214 body,
2215 body_p,
2216 }
2217 | GNode::Forall {
2218 binds,
2219 body,
2220 body_p,
2221 } => {
2222 for b in binds {
2223 p(b.domain, out);
2224 }
2225 p(*body_p, out);
2226 inner |= self.g_free(*body, out, depth + 1, instance)?;
2227 }
2228 GNode::If { cond, then, other } => {
2229 p(*cond, out);
2230 inner |= self.g_free(*then, out, depth + 1, instance)?;
2231 inner |= self.g_free(*other, out, depth + 1, instance)?;
2232 }
2233 GNode::Case { arms, other } => {
2234 for &(c, g) in arms {
2235 p(c, out);
2236 inner |= self.g_free(g, out, depth + 1, instance)?;
2237 }
2238 if let Some(o) = other {
2239 inner |= self.g_free(*o, out, depth + 1, instance)?;
2240 }
2241 }
2242 GNode::Implies { lhs, rhs } => {
2243 p(*lhs, out);
2244 inner |= self.g_free(*rhs, out, depth + 1, instance)?;
2245 }
2246 GNode::Assign { rhs, .. } => p(*rhs, out),
2247 GNode::AssignIn { set, .. } | GNode::AssignInRaw { set, .. } => p(*set, out),
2248 GNode::Unchanged(items) => unch(items, out, &mut p),
2249 GNode::StepBox { action, vars } => {
2250 unch(vars, out, &mut p);
2251 inner |= self.g_free(*action, out, depth + 1, instance)?;
2252 }
2253 GNode::StepAngle { action, same } => {
2254 p(*same, out);
2255 inner |= self.g_free(*action, out, depth + 1, instance)?;
2256 }
2257 GNode::FcnAction { binds, arg, body } => {
2258 for b in binds {
2259 p(b.domain, out);
2260 }
2261 p(*arg, out);
2262 inner |= self.g_free(*body, out, depth + 1, instance)?;
2263 }
2264 GNode::Scope { reset, body } => {
2265 union(out, reset);
2266 inner |= self.g_free(*body, out, depth + 1, instance)?;
2267 }
2268 GNode::Guard(x) => p(*x, out),
2269 }
2270 if unproved {
2271 return Err(Error::unsupported(
2272 "ENABLED in an INSTANCE with effects or recursive/nested calls (M1 core)",
2273 ));
2274 }
2275 Ok(calls || inner)
2276 }
2277
2278 fn konst(&mut self, h: Handle) -> Result<P, Error> {
2279 self.push(Node::Const(h))
2280 }
2281
2282 fn gpush(&mut self, g: GNode) -> G {
2283 #[allow(clippy::cast_possible_truncation, reason = "bounded by MAX_NODES")]
2284 let id = self.code.gnodes.len() as G;
2285 if let Some(map) = &mut self.code.source_map {
2286 map.generators.push(self.debug_current);
2287 }
2288 self.code.gnodes.push(g);
2289 id
2290 }
2291
2292 fn string(&mut self, s: &str) -> Result<Handle, Error> {
2293 self.m.heap.string(s)
2294 }
2295
2296 fn is_trivial(&self, p: P) -> bool {
2297 matches!(
2298 self.code.nodes.get(p as usize),
2299 Some(Node::Const(_) | Node::Slot(_) | Node::Var(_) | Node::Primed(_))
2300 )
2301 }
2302
2303 fn site(&mut self, name: String, p: P) -> Result<Option<P>, Error> {
2305 if !self.opts.memo || self.init_mode {
2306 return Ok(None);
2307 }
2308 let Some(info) = self.info.get(p as usize) else {
2309 return Ok(None);
2310 };
2311 if info.primed != 0
2312 || info.effect
2313 || matches!(self.code.nodes.get(p as usize), Some(Node::Const(_)))
2314 {
2315 return Ok(None);
2316 }
2317 #[allow(clippy::cast_possible_truncation, reason = "at most 64 variables")]
2318 let vars: Vec<u16> = (0..64u16)
2319 .filter(|&v| info.vars & (1u64 << v) != 0)
2320 .take(MAX_KEY + 1)
2321 .collect();
2322 let slots = info.free.clone();
2323 if vars.len() + slots.len() > MAX_KEY || (vars.is_empty() && slots.is_empty()) {
2324 return Ok(None);
2325 }
2326 #[allow(clippy::cast_possible_truncation, reason = "bounded")]
2327 let site = self.code.sites.len() as u32;
2328 self.code.sites.push(MemoSite {
2329 name: name.clone(),
2330 vars: vars.into(),
2331 slots: slots.into(),
2332 primed: Box::new([]),
2333 step: false,
2334 candidate: false,
2335 });
2336 self.site_names.push(name);
2337 Ok(Some(self.push(Node::Memo { site, body: p })?))
2338 }
2339
2340 fn bind_role_lets(&mut self, env: usize, def: DefId) {
2349 let owner = self.reset_stack.len().saturating_sub(1);
2350 for (i, info) in self.ir.def(def).frame.iter().enumerate() {
2351 let dive_ir::SlotKind::LetValue(d) = info.kind else {
2352 continue;
2353 };
2354 if let Some(s @ Sb::Unset) = self.envs[env].slots.get_mut(i) {
2355 *s = Sb::LetVal {
2356 def: d,
2357 env,
2358 thunk: None,
2359 owner,
2360 };
2361 }
2362 }
2363 }
2364
2365 fn role_env(&mut self, r: &Role) -> Result<(usize, Vec<(u32, Handle)>), Error> {
2366 self.next_slot = 0;
2367 self.new_frame();
2368 self.role_env_after(r)
2369 }
2370
2371 fn role_env_after(&mut self, r: &Role) -> Result<(usize, Vec<(u32, Handle)>), Error> {
2374 self.reset_stack.clear();
2375 self.def_cache.clear();
2376 self.at_stack.clear();
2377 self.role_name.clone_from(&r.name);
2378 let def = self.ir.def(r.def);
2379 if def.depth != 0 {
2380 return Err(Error::unsupported(
2381 "a role inside a LET or LAMBDA (M0 core)",
2382 ));
2383 }
2384 let env = self.new_env(r.def, None);
2385 let mut preset = Vec::new();
2386 for (slot, v) in &r.slots {
2387 let flat = self.alloc();
2388 let h = self.convert(v)?;
2389 if let Some(s) = self.envs[env].slots.get_mut(slot.index()) {
2390 *s = Sb::Flat(flat);
2391 }
2392 preset.push((flat, h));
2393 }
2394 self.reset_stack.push(Vec::new());
2395 self.bind_role_lets(env, r.def);
2396 self.substs.clear();
2400 for rs in &r.substs {
2401 let entry = match rs {
2402 RoleSubst::Operator { decl, def } => SubstEntry {
2403 id: self.subst_id(),
2404 decl: *decl,
2405 value: Ok(Arg::Op {
2406 op: OpRef::Def(*def),
2407 level: self.ir.def(*def).level,
2408 }),
2409 env,
2410 how: ArgHow::ByName,
2411 depth: 0,
2412 },
2413 RoleSubst::Value { decl, value } => {
2414 let h = self.convert(value)?;
2415 let p = self.konst(h)?;
2416 SubstEntry {
2417 id: self.subst_id(),
2418 decl: *decl,
2419 value: Err(p),
2420 env,
2421 how: ArgHow::Alias(p),
2422 depth: 0,
2423 }
2424 }
2425 RoleSubst::Expr {
2426 decl,
2427 expr,
2428 def,
2429 slots,
2430 } => {
2431 if self.ir.def(*def).depth != 0 {
2432 return Err(Error::unsupported(
2433 "an INSTANCE substitution inside a LET or LAMBDA (M1 core)",
2434 ));
2435 }
2436 let senv = self.new_env(*def, None);
2437 for (slot, v) in slots {
2438 let flat = self.alloc();
2439 let h = self.convert(v)?;
2440 if let Some(s) = self.envs[senv].slots.get_mut(slot.index()) {
2441 *s = Sb::Flat(flat);
2442 }
2443 preset.push((flat, h));
2444 }
2445 self.bind_role_lets(senv, *def);
2446 SubstEntry {
2447 id: self.subst_id(),
2448 decl: *decl,
2449 value: Ok(Arg::Expr {
2450 expr: *expr,
2451 pass: dive_ir::Pass::Lazy,
2452 }),
2453 env: senv,
2454 how: ArgHow::ByName,
2455 depth: 0,
2456 }
2457 }
2458 };
2459 self.substs.push(entry);
2460 }
2461 Ok((env, preset))
2462 }
2463
2464 fn action(&mut self, r: &Role, init: bool) -> Result<Action, Error> {
2465 self.init_mode = init;
2466 let (env, preset) = self.role_env(r)?;
2467 let g = self.g(r.expr, env)?;
2468 Ok(Action {
2469 name: r.name.clone(),
2470 g,
2471 frame: self.next_slot,
2472 preset,
2473 })
2474 }
2475
2476 fn init_action(&mut self, roles: &[Role]) -> Result<Action, Error> {
2479 let [first, rest @ ..] = roles else {
2480 return Err(Error::internal("no initial predicate"));
2481 };
2482 if rest.is_empty() {
2483 return self.action(first, true);
2484 }
2485 self.init_mode = true;
2486 let mut items = Vec::with_capacity(roles.len());
2487 let mut presets = Vec::new();
2488 for (i, r) in roles.iter().enumerate() {
2489 let (env, preset) = if i == 0 {
2490 self.role_env(r)?
2491 } else {
2492 self.role_env_after(r)?
2493 };
2494 presets.extend(preset);
2495 let g = self.g(r.expr, env)?;
2496 let p = self.p(r.expr, env, Mode::Plain)?;
2497 items.push((g, p));
2498 }
2499 let g = self.gpush(GNode::Conj(items.into()));
2500 Ok(Action {
2501 name: first.name.clone(),
2502 g,
2503 frame: self.next_slot,
2504 preset: presets,
2505 })
2506 }
2507
2508 fn check(&mut self, r: &Role) -> Result<Check, Error> {
2509 self.init_mode = false;
2510 let (env, preset) = self.role_env(r)?;
2511 if let Some(bound) = &mut self.bound_preset {
2512 bound.extend(preset);
2513 } else if !preset.is_empty() {
2514 return Err(Error::unsupported(
2515 "an invariant with bound parameters (M0 core)",
2516 ));
2517 }
2518 let mut parts = Vec::new();
2519 self.conjuncts(r.expr, env, &mut parts)?;
2520 let mut conjuncts = Vec::new();
2521 for (k, (e, env)) in parts.into_iter().enumerate() {
2522 let p = self.p(e, env, Mode::Plain)?;
2523 let info = self.info[p as usize].clone();
2524 let skippable = info.free.is_empty() && info.primed == 0 && !info.effect;
2525 let reads = info.vars;
2526 let (p, site) = match self.site(format!("{}#{k}", r.name), p)? {
2527 Some(m) => {
2528 let site = match self.code.nodes.get(m as usize) {
2529 Some(Node::Memo { site, .. }) => Some(*site),
2530 _ => None,
2531 };
2532 (m, site)
2533 }
2534 None => (p, None),
2535 };
2536 conjuncts.push(Conjunct {
2537 p,
2538 reads,
2539 skippable,
2540 site,
2541 });
2542 }
2543 Ok(Check {
2544 name: r.name.clone(),
2545 conjuncts,
2546 frame: self.next_slot,
2547 })
2548 }
2549
2550 fn bound_test(&mut self, r: &Role, test: BoundTest) -> Result<Check, Error> {
2551 if matches!(test, BoundTest::Predicate) {
2552 return self.step_check(r);
2553 }
2554 self.init_mode = false;
2555 let (env, preset) = self.role_env(r)?;
2556 if let Some(bound) = &mut self.bound_preset {
2557 bound.extend(preset);
2558 } else if !preset.is_empty() {
2559 return Err(Error::internal(
2560 "a bound atom outside bound-test compilation",
2561 ));
2562 }
2563 let p = match test {
2564 BoundTest::Enabled(sub) => self.enabled(Some(r.expr), sub, env, Mode::Plain)?,
2565 BoundTest::Nonstuttering(sub) => {
2566 self.step = true;
2571 let same = self.changed_test(sub, env)?;
2572 let changed = self.push(Node::Not(same))?;
2573 let action = self.p(r.expr, env, Mode::Plain)?;
2574 self.step = false;
2575 self.push(Node::And([changed, action].into()))?
2576 }
2577 BoundTest::Predicate => return Err(Error::internal("ordinary bound test dispatch")),
2578 };
2579 Ok(Check {
2580 name: r.name.clone(),
2581 conjuncts: vec![Conjunct {
2582 p,
2583 reads: u64::MAX,
2584 skippable: false,
2585 site: None,
2586 }],
2587 frame: self.next_slot,
2588 })
2589 }
2590
2591 fn step_check(&mut self, r: &Role) -> Result<Check, Error> {
2595 self.step = true;
2596 let k = self.check(r);
2597 self.step = false;
2598 let mut k = k?;
2599 k.conjuncts.iter_mut().for_each(|j| j.skippable = false);
2600 Ok(k)
2601 }
2602
2603 fn view(&mut self, r: &Role) -> Result<Check, Error> {
2605 self.init_mode = false;
2606 let (env, preset) = self.role_env(r)?;
2607 if !preset.is_empty() {
2608 return Err(Error::unsupported("a VIEW with bound parameters (core)"));
2609 }
2610 let p = self.p(r.expr, env, Mode::Plain)?;
2611 let reads = self.info[p as usize].vars;
2612 Ok(Check {
2613 name: r.name.clone(),
2614 conjuncts: vec![Conjunct {
2615 p,
2616 reads,
2617 skippable: false,
2618 site: None,
2619 }],
2620 frame: self.next_slot,
2621 })
2622 }
2623
2624 fn conjuncts(
2627 &mut self,
2628 e: ExprId,
2629 env: usize,
2630 out: &mut Vec<(ExprId, usize)>,
2631 ) -> Result<(), Error> {
2632 match &self.ir.node(e).expr {
2633 Expr::Junction {
2634 kind: JunctionKind::And,
2635 items,
2636 ..
2637 } => {
2638 for &i in items {
2639 self.conjuncts(i, env, out)?;
2640 }
2641 Ok(())
2642 }
2643 Expr::Label { body, .. } | Expr::Selected(body) => self.conjuncts(*body, env, out),
2644 Expr::Def(d) => {
2645 let d = self.redirect(*d);
2646 let def = self.ir.def(d);
2647 if self.has_startup_value(d)
2648 || def.std.is_some()
2649 || def.recursive
2650 || !def.params.is_empty()
2651 || matches!(def.scope, DefScope::LetValue { .. })
2652 {
2653 out.push((e, env));
2654 return Ok(());
2655 }
2656 let parent = self.lexical_parent(d, env)?;
2657 let inner = self.new_env(d, parent);
2658 self.conjuncts(def.body, inner, out)
2659 }
2660 _ => {
2661 out.push((e, env));
2662 Ok(())
2663 }
2664 }
2665 }
2666
2667 fn p(&mut self, e: ExprId, env: usize, mode: Mode) -> Result<P, Error> {
2672 if self.code.source_map.is_none() {
2673 return self.p_inner(e, env, mode);
2674 }
2675 let previous = self.debug_current;
2676 self.debug_current = self.debug_context(e, env)?;
2677 let result = self.p_inner(e, env, mode);
2678 self.debug_current = previous;
2679 result
2680 }
2681
2682 #[allow(clippy::too_many_lines, reason = "one arm per expression kind")]
2683 fn p_inner(&mut self, e: ExprId, env: usize, mode: Mode) -> Result<P, Error> {
2684 let expr = &self.ir.node(e).expr;
2685 match expr {
2686 Expr::Bool(b) => self.konst(Handle::bool(*b)),
2687 Expr::Num(s) => {
2688 if self.m.heap.int_mode() == crate::int::IntMode::Tlc && s.parse::<i32>().is_err() {
2689 return Err(Error::unsupported(format!(
2691 "the numeral {s}, outside TLC's 32-bit integers (--compat=tlc)"
2692 )));
2693 }
2694 let v = if let Some(h) = s.parse::<i64>().ok().and_then(Handle::int) {
2695 h
2696 } else {
2697 let b = s
2699 .parse::<num_bigint::BigInt>()
2700 .map_err(|_| Error::unsupported(format!("the numeral {s}")))?;
2701 let h = self.m.heap.int_from_big(&b);
2702 let h = self.m.heap.intern_const(h);
2703 self.m.heap.reset();
2704 h?
2705 };
2706 self.konst(v)
2707 }
2708 Expr::Decimal { .. } => Err(Error::unsupported("decimal numbers")),
2709 Expr::Str(s) => {
2710 let h = self.string(s)?;
2711 self.konst(h)
2712 }
2713 Expr::Var { var, primed } => {
2714 #[allow(clippy::cast_possible_truncation, reason = "at most 64 variables")]
2715 let i = var.index() as u16;
2716 if self.init_mode {
2717 if *primed || mode == Mode::Primed {
2718 return Err(Error::unsupported(
2719 "a primed variable in an initial predicate",
2720 ));
2721 }
2722 return self.push(Node::Primed(i));
2723 }
2724 match (*primed, mode) {
2725 (false, Mode::Plain) => self.push(Node::Var(i)),
2726 (true, Mode::Plain) | (false, Mode::Primed) => self.push(Node::Primed(i)),
2727 (true, Mode::Primed) => Err(Error::unsupported("a doubly primed variable")),
2728 }
2729 }
2730 Expr::Const(c) => self.const_expr(*c, env, mode),
2731 Expr::Local(r) => self.local(*r, env, mode),
2732 Expr::Def(d) => self.def_use(*d, env, mode),
2733 Expr::Apply { callee, args } => self.apply(callee, args, env, mode),
2734 Expr::Builtin { op, args } => self.builtin(*op, args, env, mode),
2735 Expr::Junction { kind, items, .. } => {
2736 let mut ps = Vec::with_capacity(items.len());
2737 for &i in items {
2738 ps.push(self.p(i, env, mode)?);
2739 }
2740 match kind {
2741 JunctionKind::And => self.push(Node::And(ps.clone().into())),
2742 JunctionKind::Or => self.push(Node::Or(ps.clone().into())),
2743 }
2744 }
2745 Expr::Not(a) => {
2746 let a = self.p(*a, env, mode)?;
2747 self.push(Node::Not(a))
2748 }
2749 Expr::Implies(a, b) => {
2750 let a = self.p(*a, env, mode)?;
2751 let b = self.p(*b, env, mode)?;
2752 self.push(Node::Implies(a, b))
2753 }
2754 Expr::Equiv(a, b) => {
2755 let a = self.p(*a, env, mode)?;
2756 let b = self.p(*b, env, mode)?;
2757 self.push(Node::Equiv(a, b))
2758 }
2759 Expr::If { cond, then, other } => {
2760 let c = self.p(*cond, env, mode)?;
2761 let t = self.p(*then, env, mode)?;
2762 let o = self.p(*other, env, mode)?;
2763 self.push(Node::If(c, t, o))
2764 }
2765 Expr::Case { arms, other } => {
2766 let mut out = Vec::with_capacity(arms.len());
2767 for a in arms {
2768 let g = self.p(a.guard, env, mode)?;
2769 let v = self.p(a.value, env, mode)?;
2770 out.push((g, v));
2771 }
2772 let o = match other {
2773 Some(o) => Some(self.p(*o, env, mode)?),
2774 None => None,
2775 };
2776 self.push(Node::Case(out.into(), o))
2777 }
2778 Expr::Quant { kind, bounds, body } => {
2779 let (binds, saved) = self.binds(bounds, env, mode)?;
2780 let b = self.p(*body, env, mode);
2781 self.unbind(saved);
2782 let b = b?;
2783 let kind = match kind {
2784 QuantKind::Exists => Quant::Exists,
2785 QuantKind::Forall => Quant::Forall,
2786 QuantKind::Choose => Quant::Choose,
2787 };
2788 self.push(Node::Quant {
2789 kind,
2790 binds: binds.into(),
2791 body: b,
2792 })
2793 }
2794 Expr::SetFilter { bound, pred } => {
2795 let (mut binds, saved) = self.binds(std::slice::from_ref(bound), env, mode)?;
2796 let b = self.p(*pred, env, mode);
2797 self.unbind(saved);
2798 let b = b?;
2799 let bind = binds
2800 .pop()
2801 .ok_or_else(|| Error::internal("filter without a bound"))?;
2802 let subset = self.subset_rewrite(&bind, b)?;
2803 self.push_lazy(Node::Filter {
2804 bind,
2805 pred: b,
2806 subset,
2807 })
2808 }
2809 Expr::SetMap { expr, bounds } => {
2810 let (binds, saved) = self.binds(bounds, env, mode)?;
2811 let b = self.p(*expr, env, mode);
2812 self.unbind(saved);
2813 let b = b?;
2814 self.push(Node::Map {
2815 binds: binds.into(),
2816 body: b,
2817 })
2818 }
2819 Expr::FcnCons { bounds, body } => {
2820 let (binds, saved) = self.binds(bounds, env, mode)?;
2821 let b = self.p(*body, env, mode);
2822 self.unbind(saved);
2823 let b = b?;
2824 self.push_lazy(Node::FcnCons {
2825 binds: binds.into(),
2826 body: b,
2827 })
2828 }
2829 Expr::RecFcn { .. } => Err(Error::unsupported(
2830 "a recursive function used other than applied (M1 core)",
2831 )),
2832 Expr::SetEnum(items) => {
2833 let ps = self.ps(items, env, mode)?;
2834 self.push(Node::SetEnum(ps.into()))
2835 }
2836 Expr::Tuple(items) => {
2837 let ps = self.ps(items, env, mode)?;
2838 self.push(Node::Tuple(ps.into()))
2839 }
2840 Expr::Cartesian(items) => {
2841 let ps = self.ps(items, env, mode)?;
2842 self.push(Node::Product(ps.clone().into()))
2843 }
2844 Expr::Record(fields) | Expr::RecordSet(fields) => {
2845 let is_set = matches!(expr, Expr::RecordSet(_));
2846 let mut out = Vec::with_capacity(fields.len());
2847 for f in fields {
2848 let name = self.string(&f.name)?;
2849 let v = self.p(f.value, env, mode)?;
2850 out.push((name, v));
2851 }
2852 out.sort_by(|a, b| self.m.heap.cmp(a.0, b.0));
2853 if out.windows(2).any(|w| w[0].0 == w[1].0) {
2854 return Err(Error::unsupported("a record with a repeated field"));
2855 }
2856 if is_set {
2857 self.push(Node::RecSet(out.into()))
2858 } else {
2859 self.push(Node::Record(out.into()))
2860 }
2861 }
2862 Expr::FcnSet { domain, range } => {
2863 let d = self.p(*domain, env, mode)?;
2864 let r = self.p(*range, env, mode)?;
2865 self.push(Node::FcnSet(d, r))
2866 }
2867 Expr::FcnApply { fcn, arg } => {
2868 let (fcn, arg) = (*fcn, *arg);
2869 if let Some((d, fun)) = self.rec_target(fcn, env, mode)? {
2870 let a = self.p(arg, env, mode)?;
2871 return self.fun_call(d, fun, vec![a], env);
2872 }
2873 let f = self.p(fcn, env, mode)?;
2874 let a = self.p(arg, env, mode)?;
2875 self.apply_value(f, a)
2876 }
2877 Expr::RecordSelect { record, field } => {
2878 let r = self.p(*record, env, mode)?;
2879 let f = self.string(field)?;
2880 self.push(Node::Select(r, f))
2881 }
2882 Expr::Except { base, updates } => {
2883 let b = self.p(*base, env, mode)?;
2884 let mut out = Vec::with_capacity(updates.len());
2885 for u in updates {
2886 let path = self.ps(&u.path, env, mode)?;
2887 let at = self.alloc();
2888 self.at_stack.push(at);
2889 let v = self.p(u.value, env, mode);
2890 self.at_stack.pop();
2891 out.push(Update {
2892 path: path.into(),
2893 at,
2894 value: v?,
2895 });
2896 }
2897 self.push(Node::Except {
2898 base: b,
2899 updates: out.into(),
2900 })
2901 }
2902 Expr::ExceptAt => match self.at_stack.last() {
2903 Some(&at) => self.push(Node::Slot(at)),
2904 None => Err(Error::unsupported("@ outside EXCEPT")),
2905 },
2906 Expr::Let { defs, body } => {
2907 let body = *body;
2908 let defs = defs.clone();
2909 let (b, reset) = self.let_scope(&defs, env, |c| c.p(body, env, mode))?;
2910 if reset.is_empty() {
2911 Ok(b)
2912 } else {
2913 self.push(Node::Scope {
2914 reset: reset.into(),
2915 body: b,
2916 })
2917 }
2918 }
2919 Expr::Selected(a) | Expr::Label { body: a, .. } => self.p(*a, env, mode),
2920 Expr::Prime(a) => {
2921 if mode == Mode::Primed {
2922 return Err(Error::unsupported("a doubly primed expression"));
2923 }
2924 if self.init_mode {
2925 return Err(Error::unsupported(
2926 "a primed expression in an initial predicate",
2927 ));
2928 }
2929 self.p(*a, env, Mode::Primed)
2930 }
2931 Expr::Unchanged(a) => self.unchanged_value(*a, env, mode),
2932 Expr::Subst { bindings, body } => {
2933 let (bindings, body) = (bindings.clone(), *body);
2934 let (b, reset) =
2935 self.subst_scope(&bindings, env, mode, |c| c.p(body, env, mode))?;
2936 if reset.is_empty() {
2937 Ok(b)
2938 } else {
2939 self.push(Node::Scope {
2940 reset: reset.into(),
2941 body: b,
2942 })
2943 }
2944 }
2945 Expr::SubstRef { decl, primed } => {
2946 let (decl, primed) = (*decl, *primed);
2947 if primed && mode == Mode::Primed {
2948 return Err(Error::unsupported("a doubly primed expression"));
2949 }
2950 let mode = if primed { Mode::Primed } else { mode };
2951 self.subst_ref(decl, env, mode)
2952 }
2953 Expr::StepBox { action, sub } | Expr::StepAngle { action, sub } => {
2956 if mode == Mode::Primed || self.init_mode {
2957 return Err(Error::unsupported(
2958 "[A]_v under a prime or in an initial predicate (M1 core)",
2959 ));
2960 }
2961 let boxed = matches!(expr, Expr::StepBox { .. });
2962 let (action, sub) = (*action, *sub);
2963 let a = self.p(action, env, mode)?;
2964 let x = self.p(sub, env, Mode::Plain)?;
2965 let y = self.p(sub, env, Mode::Primed)?;
2966 let same = self.push(Node::Eq(x, y))?;
2967 if boxed {
2968 self.push(Node::Or([a, same].into()))
2969 } else {
2970 let changed = self.push(Node::Not(same))?;
2971 self.push(Node::And([a, changed].into()))
2972 }
2973 }
2974 Expr::Enabled(a) => self.enabled(Some(*a), None, env, mode),
2975 Expr::Cdot(a, b) => self.composition_value(*a, *b, env, mode),
2976 Expr::Always(_)
2977 | Expr::Eventually(_)
2978 | Expr::LeadsTo(..)
2979 | Expr::WhilePlus(..)
2980 | Expr::Wf { .. }
2981 | Expr::Sf { .. }
2982 | Expr::TemporalQuant { .. } => Err(Error::unsupported(
2983 "a temporal formula in a state or action role",
2984 )),
2985 Expr::Unbound(n) => Err(Error::unsupported(format!("the unbound name {n}"))),
2986 Expr::Unevaluable(_) => Err(Error::unsupported("an unevaluable expression")),
2987 }
2988 }
2989
2990 fn const_expr(&mut self, c: dive_ir::ConstId, env: usize, mode: Mode) -> Result<P, Error> {
2992 match self.h.constants.get(c.index()).cloned().flatten() {
2993 Some(ConstBinding::Value(v)) => {
2994 let h = if let Some(&h) = self.consts.get(&c.index()) {
2995 h
2996 } else {
2997 let h = self.convert(&v)?;
2998 self.consts.insert(c.index(), h);
2999 h
3000 };
3001 self.konst(h)
3002 }
3003 Some(ConstBinding::Def(d)) => {
3004 let d = self.redirect(d);
3005 let body = if self.h.overrides.contains(&d) {
3006 self.def_use(d, env, mode)?
3007 } else {
3008 self.def_body(d, env, mode)?
3012 };
3013 self.configured_result(body)
3014 }
3015 None => Err(Error::unsupported("an unbound constant")),
3016 }
3017 }
3018
3019 fn configured_result(&self, body: P) -> Result<P, Error> {
3021 if self.info[body as usize].calls {
3022 return Err(Error::unsupported(
3023 "a configured constant target with unresolved recursive or ENABLED calls (core)",
3024 ));
3025 }
3026 Ok(body)
3027 }
3028
3029 fn ps(&mut self, items: &[ExprId], env: usize, mode: Mode) -> Result<Vec<P>, Error> {
3030 let mut out = Vec::with_capacity(items.len());
3031 for &i in items {
3032 out.push(self.p(i, env, mode)?);
3033 }
3034 Ok(out)
3035 }
3036
3037 fn unchanged_value(&mut self, a: ExprId, env: usize, mode: Mode) -> Result<P, Error> {
3038 if mode == Mode::Primed || self.init_mode {
3039 return Err(Error::unsupported(
3040 "UNCHANGED under a prime or in an initial predicate",
3041 ));
3042 }
3043 let x = self.p(a, env, Mode::Plain)?;
3044 let y = self.p(a, env, Mode::Primed)?;
3045 self.push(Node::Eq(x, y))
3046 }
3047
3048 fn binds(
3051 &mut self,
3052 bounds: &[Bound],
3053 env: usize,
3054 mode: Mode,
3055 ) -> Result<(Vec<Bind>, Saved), Error> {
3056 let mut domains = Vec::with_capacity(bounds.len());
3057 for b in bounds {
3058 let Some(d) = b.domain else {
3059 return Err(Error::unsupported("an unbounded quantifier or CHOOSE"));
3060 };
3061 domains.push(self.p(d, env, mode)?);
3062 }
3063 let mut saved = Vec::new();
3064 let mut binds = Vec::with_capacity(bounds.len());
3065 for (b, domain) in bounds.iter().zip(domains) {
3066 let mut slots = Vec::with_capacity(b.vars.len());
3067 for v in &b.vars {
3068 let flat = self.alloc();
3069 let old = self.envs[env]
3070 .slots
3071 .get(v.index())
3072 .cloned()
3073 .unwrap_or(Sb::Unset);
3074 saved.push((env, v.index(), old));
3075 if let Some(s) = self.envs[env].slots.get_mut(v.index()) {
3076 *s = Sb::Flat(flat);
3077 }
3078 slots.push(flat);
3079 }
3080 binds.push(Bind {
3081 slots: slots.into(),
3082 tuple: b.tuple,
3083 domain,
3084 });
3085 }
3086 Ok((binds, saved))
3087 }
3088
3089 fn unbind(&mut self, saved: Saved) {
3090 for (env, slot, old) in saved.into_iter().rev() {
3091 if let Some(s) = self.envs[env].slots.get_mut(slot) {
3092 *s = old;
3093 }
3094 }
3095 }
3096
3097 fn let_scope<T>(
3100 &mut self,
3101 defs: &[DefId],
3102 env: usize,
3103 f: impl FnOnce(&mut Self) -> Result<T, Error>,
3104 ) -> Result<(T, Vec<u32>), Error> {
3105 let owner = self.reset_stack.len();
3106 self.reset_stack.push(Vec::new());
3107 let mut saved = Vec::new();
3108 for &d in defs {
3109 if let DefScope::LetValue { parent, slot, .. } = self.ir.def(d).scope {
3110 let target = self.find_env(env, parent).unwrap_or(env);
3111 let old = self.envs[target]
3112 .slots
3113 .get(slot.index())
3114 .cloned()
3115 .unwrap_or(Sb::Unset);
3116 saved.push((target, slot.index(), old));
3117 if let Some(s) = self.envs[target].slots.get_mut(slot.index()) {
3118 *s = Sb::LetVal {
3119 def: d,
3120 env: target,
3121 thunk: None,
3122 owner,
3123 };
3124 }
3125 }
3126 }
3127 let r = f(self);
3128 self.unbind(saved);
3129 let reset = self.reset_stack.pop().unwrap_or_default();
3130 Ok((r?, reset))
3131 }
3132
3133 fn frame_env(&self, env: usize, up: u32) -> Result<usize, Error> {
3134 let mut e = env;
3135 for _ in 0..up {
3136 e = self.envs[e]
3137 .parent
3138 .ok_or_else(|| Error::internal("a local reference beyond the outermost frame"))?;
3139 }
3140 Ok(e)
3141 }
3142
3143 fn local(&mut self, r: LocalRef, env: usize, mode: Mode) -> Result<P, Error> {
3144 let fe = self.frame_env(env, r.up)?;
3145 if self.lifts.last().is_some_and(|l| fe < l.floor) {
3146 return self.capture(fe, r.slot.index(), mode);
3147 }
3148 let sb = self.envs[fe]
3149 .slots
3150 .get(r.slot.index())
3151 .cloned()
3152 .unwrap_or(Sb::Unset);
3153 match sb {
3154 Sb::Flat(f) => self.push(Node::Slot(f)),
3155 Sb::Arg {
3156 expr,
3157 env: aenv,
3158 how,
3159 } => match (how, mode) {
3160 (ArgHow::Alias(p), Mode::Plain) => Ok(p),
3161 (ArgHow::Alias(p), Mode::Primed) => match self.code.nodes.get(p as usize) {
3162 Some(Node::Var(i)) => {
3163 let i = *i;
3164 self.push(Node::Primed(i))
3165 }
3166 Some(Node::Const(_) | Node::Slot(_)) => Ok(p),
3167 _ => {
3168 self.stats.by_name += 1;
3169 self.p(expr, aenv, Mode::Primed)
3170 }
3171 },
3172 (ArgHow::Thunk(slot, body), Mode::Plain) => {
3173 self.effect_thunk_use(slot, body)?;
3174 self.push(Node::Lazy { slot, body })
3175 }
3176 (ArgHow::Thunk(..), Mode::Primed) | (ArgHow::ByName, _) => {
3177 self.stats.by_name += 1;
3178 self.p(expr, aenv, mode)
3179 }
3180 },
3181 Sb::LetVal {
3182 def,
3183 env: lenv,
3184 thunk,
3185 owner,
3186 } => {
3187 let d = self.ir.def(def);
3188 if mode == Mode::Primed || d.level >= Level::Action {
3189 return self.p(d.body, lenv, mode);
3190 }
3191 let (slot, body) = if let Some(t) = thunk {
3192 t
3193 } else {
3194 let body = self.p(d.body, lenv, Mode::Plain)?;
3195 let slot = self.alloc();
3196 if let Some(Sb::LetVal { thunk, .. }) =
3197 self.envs[fe].slots.get_mut(r.slot.index())
3198 {
3199 *thunk = Some((slot, body));
3200 }
3201 if let Some(list) = self.reset_stack.get_mut(owner) {
3202 list.push(slot);
3203 }
3204 (slot, body)
3205 };
3206 if self.is_trivial(body) {
3207 return Ok(body);
3208 }
3209 self.effect_thunk_use(slot, body)?;
3210 self.push(Node::Lazy { slot, body })
3211 }
3212 Sb::RecSelf(..) => Err(Error::unsupported(
3213 "a recursive function used other than applied (M1 core)",
3214 )),
3215 Sb::Enclosing { env, slot } => self.capture(env, slot, mode),
3216 Sb::OpArg { .. } => Err(Error::internal("an operator parameter used as a value")),
3217 Sb::Unset => Err(Error::internal(format!(
3218 "unbound local {} in {}",
3219 self.ir
3220 .def(self.envs[fe].def)
3221 .frame
3222 .get(r.slot.index())
3223 .map_or("?", |s| s.name.as_str()),
3224 self.ir.def(self.envs[fe].def).name
3225 ))),
3226 }
3227 }
3228
3229 fn capture(&mut self, fe: usize, slot: usize, mode: Mode) -> Result<P, Error> {
3232 match (self.lifts.last().map(|l| l.mode), mode) {
3235 (None | Some(Mode::Plain), Mode::Primed) => {
3236 return Err(Error::unsupported(
3237 "a recursive LET definition reading an enclosing local under a prime (M1 core)",
3238 ));
3239 }
3240 (Some(Mode::Primed), Mode::Plain) => {
3241 return Err(Error::unsupported(
3242 "a recursive LET definition under a prime reading an enclosing local unprimed (M1 core)",
3243 ));
3244 }
3245 _ => {}
3246 }
3247 if matches!(self.envs[fe].slots.get(slot), Some(Sb::RecSelf(..))) {
3248 return Err(Error::unsupported(
3249 "a recursive function used inside a nested recursive definition (M1 core)",
3250 ));
3251 }
3252 let Some(l) = self.lifts.last() else {
3253 return Err(Error::internal("a capture outside a lifted function"));
3254 };
3255 let mut k = 0u32;
3256 let mut e = l.parent;
3257 loop {
3258 match e {
3259 Some(x) if x == fe => break,
3260 Some(x) => {
3261 e = self.envs[x].parent;
3262 k += 1;
3263 }
3264 None => {
3265 return Err(Error::unsupported(
3266 "a recursive function with a dynamic INSTANCE capture outside its lexical activation (M1 core)",
3267 ));
3268 }
3269 }
3270 }
3271 if let Some(&(_, _, c)) = l.caps.iter().find(|c| c.0 == k && c.1 == slot) {
3272 return self.push(Node::Slot(c));
3273 }
3274 let c = self.alloc();
3275 if let Some(l) = self.lifts.last_mut() {
3276 l.caps.push((k, slot, c));
3277 }
3278 self.push(Node::Slot(c))
3279 }
3280
3281 fn fun_call(&mut self, d: DefId, fun: u32, mut ps: Vec<P>, env: usize) -> Result<P, Error> {
3285 if let Some(i) = self.lifts.iter().position(|l| l.fun == fun) {
3286 if i + 1 != self.lifts.len() && self.lifts[i].parent.is_some() {
3289 return Err(Error::unsupported(
3290 "mutually recursive nested definitions (M1 core)",
3291 ));
3292 }
3293 let call = self.push(Node::Call {
3294 fun,
3295 args: ps.into(),
3296 })?;
3297 if let Some(l) = self.lifts.get_mut(i) {
3298 l.self_calls.push(call);
3299 }
3300 return Ok(call);
3301 }
3302 let caps = self.fun_caps.get(&fun).cloned().unwrap_or_default();
3303 if !caps.is_empty() {
3304 let mode = if self.primed_funs.contains(&fun) {
3305 Mode::Primed
3306 } else {
3307 Mode::Plain
3308 };
3309 let parent = match self.ir.def(d).scope {
3310 DefScope::LetValue { parent, .. } => self.find_env(env, parent),
3311 _ => self.lexical_parent(d, env)?,
3312 };
3313 let Some(parent) = parent else {
3314 return Err(Error::internal("captures of a top-level definition"));
3315 };
3316 for (k, slot) in caps {
3317 #[allow(clippy::cast_possible_truncation, reason = "frame slots are u32")]
3318 let r = LocalRef {
3319 up: k,
3320 slot: dive_ir::Slot(slot as u32),
3321 };
3322 let v = self.local(r, parent, mode)?;
3323 if self.info[v as usize].calls {
3324 return Err(Error::unsupported(
3325 "a recursive definition capturing a value with unproved recursive calls (M1 core)",
3326 ));
3327 }
3328 let v = if self.is_trivial(v) {
3329 v
3330 } else {
3331 self.stats.speculative += 1;
3332 self.push(Node::Spec(v))?
3333 };
3334 ps.push(v);
3335 }
3336 }
3337 self.push(Node::Call {
3338 fun,
3339 args: ps.into(),
3340 })
3341 }
3342
3343 fn begin_fun(
3347 &mut self,
3348 d: DefId,
3349 fun: u32,
3350 env: usize,
3351 mode: Mode,
3352 ) -> Result<(usize, bool), Error> {
3353 let parent = self.lexical_parent(d, env)?;
3354 let inner = self.new_env(d, parent);
3355 self.lifts.push(Lift {
3356 floor: inner,
3357 parent,
3358 fun,
3359 caps: Vec::new(),
3360 self_calls: Vec::new(),
3361 mode,
3362 });
3363 Ok((inner, true))
3364 }
3365
3366 fn begin_recfun(
3368 &mut self,
3369 d: DefId,
3370 fun: u32,
3371 env: usize,
3372 owner: Option<usize>,
3373 mode: Mode,
3374 ) -> Result<(usize, bool), Error> {
3375 if !matches!(self.ir.def(d).scope, DefScope::LetValue { .. }) {
3376 return self.begin_fun(d, fun, env, mode);
3377 }
3378 let owner = owner.ok_or_else(|| Error::internal("recursive LET function owner"))?;
3379 let inner = self.new_env(self.envs[owner].def, self.envs[owner].parent);
3380 for (slot, binding) in self.envs[inner].slots.iter_mut().enumerate() {
3381 *binding = Sb::Enclosing { env: owner, slot };
3382 }
3383 self.lifts.push(Lift {
3384 floor: inner,
3385 parent: Some(owner),
3386 fun,
3387 caps: Vec::new(),
3388 self_calls: Vec::new(),
3389 mode,
3390 });
3391 Ok((inner, true))
3392 }
3393
3394 fn end_fun(&mut self, fun: u32, lifted: bool) -> Result<(), Error> {
3397 if !lifted {
3398 return Ok(());
3399 }
3400 let Some(l) = self.lifts.pop() else {
3401 return Err(Error::internal("unbalanced lifted function"));
3402 };
3403 let slots: Vec<u32> = l.caps.iter().map(|c| c.2).collect();
3404 for &call in &l.self_calls {
3405 let mut extra = Vec::with_capacity(slots.len());
3406 for &c in &slots {
3407 extra.push(self.push(Node::Slot(c))?);
3408 }
3409 if let Some(Node::Call { args, .. }) = self.code.nodes.get_mut(call as usize) {
3410 let mut v = args.to_vec();
3411 v.extend(extra);
3412 *args = v.into();
3413 }
3414 }
3415 if let Some(f) = self.code.funs.get_mut(fun as usize) {
3416 f.caps = slots.clone().into();
3417 }
3418 self.fun_caps
3419 .insert(fun, l.caps.iter().map(|c| (c.0, c.1)).collect());
3420 Ok(())
3421 }
3422
3423 fn subst_scope<T>(
3428 &mut self,
3429 bindings: &[dive_ir::SubstBinding],
3430 env: usize,
3431 mode: Mode,
3432 f: impl FnOnce(&mut Self) -> Result<T, Error>,
3433 ) -> Result<(T, Vec<u32>), Error> {
3434 let depth = self.substs.len();
3435 let mut reset = Vec::new();
3436 let mut entries = Vec::with_capacity(bindings.len());
3437 for b in bindings {
3438 let how = match &b.value {
3439 Arg::Expr { expr, .. } => {
3440 let cp = self.p(*expr, env, mode)?;
3441 if self.opts.eager && self.is_trivial(cp) {
3442 self.stats.aliased += 1;
3443 ArgHow::Alias(cp)
3444 } else if self.info[cp as usize].primed == 0 {
3445 self.stats.thunks += 1;
3446 let slot = self.alloc();
3447 reset.push(slot);
3448 ArgHow::Thunk(slot, cp)
3449 } else {
3450 ArgHow::ByName
3451 }
3452 }
3453 Arg::Op { .. } => ArgHow::ByName,
3454 };
3455 let id = self.subst_id();
3456 entries.push(SubstEntry {
3457 id,
3458 decl: b.decl,
3459 value: Ok(b.value.clone()),
3460 env,
3461 how,
3462 depth,
3463 });
3464 }
3465 self.stats.substituted += entries.len();
3466 self.substs.extend(entries);
3467 let r = f(self);
3468 self.substs.truncate(depth);
3469 Ok((r?, reset))
3470 }
3471
3472 fn outside<T>(&mut self, depth: usize, f: impl FnOnce(&mut Self) -> T) -> T {
3475 let inner = self.substs.split_off(depth.min(self.substs.len()));
3476 let r = f(self);
3477 self.substs.extend(inner);
3478 r
3479 }
3480
3481 fn subst_op(&self, decl: dive_ir::DeclId) -> Result<OpRef, Error> {
3486 let mut decl = decl;
3487 let mut limit = self.substs.len();
3488 loop {
3489 let Some(i) = self.substs[..limit].iter().rposition(|s| s.decl == decl) else {
3490 return match self.ir.decl(decl).constant {
3491 Some(c) => Ok(OpRef::Const(c)),
3492 None => Err(Error::unsupported(
3493 "an unsubstituted operator declaration (M1 core)",
3494 )),
3495 };
3496 };
3497 let s = &self.substs[i];
3498 match &s.value {
3499 Ok(Arg::Op {
3500 op: OpRef::Subst(d2),
3501 ..
3502 }) => {
3503 decl = *d2;
3504 limit = s.depth.min(i);
3505 }
3506 Ok(Arg::Op {
3507 op: op @ (OpRef::Def(_) | OpRef::Std(_) | OpRef::Const(_)),
3508 ..
3509 }) if !matches!(op, OpRef::Def(d) if self.ir.def(self.redirect(*d)).scope != DefScope::TopLevel) =>
3510 {
3511 return Ok(op.clone());
3512 }
3513 _ => {
3514 return Err(Error::unsupported(
3515 "an INSTANCE substitution of an operator by a non-top-level operator (M1 core)",
3516 ));
3517 }
3518 }
3519 }
3520 }
3521
3522 fn subst_ref(&mut self, decl: dive_ir::DeclId, env: usize, mode: Mode) -> Result<P, Error> {
3526 let Some(i) = self.substs.iter().rposition(|s| s.decl == decl) else {
3527 let d = self.ir.decl(decl);
3528 #[allow(clippy::cast_possible_truncation, reason = "at most 64 variables")]
3529 return match (d.var, d.constant) {
3530 (Some(v), _) if self.init_mode => {
3531 if mode == Mode::Primed {
3532 return Err(Error::unsupported(
3533 "a primed variable in an initial predicate",
3534 ));
3535 }
3536 self.push(Node::Primed(v.index() as u16))
3537 }
3538 (Some(v), _) => match mode {
3539 Mode::Plain => self.push(Node::Var(v.index() as u16)),
3540 Mode::Primed => self.push(Node::Primed(v.index() as u16)),
3541 },
3542 (None, Some(c)) => self.const_expr(c, env, mode),
3543 (None, None) => Err(Error::unsupported(format!(
3544 "the unsubstituted variable {} of an instantiated module (M1 core)",
3545 d.name
3546 ))),
3547 };
3548 };
3549 let SubstEntry {
3550 id,
3551 value,
3552 env,
3553 how,
3554 depth,
3555 ..
3556 } = self.substs[i].clone();
3557 let expr = match value {
3558 Ok(Arg::Expr { expr, .. }) => expr,
3559 Err(p) => return Ok(p),
3560 Ok(Arg::Op { .. }) => {
3561 return Err(Error::unsupported(
3562 "an operator substitution used as a value (M1 core)",
3563 ));
3564 }
3565 };
3566 if self.lifts.last().is_some_and(|lift| env < lift.floor) {
3567 if let ArgHow::Alias(mut p) | ArgHow::Thunk(_, mut p) = how {
3571 while let Some(Node::Lazy { body, .. }) = self.code.nodes.get(p as usize) {
3574 p = *body;
3575 }
3576 if matches!(self.code.nodes.get(p as usize), Some(Node::Const(_))) {
3577 return Ok(p);
3578 }
3579 }
3580 let body = self.outside(depth, |c| c.p(expr, env, mode))?;
3581 if self.info[body as usize].effect || self.info[body as usize].calls {
3582 return Err(Error::unsupported(
3583 "an effectful or recursive INSTANCE substitution inside a recursive function (M1 core)",
3584 ));
3585 }
3586 return Ok(body);
3587 }
3588 match (how, mode) {
3589 (ArgHow::Alias(p), Mode::Plain) => Ok(p),
3590 (ArgHow::Alias(p), Mode::Primed) => match self.code.nodes.get(p as usize) {
3591 Some(Node::Var(v)) => {
3592 let v = *v;
3593 self.push(Node::Primed(v))
3594 }
3595 Some(Node::Const(_) | Node::Slot(_)) => Ok(p),
3596 _ => {
3597 self.stats.by_name += 1;
3598 self.outside(depth, |c| c.p(expr, env, Mode::Primed))
3599 }
3600 },
3601 (ArgHow::Thunk(slot, body), Mode::Plain) => {
3602 self.effect_thunk_use(slot, body)?;
3603 self.push(Node::Lazy { slot, body })
3604 }
3605 (ArgHow::Thunk(..), Mode::Primed) | (ArgHow::ByName, _) => {
3606 self.stats.by_name += 1;
3607 if self.step {
3608 return self.step_cached(Cached::Subst(id, mode), |c| {
3609 c.outside(depth, |c| c.p(expr, env, mode))
3610 });
3611 }
3612 self.outside(depth, |c| c.p(expr, env, mode))
3613 }
3614 }
3615 }
3616
3617 fn subst_id(&mut self) -> u32 {
3619 self.subst_ids += 1;
3620 self.subst_ids
3621 }
3622
3623 fn step_cached(
3630 &mut self,
3631 key: Cached,
3632 compile: impl FnOnce(&mut Self) -> Result<P, Error>,
3633 ) -> Result<P, Error> {
3634 if let Some(&(slot, body)) = self.def_cache.get(&key) {
3635 return self.push(Node::Lazy { slot, body });
3636 }
3637 let body = compile(self)?;
3638 let info = &self.info[body as usize];
3639 if !info.free.is_empty() || info.effect || info.calls || self.is_trivial(body) {
3640 return Ok(body);
3641 }
3642 let body = self.step_site(key, body)?;
3643 let slot = self.alloc();
3644 self.def_cache.insert(key, (slot, body));
3645 self.def_slots.insert(slot);
3646 self.stats.cached_defs += 1;
3647 self.push(Node::Lazy { slot, body })
3648 }
3649
3650 fn assembles(&self, mut body: P) -> bool {
3655 while let Some(Node::Scope { body: b, .. } | Node::Spec(b)) =
3656 self.code.nodes.get(body as usize)
3657 {
3658 body = *b;
3659 }
3660 let leaf = |p: &P| {
3661 matches!(
3662 self.code.nodes.get(*p as usize),
3663 Some(
3664 Node::Const(_)
3665 | Node::Slot(_)
3666 | Node::Var(_)
3667 | Node::Primed(_)
3668 | Node::Lazy { .. }
3669 | Node::Memo { .. }
3670 )
3671 )
3672 };
3673 match self.code.nodes.get(body as usize) {
3674 Some(Node::Lazy { .. } | Node::Memo { .. }) => true,
3675 Some(Node::Tuple(items) | Node::SetEnum(items)) => items.iter().all(leaf),
3676 Some(Node::Record(fields)) => fields.iter().all(|(_, p)| leaf(p)),
3677 _ => false,
3678 }
3679 }
3680
3681 fn step_site(&mut self, key: Cached, body: P) -> Result<P, Error> {
3686 if !self.opts.step_memo || self.assembles(body) {
3687 return Ok(body);
3688 }
3689 let info = &self.info[body as usize];
3690 let bits = |m: u64| -> Vec<u16> {
3691 #[allow(clippy::cast_possible_truncation, reason = "at most 64 variables")]
3692 (0..64u16).filter(|&v| m & (1u64 << v) != 0).collect()
3693 };
3694 let (vars, primed) = (bits(info.vars), bits(info.primed));
3695 if vars.len() + primed.len() > MAX_KEY || (vars.is_empty() && primed.is_empty()) {
3696 return Ok(body);
3697 }
3698 let name = match key {
3699 Cached::Def(d, mode, _) => format!("{} ({mode:?}, step)", self.ir.def(d).name),
3700 Cached::Subst(id, mode) => format!("substitution {id} ({mode:?}, step)"),
3701 };
3702 #[allow(clippy::cast_possible_truncation, reason = "bounded")]
3703 let site = self.code.sites.len() as u32;
3704 self.code.sites.push(MemoSite {
3705 name: name.clone(),
3706 vars: vars.into(),
3707 slots: Box::new([]),
3708 primed: primed.into(),
3709 step: true,
3710 candidate: false,
3711 });
3712 self.site_names.push(name);
3713 self.push(Node::Memo { site, body })
3714 }
3715
3716 fn subst_is_value(&self, decl: dive_ir::DeclId) -> bool {
3719 self.substs
3720 .iter()
3721 .rev()
3722 .find(|s| s.decl == decl)
3723 .is_some_and(|s| s.value.is_err())
3724 }
3725
3726 fn subst_expr(&self, decl: dive_ir::DeclId) -> Option<Result<(ExprId, usize, usize), Error>> {
3729 let i = self.substs.iter().rposition(|s| s.decl == decl)?;
3730 let s = &self.substs[i];
3731 Some(match &s.value {
3732 Ok(Arg::Expr { expr, .. }) => Ok((*expr, s.env, s.depth)),
3733 Ok(Arg::Op { .. }) => Err(Error::unsupported(
3734 "an operator substitution used as a value (M1 core)",
3735 )),
3736 Err(_) => Err(Error::unsupported(
3737 "a substitution by a value used as an action or a variable (M1 core)",
3738 )),
3739 })
3740 }
3741
3742 fn def_use(&mut self, d: DefId, env: usize, mode: Mode) -> Result<P, Error> {
3744 let r = self.redirect(d);
3745 if r != d
3746 && !self.h.overrides.contains(&r)
3747 && self.ir.def(r).effects.intersects(dive_ir::Effects::IMPURE)
3748 {
3749 return self.def_body(r, env, mode);
3754 }
3755 let d = r;
3756 if let Some(h) = self.precomputed(d)? {
3757 return self.konst(h);
3758 }
3759 if self.substs.is_empty()
3760 && let Some(&Some(h)) = self.settled.get(&d)
3761 {
3762 return self.konst(h);
3763 }
3764 self.def_body(d, env, mode)
3765 }
3766
3767 fn settle(&mut self, d: DefId, body: P) -> P {
3783 if !self.opts.fold
3786 || !self.substs.is_empty()
3787 || self.h.deferred.contains(&d)
3788 || self.settled.contains_key(&d)
3789 {
3790 return body;
3791 }
3792 let Some(info) = self.info.get(body as usize) else {
3793 return body;
3794 };
3795 let closed = info.vars == 0
3796 && info.primed == 0
3797 && info.free.is_empty()
3798 && !info.calls
3799 && !info.effect;
3800 if !closed || !info.heavy || self.is_trivial(body) {
3801 return body;
3802 }
3803 let fuel = SETTLE_FUEL.min(SETTLE_BUDGET.saturating_sub(self.settle_fuel));
3804 if fuel == 0 {
3805 return body;
3806 }
3807 let started = std::time::Instant::now();
3808 self.m.set_fuel(fuel);
3809 let bound = std::mem::replace(&mut self.m.transient_bound, STARTUP_TRANSIENT_BYTES);
3810 let old = self.m.enter(self.next_slot + 1);
3811 let r = self.m.eval(&self.code, body);
3812 self.m.leave(old);
3813 self.m.transient_bound = bound;
3814 let spent = fuel - self.m.fuel;
3815 let exhausted = self.m.fuel == 0;
3816 self.m.set_fuel(u64::MAX);
3817 let r = r.and_then(|h| self.m.heap.intern_const(h));
3818 self.m.heap.reset();
3819 self.settle_fuel += spent;
3820 self.stats.startup_nanos += u64::try_from(started.elapsed().as_nanos()).unwrap_or(u64::MAX);
3821 match r {
3822 Ok(h) if !exhausted && !h.is_empty() => {
3823 self.code.nodes[body as usize] = Node::Const(h);
3824 let red = self.info[body as usize].red;
3825 self.info[body as usize] = Info {
3826 red,
3827 ..Info::default()
3828 };
3829 self.settled.insert(d, Some(h));
3830 self.stats.startup_values += 1;
3831 }
3832 _ => {
3833 self.settled.insert(d, None);
3834 }
3835 }
3836 body
3837 }
3838
3839 fn def_body(&mut self, d: DefId, env: usize, mode: Mode) -> Result<P, Error> {
3841 let def = self.ir.def(d);
3842 if let Some(op) = def.std {
3843 return self.std_apply(op, &[], env, mode);
3844 }
3845 if !def.params.is_empty() {
3846 return Err(Error::unsupported(format!(
3847 "the operator {} used as a value",
3848 def.name
3849 )));
3850 }
3851 if def.recursive {
3852 return self.call(d, &[], env, mode);
3853 }
3854 let key = Cached::Def(d, mode, self.substs.last().map(|s| s.id));
3855 if self.step && !self.init_mode && def.scope == DefScope::TopLevel {
3856 let parent = self.lexical_parent(d, env)?;
3857 return self.step_cached(key, |c| {
3858 let inner = c.new_env(d, parent);
3859 let body = c.p(def.body, inner, mode)?;
3860 Ok(c.settle(d, body))
3861 });
3862 }
3863 let cacheable = mode == Mode::Plain && !self.init_mode && def.scope == DefScope::TopLevel;
3864 if cacheable && let Some(&(slot, body)) = self.def_cache.get(&key) {
3865 return self.push(Node::Lazy { slot, body });
3866 }
3867 let parent = self.lexical_parent(d, env)?;
3868 let inner = self.new_env(d, parent);
3869 let body = self.p(def.body, inner, mode)?;
3870 let body = self.settle(d, body);
3871 let info = &self.info[body as usize];
3875 if cacheable
3876 && info.free.is_empty()
3877 && info.primed == 0
3878 && !info.effect
3879 && !info.calls
3880 && !self.is_trivial(body)
3881 {
3882 let slot = self.alloc();
3883 self.def_cache.insert(key, (slot, body));
3884 self.def_slots.insert(slot);
3885 self.stats.cached_defs += 1;
3886 return self.push(Node::Lazy { slot, body });
3887 }
3888 if def.scope == DefScope::TopLevel && !self.init_mode {
3889 return self.primed_site(d, mode, body);
3890 }
3891 Ok(body)
3892 }
3893
3894 fn primed_site(&mut self, d: DefId, mode: Mode, body: P) -> Result<P, Error> {
3907 if !self.opts.primed_memo
3908 || self.assembles(body)
3909 || self.is_trivial(body)
3910 || self.structural(body)
3911 {
3912 return Ok(body);
3913 }
3914 let info = &self.info[body as usize];
3915 if info.primed == 0 || !info.free.is_empty() || info.effect || info.calls {
3916 return Ok(body);
3917 }
3918 let bits = |m: u64| -> Vec<u16> {
3919 #[allow(clippy::cast_possible_truncation, reason = "at most 64 variables")]
3920 (0..64u16).filter(|&v| m & (1u64 << v) != 0).collect()
3921 };
3922 let (vars, primed) = (bits(info.vars), bits(info.primed));
3923 if vars.len() + primed.len() > MAX_KEY {
3924 return Ok(body);
3925 }
3926 let name = format!("{} ({mode:?}, action)", self.ir.def(d).name);
3927 #[allow(clippy::cast_possible_truncation, reason = "bounded")]
3928 let site = self.code.sites.len() as u32;
3929 self.code.sites.push(MemoSite {
3930 name: name.clone(),
3931 vars: vars.into(),
3932 slots: Box::new([]),
3933 primed: primed.into(),
3934 step: true,
3935 candidate: true,
3936 });
3937 self.site_names.push(name);
3938 self.push(Node::Memo { site, body })
3939 }
3940
3941 fn structural(&self, body: P) -> bool {
3953 if self.lambda(body).is_some() {
3954 return true;
3955 }
3956 let mut p = body;
3957 while let Some(Node::Scope { body: b, .. } | Node::Spec(b)) =
3958 self.code.nodes.get(p as usize)
3959 {
3960 p = *b;
3961 }
3962 matches!(
3963 self.code.nodes.get(p as usize),
3964 Some(
3965 Node::Powerset(_)
3966 | Node::Product(_)
3967 | Node::FcnSet(..)
3968 | Node::RecSet(_)
3969 | Node::Std(StdFn::Seq, _)
3970 )
3971 )
3972 }
3973
3974 fn apply(&mut self, callee: &OpRef, args: &[Arg], env: usize, mode: Mode) -> Result<P, Error> {
3975 match callee {
3976 OpRef::Def(d) => {
3977 let d = self.redirect(*d);
3978 let def = self.ir.def(d);
3979 if let Some(op) = def.std {
3980 return self.std_apply(op, args, env, mode);
3981 }
3982 if args.is_empty() {
3983 return self.def_use(d, env, mode);
3984 }
3985 if def.recursive {
3986 return self.call(d, args, env, mode);
3987 }
3988 self.inline_apply(d, args, env, env, mode)
3989 }
3990 OpRef::Std(op) => {
3991 if let Some(&t) = self.h.std_redirects.get(op) {
3992 return self.apply(&OpRef::Def(t), args, env, mode);
3993 }
3994 self.std_apply(*op, args, env, mode)
3995 }
3996 OpRef::Param(r) => self.apply_param(*r, args, env, env, mode),
3997 OpRef::Builtin(op) => self.builtin_apply(*op, args, env, mode),
3998 OpRef::Const(c) => match self.h.constants.get(c.index()).cloned().flatten() {
4000 Some(ConstBinding::Def(_)) if args.is_empty() => self.const_expr(*c, env, mode),
4001 Some(ConstBinding::Def(d)) => {
4002 let body = self.apply(&OpRef::Def(d), args, env, mode)?;
4003 self.configured_result(body)
4004 }
4005 _ => Err(Error::unsupported(
4006 "a constant operator the configuration does not bind to a definition (M1 core)",
4007 )),
4008 },
4009 OpRef::Subst(decl) => {
4013 let op = self.subst_op(*decl)?;
4014 self.apply(&op, args, env, mode)
4015 }
4016 OpRef::Unbound(n) => Err(Error::unsupported(format!("the unbound operator {n}"))),
4017 }
4018 }
4019
4020 fn builtin_apply(
4026 &mut self,
4027 op: BuiltinOp,
4028 args: &[Arg],
4029 env: usize,
4030 mode: Mode,
4031 ) -> Result<P, Error> {
4032 if !builtin_value_arg(op) {
4033 return Err(Error::unsupported(format!(
4034 "the built-in {} as an operator argument (M0 core)",
4035 op.sany_name()
4036 )));
4037 }
4038 let mut exprs = Vec::with_capacity(args.len());
4039 for a in args {
4040 let Arg::Expr { expr, .. } = a else {
4041 return Err(Error::unsupported(format!(
4042 "the built-in {} applied to an operator argument",
4043 op.sany_name()
4044 )));
4045 };
4046 exprs.push(*expr);
4047 }
4048 if builtin_arity(op) != Some(exprs.len()) {
4049 return Err(Error::internal(format!(
4050 "the built-in {} applied to {} arguments",
4051 op.sany_name(),
4052 exprs.len()
4053 )));
4054 }
4055 self.builtin(op, &exprs, env, mode)
4056 }
4057
4058 fn inline_apply(
4062 &mut self,
4063 d: DefId,
4064 args: &[Arg],
4065 env: usize,
4066 def_env: usize,
4067 mode: Mode,
4068 ) -> Result<P, Error> {
4069 let body = self.ir.def(d).body;
4070 let (inner, reset) = self.inline(d, args, env, def_env, mode)?;
4071 let b = self.p(body, inner, mode)?;
4072 if reset.is_empty() {
4073 Ok(b)
4074 } else {
4075 self.push(Node::Scope {
4076 reset: reset.into(),
4077 body: b,
4078 })
4079 }
4080 }
4081
4082 fn g_inline(&mut self, d: DefId, args: &[Arg], env: usize, def_env: usize) -> Result<G, Error> {
4085 let body = self.ir.def(d).body;
4086 let (inner, reset) = self.inline(d, args, env, def_env, Mode::Plain)?;
4087 let g = self.g(body, inner)?;
4088 if reset.is_empty() {
4089 Ok(g)
4090 } else {
4091 Ok(self.gpush(GNode::Scope {
4092 reset: reset.into(),
4093 body: g,
4094 }))
4095 }
4096 }
4097
4098 fn g_apply_op(
4101 &mut self,
4102 op: &OpRef,
4103 args: &[Arg],
4104 e: ExprId,
4105 env: usize,
4106 aenv: usize,
4107 ) -> Result<G, Error> {
4108 let d = match *op {
4109 OpRef::Def(d) => d,
4110 OpRef::Const(c) => match self.h.constants.get(c.index()).cloned().flatten() {
4111 Some(ConstBinding::Def(d)) => d,
4112 _ => return self.guard_expr(e, env),
4113 },
4114 OpRef::Builtin(b) => {
4117 return Err(Error::unsupported(format!(
4118 "the built-in {} passed as an operator argument and applied as an action (M1 core)",
4119 b.sany_name()
4120 )));
4121 }
4122 _ => return self.guard_expr(e, env),
4123 };
4124 let d = self.redirect(d);
4125 let def = self.ir.def(d);
4126 if def.std.is_some() || def.recursive || args.is_empty() {
4127 return self.guard_expr(e, env);
4128 }
4129 let def_env = if def.scope == DefScope::TopLevel {
4130 env
4131 } else {
4132 aenv
4133 };
4134 self.g_inline(d, args, env, def_env)
4135 }
4136
4137 pub(crate) fn op_fn(
4158 &mut self,
4159 a: &Arg,
4160 env: usize,
4161 arity: usize,
4162 ) -> Result<(Box<[u32]>, P), Error> {
4163 let Arg::Op { op, .. } = a else {
4164 return Err(Error::unsupported(
4165 "an expression where an operator argument is expected (M1 core)",
4166 ));
4167 };
4168 let (op, aenv, enclosing) = match op {
4169 OpRef::Param(r) => self.resolve_param(*r, env)?,
4170 OpRef::Subst(decl) => (self.subst_op(*decl)?, env, false),
4171 op => (op.clone(), env, false),
4172 };
4173 let d = match op {
4174 OpRef::Def(d) => d,
4175 OpRef::Std(s) => match self.h.std_redirects.get(&s) {
4176 Some(&t) => t,
4177 None => return self.std_op_fn(s, arity),
4178 },
4179 OpRef::Const(c) => match self.h.constants.get(c.index()).cloned().flatten() {
4180 Some(ConstBinding::Def(d)) => d,
4181 _ => {
4182 return Err(Error::unsupported(
4183 "a constant operator the configuration does not bind to a definition (M1 core)",
4184 ));
4185 }
4186 },
4187 _ => {
4188 return Err(Error::unsupported(
4189 "a built-in operator passed to a higher-order operator (M1 core)",
4190 ));
4191 }
4192 };
4193 let mut d = self.redirect(d);
4194 if let Some(s) = self.ir.def(d).std {
4195 match self.h.std_redirects.get(&s) {
4196 Some(&t) if t != d => d = self.redirect(t),
4197 _ => {
4198 if self.ir.def(d).params.len() != arity {
4199 return Err(Error::internal(format!(
4200 "{} passed where an operator of {arity} arguments is expected",
4201 self.ir.def(d).name
4202 )));
4203 }
4204 return self.std_op_fn(s, arity);
4205 }
4206 }
4207 }
4208 let def = self.ir.def(d);
4209 if def.std.is_some() || def.recursive {
4210 return Err(Error::unsupported(
4211 "a std or recursive operator passed to a higher-order operator (M1 core)",
4212 ));
4213 }
4214 if def.params.len() != arity {
4215 return Err(Error::internal(format!(
4216 "{} passed where an operator of {arity} arguments is expected",
4217 def.name
4218 )));
4219 }
4220 let body = def.body;
4221 let def_env = if def.scope == DefScope::TopLevel {
4222 env
4223 } else {
4224 aenv
4225 };
4226 let parent = self.lexical_parent(d, def_env)?;
4227 let inner = self.new_env(d, parent);
4228 let mut slots = Vec::with_capacity(arity);
4229 for i in 0..arity {
4230 let slot = self.alloc();
4231 if let Some(s) = self.envs[inner].slots.get_mut(i) {
4232 *s = Sb::Flat(slot);
4233 }
4234 slots.push(slot);
4235 }
4236 let b = self.p(body, inner, Mode::Plain)?;
4237 self.enclosing_op_body(b, enclosing)?;
4238 Ok((slots.into(), b))
4239 }
4240
4241 fn std_op_fn(&mut self, op: StdOp, arity: usize) -> Result<(Box<[u32]>, P), Error> {
4254 if crate::stdlib::higher_order(op) || op.impure() || arity == 0 {
4255 return Err(Error::unsupported(format!(
4256 "{} passed to a higher-order operator (M1 core)",
4257 op.qualified_name()
4258 )));
4259 }
4260 if usize::try_from(op.java_arity()).ok() != Some(arity) {
4261 return Err(Error::unsupported(format!(
4262 "{} passed where an operator of {arity} arguments is expected",
4263 op.qualified_name()
4264 )));
4265 }
4266 let mut slots = Vec::with_capacity(arity);
4267 let mut ps = Vec::with_capacity(arity);
4268 for _ in 0..arity {
4269 let slot = self.alloc();
4270 slots.push(slot);
4271 ps.push(self.push(Node::Slot(slot))?);
4272 }
4273 let body = self.std_node(op, ps, None)?;
4274 let body = self.push(Node::Spec(body))?;
4275 Ok((slots.into(), body))
4276 }
4277
4278 fn resolve_param(&self, r: LocalRef, look_env: usize) -> Result<(OpRef, usize, bool), Error> {
4282 let mut r = r;
4283 let mut look = look_env;
4284 let mut enclosing = false;
4285 loop {
4286 let fe = self.frame_env(look, r.up)?;
4287 if !enclosing && self.lifts.last().is_some_and(|l| fe < l.floor) {
4288 return Err(Error::unsupported(
4289 "an enclosing operator parameter inside a recursive LET definition (M1 core)",
4290 ));
4291 }
4292 let mut binding = self.envs[fe].slots.get(r.slot.index());
4293 while let Some(Sb::Enclosing { env, slot }) = binding {
4294 enclosing = true;
4298 binding = self.envs[*env].slots.get(*slot);
4299 }
4300 let Some(Sb::OpArg { op, env }) = binding.cloned() else {
4301 return Err(Error::unsupported(
4302 "an operator parameter of a recursive operator (M1 core)",
4303 ));
4304 };
4305 match op {
4306 OpRef::Param(r2) => {
4307 r = r2;
4308 look = env;
4309 }
4310 op => return Ok((op, env, enclosing)),
4311 }
4312 }
4313 }
4314
4315 fn enclosing_op_body(&self, body: P, enclosing: bool) -> Result<(), Error> {
4318 if enclosing && (self.info[body as usize].effect || self.info[body as usize].calls) {
4319 return Err(Error::unsupported(
4320 "an enclosing operator argument with effects or recursive calls inside a recursive function (M1 core)",
4321 ));
4322 }
4323 Ok(())
4324 }
4325
4326 fn apply_param(
4331 &mut self,
4332 r: LocalRef,
4333 args: &[Arg],
4334 env: usize,
4335 look_env: usize,
4336 mode: Mode,
4337 ) -> Result<P, Error> {
4338 let (op, aenv, enclosing) = self.resolve_param(r, look_env)?;
4339 let body = match op {
4340 OpRef::Param(_) => Err(Error::internal("an unresolved operator parameter")),
4341 OpRef::Def(d) => {
4342 let d = self.redirect(d);
4343 let def = self.ir.def(d);
4344 if def.std.is_some() || def.scope == DefScope::TopLevel {
4345 self.apply(&OpRef::Def(d), args, env, mode)
4346 } else if def.recursive {
4347 Err(Error::unsupported(
4348 "a recursive LET operator passed as an operator argument (M1 core)",
4349 ))
4350 } else {
4351 self.inline_apply(d, args, env, aenv, mode)
4352 }
4353 }
4354 OpRef::Subst(_) => Err(Error::unsupported(
4355 "an INSTANCE-substituted operator passed as an operator argument (M1 core)",
4356 )),
4357 OpRef::Builtin(b) => return self.builtin_apply(b, args, env, mode),
4362 op @ (OpRef::Std(_) | OpRef::Const(_) | OpRef::Unbound(_)) => {
4363 self.apply(&op, args, env, mode)
4364 }
4365 }?;
4366 self.enclosing_op_body(body, enclosing)?;
4367 Ok(body)
4368 }
4369
4370 fn inline(
4373 &mut self,
4374 d: DefId,
4375 args: &[Arg],
4376 env: usize,
4377 def_env: usize,
4378 mode: Mode,
4379 ) -> Result<(usize, Vec<u32>), Error> {
4380 let def = self.ir.def(d);
4381 if def.params.len() != args.len() {
4382 return Err(Error::internal(format!(
4383 "{} applied to {} arguments",
4384 def.name,
4385 args.len()
4386 )));
4387 }
4388 let parent = self.lexical_parent(d, def_env)?;
4389 let inner = self.new_env(d, parent);
4390 let mut reset = Vec::new();
4391 self.stats.inlined += 1;
4392 for (i, a) in args.iter().enumerate() {
4393 let expr = match a {
4394 Arg::Expr { expr, .. } => expr,
4395 Arg::Op { op, .. } => {
4396 if let Some(s) = self.envs[inner].slots.get_mut(i) {
4397 *s = Sb::OpArg {
4398 op: op.clone(),
4399 env,
4400 };
4401 }
4402 continue;
4403 }
4404 };
4405 let cp = self.p(*expr, env, mode)?;
4406 let how = if self.opts.eager && self.is_trivial(cp) {
4407 self.stats.aliased += 1;
4408 ArgHow::Alias(cp)
4409 } else if self.info[cp as usize].primed == 0 {
4410 self.stats.thunks += 1;
4411 let slot = self.alloc();
4412 reset.push(slot);
4413 ArgHow::Thunk(slot, cp)
4414 } else {
4415 ArgHow::ByName
4416 };
4417 if let Some(s) = self.envs[inner].slots.get_mut(i) {
4418 *s = Sb::Arg {
4419 expr: *expr,
4420 env,
4421 how,
4422 };
4423 }
4424 }
4425 Ok((inner, reset))
4426 }
4427
4428 fn call(&mut self, d: DefId, args: &[Arg], env: usize, mode: Mode) -> Result<P, Error> {
4434 let fun = self.fun(d, env, mode)?;
4435 let mut ps = Vec::with_capacity(args.len());
4436 for a in args {
4437 let Arg::Expr { expr, .. } = a else {
4438 return Err(Error::unsupported("operator arguments (M0 core)"));
4439 };
4440 let a = self.p(*expr, env, mode)?;
4443 let a = if self.is_trivial(a) {
4444 a
4445 } else {
4446 self.stats.speculative += 1;
4447 self.push(Node::Spec(a))?
4448 };
4449 ps.push(a);
4450 }
4451 self.fun_call(d, fun, ps, env)
4452 }
4453
4454 fn fun(&mut self, d: DefId, call_env: usize, mode: Mode) -> Result<u32, Error> {
4455 let key = (
4456 d,
4457 mode,
4458 self.init_mode,
4459 self.lexical_parent(d, call_env)?,
4460 self.substs.last().map(|s| s.id),
4461 );
4462 if let Some(&f) = self.funs.get(&key) {
4463 return Ok(self.reenter(f));
4464 }
4465 let def = self.ir.def(d);
4466 #[allow(clippy::cast_possible_truncation, reason = "bounded")]
4467 let id = self.code.funs.len() as u32;
4468 #[allow(
4469 clippy::cast_possible_truncation,
4470 reason = "parameter counts are small"
4471 )]
4472 let params = def.params.len() as u32;
4473 self.code.funs.push(Fun {
4474 name: def.name.clone(),
4475 params,
4476 frame: params,
4477 body: 0,
4478 caps: Box::new([]),
4479 });
4480 self.funs.insert(key, id);
4481 self.open_fun(id, mode, def.level);
4482 let saved_slot = self.next_slot;
4483 let saved_resets = std::mem::take(&mut self.reset_stack);
4484 let saved_cache = std::mem::take(&mut self.def_cache);
4485 let saved_at = std::mem::take(&mut self.at_stack);
4486 self.next_slot = params;
4487 let saved_frame = self.new_frame();
4488 let (env, lifted) = match self.begin_fun(d, id, call_env, mode) {
4489 Ok(x) => x,
4490 Err(e) => {
4491 self.frame = saved_frame;
4492 self.next_slot = saved_slot;
4493 self.reset_stack = saved_resets;
4494 self.def_cache = saved_cache;
4495 self.at_stack = saved_at;
4496 return Err(e);
4497 }
4498 };
4499 for i in 0..def.params.len() {
4500 #[allow(
4501 clippy::cast_possible_truncation,
4502 reason = "parameter counts are small"
4503 )]
4504 let s = Sb::Flat(i as u32);
4505 if let Some(x) = self.envs[env].slots.get_mut(i) {
4506 *x = s;
4507 }
4508 }
4509 let body = self.p(def.body, env, mode);
4510 let ended = self.end_fun(id, lifted);
4511 self.frame = saved_frame;
4512 let frame = self.next_slot;
4513 self.next_slot = saved_slot;
4514 self.reset_stack = saved_resets;
4515 self.def_cache = saved_cache;
4516 self.at_stack = saved_at;
4517 self.open_funs.remove(&id);
4518 let body = body?;
4519 ended?;
4520 self.note_next_reads(id, &[body])?;
4521 if mode == Mode::Primed && self.info[body as usize].effect {
4522 return Err(Error::unsupported(
4523 "an effectful recursive operator under a prime (M1 core)",
4524 ));
4525 }
4526 self.complete_fun(id, body, frame);
4527 Ok(id)
4528 }
4529
4530 fn complete_fun(&mut self, fun: u32, body: P, frame: u32) {
4533 if let Some(f) = self.code.funs.get_mut(fun as usize) {
4534 f.body = body;
4535 f.frame = frame;
4536 }
4537 if let Some(vars) = self.fun_summary(fun, body) {
4538 self.fun_reads.insert(fun, vars);
4539 }
4540 }
4541
4542 fn fun_summary(&self, fun: u32, body: P) -> Option<u64> {
4555 let mut vars = 0u64;
4556 let mut seen = std::collections::HashSet::new();
4557 let mut stack = vec![body];
4558 while let Some(p) = stack.pop() {
4559 if !seen.insert(p) {
4560 continue;
4561 }
4562 let info = self.info.get(p as usize)?;
4563 if info.effect || info.nested_query {
4564 return None;
4565 }
4566 if !info.calls {
4567 vars |= info.vars;
4568 continue;
4569 }
4570 let node = self.code.nodes.get(p as usize)?;
4571 match node {
4572 Node::Call { fun: g, .. } if *g != fun => {
4573 if self.open_funs.contains(g) {
4574 return None;
4575 }
4576 vars |= *self.fun_reads.get(g)?;
4577 }
4578 Node::Enabled { .. } | Node::Composition { .. } => return None,
4579 _ => {}
4580 }
4581 push_operands(node, &mut stack);
4582 }
4583 Some(vars)
4584 }
4585
4586 fn reenter(&mut self, fun: u32) -> u32 {
4589 if self.open_funs.contains(&fun) {
4590 self.reentered_funs.insert(fun);
4591 }
4592 fun
4593 }
4594
4595 fn open_fun(&mut self, fun: u32, mode: Mode, level: Level) {
4597 if mode == Mode::Primed {
4598 self.primed_funs.insert(fun);
4599 }
4600 if mode == Mode::Primed || self.reads_next(level) {
4601 self.next_funs.insert(fun);
4602 }
4603 self.open_funs.insert(fun);
4604 }
4605
4606 fn reads_next(&self, level: Level) -> bool {
4612 let at = if self.init_mode {
4613 Level::State
4614 } else {
4615 Level::Action
4616 };
4617 level >= at
4618 || self.substs.iter().any(|s| match &s.value {
4619 Ok(Arg::Expr { expr, .. }) => self.ir.node(*expr).level >= at,
4620 Ok(Arg::Op { level, .. }) => *level >= at,
4621 Err(p) => self.info.get(*p as usize).is_none_or(|i| i.primed != 0),
4622 })
4623 }
4624
4625 fn note_next_reads(&mut self, fun: u32, parts: &[P]) -> Result<(), Error> {
4630 let reentered = self.reentered_funs.remove(&fun);
4631 if self.next_funs.contains(&fun) || parts.iter().all(|&p| self.info[p as usize].primed == 0)
4632 {
4633 return Ok(());
4634 }
4635 if reentered {
4636 return Err(Error::unsupported(
4637 "a recursive definition below action level whose body reads the next state (M1 core)",
4638 ));
4639 }
4640 self.next_funs.insert(fun);
4641 Ok(())
4642 }
4643
4644 fn lib_ho(&mut self, op: StdOp, args: &[Arg], env: usize, mode: Mode) -> Result<P, Error> {
4648 if mode == Mode::Primed && op != StdOp::SequencesSelectSeq {
4649 return Err(Error::unsupported(format!(
4650 "{} under a prime (M1 core)",
4651 op.qualified_name()
4652 )));
4653 }
4654 let mut out = Vec::with_capacity(args.len());
4655 for (i, a) in args.iter().enumerate() {
4656 match (crate::stdlib::op_arity(op, i), a) {
4657 (Some(arity), _) => {
4658 let (params, body) = self.op_fn(a, env, arity)?;
4659 if mode == Mode::Primed {
4660 let info = &self.info[body as usize];
4667 if info.vars != 0
4668 || info.primed != 0
4669 || info.effect
4670 || info.calls
4671 || info.free.iter().any(|s| !params.contains(s))
4672 {
4673 return Err(Error::unsupported(
4674 "Sequences!SelectSeq under a prime with a state-dependent, captured or effectful predicate (M1 core)",
4675 ));
4676 }
4677 }
4678 if crate::stdlib::takes_op_value(op)
4679 && matches!(self.code.nodes.get(body as usize), Some(Node::Const(_)))
4680 {
4681 return Err(Error::unsupported(format!(
4682 "{} with an operator whose body is constant: TLC may fail to apply it",
4683 op.qualified_name()
4684 )));
4685 }
4686 out.push(LibArg::Op { params, body });
4687 }
4688 (None, Arg::Expr { expr, .. }) => {
4689 out.push(LibArg::Value(self.p(*expr, env, mode)?));
4690 }
4691 (None, Arg::Op { .. }) => {
4692 return Err(Error::unsupported(format!(
4693 "{} with an operator where a value is expected",
4694 op.qualified_name()
4695 )));
4696 }
4697 }
4698 }
4699 self.push(Node::LibHo(op, out.into()))
4700 }
4701
4702 fn lib_node(&self, op: StdOp, args: Vec<P>) -> Node {
4705 let repeatable_args = args.iter().all(|&p| {
4706 let info = &self.info[p as usize];
4707 !info.effect && !info.calls && info.free.is_empty()
4709 });
4710 Node::Lib {
4711 op,
4712 args: args.into(),
4713 repeatable_args,
4714 }
4715 }
4716
4717 fn std_apply(&mut self, op: StdOp, args: &[Arg], env: usize, mode: Mode) -> Result<P, Error> {
4718 if let Some(&t) = self.h.std_redirects.get(&op) {
4719 return if args.is_empty() {
4720 self.def_use(t, env, mode)
4721 } else {
4722 self.apply(&OpRef::Def(t), args, env, mode)
4723 };
4724 }
4725 if crate::stdlib::higher_order(op) {
4726 return self.lib_ho(op, args, env, mode);
4727 }
4728 if mode == Mode::Primed
4732 && op == StdOp::TlcTLCGet
4733 && !matches!(args, [Arg::Expr { expr, .. }]
4734 if matches!(&self.ir.node(*expr).expr, Expr::Num(_))
4735 || matches!(&self.ir.node(*expr).expr, Expr::Str(k) if k.as_ref() != "level"))
4736 {
4737 return Err(Error::unsupported(
4738 "TLCGet(\"level\") under a prime, which TLC evaluates at the successor's level (M1 core)",
4739 ));
4740 }
4741 let mut ps = Vec::with_capacity(args.len());
4742 for a in args {
4743 let Arg::Expr { expr, .. } = a else {
4744 return Err(Error::unsupported(format!(
4745 "{} with an operator argument",
4746 op.qualified_name()
4747 )));
4748 };
4749 ps.push(self.p(*expr, env, mode)?);
4750 }
4751 self.std_node(op, ps, Some(args))
4752 }
4753
4754 fn std_node(&mut self, op: StdOp, ps: Vec<P>, args: Option<&[Arg]>) -> Result<P, Error> {
4758 use StdOp as S;
4759 let arg = |i: usize| {
4760 ps.get(i)
4761 .copied()
4762 .ok_or_else(|| Error::internal("missing argument"))
4763 };
4764 let arith = |o: Arith| -> Result<Node, Error> { Ok(Node::Arith(o, arg(0)?, arg(1)?)) };
4765 let cmp = |o: Cmp| -> Result<Node, Error> { Ok(Node::Cmp(o, arg(0)?, arg(1)?)) };
4766 let n = match op {
4767 S::NaturalsPlus | S::IntegersPlus => arith(Arith::Add)?,
4768 S::NaturalsMinus | S::IntegersMinus => arith(Arith::Sub)?,
4769 S::NaturalsTimes | S::IntegersTimes => arith(Arith::Mul)?,
4770 S::IntegersDiv => arith(Arith::Div)?,
4771 S::NaturalsDiv => arith(Arith::DivNaturals)?,
4772 S::NaturalsMod | S::IntegersMod => arith(Arith::Mod)?,
4773 S::NaturalsExpt | S::IntegersExpt => arith(Arith::Pow)?,
4774 S::NaturalsLt | S::IntegersLt => cmp(Cmp::Lt)?,
4775 S::NaturalsLeq | S::IntegersLeq => cmp(Cmp::Le)?,
4776 S::NaturalsGt | S::IntegersGt => cmp(Cmp::Gt)?,
4777 S::NaturalsGeq | S::IntegersGeq => cmp(Cmp::Ge)?,
4778 S::NaturalsDotDot | S::IntegersDotDot => Node::Range(arg(0)?, arg(1)?),
4779 S::IntegersNeg => Node::Neg(arg(0)?),
4780 S::NaturalsNat | S::IntegersNat => {
4781 let h = self.m.heap.symbolic(Kind::Nat, 0, &[]);
4782 let h = self.m.heap.intern_const(h)?;
4783 Node::Const(h)
4784 }
4785 S::IntegersInt => {
4786 let h = self.m.heap.symbolic(Kind::Int, 0, &[]);
4787 let h = self.m.heap.intern_const(h)?;
4788 Node::Const(h)
4789 }
4790 S::SequencesLen => Node::Std(StdFn::Len, ps.into()),
4791 S::SequencesHead => Node::Std(StdFn::Head, ps.into()),
4792 S::SequencesTail => Node::Std(StdFn::Tail, ps.into()),
4793 S::SequencesAppend => Node::Std(StdFn::Append, ps.into()),
4794 S::SequencesConcat => Node::Std(StdFn::Concat, ps.into()),
4795 S::SequencesSubSeq => Node::Std(StdFn::SubSeq, ps.into()),
4796 S::SequencesSeq => Node::Std(StdFn::Seq, ps.into()),
4797 S::FiniteSetsCardinality => Node::Std(StdFn::Cardinality, ps.into()),
4798 S::FiniteSetsIsFiniteSet => Node::Std(StdFn::IsFiniteSet, ps.into()),
4799 S::BagsEmptyBag => Node::Std(StdFn::EmptyBag, ps.into()),
4800 S::BagsSetToBag => Node::Std(StdFn::SetToBag, ps.into()),
4801 S::BagsBagToSet => Node::Std(StdFn::BagToSet, ps.into()),
4802 S::BagsBagIn => Node::Std(StdFn::BagIn, ps.into()),
4803 S::BagsCopiesIn => Node::Std(StdFn::CopiesIn, ps.into()),
4804 S::TlcTLCGet => {
4805 let lit = match args {
4809 Some([Arg::Expr { expr, .. }]) => match &self.ir.node(*expr).expr {
4810 Expr::Str(k) => Some(k.as_ref() != "level"),
4811 Expr::Num(_) => Some(true),
4812 _ => None,
4813 },
4814 _ => None,
4815 };
4816 let Some(register) = lit else {
4817 return Err(Error::unsupported(
4818 "TLCGet of an expression other than a literal, whose errors TLC reports inside TLCGet (M1 core)",
4819 ));
4820 };
4821 self.effects.registers |= register;
4822 self.effects.level |= !register;
4823 self.lib_node(op, ps)
4824 }
4825 other if crate::stdlib::implements(other) => self.lib_node(other, ps),
4826 other => {
4827 return Err(Error::unsupported(format!(
4828 "the standard operator {} (M0 core)",
4829 other.qualified_name()
4830 )));
4831 }
4832 };
4833 self.push(n)
4834 }
4835
4836 fn union_of_one_constructor(&self, args: &[ExprId]) -> Option<ExprId> {
4842 let a = *args.first()?;
4843 let Expr::SetEnum(items) = &self.ir.node(a).expr else {
4844 return None;
4845 };
4846 let [item] = items.as_ref() else {
4847 return None;
4848 };
4849 matches!(
4850 &self.ir.node(*item).expr,
4851 Expr::FcnSet { .. }
4852 | Expr::RecordSet(_)
4853 | Expr::Cartesian(_)
4854 | Expr::Builtin {
4855 op: BuiltinOp::PowerSet | BuiltinOp::Times,
4856 ..
4857 }
4858 )
4859 .then_some(*item)
4860 }
4861
4862 #[allow(clippy::too_many_lines, reason = "one arm per built-in operator")]
4863 fn builtin(
4864 &mut self,
4865 op: BuiltinOp,
4866 args: &[ExprId],
4867 env: usize,
4868 mode: Mode,
4869 ) -> Result<P, Error> {
4870 use BuiltinOp as B;
4871 match op {
4872 B::Prime => {
4873 let a = *args
4874 .first()
4875 .ok_or_else(|| Error::internal("prime without operand"))?;
4876 if mode == Mode::Primed || self.init_mode {
4877 return Err(Error::unsupported(
4878 "a doubly primed expression or a prime in Init",
4879 ));
4880 }
4881 return self.p(a, env, Mode::Primed);
4882 }
4883 B::Unchanged => {
4884 let a = *args
4885 .first()
4886 .ok_or_else(|| Error::internal("UNCHANGED without operand"))?;
4887 return self.unchanged_value(a, env, mode);
4888 }
4889 B::Boolean => {
4890 let mut v = vec![Handle::FALSE, Handle::TRUE];
4891 let h = self.m.heap.set_from(&mut v);
4892 let h = self.m.heap.intern_const(h)?;
4893 return self.konst(h);
4894 }
4895 B::BigUnion => {
4896 if let Some(item) = self.union_of_one_constructor(args) {
4897 return self.p(item, env, mode);
4898 }
4899 }
4900 B::String => return Err(Error::unsupported("STRING (M0 core)")),
4901 B::Enabled => return self.enabled(args.first().copied(), None, env, mode),
4902 B::Cdot => {
4903 let [a, b] = args else {
4904 return Err(Error::internal("action composition without two operands"));
4905 };
4906 return self.composition_value(*a, *b, env, mode);
4907 }
4908 B::Always | B::Eventually | B::LeadsTo | B::WhilePlus => {
4909 return Err(Error::unsupported(
4910 "a temporal operator in a state or action role",
4911 ));
4912 }
4913 _ => {}
4914 }
4915 let ps = self.ps(args, env, mode)?;
4916 let a = |i: usize| {
4917 ps.get(i)
4918 .copied()
4919 .ok_or_else(|| Error::internal("missing operand"))
4920 };
4921 let n = match op {
4922 B::Cup | B::Cap | B::SetMinus => {
4923 let o = match op {
4924 B::Cup => SetOp::Cup,
4925 B::Cap => SetOp::Cap,
4926 _ => SetOp::Minus,
4927 };
4928 return self.push_lazy(Node::SetBin(o, a(0)?, a(1)?));
4929 }
4930 B::In | B::NotIn => {
4931 let (x, set) = (a(0)?, a(1)?);
4932 if self.lazy_set(set) {
4933 return self.push(Node::InLazy {
4934 elem: x,
4935 set,
4936 neg: op == B::NotIn,
4937 });
4938 }
4939 if op == B::In {
4940 Node::In(x, set)
4941 } else {
4942 Node::NotIn(x, set)
4943 }
4944 }
4945 B::Eq => Node::Eq(a(0)?, a(1)?),
4946 B::Neq => Node::Neq(a(0)?, a(1)?),
4947 B::Subseteq => Node::Subseteq(a(0)?, a(1)?),
4948 B::PowerSet => Node::Powerset(a(0)?),
4949 B::BigUnion => Node::BigUnion(a(0)?),
4950 B::Domain => {
4951 let f = a(0)?;
4952 if let Some(d) = self.lambda_domain(f)? {
4953 return Ok(d);
4954 }
4955 Node::Domain(f)
4956 }
4957 B::Times => Node::Product(ps.clone().into()),
4958 B::Not => Node::Not(a(0)?),
4959 B::And => Node::And(ps.clone().into()),
4960 B::Or => Node::Or(ps.clone().into()),
4961 B::Implies => Node::Implies(a(0)?, a(1)?),
4962 B::Equiv => Node::Equiv(a(0)?, a(1)?),
4963 _ => {
4964 return Err(Error::unsupported(format!(
4965 "the built-in {} (M0 core)",
4966 op.sany_name()
4967 )));
4968 }
4969 };
4970 self.push(n)
4971 }
4972
4973 fn guard(&mut self, p: P) -> Result<G, Error> {
4978 let name = format!("{} guard", self.role_name);
4979 let p = self.site(name, p)?.unwrap_or(p);
4980 Ok(self.gpush(GNode::Guard(p)))
4981 }
4982
4983 fn guard_expr(&mut self, e: ExprId, env: usize) -> Result<G, Error> {
4984 let p = self.p(e, env, Mode::Plain)?;
4985 self.guard(p)
4986 }
4987
4988 fn g(&mut self, e: ExprId, env: usize) -> Result<G, Error> {
4989 if self.code.source_map.is_none() {
4990 return self.g_inner(e, env);
4991 }
4992 let previous = self.debug_current;
4993 self.debug_current = self.debug_context(e, env)?;
4994 let result = self.g_inner(e, env);
4995 self.debug_current = previous;
4996 result
4997 }
4998
4999 #[allow(
5000 clippy::too_many_lines,
5001 clippy::many_single_char_names,
5002 reason = "one arm per generator rule"
5003 )]
5004 fn g_inner(&mut self, e: ExprId, env: usize) -> Result<G, Error> {
5005 self.leaf += 1;
5008 let expr = &self.ir.node(e).expr;
5009 match expr {
5010 Expr::Cdot(a, b) => {
5011 let (first, then, _) = self.composition_parts(*a, *b, env)?;
5012 Ok(self.composition_gen(first, then))
5013 }
5014 Expr::Builtin {
5015 op: BuiltinOp::Cdot,
5016 args,
5017 } if args.len() == 2 => {
5018 let (first, then, _) = self.composition_parts(args[0], args[1], env)?;
5019 Ok(self.composition_gen(first, then))
5020 }
5021 Expr::Junction { kind, items, .. } => match kind {
5022 JunctionKind::And => {
5023 let mut out = Vec::with_capacity(items.len());
5024 for &i in items {
5025 let g = self.g(i, env)?;
5026 let p = self.p(i, env, Mode::Plain)?;
5027 out.push((g, p));
5028 }
5029 Ok(self.gpush(GNode::Conj(out.into())))
5030 }
5031 JunctionKind::Or => {
5032 let mut out = Vec::with_capacity(items.len());
5033 for &i in items {
5034 out.push(self.g(i, env)?);
5035 }
5036 Ok(self.gpush(GNode::Disj(out.into())))
5037 }
5038 },
5039 Expr::Quant {
5040 kind: kind @ (QuantKind::Exists | QuantKind::Forall),
5041 bounds,
5042 body,
5043 } if bounds.iter().all(|b| b.domain.is_some()) => {
5044 let exists = *kind == QuantKind::Exists;
5045 let body = *body;
5046 let (binds, saved) = self.binds(bounds, env, Mode::Plain)?;
5047 let r = (|| {
5048 let bg = self.g(body, env)?;
5049 let bp = self.p(body, env, Mode::Plain)?;
5050 Ok((bg, bp))
5051 })();
5052 self.unbind(saved);
5053 let (bg, bp) = r?;
5054 let binds: Box<[Bind]> = binds.into();
5055 Ok(self.gpush(if exists {
5056 GNode::Exists {
5057 binds,
5058 body: bg,
5059 body_p: bp,
5060 }
5061 } else {
5062 GNode::Forall {
5063 binds,
5064 body: bg,
5065 body_p: bp,
5066 }
5067 }))
5068 }
5069 Expr::If { cond, then, other } => {
5070 let c = self.p(*cond, env, Mode::Plain)?;
5071 let t = self.g(*then, env)?;
5072 let o = self.g(*other, env)?;
5073 Ok(self.gpush(GNode::If {
5074 cond: c,
5075 then: t,
5076 other: o,
5077 }))
5078 }
5079 Expr::Case { arms, other } => {
5080 let mut out = Vec::with_capacity(arms.len());
5081 for a in arms {
5082 let p = self.p(a.guard, env, Mode::Plain)?;
5083 let g = self.g(a.value, env)?;
5084 out.push((p, g));
5085 }
5086 let o = match other {
5087 Some(o) => Some(self.g(*o, env)?),
5088 None => None,
5089 };
5090 Ok(self.gpush(GNode::Case {
5091 arms: out.into(),
5092 other: o,
5093 }))
5094 }
5095 Expr::Implies(a, b) => {
5096 let l = self.p(*a, env, Mode::Plain)?;
5097 let r = self.g(*b, env)?;
5098 Ok(self.gpush(GNode::Implies { lhs: l, rhs: r }))
5099 }
5100 Expr::Builtin {
5101 op: BuiltinOp::Eq,
5102 args,
5103 } if args.len() == 2 => {
5104 if let Some(var) = self.target(args[0], env, false)? {
5105 let rhs = self.p(args[1], env, Mode::Plain)?;
5106 return Ok(self.gpush(GNode::Assign { var, rhs }));
5107 }
5108 self.guard_expr(e, env)
5109 }
5110 Expr::Builtin {
5111 op: BuiltinOp::In,
5112 args,
5113 } if args.len() == 2 => {
5114 if let Some(var) = self.target(args[0], env, false)? {
5115 let set = self.p(args[1], env, Mode::Plain)?;
5118 let set = self.unspec(set);
5119 if let Some(raw) = self.raw_plan(args[1], env)? {
5122 return Ok(self.gpush(GNode::AssignInRaw { var, set, raw }));
5123 }
5124 return Ok(self.gpush(GNode::AssignIn { var, set }));
5125 }
5126 self.guard_expr(e, env)
5127 }
5128 Expr::Builtin {
5129 op: BuiltinOp::Subseteq,
5130 args,
5131 } if args.len() == 2 => {
5132 if let Some(var) = self.target(args[0], env, false)? {
5135 let base = self.p(args[1], env, Mode::Plain)?;
5136 let set = self.push(Node::Powerset(base))?;
5137 return Ok(self.gpush(GNode::AssignIn { var, set }));
5138 }
5139 self.guard_expr(e, env)
5140 }
5141 Expr::Builtin {
5142 op: BuiltinOp::Unchanged,
5143 args,
5144 } if args.len() == 1 => {
5145 if self.init_mode {
5146 return self.guard_expr(e, env);
5147 }
5148 let mut items = Vec::new();
5149 self.unchanged_items(args[0], env, &mut items)?;
5150 Ok(self.gpush(GNode::Unchanged(items.into())))
5151 }
5152 Expr::Unchanged(a) => {
5153 if self.init_mode {
5154 return self.guard_expr(e, env);
5155 }
5156 let mut items = Vec::new();
5157 self.unchanged_items(*a, env, &mut items)?;
5158 Ok(self.gpush(GNode::Unchanged(items.into())))
5159 }
5160 Expr::StepBox { action, sub } => {
5161 if self.init_mode {
5162 return self.guard_expr(e, env);
5163 }
5164 let a = self.g(*action, env)?;
5165 let mut items = Vec::new();
5166 self.unchanged_items(*sub, env, &mut items)?;
5167 Ok(self.gpush(GNode::StepBox {
5168 action: a,
5169 vars: items.into(),
5170 }))
5171 }
5172 Expr::StepAngle { action, sub } => {
5173 if self.init_mode {
5174 return self.guard_expr(e, env);
5175 }
5176 let (action, sub) = (*action, *sub);
5177 let a = self.g(action, env)?;
5178 let same = self.changed_test(sub, env)?;
5179 Ok(self.gpush(GNode::StepAngle { action: a, same }))
5180 }
5181 Expr::FcnApply { fcn, arg } => {
5182 let (fcn, arg) = (*fcn, *arg);
5183 let Some((lambda, lenv)) = self.fcn_lambda(fcn, env, 0)? else {
5184 if self.rec_target(fcn, env, Mode::Plain)?.is_some() {
5190 self.recursive_action_predicate = true;
5191 }
5192 return self.guard_expr(e, env);
5193 };
5194 let Expr::FcnCons { bounds, body } = self.ir.node(lambda).expr.clone() else {
5195 return self.guard_expr(e, env);
5196 };
5197 if bounds.iter().any(|b| b.domain.is_none()) {
5198 return self.guard_expr(e, env);
5199 }
5200 let (binds, saved) = self.binds(&bounds, lenv, Mode::Plain)?;
5201 let r = (|| {
5202 let a = self.p(arg, env, Mode::Plain)?;
5203 let b = self.g(body, lenv)?;
5204 Ok((a, b))
5205 })();
5206 self.unbind(saved);
5207 let (a, b) = r?;
5208 Ok(self.gpush(GNode::FcnAction {
5209 binds: binds.into(),
5210 arg: a,
5211 body: b,
5212 }))
5213 }
5214 Expr::Let { defs, body } => {
5215 let body = *body;
5216 let defs = defs.clone();
5217 let (g, reset) = self.let_scope(&defs, env, |c| c.g(body, env))?;
5218 if reset.is_empty() {
5219 Ok(g)
5220 } else {
5221 Ok(self.gpush(GNode::Scope {
5222 reset: reset.into(),
5223 body: g,
5224 }))
5225 }
5226 }
5227 Expr::Selected(a) | Expr::Label { body: a, .. } => self.g(*a, env),
5228 Expr::Subst { bindings, body } => {
5229 let (bindings, body) = (bindings.clone(), *body);
5230 let (g, reset) =
5231 self.subst_scope(&bindings, env, Mode::Plain, |c| c.g(body, env))?;
5232 if reset.is_empty() {
5233 Ok(g)
5234 } else {
5235 Ok(self.gpush(GNode::Scope {
5236 reset: reset.into(),
5237 body: g,
5238 }))
5239 }
5240 }
5241 Expr::SubstRef {
5244 decl,
5245 primed: false,
5246 } if !self.subst_is_value(*decl) => match self.subst_expr(*decl) {
5247 Some(r) => {
5248 let (expr, aenv, depth) = r?;
5249 self.stats.by_name += 1;
5250 self.outside(depth, |c| c.g(expr, aenv))
5251 }
5252 None => self.guard_expr(e, env),
5253 },
5254 Expr::Def(d) => {
5255 let d = self.redirect(*d);
5256 let def = self.ir.def(d);
5257 if self.has_startup_value(d)
5258 || def.std.is_some()
5259 || def.recursive
5260 || !def.params.is_empty()
5261 || matches!(def.scope, DefScope::LetValue { .. })
5262 {
5263 return self.guard_expr(e, env);
5264 }
5265 let parent = self.lexical_parent(d, env)?;
5266 let inner = self.new_env(d, parent);
5267 self.g(def.body, inner)
5268 }
5269 Expr::Apply {
5270 callee: OpRef::Def(d),
5271 args,
5272 } => {
5273 let d = self.redirect(*d);
5274 let def = self.ir.def(d);
5275 if def.std.is_some() || def.recursive || args.is_empty() {
5276 if args.is_empty()
5277 && def.std.is_none()
5278 && !def.recursive
5279 && !self.has_startup_value(d)
5280 {
5281 let parent = self.lexical_parent(d, env)?;
5282 let inner = self.new_env(d, parent);
5283 return self.g(def.body, inner);
5284 }
5285 return self.guard_expr(e, env);
5286 }
5287 self.g_inline(d, args, env, env)
5288 }
5289 Expr::Apply {
5295 callee: OpRef::Const(c),
5296 args,
5297 } => self.g_apply_op(&OpRef::Const(*c), args, e, env, env),
5298 Expr::Apply {
5299 callee: OpRef::Subst(decl),
5300 args,
5301 } => {
5302 let op = self.subst_op(*decl)?;
5303 self.g_apply_op(&op, args, e, env, env)
5304 }
5305 Expr::Apply {
5306 callee: OpRef::Param(r),
5307 args,
5308 } => {
5309 let (op, aenv, enclosing) = self.resolve_param(*r, env)?;
5310 if enclosing {
5311 return Err(Error::unsupported(
5312 "an enclosing operator parameter used as an action inside a recursive function (M1 core)",
5313 ));
5314 }
5315 self.g_apply_op(&op, args, e, env, aenv)
5316 }
5317 Expr::Local(r) => {
5318 let fe = self.frame_env(env, r.up)?;
5319 match self.envs[fe].slots.get(r.slot.index()).cloned() {
5320 Some(Sb::Arg {
5321 expr, env: aenv, ..
5322 }) => {
5323 self.stats.by_name += 1;
5324 self.g(expr, aenv)
5325 }
5326 Some(Sb::LetVal { def, env: lenv, .. }) => {
5327 let body = self.ir.def(def).body;
5328 self.g(body, lenv)
5329 }
5330 _ => self.guard_expr(e, env),
5331 }
5332 }
5333 _ => self.guard_expr(e, env),
5334 }
5335 }
5336
5337 fn target(&mut self, e: ExprId, env: usize, under_prime: bool) -> Result<Option<u16>, Error> {
5340 #[allow(clippy::cast_possible_truncation, reason = "at most 64 variables")]
5341 match &self.ir.node(e).expr {
5342 Expr::Var { var, primed } => {
5343 let ok = if self.init_mode {
5344 !*primed && !under_prime
5345 } else {
5346 *primed != under_prime
5347 };
5348 Ok(ok.then_some(var.index() as u16))
5349 }
5350 Expr::Prime(a) if !self.init_mode && !under_prime => self.target(*a, env, true),
5351 Expr::Builtin {
5352 op: BuiltinOp::Prime,
5353 args,
5354 } if !self.init_mode && !under_prime && args.len() == 1 => {
5355 self.target(args[0], env, true)
5356 }
5357 Expr::Label { body: a, .. } | Expr::Selected(a) => self.target(*a, env, under_prime),
5358 Expr::SubstRef { decl, primed } => {
5361 let (decl, primed) = (*decl, *primed);
5362 if primed && under_prime {
5363 return Ok(None);
5364 }
5365 let under = under_prime || primed;
5366 if self.subst_is_value(decl) {
5367 return Ok(None);
5368 }
5369 if let Some(r) = self.subst_expr(decl) {
5370 let (expr, aenv, depth) = r?;
5371 return self.outside(depth, |c| c.target(expr, aenv, under));
5372 }
5373 let Some(v) = self.ir.decl(decl).var else {
5374 return Ok(None);
5375 };
5376 let ok = if self.init_mode { !under } else { under };
5377 Ok(ok.then_some(v.index() as u16))
5378 }
5379 Expr::Local(r) => {
5380 let fe = self.frame_env(env, r.up)?;
5381 match self.envs[fe].slots.get(r.slot.index()).cloned() {
5382 Some(Sb::Arg {
5383 expr, env: aenv, ..
5384 }) => self.target(expr, aenv, under_prime),
5385 Some(Sb::LetVal { def, env: lenv, .. }) => {
5386 let body = self.ir.def(def).body;
5387 self.target(body, lenv, under_prime)
5388 }
5389 _ => Ok(None),
5390 }
5391 }
5392 Expr::Def(d) => {
5393 let d = self.redirect(*d);
5394 let def = self.ir.def(d);
5395 if self.has_startup_value(d)
5396 || def.std.is_some()
5397 || !def.params.is_empty()
5398 || def.recursive
5399 {
5400 return Ok(None);
5401 }
5402 let parent = self.lexical_parent(d, env)?;
5403 let inner = self.new_env(d, parent);
5404 self.target(def.body, inner, under_prime)
5405 }
5406 _ => Ok(None),
5407 }
5408 }
5409}