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 std::ostream &operator<<(std::ostream &OS,
17                          const std::set<unsigned> &S) {
18   OS << "{";
19   for (std::set<unsigned>::const_iterator it = S.begin(),
20          ie = S.end(); it != ie; ++it) {
21     if (it != S.begin())
22       OS << ",";
23     OS << *it;
24   }
25   OS << "}";
26   return OS;
27 }
28 
29 namespace {
30 
31 class FixedDeltaAlgorithm : public DeltaAlgorithm {
32   changeset_ty FailingSet;
33   unsigned NumTests;
34 
35 protected:
36   virtual bool ExecuteOneTest(const changeset_ty &Changes) {
37     ++NumTests;
38     return std::includes(Changes.begin(), Changes.end(),
39                          FailingSet.begin(), FailingSet.end());
40   }
41 
42 public:
43   FixedDeltaAlgorithm(const changeset_ty &_FailingSet)
44     : FailingSet(_FailingSet),
45       NumTests(0) {}
46 
47   unsigned getNumTests() const { return NumTests; }
48 };
49 
50 std::set<unsigned> fixed_set(unsigned N, ...) {
51   std::set<unsigned> S;
52   va_list ap;
53   va_start(ap, N);
54   for (unsigned i = 0; i != N; ++i)
55     S.insert(va_arg(ap, unsigned));
56   va_end(ap);
57   return S;
58 }
59 
60 std::set<unsigned> range(unsigned Start, unsigned End) {
61   std::set<unsigned> S;
62   while (Start != End)
63     S.insert(Start++);
64   return S;
65 }
66 
67 std::set<unsigned> range(unsigned N) {
68   return range(0, N);
69 }
70 
71 TEST(DeltaAlgorithmTest, Basic) {
72   // P = {3,5,7} \in S
73   //   [0, 20) should minimize to {3,5,7} in a reasonable number of tests.
74   std::set<unsigned> Fails = fixed_set(3, 3, 5, 7);
75   FixedDeltaAlgorithm FDA(Fails);
76   EXPECT_EQ(fixed_set(3, 3, 5, 7), FDA.Run(range(20)));
77   EXPECT_GE(33U, FDA.getNumTests());
78 
79   // P = {3,5,7} \in S
80   //   [10, 20) should minimize to [10,20)
81   EXPECT_EQ(range(10,20), FDA.Run(range(10,20)));
82 
83   // P = [0,4) \in S
84   //   [0, 4) should minimize to [0,4) in 11 tests.
85   //
86   // 11 = |{ {},
87   //         {0}, {1}, {2}, {3},
88   //         {1, 2, 3}, {0, 2, 3}, {0, 1, 3}, {0, 1, 2},
89   //         {0, 1}, {2, 3} }|
90   FDA = FixedDeltaAlgorithm(range(10));
91   EXPECT_EQ(range(4), FDA.Run(range(4)));
92   EXPECT_EQ(11U, FDA.getNumTests());
93 }
94 
95 }
96 
97