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
14namespace 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.
35class DeltaAlgorithm {
36public:
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
42private:
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
71protected:
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
81public:
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