16f27b6231b04b85963be239e4b4e38a4ca4ad282Daniel Dunbar//===--- DeltaAlgorithm.cpp - A Set Minimization Algorithm -----*- C++ -*--===// 2eee658317491fb9c16588d9490a953cbe099099cDaniel Dunbar// 3eee658317491fb9c16588d9490a953cbe099099cDaniel Dunbar// The LLVM Compiler Infrastructure 4eee658317491fb9c16588d9490a953cbe099099cDaniel Dunbar// 5eee658317491fb9c16588d9490a953cbe099099cDaniel Dunbar// This file is distributed under the University of Illinois Open Source 6eee658317491fb9c16588d9490a953cbe099099cDaniel Dunbar// License. See LICENSE.TXT for details. 7eee658317491fb9c16588d9490a953cbe099099cDaniel Dunbar//===----------------------------------------------------------------------===// 8eee658317491fb9c16588d9490a953cbe099099cDaniel Dunbar 9eee658317491fb9c16588d9490a953cbe099099cDaniel Dunbar#include "llvm/ADT/DeltaAlgorithm.h" 10eee658317491fb9c16588d9490a953cbe099099cDaniel Dunbar#include <algorithm> 116f27b6231b04b85963be239e4b4e38a4ca4ad282Daniel Dunbar#include <iterator> 12eee658317491fb9c16588d9490a953cbe099099cDaniel Dunbarusing namespace llvm; 13eee658317491fb9c16588d9490a953cbe099099cDaniel Dunbar 14c831c64f16749af9b1a782ace983aee600d59c43Daniel DunbarDeltaAlgorithm::~DeltaAlgorithm() { 15c831c64f16749af9b1a782ace983aee600d59c43Daniel Dunbar} 16c831c64f16749af9b1a782ace983aee600d59c43Daniel Dunbar 17eee658317491fb9c16588d9490a953cbe099099cDaniel Dunbarbool DeltaAlgorithm::GetTestResult(const changeset_ty &Changes) { 18eee658317491fb9c16588d9490a953cbe099099cDaniel Dunbar if (FailedTestsCache.count(Changes)) 19eee658317491fb9c16588d9490a953cbe099099cDaniel Dunbar return false; 20eee658317491fb9c16588d9490a953cbe099099cDaniel Dunbar 21eee658317491fb9c16588d9490a953cbe099099cDaniel Dunbar bool Result = ExecuteOneTest(Changes); 22eee658317491fb9c16588d9490a953cbe099099cDaniel Dunbar if (!Result) 23eee658317491fb9c16588d9490a953cbe099099cDaniel Dunbar FailedTestsCache.insert(Changes); 24eee658317491fb9c16588d9490a953cbe099099cDaniel Dunbar 25eee658317491fb9c16588d9490a953cbe099099cDaniel Dunbar return Result; 26eee658317491fb9c16588d9490a953cbe099099cDaniel Dunbar} 27eee658317491fb9c16588d9490a953cbe099099cDaniel Dunbar 28eee658317491fb9c16588d9490a953cbe099099cDaniel Dunbarvoid DeltaAlgorithm::Split(const changeset_ty &S, changesetlist_ty &Res) { 29eee658317491fb9c16588d9490a953cbe099099cDaniel Dunbar // FIXME: Allow clients to provide heuristics for improved splitting. 30eee658317491fb9c16588d9490a953cbe099099cDaniel Dunbar 31eee658317491fb9c16588d9490a953cbe099099cDaniel Dunbar // FIXME: This is really slow. 32eee658317491fb9c16588d9490a953cbe099099cDaniel Dunbar changeset_ty LHS, RHS; 337f2dbb7358ef7af9940f385027b179b61c1ec0d0Daniel Dunbar unsigned idx = 0, N = S.size() / 2; 34eee658317491fb9c16588d9490a953cbe099099cDaniel Dunbar for (changeset_ty::const_iterator it = S.begin(), 35eee658317491fb9c16588d9490a953cbe099099cDaniel Dunbar ie = S.end(); it != ie; ++it, ++idx) 367f2dbb7358ef7af9940f385027b179b61c1ec0d0Daniel Dunbar ((idx < N) ? LHS : RHS).insert(*it); 37eee658317491fb9c16588d9490a953cbe099099cDaniel Dunbar if (!LHS.empty()) 38eee658317491fb9c16588d9490a953cbe099099cDaniel Dunbar Res.push_back(LHS); 39eee658317491fb9c16588d9490a953cbe099099cDaniel Dunbar if (!RHS.empty()) 40eee658317491fb9c16588d9490a953cbe099099cDaniel Dunbar Res.push_back(RHS); 41eee658317491fb9c16588d9490a953cbe099099cDaniel Dunbar} 42eee658317491fb9c16588d9490a953cbe099099cDaniel Dunbar 43eee658317491fb9c16588d9490a953cbe099099cDaniel DunbarDeltaAlgorithm::changeset_ty 44eee658317491fb9c16588d9490a953cbe099099cDaniel DunbarDeltaAlgorithm::Delta(const changeset_ty &Changes, 45eee658317491fb9c16588d9490a953cbe099099cDaniel Dunbar const changesetlist_ty &Sets) { 46eee658317491fb9c16588d9490a953cbe099099cDaniel Dunbar // Invariant: union(Res) == Changes 47eee658317491fb9c16588d9490a953cbe099099cDaniel Dunbar UpdatedSearchState(Changes, Sets); 48eee658317491fb9c16588d9490a953cbe099099cDaniel Dunbar 49eee658317491fb9c16588d9490a953cbe099099cDaniel Dunbar // If there is nothing left we can remove, we are done. 50eee658317491fb9c16588d9490a953cbe099099cDaniel Dunbar if (Sets.size() <= 1) 51eee658317491fb9c16588d9490a953cbe099099cDaniel Dunbar return Changes; 52eee658317491fb9c16588d9490a953cbe099099cDaniel Dunbar 53eee658317491fb9c16588d9490a953cbe099099cDaniel Dunbar // Look for a passing subset. 54eee658317491fb9c16588d9490a953cbe099099cDaniel Dunbar changeset_ty Res; 55eee658317491fb9c16588d9490a953cbe099099cDaniel Dunbar if (Search(Changes, Sets, Res)) 56eee658317491fb9c16588d9490a953cbe099099cDaniel Dunbar return Res; 57eee658317491fb9c16588d9490a953cbe099099cDaniel Dunbar 58eee658317491fb9c16588d9490a953cbe099099cDaniel Dunbar // Otherwise, partition the sets if possible; if not we are done. 59eee658317491fb9c16588d9490a953cbe099099cDaniel Dunbar changesetlist_ty SplitSets; 60eee658317491fb9c16588d9490a953cbe099099cDaniel Dunbar for (changesetlist_ty::const_iterator it = Sets.begin(), 61eee658317491fb9c16588d9490a953cbe099099cDaniel Dunbar ie = Sets.end(); it != ie; ++it) 62eee658317491fb9c16588d9490a953cbe099099cDaniel Dunbar Split(*it, SplitSets); 63eee658317491fb9c16588d9490a953cbe099099cDaniel Dunbar if (SplitSets.size() == Sets.size()) 64eee658317491fb9c16588d9490a953cbe099099cDaniel Dunbar return Changes; 65eee658317491fb9c16588d9490a953cbe099099cDaniel Dunbar 66eee658317491fb9c16588d9490a953cbe099099cDaniel Dunbar return Delta(Changes, SplitSets); 67eee658317491fb9c16588d9490a953cbe099099cDaniel Dunbar} 68eee658317491fb9c16588d9490a953cbe099099cDaniel Dunbar 69eee658317491fb9c16588d9490a953cbe099099cDaniel Dunbarbool DeltaAlgorithm::Search(const changeset_ty &Changes, 70eee658317491fb9c16588d9490a953cbe099099cDaniel Dunbar const changesetlist_ty &Sets, 71eee658317491fb9c16588d9490a953cbe099099cDaniel Dunbar changeset_ty &Res) { 72eee658317491fb9c16588d9490a953cbe099099cDaniel Dunbar // FIXME: Parallelize. 73eee658317491fb9c16588d9490a953cbe099099cDaniel Dunbar for (changesetlist_ty::const_iterator it = Sets.begin(), 74eee658317491fb9c16588d9490a953cbe099099cDaniel Dunbar ie = Sets.end(); it != ie; ++it) { 75eee658317491fb9c16588d9490a953cbe099099cDaniel Dunbar // If the test passes on this subset alone, recurse. 76eee658317491fb9c16588d9490a953cbe099099cDaniel Dunbar if (GetTestResult(*it)) { 77eee658317491fb9c16588d9490a953cbe099099cDaniel Dunbar changesetlist_ty Sets; 78eee658317491fb9c16588d9490a953cbe099099cDaniel Dunbar Split(*it, Sets); 79eee658317491fb9c16588d9490a953cbe099099cDaniel Dunbar Res = Delta(*it, Sets); 80eee658317491fb9c16588d9490a953cbe099099cDaniel Dunbar return true; 81eee658317491fb9c16588d9490a953cbe099099cDaniel Dunbar } 82eee658317491fb9c16588d9490a953cbe099099cDaniel Dunbar 83eee658317491fb9c16588d9490a953cbe099099cDaniel Dunbar // Otherwise, if we have more than two sets, see if test passes on the 84eee658317491fb9c16588d9490a953cbe099099cDaniel Dunbar // complement. 85eee658317491fb9c16588d9490a953cbe099099cDaniel Dunbar if (Sets.size() > 2) { 86eee658317491fb9c16588d9490a953cbe099099cDaniel Dunbar // FIXME: This is really slow. 87eee658317491fb9c16588d9490a953cbe099099cDaniel Dunbar changeset_ty Complement; 88eee658317491fb9c16588d9490a953cbe099099cDaniel Dunbar std::set_difference( 89eee658317491fb9c16588d9490a953cbe099099cDaniel Dunbar Changes.begin(), Changes.end(), it->begin(), it->end(), 90eee658317491fb9c16588d9490a953cbe099099cDaniel Dunbar std::insert_iterator<changeset_ty>(Complement, Complement.begin())); 91eee658317491fb9c16588d9490a953cbe099099cDaniel Dunbar if (GetTestResult(Complement)) { 92eee658317491fb9c16588d9490a953cbe099099cDaniel Dunbar changesetlist_ty ComplementSets; 93eee658317491fb9c16588d9490a953cbe099099cDaniel Dunbar ComplementSets.insert(ComplementSets.end(), Sets.begin(), it); 94eee658317491fb9c16588d9490a953cbe099099cDaniel Dunbar ComplementSets.insert(ComplementSets.end(), it + 1, Sets.end()); 95eee658317491fb9c16588d9490a953cbe099099cDaniel Dunbar Res = Delta(Complement, ComplementSets); 96eee658317491fb9c16588d9490a953cbe099099cDaniel Dunbar return true; 97eee658317491fb9c16588d9490a953cbe099099cDaniel Dunbar } 98eee658317491fb9c16588d9490a953cbe099099cDaniel Dunbar } 99eee658317491fb9c16588d9490a953cbe099099cDaniel Dunbar } 100eee658317491fb9c16588d9490a953cbe099099cDaniel Dunbar 101eee658317491fb9c16588d9490a953cbe099099cDaniel Dunbar return false; 102eee658317491fb9c16588d9490a953cbe099099cDaniel Dunbar} 103eee658317491fb9c16588d9490a953cbe099099cDaniel Dunbar 104eee658317491fb9c16588d9490a953cbe099099cDaniel DunbarDeltaAlgorithm::changeset_ty DeltaAlgorithm::Run(const changeset_ty &Changes) { 105eee658317491fb9c16588d9490a953cbe099099cDaniel Dunbar // Check empty set first to quickly find poor test functions. 106eee658317491fb9c16588d9490a953cbe099099cDaniel Dunbar if (GetTestResult(changeset_ty())) 107eee658317491fb9c16588d9490a953cbe099099cDaniel Dunbar return changeset_ty(); 108eee658317491fb9c16588d9490a953cbe099099cDaniel Dunbar 109eee658317491fb9c16588d9490a953cbe099099cDaniel Dunbar // Otherwise run the real delta algorithm. 110eee658317491fb9c16588d9490a953cbe099099cDaniel Dunbar changesetlist_ty Sets; 111eee658317491fb9c16588d9490a953cbe099099cDaniel Dunbar Split(Changes, Sets); 112eee658317491fb9c16588d9490a953cbe099099cDaniel Dunbar 113eee658317491fb9c16588d9490a953cbe099099cDaniel Dunbar return Delta(Changes, Sets); 114eee658317491fb9c16588d9490a953cbe099099cDaniel Dunbar} 115