1 // Copyright 2024 The Chromium Authors
2 // Use of this source code is governed by a BSD-style license that can be
3 // found in the LICENSE file.
4
5 #include "base/containers/heap_array.h"
6
7 #include <stdint.h>
8
9 #include <algorithm>
10 #include <type_traits>
11
12 #include "base/containers/span.h"
13 #include "base/memory/raw_ptr_exclusion.h"
14 #include "base/test/gtest_util.h"
15 #include "testing/gmock/include/gmock/gmock.h"
16 #include "testing/gtest/include/gtest/gtest.h"
17
18 using ::testing::ElementsAre;
19 using ::testing::IsEmpty;
20
21 namespace base {
22
23 namespace {
24
25 class DestructCounter {
26 public:
27 DestructCounter() = default;
~DestructCounter()28 ~DestructCounter() {
29 if (where_) {
30 (*where_)++;
31 }
32 }
33
set_where(size_t * where)34 void set_where(size_t* where) { where_ = where; }
35
36 private:
37 // RAW_PTR_EXCLUSION: Stack location only.
38 RAW_PTR_EXCLUSION size_t* where_ = nullptr;
39 };
40
CStyleInvoker(void (* cb)(void *),void * arg)41 extern "C" void CStyleInvoker(void (*cb)(void*), void* arg) {
42 (*cb)(arg);
43 }
44
45 } // namespace
46
TEST(HeapArray,DefaultConstructor)47 TEST(HeapArray, DefaultConstructor) {
48 HeapArray<uint32_t> vec;
49 EXPECT_TRUE(vec.empty());
50 EXPECT_EQ(vec.size(), 0u);
51 EXPECT_EQ(vec.data(), nullptr);
52 }
53
TEST(HeapArray,WithSizeZero)54 TEST(HeapArray, WithSizeZero) {
55 auto vec = HeapArray<uint32_t>::WithSize(0u);
56 EXPECT_EQ(vec.size(), 0u);
57 EXPECT_EQ(vec.data(), nullptr);
58 }
59
TEST(HeapArray,WithSizeNonZero)60 TEST(HeapArray, WithSizeNonZero) {
61 auto vec = HeapArray<uint32_t>::WithSize(2u);
62 EXPECT_EQ(vec.size(), 2u);
63 EXPECT_NE(vec.data(), nullptr);
64 }
65
TEST(HeapArray,FromOwningPointer)66 TEST(HeapArray, FromOwningPointer) {
67 auto vec = UNSAFE_BUFFERS(
68 HeapArray<uint32_t>::FromOwningPointer(new uint32_t[3], 3u));
69 EXPECT_EQ(vec.size(), 3u);
70 EXPECT_NE(vec.data(), nullptr);
71 }
72
TEST(HeapArray,MoveConstructor)73 TEST(HeapArray, MoveConstructor) {
74 auto that = HeapArray<uint32_t>::WithSize(2u);
75 base::HeapArray<uint32_t> vec(std::move(that));
76 EXPECT_EQ(vec.size(), 2u);
77 EXPECT_NE(vec.data(), nullptr);
78 EXPECT_EQ(that.size(), 0u);
79 EXPECT_EQ(that.data(), nullptr);
80 }
81
TEST(HeapArray,MoveAssign)82 TEST(HeapArray, MoveAssign) {
83 auto that = HeapArray<uint32_t>::WithSize(2u);
84 auto vec = HeapArray<uint32_t>::WithSize(4u);
85 vec = std::move(that);
86 EXPECT_EQ(vec.size(), 2u);
87 EXPECT_NE(vec.data(), nullptr);
88 EXPECT_EQ(that.size(), 0u);
89 EXPECT_EQ(that.data(), nullptr);
90 }
91
TEST(HeapArray,DataAndIndex)92 TEST(HeapArray, DataAndIndex) {
93 HeapArray<uint32_t> empty;
94 EXPECT_EQ(nullptr, empty.data());
95
96 auto vec = HeapArray<uint32_t>::WithSize(2u);
97 vec[0] = 100u;
98 vec[1] = 101u;
99 auto span = vec.as_span();
100 EXPECT_EQ(span.data(), vec.data());
101 EXPECT_THAT(span, ElementsAre(100u, 101u));
102 }
103
TEST(HeapArray,IteratorAndIndex)104 TEST(HeapArray, IteratorAndIndex) {
105 const HeapArray<uint32_t> empty;
106 static_assert(
107 std::is_const_v<std::remove_reference_t<decltype(*empty.begin())>>);
108 static_assert(
109 std::is_const_v<std::remove_reference_t<decltype(*empty.end())>>);
110 EXPECT_EQ(empty.begin(), empty.end());
111
112 auto vec = HeapArray<uint32_t>::WithSize(2u);
113 static_assert(
114 !std::is_const_v<std::remove_reference_t<decltype(*vec.begin())>>);
115 static_assert(
116 !std::is_const_v<std::remove_reference_t<decltype(*vec.end())>>);
117 vec[0] = 100u;
118 vec[1] = 101u;
119 uint32_t expected = 100;
120 for (auto i : vec) {
121 EXPECT_EQ(i, expected);
122 ++expected;
123 }
124 EXPECT_EQ(expected, 102u);
125 }
126
TEST(HeapArrayDeathTest,BadIndex)127 TEST(HeapArrayDeathTest, BadIndex) {
128 auto vec = HeapArray<uint32_t>::WithSize(2u);
129 EXPECT_DEATH_IF_SUPPORTED(vec[2], "");
130 }
131
TEST(HeapArray,AsSpan)132 TEST(HeapArray, AsSpan) {
133 {
134 auto vec = HeapArray<uint32_t>::WithSize(2u);
135 auto s = vec.as_span();
136 static_assert(std::same_as<decltype(s), span<uint32_t>>);
137 EXPECT_EQ(s.size(), 2u);
138 EXPECT_EQ(s.data(), vec.data());
139 }
140 {
141 const auto vec = HeapArray<uint32_t>::WithSize(2u);
142 auto s = vec.as_span();
143 static_assert(std::same_as<decltype(s), span<const uint32_t>>);
144 EXPECT_EQ(s.size(), 2u);
145 EXPECT_EQ(s.data(), vec.data());
146 }
147 }
148
TEST(HeapArray,Subspan)149 TEST(HeapArray, Subspan) {
150 auto vec = HeapArray<uint32_t>::WithSize(4u);
151 for (size_t i = 0; i < vec.size(); ++i) {
152 vec[i] = i;
153 }
154 span<uint32_t> empty = vec.subspan(2, 0);
155 EXPECT_THAT(empty, IsEmpty());
156
157 span<uint32_t> first = vec.subspan(0, 1);
158 EXPECT_THAT(first, ElementsAre(0u));
159
160 span<uint32_t> mids = vec.subspan(1, 2);
161 EXPECT_THAT(mids, ElementsAre(1u, 2u));
162
163 span<uint32_t> rest = vec.subspan(3);
164 EXPECT_THAT(rest, ElementsAre(3u));
165 }
166
TEST(HeapArray,First)167 TEST(HeapArray, First) {
168 auto vec = HeapArray<uint32_t>::WithSize(4u);
169 for (size_t i = 0; i < vec.size(); ++i) {
170 vec[i] = i;
171 }
172 span<uint32_t> empty = vec.first(0u);
173 EXPECT_THAT(empty, IsEmpty());
174
175 span<uint32_t> some = vec.first(2u);
176 EXPECT_THAT(some, ElementsAre(0u, 1u));
177 }
178
TEST(HeapArray,Last)179 TEST(HeapArray, Last) {
180 auto vec = HeapArray<uint32_t>::WithSize(4u);
181 for (size_t i = 0; i < vec.size(); ++i) {
182 vec[i] = i;
183 }
184 span<uint32_t> empty = vec.first(0u);
185 EXPECT_THAT(empty, IsEmpty());
186
187 span<uint32_t> some = vec.first(2u);
188 EXPECT_THAT(some, ElementsAre(0u, 1u));
189 }
190
TEST(HeapArray,Init)191 TEST(HeapArray, Init) {
192 auto vec = HeapArray<uint32_t>::WithSize(200);
193 EXPECT_EQ(0u, vec[0]);
194 EXPECT_EQ(0u, vec[199]);
195
196 uint32_t accumulator = 0;
197 for (auto i : vec) {
198 accumulator |= i;
199 }
200 EXPECT_EQ(0u, accumulator);
201 }
202
TEST(HeapArray,Uninit)203 TEST(HeapArray, Uninit) {
204 auto vec = HeapArray<uint32_t>::Uninit(4);
205 vec[0] = 100u;
206 vec[1] = 101u;
207 EXPECT_EQ(100u, vec[0]);
208 EXPECT_EQ(101u, vec[1]);
209 #if defined(MEMORY_SANITIZER)
210 // TODO(tsepez): figure out how to get a msan crash here.
211 // volatile uint32_t* x = vec.data() + 2;
212 // EXPECT_DEATH(*x, "");
213 #endif
214 }
215
TEST(HeapArray,Fill)216 TEST(HeapArray, Fill) {
217 auto vec = HeapArray<uint32_t>::Uninit(4);
218 std::ranges::fill(vec, 0x76543210);
219 EXPECT_EQ(0x76543210u, vec[0]);
220 EXPECT_EQ(0x76543210u, vec[1]);
221 EXPECT_EQ(0x76543210u, vec[2]);
222 EXPECT_EQ(0x76543210u, vec[3]);
223 }
224
TEST(HeapArray,CopiedFrom)225 TEST(HeapArray, CopiedFrom) {
226 span<uint32_t> empty_span;
227 auto empty_vec = HeapArray<uint32_t>::CopiedFrom(empty_span);
228 EXPECT_EQ(0u, empty_vec.size());
229
230 const uint32_t kData[] = {1000u, 1001u};
231 auto vec = HeapArray<uint32_t>::CopiedFrom(kData);
232 ASSERT_EQ(2u, vec.size());
233 EXPECT_EQ(1000u, vec[0]);
234 EXPECT_EQ(1001u, vec[1]);
235 }
236
TEST(HeapArray,RunsDestructor)237 TEST(HeapArray, RunsDestructor) {
238 size_t count = 0;
239 {
240 auto vec = HeapArray<DestructCounter>::WithSize(2);
241 vec[0].set_where(&count);
242 vec[1].set_where(&count);
243 EXPECT_EQ(count, 0u);
244 }
245 EXPECT_EQ(count, 2u);
246 }
247
TEST(HeapArray,CopyFrom)248 TEST(HeapArray, CopyFrom) {
249 HeapArray<uint32_t> empty;
250 HeapArray<uint32_t> something = HeapArray<uint32_t>::Uninit(2);
251 HeapArray<uint32_t> other = HeapArray<uint32_t>::Uninit(2);
252 const uint32_t kStuff[] = {1000u, 1001u};
253
254 empty.copy_from(span<uint32_t>()); // Should not check.
255 something.copy_from(kStuff);
256 EXPECT_EQ(1000u, something[0]);
257 EXPECT_EQ(1001u, something[1]);
258
259 other.copy_from(something);
260 EXPECT_EQ(1000u, other[0]);
261 EXPECT_EQ(1001u, other[1]);
262 }
263
TEST(HeapArrayDeathTest,CopyFrom)264 TEST(HeapArrayDeathTest, CopyFrom) {
265 HeapArray<uint32_t> empty;
266 HeapArray<uint32_t> something = HeapArray<uint32_t>::WithSize(2);
267 HeapArray<uint32_t> other = HeapArray<uint32_t>::WithSize(3);
268
269 EXPECT_DEATH_IF_SUPPORTED(empty.copy_from(something), "");
270 EXPECT_DEATH_IF_SUPPORTED(something.copy_from(empty), "");
271 EXPECT_DEATH_IF_SUPPORTED(other.copy_from(something), "");
272 EXPECT_DEATH_IF_SUPPORTED(something.copy_from(other), "");
273 }
274
TEST(HeapArray,CopyPrefixFrom)275 TEST(HeapArray, CopyPrefixFrom) {
276 HeapArray<uint32_t> empty;
277 HeapArray<uint32_t> something = HeapArray<uint32_t>::WithSize(3);
278 const uint32_t kStuff[] = {1000u, 1001u};
279
280 something.copy_prefix_from(kStuff);
281 EXPECT_EQ(1000u, something[0]);
282 EXPECT_EQ(1001u, something[1]);
283 EXPECT_EQ(0u, something[2]);
284
285 empty.copy_prefix_from(span<uint32_t>()); // Should not check.
286 something.copy_prefix_from(empty);
287 EXPECT_EQ(1000u, something[0]);
288 EXPECT_EQ(1001u, something[1]);
289 EXPECT_EQ(0u, something[2]);
290 }
291
TEST(HeapArrayDeathTest,CopyPrefixFrom)292 TEST(HeapArrayDeathTest, CopyPrefixFrom) {
293 HeapArray<uint32_t> empty;
294 HeapArray<uint32_t> something = HeapArray<uint32_t>::WithSize(2);
295 HeapArray<uint32_t> other = HeapArray<uint32_t>::WithSize(3);
296
297 EXPECT_DEATH_IF_SUPPORTED(empty.copy_prefix_from(something), "");
298 EXPECT_DEATH_IF_SUPPORTED(something.copy_prefix_from(other), "");
299 }
300
TEST(HeapArray,Leak)301 TEST(HeapArray, Leak) {
302 size_t count = 0;
303 span<DestructCounter> leaked;
304 {
305 auto vec = HeapArray<DestructCounter>::WithSize(2);
306 vec[0].set_where(&count);
307 vec[1].set_where(&count);
308
309 auto* data = vec.data();
310 leaked = std::move(vec).leak();
311 ASSERT_EQ(data, leaked.data());
312 EXPECT_EQ(count, 0u);
313 }
314 EXPECT_EQ(count, 0u);
315 CStyleInvoker(HeapArray<DestructCounter>::DeleteLeakedData, leaked.data());
316 EXPECT_EQ(count, 2u);
317 }
318
TEST(HeapArray,TakeFirst)319 TEST(HeapArray, TakeFirst) {
320 auto that = HeapArray<uint32_t>::WithSize(2u);
321 auto* that_data = that.data();
322 auto smaller_that = std::move(that).take_first(1u);
323 EXPECT_EQ(smaller_that.size(), 1u);
324 EXPECT_EQ(that_data, smaller_that.data());
325 EXPECT_EQ(that.size(), 0u);
326 EXPECT_EQ(that.data(), nullptr);
327 }
328
TEST(HeapArray,TakeFirstWithZeroSize)329 TEST(HeapArray, TakeFirstWithZeroSize) {
330 auto that = HeapArray<uint32_t>::WithSize(2u);
331 auto smaller_that = std::move(that).take_first(0u);
332 EXPECT_EQ(smaller_that.size(), 0u);
333 EXPECT_EQ(smaller_that.data(), nullptr);
334 EXPECT_EQ(that.size(), 0u);
335 EXPECT_EQ(that.data(), nullptr);
336 }
337
TEST(HeapArrayDeathTest,TakeFirstWithOverSize)338 TEST(HeapArrayDeathTest, TakeFirstWithOverSize) {
339 auto that = HeapArray<uint32_t>::WithSize(2u);
340 EXPECT_CHECK_DEATH(std::move(that).take_first(3u));
341 }
342
343 } // namespace base
344