ddmin: Delta debugging

In minex: Automatically Reduce Failing R Scripts to a Minimal Reproducible Example

Delta debugging

Description

General implementation of the ddmin minimization algorithm of Zeller and Hildebrandt (2002). Given a collection of elements and a predicate that reports whether a subset still exhibits some behavior of interest, ddmin() returns a subset that is one-minimal: the predicate holds for it, but fails for every subset obtained by removing a single element.

Usage

ddmin(
  items,
  interesting,
  algorithm = c("cdd", "ddmin"),
  max_oracle_calls = Inf,
  verbose = FALSE,
  .info = NULL
)

Arguments

items	A list or atomic vector of elements to minimize.
interesting	A predicate applied to a subset of items, in the same form as items, returning a single logical. It should return TRUE when the subset still reproduces the behavior of interest.
algorithm	Character. The reduction strategy for the first phase, one of "cdd" (convergent delta debugging, the default) or "ddmin" (the classic block-halving loop). Both are followed by a verification sweep that removes any remaining removable single elements.
max_oracle_calls	Numeric. An upper bound on the number of predicate evaluations. Must be at least 1. When the budget is exhausted the reduction stops early and returns the smallest set confirmed so far; the result is still guaranteed to reproduce the behavior but may not be one-minimal.
verbose	Logical or character. If TRUE, report each reduction phase via message(). If "trace", additionally record a per-call trace in .info$trace.
.info	Optional environment. When supplied, ddmin() populates it with oracle_calls (the number of predicate evaluations), complete (whether the reduction finished within budget), and trace (a data frame when verbose = "trace", otherwise NULL). Metadata flows only through this environment; the returned value itself carries no attributes.

Details

The algorithm partitions the current candidate into n blocks (starting with n = 2). It first tests whether any single block reproduces the behavior; if so it continues with that block. Otherwise it tests each complement (the candidate with one block removed) and continues with the first that reproduces. If neither succeeds the granularity is doubled, up to the point where each element sits in its own block, which guarantees one-minimality.

Results of the predicate are cached on the set of element indices, so an identical configuration is never evaluated twice.

Value

The one-minimal subset of items, in the original order.

References

Zeller A, Hildebrandt R (2002). "Simplifying and Isolating Failure-Inducing Input." IEEE Transactions on Software Engineering, 28(2), 183-200. \Sexpr[results=rd]{tools:::Rd_expr_doi("10.1109/32.988498")}

Zhang M, Xu Z, Tian Y, Cheng X, Sun C (2025). "Toward a Better Understanding of Probabilistic Delta Debugging." ICSE 2025. arXiv:2408.04735. https://arxiv.org/abs/2408.04735

See Also

minex() for the script-reduction front end and reduce_rows() for reducing data frames.

Examples

# Reduce a sentence to the single word a predicate depends on.
words <- strsplit("the quick brown fox", " ")[[1]]
ddmin(words, function(s) "fox" %in% s)

# When several elements are jointly required, all of them are kept.
nums <- 1:6
ddmin(nums, function(s) sum(s) >= 11 && 6 %in% s)

minex documentation built on Aug. 30, 2026, 1:07 a.m.