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:

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

Member Typedef Documentation

◆ change_ty

using llvm::DAGDeltaAlgorithm::change_ty = unsigned

Definition at line 43 of file DAGDeltaAlgorithm.h.

◆ changeset_ty

using llvm::DAGDeltaAlgorithm::changeset_ty = std::set<change_ty>

Definition at line 47 of file DAGDeltaAlgorithm.h.

◆ changesetlist_ty

using llvm::DAGDeltaAlgorithm::changesetlist_ty = std::vector<changeset_ty>

Definition at line 48 of file DAGDeltaAlgorithm.h.

◆ edge_ty

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

Definition at line 44 of file DAGDeltaAlgorithm.h.

Constructor & Destructor Documentation

◆ ~DAGDeltaAlgorithm()

virtual llvm::DAGDeltaAlgorithm::~DAGDeltaAlgorithm ( )

virtualdefault

Member Function Documentation

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

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, \( x \in S \) implies \( y \in S \). It is an error to have cyclic dependencies.

Definition at line 359 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:

include/llvm/ADT/DAGDeltaAlgorithm.h
lib/Support/DAGDeltaAlgorithm.cpp

Public Types

Public Member Functions