Ultra ALPS GP evolution hang: unsigned integer underflow in selection (tournament_size=0)

alps_repro.cc

// Minimal reproduction: Ultra ALPS GP evolution hang
//
// Two distinct bugs exist when using evolution<> directly (not via src::search):
//
// Bug 1: Unsigned integer underflow in ALPS selection (tournament_size=0)
//   - parameters::evolution::tournament_size defaults to 0 (sentinel)
//   - parameters::init() sets it to 5, but src::problem constructor does NOT
//   - ALPS selection (evolution_selection.tcc:147) computes:
//       for (auto rounds(tournament_size - 1); rounds; --rounds)
//     With tournament_size=0, rounds wraps to SIZE_MAX (~18 quintillion)
//   - Each iteration evaluates an individual, so selection never returns
//   - Manifests as: evolution stuck at generation 0, all CPUs busy
//
// Bug 2: Lock contention in ALPS replacement (separate from Bug 1)
//   - alps::try_add_to_layer() holds exclusive lock during evaluation
//   - With tournament_size properly set, this causes thread starvation
//   - Severity depends on hardware, population size, and dataset size
//
// This test isolates Bug 1 by running WITHOUT init().  Bug 1 is platform-
// independent: it hangs on any hardware because selection loops SIZE_MAX times.
//
// Test matrix:
//   Section A: alps_es WITHOUT init() -- reproduces Bug 1 (should all timeout)
//   Section B: alps_es WITH init()    -- checks if Bug 2 causes hangs
//   Section C: std_es WITHOUT init()  -- SEGFAULT (empty parents vector)

#include "kernel/ultra.h"
#include "kernel/gp/src/evaluator.h"
#include "kernel/gp/src/problem.h"

#include <csignal>
#include <iostream>
#include <sstream>
#include <string>
#include <sys/wait.h>
#include <thread>
#include <unistd.h>

// ---------------------------------------------------------------------------
// Helpers
// ---------------------------------------------------------------------------

static ultra::src::problem make_problem(int n_examples)
{
  std::string csv = "y,x1,x2\n";
  for (int i = 0; i < n_examples; ++i)
  {
    double x1 = static_cast<double>(i) / 20.0 - 5.0;
    double x2 = static_cast<double>(i % 20) / 10.0 - 1.0;
    double y  = x1 * x1 + 2.0 * x2;
    csv += std::to_string(y) + "," + std::to_string(x1)
         + "," + std::to_string(x2) + "\n";
  }

  std::istringstream stream(csv);
  ultra::src::problem prob(stream);
  prob.insert<ultra::real::abs>();
  prob.insert<ultra::real::cos>();
  prob.insert<ultra::real::sqrt>();
  prob.insert<ultra::real::sigmoid>();
  prob.insert<ultra::real::ife>();
  prob.insert<ultra::real::max>();
  return prob;
}

struct trial_params
{
  int n_examples;
  int individuals;
  int subgroups;
  int generations;
  int code_length;
  bool call_init;   // whether to call prob.params.init()
  bool use_alps;    // false = std_es, true = alps_es
};

static trial_params g_params;

static void run_trial()
{
  auto prob = make_problem(g_params.n_examples);

  if (g_params.call_init)
    prob.params.init();

  prob.params.evolution.generations     = g_params.generations;
  prob.params.population.individuals    = g_params.individuals;
  prob.params.population.init_subgroups = g_params.subgroups;
  prob.params.slp.code_length           = g_params.code_length;

  // Print tournament_size so we can confirm its value
  std::cerr << "  [child] tournament_size="
            << prob.params.evolution.tournament_size
            << " mate_zone=" << prob.params.evolution.mate_zone
            << " p_cross=" << prob.params.evolution.p_cross
            << " brood=" << prob.params.evolution.brood_recombination
            << "\n";

  ultra::src::mae_evaluator<ultra::gp::individual> eva(prob.data);
  ultra::evolution<decltype(eva)> evo(prob, eva);

  if (g_params.use_alps)
  {
    auto result = evo.run<ultra::alps_es>();
    std::cerr << "  [child] alps_es best fitness = " << result.best().fit
              << "\n";
  }
  else
  {
    auto result = evo.run<ultra::std_es>();
    std::cerr << "  [child] std_es best fitness = " << result.best().fit
              << "\n";
  }
}

static int run_in_child(int timeout_sec)
{
  pid_t pid = fork();
  if (pid < 0) { perror("fork"); return -1; }

  if (pid == 0)
  {
    run_trial();
    _exit(0);
  }

  for (int elapsed = 0; elapsed < timeout_sec; ++elapsed)
  {
    int status = 0;
    pid_t ret = waitpid(pid, &status, WNOHANG);
    if (ret > 0)
    {
      if (WIFSIGNALED(status)) return -WTERMSIG(status);
      if (WIFEXITED(status))   return WEXITSTATUS(status);
      return -1;
    }
    sleep(1);
  }

  kill(pid, SIGKILL);
  int status = 0;
  waitpid(pid, &status, 0);
  return -SIGALRM;  // timeout sentinel
}

// ---------------------------------------------------------------------------
// Main
// ---------------------------------------------------------------------------

int main()
{
  struct test_case
  {
    const char *label;
    trial_params params;
    int timeout_sec;
    int trials;
  };

  // Section A: alps_es WITHOUT init() -- Bug 1 (unsigned underflow)
  // tournament_size=0, so ALPS selection loops SIZE_MAX times.
  // Expected: ALL timeout (any hardware).
  test_case section_a[] = {
    {"[A] alps NO-INIT ind=3   sub=4 gen=20",
     {200, 3, 4, 20, 16, /*init=*/false, /*alps=*/true}, 10, 1},
    {"[A] alps NO-INIT ind=50  sub=4 gen=20",
     {200, 50, 4, 20, 16, false, true}, 10, 1},
    {"[A] alps NO-INIT ind=200 sub=4 gen=20",
     {200, 200, 4, 20, 16, false, true}, 10, 1},
  };

  // Section B: alps_es WITH init() -- tests lock contention only
  // tournament_size=5, so no underflow.
  // Expected: pass (may timeout on constrained hardware due to lock contention).
  test_case section_b[] = {
    {"[B] alps INIT ind=3   sub=4 gen=20",
     {200, 3, 4, 20, 16, /*init=*/true, /*alps=*/true}, 30, 1},
    {"[B] alps INIT ind=50  sub=4 gen=20",
     {200, 50, 4, 20, 16, true, true}, 30, 1},
    {"[B] alps INIT ind=200 sub=4 gen=20",
     {200, 200, 4, 20, 16, true, true}, 30, 1},
  };

  // Section C: std_es WITHOUT init() -- SEGFAULT
  // tournament_size=0, empty parents vector, parents[0] crash.
  // Expected: crash with signal 11 (SIGSEGV) in Release builds.
  test_case section_c[] = {
    {"[C] std  NO-INIT ind=100 sub=1 gen=5",
     {200, 100, 1, 5, 16, /*init=*/false, /*alps=*/false}, 10, 1},
  };

  std::cout << "=== Ultra GP Bug Reproduction ===\n";
  std::cout << "Compiler: "
#if defined(__clang__)
            << "Clang " << __clang_major__ << "." << __clang_minor__
#elif defined(__GNUC__)
            << "GCC " << __GNUC__ << "." << __GNUC_MINOR__
#else
            << "unknown"
#endif
            << "\n";
  std::cout << "Build: "
#ifdef NDEBUG
            << "Release"
#else
            << "Debug"
#endif
            << "\n";
  std::cout << "Platform: "
#if defined(__APPLE__)
            << "macOS"
#elif defined(__linux__)
            << "Linux"
#else
            << "other"
#endif
            << " " << sizeof(void *) * 8 << "-bit\n";
  std::cout << "Hardware threads: "
            << std::thread::hardware_concurrency() << "\n\n";

  auto run_section = [](const char *title, test_case *cases, int n,
                        int &total_pass, int &total_timeout, int &total_crash)
  {
    std::cout << "======= " << title << " =======\n\n";

    for (int i = 0; i < n; ++i)
    {
      const auto &tc = cases[i];
      std::cout << "--- " << tc.label << " ---\n";
      int pass = 0, timeout = 0, crash = 0;

      for (int t = 0; t < tc.trials; ++t)
      {
        g_params = tc.params;
        int rc = run_in_child(tc.timeout_sec);

        if (rc == -SIGALRM)
        {
          ++timeout;
          std::cout << "  Trial " << (t + 1) << "/" << tc.trials
                    << ": TIMEOUT (" << tc.timeout_sec << "s)\n";
        }
        else if (rc < 0)
        {
          ++crash;
          std::cout << "  Trial " << (t + 1) << "/" << tc.trials
                    << ": CRASHED (signal " << (-rc) << ")\n";
        }
        else if (rc == 0)
        {
          ++pass;
          std::cout << "  Trial " << (t + 1) << "/" << tc.trials
                    << ": completed\n";
        }
        else
        {
          ++crash;
          std::cout << "  Trial " << (t + 1) << "/" << tc.trials
                    << ": exit code " << rc << "\n";
        }
      }

      int failures = timeout + crash;
      if (failures > 0)
      {
        std::cout << "  => FAILED (";
        if (crash > 0)   std::cout << crash << " crashed";
        if (crash > 0 && timeout > 0) std::cout << ", ";
        if (timeout > 0) std::cout << timeout << " timed out";
        std::cout << ")\n";
      }
      else
        std::cout << "  => PASSED\n";

      std::cout << "\n";
      total_pass += pass;
      total_timeout += timeout;
      total_crash += crash;
    }
  };

  int total_pass = 0, total_timeout = 0, total_crash = 0;

  run_section("Section A: alps_es WITHOUT init() (Bug 1: unsigned underflow)",
              section_a, 3, total_pass, total_timeout, total_crash);

  run_section("Section B: alps_es WITH init() (lock contention test)",
              section_b, 3, total_pass, total_timeout, total_crash);

  run_section("Section C: std_es WITHOUT init() (Bug 2: SEGFAULT)",
              section_c, 1, total_pass, total_timeout, total_crash);

  std::cout << "=== Totals: " << total_pass << " passed, "
            << total_timeout << " timed out, "
            << total_crash << " crashed ===\n\n";

  std::cout << "Expected results:\n";
  std::cout << "  Section A: ALL timeout (tournament_size=0 -> SIZE_MAX loop)\n";
  std::cout << "  Section B: ALL pass (tournament_size=5, no underflow)\n";
  std::cout << "  Section C: crash signal 11 (empty parents[0] access)\n";

  return 0;
}

CMakeLists.txt

cmake_minimum_required(VERSION 3.24)
project(alps_repro LANGUAGES CXX)

set(CMAKE_CXX_STANDARD 23)
set(CMAKE_CXX_STANDARD_REQUIRED ON)

include(FetchContent)

# Only apply the <print> compatibility patch (needed for compilation).
# Do NOT apply the ALPS lock fix -- we want to reproduce the bug.
set(PRINT_PATCH ${CMAKE_CURRENT_SOURCE_DIR}/print-compat.patch)
FetchContent_Declare(
  ultra
  GIT_REPOSITORY https://github.com/morinim/ultra.git
  GIT_TAG        main
  SOURCE_SUBDIR  src
  PATCH_COMMAND  sh -c "git apply --reverse --check ${PRINT_PATCH} 2>/dev/null || git apply ${PRINT_PATCH}"
)
FetchContent_MakeAvailable(ultra)

add_executable(alps_repro alps_repro.cc)
target_link_libraries(alps_repro PRIVATE ultra)

print-compat.patch

diff --git a/src/utility/log.cc b/src/utility/log.cc
index 6f7eebb..39a4e89 100644
--- a/src/utility/log.cc
+++ b/src/utility/log.cc
@@ -15,7 +15,11 @@
 #include <algorithm>
 #include <chrono>
 #include <fstream>
+#if __has_include(<print>)
 #include <print>
+#else
+#include <iostream>
+#endif
 #include <string_view>

 auto std::formatter<ultra::log::level>::format(ultra::log::level l,
@@ -86,14 +90,26 @@ log::~log()
   if (level_ >= reporting_level)  // `stdout` is selective
   {
     // Clear the line using a width specifier and a carriage return.
+#if __cpp_lib_print >= 202207L
     std::print("\r{:60}\r", "");
+#else
+    std::cout << "\r" << std::string(60, ' ') << "\r";
+#endif

     // Print the tag if necessary.
     if (level_ != lSTDOUT && level_ != lPAROUT)
+#if __cpp_lib_print >= 202207L
       std::print("[{}] ", level_);
+#else
+      std::cout << "[" << std::format("{}", level_) << "] ";
+#endif

     // Flush for console.
+#if __cpp_lib_print >= 202207L
     std::println("{}", message);
+#else
+    std::cout << message << std::endl;
+#endif
   }
 }