llvm.org GIT mirror
release_29

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