1 //===--- DeltaAlgorithm.cpp - A Set Minimization Algorithm -----*- C++ -*--===// 2 // 3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 4 // See https://llvm.org/LICENSE.txt for license information. 5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 6 //===----------------------------------------------------------------------===// 7 8 #include "llvm/ADT/DeltaAlgorithm.h" 9 #include <algorithm> 10 #include <iterator> 11 #include <set> 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 (const changeset_ty &Set : Sets) 61 Split(Set, SplitSets); 62 if (SplitSets.size() == Sets.size()) 63 return Changes; 64 65 return Delta(Changes, SplitSets); 66 } 67 68 bool DeltaAlgorithm::Search(const changeset_ty &Changes, 69 const changesetlist_ty &Sets, 70 changeset_ty &Res) { 71 // FIXME: Parallelize. 72 for (changesetlist_ty::const_iterator it = Sets.begin(), 73 ie = Sets.end(); it != ie; ++it) { 74 // If the test passes on this subset alone, recurse. 75 if (GetTestResult(*it)) { 76 changesetlist_ty Sets; 77 Split(*it, Sets); 78 Res = Delta(*it, Sets); 79 return true; 80 } 81 82 // Otherwise, if we have more than two sets, see if test passes on the 83 // complement. 84 if (Sets.size() > 2) { 85 // FIXME: This is really slow. 86 changeset_ty Complement; 87 std::set_difference( 88 Changes.begin(), Changes.end(), it->begin(), it->end(), 89 std::insert_iterator<changeset_ty>(Complement, Complement.begin())); 90 if (GetTestResult(Complement)) { 91 changesetlist_ty ComplementSets; 92 ComplementSets.insert(ComplementSets.end(), Sets.begin(), it); 93 ComplementSets.insert(ComplementSets.end(), it + 1, Sets.end()); 94 Res = Delta(Complement, ComplementSets); 95 return true; 96 } 97 } 98 } 99 100 return false; 101 } 102 103 DeltaAlgorithm::changeset_ty DeltaAlgorithm::Run(const changeset_ty &Changes) { 104 // Check empty set first to quickly find poor test functions. 105 if (GetTestResult(changeset_ty())) 106 return changeset_ty(); 107 108 // Otherwise run the real delta algorithm. 109 changesetlist_ty Sets; 110 Split(Changes, Sets); 111 112 return Delta(Changes, Sets); 113 } 114