lib/Support/DeltaAlgorithm.cpp

   1 //===--- DeltaAlgorithm.cpp - A Set Minimization Algorithm -----*- C++ -*--===//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file is distributed under the University of Illinois Open Source
   6 // License. See LICENSE.TXT for details.
   7 //===----------------------------------------------------------------------===//
   8
   9 #include "llvm/ADT/DeltaAlgorithm.h"
  10 #include <algorithm>
  11 #include <iterator>
  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   // Get the iterator to the middle.
  31   unsigned N = S.size() / 2;
  32   changeset_ty::iterator middle(S.begin());
  33   std::advance(middle, N);
  34
  35   // Create each vector using the middle as the split.
  36   changeset_ty LHS(S.begin(), middle);
  37   changeset_ty RHS(middle, S.end());
  38
  39   if (!LHS.empty())
  40     Res.push_back(LHS);
  41   if (!RHS.empty())
  42     Res.push_back(RHS);
  43 }
  44
  45 DeltaAlgorithm::changeset_ty
  46 DeltaAlgorithm::Delta(const changeset_ty &Changes,
  47                       const changesetlist_ty &Sets) {
  48   // Invariant: union(Res) == Changes
  49   UpdatedSearchState(Changes, Sets);
  50
  51   // If there is nothing left we can remove, we are done.
  52   if (Sets.size() <= 1)
  53     return Changes;
  54
  55   // Look for a passing subset.
  56   changeset_ty Res;
  57   if (Search(Changes, Sets, Res))
  58     return Res;
  59
  60   // Otherwise, partition the sets if possible; if not we are done.
  61   changesetlist_ty SplitSets;
  62   for (changesetlist_ty::const_iterator it = Sets.begin(),
  63          ie = Sets.end(); it != ie; ++it)
  64     Split(*it, SplitSets);
  65   if (SplitSets.size() == Sets.size())
  66     return Changes;
  67
  68   return Delta(Changes, SplitSets);
  69 }
  70
  71 bool DeltaAlgorithm::Search(const changeset_ty &Changes,
  72                             const changesetlist_ty &Sets,
  73                             changeset_ty &Res) {
  74   // FIXME: Parallelize.
  75   for (changesetlist_ty::const_iterator it = Sets.begin(),
  76          ie = Sets.end(); it != ie; ++it) {
  77     // If the test passes on this subset alone, recurse.
  78     if (GetTestResult(*it)) {
  79       changesetlist_ty Sets;
  80       Split(*it, Sets);
  81       Res = Delta(*it, Sets);
  82       return true;
  83     }
  84
  85     // Otherwise, if we have more than two sets, see if test passes on the
  86     // complement.
  87     if (Sets.size() > 2) {
  88       // FIXME: This is really slow.
  89       changeset_ty Complement;
  90       std::set_difference(
  91         Changes.begin(), Changes.end(), it->begin(), it->end(),
  92         std::insert_iterator<changeset_ty>(Complement, Complement.begin()));
  93       if (GetTestResult(Complement)) {
  94         changesetlist_ty ComplementSets;
  95         ComplementSets.insert(ComplementSets.end(), Sets.begin(), it);
  96         ComplementSets.insert(ComplementSets.end(), it + 1, Sets.end());
  97         Res = Delta(Complement, ComplementSets);
  98         return true;
  99       }
 100     }
 101   }
 102
 103   return false;
 104 }
 105
 106 DeltaAlgorithm::changeset_ty DeltaAlgorithm::Run(const changeset_ty &Changes) {
 107   // Check empty set first to quickly find poor test functions.
 108   if (GetTestResult(changeset_ty()))
 109     return changeset_ty();
 110
 111   // Otherwise run the real delta algorithm.
 112   changesetlist_ty Sets;
 113   Split(Changes, Sets);
 114
 115   return Delta(Changes, Sets);
 116 }