class DeltaAlgorithm

Declaration

class DeltaAlgorithm { /* full declaration omitted */ };

Description

DeltaAlgorithm - Implements the delta debugging algorithm (A. Zeller '99) for minimizing arbitrary sets using a predicate function. The result of the algorithm is a subset of the input change set which is guaranteed to satisfy the predicate, assuming that the input set did. For well formed predicates, the result set is guaranteed to be such that removing any single element would falsify the predicate. For best results the predicate function *should* (but need not) satisfy certain properties, in particular: (1) The predicate should return false on an empty set and true on the full set. (2) If the predicate returns true for a set of changes, it should return true for all supersets of that set. It is not an error to provide a predicate that does not satisfy these requirements, and the algorithm will generally produce reasonable results. However, it may run substantially more tests than with a good predicate.

Declared at: llvm/include/llvm/ADT/DeltaAlgorithm.h:35

Member Variables

private std::set<changeset_ty> FailedTestsCache

Cache of failed test results. Successful test results are never cached since we always reduce following a success.

Method Overview

• private llvm::DeltaAlgorithm::changeset_ty Delta(const llvm::DeltaAlgorithm::changeset_ty & Changes, const llvm::DeltaAlgorithm::changesetlist_ty & Sets)
• protected virtual bool ExecuteOneTest(const llvm::DeltaAlgorithm::changeset_ty & S)
• private bool GetTestResult(const llvm::DeltaAlgorithm::changeset_ty & Changes)
• public llvm::DeltaAlgorithm::changeset_ty Run(const llvm::DeltaAlgorithm::changeset_ty & Changes)
• private bool Search(const llvm::DeltaAlgorithm::changeset_ty & Changes, const llvm::DeltaAlgorithm::changesetlist_ty & Sets, llvm::DeltaAlgorithm::changeset_ty & Res)
• private void Split(const llvm::DeltaAlgorithm::changeset_ty & S, llvm::DeltaAlgorithm::changesetlist_ty & Res)
• protected virtual void UpdatedSearchState(const llvm::DeltaAlgorithm::changeset_ty & Changes, const llvm::DeltaAlgorithm::changesetlist_ty & Sets)
• public virtual ~DeltaAlgorithm()

Methods

¶llvm::DeltaAlgorithm::changeset_ty Delta(
    const llvm::DeltaAlgorithm::changeset_ty&
        Changes,
    const llvm::DeltaAlgorithm::changesetlist_ty&
        Sets)

Description

Delta - Minimize a set of \p Changes which has been partitioned into smaller sets, by attempting to remove individual subsets.

Declared at: llvm/include/llvm/ADT/DeltaAlgorithm.h:59

Parameters

const llvm::DeltaAlgorithm::changeset_ty& Changes

const llvm::DeltaAlgorithm::changesetlist_ty& Sets

¶virtual bool ExecuteOneTest(
    const llvm::DeltaAlgorithm::changeset_ty& S)

Description

ExecuteOneTest - Execute a single test predicate on the change set \p S.

Declared at: llvm/include/llvm/ADT/DeltaAlgorithm.h:77

Parameters

const llvm::DeltaAlgorithm::changeset_ty& S

¶bool GetTestResult(
    const llvm::DeltaAlgorithm::changeset_ty&
        Changes)

Description

GetTestResult - Get the test result for the \p Changes from the cache, executing the test if necessary.

Declared at: llvm/include/llvm/ADT/DeltaAlgorithm.h:52

Parameters

const llvm::DeltaAlgorithm::changeset_ty& Changes

- The change set to test.

Returns

- The test result.

¶llvm::DeltaAlgorithm::changeset_ty Run(
    const llvm::DeltaAlgorithm::changeset_ty&
        Changes)

Description

Run - Minimize the set \p Changes by executing

Declared at: llvm/include/llvm/ADT/DeltaAlgorithm.h:87

Parameters

const llvm::DeltaAlgorithm::changeset_ty& Changes

¶bool Search(
    const llvm::DeltaAlgorithm::changeset_ty&
        Changes,
    const llvm::DeltaAlgorithm::changesetlist_ty&
        Sets,
    llvm::DeltaAlgorithm::changeset_ty& Res)

Description

Search - Search for a subset (or subsets) in \p Sets which can be removed from \p Changes while still satisfying the predicate.

Declared at: llvm/include/llvm/ADT/DeltaAlgorithm.h:68

Parameters

const llvm::DeltaAlgorithm::changeset_ty& Changes

const llvm::DeltaAlgorithm::changesetlist_ty& Sets

llvm::DeltaAlgorithm::changeset_ty& Res

- On success, a subset of Changes which satisfies the predicate.

Returns

- True on success.

¶void Split(
    const llvm::DeltaAlgorithm::changeset_ty& S,
    llvm::DeltaAlgorithm::changesetlist_ty& Res)

Description

Split - Partition a set of changes \p S into one or two subsets.

Declared at: llvm/include/llvm/ADT/DeltaAlgorithm.h:55

Parameters

const llvm::DeltaAlgorithm::changeset_ty& S

llvm::DeltaAlgorithm::changesetlist_ty& Res

¶virtual void UpdatedSearchState(
    const llvm::DeltaAlgorithm::changeset_ty&
        Changes,
    const llvm::DeltaAlgorithm::changesetlist_ty&
        Sets)

Description

UpdatedSearchState - Callback used when the search state changes.

Declared at: llvm/include/llvm/ADT/DeltaAlgorithm.h:73

Parameters

const llvm::DeltaAlgorithm::changeset_ty& Changes

const llvm::DeltaAlgorithm::changesetlist_ty& Sets

¶virtual ~DeltaAlgorithm()

Declared at: llvm/include/llvm/ADT/DeltaAlgorithm.h:82