DeltaAlgorithm.cpp revision 314564 
1//===--- DeltaAlgorithm.cpp - 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#include "llvm/ADT/DeltaAlgorithm.h"
10#include <algorithm>
11#include <iterator>
12#include <set>
13using namespace llvm;
14
15DeltaAlgorithm::~DeltaAlgorithm() {
16}
17
18bool DeltaAlgorithm::GetTestResult(const changeset_ty &Changes) {
19  if (FailedTestsCache.count(Changes))
20    return false;
21
22  bool Result = ExecuteOneTest(Changes);
23  if (!Result)
24    FailedTestsCache.insert(Changes);
25
26  return Result;
27}
28
29void DeltaAlgorithm::Split(const changeset_ty &S, changesetlist_ty &Res) {
30  // FIXME: Allow clients to provide heuristics for improved splitting.
31
32  // FIXME: This is really slow.
33  changeset_ty LHS, RHS;
34  unsigned idx = 0, N = S.size() / 2;
35  for (changeset_ty::const_iterator it = S.begin(),
36         ie = S.end(); it != ie; ++it, ++idx)
37    ((idx < N) ? LHS : RHS).insert(*it);
38  if (!LHS.empty())
39    Res.push_back(LHS);
40  if (!RHS.empty())
41    Res.push_back(RHS);
42}
43
44DeltaAlgorithm::changeset_ty
45DeltaAlgorithm::Delta(const changeset_ty &Changes,
46                      const changesetlist_ty &Sets) {
47  // Invariant: union(Res) == Changes
48  UpdatedSearchState(Changes, Sets);
49
50  // If there is nothing left we can remove, we are done.
51  if (Sets.size() <= 1)
52    return Changes;
53
54  // Look for a passing subset.
55  changeset_ty Res;
56  if (Search(Changes, Sets, Res))
57    return Res;
58
59  // Otherwise, partition the sets if possible; if not we are done.
60  changesetlist_ty SplitSets;
61  for (changesetlist_ty::const_iterator it = Sets.begin(),
62         ie = Sets.end(); it != ie; ++it)
63    Split(*it, SplitSets);
64  if (SplitSets.size() == Sets.size())
65    return Changes;
66
67  return Delta(Changes, SplitSets);
68}
69
70bool DeltaAlgorithm::Search(const changeset_ty &Changes,
71                            const changesetlist_ty &Sets,
72                            changeset_ty &Res) {
73  // FIXME: Parallelize.
74  for (changesetlist_ty::const_iterator it = Sets.begin(),
75         ie = Sets.end(); it != ie; ++it) {
76    // If the test passes on this subset alone, recurse.
77    if (GetTestResult(*it)) {
78      changesetlist_ty Sets;
79      Split(*it, Sets);
80      Res = Delta(*it, Sets);
81      return true;
82    }
83
84    // Otherwise, if we have more than two sets, see if test passes on the
85    // complement.
86    if (Sets.size() > 2) {
87      // FIXME: This is really slow.
88      changeset_ty Complement;
89      std::set_difference(
90        Changes.begin(), Changes.end(), it->begin(), it->end(),
91        std::insert_iterator<changeset_ty>(Complement, Complement.begin()));
92      if (GetTestResult(Complement)) {
93        changesetlist_ty ComplementSets;
94        ComplementSets.insert(ComplementSets.end(), Sets.begin(), it);
95        ComplementSets.insert(ComplementSets.end(), it + 1, Sets.end());
96        Res = Delta(Complement, ComplementSets);
97        return true;
98      }
99    }
100  }
101
102  return false;
103}
104
105DeltaAlgorithm::changeset_ty DeltaAlgorithm::Run(const changeset_ty &Changes) {
106  // Check empty set first to quickly find poor test functions.
107  if (GetTestResult(changeset_ty()))
108    return changeset_ty();
109
110  // Otherwise run the real delta algorithm.
111  changesetlist_ty Sets;
112  Split(Changes, Sets);
113
114  return Delta(Changes, Sets);
115}
116