1 //===- llvm/unittest/ADT/DAGDeltaAlgorithmTest.cpp ------------------------===//
2 //
3 //                     The LLVM Compiler Infrastructure
4 //
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
7 //
8 //===----------------------------------------------------------------------===//
9 
10 #include "gtest/gtest.h"
11 #include "llvm/ADT/DAGDeltaAlgorithm.h"
12 #include <algorithm>
13 #include <cstdarg>
14 using namespace llvm;
15 
16 namespace std {
17 
18 static std::ostream &operator<<(std::ostream &OS,
19                          const std::set<unsigned> &S) {
20   OS << "{";
21   for (std::set<unsigned>::const_iterator it = S.begin(),
22          ie = S.end(); it != ie; ++it) {
23     if (it != S.begin())
24       OS << ",";
25     OS << *it;
26   }
27   OS << "}";
28   return OS;
29 }
30 
31 }
32 
33 namespace {
34 
35 typedef DAGDeltaAlgorithm::edge_ty edge_ty;
36 
37 class FixedDAGDeltaAlgorithm : public DAGDeltaAlgorithm {
38   changeset_ty FailingSet;
39   unsigned NumTests;
40 
41 protected:
42   virtual bool ExecuteOneTest(const changeset_ty &Changes) {
43     ++NumTests;
44     return std::includes(Changes.begin(), Changes.end(),
45                          FailingSet.begin(), FailingSet.end());
46   }
47 
48 public:
49   FixedDAGDeltaAlgorithm(const changeset_ty &_FailingSet)
50     : FailingSet(_FailingSet),
51       NumTests(0) {}
52 
53   unsigned getNumTests() const { return NumTests; }
54 };
55 
56 std::set<unsigned> fixed_set(unsigned N, ...) {
57   std::set<unsigned> S;
58   va_list ap;
59   va_start(ap, N);
60   for (unsigned i = 0; i != N; ++i)
61     S.insert(va_arg(ap, unsigned));
62   va_end(ap);
63   return S;
64 }
65 
66 std::set<unsigned> range(unsigned Start, unsigned End) {
67   std::set<unsigned> S;
68   while (Start != End)
69     S.insert(Start++);
70   return S;
71 }
72 
73 std::set<unsigned> range(unsigned N) {
74   return range(0, N);
75 }
76 
77 TEST(DAGDeltaAlgorithmTest, Basic) {
78   std::vector<edge_ty> Deps;
79 
80   // Dependencies:
81   //  1 - 3
82   Deps.clear();
83   Deps.push_back(std::make_pair(3, 1));
84 
85   // P = {3,5,7} \in S,
86   //   [0, 20),
87   // should minimize to {1,3,5,7} in a reasonable number of tests.
88   FixedDAGDeltaAlgorithm FDA(fixed_set(3, 3, 5, 7));
89   EXPECT_EQ(fixed_set(4, 1, 3, 5, 7), FDA.Run(range(20), Deps));
90   EXPECT_GE(46U, FDA.getNumTests());
91 
92   // Dependencies:
93   // 0 - 1
94   //  \- 2 - 3
95   //  \- 4
96   Deps.clear();
97   Deps.push_back(std::make_pair(1, 0));
98   Deps.push_back(std::make_pair(2, 0));
99   Deps.push_back(std::make_pair(4, 0));
100   Deps.push_back(std::make_pair(3, 2));
101 
102   // This is a case where we must hold required changes.
103   //
104   // P = {1,3} \in S,
105   //   [0, 5),
106   // should minimize to {0,1,2,3} in a small number of tests.
107   FixedDAGDeltaAlgorithm FDA2(fixed_set(2, 1, 3));
108   EXPECT_EQ(fixed_set(4, 0, 1, 2, 3), FDA2.Run(range(5), Deps));
109   EXPECT_GE(9U, FDA2.getNumTests());
110 
111   // This is a case where we should quickly prune part of the tree.
112   //
113   // P = {4} \in S,
114   //   [0, 5),
115   // should minimize to {0,4} in a small number of tests.
116   FixedDAGDeltaAlgorithm FDA3(fixed_set(1, 4));
117   EXPECT_EQ(fixed_set(2, 0, 4), FDA3.Run(range(5), Deps));
118   EXPECT_GE(6U, FDA3.getNumTests());
119 }
120 
121 }
122 
123