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>
13using namespace llvm;
14
15namespace std {
16
17std::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
32namespace {
33
34class FixedDeltaAlgorithm final : public DeltaAlgorithm {
35 changeset_ty FailingSet;
36 unsigned NumTests;
37
38protected:
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
45public:
46 FixedDeltaAlgorithm(const changeset_ty &_FailingSet)
47 : FailingSet(_FailingSet),
48 NumTests(0) {}
49
50 unsigned getNumTests() const { return NumTests; }
51};
52
53std::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
63std::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
70std::set<unsigned> range(unsigned N) {
71 return range(Start: 0, End: N);
72}
73
74TEST(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

source code of llvm/unittests/ADT/DeltaAlgorithmTest.cpp