DDMin—The Original Delta Debugging
DDMin is the original delta debugging algorithm, and the one that started it all.
The Model
The goal of delta debugging is to minimize a failing test case. Specifically, we want a smaller version of the input that still triggers the bug. “Smaller” means fewer elements, i.e., fewer of some atomic unit: characters, tokens, lines, etc.
Atomic Unit
Atomic Unit is the smallest piece of the input that can be removed. Different inputs have different atomic units—characters for one input, tokens or lines for another—so the framework fixes no concrete type; it only asks that a unit be cheap to copy, compare, and hash:
/// An indivisible piece of the input: a char, token, line, etc.
trait AtomicUnit: Copy + Eq + std::hash::Hash + Ord {}
impl<T: Copy + Eq + std::hash::Hash + Ord> AtomicUnit
for T
{
}The demo at the end of this chapter minimizes a set of plain numbers, so
its atomic unit is simply u32.
Configuration
A Configuration is a subset of the atomic units in the input: the units you keep in the current iteration of the minimization. The full input keeps everything, and reduction shrinks the configuration while preserving the property (e.g., still triggering the bug).
/// The units we keep.
type Configuration<U> = HashSet<U>;Oracle
The property we want to preserve is checked by an Oracle. Given a configuration, the oracle returns a Verdict, i.e., whether it still preserves the property.
#[derive(PartialEq)]
enum Verdict {
Interesting, // still triggers the bug
NotInteresting, // does not trigger the bug or is invalid
}
type Oracle<U> = dyn Fn(&Configuration<U>) -> Verdict;The Loop
The whole framework is one loop: propose removals, keep the first one the oracle still finds interesting, and repeat. Everything else—what to propose, when to stop—is delegated:
/// A candidate removal set
type Delta<U> = HashSet<U>;
/// The main loop of delta debugging
fn reduce<U: AtomicUnit, P: Policy<U>>(
units: Configuration<U>,
oracle: &Oracle<U>,
mut policy: P,
) -> Configuration<U> {
let mut config = units;
loop {
let mut reduced = None;
for delta in policy.propose(&config) {
// an empty delta would be a no-op
// that could never make progress.
assert!(!delta.is_empty());
let candidate = &config - δ
if oracle(&candidate) == Verdict::Interesting {
reduced = Some(candidate);
break;
}
}
// the policy decides when to stop
let keep_going =
policy.on_reduced(reduced.as_ref());
if let Some(candidate) = reduced {
config = candidate; // update the current configuration
}
if !keep_going {
break;
}
}
config
}A Delta is a subset of the current configuration that we propose to remove.
Everything algorithm-specific lives in the Policy.
trait Policy<U: AtomicUnit> {
/// Generate candidate removal sets *lazily*.
fn propose(
&mut self,
config: &Configuration<U>,
) -> impl Iterator<Item = Delta<U>>;
/// React to a reduction pass.
/// `reduced` is `Some` if the pass removed anything,
/// `None` if it made no progress.
/// Return `true` to keep going, `false` to stop.
/// The default stops at the fixpoint.
fn on_reduced(
&mut self,
reduced: Option<&Configuration<U>>,
) -> bool {
reduced.is_some()
}
}For many delta debugging algorithms, including DDMin,
the default implementation of on_reduced is enough.
DDMin Policy
In DDMin, the policy is simple: it partitions the configuration into n equal-sized chunks, and proposes to keep each chunk in turn, as well as the complement of each chunk.
The granularity n starts at 2 and doubles whenever the algorithm fails to make progress.
// Compiles and runs on its own:
//
// rustc --edition 2024 ddmin.rs && ./ddmin
use std::collections::HashSet;
use std::iter::successors;
/// An indivisible piece of the input: a char, token, line, etc.
trait AtomicUnit: Copy + Eq + std::hash::Hash + Ord {}
impl<T: Copy + Eq + std::hash::Hash + Ord> AtomicUnit
for T
{
}
/// The units we keep.
type Configuration<U> = HashSet<U>;
#[derive(PartialEq)]
enum Verdict {
Interesting, // still triggers the bug
NotInteresting, // does not trigger the bug or is invalid
}
type Oracle<U> = dyn Fn(&Configuration<U>) -> Verdict;
/// A candidate removal set
type Delta<U> = HashSet<U>;
/// The main loop of delta debugging
fn reduce<U: AtomicUnit, P: Policy<U>>(
units: Configuration<U>,
oracle: &Oracle<U>,
mut policy: P,
) -> Configuration<U> {
let mut config = units;
loop {
let mut reduced = None;
for delta in policy.propose(&config) {
// an empty delta would be a no-op
// that could never make progress.
assert!(!delta.is_empty());
let candidate = &config - δ
if oracle(&candidate) == Verdict::Interesting {
reduced = Some(candidate);
break;
}
}
// the policy decides when to stop
let keep_going =
policy.on_reduced(reduced.as_ref());
if let Some(candidate) = reduced {
config = candidate; // update the current configuration
}
if !keep_going {
break;
}
}
config
}
trait Policy<U: AtomicUnit> {
/// Generate candidate removal sets *lazily*.
fn propose(
&mut self,
config: &Configuration<U>,
) -> impl Iterator<Item = Delta<U>>;
/// React to a reduction pass.
/// `reduced` is `Some` if the pass removed anything,
/// `None` if it made no progress.
/// Return `true` to keep going, `false` to stop.
/// The default stops at the fixpoint.
fn on_reduced(
&mut self,
reduced: Option<&Configuration<U>>,
) -> bool {
reduced.is_some()
}
}
/// Split `config` into at most `n` roughly-equal, disjoint subsets.
fn partition<U: AtomicUnit>(
config: &Configuration<U>,
n: usize,
) -> Vec<Delta<U>> {
let mut items: Vec<U> =
config.iter().copied().collect();
items.sort_unstable(); // deterministic chunks for a reproducible demo
let len = items.len();
if n == 0 || len == 0 {
return Vec::new();
}
let size = len.div_ceil(n);
items
.chunks(size)
.map(|c| c.iter().copied().collect())
.collect()
}
struct DDMin; // no state — granularity lives inside one `propose` call
impl<U: AtomicUnit> Policy<U> for DDMin {
fn propose(
&mut self,
config: &Configuration<U>,
) -> impl Iterator<Item = Delta<U>> {
let units = config.len();
// Granularities n = 2, 4, 8, ... up to `units`
successors(Some(2), move |&n| {
(n < units).then(|| (2 * n).min(units))
})
.flat_map(move |n| {
let subsets = partition(config, n); // n roughly-equal subsets
let keep_only = subsets
.clone()
.into_iter()
.map(move |d| config - &d);
// First every δ = ∇ᵢ (keep only Δᵢ),
// then every δ = Δᵢ (drop Δᵢ).
keep_only.chain(subsets)
})
.filter(|delta| !delta.is_empty())
}
}
fn main() {
println!("minimizing the set 1..=8; interesting iff it keeps 2 and 7");
let input: Configuration<u32> = (1..=8).collect();
let oracle_calls =
std::rc::Rc::new(std::cell::Cell::new(0u32));
let counter = oracle_calls.clone();
let keeps_2_and_7 = move |c: &Configuration<u32>| {
counter.set(counter.get() + 1);
let mut probe: Vec<u32> =
c.iter().copied().collect();
probe.sort_unstable();
let verdict = if c.contains(&2) && c.contains(&7) {
Verdict::Interesting
} else {
Verdict::NotInteresting
};
let mark = if verdict == Verdict::Interesting {
"interesting (reduce to this)"
} else {
"not interesting"
};
println!(" test {probe:?} -> {mark}");
verdict
};
let mut result: Vec<_> =
reduce(input, &keeps_2_and_7, DDMin)
.into_iter()
.collect();
result.sort_unstable();
println!(
"=> minimized to {result:?} in {} oracle calls",
oracle_calls.get()
);
assert_eq!(result, [2, 7]);
assert_eq!(oracle_calls.get(), 33);
}The partition utility it relies on:
Tip
Press play to see how it chunks
{1, ..., 8}as the granularityngrows: the chunks stay contiguous and as even as possible.
use std::collections::HashSet;
trait AtomicUnit: Copy + Eq + std::hash::Hash + Ord {}
impl<T: Copy + Eq + std::hash::Hash + Ord> AtomicUnit for T {}
type Configuration<U> = HashSet<U>;
type Delta<U> = HashSet<U>;
/// Split `config` into at most `n` roughly-equal, disjoint subsets.
fn partition<U: AtomicUnit>(
config: &Configuration<U>,
n: usize,
) -> Vec<Delta<U>> {
let mut items: Vec<U> =
config.iter().copied().collect();
items.sort_unstable(); // deterministic chunks for a reproducible demo
let len = items.len();
if n == 0 || len == 0 {
return Vec::new();
}
let size = len.div_ceil(n);
items
.chunks(size)
.map(|c| c.iter().copied().collect())
.collect()
}
fn main() {
let config: Configuration<u32> = (1..=8).collect();
for n in [2, 3, 4] {
let chunks: Vec<Vec<u32>> = partition(&config, n)
.iter()
.map(|s| {
let mut v: Vec<u32> = s.iter().copied().collect();
v.sort_unstable();
v
})
.collect();
println!("partition({{1..=8}}, {n}) = {chunks:?}");
}
}Run It
Now, let’s see how DDMin works on a simple example.
Tip
Press the play button to run the full minimization and watch DDMin narrow
{1, ..., 8}down to{2, 7}, probing coarse-to-fine the whole way.
// Compiles and runs on its own:
//
// rustc --edition 2024 ddmin.rs && ./ddmin
use std::collections::HashSet;
use std::iter::successors;
/// An indivisible piece of the input: a char, token, line, etc.
trait AtomicUnit: Copy + Eq + std::hash::Hash + Ord {}
impl<T: Copy + Eq + std::hash::Hash + Ord> AtomicUnit
for T
{
}
/// The units we keep.
type Configuration<U> = HashSet<U>;
#[derive(PartialEq)]
enum Verdict {
Interesting, // still triggers the bug
NotInteresting, // does not trigger the bug or is invalid
}
type Oracle<U> = dyn Fn(&Configuration<U>) -> Verdict;
/// A candidate removal set
type Delta<U> = HashSet<U>;
/// The main loop of delta debugging
fn reduce<U: AtomicUnit, P: Policy<U>>(
units: Configuration<U>,
oracle: &Oracle<U>,
mut policy: P,
) -> Configuration<U> {
let mut config = units;
loop {
let mut reduced = None;
for delta in policy.propose(&config) {
// an empty delta would be a no-op
// that could never make progress.
assert!(!delta.is_empty());
let candidate = &config - δ
if oracle(&candidate) == Verdict::Interesting {
reduced = Some(candidate);
break;
}
}
// the policy decides when to stop
let keep_going =
policy.on_reduced(reduced.as_ref());
if let Some(candidate) = reduced {
config = candidate; // update the current configuration
}
if !keep_going {
break;
}
}
config
}
trait Policy<U: AtomicUnit> {
/// Generate candidate removal sets *lazily*.
fn propose(
&mut self,
config: &Configuration<U>,
) -> impl Iterator<Item = Delta<U>>;
/// React to a reduction pass.
/// `reduced` is `Some` if the pass removed anything,
/// `None` if it made no progress.
/// Return `true` to keep going, `false` to stop.
/// The default stops at the fixpoint.
fn on_reduced(
&mut self,
reduced: Option<&Configuration<U>>,
) -> bool {
reduced.is_some()
}
}
/// Split `config` into at most `n` roughly-equal, disjoint subsets.
fn partition<U: AtomicUnit>(
config: &Configuration<U>,
n: usize,
) -> Vec<Delta<U>> {
let mut items: Vec<U> =
config.iter().copied().collect();
items.sort_unstable(); // deterministic chunks for a reproducible demo
let len = items.len();
if n == 0 || len == 0 {
return Vec::new();
}
let size = len.div_ceil(n);
items
.chunks(size)
.map(|c| c.iter().copied().collect())
.collect()
}
struct DDMin; // no state — granularity lives inside one `propose` call
impl<U: AtomicUnit> Policy<U> for DDMin {
fn propose(
&mut self,
config: &Configuration<U>,
) -> impl Iterator<Item = Delta<U>> {
let units = config.len();
// Granularities n = 2, 4, 8, ... up to `units`
successors(Some(2), move |&n| {
(n < units).then(|| (2 * n).min(units))
})
.flat_map(move |n| {
let subsets = partition(config, n); // n roughly-equal subsets
let keep_only = subsets
.clone()
.into_iter()
.map(move |d| config - &d);
// First every δ = ∇ᵢ (keep only Δᵢ),
// then every δ = Δᵢ (drop Δᵢ).
keep_only.chain(subsets)
})
.filter(|delta| !delta.is_empty())
}
}
fn main() {
println!("minimizing the set 1..=8; interesting iff it keeps 2 and 7");
let input: Configuration<u32> = (1..=8).collect();
let oracle_calls =
std::rc::Rc::new(std::cell::Cell::new(0u32));
let counter = oracle_calls.clone();
let keeps_2_and_7 = move |c: &Configuration<u32>| {
counter.set(counter.get() + 1);
let mut probe: Vec<u32> =
c.iter().copied().collect();
probe.sort_unstable();
let verdict = if c.contains(&2) && c.contains(&7) {
Verdict::Interesting
} else {
Verdict::NotInteresting
};
let mark = if verdict == Verdict::Interesting {
"interesting (reduce to this)"
} else {
"not interesting"
};
println!(" test {probe:?} -> {mark}");
verdict
};
let mut result: Vec<_> =
reduce(input, &keeps_2_and_7, DDMin)
.into_iter()
.collect();
result.sort_unstable();
println!(
"=> minimized to {result:?} in {} oracle calls",
oracle_calls.get()
);
assert_eq!(result, [2, 7]);
assert_eq!(oracle_calls.get(), 33);
}