LLVM 20.0.0git
Public Types | Public Member Functions | List of all members
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.
 
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 minimization 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

◆ change_ty

Definition at line 42 of file DAGDeltaAlgorithm.h.

◆ changeset_ty

Definition at line 46 of file DAGDeltaAlgorithm.h.

◆ changesetlist_ty

Definition at line 47 of file DAGDeltaAlgorithm.h.

◆ edge_ty

Definition at line 43 of file DAGDeltaAlgorithm.h.

Constructor & Destructor Documentation

◆ ~DAGDeltaAlgorithm()

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

References Run().

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.

◆ 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
ChangesThe list of changes.
DependenciesThe 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 349 of file DAGDeltaAlgorithm.cpp.

Referenced by ~DAGDeltaAlgorithm().

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


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