190075Sobrien//===--- DeltaAlgorithm.h - A Set Minimization Algorithm -------*- C++ -*--===// 2169689Skan// 390075Sobrien// The LLVM Compiler Infrastructure 490075Sobrien// 5132718Skan// This file is distributed under the University of Illinois Open Source 690075Sobrien// License. See LICENSE.TXT for details. 7132718Skan//===----------------------------------------------------------------------===// 890075Sobrien 990075Sobrien#ifndef LLVM_ADT_DELTAALGORITHM_H 1090075Sobrien#define LLVM_ADT_DELTAALGORITHM_H 1190075Sobrien 12132718Skan#include <set> 1390075Sobrien#include <vector> 1490075Sobrien 1590075Sobriennamespace llvm { 1690075Sobrien 1790075Sobrien/// DeltaAlgorithm - Implements the delta debugging algorithm (A. Zeller '99) 18132718Skan/// for minimizing arbitrary sets using a predicate function. 19169689Skan/// 20169689Skan/// The result of the algorithm is a subset of the input change set which is 2190075Sobrien/// guaranteed to satisfy the predicate, assuming that the input set did. For 2290075Sobrien/// well formed predicates, the result set is guaranteed to be such that 2390075Sobrien/// removing any single element would falsify the predicate. 24132718Skan/// 25169689Skan/// For best results the predicate function *should* (but need not) satisfy 26132718Skan/// certain properties, in particular: 2790075Sobrien/// (1) The predicate should return false on an empty set and true on the full 2890075Sobrien/// set. 2990075Sobrien/// (2) If the predicate returns true for a set of changes, it should return 30169689Skan/// true for all supersets of that set. 3190075Sobrien/// 3290075Sobrien/// It is not an error to provide a predicate that does not satisfy these 3390075Sobrien/// requirements, and the algorithm will generally produce reasonable 3496263Sobrien/// results. However, it may run substantially more tests than with a good 3590075Sobrien/// predicate. 3690075Sobrienclass DeltaAlgorithm { 37132718Skanpublic: 38132718Skan typedef unsigned change_ty; 3990075Sobrien // FIXME: Use a decent data structure. 4090075Sobrien typedef std::set<change_ty> changeset_ty; 4190075Sobrien typedef std::vector<changeset_ty> changesetlist_ty; 4290075Sobrien 43132718Skanprivate: 4490075Sobrien /// Cache of failed test results. Successful test results are never cached 4590075Sobrien /// since we always reduce following a success. 4690075Sobrien std::set<changeset_ty> FailedTestsCache; 47117395Skan 48117395Skan /// GetTestResult - Get the test result for the \p Changes from the 49117395Skan /// cache, executing the test if necessary. 50169689Skan /// 51117395Skan /// \param Changes - The change set to test. 52117395Skan /// \return - The test result. 53117395Skan bool GetTestResult(const changeset_ty &Changes); 54117395Skan 55117395Skan /// Split - Partition a set of changes \p S into one or two subsets. 56117395Skan void Split(const changeset_ty &S, changesetlist_ty &Res); 57169689Skan 58117395Skan /// Delta - Minimize a set of \p Changes which has been partioned into 59117395Skan /// smaller sets, by attempting to remove individual subsets. 60117395Skan changeset_ty Delta(const changeset_ty &Changes, 61132718Skan const changesetlist_ty &Sets); 62132718Skan 63132718Skan /// Search - Search for a subset (or subsets) in \p Sets which can be 64169689Skan /// removed from \p Changes while still satisfying the predicate. 65169689Skan /// 66169689Skan /// \param Res - On success, a subset of Changes which satisfies the 67132718Skan /// predicate. 68132718Skan /// \return - True on success. 69132718Skan bool Search(const changeset_ty &Changes, const changesetlist_ty &Sets, 70132718Skan changeset_ty &Res); 71117395Skan 72117395Skanprotected: 73117395Skan /// UpdatedSearchState - Callback used when the search state changes. 74169689Skan virtual void UpdatedSearchState(const changeset_ty &Changes, 75117395Skan const changesetlist_ty &Sets) {} 76117395Skan 77117395Skan /// ExecuteOneTest - Execute a single test predicate on the change set \p S. 7890075Sobrien virtual bool ExecuteOneTest(const changeset_ty &S) = 0; 7990075Sobrien 8090075Sobrienpublic: 81132718Skan virtual ~DeltaAlgorithm(); 8290075Sobrien 8390075Sobrien /// Run - Minimize the set \p Changes by executing \see ExecuteOneTest() on 8490075Sobrien /// subsets of changes and returning the smallest set which still satisfies 8590075Sobrien /// the test predicate. 86117395Skan changeset_ty Run(const changeset_ty &Changes); 87117395Skan}; 88117395Skan 89132718Skan} // end namespace llvm 90117395Skan 91117395Skan#endif 92117395Skan