solve in background thread

11 files changed, 444 insertions, 57 deletions

diff --git a/meson.build b/meson.build
index 49e1d13..94178d2 100644
--- a/meson.build
+++ b/meson.build
@@ -40,6 +40,7 @@ sok_exe = executable('sok', sources + [
   'src/sdl/main.c',
   'src/sdl/theme.c',
   'src/sdl/log-renderer-info.c',
+  'src/sdl/solve.c',
 ], dependencies: [
   dependency('SDL2'),
   dependency('SDL2_ttf'),
diff --git a/src/sdl/action.c b/src/sdl/action.c
index 415c3f5..18badc1 100644
--- a/src/sdl/action.c
+++ b/src/sdl/action.c
@@ -1,5 +1,8 @@
 #include "../core/sok.h"
 #include "action.h"
+#include "solve.h"
+#include "game-state.h"
+#include "util.h"
 
 #define CASE_DIGIT \
   case SDLK_0: \
@@ -94,20 +97,47 @@ get_wheel_action(
 
 action_t
 get_action(
-  const SDL_Event * const ev
+  const game_state_t state,
+  const SDL_Event * const ev,
+  const Uint32 solve_event_type
 ) {
   switch (ev->type) {
   case SDL_QUIT:
     return (action_t) { .type = ACTION_QUIT };
     break;
-  case SDL_KEYUP:
-    return get_key_action(ev->key.keysym.sym);
-    break;
   case SDL_MOUSEWHEEL:
     return get_wheel_action(ev->wheel.y);
     break;
+  case SDL_KEYUP:
+    if (state == GAME_STATE_SOLVE) {
+      return (action_t) { .type = ACTION_SOLVE_CANCEL };
+    } else {
+      return get_key_action(ev->key.keysym.sym);
+    }
+    break;
   default:
-    // ignore event
-    return (action_t) { .type = ACTION_NONE };
+    if (state == GAME_STATE_SOLVE && ev->type == solve_event_type) {
+      switch (ev->user.code) {
+      case SOLVE_EVENT_STEP:
+        return (action_t) {
+          .type = ACTION_SOLVE_EVENT_STEP,
+          .data = solve_get_num_steps(ev->user.data1),
+        };
+        break;
+      case SOLVE_EVENT_FAIL:
+        warn("solve failed: %s", ev->user.data2 ? ev->user.data2 : "unknown error");
+        return (action_t) { .type = ACTION_SOLVE_EVENT_FAIL };
+        break;
+      case SOLVE_EVENT_DONE:
+        return (action_t) { .type = ACTION_SOLVE_EVENT_DONE };
+        break;
+      default:
+        // ignore event
+        break;
+      }
+    }
   }
+
+  // ignore event
+  return (action_t) { .type = ACTION_NONE };
 }
diff --git a/src/sdl/action.h b/src/sdl/action.h
index e28f9ce..afe6fd3 100644
--- a/src/sdl/action.h
+++ b/src/sdl/action.h
@@ -2,6 +2,7 @@
 #define ACTION_H
 
 #include <SDL.h>
+#include "game-state.h"
 
 typedef enum {
   ACTION_NONE,
@@ -16,6 +17,10 @@ typedef enum {
   ACTION_UNDO,
   ACTION_NEXT,
   ACTION_SOLVE,
+  ACTION_SOLVE_CANCEL,
+  ACTION_SOLVE_EVENT_STEP,
+  ACTION_SOLVE_EVENT_FAIL,
+  ACTION_SOLVE_EVENT_DONE,
   ACTION_RESET,
   ACTION_FULLSCREEN,
   ACTION_LAST,
@@ -26,6 +31,10 @@ typedef struct {
   uint64_t data;
 } action_t;
 
-action_t get_action(const SDL_Event * const);
+action_t get_action(
+  const game_state_t,
+  const SDL_Event * const,
+  const Uint32
+);
 
 #endif /* ACTION_H */
diff --git a/src/sdl/draw.c b/src/sdl/draw.c
index 5bb8de7..322bd7a 100644
--- a/src/sdl/draw.c
+++ b/src/sdl/draw.c
@@ -230,12 +230,16 @@ draw_help_text(
 
   // build text
   char buf[256];
+  if (draw_ctx->state == GAME_STATE_SOLVE) {
+    snprintf(buf, sizeof(buf), " Space: Cancel ");
+  } else {
 #define D "     "
-  snprintf(
-    buf, sizeof(buf),
-    " %sU: Undo" D "R: Reset" D "S: Solve" D "Q: Quit ",
-    sok_ctx_is_done(draw_ctx->ctx) ? "Space: Next Level" D : ""
-  );
+    snprintf(
+      buf, sizeof(buf),
+      " %sU: Undo" D "R: Reset" D "S: Solve" D "Q: Quit ",
+      sok_ctx_is_done(draw_ctx->ctx) ? "Space: Next Level" D : ""
+    );
+  }
 #undef D
 
   // draw text
@@ -243,6 +247,42 @@ draw_help_text(
 }
 
 static void
+draw_solve_wait_text(
+  draw_ctx_t * const draw_ctx
+) {
+  if (draw_ctx->state != GAME_STATE_SOLVE) {
+    return;
+  }
+
+  // get text style
+  const text_style_t *style = theme_get_text_style(draw_ctx->theme, TEXT_STYLE_SOLVE_WAIT);
+  const char *text = " Solving, Please Wait (press space to cancel) ";
+
+  // draw text
+  draw_text(draw_ctx->renderer, draw_ctx->font, style, text);
+}
+
+static void
+draw_solve_moves_text(
+  draw_ctx_t * const draw_ctx
+) {
+  if (draw_ctx->state != GAME_STATE_SOLVE) {
+    return;
+  }
+
+  // get text style
+  const text_style_t *style = theme_get_text_style(draw_ctx->theme, TEXT_STYLE_SOLVE_MOVES);
+  char buf[1024];
+
+  // fill buffer
+  snprintf(buf, sizeof(buf), " %lu attempts ", draw_ctx->solve_num_steps);
+
+  // draw text
+  draw_text(draw_ctx->renderer, draw_ctx->font, style, buf);
+}
+
+
+static void
 draw_bg(
   draw_ctx_t * const draw_ctx
 ) {
@@ -281,6 +321,8 @@ draw(
   draw_title_text(draw_ctx);
   draw_help_text(draw_ctx);
   draw_moves_text(draw_ctx);
+  draw_solve_wait_text(draw_ctx);
+  draw_solve_moves_text(draw_ctx);
 
   // flip
   SDL_RenderPresent(draw_ctx->renderer);
diff --git a/src/sdl/draw.h b/src/sdl/draw.h
index 7be5a28..f947a70 100644
--- a/src/sdl/draw.h
+++ b/src/sdl/draw.h
@@ -7,6 +7,8 @@
 #include "../core/sok.h" 
 #include "../levels/levels.h"
 #include "theme.h"
+#include "game-state.h"
+#include "solve.h"
 
 // arbitrary
 #define MAX_SPRITES 32
@@ -28,6 +30,10 @@ typedef struct {
   Uint32 ticks;
 
   const theme_t * const theme;
+
+  game_state_t state;
+  solve_t *solve;
+  size_t solve_num_steps;
 } draw_ctx_t;
 
 void draw(draw_ctx_t * const);
diff --git a/src/sdl/game-state.h b/src/sdl/game-state.h
new file mode 100644
index 0000000..f3bd8d4
--- /dev/null
+++ b/src/sdl/game-state.h
@@ -0,0 +1,10 @@
+#ifndef GAME_STATE_H
+#define GAME_STATE_H
+
+typedef enum {
+  GAME_STATE_PLAY,
+  GAME_STATE_SOLVE,
+  GAME_STATE_LAST,
+} game_state_t;
+
+#endif /* GAME_STATE_H */
diff --git a/src/sdl/main.c b/src/sdl/main.c
index c3a9abe..8e96fa5 100644
--- a/src/sdl/main.c
+++ b/src/sdl/main.c
@@ -12,25 +12,7 @@
 #include "draw.h"
 #include "log-renderer-info.h"
 #include "assets.h"
-
-static void
-log_moves(
-  const sok_ctx_t * const ctx,
-  const size_t skip_moves
-) {
-  char buf[1024] = { 0 };
-  size_t ofs = 0;
-
-  for (size_t i = skip_moves; i < ctx->num_moves; i++) {
-    if (ctx->moves[i].dir >= SOK_DIR_LAST) {
-      die("invalid move: %u", ctx->moves[i].dir);
-    }
-
-    buf[ofs++] = SOK_DIR_TO_CHAR(ctx->moves[i].dir);
-  }
-
-  SDL_Log("Solution (%d moves): %s", (int) (ctx->num_moves - skip_moves), buf);
-}
+#include "solve.h"
 
 static TTF_Font *
 load_font(
@@ -59,20 +41,6 @@ load_font(
 }
 
 static void
-solve_on_error(
-  const char * const err,
-  void *user_data
-) {
-  UNUSED(user_data);
-  die("Error solving level: %s", err);
-}
-
-static const sok_solve_cbs_t
-SOLVE_CBS = {
-  .on_error = solve_on_error,
-};
-
-static void
 set_level(
   draw_ctx_t * const draw_ctx,
   sok_ctx_t * const ctx,
@@ -95,6 +63,41 @@ set_level(
   );
 }
 
+static void
+log_moves(
+  const sok_ctx_t * const ctx
+) {
+  char buf[1024] = { 0 };
+  size_t ofs = 0;
+
+  for (size_t i = 0; i < ctx->num_moves; i++) {
+    if (ctx->moves[i].dir >= SOK_DIR_LAST) {
+      die("invalid move: %u", ctx->moves[i].dir);
+    }
+
+    buf[ofs++] = SOK_DIR_TO_CHAR(ctx->moves[i].dir);
+  }
+
+  SDL_Log("Solution (%d moves): %s", (int) ctx->num_moves, buf);
+}
+
+static void
+solve_on_done(
+  const bool result,
+  const sok_ctx_t * const solved_ctx,
+  const size_t num_steps,
+  void *user_data
+) {
+  if (result) {
+    // copy context
+    sok_ctx_t *ctx = user_data;
+    *ctx = *solved_ctx;
+
+    // log moves
+    log_moves(ctx);
+  }
+}
+
 int main(int argc, char *argv[]) {
   size_t level_num = (argc > 1) ? atoi(argv[1]) : 0,
          zoom = 0;
@@ -154,6 +157,7 @@ int main(int argc, char *argv[]) {
 
   // init draw context
   draw_ctx_t draw_ctx = {
+    .state      = GAME_STATE_PLAY,
     .level_num  = &level_num,
     .ctx        = &ctx,
     .renderer   = renderer,
@@ -168,6 +172,12 @@ int main(int argc, char *argv[]) {
   sprites_init(renderer, draw_ctx.sprites);
   draw_ctx.font = load_font(ASSET_ROBOTO_TTF);
 
+  // register solve event
+  const Uint32 solve_event_type = SDL_RegisterEvents(1);
+  if (solve_event_type == ((Uint32)-1)) {
+    die("SDL_RegisterEvents(): %s", SDL_GetError());
+  }
+
   bool is_fullscreen = false;
   bool done = false;
   while (!done) {
@@ -176,7 +186,7 @@ int main(int argc, char *argv[]) {
     // read events
     while (SDL_PollEvent(&ev)) {
       // get action
-      const action_t action = get_action(&ev);
+      const action_t action = get_action(draw_ctx.state, &ev, solve_event_type);
 
       // handle action
       switch (action.type) {
@@ -236,17 +246,9 @@ int main(int argc, char *argv[]) {
 
         break;
       case ACTION_SOLVE:
-        {
-          // get current number of moves
-          const size_t old_num_moves = ctx.num_moves;
-
-          if (sok_solve(&ctx, &SOLVE_CBS, NULL)) {
-            // found solution, print it
-            log_moves(&ctx, old_num_moves);
-          } else {
-            warn("Couldn't solve level");
-          }
-        }
+        draw_ctx.state = GAME_STATE_SOLVE;
+        draw_ctx.solve_num_steps = 0;
+        draw_ctx.solve = solve(&ctx, solve_event_type);
 
         break;
       case ACTION_ZOOM_IN:
@@ -270,6 +272,31 @@ int main(int argc, char *argv[]) {
         is_fullscreen = !is_fullscreen;
 
         break;
+      case ACTION_SOLVE_CANCEL:
+        SDL_Log("solve cancelled by user");
+        draw_ctx.state = GAME_STATE_PLAY;
+        solve_cancel(draw_ctx.solve);
+
+        break;
+      case ACTION_SOLVE_EVENT_STEP:
+        draw_ctx.solve_num_steps = action.data;
+
+        break;
+      case ACTION_SOLVE_EVENT_DONE:
+        SDL_Log("solve done");
+        draw_ctx.state = GAME_STATE_PLAY;
+        // TODO: handle success
+        solve_fini(draw_ctx.solve, solve_on_done, &ctx);
+        draw_ctx.solve = NULL;
+
+        break;
+      case ACTION_SOLVE_EVENT_FAIL:
+        SDL_Log("solve fail");
+        draw_ctx.state = GAME_STATE_PLAY;
+        solve_fini(draw_ctx.solve, NULL, NULL);
+        draw_ctx.solve = NULL;
+
+        break;
       default:
         // ignore
         break;
diff --git a/src/sdl/solve.c b/src/sdl/solve.c
new file mode 100644
index 0000000..0fee274
--- /dev/null
+++ b/src/sdl/solve.c
@@ -0,0 +1,218 @@
+#include <stdbool.h> // bool
+#include <errno.h> // errno
+#include <string.h> // strerror()
+#include <SDL.h>
+#include "util.h"
+#include "solve.h"
+
+struct solve_t_ {
+  SDL_mutex *mutex;
+
+  // thread-private copy of context
+  sok_ctx_t ctx;
+
+  Uint32 solve_event_type;
+
+  // number of moves at call to solve()
+  size_t old_num_moves;
+
+  // number of times the on_step cb has been invoked
+  size_t num_steps;
+  
+  // result of solve
+  bool result;
+
+  // cancel solve
+  bool cancel;
+};
+
+static void
+push_event(
+  solve_t * const data,
+  const solve_event_type_t type,
+  void *user_data
+) {
+  // alloc/clear event
+  SDL_Event ev;
+  memset(&ev, 0, sizeof(SDL_Event));
+
+  // init event
+  ev.type = data->solve_event_type;
+  ev.user.code = (Sint32) type;
+  ev.user.data1 = data;
+  ev.user.data2 = user_data;
+  
+  // push event
+  if (!SDL_PushEvent(&ev)) {
+    die("SDL_PushEvent(): %s", SDL_GetError());
+  }
+}
+
+static bool
+solve_on_step(
+  const sok_ctx_t * const ctx,
+  void *user_data
+) {
+  solve_t *data = user_data;
+  UNUSED(ctx);
+
+  // lock mutex
+  if (SDL_LockMutex(data->mutex)) {
+    die("SDL_LockMutex(): %s", SDL_GetError());
+  }
+
+  // increment number of steps
+  data->num_steps++;
+
+  // cache number of steps and cancel state
+  const size_t num_steps = data->num_steps;
+  const bool cancel = data->cancel;
+
+  // unlock mutex
+  if (SDL_UnlockMutex(data->mutex)) {
+    die("SDL_UnlockMutex(): %s", SDL_GetError());
+  }
+
+  if ((num_steps % 100) == 0) {
+    // push event
+    push_event(data, SOLVE_EVENT_STEP, NULL);
+  }
+
+  // return false if cancelled
+  return !cancel;
+}
+
+static void
+solve_on_error(
+  const char * const err,
+  void *user_data
+) {
+  solve_t *data = user_data;
+  UNUSED(user_data);
+  // die("Error solving level: %s", err);
+  push_event(data, SOLVE_EVENT_FAIL, (void*) err);
+}
+
+static const sok_solve_cbs_t
+SOLVE_CBS = {
+  .on_step  = solve_on_step,
+  .on_error = solve_on_error,
+};
+
+static int
+solve_thread(
+  void * const thread_data
+) {
+  solve_t *data = thread_data;
+  warn("solve started");
+
+  // solve board
+  data->result = sok_solve(&(data->ctx), &SOLVE_CBS, data);
+  if (data->result) {
+    // push success
+    push_event(data, SOLVE_EVENT_DONE, NULL);
+  }
+  warn("solve done");
+
+  return 0;
+}
+
+solve_t *
+solve(
+  const sok_ctx_t * const ctx,
+  const Uint32 solve_event_type
+) {
+  // create thread mutex
+  SDL_mutex *mutex = SDL_CreateMutex();
+  if (!mutex) {
+    die("SDL_CreateMutex(): %s", SDL_GetError());
+  }
+
+  // alloc solve thread data
+  solve_t *data = malloc(sizeof(solve_t));
+  if (!data) {
+    die("malloc(): %s", strerror(errno));
+  }
+
+  // init solve data
+  data->mutex = mutex;
+  data->ctx = *ctx;
+  data->solve_event_type = solve_event_type;
+  data->old_num_moves = ctx->num_moves;
+  data->num_steps = 0;
+  data->result = false;
+  data->cancel = false;
+
+  // create solve thread
+  SDL_Thread *thread = SDL_CreateThread(solve_thread, "solve", data);
+  if (!thread) {
+    die("SDL_CreateThread(): %s", SDL_GetError());
+  }
+
+  // detach thread
+  SDL_DetachThread(thread);
+
+  SDL_Log("Solving (thread ID = %lu, address = %p)", SDL_GetThreadID(thread), thread);
+
+  // return thread data
+  return data;
+}
+
+void
+solve_fini(
+  solve_t * const data,
+  void (*on_done)(const bool, const sok_ctx_t *, const size_t, void *),
+  void *user_data
+) {
+  if (on_done) {
+    // call handler
+    on_done(data->result, &(data->ctx), data->num_steps, user_data);
+  }
+
+  // free mutex
+  SDL_DestroyMutex(data->mutex);
+  data->mutex = NULL;
+
+  // free thread data
+  free(data);
+}
+
+void
+solve_cancel(solve_t * const data) {
+  // lock mutex
+  if (SDL_LockMutex(data->mutex)) {
+    die("SDL_LockMutex(): %s", SDL_GetError());
+  }
+
+  // set cancel
+  data->cancel = true;
+
+  // lock mutex
+  if (SDL_UnlockMutex(data->mutex)) {
+    die("SDL_UnlockMutex(): %s", SDL_GetError());
+  }
+}
+
+size_t
+solve_get_num_steps(solve_t * const data) {
+  // lock mutex
+  if (SDL_LockMutex(data->mutex)) {
+    die("SDL_LockMutex(): %s", SDL_GetError());
+  }
+
+  // get num steps
+  const size_t num_steps = data->num_steps;
+
+  // lock mutex
+  if (SDL_UnlockMutex(data->mutex)) {
+    die("SDL_UnlockMutex(): %s", SDL_GetError());
+  }
+
+  // return num_steps
+  return num_steps;
+}
+
+bool
+solve_get_result(solve_t * const data) {
+  return data->result;
+}
diff --git a/src/sdl/solve.h b/src/sdl/solve.h
new file mode 100644
index 0000000..0bd0ae1
--- /dev/null
+++ b/src/sdl/solve.h
@@ -0,0 +1,28 @@
+#ifndef SOLVE_H
+#define SOLVE_H
+
+#include <SDL.h>
+#include "../core/sok.h"
+
+typedef enum {
+  SOLVE_EVENT_STEP,
+  SOLVE_EVENT_FAIL,
+  SOLVE_EVENT_DONE,
+  SOLVE_EVENT_LAST,
+} solve_event_type_t;
+
+struct solve_t_;
+typedef struct solve_t_ solve_t;
+
+solve_t *solve(const sok_ctx_t * const, const Uint32);
+void solve_fini(
+  solve_t * const,
+  void (*)(const _Bool, const sok_ctx_t *, const size_t, void *),
+  void *
+);
+void solve_cancel(solve_t * const);
+
+size_t solve_get_num_steps(solve_t * const);
+_Bool solve_get_result(solve_t * const);
+
+#endif /* SOLVE_H */
diff --git a/src/sdl/theme.c b/src/sdl/theme.c
index 93b7950..680b6ee 100644
--- a/src/sdl/theme.c
+++ b/src/sdl/theme.c
@@ -24,6 +24,20 @@ DEFAULT_THEME = {
       { 0xff, 0xff, 0xff, 0xff },
       { 0x00, 0x00, 0x00, 0xff },
     },
+  }, {
+    .align  = TEXT_ALIGN_CENTER_CENTER,
+    .pad    = { 0, 0 },
+    .colors = {
+      { 0xff, 0xff, 0xff, 0xff },
+      { 0x00, 0x00, 0x00, 0xff },
+    },
+  }, {
+    .align  = TEXT_ALIGN_TOP_RIGHT,
+    .pad    = { 10, 10 },
+    .colors = {
+      { 0xff, 0xff, 0xff, 0xff },
+      { 0x00, 0x00, 0x00, 0xff },
+    },
   }},
 
   .bg_styles = {{
diff --git a/src/sdl/theme.h b/src/sdl/theme.h
index 562df3f..36f75f2 100644
--- a/src/sdl/theme.h
+++ b/src/sdl/theme.h
@@ -8,6 +8,8 @@ typedef enum {
   TEXT_STYLE_TITLE,
   TEXT_STYLE_MOVES,
   TEXT_STYLE_HELP,
+  TEXT_STYLE_SOLVE_WAIT,
+  TEXT_STYLE_SOLVE_MOVES,
   TEXT_STYLE_LAST,
 } text_style_id_t;