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