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 "llvm/ADT/DeltaAlgorithm.h"
11 #include "gtest/gtest.h"
12 #include <algorithm>
13 #include <cstdarg>
14 using namespace llvm;
15
16 namespace std {
17
operator <<(std::ostream & OS,const std::set<unsigned> & S)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 final : public DeltaAlgorithm {
36 changeset_ty FailingSet;
37 unsigned NumTests;
38
39 protected:
ExecuteOneTest(const changeset_ty & Changes)40 bool ExecuteOneTest(const changeset_ty &Changes) override {
41 ++NumTests;
42 return std::includes(Changes.begin(), Changes.end(),
43 FailingSet.begin(), FailingSet.end());
44 }
45
46 public:
FixedDeltaAlgorithm(const changeset_ty & _FailingSet)47 FixedDeltaAlgorithm(const changeset_ty &_FailingSet)
48 : FailingSet(_FailingSet),
49 NumTests(0) {}
50
getNumTests() const51 unsigned getNumTests() const { return NumTests; }
52 };
53
fixed_set(unsigned N,...)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
range(unsigned Start,unsigned End)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
range(unsigned N)71 std::set<unsigned> range(unsigned N) {
72 return range(0, N);
73 }
74
TEST(DeltaAlgorithmTest,Basic)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