OILS / mycpp / gc_list_test.cc View on Github | oilshell.org

507 lines, 352 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
221 ASSERT_EQ(0, int_cmp(0, 0));
222 ASSERT_EQ(-1, int_cmp(0, 5));
223 ASSERT_EQ(1, int_cmp(0, -5));
224
225 ASSERT_EQ(0, str_cmp(kEmptyString, kEmptyString));
226 ASSERT_EQ(-1, str_cmp(kEmptyString, a));
227 ASSERT_EQ(-1, str_cmp(a, aa));
228 ASSERT_EQ(-1, str_cmp(a, b));
229
230 ASSERT_EQ(1, str_cmp(b, a));
231 ASSERT_EQ(1, str_cmp(b, kEmptyString));
232
233 PASS();
234}
235
236void ListFunc(std::initializer_list<BigStr*> init) {
237 log("init.size() = %d", init.size());
238}
239
240TEST test_list_iters() {
241 log(" forward iteration over list");
242 auto ints = NewList<int>({1, 2, 3});
243 for (ListIter<int> it(ints); !it.Done(); it.Next()) {
244 int x = it.Value();
245 log("x = %d", x);
246 }
247
248 {
249 ListIter<int> it(ints);
250 auto ints2 = list(it);
251 ASSERT_EQ(ints->at(0), ints2->at(0));
252 ASSERT_EQ(ints->at(1), ints2->at(1));
253 ASSERT_EQ(ints->at(2), ints2->at(2));
254 }
255
256 log(" backward iteration over list");
257 for (ReverseListIter<int> it(ints); !it.Done(); it.Next()) {
258 int x = it.Value();
259 log("x = %d", x);
260 }
261
262 // hm std::initializer_list is "first class"
263 auto strs = {StrFromC("foo"), StrFromC("bar")};
264 ListFunc(strs);
265
266 PASS();
267}
268
269TEST test_list_copy() {
270 List<int>* a = NewList<int>(std::initializer_list<int>{1, 2, 3});
271 List<int>* b = list(a);
272
273 ASSERT_EQ(b->len_, a->len_);
274 ASSERT_EQ(b->at(0), a->at(0));
275 ASSERT_EQ(b->at(1), a->at(1));
276 ASSERT_EQ(b->at(2), a->at(2));
277
278 PASS();
279}
280
281TEST list_methods_test() {
282 List<int>* ints = nullptr;
283 StackRoots _roots({&ints});
284
285 ints = NewList<int>(std::initializer_list<int>{5, 6, 7, 8});
286
287 List<int>* slice1 = ints->slice(1);
288 ASSERT_EQ(3, len(slice1));
289 ASSERT_EQ(6, slice1->at(0));
290
291 List<int>* slice2 = ints->slice(-4, -2);
292 ASSERT_EQ(2, len(slice2));
293 ASSERT_EQ(5, slice2->at(0));
294
295 List<int>* slice3 = ints->slice(1, 4);
296 ASSERT_EQ(3, len(slice3));
297 ASSERT_EQ(6, slice3->at(0));
298 ASSERT_EQ(7, slice3->at(1));
299 ASSERT_EQ(8, slice3->at(2));
300
301 log("-- before pop(0)");
302 for (int i = 0; i < len(ints); ++i) {
303 log("ints[%d] = %d", i, ints->at(i));
304 }
305 ASSERT_EQ(4, len(ints)); // [5, 6, 7, 8]
306
307 log("pop()");
308
309 ints->pop(); // [5, 6, 7]
310 ASSERT_EQ(3, len(ints));
311 ASSERT_EQ_FMT(5, ints->at(0), "%d");
312 ASSERT_EQ_FMT(6, ints->at(1), "%d");
313 ASSERT_EQ_FMT(7, ints->at(2), "%d");
314
315 log("pop(0)");
316
317 ints->pop(0); // [6, 7]
318 ASSERT_EQ(2, len(ints));
319 ASSERT_EQ_FMT(6, ints->at(0), "%d");
320 ASSERT_EQ_FMT(7, ints->at(1), "%d");
321
322 ints->reverse();
323 ASSERT_EQ(2, len(ints)); // [7, 6]
324
325 ASSERT_EQ_FMT(7, ints->at(0), "%d");
326 ASSERT_EQ_FMT(6, ints->at(1), "%d");
327
328 ints->append(9); // [7, 6, 9]
329 ASSERT_EQ(3, len(ints));
330
331 ints->reverse(); // [9, 6, 7]
332 ASSERT_EQ(9, ints->at(0));
333 ASSERT_EQ(6, ints->at(1));
334 ASSERT_EQ(7, ints->at(2));
335
336 auto other = NewList<int>(std::initializer_list<int>{-1, -2});
337 ints->extend(other); // [9, 6, 7, 1, 2]
338 ASSERT_EQ(5, len(ints));
339 ASSERT_EQ(-2, ints->at(4));
340 ASSERT_EQ(-1, ints->at(3));
341
342 ints->clear();
343 ASSERT_EQ(0, len(ints));
344 ASSERT_EQ(0, ints->slab_->items_[0]); // make sure it's zero'd
345
346 // Clear empty list
347 auto empty = NewList<int*>();
348 empty->clear();
349
350 PASS();
351}
352
353TEST sort_test() {
354 ASSERT_EQ(0, int_cmp(0, 0));
355 ASSERT_EQ(-1, int_cmp(0, 5));
356 ASSERT_EQ(1, int_cmp(0, -5));
357
358 BigStr *a = nullptr, *aa = nullptr, *b = nullptr;
359 StackRoots _roots({&a, &aa, &b});
360
361 a = StrFromC("a");
362 aa = StrFromC("aa");
363 b = StrFromC("b");
364
365 ASSERT_EQ(0, str_cmp(kEmptyString, kEmptyString));
366 ASSERT_EQ(-1, str_cmp(kEmptyString, a));
367 ASSERT_EQ(-1, str_cmp(a, aa));
368 ASSERT_EQ(-1, str_cmp(a, b));
369
370 ASSERT_EQ(1, str_cmp(b, a));
371 ASSERT_EQ(1, str_cmp(b, kEmptyString));
372
373 List<BigStr*>* strs = nullptr;
374 StackRoots _roots2({&strs});
375 strs = Alloc<List<BigStr*>>();
376
377 strs->append(a);
378 strs->append(aa);
379 strs->append(b);
380 strs->append(kEmptyString);
381 ASSERT_EQ(4, len(strs)); // ['a', 'aa', 'b', '']
382
383 strs->sort(); // ['', 'a', 'aa', 'b']
384 ASSERT_EQ(4, len(strs));
385 ASSERT(str_equals(kEmptyString, strs->at(0)));
386 ASSERT(str_equals0("a", strs->at(1)));
387 ASSERT(str_equals0("aa", strs->at(2)));
388 ASSERT(str_equals0("b", strs->at(3)));
389
390 PASS();
391}
392
393TEST contains_test() {
394 BigStr* s = nullptr;
395 BigStr* nul = nullptr;
396 StackRoots _roots({&s, &nul});
397
398 log(" List<BigStr*>");
399 List<BigStr*>* strs = nullptr;
400 List<int>* ints = nullptr;
401 List<double>* floats = nullptr;
402
403 StackRoots _roots2({&strs, &ints, &floats});
404
405 strs = Alloc<List<BigStr*>>();
406
407 strs->append(kSpace);
408 s = StrFromC(" "); // LOCAL space
409 ASSERT(list_contains(strs, s));
410 ASSERT(!list_contains(strs, kStrFoo));
411
412 strs->append(kStrFoo);
413 ASSERT(list_contains(strs, kStrFoo));
414
415 log(" ints");
416 ints = NewList<int>(std::initializer_list<int>{1, 2, 3});
417 ASSERT(list_contains(ints, 1));
418
419 ASSERT(!list_contains(ints, 42));
420
421#if 0
422 log(" floats");
423 floats = NewList<double>(std::initializer_list<double>{0.5, 0.25, 0.0});
424 ASSERT(list_contains(floats, 0.0));
425 ASSERT(!list_contains(floats, 42.0));
426#endif
427
428 PASS();
429}
430
431TEST test_list_sort() {
432 auto s1 = StrFromC("fooA");
433 auto s2 = StrFromC("fooB");
434 auto s3 = StrFromC("fooC");
435 auto l = NewList<BigStr*>(std::initializer_list<BigStr*>{s3, s1, s2});
436
437 auto s = sorted(l);
438 ASSERT(str_equals(s->at(0), s1));
439 ASSERT(str_equals(s->at(1), s2));
440 ASSERT(str_equals(s->at(2), s3));
441
442 PASS();
443}
444
445TEST test_list_remove() {
446 auto l = NewList<int>(std::initializer_list<int>{1, 3, 3, 3, 2});
447
448 for (int i = 0; i < 3; ++i) {
449 l->remove(3);
450 }
451
452 bool caught = false;
453 try {
454 l->index(3);
455 } catch (ValueError* e) {
456 caught = true;
457 }
458 ASSERT(caught);
459
460 ASSERT_EQ(l->at(0), 1);
461 ASSERT_EQ(l->at(1), 2);
462
463 PASS();
464}
465
466TEST test_list_pop() {
467 auto l = NewList<int>();
468
469 // List::pop(int) had a memory bug where it would buffer overflow due to a
470 // mistake when calling memmove. To reproduce, the list had to be at least 16
471 // items long, otherwise ASAN will not catch the error.
472 for (int i = 0; i < 16; ++i) {
473 l->append(i);
474 }
475
476 l->pop(15);
477
478 PASS();
479}
480
481GREATEST_MAIN_DEFS();
482
483int main(int argc, char** argv) {
484 gHeap.Init();
485
486 GREATEST_MAIN_BEGIN();
487
488 RUN_TEST(test_list_gc_header);
489 RUN_TEST(test_global_list);
490
491 RUN_TEST(test_list_funcs);
492 RUN_TEST(test_list_iters);
493
494 RUN_TEST(list_methods_test);
495 RUN_TEST(sort_test);
496 RUN_TEST(contains_test);
497
498 RUN_TEST(test_list_copy);
499 RUN_TEST(test_list_sort);
500 RUN_TEST(test_list_remove);
501 RUN_TEST(test_list_pop);
502
503 gHeap.CleanProcessExit();
504
505 GREATEST_MAIN_END();
506 return 0;
507}