1200581Srdivacky//===--- DeltaAlgorithm.cpp - A Set Minimization Algorithm -----*- C++ -*--===// 2200581Srdivacky// 3353358Sdim// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 4353358Sdim// See https://llvm.org/LICENSE.txt for license information. 5353358Sdim// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 6200581Srdivacky//===----------------------------------------------------------------------===// 7200581Srdivacky 8200581Srdivacky#include "llvm/ADT/DeltaAlgorithm.h" 9200581Srdivacky#include <algorithm> 10200581Srdivacky#include <iterator> 11314564Sdim#include <set> 12200581Srdivackyusing namespace llvm; 13200581Srdivacky 14200581SrdivackyDeltaAlgorithm::~DeltaAlgorithm() { 15200581Srdivacky} 16200581Srdivacky 17200581Srdivackybool DeltaAlgorithm::GetTestResult(const changeset_ty &Changes) { 18200581Srdivacky if (FailedTestsCache.count(Changes)) 19200581Srdivacky return false; 20200581Srdivacky 21200581Srdivacky bool Result = ExecuteOneTest(Changes); 22200581Srdivacky if (!Result) 23200581Srdivacky FailedTestsCache.insert(Changes); 24200581Srdivacky 25200581Srdivacky return Result; 26200581Srdivacky} 27200581Srdivacky 28200581Srdivackyvoid DeltaAlgorithm::Split(const changeset_ty &S, changesetlist_ty &Res) { 29200581Srdivacky // FIXME: Allow clients to provide heuristics for improved splitting. 30200581Srdivacky 31200581Srdivacky // FIXME: This is really slow. 32200581Srdivacky changeset_ty LHS, RHS; 33210299Sed unsigned idx = 0, N = S.size() / 2; 34200581Srdivacky for (changeset_ty::const_iterator it = S.begin(), 35200581Srdivacky ie = S.end(); it != ie; ++it, ++idx) 36210299Sed ((idx < N) ? LHS : RHS).insert(*it); 37200581Srdivacky if (!LHS.empty()) 38200581Srdivacky Res.push_back(LHS); 39200581Srdivacky if (!RHS.empty()) 40200581Srdivacky Res.push_back(RHS); 41200581Srdivacky} 42200581Srdivacky 43200581SrdivackyDeltaAlgorithm::changeset_ty 44200581SrdivackyDeltaAlgorithm::Delta(const changeset_ty &Changes, 45200581Srdivacky const changesetlist_ty &Sets) { 46200581Srdivacky // Invariant: union(Res) == Changes 47200581Srdivacky UpdatedSearchState(Changes, Sets); 48200581Srdivacky 49200581Srdivacky // If there is nothing left we can remove, we are done. 50200581Srdivacky if (Sets.size() <= 1) 51200581Srdivacky return Changes; 52200581Srdivacky 53200581Srdivacky // Look for a passing subset. 54200581Srdivacky changeset_ty Res; 55200581Srdivacky if (Search(Changes, Sets, Res)) 56200581Srdivacky return Res; 57200581Srdivacky 58200581Srdivacky // Otherwise, partition the sets if possible; if not we are done. 59200581Srdivacky changesetlist_ty SplitSets; 60200581Srdivacky for (changesetlist_ty::const_iterator it = Sets.begin(), 61200581Srdivacky ie = Sets.end(); it != ie; ++it) 62200581Srdivacky Split(*it, SplitSets); 63200581Srdivacky if (SplitSets.size() == Sets.size()) 64200581Srdivacky return Changes; 65200581Srdivacky 66200581Srdivacky return Delta(Changes, SplitSets); 67200581Srdivacky} 68200581Srdivacky 69200581Srdivackybool DeltaAlgorithm::Search(const changeset_ty &Changes, 70200581Srdivacky const changesetlist_ty &Sets, 71200581Srdivacky changeset_ty &Res) { 72200581Srdivacky // FIXME: Parallelize. 73200581Srdivacky for (changesetlist_ty::const_iterator it = Sets.begin(), 74200581Srdivacky ie = Sets.end(); it != ie; ++it) { 75200581Srdivacky // If the test passes on this subset alone, recurse. 76200581Srdivacky if (GetTestResult(*it)) { 77200581Srdivacky changesetlist_ty Sets; 78200581Srdivacky Split(*it, Sets); 79200581Srdivacky Res = Delta(*it, Sets); 80200581Srdivacky return true; 81200581Srdivacky } 82200581Srdivacky 83200581Srdivacky // Otherwise, if we have more than two sets, see if test passes on the 84200581Srdivacky // complement. 85200581Srdivacky if (Sets.size() > 2) { 86200581Srdivacky // FIXME: This is really slow. 87200581Srdivacky changeset_ty Complement; 88200581Srdivacky std::set_difference( 89200581Srdivacky Changes.begin(), Changes.end(), it->begin(), it->end(), 90200581Srdivacky std::insert_iterator<changeset_ty>(Complement, Complement.begin())); 91200581Srdivacky if (GetTestResult(Complement)) { 92200581Srdivacky changesetlist_ty ComplementSets; 93200581Srdivacky ComplementSets.insert(ComplementSets.end(), Sets.begin(), it); 94200581Srdivacky ComplementSets.insert(ComplementSets.end(), it + 1, Sets.end()); 95200581Srdivacky Res = Delta(Complement, ComplementSets); 96200581Srdivacky return true; 97200581Srdivacky } 98200581Srdivacky } 99200581Srdivacky } 100200581Srdivacky 101200581Srdivacky return false; 102200581Srdivacky} 103200581Srdivacky 104200581SrdivackyDeltaAlgorithm::changeset_ty DeltaAlgorithm::Run(const changeset_ty &Changes) { 105200581Srdivacky // Check empty set first to quickly find poor test functions. 106200581Srdivacky if (GetTestResult(changeset_ty())) 107200581Srdivacky return changeset_ty(); 108200581Srdivacky 109200581Srdivacky // Otherwise run the real delta algorithm. 110200581Srdivacky changesetlist_ty Sets; 111200581Srdivacky Split(Changes, Sets); 112200581Srdivacky 113200581Srdivacky return Delta(Changes, Sets); 114200581Srdivacky} 115