1 | //===- llvm/unittest/ADT/DAGDeltaAlgorithmTest.cpp ------------------------===// |
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 | |
9 | #include "llvm/ADT/DAGDeltaAlgorithm.h" |
10 | #include "gtest/gtest.h" |
11 | #include <algorithm> |
12 | #include <cstdarg> |
13 | using namespace llvm; |
14 | |
15 | namespace { |
16 | |
17 | typedef DAGDeltaAlgorithm::edge_ty edge_ty; |
18 | |
19 | class FixedDAGDeltaAlgorithm : public DAGDeltaAlgorithm { |
20 | changeset_ty FailingSet; |
21 | unsigned NumTests; |
22 | |
23 | protected: |
24 | bool ExecuteOneTest(const changeset_ty &Changes) override { |
25 | ++NumTests; |
26 | return std::includes(first1: Changes.begin(), last1: Changes.end(), |
27 | first2: FailingSet.begin(), last2: FailingSet.end()); |
28 | } |
29 | |
30 | public: |
31 | FixedDAGDeltaAlgorithm(const changeset_ty &_FailingSet) |
32 | : FailingSet(_FailingSet), |
33 | NumTests(0) {} |
34 | |
35 | unsigned getNumTests() const { return NumTests; } |
36 | }; |
37 | |
38 | std::set<unsigned> fixed_set(unsigned N, ...) { |
39 | std::set<unsigned> S; |
40 | va_list ap; |
41 | va_start(ap, N); |
42 | for (unsigned i = 0; i != N; ++i) |
43 | S.insert(va_arg(ap, unsigned)); |
44 | va_end(ap); |
45 | return S; |
46 | } |
47 | |
48 | std::set<unsigned> range(unsigned Start, unsigned End) { |
49 | std::set<unsigned> S; |
50 | while (Start != End) |
51 | S.insert(x: Start++); |
52 | return S; |
53 | } |
54 | |
55 | std::set<unsigned> range(unsigned N) { |
56 | return range(Start: 0, End: N); |
57 | } |
58 | |
59 | TEST(DAGDeltaAlgorithmTest, Basic) { |
60 | std::vector<edge_ty> Deps; |
61 | |
62 | // Dependencies: |
63 | // 1 - 3 |
64 | Deps.clear(); |
65 | Deps.push_back(x: std::make_pair(x: 3, y: 1)); |
66 | |
67 | // P = {3,5,7} \in S, |
68 | // [0, 20), |
69 | // should minimize to {1,3,5,7} in a reasonable number of tests. |
70 | FixedDAGDeltaAlgorithm FDA(fixed_set(N: 3, 3, 5, 7)); |
71 | EXPECT_EQ(fixed_set(4, 1, 3, 5, 7), FDA.Run(range(20), Deps)); |
72 | EXPECT_GE(46U, FDA.getNumTests()); |
73 | |
74 | // Dependencies: |
75 | // 0 - 1 |
76 | // \- 2 - 3 |
77 | // \- 4 |
78 | Deps.clear(); |
79 | Deps.push_back(x: std::make_pair(x: 1, y: 0)); |
80 | Deps.push_back(x: std::make_pair(x: 2, y: 0)); |
81 | Deps.push_back(x: std::make_pair(x: 4, y: 0)); |
82 | Deps.push_back(x: std::make_pair(x: 3, y: 2)); |
83 | |
84 | // This is a case where we must hold required changes. |
85 | // |
86 | // P = {1,3} \in S, |
87 | // [0, 5), |
88 | // should minimize to {0,1,2,3} in a small number of tests. |
89 | FixedDAGDeltaAlgorithm FDA2(fixed_set(N: 2, 1, 3)); |
90 | EXPECT_EQ(fixed_set(4, 0, 1, 2, 3), FDA2.Run(range(5), Deps)); |
91 | EXPECT_GE(9U, FDA2.getNumTests()); |
92 | |
93 | // This is a case where we should quickly prune part of the tree. |
94 | // |
95 | // P = {4} \in S, |
96 | // [0, 5), |
97 | // should minimize to {0,4} in a small number of tests. |
98 | FixedDAGDeltaAlgorithm FDA3(fixed_set(N: 1, 4)); |
99 | EXPECT_EQ(fixed_set(2, 0, 4), FDA3.Run(range(5), Deps)); |
100 | EXPECT_GE(6U, FDA3.getNumTests()); |
101 | } |
102 | |
103 | } |
104 | |
105 | |