1use std::sync::Arc;
5
6use crate::Error;
7use crate::compare;
8use crate::handle::Handle;
9use crate::heap::{Cursor, Heap};
10use crate::int::{IntMode, IntOp};
11use crate::memo::{MAX_KEY, Memo};
12use crate::node::Kind;
13use crate::opts::Opts;
14use crate::plan::{Arith, Bind, Cmp, Code, LibArg, Node, P, Quant, SetOp, StdFn, Update};
15use crate::store::Store;
16
17#[path = "eval_product.rs"]
18mod product;
19#[path = "eval_work.rs"]
20mod work;
21
22const MAX_CALL_DEPTH: usize = 64;
25
26pub const WORK_POLL_UNITS: u64 = 32;
33
34#[derive(Clone, Copy, Debug, Default)]
36pub struct EvalStats {
37 pub forced: u64,
39 pub cached: u64,
41 pub transient_thunks: u64,
44}
45
46pub trait WorkControl: std::fmt::Debug + Send + Sync {
49 fn proceed(&self) -> bool;
51}
52
53#[derive(Debug)]
55pub struct Machine {
56 pub heap: Heap,
58 pub frame: Vec<Handle>,
60 pub base: usize,
62 pub s0: Vec<Handle>,
64 pub s1: Vec<Handle>,
66 pub assigned: usize,
68 pub opts: Opts,
70 pub memo: Memo,
72 pub stats: EvalStats,
74 pub warn: bool,
77 pub warnings: Vec<(u16, u32)>,
81 pub printed: Vec<String>,
84 output_limits: Option<(usize, usize)>,
85 output_used: (usize, usize),
86 output_failure: Option<&'static str>,
87 pub(crate) checker_access: CheckerAccess,
88 pub draw: Option<Box<dyn crate::random::DrawStream>>,
91 pub draws: u64,
94 pub level: i64,
98 pub(crate) conts: Vec<crate::generate::ContNode>,
99 pub(crate) cvals: Vec<Handle>,
100 pub(crate) saved: Vec<Handle>,
101 scratch: Vec<Vec<Handle>>,
102 transient_slots: Vec<usize>,
106 depth: usize,
107 pub(crate) fuel: u64,
111 refuse_unrecorded_warnings: bool,
115 proven_s0: Vec<Handle>,
119 proven_s1: Vec<Handle>,
120 proven: Vec<Handle>,
121 work_control: Option<Arc<dyn WorkControl>>,
122 work_countdown: u64,
125 bounded_countdown: u64,
127 pub(crate) debugger: Option<Arc<dyn crate::debug::Observer>>,
128 pub(crate) calls: Option<CallCache>,
131 pub(crate) transient_bound: usize,
135}
136
137#[derive(Debug, Clone, Copy, PartialEq, Eq)]
139pub(crate) enum CheckerAccess {
140 Full,
142 Level,
144 Denied,
146}
147
148#[derive(Debug, Default)]
160pub(crate) struct CallCache {
161 revision: (u64, u64),
162 results: std::collections::HashMap<Box<[u64]>, Handle>,
163 key: Vec<u64>,
164 pub(crate) hits: u64,
166}
167
168const CALL_CACHE_ENTRIES: usize = 1 << 16;
170
171fn eval_err(what: &str) -> Error {
172 Error::eval(what)
173}
174
175fn general(what: &str) -> Error {
179 Error::eval_class(crate::TlcClass::GENERAL, what)
180}
181
182fn eval_exc(code: u32, what: &str) -> Error {
184 Error::eval_class(crate::TlcClass::eval_exception(code), what)
185}
186
187pub(crate) fn cardinality_error() -> Error {
191 eval_exc(2181, "Attempted to compute cardinality of the value")
192}
193
194fn one_arg(op: &str, what: &str) -> Error {
196 eval_exc(
197 2283,
198 &format!("The argument of {op} should be a {what}, but instead it is not"),
199 )
200}
201
202fn speculative(e: Error) -> Error {
205 if e.kind() == crate::ErrorKind::Eval {
206 Error::unsupported(format!(
207 "an evaluation error in an expression TLC evaluates lazily, where it may not fail: {}",
208 e.message()
209 ))
210 } else {
211 e
212 }
213}
214
215fn int_of(h: Handle) -> Result<i64, Error> {
216 h.as_int().ok_or_else(|| eval_err("expected an integer"))
217}
218
219fn bool_of(h: Handle) -> Result<bool, Error> {
220 h.as_bool().ok_or_else(|| eval_err("expected a boolean"))
221}
222
223fn mk_int(v: i64) -> Result<Handle, Error> {
224 Handle::int(v).ok_or_else(|| Error::unsupported("integer outside the M0 core's 61-bit range"))
225}
226
227impl Machine {
228 #[must_use]
230 pub fn new(store: Arc<Store>, nvars: usize, opts: Opts, mut memo: Memo) -> Self {
231 memo.set_cap(opts.memo_cap);
232 memo.reserve_members(opts.memo && store.semantics().tlc_comparisons);
233 memo.reserve_member_index(opts.member_index && !store.semantics().tlc_comparisons);
234 Self {
235 heap: Heap::new(store, !opts.arena, !opts.delta_hash),
236 frame: Vec::new(),
237 base: 0,
238 s0: vec![Handle::EMPTY; nvars],
239 s1: vec![Handle::EMPTY; nvars],
240 assigned: 0,
241 opts,
242 memo,
243 stats: EvalStats::default(),
244 warn: true,
245 warnings: Vec::new(),
246 printed: Vec::new(),
247 output_limits: None,
248 output_used: (0, 0),
249 output_failure: None,
250 checker_access: CheckerAccess::Full,
251 draw: None,
252 draws: 0,
253 level: 0,
254 conts: Vec::new(),
255 cvals: Vec::new(),
256 saved: Vec::new(),
257 scratch: Vec::new(),
258 transient_slots: Vec::new(),
259 depth: 0,
260 fuel: u64::MAX,
261 refuse_unrecorded_warnings: false,
262 proven_s0: Vec::new(),
263 proven_s1: Vec::new(),
264 proven: Vec::new(),
265 work_control: None,
266 work_countdown: 0,
267 bounded_countdown: 0,
268 debugger: None,
269 calls: None,
270 transient_bound: usize::MAX,
271 }
272 }
273
274 pub fn set_fuel(&mut self, units: u64) {
283 self.disarm_inline_charge();
284 self.fuel = units;
285 self.memo.reserve_member_index(
286 units == u64::MAX
287 && self.opts.member_index
288 && !self.heap.store.semantics().tlc_comparisons,
289 );
290 }
291
292 #[must_use]
301 pub const fn fuel_exhausted(&self) -> bool {
302 self.fuel == 0
303 }
304
305 pub fn set_refuse_unrecorded_warnings(&mut self, enabled: bool) {
318 self.refuse_unrecorded_warnings = enabled;
319 }
320
321 pub fn set_proven_materialized(
346 &mut self,
347 s0: &[Handle],
348 s1: &[Handle],
349 others: impl IntoIterator<Item = Handle>,
350 ) {
351 let keep = |h: &Handle| {
352 if h.is_persistent() && h.is_compound() {
353 *h
354 } else {
355 Handle::EMPTY
356 }
357 };
358 self.proven_s0.clear();
359 self.proven_s0.extend(s0.iter().map(keep));
360 self.proven_s1.clear();
361 self.proven_s1.extend(s1.iter().map(keep));
362 self.proven.clear();
363 self.proven.extend(
364 others
365 .into_iter()
366 .filter(|h| h.is_persistent() && h.is_compound()),
367 );
368 }
369
370 fn proven(&self, h: Handle) -> bool {
373 h.is_compound()
374 && (self.proven_s0.contains(&h)
375 || self.proven_s1.contains(&h)
376 || self.proven.contains(&h))
377 }
378
379 #[inline]
382 fn proven_at(&self, v: usize, primed: bool, h: Handle) -> bool {
383 let row = if primed {
384 &self.proven_s1
385 } else {
386 &self.proven_s0
387 };
388 (h.is_compound() && row.get(v) == Some(&h)) || self.proven(h)
389 }
390
391 pub fn set_work_control(&mut self, control: Option<Arc<dyn WorkControl>>) {
400 self.heap.set_work_control(control.clone());
401 self.work_control = control;
402 self.work_countdown = 0;
403 self.bounded_countdown = 0;
404 }
405
406 pub fn set_debugger(&mut self, observer: Option<Arc<dyn crate::debug::Observer>>) {
409 self.debugger = observer;
410 }
411
412 pub fn with_deferred_reclamation<T>(&mut self, work: impl FnOnce(&mut Self) -> T) -> T {
428 let previous = std::mem::replace(&mut self.heap.defer_reclamation, true);
429 let result = work(self);
430 self.heap.defer_reclamation = previous;
431 result
432 }
433
434 pub fn deny_checker_access(&mut self) {
437 self.checker_access = CheckerAccess::Denied;
438 }
439
440 pub fn allow_finite_level(&mut self) {
444 if self.checker_access == CheckerAccess::Denied {
445 self.checker_access = CheckerAccess::Level;
446 }
447 }
448
449 fn check_finite_access(&self, op: dive_ir::StdOp) -> Result<(), Error> {
450 let allowed = match self.checker_access {
451 CheckerAccess::Full => true,
452 CheckerAccess::Level => op == dive_ir::StdOp::TlcTLCGet,
453 CheckerAccess::Denied => false,
454 };
455 if !allowed
456 && op.impure()
457 && !matches!(op, dive_ir::StdOp::TlcPrint | dive_ir::StdOp::TlcPrintT)
458 {
459 return Err(Error::unsupported(format!(
460 "{}: native finite mode runtime effect is unsupported",
461 op.qualified_name()
462 )));
463 }
464 Ok(())
465 }
466
467 pub fn set_output_limits(&mut self, events: usize, bytes: usize) {
470 self.output_limits = Some((events, bytes));
471 }
472
473 #[must_use]
475 pub const fn output_failure(&self) -> Option<&'static str> {
476 self.output_failure
477 }
478
479 pub(crate) fn print(&mut self, text: String) -> Result<(), Error> {
480 if let Some((events, bytes)) = self.output_limits {
481 let total = self.output_used.1.checked_add(text.len());
482 let failure = if self.output_used.0 >= events {
483 Some("simulation output event bound")
484 } else if total.is_none_or(|total| total > bytes) {
485 Some("simulation output byte bound")
486 } else {
487 None
488 };
489 if let Some(failure) = failure {
490 self.output_failure.get_or_insert(failure);
491 return Err(Error::unsupported(failure));
492 }
493 self.output_used = (self.output_used.0 + 1, total.unwrap_or(bytes));
494 }
495 self.printed.push(text);
496 Ok(())
497 }
498
499 #[inline]
506 pub(crate) fn charge(&mut self, n: usize) -> Result<(), Error> {
507 let units = (n as u64).max(1);
508 if units < self.work_countdown {
509 self.work_countdown -= units;
510 return Ok(());
511 }
512 self.charge_slow(units, n)
513 }
514
515 #[inline(never)]
523 fn charge_slow(&mut self, units: u64, n: usize) -> Result<(), Error> {
524 let left = self.work_countdown.max(self.bounded_countdown);
525 self.work_countdown = 0;
526 self.bounded_countdown = 0;
527 if units < left {
528 self.bounded_countdown = left - units;
529 } else if self
530 .work_control
531 .as_ref()
532 .is_some_and(|control| !control.proceed())
533 {
534 self.heap.mark_work_interrupted();
535 return Err(Error::stop());
536 } else {
537 self.bounded_countdown = WORK_POLL_UNITS;
538 }
539 if self.transient_bound != usize::MAX && self.heap.arena.footprint() > self.transient_bound
540 {
541 return Err(Error::unsupported("the start-up evaluation memory bound"));
542 }
543 if self.fuel == u64::MAX {
544 if self.transient_bound == usize::MAX {
545 self.work_countdown = std::mem::take(&mut self.bounded_countdown);
546 }
547 return Ok(());
548 }
549 let n = n as u64;
550 if self.fuel < n {
551 self.fuel = 0;
552 return Err(Error::unsupported("the constant-folding budget"));
553 }
554 self.fuel -= n;
555 Ok(())
556 }
557
558 fn disarm_inline_charge(&mut self) {
561 self.bounded_countdown = self
562 .bounded_countdown
563 .max(std::mem::take(&mut self.work_countdown));
564 }
565
566 pub(crate) fn set_transient_bound(&mut self, bytes: usize) {
569 self.disarm_inline_charge();
570 self.transient_bound = bytes;
571 }
572
573 fn take_scratch(&mut self) -> Vec<Handle> {
574 let mut v = self.scratch.pop().unwrap_or_default();
575 v.clear();
576 v
577 }
578
579 fn give_scratch(&mut self, v: Vec<Handle>) {
580 self.scratch.push(v);
581 }
582
583 pub fn enter(&mut self, size: u32) -> usize {
585 let old = self.base;
586 self.base = self.frame.len();
587 self.frame.resize(self.base + size as usize, Handle::EMPTY);
588 old
589 }
590
591 pub fn leave(&mut self, old: usize) {
593 self.frame.truncate(self.base);
594 self.base = old;
595 if self.frame.is_empty() {
596 self.transient_slots.clear();
598 }
599 }
600
601 #[must_use]
605 pub fn thunk_mark(&self) -> usize {
606 self.transient_slots.len()
607 }
608
609 pub fn thunks_released(&mut self, since: usize) -> bool {
617 let len = self.transient_slots.len();
618 if since >= len {
619 return true;
620 }
621 let live = self.frame.len();
622 let mut kept = since;
623 let mut i = since;
624 while i < len {
625 let slot = self.transient_slots[i];
626 if slot < live {
627 self.transient_slots[kept] = slot;
628 kept += 1;
629 }
630 i += 1;
631 }
632 self.transient_slots.truncate(kept);
633 kept == since
634 }
635
636 #[inline]
637 pub(crate) fn slot(&self, s: u32) -> Handle {
638 self.frame
639 .get(self.base + s as usize)
640 .copied()
641 .unwrap_or(Handle::EMPTY)
642 }
643
644 #[inline]
645 pub(crate) fn set_slot(&mut self, s: u32, v: Handle) {
646 if let Some(x) = self.frame.get_mut(self.base + s as usize) {
647 *x = v;
648 }
649 }
650
651 pub fn eval_bool(&mut self, code: &Code, p: P) -> Result<bool, Error> {
656 let v = self.eval(code, p)?;
657 bool_of(v)
658 }
659
660 pub fn eval_norm(&mut self, code: &Code, p: P) -> Result<Handle, Error> {
665 let v = self.eval(code, p)?;
666 self.work_norm(v)
667 }
668
669 fn same_vars_direct(&self, leaves: &[(u16, u8)], thunks: &[u32]) -> Result<bool, Error> {
681 if self.debugger.is_some()
682 || self.heap.store().semantics().tlc_comparisons
683 || thunks.iter().any(|&slot| !self.slot(slot).is_empty())
684 {
685 return Ok(false);
686 }
687 for &(v, depth) in leaves {
688 let v = usize::from(v);
689 let (Some(&a), Some(&b)) = (self.s0.get(v), self.s1.get(v)) else {
690 return Ok(false);
691 };
692 if !(self.proven_at(v, false, a) || compare::materialized(&self.heap, a, depth)?)
693 || (a != b
694 && !(self.proven_at(v, true, b)
695 || compare::materialized(&self.heap, b, depth)?))
696 {
697 return Ok(false);
698 }
699 }
700 Ok(true)
701 }
702
703 pub(crate) fn demand_equals(&mut self, a: Handle, b: Handle) -> Result<bool, Error> {
704 let a = self.work_norm(a)?;
705 let b = self.work_norm(b)?;
706 compare::equals(&self.heap, a, b)
707 }
708
709 pub(crate) fn eval_component(&mut self, code: &Code, p: P) -> Result<Handle, Error> {
710 let value = self.eval(code, p)?;
711 if self.heap.kind(value) == Some(Kind::Product) {
712 Ok(value)
714 } else {
715 self.work_norm(value)
716 }
717 }
718
719 pub fn eval(&mut self, code: &Code, p: P) -> Result<Handle, Error> {
724 let Some(observer) = &self.debugger else {
725 return self.eval_inner(code, p);
726 };
727 let instruction = crate::debug::Instruction::Value(p);
728 let guard = crate::debug::Guard::enter(observer, instruction, code, self)?;
729 let result = self.eval_inner(code, p);
730 let returned = match &result {
731 Ok(value) => crate::debug::Returned::Value(*value),
732 Err(error) => crate::debug::Returned::Failed(error),
733 };
734 guard.returned(instruction, code, self, returned)?;
735 result
736 }
737
738 #[allow(
739 clippy::too_many_lines,
740 clippy::many_single_char_names,
741 reason = "one arm per node kind, with operand names as in the semantics"
742 )]
743 fn eval_inner(&mut self, code: &Code, p: P) -> Result<Handle, Error> {
744 if self.fuel != u64::MAX {
745 self.charge(1)?;
746 }
747 let Some(node) = code.nodes.get(p as usize) else {
748 return Err(Error::internal("plan node out of range"));
749 };
750 match node {
751 Node::Const(h) => Ok(*h),
752 Node::Slot(s) => {
753 let v = self.slot(*s);
754 if v.is_empty() {
755 return Err(Error::internal("read of an unbound slot"));
756 }
757 Ok(v)
758 }
759 Node::Lazy { slot, body } => {
760 let v = self.slot(*slot);
761 if !v.is_empty() {
762 self.stats.cached += 1;
763 return Ok(v);
764 }
765 self.stats.forced += 1;
766 let v = self.eval(code, *body)?;
767 if v.is_transient() {
768 self.stats.transient_thunks += 1;
769 self.transient_slots.push(self.base + *slot as usize);
770 }
771 self.set_slot(*slot, v);
772 Ok(v)
773 }
774 Node::Var(i) => {
775 let v = self
776 .s0
777 .get(usize::from(*i))
778 .copied()
779 .unwrap_or(Handle::EMPTY);
780 if v.is_empty() {
781 return Err(eval_err("read of an unassigned variable"));
782 }
783 Ok(v)
784 }
785 Node::Primed(i) => {
786 let v = self
787 .s1
788 .get(usize::from(*i))
789 .copied()
790 .unwrap_or(Handle::EMPTY);
791 if v.is_empty() {
792 return Err(eval_err("read of an unassigned primed variable"));
793 }
794 Ok(v)
795 }
796 Node::Not(a) => Ok(Handle::bool(!self.eval_bool(code, *a)?)),
797 Node::And(items) => {
798 for &i in items {
799 if !self.eval_bool(code, i)? {
800 return Ok(Handle::FALSE);
801 }
802 }
803 Ok(Handle::TRUE)
804 }
805 Node::Or(items) => {
806 for &i in items {
807 if self.eval_bool(code, i)? {
808 return Ok(Handle::TRUE);
809 }
810 }
811 Ok(Handle::FALSE)
812 }
813 Node::Implies(a, b) => {
814 if self.eval_bool(code, *a)? {
815 Ok(Handle::bool(self.eval_bool(code, *b)?))
816 } else {
817 Ok(Handle::TRUE)
818 }
819 }
820 Node::Equiv(a, b) => {
821 let x = self.eval_bool(code, *a)?;
822 let y = self.eval_bool(code, *b)?;
823 Ok(Handle::bool(x == y))
824 }
825 Node::If(c, a, b) => {
826 if self.eval_bool(code, *c)? {
827 self.eval(code, *a)
828 } else {
829 self.eval(code, *b)
830 }
831 }
832 Node::Case(arms, other) => {
833 for &(g, v) in arms {
834 if self.eval_bool(code, g)? {
835 return self.eval(code, v);
836 }
837 }
838 match other {
839 Some(o) => self.eval(code, *o),
840 None => Err(eval_err("TLC encountered a CASE with no conditions true")),
841 }
842 }
843 Node::Eq(a, b) => {
844 let x = self.eval_norm(code, *a)?;
845 let y = self.eval_norm(code, *b)?;
846 Ok(Handle::bool(compare::equals(&self.heap, x, y)?))
847 }
848 Node::SameVars { eq, leaves, thunks } => {
849 if self.same_vars_direct(leaves, thunks)? {
850 let same = leaves.iter().all(|&(v, _)| {
851 let v = usize::from(v);
852 match (self.s0.get(v), self.s1.get(v)) {
853 (Some(&a), Some(&b)) => self.heap.eq(a, b),
854 _ => false,
855 }
856 });
857 return Ok(Handle::bool(same));
858 }
859 self.eval(code, *eq)
860 }
861 Node::Neq(a, b) => {
862 let x = self.eval_norm(code, *a)?;
863 let y = self.eval_norm(code, *b)?;
864 Ok(Handle::bool(!compare::equals(&self.heap, x, y)?))
865 }
866 Node::In(a, s) => {
867 let x = self.eval_norm(code, *a)?;
868 let set = self.eval(code, *s)?;
869 Ok(Handle::bool(self.member(x, set)?))
870 }
871 Node::NotIn(a, s) => {
872 let x = self.eval_norm(code, *a)?;
873 let set = self.eval(code, *s)?;
874 Ok(Handle::bool(!self.member(x, set)?))
875 }
876 Node::Subseteq(a, b) => {
877 let x = self.eval(code, *a)?;
878 let x = self.work_norm(x)?;
879 let y = self.eval(code, *b)?;
880 let elems = self.work_elements(x)?;
881 self.charge(elems.len())?;
882 for e in elems {
883 if !self.member(e, y)? {
884 return Ok(Handle::FALSE);
885 }
886 }
887 Ok(Handle::TRUE)
888 }
889 Node::Arith(op, a, b) => {
890 let x = self.eval(code, *a)?;
891 let y = self.eval(code, *b)?;
892 if let (Some(i), Some(j)) = (x.as_int(), y.as_int())
896 && let Some(h) = fast_arith(*op, i, j, self.heap.int_mode())
897 {
898 return Ok(h);
899 }
900 if *op == Arith::Pow && self.fuel != u64::MAX {
903 let words = self.heap.pow_result_words(x, y);
904 self.charge(usize::try_from(words).unwrap_or(usize::MAX))?;
905 }
906 self.heap.int_arith(int_op(*op), x, y)
907 }
908 Node::Cmp(op, a, b) => {
909 let x = self.eval(code, *a)?;
910 let y = self.eval(code, *b)?;
911 let o = match (x.as_int(), y.as_int()) {
912 (Some(i), Some(j)) => i.cmp(&j),
913 _ => self
914 .heap
915 .int_cmp(x, y)
916 .ok_or_else(|| eval_err("expected an integer"))?,
917 };
918 Ok(Handle::bool(match op {
919 Cmp::Lt => o.is_lt(),
920 Cmp::Le => o.is_le(),
921 Cmp::Gt => o.is_gt(),
922 Cmp::Ge => o.is_ge(),
923 }))
924 }
925 Node::Neg(a) => {
926 let x = self.eval(code, *a)?;
927 if self.heap.int_mode() == IntMode::Big
928 && let Some(h) = x.as_int().and_then(i64::checked_neg).and_then(Handle::int)
929 {
930 return Ok(h);
931 }
932 self.heap.int_neg(x)
933 }
934 Node::Range(a, b) => {
935 let x = int_of(self.eval(code, *a)?)?;
936 let y = int_of(self.eval(code, *b)?)?;
937 Ok(self.heap.interval(x, y))
938 }
939 Node::SetEnum(items) => {
940 let mut v = self.take_scratch();
941 for &i in items {
942 match self.eval_component(code, i) {
943 Ok(e) => v.push(e),
944 Err(e) => {
945 self.give_scratch(v);
946 return Err(e);
947 }
948 }
949 }
950 for value in &mut v {
951 *value = self.work_norm(*value)?;
952 }
953 if let Err(error) = compare::require_materialized(&self.heap, &v) {
954 self.give_scratch(v);
955 return Err(error);
956 }
957 let r = self.heap.set_from(&mut v);
958 self.give_scratch(v);
959 self.checked_set(r)
960 }
961 Node::SetBin(op, a, b) => {
962 let x = self.eval(code, *a)?;
963 let y = self.eval(code, *b)?;
964 self.set_bin(*op, x, y)
965 }
966 Node::Powerset(a) => {
967 let x = self.eval(code, *a)?;
968 Ok(self.heap.symbolic(Kind::Subset, 0, &[x]))
969 }
970 Node::BigUnion(a) => {
971 let x = self.eval_norm(code, *a)?;
972 let members = self.work_elements(x)?;
973 let mut normed = Vec::with_capacity(members.len());
977 for m in members {
978 normed.push(self.work_norm(m)?);
979 }
980 if normed.iter().any(|&m| !self.heap.is_finite(m)) {
981 let mut it = normed.into_iter();
982 let Some(first) = it.next() else {
983 return Err(Error::internal("an empty UNION with an infinite member"));
984 };
985 return Ok(it.fold(first, |acc, m| self.heap.union(acc, m)));
986 }
987 let mut out = Vec::new();
988 for m in normed {
989 let m = self.work_norm(m)?;
990 let es = self.work_elements(m)?;
991 self.charge(es.len())?;
992 out.extend(es);
993 }
994 let r = self.heap.set_from(&mut out);
995 self.checked_set(r)
996 }
997 Node::Product(items) => {
998 let mut v = Vec::with_capacity(items.len());
999 for &i in items {
1000 v.push(self.eval(code, i)?);
1001 }
1002 Ok(self.heap.symbolic(Kind::Product, 0, &v))
1003 }
1004 Node::FcnSet(d, r) => {
1005 let x = self.eval_component(code, *d)?;
1006 let y = self.eval(code, *r)?;
1007 Ok(self.heap.symbolic(Kind::FcnSet, 0, &[x, y]))
1008 }
1009 Node::RecSet(fields) => {
1010 let mut v: Vec<Handle> = fields.iter().map(|f| f.0).collect();
1011 for &(_, s) in fields {
1012 v.push(self.eval(code, s)?);
1013 }
1014 Ok(self.heap.symbolic(Kind::RecSet, 0, &v))
1015 }
1016 Node::Filter { bind, pred, subset } => self.filter(code, bind, *pred, *subset),
1017 Node::Map { binds, body } => {
1018 let mut out = Vec::new();
1019 self.for_each_binding(code, binds, &mut |m: &mut Self| {
1020 let v = m.eval_component(code, *body)?;
1021 let v = m.work_norm(v)?;
1022 m.charge(1)?;
1023 out.try_reserve(1)
1024 .map_err(|_| Error::unsupported("MAP construction allocation"))?;
1025 out.push(v);
1026 Ok(true)
1027 })?;
1028 compare::require_materialized(&self.heap, &out)?;
1029 let r = self.heap.set_from(&mut out);
1030 self.checked_set(r)
1031 }
1032 Node::FcnCons { binds, body } => self.fcn_cons(code, binds, *body),
1033 Node::Quant { kind, binds, body } => self.quant(code, *kind, binds, *body),
1034 Node::Apply(f, a) => {
1035 let fv = self.eval(code, *f)?;
1036 let av = self.eval_norm(code, *a)?;
1037 self.apply(fv, av)
1038 }
1039 Node::Select(r, field) => {
1040 let rv = self.eval(code, *r)?;
1041 self.select(rv, *field)
1042 }
1043 Node::Domain(f) => {
1044 let fv = self.eval(code, *f)?;
1045 self.domain(fv)
1046 }
1047 Node::Except { base, updates } => {
1048 let mut f = self.eval_norm(code, *base)?;
1049 for u in updates {
1050 f = self.except(code, f, u, 0)?;
1051 }
1052 Ok(f)
1053 }
1054 Node::Tuple(items) => {
1055 let mut v = self.take_scratch();
1056 for &i in items {
1057 match self.eval_component(code, i) {
1058 Ok(e) => v.push(e),
1059 Err(e) => {
1060 self.give_scratch(v);
1061 return Err(e);
1062 }
1063 }
1064 }
1065 let r = self.heap.tuple_literal(&v);
1066 self.give_scratch(v);
1067 Ok(r)
1068 }
1069 Node::Record(fields) => {
1070 let mut keys = self.take_scratch();
1071 let mut vals = self.take_scratch();
1072 for &(k, e) in fields {
1073 keys.push(k);
1074 match self.eval_component(code, e) {
1075 Ok(v) => vals.push(v),
1076 Err(e) => {
1077 self.give_scratch(keys);
1078 self.give_scratch(vals);
1079 return Err(e);
1080 }
1081 }
1082 }
1083 let r = self.heap.record(&keys, &vals);
1084 self.give_scratch(keys);
1085 self.give_scratch(vals);
1086 Ok(r)
1087 }
1088 Node::Scope { reset, body } => {
1089 for &s in reset {
1090 self.set_slot(s, Handle::EMPTY);
1091 }
1092 self.eval(code, *body)
1093 }
1094 Node::Call { fun, args } => self.call(code, *fun, args),
1095 Node::Std(f, args) => self.std(code, *f, args),
1096 Node::Lib {
1097 op,
1098 args,
1099 repeatable_args,
1100 } => {
1101 self.check_finite_access(*op)?;
1102 if crate::stdlib::deferred(*op) {
1106 return Err(crate::stdlib::deferred_refusal(*op));
1107 }
1108 let prints = matches!(
1112 op,
1113 dive_ir::StdOp::TlcPrint
1114 | dive_ir::StdOp::TlcPrintT
1115 | dive_ir::StdOp::TlcToString
1116 | dive_ir::StdOp::TlcRandomElement
1117 );
1118 let mut a = Vec::with_capacity(args.len());
1119 for &x in args {
1120 a.push(if prints {
1121 self.eval(code, x)?
1122 } else if *op == dive_ir::StdOp::TlcMakeFcn {
1123 self.eval_component(code, x)?
1124 } else {
1125 let value = self.eval_component(code, x)?;
1126 self.work_norm(value)?
1127 });
1128 }
1129 if !repeatable_args
1133 && matches!(
1134 op,
1135 dive_ir::StdOp::SequencesExtReplaceFirstSubSeq
1136 | dive_ir::StdOp::SequencesExtReplaceAllSubSeqs
1137 )
1138 && a.iter().any(|h| h.as_str_id().is_none())
1139 {
1140 return Err(Error::unsupported(format!(
1141 "{} with sequence arguments whose repeated fallback demand is not proven effect-free",
1142 op.qualified_name()
1143 )));
1144 }
1145 crate::stdlib::call(self, *op, &a)
1146 }
1147 Node::LibHo(op, args) => {
1148 self.check_finite_access(*op)?;
1149 let mut a = Vec::with_capacity(args.len());
1150 for x in args {
1151 a.push(match x {
1152 LibArg::Value(p) => {
1153 let value = self.eval_component(code, *p)?;
1154 crate::stdlib::Ho::Value(self.work_norm(value)?)
1155 }
1156 LibArg::Op { params, body } => {
1157 crate::stdlib::Ho::Op(crate::stdlib::OpFn::new(code, params, *body))
1158 }
1159 });
1160 }
1161 crate::stdlib::call_ho(self, *op, &a)
1162 }
1163 Node::Enabled { g, .. } => self.enabled(code, *g),
1164 Node::Composition {
1165 first, then, reset, ..
1166 } => self.composition_holds(code, *first, *then, reset),
1167 Node::Memo { site, body } => self.memo_eval(code, *site, *body),
1168 Node::Spec(b) => self.eval(code, *b).map_err(speculative),
1169 Node::Beta { chain, fc, arg } => self.beta(code, *chain, *fc, *arg),
1170 Node::DomCheck { slot, domain, body } => {
1171 let d = self.eval(code, *domain).map_err(speculative)?;
1172 let x = self.slot(*slot);
1173 if !self.member(x, d)? {
1174 return Err(general(
1175 "In applying the function\na recursive function, the argument is not in its domain",
1176 ));
1177 }
1178 self.eval(code, *body)
1179 }
1180 Node::InLazy { elem, set, neg } => {
1181 let x = self.eval_norm(code, *elem)?;
1182 let r = self.member_lazy(code, x, *set)?;
1183 Ok(Handle::bool(r != *neg))
1184 }
1185 }
1186 }
1187
1188 fn beta(&mut self, code: &Code, chain: P, fc: P, arg: P) -> Result<Handle, Error> {
1196 match code.nodes.get(chain as usize) {
1197 Some(Node::Lazy { slot, body }) => {
1198 let v = self.slot(*slot);
1199 if v.is_empty() {
1200 self.beta(code, *body, fc, arg)
1201 } else {
1202 let a = self.eval_norm(code, arg)?;
1203 self.apply(v, a)
1204 }
1205 }
1206 Some(Node::Scope { reset, body }) => {
1207 for &s in reset {
1208 self.set_slot(s, Handle::EMPTY);
1209 }
1210 self.beta(code, *body, fc, arg)
1211 }
1212 Some(Node::Spec(b)) => self.beta(code, *b, fc, arg),
1213 Some(Node::FcnCons { binds, body }) if chain == fc => {
1214 if let [bind] = &binds[..]
1215 && let [slot] = bind.slots[..]
1216 {
1217 return self.beta_one(code, bind.domain, slot, arg, *body);
1218 }
1219 self.beta_many(code, chain, binds, arg, *body)
1220 }
1221 _ => Err(Error::internal("a lazy application of a non-function node")),
1222 }
1223 }
1224
1225 fn beta_one(
1226 &mut self,
1227 code: &Code,
1228 domain: P,
1229 slot: u32,
1230 arg: P,
1231 body: P,
1232 ) -> Result<Handle, Error> {
1233 let dom = self.eval(code, domain)?;
1234 let x = self.eval_norm(code, arg)?;
1235 if !self.member(x, dom)? {
1236 return Err(general(
1237 "In applying the function\na function, the argument is not in its domain",
1238 ));
1239 }
1240 let old = self.slot(slot);
1241 self.set_slot(slot, x);
1242 let out = self.eval(code, body);
1243 self.set_slot(slot, old);
1244 out
1245 }
1246
1247 fn beta_many(
1251 &mut self,
1252 code: &Code,
1253 fc: P,
1254 binds: &[Bind],
1255 arg: P,
1256 body: P,
1257 ) -> Result<Handle, Error> {
1258 if binds.iter().any(|b| b.tuple || b.slots.is_empty()) {
1259 return Err(Error::internal(
1260 "a lazy application with a tuple pattern or no bound variable",
1261 ));
1262 }
1263 let mut doms = Vec::with_capacity(binds.len());
1264 for b in binds {
1265 doms.push(self.eval(code, b.domain)?);
1266 }
1267 let x = self.eval_norm(code, arg)?;
1268 let arity: usize = binds.iter().map(|b| b.slots.len()).sum();
1269 let parts = if x.is_compound() {
1270 let v = self.heap.view(x);
1271 (v.kind == Kind::IntFcn && v.lo == 1 && v.data.len() == arity).then(|| v.data.to_vec())
1272 } else {
1273 None
1274 };
1275 let Some(parts) = parts else {
1276 let f = self.eval(code, fc).map_err(speculative)?;
1277 return self.apply(f, x);
1278 };
1279 let mut k = 0;
1280 for (b, &dom) in binds.iter().zip(&doms) {
1281 for _ in &b.slots {
1282 if !self.member(parts[k], dom)? {
1283 return Err(general(
1284 "In applying the function\na function, the argument is not in its domain",
1285 ));
1286 }
1287 k += 1;
1288 }
1289 }
1290 let mark = self.saved.len();
1291 for &s in binds.iter().flat_map(|b| b.slots.iter()) {
1292 let v = self.slot(s);
1293 self.saved.push(v);
1294 }
1295 for (&s, &p) in binds.iter().flat_map(|b| b.slots.iter()).zip(&parts) {
1296 self.set_slot(s, p);
1297 }
1298 let out = self.eval(code, body);
1299 for (k, &s) in binds.iter().flat_map(|b| b.slots.iter()).enumerate() {
1300 let v = self.saved.get(mark + k).copied().unwrap_or(Handle::EMPTY);
1301 self.set_slot(s, v);
1302 }
1303 self.saved.truncate(mark);
1304 out
1305 }
1306
1307 fn member_lazy(&mut self, code: &Code, x: Handle, set: P) -> Result<bool, Error> {
1310 match code.nodes.get(set as usize) {
1311 Some(Node::Filter { bind, pred, .. }) => {
1314 if !self.member_lazy(code, x, bind.domain)? {
1315 return Ok(false);
1316 }
1317 let mark = self.saved.len();
1318 for &s in &bind.slots {
1319 let v = self.slot(s);
1320 self.saved.push(v);
1321 }
1322 let r = self
1323 .bind_one(bind, x)
1324 .and_then(|()| self.eval_bool(code, *pred));
1325 for (k, &s) in bind.slots.iter().enumerate() {
1326 let v = self.saved.get(mark + k).copied().unwrap_or(Handle::EMPTY);
1327 self.set_slot(s, v);
1328 }
1329 self.saved.truncate(mark);
1330 r
1331 }
1332 Some(Node::SetBin(op, a, b)) => {
1335 let (op, a, b) = (*op, *a, *b);
1336 let left = self.member_lazy(code, x, a)?;
1337 match op {
1338 SetOp::Cup if left => Ok(true),
1339 SetOp::Cap | SetOp::Minus if !left => Ok(false),
1340 SetOp::Cup | SetOp::Cap => self.member_lazy(code, x, b),
1341 SetOp::Minus => Ok(!self.member_lazy(code, x, b)?),
1342 }
1343 }
1344 Some(Node::Lazy { slot, body }) => {
1347 let v = self.slot(*slot);
1348 if v.is_empty() {
1349 self.member_lazy(code, x, *body)
1350 } else {
1351 self.member(x, v)
1352 }
1353 }
1354 Some(Node::Scope { reset, body }) => {
1355 for &s in reset {
1356 self.set_slot(s, Handle::EMPTY);
1357 }
1358 self.member_lazy(code, x, *body)
1359 }
1360 Some(Node::Spec(b)) => self.member_lazy(code, x, *b),
1364 Some(Node::Memo { site, body })
1368 if code.sites.get(*site as usize).is_some_and(|s| s.candidate) =>
1369 {
1370 self.member_lazy(code, x, *body)
1371 }
1372 _ => {
1373 let s = self.eval(code, set)?;
1374 self.member(x, s)
1375 }
1376 }
1377 }
1378
1379 fn memo_eval(&mut self, code: &Code, site: u32, body: P) -> Result<Handle, Error> {
1381 if self.heap.speculative {
1384 return self.eval(code, body);
1385 }
1386 let Some(s) = code.sites.get(site as usize) else {
1387 return self.eval(code, body);
1388 };
1389 if !(self.opts.memo || s.step) || !self.memo.active(site) {
1390 return self.eval(code, body);
1391 }
1392 if s.candidate && !self.memo.may_keep() {
1395 self.memo.charge_kept(site, 0);
1396 return self.eval(code, body);
1397 }
1398 let added = self.heap.cache.added;
1399 let mut key = [Handle::EMPTY; MAX_KEY];
1400 let mut n = 0;
1401 for &v in &s.vars {
1402 let h = self
1403 .s0
1404 .get(usize::from(v))
1405 .copied()
1406 .unwrap_or(Handle::EMPTY);
1407 if h.is_transient() || h.is_empty() || n >= MAX_KEY {
1408 self.memo.bypass(site);
1409 return self.eval(code, body);
1410 }
1411 key[n] = h;
1412 n += 1;
1413 }
1414 for &v in &s.primed {
1415 let h = self
1416 .s1
1417 .get(usize::from(v))
1418 .copied()
1419 .unwrap_or(Handle::EMPTY);
1420 let h = match self.heap.intern_exact(h) {
1424 Ok(k) if !h.is_empty() && n < MAX_KEY => k,
1425 _ => {
1426 if s.candidate {
1427 self.charge_kept(site, added);
1428 }
1429 self.memo.bypass(site);
1430 return self.eval(code, body);
1431 }
1432 };
1433 key[n] = h;
1434 n += 1;
1435 }
1436 for &sl in &s.slots {
1437 let h = self.slot(sl);
1438 if h.is_transient() || h.is_empty() || n >= MAX_KEY {
1439 self.memo.bypass(site);
1440 return self.eval(code, body);
1441 }
1442 key[n] = h;
1443 n += 1;
1444 }
1445 if s.candidate {
1446 self.charge_kept(site, added);
1447 }
1448 if let Some(r) = self.memo.get(site, &key[..n]) {
1449 return Ok(r);
1450 }
1451 let r = self.eval(code, body)?;
1452 let added = self.heap.cache.added;
1453 let kept = if s.step && r.is_transient() {
1456 self.heap.intern_exact(r).unwrap_or(r)
1457 } else {
1458 r
1459 };
1460 if s.candidate {
1461 self.charge_kept(site, added);
1462 }
1463 if !kept.is_transient() {
1464 self.memo.put(site, &key[..n], kept);
1465 }
1466 Ok(kept)
1467 }
1468
1469 fn charge_kept(&mut self, site: u32, since: u64) {
1472 let bytes = self.heap.cache.added.saturating_sub(since);
1473 self.memo.charge_kept(site, bytes);
1474 }
1475
1476 fn call(&mut self, code: &Code, fun: u32, args: &[P]) -> Result<Handle, Error> {
1477 self.charge(1)?;
1478 if self.depth >= MAX_CALL_DEPTH {
1479 return Err(Error::unsupported(
1480 "Core recursive-call depth limit (64 activations)",
1481 ));
1482 }
1483 self.depth += 1;
1486 let result = self.call_inner(code, fun, args);
1487 self.depth -= 1;
1488 result
1489 }
1490
1491 fn call_inner(&mut self, code: &Code, fun: u32, args: &[P]) -> Result<Handle, Error> {
1492 let Some(f) = code.funs.get(fun as usize) else {
1493 return Err(Error::internal("call of an unknown function"));
1494 };
1495 let mut vals = self.take_scratch();
1496 for &a in args {
1497 match self.eval_norm(code, a) {
1498 Ok(v) => vals.push(v),
1499 Err(e) => {
1500 self.give_scratch(vals);
1501 return Err(e);
1502 }
1503 }
1504 }
1505 let cached = match &mut self.calls {
1506 Some(cache) if !self.heap.speculative => {
1507 let revision = self.heap.arena.cache_revision();
1508 if cache.revision != revision {
1509 cache.results.clear();
1510 cache.revision = revision;
1511 }
1512 cache.key.clear();
1513 cache.key.push(u64::from(fun));
1514 cache.key.extend(vals.iter().map(|h| h.0));
1515 if let Some(&r) = cache.results.get(cache.key.as_slice()) {
1516 cache.hits += 1;
1517 self.give_scratch(vals);
1518 return Ok(r);
1519 }
1520 Some(cache.key.clone().into_boxed_slice())
1521 }
1522 _ => None,
1523 };
1524 let old = self.enter(f.frame);
1525 for (i, &v) in vals.iter().enumerate() {
1526 #[allow(
1527 clippy::cast_possible_truncation,
1528 reason = "parameter counts are small"
1529 )]
1530 let i = i as u32;
1531 let s = match i.checked_sub(f.params) {
1532 None => i,
1533 Some(c) => f.caps.get(c as usize).copied().unwrap_or(i),
1534 };
1535 self.set_slot(s, v);
1536 }
1537 self.give_scratch(vals);
1538 let r = self.eval(code, f.body);
1539 self.leave(old);
1540 if let (Some(key), Ok(h), Some(cache)) = (cached, &r, &mut self.calls)
1541 && cache.revision == self.heap.arena.cache_revision()
1542 {
1543 if cache.results.len() >= CALL_CACHE_ENTRIES {
1544 cache.results.clear();
1545 }
1546 cache.results.insert(key, *h);
1547 }
1548 r
1549 }
1550
1551 fn checked_set(&self, s: Handle) -> Result<Handle, Error> {
1558 compare::require_materialized(&self.heap, &[s])?;
1559 if self.heap.store().semantics().tlc_comparisons && s.is_compound() {
1560 compare::check_set(&self.heap, self.heap.view(s).data)?;
1561 }
1562 Ok(s)
1563 }
1564
1565 fn non_fcn_member(&self, x: Handle, what: &str) -> Result<bool, Error> {
1568 if x.is_compound() && self.heap.view(x).kind.is_fcn() {
1569 return Ok(false);
1570 }
1571 if x.as_model_id().is_some() {
1572 return self.mv_member(x);
1573 }
1574 Err(eval_err(&format!(
1575 "Attempted to check if a value that is not a function is in {what}"
1576 )))
1577 }
1578
1579 fn mv_member(&self, x: Handle) -> Result<bool, Error> {
1582 if compare::mv_type(&self.heap, x).is_none() {
1583 return Ok(false);
1584 }
1585 Err(general(
1586 "Attempted to check if the typed model value is an element of a set of another kind",
1587 ))
1588 }
1589
1590 #[allow(clippy::too_many_lines, reason = "one arm per set kind")]
1595 pub fn member(&mut self, x: Handle, set: Handle) -> Result<bool, Error> {
1596 if self.fuel != u64::MAX && set.is_compound() && self.heap.view(set).kind == Kind::SetEnum {
1597 self.domain_work(set, false, 0)?;
1598 }
1599 if !set.is_compound() {
1600 return Err(eval_err("membership in a value that is not a set"));
1601 }
1602 let kind = self.heap.view(set).kind;
1603 if kind != Kind::Set
1604 && kind != Kind::Product
1605 && kind != Kind::Subset
1606 && !self.opts.symbolic_member
1607 && self.heap.is_finite(set)
1608 && !self.heap.is_lazy(set)
1609 {
1610 let m = self.work_materialize_cached(set)?;
1611 return self.member(x, m);
1612 }
1613 let v = self.heap.view(set);
1614 match v.kind {
1615 Kind::Set => {
1616 let indexed = if self.fuel == u64::MAX && !v.is_lazy() {
1617 self.memo.member_index.search(&self.heap, set, x, v.data)?
1618 } else {
1619 None
1620 };
1621 if indexed.is_none() {
1622 for h in [x, set] {
1623 if !h.is_compound()
1626 || self.heap.view(h).flags & crate::node::flags::CONCRETE != 0
1627 || !self.proven(h)
1628 {
1629 compare::require_materialized(&self.heap, &[h])?;
1630 }
1631 }
1632 }
1633 if indexed
1634 .unwrap_or_else(|| v.data.binary_search_by(|&e| self.heap.cmp(e, x)).is_ok())
1635 {
1636 return Ok(true);
1637 }
1638 compare::miss_cached(&self.heap, &mut self.memo, x, set, v.data)?;
1639 Ok(false)
1640 }
1641 Kind::Interval => {
1642 let hi = v.data[0].as_int().unwrap_or(v.lo - 1);
1643 let lo = v.lo;
1644 match x.as_int() {
1645 Some(i) => Ok(lo <= i && i <= hi),
1646 None if lo > hi => Ok(false),
1649 None if x.as_model_id().is_some()
1650 && compare::mv_type(&self.heap, x).is_none() =>
1651 {
1652 Ok(false)
1653 }
1654 None if self.heap.is_int(x) => Ok(false),
1656 None => Err(general(
1657 "Attempted to check if the value:\na value that is not an integer\nis in the integer interval",
1658 )),
1659 }
1660 }
1661 Kind::Nat | Kind::Int if self.heap.is_int(x) => Ok(match x.as_int() {
1662 Some(i) => v.kind == Kind::Int || i >= 0,
1663 None => {
1665 v.kind == Kind::Int
1666 || self
1667 .heap
1668 .int_cmp(x, Handle::int(0).unwrap_or(Handle::EMPTY))
1669 == Some(std::cmp::Ordering::Greater)
1670 }
1671 }),
1672 Kind::Nat | Kind::Int if x.as_model_id().is_some() => self.mv_member(x),
1673 Kind::Nat | Kind::Int => Err(eval_exc(
1674 2158,
1675 "Attempted to check if the value:\na value that is not an integer\nis an element of Nat or Int.",
1676 )),
1677 Kind::Subset => {
1678 let base = v.data[0];
1679 let query_kind = self.heap.kind(x);
1680 if !matches!(query_kind, Some(Kind::Set | Kind::SetEnum | Kind::Interval)) {
1681 return Err(eval_err(
1682 "Attempted to check if a non-enumerable value is an element of SUBSET",
1683 ));
1684 }
1685 let mut elements = self.work_cursor(x)?;
1689 while let Some(e) = self.work_next(&mut elements)? {
1690 if !self.member(e, base)? {
1691 return Ok(false);
1692 }
1693 }
1694 Ok(true)
1695 }
1696 Kind::SeqSet => {
1697 let base = v.data[0];
1698 if !x.is_compound() || !self.heap.view(x).kind.is_fcn() {
1699 return self.non_fcn_member(x, "a set of sequences");
1700 }
1701 let xv = self.heap.view(x);
1702 if xv.kind != Kind::IntFcn || xv.lo != 1 {
1703 compare::guard_kind_member(
1705 &self.heap,
1706 "a membership test of a function that is not a sequence in Seq(S)",
1707 )?;
1708 return Ok(false);
1709 }
1710 let vals = xv.data.to_vec();
1711 for e in vals {
1712 if !self.member(e, base)? {
1713 return Ok(false);
1714 }
1715 }
1716 Ok(true)
1717 }
1718 Kind::FcnSet => {
1719 let (dom, rng) = (v.data[0], v.data[1]);
1720 if !x.is_compound() || !self.heap.view(x).kind.is_fcn() {
1721 return self.non_fcn_member(x, "a set of functions");
1722 }
1723 let d = self.domain(x)?;
1724 let d = self.work_norm(d)?;
1725 let dom = self.work_norm(dom)?;
1726 if !self.heap.eq(d, dom) {
1727 if self.heap.store().semantics().tlc_comparisons {
1729 compare::equals(&self.heap, d, dom)?;
1730 }
1731 return Ok(false);
1732 }
1733 let vals = self.heap.view(x).values().to_vec();
1734 for e in vals {
1735 if !self.member(e, rng)? {
1736 return Ok(false);
1737 }
1738 }
1739 Ok(true)
1740 }
1741 Kind::RecSet => {
1742 let n = v.data.len() / 2;
1743 let (names, sets) = (v.data[..n].to_vec(), v.data[n..].to_vec());
1744 if !x.is_compound() || !self.heap.view(x).kind.is_fcn() {
1745 return self.non_fcn_member(x, "a set of records");
1746 }
1747 let xv = self.heap.view(x);
1748 if xv.kind != Kind::Fcn || xv.keys().iter().any(|k| k.as_str_id().is_none()) {
1749 compare::guard_kind_member(
1751 &self.heap,
1752 "a membership test of a function that is not a record in a set of records",
1753 )?;
1754 return Ok(false);
1755 }
1756 if xv.keys() != names.as_slice() {
1757 return Ok(false);
1758 }
1759 let vals = xv.values().to_vec();
1760 for (e, s) in vals.into_iter().zip(sets) {
1761 if !self.member(e, s)? {
1762 return Ok(false);
1763 }
1764 }
1765 Ok(true)
1766 }
1767 Kind::Product => {
1768 let sets = v.data.to_vec();
1769 if !x.is_compound() || !self.heap.view(x).kind.is_fcn() {
1770 return self.non_fcn_member(x, "a set of tuples");
1771 }
1772 let xv = self.heap.view(x);
1773 if xv.kind == Kind::Fcn && xv.keys().iter().any(|k| k.as_int().is_none()) {
1774 compare::guard_kind_member(
1776 &self.heap,
1777 "a membership test of a function over non-integers in a set of tuples",
1778 )?;
1779 }
1780 if xv.kind != Kind::IntFcn || xv.lo != 1 || xv.data.len() != sets.len() {
1781 return Ok(false);
1782 }
1783 let vals = xv.data.to_vec();
1784 for (e, s) in vals.into_iter().zip(sets) {
1785 if !self.member(e, s)? {
1786 return Ok(false);
1787 }
1788 }
1789 Ok(true)
1790 }
1791 Kind::IntFcn | Kind::Fcn | Kind::Lambda => Err(eval_err("membership in a function")),
1792 Kind::BigInt => Err(eval_err("membership in a value that is not a set")),
1793 Kind::Union => {
1795 let (a, b) = (v.data[0], v.data[1]);
1796 Ok(self.member(x, a)? || self.member(x, b)?)
1797 }
1798 Kind::SetPred => Err(Error::unsupported(
1799 "membership in a lazy set predicate (the evaluator side is not built)",
1800 )),
1801 Kind::SetEnum => Err(Error::unsupported(
1805 "membership in a set enumeration TLC has not normalized (--compat=tlc)",
1806 )),
1807 }
1808 }
1809
1810 fn set_bin(&mut self, op: SetOp, x: Handle, y: Handle) -> Result<Handle, Error> {
1811 let (x, y) = (self.work_norm(x)?, self.work_norm(y)?);
1812 let fx = self.heap.is_finite(x);
1813 let fy = self.heap.is_finite(y);
1814 for (s, finite) in [(x, fx), (y, fy)] {
1815 if finite && s.is_compound() {
1816 let n = self.heap.view(s).len();
1817 self.charge(n)?;
1818 }
1819 }
1820 match op {
1821 SetOp::Cup => {
1822 if !fx || !fy {
1825 return Ok(self.heap.union(x, y));
1826 }
1827 if let Some(union) = self.union_concrete(x, y)? {
1828 return self.checked_set(union);
1829 }
1830 let mut v = self.work_elements(x)?;
1831 v.extend(self.work_elements(y)?);
1832 let r = self.heap.set_from(&mut v);
1833 self.checked_set(r)
1834 }
1835 SetOp::Cap => {
1836 let (a, b) = if fx {
1837 (x, y)
1838 } else if fy {
1839 (y, x)
1840 } else {
1841 return Err(Error::unsupported("intersection of infinite sets"));
1842 };
1843 let mut out = Vec::new();
1844 for e in self.work_elements(a)? {
1845 if self.member(e, b)? {
1846 out.push(e);
1847 }
1848 }
1849 Ok(self.heap.set_sorted(&out))
1850 }
1851 SetOp::Minus => {
1852 if !fx {
1853 return Err(Error::unsupported("difference of an infinite set"));
1854 }
1855 if let Some(r) = self.minus_small(x, y)? {
1856 return Ok(r);
1857 }
1858 let mut out = Vec::new();
1859 for e in self.work_elements(x)? {
1860 if !self.member(e, y)? {
1861 out.push(e);
1862 }
1863 }
1864 Ok(self.heap.set_sorted(&out))
1865 }
1866 }
1867 }
1868
1869 fn union_concrete(&mut self, x: Handle, y: Handle) -> Result<Option<Handle>, Error> {
1871 if !x.is_compound() || !y.is_compound() {
1872 return Ok(None);
1873 }
1874 let (left_view, right_view) = (self.heap.view(x), self.heap.view(y));
1875 if left_view.kind != Kind::Set
1876 || right_view.kind != Kind::Set
1877 || left_view.is_lazy()
1878 || right_view.is_lazy()
1879 {
1880 return Ok(None);
1881 }
1882 let capacity = left_view
1883 .data
1884 .len()
1885 .checked_add(right_view.data.len())
1886 .ok_or_else(|| Error::unsupported("set union address space"))?;
1887 let mut out = Vec::new();
1888 out.try_reserve_exact(capacity)
1889 .map_err(|_| Error::unsupported("set union allocation"))?;
1890 let (mut i, mut j) = (0, 0);
1891 while i < left_view.data.len() || j < right_view.data.len() {
1892 self.heap.work_poll()?;
1893 let value = match (left_view.data.get(i), right_view.data.get(j)) {
1894 (Some(&left), Some(&right)) => match self.heap.cmp(left, right) {
1895 std::cmp::Ordering::Less => {
1896 i += 1;
1897 left
1898 }
1899 std::cmp::Ordering::Greater => {
1900 j += 1;
1901 right
1902 }
1903 std::cmp::Ordering::Equal => {
1904 i += 1;
1905 j += 1;
1906 left
1907 }
1908 },
1909 (Some(&left), None) => {
1910 i += 1;
1911 left
1912 }
1913 (None, Some(&right)) => {
1914 j += 1;
1915 right
1916 }
1917 (None, None) => return Err(Error::internal("union cursor past both operands")),
1918 };
1919 out.push(value);
1920 }
1921 Ok(Some(self.heap.set_sorted(&out)))
1922 }
1923
1924 fn minus_small(&mut self, x: Handle, y: Handle) -> Result<Option<Handle>, Error> {
1930 if !x.is_compound() || !y.is_compound() {
1931 return Ok(None);
1932 }
1933 let (vx, vy) = (self.heap.view(x), self.heap.view(y));
1934 if vx.kind != Kind::Set || vy.kind != Kind::Set || vy.data.len() >= vx.data.len() {
1935 return Ok(None);
1936 }
1937 let (xs, ys) = (vx.data, vy.data);
1938 let mut drop = Vec::with_capacity(ys.len());
1939 for &z in ys {
1940 if let Ok(i) = xs.binary_search_by(|&e| self.heap.cmp(e, z)) {
1941 drop.push(i);
1942 }
1943 }
1944 drop.sort_unstable();
1945 let mut out = Vec::with_capacity(xs.len() - drop.len());
1946 for (i, &e) in xs.iter().enumerate() {
1947 if drop.binary_search(&i).is_err() {
1948 compare::miss(&self.heap, e, ys)?;
1949 out.push(e);
1950 }
1951 }
1952 Ok(Some(self.heap.set_sorted(&out)))
1953 }
1954
1955 fn filter(
1956 &mut self,
1957 code: &Code,
1958 bind: &Bind,
1959 pred: P,
1960 subset: Option<P>,
1961 ) -> Result<Handle, Error> {
1962 if let Some(mut cur) = self.subset_cursor(code, subset)? {
1963 let mut out = Vec::new();
1964 while let Some(e) = self.work_next(&mut cur)? {
1965 self.charge(1)?;
1966 out.push(e);
1967 }
1968 return Ok(self.heap.set_sorted(&out));
1969 }
1970 let dom = self.eval(code, bind.domain)?;
1973 let mut cur = self.work_cursor(dom)?;
1974 let mut out = Vec::new();
1975 loop {
1976 let before = self.heap.mark();
1981 let Some(e) = self.work_next(&mut cur)? else {
1982 break;
1983 };
1984 self.charge(1)?;
1985 let after = self.heap.mark();
1986 let forced = self.thunk_mark();
1987 self.bind_one(bind, e)?;
1988 let keep = self.eval_bool(code, pred)?;
1989 if self.thunks_released(forced) {
1990 if keep {
1991 self.heap.rollback(after);
1992 } else {
1993 self.heap.rollback(before);
1994 }
1995 }
1996 if keep {
1997 out.push(e);
1998 }
1999 }
2000 Ok(self.heap.set_sorted(&out))
2001 }
2002
2003 pub(crate) fn subset_cursor(
2011 &mut self,
2012 code: &Code,
2013 subset: Option<P>,
2014 ) -> Result<Option<Cursor>, Error> {
2015 let Some(set) = subset else {
2016 return Ok(None);
2017 };
2018 let before = self.heap.mark();
2019 let forced = self.thunk_mark();
2020 match self.eval_norm(code, set) {
2021 Ok(f) => {
2022 let powerset = self.heap.symbolic(Kind::Subset, 0, &[f]);
2023 self.work_cursor(powerset).map(Some)
2024 }
2025 Err(e) if e.kind() == crate::ErrorKind::Eval => {
2026 if self.thunks_released(forced) {
2027 self.heap.rollback(before);
2028 }
2029 Ok(None)
2030 }
2031 Err(e) => Err(e),
2032 }
2033 }
2034
2035 pub(crate) fn bind_one(&mut self, bind: &Bind, e: Handle) -> Result<(), Error> {
2038 if bind.tuple {
2039 let v = self.heap.view(e);
2040 if v.kind != Kind::IntFcn || v.lo != 1 || v.data.len() != bind.slots.len() {
2041 return Err(eval_err("a tuple pattern does not match the element"));
2042 }
2043 let parts = v.data.to_vec();
2044 for (&s, p) in bind.slots.iter().zip(parts) {
2045 self.set_slot(s, p);
2046 }
2047 } else if let Some(&s) = bind.slots.first() {
2048 self.set_slot(s, e);
2049 }
2050 Ok(())
2051 }
2052
2053 pub(crate) fn units(
2056 &mut self,
2057 code: &Code,
2058 binds: &[Bind],
2059 ) -> Result<Vec<(Unit, Vec<Handle>)>, Error> {
2060 let mut out = Vec::new();
2061 for (bi, b) in binds.iter().enumerate() {
2062 let d = match code.nodes.get(b.domain as usize) {
2063 Some(Node::Const(h)) if self.fuel == u64::MAX => {
2066 self.heap.enumerate_constant(*h)?
2067 }
2068 _ => {
2069 let d = self.eval(code, b.domain)?;
2070 self.work_norm(d)?
2071 }
2072 };
2073 let elems = self.work_elements(d)?;
2074 if b.tuple {
2075 out.push((
2076 Unit {
2077 bind: bi,
2078 var: None,
2079 },
2080 elems,
2081 ));
2082 } else {
2083 for vi in 0..b.slots.len() {
2084 self.charge(elems.len() + 1)?;
2085 out.push((
2086 Unit {
2087 bind: bi,
2088 var: Some(vi),
2089 },
2090 elems.clone(),
2091 ));
2092 }
2093 }
2094 }
2095 Ok(out)
2096 }
2097
2098 pub(crate) fn bind_unit(&mut self, binds: &[Bind], u: Unit, e: Handle) -> Result<(), Error> {
2099 let b = &binds[u.bind];
2100 match u.var {
2101 Some(vi) => {
2102 self.set_slot(b.slots[vi], e);
2103 Ok(())
2104 }
2105 None => self.bind_one(b, e),
2106 }
2107 }
2108
2109 pub(crate) fn for_each_binding(
2112 &mut self,
2113 code: &Code,
2114 binds: &[Bind],
2115 f: &mut dyn FnMut(&mut Self) -> Result<bool, Error>,
2116 ) -> Result<bool, Error> {
2117 if self.fuel != u64::MAX {
2118 return self.binding_stream(code, binds, f);
2119 }
2120 let units = self.units(code, binds)?;
2121 if units.iter().any(|(_, e)| e.is_empty()) {
2122 return Ok(true);
2123 }
2124 let mut idx = vec![0usize; units.len()];
2125 loop {
2126 self.charge(1)?;
2127 for (k, (u, elems)) in units.iter().enumerate() {
2128 self.bind_unit(binds, *u, elems[idx[k]])?;
2129 }
2130 if !f(self)? {
2131 return Ok(false);
2132 }
2133 let mut k = 0;
2134 loop {
2135 if k == units.len() {
2136 return Ok(true);
2137 }
2138 idx[k] += 1;
2139 if idx[k] < units[k].1.len() {
2140 break;
2141 }
2142 idx[k] = 0;
2143 k += 1;
2144 }
2145 }
2146 }
2147
2148 fn quant(
2149 &mut self,
2150 code: &Code,
2151 kind: Quant,
2152 binds: &[Bind],
2153 body: P,
2154 ) -> Result<Handle, Error> {
2155 match kind {
2156 Quant::Exists => {
2157 let mut found = false;
2158 self.for_each_binding(code, binds, &mut |m: &mut Self| {
2159 if m.eval_bool(code, body)? {
2160 found = true;
2161 return Ok(false);
2162 }
2163 Ok(true)
2164 })?;
2165 Ok(Handle::bool(found))
2166 }
2167 Quant::Forall => {
2168 let all = self
2169 .for_each_binding(code, binds, &mut |m: &mut Self| m.eval_bool(code, body))?;
2170 Ok(Handle::bool(all))
2171 }
2172 Quant::Choose => {
2173 if binds.len() != 1 || (!binds[0].tuple && binds[0].slots.len() != 1) {
2174 return Err(Error::unsupported("CHOOSE with several bound variables"));
2175 }
2176 let d = self.eval(code, binds[0].domain)?;
2177 let mut cur = self.work_cursor(d)?;
2178 loop {
2179 let before = self.heap.mark();
2182 let Some(e) = self.work_next(&mut cur)? else {
2183 break;
2184 };
2185 self.charge(1)?;
2186 let forced = self.thunk_mark();
2187 self.bind_one(&binds[0], e)?;
2188 if self.eval_bool(code, body)? {
2189 return Ok(e);
2190 }
2191 if self.thunks_released(forced) {
2192 self.heap.rollback(before);
2193 }
2194 }
2195 Err(general(
2196 "Attempted to compute the value of an expression of form\nCHOOSE x \\in S: P, but no element of S satisfied P.",
2197 ))
2198 }
2199 }
2200 }
2201
2202 fn fcn_cons(&mut self, code: &Code, binds: &[Bind], body: P) -> Result<Handle, Error> {
2203 let units = self.units(code, binds)?;
2204 if units.len() == 1 {
2205 let (u, keys) = units
2206 .into_iter()
2207 .next()
2208 .unwrap_or((Unit { bind: 0, var: None }, Vec::new()));
2209 self.charge(keys.len())?;
2210 let mut vals = Vec::with_capacity(keys.len());
2211 for &k in &keys {
2212 self.bind_unit(binds, u, k)?;
2213 vals.push(self.eval_component(code, body)?);
2214 }
2215 return Ok(self.heap.fcn_sorted(&keys, &vals));
2216 }
2217 if units.iter().any(|(u, _)| u.var.is_none()) {
2218 return Err(Error::unsupported(
2219 "a function constructor mixing tuple patterns and several bounds",
2220 ));
2221 }
2222 let mut keys = Vec::new();
2225 let mut vals = Vec::new();
2226 if units.iter().any(|(_, e)| e.is_empty()) {
2227 return Ok(self.heap.fcn_sorted(&[], &[]));
2228 }
2229 let mut idx = vec![0usize; units.len()];
2230 'outer: loop {
2231 self.charge(1)?;
2232 let comps: Vec<Handle> = idx.iter().zip(&units).map(|(&i, (_, e))| e[i]).collect();
2233 for (k, (u, _)) in units.iter().enumerate() {
2234 self.bind_unit(binds, *u, comps[k])?;
2235 }
2236 keys.push(self.heap.tuple(&comps));
2237 vals.push(self.eval_component(code, body)?);
2238 let mut k = units.len();
2239 loop {
2240 if k == 0 {
2241 break 'outer;
2242 }
2243 k -= 1;
2244 idx[k] += 1;
2245 if idx[k] < units[k].1.len() {
2246 break;
2247 }
2248 idx[k] = 0;
2249 }
2250 }
2251 Ok(self.heap.fcn_sorted(&keys, &vals))
2252 }
2253
2254 pub(crate) fn fcn_index(&self, f: Handle, key: Handle) -> Result<Option<usize>, Error> {
2260 if !f.is_compound() {
2261 return Err(eval_err("application of a value that is not a function"));
2262 }
2263 let v = self.heap.view(f);
2264 match v.kind {
2265 Kind::IntFcn => Ok(key.as_int().and_then(|k| {
2266 let i = k.checked_sub(v.lo)?;
2267 usize::try_from(i).ok().filter(|&i| i < v.data.len())
2268 })),
2269 Kind::Fcn => {
2270 let keys = v.keys();
2271 if key.as_str_id().is_some() || keys.len() <= 8 {
2272 Ok(keys.iter().position(|&k| self.heap.eq(k, key)))
2273 } else if let Some(i) = self.grid_index(keys, key) {
2274 Ok(Some(i))
2275 } else {
2276 Ok(keys.binary_search_by(|&k| self.heap.cmp(k, key)).ok())
2277 }
2278 }
2279 _ => Err(eval_err("application of a set as a function")),
2280 }
2281 }
2282
2283 fn grid_index(&self, keys: &[Handle], key: Handle) -> Option<usize> {
2289 let (row, col) = self.int_pair(key)?;
2290 let (l1, l2) = self.int_pair(*keys.first()?)?;
2291 let (h1, h2) = self.int_pair(*keys.last()?)?;
2292 let rows = usize::try_from(h1.checked_sub(l1)?.checked_add(1)?).ok()?;
2293 let width = usize::try_from(h2.checked_sub(l2)?.checked_add(1)?).ok()?;
2294 if rows.checked_mul(width)? != keys.len()
2295 || !(l1..=h1).contains(&row)
2296 || !(l2..=h2).contains(&col)
2297 {
2298 return None;
2299 }
2300 let at = usize::try_from(row - l1).ok()? * width + usize::try_from(col - l2).ok()?;
2301 let k = *keys.get(at)?;
2302 self.heap.eq(k, key).then_some(at)
2303 }
2304
2305 fn int_pair(&self, h: Handle) -> Option<(i64, i64)> {
2307 if !h.is_compound() {
2308 return None;
2309 }
2310 let v = self.heap.view(h);
2311 match (v.kind, v.lo, v.data) {
2312 (Kind::IntFcn, 1, &[a, b]) => Some((a.as_int()?, b.as_int()?)),
2313 _ => None,
2314 }
2315 }
2316
2317 pub fn apply(&mut self, f: Handle, a: Handle) -> Result<Handle, Error> {
2322 if let Some(i) = self.fcn_index(f, a)? {
2323 return Ok(self.heap.view(f).values()[i]);
2324 }
2325 let msg = "Attempted to apply function to an argument not in its domain";
2326 let v = self.heap.view(f);
2327 match v.kind {
2328 Kind::Fcn => {
2331 compare::miss(&self.heap, a, v.keys())?;
2332 Err(general(msg))
2333 }
2334 Kind::IntFcn if a.as_int().is_some() => Err(general(msg)),
2335 _ => Err(eval_err(msg)),
2336 }
2337 }
2338
2339 fn select(&mut self, r: Handle, field: Handle) -> Result<Handle, Error> {
2340 if !r.is_compound() {
2341 return Err(eval_err("field selection on a value that is not a record"));
2342 }
2343 let v = self.heap.view(r);
2344 if v.kind == Kind::Fcn
2345 && let Some(i) = v.keys().iter().position(|&k| k == field)
2346 {
2347 return Ok(v.values()[i]);
2348 }
2349 Err(eval_err(
2350 "Attempted to access a record field that does not exist",
2351 ))
2352 }
2353
2354 fn domain(&mut self, f: Handle) -> Result<Handle, Error> {
2355 if !f.is_compound() {
2356 return Err(eval_err("DOMAIN of a value that is not a function"));
2357 }
2358 let len = self.heap.view(f).len();
2359 self.charge(len.saturating_mul(2))?;
2360 let v = self.heap.view(f);
2361 match v.kind {
2362 #[allow(clippy::cast_possible_wrap, reason = "domains fit in i64")]
2363 Kind::IntFcn => {
2364 let (lo, n) = (v.lo, v.data.len() as i64);
2365 if n == 0 {
2366 return Ok(self.heap.empty_set());
2367 }
2368 let mut out = Vec::with_capacity(v.data.len());
2369 for k in lo..lo + n {
2370 out.push(mk_int(k)?);
2371 }
2372 Ok(self.heap.set_sorted(&out))
2373 }
2374 Kind::Fcn => {
2375 let keys = v.keys().to_vec();
2376 Ok(self.heap.set_sorted(&keys))
2377 }
2378 _ => Err(eval_err("DOMAIN of a set")),
2379 }
2380 }
2381
2382 fn except(
2383 &mut self,
2384 code: &Code,
2385 f: Handle,
2386 u: &Update,
2387 depth: usize,
2388 ) -> Result<Handle, Error> {
2389 let Some(&step) = u.path.get(depth) else {
2390 return Err(Error::internal("EXCEPT path out of range"));
2391 };
2392 let key = self.eval_norm(code, step)?;
2393 if !f.is_compound() || !self.heap.view(f).kind.is_fcn() {
2394 return Err(eval_err("EXCEPT on a value that is not a function"));
2395 }
2396 self.charge(self.heap.view(f).len())?;
2397 let Some(i) = self.fcn_index(f, key)? else {
2398 let v = self.heap.view(f);
2402 if v.kind == Kind::IntFcn {
2403 if key.as_int().is_none() && !v.data.is_empty() {
2404 return Err(eval_err(
2405 "Attempted to apply EXCEPT to a tuple at a non-integral index",
2406 ));
2407 }
2408 } else {
2409 compare::miss(&self.heap, key, v.keys())?;
2410 }
2411 if self.refuse_unrecorded_warnings {
2412 return Err(Error::unsupported(
2413 "an EXCEPT key outside the function's domain, where the reference prints warning 2144",
2414 ));
2415 }
2416 return Ok(f);
2417 };
2418 let old = self.heap.view(f).values()[i];
2419 let new = if depth + 1 == u.path.len() {
2420 self.set_slot(u.at, old);
2421 self.eval_component(code, u.value)?
2422 } else {
2423 self.except(code, old, u, depth + 1)?
2424 };
2425 if new == old {
2426 return Ok(f);
2427 }
2428 self.charge(self.heap.view(f).data.len())?;
2429 Ok(self.heap.fcn_with(f, i, new))
2430 }
2431
2432 fn seq_vals(&mut self, s: Handle) -> Result<Vec<Handle>, Error> {
2437 if !s.is_compound() {
2438 return Err(eval_err("expected a sequence"));
2439 }
2440 let v = self.heap.view(s);
2441 if v.kind != Kind::IntFcn || v.lo != 1 {
2442 return Err(eval_err("expected a sequence"));
2443 }
2444 let len = v.data.len();
2445 self.charge(len)?;
2446 Ok(self.heap.view(s).data.to_vec())
2447 }
2448
2449 fn bag(&mut self, op: StdFn, args: &[Handle]) -> Result<Handle, Error> {
2451 let arg = |i: usize| {
2452 args.get(i)
2453 .copied()
2454 .ok_or_else(|| Error::internal("missing argument"))
2455 };
2456 match op {
2457 StdFn::EmptyBag => Ok(self.heap.fcn_sorted(&[], &[])),
2458 StdFn::SetToBag => {
2459 let set = arg(0)?;
2460 if !set.is_compound()
2461 || matches!(self.heap.view(set).kind, Kind::Fcn | Kind::IntFcn)
2462 {
2463 return Err(eval_err(
2464 "The argument of SetToBag should be a finite set, but instead it is not",
2465 ));
2466 }
2467 let keys = self.work_elements(set)?;
2468 let one = mk_int(1)?;
2469 let ones = vec![one; keys.len()];
2470 Ok(self.heap.fcn_sorted(&keys, &ones))
2471 }
2472 StdFn::BagToSet => {
2473 let bag = arg(0)?;
2474 if !bag.is_compound()
2475 || !matches!(self.heap.view(bag).kind, Kind::Fcn | Kind::IntFcn)
2476 {
2477 return Err(eval_err(
2478 "The argument of BagToSet should be a function with a finite domain",
2479 ));
2480 }
2481 self.domain(bag)
2482 }
2483 StdFn::BagIn | StdFn::CopiesIn => {
2484 let (elem, bag) = (arg(0)?, arg(1)?);
2485 if !bag.is_compound()
2486 || !matches!(self.heap.view(bag).kind, Kind::Fcn | Kind::IntFcn)
2487 {
2488 return Err(eval_err("BagIn or CopiesIn of a value that is not a bag"));
2489 }
2490 let dom = self.domain(bag)?;
2493 if !self.member(elem, dom)? {
2494 return Ok(if op == StdFn::BagIn {
2495 Handle::bool(false)
2496 } else {
2497 mk_int(0)?
2498 });
2499 }
2500 let count = self.apply(bag, elem)?;
2501 let n = count
2502 .as_int()
2503 .ok_or_else(|| eval_err("The second argument of BagIn should be a bag"))?;
2504 Ok(if op == StdFn::BagIn {
2505 Handle::bool(n > 0)
2506 } else {
2507 count
2508 })
2509 }
2510 _ => Err(Error::internal("not a Bags operator")),
2511 }
2512 }
2513
2514 fn len(&mut self, s: Handle) -> Result<Handle, Error> {
2517 if let Some(id) = s.as_str_id() {
2518 let text = self
2519 .heap
2520 .store()
2521 .strings()
2522 .text(id)
2523 .ok_or_else(|| Error::internal("unknown string"))?;
2524 self.charge(text.len())?;
2527 return mk_int(i64::try_from(text.encode_utf16().count()).unwrap_or(i64::MAX));
2528 }
2529 if !s.is_compound() {
2531 return Err(one_arg("Len", "sequence"));
2532 }
2533 let v = self.heap.view(s);
2534 if v.kind != Kind::IntFcn || v.lo != 1 {
2535 return Err(one_arg("Len", "sequence"));
2536 }
2537 mk_int(i64::try_from(v.data.len()).unwrap_or(i64::MAX))
2538 }
2539
2540 fn std_arg(&mut self, code: &Code, f: StdFn, index: usize, x: P) -> Result<Handle, Error> {
2541 let value = if matches!(f, StdFn::IsFiniteSet | StdFn::Cardinality | StdFn::Seq) {
2544 self.eval(code, x)?
2545 } else {
2546 self.eval_component(code, x)?
2547 };
2548 let product = self.heap.kind(value) == Some(Kind::Product);
2549 if matches!(f, StdFn::Seq | StdFn::IsFiniteSet)
2550 || (f == StdFn::Append && index == 1)
2551 || (product && matches!(f, StdFn::Cardinality | StdFn::IsFiniteSet | StdFn::Seq))
2552 {
2553 Ok(value)
2554 } else {
2555 self.work_norm(value)
2556 }
2557 }
2558
2559 fn std(&mut self, code: &Code, f: StdFn, args: &[P]) -> Result<Handle, Error> {
2560 let mut a = Vec::with_capacity(args.len());
2561 for (index, &x) in args.iter().enumerate() {
2562 a.push(self.std_arg(code, f, index, x)?);
2563 }
2564 let arg = |i: usize| {
2565 a.get(i)
2566 .copied()
2567 .ok_or_else(|| Error::internal("missing argument"))
2568 };
2569 match f {
2570 StdFn::Len => self.len(arg(0)?),
2571 StdFn::Head => {
2572 let vals = self.seq_vals(arg(0)?)?;
2573 vals.first()
2574 .copied()
2575 .ok_or_else(|| eval_exc(2184, "Attempted to apply Head to the empty sequence."))
2576 }
2577 StdFn::Tail => {
2578 let vals = self.seq_vals(arg(0)?)?;
2579 if vals.is_empty() {
2580 return Err(eval_exc(
2581 2184,
2582 "Attempted to apply Tail to the empty sequence.",
2583 ));
2584 }
2585 Ok(self.heap.tuple(&vals[1..]))
2586 }
2587 StdFn::Append => {
2588 let mut vals = self.seq_vals(arg(0)?)?;
2589 vals.push(arg(1)?);
2590 Ok(self.heap.tuple(&vals))
2591 }
2592 StdFn::Concat => {
2593 let mut vals = self.seq_vals(arg(0)?)?;
2594 vals.extend(self.seq_vals(arg(1)?)?);
2595 Ok(self.heap.tuple(&vals))
2596 }
2597 StdFn::SubSeq => {
2598 let vals = self.seq_vals(arg(0)?)?;
2599 let m = int_of(arg(1)?)?;
2600 let n = int_of(arg(2)?)?;
2601 if m > n {
2602 return Ok(self.heap.tuple(&[]));
2603 }
2604 let len = i64::try_from(vals.len()).unwrap_or(i64::MAX);
2605 if m < 1 || n > len {
2606 return Err(eval_err("SubSeq indices out of range"));
2607 }
2608 #[allow(
2609 clippy::cast_sign_loss,
2610 clippy::cast_possible_truncation,
2611 reason = "checked range"
2612 )]
2613 Ok(self.heap.tuple(&vals[(m - 1) as usize..n as usize]))
2614 }
2615 StdFn::Cardinality => {
2616 let s = arg(0)?;
2617 if self.heap.kind(s) == Some(Kind::Set) {
2618 compare::require_materialized(&self.heap, &[s])?;
2619 }
2620 if self.heap.kind(s) == Some(Kind::Product) {
2621 return self.product_cardinality(s);
2622 }
2623 let kind = self.heap.kind(s);
2624 match kind {
2625 None | Some(Kind::IntFcn | Kind::Fcn | Kind::Nat | Kind::Int) => {
2627 return Err(cardinality_error());
2628 }
2629 Some(Kind::SeqSet) => {
2630 return Err(Error::unsupported("Cardinality of Seq(S) (M1 core)"));
2631 }
2632 Some(_) if !self.heap.is_finite(s) => return Err(cardinality_error()),
2633 Some(_) => {}
2634 }
2635 let n = self.work_cardinality(s)?;
2636 mk_int(i64::try_from(n).unwrap_or(i64::MAX))
2637 }
2638 StdFn::Seq => {
2639 let s = arg(0)?;
2640 Ok(self.heap.symbolic(Kind::SeqSet, 0, &[s]))
2641 }
2642 StdFn::IsFiniteSet => self.symbolic_finiteness(arg(0)?).map(Handle::bool),
2643 StdFn::EmptyBag
2644 | StdFn::SetToBag
2645 | StdFn::BagToSet
2646 | StdFn::BagIn
2647 | StdFn::CopiesIn => self.bag(f, &a),
2648 }
2649 }
2650}
2651
2652#[derive(Clone, Copy, Debug)]
2654pub(crate) struct Unit {
2655 pub(crate) bind: usize,
2656 pub(crate) var: Option<usize>,
2657}
2658
2659const fn int_op(op: Arith) -> IntOp {
2661 match op {
2662 Arith::Add => IntOp::Add,
2663 Arith::Sub => IntOp::Sub,
2664 Arith::Mul => IntOp::Mul,
2665 Arith::Div => IntOp::Div,
2666 Arith::DivNaturals => IntOp::DivNaturals,
2667 Arith::Mod => IntOp::Mod,
2668 Arith::Pow => IntOp::Pow,
2669 }
2670}
2671
2672fn fast_arith(op: Arith, x: i64, y: i64, mode: IntMode) -> Option<Handle> {
2676 let r = match op {
2677 Arith::Add => x.checked_add(y)?,
2678 Arith::Sub => x.checked_sub(y)?,
2679 Arith::Mul => x.checked_mul(y)?,
2680 Arith::Div | Arith::DivNaturals if y > 0 && (mode == IntMode::Big || x >= 0) => {
2683 x.div_euclid(y)
2684 }
2685 Arith::Mod if y > 0 => x.rem_euclid(y),
2686 _ => return None,
2687 };
2688 if mode == IntMode::Tlc && i32::try_from(r).is_err() {
2689 return None;
2690 }
2691 Handle::int(r)
2692}
2693
2694#[cfg(test)]
2695#[path = "eval_union_tests.rs"]
2696mod union_tests;
2697
2698#[cfg(test)]
2699mod tests {
2700 #![allow(clippy::unwrap_used, reason = "tests")]
2701 use super::*;
2702 use crate::TlcClass;
2703
2704 #[test]
2709 fn candidate_site_copies_stay_within_the_memo_cap() {
2710 use crate::plan::{Code, MemoSite};
2711 let cap = 64 << 10;
2712 let store = Arc::new(Store::new(true));
2713 let opts = Opts {
2714 memo_cap: cap,
2715 ..Opts::default()
2716 };
2717 let mut m = Machine::new(Arc::clone(&store), 1, opts, Memo::new(&[1]));
2718 let code = Code {
2719 nodes: vec![
2720 Node::Primed(0),
2721 Node::Tuple(vec![0, 0].into()),
2722 Node::Memo { site: 0, body: 1 },
2723 ],
2724 sites: vec![MemoSite {
2725 name: "F (Primed, action)".into(),
2726 vars: vec![].into(),
2727 slots: vec![].into(),
2728 primed: vec![0].into(),
2729 step: true,
2730 candidate: true,
2731 }],
2732 ..Code::default()
2733 };
2734 let before = store.stats().nodes;
2735 let candidates: i64 = 20_000;
2736 for i in 0..candidates {
2737 let items: Vec<Handle> = (0..6).map(|k| Handle::int(i * 8 + k).unwrap()).collect();
2738 let x = m.heap.tuple(&items);
2739 m.s1[0] = x;
2740 let expected = m.heap.tuple(&[x, x]);
2741 for _ in 0..4 {
2742 let r = m.eval(&code, 2).unwrap();
2743 assert!(
2744 compare::equals(&m.heap, r, expected).unwrap(),
2745 "candidate {i}"
2746 );
2747 }
2748 m.s1[0] = Handle::EMPTY;
2749 m.heap.reset();
2750 }
2751 let added = store.stats().nodes - before;
2752 assert!(
2755 added < 2 * candidates.unsigned_abs() / 4,
2756 "{added} persistent nodes"
2757 );
2758 assert!(!m.memo.may_keep());
2759 assert!(m.memo.stats()[0].off);
2760 assert!(m.memo.stats()[0].hits > 0);
2761 }
2762
2763 #[test]
2764 fn a_transient_bound_stops_an_evaluation_by_name() {
2765 let mut m = Machine::new(
2766 Arc::new(Store::with_semantics(true, crate::Semantics::default())),
2767 0,
2768 Opts::default(),
2769 Memo::new(&[]),
2770 );
2771 let one = Handle::int(1).unwrap();
2772 assert_eq!(m.charge(1), Ok(()));
2773 m.set_transient_bound(4096);
2774 while m.heap.arena.footprint() <= 4096 {
2775 m.heap.tuple(&[one, one, one, one]);
2776 }
2777 let error = m.charge(1).unwrap_err();
2778 assert_eq!(error.kind(), crate::ErrorKind::Unsupported);
2779 assert!(error.message().contains("start-up evaluation memory bound"));
2780 m.set_transient_bound(usize::MAX);
2781 assert_eq!(m.charge(1), Ok(()));
2782 m.heap.reset();
2783 m.heap.arena.release();
2784 assert_eq!(m.heap.arena.footprint(), 0);
2785 }
2786
2787 #[test]
2788 fn sequences_keep_the_original_product_range_and_its_member_demand() {
2789 for tlc in [false, true] {
2790 let semantics = if tlc {
2791 crate::Semantics::tlc()
2792 } else {
2793 crate::Semantics::default()
2794 };
2795 let mut m = Machine::new(
2796 Arc::new(Store::with_semantics(true, semantics)),
2797 1,
2798 Opts::default(),
2799 Memo::new(&[]),
2800 );
2801 let zero = Handle::int(0).unwrap();
2802 let empty = m.heap.interval(0, -1);
2803 let product = m.heap.symbolic(Kind::Product, 0, &[empty, zero]);
2804 let code = Code {
2805 nodes: vec![Node::Const(product), Node::Std(StdFn::Seq, vec![0].into())],
2806 ..Code::default()
2807 };
2808 let sequences = m.eval(&code, 1).unwrap();
2809 assert_eq!(m.heap.view(sequences).kind, Kind::SeqSet);
2810 assert_eq!(m.heap.view(sequences).data, &[product]);
2811 assert_eq!(m.heap.view(product).data, &[empty, zero]);
2812 let empty_sequence = m.heap.tuple(&[]);
2813 assert_eq!(m.member(empty_sequence, sequences), Ok(true));
2814 let scalar_sequence = m.heap.tuple(&[zero]);
2815 let error = m.member(scalar_sequence, sequences).unwrap_err();
2816 assert_eq!(error.kind(), crate::ErrorKind::Eval);
2817 assert!(error.message().contains("not a function"));
2818 assert_eq!(m.heap.view(sequences).data, &[product]);
2819
2820 let mut values = vec![zero];
2821 let nonempty = m.heap.set_from(&mut values);
2822 let malformed = m.heap.symbolic(Kind::Product, 0, &[nonempty, zero]);
2823 let code = Code {
2824 nodes: vec![
2825 Node::Const(malformed),
2826 Node::Std(StdFn::Seq, vec![0].into()),
2827 ],
2828 ..Code::default()
2829 };
2830 let sequences = m.eval(&code, 1).unwrap();
2831 assert_eq!(m.member(empty_sequence, sequences), Ok(true));
2832 let element = m.heap.tuple(&[zero, zero]);
2833 let nonempty_sequence = m.heap.tuple(&[element]);
2834 let error = m.member(nonempty_sequence, sequences).unwrap_err();
2835 assert_eq!(error.kind(), crate::ErrorKind::Eval);
2836 assert!(error.message().contains("not a set"));
2837 assert_eq!(m.heap.view(sequences).data, &[malformed]);
2838 }
2839 }
2840
2841 #[test]
2842 fn public_cap_shrink_and_memo_move_cannot_add_over_budget_certificates() {
2843 let one = Handle::int(1).unwrap();
2844 let two = Handle::int(2).unwrap();
2845 for warm_first in [false, true] {
2846 let store = Arc::new(Store::with_semantics(true, crate::Semantics::tlc()));
2847 let mut m = Machine::new(
2848 store.clone(),
2849 0,
2850 Opts {
2851 memo_cap: 2048,
2852 ..Opts::default()
2853 },
2854 Memo::new(&[]),
2855 );
2856 let vertex = m.heap.tuple(&[one]);
2857 let set = m.heap.set_from(&mut vec![vertex]);
2858 let set = m.heap.intern_exact(set).unwrap();
2859 let query = m.heap.tuple(&[two]);
2860 if warm_first {
2861 assert_eq!(m.member(query, set), Ok(false));
2862 assert_eq!(m.memo.bytes(), 128);
2863 assert_eq!(Arc::weak_count(&store), 1);
2864 }
2865 m.memo.set_cap(64);
2866 assert_eq!(m.memo.bytes(), 0);
2867 assert_eq!(Arc::weak_count(&store), 0, "release the certificate owner");
2868 let expected = compare::miss(&m.heap, query, m.heap.view(set).data).map(|()| false);
2869 assert_eq!(m.member(query, set), expected);
2870 assert!(m.memo.bytes() <= 64);
2871 assert!(!m.memo.members_active());
2872
2873 let memo = std::mem::take(&mut m.memo);
2874 let mut moved = Machine::new(
2875 store,
2876 0,
2877 Opts {
2878 memo_cap: 64,
2879 ..Opts::default()
2880 },
2881 memo,
2882 );
2883 let query = moved.heap.tuple(&[two]);
2884 assert_eq!(moved.member(query, set), expected);
2885 assert!(moved.memo.bytes() <= 64);
2886 assert!(!moved.heap.poisoned());
2887 }
2888 }
2889
2890 #[test]
2891 fn prepopulated_public_memo_keeps_membership_allocation_within_its_cap() {
2892 let one = Handle::int(1).unwrap();
2893 let two = Handle::int(2).unwrap();
2894 for cap in [2048, 2079, 2112, 4096, 1 << 20, crate::memo::DEFAULT_CAP] {
2895 for (semantics, memo_enabled) in [
2896 (crate::Semantics::tlc(), true),
2897 (crate::Semantics::default(), true),
2898 (crate::Semantics::tlc(), false),
2899 ] {
2900 let mut memo = Memo::new(&[1]);
2901 memo.set_cap(cap);
2902 memo.put(0, &[one], two);
2903 assert_eq!(memo.bytes(), 2048);
2904 let body_bytes = memo.bytes();
2905 let store = Arc::new(Store::with_semantics(true, semantics));
2906 let opts = Opts {
2907 memo_cap: cap,
2908 memo: memo_enabled,
2909 ..Opts::default()
2910 };
2911 let mut m = Machine::new(store, 0, opts, memo);
2912 let vertex = m.heap.tuple(&[one]);
2913 let set = m.heap.set_from(&mut vec![vertex]);
2914 let set = m.heap.intern_exact(set).unwrap();
2915 let query = m.heap.tuple(&[two]);
2916 assert_eq!(m.member(query, set), Ok(false));
2917 assert!(m.memo.bytes() <= cap);
2918 assert_eq!(m.memo.get(0, &[one]), Some(two), "keep the body result");
2919 if cap == 2048 || cap == 2079 || !memo_enabled || !semantics.tlc_comparisons {
2920 assert!(!m.memo.members_active());
2921 assert_eq!(m.memo.bytes(), body_bytes);
2922 } else {
2923 assert!(m.memo.members_active());
2924 assert!(m.memo.bytes() > body_bytes);
2925 if cap == 2112 {
2926 assert_eq!(m.memo.bytes(), 2112, "only 64 bytes remain");
2927 }
2928 }
2929 if cap == 2048 {
2930 m.memo.set_cap(64);
2931 assert_eq!(m.memo.bytes(), body_bytes, "retain existing body storage");
2932 assert_eq!(m.memo.get(0, &[one]), Some(two));
2933 assert_eq!(m.member(query, set), Ok(false));
2934 assert_eq!(m.memo.bytes(), body_bytes, "add no certificate bytes");
2935 }
2936 for i in 1..1000 {
2939 m.memo.put(0, &[Handle::int(i).unwrap()], two);
2940 assert!(m.memo.bytes() <= cap);
2941 }
2942 assert!(!m.heap.poisoned());
2943 }
2944 }
2945 }
2946
2947 #[test]
2948 fn public_heap_replacement_cannot_reuse_another_stores_membership_proof() {
2949 fn values(heap: &mut Heap, name: &str) -> (Handle, Handle) {
2950 let one = Handle::int(1).unwrap();
2951 let model = Handle::model(heap.store().strings().intern(name).unwrap());
2952 let witness = heap.tuple(&[one]);
2953 let witness = heap.intern_exact(witness).unwrap();
2954 let other = heap.tuple(&[model]);
2955 let other = heap.intern_exact(other).unwrap();
2956 let set = heap.set_from(&mut vec![witness, other]);
2957 let set = heap.intern_exact(set).unwrap();
2958 (set, witness)
2959 }
2960
2961 for hashcons in [true, false] {
2962 let store = Arc::new(Store::with_semantics(hashcons, crate::Semantics::tlc()));
2963 let old_owner = Arc::downgrade(&store);
2964 let mut m = Machine::new(store, 0, Opts::default(), Memo::new(&[]));
2965 let (old_set, old_witness) = values(&mut m.heap, "u");
2966 let two = Handle::int(2).unwrap();
2967 let query = m.heap.tuple(&[two]);
2968 assert_eq!(m.member(query, old_set), Ok(false));
2969 assert!(m.memo.bytes() > 0);
2970
2971 let store = Arc::new(Store::with_semantics(hashcons, crate::Semantics::tlc()));
2972 let mut replacement = Heap::new(store, false, false);
2973 let (set, witness) = values(&mut replacement, "T_x");
2974 assert_eq!(old_set, set, "complete set handles collide across stores");
2975 assert_eq!(old_witness, witness, "witness handles also collide");
2976 m.heap = replacement;
2977 assert!(
2978 old_owner.upgrade().is_none(),
2979 "a certificate does not retain Store"
2980 );
2981 let query = m.heap.tuple(&[two]);
2982 let expected = compare::miss(&m.heap, query, m.heap.view(set).data).map(|()| false);
2983 assert!(expected.is_err(), "typed versus integer constraints refuse");
2984 assert_eq!(m.member(query, set), expected, "warm equals the full miss");
2985 assert_eq!(m.memo.bytes(), 0, "rebind drops the old entries");
2986 m.memo.clear();
2987 assert_eq!(m.member(query, set), expected, "cold equals the full miss");
2988 assert!(!m.heap.poisoned());
2989 }
2990 }
2991
2992 #[test]
2993 fn membership_certificates_respect_profiles_epochs_and_machine_stores() {
2994 let one = Handle::int(1).unwrap();
2995 let two = Handle::int(2).unwrap();
2996 for hashcons in [false, true] {
2997 let store = Arc::new(Store::with_semantics(hashcons, crate::Semantics::tlc()));
2998 let opts = Opts {
2999 memo_cap: 512,
3000 ..Opts::default()
3001 };
3002 let mut m = Machine::new(store.clone(), 0, opts, Memo::new(&[]));
3003 let u = Handle::model(store.strings().intern("u").unwrap());
3004 let genesis = m.heap.tuple(&[]);
3005 let vertex = m.heap.tuple(&[u, one]);
3006 let set = m.heap.set_from(&mut vec![genesis, vertex]);
3007 let set = m.heap.intern_exact(set).unwrap();
3008 let query = m.heap.tuple(&[u, two]);
3009 assert_eq!(m.member(query, set), Ok(false));
3010 let vertex = m.memo.member_witness(m.heap.store(), set).unwrap();
3011 assert_eq!(m.memo.bytes(), 32);
3012 m.heap.reset();
3013 let mark = m.heap.mark();
3014 let query = m.heap.tuple(&[u, two]);
3015 assert_eq!(m.member(query, set), Ok(false));
3016 m.heap.rollback(mark);
3017 let query = m.heap.tuple(&[u, two]);
3018 assert_eq!(m.member(query, set), Ok(false));
3019 let ephemeral = m.heap.set_from(&mut vec![query]);
3020 assert_eq!(m.member(vertex, ephemeral), Ok(false));
3021 assert_eq!(m.memo.member_witness(m.heap.store(), ephemeral), None);
3022 assert!(!m.heap.poisoned());
3023
3024 let mut worker = Machine::new(store, 0, opts, Memo::new(&[]));
3025 assert_eq!(worker.memo.member_witness(worker.heap.store(), set), None);
3026 let query = worker.heap.tuple(&[u, two]);
3027 assert_eq!(worker.member(query, set), Ok(false));
3028 assert!(
3029 worker
3030 .memo
3031 .member_witness(worker.heap.store(), set)
3032 .is_some()
3033 );
3034 let reused = std::mem::take(&mut worker.memo);
3035 let other = Arc::new(Store::with_semantics(hashcons, crate::Semantics::tlc()));
3036 let mut worker = Machine::new(other, 0, opts, reused);
3037 assert_eq!(worker.memo.member_witness(worker.heap.store(), set), None);
3038 assert_eq!(worker.memo.bytes(), 0);
3039 }
3040 for (semantics, memo_enabled) in [
3041 (crate::Semantics::default(), true),
3042 (crate::Semantics::tlc(), false),
3043 ] {
3044 let store = Arc::new(Store::with_semantics(true, semantics));
3045 let mut m = Machine::new(
3046 store,
3047 0,
3048 Opts {
3049 memo: memo_enabled,
3050 ..Opts::default()
3051 },
3052 Memo::new(&[]),
3053 );
3054 assert!(!m.memo.members_active());
3055 let vertex = m.heap.tuple(&[one]);
3056 let set = m.heap.set_from(&mut vec![vertex]);
3057 let set = m.heap.intern_exact(set).unwrap();
3058 let query = m.heap.tuple(&[two]);
3059 assert_eq!(m.member(query, set), Ok(false));
3060 assert_eq!(m.memo.bytes(), 0);
3061 }
3062 }
3063
3064 #[test]
3065 fn arithmetic_errors_carry_tlc_classes() {
3066 let exc = |c| Some(TlcClass::eval_exception(c));
3067 for mode in [crate::int::IntMode::Big, crate::int::IntMode::Tlc] {
3068 let mut h =
3069 crate::Heap::new(std::sync::Arc::new(crate::Store::default()), false, false);
3070 h.set_int_mode(mode);
3071 let n = |v| Handle::int(v).unwrap();
3072 let mut class = |op, x, y| h.int_arith(op, n(x), n(y)).unwrap_err().tlc();
3073 assert_eq!(class(IntOp::Div, 1, 0), exc(2179));
3074 assert_eq!(class(IntOp::Mod, 1, 0), exc(2169));
3075 assert_eq!(class(IntOp::Pow, 2, -1), exc(2169));
3076 assert_eq!(class(IntOp::Pow, 0, 0), exc(2180));
3077 }
3078 let mut h = crate::Heap::new(std::sync::Arc::new(crate::Store::default()), false, false);
3079 h.set_int_mode(crate::int::IntMode::Tlc);
3080 let big = h
3081 .int_arith(
3082 IntOp::Mul,
3083 Handle::int(1 << 20).unwrap(),
3084 Handle::int(1 << 20).unwrap(),
3085 )
3086 .unwrap_err();
3087 assert_eq!(big.tlc(), exc(2178));
3088 }
3089}
3090
3091#[cfg(test)]
3092mod recursive_call_bounds {
3093 use super::*;
3094 use std::sync::atomic::{AtomicUsize, Ordering};
3095
3096 #[derive(Debug)]
3097 struct StopAfterOne(AtomicUsize);
3098 impl WorkControl for StopAfterOne {
3099 fn proceed(&self) -> bool {
3100 self.0.fetch_add(1, Ordering::Relaxed) == 0
3101 }
3102 }
3103
3104 #[test]
3105 fn recursive_calls_poll_work_and_restore_depth_and_frames_after_stops()
3106 -> Result<(), Box<dyn std::error::Error>> {
3107 let code = Code {
3108 nodes: vec![Node::Call {
3109 fun: 0,
3110 args: Box::new([]),
3111 }],
3112 funs: vec![crate::plan::Fun {
3113 name: "loop".into(),
3114 params: 0,
3115 frame: 0,
3116 body: 0,
3117 caps: Box::new([]),
3118 }],
3119 ..Default::default()
3120 };
3121 let mut m = Machine::new(
3122 Arc::new(Store::default()),
3123 0,
3124 Opts::default(),
3125 Memo::default(),
3126 );
3127 let control = Arc::new(StopAfterOne(AtomicUsize::new(0)));
3128 m.set_work_control(Some(control.clone()));
3129 let stopped = m.eval(&code, 0).err().ok_or("expected cooperative stop")?;
3130 assert_eq!(stopped.kind(), crate::ErrorKind::Stop);
3131 assert_eq!(control.0.load(Ordering::Relaxed), 2);
3132 assert_eq!(m.depth, 0);
3133 assert_eq!(m.frame, Vec::<Handle>::new());
3134 m.set_work_control(None);
3135 let bounded = m.eval(&code, 0).err().ok_or("expected depth refusal")?;
3136 assert_eq!(bounded.kind(), crate::ErrorKind::Unsupported);
3137 assert!(bounded.message().contains("recursive-call depth limit"));
3138 assert_eq!(m.depth, 0);
3139 assert_eq!(m.frame, Vec::<Handle>::new());
3140 Ok(())
3141 }
3142}
3143
3144#[cfg(test)]
3145mod thunk_rollback {
3146 #![allow(clippy::unwrap_used, reason = "tests")]
3147 use super::*;
3148
3149 fn code() -> Code {
3151 Code {
3152 nodes: vec![
3153 Node::Var(0),
3154 Node::Tuple(Box::new([0, 0])),
3155 Node::Lazy { slot: 0, body: 1 },
3156 ],
3157 ..Default::default()
3158 }
3159 }
3160
3161 fn machine() -> Machine {
3162 let mut m = Machine::new(
3163 Arc::new(Store::default()),
3164 1,
3165 Opts::default(),
3166 Memo::default(),
3167 );
3168 m.s0[0] = Handle::int(1).unwrap();
3169 m
3170 }
3171
3172 #[test]
3173 fn a_thunk_forced_in_a_left_frame_releases_the_rollback() {
3174 let code = code();
3175 let mut m = machine();
3176 let outer = m.enter(1);
3177 let before = m.heap.mark();
3178 let since = m.thunk_mark();
3179 let inner = m.enter(1);
3180 let v = m.eval(&code, 2).unwrap();
3181 assert!(v.is_transient());
3182 assert!(!m.thunks_released(since));
3184 m.leave(inner);
3185 assert!(m.thunks_released(since));
3186 m.heap.rollback(before);
3187 assert!(!m.heap.poisoned());
3188 let w = m.eval(&code, 2).unwrap();
3190 assert!(compare::equals(&m.heap, w, w).unwrap());
3191 assert!(!m.heap.poisoned());
3192 m.leave(outer);
3193 }
3194
3195 #[test]
3196 fn a_thunk_forced_in_a_live_frame_keeps_the_values_it_holds() {
3197 let code = code();
3198 let mut m = machine();
3199 let outer = m.enter(1);
3200 let since = m.thunk_mark();
3201 let v = m.eval(&code, 2).unwrap();
3202 let inner = m.enter(1);
3203 m.leave(inner);
3204 assert!(!m.thunks_released(since));
3206 assert!(!m.thunks_released(0));
3208 let later = m.thunk_mark();
3209 assert!(m.thunks_released(later));
3210 assert_eq!(m.eval(&code, 2).unwrap(), v);
3211 assert!(!m.heap.poisoned());
3212 m.leave(outer);
3213 assert!(m.thunks_released(0));
3215 }
3216
3217 #[test]
3218 fn a_released_inner_scope_keeps_the_enclosing_scopes_live_slots() {
3219 let code = code();
3220 let mut m = machine();
3221 let outer = m.enter(1);
3222 let since = m.thunk_mark();
3223 m.eval(&code, 2).unwrap();
3224 let inner_since = m.thunk_mark();
3225 let inner = m.enter(1);
3226 m.eval(&code, 2).unwrap();
3227 m.leave(inner);
3228 assert!(m.thunks_released(inner_since));
3229 assert!(!m.thunks_released(since));
3230 m.leave(outer);
3231 }
3232}
3233
3234#[cfg(test)]
3235mod work_poll_bound {
3236 use super::*;
3237 use std::sync::atomic::{AtomicUsize, Ordering};
3238
3239 #[derive(Debug)]
3241 struct Allow {
3242 allow: usize,
3243 polls: AtomicUsize,
3244 }
3245 impl WorkControl for Allow {
3246 fn proceed(&self) -> bool {
3247 self.polls.fetch_add(1, Ordering::Relaxed) < self.allow
3248 }
3249 }
3250
3251 fn machine(allow: usize) -> (Machine, Arc<Allow>) {
3252 let mut m = Machine::new(
3253 Arc::new(Store::default()),
3254 0,
3255 Opts::default(),
3256 Memo::default(),
3257 );
3258 let control = Arc::new(Allow {
3259 allow,
3260 polls: AtomicUsize::new(0),
3261 });
3262 m.set_work_control(Some(control.clone()));
3263 (m, control)
3264 }
3265
3266 fn polls(control: &Allow) -> usize {
3267 control.polls.load(Ordering::Relaxed)
3268 }
3269
3270 #[test]
3271 fn the_first_charge_after_installation_polls() {
3272 let (mut m, control) = machine(0);
3273 let error = m.charge(1).err();
3274 assert!(error.is_some_and(|e| e.kind() == crate::ErrorKind::Stop));
3275 assert_eq!(polls(&control), 1);
3276 assert!(m.heap.work_interrupted());
3277 }
3278
3279 #[test]
3280 fn a_stop_is_seen_within_the_documented_unit_bound() {
3281 let units = usize::try_from(WORK_POLL_UNITS).unwrap_or(usize::MAX);
3282 for n in [0, 1, 3] {
3283 let (mut m, control) = machine(1);
3284 let mut charged = 0usize;
3285 let mut calls = 0usize;
3286 let stopped = loop {
3287 let result = m.charge(n);
3288 calls += 1;
3289 if let Err(error) = result {
3290 break error;
3291 }
3292 charged += n.max(1);
3293 assert!(calls <= units + 1, "no stop within the bound (n={n})");
3294 };
3295 assert_eq!(stopped.kind(), crate::ErrorKind::Stop);
3296 assert_eq!(polls(&control), 2);
3297 assert!(charged < units + n.max(1), "n={n} charged={charged}");
3300 assert!(calls <= units + 1, "n={n} calls={calls}");
3301 for _ in 0..3 {
3303 assert!(m.charge(1).is_err());
3304 }
3305 assert_eq!(polls(&control), 5);
3306 }
3307 }
3308
3309 #[test]
3310 fn a_large_charge_polls_before_its_work() {
3311 let (mut m, control) = machine(1);
3312 assert_eq!(m.charge(1), Ok(()));
3313 let big = usize::try_from(WORK_POLL_UNITS).unwrap_or(usize::MAX);
3314 let error = m.charge(big).err();
3315 assert!(error.is_some_and(|e| e.kind() == crate::ErrorKind::Stop));
3316 assert_eq!(polls(&control), 2);
3317 }
3318
3319 #[test]
3320 fn bounded_fuel_and_transients_are_checked_on_every_charge_and_polled_on_the_bound() {
3321 let units = usize::try_from(WORK_POLL_UNITS).unwrap_or(usize::MAX);
3322 let (mut m, control) = machine(usize::MAX);
3323 assert_eq!(m.charge(1), Ok(()));
3324 m.set_fuel(10);
3325 for spent in 1..=10 {
3326 assert_eq!(m.charge(1), Ok(()));
3327 assert_eq!(m.fuel, 10 - spent);
3328 }
3329 let error = m.charge(1).err();
3330 assert!(error.is_some_and(|e| e.kind() == crate::ErrorKind::Unsupported));
3331 assert_eq!(polls(&control), 1);
3332 m.set_fuel(u64::MAX);
3333 m.heap.tuple(&[Handle::TRUE]);
3334 m.set_transient_bound(0);
3335 let error = m.charge(1).err();
3336 assert!(error.is_some_and(|e| e.kind() == crate::ErrorKind::Unsupported));
3337 m.set_transient_bound(usize::MAX);
3338 for _ in 13..units {
3341 assert_eq!(m.charge(1), Ok(()));
3342 }
3343 assert_eq!(polls(&control), 1);
3344 assert_eq!(m.charge(1), Ok(()));
3345 assert_eq!(polls(&control), 2);
3346 m.set_fuel(u64::MAX - 1);
3348 for _ in 1..units {
3349 assert_eq!(m.charge(1), Ok(()));
3350 }
3351 assert_eq!(polls(&control), 2);
3352 assert_eq!(m.charge(1), Ok(()));
3353 assert_eq!(polls(&control), 3);
3354 }
3355
3356 #[test]
3357 fn reinstalling_a_control_polls_at_once() {
3358 let (mut m, control) = machine(usize::MAX);
3359 assert_eq!(m.charge(1), Ok(()));
3360 assert_eq!(polls(&control), 1);
3361 let deny = Arc::new(Allow {
3362 allow: 0,
3363 polls: AtomicUsize::new(0),
3364 });
3365 m.set_work_control(Some(deny.clone()));
3366 assert!(m.charge(1).is_err());
3367 assert_eq!(polls(&deny), 1);
3368 }
3369}
3370
3371#[cfg(test)]
3372mod bounded_analysis_machine {
3373 #![allow(clippy::unwrap_used, reason = "tests")]
3374 use super::*;
3375 use crate::plan::MemoSite;
3376
3377 fn memo_code(step: bool) -> Code {
3378 Code {
3379 nodes: vec![
3380 Node::Const(Handle::int(7).unwrap()),
3381 Node::Memo { site: 0, body: 0 },
3382 ],
3383 sites: vec![MemoSite {
3384 name: "site".into(),
3385 vars: Box::new([0]),
3386 slots: Box::new([]),
3387 primed: Box::new([]),
3388 step,
3389 candidate: false,
3390 }],
3391 ..Default::default()
3392 }
3393 }
3394
3395 fn machine(memo_on: bool, memo: Memo) -> Machine {
3396 let opts = Opts {
3397 memo: memo_on,
3398 step_memo: memo_on,
3399 ..Opts::default()
3400 };
3401 let mut m = Machine::new(Arc::new(Store::default()), 1, opts, memo);
3402 m.s0[0] = Handle::int(1).unwrap();
3403 m
3404 }
3405
3406 #[test]
3407 fn memo_off_machines_evaluate_memo_bodies_without_reading_or_filling_a_site() {
3408 let mut on = machine(true, Memo::new(&[1]));
3410 assert_eq!(
3411 on.eval(&memo_code(false), 1).unwrap(),
3412 Handle::int(7).unwrap()
3413 );
3414 assert_eq!(on.memo.stats()[0].lookups, 1);
3415 assert!(on.memo.bytes() > 0);
3416 let mut off = machine(false, Memo::new(&[1]));
3418 for _ in 0..2 {
3419 assert_eq!(
3420 off.eval(&memo_code(false), 1).unwrap(),
3421 Handle::int(7).unwrap()
3422 );
3423 }
3424 assert_eq!(off.memo.stats()[0].lookups, 0);
3425 assert_eq!(off.memo.bytes(), 0);
3426 let mut analysis = machine(false, Memo::default());
3429 for step in [false, true] {
3430 assert_eq!(
3431 analysis.eval(&memo_code(step), 1).unwrap(),
3432 Handle::int(7).unwrap()
3433 );
3434 }
3435 assert_eq!(analysis.memo.stats(), Vec::new());
3436 assert_eq!(analysis.memo.bytes(), 0);
3437 }
3438
3439 #[test]
3440 fn bounded_machines_precharge_big_powers_before_allocating() {
3441 let pow = |x: i64, y: i64| Code {
3442 nodes: vec![
3443 Node::Const(Handle::int(x).unwrap()),
3444 Node::Const(Handle::int(y).unwrap()),
3445 Node::Arith(Arith::Pow, 0, 1),
3446 ],
3447 ..Default::default()
3448 };
3449 let mut m = machine(false, Memo::default());
3450 m.set_fuel(1000);
3452 let nodes = m.heap.arena().peak().0;
3453 let error = m.eval(&pow(3, 100_000), 2).unwrap_err();
3454 assert_eq!(error.kind(), crate::ErrorKind::Unsupported);
3455 assert!(m.fuel_exhausted());
3456 assert_eq!(m.heap.arena().peak().0, nodes, "no digits allocated");
3457 m.set_fuel(1 << 20);
3459 let big = m.eval(&pow(3, 100_000), 2).unwrap();
3460 assert_eq!(
3461 m.heap.big(big).unwrap(),
3462 num_traits::Pow::pow(num_bigint::BigInt::from(3), 100_000_u32)
3463 );
3464 assert!(!m.fuel_exhausted());
3465 m.set_fuel(4);
3467 assert_eq!(m.eval(&pow(2, 10), 2).unwrap(), Handle::int(1024).unwrap());
3468 m.heap.set_int_mode(crate::int::IntMode::Tlc);
3469 m.set_fuel(4);
3470 assert_eq!(m.eval(&pow(2, 10), 2).unwrap(), Handle::int(1024).unwrap());
3471 }
3472}
3473
3474#[cfg(test)]
3475mod same_vars {
3476 #![allow(clippy::unwrap_used, reason = "tests")]
3477 use super::*;
3478
3479 fn code() -> Code {
3482 Code {
3483 nodes: vec![
3484 Node::Var(0),
3485 Node::Var(1),
3486 Node::Var(2),
3487 Node::Tuple(Box::new([1, 2])),
3488 Node::Tuple(Box::new([0, 3])),
3489 Node::Lazy { slot: 0, body: 4 },
3490 Node::Primed(0),
3491 Node::Primed(1),
3492 Node::Eq(5, 13),
3493 Node::Primed(2),
3494 Node::Tuple(Box::new([7, 9])),
3495 Node::Tuple(Box::new([6, 10])),
3496 Node::Lazy { slot: 1, body: 11 },
3497 Node::Lazy { slot: 2, body: 12 },
3498 Node::Const(Handle::TRUE),
3499 Node::SameVars {
3500 eq: 8,
3501 leaves: Box::new([(0, 1), (1, 2), (2, 2)]),
3502 thunks: Box::new([0, 1, 2]),
3503 },
3504 ],
3505 ..Default::default()
3506 }
3507 }
3508
3509 fn values(m: &mut Machine) -> Vec<Handle> {
3510 let one = Handle::int(1).unwrap();
3511 let two = Handle::int(2).unwrap();
3512 let text = m.heap.string("a").unwrap();
3513 let set = m.heap.set_enum(&[one, two]);
3514 let set = m.heap.intern(set).unwrap();
3515 let other = m.heap.set_enum(&[one]);
3516 let other = m.heap.intern(other).unwrap();
3517 let fcn = m.heap.int_fcn(1, &[set, text]);
3518 let fcn = m.heap.intern_exact(fcn).unwrap();
3519 let interval = m.heap.interval(1, 2);
3521 let interval = m.heap.intern_exact(interval).unwrap();
3522 vec![one, two, text, set, other, fcn, interval, Handle::EMPTY]
3523 }
3524
3525 fn agrees(semantics: crate::store::Semantics) {
3528 let code = code();
3529 let store = Arc::new(Store::with_semantics(true, semantics));
3530 let mut m = Machine::new(store, 3, Opts::default(), Memo::default());
3531 let values = values(&mut m);
3532 let pick = |i: usize| values[i % values.len()];
3533 let mut checked = 0;
3534 for i in 0..values.len().pow(2) {
3535 let (a, b) = (i % values.len(), i / values.len());
3536 for row in [[a, a, b], [a, b, b], [b, a, a], [a, a, a]] {
3537 let before: Vec<_> = row.iter().map(|&k| pick(k)).collect();
3538 for after in [before.clone(), vec![pick(b), before[1], before[2]]] {
3539 m.s0.copy_from_slice(&before);
3540 m.s1.copy_from_slice(&after);
3541 let frame = m.enter(3);
3542 let eq = m.eval(&code, 8).map_err(|e| e.kind());
3543 m.leave(frame);
3544 let frame = m.enter(3);
3545 let same = m.eval(&code, 15).map_err(|e| e.kind());
3546 m.leave(frame);
3547 assert_eq!(same, eq, "{before:?} {after:?}");
3548 let proven: Vec<_> = before
3551 .iter()
3552 .chain(&after)
3553 .copied()
3554 .filter(|&h| m.heap.materialized_within(&[h], 4096, None))
3555 .collect();
3556 let keep = |row: &[Handle]| -> Vec<Handle> {
3557 row.iter()
3558 .map(|&h| {
3559 if proven.contains(&h) {
3560 h
3561 } else {
3562 Handle::EMPTY
3563 }
3564 })
3565 .collect()
3566 };
3567 m.set_proven_materialized(&keep(&before), &keep(&after), []);
3568 let frame = m.enter(3);
3569 let reused = m.eval(&code, 15).map_err(|e| e.kind());
3570 m.leave(frame);
3571 m.set_proven_materialized(&[], &[], []);
3572 assert_eq!(reused, eq, "{before:?} {after:?} with proofs");
3573 checked += 1;
3574 }
3575 }
3576 }
3577 assert!(checked > 100);
3578 assert!(!m.heap.poisoned());
3579 }
3580
3581 #[test]
3585 fn membership_reuses_only_recorded_proofs() {
3586 let store = Arc::new(Store::default());
3587 let mut m = Machine::new(store, 2, Opts::default(), Memo::default());
3588 m.set_fuel(1 << 30);
3590 let one = Handle::int(1).unwrap();
3591 let two = Handle::int(2).unwrap();
3592 let inner = m.heap.set_from(&mut vec![one, two]);
3595 let inner = m.heap.unmarked_copy(inner);
3596 let single = m.heap.set_from(&mut vec![one]);
3597 let single = m.heap.unmarked_copy(single);
3598 let outer = m.heap.set_from(&mut vec![inner, single]);
3599 let outer = m.heap.unmarked_copy(outer);
3600 let other = m.heap.set_from(&mut vec![two]);
3601 let other = m.heap.unmarked_copy(other);
3602 let interval = m.heap.interval(1, 2);
3603 let interval = m.heap.intern_exact(interval).unwrap();
3604 let lazy = m.heap.set_from(&mut vec![interval]);
3605 let lazy = m.heap.unmarked_copy(lazy);
3606 for h in [inner, single, outer, other] {
3607 assert!(!m.heap.proved_concrete(h));
3608 assert!(m.heap.materialized_within(&[h], 64, None));
3609 }
3610 assert!(!m.heap.materialized_within(&[lazy], 64, None));
3611 let cases = [(inner, outer), (other, outer), (one, inner), (two, single)];
3612 for (x, set) in cases {
3613 m.set_proven_materialized(&[], &[], []);
3614 let plain = m.member(x, set).map_err(|e| e.kind());
3615 assert!(plain.is_ok(), "{x:?} {set:?} {plain:?}");
3616 m.set_proven_materialized(&[x], &[set], []);
3617 assert_eq!(m.member(x, set).map_err(|e| e.kind()), plain);
3618 m.set_proven_materialized(&[], &[], [x, set]);
3619 assert_eq!(m.member(x, set).map_err(|e| e.kind()), plain);
3620 }
3621 assert_eq!(m.member(inner, outer).ok(), Some(true));
3622 assert_eq!(m.member(other, outer).ok(), Some(false));
3623 assert_eq!(m.member(two, single).ok(), Some(false));
3624 m.set_proven_materialized(&[], &[], []);
3627 let refused = m.member(lazy, outer).map_err(|e| e.kind());
3628 assert!(refused.is_err());
3629 m.set_proven_materialized(&[outer], &[], []);
3630 assert_eq!(m.member(lazy, outer).map_err(|e| e.kind()), refused);
3631 m.set_proven_materialized(&[], &[], []);
3632 assert!(!m.heap.poisoned());
3633 }
3634
3635 #[test]
3636 fn same_vars_agrees_with_the_tuple_equality_it_wraps() {
3637 agrees(crate::store::Semantics::default());
3638 agrees(crate::store::Semantics::tlc());
3639 }
3640
3641 #[test]
3642 fn a_forced_thunk_is_read_as_the_tuple_equality_reads_it() {
3643 let code = code();
3644 let mut m = Machine::new(
3645 Arc::new(Store::default()),
3646 3,
3647 Opts::default(),
3648 Memo::default(),
3649 );
3650 let one = Handle::int(1).unwrap();
3651 let two = Handle::int(2).unwrap();
3652 m.s0.copy_from_slice(&[one, one, one]);
3653 m.s1.copy_from_slice(&[one, one, one]);
3654 let frame = m.enter(3);
3655 let stale = m.heap.tuple(&[two, two]);
3657 m.set_slot(0, stale);
3658 assert_eq!(m.eval(&code, 15).unwrap(), Handle::FALSE);
3659 for slot in 0..3 {
3660 m.set_slot(slot, Handle::EMPTY);
3661 }
3662 assert_eq!(m.eval(&code, 15).unwrap(), Handle::TRUE);
3663 assert!((0..3).all(|slot| m.slot(slot).is_empty()));
3665 m.s1[2] = two;
3666 assert_eq!(m.eval(&code, 15).unwrap(), Handle::FALSE);
3667 assert!((0..3).all(|slot| m.slot(slot).is_empty()));
3668 m.leave(frame);
3669 }
3670}