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
~DeltaAlgorithm()14 DeltaAlgorithm::~DeltaAlgorithm() {
15 }
16
GetTestResult(const changeset_ty & Changes)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
Split(const changeset_ty & S,changesetlist_ty & Res)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
Delta(const changeset_ty & Changes,const changesetlist_ty & Sets)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
Search(const changeset_ty & Changes,const changesetlist_ty & Sets,changeset_ty & Res)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
Run(const changeset_ty & Changes)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