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