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