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(Changes.begin(), Changes.end(),
42                          FailingSet.begin(), 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(Start++);
67   return S;
68 }
69 
70 std::set<unsigned> range(unsigned N) {
71   return range(0, 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(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