LLVM  9.0.0svn
DeltaAlgorithm.h
Go to the documentation of this file.
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.
36 public:
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 partioned 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
This class represents lattice values for constants.
Definition: AllocatorList.h:23
virtual void UpdatedSearchState(const changeset_ty &Changes, const changesetlist_ty &Sets)
UpdatedSearchState - Callback used when the search state changes.
std::set< change_ty > changeset_ty
DeltaAlgorithm - Implements the delta debugging algorithm (A.
DeltaAlgorithm & operator=(const DeltaAlgorithm &)=default
changeset_ty Run(const changeset_ty &Changes)
Run - Minimize the set Changes by executing.
std::vector< changeset_ty > changesetlist_ty
virtual bool ExecuteOneTest(const changeset_ty &S)=0
ExecuteOneTest - Execute a single test predicate on the change set S.