dive_trace/mutate.rs
1//! Negative controls: mutants of a valid counterexample that are invalid by
2//! construction.
3//!
4//! The caller selects [`ControlMode`] explicitly. Dropping and swapping
5//! states require a valid shortest breadth-first counterexample:
6//! state `k` is at distance exactly `k` from the initial states, and no two
7//! states are equal. Simulation, multi-worker and liveness words have no
8//! such guarantee; [`ControlMode::Counterexample`] omits these controls.
9//! The remaining controls use the valid counterexample's first-violation,
10//! constrained-variable and label obligations, without a distance premise.
11//!
12//! | Mutant | Why it is invalid |
13//! |---|---|
14//! | `drop-state-k`: remove a middle state | if `s(k-1) -> s(k+1)` were a step, `s(k+1)` would be at distance `k`, not `k+1` |
15//! | `drop-first`: remove the initial state | if `s1` were initial, it would be at distance 0 |
16//! | `swap-k`: exchange states `k` and `k+1` | the step into the earlier position would put `s(k+1)` at distance `k` (or make it initial) |
17//! | `change-k-var`: one variable of a middle state becomes a model value with a reserved Boolean keyword | the step into the state would have to set the variable to a value no expression of the specification can produce |
18//! | `truncate`: remove the last state, keep the claim (invariant, named invariant-error and property endings) | the claimed invariant or property held, or did not raise the claimed error, at the new last state, or the search would have stopped there |
19//! | `claim-Q`: claim a different invariant or property `Q` | `Q` either holds at the end, or is listed after the violated one, which is then false first |
20//! | `claim-error`: change a named invariant error's cause | the exact cause differs from the known valid claim |
21//! | `relabel-k`: label step `k` with another action of the trace that is false on it | the label must hold on the step |
22//!
23//! Labels on the steps a mutation touches are removed, so a mutant is
24//! rejected for its states, not its labels. The `change` mutants assume
25//! every variable is constrained by the next-state relation, as TLC's
26//! successor generator requires. The changed value is a model value named `TRUE`: the reserved
27//! Boolean keyword cannot denote a model value in a specification or
28//! configuration. Its atom already belongs to the startup name table, so
29//! generating a control never interns a runtime name.
30
31use dive_model::Model;
32use dive_value::Value;
33
34use crate::format::Ending;
35use crate::trace::Trace;
36
37/// The model value the `change` mutants use. The reserved Boolean keyword
38/// cannot denote a model value in a specification or configuration, and its
39/// name is already interned at startup.
40pub const MUTANT_MODEL_VALUE: &str = "TRUE";
41
42/// Which invalid-by-construction controls the caller's counterexample supports.
43///
44/// This choice declares the producer's contract; validation does not infer
45/// shortestness from a supplied word or search for a shorter path.
46#[derive(Clone, Copy, Debug, PartialEq, Eq)]
47pub enum ControlMode {
48 /// A known shortest breadth-first counterexample. Includes dropping and
49 /// swapping states, whose invalidity relies on shortest distances.
50 ShortestBfs,
51 /// A known valid counterexample without a shortest-path guarantee.
52 /// Includes changed values, truncated claims, changed claims and false
53 /// action labels, subject to their existing construction preconditions.
54 Counterexample,
55}
56
57/// A mutant: what was done, and the trace.
58#[derive(Clone, Debug)]
59pub struct Mutant {
60 /// What was done, e.g. `swap-3`.
61 pub name: String,
62 /// The mutated trace.
63 pub trace: Trace,
64}
65
66/// The by-construction mutants of a known valid shortest BFS `trace`.
67///
68/// Compatibility wrapper for [`mutants_with_mode`] with
69/// [`ControlMode::ShortestBfs`]. Use the explicit mode for other producers.
70#[must_use]
71pub fn mutants(model: &Model, trace: &Trace) -> Vec<Mutant> {
72 mutants_with_mode(model, trace, ControlMode::ShortestBfs)
73}
74
75/// The by-construction mutants supported by a known valid counterexample's
76/// producer contract (see the module documentation).
77#[must_use]
78#[allow(
79 clippy::too_many_lines,
80 reason = "the table in the module documentation, one block per row"
81)]
82pub fn mutants_with_mode(model: &Model, trace: &Trace, mode: ControlMode) -> Vec<Mutant> {
83 let n = trace.states.len();
84 let mut out = Vec::new();
85 let base = Trace {
86 length: None,
87 ..trace.clone()
88 };
89 let mut push = |name: String, t: Trace| out.push(Mutant { name, trace: t });
90 if mode == ControlMode::ShortestBfs && n >= 3 {
91 let k = n / 2;
92 let mut t = base.clone();
93 t.states.remove(k);
94 t.labels.remove(k);
95 t.labels[k] = None;
96 push(format!("drop-state-{k}"), t);
97 }
98 if mode == ControlMode::ShortestBfs && n >= 2 {
99 let mut t = base.clone();
100 t.states.remove(0);
101 t.labels.remove(0);
102 t.labels[0] = None;
103 push("drop-first".to_owned(), t);
104 }
105 if mode == ControlMode::ShortestBfs && n >= 2 {
106 let k = if n >= 3 { (n - 1) / 2 } else { 0 };
107 if trace.states[k] != trace.states[k + 1] {
108 let mut t = base.clone();
109 t.states.swap(k, k + 1);
110 for j in k..(k + 3).min(n) {
111 t.labels[j] = None;
112 }
113 push(format!("swap-{k}"), t);
114 }
115 }
116 if n != 0
117 && let Some(atom) = model.names.get(MUTANT_MODEL_VALUE)
118 && (atom.tok() as usize) < model.evaluator.startup_names()
119 {
120 let k = if n >= 3 { n / 2 } else { 0 };
121 let vars = crate::trace::variables(model);
122 let fresh = Value::Model(atom);
123 for (i, name) in vars.iter().enumerate() {
124 let mut t = base.clone();
125 let mut s: Vec<Option<Value>> = t.states[k].to_vec();
126 s[i] = Some(fresh.clone());
127 t.states[k] = s.into();
128 t.labels[k] = None;
129 if k + 1 < n {
130 t.labels[k + 1] = None;
131 }
132 push(format!("change-{k}-{name}"), t);
133 }
134 }
135 // Violations and named invariant errors must first arise at the original
136 // end. Generic expansion-error and liveness endings retain their existing
137 // validation boundary.
138 if n >= 2
139 && matches!(
140 trace.ending,
141 Ending::Invariant(_) | Ending::Property(_) | Ending::InvariantError { .. }
142 )
143 {
144 let mut t = base.clone();
145 t.states.pop();
146 t.labels.pop();
147 push("truncate".to_owned(), t);
148 }
149 let names =
150 |list: &[dive_model::Named]| list.iter().map(|x| x.name.clone()).collect::<Vec<_>>();
151 let claims: Vec<Ending> = match &trace.ending {
152 Ending::InvariantError { name, ec } => names(&model.invariants)
153 .into_iter()
154 .filter(|other| other != name)
155 .chain(std::iter::once(format!("{name}_dive_trace_mutant")))
156 .map(|name| Ending::InvariantError {
157 name,
158 ec: ec.clone(),
159 })
160 .chain(std::iter::once(Ending::InvariantError {
161 name: name.clone(),
162 ec: if ec == "TLC_MODULE_DIVISION_BY_ZERO" {
163 "TLC_VALUE_ASSERT_FAILED"
164 } else {
165 "TLC_MODULE_DIVISION_BY_ZERO"
166 }
167 .to_owned(),
168 }))
169 .collect(),
170 Ending::Invariant(p) => names(&model.invariants)
171 .into_iter()
172 .filter(|q| q != p)
173 .map(Ending::Invariant)
174 .chain(std::iter::once(Ending::Invariant(format!(
175 "{p}_dive_trace_mutant"
176 ))))
177 .collect(),
178 Ending::Property(p) => {
179 let list = if n == 1 {
180 &model.implied_inits
181 } else {
182 &model.implied_actions
183 };
184 names(list)
185 .into_iter()
186 .filter(|q| q != p)
187 .map(Ending::Property)
188 .chain(std::iter::once(Ending::Property(format!(
189 "{p}_dive_trace_mutant"
190 ))))
191 .collect()
192 }
193 _ => names(&model.invariants)
194 .into_iter()
195 .take(1)
196 .map(Ending::Invariant)
197 .collect(),
198 };
199 for c in claims {
200 let label = match &c {
201 Ending::Invariant(q) | Ending::Property(q) => q.clone(),
202 other => format!("{other:?}"),
203 };
204 push(
205 format!("claim-{label}"),
206 Trace {
207 ending: c,
208 ..base.clone()
209 },
210 );
211 }
212 if let Some(t) = relabel(model, &base) {
213 out.push(t);
214 }
215 out
216}
217
218/// Labels the first step it can with another of the trace's action names
219/// that is false on that step.
220fn relabel(model: &Model, trace: &Trace) -> Option<Mutant> {
221 let ev = &model.evaluator;
222 let mut names: Vec<&str> = trace
223 .labels
224 .iter()
225 .flatten()
226 .map(|l| l.name.as_str())
227 .collect();
228 names.sort_unstable();
229 names.dedup();
230 let checkable = |name: &str| {
231 model
232 .ir
233 .root_def(name)
234 .map(|d| ev.redirected(d))
235 .filter(|&d| {
236 model.ir.def(d).params.is_empty()
237 && !ev.is_value_override(d)
238 && !model.ir.def(d).effects.intersects(dive_ir::Effects::IMPURE)
239 })
240 };
241 for k in 1..trace.states.len() {
242 let Some(current) = &trace.labels[k] else {
243 continue;
244 };
245 for other in &names {
246 if *other == current.name {
247 continue;
248 }
249 if checkable(other).is_some() {
250 let mut t = trace.clone();
251 t.labels[k] = Some(crate::format::Label {
252 name: (*other).to_owned(),
253 location: None,
254 });
255 // Skip impure alternatives above, then use guarded validation
256 // rather than evaluating a label in the caller's runtime.
257 if matches!(crate::validate(model, &t).validation,
258 crate::Validation::Invalid(ref failure)
259 if failure.state == k && failure.check == crate::Check::Label)
260 {
261 return Some(Mutant {
262 name: format!("relabel-{k}-{other}"),
263 trace: t,
264 });
265 }
266 }
267 }
268 }
269 None
270}