Keyboard shortcuts

Press ← or → to navigate between chapters

Press S or / to search in the book

Press ? to show this help

Press Esc to hide this help

Perses

HDD reduces a tree by deleting whole subtrees, which can be an entire function. That clears noise, but deleting a subtree can’t free a bug from what’s nested around it. Take a bug buried in nested ifs:

int main() { if (c1) { if (c2) { if (c3) { crash(); } } } }

To delete an if is to delete crash() with it; whole-subtree deletion is all HDD has. So it’s stuck.

Perses adds one move: node replacement. main’s body is a block, and so is the innermost block wrapping crash(), so Perses deletes everything in between and promotes the inner block into its place: { if (c1) { ... { crash(); } ... } } becomes { crash(); }. It’s still deletion, just of the surrounding wrapper.

A Parse Tree, by Hand

Here is the toy grammar—just enough for nested ifs and statement lists:

func    ::= "int" "main" "(" ")" block
block   ::= "{" stmt* "}"
stmt    ::= if_stmt | block | call
if_stmt ::= "if" "(" expr ")" block
call    ::= ident "(" ")" ";"
expr    ::= ident

We model the input as a parse tree: every token is a leaf, every internal node carries a kind, and concatenating the surviving tokens is the program.

The two-space discipline from HDD carries over unchanged: the atomic units are the tokens, numbered 0..n in source order, and the configuration is a set of unit indices. Internal nodes are NodeIds—names for regions of the program—and never sit in the configuration. Rendering is now trivial: sort the surviving units ascending and print their labels; for a parse tree, that is the program.

/// A node's grammar kind. `Token` is a terminal leaf; `List` is a Kleene node
/// (zero-or-more, so its children are deletable); the rest are non-terminals.
#[derive(Clone, Copy, PartialEq, Eq)]
enum Kind {
    Token, // a terminal: "if", "(", "{", "crash", ";", ...

    List, // a Kleene list of statements (its children are removable)

    Expr, // a condition
    Func, // the function definition (root)

    IfStmt, // if ( cond ) block       ┐
    Block, // { stmt-list }            │- these three are statements
    Call,  // name ( ) ;               ┘
}

fn is_stmt(kind: Kind) -> bool {
    matches!(kind, Kind::IfStmt | Kind::Block | Kind::Call)
}

/// 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 {
    kind: Kind,
    label: &'static str, // the source text, for a `Token` leaf
    children: Vec<NodeId>,
}

struct Tree {
    id2node: HashMap<NodeId, Node>,
    root: NodeId,
    node2depth: HashMap<NodeId, usize>,
    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`
}

Note

The root of HDD’s trouble is its AST: the if ( ) wrapper isn’t separate nodes at all—there is nothing there to delete.

A parse tree or concrete syntax tree (CST) makes each token a node, which is what node replacement carves away.

What HDD May Delete

The freedom of a parse tree cuts both ways: now that mandatory tokens are leaves too, a careless reducer could drop the if in if (cond) { } and leave a dangling ( ), or drop a { but keep its }.

To keep the baseline faithful to the original HDD—which uses an AST and thus only ever drops what the grammar marks optional—we mark every node unremovable except a List element (because a Kleene stmt* may legally hold fewer statements):

    /// A node may be deleted only when it is an element of a `List` (Kleene).
    fn deletable(&self, id: NodeId) -> bool {
        self.node2parent.get(&id).is_some_and(|p| {
            self.id2node[p].kind == Kind::List
        })
    }

HDD consults it where it gathers each level’s deletion candidates:

    /// The level-`level` subtrees still holding a token -- the candidates HDD
    /// may delete at this level. Each surviving unit's leaf contributes its
    /// level-`L` ancestor; we keep only the `deletable` ones.
    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))
            .filter(|&node| self.deletable(node))
            .collect()
    }

Now, the if (cond) { } wrapper is not a removable subtree, so HDD has no deletion that drops it and keeps the body.

Note

We will try to allow HDD to delete any node, not just List elements. Please see the last section, “Delete Anything?”, for that experiment.

Tracking Node Existence

Before we can build the replacement move, we need an ability the configuration doesn’t give us directly. The configuration records only which tokens survive; it never says whether an internal node still exists. Yet Perses constantly asks exactly that—replacement only makes sense between nodes that still exist. So the first ingredient is recovering internal-node existence from the token set.

To see why this is subtle, watch what the promotion from the intro does to the tree. Take this program:

int main() {
   if (c) {
      crash();
   }
}

whose parse tree is:

func
 ├─ "int"
 ├─ "main"
 ├─ "("
 ├─ ")"
 └─ block                   <- n: the node we replace
    ├─ "{"
    ├─ stmt*
    │  └─ if_stmt
    │     ├─ "if"
    │     ├─ "("
    │     ├─ expr
    │     │  └─ "c"
    │     ├─ ")"
    │     └─ block          <- d: kept, promoted into n's place
    │        ├─ "{"
    │        ├─ stmt*
    │        │  └─ call
    │        │     ├─ "crash"
    │        │     ├─ "("
    │        │     ├─ ")"
    │        │     └─ ";"
    │        └─ "}"
    └─ "}"

Replacing the outer block (n) with the inner one (d) promotes crash(); into main’s body:

int main() {
   crash();
}

so the parse tree should become:

func
 ├─ "int"
 ├─ "main"
 ├─ "("
 ├─ ")"
 └─ block
    ├─ "{"
    ├─ stmt*
    │  └─ call
    │     ├─ "crash"
    │     ├─ "("
    │     ├─ ")"
    │     └─ ";"
    └─ "}"

But the tree in our implementation is fixed—we only drop units from the configuration. So structurally it is unchanged, with X marking a dropped token and ? an internal node that should be gone yet still sits there:

func
 ├─ "int"
 ├─ "main"
 ├─ "("
 ├─ ")"
 └─ block             <- ?
    ├─ "{"            <- X
    ├─ stmt*          <- ?
    │  └─ if_stmt     <- ?
    │     ├─ "if"     <- X
    │     ├─ "("      <- X
    │     ├─ expr     <- ?
    │     │  └─ "c"   <- X
    │     ├─ ")"      <- X
    │     └─ block
    │        ├─ "{"
    │        ├─ stmt*
    │        │  └─ call
    │        │     ├─ "crash"
    │        │     ├─ "("
    │        │     ├─ ")"
    │        │     └─ ";"
    │        └─ "}"
    └─ "}"            <- X

A token’s presence is a single config lookup; an internal node’s is not. We have to recover it—decide that the ? nodes are gone even though the tree still holds them. Three rules, one per kind, do it:

  • a token (leaf) exists iff the configuration still holds its unit;
  • a regular node (Block, IfStmt, Call, …) exists iff all its mandatory parts do—every non-List child (an if stops existing the moment any of if ( … ) or its block is gone);
  • a list (stmt*) has no tokens of its own and may legally be empty, so it cannot be judged by its own contents; it exists iff the block bracketing it does—its parent.

A node that still exists is live:

    /// Does this node still exist in the reduced program?
    fn live(
        &self,
        id: NodeId,
        config: &Configuration<Token>,
    ) -> bool {
        let node = &self.id2node[&id];
        match node.kind {
            Kind::Token => {
                config.contains(&self.leaf2token[&id])
            }
            // no tokens of its own: defer to the parent block
            Kind::List => self
                .node2parent
                .get(&id)
                .is_some_and(|&p| self.live(p, config)),
            // all mandatory (non-List) children
            _ => node
                .children
                .iter()
                .filter(|&&c| {
                    self.id2node[&c].kind != Kind::List
                })
                .all(|&c| self.live(c, config)),
        }
    }

live asks whether a node still fills its grammar slot. Some of the machinery below needs only a weaker question—does any token under the node survive?—answered by present:

    /// Does any token under `id` survive?
    fn present(
        &self,
        id: NodeId,
        config: &Configuration<Token>,
    ) -> bool {
        !self.leaves_under(id, config).is_empty()
    }

The two disagree exactly on the ? nodes above: the promoted block’s tokens still sit under them, so every ? node is present, yet none of them is live.

Node Replacement

With liveness in hand we can build the move itself. It has three parts: what a replacement removes, which slot the replaced node occupies, and which descendants fit that slot.

The Move and Its Delta

Perses replaces a node n with one of its descendants d: d is kept, everything else under n goes. Since the configuration is a set of units, the delta is just the tokens under n minus the tokens under d—the surrounding wrapper:

let delta = leaves_under(n) - leaves_under(d);

In the promotion above, n is main’s body and d the inner block: the delta is {, if, (, c, ), }—six wrapper tokens—and one oracle test later the whole nest is gone.

Which Slot Is n Filling?

Replacement must keep the program grammatical, so before asking whether d fits, we must know which grammar slot it would be filling. The obvious answer—the slot of n’s parent’s child, i.e. n’s own position—is wrong as soon as replacements start stacking, because n’s own parent may already be dead.

Watch it happen in the demo run. After the promotion above, the live inner block hangs below a chain of ? nodes:

func                          (root, live)
 ├─ "int" "main" "(" ")"
 └─ block          <- dead    ┐
    └─ stmt*       <- dead    │ the dead chain
       └─ if_stmt  <- dead    │ anchor_of climbs
          └─ ...   <- dead    ┘
             └─ block         <- live: the promoted { crash(); }

If Perses later wants to replace that promoted block, judging it by its literal parent (a dead if_stmt) would conclude “a block in an if_stmt slot”—but that if_stmt no longer exists. The block was promoted into main’s body slot, and that is the slot any further replacement must keep filling. anchor_of recovers this: climb from n up the dead chain to the first node whose own parent is live (or the root). That ancestor’s slot is the one n effectively occupies:

    /// The node whose grammar slot `n` is *effectively* filling: the top
    /// of the dead chain `n` was promoted through.
    fn anchor_of(
        &self,
        n: NodeId,
        config: &Configuration<Token>,
    ) -> NodeId {
        let mut anchor = n;
        while let Some(&p) = self.node2parent.get(&anchor) {
            if p == self.root || self.live(p, config) {
                break;
            }
            anchor = p;
        }
        anchor
    }

Tracing it on the picture: start at the promoted block; its parent if_stmt is dead, keep climbing; stmt*, dead; the outer block’s parent is func, the live root—stop. The anchor is the outer block, whose slot (func’s mandatory body) demands a Block.

Is d Compatible?

Now the compatibility test is two rules over the anchor’s slot, read straight from the grammar:

  • if the anchor is a List element, the slot is stmt—any statement kind (IfStmt, Block, Call) fits;
  • if the anchor is a fixed child (like func’s body), the slot admits exactly one kind—d must match it (a Block slot accepts only a Block).
    /// Can `d` replace `n`? Its kind must fit the slot `n` is
    /// effectively filling.
    fn can_replace(
        &self,
        n: NodeId,
        d: NodeId,
        config: &Configuration<Token>,
    ) -> bool {
        if n == d {
            return false;
        }
        let anchor = self.anchor_of(n, config);
        let d_kind = self.id2node[&d].kind;
        match self.node2parent.get(&anchor) {
            Some(p) if self.id2node[p].kind == Kind::List => {
                is_stmt(d_kind)
            }
            Some(_) => d_kind == self.id2node[&anchor].kind,
            None => false, // the root fills no slot
        }
    }

The Perses Policy

Like HDD, Perses is still a Policy: the same reduce loop drives it, and all its strategy lives behind propose/on_reduced. Its state is the tree, one active List with a persisted deletion minimizer (the same trick HDD uses per level), and a bookkeeping set done:

/// Perses is a Policy. Largest node first, it proposes **node
/// replacement** (drop everything under `n` except a compatible
/// descendant `d`'s tokens) plus, for `List` nodes, HDD's
/// deletion.
struct Perses<'t, F, P> {
    tree: &'t Tree,
    new_minimizer: F,
    // the active `List` node
    active: Option<NodeId>,
    // the active node's minimizer, rebuilt when `active` changes
    minimizer: Option<P>,
    // the active node's present elements, in a field so the
    // returned iterator can borrow them (as HDD does per level)
    active_elems: Configuration<NodeId>,
    // `List`s whose minimizer found nothing more to delete;
    // cleared whenever any reduction succeeds
    done: HashSet<NodeId>,
}

We build propose out of four small pieces, each answering one question.

Largest First

Which node should we spend the next test on? HDD answered “whatever the current level holds”; Perses answers “whatever pays the most”. A node’s payoff is the number of surviving tokens under it, so each pass recomputes subtree sizes and orders the live internal nodes largest first:

    /// Surviving tokens under each node.
    fn subtree_sizes(
        &self,
        config: &Configuration<Token>,
    ) -> HashMap<NodeId, usize> {
        self.id2node
            .keys()
            .map(|&id| {
                (id, self.leaves_under(id, config).len())
            })
            .collect()
    }
    /// The live internal nodes, largest subtree first (ties by id for a
    /// reproducible demo).
    fn live_internal_largest_first(
        &self,
        config: &Configuration<Token>,
        node2size: &HashMap<NodeId, usize>,
    ) -> Vec<NodeId> {
        let mut nodes: Vec<NodeId> = self
            .id2node
            .keys()
            .copied()
            .filter(|&id| {
                !self.id2node[&id].children.is_empty()
                    && self.live(id, config)
            })
            .collect();
        nodes.sort_by(|&a, &b| {
            node2size[&b]
                .cmp(&node2size[&a])
                .then(a.cmp(&b))
        });
        nodes
    }

From here on we trace the chapter’s running demo: the nested-if program from the top, with a noise(); call added at every level. Each call is 4 tokens (noise ( ) ;), each if (cN) header is 4, each brace pair 2, and the int main ( ) header 4—48 tokens in all:

int main() {
   if (c1) {
      if (c2) {
         if (c3) { crash(); noise(); }
         noise();
      }
      noise();
   }
   noise(); noise();
}

On its first pass the ordering starts:

live nodeits surviving tokenscount
func (root)the whole program48
block (main’s body){ if (c1) {...} noise(); noise(); }44
stmt* (outermost list)the same, minus its { }42
if_stmt (if (c1) ...)if (c1) { if (c2) {...} noise(); }34
block (if (c1)’s body){ if (c2) {...} noise(); }30
⋮⋮⋮

Generating Replacements

What is the best replacement to try at each node? For a node n, the smallest compatible descendant d removes the most—so candidates are emitted per node largest-n-first, and within a node smallest-d-first: the biggest jump that still parses comes out of the iterator before the cautious ones. The pool of candidate ds comes from descendants:

    /// Every present proper descendant of `id`.
    fn descendants(
        &self,
        id: NodeId,
        config: &Configuration<Token>,
    ) -> Vec<NodeId> {
        let mut out = Vec::new();
        let mut stack: Vec<NodeId> = self.id2node[&id]
            .children
            .iter()
            .copied()
            .collect();
        while let Some(n) = stack.pop() {
            if !self.present(n, config) {
                continue;
            }
            out.push(n);
            stack.extend(
                self.id2node[&n].children.iter().copied(),
            );
        }
        out
    }
    /// Replacement candidates. The delta is the wrapper: `n`'s tokens
    /// minus `d`'s.
    fn replacements(
        &self,
        nodes: &[NodeId],
        node2size: &HashMap<NodeId, usize>,
        config: &Configuration<Token>,
    ) -> Vec<Delta<Token>> {
        let tree = self.tree;
        let mut reps: Vec<Delta<Token>> = Vec::new();
        for &n in nodes {
            let n_leaves = tree.leaves_under(n, config);
            let mut ds: Vec<NodeId> = tree
                .descendants(n, config)
                .into_iter()
                .filter(|&d| {
                    tree.live(d, config)
                        && tree.can_replace(n, d, config)
                })
                .collect();
            ds.sort_by(|&a, &b| {
                node2size[&a]
                    .cmp(&node2size[&b])
                    .then(a.cmp(&b))
            });
            for d in ds {
                let delta: Delta<Token> = n_leaves
                    .difference(
                        &tree.leaves_under(d, config),
                    )
                    .copied()
                    .collect();
                if !delta.is_empty() {
                    reps.push(delta);
                }
            }
        }
        reps
    }

Trace it on main’s body (n), the 44-token block:

{ if (c1) { if (c2) { if (c3) { crash(); noise(); } noise(); } noise(); } noise(); noise(); }

Its compatible live descendants are the three nested if bodies, tried smallest first, so the innermost one comes out first as d, 10 tokens:

{ crash(); noise(); }

The delta is everything in n but not in d—the 34-token wrapper. On the demo that very first candidate is accepted, collapsing all three ifs in one test.

One Active List at a Time

Where does deletion happen? Deletion needs a stateful minimizer driven across passes (that is how DDMin escalates granularity and how ProbDD learns), and state needs a home. Perses keeps one persisted minimizer at a time, attached to the active List. The active list changes in only two cases: its minimizer declares it minimal (the list joins done), or a replacement elsewhere deletes the list’s last surviving tokens (the list stops being live). Either way, the next pass picks the largest live list not in done:

    /// Pick the *active* `List`: the first one in `nodes` not in `done`
    /// (`nodes` is sorted largest-first, so this is the largest such
    /// list). Once picked, stick with it---switching away mid-run would
    /// discard what the inner policy has learned about it.
    fn pick_active(&mut self, nodes: &[NodeId]) {
        let tree = self.tree;
        if let Some(a) = self.active {
            if !self.done.contains(&a)
                && nodes.contains(&a)
            {
                return; // still minimizing the current list
            }
        }
        let active = nodes.iter().copied().find(|&id| {
            tree.id2node[&id].kind == Kind::List
                && !self.done.contains(&id)
        });
        if active != self.active {
            self.active = active;
            self.minimizer = None;
        }
    }

The active list’s deletions are generated exactly as HDD generates a level’s: hand the minimizer the list’s elements, gathered by elems_of, stream its choices lazily, and map each through leaves_under into a unit-delta:

    /// The still-present elements (children) of a `List` node -- the
    /// things a deletion minimizer may remove from it.
    fn elems_of(
        &self,
        list: NodeId,
        config: &Configuration<Token>,
    ) -> Configuration<NodeId> {
        // `pick_active` only ever selects `List` nodes
        assert!(self.id2node[&list].kind == Kind::List);
        self.id2node[&list]
            .children
            .iter()
            .copied()
            .filter(|&c| self.present(c, config))
            .collect()
    }

The assert holds because elems_of is only ever called on the active list, and pick_active filters for Kind::List when choosing it.

    /// Deletion candidates from the active `List`. Its present elements
    /// go in a field so the returned iterator can borrow them.
    fn deletions(
        &mut self,
        config: &Configuration<Token>,
    ) -> impl Iterator<Item = Delta<Token>> {
        let tree = self.tree;
        self.active_elems = match self.active {
            Some(a) => tree.elems_of(a, config),
            None => Configuration::new(),
        };
        if self.minimizer.is_none() {
            self.minimizer = Some((self.new_minimizer)());
        }
        let elems = &self.active_elems;
        let minimizer = self.minimizer.as_mut().unwrap();
        minimizer.propose(elems).map(
            move |drop| -> Delta<Token> {
                // dropping a subtree drops the tokens under it
                drop.iter()
                    .flat_map(|&id| {
                        tree.leaves_under(id, config)
                    })
                    .collect()
            },
        )
    }

Assembled, propose is the four questions in order:

    fn propose(
        &mut self,
        config: &Configuration<Token>,
    ) -> impl Iterator<Item = Delta<Token>> {
        // biggest payoff first: order the live nodes by surviving size
        let node2size = self.tree.subtree_sizes(config);
        let nodes = self
            .tree
            .live_internal_largest_first(config, &node2size);
        // one List at a time gets a persisted deletion minimizer
        self.pick_active(&nodes);
        // replacements first, then the active List's deletions
        let reps =
            self.replacements(&nodes, &node2size, config);
        reps.into_iter().chain(self.deletions(config))
    }

Warning

Real Perses bounds the descendant search and can splice a nested list into its parent. We keep the descendant search simple and skip the splice—the collapse here is pure statement-for-statement replacement.

Finishing a List

When is a list finished—and when is the whole run? on_reduced closes the loop: it forwards each pass’s outcome to the active minimizer in its own space—the list’s still-present elements—and updates done:

    fn on_reduced(
        &mut self,
        reduced: Option<&Configuration<Token>>,
    ) -> bool {
        let tree = self.tree;
        match self.active {
            Some(a) => {
                // the outcome, in the minimizer's space
                let elems =
                    reduced.map(|c| tree.elems_of(a, c));
                let inner =
                    self.minimizer.as_mut().unwrap();
                let keep = inner.on_reduced(elems.as_ref());
                if reduced.is_some() {
                    // reconsider every `List`
                    self.done.clear();
                    true
                } else if keep {
                    true // the inner policy isn't minimal yet
                } else {
                    // nothing more to delete here: mark the list
                    // done and move on. Once every list is done,
                    // `active` is None and the next all-failing
                    // pass ends the run.
                    self.done.insert(a);
                    true
                }
            }
            None => reduced.is_some(), // replacements-only pass
        }
    }

Why does a success clear done? A deletion that failed once is not doomed forever: the oracle judges the whole surviving program, so shrinking it elsewhere can flip the verdict. Suppose int y = 0; sits in one list and its only use y++; in another. Deleting the declaration fails while the use survives—the program no longer compiles, so it cannot crash. The moment a collapse elsewhere removes y++;, the declaration is free to go. A done mark is only valid for the program it was measured on, and every reduction changes that program.

Here is the protocol at work on the demo run, pass by pass:

passactive listfirst accepted candidateoutcomedone after
1outermost stmt*replace main’s body with innermost blockreduced∅ (re-opened)
2innermost stmt*delete noise(); (keep only crash();)reduced∅ (re-opened)
3innermost stmt*none—deleting crash(); is rejectedno progress{ innermost stmt* }
4none leftno candidatesstop

Run It

Time to compare HDD and Perses head to head. The input is the running demo program, repeated here:

int main() {
   if (c1) {
      if (c2) {
         if (c3) { crash(); noise(); }
         noise();
      }
      noise();
   }
   noise(); noise();
}

Both run against the same oracle:

    // Interesting iff the program still contains crash() *and* still parses. The
    // returned counter tallies how many candidates each reducer tries.
    let make_oracle = || {
        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 src = render(&otree, c);
            let ok = c.contains(&crash) && parses(&src);
            println!(
                "  test {src:?}  ->  {}",
                if ok {
                    "crashes (keep)"
                } else {
                    "reject"
                }
            );
            if ok {
                Verdict::Interesting
            } else {
                Verdict::NotInteresting
            }
        };
        (oracle, calls)
    };

The reducers are HDD, which deletes removable elements, and Perses, which also deletes a wrapper to promote what’s inside (node replacement).

Tip

Press play. HDD strips the noise; lines but can’t break the if nesting; Perses replaces main’s body with the inner block in one test, then clears the leftover noise.

// Perses: syntax-guided reduction. Its new move is *node replacement* -- delete a
// node's surrounding wrapper to promote a compatible descendant (a block nested
// inside another block is still a block, so `{ ... { body } ... }` becomes
// `{ body }`). Runs on its own:
//
//     rustc --edition 2024 perses.rs && ./perses

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 - &delta;
            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();
    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;

impl<U: AtomicUnit> Policy<U> for DDMin {
    fn propose(
        &mut self,
        config: &Configuration<U>,
    ) -> impl Iterator<Item = Delta<U>> {
        let units = config.len();
        successors(Some(2), move |&n| {
            (n < units).then(|| (2 * n).min(units))
        })
        .flat_map(move |n| {
            let subsets = partition(config, n);
            let keep_only = subsets
                .clone()
                .into_iter()
                .map(move |d| config - &d);
            keep_only.chain(subsets)
        })
        .filter(|delta| !delta.is_empty())
    }
}

/// A node's grammar kind. `Token` is a terminal leaf; `List` is a Kleene node
/// (zero-or-more, so its children are deletable); the rest are non-terminals.
#[derive(Clone, Copy, PartialEq, Eq)]
enum Kind {
    Token, // a terminal: "if", "(", "{", "crash", ";", ...

    List, // a Kleene list of statements (its children are removable)

    Expr, // a condition
    Func, // the function definition (root)

    IfStmt, // if ( cond ) block       ┐
    Block, // { stmt-list }            │- these three are statements
    Call,  // name ( ) ;               ┘
}

fn is_stmt(kind: Kind) -> bool {
    matches!(kind, Kind::IfStmt | Kind::Block | Kind::Call)
}

/// 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 {
    kind: Kind,
    label: &'static str, // the source text, for a `Token` leaf
    children: Vec<NodeId>,
}

struct Tree {
    id2node: HashMap<NodeId, Node>,
    root: NodeId,
    node2depth: HashMap<NodeId, usize>,
    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 {
        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` (for a leaf, its own token if kept).
    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
    }


    /// Does any token under `id` survive?
    fn present(
        &self,
        id: NodeId,
        config: &Configuration<Token>,
    ) -> bool {
        !self.leaves_under(id, config).is_empty()
    }

    /// Every present proper descendant of `id`.
    fn descendants(
        &self,
        id: NodeId,
        config: &Configuration<Token>,
    ) -> Vec<NodeId> {
        let mut out = Vec::new();
        let mut stack: Vec<NodeId> = self.id2node[&id]
            .children
            .iter()
            .copied()
            .collect();
        while let Some(n) = stack.pop() {
            if !self.present(n, config) {
                continue;
            }
            out.push(n);
            stack.extend(
                self.id2node[&n].children.iter().copied(),
            );
        }
        out
    }

    /// The level-`level` subtrees still holding a token -- the candidates HDD
    /// may delete at this level. Each surviving unit's leaf contributes its
    /// level-`L` ancestor; we keep only the `deletable` ones.
    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))
            .filter(|&node| self.deletable(node))
            .collect()
    }

    /// A node may be deleted only when it is an element of a `List` (Kleene).
    fn deletable(&self, id: NodeId) -> bool {
        self.node2parent.get(&id).is_some_and(|p| {
            self.id2node[p].kind == Kind::List
        })
    }

    fn ancestor_at(
        &self,
        mut id: NodeId,
        level: usize,
    ) -> NodeId {
        while self.node2depth[&id] > level {
            id = self.node2parent[&id];
        }
        id
    }


    /// Does this node still exist in the reduced program?
    fn live(
        &self,
        id: NodeId,
        config: &Configuration<Token>,
    ) -> bool {
        let node = &self.id2node[&id];
        match node.kind {
            Kind::Token => {
                config.contains(&self.leaf2token[&id])
            }
            // no tokens of its own: defer to the parent block
            Kind::List => self
                .node2parent
                .get(&id)
                .is_some_and(|&p| self.live(p, config)),
            // all mandatory (non-List) children
            _ => node
                .children
                .iter()
                .filter(|&&c| {
                    self.id2node[&c].kind != Kind::List
                })
                .all(|&c| self.live(c, config)),
        }
    }

    /// The node whose grammar slot `n` is *effectively* filling: the top
    /// of the dead chain `n` was promoted through.
    fn anchor_of(
        &self,
        n: NodeId,
        config: &Configuration<Token>,
    ) -> NodeId {
        let mut anchor = n;
        while let Some(&p) = self.node2parent.get(&anchor) {
            if p == self.root || self.live(p, config) {
                break;
            }
            anchor = p;
        }
        anchor
    }

    /// Can `d` replace `n`? Its kind must fit the slot `n` is
    /// effectively filling.
    fn can_replace(
        &self,
        n: NodeId,
        d: NodeId,
        config: &Configuration<Token>,
    ) -> bool {
        if n == d {
            return false;
        }
        let anchor = self.anchor_of(n, config);
        let d_kind = self.id2node[&d].kind;
        match self.node2parent.get(&anchor) {
            Some(p) if self.id2node[p].kind == Kind::List => {
                is_stmt(d_kind)
            }
            Some(_) => d_kind == self.id2node[&anchor].kind,
            None => false, // the root fills no slot
        }
    }

    /// Surviving tokens under each node.
    fn subtree_sizes(
        &self,
        config: &Configuration<Token>,
    ) -> HashMap<NodeId, usize> {
        self.id2node
            .keys()
            .map(|&id| {
                (id, self.leaves_under(id, config).len())
            })
            .collect()
    }

    /// The live internal nodes, largest subtree first (ties by id for a
    /// reproducible demo).
    fn live_internal_largest_first(
        &self,
        config: &Configuration<Token>,
        node2size: &HashMap<NodeId, usize>,
    ) -> Vec<NodeId> {
        let mut nodes: Vec<NodeId> = self
            .id2node
            .keys()
            .copied()
            .filter(|&id| {
                !self.id2node[&id].children.is_empty()
                    && self.live(id, config)
            })
            .collect();
        nodes.sort_by(|&a, &b| {
            node2size[&b]
                .cmp(&node2size[&a])
                .then(a.cmp(&b))
        });
        nodes
    }

    /// The still-present elements (children) of a `List` node -- the
    /// things a deletion minimizer may remove from it.
    fn elems_of(
        &self,
        list: NodeId,
        config: &Configuration<Token>,
    ) -> Configuration<NodeId> {
        // `pick_active` only ever selects `List` nodes
        assert!(self.id2node[&list].kind == Kind::List);
        self.id2node[&list]
            .children
            .iter()
            .copied()
            .filter(|&c| self.present(c, config))
            .collect()
    }
}

/// Render a configuration by concatenating the surviving tokens in source
/// order -- for a parse tree, that *is* the program. Because a unit is its
/// token's source-order index, "in source order" is just ascending units.
fn render(tree: &Tree, present: &Configuration<Token>) -> String {
    let mut units: Vec<Token> =
        present.iter().copied().collect();
    units.sort_unstable();
    units
        .iter()
        .map(|&u| {
            tree.id2node[&tree.token2leaf[&u]].label
        })
        .collect::<Vec<_>>()
        .join(" ")
}

/// HDD walks the tree level by level and lets a fresh list-minimizer drop the
/// level's *deletable* nodes. Pure deletion -- the baseline.
struct Hdd<'t, F, P> {
    tree: &'t Tree,
    new_minimizer: F,
    level: usize,
    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(),
        }
    }
}

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. `on_reduced` clears it
        // only when we descend a level, so a stateful inner policy (ProbDD) keeps
        // learning across a level's passes and is reset only at a level boundary.
        if self.minimizer.is_none() {
            self.minimizer = Some((self.new_minimizer)());
        }
        self.level_subtrees =
            tree.alive_level_nodes(level, config);
        let subtrees = &self.level_subtrees;
        let minimizer = self.minimizer.as_mut().unwrap();
        // Lazily: `reduce` stops pulling at the first success, so a stateful
        // inner policy only ever advances its model over *confirmed* failures.
        minimizer.propose(subtrees).map(
            move |drop| -> Delta<Token> {
                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);
        // Report the pass outcome to the inner minimizer
        // in its own space: this level's still-live
        // subtrees, or `None` when nothing was found.
        // Driving the inner policy through its full
        // protocol keeps HDD agnostic to the inner policy.
        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
    }
}

/// Perses is a Policy. Largest node first, it proposes **node
/// replacement** (drop everything under `n` except a compatible
/// descendant `d`'s tokens) plus, for `List` nodes, HDD's
/// deletion.
struct Perses<'t, F, P> {
    tree: &'t Tree,
    new_minimizer: F,
    // the active `List` node
    active: Option<NodeId>,
    // the active node's minimizer, rebuilt when `active` changes
    minimizer: Option<P>,
    // the active node's present elements, in a field so the
    // returned iterator can borrow them (as HDD does per level)
    active_elems: Configuration<NodeId>,
    // `List`s whose minimizer found nothing more to delete;
    // cleared whenever any reduction succeeds
    done: HashSet<NodeId>,
}

impl<'t, F, P> Perses<'t, F, P>
where
    F: Fn() -> P,
    P: Policy<NodeId>,
{
    fn new(tree: &'t Tree, new_minimizer: F) -> Self {
        Perses {
            tree,
            new_minimizer,
            active: None,
            minimizer: None,
            active_elems: Configuration::new(),
            done: HashSet::new(),
        }
    }

    /// Pick the *active* `List`: the first one in `nodes` not in `done`
    /// (`nodes` is sorted largest-first, so this is the largest such
    /// list). Once picked, stick with it---switching away mid-run would
    /// discard what the inner policy has learned about it.
    fn pick_active(&mut self, nodes: &[NodeId]) {
        let tree = self.tree;
        if let Some(a) = self.active {
            if !self.done.contains(&a)
                && nodes.contains(&a)
            {
                return; // still minimizing the current list
            }
        }
        let active = nodes.iter().copied().find(|&id| {
            tree.id2node[&id].kind == Kind::List
                && !self.done.contains(&id)
        });
        if active != self.active {
            self.active = active;
            self.minimizer = None;
        }
    }

    /// Replacement candidates. The delta is the wrapper: `n`'s tokens
    /// minus `d`'s.
    fn replacements(
        &self,
        nodes: &[NodeId],
        node2size: &HashMap<NodeId, usize>,
        config: &Configuration<Token>,
    ) -> Vec<Delta<Token>> {
        let tree = self.tree;
        let mut reps: Vec<Delta<Token>> = Vec::new();
        for &n in nodes {
            let n_leaves = tree.leaves_under(n, config);
            let mut ds: Vec<NodeId> = tree
                .descendants(n, config)
                .into_iter()
                .filter(|&d| {
                    tree.live(d, config)
                        && tree.can_replace(n, d, config)
                })
                .collect();
            ds.sort_by(|&a, &b| {
                node2size[&a]
                    .cmp(&node2size[&b])
                    .then(a.cmp(&b))
            });
            for d in ds {
                let delta: Delta<Token> = n_leaves
                    .difference(
                        &tree.leaves_under(d, config),
                    )
                    .copied()
                    .collect();
                if !delta.is_empty() {
                    reps.push(delta);
                }
            }
        }
        reps
    }

    /// Deletion candidates from the active `List`. Its present elements
    /// go in a field so the returned iterator can borrow them.
    fn deletions(
        &mut self,
        config: &Configuration<Token>,
    ) -> impl Iterator<Item = Delta<Token>> {
        let tree = self.tree;
        self.active_elems = match self.active {
            Some(a) => tree.elems_of(a, config),
            None => Configuration::new(),
        };
        if self.minimizer.is_none() {
            self.minimizer = Some((self.new_minimizer)());
        }
        let elems = &self.active_elems;
        let minimizer = self.minimizer.as_mut().unwrap();
        minimizer.propose(elems).map(
            move |drop| -> Delta<Token> {
                // dropping a subtree drops the tokens under it
                drop.iter()
                    .flat_map(|&id| {
                        tree.leaves_under(id, config)
                    })
                    .collect()
            },
        )
    }
}

impl<'t, F, P> Policy<Token> for Perses<'t, F, P>
where
    F: Fn() -> P,
    P: Policy<NodeId>,
{
    fn propose(
        &mut self,
        config: &Configuration<Token>,
    ) -> impl Iterator<Item = Delta<Token>> {
        // biggest payoff first: order the live nodes by surviving size
        let node2size = self.tree.subtree_sizes(config);
        let nodes = self
            .tree
            .live_internal_largest_first(config, &node2size);
        // one List at a time gets a persisted deletion minimizer
        self.pick_active(&nodes);
        // replacements first, then the active List's deletions
        let reps =
            self.replacements(&nodes, &node2size, config);
        reps.into_iter().chain(self.deletions(config))
    }

    fn on_reduced(
        &mut self,
        reduced: Option<&Configuration<Token>>,
    ) -> bool {
        let tree = self.tree;
        match self.active {
            Some(a) => {
                // the outcome, in the minimizer's space
                let elems =
                    reduced.map(|c| tree.elems_of(a, c));
                let inner =
                    self.minimizer.as_mut().unwrap();
                let keep = inner.on_reduced(elems.as_ref());
                if reduced.is_some() {
                    // reconsider every `List`
                    self.done.clear();
                    true
                } else if keep {
                    true // the inner policy isn't minimal yet
                } else {
                    // nothing more to delete here: mark the list
                    // done and move on. Once every list is done,
                    // `active` is None and the next all-failing
                    // pass ends the run.
                    self.done.insert(a);
                    true
                }
            }
            None => reduced.is_some(), // replacements-only pass
        }
    }
}

/// Does the surviving program still parse against the grammar? Once *any* node is
/// deletable, a deletion can land mid-production (drop `{` but keep `}`), so the
/// oracle must also reject programs the grammar no longer accepts.
fn parses(src: &str) -> bool {
    fn is_ident(t: &str) -> bool {
        !matches!(
            t,
            "int"
                | "main"
                | "if"
                | "("
                | ")"
                | "{"
                | "}"
                | ";"
        )
    }
    struct Parser<'a> {
        toks: Vec<&'a str>,
        pos: usize,
    }
    impl Parser<'_> {
        fn eat(&mut self, s: &str) -> bool {
            let ok = self.toks.get(self.pos) == Some(&s);
            self.pos += ok as usize;
            ok
        }
        fn ident(&mut self) -> bool {
            let ok = self
                .toks
                .get(self.pos)
                .is_some_and(|t| is_ident(t));
            self.pos += ok as usize;
            ok
        }
        // func ::= "int" "main" "(" ")" block
        fn func(&mut self) -> bool {
            self.eat("int")
                && self.eat("main")
                && self.eat("(")
                && self.eat(")")
                && self.block()
        }
        // block ::= "{" stmt* "}"
        fn block(&mut self) -> bool {
            if !self.eat("{") {
                return false;
            }
            while self.stmt() {}
            self.eat("}")
        }
        // stmt ::= if_stmt | block | call  (each alternative backtracks on failure)
        fn stmt(&mut self) -> bool {
            let save = self.pos;
            self.if_stmt()
                || (self.reset(save), self.block()).1
                || (self.reset(save), self.call()).1
                || (self.reset(save), false).1
        }
        // if_stmt ::= "if" "(" ident ")" block
        fn if_stmt(&mut self) -> bool {
            self.eat("if")
                && self.eat("(")
                && self.ident()
                && self.eat(")")
                && self.block()
        }
        // call ::= ident "(" ")" ";"
        fn call(&mut self) -> bool {
            self.ident()
                && self.eat("(")
                && self.eat(")")
                && self.eat(";")
        }
        fn reset(&mut self, pos: usize) {
            self.pos = pos;
        }
    }
    let mut p = Parser {
        toks: src.split_whitespace().collect(),
        pos: 0,
    };
    p.func() && p.pos == p.toks.len()
}

fn main() {
    // nested `if`s, with crash() at the bottom and noise() statements throughout
    let tree = std::rc::Rc::new(example_tree());
    // The configuration is every token of the program: units 0..n in
    // source order. Tree nodes are bookkeeping; they never sit in it.
    let all: Configuration<Token> =
        (0..tree.token2leaf.len() as Token).collect();

    let crash: Token = tree
        .id2node
        .iter()
        .find(|(_, n)| n.label == "crash")
        .map(|(id, _)| tree.leaf2token[id])
        .unwrap();

    // Interesting iff the program still contains crash() *and* still parses. The
    // returned counter tallies how many candidates each reducer tries.
    let make_oracle = || {
        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 src = render(&otree, c);
            let ok = c.contains(&crash) && parses(&src);
            println!(
                "  test {src:?}  ->  {}",
                if ok {
                    "crashes (keep)"
                } else {
                    "reject"
                }
            );
            if ok {
                Verdict::Interesting
            } else {
                Verdict::NotInteresting
            }
        };
        (oracle, calls)
    };

    // Level 0 is safe here, unlike the HDD chapter's demo: `deletable`
    // filters what HDD may delete, and the root is no List element, so a
    // level-0 pass simply proposes nothing.
    let (hdd_oracle, hdd_calls) = make_oracle();
    let hdd = reduce(
        all.clone(),
        &hdd_oracle,
        Hdd::new(&*tree, 0, || DDMin),
    );
    println!(
        "HDD (Kleene only) => {:?}  in {} calls\n",
        render(&tree, &hdd),
        hdd_calls.get()
    );

    let (perses_oracle, perses_calls) = make_oracle();
    let perses = reduce(
        all.clone(),
        &perses_oracle,
        Perses::new(&*tree, || DDMin),
    );
    println!(
        "Perses            => {:?}  in {} calls\n",
        render(&tree, &perses),
        perses_calls.get()
    );

    assert_eq!(
        render(&tree, &hdd),
        "int main ( ) { if ( c1 ) { if ( c2 ) { if ( c3 ) { crash ( ) ; } } } }"
    );
    assert_eq!(
        render(&tree, &perses),
        "int main ( ) { crash ( ) ; }"
    );
    assert_eq!(hdd_calls.get(), 9);
    assert_eq!(perses_calls.get(), 3);
}

/// A tiny builder so the nested example reads top-down instead of as a giant map.
struct Builder {
    id2node: HashMap<NodeId, Node>,
    next: u32,
}
impl Builder {
    fn new() -> Builder {
        Builder {
            id2node: HashMap::new(),
            next: 0,
        }
    }
    fn add(
        &mut self,
        kind: Kind,
        label: &'static str,
        children: Vec<NodeId>,
    ) -> NodeId {
        let id = NodeId(self.next);
        self.next += 1;
        self.id2node.insert(
            id,
            Node {
                kind,
                label,
                children,
            },
        );
        id
    }
    fn tok(&mut self, s: &'static str) -> NodeId {
        self.add(Kind::Token, s, vec![])
    }
    /// `name ( ) ;`  -- an expression statement.
    fn call(&mut self, name: &'static str) -> NodeId {
        let n = self.tok(name);
        let lp = self.tok("(");
        let rp = self.tok(")");
        let sc = self.tok(";");
        self.add(Kind::Call, "", vec![n, lp, rp, sc])
    }
    fn list(&mut self, elems: Vec<NodeId>) -> NodeId {
        self.add(Kind::List, "", elems)
    }
    /// `{ stmts }`
    fn block(&mut self, list: NodeId) -> NodeId {
        let lb = self.tok("{");
        let rb = self.tok("}");
        self.add(Kind::Block, "", vec![lb, list, rb])
    }
    /// `if ( cond ) body`
    fn if_stmt(
        &mut self,
        cond_name: &'static str,
        body: NodeId,
    ) -> NodeId {
        let kw = self.tok("if");
        let lp = self.tok("(");
        let c = self.tok(cond_name);
        let cond = self.add(Kind::Expr, "", vec![c]);
        let rp = self.tok(")");
        self.add(
            Kind::IfStmt,
            "",
            vec![kw, lp, cond, rp, body],
        )
    }
    /// `int main ( ) body`
    fn func(&mut self, body: NodeId) -> NodeId {
        let t = self.tok("int");
        let m = self.tok("main");
        let lp = self.tok("(");
        let rp = self.tok(")");
        self.add(Kind::Func, "", vec![t, m, lp, rp, body])
    }
}

fn example_tree() -> Tree {
    let mut b = Builder::new();
    // innermost: { crash(); noise(); }
    let crash = b.call("crash");
    let n0 = b.call("noise");
    let l3 = b.list(vec![crash, n0]);
    let blk3 = b.block(l3);
    let if3 = b.if_stmt("c3", blk3);
    // { if (c3) {...} noise(); }
    let n1 = b.call("noise");
    let l2 = b.list(vec![if3, n1]);
    let blk2 = b.block(l2);
    let if2 = b.if_stmt("c2", blk2);
    // { if (c2) {...} noise(); }
    let n2 = b.call("noise");
    let l1 = b.list(vec![if2, n2]);
    let blk1 = b.block(l1);
    let if1 = b.if_stmt("c1", blk1);
    // int main() { if (c1) {...} noise(); noise(); }
    let n3 = b.call("noise");
    let n4 = b.call("noise");
    let l0 = b.list(vec![if1, n3, n4]);
    let body = b.block(l0);
    let root = b.func(body);
    Tree::new(root, b.id2node)
}

HDD bottoms out at the nesting it can’t remove:

int main() { if (c1) { if (c2) { if (c3) { crash(); } } } }

Perses collapses it to the core:

int main() { crash(); }

Note

Perses reaches a strictly smaller program—in fewer calls (3 vs 9)—because it can delete the wrapper around the bug, not just the noise beside it.

Delete Anything?

HDD got stuck only because we let it delete List elements and nothing else. So let’s try letting it delete any node, not just List elements. The only change is to remove the deletable filter from alive_level_nodes:

    /// The level-`level` subtrees still holding a token -- the candidates HDD
    /// may delete at this level. Every node but the root is eligible.
    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))
            .filter(|&node| node != self.root)
            .collect()
    }

Now it can drop an if (cond) header and keep the block inside, collapsing the nest just as Perses did. However, with no grammar to guide it, most of these new deletions break the program—for example, a { left without its }.

Tip

Press play to watch HDD grope: most of its candidates get rejected as unparsable before one finally collapses the nest.

// Perses, "Delete Anything?" variant: same framework as perses.rs, but HDD's
// `List`-only restriction is lifted -- every node but the root is a deletion
// candidate. A blind deletion can now break the parse (drop a `{`, keep its `}`),
// so the oracle also checks the program still parses. Compiles and runs on its
// own:
//
//     rustc --edition 2024 perses_all_deletable.rs && ./perses_all_deletable

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 - &delta;
            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();
    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;

impl<U: AtomicUnit> Policy<U> for DDMin {
    fn propose(
        &mut self,
        config: &Configuration<U>,
    ) -> impl Iterator<Item = Delta<U>> {
        let units = config.len();
        successors(Some(2), move |&n| {
            (n < units).then(|| (2 * n).min(units))
        })
        .flat_map(move |n| {
            let subsets = partition(config, n);
            let keep_only = subsets
                .clone()
                .into_iter()
                .map(move |d| config - &d);
            keep_only.chain(subsets)
        })
        .filter(|delta| !delta.is_empty())
    }
}

/// 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);

/// A parse tree: every token is a leaf, so concatenating the surviving tokens
/// *is* the program.
struct Node {
    label: &'static str, // the source text, for a leaf
    children: Vec<NodeId>,
}

struct Tree {
    id2node: HashMap<NodeId, Node>,
    root: NodeId,
    node2depth: HashMap<NodeId, usize>,
    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 {
        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` (for a leaf, its own token if kept).
    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
    }

    /// The level-`level` subtrees still holding a token -- the candidates HDD
    /// may delete at this level. Every node but the root is eligible.
    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))
            .filter(|&node| node != self.root)
            .collect()
    }

    fn ancestor_at(
        &self,
        mut id: NodeId,
        level: usize,
    ) -> NodeId {
        while self.node2depth[&id] > level {
            id = self.node2parent[&id];
        }
        id
    }

}

/// Render a configuration by concatenating the surviving tokens in source
/// order -- for a parse tree, that *is* the program. Because a unit is its
/// token's source-order index, "in source order" is just ascending units.
fn render(tree: &Tree, present: &Configuration<Token>) -> String {
    let mut units: Vec<Token> =
        present.iter().copied().collect();
    units.sort_unstable();
    units
        .iter()
        .map(|&u| {
            tree.id2node[&tree.token2leaf[&u]].label
        })
        .collect::<Vec<_>>()
        .join(" ")
}

/// HDD walks the tree level by level and lets a fresh list-minimizer drop the
/// level's candidates -- here, any node but the root.
struct Hdd<'t, F, P> {
    tree: &'t Tree,
    new_minimizer: F,
    level: usize,
    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(),
        }
    }
}

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. `on_reduced` clears it
        // only when we descend a level, so a stateful inner policy (ProbDD) keeps
        // learning across a level's passes and is reset only at a level boundary.
        if self.minimizer.is_none() {
            self.minimizer = Some((self.new_minimizer)());
        }
        self.level_subtrees =
            tree.alive_level_nodes(level, config);
        let subtrees = &self.level_subtrees;
        let minimizer = self.minimizer.as_mut().unwrap();
        // Lazily: `reduce` stops pulling at the first success, so a stateful
        // inner policy only ever advances its model over *confirmed* failures.
        minimizer.propose(subtrees).map(
            move |drop| -> Delta<Token> {
                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);
        // Report the pass outcome to the inner minimizer
        // in its own space: this level's still-live
        // subtrees, or `None` when nothing was found.
        // Driving the inner policy through its full
        // protocol keeps HDD agnostic to the inner policy.
        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
    }
}

/// Does the surviving program still parse against the grammar? Once *any* node is
/// deletable, a deletion can land mid-production (drop `{` but keep `}`), so the
/// oracle must also reject programs the grammar no longer accepts.
fn parses(src: &str) -> bool {
    fn is_ident(t: &str) -> bool {
        !matches!(
            t,
            "int"
                | "main"
                | "if"
                | "("
                | ")"
                | "{"
                | "}"
                | ";"
        )
    }
    struct Parser<'a> {
        toks: Vec<&'a str>,
        pos: usize,
    }
    impl Parser<'_> {
        fn eat(&mut self, s: &str) -> bool {
            let ok = self.toks.get(self.pos) == Some(&s);
            self.pos += ok as usize;
            ok
        }
        fn ident(&mut self) -> bool {
            let ok = self
                .toks
                .get(self.pos)
                .is_some_and(|t| is_ident(t));
            self.pos += ok as usize;
            ok
        }
        // func ::= "int" "main" "(" ")" block
        fn func(&mut self) -> bool {
            self.eat("int")
                && self.eat("main")
                && self.eat("(")
                && self.eat(")")
                && self.block()
        }
        // block ::= "{" stmt* "}"
        fn block(&mut self) -> bool {
            if !self.eat("{") {
                return false;
            }
            while self.stmt() {}
            self.eat("}")
        }
        // stmt ::= if_stmt | block | call  (each alternative backtracks on failure)
        fn stmt(&mut self) -> bool {
            let save = self.pos;
            self.if_stmt()
                || (self.reset(save), self.block()).1
                || (self.reset(save), self.call()).1
                || (self.reset(save), false).1
        }
        // if_stmt ::= "if" "(" ident ")" block
        fn if_stmt(&mut self) -> bool {
            self.eat("if")
                && self.eat("(")
                && self.ident()
                && self.eat(")")
                && self.block()
        }
        // call ::= ident "(" ")" ";"
        fn call(&mut self) -> bool {
            self.ident()
                && self.eat("(")
                && self.eat(")")
                && self.eat(";")
        }
        fn reset(&mut self, pos: usize) {
            self.pos = pos;
        }
    }
    let mut p = Parser {
        toks: src.split_whitespace().collect(),
        pos: 0,
    };
    p.func() && p.pos == p.toks.len()
}

fn main() {
    // nested `if`s, with crash() at the bottom and noise() statements throughout
    let tree = std::rc::Rc::new(example_tree());
    // The configuration is every token of the program: units 0..n in
    // source order. Tree nodes are bookkeeping; they never sit in it.
    let all: Configuration<Token> =
        (0..tree.token2leaf.len() as Token).collect();

    let crash: Token = tree
        .id2node
        .iter()
        .find(|(_, n)| n.label == "crash")
        .map(|(id, _)| tree.leaf2token[id])
        .unwrap();

    // Interesting iff the program still contains crash() *and* still parses.
    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 src = render(&otree, c);
        let ok = c.contains(&crash) && parses(&src);
        println!(
            "  test {src:?}  ->  {}",
            if ok { "crashes (keep)" } else { "reject" }
        );
        if ok {
            Verdict::Interesting
        } else {
            Verdict::NotInteresting
        }
    };

    let hdd_all = reduce(
        all,
        &oracle,
        Hdd::new(&*tree, 0, || DDMin),
    );
    println!(
        "HDD (all deletable) => {:?}  in {} calls",
        render(&tree, &hdd_all),
        calls.get()
    );

    assert_eq!(
        render(&tree, &hdd_all),
        "int main ( ) { crash ( ) ; }"
    );
    assert_eq!(calls.get(), 105);
}

/// A tiny builder so the nested example reads top-down instead of as a giant map.
struct Builder {
    id2node: HashMap<NodeId, Node>,
    next: u32,
}
impl Builder {
    fn new() -> Builder {
        Builder {
            id2node: HashMap::new(),
            next: 0,
        }
    }
    fn add(
        &mut self,
        label: &'static str,
        children: Vec<NodeId>,
    ) -> NodeId {
        let id = NodeId(self.next);
        self.next += 1;
        self.id2node.insert(id, Node { label, children });
        id
    }
    fn tok(&mut self, s: &'static str) -> NodeId {
        self.add(s, vec![])
    }
    /// `name ( ) ;`  -- an expression statement.
    fn call(&mut self, name: &'static str) -> NodeId {
        let n = self.tok(name);
        let lp = self.tok("(");
        let rp = self.tok(")");
        let sc = self.tok(";");
        self.add("", vec![n, lp, rp, sc])
    }
    fn list(&mut self, elems: Vec<NodeId>) -> NodeId {
        self.add("", elems)
    }
    /// `{ stmts }`
    fn block(&mut self, list: NodeId) -> NodeId {
        let lb = self.tok("{");
        let rb = self.tok("}");
        self.add("", vec![lb, list, rb])
    }
    /// `if ( cond ) body`
    fn if_stmt(
        &mut self,
        cond_name: &'static str,
        body: NodeId,
    ) -> NodeId {
        let kw = self.tok("if");
        let lp = self.tok("(");
        let c = self.tok(cond_name);
        let cond = self.add("", vec![c]);
        let rp = self.tok(")");
        self.add("", vec![kw, lp, cond, rp, body])
    }
    /// `int main ( ) body`
    fn func(&mut self, body: NodeId) -> NodeId {
        let t = self.tok("int");
        let m = self.tok("main");
        let lp = self.tok("(");
        let rp = self.tok(")");
        self.add("", vec![t, m, lp, rp, body])
    }
}

fn example_tree() -> Tree {
    let mut b = Builder::new();
    // innermost: { crash(); noise(); }
    let crash = b.call("crash");
    let n0 = b.call("noise");
    let l3 = b.list(vec![crash, n0]);
    let blk3 = b.block(l3);
    let if3 = b.if_stmt("c3", blk3);
    // { if (c3) {...} noise(); }
    let n1 = b.call("noise");
    let l2 = b.list(vec![if3, n1]);
    let blk2 = b.block(l2);
    let if2 = b.if_stmt("c2", blk2);
    // { if (c2) {...} noise(); }
    let n2 = b.call("noise");
    let l1 = b.list(vec![if2, n2]);
    let blk1 = b.block(l1);
    let if1 = b.if_stmt("c1", blk1);
    // int main() { if (c1) {...} noise(); noise(); }
    let n3 = b.call("noise");
    let n4 = b.call("noise");
    let l0 = b.list(vec![if1, n3, n4]);
    let body = b.block(l0);
    let root = b.func(body);
    Tree::new(root, b.id2node)
}

It does reach Perses’s result:

int main() { crash(); }

Note

Same program—but 105 oracle calls versus Perses’s 3.