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(Changes.begin(), Changes.end(),
27                          FailingSet.begin(), 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(Start++);
52   return S;
53 }
54 
55 std::set<unsigned> range(unsigned N) {
56   return range(0, 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(std::make_pair(3, 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(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(std::make_pair(1, 0));
80   Deps.push_back(std::make_pair(2, 0));
81   Deps.push_back(std::make_pair(4, 0));
82   Deps.push_back(std::make_pair(3, 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(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(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