use std::collections::BTreeSet;
use std::sync::atomic::{AtomicBool, AtomicI64, AtomicU64, Ordering};
use std::sync::{Arc, Mutex, PoisonError};
use dive_eval::{AssumptionOutcome, ErrorClass, EvalError, Host, HostError, St, StateRef};
use dive_ir::StdOp;
use dive_model::{Model, Pred};
use dive_value::{Ctx, Value};
use crate::format::Ending;
use crate::trace::Trace;
#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash)]
#[non_exhaustive]
pub enum Check {
Shape,
Length,
Assumption,
Init,
Next,
Label,
Constraint,
ActionConstraint,
Invariant,
ImpliedInit,
ImpliedAction,
Ending,
Fairness,
Temporal,
}
impl Check {
#[must_use]
pub fn name(self) -> &'static str {
match self {
Self::Shape => "shape",
Self::Length => "length",
Self::Assumption => "assumption",
Self::Init => "init",
Self::Next => "next",
Self::Label => "label",
Self::Constraint => "constraint",
Self::ActionConstraint => "action-constraint",
Self::Invariant => "invariant",
Self::ImpliedInit => "implied-init",
Self::ImpliedAction => "implied-action",
Self::Ending => "ending",
Self::Fairness => "fairness",
Self::Temporal => "temporal",
}
}
}
#[derive(Clone, Debug, PartialEq, Eq)]
pub struct Failure {
pub state: usize,
pub check: Check,
pub detail: String,
}
#[derive(Clone, Debug, PartialEq, Eq)]
#[non_exhaustive]
pub enum Validation {
Valid,
Invalid(Failure),
Unsupported(String),
}
impl Validation {
#[must_use]
pub fn is_valid(&self) -> bool {
matches!(self, Self::Valid)
}
#[must_use]
pub fn kind(&self) -> &'static str {
match self {
Self::Valid => "valid",
Self::Invalid(_) => "invalid",
Self::Unsupported(_) => "unsupported",
}
}
}
#[derive(Clone, Debug, PartialEq, Eq)]
pub struct Report {
pub validation: Validation,
pub notes: Vec<String>,
pub length: usize,
}
#[derive(Clone, Debug, PartialEq, Eq)]
pub struct ValidationProgress {
pub checks_passed: u64,
pub state: Option<usize>,
pub check: Option<Check>,
}
#[derive(Clone, Debug, PartialEq, Eq)]
#[non_exhaustive]
pub enum ValidationRunError {
Interrupted {
error: EvalError,
progress: ValidationProgress,
},
ResourceLimit {
error: EvalError,
progress: ValidationProgress,
},
EvaluationFailure {
error: EvalError,
progress: ValidationProgress,
},
BindingFailure {
error: dive_model::BindError,
progress: ValidationProgress,
},
ThreadFailure(String),
ControlConflict(dive_eval::HostControlConflict),
}
impl std::fmt::Display for ValidationRunError {
fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
match self {
Self::Interrupted { error, .. }
| Self::ResourceLimit { error, .. }
| Self::EvaluationFailure { error, .. } => error.fmt(f),
Self::BindingFailure { error, .. } => error.fmt(f),
Self::ThreadFailure(message) => f.write_str(message),
Self::ControlConflict(error) => error.fmt(f),
}
}
}
impl std::error::Error for ValidationRunError {}
pub const DEADLOCK_UNSUPPORTED: &str = "deadlock: ENABLED of the next-state relation could not be decided on the last state; every other check passed";
pub const RUNTIME_NAMES_UNSUPPORTED: &str = "runtime string encounter order: decoding the trace or checking it created a string or model value that was not interned when the model was bound, and its order relative to other names depends on evaluations outside the trace";
pub const RANDOM_UNSUPPORTED: &str = "a random draw: the value depends on the checking run's stream position, which only the successor generator determines, so the independent validator cannot check it";
pub const REGISTERS_UNSUPPORTED: &str = "TLCGet/TLCSet registers: their contents depend on evaluations outside the trace, so the independent validator cannot read or write them";
pub const COMPOSITION_UNSUPPORTED: &str = "action composition: independent replay requires TLA mode, pure finite complete intermediates and at most one complete tail successor";
pub(crate) enum Stop {
Invalid(Failure),
Unsupported(String),
Interrupted {
error: EvalError,
state: Option<usize>,
check: Option<Check>,
},
ControlConflict(dive_eval::HostControlConflict),
}
impl Stop {
fn at(self, state: Option<usize>, check: Check) -> Self {
match self {
Self::Interrupted { error, .. } => Self::Interrupted {
error,
state,
check: Some(check),
},
other => other,
}
}
}
impl From<Stop> for Validation {
fn from(s: Stop) -> Self {
match s {
Stop::Invalid(f) => Self::Invalid(f),
Stop::Unsupported(u) => Self::Unsupported(u),
Stop::Interrupted { .. } => Self::Unsupported(
"the caller interrupted validation; use validate_controlled for typed transport"
.into(),
),
Stop::ControlConflict(error) => Self::Unsupported(error.to_string()),
}
}
}
enum Goal {
Invariant(usize),
InvariantError(usize, String),
ImpliedInit(usize),
ImpliedAction(usize),
Deadlock,
Behavior,
Liveness(&'static str),
ErrorEnd(&'static str),
TemporalStateError,
NextStateError,
}
enum AssumptionControl {
Unit,
Cooperative,
}
#[derive(Clone, Copy, Debug, PartialEq, Eq)]
pub(crate) enum FiniteScope {
Behavior,
Sample,
SampledDeadlock,
}
pub(crate) struct Run<'a> {
model: &'a Model,
host: Arc<TraceHost>,
inner: Option<Arc<dyn Host>>,
pub(crate) passed: u64,
pub(crate) notes: BTreeSet<String>,
private_init: bool,
pub(crate) init_incomplete: bool,
endpoint_prepared: bool,
endpoint_exception: Option<(EvalError, Option<usize>, Check)>,
control: Option<Arc<dyn dive_eval::HostControl>>,
assumption_control: AssumptionControl,
finite_scope: FiniteScope,
}
impl<'a> Run<'a> {
pub(crate) fn new(model: &'a Model) -> Self {
let inner = model.evaluator.host();
let host = Arc::new(TraceHost {
level: AtomicI64::new(0),
inner: inner.clone(),
drew: Mutex::new(None),
any: AtomicBool::new(false),
registers: AtomicBool::new(false),
composition: AtomicBool::new(false),
register_used: AtomicBool::new(false),
startup: AtomicBool::new(false),
next_error: AtomicBool::new(false),
effect: Mutex::new(None),
private: false,
run_config: Mutex::new(None),
cache_domain: next_cache_domain(),
choices: None,
predicate_init: AtomicBool::new(false),
predicate_next: AtomicBool::new(false),
inputs: None,
});
model.evaluator.set_host(host.clone());
Self {
model,
host,
inner,
passed: 0,
notes: BTreeSet::new(),
private_init: false,
init_incomplete: false,
endpoint_prepared: false,
endpoint_exception: None,
control: None,
assumption_control: AssumptionControl::Unit,
finite_scope: FiniteScope::Behavior,
}
}
pub(crate) fn private(model: &'a Model, host: Arc<TraceHost>, initial: bool) -> Self {
let inner = model.evaluator.replace_host(Some(host.clone()));
let notes = if host.inputs.is_some() {
BTreeSet::from(["External inputs are explicit assumptions. Fresh source replay verifies their ordered use; it does not authenticate past host contents.".into()])
} else {
BTreeSet::new()
};
Self {
model,
host,
inner,
passed: 0,
notes,
private_init: initial,
init_incomplete: false,
endpoint_prepared: false,
endpoint_exception: None,
control: None,
assumption_control: AssumptionControl::Unit,
finite_scope: FiniteScope::Behavior,
}
}
pub(crate) fn validate(&mut self, trace: &Trace) -> Validation {
self.validate_result(trace).unwrap_or_else(Validation::from)
}
fn validate_result(&mut self, trace: &Trace) -> Result<Validation, Stop> {
let v = match self.run(trace) {
Ok(None) => Validation::Valid,
Ok(Some(why)) => Validation::Unsupported(why),
Err(stop @ (Stop::Interrupted { .. } | Stop::ControlConflict(_))) => return Err(stop),
Err(stop) => stop.into(),
};
let v = self.refusal().map_or(v, Validation::Unsupported);
if v == Validation::Valid {
self.poll(None, None)?;
}
Ok(v)
}
fn poll(&self, state: Option<usize>, check: Option<Check>) -> Result<(), Stop> {
if let Some(control) = &self.control {
control.check().map_err(|interrupted| Stop::Interrupted {
error: EvalError::interrupted(interrupted),
state,
check,
})?;
}
Ok(())
}
pub(crate) fn refusal(&self) -> Option<String> {
if let Some(feature) = self.model.evaluator.external_input_refusal() {
return Some(feature);
}
if self.host.inputs.is_none() && !self.model.evaluator.options().host_access.is_empty() {
return Some(
"external inputs require a fresh Session with explicit recorded assumptions".into(),
);
}
if let Some(error) = self
.host
.inputs
.as_ref()
.and_then(|inputs| inputs.failure())
{
return Some(error.message);
}
if let Some(reason) = self
.host
.choices
.as_ref()
.and_then(|choices| choices.refusal())
{
return Some(reason);
}
if let Some(effect) = self
.host
.effect
.lock()
.unwrap_or_else(PoisonError::into_inner)
.clone()
{
return Some(effect);
}
if self.host.any.load(Ordering::Relaxed) {
let op = self
.host
.drew
.lock()
.unwrap_or_else(PoisonError::into_inner)
.map_or_else(|| "a random operator".to_owned(), StdOp::qualified_name);
return Some(format!("{op}: {RANDOM_UNSUPPORTED}"));
}
if self.host.registers.load(Ordering::Relaxed) {
return Some(REGISTERS_UNSUPPORTED.to_owned());
}
if self.host.composition.load(Ordering::Relaxed) {
return Some(COMPOSITION_UNSUPPORTED.to_owned());
}
self.model
.has_runtime_names()
.then(|| RUNTIME_NAMES_UNSUPPORTED.to_owned())
}
#[allow(
clippy::too_many_lines,
reason = "every trace check, in the order the search makes them"
)]
fn run(&mut self, trace: &Trace) -> Result<Option<String>, Stop> {
self.poll(None, None)?;
let m = self.model;
if matches!(
trace.ending,
Ending::TemporalStateError { .. }
| Ending::TemporalSourceError { .. }
| Ending::NextStateError { .. }
| Ending::ViewSourceError { .. }
| Ending::CandidateStateError { .. }
| Ending::PartialNext { .. }
| Ending::PartialInit { .. }
) && (!self.host.private || !self.endpoint_prepared)
{
return Err(Stop::Unsupported(
"temporal error endpoint requires a privately reconstructed source session".into(),
));
}
let n = trace.states.len();
if n == 0 {
return Err(invalid(0, Check::Shape, "the trace has no states"));
}
if trace.labels.len() != n {
return Err(invalid(
0,
Check::Shape,
"the trace has a label list of the wrong length",
));
}
if let Some(len) = trace.length
&& len != n
{
return Err(invalid(
n - 1,
Check::Length,
format!("the trace claims {len} states but has {n}"),
));
}
let vars = m.ir.vars().len();
for (k, s) in trace.states.iter().enumerate() {
if k.is_multiple_of(1024) {
self.poll(Some(k), Some(Check::Shape))?;
}
if s.len() != vars || s.iter().any(Option::is_none) {
return Err(invalid(
k,
Check::Shape,
"the state does not assign every variable",
));
}
crate::trace::validate_state_names(m, s).map_err(Stop::Unsupported)?;
}
let named_lasso = !trace.properties.is_empty();
if named_lasso {
self.host.startup.store(false, Ordering::Relaxed);
self.prepare_periodic(&trace.ending, &trace.properties)?;
self.host
.startup
.store(self.private_init, Ordering::Relaxed);
}
self.assumptions()?;
if self.private_init {
self.host
.startup
.store(self.private_init, Ordering::Relaxed);
}
let last = if matches!(trace.ending, Ending::CandidateStateError { .. }) {
n.checked_sub(2).ok_or_else(|| {
invalid(
0,
Check::Shape,
"candidate error requires a complete source prefix and terminal row",
)
})?
} else {
n - 1
};
let goal = self.goal(&trace.ending, last)?;
let terminal_before_exclusion = matches!(
goal,
Goal::Invariant(_)
| Goal::InvariantError(..)
| Goal::ImpliedInit(_)
| Goal::ImpliedAction(_)
);
let behavior =
matches!(goal, Goal::Behavior) && matches!(self.finite_scope, FiniteScope::Behavior);
for k in 0..=last {
if k.is_multiple_of(1024) {
self.poll(Some(k), None)?;
}
if let Some(choices) = &self.host.choices {
choices.prefer(&trace.states[k]);
}
let here = St::state(trace.states[k].clone());
let step =
(k > 0).then(|| St::action(trace.states[k - 1].clone(), trace.states[k].clone()));
match &step {
None => {
if self.private_init {
self.host.startup.store(false, Ordering::Relaxed);
let operation = if self.host.register_used.load(Ordering::Relaxed) {
self.host.startup.store(true, Ordering::Relaxed);
crate::initial::check(m, &trace.states[0], self.control.as_deref())
} else {
match crate::initial::random_check(m, &trace.states[0]) {
Ok(Some(member)) => Ok(Some(member)),
Ok(None) => crate::initial::check(
m,
&trace.states[0],
self.control.as_deref(),
),
Err(error) => Err(error),
}
};
let member = match operation {
Ok(Some(member)) => member,
Ok(None) => {
self.init_incomplete = !self
.host
.choices
.as_ref()
.is_some_and(|choices| choices.drew());
let error = EvalError::unsupported(crate::initial::UNSUPPORTED);
return Err(self.evaluation_refusal(&error, Some(0), Check::Init));
}
Err(error) => {
if error.class() == ErrorClass::Eval {
return Err(Stop::Unsupported(format!(
"independent Init source evaluation fails: {error}"
)));
}
return Err(self.evaluation_refusal(&error, Some(0), Check::Init));
}
};
if !member {
return Err(invalid(
0,
Check::Init,
"the first state is outside the independent Init relation",
));
}
self.passed += 1;
} else {
self.host.predicate_init.store(true, Ordering::Relaxed);
let initial = St::initial(trace.states[0].clone());
for init in &m.init {
self.require(&init.pred, &initial, 0, Check::Init, || {
format!(
"the initial predicate {} is false in the first state",
m.location(&init.pred)
)
})?;
}
}
self.host.startup.store(false, Ordering::Relaxed);
self.host.predicate_init.store(false, Ordering::Relaxed);
}
Some(step) => {
if !(named_lasso && trace.states[k - 1] == trace.states[k]) {
self.next(step, k, "the step into this state")?;
}
if let Some(label) = &trace.labels[k] {
self.label(&label.name, step, k)?;
}
}
}
if behavior {
continue;
}
let is_last = k == last;
let constrained_step = step
.as_ref()
.filter(|_| !(named_lasso && trace.states[k - 1] == trace.states[k]));
self.constraints(
&here,
constrained_step,
k,
is_last && terminal_before_exclusion,
)?;
match (&goal, is_last) {
(Goal::Invariant(i), true) => {
self.claimed(&m.invariants, *i, &here, k, Check::Invariant, "invariant")?;
}
(Goal::InvariantError(i, ec), true) => {
self.invariant_error(*i, ec, &here, k)?;
return Ok(None);
}
_ => {
for inv in &m.invariants {
self.require(&inv.pred, &here, k, Check::Invariant, || {
format!("invariant {} is false here, so the search would have stopped at this state", inv.name)
})?;
}
}
}
match (&goal, &step, is_last) {
(Goal::Invariant(_), _, true) => {}
(Goal::ImpliedInit(i), None, _) => {
self.claimed(
&m.implied_inits,
*i,
&here,
k,
Check::ImpliedInit,
"property",
)?;
}
(Goal::ImpliedAction(i), Some(step), true) => {
self.claimed(
&m.implied_actions,
*i,
step,
k,
Check::ImpliedAction,
"property",
)?;
}
(_, None, _) => {
for p in &m.implied_inits {
self.require(&p.pred, &here, k, Check::ImpliedInit, || {
format!("property {} is false in the first state", p.name)
})?;
}
}
(_, Some(step), _) => {
for p in &m.implied_actions {
self.require(&p.pred, step, k, Check::ImpliedAction, || {
format!("action property {} is false on this step, so the search would have stopped here", p.name)
})?;
}
}
}
}
if named_lasso {
self.periodic_end(trace)?;
return Ok(None);
}
if let Ending::Lasso { back_to } = trace.ending {
if m.view.is_some() {
self.notes.insert("VIEW: TLC's loop closes on the view, not the state; the loop step is not checked".to_owned());
} else {
let step = St::action(trace.states[last].clone(), trace.states[back_to].clone());
let what = format!(
"the loop from the last state back to state {} (numbered from 1)",
back_to + 1
);
self.next(&step, last, &what)?;
}
}
Ok(match goal {
Goal::Deadlock
if self.finite_scope == FiniteScope::SampledDeadlock
&& !(m.constraints.is_empty() && m.action_constraints.is_empty()) =>
{
return self.sampled_deadlock(&trace.states[last], last);
}
Goal::Deadlock => {
if let Some(next) = &m.next {
match crate::enabled::enabled(m, next, None, &trace.states[last]) {
Ok(false) => None,
Ok(true) => {
return Err(invalid(
last,
Check::Ending,
"the claimed deadlock has a successor",
));
}
Err(e) => {
if let crate::enabled::EnabledError::Interrupted(error) = e {
return Err(refused(&error).at(Some(last), Check::Ending));
}
self.notes.insert(e.to_string());
Some(DEADLOCK_UNSUPPORTED.to_owned())
}
}
} else {
Some(DEADLOCK_UNSUPPORTED.to_owned())
}
}
Goal::TemporalStateError
| Goal::Invariant(_)
| Goal::InvariantError(..)
| Goal::ImpliedInit(_)
| Goal::ImpliedAction(_)
| Goal::Behavior
| Goal::NextStateError => None,
Goal::Liveness(why) | Goal::ErrorEnd(why) => Some(why.to_owned()),
})
}
pub(crate) fn prepare_periodic(
&mut self,
ending: &Ending,
properties: &[String],
) -> Result<(), Stop> {
if !matches!(ending, Ending::Lasso { .. } | Ending::Stuttering) {
return Err(invalid(
0,
Check::Ending,
"temporal property names require a periodic ending",
));
}
if self.model.view.is_some()
|| self.model.symmetry_reduction.is_some()
|| (self.model.symmetry.is_some() && !self.model.unreduced_symmetry_liveness())
{
return Err(Stop::Unsupported(
"periodic validation under VIEW or SYMMETRY needs concrete closing-state evidence"
.into(),
));
}
let mut names = BTreeSet::new();
let mut declared = BTreeSet::new();
if self
.model
.property_claims()
.iter()
.any(|p| !declared.insert(&p.name))
{
return Err(Stop::Unsupported(
"split temporal properties with ambiguous repeated names".into(),
));
}
let mut previous = None;
for name in properties {
if name.is_empty() || !names.insert(name) {
return Err(invalid(
0,
Check::Ending,
"empty or repeated temporal property name",
));
}
let Some(index) = self
.model
.property_claims()
.iter()
.position(|p| p.name == *name)
else {
return Err(invalid(
0,
Check::Ending,
format!("the model has no temporal property named `{name}`"),
));
};
if previous.is_some_and(|prior| index <= prior) {
return Err(invalid(
0,
Check::Ending,
"temporal property names are not in configured order",
));
}
previous = Some(index);
}
let check = |pred: &Pred| {
crate::temporal::check_periodic_context(self.model, pred).map_err(|error| match error {
crate::temporal::TemporalError::Interrupted(error) => refused(&error),
other => Stop::Unsupported(other.to_string()),
})
};
for init in &self.model.init {
check(&init.pred)?;
}
if let Some(next) = &self.model.next {
check(next)?;
}
for p in self
.model
.constraints
.iter()
.chain(&self.model.action_constraints)
.chain(&self.model.invariants)
.chain(&self.model.implied_inits)
.chain(&self.model.implied_actions)
{
check(&p.pred)?;
}
for &d in &self.model.assumptions {
check(&Pred::new(
self.model.ir.def(d).body,
self.model.evaluator.scope(d).map_err(|error| {
if error.class() == ErrorClass::Interrupted {
refused(&error).at(None, Check::Assumption)
} else {
Stop::Unsupported(error.to_string())
}
})?,
))?;
}
Ok(())
}
fn periodic_end(&mut self, trace: &Trace) -> Result<(), Stop> {
let last = trace.states.len() - 1;
let back = match trace.ending {
Ending::Lasso { back_to } => back_to,
Ending::Stuttering => last,
_ => return Err(Stop::Unsupported("internal nonperiodic ending".into())),
};
let stutter = trace.states[last] == trace.states[back];
let step = St::action(trace.states[last].clone(), trace.states[back].clone());
if !stutter {
self.next(&step, last, "the closing step")?;
for c in &self.model.action_constraints {
self.require(&c.pred, &step, last, Check::ActionConstraint, || {
format!("ACTION_CONSTRAINT {} is false on the closing step", c.name)
})?;
}
}
for p in &self.model.implied_actions {
self.require(&p.pred, &step, last, Check::ImpliedAction, || {
format!("action property {} is false on the closing step", p.name)
})?;
}
for p in &self.model.temporals {
if !self.temporal_truth(&p.pred, trace, back)? {
return Err(invalid(
0,
Check::Fairness,
format!(
"behavior temporal conjunct {} is false on this word",
p.name
),
));
}
self.passed += 1;
}
for p in self.model.property_claims() {
let holds = self.temporal_truth(&p.pred, trace, back)?;
let claimed = trace.properties.contains(&p.name);
if claimed && holds {
return Err(invalid(
0,
Check::Temporal,
format!("temporal property {} holds on this word", p.name),
));
}
if !claimed && !holds {
return Err(invalid(
0,
Check::Temporal,
format!("violated temporal property {} was omitted", p.name),
));
}
self.passed += 1;
}
Ok(())
}
fn temporal_truth(&self, pred: &Pred, trace: &Trace, back: usize) -> Result<bool, Stop> {
use crate::temporal::TemporalError;
match crate::temporal::evaluate_lasso(self.model, pred, &trace.states, back) {
Ok(values) => values
.first()
.copied()
.ok_or_else(|| Stop::Unsupported("internal empty temporal truth vector".into())),
Err(TemporalError::Invalid(detail)) => Err(invalid(0, Check::Temporal, detail)),
Err(TemporalError::Unsupported(detail)) => Err(Stop::Unsupported(detail)),
Err(TemporalError::Interrupted(error)) => {
Err(refused(&error).at(None, Check::Temporal))
}
}
}
fn goal(&self, ending: &Ending, last: usize) -> Result<Goal, Stop> {
let m = self.model;
let find =
|list: &[dive_model::Named], name: &str| list.iter().position(|n| n.name == name);
Ok(match ending {
Ending::Invariant(name) => Goal::Invariant(find(&m.invariants, name).ok_or_else(|| {
invalid(last, Check::Ending, format!("the model has no invariant named `{name}`"))
})?),
Ending::InvariantError { name, ec } => Goal::InvariantError(
find(&m.invariants, name).ok_or_else(|| {
invalid(last, Check::Ending, format!("the model has no invariant named `{name}`"))
})?,
ec.clone(),
),
Ending::Property(name) if last == 0 => {
Goal::ImpliedInit(find(&m.implied_inits, name).ok_or_else(|| {
invalid(
last,
Check::Ending,
format!("the model has no implied initial predicate named `{name}`, and a one-state trace cannot violate an action property"),
)
})?)
}
Ending::Property(name) => Goal::ImpliedAction(find(&m.implied_actions, name).ok_or_else(|| {
invalid(last, Check::Ending, format!("the model has no action property named `{name}`"))
})?),
Ending::Deadlock => {
if !m.settings.check_deadlock {
return Err(invalid(
last,
Check::Ending,
"the model does not check for deadlock (CHECK_DEADLOCK FALSE or -deadlock)",
));
}
Goal::Deadlock
}
Ending::Behavior => Goal::Behavior,
Ending::TemporalStateError { .. } => Goal::TemporalStateError,
Ending::NextStateError { .. } | Ending::TemporalSourceError { .. }
| Ending::ViewSourceError { .. }
| Ending::CandidateStateError { .. } | Ending::PartialNext { .. } | Ending::PartialInit { .. } => Goal::NextStateError,
Ending::Lasso { back_to } => {
if *back_to > last {
return Err(invalid(last, Check::Shape, format!("the lasso loops back to state {back_to}, past the end")));
}
Goal::Liveness("liveness: the steps and the loop back (unless noted) were checked, but named temporal-property claims are missing")
}
Ending::Stuttering => Goal::Liveness("liveness: the steps were checked, but named temporal-property claims are missing"),
Ending::Assertion | Ending::Error { .. } => Goal::ErrorEnd("an error while expanding the last state: the steps were checked, but re-raising the error needs the successor generator, which the independent validator does not have"),
})
}
fn assumptions(&mut self) -> Result<(), Stop> {
let _assumptions = if self.control.is_some()
&& !self.endpoint_prepared
&& matches!(self.assumption_control, AssumptionControl::Unit)
{
Some(
self.model
.evaluator
.host_control(None)
.map_err(Stop::ControlConflict)?,
)
} else {
None
};
match self.model.check_assumptions() {
AssumptionOutcome::AllTrue => {
self.passed += 1;
Ok(())
}
AssumptionOutcome::False { message, .. } => Err(invalid(0, Check::Assumption, message)),
AssumptionOutcome::Error { error, message, .. } => match error.class() {
ErrorClass::Eval => Err(invalid(0, Check::Assumption, message)),
_ => Err(self.evaluation_refusal(&error, None, Check::Assumption)),
},
}
}
fn next(&mut self, step: &St, k: usize, what: &str) -> Result<(), Stop> {
let m = self.model;
let Some(next) = &m.next else {
return Err(invalid(
k,
Check::Next,
"the model has no next-state relation, so a trace has one state",
));
};
if let Some(choices) = &self.host.choices
&& m.ir
.node(next.expr)
.effects
.intersects(dive_ir::Effects::IMPURE.union(dive_ir::Effects::OPEN))
{
let (StateRef::Vals(source), StateRef::Vals(target)) = (&step.s0, &step.s1) else {
return Err(Stop::Unsupported(
"independent random Next needs complete source/target rows".into(),
));
};
self.host
.level
.store(i64::try_from(k).unwrap_or(i64::MAX), Ordering::Relaxed);
match crate::initial::next(m, source, target, choices) {
Ok(Some(true)) => {
self.passed += 1;
return Ok(());
}
Ok(Some(false)) => {
return Err(invalid(
k,
Check::Next,
"the step is outside the independent ordered Next relation",
));
}
Ok(None) => {}
Err(error) => return Err(self.evaluation_refusal(&error, Some(k), Check::Next)),
}
}
self.host.predicate_next.store(true, Ordering::Relaxed);
let result = self.require(next, step, k, Check::Next, || {
format!(
"{what} does not satisfy the next-state relation {}",
m.location(next)
)
});
self.host.predicate_next.store(false, Ordering::Relaxed);
result
}
fn label(&mut self, name: &str, step: &St, k: usize) -> Result<(), Stop> {
let m = self.model;
let ev = &m.evaluator;
let Some(d) = m.ir.root_def(name) else {
self.notes.insert(format!(
"label `{name}` names no definition of the root module; not checked"
));
return Ok(());
};
let d = ev.redirected(d);
if !m.ir.def(d).params.is_empty() || ev.is_value_override(d) {
self.notes.insert(format!(
"label `{name}` names an operator with parameters; not checked"
));
return Ok(());
}
let r = ev.eval_def(d, step);
match r {
Ok(Value::Bool(true)) => {
self.passed += 1;
Ok(())
}
Ok(Value::Bool(false)) => Err(invalid(
k,
Check::Label,
format!("the step is labelled `{name}`, but `{name}` is false on it"),
)),
Err(error)
if matches!(error.class(), ErrorClass::ResourceLimit | ErrorClass::Bug)
&& self.endpoint_prepared =>
{
Err(self.evaluation_refusal(&error, Some(k), Check::Label))
}
Err(error) if error.class() == ErrorClass::Interrupted => {
Err(refused(&error).at(Some(k), Check::Label))
}
_ => {
self.notes.insert(format!(
"label `{name}` could not be evaluated on its own; not checked"
));
Ok(())
}
}
}
fn claimed(
&mut self,
list: &[dive_model::Named],
i: usize,
st: &St,
k: usize,
check: Check,
what: &str,
) -> Result<(), Stop> {
for earlier in &list[..i] {
self.require(&earlier.pred, st, k, check, || {
format!("{what} {} is also false here and comes first in the configuration, so it would be reported instead of {}", earlier.name, list[i].name)
})?;
}
let p = &list[i];
if self.holds(&p.pred, st, k, check)? {
return Err(invalid(
k,
Check::Ending,
format!(
"{what} {} holds at the end of the trace, so the trace does not violate it",
p.name
),
));
}
self.passed += 1;
Ok(())
}
fn require(
&mut self,
pred: &Pred,
st: &St,
k: usize,
check: Check,
detail: impl FnOnce() -> String,
) -> Result<(), Stop> {
if self.holds(pred, st, k, check)? {
self.passed += 1;
Ok(())
} else {
Err(invalid(k, check, detail()))
}
}
fn invariant_error(&mut self, i: usize, ec: &str, st: &St, k: usize) -> Result<(), Stop> {
let m = self.model;
for earlier in &m.invariants[..i] {
self.require(&earlier.pred, st, k, Check::Invariant, || {
format!(
"invariant {} comes before {}, so it would decide first",
earlier.name, m.invariants[i].name
)
})?;
}
let named = &m.invariants[i];
self.host
.level
.store(i64::try_from(k + 1).unwrap_or(i64::MAX), Ordering::Relaxed);
let actual = match m.eval(&named.pred, st) {
Err(error) if error.class() == ErrorClass::Eval => error.ec(),
Err(error) => return Err(self.evaluation_refusal(&error, Some(k), Check::Invariant)),
Ok(value) if !matches!(value, Value::Bool(_)) => dive_eval::Ec::ExpectedValue,
Ok(_) => {
return Err(invalid(
k,
Check::Ending,
format!(
"invariant {} does not raise the claimed evaluation error",
named.name
),
));
}
};
if actual.name() != ec {
return Err(invalid(
k,
Check::Ending,
format!(
"invariant {} raises {}, not the claimed {ec}",
named.name,
actual.name()
),
));
}
self.passed += 1;
Ok(())
}
fn constraints(
&mut self,
here: &St,
step: Option<&St>,
state: usize,
allow_excluded: bool,
) -> Result<(), Stop> {
for constraint in &self.model.constraints {
if !self.holds(&constraint.pred, here, state, Check::Constraint)? {
return if allow_excluded {
Ok(())
} else {
Err(invalid(
state,
Check::Constraint,
format!(
"CONSTRAINT {} is false; only a checked terminal invariant or property may lie outside the model",
constraint.name,
),
))
};
}
}
if let Some(step) = step {
for constraint in &self.model.action_constraints {
if !self.holds(&constraint.pred, step, state, Check::ActionConstraint)? {
return if allow_excluded {
Ok(())
} else {
Err(invalid(
state,
Check::ActionConstraint,
format!(
"ACTION_CONSTRAINT {} is false; only a checked terminal invariant or property may lie outside the model",
constraint.name,
),
))
};
}
}
}
Ok(())
}
fn sampled_deadlock(
&mut self,
state: &crate::State,
last: usize,
) -> Result<Option<String>, Stop> {
let m = self.model;
if m.next.is_none() || m.actions.is_empty() {
return Ok(Some(DEADLOCK_UNSUPPORTED.to_owned()));
}
let source_level = last.saturating_add(1);
let mut ordinal = 0u64;
for action in &m.actions {
self.poll(Some(last), Some(Check::Ending))?;
let host = &self.host;
host.set_replay_level(source_level);
let mut found = None;
let mut sink = |candidate: &dive_eval::next::Successor<'_>| {
if !candidate.complete() {
found = Some(Found::Incomplete);
return dive_eval::next::Flow::Stop;
}
let successor: crate::State = candidate.state.iter().cloned().collect();
let here = St::state(successor.clone());
let step = St::action(state.clone(), successor);
let decision = in_model(m, host, &here, &step, source_level);
host.set_replay_level(source_level);
match decision {
Ok(false) => dive_eval::next::Flow::Continue,
Ok(true) => {
found = Some(Found::Inside);
dive_eval::next::Flow::Stop
}
Err(other) => {
found = Some(other);
dive_eval::next::Flow::Stop
}
}
};
let outcome = m.evaluator.next_states(action, state, ordinal, &mut sink);
match found {
None => {}
Some(Found::Inside) => {
return Err(invalid(
last,
Check::Ending,
"the claimed deadlock has a successor that satisfies every constraint",
));
}
Some(Found::Incomplete) => {
return Err(invalid(
last,
Check::Ending,
"the claimed deadlock has a successor that does not assign every variable",
));
}
Some(Found::NotBoolean(detail)) => {
return Err(invalid(last, Check::Ending, detail));
}
Some(Found::Error(e)) => {
return Err(match e.class() {
ErrorClass::Eval => invalid(
last,
Check::Ending,
format!(
"evaluating a constraint on a successor of the claimed deadlock fails: {}",
e.message()
),
),
_ => self.evaluation_refusal(&e, Some(last), Check::Ending),
});
}
}
match outcome {
Ok(o) => ordinal = ordinal.saturating_add(o.emitted),
Err(e) => {
return Err(match e.error.class() {
ErrorClass::Eval => invalid(
last,
Check::Ending,
format!(
"generating a successor of the claimed deadlock fails: {}",
e.error.message()
),
),
_ => self.evaluation_refusal(&e.error, Some(last), Check::Ending),
});
}
}
}
if m.has_runtime_names() {
return Ok(Some(crate::RUNTIME_NAMES_UNSUPPORTED.to_owned()));
}
self.notes.insert("Simulation deadlock: every successor of the last state lies outside the model's constraints, so TLC's simulator keeps none".to_owned());
Ok(None)
}
fn evaluation_refusal(
&mut self,
error: &EvalError,
state: Option<usize>,
check: Check,
) -> Stop {
if self.endpoint_prepared
&& matches!(error.class(), ErrorClass::ResourceLimit | ErrorClass::Bug)
{
self.endpoint_exception = Some((error.clone(), state, check));
}
refused(error).at(state, check)
}
fn holds(&mut self, pred: &Pred, st: &St, k: usize, check: Check) -> Result<bool, Stop> {
let m = self.model;
let level = if matches!(st.s1, StateRef::Vals(_)) {
k
} else {
k + 1
};
self.host
.level
.store(i64::try_from(level).unwrap_or(i64::MAX), Ordering::Relaxed);
match m.eval(pred, st) {
Ok(Value::Bool(b)) => Ok(b),
Ok(v) => Err(invalid(
k,
check,
format!(
"{} is not a boolean here: {}",
m.location(pred),
v.kind_name()
),
)),
Err(e) => match e.class() {
ErrorClass::Eval => Err(invalid(
k,
check,
format!("evaluating {} fails: {}", m.location(pred), e.message()),
)),
_ => Err(self.evaluation_refusal(&e, Some(k), check)),
},
}
}
}
enum Found {
Inside,
Incomplete,
NotBoolean(String),
Error(EvalError),
}
fn in_model(
m: &Model,
host: &TraceHost,
here: &St,
step: &St,
source_level: usize,
) -> Result<bool, Found> {
let truth = |pred: &Pred, st: &St| match m.eval(pred, st) {
Ok(Value::Bool(b)) => Ok(b),
Ok(v) => Err(Found::NotBoolean(format!(
"{} is not a boolean on a successor of the claimed deadlock: {}",
m.location(pred),
v.kind_name()
))),
Err(e) => Err(Found::Error(e)),
};
host.set_replay_level(source_level.saturating_add(1));
for constraint in &m.constraints {
if !truth(&constraint.pred, here)? {
return Ok(false);
}
}
host.set_replay_level(source_level);
for constraint in &m.action_constraints {
if !truth(&constraint.pred, step)? {
return Ok(false);
}
}
Ok(true)
}
fn invalid(state: usize, check: Check, detail: impl Into<String>) -> Stop {
Stop::Invalid(Failure {
state,
check,
detail: detail.into(),
})
}
fn refused(e: &EvalError) -> Stop {
if e.class() == ErrorClass::Interrupted {
return Stop::Interrupted {
error: e.clone(),
state: None,
check: None,
};
}
Stop::Unsupported(match e.class() {
ErrorClass::Unsupported => format!("the evaluator refuses: {}", e.message()),
ErrorClass::ResourceLimit => format!("resource limit: {}", e.message()),
_ => format!("internal evaluator error (a bug): {e}"),
})
}
impl Drop for Run<'_> {
fn drop(&mut self) {
let _ = self.model.evaluator.replace_host(self.inner.take());
}
}
#[derive(Debug)]
pub(crate) struct TraceHost {
inputs: Option<Arc<dive_eval::inputs::InputReplay>>,
level: AtomicI64,
inner: Option<Arc<dyn Host>>,
drew: Mutex<Option<StdOp>>,
any: AtomicBool,
pub(crate) registers: AtomicBool,
composition: AtomicBool,
pub(crate) register_used: AtomicBool,
pub(crate) startup: AtomicBool,
pub(crate) next_error: AtomicBool,
effect: Mutex<Option<String>>,
private: bool,
pub(crate) run_config: Mutex<Option<dive_eval::RunConfig>>,
cache_domain: u64,
pub(crate) choices: Option<Arc<crate::choices::Search>>,
predicate_init: AtomicBool,
predicate_next: AtomicBool,
}
pub(crate) fn next_cache_domain() -> u64 {
static NEXT: AtomicU64 = AtomicU64::new(1);
NEXT.fetch_add(1, Ordering::Relaxed)
}
impl TraceHost {
#[cfg(test)]
pub(crate) fn startup() -> Arc<Self> {
Self::startup_context(None, None)
}
pub(crate) fn set_replay_level(&self, level: usize) {
self.level
.store(i64::try_from(level).unwrap_or(i64::MAX), Ordering::Relaxed);
}
pub(crate) fn startup_context(
inputs: Option<Arc<dive_eval::inputs::InputReplay>>,
choices: Option<Arc<crate::choices::Search>>,
) -> Arc<Self> {
Arc::new(Self {
inputs,
level: AtomicI64::new(0),
inner: None,
drew: Mutex::new(None),
any: AtomicBool::new(false),
registers: AtomicBool::new(false),
composition: AtomicBool::new(false),
register_used: AtomicBool::new(false),
startup: AtomicBool::new(true),
next_error: AtomicBool::new(false),
effect: Mutex::new(None),
private: true,
run_config: Mutex::new(None),
cache_domain: next_cache_domain(),
choices,
predicate_init: AtomicBool::new(false),
predicate_next: AtomicBool::new(false),
})
}
pub(crate) fn finish_input_binding(&self, model: &Model) -> Result<(), String> {
if let Some(feature) = model.evaluator.external_input_refusal() {
return Err(feature);
}
self.inputs.as_ref().map_or(Ok(()), |inputs| {
inputs.finish_binding().map_err(|error| error.message)
})
}
fn private_host(&self) -> bool {
self.private
}
fn refuse_effect(&self, feature: String) -> Result<(), HostError> {
let mut effect = self.effect.lock().unwrap_or_else(PoisonError::into_inner);
if effect.is_none() {
*effect = Some(feature.clone());
}
Err(HostError {
code: 0,
message: feature,
})
}
}
impl Host for TraceHost {
fn input(
&self,
request: &dive_eval::inputs::InputRequest,
) -> Option<Result<dive_eval::inputs::InputResponse, HostError>> {
self.inputs.as_ref().map(|inputs| inputs.request(request))
}
fn check_random_in_enabled(&self) -> Result<(), HostError> {
self.refuse_effect(
"RandomElement/Randomization inside ENABLED is unsupported in independent replay"
.into(),
)
}
fn check_native_access(&self, op: StdOp) -> Result<(), HostError> {
if self.inputs.is_some() && matches!(op, StdOp::IoUtilsIOEnv | StdOp::IoUtilsDeserialize) {
return Ok(());
}
if op == StdOp::TlcRandomElement
&& let Some(choices) = &self.choices
{
if self.register_used.load(Ordering::Relaxed)
|| self.predicate_init.load(Ordering::Relaxed)
|| self.predicate_next.load(Ordering::Relaxed)
{
return Err(choices.refuse(
"random choice requires supported ordered Init/Next and a register-free replay prefix",
));
}
return Ok(());
}
if self.private_host()
&& matches!(
op,
StdOp::TlcRandomElement
| StdOp::RandomizationRandomSubset
| StdOp::RandomizationRandomSetOfSubsets
| StdOp::RandomizationRandomSubsetSet
)
{
if !self.any.swap(true, Ordering::Relaxed) {
*self.drew.lock().unwrap_or_else(PoisonError::into_inner) = Some(op);
}
return Err(HostError {
code: 0,
message: format!("{}: {RANDOM_UNSUPPORTED}", op.qualified_name()),
});
}
if self.private_host()
&& op.impure()
&& !matches!(
op,
StdOp::TlcTLCGet | StdOp::TlcTLCSet | StdOp::TlcPrint | StdOp::TlcPrintT
)
{
return self.refuse_effect(format!(
"{}: private trace startup does not support this host effect",
op.qualified_name()
));
}
Ok(())
}
fn print_output(&self, _text: &str) -> Result<bool, HostError> {
if self.next_error.load(Ordering::Relaxed) {
self.refuse_effect("Print/PrintT in Next error reconstruction".into())?;
}
Ok(false)
}
fn check_tlc_access(&self, key: &str, write: bool) -> Result<(), HostError> {
if self.private_host()
&& !(key.starts_with("s:")
|| !write && matches!(key, "config" | "level" | "all" | "all:named"))
{
return self.refuse_effect(format!(
"TLC{}({key:?}): private trace startup does not support this host effect",
if write { "Set" } else { "Get" }
));
}
Ok(())
}
fn check_register_access(&self) -> Result<(), HostError> {
if let Some(choices) = &self.choices
&& choices.drew()
{
self.registers.store(true, Ordering::Relaxed);
return Err(choices.refuse(REGISTERS_UNSUPPORTED));
}
self.register_used.store(true, Ordering::Relaxed);
if self.startup.load(Ordering::Relaxed) {
return Ok(());
}
self.registers.store(true, Ordering::Relaxed);
Err(HostError {
code: 0,
message: REGISTERS_UNSUPPORTED.to_owned(),
})
}
fn check_action_composition(&self) -> Result<(), HostError> {
self.composition.store(true, Ordering::Relaxed);
Err(HostError {
code: 0,
message: COMPOSITION_UNSUPPORTED.to_owned(),
})
}
fn requires_bounded_action_composition(&self) -> bool {
true
}
fn check_bounded_action_composition(&self) -> Result<(), HostError> {
let result = self
.inner
.as_ref()
.map_or(Ok(()), |host| host.check_bounded_action_composition());
if result.is_err() {
self.composition.store(true, Ordering::Relaxed);
}
result
}
fn expression_cache_domain(&self) -> u64 {
self.cache_domain
}
fn random(&self, op: StdOp, args: &[Value], ctx: Ctx) -> Option<Result<Value, HostError>> {
if let Some(choices) = &self.choices {
return Some(choices.random(op, args, ctx));
}
if !self.any.swap(true, Ordering::Relaxed) {
*self.drew.lock().unwrap_or_else(PoisonError::into_inner) = Some(op);
}
None
}
fn level(&self) -> Option<i64> {
Some(self.level.load(Ordering::Relaxed))
}
fn successor_level(&self) -> Result<i64, HostError> {
self.refuse_effect(dive_eval::PRIMED_LEVEL_UNSUPPORTED.to_owned())
.map(|()| 0)
}
fn config(&self) -> Option<dive_eval::RunConfig> {
self.run_config
.lock()
.unwrap_or_else(PoisonError::into_inner)
.clone()
.or_else(|| self.inner.as_ref().and_then(|h| h.config()))
}
}
#[must_use]
pub fn validate(model: &Model, trace: &Trace) -> Report {
let admitted = model.validate_context().and_then(|()| {
for &def in &model.assumptions {
model.evaluator.scope(def)?;
}
Ok(())
});
if let Err(error) = admitted {
return Report {
validation: Validation::Unsupported(error.to_string()),
notes: Vec::new(),
length: trace.logical_length(),
};
}
let mut run = Run::new(model);
let validation = run.validate(trace);
Report {
validation,
notes: std::mem::take(&mut run.notes).into_iter().collect(),
length: trace.logical_length(),
}
}
pub fn validate_controlled(
model: &Model,
trace: &Trace,
control: Arc<dyn dive_eval::HostControl>,
) -> Result<Report, ValidationRunError> {
let _scope = model
.evaluator
.host_control(Some(control.clone()))
.map_err(ValidationRunError::ControlConflict)?;
let admitted = model.validate_context().and_then(|()| {
for &def in &model.assumptions {
model.evaluator.scope(def)?;
}
Ok(())
});
if let Err(error) = admitted {
if error.class() == ErrorClass::Interrupted {
return Err(ValidationRunError::Interrupted {
error,
progress: ValidationProgress {
checks_passed: 0,
state: None,
check: None,
},
});
}
return Ok(Report {
validation: Validation::Unsupported(error.to_string()),
notes: Vec::new(),
length: trace.logical_length(),
});
}
let mut run = Run::new(model);
run.control = Some(control);
controlled_report(&mut run, trace)
}
#[allow(
clippy::too_many_lines,
reason = "finite validation and independent endpoint phases share one fallible report boundary"
)]
fn controlled_report(run: &mut Run<'_>, trace: &Trace) -> Result<Report, ValidationRunError> {
let endpoint = if matches!(trace.ending, Ending::TemporalStateError { .. }) {
if !run.host.private {
return Ok(Report {
validation: Validation::Unsupported(
"temporal error endpoint requires a privately reconstructed source session"
.into(),
),
notes: Vec::new(),
length: trace.logical_length(),
});
}
if !trace.properties.is_empty() {
return Ok(Report {
validation: Validation::Invalid(Failure {
state: 0,
check: Check::Shape,
detail: "finite error endpoints cannot claim temporal properties".into(),
}),
notes: Vec::new(),
length: trace.logical_length(),
});
}
match crate::row_demand::prepare(run.model, &trace.states, run.control.as_deref()) {
Ok(program) => {
run.endpoint_prepared = true;
Some(program)
}
Err(error) => return endpoint_refusal(run, trace, error, None),
}
} else {
None
};
let result = run.validate_result(trace);
let mut validation = controlled_result(run, result)?;
if validation == Validation::Valid
&& let Some(program) = endpoint
{
let Some(last) = trace.states.len().checked_sub(1) else {
return Ok(Report {
validation: Validation::Invalid(Failure {
state: 0,
check: Check::Shape,
detail: "endpoint has no state".into(),
}),
notes: Vec::new(),
length: 0,
});
};
let Ending::TemporalStateError { ec, endpoint } = &trace.ending else {
return Ok(Report {
validation: Validation::Unsupported("missing endpoint ending".into()),
notes: Vec::new(),
length: trace.logical_length(),
});
};
match program.replay(
run.model,
&trace.states[last],
ec,
endpoint,
run.control.as_deref(),
) {
Ok(Ok(())) => {}
Ok(Err(detail)) => {
validation = Validation::Invalid(Failure {
state: last,
check: Check::Ending,
detail,
});
}
Err(error) => return endpoint_refusal(run, trace, error, Some(last)),
}
if let Some(control) = &run.control {
control
.check()
.map_err(|error| ValidationRunError::Interrupted {
error: EvalError::interrupted(error),
progress: progress(run, Some(last)),
})?;
}
}
if let Some(feature) = run.refusal() {
validation = Validation::Unsupported(feature);
}
Ok(Report {
validation,
notes: std::mem::take(&mut run.notes).into_iter().collect(),
length: trace.logical_length(),
})
}
fn controlled_result(
run: &mut Run<'_>,
result: Result<Validation, Stop>,
) -> Result<Validation, ValidationRunError> {
if let Some((error, state, check)) = run.endpoint_exception.take() {
let progress = ValidationProgress {
checks_passed: run.passed,
state,
check: Some(check),
};
return Err(if error.class() == ErrorClass::ResourceLimit {
ValidationRunError::ResourceLimit { error, progress }
} else {
ValidationRunError::EvaluationFailure { error, progress }
});
}
let validation = match result {
Ok(validation) => validation,
Err(Stop::Interrupted {
error,
state,
check,
}) => {
return Err(ValidationRunError::Interrupted {
error,
progress: ValidationProgress {
checks_passed: run.passed,
state,
check,
},
});
}
Err(Stop::ControlConflict(error)) => {
return Err(ValidationRunError::ControlConflict(error));
}
Err(other) => other.into(),
};
Ok(validation)
}
fn progress(run: &Run<'_>, state: Option<usize>) -> ValidationProgress {
ValidationProgress {
checks_passed: run.passed,
state,
check: Some(Check::Ending),
}
}
fn endpoint_refusal(
run: &Run<'_>,
trace: &Trace,
error: crate::row_demand::FormulaError,
state: Option<usize>,
) -> Result<Report, ValidationRunError> {
let feature = match error {
crate::row_demand::FormulaError::Evaluation(error) => match error.class() {
ErrorClass::Interrupted => {
return Err(ValidationRunError::Interrupted {
error,
progress: progress(run, state),
});
}
ErrorClass::ResourceLimit => {
return Err(ValidationRunError::ResourceLimit {
error,
progress: progress(run, state),
});
}
ErrorClass::Bug => {
return Err(ValidationRunError::EvaluationFailure {
error,
progress: progress(run, state),
});
}
_ => error.to_string(),
},
other => other.to_string(),
};
Ok(Report {
validation: Validation::Unsupported(feature),
notes: Vec::new(),
length: trace.logical_length(),
})
}
pub(crate) fn validate_private_controlled(
model: &Model,
host: Arc<TraceHost>,
trace: &Trace,
control: Option<Arc<dyn dive_eval::HostControl>>,
) -> Result<Report, ValidationRunError> {
let _scope = control
.as_ref()
.map(|control| model.evaluator.host_control(Some(control.clone())))
.transpose()
.map_err(ValidationRunError::ControlConflict)?;
let mut run = Run::private(model, host, false);
run.control = control;
controlled_report(&mut run, trace)
}
pub(crate) fn validate_finite_private_controlled(
model: &Model,
host: &Arc<TraceHost>,
trace: &Trace,
initial: bool,
control: Option<Arc<dyn dive_eval::HostControl>>,
scope: FiniteScope,
) -> Result<(Report, bool), ValidationRunError> {
let _scope = control
.as_ref()
.map(|control| model.evaluator.host_control(Some(control.clone())))
.transpose()
.map_err(ValidationRunError::ControlConflict)?;
let mut run = Run::private(model, host.clone(), initial);
run.control = control;
run.assumption_control = AssumptionControl::Cooperative;
run.finite_scope = scope;
let report = controlled_report(&mut run, trace)?;
let retry = initial && run.init_incomplete && !host.register_used.load(Ordering::Relaxed);
Ok((report, retry))
}
pub(crate) fn validate_next_prefix_controlled(
model: &Model,
host: Arc<TraceHost>,
trace: &Trace,
control: Option<Arc<dyn dive_eval::HostControl>>,
) -> Result<(Report, u64), ValidationRunError> {
let _scope = control
.as_ref()
.map(|control| model.evaluator.host_control(Some(control.clone())))
.transpose()
.map_err(ValidationRunError::ControlConflict)?;
let mut run = Run::private(model, host, false);
run.control = control;
run.endpoint_prepared = true;
let mut report = controlled_report(&mut run, trace)?;
if report.validation == Validation::Valid
&& matches!(trace.ending, Ending::CandidateStateError { .. })
{
let last = trace.states.len() - 1;
if let Some(label) = &trace.labels[last] {
run.host.set_replay_level(last);
let step = St::action(trace.states[last - 1].clone(), trace.states[last].clone());
let result = run
.label(&label.name, &step, last)
.map(|()| Validation::Valid);
report.validation = controlled_result(&mut run, result)?;
report.notes.extend(std::mem::take(&mut run.notes));
}
report.length = trace.logical_length();
}
Ok((report, run.passed))
}
#[allow(
clippy::too_many_lines,
reason = "one typed control boundary dispatches independently replayed terminal sites"
)]
pub(crate) fn replay_next_controlled(
model: &Model,
host: Arc<TraceHost>,
trace: &Trace,
state: &crate::State,
checks_passed: u64,
control: Option<Arc<dyn dive_eval::HostControl>>,
) -> Result<Report, ValidationRunError> {
let _scope = control
.as_ref()
.map(|control| model.evaluator.host_control(Some(control.clone())))
.transpose()
.map_err(ValidationRunError::ControlConflict)?;
let mut run = Run::private(model, host, false);
run.control = control;
run.passed = checks_passed;
let Some(last) = trace.states.len().checked_sub(1) else {
return Ok(Report {
validation: Validation::Invalid(Failure {
state: 0,
check: Check::Shape,
detail: "Next endpoint has no state".into(),
}),
notes: Vec::new(),
length: 0,
});
};
run.poll(Some(last), Some(Check::Ending))
.map_err(|stop| match stop {
Stop::Interrupted { error, .. } => ValidationRunError::Interrupted {
error,
progress: progress(&run, Some(last)),
},
_ => ValidationRunError::EvaluationFailure {
error: EvalError::bug("unexpected terminal replay poll outcome"),
progress: progress(&run, Some(last)),
},
})?;
run.host.level.store(
i64::try_from(last.saturating_add(1)).unwrap_or(i64::MAX),
Ordering::Relaxed,
);
let replay = match &trace.ending {
Ending::ViewSourceError { ec, endpoint } => crate::ordered_prefix::view(
model,
trace,
ec,
endpoint,
&run.host,
run.control.as_deref(),
),
Ending::CandidateStateError { ec, endpoint } => {
let Some(source) = last
.checked_sub(1)
.and_then(|index| trace.states.get(index))
else {
return Ok(Report {
validation: Validation::Invalid(Failure {
state: last,
check: Check::Shape,
detail: "candidate error has no predecessor".into(),
}),
notes: Vec::new(),
length: trace.logical_length(),
});
};
crate::candidate_error::replay(
model,
source,
state,
last,
ec,
endpoint,
&run.host,
run.control.as_deref(),
)
}
Ending::TemporalSourceError { ec, endpoint } => crate::source_row::replay(
model,
state,
last,
ec,
endpoint,
&run.host,
run.control.as_deref(),
),
Ending::NextStateError { ec, endpoint } => crate::next_error::replay(
model,
state,
last,
ec,
endpoint,
&run.host,
run.control.as_deref(),
),
_ => Ok(Validation::Unsupported(
"missing source terminal endpoint".into(),
)),
};
let mut validation = replay.map_err(|error| match error.class() {
ErrorClass::Interrupted => ValidationRunError::Interrupted {
error,
progress: progress(&run, Some(last)),
},
ErrorClass::ResourceLimit => ValidationRunError::ResourceLimit {
error,
progress: progress(&run, Some(last)),
},
_ => ValidationRunError::EvaluationFailure {
error,
progress: progress(&run, Some(last)),
},
})?;
if let Some(feature) = run.refusal() {
validation = Validation::Unsupported(feature);
}
Ok(Report {
validation,
notes: Vec::new(),
length: trace.logical_length(),
})
}
pub(crate) fn replay_partial_controlled(
model: &Model,
host: Arc<TraceHost>,
trace: &Trace,
endpoint: &crate::PartialNextEndpoint,
checks_passed: u64,
control: Option<Arc<dyn dive_eval::HostControl>>,
) -> Result<Report, ValidationRunError> {
let _scope = control
.as_ref()
.map(|control| model.evaluator.host_control(Some(control.clone())))
.transpose()
.map_err(ValidationRunError::ControlConflict)?;
let mut run = Run::private(model, host, false);
run.control = control;
run.passed = checks_passed;
let Some(last) = trace.states.len().checked_sub(1) else {
return Ok(Report {
validation: Validation::Invalid(Failure {
state: 0,
check: Check::Shape,
detail: "Next endpoint has no state".into(),
}),
notes: Vec::new(),
length: 0,
});
};
run.poll(Some(last), Some(Check::Ending))
.map_err(|stop| match stop {
Stop::Interrupted { error, .. } => ValidationRunError::Interrupted {
error,
progress: progress(&run, Some(last)),
},
_ => ValidationRunError::EvaluationFailure {
error: EvalError::bug("unexpected terminal replay poll outcome"),
progress: progress(&run, Some(last)),
},
})?;
run.host.level.store(
i64::try_from(last.saturating_add(1)).unwrap_or(i64::MAX),
Ordering::Relaxed,
);
let mut validation = crate::partial::replay(
model,
&trace.states[last],
trace.states.len(),
endpoint,
&run.host,
run.control.as_deref(),
)
.map_err(|error| match error.class() {
ErrorClass::Interrupted => ValidationRunError::Interrupted {
error,
progress: progress(&run, Some(last)),
},
ErrorClass::ResourceLimit => ValidationRunError::ResourceLimit {
error,
progress: progress(&run, Some(last)),
},
_ => ValidationRunError::EvaluationFailure {
error,
progress: progress(&run, Some(last)),
},
})?;
if let Some(feature) = run.refusal() {
validation = Validation::Unsupported(feature);
}
Ok(Report {
validation,
notes: Vec::new(),
length: trace.states.len().saturating_add(1),
})
}
pub(crate) fn replay_initial_partial_controlled(
model: &Model,
host: Arc<TraceHost>,
endpoint: &crate::PartialStateEndpoint,
control: Option<Arc<dyn dive_eval::HostControl>>,
) -> Result<Report, ValidationRunError> {
let _scope = control
.as_ref()
.map(|c| model.evaluator.host_control(Some(c.clone())))
.transpose()
.map_err(ValidationRunError::ControlConflict)?;
let mut run = Run::private(model, host, false);
run.control = control;
run.endpoint_prepared = true;
run.host.set_replay_level(0);
run.poll(None, Some(Check::Assumption))
.map_err(|stop| match stop {
Stop::Interrupted { error, .. } => ValidationRunError::Interrupted {
error,
progress: progress(&run, None),
},
_ => ValidationRunError::EvaluationFailure {
error: EvalError::bug("unexpected Init partial control failure"),
progress: progress(&run, None),
},
})?;
let result = run.assumptions().map(|()| Validation::Valid);
let mut validation = controlled_result(&mut run, result)?;
if validation == Validation::Valid {
let empty = Arc::from([]);
validation = crate::partial::replay(
model,
&empty,
0,
endpoint,
&run.host,
run.control.as_deref(),
)
.map_err(|error| match error.class() {
ErrorClass::Interrupted => ValidationRunError::Interrupted {
error,
progress: progress(&run, None),
},
ErrorClass::ResourceLimit => ValidationRunError::ResourceLimit {
error,
progress: progress(&run, None),
},
_ => ValidationRunError::EvaluationFailure {
error,
progress: progress(&run, None),
},
})?;
}
if let Some(feature) = run.refusal() {
validation = Validation::Unsupported(feature);
}
if let Some(control) = &run.control {
control
.check()
.map_err(|error| ValidationRunError::Interrupted {
error: EvalError::interrupted(error),
progress: progress(&run, None),
})?;
}
Ok(Report {
validation,
notes: Vec::new(),
length: 1,
})
}
pub(crate) fn guard_runtime_names(model: &Model, mut report: Report) -> Report {
if model.has_runtime_names() {
report.validation = Validation::Unsupported(RUNTIME_NAMES_UNSUPPORTED.to_owned());
}
report
}
#[cfg(test)]
mod negative_controls {
#![allow(clippy::expect_used, clippy::panic, reason = "test assertions")]
use std::sync::Arc;
use super::{
Check, ErrorClass, Run, TraceHost, Validation, ValidationRunError, endpoint_refusal,
validate,
};
use crate::{Ending, Trace, TraceDoc};
const SPEC: &str = "---- MODULE Count ----\nEXTENDS Naturals\nVARIABLE x\n\
Init == x = 0\nNext == x' = x + 1\nSmall == x < 3\nTiny == x < 5\n====\n";
fn model() -> dive_model::Model {
let analysis = dive_sema::analyze_source("Count.tla", SPEC, &dive_sema::Options::default());
let ir = Arc::new(dive_ir::lower(&analysis).expect("lower"));
let cfg = dive_config::parse("INIT Init\nNEXT Next\nINVARIANT Tiny Small\n")
.into_config()
.expect("cfg");
dive_model::bind(ir, &cfg, &dive_model::BindOptions::tlc()).expect("bind")
}
fn trace(model: &dive_model::Model, xs: &[i64]) -> Trace {
let states = xs.iter().map(|x| serde_json::json!({ "x": x })).collect();
let doc = TraceDoc::behavior(states)
.expect("states")
.with_ending(Ending::Invariant("Small".to_owned()));
Trace::decode(model, &doc).expect("decode")
}
fn rejected(model: &dive_model::Model, t: &Trace) -> Check {
match validate(model, t).validation {
Validation::Invalid(f) => f.check,
other => panic!("{other:?}"),
}
}
#[test]
fn endpoint_allocation_failure_has_no_completed_validation_report() {
let model = model();
let trace = trace(&model, &[0, 1]);
let host = TraceHost::startup();
let run = Run::private(&model, host, false);
let error = crate::row_demand::reserve(&mut Vec::<u64>::new(), usize::MAX)
.expect_err("actual allocation capacity overflow");
let error =
endpoint_refusal(&run, &trace, error, Some(1)).expect_err("no report on exhaustion");
assert!(
matches!(error,ValidationRunError::ResourceLimit{error,progress} if error.class()==ErrorClass::ResourceLimit&&progress.state==Some(1)&&progress.check==Some(Check::Ending))
);
}
#[test]
fn edits_of_a_valid_counterexample_are_rejected() {
let m = model();
let original = trace(&m, &[0, 1, 2, 3]);
assert_eq!(validate(&m, &original).validation, Validation::Valid);
assert_eq!(rejected(&m, &trace(&m, &[0, 1, 3])), Check::Next);
assert_eq!(rejected(&m, &trace(&m, &[1, 2, 3])), Check::Init);
assert_eq!(rejected(&m, &trace(&m, &[0, 2, 1, 3])), Check::Next);
assert_eq!(rejected(&m, &trace(&m, &[0, 1, 7, 3])), Check::Next);
assert_eq!(rejected(&m, &trace(&m, &[0, 1, 2])), Check::Ending);
let mut claim = original.clone();
claim.ending = Ending::Invariant("Tiny".to_owned());
assert_eq!(rejected(&m, &claim), Check::Ending);
claim.ending = Ending::Invariant("Missing".to_owned());
assert_eq!(rejected(&m, &claim), Check::Ending);
}
}