array_list_tests.h

Go to the documentation of this file.

/* -*- C -*-
 * Serene programming language
 * Copyright (C) 2019-2026 Sameer Rahmani <lxsameer@lxsameer.com>
 *
 * This program is free software: you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published by
 * the Free Software Foundation, either version 3 of the License, or
 * (at your option) any later version.
 *
 * This program is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with this program.  If not, see <https://www.gnu.org/licenses/>.
 */
 
#pragma once
 
#include <stdio.h>
 
#include <serene/rt/context.h>
#include <serene/rt/impl/array_list.h>
 
#include "base.h"
 
#define AL_TESTS(X)                                                                   \
  X("array_list::empty", test_al_empty),                                              \
    X("array_list::push_less_than_32", test_al_push_less_than_32),                    \
    X("array_list::push_more_than_32", test_al_push_more_than_32),                    \
    X("array_list::tail_to_trie_boundary", test_al_push_tail_to_trie_boundary),       \
    X("array_list::get_out_of_bounds", test_al_get_out_of_bounds),                    \
    X("array_list::update", test_al_update), X("array_list::remove", test_al_remove), \
    X("array_list::remove_out_of_bounds", test_al_remove_out_of_bounds),              \
    X("array_list::remove_drain_and_push", test_al_remove_drain_and_push)
 
#if defined(AL_DEBUG)
#  define AL_TEST_LOG(...) DBG("AL_TEST", __VA_ARGS__)
#else
#  define AL_TEST_LOG(...)
#endif
 
typedef struct al_dummy {
  int foo;
  int bar;
} al_dummy;
 
static void test_al_empty() {
  MAKE_ENGINE(mm, engine);
  MAKE_CONTEXT(engine, ctx);
 
  auto s = array_list_empty(ctx);
 
  TEST_CHECK(s.len == 0);
  TEST_CHECK(s.tail_len == 0);
  TEST_CHECK(s.root == nullptr);
  TEST_CHECK(s.maybe_error == nullptr);
 
  RELEASE_CONTEXT(ctx);
  SHUTDOWN_ENGINE(mm, engine);
}
 
static void test_al_push_less_than_32() {
  MAKE_ENGINE(mm, engine);
  MAKE_CONTEXT(engine, ctx);
 
  auto s = array_list_empty(ctx);
 
  for (size_t i = 0; i < 31; i++) {
    auto g   = ALLOC(ctx, al_dummy);
    g->bar   = (int)i + 1;
    g->foo   = (int)i + 2;
    auto err = array_list_push(&s, g);
    ASSERT_NULL(err);
 
    TEST_CHECK(s.len == i + 1);
    TEST_CHECK(s.tail_len == i + 1);
    TEST_CHECK(s.root == nullptr);
    TEST_CHECK(s.maybe_error == nullptr);
  }
 
  for (size_t i = 0; i < 30; i++) {
    auto res = array_list_get(&s, i);
    TEST_NO_ERROR(res);
    ASSERT_NOT_NULL(res.data);
 
    al_dummy *d = res.data;
    TEST_CHECK(d->foo == (int)(i + 2));
    TEST_CHECK(d->bar == (int)(i + 1));
  }
 
  RELEASE_CONTEXT(ctx);
  SHUTDOWN_ENGINE(mm, engine);
}
 
static void test_al_push_more_than_32() {
  MAKE_ENGINE(mm, engine);
  MAKE_CONTEXT(engine, ctx);
 
  auto s = array_list_empty(ctx);
 
  for (int i = 0; i < 2000; i++) {
 
    al_dummy *d = ALLOC(ctx, al_dummy);
    ASSERT_NOT_NULL(d);
    d->foo   = i;
    d->bar   = 3000 - i;
    auto err = array_list_push(&s, d);
    ASSERT_NULL(err);
  }
 
  TEST_CHECK(s.len == 2000);
  TEST_CHECK(s.tail_len == 16);
  TEST_CHECK(s.root != nullptr);
  TEST_CHECK(s.maybe_error == nullptr);
 
  al_dummy *d1 = (al_dummy *)s.tail[0];
 
  ASSERT_NOT_NULL(d1);
  TEST_CHECK(d1->foo == 1984);
  TEST_CHECK(d1->bar == 3000 - d1->foo);
 
  al_dummy *d2 = (al_dummy *)s.tail[s.tail_len - 1];
  ASSERT_NOT_NULL(d2);
  TEST_CHECK(d2->foo == 1999);
  TEST_CHECK(d2->bar == 3000 - d2->foo);
 
  for (int i = 0; i < 2000; i++) {
    auto res = array_list_get(&s, (size_t)i);
    TEST_NO_ERROR(res);
    ASSERT_NOT_NULL(res.data);
 
    al_dummy *d = res.data;
 
    // AL_TEST_LOG("%d %d %d", i, d->foo, d->bar);
    TEST_CHECK(d->foo == i);
    TEST_CHECK(d->bar == 3000 - i);
  };
 
  RELEASE_CONTEXT(ctx);
  SHUTDOWN_ENGINE(mm, engine);
}
 
// Pushing element AL_BR + 1 moves the full tail into the trie and starts a
// fresh tail. This isolates that transition, which the bulk push tests only
// cross incidentally.
static void test_al_push_tail_to_trie_boundary() {
  MAKE_ENGINE(mm, engine);
  MAKE_CONTEXT(engine, ctx);
 
  auto s = array_list_empty(ctx);
 
  // Fill the tail exactly to AL_BR. Everything still lives in the tail.
  for (int i = 0; i < 32; i++) {
    al_dummy *d = ALLOC(ctx, al_dummy);
    d->foo      = i;
    d->bar      = 3000 - i;
    auto err    = array_list_push(&s, d);
    ASSERT_NULL(err);
  }
 
  TEST_CHECK(s.len == 32);
  TEST_CHECK(s.tail_len == 32);
  TEST_CHECK(s.root == nullptr);
  TEST_CHECK(s.maybe_error == nullptr);
 
  // One more push moves the full tail into the trie and starts a fresh tail.
  al_dummy *d = ALLOC(ctx, al_dummy);
  d->foo      = 32;
  d->bar      = 3000 - 32;
  auto err    = array_list_push(&s, d);
  ASSERT_NULL(err);
 
  TEST_CHECK(s.len == 33);
  TEST_CHECK(s.tail_len == 1);
  TEST_CHECK(s.root != nullptr);
  TEST_CHECK(s.depth == 0);
  TEST_CHECK(s.maybe_error == nullptr);
 
  // The last element of the old tail now lives in the trie, the new one in the
  // fresh tail, and the first element is still reachable.
  auto first = array_list_get(&s, 0);
  TEST_NO_ERROR(first);
  ASSERT_NOT_NULL(first.data);
  TEST_CHECK(((al_dummy *)first.data)->foo == 0);
 
  auto last_moved = array_list_get(&s, 31);
  TEST_NO_ERROR(last_moved);
  ASSERT_NOT_NULL(last_moved.data);
  TEST_CHECK(((al_dummy *)last_moved.data)->foo == 31);
 
  auto in_tail = array_list_get(&s, 32);
  TEST_NO_ERROR(in_tail);
  ASSERT_NOT_NULL(in_tail.data);
  TEST_CHECK(((al_dummy *)in_tail.data)->foo == 32);
 
  RELEASE_CONTEXT(ctx);
  SHUTDOWN_ENGINE(mm, engine);
}
 
// array_list_get must reject any index at or past len with INDEX_OUT_OF_BOUND
// and no data, both on an empty list and after pushes.
static void test_al_get_out_of_bounds() {
  MAKE_ENGINE(mm, engine);
  MAKE_CONTEXT(engine, ctx);
 
  auto s = array_list_empty(ctx);
 
  // Empty list: index 0 is already out of bounds.
  auto empty = array_list_get(&s, 0);
  ASSERT_NOT_NULL(empty.maybe_error);
  TEST_CHECK(empty.maybe_error->tag == INDEX_OUT_OF_BOUND);
  ASSERT_NULL(empty.data);
 
  for (int i = 0; i < 40; i++) {
    al_dummy *d = ALLOC(ctx, al_dummy);
    d->foo      = i;
    d->bar      = 3000 - i;
    auto err    = array_list_push(&s, d);
    ASSERT_NULL(err);
  }
 
  // The first invalid index is exactly len.
  auto at_len = array_list_get(&s, s.len);
  ASSERT_NOT_NULL(at_len.maybe_error);
  TEST_CHECK(at_len.maybe_error->tag == INDEX_OUT_OF_BOUND);
  ASSERT_NULL(at_len.data);
 
  // A far larger index fails the same way and exercises the message sizing path.
  auto far = array_list_get(&s, s.len + 1000);
  ASSERT_NOT_NULL(far.maybe_error);
  TEST_CHECK(far.maybe_error->tag == INDEX_OUT_OF_BOUND);
  ASSERT_NULL(far.data);
 
  // The last valid index still succeeds.
  auto last = array_list_get(&s, s.len - 1);
  TEST_NO_ERROR(last);
  ASSERT_NOT_NULL(last.data);
  TEST_CHECK(((al_dummy *)last.data)->foo == 39);
 
  RELEASE_CONTEXT(ctx);
  SHUTDOWN_ENGINE(mm, engine);
}
 
static void test_al_update() {
  MAKE_ENGINE(mm, engine);
  MAKE_CONTEXT(engine, ctx);
 
  auto s = array_list_empty(ctx);
 
  al_dummy *a = ALLOC(ctx, al_dummy);
  a->foo      = 1;
  a->bar      = 1;
  ASSERT_NULL(array_list_push(&s, a));
 
  al_dummy *b = ALLOC(ctx, al_dummy);
  b->foo      = 2;
  b->bar      = 2;
 
  // a and b are distinct allocations, so distinct pointers.
  TEST_CHECK(a != b);
 
  // Precondition: slot 0 holds `a`.
  auto before = array_list_get(&s, 0);
  TEST_NO_ERROR(before);
  TEST_CHECK(before.data == a);
 
  // Update slot 0 to point at `b`.
  ASSERT_NULL(array_list_update(&s, 0, b));
 
  // Postcondition: a fresh fetch must now yield `b`, not `a`.
  auto after = array_list_get(&s, 0);
  TEST_NO_ERROR(after);
  TEST_CHECK(after.data == b);
 
  RELEASE_CONTEXT(ctx);
  SHUTDOWN_ENGINE(mm, engine);
}
 
// Removing a middle index shifts every later element down one and shrinks the
// length by one, across the tail-to-trie boundary.
static void test_al_remove() {
  MAKE_ENGINE(mm, engine);
  MAKE_CONTEXT(engine, ctx);
 
  auto s = array_list_empty(ctx);
 
  // foo carries the logical index so a shift is visible after removal.
  for (int i = 0; i < 100; i++) {
    al_dummy *d = ALLOC(ctx, al_dummy);
    d->foo      = i;
    d->bar      = 3000 - i;
    ASSERT_NULL(array_list_push(&s, d));
  }
 
  auto err = array_list_remove(&s, 50);
  ASSERT_NULL(err);
  TEST_CHECK(s.len == 99);
 
  // Elements before the hole are untouched, everything after slid down one.
  for (int i = 0; i < 99; i++) {
    auto res = array_list_get(&s, (size_t)i);
    TEST_NO_ERROR(res);
    ASSERT_NOT_NULL(res.data);
    int expected = i < 50 ? i : i + 1;
    TEST_CHECK(((al_dummy *)res.data)->foo == expected);
  }
 
  // The old last index is now out of bounds.
  auto gone = array_list_get(&s, 99);
  ASSERT_NOT_NULL(gone.maybe_error);
  TEST_CHECK(gone.maybe_error->tag == INDEX_OUT_OF_BOUND);
 
  // Removing the final element is the pop case: no shift, just a shrink.
  ASSERT_NULL(array_list_remove(&s, s.len - 1));
  TEST_CHECK(s.len == 98);
  auto last = array_list_get(&s, s.len - 1);
  TEST_NO_ERROR(last);
  // Index 97 held foo 98 after the first removal, and dropping the final
  // element does not disturb it.
  TEST_CHECK(((al_dummy *)last.data)->foo == 98);
 
  RELEASE_CONTEXT(ctx);
  SHUTDOWN_ENGINE(mm, engine);
}
 
// array_list_remove rejects any index at or past len, on both an empty and a
// populated list, without changing the length.
static void test_al_remove_out_of_bounds() {
  MAKE_ENGINE(mm, engine);
  MAKE_CONTEXT(engine, ctx);
 
  auto s = array_list_empty(ctx);
 
  auto empty = array_list_remove(&s, 0);
  ASSERT_NOT_NULL(empty);
  TEST_CHECK(empty->tag == INDEX_OUT_OF_BOUND);
  TEST_CHECK(s.len == 0);
 
  for (int i = 0; i < 40; i++) {
    al_dummy *d = ALLOC(ctx, al_dummy);
    d->foo      = i;
    ASSERT_NULL(array_list_push(&s, d));
  }
 
  auto at_len = array_list_remove(&s, s.len);
  ASSERT_NOT_NULL(at_len);
  TEST_CHECK(at_len->tag == INDEX_OUT_OF_BOUND);
  TEST_CHECK(s.len == 40);
 
  RELEASE_CONTEXT(ctx);
  SHUTDOWN_ENGINE(mm, engine);
}
 
// Repeatedly removing the front drains the tail many times over, which forces
// array_list_pull_last_leaf, then pushing again reuses the drained (over-tall)
// trie. Everything must still read back in order.
static void test_al_remove_drain_and_push() {
  MAKE_ENGINE(mm, engine);
  MAKE_CONTEXT(engine, ctx);
 
  auto s = array_list_empty(ctx);
 
  for (int i = 0; i < 2000; i++) {
    al_dummy *d = ALLOC(ctx, al_dummy);
    d->foo      = i;
    ASSERT_NULL(array_list_push(&s, d));
  }
 
  // Drop the front 1990 times; the survivors are the original 1990..1999.
  for (int i = 0; i < 1990; i++) {
    ASSERT_NULL(array_list_remove(&s, 0));
  }
  TEST_CHECK(s.len == 10);
 
  for (int i = 0; i < 10; i++) {
    auto res = array_list_get(&s, (size_t)i);
    TEST_NO_ERROR(res);
    ASSERT_NOT_NULL(res.data);
    TEST_CHECK(((al_dummy *)res.data)->foo == 1990 + i);
  }
 
  // Push a fresh batch into the shrunken trie.
  for (int i = 0; i < 2000; i++) {
    al_dummy *d = ALLOC(ctx, al_dummy);
    d->foo      = 10000 + i;
    ASSERT_NULL(array_list_push(&s, d));
  }
  TEST_CHECK(s.len == 2010);
 
  // The ten survivors are still first, the new batch follows in order.
  for (int i = 0; i < 10; i++) {
    auto res = array_list_get(&s, (size_t)i);
    TEST_NO_ERROR(res);
    TEST_CHECK(((al_dummy *)res.data)->foo == 1990 + i);
  }
  for (int i = 0; i < 2000; i++) {
    auto res = array_list_get(&s, (size_t)(10 + i));
    TEST_NO_ERROR(res);
    TEST_CHECK(((al_dummy *)res.data)->foo == 10000 + i);
  }
 
  RELEASE_CONTEXT(ctx);
  SHUTDOWN_ENGINE(mm, engine);
}