1#![forbid(unsafe_code)]
28
29mod candidate;
30pub mod checkpoint;
31pub mod distributed;
32pub mod ending;
33#[cfg(test)]
34mod exact_identity_tests;
35pub mod graph;
36mod parallel;
37mod reclaim;
38pub mod sample;
39pub mod storage;
40pub mod trace;
41
42use std::sync::Arc;
43use std::time::{Duration, Instant};
44
45use dive_core::handle::{K_STATE, fin, state_term};
46use dive_core::memo::{Memo, SiteStats};
47use dive_core::plan::{Check, Code};
48use dive_core::store::{StoreMemory, StoreStats};
49use dive_core::{Error, ErrorKind, Handle, Machine, Opts, Plan, Sink, Store};
50use dive_store::predecessor::PredecessorLog;
51use dive_store::trace::StateId;
52
53pub use ending::{Failure, Replayed, Site};
54pub use trace::TraceState;
55
56#[derive(Clone, Debug, PartialEq, Eq)]
58pub enum Verdict {
59 Success,
61 InvariantViolated {
63 property: String,
65 initial: bool,
67 },
68 Deadlock,
70 NoNextAction,
73 PropertyViolatedInitially {
76 property: String,
78 },
79 ActionPropertyViolated {
81 property: String,
83 },
84 Failed,
87 Unsupported {
89 feature: String,
91 },
92 Budget,
94 Admission {
96 limit: Limit,
98 max: u64,
100 observed: u64,
103 },
104 GraphStop,
107 PrefixStop {
110 level: u64,
112 },
113 CheckpointPaused {
115 next_level: u64,
117 },
118 CheckpointError {
120 message: String,
122 },
123 Internal {
125 message: String,
127 },
128}
129
130#[derive(Clone, Copy, Debug, PartialEq, Eq)]
132pub enum Limit {
133 States,
135 Depth,
137}
138
139#[derive(Clone, Copy, Debug, Default, PartialEq, Eq)]
141pub struct Stats {
142 pub generated: u64,
144 pub distinct: u64,
146 pub depth: u64,
148 pub left_on_queue: u64,
150 pub initial_generated: u64,
152}
153
154#[derive(Clone, Debug, Default)]
156pub struct Metrics {
157 pub distributed: Option<distributed::Usage>,
159 pub storage: storage::Usage,
161 pub discarded_before_intern: u64,
163 pub probed: u64,
165 pub conjuncts_total: u64,
167 pub conjuncts_skipped: u64,
169 pub store: StoreStats,
171 pub store_memory: StoreMemory,
174 pub memo: Vec<(String, SiteStats)>,
176 pub arena_peak: (usize, usize),
178 pub thunks: (u64, u64),
180 pub explore_time: Duration,
182 pub expand_time: Duration,
185 pub commit_time: Duration,
187}
188
189#[derive(Clone, Debug)]
191pub struct Outcome {
192 pub verdict: Verdict,
194 pub stats: Stats,
196 pub metrics: Metrics,
198 pub warnings: Vec<(u16, u32)>,
201 pub trace: Option<Result<Vec<TraceState>, String>>,
205 pub failure: Option<Failure>,
207 pub in_init: bool,
209 pub expanded: bool,
212 pub replayed: Option<Replayed>,
215 pub sampled: Vec<sample::SampledState>,
218 pub printed: Vec<String>,
221}
222
223#[derive(Clone, Copy, Debug)]
225pub struct Config {
226 pub opts: Opts,
228 pub max_states: Option<u64>,
230 pub max_depth: Option<u64>,
232 pub workers: usize,
234 pub warn: bool,
237 pub sample: Option<sample::Sample>,
239}
240
241#[derive(Debug)]
243pub struct Seen {
244 table: Vec<u64>,
245 len: usize,
246 exact: Option<storage::Exact>,
247 #[cfg(test)]
249 collide_keys: Option<u64>,
250}
251
252impl Default for Seen {
253 fn default() -> Self {
254 Self {
255 table: vec![0; 1 << 16],
256 len: 0,
257 exact: None,
258 #[cfg(test)]
259 collide_keys: None,
260 }
261 }
262}
263
264impl Seen {
265 fn with_detached_exact(exact: bool, detached: bool) -> Self {
266 Self {
267 exact: exact.then(|| {
268 if detached {
269 storage::Exact::detached()
270 } else {
271 storage::Exact::default()
272 }
273 }),
274 ..Self::default()
275 }
276 }
277
278 fn empty_like(&self) -> Self {
279 Self {
280 #[cfg(test)]
281 collide_keys: self.collide_keys,
282 ..Self::with_detached_exact(
283 self.exact.is_some(),
284 self.exact.as_ref().is_some_and(storage::Exact::is_detached),
285 )
286 }
287 }
288
289 #[cfg(test)]
292 fn key(&self, key: u64) -> u64 {
293 self.collide_keys.unwrap_or(key)
294 }
295
296 #[cfg(not(test))]
299 #[inline]
300 #[allow(clippy::unused_self, reason = "the test build reads a key override")]
301 const fn key(&self, key: u64) -> u64 {
302 key
303 }
304
305 fn contains_row(
306 &self,
307 key: u64,
308 row: &[Handle],
309 heap: &dive_core::Heap,
310 poll: &(dyn Fn() -> bool + Sync),
311 ) -> Result<bool, Error> {
312 self.exact.as_ref().map_or_else(
313 || Ok(self.contains(key)),
314 |exact| exact.contains_controlled(key, row, heap, poll),
315 )
316 }
317
318 fn insert_row(
320 &mut self,
321 key: u64,
322 row: &[Handle],
323 heap: &dive_core::Heap,
324 id: u64,
325 poll: &(dyn Fn() -> bool + Sync),
326 ) -> Result<storage::Inserted, Error> {
327 if let Some(exact) = &mut self.exact {
328 exact.insert_controlled(key, row, heap, id, poll)
329 } else if self.insert(key) {
330 Ok(storage::Inserted::New)
331 } else {
332 Ok(storage::Inserted::Seen(None))
333 }
334 }
335
336 fn fix(k: u64) -> u64 {
337 if k == 0 { 1 } else { k }
338 }
339
340 fn mask(&self) -> usize {
341 self.table.len() - 1
342 }
343
344 #[allow(clippy::cast_possible_truncation, reason = "masked to the table size")]
345 fn start(&self, k: u64) -> usize {
346 (k as usize) & self.mask()
347 }
348
349 #[must_use]
351 pub fn contains(&self, k: u64) -> bool {
352 let k = Self::fix(k);
353 let mut i = self.start(k);
354 loop {
355 match self.table[i] {
356 0 => return false,
357 x if x == k => return true,
358 _ => i = (i + 1) & self.mask(),
359 }
360 }
361 }
362
363 pub fn insert(&mut self, k: u64) -> bool {
365 if (self.len + 1) * 4 > self.table.len() * 3 {
366 self.grow();
367 }
368 let k = Self::fix(k);
369 let mut i = self.start(k);
370 loop {
371 match self.table[i] {
372 0 => {
373 self.table[i] = k;
374 self.len += 1;
375 return true;
376 }
377 x if x == k => return false,
378 _ => i = (i + 1) & self.mask(),
379 }
380 }
381 }
382
383 fn grow(&mut self) {
384 let size = self.table.len() * 2;
385 let old = std::mem::replace(&mut self.table, vec![0; size]);
386 for k in old.into_iter().filter(|&k| k != 0) {
387 let mut i = self.start(k);
388 while self.table[i] != 0 {
389 i = (i + 1) & self.mask();
390 }
391 self.table[i] = k;
392 }
393 }
394
395 #[must_use]
397 pub fn len(&self) -> usize {
398 self.len
399 }
400
401 #[must_use]
403 pub fn is_empty(&self) -> bool {
404 self.len == 0
405 }
406}
407
408fn state_identity(
415 m: &mut Machine,
416 plan: &Plan,
417 identity: Option<&mut Vec<Handle>>,
418) -> Result<u64, Error> {
419 if let Some(view) = &plan.view {
420 return view_key(m, plan, view, identity);
421 }
422 let image;
423 let state: &[Handle] = match &plan.symmetry {
424 Some(sym) => {
425 let mut out = Vec::with_capacity(m.s1.len());
426 let s1 = m.s1.clone();
427 sym.canonical_from(&mut m.heap, &s1, &m.s0, &mut out)?;
429 image = out;
430 &image
431 }
432 None => &m.s1,
433 };
434 let mut sum = 0u64;
435 for (i, &h) in state.iter().enumerate() {
436 sum = sum.wrapping_add(state_term(i, m.heap.hash(h)));
437 }
438 if let Some(identity) = identity {
439 capture_reserve(identity, state.len())?;
440 if m.heap.is_speculative() {
441 identity.extend(m.heap.close_identity_row_local(state)?);
442 } else {
443 for &handle in state {
444 identity.push(m.heap.intern(handle)?);
445 }
446 }
447 }
448 Ok(fin(K_STATE, state.len() as u64, sum))
449}
450
451fn view_key(
458 m: &mut Machine,
459 plan: &Plan,
460 view: &Check,
461 identity: Option<&mut Vec<Handle>>,
462) -> Result<u64, Error> {
463 let Some(conj) = view.conjuncts.first() else {
464 return Err(Error::internal("a VIEW without its expression"));
465 };
466 if !fingerprintable(m, true)? {
467 return Err(Error::unsupported(
468 "a VIEW over a state holding an infinite or lazily represented set (core)",
469 ));
470 }
471 let image = match &plan.symmetry {
474 Some(sym) => {
475 let mut out = Vec::with_capacity(m.s1.len());
476 let s1 = m.s1.clone();
477 sym.canonical_from(&mut m.heap, &s1, &m.s0, &mut out)?;
479 Some(out)
480 }
481 None => None,
482 };
483 let saved = if let Some(image) = image {
485 Some(std::mem::replace(&mut m.s0, image))
486 } else {
487 std::mem::swap(&mut m.s0, &mut m.s1);
488 None
489 };
490 let old = m.enter(view.frame);
491 let r = m.eval_norm(&plan.code, conj.p);
492 m.leave(old);
493 if let Some(s0) = saved {
494 m.s0 = s0;
495 } else {
496 std::mem::swap(&mut m.s0, &mut m.s1);
497 }
498 let v = m.heap.state_identity(r?)?;
499 if !closed_fingerprintable(&m.heap, v) {
500 return Err(Error::unsupported(
501 "a VIEW value holding an infinite or lazily represented set (core)",
502 ));
503 }
504 if let Some(identity) = identity {
505 capture_reserve(identity, 1)?;
506 identity.push(v);
507 }
508 Ok(fin(K_STATE, 1, state_term(0, m.heap.hash(v))))
509}
510
511pub(crate) fn capture_reserve<T>(values: &mut Vec<T>, additional: usize) -> Result<(), Error> {
514 values
515 .len()
516 .checked_add(additional)
517 .and_then(|n| n.checked_mul(std::mem::size_of::<T>()))
518 .ok_or_else(|| Error::unsupported("capture buffer address space"))?;
519 values
520 .try_reserve(additional)
521 .map_err(|_| Error::unsupported("capture buffer allocation"))
522}
523
524pub(crate) fn capture_copy(values: &[Handle]) -> Result<Vec<Handle>, Error> {
525 let mut copy = Vec::new();
526 capture_reserve(&mut copy, values.len())?;
527 copy.extend_from_slice(values);
528 Ok(copy)
529}
530
531struct Explorer<'p> {
532 plan: &'p Plan,
533 graph: Option<&'p mut dyn graph::GraphSink>,
535 stats: Stats,
536 metrics: Metrics,
537 seen: Seen,
538 disk: Option<storage::Disk>,
539 checkpoint: Option<&'p mut checkpoint::Session>,
540 distributed: Option<&'p distributed::Coordinator>,
541 next: Vec<Handle>,
542 frontier: Option<storage::Frontiers>,
544 candidates: Option<candidate::Account>,
545 candidate_storage: storage::Storage,
546 next_originals: Vec<Handle>,
549 emitted: u64,
550 initial: bool,
551 changed: u64,
554 level: u64,
556 expanded: bool,
559 opts: Opts,
560 stop: Option<Verdict>,
561 action: Option<usize>,
563 init_action: Option<usize>,
565 log: PredecessorLog,
567 next_ids: Vec<StateId>,
569 cur_id: Option<StateId>,
571 predicted: Option<StateId>,
574 end: Option<End>,
577 in_model: bool,
579 action_start: u64,
581 failure: Option<Failure>,
583 poll: &'p (dyn Fn() -> bool + Sync),
586 max_states: Option<u64>,
587 max_depth: Option<u64>,
588 warnings: Vec<(u16, u32)>,
591}
592
593#[derive(Clone, Copy, Debug)]
595enum Recorded {
596 New,
598 Seen(Option<StateId>),
600}
601
602struct End {
604 upto: Option<StateId>,
606 last: Option<(Option<usize>, Vec<Handle>)>,
609 expect: Vec<Handle>,
612}
613
614enum Probe {
615 Seen(Option<StateId>),
617 New,
618}
619
620impl Explorer<'_> {
621 fn seen_contains(
622 &mut self,
623 key: u64,
624 row: &[Handle],
625 heap: &dive_core::Heap,
626 phase: (&'static str, Option<u64>),
627 ) -> Result<bool, Error> {
628 let exact = self.seen.exact.is_some();
629 let position = (
630 phase.0,
631 self.stats.generated,
632 self.cur_id,
633 phase.1.unwrap_or_else(|| self.emitted.saturating_sub(1)),
634 );
635 self.disk.as_mut().map_or_else(
636 || self.seen.contains_row(key, row, heap, self.poll),
637 |disk| disk.operation(exact, key, row, heap, false, position, self.poll),
638 )
639 }
640
641 fn seen_insert(
645 &mut self,
646 key: u64,
647 row: &[Handle],
648 heap: &dive_core::Heap,
649 phase: (&'static str, Option<u64>),
650 ) -> Result<storage::Inserted, Error> {
651 let exact = self.seen.exact.is_some();
652 let position = (
653 phase.0,
654 self.stats.generated,
655 self.cur_id,
656 phase.1.unwrap_or_else(|| self.emitted.saturating_sub(1)),
657 );
658 if let Some(disk) = &mut self.disk {
659 return disk
660 .operation(exact, key, row, heap, true, position, self.poll)
661 .map(|new| {
662 if new {
663 storage::Inserted::New
664 } else {
665 storage::Inserted::Seen(None)
666 }
667 });
668 }
669 if !exact {
670 return self.seen.insert_row(key, row, heap, 0, self.poll);
671 }
672 if self.predicted.is_some() {
673 return Err(Error::internal(
674 "an exact discovery id was recorded for a state that was never logged",
675 ));
676 }
677 let predicted = self.log.len();
678 let inserted = self.seen.insert_row(key, row, heap, predicted, self.poll)?;
679 if inserted.is_new() {
680 self.predicted = Some(predicted);
681 }
682 Ok(inserted)
683 }
684
685 fn confirm_logged(&mut self, id: StateId) -> Result<(), Error> {
688 match self.predicted.take() {
689 Some(predicted) if predicted != id => Err(Error::internal(format!(
690 "the exact seen set recorded discovery id {predicted} for a state logged as {id}"
691 ))),
692 None if self.seen.exact.is_some() && self.disk.is_none() => Err(Error::internal(
693 "a state was logged without its exact discovery id",
694 )),
695 _ => Ok(()),
696 }
697 }
698
699 fn queued_states(&self) -> usize {
700 if self.plan.vars.is_empty() {
701 return 0;
702 }
703 self.frontier.as_ref().map_or_else(
704 || self.next.len() / self.plan.vars.len(),
705 storage::Frontiers::next_len,
706 )
707 }
708
709 fn advance_frontier(&mut self) -> Result<(), Error> {
710 let queued = self.queued_states();
711 if let Some(frontier) = &mut self.frontier {
712 match frontier.advance(self.poll) {
713 Ok(true) => {}
714 Ok(false) => {
715 self.stats.left_on_queue = queued as u64;
716 self.stop = Some(Verdict::Budget);
717 return Err(Error::stop());
718 }
719 Err(error) => {
720 self.stats.left_on_queue = queued as u64;
721 return Err(error);
722 }
723 }
724 }
725 Ok(())
726 }
727
728 fn check(&mut self, m: &mut Machine, code: &Code, c: &Check) -> Result<bool, Error> {
730 let skip = self.opts.parent_skip && !self.initial;
731 eval_check(m, code, c, skip.then_some(self.changed), &mut self.metrics)
732 }
733
734 fn in_model_of(&mut self, m: &mut Machine) -> Result<bool, (Site, Error)> {
737 let skip = self.opts.parent_skip && !self.initial;
738 in_model(
739 m,
740 self.plan,
741 !self.initial,
742 skip.then_some(self.changed),
743 &mut self.metrics,
744 )
745 }
746
747 fn probe(&mut self, m: &mut Machine) -> Result<(Probe, bool, u64), Error> {
748 let in_model = match self.in_model_of(m) {
749 Ok(b) => b,
750 Err((site, e)) => {
751 let e = self.fail_check(m, site, e);
752 if self.failure.is_some() {
753 self.end_here(m)?;
754 }
755 return Err(e);
756 }
757 };
758 self.in_model = in_model;
759 if !self.opts.early_probe {
760 for i in 0..m.s1.len() {
761 m.s1[i] = m.heap.intern(m.s1[i])?;
762 }
763 }
764 if !in_model && (self.plan.symmetry.is_some() || self.plan.view.is_some()) {
765 return Ok((Probe::New, false, 0));
771 }
772 let mut identity = Vec::new();
773 let key = match state_identity(
774 m,
775 self.plan,
776 self.seen.exact.as_ref().map(|_| &mut identity),
777 ) {
778 Ok(k) => self.seen.key(k),
779 Err(e) if e.kind() == ErrorKind::Eval && self.plan.view.is_some() => {
780 self.failure = Some(self.failure_at(m, Site::View, e.message().to_owned())?);
781 self.end_here(m)?;
782 return Err(Error::stop());
783 }
784 Err(e) => return Err(e),
785 };
786 self.metrics.probed += 1;
787 if in_model
788 && (self.max_states.is_some() || self.max_depth.is_some())
789 && !self.seen_contains(key, &identity, &m.heap, ("AdmissionMembership", None))?
790 {
791 self.admit_new()?;
792 }
793 let inserted = if in_model {
794 self.seen_insert(key, &identity, &m.heap, ("Insertion", None))?
795 } else if self.seen_contains(key, &identity, &m.heap, ("AdmissionMembership", None))? {
796 storage::Inserted::Seen(None)
797 } else {
798 storage::Inserted::New
799 };
800 if let storage::Inserted::Seen(id) = inserted {
801 self.metrics.discarded_before_intern +=
802 u64::from(self.opts.early_probe && (!in_model || self.graph.is_none()));
803 return Ok((Probe::Seen(id), in_model, key));
804 }
805 Ok((Probe::New, in_model, key))
806 }
807
808 fn accept(&mut self, m: &mut Machine) -> Result<(), Error> {
809 let plan = self.plan;
810 let code = &plan.code;
811 let original = (self.graph.is_some() || self.checkpoint.is_some())
814 .then(|| capture_copy(&m.s1))
815 .transpose()?;
816 if m.assigned != m.s1.len() {
817 let message = incomplete_message(plan, m);
818 self.failure = Some(self.failure_at(m, Site::Incomplete, message)?);
819 self.end_here(m)?;
820 return Err(Error::stop());
821 }
822 if !self.initial {
823 self.changed = changed_vars(m);
824 }
825 let (probe, in_model, key) = self.probe(m)?;
826 if let Probe::Seen(seen) = probe {
827 if !self.initial {
830 self.implied_actions(m)?;
831 }
832 return if in_model {
833 self.record(m, key, Recorded::Seen(seen), original.as_deref())
834 } else {
835 Ok(())
836 };
837 }
838 if in_model && self.plan.view.is_none() && !fingerprintable(m, self.initial)? {
841 self.failure = Some(self.failure_at(m, Site::Fingerprint, FP_MESSAGE.into())?);
842 self.end_here(m)?;
843 return Err(Error::stop());
844 }
845 if in_model {
848 self.stats.distinct += 1;
849 self.stats.depth = self.stats.depth.max(self.level);
850 }
851 let enqueue_first = self.initial && in_model;
855 if enqueue_first {
856 self.enqueue(m, original.as_deref())?;
857 }
858 for (i, c) in plan.invariants.iter().enumerate() {
859 let holds = match self.check(m, code, c) {
860 Ok(b) => b,
861 Err(e) => {
862 let e = self.fail_check(m, Site::Invariant(i), e);
863 if self.failure.is_some() {
864 self.end_here(m)?;
865 }
866 return Err(e);
867 }
868 };
869 if !holds {
870 self.stop = Some(Verdict::InvariantViolated {
871 property: c.name.clone(),
872 initial: self.initial,
873 });
874 self.end_here(m)?;
875 return Err(Error::stop());
876 }
877 }
878 if self.initial {
879 for (i, c) in plan.implied_inits.iter().enumerate() {
880 let holds = match self.check(m, code, c) {
881 Ok(b) => b,
882 Err(e) => {
883 let e = self.fail_check(m, Site::ImpliedInit(i), e);
884 if self.failure.is_some() {
885 self.end_here(m)?;
886 }
887 return Err(e);
888 }
889 };
890 if !holds {
891 self.stop = Some(Verdict::PropertyViolatedInitially {
892 property: c.name.clone(),
893 });
894 self.end_here(m)?;
895 return Err(Error::stop());
896 }
897 }
898 } else {
899 self.implied_actions(m)?;
900 }
901 if in_model && !enqueue_first {
902 self.enqueue(m, original.as_deref())?;
903 }
904 if in_model {
905 self.record(m, key, Recorded::New, original.as_deref())?;
906 }
907 Ok(())
908 }
909
910 fn record(
913 &mut self,
914 m: &mut Machine,
915 key: u64,
916 recorded: Recorded,
917 original: Option<&[Handle]>,
918 ) -> Result<(), Error> {
919 let (new, seen) = match recorded {
920 Recorded::New => (true, None),
921 Recorded::Seen(seen) => (false, seen),
922 };
923 if new && let Some(session) = &mut self.checkpoint {
924 let values = m.s1.clone();
925 let original = original.unwrap_or(&values);
926 let ordinal = u32::try_from(self.emitted.saturating_sub(1))
927 .map_err(|_| Error::unsupported("checkpoint successor ordinal bound"))?;
928 if let Err(error) =
929 session.record(&mut m.heap, &values, original, key, self.cur_id, ordinal)
930 {
931 self.stop = Some(Verdict::CheckpointError {
932 message: error.message().to_owned(),
933 });
934 return Err(Error::stop());
935 }
936 }
937 let Some(sink) = self.graph.as_deref_mut() else {
938 return Ok(());
939 };
940 let nvars = m.s1.len();
941 let kept = if new {
945 Vec::new()
946 } else {
947 let values = original.unwrap_or(&m.s1);
948 let mut kept = Vec::new();
949 capture_reserve(&mut kept, values.len())?;
950 for &handle in values {
951 kept.push(m.heap.intern_exact(handle)?);
952 }
953 kept
954 };
955 let original = if new {
956 self.next_originals
957 .get(self.next_originals.len().saturating_sub(nvars)..)
958 .ok_or_else(|| Error::internal("a new state's original values were not retained"))?
959 } else {
960 &kept
961 };
962 let new = if new {
963 let id = self
964 .next_ids
965 .last()
966 .copied()
967 .ok_or_else(|| Error::internal("a new state was not enqueued"))?;
968 let values = self
969 .next
970 .get(self.next.len().saturating_sub(nvars)..)
971 .ok_or_else(|| Error::internal("a new state's values were not enqueued"))?;
972 Some((id, values))
973 } else {
974 None
975 };
976 let step = graph::Step {
977 key,
978 new,
979 seen,
980 original,
981 parent: self.cur_id,
982 ordinal: self.emitted.saturating_sub(1),
983 action: self.action,
984 };
985 if sink.state(&mut m.heap, step).is_err() {
986 self.stop = Some(Verdict::GraphStop);
987 return Err(Error::stop());
988 }
989 Ok(())
990 }
991
992 fn report_emitted(&mut self) -> Result<(), Error> {
995 if self.checkpoint.is_some() && self.stats.generated > i64::MAX as u64 {
996 self.stop = Some(Verdict::CheckpointError {
997 message: "native recovery counter bound exceeded".into(),
998 });
999 return Err(Error::stop());
1000 }
1001 let ordinal = (!self.initial).then(|| self.emitted.saturating_sub(1));
1002 let generated = self.stats.generated;
1003 if let Some(sink) = self.graph.as_deref_mut()
1004 && sink.emitted(generated, ordinal).is_err()
1005 {
1006 self.stop = Some(Verdict::GraphStop);
1007 return Err(Error::stop());
1008 }
1009 Ok(())
1010 }
1011
1012 fn implied_actions(&mut self, m: &mut Machine) -> Result<(), Error> {
1015 m.level -= 1;
1017 let r = self.implied_actions_at(m);
1018 m.level += 1;
1019 r
1020 }
1021
1022 fn implied_actions_at(&mut self, m: &mut Machine) -> Result<(), Error> {
1023 let plan = self.plan;
1024 for (i, c) in plan.implied_actions.iter().enumerate() {
1025 let holds = match check_step(m, &plan.code, c) {
1026 Ok(b) => b,
1027 Err(e) => {
1028 let e = self.fail_check(m, Site::ImpliedAction(i), e);
1029 if self.failure.is_some() {
1030 self.end_here(m)?;
1031 }
1032 return Err(e);
1033 }
1034 };
1035 if !holds {
1036 self.stop = Some(Verdict::ActionPropertyViolated {
1037 property: c.name.clone(),
1038 });
1039 self.end_here(m)?;
1040 return Err(Error::stop());
1041 }
1042 }
1043 Ok(())
1044 }
1045
1046 fn admit_new(&mut self) -> Result<(), Error> {
1050 let states = self.stats.distinct + 1;
1051 let stop = if let Some(max) = self.max_states
1052 && states > max
1053 {
1054 Some((Limit::States, max, states))
1055 } else if let Some(max) = self.max_depth
1056 && self.level > max
1057 {
1058 Some((Limit::Depth, max, self.level))
1059 } else {
1060 None
1061 };
1062 if let Some((limit, max, observed)) = stop {
1063 self.stop = Some(Verdict::Admission {
1064 limit,
1065 max,
1066 observed,
1067 });
1068 return Err(Error::stop());
1069 }
1070 Ok(())
1071 }
1072
1073 fn enqueue(&mut self, m: &mut Machine, original: Option<&[Handle]>) -> Result<(), Error> {
1076 if self.frontier.is_some() {
1077 let mut identity = Vec::new();
1078 let mut retained = Vec::new();
1079 capture_reserve(&mut identity, m.s1.len())?;
1080 capture_reserve(&mut retained, m.s1.len())?;
1081 for &value in &m.s1 {
1082 identity.push(m.heap.intern(value)?);
1083 }
1084 for &value in original.unwrap_or(&m.s1) {
1085 retained.push(m.heap.intern_exact(value)?);
1086 }
1087 let ordinal = u32::try_from(self.emitted.saturating_sub(1))
1088 .map_err(|_| Error::unsupported("more than 2^32 successors of one state"))?;
1089 let id = match self.cur_id {
1090 None => self.log.push_initial(ordinal),
1091 Some(parent) => self.log.push(parent, ordinal),
1092 }
1093 .map_err(|e| Error::internal(format!("predecessor log: {e}")))?;
1094 self.confirm_logged(id)?;
1095 return self
1096 .frontier
1097 .as_mut()
1098 .ok_or_else(|| Error::internal("the spilled frontier disappeared"))?
1099 .push(id, &identity, &retained);
1100 }
1101 if self.graph.is_some() || self.checkpoint.is_some() {
1102 capture_reserve(&mut self.next, m.s1.len())?;
1103 capture_reserve(&mut self.next_originals, m.s1.len())?;
1104 capture_reserve(&mut self.next_ids, 1)?;
1105 }
1106 for i in 0..m.s1.len() {
1107 let h = m.heap.intern(m.s1[i])?;
1108 self.next.push(h);
1109 }
1110 if self.graph.is_some() || self.checkpoint.is_some() {
1111 for &h in original.unwrap_or(&m.s1) {
1112 self.next_originals.push(m.heap.intern_exact(h)?);
1113 }
1114 }
1115 let ordinal = u32::try_from(self.emitted.saturating_sub(1))
1116 .map_err(|_| Error::unsupported("more than 2^32 successors of one state"))?;
1117 let id = match self.cur_id {
1118 None => self.log.push_initial(ordinal),
1119 Some(parent) => self.log.push(parent, ordinal),
1120 }
1121 .map_err(|e| Error::internal(format!("predecessor log: {e}")))?;
1122 self.confirm_logged(id)?;
1123 self.next_ids.push(id);
1124 Ok(())
1125 }
1126
1127 fn end_here(&mut self, m: &mut Machine) -> Result<(), Error> {
1129 let mut values = Vec::with_capacity(m.s1.len());
1130 for &h in &m.s1 {
1131 values.push(if h.is_empty() { h } else { m.heap.intern(h)? });
1132 }
1133 let expect = if self.cur_id.is_some() {
1134 if self.graph.is_some() || self.checkpoint.is_some() || self.distributed.is_some() {
1135 m.s0.iter()
1136 .map(|&h| m.heap.intern(h))
1137 .collect::<Result<Vec<_>, _>>()?
1138 } else {
1139 m.s0.clone()
1140 }
1141 } else {
1142 Vec::new()
1143 };
1144 self.end = Some(End {
1145 upto: self.cur_id,
1146 last: Some((self.action, values)),
1147 expect,
1148 });
1149 Ok(())
1150 }
1151}
1152
1153pub(crate) fn eval_check(
1157 m: &mut Machine,
1158 code: &Code,
1159 c: &Check,
1160 skip: Option<u64>,
1161 metrics: &mut Metrics,
1162) -> Result<bool, Error> {
1163 std::mem::swap(&mut m.s0, &mut m.s1);
1164 let old = m.enter(c.frame);
1165 let mut r = Ok(true);
1166 for conj in &c.conjuncts {
1167 metrics.conjuncts_total += 1;
1168 if let Some(changed) = skip
1169 && conj.skippable
1170 && conj.reads & changed == 0
1171 {
1172 metrics.conjuncts_skipped += 1;
1173 continue;
1174 }
1175 match m.eval_bool(code, conj.p) {
1176 Ok(true) => {}
1177 Ok(false) => {
1178 r = Ok(false);
1179 break;
1180 }
1181 Err(e) => {
1182 r = Err(e);
1183 break;
1184 }
1185 }
1186 }
1187 m.leave(old);
1188 std::mem::swap(&mut m.s0, &mut m.s1);
1189 r
1190}
1191
1192pub(crate) fn in_model(
1195 m: &mut Machine,
1196 plan: &Plan,
1197 step: bool,
1198 skip: Option<u64>,
1199 metrics: &mut Metrics,
1200) -> Result<bool, (Site, Error)> {
1201 let code = &plan.code;
1202 for (i, c) in plan.constraints.iter().enumerate() {
1203 if !eval_check(m, code, c, skip, metrics).map_err(|e| (Site::Constraint(i), e))? {
1204 return Ok(false);
1205 }
1206 }
1207 if step {
1210 m.level -= 1;
1212 let r = (|| {
1213 for (i, c) in plan.action_constraints.iter().enumerate() {
1214 if !check_step(m, code, c).map_err(|e| (Site::ActionConstraint(i), e))? {
1215 return Ok(false);
1216 }
1217 }
1218 Ok(true)
1219 })();
1220 m.level += 1;
1221 return r;
1222 }
1223 Ok(true)
1224}
1225
1226pub(crate) fn incomplete_message(plan: &Plan, m: &Machine) -> String {
1229 let missing: Vec<&str> =
1230 m.s1.iter()
1231 .zip(&plan.vars)
1232 .filter(|(h, _)| h.is_empty())
1233 .map(|(_, n)| n.as_str())
1234 .collect();
1235 format!("not completely specified: {}", missing.join(", "))
1236}
1237
1238pub(crate) fn changed_vars(m: &Machine) -> u64 {
1240 let mut changed = 0;
1241 for (i, (a, b)) in m.s0.iter().zip(&m.s1).enumerate() {
1242 if a != b {
1243 changed |= 1u64 << i;
1244 }
1245 }
1246 changed
1247}
1248
1249const FP_MESSAGE: &str = "a state holds a set that cannot be fingerprinted";
1251
1252pub(crate) fn fingerprintable(m: &mut Machine, initial: bool) -> Result<bool, Error> {
1264 fingerprintable_with_identity(m, initial, None)
1265}
1266
1267pub(crate) fn fingerprintable_with_identity(
1270 m: &mut Machine,
1271 initial: bool,
1272 identity: Option<&[Handle]>,
1273) -> Result<bool, Error> {
1274 for i in 0..m.s1.len() {
1275 let h = m.s1[i];
1276 if h.is_empty() || !h.is_compound() || (!initial && m.s0.get(i) == Some(&h)) {
1277 continue;
1278 }
1279 let p = if let Some(identity) = identity {
1280 *identity
1281 .get(i)
1282 .ok_or_else(|| Error::internal("candidate identity row width"))?
1283 } else {
1284 m.heap.state_identity(h)?
1285 };
1286 m.s1[i] = p;
1287 if !closed_fingerprintable(&m.heap, p) {
1288 return Ok(false);
1289 }
1290 }
1291 Ok(true)
1292}
1293
1294fn closed_fingerprintable(heap: &dive_core::Heap, h: Handle) -> bool {
1296 use dive_core::node::Kind;
1297 if !h.is_compound() {
1298 return true;
1299 }
1300 let v = heap.view(h);
1301 match v.kind {
1302 Kind::Set | Kind::IntFcn | Kind::Fcn => {
1303 v.data.iter().all(|&d| closed_fingerprintable(heap, d))
1304 }
1305 Kind::BigInt | Kind::Interval => true,
1306 _ => false,
1307 }
1308}
1309
1310fn check_step(m: &mut Machine, code: &Code, c: &Check) -> Result<bool, Error> {
1312 let old = m.enter(c.frame);
1313 let mut r = Ok(true);
1314 for conj in &c.conjuncts {
1315 match m.eval_bool(code, conj.p) {
1316 Ok(true) => {}
1317 other => {
1318 r = other;
1319 break;
1320 }
1321 }
1322 }
1323 m.leave(old);
1324 r
1325}
1326
1327impl Sink for Explorer<'_> {
1328 fn emit(&mut self, m: &mut Machine, _code: &Code) -> Result<(), Error> {
1329 if self.initial && (self.poll)() {
1332 self.stop = Some(Verdict::Budget);
1333 return Err(Error::stop());
1334 }
1335 if self.graph.is_some() {
1336 self.stats.generated = self
1337 .stats
1338 .generated
1339 .checked_add(1)
1340 .ok_or_else(|| Error::unsupported("capture generated counter overflow"))?;
1341 self.emitted = self
1342 .emitted
1343 .checked_add(1)
1344 .ok_or_else(|| Error::unsupported("capture successor ordinal overflow"))?;
1345 if self.initial {
1346 self.stats.initial_generated = self
1347 .stats
1348 .initial_generated
1349 .checked_add(1)
1350 .ok_or_else(|| Error::unsupported("capture initial counter overflow"))?;
1351 }
1352 } else {
1353 self.stats.generated += 1;
1354 self.emitted += 1;
1355 if self.initial {
1356 self.stats.initial_generated += 1;
1357 }
1358 }
1359 self.report_emitted()?;
1360 if !self.initial && self.graph.is_some() && (self.poll)() {
1361 self.stop = Some(Verdict::Budget);
1362 return Err(Error::stop());
1363 }
1364 let before = m.heap.mark();
1372 let forced = m.thunk_mark();
1373 let draws = m.draws;
1374 let level = m.level;
1376 m.level = i64::try_from(self.level).unwrap_or(i64::MAX);
1377 let r = self.accept(m);
1378 m.level = level;
1379 if m.draws != draws {
1380 return Err(Error::unsupported(
1383 "RandomElement in an invariant, constraint or implied action (M1 core)",
1384 ));
1385 }
1386 if r.is_ok() && m.thunks_released(forced) {
1387 m.heap.rollback(before);
1388 }
1389 if m.heap.poisoned() {
1390 return Err(Error::internal("a stale value handle was read"));
1391 }
1392 r
1393 }
1394}
1395
1396fn run_actions(
1397 m: &mut Machine,
1398 ex: &mut Explorer<'_>,
1399 actions: &[dive_core::plan::Action],
1400 code: &Code,
1401) -> Result<(), Error> {
1402 for (i, a) in actions.iter().enumerate() {
1403 ex.action = (!ex.initial).then_some(i);
1404 ex.init_action = ex.initial.then_some(i);
1405 ex.action_start = ex.emitted;
1406 let old = m.enter(a.frame);
1407 for &(slot, v) in &a.preset {
1408 if let Some(x) = m.frame.get_mut(m.base + slot as usize) {
1409 *x = v;
1410 }
1411 }
1412 let r = m.run_action(code, a.g, ex);
1413 m.leave(old);
1414 r?;
1415 }
1416 Ok(())
1417}
1418
1419fn workers(plan: &Plan, config: &Config) -> usize {
1422 if plan.effects.any {
1423 1
1424 } else {
1425 config.workers.max(1)
1426 }
1427}
1428
1429#[must_use]
1431pub fn explore(
1432 plan: &Plan,
1433 store: &Arc<Store>,
1434 config: Config,
1435 poll: &(dyn Fn() -> bool + Sync),
1436) -> Outcome {
1437 explore_with(plan, store, config, poll, None)
1438}
1439
1440#[must_use]
1443#[allow(
1444 clippy::too_many_lines,
1445 reason = "ordered search setup and result assembly stay in one entrypoint"
1446)]
1447pub fn explore_with<'p>(
1448 plan: &'p Plan,
1449 store: &Arc<Store>,
1450 config: Config,
1451 poll: &'p (dyn Fn() -> bool + Sync),
1452 graph: Option<&'p mut dyn graph::GraphSink>,
1453) -> Outcome {
1454 explore_with_control(plan, store, config, poll, graph, None)
1455}
1456
1457#[must_use]
1460#[allow(
1461 clippy::too_many_lines,
1462 reason = "ordered search setup/result assembly"
1463)]
1464pub fn explore_with_control<'p>(
1465 plan: &'p Plan,
1466 store: &Arc<Store>,
1467 config: Config,
1468 poll: &'p (dyn Fn() -> bool + Sync),
1469 graph: Option<&'p mut dyn graph::GraphSink>,
1470 control: Option<&Arc<dyn dive_core::eval::WorkControl>>,
1471) -> Outcome {
1472 explore_with_storage(
1473 plan,
1474 store,
1475 config,
1476 poll,
1477 graph,
1478 control,
1479 &storage::Storage::default(),
1480 )
1481}
1482
1483#[must_use]
1486#[allow(
1487 clippy::too_many_arguments,
1488 clippy::too_many_lines,
1489 reason = "search setup and storage policy"
1490)]
1491pub fn explore_with_storage<'p>(
1492 plan: &'p Plan,
1493 store: &Arc<Store>,
1494 config: Config,
1495 poll: &'p (dyn Fn() -> bool + Sync),
1496 graph: Option<&'p mut dyn graph::GraphSink>,
1497 control: Option<&Arc<dyn dive_core::eval::WorkControl>>,
1498 storage: &storage::Storage,
1499) -> Outcome {
1500 let mut owner = Arc::clone(store);
1501 explore_inner(
1502 plan, &mut owner, config, poll, graph, control, storage, None, None, false, None,
1503 )
1504}
1505
1506#[must_use]
1516#[allow(
1517 clippy::too_many_arguments,
1518 reason = "existing owned search, control and recovery owners"
1519)]
1520pub fn explore_owned<'p>(
1521 plan: &'p Plan,
1522 store: &mut Arc<Store>,
1523 config: Config,
1524 poll: &'p (dyn Fn() -> bool + Sync),
1525 control: Option<&Arc<dyn dive_core::eval::WorkControl>>,
1526 storage: &storage::Storage,
1527 session: Option<&'p mut checkpoint::Session>,
1528 permanent: Option<&dive_core::store::compact::Permanent>,
1529) -> Outcome {
1530 explore_inner(
1531 plan, store, config, poll, None, control, storage, session, permanent, true, None,
1532 )
1533}
1534
1535#[must_use]
1538#[allow(
1539 clippy::too_many_arguments,
1540 reason = "existing search owners and explicit authenticated coordinator"
1541)]
1542pub fn explore_distributed<'p>(
1543 plan: &'p Plan,
1544 store: &Arc<Store>,
1545 config: Config,
1546 poll: &'p (dyn Fn() -> bool + Sync),
1547 control: Option<&Arc<dyn dive_core::eval::WorkControl>>,
1548 storage: &storage::Storage,
1549 coordinator: &'p distributed::Coordinator,
1550) -> Outcome {
1551 let mut owner = Arc::clone(store);
1552 explore_inner(
1553 plan,
1554 &mut owner,
1555 config,
1556 poll,
1557 None,
1558 control,
1559 storage,
1560 None,
1561 None,
1562 false,
1563 Some(coordinator),
1564 )
1565}
1566
1567#[allow(
1568 clippy::too_many_arguments,
1569 clippy::too_many_lines,
1570 reason = "one existing search owner with an optional completed-level transaction"
1571)]
1572fn explore_inner<'p>(
1573 plan: &'p Plan,
1574 store: &mut Arc<Store>,
1575 config: Config,
1576 poll: &'p (dyn Fn() -> bool + Sync),
1577 graph: Option<&'p mut dyn graph::GraphSink>,
1578 control: Option<&Arc<dyn dive_core::eval::WorkControl>>,
1579 storage: &storage::Storage,
1580 checkpoint: Option<&'p mut checkpoint::Session>,
1581 permanent: Option<&dive_core::store::compact::Permanent>,
1582 owned: bool,
1583 distributed: Option<&'p distributed::Coordinator>,
1584) -> Outcome {
1585 let start = Instant::now();
1586 let trigger_bytes = storage.store_compact_bytes;
1587 let mut compact = trigger_bytes.is_some();
1588 let mut reclaim_refusal = if compact && distributed.is_some() {
1589 Some("Store reclamation with distributed workers is not implemented")
1590 } else if compact && !owned {
1591 Some("Store reclamation requires the owned exploration entrypoint")
1592 } else if compact && (graph.is_some() || plan.effects.any || config.sample.is_some()) {
1593 Some("Store reclamation with temporal capture, runtime effects or sampling")
1594 } else if compact && checkpoint.as_ref().is_some_and(|s| s.pause_after.is_some()) {
1595 Some("Store reclamation with checkpoint pause (discovery residency is unsupported)")
1596 } else {
1597 None
1598 };
1599 let mut default_skip = None;
1602 if storage.store_compact_default
1603 && let Some(feature) = reclaim_refusal.take()
1604 {
1605 compact = false;
1606 default_skip = Some(feature.to_owned());
1607 }
1608 let captured_permanent = if compact && permanent.is_none() && reclaim_refusal.is_none() {
1609 Some(dive_core::store::compact::Permanent::capture(
1610 store,
1611 &|| !poll(),
1612 ))
1613 } else {
1614 None
1615 };
1616 let (captured_permanent, mut permanent_error) = match captured_permanent.transpose() {
1617 Ok(permanent) => (permanent, None),
1618 Err(error) => (None, Some(error)),
1619 };
1620 if storage.store_compact_default
1621 && let Some(error) = permanent_error.take_if(|error| reclaim::skippable(error))
1622 {
1623 compact = false;
1624 default_skip = Some(error.message().to_owned());
1625 }
1626 let storage_owned;
1627 let storage = if storage.store_compact_default && !compact {
1628 storage_owned = storage::Storage {
1629 store_compact_bytes: None,
1630 ..storage.clone()
1631 };
1632 &storage_owned
1633 } else {
1634 storage
1635 };
1636 let permanent = permanent.or(captured_permanent.as_ref());
1637 let config = if storage.seen_disk.is_some() {
1638 Config {
1639 workers: 1,
1640 ..config
1641 }
1642 } else {
1643 config
1644 };
1645 let unsupported_storage = graph.is_some()
1646 && (storage.seen_disk.is_some()
1647 || storage.predecessor_memory_bytes.is_some()
1648 || storage.predecessor_directory.is_some()
1649 || storage.frontier_memory_bytes.is_some()
1650 || storage.frontier_directory.is_some()
1651 || storage.candidate_memory_bytes.is_some()
1652 || storage.candidate_directory.is_some());
1653 let nvars = plan.vars.len();
1654 let (frontier, storage_setup_error) = match storage
1655 .frontier_memory_bytes
1656 .map(|_| storage::Frontiers::new(store, nvars, storage))
1657 .transpose()
1658 {
1659 Ok(frontier) => (frontier, None),
1660 Err(error) => (None, Some(error)),
1661 };
1662 let mut initial_metrics = Metrics::default();
1663 initial_metrics.storage.reclamation.trigger_bytes = trigger_bytes;
1664 initial_metrics.storage.reclamation.default_trigger = storage.store_compact_default;
1665 initial_metrics.storage.reclamation.skipped = default_skip;
1666 let (disk, disk_setup_error) = match storage
1667 .seen_disk
1668 .as_ref()
1669 .map(|options| storage::Disk::new(storage.exact, options))
1670 .transpose()
1671 {
1672 Ok(disk) => (disk, None),
1673 Err(error) => {
1674 initial_metrics.storage.seen = Some(storage::DiskUsage {
1675 limits: storage
1676 .seen_disk
1677 .as_ref()
1678 .map_or_else(dive_store::seen::Limits::default, |options| options.limits),
1679 admitted_keys: 0,
1680 before_cleanup: None,
1681 after_cleanup: None,
1682 first_failure: Some(storage::DiskFailure {
1683 phase: "Creation",
1684 error: error.clone(),
1685 generated: 0,
1686 predecessor: None,
1687 successor_ordinal: 0,
1688 }),
1689 deciding_event_before_failure: None,
1690 audit_completed: false,
1691 });
1692 (None, Some(Error::internal(error.to_string())))
1693 }
1694 };
1695 let mut seen = Seen::with_detached_exact(storage.exact, compact);
1696 #[cfg(test)]
1697 {
1698 seen.collide_keys = storage.collide_keys;
1699 }
1700 if storage.seen_disk.is_some() {
1701 seen.table = Vec::new();
1702 }
1703 let keys: Vec<usize> = plan
1704 .code
1705 .sites
1706 .iter()
1707 .map(dive_core::plan::MemoSite::key_len)
1708 .collect();
1709 let local_workers = if distributed.is_some() {
1710 1
1711 } else {
1712 workers(plan, &config)
1713 };
1714 let mut machines: Vec<Machine> = (0..local_workers)
1715 .map(|_| {
1716 let mut m = Machine::new(Arc::clone(store), nvars, config.opts, Memo::new(&keys));
1717 m.warn = config.warn;
1718 m.set_work_control(control.cloned());
1719 m.set_debugger(plan.code.debugger.clone());
1720 m
1721 })
1722 .collect();
1723 let mut ex = Explorer {
1724 plan,
1725 graph,
1726 stats: Stats::default(),
1727 metrics: initial_metrics,
1728 seen,
1729 disk,
1730 checkpoint,
1731 distributed,
1732 next: Vec::new(),
1733 frontier,
1734 candidates: storage.candidate_memory_bytes.map(|bytes| {
1735 Arc::new(std::sync::Mutex::new(storage::CandidateUsage {
1736 memory_bytes_per_worker: Some(bytes),
1737 ..storage::CandidateUsage::default()
1738 }))
1739 }),
1740 candidate_storage: storage.clone(),
1741 next_originals: Vec::new(),
1742 emitted: 0,
1743 initial: true,
1744 changed: u64::MAX,
1745 level: 1,
1746 expanded: false,
1747 opts: config.opts,
1748 stop: None,
1749 action: None,
1750 init_action: None,
1751 log: PredecessorLog::new(
1752 storage.predecessor_memory_bytes,
1753 storage.predecessor_directory.as_deref(),
1754 ),
1755 next_ids: Vec::new(),
1756 cur_id: None,
1757 predicted: None,
1758 end: None,
1759 in_model: true,
1760 action_start: 0,
1761 failure: None,
1762 poll,
1763 max_states: config.max_states,
1764 max_depth: config.max_depth,
1765 warnings: Vec::new(),
1766 };
1767 let mut replayed = None;
1768 let mut reservoir = config.sample.map(sample::Reservoir::new);
1769 let result = if let Some(feature) = reclaim_refusal {
1770 Err(Error::unsupported(feature))
1771 } else if let Some(error) = permanent_error.or(disk_setup_error).or(storage_setup_error) {
1772 Err(error)
1773 } else if distributed.is_some()
1774 && (ex.graph.is_some()
1775 || config.sample.is_some()
1776 || plan.effects.any
1777 || plan.view.is_some()
1778 || plan.symmetry.is_some()
1779 || storage.seen_disk.is_some()
1780 || storage.candidate_memory_bytes.is_some())
1781 {
1782 Err(Error::unsupported(
1783 "distributed effects, VIEW, symmetry, sampling, disk seen or candidate spill",
1784 ))
1785 } else if unsupported_storage {
1786 Err(Error::unsupported(
1787 "spilled native temporal storage (disk seen set, predecessor, frontier or candidate spill)",
1788 ))
1789 } else if storage.candidate_directory.is_some() && storage.candidate_memory_bytes.is_none() {
1790 Err(Error::unsupported(
1791 "a candidate directory without a candidate memory budget",
1792 ))
1793 } else if storage.candidate_memory_bytes.is_some() && plan.effects.any {
1794 Err(Error::unsupported("candidate spill with runtime effects"))
1795 } else if storage.predecessor_directory.is_some() && storage.predecessor_memory_bytes.is_none()
1796 {
1797 Err(Error::unsupported(
1798 "a predecessor directory without a predecessor memory budget",
1799 ))
1800 } else if storage.frontier_directory.is_some() && storage.frontier_memory_bytes.is_none() {
1801 Err(Error::unsupported(
1802 "a frontier directory without a frontier memory budget",
1803 ))
1804 } else {
1805 run(
1806 &mut machines,
1807 &mut ex,
1808 plan,
1809 &mut replayed,
1810 reservoir.as_mut(),
1811 store,
1812 permanent,
1813 control,
1814 )
1815 };
1816 let parallel = machines.len() > 1 || ex.candidates.is_some() || ex.distributed.is_some();
1817 if let (Some(coordinator), Err(error)) = (distributed, &result) {
1818 coordinator.record_failure(error);
1819 }
1820 let mut m = machines.swap_remove(0);
1821 if let Err(error) = &result
1822 && error.message().starts_with("DIVE-S0203:")
1823 {
1824 ex.metrics
1825 .storage
1826 .reclamation
1827 .failures
1828 .push(error.message().to_owned());
1829 }
1830 let mut trace = ex
1831 .end
1832 .take()
1833 .map(|end| reconstruct(plan, store, &config, &ex.log, end));
1834 let mut verdict = match result {
1835 Ok(()) => Verdict::Success,
1836 Err(e) => match e.into_parts() {
1837 (ErrorKind::Stop, _) if ex.failure.is_some() => Verdict::Failed,
1838 (ErrorKind::Stop, _) => match ex.stop.take() {
1839 Some(stop) => stop,
1840 None if (poll)() || m.heap.work_interrupted() => Verdict::Budget,
1841 None => Verdict::Success,
1842 },
1843 (ErrorKind::Unsupported, message) => Verdict::Unsupported { feature: message },
1844 (ErrorKind::Eval, message) => Verdict::Unsupported {
1845 feature: format!("evaluation error classification (M0 core): {message}"),
1846 },
1847 (ErrorKind::Internal, message) => Verdict::Internal { message },
1848 },
1849 };
1850 if let Some(account) = &ex.candidates {
1851 ex.metrics.storage.candidates = account
1852 .lock()
1853 .unwrap_or_else(std::sync::PoisonError::into_inner)
1854 .clone();
1855 if !ex.metrics.storage.candidates.failures.is_empty() {
1856 ex.metrics.storage.candidates.deciding_event_before_failure =
1857 Some(format!("{verdict:?}"));
1858 verdict = Verdict::Internal {
1859 message: ex.metrics.storage.candidates.failures.join("; "),
1860 };
1861 trace = None;
1862 }
1863 }
1864 ex.metrics.storage.exact_states = ex.seen.exact.as_ref().map_or(0, storage::Exact::len);
1865 if let Some(disk) = &mut ex.disk {
1866 let validate = !matches!(
1867 verdict,
1868 Verdict::Budget
1869 | Verdict::Admission { .. }
1870 | Verdict::Unsupported { .. }
1871 | Verdict::Internal { .. }
1872 );
1873 let complete = disk.finish(validate, poll, verdict.clone());
1874 if storage.exact {
1875 ex.metrics.storage.exact_states =
1876 usize::try_from(disk.usage.admitted_keys).unwrap_or(usize::MAX);
1877 }
1878 ex.metrics.storage.seen = Some(disk.usage.clone());
1879 if let Some(failure) = &disk.usage.first_failure {
1880 verdict = Verdict::Internal {
1881 message: failure.error.to_string(),
1882 };
1883 trace = None;
1884 } else if !complete {
1885 verdict = Verdict::Budget;
1886 trace = None;
1887 }
1888 }
1889 ex.metrics.storage.predecessor = ex.log.usage();
1890 if let Some(error) = ex.log.failure() {
1891 ex.metrics
1892 .storage
1893 .predecessor_failures
1894 .push(error.to_string());
1895 }
1896 match ex.log.close() {
1897 Ok(()) => ex.metrics.storage.predecessor_cleanup_completed = true,
1898 Err(error) => ex
1899 .metrics
1900 .storage
1901 .predecessor_failures
1902 .push(error.to_string()),
1903 }
1904 if !ex.metrics.storage.predecessor_failures.is_empty() {
1905 ex.metrics.storage.predecessor_deciding_event = Some(format!("{verdict:?}"));
1906 verdict = Verdict::Internal {
1907 message: ex.metrics.storage.predecessor_failures.join("; "),
1908 };
1909 trace = None;
1910 }
1911 if let Some(frontier) = &mut ex.frontier {
1912 let validate = !matches!(
1913 verdict,
1914 Verdict::Budget
1915 | Verdict::Admission { .. }
1916 | Verdict::Unsupported { .. }
1917 | Verdict::Internal { .. }
1918 );
1919 let completed = frontier.finish(validate, poll);
1920 ex.metrics.storage.frontier = frontier.usage.clone();
1921 if !ex.metrics.storage.frontier.failures.is_empty() {
1922 ex.metrics.storage.frontier.deciding_event_before_failure =
1923 Some(format!("{verdict:?}"));
1924 verdict = Verdict::Internal {
1925 message: ex.metrics.storage.frontier.failures.join("; "),
1926 };
1927 trace = None;
1928 } else if !completed {
1929 verdict = Verdict::Budget;
1930 trace = None;
1931 }
1932 }
1933 let mut metrics = ex.metrics;
1934 metrics.distributed = distributed.map(distributed::Coordinator::usage);
1935 metrics.store = store.stats();
1936 metrics.store_memory = store.memory_usage();
1937 metrics.memo = plan
1938 .code
1939 .sites
1940 .iter()
1941 .map(|s| s.name.clone())
1942 .zip(m.memo.stats())
1943 .collect();
1944 let (nodes, handles) = m.heap.arena().peak();
1945 metrics.arena_peak.0 = metrics.arena_peak.0.max(nodes);
1946 metrics.arena_peak.1 = metrics.arena_peak.1.max(handles);
1947 for worker in &machines {
1948 let (nodes, handles) = worker.heap.arena().peak();
1949 metrics.arena_peak.0 = metrics.arena_peak.0.max(nodes);
1950 metrics.arena_peak.1 = metrics.arena_peak.1.max(handles);
1951 }
1952 metrics.thunks = (m.stats.forced, m.stats.cached);
1953 metrics.explore_time = start.elapsed();
1954 let warnings = if !config.warn {
1955 Vec::new()
1956 } else if parallel {
1957 std::mem::take(&mut ex.warnings)
1958 } else {
1959 std::mem::take(&mut m.warnings)
1960 };
1961 Outcome {
1962 verdict,
1963 stats: ex.stats,
1964 metrics,
1965 warnings,
1966 trace,
1967 failure: ex.failure,
1968 in_init: ex.initial,
1969 expanded: ex.expanded,
1970 replayed,
1971 sampled: reservoir.map(|r| r.states).unwrap_or_default(),
1972 printed: std::mem::take(&mut m.printed),
1973 }
1974}
1975
1976fn reconstruct(
1978 plan: &Plan,
1979 store: &Arc<Store>,
1980 config: &Config,
1981 log: &PredecessorLog,
1982 end: End,
1983) -> Result<Vec<TraceState>, String> {
1984 let mut states = match end.upto {
1985 None => Vec::new(),
1986 Some(id) => {
1987 let path = log.path(id).map_err(|e| format!("predecessor log: {e}"))?;
1988 let states = trace::replay(plan, store, config.opts, config.warn, &path)
1989 .map_err(|e| e.message().to_owned())?;
1990 if !states
1991 .last()
1992 .is_some_and(|s| replay_values_match(store, &s.values, &end.expect))
1993 {
1994 return Err("trace replay produced a different state than the search".into());
1995 }
1996 states
1997 }
1998 };
1999 if let Some((action, values)) = end.last {
2000 states.push(TraceState { action, values });
2001 }
2002 Ok(states)
2003}
2004
2005fn replay_values_match(store: &Arc<Store>, actual: &[Handle], expected: &[Handle]) -> bool {
2008 if actual == expected {
2009 return true;
2010 }
2011 if store.hashcons() || actual.len() != expected.len() {
2012 return false;
2013 }
2014 let heap = dive_core::Heap::new(Arc::clone(store), false, false);
2015 actual.iter().zip(expected).all(|(&a, &b)| heap.eq(a, b))
2016}
2017
2018fn generator_error(m: &Machine, ex: &mut Explorer<'_>, identity: &[Handle], e: Error) -> Error {
2023 if e.kind() != ErrorKind::Eval || ex.failure.is_some() {
2024 return e;
2025 }
2026 ex.failure = Some(ex.generator_failure(m, e.message().to_owned()));
2027 if let Some(id) = ex.cur_id {
2028 ex.end = Some(End {
2029 upto: Some(id),
2030 last: None,
2031 expect: identity.to_vec(),
2032 });
2033 }
2034 Error::stop()
2035}
2036
2037fn source_row(
2038 machine: &mut Machine,
2039 explorer: &mut Explorer<'_>,
2040 identity: &[Handle],
2041 left: u64,
2042 terminal: bool,
2043) -> Result<(), Error> {
2044 let Some(source) = explorer.cur_id else {
2045 return Ok(());
2046 };
2047 let error = terminal.then_some(explorer.failure.as_ref()).flatten();
2048 let Some(sink) = explorer.graph.as_deref_mut() else {
2049 return Ok(());
2050 };
2051 let row = graph::SourceRow {
2052 source,
2053 original: &machine.s0,
2054 emitted: explorer.emitted,
2055 next_error: error,
2056 stats: Stats {
2057 left_on_queue: left,
2058 ..explorer.stats
2059 },
2060 };
2061 if sink.source_row(&mut machine.heap, row).is_err() {
2062 explorer.stats.left_on_queue = left;
2063 explorer.stop = Some(Verdict::GraphStop);
2064 explorer.end = Some(End {
2065 upto: Some(source),
2066 last: None,
2067 expect: identity.to_vec(),
2068 });
2069 return Err(Error::stop());
2070 }
2071 Ok(())
2072}
2073
2074pub(crate) fn start_stream(
2077 m: &mut Machine,
2078 plan: &Plan,
2079 state: Option<&[Handle]>,
2080) -> Result<(), Error> {
2081 if !plan.effects.draws {
2082 return Ok(());
2083 }
2084 let Some(draws) = m.heap.store().draws().cloned() else {
2085 return Err(Error::unsupported(
2086 "RandomElement without the run's random streams (M1 core)",
2087 ));
2088 };
2089 m.draw = Some(match state {
2090 None => draws.startup(),
2091 Some(vars) => draws.state(&mut m.heap, vars)?,
2092 });
2093 Ok(())
2094}
2095
2096fn level_done(ex: &mut Explorer<'_>, _nvars: usize) -> Result<(), Error> {
2099 let left_on_queue = ex.queued_states() as u64;
2100 let Some(sink) = ex.graph.as_deref_mut() else {
2101 return Ok(());
2102 };
2103 let counts = Stats {
2104 left_on_queue,
2105 ..ex.stats
2106 };
2107 let level = ex.level - 1;
2108 let stop = sink.level_done(level, counts);
2109 if stop == Ok(false) {
2110 return Ok(());
2111 }
2112 ex.stats.left_on_queue = counts.left_on_queue;
2113 ex.stop = Some(match stop {
2114 Ok(_) if counts.left_on_queue > 0 => Verdict::PrefixStop { level },
2115 Ok(_) => Verdict::Internal {
2116 message: "a prefix stop with an exhausted frontier".into(),
2117 },
2118 Err(graph::Stopped) => Verdict::GraphStop,
2119 });
2120 Err(Error::stop())
2121}
2122
2123const CHUNK_PER_WORKER: usize = 4096;
2125const FRONTIER_CHUNK_STATES: usize = 1024;
2127
2128#[allow(
2129 clippy::too_many_lines,
2130 clippy::too_many_arguments,
2131 reason = "TLC's ordered level loop: expansion, stops, replay and deadlock"
2132)]
2133fn run(
2134 machines: &mut [Machine],
2135 ex: &mut Explorer<'_>,
2136 plan: &Plan,
2137 replayed: &mut Option<Replayed>,
2138 mut reservoir: Option<&mut sample::Reservoir>,
2139 store: &mut Arc<Store>,
2140 permanent: Option<&dive_core::store::compact::Permanent>,
2141 control: Option<&Arc<dyn dive_core::eval::WorkControl>>,
2142) -> Result<(), Error> {
2143 let code = &plan.code;
2144 let nvars = plan.vars.len();
2145 let parallel = machines.len() > 1 || ex.candidates.is_some() || ex.distributed.is_some();
2146 let Some(m) = machines.first_mut() else {
2147 return Err(Error::internal("no core machine"));
2148 };
2149 let recovered = checkpoint::restore(ex, m)?;
2150 if !recovered {
2151 start_stream(m, plan, None)?;
2152 m.level = 0;
2154 if let Err(e) = run_actions(m, ex, &plan.init, code) {
2155 ex.stats.left_on_queue = ex.queued_states() as u64;
2156 return Err(generator_error(m, ex, &[], e));
2157 }
2158 ex.stats.depth = ex
2161 .stats
2162 .depth
2163 .max(u64::from(ex.stats.initial_generated > 0));
2164 if plan.next.is_empty() && ex.queued_states() > 0 {
2168 ex.stats.left_on_queue = ex.queued_states() as u64;
2169 ex.stop = Some(Verdict::NoNextAction);
2170 return Err(Error::stop());
2171 }
2172 m.heap.reset();
2173 ex.initial = false;
2174 ex.warnings.clone_from(&m.warnings);
2175 }
2176 checkpoint::boundary(ex)?;
2177 reclaim::boundary(machines, ex, store, permanent, control)?;
2178 let mut cur = std::mem::take(&mut ex.next);
2179 let mut cur_originals = std::mem::take(&mut ex.next_originals);
2180 let mut cur_ids = std::mem::take(&mut ex.next_ids);
2181 ex.advance_frontier()?;
2182 let mut generated_before = 0;
2183 loop {
2184 let states = cur.len().checked_div(nvars).map_or(0, |in_memory| {
2185 ex.frontier
2186 .as_ref()
2187 .map_or(in_memory, storage::Frontiers::current_len)
2188 });
2189 if states == 0 {
2190 break;
2191 }
2192 if (ex.graph.is_some() || ex.checkpoint.is_some())
2193 && ex.frontier.is_none()
2194 && cur_originals.len() != cur.len()
2195 {
2196 return Err(Error::internal(
2197 "capture frontier original/identity row mismatch",
2198 ));
2199 }
2200 ex.level += 1;
2201 ex.expanded = true;
2202 let estimate = usize::try_from(ex.stats.generated - generated_before).unwrap_or(1 << 20);
2204 generated_before = ex.stats.generated;
2205 let level_started = Instant::now();
2206 let mut expand_time = std::time::Duration::ZERO;
2207 let chunk = ex.graph.as_deref().map_or_else(
2212 || (machines.len() * CHUNK_PER_WORKER).max(1),
2213 |sink| sink.max_expansion_units().max(1),
2214 );
2215 let chunk = if ex.candidates.is_some() {
2216 machines.len().max(1)
2217 } else {
2218 chunk
2219 };
2220 let chunk = ex
2221 .distributed
2222 .map_or(chunk, |coordinator| chunk.min(coordinator.width()));
2223 let chunk = if ex.frontier.is_some() {
2224 chunk.min(FRONTIER_CHUNK_STATES)
2225 } else {
2226 chunk
2227 };
2228 let mut expanded: Option<Vec<Option<parallel::Expanded>>> = None;
2229 let mut received: Option<Vec<Option<distributed::Received>>> = None;
2230 let mut decoded = storage::Chunk::default();
2231 let mut base = 0;
2232 for k in 0..states {
2233 if k % chunk == 0 {
2234 let queued = ex.queued_states();
2235 if let Some(frontier) = &mut ex.frontier {
2236 decoded = match frontier.chunk(k, (k + chunk).min(states), ex.poll) {
2237 Ok(Some(decoded)) => decoded,
2238 Ok(None) => {
2239 ex.stats.left_on_queue = (states - k + queued) as u64;
2240 ex.stop = Some(Verdict::Budget);
2241 return Err(Error::stop());
2242 }
2243 Err(error) => {
2244 ex.stats.left_on_queue = (states - k + queued) as u64;
2245 return Err(error);
2246 }
2247 };
2248 }
2249 }
2250 let local = k % chunk;
2251 let state = if ex.frontier.is_some() {
2252 &decoded.identity[local * nvars..(local + 1) * nvars]
2253 } else {
2254 &cur[k * nvars..(k + 1) * nvars]
2255 };
2256 if parallel && k % chunk == 0 {
2257 let started = Instant::now();
2258 let end = (k + chunk).min(states);
2259 let mut metrics = Metrics::default();
2260 let r = if let Some(coordinator) = ex.distributed {
2261 coordinator
2262 .expand(
2263 plan,
2264 machines[0].heap.store(),
2265 if ex.frontier.is_some() {
2266 &decoded.original
2267 } else {
2268 &cur[k * nvars..end * nvars]
2269 },
2270 &ex.seen,
2271 ex.level - 1,
2272 ex.poll,
2273 )
2274 .map(|work| {
2275 received = Some(work);
2276 Vec::new()
2277 })
2278 } else {
2279 parallel::expand_level(
2280 plan,
2281 machines,
2282 if ex.frontier.is_some() {
2283 &decoded.original
2284 } else if ex.graph.is_some() || ex.checkpoint.is_some() {
2285 &cur_originals[k * nvars..end * nvars]
2286 } else {
2287 &cur[k * nvars..end * nvars]
2288 },
2289 nvars,
2290 &ex.seen,
2291 ex.opts,
2292 ex.checkpoint.is_some(),
2293 ex.graph
2294 .as_deref()
2295 .map(graph::GraphSink::max_successors_per_unit),
2296 ex.candidates
2297 .as_ref()
2298 .map(|account| (&ex.candidate_storage, account)),
2299 ex.poll,
2300 estimate.saturating_mul(end - k) / states.max(1),
2301 &mut metrics,
2302 )
2303 };
2304 let r = match r {
2305 Ok(r) => r,
2306 Err(error) => {
2307 ex.stats.left_on_queue = (states - k + ex.queued_states()) as u64;
2308 return Err(error);
2309 }
2310 };
2311 ex.metrics.conjuncts_total += metrics.conjuncts_total;
2312 ex.metrics.conjuncts_skipped += metrics.conjuncts_skipped;
2313 ex.metrics.discarded_before_intern += metrics.discarded_before_intern;
2314 expand_time += started.elapsed();
2315 expanded = if received.is_some() { None } else { Some(r) };
2316 base = k;
2317 }
2318 let Some(m) = machines.first_mut() else {
2319 return Err(Error::internal("no core machine"));
2320 };
2321 let have_expansion = expanded.is_some() || received.is_some();
2322 let mut remote_expansion = if let Some(work) = received
2323 .as_mut()
2324 .and_then(|work| work.get_mut(k - base))
2325 .and_then(Option::take)
2326 {
2327 let Some(coordinator) = ex.distributed else {
2328 return Err(Error::internal("remote result without its coordinator"));
2329 };
2330 let started = Instant::now();
2331 let mut metrics = Metrics::default();
2332 let imported = coordinator.import(work, plan, &mut m.heap, ex.poll, &mut metrics);
2333 let imported = match imported {
2334 Ok(imported) => imported,
2335 Err(error) => {
2336 ex.stats.left_on_queue = (states - k + ex.queued_states()) as u64;
2337 return Err(error);
2338 }
2339 };
2340 ex.metrics.conjuncts_total += metrics.conjuncts_total;
2341 ex.metrics.conjuncts_skipped += metrics.conjuncts_skipped;
2342 ex.metrics.discarded_before_intern += metrics.discarded_before_intern;
2343 expand_time += started.elapsed();
2344 Some(imported)
2345 } else {
2346 None
2347 };
2348 let res = remote_expansion.as_mut().or_else(|| {
2349 expanded
2350 .as_mut()
2351 .and_then(|all| all.get_mut(k - base).and_then(Option::as_mut))
2352 });
2353 let exhausted = if have_expansion {
2356 res.is_none()
2357 } else {
2358 (ex.poll)()
2359 };
2360 if exhausted {
2361 ex.stats.left_on_queue = (states - k + ex.queued_states()) as u64;
2362 ex.stop = Some(Verdict::Budget);
2363 return Err(Error::stop());
2364 }
2365 let source = if ex.frontier.is_some() {
2366 &decoded.original[local * nvars..(local + 1) * nvars]
2367 } else if ex.graph.is_some() || ex.checkpoint.is_some() {
2368 cur_originals
2369 .get(k * nvars..(k + 1) * nvars)
2370 .ok_or_else(|| Error::internal("capture source original row missing"))?
2371 } else {
2372 state
2373 };
2374 m.s0.copy_from_slice(source);
2375 let level = i64::try_from(ex.level - 1).unwrap_or(i64::MAX);
2376 if res.is_none() {
2377 start_stream(m, plan, Some(source))?;
2378 m.level = level;
2379 }
2380 if let Some(r) = reservoir.as_deref_mut() {
2381 r.offer(source, level);
2382 }
2383 ex.cur_id = if ex.frontier.is_some() {
2384 decoded.ids.get(local).copied()
2385 } else {
2386 cur_ids.get(k).copied()
2387 };
2388 ex.emitted = 0;
2389 let r = match res {
2390 Some(res) => ex.commit(m, res),
2391 None => run_actions(m, ex, &plan.next, code),
2392 }
2393 .map_err(|e| generator_error(m, ex, state, e));
2394 if r.is_err()
2395 && ex
2396 .failure
2397 .as_ref()
2398 .is_some_and(|failure| matches!(failure.site, Site::Next(_)))
2399 {
2400 let row_left = (states - k - 1 + ex.queued_states()) as u64;
2401 source_row(m, ex, state, row_left, true)?;
2402 }
2403 if r.is_err()
2404 && let Some(f) = &ex.failure
2405 && f.site_resumes()
2406 {
2407 if plan.effects.draws {
2409 return Err(Error::unsupported(
2410 "TLC's replay after a failing check, in a specification that draws (RandomElement) (M1 core)",
2411 ));
2412 }
2413 if plan.effects.registers || plan.effects.level {
2414 return Err(Error::unsupported(
2415 "TLC's replay after a failing check, in a specification that uses TLCSet or TLCGet (M1 core)",
2416 ));
2417 }
2418 ex.graph = None;
2420 let ordinal = ex.emitted - 1;
2421 let saved = std::mem::take(&mut m.warnings);
2422 *replayed = Some(ending::replay_after(m, ex, ordinal)?);
2423 for w in std::mem::replace(&mut m.warnings, saved) {
2424 if parallel && !ex.warnings.contains(&w) {
2425 ex.warnings.push(w);
2426 } else if !parallel && !m.warnings.contains(&w) {
2427 m.warnings.push(w);
2428 }
2429 }
2430 }
2431 if let Some(all) = &mut expanded {
2432 all[k - base] = None;
2433 }
2434 m.heap.reset();
2435 let left = (states - k - 1 + ex.queued_states()) as u64;
2436 if let Err(e) = r {
2437 ex.stats.left_on_queue = left;
2438 return Err(e);
2439 }
2440 if ex.emitted == 0 && plan.check_deadlock {
2441 ex.stats.left_on_queue = left;
2442 ex.stop = Some(Verdict::Deadlock);
2443 ex.end = Some(End {
2444 upto: ex.cur_id,
2445 last: None,
2446 expect: state.to_vec(),
2447 });
2448 return Err(Error::stop());
2449 }
2450 if let Some(id) = ex.cur_id
2451 && let Some(sink) = ex.graph.as_deref_mut()
2452 && sink.stutter(id).is_err()
2453 {
2454 ex.stats.left_on_queue = left;
2455 ex.stop = Some(Verdict::GraphStop);
2456 return Err(Error::stop());
2457 }
2458 source_row(m, ex, state, left, false)?;
2459 }
2460 level_done(ex, nvars)?;
2461 if !parallel {
2462 ex.warnings.clone_from(&machines[0].warnings);
2463 }
2464 checkpoint::boundary(ex)?;
2465 if parallel {
2466 ex.metrics.expand_time += expand_time;
2467 ex.metrics.commit_time += level_started.elapsed().saturating_sub(expand_time);
2468 }
2469 cur.clear();
2470 cur_originals.clear();
2471 cur_ids.clear();
2472 drop(expanded);
2475 drop(decoded);
2476 reclaim::boundary(machines, ex, store, permanent, control)?;
2477 std::mem::swap(&mut cur, &mut ex.next);
2478 std::mem::swap(&mut cur_originals, &mut ex.next_originals);
2479 std::mem::swap(&mut cur_ids, &mut ex.next_ids);
2480 ex.advance_frontier()?;
2481 }
2482 Ok(())
2483}
2484
2485#[cfg(test)]
2486mod tests {
2487 use super::*;
2488
2489 pub(super) fn frontier_plan(store: &Arc<Store>, false_invariant: bool) -> Result<Plan, Error> {
2490 use dive_core::plan::{Action, CompileStats, Conjunct, Effects, GNode, Node};
2491
2492 let mut heap = dive_core::Heap::new(Arc::clone(store), true, false);
2493 let domain = heap.interval(0, 127);
2494 let domain = heap.intern_const(domain)?;
2495 let action = |name: &str, g| Action {
2496 name: name.into(),
2497 g,
2498 frame: 0,
2499 preset: Vec::new(),
2500 };
2501 Ok(Plan {
2502 code: Code {
2503 nodes: vec![
2504 Node::Const(domain),
2505 Node::Var(0),
2506 Node::Const(Handle::FALSE),
2507 ],
2508 gnodes: vec![
2509 GNode::AssignIn { var: 0, set: 0 },
2510 GNode::Assign { var: 0, rhs: 1 },
2511 ],
2512 ..Code::default()
2513 },
2514 vars: vec!["x".into()],
2515 init: vec![action("Init", 0)],
2516 next: vec![action("Next", 1)],
2517 invariants: if false_invariant {
2518 vec![Check {
2519 name: "Inv".into(),
2520 frame: 0,
2521 conjuncts: vec![Conjunct {
2522 p: 2,
2523 reads: 1,
2524 skippable: false,
2525 site: None,
2526 }],
2527 }]
2528 } else {
2529 Vec::new()
2530 },
2531 constraints: Vec::new(),
2532 action_constraints: Vec::new(),
2533 implied_inits: Vec::new(),
2534 implied_actions: Vec::new(),
2535 check_deadlock: true,
2536 symmetry: None,
2537 effects: Effects::default(),
2538 view: None,
2539 stats: CompileStats::default(),
2540 bound_preset: Vec::new(),
2541 startup_assumptions: Vec::new(),
2542 startup_assumption_false: None,
2543 })
2544 }
2545
2546 #[derive(Clone, Copy, Debug)]
2547 enum FrontierFault {
2548 Corrupt,
2549 Missing,
2550 Cleanup,
2551 }
2552
2553 #[allow(
2554 clippy::unwrap_used,
2555 clippy::too_many_lines,
2556 reason = "fault mutation and real explorer outcome remain in one deterministic control"
2557 )]
2558 fn frontier_fault(
2559 tlc: bool,
2560 exact: bool,
2561 workers: usize,
2562 initial_violation: bool,
2563 fault: FrontierFault,
2564 ) {
2565 use std::fs;
2566 use std::io::{Seek, SeekFrom, Write};
2567 use std::sync::atomic::{AtomicBool, AtomicUsize, Ordering};
2568
2569 static NEXT: AtomicUsize = AtomicUsize::new(0);
2570 let directory = std::env::temp_dir().join(format!(
2571 "dive-frontier-explorer-{}-{}",
2572 std::process::id(),
2573 NEXT.fetch_add(1, Ordering::Relaxed)
2574 ));
2575 fs::create_dir(&directory).unwrap();
2576 let store = Arc::new(Store::with_semantics(
2577 true,
2578 if tlc {
2579 dive_core::Semantics::tlc()
2580 } else {
2581 dive_core::Semantics::default()
2582 },
2583 ));
2584 let plan = frontier_plan(&store, initial_violation).unwrap();
2585 let calls = AtomicUsize::new(0);
2586 let injected = AtomicBool::new(false);
2587 let trigger = if initial_violation { 1 } else { 129 };
2588 let poll = || {
2589 if calls.fetch_add(1, Ordering::Relaxed) == trigger {
2590 let owned = fs::read_dir(&directory)
2591 .unwrap()
2592 .next()
2593 .unwrap()
2594 .unwrap()
2595 .path();
2596 match fault {
2597 FrontierFault::Corrupt => {
2598 let mut file = fs::OpenOptions::new()
2599 .write(true)
2600 .open(owned.join("states"))
2601 .unwrap();
2602 file.seek(SeekFrom::End(-1)).unwrap();
2603 file.write_all(&[255]).unwrap();
2604 }
2605 FrontierFault::Missing => fs::remove_file(owned.join("states")).unwrap(),
2606 FrontierFault::Cleanup => {
2607 fs::rename(&owned, directory.join("moved")).unwrap();
2608 fs::write(owned, b"blocks directory cleanup").unwrap();
2609 }
2610 }
2611 injected.store(true, Ordering::Relaxed);
2612 }
2613 false
2614 };
2615 let out = explore_with_storage(
2616 &plan,
2617 &store,
2618 Config {
2619 opts: Opts::default(),
2620 max_states: None,
2621 max_depth: None,
2622 workers,
2623 warn: true,
2624 sample: None,
2625 },
2626 &poll,
2627 None,
2628 None,
2629 &storage::Storage {
2630 exact,
2631 frontier_memory_bytes: Some(0),
2632 frontier_directory: Some(directory.clone()),
2633 ..storage::Storage::default()
2634 },
2635 );
2636 assert!(injected.load(Ordering::Relaxed), "{fault:?}");
2637 assert!(
2638 matches!(out.verdict, Verdict::Internal { .. }),
2639 "{fault:?}: {:?}",
2640 out.verdict
2641 );
2642 assert!(
2643 out.trace.is_none(),
2644 "corrupt storage must clear a deciding word"
2645 );
2646 let failures = &out.metrics.storage.frontier.failures;
2647 assert_ne!(failures.as_slice(), [] as [String; 0]);
2648 let expected = match fault {
2649 FrontierFault::Corrupt => "checksum",
2650 FrontierFault::Missing => "open record",
2651 FrontierFault::Cleanup => "cleanup",
2652 };
2653 assert!(
2654 failures.iter().any(|message| message.contains(expected)),
2655 "{failures:?}"
2656 );
2657 if initial_violation {
2658 assert!(
2659 out.metrics
2660 .storage
2661 .frontier
2662 .deciding_event_before_failure
2663 .as_ref()
2664 .unwrap()
2665 .contains("InvariantViolated")
2666 );
2667 }
2668 fs::remove_dir_all(directory).unwrap();
2669 }
2670
2671 #[test]
2672 fn corrupt_read_and_cleanup_failures_prevent_success_and_counterexample_certification() {
2673 for tlc in [false, true] {
2674 for exact in [false, true] {
2675 for workers in [1, 4, 8] {
2676 for initial in [false, true] {
2677 for fault in [
2678 FrontierFault::Corrupt,
2679 FrontierFault::Missing,
2680 FrontierFault::Cleanup,
2681 ] {
2682 frontier_fault(tlc, exact, workers, initial, fault);
2683 }
2684 }
2685 }
2686 }
2687 }
2688 }
2689
2690 #[test]
2691 #[allow(
2692 clippy::unwrap_used,
2693 reason = "owned cancellation during final frontier validation"
2694 )]
2695 fn validation_cancellation_is_a_budget_stop_without_storage_failure_or_word() {
2696 use std::sync::atomic::{AtomicUsize, Ordering};
2697
2698 for initial_violation in [false, true] {
2699 for workers in [1, 4, 8] {
2700 let store = Arc::new(Store::new(true));
2701 let plan = frontier_plan(&store, initial_violation).unwrap();
2702 let trigger = if initial_violation { 1 } else { 257 };
2705 let calls = AtomicUsize::new(0);
2706 let poll = || calls.fetch_add(1, Ordering::Relaxed) >= trigger;
2707 let out = explore_with_storage(
2708 &plan,
2709 &store,
2710 Config {
2711 opts: Opts::default(),
2712 max_states: None,
2713 max_depth: None,
2714 workers,
2715 warn: true,
2716 sample: None,
2717 },
2718 &poll,
2719 None,
2720 None,
2721 &storage::Storage {
2722 frontier_memory_bytes: Some(0),
2723 ..storage::Storage::default()
2724 },
2725 );
2726 assert_eq!(out.verdict, Verdict::Budget);
2727 assert!(out.trace.is_none());
2728 assert_eq!(out.metrics.storage.frontier.failures, [] as [String; 0]);
2729 assert_eq!(calls.load(Ordering::Relaxed), trigger + 1);
2730 assert_eq!(out.metrics.storage.frontier.retained_bytes, 0);
2731 }
2732 }
2733 }
2734
2735 #[test]
2736 #[allow(
2737 clippy::unwrap_used,
2738 reason = "deterministic owned budget and spilled-frontier control"
2739 )]
2740 fn budget_stop_closes_an_unread_spilled_frontier_without_validation_polls() {
2741 use std::sync::atomic::{AtomicUsize, Ordering};
2742
2743 for tlc in [false, true] {
2744 for exact in [false, true] {
2745 for workers in [1, 4, 8] {
2746 let store = Arc::new(Store::with_semantics(
2747 true,
2748 if tlc {
2749 dive_core::Semantics::tlc()
2750 } else {
2751 dive_core::Semantics::default()
2752 },
2753 ));
2754 let plan = frontier_plan(&store, false).unwrap();
2755 let calls = AtomicUsize::new(0);
2756 let poll = || calls.fetch_add(1, Ordering::Relaxed) >= 128;
2757 let out = explore_with_storage(
2758 &plan,
2759 &store,
2760 Config {
2761 opts: Opts::default(),
2762 max_states: None,
2763 max_depth: None,
2764 workers,
2765 warn: true,
2766 sample: None,
2767 },
2768 &poll,
2769 None,
2770 None,
2771 &storage::Storage {
2772 exact,
2773 frontier_memory_bytes: Some(0),
2774 ..storage::Storage::default()
2775 },
2776 );
2777 assert_eq!(out.verdict, Verdict::Budget);
2778 assert_eq!(
2779 out.stats,
2780 Stats {
2781 generated: 128,
2782 distinct: 128,
2783 depth: 1,
2784 left_on_queue: 128,
2785 initial_generated: 128
2786 }
2787 );
2788 assert!(out.trace.is_none());
2789 assert_eq!(
2790 calls.load(Ordering::Relaxed),
2791 129,
2792 "cleanup must not scan/poll the unread queue"
2793 );
2794 assert!(out.metrics.storage.frontier.spilled_bytes > 0);
2795 assert_eq!(out.metrics.storage.frontier.retained_bytes, 0);
2796 assert_eq!(out.metrics.storage.frontier.failures, [] as [String; 0]);
2797 }
2798 }
2799 }
2800 }
2801
2802 #[test]
2803 fn impossible_capture_growth_is_fallible_without_modifying_retained_payload() {
2804 let mut values = vec![Handle::EMPTY];
2805 let capacity = values.capacity();
2806 assert!(capture_reserve(&mut values, usize::MAX).is_err());
2807 assert_eq!(values, [Handle::EMPTY]);
2808 assert_eq!(values.capacity(), capacity);
2809 }
2810
2811 #[test]
2817 #[allow(clippy::unwrap_used, reason = "deterministic explorer control")]
2818 fn invariant_frame_thunks_do_not_hold_initial_transients() {
2819 use dive_core::plan::{Action, CompileStats, Conjunct, Effects, GNode, Node};
2820
2821 const WIDTH: usize = 64;
2822 const STATES: u64 = 128;
2823 let store = Arc::new(Store::new(false));
2824 let mut heap = dive_core::Heap::new(Arc::clone(&store), false, false);
2825 let domain = heap.interval(0, 127);
2826 let domain = heap.intern_const(domain).unwrap();
2827 let action = |name: &str, g| Action {
2828 name: name.into(),
2829 g,
2830 frame: 1,
2832 preset: Vec::new(),
2833 };
2834 let plan = Plan {
2835 code: Code {
2836 nodes: vec![
2837 Node::Const(domain),
2838 Node::Var(0),
2839 Node::Tuple(vec![1; WIDTH].into_boxed_slice()),
2841 Node::Lazy { slot: 0, body: 2 },
2842 Node::Eq(3, 3),
2843 ],
2844 gnodes: vec![
2845 GNode::AssignIn { var: 0, set: 0 },
2846 GNode::Assign { var: 0, rhs: 1 },
2847 ],
2848 ..Code::default()
2849 },
2850 vars: vec!["x".into()],
2851 init: vec![action("Init", 0)],
2852 next: vec![action("Next", 1)],
2853 invariants: vec![Check {
2854 name: "Inv".into(),
2855 frame: 1,
2856 conjuncts: vec![Conjunct {
2857 p: 4,
2858 reads: 1,
2859 skippable: false,
2860 site: None,
2861 }],
2862 }],
2863 constraints: Vec::new(),
2864 action_constraints: Vec::new(),
2865 implied_inits: Vec::new(),
2866 implied_actions: Vec::new(),
2867 check_deadlock: true,
2868 symmetry: None,
2869 effects: Effects::default(),
2870 view: None,
2871 stats: CompileStats::default(),
2872 bound_preset: Vec::new(),
2873 startup_assumptions: Vec::new(),
2874 startup_assumption_false: None,
2875 };
2876 let out = explore(
2877 &plan,
2878 &store,
2879 Config {
2880 opts: Opts::default(),
2881 max_states: None,
2882 max_depth: None,
2883 workers: 1,
2884 warn: true,
2885 sample: None,
2886 },
2887 &|| false,
2888 );
2889 assert_eq!(out.verdict, Verdict::Success);
2890 assert_eq!(out.stats.distinct, STATES);
2891 assert_eq!(out.metrics.thunks, (STATES, STATES));
2892 let (_, handles) = out.metrics.arena_peak;
2894 assert!(
2895 handles < 4 * WIDTH,
2896 "arena peak of {handles} handles holds the initial states' check transients"
2897 );
2898 }
2899
2900 #[test]
2901 fn replay_checks_compound_values_without_hashconsing() -> Result<(), Error> {
2902 let store = Arc::new(Store::new(false));
2903 let mut heap = dive_core::Heap::new(Arc::clone(&store), false, false);
2904 let one = heap.int_from_i64(1);
2905 let two = heap.int_from_i64(2);
2906 let a = heap.tuple(&[one]);
2907 let a = heap.intern(a)?;
2908 let equal = heap.tuple(&[one]);
2909 let equal = heap.intern(equal)?;
2910 let different = heap.tuple(&[two]);
2911 let different = heap.intern(different)?;
2912 assert_ne!(a, equal, "the control must allocate distinct handles");
2913 assert!(replay_values_match(&store, &[a], &[equal]));
2914 assert!(!replay_values_match(&store, &[a], &[different]));
2915 assert!(!replay_values_match(&store, &[a], &[equal, equal]));
2916 assert!(!replay_values_match(&store, &[], &[equal]));
2917 let nested_a = heap.tuple(&[a]);
2918 let nested_a = heap.intern(nested_a)?;
2919 let nested_equal = heap.tuple(&[equal]);
2920 let nested_equal = heap.intern(nested_equal)?;
2921 let nested_different = heap.tuple(&[different]);
2922 let nested_different = heap.intern(nested_different)?;
2923 assert!(replay_values_match(&store, &[nested_a], &[nested_equal]));
2924 assert!(!replay_values_match(
2925 &store,
2926 &[nested_a],
2927 &[nested_different]
2928 ));
2929 Ok(())
2930 }
2931
2932 #[test]
2933 fn seen_set_inserts_and_grows() {
2934 let mut s = Seen::default();
2935 for k in 0..200_000u64 {
2936 assert!(s.insert(k.wrapping_mul(0x9e37_79b9_7f4a_7c15)));
2937 }
2938 assert_eq!(s.len(), 200_000);
2939 assert!(!s.insert(0));
2940 assert!(s.contains(5u64.wrapping_mul(0x9e37_79b9_7f4a_7c15)));
2941 assert!(!s.contains(7));
2942 }
2943}