/* book.c -- the opening book module for xboard-engine-tactical.
 *
 * See book.h for the five functions the rest of the engine actually
 * calls, and the file header comment there for when each is called.
 * Everything below is private to this file.
 *
 * This module has no dependency on the SAN Kit chess engine at all
 * -- not even a shared typedef, deliberately: everything here uses
 * plain C types (int, char *) rather than sandef.h's siT and
 * friends, both to keep that independence concrete rather than
 * accidental, and because sandef.h has no #ifndef include guard of
 * its own, so a second, indirect #include of it from here (on top
 * of the direct one in xboard-engine-tactical.c) would otherwise
 * redefine every type and struct in it and fail to compile. This
 * module only ever deals with move text and a generic tree, never a real chess position, move generator, or
 * board. It doesn't know, or need to know, whether "e2e4" is a
 * legal chess move -- only whether it's the text the caller is
 * looking for. That's what makes it possible to build and check
 * this module entirely on its own, and equally possible to drop it
 * into a different engine's source tree largely unchanged.
 *
 * File format
 * ------------
 * Loaded from two plain-text files, "white.txt" and "black.txt", in
 * the working directory (missing or unreadable files simply disable
 * the book -- this is an optional enhancement, never a requirement
 * to run). Each file is a single, whitespace-free tree of moves in
 * coordinate notation, written as nested parenthesised
 * s-expressions: "(move child child ...)", where several
 * parenthesised groups at the same nesting level are alternative
 * moves recorded from that same position (chosen among at random
 * when it's this engine's turn to play one, and matched against
 * when it's the opponent's).
 *
 * white.txt's top level is this engine's own first move (as White);
 * one level down is the opponent's (Black's) reply; and so on,
 * alternating. black.txt is the mirror image: top level is the
 * opponent's (White's) first move, one level down is this engine's
 * (Black's) reply. Which file applies is decided by whichever of
 * TryBookMove() (this engine is asked to move first) or
 * BookNoteOpponentMove() (the opponent's move arrives first) is
 * called first in a given game -- see book_started below.
 */

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>

#include "book.h"

typedef struct BookNodeS
{
  char move[6];                 /* "e2e4" or "e7e8q", NUL-terminated */
  struct BookNodeS *first_child;
  struct BookNodeS *next_sibling;
}
BookNodeT;

static BookNodeT *white_book;   /* top-level list from white.txt, or
                                    NULL if that file wasn't usable */
static BookNodeT *black_book;   /* likewise, from black.txt */

/* whether this game has settled on which of the two trees above
   applies yet (see the file header comment); once true, book_cursor
   is what actually gets consulted from then on */
static int book_started;
static BookNodeT *book_cursor;

/* set whenever this game is known not to be following a recorded
   book line any more (including from the very start, if "setboard"
   was used with anything other than the standard starting
   position) -- checked before book_started even matters */
static int book_disabled;

/*--> ReadWholeFile: read an entire file into a single freshly
      malloc()'d, NUL-terminated buffer; returns NULL (without
      complaint -- the caller decides whether that's worth a
      message) if the file can't be opened or read */
static char *
ReadWholeFile (const char *path)
{
  FILE *f;
  long size;
  char *buf;

  f = fopen (path, "rb");
  if (f == NULL)
    return (NULL);

  if ((fseek (f, 0, SEEK_END) != 0) || ((size = ftell (f)) < 0) ||
      (fseek (f, 0, SEEK_SET) != 0))
    {
      fclose (f);
      return (NULL);
    };

  buf = (char *) malloc ((size_t) size + 1);
  if (buf == NULL)
    {
      fclose (f);
      return (NULL);
    };

  if (fread (buf, 1, (size_t) size, f) != (size_t) size)
    {
      free (buf);
      fclose (f);
      return (NULL);
    };
  buf[size] = '\0';

  fclose (f);
  return (buf);
}

/* cursor used only while parsing (LoadBookFile()/BookParse*()); not
   meaningful at any other time */
static char *book_parse_pos;

static BookNodeT *BookParseNodeList (void);

/*--> BookParseMove: parse one "(move child*)" group at
      *book_parse_pos (which must be pointing at its opening '(')
      and return it, having advanced book_parse_pos past its
      closing ')' */
static BookNodeT *
BookParseMove (void)
{
  BookNodeT *node;
  char *start;
  size_t len;

  book_parse_pos++;             /* consume '(' */
  start = book_parse_pos;
  while (isalnum ((unsigned char) *book_parse_pos))
    book_parse_pos++;
  len = (size_t) (book_parse_pos - start);
  if (len >= sizeof (node->move))
    len = sizeof (node->move) - 1;        /* defensive; never
                                              actually needed for a
                                              well-formed book */

  node = (BookNodeT *) malloc (sizeof (BookNodeT));
  memcpy (node->move, start, len);
  node->move[len] = '\0';

  node->first_child = BookParseNodeList ();
  node->next_sibling = NULL;

  if (*book_parse_pos == ')')
    book_parse_pos++;           /* consume ')' */

  return (node);
}

/*--> BookParseNodeList: parse zero or more consecutive "(move...)"
      groups at *book_parse_pos into a sibling list, stopping at the
      first character that isn't '(' (typically the ')' closing the
      parent, or end of file at the top level) */
static BookNodeT *
BookParseNodeList (void)
{
  BookNodeT *head, *tail, *node;

  head = NULL;
  tail = NULL;
  while (*book_parse_pos == '(')
    {
      node = BookParseMove ();
      if (tail == NULL)
        head = node;
      else
        tail->next_sibling = node;
      tail = node;
    };

  return (head);
}

/*--> LoadBookFile: parse an entire book file into a tree and return
      its top-level sibling list, or NULL (with a one-line stderr
      comment either way) if the file couldn't be read. Private to
      this module -- see LoadBooks() below for the public,
      no-argument entry point the rest of the engine actually
      calls. */
static BookNodeT *
LoadBookFile (const char *path)
{
  char *text;
  BookNodeT *tree;

  text = ReadWholeFile (path);
  if (text == NULL)
    {
      fprintf (stderr,
        "# book: %s not found or unreadable; opening book from it "
        "disabled\n", path);
      return (NULL);
    };

  book_parse_pos = text;
  tree = BookParseNodeList ();
  free (text);

  fprintf (stderr, "# book: loaded %s\n", path);

  return (tree);
}

/*--> LoadBooks: see book.h */
void
LoadBooks (void)
{
  white_book = LoadBookFile ("white.txt");
  black_book = LoadBookFile ("black.txt");

  return;
}

/*--> BookCountAndPick: count the siblings in a list and return the
      one at a uniformly random index -- used whenever it's this
      engine's own turn to play a book move, so it doesn't play the
      exact same game every time it has a choice */
static BookNodeT *
BookCountAndPick (BookNodeT *list)
{
  BookNodeT *p;
  int n, pick;

  n = 0;
  for (p = list; p != NULL; p = p->next_sibling)
    n++;

  pick = rand () % n;
  p = list;
  while (pick-- > 0)
    p = p->next_sibling;

  return (p);
}

/*--> TryBookMove: see book.h */
int
TryBookMove (char *coord)
{
  BookNodeT *candidates, *chosen;

  if (book_disabled)
    return (0);

  candidates = book_started ? book_cursor : white_book;
  book_started = 1;

  if (candidates == NULL)
    return (0);

  chosen = BookCountAndPick (candidates);
  strcpy (coord, chosen->move);
  book_cursor = chosen->first_child;

  fprintf (stderr, "# book: playing %s\n", coord);

  return (1);
}

/*--> BookNoteOpponentMove: see book.h */
void
BookNoteOpponentMove (const char *coord)
{
  BookNodeT *candidates, *p;

  if (book_disabled)
    return;

  candidates = book_started ? book_cursor : black_book;
  book_started = 1;

  p = NULL;
  if (candidates != NULL)
    for (p = candidates; p != NULL; p = p->next_sibling)
      if (strcmp (p->move, coord) == 0)
        break;

  if (p == NULL)
    {
      if (book_cursor != NULL || !book_started)
        fprintf (stderr,
          "# book: %s is not a recorded continuation; leaving the "
          "book for the rest of this game\n", coord);
      book_cursor = NULL;
    }
  else
    book_cursor = p->first_child;

  return;
}

/*--> BookReset: see book.h */
void
BookReset (void)
{
  book_started = 0;
  book_cursor = NULL;
  book_disabled = 0;

  return;
}

/*--> BookDisable: see book.h */
void
BookDisable (void)
{
  book_disabled = 1;

  return;
}
