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