LCOV - code coverage report
Current view: top level - lib/Support - DeltaAlgorithm.cpp (source / functions) Hit Total Coverage
Test: llvm-toolchain.info Lines: 49 50 98.0 %
Date: 2017-09-14 15:23:50 Functions: 6 7 85.7 %
Legend: Lines: hit not hit

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

Generated by: LCOV version 1.13