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