1 // Copyright 2025 The BoringSSL Authors
2 //
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 //     https://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 #include <openssl/mem.h>
16 
17 #include <memory>
18 #include <utility>
19 #include <vector>
20 
21 #include <gtest/gtest.h>
22 
23 #include "mem_internal.h"
24 
25 
26 #if !defined(BORINGSSL_SHARED_LIBRARY)
27 BSSL_NAMESPACE_BEGIN
28 namespace {
29 
TEST(ArrayTest,Basic)30 TEST(ArrayTest, Basic) {
31   Array<int> array;
32   EXPECT_TRUE(array.empty());
33   EXPECT_EQ(array.size(), 0u);
34   const int v[] = {1, 2, 3, 4};
35   ASSERT_TRUE(array.CopyFrom(v));
36   EXPECT_FALSE(array.empty());
37   EXPECT_EQ(array.size(), 4u);
38   EXPECT_EQ(array[0], 1);
39   EXPECT_EQ(array[1], 2);
40   EXPECT_EQ(array[2], 3);
41   EXPECT_EQ(array[3], 4);
42   EXPECT_EQ(array.front(), 1);
43   EXPECT_EQ(array.back(), 4);
44 }
45 
TEST(ArrayTest,InitValueConstructs)46 TEST(ArrayTest, InitValueConstructs) {
47   Array<uint8_t> array;
48   ASSERT_TRUE(array.Init(10));
49   EXPECT_EQ(array.size(), 10u);
50   for (size_t i = 0; i < 10u; i++) {
51     EXPECT_EQ(0u, array[i]);
52   }
53 }
54 
TEST(ArrayDeathTest,BoundsChecks)55 TEST(ArrayDeathTest, BoundsChecks) {
56   Array<int> array;
57   EXPECT_DEATH_IF_SUPPORTED(array.front(), "");
58   EXPECT_DEATH_IF_SUPPORTED(array.back(), "");
59   const int v[] = {1, 2, 3, 4};
60   ASSERT_TRUE(array.CopyFrom(v));
61   EXPECT_DEATH_IF_SUPPORTED(array[4], "");
62 }
63 
TEST(VectorTest,Resize)64 TEST(VectorTest, Resize) {
65   Vector<size_t> vec;
66   ASSERT_TRUE(vec.empty());
67   EXPECT_EQ(vec.size(), 0u);
68 
69   ASSERT_TRUE(vec.Push(42));
70   ASSERT_TRUE(!vec.empty());
71   EXPECT_EQ(vec.size(), 1u);
72 
73   // Force a resize operation to occur
74   for (size_t i = 0; i < 16; i++) {
75     ASSERT_TRUE(vec.Push(i + 1));
76   }
77 
78   EXPECT_EQ(vec.size(), 17u);
79 
80   // Verify that expected values are still contained in vec
81   for (size_t i = 0; i < vec.size(); i++) {
82     EXPECT_EQ(vec[i], i == 0 ? 42 : i);
83   }
84   EXPECT_EQ(vec.front(), 42u);
85   EXPECT_EQ(vec.back(), 16u);
86 
87   // Clearing the vector should give an empty one.
88   vec.clear();
89   ASSERT_TRUE(vec.empty());
90   EXPECT_EQ(vec.size(), 0u);
91 
92   ASSERT_TRUE(vec.Push(42));
93   ASSERT_TRUE(!vec.empty());
94   EXPECT_EQ(vec.size(), 1u);
95   EXPECT_EQ(vec[0], 42u);
96   EXPECT_EQ(vec.front(), 42u);
97   EXPECT_EQ(vec.back(), 42u);
98 }
99 
TEST(VectorTest,MoveConstructor)100 TEST(VectorTest, MoveConstructor) {
101   Vector<size_t> vec;
102   for (size_t i = 0; i < 100; i++) {
103     ASSERT_TRUE(vec.Push(i));
104   }
105 
106   Vector<size_t> vec_moved(std::move(vec));
107   for (size_t i = 0; i < 100; i++) {
108     EXPECT_EQ(vec_moved[i], i);
109   }
110 }
111 
TEST(VectorTest,VectorContainingVectors)112 TEST(VectorTest, VectorContainingVectors) {
113   // Representative example of a struct that contains a Vector.
114   struct TagAndArray {
115     size_t tag;
116     Vector<size_t> vec;
117   };
118 
119   Vector<TagAndArray> vec;
120   for (size_t i = 0; i < 100; i++) {
121     TagAndArray elem;
122     elem.tag = i;
123     for (size_t j = 0; j < i; j++) {
124       ASSERT_TRUE(elem.vec.Push(j));
125     }
126     ASSERT_TRUE(vec.Push(std::move(elem)));
127   }
128   EXPECT_EQ(vec.size(), 100u);
129 
130   // Add and remove some element.
131   TagAndArray extra;
132   extra.tag = 1234;
133   ASSERT_TRUE(extra.vec.Push(1234));
134   ASSERT_TRUE(vec.Push(std::move(extra)));
135   EXPECT_EQ(vec.size(), 101u);
136   vec.pop_back();
137   EXPECT_EQ(vec.size(), 100u);
138 
139   Vector<TagAndArray> vec_moved(std::move(vec));
140   EXPECT_EQ(vec_moved.size(), 100u);
141   size_t count = 0;
142   for (const TagAndArray &elem : vec_moved) {
143     // Test the square bracket operator returns the same value as iteration.
144     EXPECT_EQ(&elem, &vec_moved[count]);
145 
146     EXPECT_EQ(elem.tag, count);
147     EXPECT_EQ(elem.vec.size(), count);
148     for (size_t j = 0; j < count; j++) {
149       EXPECT_EQ(elem.vec[j], j);
150     }
151     count++;
152   }
153 }
154 
TEST(VectorTest,NotDefaultConstructible)155 TEST(VectorTest, NotDefaultConstructible) {
156   struct NotDefaultConstructible {
157     explicit NotDefaultConstructible(size_t n) { BSSL_CHECK(array.Init(n)); }
158     Array<int> array;
159   };
160 
161   Vector<NotDefaultConstructible> vec;
162   ASSERT_TRUE(vec.Push(NotDefaultConstructible(0)));
163   ASSERT_TRUE(vec.Push(NotDefaultConstructible(1)));
164   ASSERT_TRUE(vec.Push(NotDefaultConstructible(2)));
165   ASSERT_TRUE(vec.Push(NotDefaultConstructible(3)));
166   EXPECT_EQ(vec.size(), 4u);
167   EXPECT_EQ(0u, vec[0].array.size());
168   EXPECT_EQ(1u, vec[1].array.size());
169   EXPECT_EQ(2u, vec[2].array.size());
170   EXPECT_EQ(3u, vec[3].array.size());
171 }
172 
TEST(VectorDeathTest,BoundsChecks)173 TEST(VectorDeathTest, BoundsChecks) {
174   Vector<int> vec;
175   EXPECT_DEATH_IF_SUPPORTED(vec.front(), "");
176   EXPECT_DEATH_IF_SUPPORTED(vec.back(), "");
177   EXPECT_DEATH_IF_SUPPORTED(vec.pop_back(), "");
178   ASSERT_TRUE(vec.Push(1));
179   // Within bounds of the capacity, but not the vector.
180   EXPECT_DEATH_IF_SUPPORTED(vec[1], "");
181   // Not within bounds of the capacity either.
182   EXPECT_DEATH_IF_SUPPORTED(vec[10000], "");
183 }
184 
TEST(InplaceVector,Basic)185 TEST(InplaceVector, Basic) {
186   InplaceVector<int, 4> vec;
187   EXPECT_TRUE(vec.empty());
188   EXPECT_EQ(0u, vec.size());
189   EXPECT_EQ(vec.begin(), vec.end());
190 
191   int data3[] = {1, 2, 3};
192   ASSERT_TRUE(vec.TryCopyFrom(data3));
193   EXPECT_FALSE(vec.empty());
194   EXPECT_EQ(3u, vec.size());
195   auto iter = vec.begin();
196   EXPECT_EQ(1, vec[0]);
197   EXPECT_EQ(1, *iter);
198   iter++;
199   EXPECT_EQ(2, vec[1]);
200   EXPECT_EQ(2, *iter);
201   iter++;
202   EXPECT_EQ(3, vec[2]);
203   EXPECT_EQ(3, *iter);
204   iter++;
205   EXPECT_EQ(iter, vec.end());
206   EXPECT_EQ(Span(vec), Span(data3));
207   EXPECT_EQ(vec.front(), 1);
208   EXPECT_EQ(vec.back(), 3);
209 
210   InplaceVector<int, 4> vec2 = vec;
211   EXPECT_EQ(Span(vec), Span(vec2));
212 
213   InplaceVector<int, 4> vec3;
214   vec3 = vec;
215   EXPECT_EQ(Span(vec), Span(vec2));
216 
217   int data4[] = {1, 2, 3, 4};
218   ASSERT_TRUE(vec.TryCopyFrom(data4));
219   EXPECT_EQ(Span(vec), Span(data4));
220 
221   int data5[] = {1, 2, 3, 4, 5};
222   EXPECT_FALSE(vec.TryCopyFrom(data5));
223   EXPECT_FALSE(vec.TryResize(5));
224 
225   // Shrink the vector.
226   ASSERT_TRUE(vec.TryResize(3));
227   EXPECT_EQ(Span(vec), Span(data3));
228 
229   // Enlarge it again. The new value should have been value-initialized.
230   ASSERT_TRUE(vec.TryResize(4));
231   EXPECT_EQ(vec[3], 0);
232 
233   // Self-assignment should not break the vector. Indirect through a pointer to
234   // avoid tripping a compiler warning.
235   vec.CopyFrom(data4);
236   const auto *ptr = &vec;
237   vec = *ptr;
238   EXPECT_EQ(Span(vec), Span(data4));
239 }
240 
TEST(InplaceVectorTest,ComplexType)241 TEST(InplaceVectorTest, ComplexType) {
242   InplaceVector<std::vector<int>, 4> vec_of_vecs;
243   const std::vector<int> data[] = {{1, 2, 3}, {4, 5, 6}, {7, 8, 9}};
244   vec_of_vecs.CopyFrom(data);
245   EXPECT_EQ(Span(vec_of_vecs), Span(data));
246 
247   vec_of_vecs.Resize(2);
248   EXPECT_EQ(Span(vec_of_vecs), Span(data, 2));
249 
250   vec_of_vecs.PushBack({42});
251   EXPECT_EQ(3u, vec_of_vecs.size());
252   vec_of_vecs.pop_back();
253   EXPECT_EQ(2u, vec_of_vecs.size());
254 
255   vec_of_vecs.Resize(4);
256   EXPECT_EQ(4u, vec_of_vecs.size());
257   EXPECT_EQ(vec_of_vecs[0], data[0]);
258   EXPECT_EQ(vec_of_vecs[1], data[1]);
259   EXPECT_TRUE(vec_of_vecs[2].empty());
260   EXPECT_TRUE(vec_of_vecs[3].empty());
261 
262   // Copy-construction.
263   InplaceVector<std::vector<int>, 4> vec_of_vecs2 = vec_of_vecs;
264   EXPECT_EQ(4u, vec_of_vecs2.size());
265   EXPECT_EQ(vec_of_vecs2[0], data[0]);
266   EXPECT_EQ(vec_of_vecs2[1], data[1]);
267   EXPECT_TRUE(vec_of_vecs2[2].empty());
268   EXPECT_TRUE(vec_of_vecs2[3].empty());
269 
270   // Copy-assignment.
271   InplaceVector<std::vector<int>, 4> vec_of_vecs3;
272   vec_of_vecs3 = vec_of_vecs;
273   EXPECT_EQ(4u, vec_of_vecs3.size());
274   EXPECT_EQ(vec_of_vecs3[0], data[0]);
275   EXPECT_EQ(vec_of_vecs3[1], data[1]);
276   EXPECT_TRUE(vec_of_vecs3[2].empty());
277   EXPECT_TRUE(vec_of_vecs3[3].empty());
278 
279   // Move-construction.
280   InplaceVector<std::vector<int>, 4> vec_of_vecs4 = std::move(vec_of_vecs);
281   EXPECT_EQ(4u, vec_of_vecs4.size());
282   EXPECT_EQ(vec_of_vecs4[0], data[0]);
283   EXPECT_EQ(vec_of_vecs4[1], data[1]);
284   EXPECT_TRUE(vec_of_vecs4[2].empty());
285   EXPECT_TRUE(vec_of_vecs4[3].empty());
286 
287   // The elements of the original vector should have been moved-from.
288   EXPECT_EQ(4u, vec_of_vecs.size());
289   for (const auto &vec : vec_of_vecs) {
290     EXPECT_TRUE(vec.empty());
291   }
292 
293   // Move-assignment.
294   InplaceVector<std::vector<int>, 4> vec_of_vecs5;
295   vec_of_vecs5 = std::move(vec_of_vecs4);
296   EXPECT_EQ(4u, vec_of_vecs5.size());
297   EXPECT_EQ(vec_of_vecs5[0], data[0]);
298   EXPECT_EQ(vec_of_vecs5[1], data[1]);
299   EXPECT_TRUE(vec_of_vecs5[2].empty());
300   EXPECT_TRUE(vec_of_vecs5[3].empty());
301 
302   // The elements of the original vector should have been moved-from.
303   EXPECT_EQ(4u, vec_of_vecs4.size());
304   for (const auto &vec : vec_of_vecs4) {
305     EXPECT_TRUE(vec.empty());
306   }
307 
308   std::vector<int> v = {42};
309   vec_of_vecs5.Resize(3);
310   EXPECT_TRUE(vec_of_vecs5.TryPushBack(v));
311   EXPECT_EQ(v, vec_of_vecs5[3]);
312   EXPECT_FALSE(vec_of_vecs5.TryPushBack(v));
313 }
314 
TEST(InplaceVectorTest,EraseIf)315 TEST(InplaceVectorTest, EraseIf) {
316   // Test that EraseIf never causes a self-move, and also correctly works with
317   // a move-only type that cannot be default-constructed.
318   class NoSelfMove {
319    public:
320     explicit NoSelfMove(int v) : v_(std::make_unique<int>(v)) {}
321     NoSelfMove(NoSelfMove &&other) { *this = std::move(other); }
322     NoSelfMove &operator=(NoSelfMove &&other) {
323       BSSL_CHECK(this != &other);
324       v_ = std::move(other.v_);
325       return *this;
326     }
327 
328     int value() const { return *v_; }
329 
330    private:
331     std::unique_ptr<int> v_;
332   };
333 
334   InplaceVector<NoSelfMove, 8> vec;
335   auto reset = [&] {
336     vec.clear();
337     for (int i = 0; i < 8; i++) {
338       vec.PushBack(NoSelfMove(i));
339     }
340   };
341   auto expect = [&](const std::vector<int> &expected) {
342     ASSERT_EQ(vec.size(), expected.size());
343     for (size_t i = 0; i < vec.size(); i++) {
344       SCOPED_TRACE(i);
345       EXPECT_EQ(vec[i].value(), expected[i]);
346     }
347   };
348 
349   reset();
350   vec.EraseIf([](const auto &) { return false; });
351   expect({0, 1, 2, 3, 4, 5, 6, 7});
352 
353   reset();
354   vec.EraseIf([](const auto &) { return true; });
355   expect({});
356 
357   reset();
358   vec.EraseIf([](const auto &v) { return v.value() < 4; });
359   expect({4, 5, 6, 7});
360 
361   reset();
362   vec.EraseIf([](const auto &v) { return v.value() >= 4; });
363   expect({0, 1, 2, 3});
364 
365   reset();
366   vec.EraseIf([](const auto &v) { return v.value() % 2 == 0; });
367   expect({1, 3, 5, 7});
368 
369   reset();
370   vec.EraseIf([](const auto &v) { return v.value() % 2 == 1; });
371   expect({0, 2, 4, 6});
372 
373   reset();
374   vec.EraseIf([](const auto &v) { return 2 <= v.value() && v.value() <= 5; });
375   expect({0, 1, 6, 7});
376 
377   reset();
378   vec.EraseIf([](const auto &v) { return v.value() == 0; });
379   expect({1, 2, 3, 4, 5, 6, 7});
380 
381   reset();
382   vec.EraseIf([](const auto &v) { return v.value() == 4; });
383   expect({0, 1, 2, 3, 5, 6, 7});
384 
385   reset();
386   vec.EraseIf([](const auto &v) { return v.value() == 7; });
387   expect({0, 1, 2, 3, 4, 5, 6});
388 }
389 
TEST(InplaceVectorDeathTest,BoundsChecks)390 TEST(InplaceVectorDeathTest, BoundsChecks) {
391   InplaceVector<int, 4> vec;
392   // The vector is currently empty.
393   EXPECT_DEATH_IF_SUPPORTED(vec[0], "");
394   EXPECT_DEATH_IF_SUPPORTED(vec.front(), "");
395   EXPECT_DEATH_IF_SUPPORTED(vec.back(), "");
396   EXPECT_DEATH_IF_SUPPORTED(vec.pop_back(), "");
397   int data[] = {1, 2, 3};
398   vec.CopyFrom(data);
399   // Some more out-of-bounds elements.
400   EXPECT_DEATH_IF_SUPPORTED(vec[3], "");
401   EXPECT_DEATH_IF_SUPPORTED(vec[4], "");
402   EXPECT_DEATH_IF_SUPPORTED(vec[1000], "");
403   // The vector cannot be resized past the capacity.
404   EXPECT_DEATH_IF_SUPPORTED(vec.Resize(5), "");
405   EXPECT_DEATH_IF_SUPPORTED(vec.ResizeForOverwrite(5), "");
406   int too_much_data[] = {1, 2, 3, 4, 5};
407   EXPECT_DEATH_IF_SUPPORTED(vec.CopyFrom(too_much_data), "");
408   vec.Resize(4);
409   EXPECT_DEATH_IF_SUPPORTED(vec.PushBack(42), "");
410 }
411 
412 }  // namespace
413 BSSL_NAMESPACE_END
414 #endif  // !BORINGSSL_SHARED_LIBRARY
415