1 /**
2 * Copyright (c) 2021-2022 Huawei Device Co., Ltd.
3 * Licensed under the Apache License, Version 2.0 (the "License");
4 * you may not use this file except in compliance with the License.
5 * You may obtain a copy of the License at
6 *
7 * http://www.apache.org/licenses/LICENSE-2.0
8 *
9 * Unless required by applicable law or agreed to in writing, software
10 * distributed under the License is distributed on an "AS IS" BASIS,
11 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12 * See the License for the specific language governing permissions and
13 * limitations under the License.
14 */
15
16 #include "util/int_set.h"
17
18 #ifdef PANDA_CATCH2
19 #include <rapidcheck/catch.h>
20 #include "util/tests/environment.h"
21 #endif
22
23 using namespace panda::verifier;
24
25 namespace panda::verifier::test {
26
27 #ifdef PANDA_CATCH2
28
29 namespace {
30
31 const EnvOptions Options {"VERIFIER_TEST"};
32
33 using T = size_t;
34 // to actually get to the threshold in tests
35 constexpr size_t THRESHOLD = 32;
36 using StdSetT = std::set<T>;
37 using IntSetT = IntSet<T, THRESHOLD>;
38
AssertSetsEqual(const StdSetT & model,const IntSetT & sut)39 void AssertSetsEqual(const StdSetT &model, const IntSetT &sut)
40 {
41 RC_ASSERT(model.size() == sut.Size());
42 for (auto x : model) {
43 RC_ASSERT(sut.Contains(x));
44 }
45 RC_TAG(sut.Size() < THRESHOLD ? "sorted vector" : "bitvector");
46 }
47
48 template <typename StreamT>
AssertLazySetsEqual(const StdSetT & model,StreamT && sut)49 void AssertLazySetsEqual(const StdSetT &model, StreamT &&sut)
50 {
51 Index<size_t> tmp = sut();
52 size_t size = 0;
53 while (tmp.IsValid()) {
54 RC_ASSERT(model.find(tmp) != model.end());
55 size++;
56 tmp = sut();
57 }
58 RC_ASSERT(model.size() == size);
59 }
60
MakeIntSet(const StdSetT & model)61 IntSetT MakeIntSet(const StdSetT &model)
62 {
63 IntSetT result;
64 for (T x : model) {
65 result.Insert(x);
66 }
67 return result;
68 }
69
70 } // namespace
71
72 TEST_CASE("Test IntSet behaves like std::set", "verifier_IntSetT")
73 {
74 T max_value = 2048;
75 auto value_gen = rc::gen::inRange<T>(0, max_value);
76
__anon50e355d80202() 77 rc::prop("Insert", [&]() {
78 StdSetT set = *rc::gen::container<StdSetT>(value_gen);
79 bool pick_from_set = *rc::gen::arbitrary<bool>();
80 T value = pick_from_set ? *rc::gen::elementOf(set) : *value_gen;
81 RC_PRE(Index(value).IsValid());
82 RC_TAG(set.find(value) == set.end() ? "value not in set" : "value in set");
83 IntSetT int_set {MakeIntSet(set)};
84
85 set.insert(value);
86 int_set.Insert(value);
87
88 AssertSetsEqual(set, int_set);
89 });
90
__anon50e355d80302() 91 rc::prop("InsertMany", [&]() {
92 StdSetT set = *rc::gen::container<StdSetT>(value_gen);
93 auto values = *rc::gen::container<std::vector<T>>(value_gen);
94 bool sorted = *rc::gen::arbitrary<bool>();
95 IntSetT int_set {MakeIntSet(set)};
96
97 set.insert(values.begin(), values.end());
98 if (sorted) {
99 std::sort(values.begin(), values.end());
100 int_set.Insert<true>(values.begin(), values.end());
101 } else {
102 int_set.Insert(values.begin(), values.end());
103 }
104
105 AssertSetsEqual(set, int_set);
106 });
107
__anon50e355d80402() 108 rc::prop("Intersect/IntersectionSize", [&]() {
109 StdSetT set1 = *rc::gen::container<StdSetT>(value_gen), set2 = *rc::gen::container<StdSetT>(value_gen);
110 size_t num_common_elems = *rc::gen::inRange<size_t>(0, 2 * THRESHOLD);
111 std::vector<T> common_elems = *rc::gen::unique<std::vector<T>>(num_common_elems, value_gen);
112
113 for (T value : common_elems) {
114 set1.insert(value);
115 set2.insert(value);
116 }
117
118 IntSetT int_set1 {MakeIntSet(set1)}, int_set2 {MakeIntSet(set2)};
119
120 StdSetT std_intersection;
121 std::set_intersection(set1.begin(), set1.end(), set2.begin(), set2.end(),
122 std::inserter(std_intersection, std_intersection.begin()));
123 IntSetT int_set_intersection = int_set1 & int_set2;
124
125 AssertSetsEqual(std_intersection, int_set_intersection);
126
127 AssertLazySetsEqual(std_intersection, int_set1.LazyIntersect(int_set2));
128
129 int_set1 &= int_set2;
130 AssertSetsEqual(std_intersection, int_set1);
131 });
132
__anon50e355d80502() 133 rc::prop("Union", [&]() {
134 StdSetT set1 = *rc::gen::container<StdSetT>(value_gen), set2 = *rc::gen::container<StdSetT>(value_gen);
135 size_t num_common_elems = *rc::gen::inRange<size_t>(0, 2 * THRESHOLD);
136 std::vector<T> common_elems = *rc::gen::unique<std::vector<T>>(num_common_elems, value_gen);
137
138 for (T value : common_elems) {
139 set1.insert(value);
140 set2.insert(value);
141 }
142
143 IntSetT int_set1 {MakeIntSet(set1)}, int_set2 {MakeIntSet(set2)};
144
145 StdSetT std_union;
146 std::set_union(set1.begin(), set1.end(), set2.begin(), set2.end(), std::inserter(std_union, std_union.begin()));
147 IntSetT int_set_union = int_set1 | int_set2;
148
149 AssertSetsEqual(std_union, int_set_union);
150
151 int_set1 |= int_set2;
152 AssertSetsEqual(std_union, int_set1);
153 });
154 }
155
156 #endif // !PANDA_CATCH2
157
158 } // namespace panda::verifier::test
159