Hierarchical Delta Debugging
DDMin and ProbDD both see the input as one flat list of atomic units. But real failing inputs—programs, HTML, JSON—are trees. Flattening a tree throws away exactly the structure that tells us where to cut: a single node high in the tree can stand for thousands of atomic units below it.
HDD keeps the tree. It walks the syntax tree level by level, from the root down, and at each level it asks an ordinary list-minimizer which of that level’s nodes to drop. Dropping a node drops its whole subtree, so one test high in the tree can delete a huge, irrelevant region at once—and every candidate it produces is still a syntactically valid tree.
Two Spaces: Nodes and Units
If the input is now a tree, what should the configuration—the set that reduction shrinks—contain?
Not tree nodes. The atomic units are still exactly what they were in DDMin: the indivisible pieces of the input. For a program those are its tokens:
/// This chapter's atomic unit: a token of the program, identified by
/// its position in source order (0, 1, 2, ...).
type Token = u32;The tree is a separate, static map over those units, so its nodes get
their own id type. An internal node like fn bar spans many tokens,
but it is not itself an input—it is a name for a region of the
input—so it must never be confused with one of the input’s tokens.
Only the leaves touch the input:
/// Identifies a node of the parse tree. *Not* an atomic unit: internal
/// nodes never appear in a Configuration. A leaf (token) node corresponds
/// to exactly one atomic unit: its source-order index, `tree.leaf2token[&id]`.
#[derive(Clone, Copy, PartialEq, Eq, Hash, PartialOrd, Ord, Debug)]
struct NodeId(u32);
struct Node {
label: &'static str,
children: Vec<NodeId>,
}
struct Tree {
id2node: HashMap<NodeId, Node>,
root: NodeId,
node2depth: HashMap<NodeId, usize>, // BFS depth of each node
node2parent: HashMap<NodeId, NodeId>,
max_depth: usize,
leaf2token: HashMap<NodeId, Token>, // a leaf's token is its source-order index
token2leaf: HashMap<Token, NodeId>, // inverse of `leaf2token`
}In the demo tree used below, the tokens number like this:
program
├─ fn bar (the bug)
│ ├─ stmt b1 unit 0
│ ├─ if guard
│ │ ├─ stmt g unit 1
│ │ └─ crash() unit 2
│ └─ stmt b2 unit 3
├─ fn f2 { stmt; stmt; } units 4, 5
├─ fn f3 { stmt; stmt; } units 6, 7
├─ fn f4 { stmt; stmt; } units 8, 9
├─ fn f5 { stmt; stmt; } units 10, 11
└─ fn f6 { stmt; stmt; } units 12, 13
The starting configuration is simply every token: {0, 1, ..., 13}. The
tree never shrinks; only the configuration does. That split means HDD keeps
working in two spaces at once—nodes to decide, units to test—and it
needs one bridge in each direction.
Node space → unit space. When HDD decides to try dropping the subtree
fn f2, the reduce loop can’t test a node: a Delta is a set of units.
leaves_under translates the decision into a testable delta by collecting
the surviving units inside the subtree—dropping fn f2 means the delta
{4, 5}:
/// Node space -> unit space: the surviving atomic units in the subtree
/// rooted at `id`.
fn leaves_under(
&self,
id: NodeId,
present: &Configuration<Token>,
) -> Delta<Token> {
let mut out = Delta::new();
let mut stack = vec![id];
while let Some(n) = stack.pop() {
let node = &self.id2node[&n];
if node.children.is_empty() {
let u = self.leaf2token[&n];
if present.contains(&u) {
out.insert(u);
}
} else {
stack.extend(node.children.iter().copied());
}
}
out
}Unit space → node space. Going the other way, HDD must ask which
level-L subtrees still exist: a node whose tokens have all been deleted
is gone, even though the static tree still has it. Rather than store
liveness separately (state that could drift out of sync), we recover it
from the configuration itself: walk each surviving unit’s leaf up to its
ancestor at level L. If units {0,...,5} survive, level 1 holds
{fn bar, fn f2}; delete units 4 and 5 and it holds only {fn bar}:
/// Unit space -> node space: the level-`level` subtrees that still hold
/// a surviving token.
fn alive_level_nodes(
&self,
level: usize,
present: &Configuration<Token>,
) -> Configuration<NodeId> {
present
.iter()
.map(|&u| self.token2leaf[&u])
.filter(|leaf| self.node2depth[leaf] >= level)
.map(|leaf| self.ancestor_at(leaf, level))
.collect()
}
/// Walk up from `id` to its ancestor sitting at `level`.
fn ancestor_at(
&self,
mut id: NodeId,
level: usize,
) -> NodeId {
while self.node2depth[&id] > level {
id = self.node2parent[&id];
}
id
}A Policy Over Subtrees
HDD’s plan is to reuse a plain list-minimizer at every level: hand it the
set of live level-L subtrees and let it discover which of them are
removable. A subtree is hardly “atomic”—it holds many tokens—but
atomicity is relative to the reduction problem: it means whatever pieces
that problem never splits. The inner problem—shrink this level’s list of
subtrees—only keeps or drops whole subtrees, so there NodeId is the
atomic unit: the inner minimizer runs as a Policy<NodeId>, and
DDMin/ProbDD satisfy it unchanged.
HDD itself is a Policy<Token> toward the reduce loop: whatever the
inner policy decides in node space is expanded through leaves_under
into a token-delta before the oracle ever sees it.
HDD Is a Policy
HDD is itself just another Policy—to the reduce loop it looks
exactly like DDMin: a stream of unit-deltas. All the hierarchy hides behind
propose:
/// HDD is a Policy over atomic units. It walks the tree level by level
/// (coarse → fine) and, for the current level, lets an *inner policy*
/// -- a `Policy<NodeId>` -- choose which of that level's subtrees to
/// drop. Each chosen node is mapped down to the units under it before
/// the single `reduce` loop tests the removal.
struct Hdd<'t, F, P> {
tree: &'t Tree,
new_minimizer: F, // build a fresh list-minimizer for a level, e.g. `|| DDMin`
level: usize, // the shallowest level not yet known to be minimal
minimizer: Option<P>, // The inner minimizer for the current level
level_subtrees: Configuration<NodeId>, // a field, not a local, so `propose`'s returned iterator can borrow it
}
impl<'t, F, P> Hdd<'t, F, P>
where
F: Fn() -> P,
P: Policy<NodeId>,
{
fn new(
tree: &'t Tree,
level: usize,
new_minimizer: F,
) -> Self {
Hdd {
tree,
new_minimizer,
level,
minimizer: None,
level_subtrees: Configuration::new(),
}
}
}propose is the delegation step. For the current level it names the live
subtrees with alive_level_nodes, lets the inner policy (DDMin,
ProbDD, …) choose which nodes to drop, and maps each choice down
through leaves_under into the unit-delta the loop can test:
// To the `reduce` loop HDD removes atomic units (`Policy` defaults to
// `Policy<AtomicUnit>`); its inner minimizer picks among *subtrees*.
impl<'t, F, P> Policy<Token> for Hdd<'t, F, P>
where
F: Fn() -> P,
P: Policy<NodeId>,
{
fn propose(
&mut self,
config: &Configuration<Token>,
) -> impl Iterator<Item = Delta<Token>> {
let tree = self.tree;
let level = self.level;
// Build this level's minimizer on its first pass.
if self.minimizer.is_none() {
self.minimizer = Some((self.new_minimizer)());
}
// Hand the inner minimizer the level's *subtrees*
self.level_subtrees =
tree.alive_level_nodes(level, config);
let subtrees = &self.level_subtrees;
let minimizer = self.minimizer.as_mut().unwrap();
// lazily: the inner policy may only learn from confirmed failures
minimizer.propose(subtrees).map(
move |drop| -> Delta<Token> {
// dropping a subtree drops the units under it
drop.iter()
.flat_map(|&id| {
tree.leaves_under(id, config)
})
.collect()
},
)
}Why stream instead of collecting the inner policy’s candidates in one
batch? Pulling the next candidate from propose is itself the signal that
the previous one failed. A stateful policy like ProbDD updates its model on
every failure, and because self.minimizer is reused across a level’s
passes, it carries that learning from one pass to the next. Streaming
lazily means the inner policy advances only as the oracle consumes
candidates, so the model learns only from failures that actually happened.
Deciding when to descend is delegated the same way. When a pass ends, HDD
forwards the outcome to the inner policy’s own on_reduced—translated
into the inner policy’s space, this level’s live subtrees—and descends
only when the inner policy declares itself minimal:
fn on_reduced(
&mut self,
reduced: Option<&Configuration<Token>>,
) -> bool {
let (tree, level) = (self.tree, self.level);
// the pass outcome, in the inner policy's space
let subtrees = reduced
.map(|c| tree.alive_level_nodes(level, c));
let inner = self.minimizer.as_mut().unwrap();
if inner.on_reduced(subtrees.as_ref()) {
return true; // inner isn't minimal here yet
}
// The inner policy is minimal: descend and rebuild.
self.level += 1;
self.minimizer = None;
self.level <= tree.max_depth
}HDD never hard-codes the stop test, so any list-minimizer—stateless or learning—drives the descent.
To make the delegation concrete, here is the first pass on the demo tree.
The level-1 live subtrees are all six functions; the inner DDMin’s first
candidate keeps the half {fn bar, fn f2, fn f3}, i.e. proposes dropping
the node-set {fn f4, fn f5, fn f6}; leaves_under turns that into the
unit-delta {8, ..., 13}; the oracle still sees crash() (unit 2), so
half the noise disappears in a single test.
level 1 subtrees {fn bar, f2, f3, f4, f5, f6}
inner DDMin drops {f4, f5, f6} (node space)
leaves_under {8, 9, 10, 11, 12, 13} (unit space)
oracle still crashes => reduced
Note
Because HDD only ever removes whole subtrees, every candidate it hands the oracle is a syntactically valid tree. The original DDMin on a flattened token list would spend most of its tests on inputs that don’t even parse; HDD never wastes a test on a parse error. (Measured in The Flat Baseline below.)
Note
The demos start HDD at level 1, not level 0. Level 0 holds only the root, and deleting the whole program can never stay interesting, so a level-0 pass is guaranteed wasted work. (Perses will make level 0 harmless in a different way: a grammar-driven filter on what may be deleted at all.)
Run It
The input is the tree above: fn bar holds the bug—an if whose body
calls crash()—and the other five functions are noise.
Keeping the crash() token keeps its whole ancestor chain, so the answer
must be program → fn bar → if → crash().
Tip
Press play. Watch the first few tests delete whole functions at the top level (one test each), then watch HDD descend into
fn barand trim it down, coarse-to-fine.
// Hierarchical delta debugging: HDD is *itself* a Policy, driven by the same
// single `reduce` loop as DDMin/ProbDD. Internally its `propose` walks the parse
// tree level by level and delegates candidate generation to an inner Policy
// (DDMin, ProbDD, ...). Compiles and runs on its own:
//
// rustc --edition 2024 hdd.rs && ./hdd
use std::collections::HashMap;
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 {}
/// This chapter's atomic unit: a token of the program, identified by
/// its position in source order (0, 1, 2, ...).
type Token = u32;
/// 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
// First every δ = ∇ᵢ (keep only Δᵢ), then every δ = Δᵢ (drop Δᵢ).
let keep_only = subsets
.clone()
.into_iter()
.map(move |d| config - &d);
keep_only.chain(subsets)
})
.filter(|delta| !delta.is_empty())
}
}
struct ProbDD<U: AtomicUnit> {
unit2prob: HashMap<U, f64>,
p0: f64,
}
impl<U: AtomicUnit> ProbDD<U> {
fn sync(&mut self, config: &Configuration<U>) {
self.unit2prob.retain(|u, _| config.contains(u));
for &u in config {
self.unit2prob.entry(u).or_insert(self.p0);
}
}
}
fn best_prefix<U: AtomicUnit>(
unit2prob: &HashMap<U, f64>,
) -> Vec<U> {
let mut units: Vec<U> =
unit2prob.keys().copied().collect();
units.sort_by(|a, b| {
unit2prob[a]
.partial_cmp(&unit2prob[b])
.unwrap()
.then(a.cmp(b))
});
let mut survive = 1.0;
let (mut best_k, mut best_gain) = (0, 0.0);
for (i, u) in units.iter().enumerate() {
survive *= 1.0 - unit2prob[u];
let gain = (i + 1) as f64 * survive;
if gain > best_gain {
(best_k, best_gain) = (i + 1, gain);
}
}
units.truncate(best_k);
units
}
fn bayes_update<U: AtomicUnit>(
unit2prob: &mut HashMap<U, f64>,
pre: &[U],
) {
let survive: f64 =
pre.iter().map(|u| 1.0 - unit2prob[u]).product();
let denom = 1.0 - survive;
if denom <= 0.0 {
return;
}
for u in pre {
let p = unit2prob[u];
unit2prob.insert(*u, (p / denom).min(1.0));
}
}
impl<U: AtomicUnit> Policy<U> for ProbDD<U> {
fn propose(
&mut self,
config: &Configuration<U>,
) -> impl Iterator<Item = Delta<U>> {
self.sync(config);
let unit2prob = &mut self.unit2prob;
let mut last: Option<Vec<U>> = None;
std::iter::from_fn(move || {
if let Some(pre) = &last {
bayes_update(unit2prob, pre);
}
if unit2prob.values().all(|&p| p >= 1.0) {
return None;
}
let pre = best_prefix(unit2prob);
if pre.is_empty() {
return None;
}
last = Some(pre.clone());
Some(pre.into_iter().collect())
})
}
}
/// Identifies a node of the parse tree. *Not* an atomic unit: internal
/// nodes never appear in a Configuration. A leaf (token) node corresponds
/// to exactly one atomic unit: its source-order index, `tree.leaf2token[&id]`.
#[derive(Clone, Copy, PartialEq, Eq, Hash, PartialOrd, Ord, Debug)]
struct NodeId(u32);
struct Node {
label: &'static str,
children: Vec<NodeId>,
}
struct Tree {
id2node: HashMap<NodeId, Node>,
root: NodeId,
node2depth: HashMap<NodeId, usize>, // BFS depth of each node
node2parent: HashMap<NodeId, NodeId>,
max_depth: usize,
leaf2token: HashMap<NodeId, Token>, // a leaf's token is its source-order index
token2leaf: HashMap<Token, NodeId>, // inverse of `leaf2token`
}
impl Tree {
fn new(
root: NodeId,
id2node: HashMap<NodeId, Node>,
) -> Tree {
// BFS from the root to label every node with its depth (= its level)
// and remember its parent.
let mut node2depth = HashMap::new();
let mut node2parent = HashMap::new();
let mut max_depth = 0;
let mut frontier = vec![root];
let mut d = 0;
while !frontier.is_empty() {
let mut next = Vec::new();
for &id in &frontier {
node2depth.insert(id, d);
max_depth = d;
for &c in &id2node[&id].children {
node2parent.insert(c, id);
next.push(c);
}
}
frontier = next;
d += 1;
}
// DFS in child order (= source order): the k-th leaf from the left
// is the token with source-order index k, i.e. atomic unit k.
let mut leaf2token = HashMap::new();
let mut token2leaf = HashMap::new();
let mut stack = vec![root];
while let Some(id) = stack.pop() {
let node = &id2node[&id];
if node.children.is_empty() {
let u = token2leaf.len() as Token;
leaf2token.insert(id, u);
token2leaf.insert(u, id);
} else {
// push in reverse so children pop left-to-right
stack.extend(
node.children.iter().rev().copied(),
);
}
}
Tree {
id2node,
root,
node2depth,
node2parent,
max_depth,
leaf2token,
token2leaf,
}
}
/// Node space -> unit space: the surviving atomic units in the subtree
/// rooted at `id`.
fn leaves_under(
&self,
id: NodeId,
present: &Configuration<Token>,
) -> Delta<Token> {
let mut out = Delta::new();
let mut stack = vec![id];
while let Some(n) = stack.pop() {
let node = &self.id2node[&n];
if node.children.is_empty() {
let u = self.leaf2token[&n];
if present.contains(&u) {
out.insert(u);
}
} else {
stack.extend(node.children.iter().copied());
}
}
out
}
/// Unit space -> node space: the level-`level` subtrees that still hold
/// a surviving token.
fn alive_level_nodes(
&self,
level: usize,
present: &Configuration<Token>,
) -> Configuration<NodeId> {
present
.iter()
.map(|&u| self.token2leaf[&u])
.filter(|leaf| self.node2depth[leaf] >= level)
.map(|leaf| self.ancestor_at(leaf, level))
.collect()
}
/// Walk up from `id` to its ancestor sitting at `level`.
fn ancestor_at(
&self,
mut id: NodeId,
level: usize,
) -> NodeId {
while self.node2depth[&id] > level {
id = self.node2parent[&id];
}
id
}
}
/// HDD is a Policy over atomic units. It walks the tree level by level
/// (coarse → fine) and, for the current level, lets an *inner policy*
/// -- a `Policy<NodeId>` -- choose which of that level's subtrees to
/// drop. Each chosen node is mapped down to the units under it before
/// the single `reduce` loop tests the removal.
struct Hdd<'t, F, P> {
tree: &'t Tree,
new_minimizer: F, // build a fresh list-minimizer for a level, e.g. `|| DDMin`
level: usize, // the shallowest level not yet known to be minimal
minimizer: Option<P>, // The inner minimizer for the current level
level_subtrees: Configuration<NodeId>, // a field, not a local, so `propose`'s returned iterator can borrow it
}
impl<'t, F, P> Hdd<'t, F, P>
where
F: Fn() -> P,
P: Policy<NodeId>,
{
fn new(
tree: &'t Tree,
level: usize,
new_minimizer: F,
) -> Self {
Hdd {
tree,
new_minimizer,
level,
minimizer: None,
level_subtrees: Configuration::new(),
}
}
}
// To the `reduce` loop HDD removes atomic units (`Policy` defaults to
// `Policy<AtomicUnit>`); its inner minimizer picks among *subtrees*.
impl<'t, F, P> Policy<Token> for Hdd<'t, F, P>
where
F: Fn() -> P,
P: Policy<NodeId>,
{
fn propose(
&mut self,
config: &Configuration<Token>,
) -> impl Iterator<Item = Delta<Token>> {
let tree = self.tree;
let level = self.level;
// Build this level's minimizer on its first pass.
if self.minimizer.is_none() {
self.minimizer = Some((self.new_minimizer)());
}
// Hand the inner minimizer the level's *subtrees*
self.level_subtrees =
tree.alive_level_nodes(level, config);
let subtrees = &self.level_subtrees;
let minimizer = self.minimizer.as_mut().unwrap();
// lazily: the inner policy may only learn from confirmed failures
minimizer.propose(subtrees).map(
move |drop| -> Delta<Token> {
// dropping a subtree drops the units under it
drop.iter()
.flat_map(|&id| {
tree.leaves_under(id, config)
})
.collect()
},
)
}
fn on_reduced(
&mut self,
reduced: Option<&Configuration<Token>>,
) -> bool {
let (tree, level) = (self.tree, self.level);
// the pass outcome, in the inner policy's space
let subtrees = reduced
.map(|c| tree.alive_level_nodes(level, c));
let inner = self.minimizer.as_mut().unwrap();
if inner.on_reduced(subtrees.as_ref()) {
return true; // inner isn't minimal here yet
}
// The inner policy is minimal: descend and rebuild.
self.level += 1;
self.minimizer = None;
self.level <= tree.max_depth
}
}
/// Render a configuration (a set of surviving tokens) back into nested
/// source-ish text: a node is shown iff some token under it survives.
fn render(tree: &Tree, present: &Configuration<Token>) -> String {
fn alive(
tree: &Tree,
id: NodeId,
present: &Configuration<Token>,
) -> bool {
let node = &tree.id2node[&id];
if node.children.is_empty() {
present.contains(&tree.leaf2token[&id])
} else {
node.children
.iter()
.any(|&c| alive(tree, c, present))
}
}
fn go(
tree: &Tree,
id: NodeId,
present: &Configuration<Token>,
out: &mut String,
) {
let node = &tree.id2node[&id];
out.push_str(node.label);
let kids: Vec<NodeId> = node
.children
.iter()
.copied()
.filter(|&c| alive(tree, c, present))
.collect();
if !kids.is_empty() {
out.push_str(" { ");
for (i, c) in kids.iter().enumerate() {
if i > 0 {
out.push_str("; ");
}
go(tree, *c, present, out);
}
out.push_str(" }");
}
}
if !alive(tree, tree.root, present) {
return String::new();
}
let mut out = String::new();
go(tree, tree.root, present, &mut out);
out
}
fn main() {
// The chapter's demo tree: one buggy function among five noise functions.
let tree = std::rc::Rc::new(example_tree());
// the starting configuration: every token
let all: Configuration<Token> =
(0..tree.token2leaf.len() as Token).collect();
// Interesting iff the program still contains the crash() token.
let crash: Token = tree
.id2node
.iter()
.find(|(_, n)| n.label == "crash()")
.map(|(id, _)| tree.leaf2token[id])
.unwrap();
let expected = vec![crash]; // just the crash() token
for (name, run) in
[("HDD + DDMin", 0u8), ("HDD + ProbDD", 1u8)]
{
println!("\n================== {name} ==================");
let calls =
std::rc::Rc::new(std::cell::Cell::new(0u32));
let counter = calls.clone();
let otree = tree.clone();
let oracle = move |c: &Configuration<Token>| {
counter.set(counter.get() + 1);
let verdict = if c.contains(&crash) {
Verdict::Interesting
} else {
Verdict::NotInteresting
};
println!(
" test {:?} -> {}",
render(&otree, c),
if verdict == Verdict::Interesting {
"crashes (keep)"
} else {
"ok (reject)"
},
);
verdict
};
// start at level 1 (the chapter's note explains why)
let result = if run == 0 {
reduce(
all.clone(),
&oracle,
Hdd::new(&*tree, 1, || DDMin),
)
} else {
reduce(
all.clone(),
&oracle,
Hdd::new(&*tree, 1, || ProbDD {
unit2prob: HashMap::new(),
p0: 0.1,
}),
)
};
let mut got: Vec<Token> =
result.iter().copied().collect();
got.sort_unstable();
println!(
" => minimized to {} in {} oracle calls",
render(&tree, &result),
calls.get()
);
assert_eq!(got, expected);
assert_eq!(calls.get(), if run == 0 { 11 } else { 15 });
}
}
fn example_tree() -> Tree {
fn n(
label: &'static str,
children: Vec<u32>,
) -> Node {
Node {
label,
children: children
.into_iter()
.map(NodeId)
.collect(),
}
}
let id2node: HashMap<NodeId, Node> = HashMap::from([
(NodeId(0), n("program", vec![1, 2, 3, 4, 5, 6])),
// fn bar — holds the bug
(NodeId(1), n("fn bar", vec![7, 8, 9])),
(NodeId(7), n("stmt b1", vec![])),
(NodeId(8), n("if guard", vec![20, 21])),
(NodeId(20), n("stmt g", vec![])),
(NodeId(21), n("crash()", vec![])),
(NodeId(9), n("stmt b2", vec![])),
// fn f2..f6 — irrelevant noise, each a small subtree
(NodeId(2), n("fn f2", vec![10, 11])),
(NodeId(10), n("stmt", vec![])),
(NodeId(11), n("stmt", vec![])),
(NodeId(3), n("fn f3", vec![12, 13])),
(NodeId(12), n("stmt", vec![])),
(NodeId(13), n("stmt", vec![])),
(NodeId(4), n("fn f4", vec![14, 15])),
(NodeId(14), n("stmt", vec![])),
(NodeId(15), n("stmt", vec![])),
(NodeId(5), n("fn f5", vec![16, 17])),
(NodeId(16), n("stmt", vec![])),
(NodeId(17), n("stmt", vec![])),
(NodeId(6), n("fn f6", vec![18, 19])),
(NodeId(18), n("stmt", vec![])),
(NodeId(19), n("stmt", vec![])),
]);
Tree::new(NodeId(0), id2node)
}The top level goes first: fn f4, fn f5, and fn f6, then fn f3, then
fn f2 are dropped—each whole function subtree gone in a single test.
Only then does HDD step inside the surviving fn bar, drop its stray
statements, and finally, one level deeper, drop the if’s body.
Rendered back into the tree it came from, that is:
program { fn bar { if guard { crash() } } }
Swapping the Minimizer
The inner minimizer is a constructor argument, so swapping DDMin for ProbDD
is one line—|| DDMin becomes || ProbDD { probs: HashMap::new(), p0: 0.1 },
and nothing else changes. The demo above already runs both and prints each
count.
Note
ProbDD reaches the same result—but in 15 calls, more than DDMin’s 11.
That is not a bug. HDD hands the inner policy a fresh, tiny list at every level and rebuilds it from scratch each round, so ProbDD’s probability model—its whole advantage—never has room to learn, and never carries information from one level of the tree to the next.
The hierarchy and the statistics never talk. Closing that gap would need a policy that reasons across the whole tree at once, a different problem than the one explored here.
The Flat Baseline
How much did the tree actually buy? Let’s strip it away and measure, with
plain DDMin and ProbDD as the policy—each is already a
Policy<Token>, so no adapter is needed. But stripping the tree changes
what a “token” is. The 14 units above were statements—a grouping the
tree gave us. A flat minimizer sees the raw token stream, keywords, braces,
and semicolons included: 58 units, most of them punctuation.
/// The demo program as a raw token stream.
const TOKENS: &[&str] = &[
// fn bar { b1 ; if guard { g ; crash ( ) ; } b2 ; }
"fn", "bar", "{", "b1", ";", "if", "guard", "{", "g",
";", "crash", "(", ")", ";", "}", "b2", ";", "}",
// fn f2 { s ; s ; } ... fn f6 { s ; s ; }
"fn", "f2", "{", "s", ";", "s", ";", "}",
"fn", "f3", "{", "s", ";", "s", ";", "}",
"fn", "f4", "{", "s", ";", "s", ";", "}",
"fn", "f5", "{", "s", ";", "s", ";", "}",
"fn", "f6", "{", "s", ";", "s", ";", "}",
];
/// Render a configuration back into source: the surviving tokens
/// in source order.
fn render(config: &Configuration<Token>) -> String {
let mut keep: Vec<Token> =
config.iter().copied().collect();
keep.sort_unstable();
keep.iter()
.map(|&u| TOKENS[u as usize])
.collect::<Vec<_>>()
.join(" ")
}The oracle changes too. HDD removed only whole subtrees, so every candidate
parsed by construction, and “interesting” could reduce to “does crash()
survive”. A flat delta can drop a { and keep its }, so the oracle must
now parse each candidate before it can possibly crash:
// A recursive-descent parser for the demo language:
//
// program := fn_item*
// fn_item := "fn" IDENT "{" stmt* "}"
// stmt := "if" IDENT "{" stmt* "}"
// | IDENT "(" ")" ";"
// | IDENT ";"
fn parses(toks: &[&str]) -> bool {
let mut pos = 0;
while pos < toks.len() {
if !fn_item(toks, &mut pos) {
return false;
}
}
true
}
fn fn_item(toks: &[&str], pos: &mut usize) -> bool {
eat(toks, pos, "fn")
&& ident(toks, pos)
&& block(toks, pos)
}
fn block(toks: &[&str], pos: &mut usize) -> bool {
if !eat(toks, pos, "{") {
return false;
}
while toks.get(*pos) != Some(&"}") {
if *pos >= toks.len() || !stmt(toks, pos) {
return false;
}
}
eat(toks, pos, "}")
}
fn stmt(toks: &[&str], pos: &mut usize) -> bool {
if eat(toks, pos, "if") {
return ident(toks, pos) && block(toks, pos);
}
if !ident(toks, pos) {
return false;
}
if eat(toks, pos, "(") && !eat(toks, pos, ")") {
return false;
}
eat(toks, pos, ";")
}
fn eat(
toks: &[&str],
pos: &mut usize,
want: &str,
) -> bool {
let hit = toks.get(*pos) == Some(&want);
if hit {
*pos += 1;
}
hit
}
fn ident(toks: &[&str], pos: &mut usize) -> bool {
let hit = toks.get(*pos).is_some_and(|t| {
!matches!(
*t,
"fn" | "if" | "{" | "}" | "(" | ")" | ";"
)
});
if hit {
*pos += 1;
}
hit
}// HDD chapter, flat baseline: the same program as hdd.rs, but as the raw
// token stream a flat minimizer would really see -- keywords, braces,
// semicolons and all. The oracle now has to check that a candidate still
// *parses* before it can crash. The framework, DDMin, and ProbDD are
// byte-for-byte the same as in ddmin.rs/probdd.rs. Compiles and runs on
// its own:
//
// rustc --edition 2024 hdd_flat.rs && ./hdd_flat
use std::collections::HashMap;
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 {}
/// This chapter's atomic unit: a token of the program, identified by
/// its position in source order (0, 1, 2, ...).
type Token = u32;
/// 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())
}
}
struct ProbDD<U: AtomicUnit> {
/// `unit2prob[u]`: the belief that `u` is *essential*.
unit2prob: HashMap<U, f64>,
/// The prior for unseen units.
p0: f64,
}
impl<U: AtomicUnit> ProbDD<U> {
/// Realign the model with `config`.
fn sync(&mut self, config: &Configuration<U>) {
self.unit2prob.retain(|u, _| config.contains(u));
for &u in config {
self.unit2prob.entry(u).or_insert(self.p0);
}
}
}
/// Choose the removal set with the highest *expected gain*.
fn best_prefix<U: AtomicUnit>(
unit2prob: &HashMap<U, f64>,
) -> Vec<U> {
let mut units: Vec<U> =
unit2prob.keys().copied().collect();
// ascending by probability; ties by id for a reproducible demo.
units.sort_by(|a, b| {
unit2prob[a]
.partial_cmp(&unit2prob[b])
.unwrap()
.then(a.cmp(b))
});
let mut survive = 1.0; // ∏ (1 - p) over the current prefix
let (mut best_k, mut best_gain) = (0, 0.0);
for (i, u) in units.iter().enumerate() {
survive *= 1.0 - unit2prob[u];
// gain = k · ∏(1 - p)
let gain = (i + 1) as f64 * survive;
if gain > best_gain {
(best_k, best_gain) = (i + 1, gain);
}
}
units.truncate(best_k);
units
}
/// A removal of `pre` just failed: raise the belief of every unit in it.
fn bayes_update<U: AtomicUnit>(
unit2prob: &mut HashMap<U, f64>,
pre: &[U],
) {
let survive: f64 =
pre.iter().map(|u| 1.0 - unit2prob[u]).product();
let denom = 1.0 - survive;
if denom <= 0.0 {
return;
}
for u in pre {
let p = unit2prob[u];
unit2prob.insert(*u, (p / denom).min(1.0));
}
}
impl<U: AtomicUnit> Policy<U> for ProbDD<U> {
fn propose(
&mut self,
config: &Configuration<U>,
) -> impl Iterator<Item = Delta<U>> {
self.sync(config);
let unit2prob = &mut self.unit2prob;
// pulling the next delta means the previous one failed
let mut last: Option<Vec<U>> = None;
std::iter::from_fn(move || {
if let Some(pre) = &last {
bayes_update(unit2prob, pre);
}
// Done once every survivor is believed essential (p = 1).
if unit2prob.values().all(|&p| p >= 1.0) {
return None;
}
let pre = best_prefix(unit2prob);
if pre.is_empty() {
return None;
}
last = Some(pre.clone());
Some(pre.into_iter().collect())
})
}
}
/// The demo program as a raw token stream.
const TOKENS: &[&str] = &[
// fn bar { b1 ; if guard { g ; crash ( ) ; } b2 ; }
"fn", "bar", "{", "b1", ";", "if", "guard", "{", "g",
";", "crash", "(", ")", ";", "}", "b2", ";", "}",
// fn f2 { s ; s ; } ... fn f6 { s ; s ; }
"fn", "f2", "{", "s", ";", "s", ";", "}",
"fn", "f3", "{", "s", ";", "s", ";", "}",
"fn", "f4", "{", "s", ";", "s", ";", "}",
"fn", "f5", "{", "s", ";", "s", ";", "}",
"fn", "f6", "{", "s", ";", "s", ";", "}",
];
/// Render a configuration back into source: the surviving tokens
/// in source order.
fn render(config: &Configuration<Token>) -> String {
let mut keep: Vec<Token> =
config.iter().copied().collect();
keep.sort_unstable();
keep.iter()
.map(|&u| TOKENS[u as usize])
.collect::<Vec<_>>()
.join(" ")
}
// A recursive-descent parser for the demo language:
//
// program := fn_item*
// fn_item := "fn" IDENT "{" stmt* "}"
// stmt := "if" IDENT "{" stmt* "}"
// | IDENT "(" ")" ";"
// | IDENT ";"
fn parses(toks: &[&str]) -> bool {
let mut pos = 0;
while pos < toks.len() {
if !fn_item(toks, &mut pos) {
return false;
}
}
true
}
fn fn_item(toks: &[&str], pos: &mut usize) -> bool {
eat(toks, pos, "fn")
&& ident(toks, pos)
&& block(toks, pos)
}
fn block(toks: &[&str], pos: &mut usize) -> bool {
if !eat(toks, pos, "{") {
return false;
}
while toks.get(*pos) != Some(&"}") {
if *pos >= toks.len() || !stmt(toks, pos) {
return false;
}
}
eat(toks, pos, "}")
}
fn stmt(toks: &[&str], pos: &mut usize) -> bool {
if eat(toks, pos, "if") {
return ident(toks, pos) && block(toks, pos);
}
if !ident(toks, pos) {
return false;
}
if eat(toks, pos, "(") && !eat(toks, pos, ")") {
return false;
}
eat(toks, pos, ";")
}
fn eat(
toks: &[&str],
pos: &mut usize,
want: &str,
) -> bool {
let hit = toks.get(*pos) == Some(&want);
if hit {
*pos += 1;
}
hit
}
fn ident(toks: &[&str], pos: &mut usize) -> bool {
let hit = toks.get(*pos).is_some_and(|t| {
!matches!(
*t,
"fn" | "if" | "{" | "}" | "(" | ")" | ";"
)
});
if hit {
*pos += 1;
}
hit
}
fn main() {
// Every token of the program, punctuation included.
let all: Configuration<Token> =
(0..TOKENS.len() as Token).collect();
// The bug is the call `crash ( ) ;` — four consecutive tokens.
let crash: Token = TOKENS
.iter()
.position(|&t| t == "crash")
.unwrap() as Token;
let crash_call = crash..crash + 4;
for (name, run) in
[("Flat DDMin", 0u8), ("Flat ProbDD", 1u8)]
{
println!("\n================== {name} ==================");
let calls =
std::rc::Rc::new(std::cell::Cell::new(0u32));
let parse_errors =
std::rc::Rc::new(std::cell::Cell::new(0u32));
let (counter, errors) =
(calls.clone(), parse_errors.clone());
let crash_call2 = crash_call.clone();
// Interesting iff the candidate still *parses* and the
// crash() call survives whole. A flat minimizer knows
// nothing about syntax, so it must discover both by test.
let oracle = move |c: &Configuration<Token>| {
counter.set(counter.get() + 1);
let keep: Vec<&str> = {
let mut ks: Vec<Token> =
c.iter().copied().collect();
ks.sort_unstable();
ks.iter()
.map(|&u| TOKENS[u as usize])
.collect()
};
let (verdict, mark) = if !parses(&keep) {
errors.set(errors.get() + 1);
(Verdict::NotInteresting, "doesn't parse (reject)")
} else if crash_call2
.clone()
.all(|u| c.contains(&u))
{
(Verdict::Interesting, "crashes (keep)")
} else {
(Verdict::NotInteresting, "ok (reject)")
};
println!(" test \"{}\" -> {mark}", keep.join(" "));
verdict
};
let result = if run == 0 {
reduce(all.clone(), &oracle, DDMin)
} else {
reduce(
all.clone(),
&oracle,
ProbDD {
unit2prob: HashMap::new(),
p0: 0.1,
},
)
};
println!(
" => minimized to \"{}\" in {} oracle calls ({} wasted on parse errors)",
render(&result),
calls.get(),
parse_errors.get()
);
assert!(crash_call.clone().all(|u| result.contains(&u)));
assert_eq!(calls.get(), if run == 0 { 253 } else { 80 });
assert_eq!(
parse_errors.get(),
if run == 0 { 249 } else { 68 }
);
}
// The flat optimum: strip the `if guard { ... }` wrapper (tokens 5-7
// and the matching `}` at 14). Neither policy above found it.
let optimum: Configuration<Token> =
[0, 1, 2, 10, 11, 12, 13, 17].into_iter().collect();
let keep: Vec<&str> = {
let mut ks: Vec<Token> =
optimum.iter().copied().collect();
ks.sort_unstable();
ks.iter().map(|&u| TOKENS[u as usize]).collect()
};
assert!(parses(&keep));
assert!(crash_call.clone().all(|u| optimum.contains(&u)));
println!(
"\nnote: the flat optimum \"{}\" parses and crashes,\n\
but neither policy found it",
render(&optimum)
);
}Note
Flat DDMin: 253 calls, 249 of them rejected as parse errors (HDD + DDMin: 11, parse errors impossible). Flat ProbDD: 80 calls, 68 parse errors (HDD + ProbDD: 15).
And the wasted calls didn’t even buy a clean result: chunk boundaries that ignore syntax leave junk like
fn f3 { s ; }(DDMin) or empty functions (ProbDD) that no single token removal can shrink further.
This is the tree’s real payoff. It groups tokens into units worth removing together, and it makes every candidate valid by construction—a flat minimizer must rediscover both, one rejected oracle call at a time.
On Minimality
DDMin on a flat list guarantees 1-minimality: no single unit can be removed. HDD inherits a weaker, tree-shaped cousin. Because it walks top-down and never revisits a level, it guarantees only that no single subtree can be removed given the levels above it—1-tree-minimality. A subtree high in the tree might have become removable only after something below it was cut, and plain HDD won’t go back to find out.
The flat baseline above shows both sides of that trade. Token deltas can
do what subtree deltas can’t: the flat optimum fn bar { crash ( ) ; }
strips the if guard { ... } wrapper, which is no subtree—HDD can never
reach it. (The demo’s last lines verify it parses and crashes.) Yet
neither flat policy found it; both stalled on junk larger than HDD’s
answer, because 1-minimality only rules out single-token removals:
DDMin’s contiguous chunks never align with the wrapper’s scattered
tokens, and ProbDD pinned whole groups “essential” without testing them
alone. The freedom of token space is real—blind search can’t spend it.
Variants like HDD+ and HDD* iterate to close the tree-side gap; Perses attacks it with the grammar.