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