Home | History | Annotate | Download | only in ADT 
      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 
    106