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 (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 } 115