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