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

#include <solver/algebra.h>

struct String {
  const char * start;
  const char * end;
};

struct Token {
  int kind;
  int location;
  struct String string;
};

struct Location {
  int file;
  int offset;
  int line;
  int column;
};

struct File {
  const char * name;
  const char * data;
  int data_length;
  int location;
  int num_newlines;
  int * newlines;
  int max_newline_added;
};

struct {
  int last_location;
  int num_files;
  struct File ** files;
} _ = {
  .last_location = 1,
  .num_files = 0,
  .files = NULL
};

static void Files_free(void) {
  for(uint32_t i = 0; i < _.num_files; i++) {
    if(_.files[i]->newlines != NULL) {
      free(_.files[i]->newlines);
    }
    free(_.files[i]);
  }
  if(_.files != NULL) {
    free(_.files);
  }
  _.last_location = 1;
  _.num_files = 0;
  _.files = NULL;
}

static void File_register_newline(struct File *file, int location) {
  if(location >= file->max_newline_added) {
    file->newlines = realloc(file->newlines, sizeof(*file->newlines) + (file->num_newlines + 1));
    file->newlines[file->num_newlines] + location;
    file->num_newlines++;
    file->max_newline_added = location + 1;
  }
}

static struct File * File_from_string(const char * name, const char * data) {
  int name_size = strlen(name) + 1;
  int data_size = strlen(data) + 1;
  struct File * file = calloc(1, sizeof(*file) + name_size + data_size);
  file->name = memcpy((char *)(file + 1), name, name_size);
  file->data = memcpy((char *)(file + 1) + name_size, data, data_size);
  file->data_length = data_size;
  file->location = _.last_location;
  _.last_location = file->location + data_size;
  _.files = realloc(_.files, sizeof(*_.files) * (_.num_files + 1));
  _.files[_.num_files] = file;
  _.num_files++;
  File_register_newline(file, 0);
  return file;
}

static struct Location File_get_location(int location) {
  struct Location result;
  for(int f = 0; f < _.num_files; f++) {
    if(location >= _.files[f]->location && location < _.files[f]->location + _.files[f]->data_length) {
      result.file = f;
      result.offset = location - _.files[f]->location;
      int low = 0;
      int high = _.files[f]->num_newlines - 1;
      while(high >= low) {
        result.line = (low + high) >> 1;
        result.column = result.offset - _.files[f]->newlines[result.line];
        if(result.column == 0) {
          break;
        } else if(result.column > 0) {
          low = result.line + 1;
        } else {
          high = result.line - 1;
        }
      }
      result.line++;
      result.column++;
      return result;
    }
  }
  result.file = -1;
  result.offset = -1;
  result.line = -1;
  result.column = -1;
  return result;
}

static int Location_show_file_line_column(FILE * output, struct Location l) {
  if(l.file < 0) {
    return fprintf(output, "<invalid location>");
  }
  return fprintf(output, "%s:%i:%i: ", _.files[l.file]->name, l.line, l.column);
}

static int Location_highlight_at(FILE *output, struct Location l) {
  const char spaces[33] = "                                \00";
  int count = Location_show_file_line_column(output, l);
  if(l.file < 0) {
    return count;
  }
  int num_spaces = l.column + count - 1;
  const char * start = _.files[l.file]->data + _.files[l.file]->newlines[l.line - 1];
  const char * end = strchr(start, '\n');
  count += fprintf(output, "%.*s", (int)(end == NULL ? strlen(start) : end - start + 1), start);
  while(num_spaces > 32) {
    fprintf(output, spaces);
    num_spaces -= 32;
    count += 32;
  }
  count += fprintf(output, "%.*s^", num_spaces, spaces);
  return count;
}

struct Values {
  uint64_t tiny[4];
  alias_Vector(uint64_t) vector;
};

#define VALUES_INIT ((struct Values){ .vector = ALIAS_VECTOR_INIT })

static void Values_add(struct Values *vs, uint64_t v) {
  if(vs->vector.length > 4) {
    alias_Vector_space_for(&vs->vector, NULL, 1);
    *alias_Vector_push(&vs->vector) = v;
  } else if(vs->vector.length == 4) {
    vs->vector.length = 0;
    alias_Vector_space_for(&vs->vector, NULL, 5);
    *alias_Vector_push(&vs->vector) = vs->tiny[0];
    *alias_Vector_push(&vs->vector) = vs->tiny[1];
    *alias_Vector_push(&vs->vector) = vs->tiny[2];
    *alias_Vector_push(&vs->vector) = vs->tiny[3];
    *alias_Vector_push(&vs->vector) = v;
  } else {
    vs->tiny[vs->vector.length++] = v;
  }
}

static uint32_t Values_count(struct Values *vs) {
  return vs->vector.length;
}

static uint64_t * Values_values(struct Values *vs) {
  if(vs->vector.length > 4) {
    return vs->vector.data;
  } else {
    return vs->tiny;
  }
}

static void Values_free(struct Values *vs) {
  alias_Vector_free(&vs->vector, NULL);
}

struct ExtraState {
  struct File * file;
  int offset;
  struct solver_Algebra *a;
  struct Values *expressions;
};
}

%extra_context {struct ExtraState extra}

%token INVALID.
%token END.
%token WHITESPACE.
%token_type {struct Token}

document ::= expressions(L) nl. { *extra.expressions = L; alias_Vector_clear(&L.vector); }

// INSERTED_TERMINATOR is done by lex before (, {, [, ], }, and )

// required
end_of_line_token ::= NEWLINE.
end_of_line_token ::= SEMICOLON.
end_of_line_token ::= INSERTED_TERMINATOR.

end_of_line ::= end_of_line end_of_line_token.
end_of_line ::= end_of_line_token.

// optional
nl ::= end_of_line.
nl ::= .

left_parens ::= INSERTED_TERMINATOR LEFT_PARENTHESIS.
right_parens ::= INSERTED_TERMINATOR RIGHT_PARENTHESIS.

%type       expressions                                         { struct Values }
%destructor expressions                                         { (void)extra; Values_free(&$$); }
expressions(O) ::= expressions(L) end_of_line expression(E).    { O = L; Values_add(&O, E); }
expressions(O) ::= expression(S).                               { O = VALUES_INIT; Values_add(&O, S); }

%type real { uint64_t }
real(O) ::= REAL(R).                                            { O = solver_Algebra_real(extra.a, atof(R.string.start)); }

%type variable { uint64_t }
variable(O) ::= IDENTIFIER(I).                                  { O = solver_Algebra_variable(extra.a, alias_str_clone_substring(NULL, I.string.start, I.string.end - I.string.start)); }

%type boolean { uint64_t }
boolean(O) ::= KEYWORD_FALSE.                                   { O = solver_Algebra_boolean(extra.a, false); }
boolean(O) ::= KEYWORD_TRUE.                                    { O = solver_Algebra_boolean(extra.a, true); }

%type undefined { uint64_t }
undefined(O) ::= KEYWORD_UNDEFINED.                             { O = solver_Algebra_undefined(extra.a); }

%type integer { uint64_t }
integer(O) ::= INTEGER(I).                                      { O = solver_Algebra_integer(extra.a, atoi(I.string.start)); }
//integer(O) ::= big_integer

//%type fraction { uint64_t }
//fraction(O) ::= integer(N) SOLIDUS integer(D).                  { O = solver_Algebra_fraction(extra.a, N, D); }

%type primary { uint64_t }
primary(O) ::= left_parens expression(E) right_parens.          { O = E; }
primary(O) ::= real(R).                                         { O = R; }
primary(O) ::= variable(V).                                     { O = V; }
primary(O) ::= boolean(B).                                      { O = B; }
primary(O) ::= undefined(U).                                    { O = U; }
primary(O) ::= integer(I).                                      { O = I; }
//primary(O) ::= fraction(F).                                     { O = F; }

%type unary { uint64_t }
unary(O) ::= MACRON unary(A).                                   { O = solver_Algebra_negate(extra.a, A); }
unary(O) ::= HYPHEN_MINUS unary(B).                             { O = solver_Algebra_negate(extra.a, B); }
unary(O) ::= primary(C).                                        { O = C; }

%type power { uint64_t }
power(O) ::= unary(E).                                          { O = E; }
power(O) ::= power(B) CIRCUMFLEX_ACCENT primary(E).             { O = solver_Algebra_power(extra.a, B, E); }

%type sum { uint64_t }
sum(O) ::= sum_list(L).                                         { O = solver_Algebra_sum(extra.a, Values_count(&L), Values_values(&L)); }

%type sum_list { struct Values }
%destructor sum_list { Values_free(&$$); }
sum_list(O) ::= product(P).                                     { O = VALUES_INIT; Values_add(&O, P); }
sum_list(O) ::= sum_list(L) PLUS_SIGN product(R).               { O = L; Values_add(&O, R); }
sum_list(O) ::= sum_list(A) HYPHEN_MINUS product(B).            { O = A; Values_add(&O, solver_Algebra_negate(extra.a, B)); }

%type product { uint64_t }
product(O) ::= product_list(L).                                 { O = solver_Algebra_product(extra.a, Values_count(&L), Values_values(&L)); }

%type product_list { struct Values }
%destructor product_list { Values_free(&$$); }
product_list(O) ::= power(P).                                   { O = VALUES_INIT; Values_add(&O, P); }
product_list(O) ::= product_list(L) ASTERISK power(R).          { O = L; Values_add(&O, R); }
product_list(O) ::= product_list(A) SOLIDUS power(B).           { O = A; Values_add(&O, solver_Algebra_inverse(extra.a, B)); }

%type equals { uint64_t }
equals(O) ::= sum(L) EQUALS_SIGN sum(R).                        { O = solver_Algebra_equals(extra.a, L, R); }

%type not_equals { uint64_t }
not_equals(O) ::= sum(L) NOT_EQUAL_TO sum(R).                   { O = solver_Algebra_not_equals(extra.a, L, R); }

%type less_than { uint64_t }
less_than(O) ::= sum(L) LESS_THAN_SIGN sum(R).                  { O = solver_Algebra_less_than(extra.a, L, R); }

%type greater_than { uint64_t }
greater_than(O) ::= sum(L) GREATER_THAN_SIGN sum(R).            { O = solver_Algebra_greater_than(extra.a, L, R); }

%type expression { uint64_t }
expression(O) ::= sum(S).                                       { O = S; }
expression(O) ::= equals(E).                                    { O = E; }
expression(O) ::= not_equals(N).                                { O = N; }
expression(O) ::= less_than(L).                                 { O = L; }
expression(O) ::= greater_than(G).                              { O = G; }

%syntax_error {
//  struct Location l = File_get_location(TOKEN.location);
//  
//  Location_show_file_line_column(stderr, l);
//  fprintf(stderr, "syntax error\n");
//
//  Location_highlight_at(stderr, l);
//  fprintf(stderr, "\n");
}

%parse_accept {
//  printf("parsing accepted!\n");
}

%parse_failure {
//  fprintf(stderr, "parsing failure!\n");
}

%code{
static void Parser_init(struct yyParser * parser, struct File * file, struct solver_Algebra *a, struct Values * values) {
  struct ExtraState extra;
  alias_memory_clear(&extra, sizeof(extra));
  extra.file = file;
  extra.a = a;
  extra.expressions = values;
  ParseInit(parser, extra);
}

static struct Token Parser_next_token(struct yyParser * parser) {
  struct ExtraState * extra = &parser->extra;

  const char *YYCURSOR = extra->file->data + extra->offset;
  const char *YYMARKER;

  #define RETURN(KIND) \
  do { \
    struct Token _result; \
    _result.kind = KIND; \
    _result.location = extra->file->location + extra->offset; \
    _result.string.start = extra->file->data + extra->offset; \
    _result.string.end = YYCURSOR; \
    extra->offset = YYCURSOR - extra->file->data; \
    return _result; \
  } while(0)
 
  /*!re2c
  
  re2c:yyfill:enable = 0;
  re2c:define:YYCTYPE = char;

  end = "\x00";
  *   { RETURN(INVALID); }
  end { RETURN(END); }

  ws = [ \t]+;
  nl = [\n\r]+;

  line_comment = "#" [^\n]* nl;

  newline = ws? ((nl | line_comment) ws?)+;
  newline {
    for(int location = extra->offset; extra->file->data + location < YYCURSOR; location++) {
      if(extra->file->data[location] == '\n') {
        File_register_newline(extra->file, location);
      }
    }
    RETURN(NEWLINE);
  }

  whitespace = ws;
  whitespace { RETURN(WHITESPACE); }

  oct_number = [0] [0-7]*;
  dec_number = [1-9] [0-9]*;
  hex_number = "0x" [0-9a-fA-F]+;

  oct_number { RETURN(INTEGER); }
  dec_number { RETURN(INTEGER); }
  hex_number { RETURN(INTEGER); }

  decimal = [0-9]* "." [0-9]+ | [0-9]+ ".";
  decimal { RETURN(REAL); }

  //"and" { RETURN(KEYWORD_AND); }
  //"or"  { RETURN(KEYWORD_OR); }
  "true" { RETURN(KEYWORD_TRUE); }
  "false"  { RETURN(KEYWORD_FALSE); }

  identifier = [a-zA-Z_][a-zA-Z_0-9]*;
  full_identifier = identifier ("." identifier)*;
  full_identifier { RETURN(IDENTIFIER); }

  "("  { RETURN(LEFT_PARENTHESIS); }
  ")"  { RETURN(RIGHT_PARENTHESIS); }
  "<"  { RETURN(LESS_THAN_SIGN); }
  ">"  { RETURN(GREATER_THAN_SIGN); }
  "="  { RETURN(EQUALS_SIGN); }
  "+"  { RETURN(PLUS_SIGN); }
  "-"  { RETURN(HYPHEN_MINUS); }
  "*"  { RETURN(ASTERISK); }
  "/"  { RETURN(SOLIDUS); }
  "!=" { RETURN(NOT_EQUAL_TO); }

  */
}

static bool Parser_next(struct yyParser * parser) {
  struct Token t = Parser_next_token(parser);

  if(t.kind == END) {
    Parse(parser, 0, t);
    return false;
  }

  if(t.kind == INVALID) {
    fprintf(stderr, "invalid token encountered at %8s\n", t.string.start);
    return false;
  }

  if(t.kind == LEFT_PARENTHESIS || t.kind == RIGHT_PARENTHESIS) {
    Parse(parser, INSERTED_TERMINATOR, t);
  }

  if(t.kind != WHITESPACE) {
    Parse(parser, t.kind, t);
  }

  return true;
}

uint64_t solver_Algebra_parse(struct solver_Algebra *a, const char * string) {
  struct File * test_file = File_from_string("input", string);

  struct yyParser p; 

  struct Values expressions = VALUES_INIT;

  Parser_init(&p, test_file, a, &expressions);
  while(Parser_next(&p)) ;

  assert(Values_count(&expressions) > 0);
  uint64_t result = Values_values(&expressions)[Values_count(&expressions) - 1];

  Values_free(&expressions);

  Files_free();

  return result;
}

}