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