1 | //===- DeltaAlgorithm.h - A Set 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_DELTAALGORITHM_H |
9 | #define LLVM_ADT_DELTAALGORITHM_H |
10 | |
11 | #include <set> |
12 | #include <vector> |
13 | |
14 | namespace llvm { |
15 | |
16 | /// DeltaAlgorithm - Implements the delta debugging algorithm (A. Zeller '99) |
17 | /// for minimizing arbitrary sets using a predicate function. |
18 | /// |
19 | /// The result of the algorithm is a subset of the input change set which is |
20 | /// guaranteed to satisfy the predicate, assuming that the input set did. For |
21 | /// well formed predicates, the result set is guaranteed to be such that |
22 | /// removing any single element would falsify the predicate. |
23 | /// |
24 | /// For best results the predicate function *should* (but need not) satisfy |
25 | /// certain properties, in particular: |
26 | /// (1) The predicate should return false on an empty set and true on the full |
27 | /// set. |
28 | /// (2) If the predicate returns true for a set of changes, it should return |
29 | /// true for all supersets of that set. |
30 | /// |
31 | /// It is not an error to provide a predicate that does not satisfy these |
32 | /// requirements, and the algorithm will generally produce reasonable |
33 | /// results. However, it may run substantially more tests than with a good |
34 | /// predicate. |
35 | class DeltaAlgorithm { |
36 | public: |
37 | using change_ty = unsigned; |
38 | // FIXME: Use a decent data structure. |
39 | using changeset_ty = std::set<change_ty>; |
40 | using changesetlist_ty = std::vector<changeset_ty>; |
41 | |
42 | private: |
43 | /// Cache of failed test results. Successful test results are never cached |
44 | /// since we always reduce following a success. |
45 | std::set<changeset_ty> FailedTestsCache; |
46 | |
47 | /// GetTestResult - Get the test result for the \p Changes from the |
48 | /// cache, executing the test if necessary. |
49 | /// |
50 | /// \param Changes - The change set to test. |
51 | /// \return - The test result. |
52 | bool GetTestResult(const changeset_ty &Changes); |
53 | |
54 | /// Split - Partition a set of changes \p S into one or two subsets. |
55 | void Split(const changeset_ty &S, changesetlist_ty &Res); |
56 | |
57 | /// Delta - Minimize a set of \p Changes which has been partitioned into |
58 | /// smaller sets, by attempting to remove individual subsets. |
59 | changeset_ty Delta(const changeset_ty &Changes, |
60 | const changesetlist_ty &Sets); |
61 | |
62 | /// Search - Search for a subset (or subsets) in \p Sets which can be |
63 | /// removed from \p Changes while still satisfying the predicate. |
64 | /// |
65 | /// \param Res - On success, a subset of Changes which satisfies the |
66 | /// predicate. |
67 | /// \return - True on success. |
68 | bool Search(const changeset_ty &Changes, const changesetlist_ty &Sets, |
69 | changeset_ty &Res); |
70 | |
71 | protected: |
72 | /// UpdatedSearchState - Callback used when the search state changes. |
73 | virtual void UpdatedSearchState(const changeset_ty &Changes, |
74 | const changesetlist_ty &Sets) {} |
75 | |
76 | /// ExecuteOneTest - Execute a single test predicate on the change set \p S. |
77 | virtual bool ExecuteOneTest(const changeset_ty &S) = 0; |
78 | |
79 | DeltaAlgorithm& operator=(const DeltaAlgorithm&) = default; |
80 | |
81 | public: |
82 | virtual ~DeltaAlgorithm(); |
83 | |
84 | /// Run - Minimize the set \p Changes by executing \see ExecuteOneTest() on |
85 | /// subsets of changes and returning the smallest set which still satisfies |
86 | /// the test predicate. |
87 | changeset_ty Run(const changeset_ty &Changes); |
88 | }; |
89 | |
90 | } // end namespace llvm |
91 | |
92 | #endif // LLVM_ADT_DELTAALGORITHM_H |
93 | |