Skip to main content

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}