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