1 /* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 2 -*- */
2 /* vim: set ts=8 sts=2 et sw=2 tw=80: */
3 /* This Source Code Form is subject to the terms of the Mozilla Public
4 * License, v. 2.0. If a copy of the MPL was not distributed with this
5 * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
6
7 #include "nsTArray.h"
8 #include "gtest/gtest.h"
9 #include "mozilla/ArrayUtils.h"
10 #include "mozilla/RefPtr.h"
11 #include "nsTHashMap.h"
12
13 using namespace mozilla;
14
15 namespace TestTArray {
16
17 struct Copyable {
CopyableTestTArray::Copyable18 Copyable() : mDestructionCounter(nullptr) {}
19
~CopyableTestTArray::Copyable20 ~Copyable() {
21 if (mDestructionCounter) {
22 (*mDestructionCounter)++;
23 }
24 }
25
26 Copyable(const Copyable&) = default;
27 Copyable& operator=(const Copyable&) = default;
28
29 uint32_t* mDestructionCounter;
30 };
31
32 struct Movable {
MovableTestTArray::Movable33 Movable() : mDestructionCounter(nullptr) {}
34
~MovableTestTArray::Movable35 ~Movable() {
36 if (mDestructionCounter) {
37 (*mDestructionCounter)++;
38 }
39 }
40
MovableTestTArray::Movable41 Movable(Movable&& aOther) : mDestructionCounter(aOther.mDestructionCounter) {
42 aOther.mDestructionCounter = nullptr;
43 }
44
45 uint32_t* mDestructionCounter;
46 };
47
48 } // namespace TestTArray
49
50 template <>
51 struct nsTArray_RelocationStrategy<TestTArray::Copyable> {
52 using Type = nsTArray_RelocateUsingMoveConstructor<TestTArray::Copyable>;
53 };
54
55 template <>
56 struct nsTArray_RelocationStrategy<TestTArray::Movable> {
57 using Type = nsTArray_RelocateUsingMoveConstructor<TestTArray::Movable>;
58 };
59
60 namespace TestTArray {
61
62 constexpr int dummyArrayData[] = {4, 1, 2, 8};
63
DummyArray()64 static const nsTArray<int>& DummyArray() {
65 static nsTArray<int> sArray;
66 if (sArray.IsEmpty()) {
67 sArray.AppendElements(dummyArrayData, ArrayLength(dummyArrayData));
68 }
69 return sArray;
70 }
71
72 // This returns an invalid nsTArray with a huge length in order to test that
73 // fallible operations actually fail.
74 #ifdef DEBUG
FakeHugeArray()75 static const nsTArray<int>& FakeHugeArray() {
76 static nsTArray<int> sArray;
77 if (sArray.IsEmpty()) {
78 sArray.AppendElement();
79 ((nsTArrayHeader*)sArray.DebugGetHeader())->mLength = UINT32_MAX;
80 }
81 return sArray;
82 }
83 #endif
84
TEST(TArray,int_AppendElements_PlainArray)85 TEST(TArray, int_AppendElements_PlainArray)
86 {
87 nsTArray<int> array;
88
89 int* ptr = array.AppendElements(dummyArrayData, ArrayLength(dummyArrayData));
90 ASSERT_EQ(&array[0], ptr);
91 ASSERT_EQ(DummyArray(), array);
92
93 ptr = array.AppendElements(dummyArrayData, ArrayLength(dummyArrayData));
94 ASSERT_EQ(&array[DummyArray().Length()], ptr);
95 nsTArray<int> expected;
96 expected.AppendElements(DummyArray());
97 expected.AppendElements(DummyArray());
98 ASSERT_EQ(expected, array);
99 }
100
TEST(TArray,int_AppendElements_PlainArray_Fallible)101 TEST(TArray, int_AppendElements_PlainArray_Fallible)
102 {
103 nsTArray<int> array;
104
105 int* ptr = array.AppendElements(dummyArrayData, ArrayLength(dummyArrayData),
106 fallible);
107 ASSERT_EQ(&array[0], ptr);
108 ASSERT_EQ(DummyArray(), array);
109
110 ptr = array.AppendElements(dummyArrayData, ArrayLength(dummyArrayData),
111 fallible);
112 ASSERT_EQ(&array[DummyArray().Length()], ptr);
113 nsTArray<int> expected;
114 expected.AppendElements(DummyArray());
115 expected.AppendElements(DummyArray());
116 ASSERT_EQ(expected, array);
117 }
118
TEST(TArray,int_AppendElements_TArray_Copy)119 TEST(TArray, int_AppendElements_TArray_Copy)
120 {
121 nsTArray<int> array;
122
123 const nsTArray<int> temp(DummyArray().Clone());
124 int* ptr = array.AppendElements(temp);
125 ASSERT_EQ(&array[0], ptr);
126 ASSERT_EQ(DummyArray(), array);
127 ASSERT_FALSE(temp.IsEmpty());
128
129 ptr = array.AppendElements(temp);
130 ASSERT_EQ(&array[DummyArray().Length()], ptr);
131 nsTArray<int> expected;
132 expected.AppendElements(DummyArray());
133 expected.AppendElements(DummyArray());
134 ASSERT_EQ(expected, array);
135 ASSERT_FALSE(temp.IsEmpty());
136 }
137
TEST(TArray,int_AppendElements_TArray_Copy_Fallible)138 TEST(TArray, int_AppendElements_TArray_Copy_Fallible)
139 {
140 nsTArray<int> array;
141
142 const nsTArray<int> temp(DummyArray().Clone());
143 int* ptr = array.AppendElements(temp, fallible);
144 ASSERT_EQ(&array[0], ptr);
145 ASSERT_EQ(DummyArray(), array);
146 ASSERT_FALSE(temp.IsEmpty());
147
148 ptr = array.AppendElements(temp, fallible);
149 ASSERT_EQ(&array[DummyArray().Length()], ptr);
150 nsTArray<int> expected;
151 expected.AppendElements(DummyArray());
152 expected.AppendElements(DummyArray());
153 ASSERT_EQ(expected, array);
154 ASSERT_FALSE(temp.IsEmpty());
155 }
156
TEST(TArray,int_AppendElements_TArray_Rvalue)157 TEST(TArray, int_AppendElements_TArray_Rvalue)
158 {
159 nsTArray<int> array;
160
161 nsTArray<int> temp(DummyArray().Clone());
162 int* ptr = array.AppendElements(std::move(temp));
163 ASSERT_EQ(&array[0], ptr);
164 ASSERT_EQ(DummyArray(), array);
165 ASSERT_TRUE(temp.IsEmpty());
166
167 temp = DummyArray().Clone();
168 ptr = array.AppendElements(std::move(temp));
169 ASSERT_EQ(&array[DummyArray().Length()], ptr);
170 nsTArray<int> expected;
171 expected.AppendElements(DummyArray());
172 expected.AppendElements(DummyArray());
173 ASSERT_EQ(expected, array);
174 ASSERT_TRUE(temp.IsEmpty());
175 }
176
TEST(TArray,int_AppendElements_TArray_Rvalue_Fallible)177 TEST(TArray, int_AppendElements_TArray_Rvalue_Fallible)
178 {
179 nsTArray<int> array;
180
181 nsTArray<int> temp(DummyArray().Clone());
182 int* ptr = array.AppendElements(std::move(temp), fallible);
183 ASSERT_EQ(&array[0], ptr);
184 ASSERT_EQ(DummyArray(), array);
185 ASSERT_TRUE(temp.IsEmpty());
186
187 temp = DummyArray().Clone();
188 ptr = array.AppendElements(std::move(temp), fallible);
189 ASSERT_EQ(&array[DummyArray().Length()], ptr);
190 nsTArray<int> expected;
191 expected.AppendElements(DummyArray());
192 expected.AppendElements(DummyArray());
193 ASSERT_EQ(expected, array);
194 ASSERT_TRUE(temp.IsEmpty());
195 }
196
TEST(TArray,int_AppendElements_FallibleArray_Rvalue)197 TEST(TArray, int_AppendElements_FallibleArray_Rvalue)
198 {
199 nsTArray<int> array;
200
201 FallibleTArray<int> temp;
202 ASSERT_TRUE(temp.AppendElements(DummyArray(), fallible));
203 int* ptr = array.AppendElements(std::move(temp));
204 ASSERT_EQ(&array[0], ptr);
205 ASSERT_EQ(DummyArray(), array);
206 ASSERT_TRUE(temp.IsEmpty());
207
208 ASSERT_TRUE(temp.AppendElements(DummyArray(), fallible));
209 ptr = array.AppendElements(std::move(temp));
210 ASSERT_EQ(&array[DummyArray().Length()], ptr);
211 nsTArray<int> expected;
212 expected.AppendElements(DummyArray());
213 expected.AppendElements(DummyArray());
214 ASSERT_EQ(expected, array);
215 ASSERT_TRUE(temp.IsEmpty());
216 }
217
TEST(TArray,int_AppendElements_FallibleArray_Rvalue_Fallible)218 TEST(TArray, int_AppendElements_FallibleArray_Rvalue_Fallible)
219 {
220 nsTArray<int> array;
221
222 FallibleTArray<int> temp;
223 ASSERT_TRUE(temp.AppendElements(DummyArray(), fallible));
224 int* ptr = array.AppendElements(std::move(temp), fallible);
225 ASSERT_EQ(&array[0], ptr);
226 ASSERT_EQ(DummyArray(), array);
227 ASSERT_TRUE(temp.IsEmpty());
228
229 ASSERT_TRUE(temp.AppendElements(DummyArray(), fallible));
230 ptr = array.AppendElements(std::move(temp), fallible);
231 ASSERT_EQ(&array[DummyArray().Length()], ptr);
232 nsTArray<int> expected;
233 expected.AppendElements(DummyArray());
234 expected.AppendElements(DummyArray());
235 ASSERT_EQ(expected, array);
236 ASSERT_TRUE(temp.IsEmpty());
237 }
238
TEST(TArray,AppendElementsSpan)239 TEST(TArray, AppendElementsSpan)
240 {
241 nsTArray<int> array;
242
243 nsTArray<int> temp(DummyArray().Clone());
244 Span<int> span = temp;
245 array.AppendElements(span);
246 ASSERT_EQ(DummyArray(), array);
247
248 Span<const int> constSpan = temp;
249 array.AppendElements(constSpan);
250 nsTArray<int> expected;
251 expected.AppendElements(DummyArray());
252 expected.AppendElements(DummyArray());
253 ASSERT_EQ(expected, array);
254 }
255
TEST(TArray,int_AppendElement_NoElementArg)256 TEST(TArray, int_AppendElement_NoElementArg)
257 {
258 nsTArray<int> array;
259 array.AppendElement();
260
261 ASSERT_EQ(1u, array.Length());
262 }
263
TEST(TArray,int_AppendElement_NoElementArg_Fallible)264 TEST(TArray, int_AppendElement_NoElementArg_Fallible)
265 {
266 nsTArray<int> array;
267 ASSERT_NE(nullptr, array.AppendElement(fallible));
268
269 ASSERT_EQ(1u, array.Length());
270 }
271
TEST(TArray,int_AppendElement_NoElementArg_Address)272 TEST(TArray, int_AppendElement_NoElementArg_Address)
273 {
274 nsTArray<int> array;
275 *array.AppendElement() = 42;
276
277 ASSERT_EQ(1u, array.Length());
278 ASSERT_EQ(42, array[0]);
279 }
280
TEST(TArray,int_AppendElement_NoElementArg_Fallible_Address)281 TEST(TArray, int_AppendElement_NoElementArg_Fallible_Address)
282 {
283 nsTArray<int> array;
284 *array.AppendElement(fallible) = 42;
285
286 ASSERT_EQ(1u, array.Length());
287 ASSERT_EQ(42, array[0]);
288 }
289
TEST(TArray,int_AppendElement_ElementArg)290 TEST(TArray, int_AppendElement_ElementArg)
291 {
292 nsTArray<int> array;
293 array.AppendElement(42);
294
295 ASSERT_EQ(1u, array.Length());
296 ASSERT_EQ(42, array[0]);
297 }
298
TEST(TArray,int_AppendElement_ElementArg_Fallible)299 TEST(TArray, int_AppendElement_ElementArg_Fallible)
300 {
301 nsTArray<int> array;
302 ASSERT_NE(nullptr, array.AppendElement(42, fallible));
303
304 ASSERT_EQ(1u, array.Length());
305 ASSERT_EQ(42, array[0]);
306 }
307
308 constexpr size_t dummyMovableArrayLength = 4;
309 uint32_t dummyMovableArrayDestructorCounter;
310
DummyMovableArray()311 static nsTArray<Movable> DummyMovableArray() {
312 nsTArray<Movable> res;
313 res.SetLength(dummyMovableArrayLength);
314 for (size_t i = 0; i < dummyMovableArrayLength; ++i) {
315 res[i].mDestructionCounter = &dummyMovableArrayDestructorCounter;
316 }
317 return res;
318 }
319
TEST(TArray,Movable_AppendElements_TArray_Rvalue)320 TEST(TArray, Movable_AppendElements_TArray_Rvalue)
321 {
322 dummyMovableArrayDestructorCounter = 0;
323 {
324 nsTArray<Movable> array;
325
326 nsTArray<Movable> temp(DummyMovableArray());
327 Movable* ptr = array.AppendElements(std::move(temp));
328 ASSERT_EQ(&array[0], ptr);
329 ASSERT_TRUE(temp.IsEmpty());
330
331 temp = DummyMovableArray();
332 ptr = array.AppendElements(std::move(temp));
333 ASSERT_EQ(&array[dummyMovableArrayLength], ptr);
334 ASSERT_TRUE(temp.IsEmpty());
335 }
336 ASSERT_EQ(2 * dummyMovableArrayLength, dummyMovableArrayDestructorCounter);
337 }
338
TEST(TArray,Movable_AppendElements_TArray_Rvalue_Fallible)339 TEST(TArray, Movable_AppendElements_TArray_Rvalue_Fallible)
340 {
341 dummyMovableArrayDestructorCounter = 0;
342 {
343 nsTArray<Movable> array;
344
345 nsTArray<Movable> temp(DummyMovableArray());
346 Movable* ptr = array.AppendElements(std::move(temp), fallible);
347 ASSERT_EQ(&array[0], ptr);
348 ASSERT_TRUE(temp.IsEmpty());
349
350 temp = DummyMovableArray();
351 ptr = array.AppendElements(std::move(temp), fallible);
352 ASSERT_EQ(&array[dummyMovableArrayLength], ptr);
353 ASSERT_TRUE(temp.IsEmpty());
354 }
355 ASSERT_EQ(2 * dummyMovableArrayLength, dummyMovableArrayDestructorCounter);
356 }
357
TEST(TArray,Movable_AppendElements_FallibleArray_Rvalue)358 TEST(TArray, Movable_AppendElements_FallibleArray_Rvalue)
359 {
360 dummyMovableArrayDestructorCounter = 0;
361 {
362 nsTArray<Movable> array;
363
364 FallibleTArray<Movable> temp(DummyMovableArray());
365 Movable* ptr = array.AppendElements(std::move(temp));
366 ASSERT_EQ(&array[0], ptr);
367 ASSERT_TRUE(temp.IsEmpty());
368
369 temp = DummyMovableArray();
370 ptr = array.AppendElements(std::move(temp));
371 ASSERT_EQ(&array[dummyMovableArrayLength], ptr);
372 ASSERT_TRUE(temp.IsEmpty());
373 }
374 ASSERT_EQ(2 * dummyMovableArrayLength, dummyMovableArrayDestructorCounter);
375 }
376
TEST(TArray,Movable_AppendElements_FallibleArray_Rvalue_Fallible)377 TEST(TArray, Movable_AppendElements_FallibleArray_Rvalue_Fallible)
378 {
379 dummyMovableArrayDestructorCounter = 0;
380 {
381 nsTArray<Movable> array;
382
383 FallibleTArray<Movable> temp(DummyMovableArray());
384 Movable* ptr = array.AppendElements(std::move(temp), fallible);
385 ASSERT_EQ(&array[0], ptr);
386 ASSERT_TRUE(temp.IsEmpty());
387
388 temp = DummyMovableArray();
389 ptr = array.AppendElements(std::move(temp), fallible);
390 ASSERT_EQ(&array[dummyMovableArrayLength], ptr);
391 ASSERT_TRUE(temp.IsEmpty());
392 }
393 ASSERT_EQ(2 * dummyMovableArrayLength, dummyMovableArrayDestructorCounter);
394 }
395
TEST(TArray,Movable_AppendElement_NoElementArg)396 TEST(TArray, Movable_AppendElement_NoElementArg)
397 {
398 nsTArray<Movable> array;
399 array.AppendElement();
400
401 ASSERT_EQ(1u, array.Length());
402 }
403
TEST(TArray,Movable_AppendElement_NoElementArg_Fallible)404 TEST(TArray, Movable_AppendElement_NoElementArg_Fallible)
405 {
406 nsTArray<Movable> array;
407 ASSERT_NE(nullptr, array.AppendElement(fallible));
408
409 ASSERT_EQ(1u, array.Length());
410 }
411
TEST(TArray,Movable_AppendElement_NoElementArg_Address)412 TEST(TArray, Movable_AppendElement_NoElementArg_Address)
413 {
414 dummyMovableArrayDestructorCounter = 0;
415 {
416 nsTArray<Movable> array;
417 array.AppendElement()->mDestructionCounter =
418 &dummyMovableArrayDestructorCounter;
419
420 ASSERT_EQ(1u, array.Length());
421 }
422 ASSERT_EQ(1u, dummyMovableArrayDestructorCounter);
423 }
424
TEST(TArray,Movable_AppendElement_NoElementArg_Fallible_Address)425 TEST(TArray, Movable_AppendElement_NoElementArg_Fallible_Address)
426 {
427 dummyMovableArrayDestructorCounter = 0;
428 {
429 nsTArray<Movable> array;
430 array.AppendElement(fallible)->mDestructionCounter =
431 &dummyMovableArrayDestructorCounter;
432
433 ASSERT_EQ(1u, array.Length());
434 ASSERT_EQ(&dummyMovableArrayDestructorCounter,
435 array[0].mDestructionCounter);
436 }
437 ASSERT_EQ(1u, dummyMovableArrayDestructorCounter);
438 }
439
TEST(TArray,Movable_AppendElement_ElementArg)440 TEST(TArray, Movable_AppendElement_ElementArg)
441 {
442 dummyMovableArrayDestructorCounter = 0;
443 Movable movable;
444 movable.mDestructionCounter = &dummyMovableArrayDestructorCounter;
445 {
446 nsTArray<Movable> array;
447 array.AppendElement(std::move(movable));
448
449 ASSERT_EQ(1u, array.Length());
450 ASSERT_EQ(&dummyMovableArrayDestructorCounter,
451 array[0].mDestructionCounter);
452 }
453 ASSERT_EQ(1u, dummyMovableArrayDestructorCounter);
454 }
455
TEST(TArray,Movable_AppendElement_ElementArg_Fallible)456 TEST(TArray, Movable_AppendElement_ElementArg_Fallible)
457 {
458 dummyMovableArrayDestructorCounter = 0;
459 Movable movable;
460 movable.mDestructionCounter = &dummyMovableArrayDestructorCounter;
461 {
462 nsTArray<Movable> array;
463 ASSERT_NE(nullptr, array.AppendElement(std::move(movable), fallible));
464
465 ASSERT_EQ(1u, array.Length());
466 ASSERT_EQ(&dummyMovableArrayDestructorCounter,
467 array[0].mDestructionCounter);
468 }
469 ASSERT_EQ(1u, dummyMovableArrayDestructorCounter);
470 }
471
TEST(TArray,int_Assign)472 TEST(TArray, int_Assign)
473 {
474 nsTArray<int> array;
475 array.Assign(DummyArray());
476 ASSERT_EQ(DummyArray(), array);
477
478 ASSERT_TRUE(array.Assign(DummyArray(), fallible));
479 ASSERT_EQ(DummyArray(), array);
480
481 #ifdef DEBUG
482 ASSERT_FALSE(array.Assign(FakeHugeArray(), fallible));
483 #endif
484
485 nsTArray<int> array2;
486 array2.Assign(std::move(array));
487 ASSERT_TRUE(array.IsEmpty());
488 ASSERT_EQ(DummyArray(), array2);
489 }
490
TEST(TArray,int_Assign_FromEmpty_ToNonEmpty)491 TEST(TArray, int_Assign_FromEmpty_ToNonEmpty)
492 {
493 nsTArray<int> array;
494 array.AppendElement(42);
495
496 const nsTArray<int> empty;
497 array.Assign(empty);
498
499 ASSERT_TRUE(array.IsEmpty());
500 }
501
TEST(TArray,int_Assign_FromEmpty_ToNonEmpty_Fallible)502 TEST(TArray, int_Assign_FromEmpty_ToNonEmpty_Fallible)
503 {
504 nsTArray<int> array;
505 array.AppendElement(42);
506
507 const nsTArray<int> empty;
508 ASSERT_TRUE(array.Assign(empty, fallible));
509
510 ASSERT_TRUE(array.IsEmpty());
511 }
512
TEST(TArray,int_AssignmentOperatorSelfAssignment)513 TEST(TArray, int_AssignmentOperatorSelfAssignment)
514 {
515 CopyableTArray<int> array;
516 array = DummyArray();
517
518 array = *&array;
519 ASSERT_EQ(DummyArray(), array);
520
521 #if defined(__clang__)
522 # pragma clang diagnostic push
523 # pragma clang diagnostic ignored "-Wself-move"
524 #endif
525 array = std::move(array); // self-move
526 ASSERT_EQ(DummyArray(), array);
527 #if defined(__clang__)
528 # pragma clang diagnostic pop
529 #endif
530 }
531
TEST(TArray,Movable_CopyOverlappingForwards)532 TEST(TArray, Movable_CopyOverlappingForwards)
533 {
534 const size_t rangeLength = 8;
535 const size_t initialLength = 2 * rangeLength;
536 uint32_t destructionCounters[initialLength];
537 nsTArray<Movable> array;
538 array.AppendElements(initialLength);
539
540 for (uint32_t i = 0; i < initialLength; ++i) {
541 destructionCounters[i] = 0;
542 }
543 for (uint32_t i = 0; i < initialLength; ++i) {
544 array[i].mDestructionCounter = &destructionCounters[i];
545 }
546
547 const size_t removedLength = rangeLength / 2;
548 array.RemoveElementsAt(0, removedLength);
549
550 for (uint32_t i = 0; i < removedLength; ++i) {
551 ASSERT_EQ(destructionCounters[i], 1u);
552 }
553 for (uint32_t i = removedLength; i < initialLength; ++i) {
554 ASSERT_EQ(destructionCounters[i], 0u);
555 }
556 }
557
558 // The code to copy overlapping regions had a bug in that it wouldn't correctly
559 // destroy all over the source elements being copied.
TEST(TArray,Copyable_CopyOverlappingBackwards)560 TEST(TArray, Copyable_CopyOverlappingBackwards)
561 {
562 const size_t rangeLength = 8;
563 const size_t initialLength = 2 * rangeLength;
564 uint32_t destructionCounters[initialLength];
565 nsTArray<Copyable> array;
566 array.SetCapacity(3 * rangeLength);
567 array.AppendElements(initialLength);
568 // To tickle the bug, we need to copy a source region:
569 //
570 // ..XXXXX..
571 //
572 // such that it overlaps the destination region:
573 //
574 // ....XXXXX
575 //
576 // so we are forced to copy back-to-front to ensure correct behavior.
577 // The easiest way to do that is to call InsertElementsAt, which will force
578 // the desired kind of shift.
579 for (uint32_t i = 0; i < initialLength; ++i) {
580 destructionCounters[i] = 0;
581 }
582 for (uint32_t i = 0; i < initialLength; ++i) {
583 array[i].mDestructionCounter = &destructionCounters[i];
584 }
585
586 array.InsertElementsAt(0, rangeLength);
587
588 for (uint32_t i = 0; i < initialLength; ++i) {
589 ASSERT_EQ(destructionCounters[i], 1u);
590 }
591 }
592
593 namespace {
594
595 class E {
596 public:
E()597 E() : mA(-1), mB(-2) { constructCount++; }
E(int a,int b)598 E(int a, int b) : mA(a), mB(b) { constructCount++; }
E(E && aRhs)599 E(E&& aRhs) : mA(aRhs.mA), mB(aRhs.mB) {
600 aRhs.mA = 0;
601 aRhs.mB = 0;
602 moveCount++;
603 }
604
operator =(E && aRhs)605 E& operator=(E&& aRhs) {
606 mA = aRhs.mA;
607 aRhs.mA = 0;
608 mB = aRhs.mB;
609 aRhs.mB = 0;
610 moveCount++;
611 return *this;
612 }
613
a() const614 int a() const { return mA; }
b() const615 int b() const { return mB; }
616
617 E(const E&) = delete;
618 E& operator=(const E&) = delete;
619
620 static size_t constructCount;
621 static size_t moveCount;
622
623 private:
624 int mA;
625 int mB;
626 };
627
628 size_t E::constructCount = 0;
629 size_t E::moveCount = 0;
630
631 } // namespace
632
TEST(TArray,Emplace)633 TEST(TArray, Emplace)
634 {
635 nsTArray<E> array;
636 array.SetCapacity(20);
637
638 ASSERT_EQ(array.Length(), 0u);
639
640 for (int i = 0; i < 10; i++) {
641 E s(i, i * i);
642 array.AppendElement(std::move(s));
643 }
644
645 ASSERT_EQ(array.Length(), 10u);
646 ASSERT_EQ(E::constructCount, 10u);
647 ASSERT_EQ(E::moveCount, 10u);
648
649 for (int i = 10; i < 20; i++) {
650 array.EmplaceBack(i, i * i);
651 }
652
653 ASSERT_EQ(array.Length(), 20u);
654 ASSERT_EQ(E::constructCount, 20u);
655 ASSERT_EQ(E::moveCount, 10u);
656
657 for (int i = 0; i < 20; i++) {
658 ASSERT_EQ(array[i].a(), i);
659 ASSERT_EQ(array[i].b(), i * i);
660 }
661
662 array.EmplaceBack();
663
664 ASSERT_EQ(array.Length(), 21u);
665 ASSERT_EQ(E::constructCount, 21u);
666 ASSERT_EQ(E::moveCount, 10u);
667
668 ASSERT_EQ(array[20].a(), -1);
669 ASSERT_EQ(array[20].b(), -2);
670 }
671
TEST(TArray,UnorderedRemoveElements)672 TEST(TArray, UnorderedRemoveElements)
673 {
674 // When removing an element from the end of the array, it can be removed in
675 // place, by destroying it and decrementing the length.
676 //
677 // [ 1, 2, 3 ] => [ 1, 2 ]
678 // ^
679 {
680 nsTArray<int> array{1, 2, 3};
681 array.UnorderedRemoveElementAt(2);
682
683 nsTArray<int> goal{1, 2};
684 ASSERT_EQ(array, goal);
685 }
686
687 // When removing any other single element, it is removed by swapping it with
688 // the last element, and then decrementing the length as before.
689 //
690 // [ 1, 2, 3, 4, 5, 6 ] => [ 1, 6, 3, 4, 5 ]
691 // ^
692 {
693 nsTArray<int> array{1, 2, 3, 4, 5, 6};
694 array.UnorderedRemoveElementAt(1);
695
696 nsTArray<int> goal{1, 6, 3, 4, 5};
697 ASSERT_EQ(array, goal);
698 }
699
700 // This method also supports efficiently removing a range of elements. If they
701 // are at the end, then they can all be removed like in the one element case.
702 //
703 // [ 1, 2, 3, 4, 5, 6 ] => [ 1, 2 ]
704 // ^--------^
705 {
706 nsTArray<int> array{1, 2, 3, 4, 5, 6};
707 array.UnorderedRemoveElementsAt(2, 4);
708
709 nsTArray<int> goal{1, 2};
710 ASSERT_EQ(array, goal);
711 }
712
713 // If more elements are removed than exist after the removed section, the
714 // remaining elements will be shifted down like in a normal removal.
715 //
716 // [ 1, 2, 3, 4, 5, 6, 7, 8 ] => [ 1, 2, 7, 8 ]
717 // ^--------^
718 {
719 nsTArray<int> array{1, 2, 3, 4, 5, 6, 7, 8};
720 array.UnorderedRemoveElementsAt(2, 4);
721
722 nsTArray<int> goal{1, 2, 7, 8};
723 ASSERT_EQ(array, goal);
724 }
725
726 // And if fewer elements are removed than exist after the removed section,
727 // elements will be moved from the end of the array to fill the vacated space.
728 //
729 // [ 1, 2, 3, 4, 5, 6, 7, 8 ] => [ 1, 7, 8, 4, 5, 6 ]
730 // ^--^
731 {
732 nsTArray<int> array{1, 2, 3, 4, 5, 6, 7, 8};
733 array.UnorderedRemoveElementsAt(1, 2);
734
735 nsTArray<int> goal{1, 7, 8, 4, 5, 6};
736 ASSERT_EQ(array, goal);
737 }
738
739 // We should do the right thing if we drain the entire array.
740 {
741 nsTArray<int> array{1, 2, 3, 4, 5};
742 array.UnorderedRemoveElementsAt(0, 5);
743
744 nsTArray<int> goal{};
745 ASSERT_EQ(array, goal);
746 }
747
748 {
749 nsTArray<int> array{1};
750 array.UnorderedRemoveElementAt(0);
751
752 nsTArray<int> goal{};
753 ASSERT_EQ(array, goal);
754 }
755
756 // We should do the right thing if we remove the same number of elements that
757 // we have remaining.
758 {
759 nsTArray<int> array{1, 2, 3, 4, 5, 6};
760 array.UnorderedRemoveElementsAt(2, 2);
761
762 nsTArray<int> goal{1, 2, 5, 6};
763 ASSERT_EQ(array, goal);
764 }
765
766 {
767 nsTArray<int> array{1, 2, 3};
768 array.UnorderedRemoveElementAt(1);
769
770 nsTArray<int> goal{1, 3};
771 ASSERT_EQ(array, goal);
772 }
773
774 // We should be able to remove elements from the front without issue.
775 {
776 nsTArray<int> array{1, 2, 3, 4, 5, 6};
777 array.UnorderedRemoveElementsAt(0, 2);
778
779 nsTArray<int> goal{5, 6, 3, 4};
780 ASSERT_EQ(array, goal);
781 }
782
783 {
784 nsTArray<int> array{1, 2, 3, 4};
785 array.UnorderedRemoveElementAt(0);
786
787 nsTArray<int> goal{4, 2, 3};
788 ASSERT_EQ(array, goal);
789 }
790 }
791
TEST(TArray,RemoveFromEnd)792 TEST(TArray, RemoveFromEnd)
793 {
794 {
795 nsTArray<int> array{1, 2, 3, 4};
796 ASSERT_EQ(array.PopLastElement(), 4);
797 array.RemoveLastElement();
798 ASSERT_EQ(array.PopLastElement(), 2);
799 array.RemoveLastElement();
800 ASSERT_TRUE(array.IsEmpty());
801 }
802 }
803
TEST(TArray,ConvertIteratorToConstIterator)804 TEST(TArray, ConvertIteratorToConstIterator)
805 {
806 nsTArray<int> array{1, 2, 3, 4};
807
808 nsTArray<int>::const_iterator it = array.begin();
809 ASSERT_EQ(array.cbegin(), it);
810 }
811
TEST(TArray,RemoveElementAt_ByIterator)812 TEST(TArray, RemoveElementAt_ByIterator)
813 {
814 nsTArray<int> array{1, 2, 3, 4};
815 const auto it = std::find(array.begin(), array.end(), 3);
816 const auto itAfter = array.RemoveElementAt(it);
817
818 // Based on the implementation of the iterator, we could compare it and
819 // itAfter, but we should not rely on such implementation details.
820
821 ASSERT_EQ(2, std::distance(array.cbegin(), itAfter));
822 const nsTArray<int> expected{1, 2, 4};
823 ASSERT_EQ(expected, array);
824 }
825
TEST(TArray,RemoveElementsRange_ByIterator)826 TEST(TArray, RemoveElementsRange_ByIterator)
827 {
828 nsTArray<int> array{1, 2, 3, 4};
829 const auto it = std::find(array.begin(), array.end(), 3);
830 const auto itAfter = array.RemoveElementsRange(it, array.end());
831
832 // Based on the implementation of the iterator, we could compare it and
833 // itAfter, but we should not rely on such implementation details.
834
835 ASSERT_EQ(2, std::distance(array.cbegin(), itAfter));
836 const nsTArray<int> expected{1, 2};
837 ASSERT_EQ(expected, array);
838 }
839
TEST(TArray,RemoveLastElements_None)840 TEST(TArray, RemoveLastElements_None)
841 {
842 const nsTArray<int> original{1, 2, 3, 4};
843 nsTArray<int> array = original.Clone();
844 array.RemoveLastElements(0);
845
846 ASSERT_EQ(original, array);
847 }
848
TEST(TArray,RemoveLastElements_Empty_None)849 TEST(TArray, RemoveLastElements_Empty_None)
850 {
851 nsTArray<int> array;
852 array.RemoveLastElements(0);
853
854 ASSERT_EQ(0u, array.Length());
855 }
856
TEST(TArray,RemoveLastElements_All)857 TEST(TArray, RemoveLastElements_All)
858 {
859 nsTArray<int> array{1, 2, 3, 4};
860 array.RemoveLastElements(4);
861
862 ASSERT_EQ(0u, array.Length());
863 }
864
TEST(TArray,RemoveLastElements_One)865 TEST(TArray, RemoveLastElements_One)
866 {
867 nsTArray<int> array{1, 2, 3, 4};
868 array.RemoveLastElements(1);
869
870 ASSERT_EQ((nsTArray<int>{1, 2, 3}), array);
871 }
872
873 static_assert(std::is_copy_assignable<decltype(MakeBackInserter(
874 std::declval<nsTArray<int>&>()))>::value,
875 "output iteraror must be copy-assignable");
876 static_assert(std::is_copy_constructible<decltype(MakeBackInserter(
877 std::declval<nsTArray<int>&>()))>::value,
878 "output iterator must be copy-constructible");
879
TEST(TArray,MakeBackInserter)880 TEST(TArray, MakeBackInserter)
881 {
882 const std::vector<int> src{1, 2, 3, 4};
883 nsTArray<int> dst;
884
885 std::copy(src.begin(), src.end(), MakeBackInserter(dst));
886
887 const nsTArray<int> expected{1, 2, 3, 4};
888 ASSERT_EQ(expected, dst);
889 }
890
TEST(TArray,MakeBackInserter_Move)891 TEST(TArray, MakeBackInserter_Move)
892 {
893 uint32_t destructionCounter = 0;
894
895 {
896 std::vector<Movable> src(1);
897 src[0].mDestructionCounter = &destructionCounter;
898
899 nsTArray<Movable> dst;
900
901 std::copy(std::make_move_iterator(src.begin()),
902 std::make_move_iterator(src.end()), MakeBackInserter(dst));
903
904 ASSERT_EQ(1u, dst.Length());
905 ASSERT_EQ(0u, destructionCounter);
906 }
907
908 ASSERT_EQ(1u, destructionCounter);
909 }
910
TEST(TArray,ConvertToSpan)911 TEST(TArray, ConvertToSpan)
912 {
913 nsTArray<int> arr = {1, 2, 3, 4, 5};
914
915 // from const
916 {
917 const auto& constArrRef = arr;
918
919 auto span = Span{constArrRef};
920 static_assert(std::is_same_v<decltype(span), Span<const int>>);
921 }
922
923 // from non-const
924 {
925 auto span = Span{arr};
926 static_assert(std::is_same_v<decltype(span), Span<int>>);
927 }
928 }
929
930 // This should compile:
931 struct RefCounted;
932
933 class Foo {
934 ~Foo(); // Intentionally out of line
935
936 nsTArray<RefPtr<RefCounted>> mArray;
937
GetFirst() const938 const RefCounted* GetFirst() const { return mArray.SafeElementAt(0); }
939 };
940
TEST(TArray,ArrayView)941 TEST(TArray, ArrayView)
942 {
943 const nsTArray<int> expected = {1, 2, 3, 4, 5};
944 const nsTArrayView<int> view(expected.Clone());
945
946 nsTArray<int> fromSpan;
947 fromSpan.AppendElements(view.AsSpan());
948 EXPECT_EQ(expected, fromSpan);
949
950 for (auto& element : view) {
951 element++;
952 }
953
954 int i = 2;
955 for (const auto& element : view) {
956 EXPECT_EQ(i++, element);
957 }
958 }
959
TEST(TArray,StableSort)960 TEST(TArray, StableSort)
961 {
962 const nsTArray<std::pair<int, int>> expected = {
963 std::pair(1, 9), std::pair(1, 8), std::pair(1, 7), std::pair(2, 0),
964 std::pair(3, 0)};
965 nsTArray<std::pair<int, int>> array = {std::pair(1, 9), std::pair(2, 0),
966 std::pair(1, 8), std::pair(3, 0),
967 std::pair(1, 7)};
968
969 array.StableSort([](std::pair<int, int> left, std::pair<int, int> right) {
970 return left.first - right.first;
971 });
972
973 EXPECT_EQ(expected, array);
974 }
975
TEST(TArray,ToArray)976 TEST(TArray, ToArray)
977 {
978 const auto src = std::array{0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
979
980 nsTArray<int> keys = ToArray(src);
981 keys.Sort();
982
983 EXPECT_EQ((nsTArray<int>{0, 1, 2, 3, 4, 5, 6, 7, 8, 9}), keys);
984 }
985
986 // Test this to make sure this properly uses ADL.
TEST(TArray,ToArray_HashMap)987 TEST(TArray, ToArray_HashMap)
988 {
989 nsTHashMap<uint32_t, uint64_t> src;
990
991 for (uint32_t i = 0; i < 10; ++i) {
992 src.InsertOrUpdate(i, i);
993 }
994
995 nsTArray<uint32_t> keys = ToArray(src.Keys());
996 keys.Sort();
997
998 EXPECT_EQ((nsTArray<uint32_t>{0, 1, 2, 3, 4, 5, 6, 7, 8, 9}), keys);
999 }
1000
TEST(TArray,ToTArray)1001 TEST(TArray, ToTArray)
1002 {
1003 const auto src = std::array{0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
1004
1005 auto keys = ToTArray<AutoTArray<uint64_t, 10>>(src);
1006 keys.Sort();
1007
1008 static_assert(std::is_same_v<decltype(keys), AutoTArray<uint64_t, 10>>);
1009
1010 EXPECT_EQ((nsTArray<uint64_t>{0, 1, 2, 3, 4, 5, 6, 7, 8, 9}), keys);
1011 }
1012
TEST(TArray,RemoveElementsBy)1013 TEST(TArray, RemoveElementsBy)
1014 {
1015 // Removing elements returns the correct number of removed elements.
1016 {
1017 nsTArray<int> array{8, 1, 1, 3, 3, 5, 2, 3};
1018 auto removed = array.RemoveElementsBy([](int i) { return i == 3; });
1019 EXPECT_EQ(removed, 3u);
1020
1021 nsTArray<int> goal{8, 1, 1, 5, 2};
1022 EXPECT_EQ(array, goal);
1023 }
1024
1025 // The check is called in order.
1026 {
1027 int index = 0;
1028 nsTArray<int> array{0, 1, 2, 3, 4, 5};
1029 auto removed = array.RemoveElementsBy([&](int i) {
1030 EXPECT_EQ(index, i);
1031 index++;
1032 return i == 3;
1033 });
1034 EXPECT_EQ(removed, 1u);
1035
1036 nsTArray<int> goal{0, 1, 2, 4, 5};
1037 EXPECT_EQ(array, goal);
1038 }
1039
1040 // Removing nothing works
1041 {
1042 nsTArray<int> array{0, 1, 2, 3, 4};
1043 auto removed = array.RemoveElementsBy([](int) { return false; });
1044 EXPECT_EQ(removed, 0u);
1045
1046 nsTArray<int> goal{0, 1, 2, 3, 4};
1047 EXPECT_EQ(array, goal);
1048 }
1049
1050 // Removing everything works
1051 {
1052 nsTArray<int> array{0, 1, 2, 3, 4};
1053 auto removed = array.RemoveElementsBy([](int) { return true; });
1054 EXPECT_EQ(removed, 5u);
1055
1056 nsTArray<int> goal{};
1057 EXPECT_EQ(array, goal);
1058 }
1059 }
1060
1061 } // namespace TestTArray
1062