LLVM  6.0.0svn
Public Types | Public Member Functions | Protected Member Functions | List of all members
llvm::DeltaAlgorithm Class Referenceabstract

DeltaAlgorithm - Implements the delta debugging algorithm (A. More...

#include "llvm/ADT/DeltaAlgorithm.h"

Public Types

using change_ty = unsigned
 
using changeset_ty = std::set< change_ty >
 
using changesetlist_ty = std::vector< changeset_ty >
 

Public Member Functions

virtual ~DeltaAlgorithm ()
 
changeset_ty Run (const changeset_ty &Changes)
 Run - Minimize the set Changes by executing. More...
 

Protected Member Functions

virtual void UpdatedSearchState (const changeset_ty &Changes, const changesetlist_ty &Sets)
 UpdatedSearchState - Callback used when the search state changes. More...
 
virtual bool ExecuteOneTest (const changeset_ty &S)=0
 ExecuteOneTest - Execute a single test predicate on the change set S. More...
 
DeltaAlgorithmoperator= (const DeltaAlgorithm &)=default
 

Detailed 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.

Definition at line 36 of file DeltaAlgorithm.h.

Member Typedef Documentation

◆ change_ty

Definition at line 38 of file DeltaAlgorithm.h.

◆ changeset_ty

Definition at line 40 of file DeltaAlgorithm.h.

◆ changesetlist_ty

Definition at line 41 of file DeltaAlgorithm.h.

Constructor & Destructor Documentation

◆ ~DeltaAlgorithm()

DeltaAlgorithm::~DeltaAlgorithm ( )
virtual

Definition at line 15 of file DeltaAlgorithm.cpp.

References ExecuteOneTest(), N, llvm::set_difference(), and UpdatedSearchState().

Referenced by UpdatedSearchState().

Member Function Documentation

◆ ExecuteOneTest()

virtual bool llvm::DeltaAlgorithm::ExecuteOneTest ( const changeset_ty S)
protectedpure virtual

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

Referenced by UpdatedSearchState(), and ~DeltaAlgorithm().

◆ operator=()

DeltaAlgorithm& llvm::DeltaAlgorithm::operator= ( const DeltaAlgorithm )
protecteddefault

Referenced by UpdatedSearchState().

◆ Run()

DeltaAlgorithm::changeset_ty DeltaAlgorithm::Run ( const changeset_ty Changes)

Run - Minimize the set Changes by executing.

See also
ExecuteOneTest() on subsets of changes and returning the smallest set which still satisfies the test predicate.

Definition at line 105 of file DeltaAlgorithm.cpp.

Referenced by UpdatedSearchState().

◆ UpdatedSearchState()

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

UpdatedSearchState - Callback used when the search state changes.

Definition at line 74 of file DeltaAlgorithm.h.

References ExecuteOneTest(), operator=(), Run(), and ~DeltaAlgorithm().

Referenced by ~DeltaAlgorithm().


The documentation for this class was generated from the following files: