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