1use std::cell::Cell;
6use std::collections::HashMap;
7use std::sync::{Arc, Mutex, OnceLock, PoisonError};
8
9use dive_ir::{DefId, Expr, ExprId, Ir};
10use dive_value::{Atom, Ctx, DeferredKind, Int, Interner, SetKind, Value, ValueOrder};
11
12use crate::error::{EvalError, Result};
13use crate::options::Options;
14use crate::{ConstBinding, Model};
15
16#[derive(Clone, Debug)]
18pub(crate) enum Lit {
19 None,
21 Val(Value),
23 Err(EvalError),
26}
27
28pub trait PrintSink: Send + Sync {
30 fn print(&self, text: String);
33}
34
35#[derive(Default, Debug)]
37pub struct CollectSink {
38 lines: Mutex<Vec<String>>,
39}
40
41impl CollectSink {
42 pub fn take(&self) -> Vec<String> {
44 std::mem::take(&mut *self.lines.lock().unwrap_or_else(PoisonError::into_inner))
45 }
46}
47
48impl PrintSink for CollectSink {
49 fn print(&self, text: String) {
50 self.lines
51 .lock()
52 .unwrap_or_else(PoisonError::into_inner)
53 .push(text);
54 }
55}
56
57pub(crate) struct Core {
59 pub(crate) input_refusal: Mutex<Option<String>>,
60 pub(crate) text_input_used: std::sync::atomic::AtomicBool,
62 pub(crate) environment_initialized: std::sync::atomic::AtomicBool,
64 pub(crate) input_name_baseline: usize,
66 pub(crate) receiver_domain: Option<dive_value::ReceiverDomain>,
67 pub(crate) ir: Arc<Ir>,
68 pub(crate) opts: Options,
69 pub(crate) ctx: Ctx,
70 pub(crate) names: Arc<Interner>,
71 pub(crate) consts: Vec<Option<ConstBinding>>,
72 pub(crate) redirects: HashMap<DefId, DefId>,
73 pub(crate) def_values: HashMap<DefId, Value>,
74 pub(crate) std_redirects: HashMap<dive_ir::StdOp, DefId>,
77 pub(crate) std_redirect_table: Box<[Option<DefId>]>,
80 pub(crate) redirect_table: Box<[Option<DefId>]>,
83 pub(crate) lits: Vec<Lit>,
84 pub(crate) fields: Vec<Option<Box<[Atom]>>>,
87 pub(crate) frame_owners: Vec<DefId>,
88 pub(crate) frame_required: Vec<bool>,
89 pub(crate) def_cache: Vec<OnceLock<Value>>,
93 pub(crate) constant_cache_safe: Vec<OnceLock<bool>>,
97 pub(crate) call_cache_safe: Vec<OnceLock<Option<Arc<[dive_ir::DeclId]>>>>,
101 pub(crate) startup_calls: Mutex<Option<crate::startup_calls::StartupCalls>>,
104 pub(crate) startup_call_hits: std::sync::atomic::AtomicU64,
106 pub(crate) open_ok: bool,
111 pub(crate) warned: Mutex<std::collections::HashSet<String>>,
113 pub(crate) startup: Vec<OnceLock<Value>>,
117 pub(crate) startup_eager: Vec<OnceLock<bool>>,
120 pub(crate) sink: Arc<dyn PrintSink>,
121 pub(crate) printed: std::sync::atomic::AtomicBool,
123 pub(crate) simulation_active: std::sync::atomic::AtomicBool,
125 pub(crate) host: crate::host::HostSlot,
127 pub(crate) startup_names: std::sync::atomic::AtomicUsize,
130}
131
132impl std::fmt::Debug for Core {
133 fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
134 f.debug_struct("Core")
135 .field("opts", &self.opts)
136 .finish_non_exhaustive()
137 }
138}
139
140thread_local! {
141 static LOOP_WORK: Cell<u16> = const { Cell::new(1024) };
144}
145
146impl Core {
147 #[inline]
149 pub(crate) fn loop_work(&self) -> Result<()> {
150 let due = LOOP_WORK.with(|counter| {
151 let remaining = counter.get() - 1;
152 counter.set(if remaining == 0 { 1024 } else { remaining });
153 remaining == 0
154 });
155 if due && !dive_value::quiet_operation_active() {
159 self.host.check_control()
160 } else {
161 Ok(())
162 }
163 }
164
165 pub(crate) fn new(model: Model, opts: Options, sink: Arc<dyn PrintSink>) -> Self {
166 let ir = model.ir;
167 let names = model.names;
168 let (frame_owners, frame_required) = crate::context::frame_metadata(&ir);
169 let n = ir.nodes().len();
170 let mut lits = Vec::with_capacity(n);
171 let mut fields = Vec::with_capacity(n);
172 for node in ir.nodes() {
173 lits.push(match &node.expr {
174 Expr::Bool(b) => Lit::Val(Value::Bool(*b)),
175 Expr::Num(text) => match Int::from_literal(text, opts.ctx.int_mode) {
176 Ok(i) => Lit::Val(Value::int(i)),
177 Err(e) => Lit::Err(e.into()),
178 },
179 Expr::Decimal { int, frac } => Lit::Err(EvalError::coded(
180 crate::error::Ec::CantHandleReal,
181 format!("TLC can't handle real numbers.\n{int}.{frac}"),
182 )),
183 Expr::Str(s) => Lit::Val(Value::string(&names, s)),
184 _ => Lit::None,
185 });
186 fields.push(match &node.expr {
187 Expr::Record(fs) | Expr::RecordSet(fs) => {
188 Some(fs.iter().map(|f| names.intern(&f.name)).collect())
189 }
190 Expr::RecordSelect { field, .. } => {
191 Some(Box::new([names.intern(field)]) as Box<[Atom]>)
192 }
193 _ => None,
194 });
195 }
196 let def_cache = (0..ir.defs().len()).map(|_| OnceLock::new()).collect();
197 let constant_cache_safe = (0..ir.defs().len()).map(|_| OnceLock::new()).collect();
198 let call_cache_safe = (0..ir.defs().len()).map(|_| OnceLock::new()).collect();
199 let constant_pure = |d: &DefId| {
200 let def = ir.def(*d);
201 def.level == dive_ir::Level::Constant
202 && !def.effects.intersects(dive_ir::Effects::IMPURE)
203 };
204 let open_ok = model.constants.iter().flatten().all(|b| match b {
205 ConstBinding::Def(d) => constant_pure(d),
206 ConstBinding::Value(_) => true,
207 }) && model.redirects.values().all(constant_pure);
208 let startup = (0..ir.defs().len()).map(|_| OnceLock::new()).collect();
209 let startup_eager = (0..ir.defs().len()).map(|_| OnceLock::new()).collect();
210 let std_redirects = model
211 .redirects
212 .iter()
213 .filter_map(|(d, t)| ir.def(*d).std.map(|op| (op, *t)))
214 .collect::<HashMap<_, _>>();
215 let mut std_redirect_table = vec![None; dive_ir::StdOp::ALL.len()].into_boxed_slice();
216 for (&op, &target) in &std_redirects {
217 if let Some(slot) = std_redirect_table.get_mut(op as usize) {
218 *slot = Some(target);
219 }
220 }
221 let mut redirect_table = vec![None; ir.defs().len()].into_boxed_slice();
222 for (&source, &target) in &model.redirects {
223 if let Some(slot) = redirect_table.get_mut(source.index()) {
224 *slot = Some(target);
225 }
226 }
227 Self {
228 input_refusal: Mutex::new(None),
229 text_input_used: std::sync::atomic::AtomicBool::new(false),
230 environment_initialized: std::sync::atomic::AtomicBool::new(false),
231 input_name_baseline: names.len(),
232 receiver_domain: dive_value::ReceiverDomain::new(),
233 ir,
234 ctx: opts.ctx,
235 opts,
236 names,
237 consts: model.constants,
238 redirects: model.redirects,
239 def_values: model.def_values,
240 std_redirects,
241 std_redirect_table,
242 redirect_table,
243 lits,
244 fields,
245 frame_owners,
246 frame_required,
247 def_cache,
248 constant_cache_safe,
249 call_cache_safe,
250 startup_calls: Mutex::default(),
251 startup_call_hits: std::sync::atomic::AtomicU64::new(0),
252 open_ok,
253 warned: Mutex::default(),
254 startup,
255 startup_eager,
256 sink,
257 printed: std::sync::atomic::AtomicBool::new(false),
258 startup_names: std::sync::atomic::AtomicUsize::new(0),
259 host: crate::host::HostSlot::default(),
260 simulation_active: std::sync::atomic::AtomicBool::new(false),
261 }
262 }
263
264 pub(crate) fn startup_error(&self) -> Option<EvalError> {
269 for (i, lit) in self.lits.iter().enumerate() {
270 let Lit::Err(e) = lit else { continue };
271 let node = &self.ir.nodes()[i];
272 let standard = node
273 .origin
274 .file
275 .and_then(|f| self.ir.files().get(f.index()))
276 .is_some_and(|f| f.standard);
277 if !standard {
278 return Some(e.clone());
279 }
280 }
281 None
282 }
283
284 pub(crate) fn loc(&self, e: ExprId) -> String {
287 let Some(node) = self.ir.nodes().get(e.index()) else {
288 return format!("unknown expression #{}", e.0);
289 };
290 match &node.expr {
291 Expr::Num(text) => text.to_string(),
292 Expr::Decimal { int, frac } => format!("{int}.{frac}"),
293 _ => self.ir.location(&node.origin),
294 }
295 }
296
297 pub(crate) fn ppr(&self, v: &Value) -> String {
299 dive_value::print::print_value(v, self.ctx)
300 .unwrap_or_else(|_| dive_value::print::to_tlc_string_lenient(v, self.ctx))
301 }
302
303 pub(crate) fn explore(&self, set: &dive_value::Set) -> Result<Arc<[Value]>> {
306 self.enum_guard(set)?;
307 let elems = set.elements(self.ctx)?;
308 let order = self.opts.explore_order();
309 if order == set.order() || elems.len() < 2 || !needs_resort(&elems) {
310 return Ok(elems);
311 }
312 let mut v = elems.to_vec();
313 v.sort_by(|a, b| a.cmp_with(b, order));
314 Ok(v.into())
315 }
316
317 pub(crate) fn enum_guard(&self, set: &dive_value::Set) -> Result<()> {
321 let comps = set.components();
322 match set.kind() {
323 SetKind::Subset => {
324 if let Some((_, b)) = comps.first() {
325 if is_user_value(b) {
326 return Err(EvalError::general(format!(
327 "Attempted to compute the number of elements in the overridden value {}.",
328 self.ppr(b)
329 )));
330 }
331 if let Value::Set(bs) = b {
332 self.enum_guard(bs)?;
333 }
334 }
335 }
336 SetKind::FcnSet => {
337 if let (Some((_, d)), Some((_, r))) = (comps.first(), comps.get(1)) {
338 if structural_set_operand(d)
342 && structural_set_operand(r)
343 && (dive_value::tlc::is_empty(d, self.ctx)?
344 || dive_value::tlc::is_empty(r, self.ctx)?)
345 {
346 return Ok(());
347 }
348 if is_user_value(d) {
349 return Err(EvalError::general(format!(
350 "Attempted to enumerate a set of the form [D -> R],but the domain D:\n{}\ncannot be enumerated.",
351 self.ppr(d)
352 )));
353 }
354 if let Value::Set(ds) = d {
355 self.enum_guard(ds)?;
356 }
357 if is_user_value(r) && !dive_value::tlc::is_empty(d, self.ctx)? {
358 return Err(EvalError::general(format!(
359 "Attempted to enumerate a set of the form [D -> R],but the range R:\n{}\ncannot be enumerated.",
360 self.ppr(r)
361 )));
362 }
363 if let Value::Set(rs) = r {
364 self.enum_guard(rs)?;
365 }
366 }
367 }
368 SetKind::Product | SetKind::RcdSet => {
369 for (_, c) in &comps {
370 if is_user_value(c) {
371 return Err(EvalError::unsupported(format!(
372 "enumerating {} with the infinite component {}",
373 self.ppr(&Value::Set(set.clone())),
374 self.ppr(c)
375 )));
376 }
377 if let Value::Set(cs) = c {
378 self.enum_guard(cs)?;
379 }
380 }
381 }
382 SetKind::Seq | SetKind::Nat | SetKind::Int | SetKind::Strings => {
383 return Err(EvalError::unsupported(format!(
384 "enumerating the infinite set {}",
385 self.ppr(&Value::Set(set.clone()))
386 )));
387 }
388 _ => {}
389 }
390 Ok(())
391 }
392
393 pub(crate) fn size_guard(&self, set: &dive_value::Set) -> Result<()> {
396 if let Some((d, r)) = set.as_fcn_set()
397 && structural_set_operand(d)
398 && structural_set_operand(r)
399 {
400 if dive_value::tlc::is_empty(d, self.ctx)? || dive_value::tlc::is_empty(r, self.ctx)? {
401 return Ok(());
402 }
403 self.component_size_guard(r)?;
406 if let Value::Set(rs) = r
407 && rs.size(self.ctx)? == 1
408 {
409 return Ok(());
410 }
411 return self.component_size_guard(d);
412 }
413 for (_, c) in set.components() {
414 self.component_size_guard(&c)?;
415 }
416 Ok(())
417 }
418
419 fn component_size_guard(&self, c: &Value) -> Result<()> {
420 if is_user_value(c) {
421 return Err(EvalError::general(format!(
422 "Attempted to compute the number of elements in the overridden value {}.",
423 self.ppr(c)
424 )));
425 }
426 if let Value::Set(cs) = c {
427 self.size_guard(cs)?;
428 }
429 Ok(())
430 }
431
432 pub(crate) fn explore_unsized(&self, set: &dive_value::Set) -> Result<Arc<[Value]>> {
437 match self.explore(set) {
438 Err(e)
439 if e.is_eval()
440 && (e
441 .message()
442 .starts_with("Overflow when computing the number of elements")
443 || e.message().contains("more elements than dive enumerates")) =>
444 {
445 Err(EvalError::unsupported(format!(
446 "enumerating, without materializing it, a set too large to size: {}",
447 e.message().lines().last().unwrap_or("")
448 )))
449 }
450 r => r,
451 }
452 }
453
454 pub(crate) fn print(&self, text: String) {
457 self.printed
458 .store(true, std::sync::atomic::Ordering::Relaxed);
459 if let Some(text) = crate::capture::push(text, false) {
460 self.sink.print(text);
461 }
462 }
463
464 pub(crate) fn print_warning(&self, msg: String) {
468 if crate::capture::active() {
469 let _ = crate::capture::push(msg, true);
470 } else if self.first_warning(&msg) {
471 self.sink.print(msg);
472 }
473 }
474
475 pub(crate) fn first_warning(&self, msg: &str) -> bool {
477 let mut warned = self.warned.lock().unwrap_or_else(PoisonError::into_inner);
478 if warned.contains(msg) {
479 false
480 } else {
481 warned.insert(msg.to_owned());
482 true
483 }
484 }
485
486 pub(crate) fn evaluation_depth() -> u32 {
488 DEPTH.with(Cell::get)
489 }
490
491 pub(crate) fn enter(&self, what: ExprId) -> Result<DepthGuard> {
493 DEPTH.with(|d| {
494 let n = d.get();
495 if n >= self.opts.max_depth {
496 return Err(EvalError::resource_limit(format!(
497 "evaluation nested more than {} levels deep (recursion at {})",
498 self.opts.max_depth,
499 self.loc(what)
500 ))
501 .at(what));
502 }
503 d.set(n + 1);
504 Ok(DepthGuard)
505 })
506 }
507}
508
509fn needs_resort(elems: &[Value]) -> bool {
512 fn has_name(v: &Value, depth: u32) -> bool {
513 if depth > 64 {
514 return true;
515 }
516 match v {
517 Value::Str(_) | Value::Model(_) => true,
518 Value::Bool(_) | Value::Int(_) | Value::BigInt(_) => false,
519 Value::Fcn(f) => {
520 f.as_record().is_some()
521 || f.iter()
522 .any(|(d, x)| has_name(&d, depth + 1) || has_name(x, depth + 1))
523 }
524 Value::Set(s) => !matches!(s.kind(), SetKind::Interval | SetKind::Nat | SetKind::Int),
525 }
526 }
527 elems.iter().any(|v| has_name(v, 0))
528}
529
530thread_local! {
531 static DEPTH: Cell<u32> = const { Cell::new(0) };
532}
533
534pub(crate) struct DepthGuard;
536
537impl Drop for DepthGuard {
538 fn drop(&mut self) {
539 DEPTH.with(|d| d.set(d.get().saturating_sub(1)));
540 }
541}
542
543pub(crate) fn kind_string(v: &Value) -> &'static str {
545 match v {
546 Value::Bool(_) => "a Boolean value",
547 Value::Int(_) | Value::BigInt(_) => "an integer",
548 Value::Str(_) => "a string",
549 Value::Model(_) => "a model value",
550 Value::Fcn(f) => {
551 if f.is_record_literal() {
552 "a record"
553 } else if f.is_tuple_literal() {
554 "a tuple"
555 } else {
556 "a function of the form (d1 :> e1 @@ ... @@ dN :> eN)"
557 }
558 }
559 Value::Set(s) => set_kind_string(s),
560 }
561}
562
563fn set_kind_string(s: &dive_value::Set) -> &'static str {
564 match s.kind() {
565 SetKind::Enum | SetKind::Raw => "a set of the form {e1, ... ,eN}",
566 SetKind::Interval => "a set of the form i..j",
567 SetKind::Subset => "a set of the form SUBSET S",
568 SetKind::FcnSet => "a set of the form [S -> T]",
569 SetKind::RcdSet => "a set of the form [d1 : S1, ... , dN : SN]",
570 SetKind::Product => "a cartesian product",
571 SetKind::Nat | SetKind::Int | SetKind::Strings | SetKind::Seq => "a special set constant",
572 SetKind::Deferred => deferred_kind_string(s),
573 }
574}
575
576fn deferred_kind_string(s: &dive_value::Set) -> &'static str {
577 match s.as_deferred().map(|d| d.kind()) {
578 Some(DeferredKind::Cup) => "a set of the form S \\cup T",
579 Some(DeferredKind::Cap) => "a set of the form S \\cap T",
580 Some(DeferredKind::Diff) => "a set of the form S \\ T",
581 Some(DeferredKind::Union) => "a set of the form UNION S",
582 Some(DeferredKind::Map) => "a set of the form {e1, ... ,eN}",
583 _ => "a set of the form {x \\in S : expr}",
584 }
585}
586
587pub(crate) fn java_class(v: &Value) -> &'static str {
590 match v {
591 Value::Bool(_) => "BoolValue",
592 Value::Int(_) | Value::BigInt(_) => "IntValue",
593 Value::Str(_) => "StringValue",
594 Value::Model(_) => "ModelValue",
595 Value::Fcn(f) => {
596 if f.is_record_literal() {
597 "RecordValue"
598 } else if f.is_tuple_literal() {
599 "TupleValue"
600 } else {
601 "FcnRcdValue"
602 }
603 }
604 Value::Set(s) => match s.kind() {
605 SetKind::Enum | SetKind::Raw => "SetEnumValue",
606 SetKind::Interval => "IntervalValue",
607 SetKind::Subset => "SubsetValue",
608 SetKind::FcnSet => "SetOfFcnsValue",
609 SetKind::RcdSet => "SetOfRcdsValue",
610 SetKind::Product => "SetOfTuplesValue",
611 SetKind::Nat | SetKind::Int | SetKind::Strings | SetKind::Seq => "UserValue",
612 SetKind::Deferred => match s.as_deferred().map(|d| d.kind()) {
613 Some(DeferredKind::Cup) => "SetCupValue",
614 Some(DeferredKind::Cap) => "SetCapValue",
615 Some(DeferredKind::Diff) => "SetDiffValue",
616 Some(DeferredKind::Union) => "UnionValue",
617 Some(DeferredKind::Map) => "SetEnumValue",
618 _ => "SetPredValue",
619 },
620 },
621 }
622}
623
624pub(crate) fn is_user_value(v: &Value) -> bool {
627 matches!(v, Value::Set(s) if matches!(s.kind(), SetKind::Nat | SetKind::Int | SetKind::Strings | SetKind::Seq))
628}
629
630pub(crate) fn is_reducible(v: &Value) -> bool {
632 matches!(v, Value::Set(s) if matches!(s.kind(), SetKind::Enum | SetKind::Raw | SetKind::Interval))
633}
634
635pub(crate) fn is_enumerable(v: &Value) -> bool {
638 matches!(v, Value::Set(s) if !matches!(s.kind(), SetKind::Nat | SetKind::Int | SetKind::Strings | SetKind::Seq))
639}
640
641pub(crate) const TLC_ORDER: ValueOrder = ValueOrder::Tlc;
643
644fn structural_set_operand(value: &Value) -> bool {
647 let mut todo = vec![value.clone()];
648 while let Some(v) = todo.pop() {
649 if let Value::Fcn(f) = &v {
650 todo.extend(f.iter().flat_map(|(d, v)| [d, v.clone()]));
651 continue;
652 }
653 let Value::Set(s) = v else { continue };
654 if s.kind() == SetKind::Deferred {
655 return false;
656 }
657 if let Some(elements) = s.raw_elements() {
658 todo.extend(elements.iter().cloned());
659 }
660 todo.extend(s.components().into_iter().map(|(_, v)| v));
661 }
662 true
663}
664
665#[cfg(test)]
666mod print_events {
667 #![allow(clippy::expect_used, reason = "test setup")]
668 use super::*;
669
670 #[test]
671 fn actual_empty_print_event_survives_drain_and_quiet_capture_without_sink_calls() {
672 let analysis = dive_sema::analyze_source(
673 "PrintFacts.tla",
674 "---- MODULE PrintFacts ----\nEXTENDS TLC\nUnused == PrintT(\"unused\")\n====\n",
675 &dive_sema::Options::default(),
676 );
677 assert!(analysis.accepted());
678 let ir = Arc::new(dive_ir::lower(&analysis).expect("IR"));
679 let ev = crate::Evaluator::new(crate::Model::new(ir), Options::tlc()).expect("context");
680 assert!(
681 !ev.has_print_event(),
682 "unused Print definition is not execution"
683 );
684 ev.core.print_warning("warning".into());
685 assert!(!ev.has_print_event(), "warnings are separate events");
686 assert_eq!(ev.take_output(), ["warning"]);
687 let cap = crate::capture::PrintCapture::start();
688 ev.core.print(String::new());
689 assert!(ev.has_print_event());
690 assert!(ev.take_output().is_empty(), "quiet event did not call sink");
691 assert_eq!(
692 cap.take(),
693 [crate::capture::Captured {
694 text: String::new(),
695 warning: false
696 }]
697 );
698 drop(cap);
699 assert!(
700 ev.has_print_event(),
701 "draining a quiet capture does not erase execution"
702 );
703 }
704}