unittests/ADT/DAGDeltaAlgorithmTest.cpp

   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