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

/*
 * ©2022 Daniel Barowy
 *
 * Version history.
 * 2020-02-02, v1.0: Initial version.
 * 2020-02-06, v1.1: Changed j and u return values, added comment feature, better debugging output, and documented code.
 * 2020-02-07, v1.2: Better loop handling.
 * 2020-02-12, v1.3: Disable stdout buffering.
 */

#define FAIL(s) { fail(s); exit(EXIT_FAILURE); }
#define MEM_SZ 30000
#define min(a,b) (((a) < (b)) ? (a) : (b))

/* DATA TYPES */
typedef enum opcode {
  ICHAR,
  INUM,
  OCHAR,
  ONUM,
  INCREMENT,
  DECREMENT,
  STORE,
  STOREPTR,
  SCRATCH,
  RESTORE,
  DEREFERENCE,
  ADDRESSOF,
  JUMP,
  UNJUMP,
  NEWLINE,
  COMMENT,
  NOP,
  UNKNOWN
} opcode_t;

typedef struct operation {
  opcode_t code;
  int      nesting;
} op_t;

/**
 * Operation constructor.
 * @param code     An opcode.
 * @param nesting  The nesting level of the operation.
 */
op_t op(opcode_t code, int nesting) {
  op_t op;
  op.code = code;
  op.nesting = nesting;
  return op;
}

typedef struct result {
  opcode_t  code;
  int       result;
  int       scratch;
  int       nesting;
} res_t;

/**
 * State vector constructor.
 */
res_t retval(opcode_t code, int result, int scratch, int nesting) {
  res_t res;
  res.code = code;
  res.result = result;
  res.scratch = scratch;
  res.nesting = nesting;
  return res;
}

/**
 * A simple function that prints an error message.
 */
void fail(char* errorMessage) {
  printf("%s", errorMessage);
}

/**
 * Print usage information and quit.
 */
void usage() {
  printf("\nUsage: ./breph [-d] <file>\n");
  printf("\nBreph is a Turing machine simulator, with a C-like pointer syntax.\nUnlike a real Turing machine, Breph has a finite tape consisting\nof 30,000 one-byte cells.  The read/write head is initially at\nindex 0 and all cells are initially 0. In the syntax below,\n<e> is the value of the expression cell.\n");
  printf("\nFlags:\n");
  printf("  -d\tWhen the optional debug flag is given, Breph will print out\n\tall machine state and wait for the user to press the [Enter]\n\tkey.\n");
  printf("\nBreph syntax:\n");
  printf("\n  Input\n");
  printf("  i\tPrompt for a character of input and return it.\n");
  printf("  n\tPrompt for a character of input, interpret it as a number,\n\tand return it as a number.\n");
  printf("\n  Output\n");
  printf("  o\tPrint <e> as a character and return <e>.\n");
  printf("  #\tPrint <e> as a numeric character and return <e>.\n");
  printf("\n  Math\n");
  printf("  +\tAdd one to <e> and return it.\n");
  printf("  -\tSubtract one <e> and return it.\n");
  printf("\n  Pointer operations\n");
  printf("  *\tReturn the contents of the current cell.\n");
  printf("  &\tReturn the location of the current cell.\n");
  printf("\n  State\n");
  printf("  .\tStore <e> in the current cell and return <e>.\n");
  printf("  !\tChange the location of the current cell to <e> and return <e>.\n");
  printf("  s\tCopy <e> to the scratch cell and then return <e>.\n");
  printf("  r\tCopy the scratch cell to <e> and then return <e>.\n");
  printf("  \\n\tA new line resets the return value to 0.\n");
  printf("\n  Control flow\n");
  printf("  j\tIf the current cell is zero, jump to the operation after the\n\tnext u, returning <e>.\n");
  printf("  u\tIf the current cell is nonzero, jump to the previous j,\n\treturning <e>.\n");
  printf("\n  Comments\n");
  printf("  %%\tAny line starting with a %% and ending with a newline is\n\tinterpreted as a comment.\n");
  printf("\nExample:\n");
  printf("\t$ ./breph program.eph\n");
  printf("\n");
  printf("Version 1.2, Feb 7, 2022.");
  printf("\n");
  
  exit(EXIT_FAILURE);
}

/**
 * Returns a printable representation of an operation.
*/
char* op_symbol(opcode_t code) {
  switch(code) {
    case ICHAR:
      return "ICHAR";
    case INUM:
      return "INUM";
    case OCHAR:
      return "OCHAR";
    case ONUM:
      return "ONUM";
    case INCREMENT:
      return "INCREMENT";
    case DECREMENT:
      return "DECREMENT";
    case STORE:
      return "STORE";
    case STOREPTR:
      return "STOREPTR";
    case SCRATCH:
      return "SCRATCH";
    case RESTORE:
      return "RESTORE";
    case DEREFERENCE:
      return "DEREFERENCE";
    case ADDRESSOF:
      return "ADDRESSOF";
    case JUMP:
      return "JUMP";
    case UNJUMP:
      return "UNJUMP";
    case NEWLINE:
      return "NEWLINE";
    case COMMENT:
      return "COMMENT";
    case NOP:
      return "NOP";
    default:
      FAIL("Unknown operation.\n");
  }
}

/**
 * Debugging function. Prints the current state.
 * 
 * @param mem  A pointer to an array of integers.
 * @param rv   The last return value.
 * @param ptr  The position of the read/write head.
 */
void dump_state(int* mem, res_t rv, int ptr) {
  // what set memory cell has the largest index?
  int max = 0;
  for (int i = 0; i < MEM_SZ; i++) {
    if (mem[i] != 0) {
      max = i;
    }
  }
  max = max > 3 ? max : 3;

  // draw memory
  char top[(max+1)*4+2];
  char mid[(max+1)*4+2];
  char bot[(max+1)*4+2];
  memset(top, 0, (max+1)*4+2);
  memset(mid, 0, (max+1)*4+2);
  memset(bot, 0, (max+1)*4+2);
  for (int i = 0; i < (max+1); i++) {
    // bars
    for (int j = 0; j < 4; j++) {
      int k = i*4+j;
      top[k] = '-';
      bot[k] = '-';
    }

    // number
    char num[4] = {0};
    int val = min(mem[i], 999);
    snprintf(num, 4, "%.3d", val);
    mid[i*4] = '|';
    for (int j = 0; j < strlen(num); j++) {
      int k = i*4+j;
      mid[k+1] = num[j];
    }
  }
  top[sizeof(top)-2] = '-';
  mid[sizeof(mid)-2] = '|';
  bot[sizeof(bot)-2] = '-';

  // print it
  printf("%s\n%s\n%s\n", top, mid, bot);
  printf("PTR: %d\n", ptr);
  printf(" ER: %d\n", rv.result);
  printf(" SR: %d\n", rv.scratch);
}

/**
 * Parse a line of Breph code, returning the appropriate
 * AST node.  Recurses if there is more than one Breph
 * character in the line.
 *
 * @param c        A character.
 * @param nesting  The current nesting level of the operation.
 */
op_t parse_char(char c, int nesting) {
  switch (c) {
    case ' ':
      return op(NOP, nesting);
    case 'i':
      return op(ICHAR, nesting);
    case 'n':
      return op(INUM, nesting);
    case 'o':
      return op(OCHAR, nesting);
    case '#':
      return op(ONUM, nesting);
    case '+':
      return op(INCREMENT, nesting);
    case '-':
      return op(DECREMENT, nesting);
    case '.':
      return op(STORE, nesting);
    case '!':
      return op(STOREPTR, nesting);
    case '*':
      return op(DEREFERENCE, nesting);
    case '&':
      return op(ADDRESSOF, nesting);
    case 'j':
      return op(JUMP, nesting);
    case 'u': {
      // the one special case: refers to the previous nesting level
      return op(UNJUMP, nesting - 1);
    }
    case 's':
      return op(SCRATCH, nesting);
    case 'r':
      return op(RESTORE, nesting);
    case '\r':
    case '\n':
      return op(NEWLINE, nesting);
    case '%':
      return op(COMMENT, nesting);
    default:
      return op(UNKNOWN, nesting);
  }
}

/**
 * Evaluate the current operation, updating machine state.
 *
 * @param operations  A pointer to an array of operations.
 * @param len         The length of the operations array.
 * @param mem         A pointer to an integer array representing a Breph tape.
 * @param debug       If true, runs in single-step mode.
 */
int eval(const op_t* operations, long len, int* const mem, bool debug) {
  // initalize ptr
  int ptr = 0;
  
  // initialize retvals
  res_t rv = retval(NOP, 0, 0, 0);
  
  for (int i = 0; i < len; i++) {
    start_eval:;

    if (debug && operations[i].code != NOP) {
      char* op_name = op_symbol(operations[i].code);
      printf("Evaluating step %d, op %s\n", i, op_name);
      dump_state(mem, rv, ptr);
      printf("Press [Enter] to continue. ");
      getchar();
    }
    
    switch(operations[i].code) {
      // the following operations should never appear in a command list
      case UNKNOWN:
      case COMMENT:
      {
        FAIL("Unknown operation.\n");
      }
      case NOP:
        break; // do nothing
      case ICHAR:
      {
        if (debug) {
          printf("Enter an input and press [Enter]: ");
        }
        char c = getchar();
        rv = retval(ICHAR, c, rv.scratch, rv.nesting);
        break;
      }
      case INUM:
      {
        if (debug) {
          printf("Enter an input and press [Enter]: ");
        }
        char c = getchar();
        rv = retval(INUM, atoi(&c), rv.scratch, rv.nesting);
        break;
      }
      case OCHAR:
      {
        // only print if the result is not NOP
        if (rv.code != NOP) {
          if (debug) {
            printf("OUTPUT (%d) AS CHAR: '%c'\n", rv.result, rv.result);
          } else {
            printf("%c", rv.result);
          }
          rv = retval(OCHAR, rv.result, rv.scratch, rv.nesting);
        }
        break;
      }
      case ONUM:
      {
        // only print if the result is not NOP
        if (rv.code != NOP) {
          int sz = snprintf(NULL, 0, "%d", rv.result);
          char * c = malloc(sz + 1);
          sprintf(c, "%d", rv.result);
          if (debug) {
            printf("OUTPUT AS NUM: '%s'\n", c);
          } else {
            printf("%s", c);
          }
          free(c);
          rv = retval(ONUM, rv.result, rv.scratch, rv.nesting);
        }
        break;
      }
      case INCREMENT:
      {
        rv = retval(INCREMENT, rv.result + 1, rv.scratch, rv.nesting);
        break;
      }
      case DECREMENT:
      {
        rv = retval(INCREMENT, rv.result - 1, rv.scratch, rv.nesting);
        break;
      }
      case STORE:
      {
        if (ptr < 0 || ptr >= len) {
          FAIL("ERROR: Cannot store out of bounds.\n");
        }
        mem[ptr] = rv.result;
        rv = retval(STORE, rv.result, rv.scratch, rv.nesting);
        break;
      }
      case STOREPTR:
      {
        if (rv.result < 0 || rv.result >= len) {
          FAIL("ERROR: Cannot move data pointer out of bounds.\n");
        }
        ptr = rv.result;
        rv = retval(STOREPTR, rv.result, rv.scratch, rv.nesting);
        break;
      }
      case SCRATCH:
      {
        rv = retval(SCRATCH, rv.result, rv.result, rv.nesting);
        break;
      }
      case RESTORE:
      {
        rv = retval(RESTORE, rv.scratch, rv.scratch, rv.nesting);
        break;
      }
      case DEREFERENCE:
      {
        if (ptr < 0 || ptr >= len) {
          FAIL("ERROR: Cannot dereference out of bounds.\n");
        }
        rv = retval(DEREFERENCE, mem[ptr], rv.scratch, rv.nesting);
        break;
      }
      case ADDRESSOF:
      {
        if (ptr < 0 || ptr >= len) {
          FAIL("ERROR: Cannot take address of out of bounds data pointer.\n");
        }
        rv = retval(ADDRESSOF, ptr, rv.scratch, rv.nesting);
        break;
      }
      case JUMP:
      {
        if (ptr < 0 || ptr >= len) {
          FAIL("ERROR: Cannot jump from out of bounds.\n");
        }
        if (mem[ptr] == 0) {
          // search for the next u in the same nesting level
          int j = i + 1;
          while (j < len - 1) {
            if (operations[j].code == UNJUMP && operations[i].nesting == operations[j].nesting) {
              // set pc after this UNJUMP
              i = j + 1;
              
              // leave return value unchanged
              rv = retval(JUMP, rv.result, rv.scratch, rv.nesting);
          
              // immediately evaluate the instruction above
              goto start_eval;
            }
            j++;
          }
          FAIL("ERROR: No matching u after j found.\n");
        }
        // leave return value unchanged
        rv = retval(JUMP, rv.result, rv.scratch, rv.nesting + 1);
        break;
      }
      case UNJUMP:
      {
        if (ptr < 0 || ptr >= len) {
          FAIL("ERROR: Cannot unjump from out of bounds.\n");
        }
        
        if (mem[ptr] != 0) {          
          // search for the previous j in the same nesting level
          int j = i - 1;
          while (j > 0) {
            if (operations[j].code == JUMP && operations[i].nesting == operations[j].nesting) {
              // set pc to this JUMP
              i = j;
              
              // leave return value unchanged
              rv = retval(UNJUMP, rv.result, rv.scratch, rv.nesting);
              
              // immediately evaluate the instruction at i
              goto start_eval;
            }
            j--;
          }
          FAIL("ERROR: No matching j before u found.\n");
        }
        
        // leave return value unchanged
        rv = retval(UNJUMP, rv.result, rv.scratch, rv.nesting - 1);
        break;
      }
      case NEWLINE:
      {
        rv = retval(NOP, 0, rv.scratch, rv.nesting);
        break;
      }
      default: // do nothing
        continue;
    }
  }
  // return the current value under the pointer
  return mem[ptr];
}

/**
 * Obtain the length of the program in bytes.
 *
 * @param f  A pointer to a file.
 */
long file_len(FILE* f) {
  fseek(f, 0L, SEEK_END);
  long len = ftell(f);
  rewind(f);
  return len;
}

/**
 * Read a program from file f of length len, parse it, and return an
 * array of commands in operations. Returns the length of the parsed
 * program (in operations).
 *
 * @param f           A pointer to a file.
 * @param operations  A pointer to an array to store operations of length len.
 * @param len         The length of the operations array.
 */ 
int parse(FILE* f, op_t* operations, int len) {
  bool comment_mode = false;
  int i = 0; // indexes operations
  int j = 0; // true operation count (excluding comments)
  int nlcount = 0;
  int nesting = 0; // current nesting level
  while (i < len) {
    char c = getc(f);
    if (c == EOF) FAIL("Unexpected end of file.");
    op_t op = parse_char(c, nesting);

    if (comment_mode) {
      // we're in the middle of a comment
      if (op.code == NEWLINE) {
        // disable comment mode but record newline
        comment_mode = false;
        nlcount++;
        operations[j] = op;
        j++;
      }
    } else {
      // we're outside a comment
      if (op.code == COMMENT) {
        // enable comment mode, record nothing
        comment_mode = true;
      } else {
        // some other operation, record it
        operations[j] = op;
        if (op.code == NEWLINE) {
          nlcount++;
        } else if (op.code == JUMP) {
          nesting++;
        } else if (op.code == UNJUMP) {
          nesting--;
        }
        j++;
      }
    }
    i++;
  }
  return j;
}

/**
 * Breph interpreter.
 * Reads a file from argv[1] unless a flag is given, in which case
 * it reads a file from argv[2].
 * Returns as exit code the value under the read/write head.
 */
int main(int argc, char** argv) {
  // disable stdout buffering
  setbuf(stdout, NULL);

  if (argc != 2 && argc != 3) {
    usage();
  }
  
  char* fname = argc == 2 ? argv[1] : argv[2];
  bool debug = argc == 3;
  
  // initialize main memory
  int mem[MEM_SZ] = {0};
  
  // open the given file
  FILE* f = fopen(fname, "r");
  
  // how long is the program?
  long len = file_len(f);
  
  // consevatibely allocate enough storage for program
  op_t operations[len];
  
  // parse program and get actual program length
  int op_len = parse(f, operations, len);
  
  // evaluate program
  int final = eval(operations, op_len, mem, debug);
  
  // flush output
  printf("\n");
  
  return final;
}