DAGDeltaAlgorithmTest.cpp revision 73c6031a2546ad18ab0b454fe5d711715620d140 
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>
14using namespace llvm;
15
16namespace std {
17
18static 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
33namespace {
34
35typedef DAGDeltaAlgorithm::edge_ty edge_ty;
36
37class FixedDAGDeltaAlgorithm : public DAGDeltaAlgorithm {
38  changeset_ty FailingSet;
39  unsigned NumTests;
40
41protected:
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
48public:
49  FixedDAGDeltaAlgorithm(const changeset_ty &_FailingSet)
50    : FailingSet(_FailingSet),
51      NumTests(0) {}
52
53  unsigned getNumTests() const { return NumTests; }
54};
55
56std::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
66std::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
73std::set<unsigned> range(unsigned N) {
74  return range(0, N);
75}
76
77TEST(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