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
| //===- llvm/unittest/ADT/DAGDeltaAlgorithmTest.cpp ------------------------===//
//
// 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/DAGDeltaAlgorithm.h"
#include "gtest/gtest.h"
#include <algorithm>
#include <cstdarg>
using namespace llvm;
namespace {
typedef DAGDeltaAlgorithm::edge_ty edge_ty;
class FixedDAGDeltaAlgorithm : public DAGDeltaAlgorithm {
changeset_ty FailingSet;
unsigned NumTests;
protected:
bool ExecuteOneTest(const changeset_ty &Changes) override {
++NumTests;
return std::includes(Changes.begin(), Changes.end(),
FailingSet.begin(), FailingSet.end());
}
public:
FixedDAGDeltaAlgorithm(const changeset_ty &_FailingSet)
: FailingSet(_FailingSet),
NumTests(0) {}
unsigned getNumTests() const { return NumTests; }
};
std::set<unsigned> fixed_set(unsigned N, ...) {
std::set<unsigned> S;
va_list ap;
va_start(ap, N);
for (unsigned i = 0; i != N; ++i)
S.insert(va_arg(ap, unsigned));
va_end(ap);
return S;
}
std::set<unsigned> range(unsigned Start, unsigned End) {
std::set<unsigned> S;
while (Start != End)
S.insert(Start++);
return S;
}
std::set<unsigned> range(unsigned N) {
return range(0, N);
}
TEST(DAGDeltaAlgorithmTest, Basic) {
std::vector<edge_ty> Deps;
// Dependencies:
// 1 - 3
Deps.clear();
Deps.push_back(std::make_pair(3, 1));
// P = {3,5,7} \in S,
// [0, 20),
// should minimize to {1,3,5,7} in a reasonable number of tests.
FixedDAGDeltaAlgorithm FDA(fixed_set(3, 3, 5, 7));
EXPECT_EQ(fixed_set(4, 1, 3, 5, 7), FDA.Run(range(20), Deps));
EXPECT_GE(46U, FDA.getNumTests());
// Dependencies:
// 0 - 1
// \- 2 - 3
// \- 4
Deps.clear();
Deps.push_back(std::make_pair(1, 0));
Deps.push_back(std::make_pair(2, 0));
Deps.push_back(std::make_pair(4, 0));
Deps.push_back(std::make_pair(3, 2));
// This is a case where we must hold required changes.
//
// P = {1,3} \in S,
// [0, 5),
// should minimize to {0,1,2,3} in a small number of tests.
FixedDAGDeltaAlgorithm FDA2(fixed_set(2, 1, 3));
EXPECT_EQ(fixed_set(4, 0, 1, 2, 3), FDA2.Run(range(5), Deps));
EXPECT_GE(9U, FDA2.getNumTests());
// This is a case where we should quickly prune part of the tree.
//
// P = {4} \in S,
// [0, 5),
// should minimize to {0,4} in a small number of tests.
FixedDAGDeltaAlgorithm FDA3(fixed_set(1, 4));
EXPECT_EQ(fixed_set(2, 0, 4), FDA3.Run(range(5), Deps));
EXPECT_GE(6U, FDA3.getNumTests());
}
}
|