DeltaAlgorithm.cpp revision 314564
1150957Simp//===--- DeltaAlgorithm.cpp - A Set Minimization Algorithm -----*- C++ -*--===// 2150957Simp// 3150957Simp// The LLVM Compiler Infrastructure 4150957Simp// 5150957Simp// This file is distributed under the University of Illinois Open Source 6150957Simp// License. See LICENSE.TXT for details. 7150957Simp//===----------------------------------------------------------------------===// 8150957Simp 9150957Simp#include "llvm/ADT/DeltaAlgorithm.h" 10150957Simp#include <algorithm> 11150957Simp#include <iterator> 12150957Simp#include <set> 13150957Simpusing namespace llvm; 14150957Simp 15150957SimpDeltaAlgorithm::~DeltaAlgorithm() { 16150957Simp} 17150957Simp 18150957Simpbool DeltaAlgorithm::GetTestResult(const changeset_ty &Changes) { 19150957Simp if (FailedTestsCache.count(Changes)) 20150957Simp return false; 21150957Simp 22150957Simp bool Result = ExecuteOneTest(Changes); 23150957Simp if (!Result) 24150957Simp FailedTestsCache.insert(Changes); 25150957Simp 26150957Simp return Result; 27150957Simp} 28150957Simp 29150957Simpvoid DeltaAlgorithm::Split(const changeset_ty &S, changesetlist_ty &Res) { 30150957Simp // FIXME: Allow clients to provide heuristics for improved splitting. 31150957Simp 32150957Simp // FIXME: This is really slow. 33150957Simp changeset_ty LHS, RHS; 34150957Simp unsigned idx = 0, N = S.size() / 2; 35150957Simp for (changeset_ty::const_iterator it = S.begin(), 36150957Simp ie = S.end(); it != ie; ++it, ++idx) 37150957Simp ((idx < N) ? LHS : RHS).insert(*it); 38150957Simp if (!LHS.empty()) 39150957Simp Res.push_back(LHS); 40150957Simp if (!RHS.empty()) 41150957Simp Res.push_back(RHS); 42150957Simp} 43150957Simp 44150957SimpDeltaAlgorithm::changeset_ty 45150957SimpDeltaAlgorithm::Delta(const changeset_ty &Changes, 46150957Simp const changesetlist_ty &Sets) { 47150957Simp // Invariant: union(Res) == Changes 48150957Simp UpdatedSearchState(Changes, Sets); 49150957Simp 50150957Simp // If there is nothing left we can remove, we are done. 51150957Simp if (Sets.size() <= 1) 52150957Simp return Changes; 53150957Simp 54150957Simp // Look for a passing subset. 55150957Simp changeset_ty Res; 56150957Simp if (Search(Changes, Sets, Res)) 57150957Simp return Res; 58150957Simp 59150957Simp // Otherwise, partition the sets if possible; if not we are done. 60150957Simp changesetlist_ty SplitSets; 61150957Simp for (changesetlist_ty::const_iterator it = Sets.begin(), 62150957Simp ie = Sets.end(); it != ie; ++it) 63150957Simp Split(*it, SplitSets); 64150957Simp if (SplitSets.size() == Sets.size()) 65150957Simp return Changes; 66150957Simp 67150957Simp return Delta(Changes, SplitSets); 68150957Simp} 69150957Simp 70150957Simpbool DeltaAlgorithm::Search(const changeset_ty &Changes, 71150957Simp const changesetlist_ty &Sets, 72150957Simp changeset_ty &Res) { 73150957Simp // FIXME: Parallelize. 74150957Simp for (changesetlist_ty::const_iterator it = Sets.begin(), 75150957Simp ie = Sets.end(); it != ie; ++it) { 76150957Simp // If the test passes on this subset alone, recurse. 77150957Simp if (GetTestResult(*it)) { 78151299Simp changesetlist_ty Sets; 79150957Simp Split(*it, Sets); 80150957Simp Res = Delta(*it, Sets); 81150957Simp return true; 82150957Simp } 83151547Simp 84151547Simp // Otherwise, if we have more than two sets, see if test passes on the 85151547Simp // complement. 86150957Simp if (Sets.size() > 2) { 87150957Simp // FIXME: This is really slow. 88150957Simp changeset_ty Complement; 89150957Simp std::set_difference( 90150957Simp Changes.begin(), Changes.end(), it->begin(), it->end(), 91150957Simp std::insert_iterator<changeset_ty>(Complement, Complement.begin())); 92150957Simp if (GetTestResult(Complement)) { 93150957Simp changesetlist_ty ComplementSets; 94150957Simp ComplementSets.insert(ComplementSets.end(), Sets.begin(), it); 95150957Simp ComplementSets.insert(ComplementSets.end(), it + 1, Sets.end()); 96151299Simp Res = Delta(Complement, ComplementSets); 97150957Simp return true; 98150957Simp } 99150957Simp } 100151299Simp } 101150957Simp 102150957Simp return false; 103150957Simp} 104150957Simp 105150957SimpDeltaAlgorithm::changeset_ty DeltaAlgorithm::Run(const changeset_ty &Changes) { 106150957Simp // Check empty set first to quickly find poor test functions. 107150957Simp if (GetTestResult(changeset_ty())) 108150957Simp return changeset_ty(); 109151299Simp 110150957Simp // Otherwise run the real delta algorithm. 111150957Simp changesetlist_ty Sets; 112150957Simp Split(Changes, Sets); 113150957Simp 114150957Simp return Delta(Changes, Sets); 115150957Simp} 116150957Simp