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