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 // Get the iterator to the middle. 31 unsigned N = S.size() / 2; 32 changeset_ty::iterator middle(S.begin()); 33 std::advance(middle, N); 34 35 // Create each vector using the middle as the split. 36 changeset_ty LHS(S.begin(), middle); 37 changeset_ty RHS(middle, S.end()); 38 39 if (!LHS.empty()) 40 Res.push_back(LHS); 41 if (!RHS.empty()) 42 Res.push_back(RHS); 43 } 44 45 DeltaAlgorithm::changeset_ty 46 DeltaAlgorithm::Delta(const changeset_ty &Changes, 47 const changesetlist_ty &Sets) { 48 // Invariant: union(Res) == Changes 49 UpdatedSearchState(Changes, Sets); 50 51 // If there is nothing left we can remove, we are done. 52 if (Sets.size() <= 1) 53 return Changes; 54 55 // Look for a passing subset. 56 changeset_ty Res; 57 if (Search(Changes, Sets, Res)) 58 return Res; 59 60 // Otherwise, partition the sets if possible; if not we are done. 61 changesetlist_ty SplitSets; 62 for (changesetlist_ty::const_iterator it = Sets.begin(), 63 ie = Sets.end(); it != ie; ++it) 64 Split(*it, SplitSets); 65 if (SplitSets.size() == Sets.size()) 66 return Changes; 67 68 return Delta(Changes, SplitSets); 69 } 70 71 bool DeltaAlgorithm::Search(const changeset_ty &Changes, 72 const changesetlist_ty &Sets, 73 changeset_ty &Res) { 74 // FIXME: Parallelize. 75 for (changesetlist_ty::const_iterator it = Sets.begin(), 76 ie = Sets.end(); it != ie; ++it) { 77 // If the test passes on this subset alone, recurse. 78 if (GetTestResult(*it)) { 79 changesetlist_ty Sets; 80 Split(*it, Sets); 81 Res = Delta(*it, Sets); 82 return true; 83 } 84 85 // Otherwise, if we have more than two sets, see if test passes on the 86 // complement. 87 if (Sets.size() > 2) { 88 // FIXME: This is really slow. 89 changeset_ty Complement; 90 std::set_difference( 91 Changes.begin(), Changes.end(), it->begin(), it->end(), 92 std::insert_iterator<changeset_ty>(Complement, Complement.begin())); 93 if (GetTestResult(Complement)) { 94 changesetlist_ty ComplementSets; 95 ComplementSets.insert(ComplementSets.end(), Sets.begin(), it); 96 ComplementSets.insert(ComplementSets.end(), it + 1, Sets.end()); 97 Res = Delta(Complement, ComplementSets); 98 return true; 99 } 100 } 101 } 102 103 return false; 104 } 105 106 DeltaAlgorithm::changeset_ty DeltaAlgorithm::Run(const changeset_ty &Changes) { 107 // Check empty set first to quickly find poor test functions. 108 if (GetTestResult(changeset_ty())) 109 return changeset_ty(); 110 111 // Otherwise run the real delta algorithm. 112 changesetlist_ty Sets; 113 Split(Changes, Sets); 114 115 return Delta(Changes, Sets); 116 } 117