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