unittests/ADT/DeltaAlgorithmTest.cpp

   1 //===- llvm/unittest/ADT/DeltaAlgorithmTest.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/DeltaAlgorithm.h"
  12 #include <algorithm>
  13 #include <cstdarg>
  14 using namespace llvm;
  15
  16 namespace std {
  17
  18 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 class FixedDeltaAlgorithm : public DeltaAlgorithm {
  36   changeset_ty FailingSet;
  37   unsigned NumTests;
  38
  39 protected:
  40   virtual bool ExecuteOneTest(const changeset_ty &Changes) {
  41     ++NumTests;
  42     return std::includes(Changes.begin(), Changes.end(),
  43                          FailingSet.begin(), FailingSet.end());
  44   }
  45
  46 public:
  47   FixedDeltaAlgorithm(const changeset_ty &_FailingSet)
  48     : FailingSet(_FailingSet),
  49       NumTests(0) {}
  50
  51   unsigned getNumTests() const { return NumTests; }
  52 };
  53
  54 std::set<unsigned> fixed_set(unsigned N, ...) {
  55   std::set<unsigned> S;
  56   va_list ap;
  57   va_start(ap, N);
  58   for (unsigned i = 0; i != N; ++i)
  59     S.insert(va_arg(ap, unsigned));
  60   va_end(ap);
  61   return S;
  62 }
  63
  64 std::set<unsigned> range(unsigned Start, unsigned End) {
  65   std::set<unsigned> S;
  66   while (Start != End)
  67     S.insert(Start++);
  68   return S;
  69 }
  70
  71 std::set<unsigned> range(unsigned N) {
  72   return range(0, N);
  73 }
  74
  75 TEST(DeltaAlgorithmTest, Basic) {
  76   // P = {3,5,7} \in S
  77   //   [0, 20) should minimize to {3,5,7} in a reasonable number of tests.
  78   std::set<unsigned> Fails = fixed_set(3, 3, 5, 7);
  79   FixedDeltaAlgorithm FDA(Fails);
  80   EXPECT_EQ(fixed_set(3, 3, 5, 7), FDA.Run(range(20)));
  81   EXPECT_GE(33U, FDA.getNumTests());
  82
  83   // P = {3,5,7} \in S
  84   //   [10, 20) should minimize to [10,20)
  85   EXPECT_EQ(range(10,20), FDA.Run(range(10,20)));
  86
  87   // P = [0,4) \in S
  88   //   [0, 4) should minimize to [0,4) in 11 tests.
  89   //
  90   // 11 = |{ {},
  91   //         {0}, {1}, {2}, {3},
  92   //         {1, 2, 3}, {0, 2, 3}, {0, 1, 3}, {0, 1, 2},
  93   //         {0, 1}, {2, 3} }|
  94   FDA = FixedDeltaAlgorithm(range(10));
  95   EXPECT_EQ(range(4), FDA.Run(range(4)));
  96   EXPECT_EQ(11U, FDA.getNumTests());
  97 }
  98
  99 }
 100