lib/Support/DeltaAlgorithm.cpp

   1 //===--- DeltaAlgorithm.cpp - A Set Minimization Algorithm -----*- C++ -*--===//
   2 //
   3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
   4 // See https://llvm.org/LICENSE.txt for license information.
   5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
   6 //===----------------------------------------------------------------------===//
   7
   8 #include "llvm/ADT/DeltaAlgorithm.h"
   9 #include <algorithm>
  10 #include <iterator>
  11 #include <set>
  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 }