/****************************************************************************
* trace.c
* David Boozer
* June 20, 2000
* 07 November 2007 (modified)
*****************************************************************************
* Turing machine simulator (single step through simulation).
* To compile, use: "gcc -g trace.c -lcurses -ltermcap -o trace"
****************************************************************************/

#include <stdio.h>
#include <curses.h>

#define TAPE_LEN 10000
#define OFFSET 2000
#define NUM_FSM_STATES 256

#define NUM 1
#define ARW 2
#define RL  3

#define ARROW_U 65
#define ARROW_D 66
#define ARROW_R 67
#define ARROW_L 68

#define INDEX_L (OFFSET - 15)
#define INDEX_R (OFFSET + 60)

FILE *input_file;

int line_num = 1;
int token_val;
int lookahead;

WINDOW *win;

int fsm[2*NUM_FSM_STATES];

typedef struct {
  int head_pos;
  int fsm_state;
  char tape[TAPE_LEN];
} tm_state;

void syntax_error () {
  fprintf (stderr, "Error: syntax error in line %d\n", line_num);
  exit (0);
}

int next_token () {
  char t;
  
  while (1) {
    t = getc (input_file);
    if (t == ' ' || t == '\t') ;
    else if (t == '\n') line_num++;
    else if (t == ';') {
      do
	t = getc (input_file);
      while (t != '\n' && t != EOF);
      line_num++;
    }
    else if (isdigit(t)) {
      ungetc (t, input_file);
      fscanf (input_file, "%d", &token_val);
      return NUM;
    }
    else if (t == '-') {
      if (getc (input_file) != '-') syntax_error ();
      if (getc (input_file) != '>') syntax_error ();
      return ARW;
    }
    else if (t == 'R' || t == 'L') {
      token_val = t;
      return RL;
    }
    else if (t == EOF) return EOF;
    else syntax_error ();
  }
}

void match (int token) {
  if (lookahead == token) lookahead = next_token ();
  else {
    fclose (input_file);
    syntax_error ();
  }
}

int match_index () {
  int fsm_state, bit;

  fsm_state = token_val;
  match (NUM);
  bit = token_val;
  match (NUM);
  if (bit != 0 && bit != 1) syntax_error ();
  return fsm_state<<1 | bit;
}

void parse () {
  int index, n;
  static next_index = 2;
  
  index = match_index ();
  if (index != next_index++) {
    fprintf (stderr, "Error: fsm entry skipped in line %d\n", line_num);
    fclose (input_file);
    exit (0);
  }
  match (ARW);
  n = match_index ();
  if (token_val == 'R') fsm[index] = n<<1 | 0;
  if (token_val == 'L') fsm[index] = n<<1 | 1;
  match (RL);
}

void load_fsm (char *file_name) {

  input_file = fopen (file_name, "r");
  if (input_file == NULL) {
    fprintf (stderr, "Error: cannot load file %s\n", file_name);
    exit (0);
  }

  lookahead = next_token ();
  while (lookahead != EOF) parse ();

  fclose (input_file);
}

void initialize_state (char *file_name, tm_state *state_ptr) {
  char *tape, t;
  int i;

  input_file = fopen (file_name, "r");
  if (input_file == NULL) {
    fprintf (stderr, "Error: cannot load file %s\n", file_name);
    exit (0);
  }

  tape = state_ptr->tape;
  for (i=0; i<OFFSET; i++) tape[i] = 0;
  do {
    t = fgetc (input_file);
    if (t == '0') tape[i++] = 0;
    if (t == '1') tape[i++] = 1;
  }
  while (t != EOF);
  for (; i<TAPE_LEN; i++) tape[i] = 0;

  fclose (input_file);

  state_ptr->head_pos = OFFSET;
  state_ptr->fsm_state = 1;
}

void print_tape (tm_state *state_ptr) {
  int i;
  char *tape;
  
  tape = state_ptr->tape;

  printw ("%03d ", state_ptr->fsm_state);
  for (i=INDEX_L; i<INDEX_R; i++) {
    attroff (A_UNDERLINE);
    if (i == state_ptr->head_pos) attron (A_UNDERLINE);
    addch(tape[i] ? '1' : '0');
  }
  addch ('\n');

  refresh ();
}

void edit_tape (tm_state *state_ptr) {
  int i, cursor_pos, x, y;
  char *tape, key;

  getyx (win, y, x);  
  tape = state_ptr->tape;
  cursor_pos = state_ptr->head_pos;

  do {
    move (y, 0);
    printw ("%03d ", state_ptr->fsm_state);
    for (i=INDEX_L; i<INDEX_R; i++) addch (tape[i] ? '1' : '0');
    move (y, cursor_pos - INDEX_L + 4);
    refresh ();

    key = getch ();
    switch (key) {
    case ARROW_R:
      cursor_pos++;
      break;
    case ARROW_L:
      cursor_pos--;
      break;
    case ARROW_U:
    case ARROW_D:
      tape[cursor_pos] = tape[cursor_pos]^1;      
    }
  } while (key != ' ');

  move (y, 0);
  print_tape (state_ptr);
}

void simulate_tm (tm_state *state_ptr) {
  int action, fsm_state, head_pos;
  char *tape;
  
  head_pos = state_ptr->head_pos;
  fsm_state = state_ptr->fsm_state;
  tape = state_ptr->tape;

  do {
    state_ptr->head_pos = head_pos;
    state_ptr->fsm_state = fsm_state;
    edit_tape (state_ptr);

    action = fsm[fsm_state<<1 | tape[head_pos]];
    fsm_state = action>>2;
    tape[head_pos] = action>>1 & 1;
    if ((action & 1) == 0) head_pos++;
    if ((action & 1) == 1) head_pos--;
  }
  while (fsm_state != 0 && head_pos >= 0 && head_pos < TAPE_LEN);

  if (fsm_state == 0) {
    state_ptr->head_pos = head_pos;
    state_ptr->fsm_state = fsm_state;
    print_tape (state_ptr);
    printw ("*** Done ***\n");
    do {} while (getch () != 'q');
    endwin ();
    return;
  }
  else {
    endwin ();
    fprintf (stderr, "Error: head exceeded tape bounds\n");
    exit (0);
  }
}

int main (int argc, char *argv[]) {
  tm_state state;

  if (argc != 3) {
    fprintf (stderr, "syntax: tm <machine file> <tape file>\n");
    exit (0);
  }

  load_fsm (argv[1]);
  initialize_state (argv[2], &state);

  win = initscr ();
  scrollok (win, TRUE);
  noecho ();
  clear ();
  refresh ();

  simulate_tm (&state);

  return (0);
}