OILS / mycpp / gc_list_test.cc View on Github | oils.pub

596 lines, 407 significant
1#include "mycpp/gc_list.h"
2
3#include <assert.h>
4#include <stdarg.h> // va_list, etc.
5#include <stdio.h> // vprintf
6
7#include "mycpp/common.h"
8#include "mycpp/gc_alloc.h" // gHeap
9#include "mycpp/gc_obj.h"
10#include "vendor/greatest.h"
11
12using mylib::str_cmp;
13
14GLOBAL_STR(kStrFoo, "foo");
15GLOBAL_STR(kSpace, " ");
16
17void Print(List<BigStr*>* parts) {
18 log("---");
19 log("len = %d", len(parts));
20 for (int i = 0; i < len(parts); ++i) {
21 BigStr* s = parts->at(i);
22 printf("%d [ %s ]\n", i, s->data_);
23 }
24}
25
26// TODO:
27//
28// - Test what happens append() runs over the max heap size
29// - how does it trigger a collection?
30
31TEST test_list_gc_header() {
32 auto list1 = NewList<int>();
33 StackRoots _roots1({&list1});
34 auto list2 = NewList<BigStr*>();
35 StackRoots _roots2({&list2});
36
37 ASSERT_EQ(0, len(list1));
38 ASSERT_EQ(0, len(list2));
39
40 ASSERT_EQ_FMT(0, list1->capacity_, "%d");
41 ASSERT_EQ_FMT(0, list2->capacity_, "%d");
42
43 ASSERT_EQ_FMT(HeapTag::FixedSize, ObjHeader::FromObject(list1)->heap_tag,
44 "%d");
45 ASSERT_EQ_FMT(HeapTag::FixedSize, ObjHeader::FromObject(list2)->heap_tag,
46 "%d");
47
48#if 0
49 // 8 byte obj header + 2 integers + pointer
50 ASSERT_EQ_FMT(24, ObjHeader::FromObject(list1)->obj_len, "%d");
51 ASSERT_EQ_FMT(24, ObjHeader::FromObject(list2)->obj_len, "%d");
52#endif
53
54 // Make sure they're on the heap
55#ifndef MARK_SWEEP
56 int diff1 = reinterpret_cast<char*>(list1) - gHeap.from_space_.begin_;
57 int diff2 = reinterpret_cast<char*>(list2) - gHeap.from_space_.begin_;
58 ASSERT(diff1 < 1024);
59 ASSERT(diff2 < 1024);
60#endif
61
62 auto more = NewList<int>(std::initializer_list<int>{11, 22, 33});
63 StackRoots _roots3({&more});
64 list1->extend(more);
65 ASSERT_EQ_FMT(3, len(list1), "%d");
66
67 ASSERT_EQ_FMT(HeapTag::Opaque, ObjHeader::FromObject(list1->slab_)->heap_tag,
68 "%d");
69
70#if 0
71 // 8 byte header + 3*4 == 8 + 12 == 20, rounded up to power of 2
72 ASSERT_EQ_FMT(32, ObjHeader::FromObject(list1->slab_)->obj_len, "%d");
73#endif
74
75 ASSERT_EQ_FMT(11, list1->at(0), "%d");
76 ASSERT_EQ_FMT(22, list1->at(1), "%d");
77 ASSERT_EQ_FMT(33, list1->at(2), "%d");
78
79 log("extending");
80 auto more2 = NewList<int>(std::initializer_list<int>{44, 55, 66, 77});
81 StackRoots _roots4({&more2});
82 list1->extend(more2);
83
84 ASSERT_EQ_FMT(7, len(list1), "%d");
85
86#if 0
87 // 8 bytes header + 7*4 == 8 + 28 == 36, rounded up to power of 2
88 ASSERT_EQ_FMT(64, ObjHeader::FromObject(list1->slab_)->obj_len, "%d");
89#endif
90
91 ASSERT_EQ_FMT(11, list1->at(0), "%d");
92 ASSERT_EQ_FMT(22, list1->at(1), "%d");
93 ASSERT_EQ_FMT(33, list1->at(2), "%d");
94 ASSERT_EQ_FMT(44, list1->at(3), "%d");
95 ASSERT_EQ_FMT(55, list1->at(4), "%d");
96 ASSERT_EQ_FMT(66, list1->at(5), "%d");
97 ASSERT_EQ_FMT(77, list1->at(6), "%d");
98
99 list1->append(88);
100 ASSERT_EQ_FMT(88, list1->at(7), "%d");
101 ASSERT_EQ_FMT(8, len(list1), "%d");
102
103#ifndef MARK_SWEEP
104 int d_slab = reinterpret_cast<char*>(list1->slab_) - gHeap.from_space_.begin_;
105 ASSERT(d_slab < 1024);
106#endif
107
108 log("list1_ = %p", list1);
109 log("list1->slab_ = %p", list1->slab_);
110
111 auto str1 = StrFromC("foo");
112 StackRoots _roots5({&str1});
113 log("str1 = %p", str1);
114 auto str2 = StrFromC("bar");
115 StackRoots _roots6({&str2});
116 log("str2 = %p", str2);
117
118 list2->append(str1);
119 list2->append(str2);
120 ASSERT_EQ(2, len(list2));
121 ASSERT(str_equals(str1, list2->at(0)));
122 ASSERT(str_equals(str2, list2->at(1)));
123
124 PASS();
125}
126
127// Manual initialization. This helped me write the GLOBAL_LIST() macro.
128GcGlobal<GlobalSlab<int, 3>> _gSlab = {
129 .header = {0, kZeroMask, HeapTag::Global, kUndefinedId},
130 {.items_ = {5, 6, 7}}};
131GcGlobal<GlobalList<int, 3>> _gList = {
132 .header = {0, kZeroMask, HeapTag::Global, kUndefinedId},
133 {.len_ = 3, .capacity_ = 3, .slab_ = &_gSlab.obj}};
134List<int>* gList = reinterpret_cast<List<int>*>(&_gList.obj);
135
136GLOBAL_LIST(gList2, int, 4, {5 COMMA 4 COMMA 3 COMMA 2});
137
138GLOBAL_STR(gFoo, "foo");
139GLOBAL_LIST(gList3, BigStr*, 2, {gFoo COMMA gFoo});
140
141TEST test_global_list() {
142 ASSERT_EQ(3, len(gList));
143 ASSERT_EQ_FMT(5, gList->at(0), "%d");
144 ASSERT_EQ_FMT(6, gList->at(1), "%d");
145 ASSERT_EQ_FMT(7, gList->at(2), "%d");
146
147 ASSERT_EQ(4, len(gList2));
148 ASSERT_EQ_FMT(5, gList2->at(0), "%d");
149 ASSERT_EQ_FMT(4, gList2->at(1), "%d");
150 ASSERT_EQ_FMT(3, gList2->at(2), "%d");
151 ASSERT_EQ_FMT(2, gList2->at(3), "%d");
152
153 ASSERT_EQ(2, len(gList3));
154 ASSERT(str_equals(gFoo, gList3->at(0)));
155 ASSERT(str_equals(gFoo, gList3->at(1)));
156
157 PASS();
158}
159
160TEST test_list_funcs() {
161 log(" ints");
162 auto ints = NewList<int>({4, 5, 6});
163 log("-- before pop(0)");
164 for (int i = 0; i < len(ints); ++i) {
165 log("ints[%d] = %d", i, ints->at(i));
166 }
167 ASSERT_EQ(3, len(ints)); // [4, 5, 6]
168 ints->pop(0); // [5, 6]
169
170 ASSERT_EQ(2, len(ints));
171 ASSERT_EQ_FMT(5, ints->at(0), "%d");
172 ASSERT_EQ_FMT(6, ints->at(1), "%d");
173
174 ints->reverse();
175 ASSERT_EQ(2, len(ints)); // [6, 5]
176
177 ASSERT_EQ_FMT(6, ints->at(0), "%d");
178 ASSERT_EQ_FMT(5, ints->at(1), "%d");
179
180 ints->append(9); // [6, 5, 9]
181 ASSERT_EQ(3, len(ints));
182
183 ints->reverse(); // [9, 5, 6]
184 ASSERT_EQ(9, ints->at(0));
185 ASSERT_EQ(5, ints->at(1));
186 ASSERT_EQ(6, ints->at(2));
187
188 ints->set(0, 42);
189 ints->set(1, 43);
190 log("-- after mutation");
191 for (int i = 0; i < len(ints); ++i) {
192 log("ints[%d] = %d", i, ints->at(i));
193 }
194
195 auto L = list_repeat<BigStr*>(nullptr, 3);
196 log("list_repeat length = %d", len(L));
197
198 auto L2 = list_repeat<bool>(true, 3);
199 log("list_repeat length = %d", len(L2));
200 log("item 0 %d", L2->at(0));
201 log("item 1 %d", L2->at(1));
202
203 auto strs = NewList<BigStr*>();
204 strs->append(StrFromC("c"));
205 strs->append(StrFromC("a"));
206 strs->append(StrFromC("b"));
207 strs->append(kEmptyString);
208 ASSERT_EQ(4, len(strs)); // ['c', 'a', 'b', '']
209
210 strs->sort();
211 ASSERT_EQ(4, len(strs)); // ['', 'a', 'b', 'c']
212 ASSERT(str_equals(kEmptyString, strs->at(0)));
213 ASSERT(str_equals(StrFromC("a"), strs->at(1)));
214 ASSERT(str_equals(StrFromC("b"), strs->at(2)));
215 ASSERT(str_equals(StrFromC("c"), strs->at(3)));
216
217 auto a = StrFromC("a");
218 auto aa = StrFromC("aa");
219 auto b = StrFromC("b");
220 auto z = StrFromC("z");
221
222 ASSERT_EQ(0, int_cmp(0, 0));
223 ASSERT_EQ(-1, int_cmp(0, 5));
224 ASSERT_EQ(1, int_cmp(0, -5));
225
226 ASSERT_EQ(0, str_cmp(kEmptyString, kEmptyString));
227 ASSERT_EQ(-1, str_cmp(kEmptyString, a));
228 ASSERT_EQ(-1, str_cmp(a, aa));
229 ASSERT_EQ(-1, str_cmp(a, b));
230 ASSERT_EQ(-1, str_cmp(a, z));
231
232 ASSERT_EQ(1, str_cmp(b, a));
233 ASSERT_EQ(1, str_cmp(z, a));
234 ASSERT_EQ(1, str_cmp(b, kEmptyString));
235
236 PASS();
237}
238
239void ListFunc(std::initializer_list<BigStr*> init) {
240 log("init.size() = %d", init.size());
241}
242
243TEST test_list_iters() {
244 log(" forward iteration over list");
245 auto ints = NewList<int>({1, 2, 3});
246 for (ListIter<int> it(ints); !it.Done(); it.Next()) {
247 int x = it.Value();
248 log("x = %d", x);
249 }
250
251 {
252 ListIter<int> it(ints);
253 auto ints2 = list(it);
254 ASSERT_EQ(ints->at(0), ints2->at(0));
255 ASSERT_EQ(ints->at(1), ints2->at(1));
256 ASSERT_EQ(ints->at(2), ints2->at(2));
257 }
258
259 log(" backward iteration over list");
260 for (ReverseListIter<int> it(ints); !it.Done(); it.Next()) {
261 int x = it.Value();
262 log("x = %d", x);
263 }
264
265 // hm std::initializer_list is "first class"
266 auto strs = {StrFromC("foo"), StrFromC("bar")};
267 ListFunc(strs);
268
269 PASS();
270}
271
272TEST test_list_copy() {
273 List<int>* a = NewList<int>(std::initializer_list<int>{1, 2, 3});
274 List<int>* b = list(a);
275
276 ASSERT_EQ(b->len_, a->len_);
277 ASSERT_EQ(b->at(0), a->at(0));
278 ASSERT_EQ(b->at(1), a->at(1));
279 ASSERT_EQ(b->at(2), a->at(2));
280
281 PASS();
282}
283
284TEST list_methods_test() {
285 List<int>* ints = nullptr;
286 StackRoots _roots({&ints});
287
288 ints = NewList<int>(std::initializer_list<int>{5, 6, 7, 8});
289
290 List<int>* slice1 = ints->slice(1);
291 ASSERT_EQ(3, len(slice1));
292 ASSERT_EQ(6, slice1->at(0));
293
294 List<int>* slice2 = ints->slice(-4, -2);
295 ASSERT_EQ(2, len(slice2));
296 ASSERT_EQ(5, slice2->at(0));
297
298 List<int>* slice3 = ints->slice(1, 4);
299 ASSERT_EQ(3, len(slice3));
300 ASSERT_EQ(6, slice3->at(0));
301 ASSERT_EQ(7, slice3->at(1));
302 ASSERT_EQ(8, slice3->at(2));
303
304 log("-- before pop(0)");
305 for (int i = 0; i < len(ints); ++i) {
306 log("ints[%d] = %d", i, ints->at(i));
307 }
308 ASSERT_EQ(4, len(ints)); // [5, 6, 7, 8]
309
310 log("pop()");
311
312 ints->pop(); // [5, 6, 7]
313 ASSERT_EQ(3, len(ints));
314 ASSERT_EQ_FMT(5, ints->at(0), "%d");
315 ASSERT_EQ_FMT(6, ints->at(1), "%d");
316 ASSERT_EQ_FMT(7, ints->at(2), "%d");
317
318 log("pop(0)");
319
320 ints->pop(0); // [6, 7]
321 ASSERT_EQ(2, len(ints));
322 ASSERT_EQ_FMT(6, ints->at(0), "%d");
323 ASSERT_EQ_FMT(7, ints->at(1), "%d");
324
325 ints->reverse();
326 ASSERT_EQ(2, len(ints)); // [7, 6]
327
328 ASSERT_EQ_FMT(7, ints->at(0), "%d");
329 ASSERT_EQ_FMT(6, ints->at(1), "%d");
330
331 ints->append(9); // [7, 6, 9]
332 ASSERT_EQ(3, len(ints));
333
334 ints->reverse(); // [9, 6, 7]
335 ASSERT_EQ(9, ints->at(0));
336 ASSERT_EQ(6, ints->at(1));
337 ASSERT_EQ(7, ints->at(2));
338
339 auto other = NewList<int>(std::initializer_list<int>{-1, -2});
340 ints->extend(other); // [9, 6, 7, 1, 2]
341 ASSERT_EQ(5, len(ints));
342 ASSERT_EQ(-2, ints->at(4));
343 ASSERT_EQ(-1, ints->at(3));
344
345 ints->clear();
346 ASSERT_EQ(0, len(ints));
347 ASSERT_EQ(0, ints->slab_->items_[0]); // make sure it's zero'd
348
349 // Clear empty list
350 auto empty = NewList<int*>();
351 empty->clear();
352
353 PASS();
354}
355
356TEST sort_test() {
357 ASSERT_EQ(0, int_cmp(0, 0));
358 ASSERT_EQ(-1, int_cmp(0, 5));
359 ASSERT_EQ(1, int_cmp(0, -5));
360
361 BigStr *a = nullptr, *aa = nullptr, *b = nullptr;
362 StackRoots _roots({&a, &aa, &b});
363
364 a = StrFromC("a");
365 aa = StrFromC("aa");
366 b = StrFromC("b");
367
368 ASSERT_EQ(0, str_cmp(kEmptyString, kEmptyString));
369 ASSERT_EQ(-1, str_cmp(kEmptyString, a));
370 ASSERT_EQ(-1, str_cmp(a, aa));
371 ASSERT_EQ(-1, str_cmp(a, b));
372
373 ASSERT_EQ(1, str_cmp(b, a));
374 ASSERT_EQ(1, str_cmp(b, kEmptyString));
375
376 List<BigStr*>* strs = nullptr;
377 StackRoots _roots2({&strs});
378 strs = Alloc<List<BigStr*>>();
379
380 strs->append(a);
381 strs->append(aa);
382 strs->append(b);
383 strs->append(kEmptyString);
384 ASSERT_EQ(4, len(strs)); // ['a', 'aa', 'b', '']
385
386 strs->sort(); // ['', 'a', 'aa', 'b']
387 ASSERT_EQ(4, len(strs));
388 ASSERT(str_equals(kEmptyString, strs->at(0)));
389 ASSERT(str_equals0("a", strs->at(1)));
390 ASSERT(str_equals0("aa", strs->at(2)));
391 ASSERT(str_equals0("b", strs->at(3)));
392
393 PASS();
394}
395
396TEST contains_test() {
397 BigStr* s = nullptr;
398 BigStr* nul = nullptr;
399 StackRoots _roots({&s, &nul});
400
401 log(" List<BigStr*>");
402 List<BigStr*>* strs = nullptr;
403 List<int>* ints = nullptr;
404 List<double>* floats = nullptr;
405
406 StackRoots _roots2({&strs, &ints, &floats});
407
408 strs = Alloc<List<BigStr*>>();
409
410 strs->append(kSpace);
411 s = StrFromC(" "); // LOCAL space
412 ASSERT(list_contains(strs, s));
413 ASSERT(!list_contains(strs, kStrFoo));
414
415 strs->append(kStrFoo);
416 ASSERT(list_contains(strs, kStrFoo));
417
418 log(" ints");
419 ints = NewList<int>(std::initializer_list<int>{1, 2, 3});
420 ASSERT(list_contains(ints, 1));
421
422 ASSERT(!list_contains(ints, 42));
423
424#if 0
425 log(" floats");
426 floats = NewList<double>(std::initializer_list<double>{0.5, 0.25, 0.0});
427 ASSERT(list_contains(floats, 0.0));
428 ASSERT(!list_contains(floats, 42.0));
429#endif
430
431 PASS();
432}
433
434TEST test_list_sort() {
435 auto s1 = StrFromC("fooA");
436 auto s2 = StrFromC("fooB");
437 auto s3 = StrFromC("fooC");
438 auto l = NewList<BigStr*>(std::initializer_list<BigStr*>{s3, s1, s2});
439
440 auto s = sorted(l);
441 ASSERT(str_equals(s->at(0), s1));
442 ASSERT(str_equals(s->at(1), s2));
443 ASSERT(str_equals(s->at(2), s3));
444
445 PASS();
446}
447
448TEST test_list_remove() {
449 auto l = NewList<int>(std::initializer_list<int>{1, 3, 3, 3, 2});
450
451 for (int i = 0; i < 3; ++i) {
452 l->remove(3);
453 }
454
455 bool caught = false;
456 try {
457 l->index(3);
458 } catch (ValueError* e) {
459 caught = true;
460 }
461 ASSERT(caught);
462
463 ASSERT_EQ(l->at(0), 1);
464 ASSERT_EQ(l->at(1), 2);
465
466 PASS();
467}
468
469TEST test_list_pop_mem_safe() {
470 auto l = NewList<int>();
471
472 // List::pop(int) had a memory bug where it would buffer overflow due to a
473 // mistake when calling memmove. To reproduce, the list had to be at least 16
474 // items long, otherwise ASAN will not catch the error.
475 for (int i = 0; i < 16; ++i) {
476 l->append(i);
477 }
478
479 l->pop(15); // This would cause a buffer overflow
480
481 PASS();
482}
483
484TEST test_index_out_of_bounds() {
485 auto l = NewList<int>({1, 2, 3});
486
487 ASSERT_EQ(3, l->at(2));
488 ASSERT_EQ(1, l->at(-3));
489
490 bool caught;
491
492 caught = false;
493 try {
494 l->at(3);
495 } catch (IndexError* e) {
496 caught = true;
497 }
498 ASSERT(caught);
499
500 caught = false;
501 try {
502 l->at(-4);
503 } catch (IndexError* e) {
504 caught = true;
505 }
506 ASSERT(caught);
507
508 // Now test setting it
509
510 l->set(2, 10);
511 l->set(-3, 11);
512
513 ASSERT_EQ(10, l->at(2));
514 ASSERT_EQ(11, l->at(-3));
515
516 caught = false;
517 try {
518 l->set(3, 12);
519 } catch (IndexError* e) {
520 caught = true;
521 }
522 ASSERT(caught);
523
524 caught = false;
525 try {
526 l->set(-4, 13);
527 } catch (IndexError* e) {
528 caught = true;
529 }
530 ASSERT(caught);
531
532 PASS();
533}
534
535TEST test_constructors() {
536 auto* li = Alloc<List<int>>();
537 // auto* li2 = Alloc<List<int>>(li);
538
539 PASS();
540}
541
542TEST test_empty_list_bugs() {
543 auto* li = Alloc<List<BigStr*>>();
544 // Gave UBSAN error before bug fix, which is NOT fatal!
545 li->sort();
546 ASSERT_EQ(0, len(li));
547
548 // Ditto
549 auto* slice = li->slice(0, 0);
550 ASSERT_EQ(0, len(slice));
551
552 // Boundary conditions for other functions
553
554 // extend empty list with empty list
555 li->extend(li);
556 ASSERT_EQ(0, len(li));
557
558 li->append(kEmptyString);
559 auto last = li->pop(0);
560 ASSERT_EQ(kEmptyString, last);
561
562 PASS();
563}
564
565GREATEST_MAIN_DEFS();
566
567int main(int argc, char** argv) {
568 gHeap.Init();
569
570 GREATEST_MAIN_BEGIN();
571
572 RUN_TEST(test_list_gc_header);
573 RUN_TEST(test_global_list);
574
575 RUN_TEST(test_list_funcs);
576 RUN_TEST(test_list_iters);
577
578 RUN_TEST(list_methods_test);
579 RUN_TEST(sort_test);
580 RUN_TEST(contains_test);
581
582 RUN_TEST(test_list_copy);
583 RUN_TEST(test_list_sort);
584 RUN_TEST(test_list_remove);
585
586 RUN_TEST(test_list_pop_mem_safe);
587
588 RUN_TEST(test_index_out_of_bounds);
589 RUN_TEST(test_constructors);
590 RUN_TEST(test_empty_list_bugs);
591
592 gHeap.CleanProcessExit();
593
594 GREATEST_MAIN_END();
595 return 0;
596}