LLVM  6.0.0svn
llvm::DAGDeltaAlgorithm Class Referenceabstract

DAGDeltaAlgorithm - Implements a "delta debugging" algorithm for minimizing directed acyclic graphs using a predicate function. More...

#include "llvm/ADT/DAGDeltaAlgorithm.h"

## Public Types

using change_ty = unsigned

using edge_ty = std::pair< change_ty, change_ty >

using changeset_ty = std::set< change_ty >

using changesetlist_ty = std::vector< changeset_ty >

## Public Member Functions

virtual ~DAGDeltaAlgorithm ()=default

changeset_ty Run (const changeset_ty &Changes, const std::vector< edge_ty > &Dependencies)
Run - Minimize the DAG formed by the Changes vertices and the Dependencies edges by executing. More...

virtual void UpdatedSearchState (const changeset_ty &Changes, const changesetlist_ty &Sets, const changeset_ty &Required)
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...

## Detailed Description

DAGDeltaAlgorithm - Implements a "delta debugging" algorithm for minimizing directed acyclic graphs 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 not required by the dependencies on the other elements would falsify the predicate.

The DAG should be used to represent dependencies in the changes which are likely to hold across the predicate function. That is, for a particular changeset S and predicate P:

The minization algorithm uses this dependency information to attempt to eagerly prune large subsets of changes. As with

DeltaAlgorithm, the DAG is not required to satisfy this property, but the algorithm will run substantially fewer tests with appropriate dependencies.
DeltaAlgorithm for more information on the properties which the predicate function itself should satisfy.

Definition at line 39 of file DAGDeltaAlgorithm.h.

## ◆ change_ty

Definition at line 43 of file DAGDeltaAlgorithm.h.

## ◆ changeset_ty

 using llvm::DAGDeltaAlgorithm::changeset_ty = std::set

Definition at line 47 of file DAGDeltaAlgorithm.h.

## ◆ changesetlist_ty

 using llvm::DAGDeltaAlgorithm::changesetlist_ty = std::vector

Definition at line 48 of file DAGDeltaAlgorithm.h.

## ◆ edge_ty

 using llvm::DAGDeltaAlgorithm::edge_ty = std::pair

Definition at line 44 of file DAGDeltaAlgorithm.h.

## ◆ ~DAGDeltaAlgorithm()

 virtual llvm::DAGDeltaAlgorithm::~DAGDeltaAlgorithm ( )
virtualdefault

## ◆ ExecuteOneTest()

 virtual bool llvm::DAGDeltaAlgorithm::ExecuteOneTest ( const changeset_ty & S )
pure virtual

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

Referenced by UpdatedSearchState().

## ◆ Run()

 DAGDeltaAlgorithm::changeset_ty DAGDeltaAlgorithm::Run ( const changeset_ty & Changes, const std::vector< edge_ty > & Dependencies )

Run - Minimize the DAG formed by the Changes vertices and the Dependencies edges by executing.

ExecuteOneTest() on subsets of changes and returning the smallest set which still satisfies the test predicate and the input Dependencies.
Parameters
 Changes The list of changes. Dependencies The list of dependencies amongst changes. For each (x,y) in Dependencies, both x and y must be in Changes. The minimization algorithm guarantees that for each tested changed set S, $$x \in S$$ implies $$y \in S$$. It is an error to have cyclic dependencies.

Definition at line 351 of file DAGDeltaAlgorithm.cpp.

## ◆ UpdatedSearchState()

 virtual void llvm::DAGDeltaAlgorithm::UpdatedSearchState ( const changeset_ty & Changes, const changesetlist_ty & Sets, const changeset_ty & Required )
inlinevirtual

UpdatedSearchState - Callback used when the search state changes.

Definition at line 69 of file DAGDeltaAlgorithm.h.

References ExecuteOneTest().

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