lib/Support/DeltaAlgorithm.cpp

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