1 | //===- DAGDeltaAlgorithm.h - A DAG Minimization Algorithm ------*- C++ -*--===// |
2 | // |
3 | // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. |
4 | // See https://llvm.org/LICENSE.txt for license information. |
5 | // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception |
6 | //===----------------------------------------------------------------------===// |
7 | |
8 | #ifndef LLVM_ADT_DAGDELTAALGORITHM_H |
9 | #define LLVM_ADT_DAGDELTAALGORITHM_H |
10 | |
11 | #include <set> |
12 | #include <utility> |
13 | #include <vector> |
14 | |
15 | namespace llvm { |
16 | |
17 | /// DAGDeltaAlgorithm - Implements a "delta debugging" algorithm for minimizing |
18 | /// directed acyclic graphs using a predicate function. |
19 | /// |
20 | /// The result of the algorithm is a subset of the input change set which is |
21 | /// guaranteed to satisfy the predicate, assuming that the input set did. For |
22 | /// well formed predicates, the result set is guaranteed to be such that |
23 | /// removing any single element not required by the dependencies on the other |
24 | /// elements would falsify the predicate. |
25 | /// |
26 | /// The DAG should be used to represent dependencies in the changes which are |
27 | /// likely to hold across the predicate function. That is, for a particular |
28 | /// changeset S and predicate P: |
29 | /// |
30 | /// P(S) => P(S union pred(S)) |
31 | /// |
32 | /// The minimization algorithm uses this dependency information to attempt to |
33 | /// eagerly prune large subsets of changes. As with \see DeltaAlgorithm, the DAG |
34 | /// is not required to satisfy this property, but the algorithm will run |
35 | /// substantially fewer tests with appropriate dependencies. \see DeltaAlgorithm |
36 | /// for more information on the properties which the predicate function itself |
37 | /// should satisfy. |
38 | class DAGDeltaAlgorithm { |
39 | virtual void anchor(); |
40 | |
41 | public: |
42 | using change_ty = unsigned; |
43 | using edge_ty = std::pair<change_ty, change_ty>; |
44 | |
45 | // FIXME: Use a decent data structure. |
46 | using changeset_ty = std::set<change_ty>; |
47 | using changesetlist_ty = std::vector<changeset_ty>; |
48 | |
49 | public: |
50 | virtual ~DAGDeltaAlgorithm() = default; |
51 | |
52 | /// Run - Minimize the DAG formed by the \p Changes vertices and the |
53 | /// \p Dependencies edges by executing \see ExecuteOneTest() on subsets of |
54 | /// changes and returning the smallest set which still satisfies the test |
55 | /// predicate and the input \p Dependencies. |
56 | /// |
57 | /// \param Changes The list of changes. |
58 | /// |
59 | /// \param Dependencies The list of dependencies amongst changes. For each |
60 | /// (x,y) in \p Dependencies, both x and y must be in \p Changes. The |
61 | /// minimization algorithm guarantees that for each tested changed set S, |
62 | /// \f$ x \in S \f$ implies \f$ y \in S \f$. It is an error to have cyclic |
63 | /// dependencies. |
64 | changeset_ty Run(const changeset_ty &Changes, |
65 | const std::vector<edge_ty> &Dependencies); |
66 | |
67 | /// UpdatedSearchState - Callback used when the search state changes. |
68 | virtual void UpdatedSearchState(const changeset_ty &Changes, |
69 | const changesetlist_ty &Sets, |
70 | const changeset_ty &Required) {} |
71 | |
72 | /// ExecuteOneTest - Execute a single test predicate on the change set \p S. |
73 | virtual bool ExecuteOneTest(const changeset_ty &S) = 0; |
74 | }; |
75 | |
76 | } // end namespace llvm |
77 | |
78 | #endif // LLVM_ADT_DAGDELTAALGORITHM_H |
79 | |