seq_tests.h

Go to the documentation of this file.

/* -*- C -*-
 * Serene programming language
 * Copyright (C) 2019-2026 Sameer Rahmani <[email protected]>
 *
 * 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/seq.h>
 
#include "base.h"
 
#define SEQ_TESTS(X)                                                                        \
  X("seq::empty", test_seq_empty), X("seq::push_less_than_32", test_seq_push_less_than_32), \
    X("seq::push_more_than_32", test_seq_push_more_than_32),                                \
    X("seq::branching_push", test_seq_branching_push),                                      \
    X("seq::branching_promotion", test_seq_branching_promotion)
 
#if defined(SEQ_DEBUG)
#  define SEQ_TEST_LOG(...) DBG("SEQ_TEST", __VA_ARGS__)
#else
#  define SEQ_TEST_LOG(...)
#endif
 
typedef struct seq_dummy {
  int foo;
  int bar;
} seq_dummy;
 
static void test_seq_empty() {
  MAKE_ENGINE(mm, engine);
  MAKE_CONTEXT(engine, ctx);
  auto s = seq_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);
}
 
void test_seq_push_less_than_32() {
  MAKE_ENGINE(mm, engine);
  MAKE_CONTEXT(engine, ctx);
 
  seq_dummy d = {.foo = 10, .bar = 20}; // NOLINT
  auto s      = seq_empty(ctx);
  auto s1     = seq_push(&s, (seq_elem_t)&d);
  TEST_CHECK(s.len == 0);
  TEST_CHECK(s.tail_len == 0);
  TEST_CHECK(s.root == nullptr);
  TEST_CHECK(s.maybe_error == nullptr);
 
  TEST_CHECK(s1.len == 1);
  TEST_CHECK(s1.tail_len == 1);
  TEST_CHECK(s1.root == nullptr);
  TEST_CHECK(s1.maybe_error == nullptr);
  seq_dummy *d1 = (seq_dummy *)s1.tail[0];
  TEST_CHECK(d1->foo == 10);
  TEST_CHECK(d1->bar == 20);
 
  RELEASE_CONTEXT(ctx);
  SHUTDOWN_ENGINE(mm, engine);
}
 
void test_seq_push_more_than_32() {
  MAKE_ENGINE(mm, engine);
  MAKE_CONTEXT(engine, ctx);
 
  seq_t s = seq_empty(ctx);
 
  for (int i = 0; i < 2000; i++) {
 
    seq_dummy *d = ALLOC(ctx, seq_dummy);
    d->foo       = i;
    d->bar       = 3000 - i;
    s            = seq_push(&s, (seq_elem_t)d);
  }
 
  TEST_CHECK(s.len == 2000);
  TEST_CHECK(s.tail_len == 16);
  TEST_CHECK(s.root != nullptr);
  TEST_CHECK(s.maybe_error == nullptr);
 
  seq_dummy *d1 = (seq_dummy *)s.tail[0];
 
  ASSERT_NOT_NULL(d1);
  TEST_CHECK(d1->foo == 1984);
  TEST_CHECK(d1->bar == 3000 - d1->foo);
 
  seq_dummy *d2 = (seq_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++) {
    seq_lookup_result_t res = seq_get(&s, (size_t)i);
    TEST_CHECK(res.maybe_error == nullptr);
    ASSERT_NOT_NULL(res.data);
    seq_dummy *d = (seq_dummy *)res.data;
 
    SEQ_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);
}
 
/// Two pushes branched off one head must not see each other's element. The
/// tail buffer is shared between versions, so without copy on write the
/// second push clobbers the first branch's slot.
static void test_seq_branching_push() {
  MAKE_ENGINE(mm, engine);
  MAKE_CONTEXT(engine, ctx);
 
  seq_t s = seq_empty(ctx);
  for (int i = 0; i < 5; i++) {
    seq_dummy *d = ALLOC(ctx, seq_dummy);
    d->foo       = i;
    d->bar       = i;
    s            = seq_push(&s, (seq_elem_t)d);
  }
 
  seq_dummy da = {.foo = 100, .bar = 1};
  seq_dummy db = {.foo = 200, .bar = 2};
 
  seq_t b1 = seq_push(&s, (seq_elem_t)&da);
  seq_t b2 = seq_push(&s, (seq_elem_t)&db);
 
  TEST_CHECK(s.len == 5);
  TEST_CHECK(b1.len == 6);
  TEST_CHECK(b2.len == 6);
 
  seq_lookup_result_t r1 = seq_get(&b1, 5);
  TEST_CHECK(r1.maybe_error == nullptr);
  TEST_CHECK(r1.data == (seq_elem_t)&da);
 
  seq_lookup_result_t r2 = seq_get(&b2, 5);
  TEST_CHECK(r2.maybe_error == nullptr);
  TEST_CHECK(r2.data == (seq_elem_t)&db);
 
  RELEASE_CONTEXT(ctx);
  SHUTDOWN_ENGINE(mm, engine);
}
 
/// Two branches that each promote their own diverging tail into the same
/// root slot must not overwrite each other. 96 shared elements put the base
/// at a 64 element tree plus a full tail; 33 pushes per branch force two
/// promotions each, the second landing in the same fringe slot of a root
/// that used to be shared.
static void test_seq_branching_promotion() {
  MAKE_ENGINE(mm, engine);
  MAKE_CONTEXT(engine, ctx);
 
  int *vals = ALLOCN(ctx, int, 96);
  seq_t s   = seq_empty(ctx);
  for (int i = 0; i < 96; i++) {
    vals[i] = i;
    s       = seq_push(&s, (seq_elem_t)&vals[i]);
  }
 
  int *b1_vals = ALLOCN(ctx, int, 33);
  int *b2_vals = ALLOCN(ctx, int, 33);
  seq_t b1     = s;
  seq_t b2     = s;
  for (int i = 0; i < 33; i++) {
    b1_vals[i] = 1000 + i;
    b2_vals[i] = 2000 + i;
    b1         = seq_push(&b1, (seq_elem_t)&b1_vals[i]);
    b2         = seq_push(&b2, (seq_elem_t)&b2_vals[i]);
  }
 
  TEST_CHECK(s.len == 96);
  TEST_CHECK(b1.len == 129);
  TEST_CHECK(b2.len == 129);
 
  // The shared prefix must read the same through every head.
  for (int i = 0; i < 96; i++) {
    TEST_CHECK(seq_get(&s, (size_t)i).data == (seq_elem_t)&vals[i]);
    TEST_CHECK(seq_get(&b1, (size_t)i).data == (seq_elem_t)&vals[i]);
    TEST_CHECK(seq_get(&b2, (size_t)i).data == (seq_elem_t)&vals[i]);
  }
 
  // Each branch must read only its own suffix.
  for (int i = 0; i < 33; i++) {
    TEST_CHECK(seq_get(&b1, (size_t)(96 + i)).data == (seq_elem_t)&b1_vals[i]);
    TEST_CHECK(seq_get(&b2, (size_t)(96 + i)).data == (seq_elem_t)&b2_vals[i]);
  }
 
  RELEASE_CONTEXT(ctx);
  SHUTDOWN_ENGINE(mm, engine);
}