llvm::DAGDeltaAlgorithm Class Reference

#include <DAGDeltaAlgorithm.h>

List of all members.

Public Types
typedef unsigned	change_ty
typedef std::pair< change_ty, change_ty >	edge_ty
typedef std::set< change_ty >	changeset_ty
typedef std::vector< changeset_ty >	changesetlist_ty
Public Member Functions
virtual	~DAGDeltaAlgorithm ()
changeset_ty	Run (const changeset_ty &Changes, const std::vector< edge_ty > &Dependencies)
virtual void	UpdatedSearchState (const changeset_ty &Changes, const changesetlist_ty &Sets, const changeset_ty &Required)
	UpdatedSearchState - Callback used when the search state changes.
virtual bool	ExecuteOneTest (const changeset_ty &S)=0
	ExecuteOneTest - Execute a single test predicate on the change set S.

---

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:

P(S) => P(S union pred(S))

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

See also:

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 38 of file DAGDeltaAlgorithm.h.

---

Member Typedef Documentation

typedef unsigned llvm::DAGDeltaAlgorithm::change_ty

Definition at line 41 of file DAGDeltaAlgorithm.h.

typedef std::set<change_ty> llvm::DAGDeltaAlgorithm::changeset_ty

Definition at line 45 of file DAGDeltaAlgorithm.h.

typedef std::vector<changeset_ty> llvm::DAGDeltaAlgorithm::changesetlist_ty

Definition at line 46 of file DAGDeltaAlgorithm.h.

typedef std::pair<change_ty, change_ty> llvm::DAGDeltaAlgorithm::edge_ty

Definition at line 42 of file DAGDeltaAlgorithm.h.

---

Constructor & Destructor Documentation

virtual llvm::DAGDeltaAlgorithm::~DAGDeltaAlgorithm

(

)

[inline, virtual]

Definition at line 49 of file DAGDeltaAlgorithm.h.

---

Member Function Documentation

virtual bool llvm::DAGDeltaAlgorithm::ExecuteOneTest

(

const changeset_ty &

S

)

[pure virtual]

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

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

See also:

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, implies . It is an error to have cyclic dependencies.

Definition at line 359 of file DAGDeltaAlgorithm.cpp.

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

UpdatedSearchState - Callback used when the search state changes.

Definition at line 67 of file DAGDeltaAlgorithm.h.

---

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

• DAGDeltaAlgorithm.h
• DAGDeltaAlgorithm.cpp