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