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>
13 using namespace llvm;
14
~DeltaAlgorithm()15 DeltaAlgorithm::~DeltaAlgorithm() {
16 }
17
GetTestResult(const changeset_ty & Changes)18 bool 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
Split(const changeset_ty & S,changesetlist_ty & Res)29 void 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
44 DeltaAlgorithm::changeset_ty
Delta(const changeset_ty & Changes,const changesetlist_ty & Sets)45 DeltaAlgorithm::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
Search(const changeset_ty & Changes,const changesetlist_ty & Sets,changeset_ty & Res)70 bool 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
Run(const changeset_ty & Changes)105 DeltaAlgorithm::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