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>
13using namespace llvm;
14
15namespace {
16
17typedef DAGDeltaAlgorithm::edge_ty edge_ty;
18
19class FixedDAGDeltaAlgorithm : public DAGDeltaAlgorithm {
20 changeset_ty FailingSet;
21 unsigned NumTests;
22
23protected:
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
30public:
31 FixedDAGDeltaAlgorithm(const changeset_ty &_FailingSet)
32 : FailingSet(_FailingSet),
33 NumTests(0) {}
34
35 unsigned getNumTests() const { return NumTests; }
36};
37
38std::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
48std::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
55std::set<unsigned> range(unsigned N) {
56 return range(Start: 0, End: N);
57}
58
59TEST(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

source code of llvm/unittests/ADT/DAGDeltaAlgorithmTest.cpp