Line data    Source code

       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           9 : DeltaAlgorithm::~DeltaAlgorithm() {
      16           9 : }
      17           0 : 
      18           0 : bool DeltaAlgorithm::GetTestResult(const changeset_ty &Changes) {
      19           9 :   if (FailedTestsCache.count(Changes))
      20           9 :     return false;
      21             : 
      22         158 :   bool Result = ExecuteOneTest(Changes);
      23             :   if (!Result)
      24          36 :     FailedTestsCache.insert(Changes);
      25             : 
      26         122 :   return Result;
      27         122 : }
      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          67 :   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          67 :   if (!LHS.empty())
      39         182 :     Res.push_back(LHS);
      40         249 :   if (!RHS.empty())
      41         182 :     Res.push_back(RHS);
      42          67 : }
      43          31 : 
      44          67 : DeltaAlgorithm::changeset_ty
      45          67 : DeltaAlgorithm::Delta(const changeset_ty &Changes,
      46          67 :                       const changesetlist_ty &Sets) {
      47             :   // Invariant: union(Res) == Changes
      48             :   UpdatedSearchState(Changes, Sets);
      49          34 : 
      50             :   // If there is nothing left we can remove, we are done.
      51             :   if (Sets.size() <= 1)
      52          34 :     return Changes;
      53             : 
      54             :   // Look for a passing subset.
      55          68 :   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          29 :   changesetlist_ty SplitSets;
      61             :   for (changesetlist_ty::const_iterator it = Sets.begin(),
      62             :          ie = Sets.end(); it != ie; ++it)
      63             :     Split(*it, SplitSets);
      64          15 :   if (SplitSets.size() == Sets.size())
      65          15 :     return Changes;
      66          68 : 
      67          53 :   return Delta(Changes, SplitSets);
      68          45 : }
      69             : 
      70             : bool DeltaAlgorithm::Search(const changeset_ty &Changes,
      71          10 :                             const changesetlist_ty &Sets,
      72             :                             changeset_ty &Res) {
      73             :   // FIXME: Parallelize.
      74          29 :   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          29 :       changesetlist_ty Sets;
      79          98 :       Split(*it, Sets);
      80             :       Res = Delta(*it, Sets);
      81          83 :       return true;
      82           4 :     }
      83           4 : 
      84           8 :     // 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         158 :         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          65 :         ComplementSets.insert(ComplementSets.end(), it + 1, Sets.end());
      96          65 :         Res = Delta(Complement, ComplementSets);
      97          10 :         return true;
      98          20 :       }
      99          20 :     }
     100          20 :   }
     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          10 : 
     110             :   // Otherwise run the real delta algorithm.
     111          20 :   changesetlist_ty Sets;
     112           0 :   Split(Changes, Sets);
     113             : 
     114             :   return Delta(Changes, Sets);
     115          10 : }