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