1 //===- llvm/unittest/ADT/DeltaAlgorithmTest.cpp ---------------------------===//
2 //
3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4 // See https://llvm.org/LICENSE.txt for license information.
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6 //
7 //===----------------------------------------------------------------------===//
8
9 #include "llvm/ADT/DeltaAlgorithm.h"
10 #include "gtest/gtest.h"
11 #include <algorithm>
12 #include <cstdarg>
13 using namespace llvm;
14
15 namespace std {
16
operator <<(std::ostream & OS,const std::set<unsigned> & S)17 std::ostream &operator<<(std::ostream &OS,
18 const std::set<unsigned> &S) {
19 OS << "{";
20 for (std::set<unsigned>::const_iterator it = S.begin(),
21 ie = S.end(); it != ie; ++it) {
22 if (it != S.begin())
23 OS << ",";
24 OS << *it;
25 }
26 OS << "}";
27 return OS;
28 }
29
30 }
31
32 namespace {
33
34 class FixedDeltaAlgorithm final : public DeltaAlgorithm {
35 changeset_ty FailingSet;
36 unsigned NumTests;
37
38 protected:
ExecuteOneTest(const changeset_ty & Changes)39 bool ExecuteOneTest(const changeset_ty &Changes) override {
40 ++NumTests;
41 return std::includes(Changes.begin(), Changes.end(),
42 FailingSet.begin(), FailingSet.end());
43 }
44
45 public:
FixedDeltaAlgorithm(const changeset_ty & _FailingSet)46 FixedDeltaAlgorithm(const changeset_ty &_FailingSet)
47 : FailingSet(_FailingSet),
48 NumTests(0) {}
49
getNumTests() const50 unsigned getNumTests() const { return NumTests; }
51 };
52
fixed_set(unsigned N,...)53 std::set<unsigned> fixed_set(unsigned N, ...) {
54 std::set<unsigned> S;
55 va_list ap;
56 va_start(ap, N);
57 for (unsigned i = 0; i != N; ++i)
58 S.insert(va_arg(ap, unsigned));
59 va_end(ap);
60 return S;
61 }
62
range(unsigned Start,unsigned End)63 std::set<unsigned> range(unsigned Start, unsigned End) {
64 std::set<unsigned> S;
65 while (Start != End)
66 S.insert(Start++);
67 return S;
68 }
69
range(unsigned N)70 std::set<unsigned> range(unsigned N) {
71 return range(0, N);
72 }
73
TEST(DeltaAlgorithmTest,Basic)74 TEST(DeltaAlgorithmTest, Basic) {
75 // P = {3,5,7} \in S
76 // [0, 20) should minimize to {3,5,7} in a reasonable number of tests.
77 std::set<unsigned> Fails = fixed_set(3, 3, 5, 7);
78 FixedDeltaAlgorithm FDA(Fails);
79 EXPECT_EQ(fixed_set(3, 3, 5, 7), FDA.Run(range(20)));
80 EXPECT_GE(33U, FDA.getNumTests());
81
82 // P = {3,5,7} \in S
83 // [10, 20) should minimize to [10,20)
84 EXPECT_EQ(range(10,20), FDA.Run(range(10,20)));
85
86 // P = [0,4) \in S
87 // [0, 4) should minimize to [0,4) in 11 tests.
88 //
89 // 11 = |{ {},
90 // {0}, {1}, {2}, {3},
91 // {1, 2, 3}, {0, 2, 3}, {0, 1, 3}, {0, 1, 2},
92 // {0, 1}, {2, 3} }|
93 FDA = FixedDeltaAlgorithm(range(10));
94 EXPECT_EQ(range(4), FDA.Run(range(4)));
95 EXPECT_EQ(11U, FDA.getNumTests());
96 }
97
98 }
99
100