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