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 | |
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: |
39 | bool ExecuteOneTest(const changeset_ty &Changes) override { |
40 | ++NumTests; |
41 | return std::includes(first1: Changes.begin(), last1: Changes.end(), |
42 | first2: FailingSet.begin(), last2: FailingSet.end()); |
43 | } |
44 | |
45 | public: |
46 | FixedDeltaAlgorithm(const changeset_ty &_FailingSet) |
47 | : FailingSet(_FailingSet), |
48 | NumTests(0) {} |
49 | |
50 | unsigned getNumTests() const { return NumTests; } |
51 | }; |
52 | |
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 | |
63 | std::set<unsigned> range(unsigned Start, unsigned End) { |
64 | std::set<unsigned> S; |
65 | while (Start != End) |
66 | S.insert(x: Start++); |
67 | return S; |
68 | } |
69 | |
70 | std::set<unsigned> range(unsigned N) { |
71 | return range(Start: 0, End: N); |
72 | } |
73 | |
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(N: 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(N: 10)); |
94 | EXPECT_EQ(range(4), FDA.Run(range(4))); |
95 | EXPECT_EQ(11U, FDA.getNumTests()); |
96 | } |
97 | |
98 | } |
99 | |
100 | |