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 {
  17
  18 typedef DAGDeltaAlgorithm::edge_ty edge_ty;
  19
  20 class FixedDAGDeltaAlgorithm : public DAGDeltaAlgorithm {
  21   changeset_ty FailingSet;
  22   unsigned NumTests;
  23
  24 protected:
  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
  31 public:
  32   FixedDAGDeltaAlgorithm(const changeset_ty &_FailingSet)
  33     : FailingSet(_FailingSet),
  34       NumTests(0) {}
  35
  36   unsigned getNumTests() const { return NumTests; }
  37 };
  38
  39 std::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
  49 std::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
  56 std::set<unsigned> range(unsigned N) {
  57   return range(0, N);
  58 }
  59
  60 TEST(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