1use std::collections::BTreeSet;
5
6use dive_eval::{Scope, SlotView};
7use dive_ir::{Arg, DefId, Effects, Expr, ExprId, OpRef, StdOp, StdSupport};
8
9use crate::bind::Binder;
10use crate::model::{Model, Pred, Unsupported, UnsupportedKind};
11use crate::tables::Look;
12
13mod tuple_calls;
14
15pub(crate) fn unsupported(b: &Binder<'_>, model: &Model) -> Vec<Unsupported> {
17 let mut out: Vec<Unsupported> = b
18 .unsupported
19 .iter()
20 .map(|feature| Unsupported {
21 feature: feature.clone(),
22 kind: UnsupportedKind::Feature,
23 })
24 .collect();
25 let ir = &*model.ir;
26 let (roots, _) = checking_path(b, model);
27 let reach = ir.reachable_defs(&roots);
28 let used = ir.reachable_defs(&startup_roots(b, model, roots.clone()));
29 let ordered_names = b.opts.eval.ctx.order == dive_value::ValueOrder::Tlc
37 || b.opts.eval.exploration == dive_eval::ExplorationOrder::Tlc;
38 for refusal in &b.startup_refusals {
39 let reached = used.get(refusal.def.index()).copied().unwrap_or(true);
40 if reached || ordered_names || !effect_free(b, refusal.def) {
41 b.ev()
42 .restore_external_input_refusal(refusal.input_refusal.clone());
43 out.push(Unsupported {
44 feature: refusal.what.clone(),
45 kind: UnsupportedKind::Feature,
46 });
47 }
48 }
49 if !model.implied_temporals.is_empty() {
50 let names: Vec<&str> = model
51 .implied_temporals
52 .iter()
53 .map(|n| n.name.as_str())
54 .collect();
55 out.push(Unsupported {
56 kind: UnsupportedKind::TemporalProperty,
57 feature: format!(
58 "temporal properties (liveness checking): {}",
59 names.join(", ")
60 ),
61 });
62 }
63 if let Some(s) = &model.symmetry
64 && !model.unreduced_symmetry_liveness()
65 {
66 out.push(Unsupported {
67 feature: format!("SYMMETRY {s}"),
68 kind: UnsupportedKind::Feature,
69 });
70 }
71 let mut refused: BTreeSet<String> = BTreeSet::new();
73 for r in ir.refusals() {
74 if reach.get(r.def.index()).copied().unwrap_or(false) {
75 if let dive_ir::Feature::StdOp(op) = &r.feature
76 && matches!(op, StdOp::IoUtilsIOEnv | StdOp::IoUtilsDeserialize)
77 && b.ev().options().host_access.allows(*op)
78 {
79 continue;
80 }
81 refused.insert(r.feature.name());
82 }
83 }
84 for d in &roots {
86 if let Some(op) = ir.def(*d).std
87 && op.support() != dive_ir::StdSupport::Core
88 {
89 if matches!(op, StdOp::IoUtilsIOEnv | StdOp::IoUtilsDeserialize)
90 && b.ev().options().host_access.allows(op)
91 {
92 continue;
93 }
94 refused.insert(dive_ir::Feature::StdOp(op).name());
95 }
96 }
97 out.extend(refused.into_iter().map(|feature| Unsupported {
98 feature,
99 kind: UnsupportedKind::Feature,
100 }));
101 out
102}
103
104fn startup_roots(b: &Binder<'_>, model: &Model, roots: Vec<DefId>) -> Vec<DefId> {
107 let mut out: BTreeSet<DefId> = roots.into_iter().collect();
108 let mut exprs = Vec::new();
109 let mut preds: Vec<&Pred> = Vec::new();
110 for group in [
111 &model.temporals,
112 &model.implied_temporals,
113 &model.configured_properties,
114 ] {
115 preds.extend(group.iter().map(|n| &n.pred));
116 }
117 if let Some(Ok(alias)) = &model.alias {
118 preds.push(&alias.pred);
119 }
120 if let Ok(post) = &model.postconditions {
121 preds.extend(post.iter().map(|n| &n.pred));
122 }
123 for p in preds {
124 role_defs(b, p.expr, &p.scope, &mut out, &mut exprs, 0);
125 }
126 if let Some(Look::Def(d) | Look::Java(_, d)) = &model.symmetry_definition {
127 out.insert(*d);
128 }
129 out.into_iter().collect()
130}
131
132fn reads_only(op: StdOp) -> bool {
135 !op.impure()
136 || matches!(
137 op,
138 StdOp::IoUtilsIOEnv | StdOp::TlcJavaTime | StdOp::TlcTLCGet
139 )
140}
141
142fn effect_free(b: &Binder<'_>, def: DefId) -> bool {
147 effect_free_with(b, def, false)
148}
149
150pub(crate) fn pure(b: &Binder<'_>, def: DefId) -> bool {
154 effect_free_with(b, def, true)
155}
156
157fn effect_free_with(b: &Binder<'_>, def: DefId, strict: bool) -> bool {
161 let reads_only = |op: StdOp| if strict { !op.impure() } else { reads_only(op) };
162 let ir = &*b.t.ir;
163 let mut seen = vec![false; ir.defs().len()];
164 let mut work = vec![def];
165 let substitutions = strict;
171 let constant = |c: dive_ir::ConstId, work: &mut Vec<DefId>| match b.t.const_look(c) {
172 Some(Look::Def(d)) => {
173 work.push(d);
174 true
175 }
176 Some(Look::Java(op, _)) => reads_only(op),
177 Some(Look::Value(_) | Look::Literal(_)) | None => true,
178 };
179 while let Some(d) = work.pop() {
180 match seen.get_mut(d.index()) {
181 Some(s) if !*s => *s = true,
182 Some(_) => continue,
183 None => return false,
184 }
185 if strict {
186 match b.t.lookup_def(d) {
187 Look::Def(r) if r != d => work.push(r),
188 Look::Java(op, r) => {
189 if !reads_only(op) {
190 return false;
191 }
192 if r != d {
193 work.push(r);
194 }
195 }
196 _ => {}
197 }
198 }
199 let def = ir.def(d);
200 if let Some(op) = def.std {
201 if !reads_only(op) {
202 return false;
203 }
204 continue;
205 }
206 let mut exprs = vec![def.body];
207 while let Some(e) = exprs.pop() {
208 let node = ir.node(e);
209 match &node.expr {
210 Expr::Def(x) => work.push(*x),
211 Expr::Let { defs, .. } => work.extend(defs.iter().copied()),
212 Expr::Const(c) => {
213 if !constant(*c, &mut work) {
214 return false;
215 }
216 }
217 Expr::SubstRef { decl, .. } => {
218 if !substitutions {
219 return false;
220 }
221 if let Some(c) = ir.decl(*decl).constant
222 && !constant(c, &mut work)
223 {
224 return false;
225 }
226 }
227 _ => {}
228 }
229 for r in node.expr.op_refs() {
230 let ok = match r {
231 OpRef::Def(x) => {
232 work.push(*x);
233 true
234 }
235 OpRef::Std(op) => reads_only(*op),
236 OpRef::Const(c) => constant(*c, &mut work),
237 OpRef::Subst(decl) => {
238 substitutions
239 && ir
240 .decl(*decl)
241 .constant
242 .is_none_or(|c| constant(c, &mut work))
243 }
244 OpRef::Param(_) => !node.effects.intersects(Effects::IMPURE),
245 OpRef::Builtin(_) | OpRef::Unbound(_) => true,
246 };
247 if !ok {
248 return false;
249 }
250 }
251 node.expr.for_each_child(|child| exprs.push(child));
252 }
253 }
254 true
255}
256
257pub(crate) fn role_defs(
260 b: &Binder<'_>,
261 e: ExprId,
262 scope: &Scope,
263 out: &mut BTreeSet<DefId>,
264 exprs: &mut Vec<ExprId>,
265 depth: u32,
266) {
267 if depth > 64 {
268 return;
269 }
270 exprs.push(e);
271 let ir = &*b.t.ir;
272 let mut stack = vec![e];
273 while let Some(x) = stack.pop() {
274 let expr = ir.expr(x);
275 match expr {
276 Expr::Def(d) => {
277 out.insert(*d);
278 }
279 Expr::Local(r) => {
280 if let SlotView::Lazy(y, s) = b.ev().scope_slot(scope, *r) {
281 role_defs(b, y, &s, out, exprs, depth + 1);
282 }
283 }
284 Expr::SubstRef { decl, .. } => {
285 if let SlotView::Lazy(y, s) = b.ev().scope_subst_slot(scope, *decl) {
286 role_defs(b, y, &s, out, exprs, depth + 1);
287 }
288 }
289 Expr::Let { defs, .. } => out.extend(defs.iter().copied()),
290 _ => {}
291 }
292 for r in expr.op_refs() {
293 if let OpRef::Def(d) = r {
294 out.insert(*d);
295 }
296 }
297 if let Expr::Apply { args, .. } = expr {
298 for a in args {
299 if let Arg::Op {
300 op: OpRef::Def(d), ..
301 } = a
302 {
303 out.insert(*d);
304 }
305 }
306 }
307 stack.extend(expr.children());
308 }
309}
310
311fn checking_path(b: &Binder<'_>, model: &Model) -> (Vec<DefId>, Vec<ExprId>) {
318 let mut roots: BTreeSet<DefId> = BTreeSet::new();
319 let mut exprs: Vec<ExprId> = Vec::new();
320 for p in role_preds(model) {
321 role_defs(b, p.expr, &p.scope, &mut roots, &mut exprs, 0);
322 }
323 roots.extend(model.assumptions.iter().copied());
324 for l in b.t.consts.iter().flatten() {
325 if let Look::Def(d) | Look::Java(_, d) = l {
326 roots.insert(*d);
327 }
328 }
329 for map in [&b.t.tool_obj, &b.t.body_obj] {
330 for l in map.values() {
331 if let Look::Def(d) | Look::Java(_, d) = l {
332 roots.insert(*d);
333 }
334 }
335 }
336 (roots.into_iter().collect(), exprs)
337}
338
339fn role_preds(model: &Model) -> Vec<&Pred> {
343 let mut preds: Vec<&Pred> = Vec::new();
344 preds.extend(model.init.iter().map(|i| &i.pred));
345 preds.extend(model.next.iter());
346 for group in [
347 &model.invariants,
348 &model.implied_inits,
349 &model.implied_actions,
350 &model.constraints,
351 &model.action_constraints,
352 ] {
353 preds.extend(group.iter().map(|n| &n.pred));
354 }
355 if let Some(v) = &model.view {
356 preds.push(&v.pred);
357 }
358 preds
359}
360
361pub(crate) struct Sequential {
362 pub reasons: Vec<String>,
363 pub names_only: bool,
364 pub runtime_names: bool,
365 pub stateful_checking: Option<String>,
366}
367
368fn native_op(ir: &dive_ir::Ir, op: &OpRef) -> Option<StdOp> {
369 match op {
370 OpRef::Std(op) => Some(*op),
371 OpRef::Def(id) => ir.def(*id).std,
372 _ => None,
373 }
374}
375
376fn sequential_op(op: StdOp, key: Option<&Expr>) -> Option<String> {
379 let name = op.qualified_name();
380 if op == StdOp::TlcTLCSet {
381 return Some(format!("{name} (writes TLC's registers)"));
382 }
383 if op == StdOp::TlcTLCGet {
384 return match key {
385 Some(Expr::Str(k)) if !dive_ir::effects::tlcget_string_is_live(k) => None,
386 Some(Expr::Str(k)) => Some(format!(
387 "{name}(\"{k}\") (reads a live counter or a register)"
388 )),
389 Some(Expr::Num(n)) => Some(format!("{name}({n}) (reads a register)")),
390 _ => Some(format!("{name} of a key computed while checking")),
391 };
392 }
393 if matches!(
394 op,
395 StdOp::TlcRandomElement
396 | StdOp::RandomizationRandomSubset
397 | StdOp::RandomizationRandomSetOfSubsets
398 | StdOp::RandomizationRandomSubsetSet
399 ) {
400 return Some(format!(
401 "{name} (draws from the expanded state's random stream)"
402 ));
403 }
404 matches!(op.support(), StdSupport::Io | StdSupport::Introspection)
405 .then(|| format!("{name} ({})", op.support().describe()))
406}
407
408pub const TLC_CDOT: &str = "action composition under `--action-composition=tlc` (TLC counts its intermediate states as generated)";
413
414pub(crate) fn sequential(b: &Binder<'_>, model: &Model) -> crate::bind::R<Sequential> {
434 let ir = &*model.ir;
435 let (roots, mut exprs) = checking_path(b, model);
436 let fixed = startup_fixed(b, ir);
437 let reach = reachable_unfixed(b.ev(), ir, &roots, &fixed);
438 let ordered_names = b.opts.eval.ctx.order == dive_value::ValueOrder::Tlc
439 || b.opts.eval.exploration == dive_eval::ExplorationOrder::Tlc;
440 let mut names: BTreeSet<String> = BTreeSet::new();
441 let mut out: BTreeSet<String> = BTreeSet::new();
442 let mut composition = false;
443 for (i, d) in ir.defs().iter().enumerate() {
444 if reach.get(i).copied().unwrap_or(false) {
445 if let Some(op) = d.std {
446 if native_random(op) {
450 out.extend(sequential_op(op, None));
451 }
452 if ordered_names && op.creates_runtime_names() {
453 names.insert(format!(
454 "{} (runtime names require TLC encounter order)",
455 op.qualified_name()
456 ));
457 }
458 } else if !fixed.get(i).copied().unwrap_or(false) {
459 exprs.push(d.body);
460 }
461 }
462 }
463 let tlc_cdot = b.opts.eval.action_composition == dive_eval::ActionComposition::Tlc;
464 let impure = |e: ExprId| b.ev().impure_after_startup(e);
467 let mut seen = vec![false; ir.nodes().len()];
468 while let Some(e) = exprs.pop() {
469 match seen.get_mut(e.index()) {
470 Some(s) if !*s => *s = true,
471 _ => continue,
472 }
473 let expr = ir.expr(e);
474 match expr {
475 Expr::Apply { callee, args } => {
476 if let Some(op) = native_op(ir, callee) {
477 let key = args.first().and_then(|a| match a {
478 Arg::Expr { expr, .. } => Some(ir.expr(*expr)),
479 Arg::Op { .. } => None,
480 });
481 if ordered_names && op.creates_runtime_names() {
482 names.insert(format!(
483 "{} (runtime names require TLC encounter order)",
484 op.qualified_name()
485 ));
486 }
487 out.extend(sequential_op(op, key));
488 }
489 for a in args {
490 if let Arg::Op { op, .. } = a
491 && let Some(op) = native_op(ir, op)
492 {
493 if ordered_names && op.creates_runtime_names() {
494 names.insert(format!(
495 "{} (runtime names require TLC encounter order)",
496 op.qualified_name()
497 ));
498 }
499 out.extend(sequential_op(op, None));
500 }
501 }
502 }
503 Expr::Cdot(..) if tlc_cdot => {
504 composition = true;
505 }
506 Expr::SetFilter { pred, .. } if impure(*pred) => {
507 out.insert("side effects inside a set filter TLC evaluates lazily".to_owned());
508 }
509 Expr::FcnCons { body, .. } | Expr::RecFcn { body, .. } if impure(*body) => {
510 out.insert("side effects inside a function TLC evaluates lazily".to_owned());
511 }
512 _ => {}
513 }
514 exprs.extend(expr.children());
515 }
516 let ev = b.ev();
517 let shared = role_preds(model)
518 .iter()
519 .any(|p| ev.scope_shares_side_effects(&p.scope));
520 let shared = shared
521 || model
522 .init_actions
523 .iter()
524 .chain(&model.actions)
525 .any(|a| ev.action_shares_side_effects(a));
526 if shared {
527 out.insert(
528 "side effects inside a lazily evaluated value bound with the model, which TLC caches (a LET or an operator argument)".to_owned(),
529 );
530 }
531 let mut classified = classify_sequential(out, names, composition);
532 tuple_calls::remove_proved_concat(b, model, &mut classified.reasons)?;
535 Ok(classified)
536}
537
538fn startup_fixed(b: &Binder<'_>, ir: &dive_ir::Ir) -> Vec<bool> {
542 let ev = b.ev();
543 (0..ir.defs().len())
544 .map(|i| u32::try_from(i).is_ok_and(|i| ev.startup_fixed(DefId(i))))
545 .collect()
546}
547
548fn reachable_unfixed(
552 ev: &dive_eval::Evaluator,
553 ir: &dive_ir::Ir,
554 roots: &[DefId],
555 fixed: &[bool],
556) -> Vec<bool> {
557 let constant = |c: &dive_ir::ConstId| match ev.constant_binding(*c) {
558 Some(dive_eval::ConstBinding::Def(d)) => Some(d),
559 _ => None,
560 };
561 let mut seen = vec![false; ir.defs().len()];
562 let mut work: Vec<DefId> = roots.to_vec();
563 while let Some(d) = work.pop() {
564 let Some(s) = seen.get_mut(d.index()) else {
565 continue;
566 };
567 if *s {
568 continue;
569 }
570 *s = true;
571 work.push(ev.redirected(d));
572 let def = ir.def(d);
573 if def.std.is_some() || fixed.get(d.index()).copied().unwrap_or(false) {
574 continue;
575 }
576 let mut exprs = vec![def.body];
577 while let Some(e) = exprs.pop() {
578 let node = ir.node(e);
579 if let Expr::Def(x) = &node.expr {
580 work.push(*x);
581 }
582 if let Expr::Let { defs, .. } = &node.expr {
583 work.extend(defs.iter().copied());
584 }
585 if let Expr::Const(c) = &node.expr {
586 work.extend(constant(c));
587 }
588 for r in node.expr.op_refs() {
589 match r {
590 OpRef::Def(x) => work.push(*x),
591 OpRef::Const(c) => work.extend(constant(c)),
592 _ => {}
593 }
594 }
595 node.expr.for_each_child(|child| exprs.push(child));
596 }
597 }
598 seen
599}
600
601fn classify_sequential(
602 mut out: BTreeSet<String>,
603 names: BTreeSet<String>,
604 composition: bool,
605) -> Sequential {
606 let stateful_checking = out.first().cloned();
607 if composition {
608 out.insert(TLC_CDOT.to_owned());
609 }
610 let runtime_names = !names.is_empty();
611 let names_only = out.is_empty() && runtime_names;
612 out.extend(names);
613 Sequential {
614 reasons: out.into_iter().collect(),
615 names_only,
616 runtime_names,
617 stateful_checking,
618 }
619}
620
621fn native_random(op: StdOp) -> bool {
622 matches!(
623 op,
624 StdOp::TlcRandomElement
625 | StdOp::RandomizationRandomSubset
626 | StdOp::RandomizationRandomSetOfSubsets
627 | StdOp::RandomizationRandomSubsetSet
628 )
629}