# include "cxgr_common.h"

# include <stdio.h>
# include <stdlib.h>
# include <string.h>
# include <setjmp.h>
# include <stdarg.h>

int g_initial_memsize = 0x10000;
int g_max_memsize = 0x100000;
double g_ideal_residency_ratio = 0.1;
int g_dump = 0;

typedef struct
{
  unsigned total_alloc;
  unsigned total_copied;
  unsigned gc_count;
  unsigned max_heap_residency;
  unsigned max_stack_size;
  cxgr_word *prev_hp;
  unsigned prev_residency;
} cxgr_stats;

struct cxgr_runtime_info_struct
{
  cxgr_word *base;
  int size;
  cxgr_word *statics;
  int static_count;
  jmp_buf abort;
  cxgr_stats stats;
};

static void cxgr_abort(cxgr_runtime_info *info, int ret)
{
  longjmp(info->abort, ret);
}

static void cxgr_failure(cxgr_runtime_info *info, const char *msg)
{
  fprintf(stderr, "%s\n", msg);
  cxgr_abort(info, 2);
}

# define PTR(x) ((cxgr_word *)(x))
# define INT(x) ((cxgr_word)(x))
# define OBJ_SIZE(p) ((p)[2] - (p)[1] + 3)
# define IS_HEAP_POINTER(v, heap, heap_end) (!((v) & 1) && heap <= PTR(v) && PTR(v) < heap_end)

static cxgr_word update_ref(cxgr_word v, cxgr_word **lead)
{
  if(PTR(v)[0] == 0) /* already copied */
    return PTR(v)[1];
  else
  {
    int size = OBJ_SIZE(PTR(v));
    cxgr_word *p = *lead;
    memcpy(p, PTR(v), size * sizeof(cxgr_word));
    *lead += size;
    PTR(v)[0] = 0;
    PTR(v)[1] = INT(p);
    return INT(p);
  }
}

static cxgr_word *copy_from_root(cxgr_word *root, cxgr_word *root_end, cxgr_word *dest, cxgr_word *lead, cxgr_word *heap, cxgr_word *heap_end)
{
  cxgr_word *p;
  for(p = root; p < root_end; p++)
    if(!(*p & 1) && heap <= PTR(*p) && PTR(*p) < heap_end)
      *dest++ = update_ref(*p, &lead);
    else
      *dest++ = *p;
  return lead;
}

static cxgr_word *copy_referred(cxgr_word *lead, cxgr_word *follow, cxgr_word *heap, cxgr_word *heap_end)
{
  while(lead != follow)
  {
    cxgr_word *arg_end;
    int narg = follow[2] - follow[1];
    follow += 3;
    arg_end = follow + narg;
    for(; follow < arg_end; follow++)
      if(IS_HEAP_POINTER(*follow, heap, heap_end))
        *follow = update_ref(*follow, &lead);
  }
  return lead;
}

static int imax(int a, int b)
{
  return a > b ? a : b;
}

static int imin(int a, int b)
{
  return a < b ? a : b;
}

static cxgr_space copy(cxgr_runtime_info *info, cxgr_word *sp, cxgr_word *hp, cxgr_word *newmem, int newsize)
{
  cxgr_space ret;
  cxgr_word *lead;
  cxgr_word *new_sp;

  new_sp = newmem + newsize - (info->base + info->size - sp);
  lead = copy_from_root(sp, info->base + info->size, new_sp, newmem, info->base, hp);
  lead = copy_from_root(info->statics, info->statics + info->static_count, info->statics, lead, info->base, hp);
  lead = copy_referred(lead, newmem, info->base, hp);

  ret.hp = lead;
  ret.sp = new_sp;
  return ret;
}

static int eprintf(const char *fmt, ...)
{
  int r;
  va_list list;
  va_start(list, fmt);
  r = vfprintf(stderr, fmt, list);
  va_end(list);
  return r;
}

static void print_value(cxgr_word *hbegin, cxgr_word *hend, cxgr_word v)
{
  if(IS_HEAP_POINTER(v, hbegin, hend))
    eprintf("[%d]", PTR(v) - hbegin);
  else if(v % 2 == 0)
    eprintf("%p", (void *)v);
  else
    eprintf("%d", v);
}

typedef struct
{
  cxgr_word **data;
  int read;
  int write;
  int end;
} gqueue;

static gqueue new_gqueue(int length)
{
  gqueue ret;
  ret.data = (cxgr_word **)malloc(length * sizeof(cxgr_word *));
  if(!ret.data)
    abort();
  ret.read = ret.write = 0;
  ret.end = length;
  return ret;
}

static int push(gqueue *q, cxgr_word *v)
{
  if(q->write == q->end)
    return 0;
  q->data[q->write++] = v;
  return 1;
}

static int lookup(gqueue *q, cxgr_word *key)
{
  int i;
  for(i = 0; i < q->write; i++)
    if(q->data[i] == key)
      return i;
  return push(q, key) ? q->write - 1 : -1;
}

static cxgr_word *pop(gqueue *q)
{
  if(q->read == q->write)
    return NULL;
  return q->data[q->read++];
}

static void destroy_gqueue(gqueue *q)
{
  free(q->data);
}

static void print_in_alpha(int i, int uppercase)
{
  char a = uppercase ? 'A' : 'a';
  if(i < 26)
    eprintf("%c", a + i);
  else
    eprintf("%c%d", a, i);
}

static void print_with_gqueue(gqueue *q, cxgr_word value, cxgr_word *hbegin, cxgr_word *hend)
{
  int i;
  if(!value)
    eprintf("(null)");
  else if(value % 2 || (i = lookup(q, (cxgr_word *)value)) == -1)
    print_value(hbegin, hend, value);
  else
    print_in_alpha(i, !IS_HEAP_POINTER(value, hbegin, hend));
}

static void graphical_dump(cxgr_word *begin, cxgr_word *end, cxgr_word *hbegin, cxgr_word *hend, int depth)
{
  gqueue q = new_gqueue(depth);
  cxgr_word *p;
  eprintf("<<<\n");
  for(p = begin; p < end; p++)
  {
    print_with_gqueue(&q, *p, hbegin, hend);
    eprintf(" ");
  }
  eprintf("\nwhere\n");
  while(p = pop(&q))
  {
    int i;
    int nvalue = p[2] - p[1];
    eprintf("  ");
    print_with_gqueue(&q, (cxgr_word)p, hbegin, hend);
    eprintf(" = %d %d %d", p[0], p[1], p[2]);
    for(i = 0; i < nvalue; i++)
    {
      eprintf(" ");
      print_with_gqueue(&q, p[3 + i], hbegin, hend);
    }
    eprintf("\n");
  }
  eprintf(">>>\n");
  destroy_gqueue(&q);
}

static void dump(cxgr_word *begin, cxgr_word *end, cxgr_word *hbegin, cxgr_word *hend)
{
  cxgr_word *p;
  eprintf("<<<\n");
  for(p = begin; p < end; p++)
  {
    print_value(hbegin, hend, *p);
    eprintf("\n");
  }
  eprintf(">>>\n");
}

static void update_stats_after_gc(cxgr_stats *stats, cxgr_word *base, cxgr_word *sp, cxgr_word *new_hp, cxgr_word *end, cxgr_word *old_hp)
{
  stats->total_alloc += old_hp - stats->prev_hp;
  stats->total_copied += new_hp - base;
  stats->gc_count++;
  stats->max_heap_residency = imax(stats->max_heap_residency, new_hp - base);
  stats->max_stack_size = imax(stats->max_stack_size, end - sp);
  stats->prev_residency = new_hp - base;
  stats->prev_hp = new_hp;
}

static void update_stats_before_exit(cxgr_stats *stats, cxgr_word *base, cxgr_word *end, cxgr_word *sp, cxgr_word *hp)
{
  stats->total_alloc += hp - stats->prev_hp;
  stats->max_stack_size = imax(stats->max_stack_size, end - sp);
}

cxgr_space cxgr_gc(cxgr_word *sp, cxgr_word *hp, int request, cxgr_runtime_info *info)
{
  int newsize = imin(g_max_memsize, imax(info->size, (int)(info->stats.prev_residency / g_ideal_residency_ratio)));
  cxgr_word *newmem = (cxgr_word *)malloc(sizeof(cxgr_word) * newsize);
  cxgr_space ret;
  if(!newmem)
    cxgr_failure(info, "memory allocation failed");
  /* fprintf(stderr, "GC entered: total = %d, sp = %d, hp = %d, request = %d, prev-res = %d, newsize = %d\n",
      info->size, (int)(sp - info->base), (int)(hp - info->base), request, info->stats.prev_residency, newsize); */
  if(g_dump) graphical_dump(sp, sp+imin(info->base+info->size-sp, 20), info->base, hp, 20);
  ret = copy(info, sp, hp, newmem, newsize);
  /* fprintf(stderr, "GC exited: hp = %d\n", ret.hp - newmem); */
  if(g_dump) graphical_dump(ret.sp, ret.sp+imin(newmem+newsize-ret.sp, 20), newmem, ret.hp, 20);
  if(ret.sp - ret.hp < request)
  {
    fprintf(stderr, "failed to allocate enouph memory: sp = %d, hp = %d, size = %d\n",
        (int)(ret.sp - newmem), (int)(ret.hp - newmem), newsize);
    free(newmem);
    cxgr_abort(info, 2);
  }
  update_stats_after_gc(&info->stats, newmem, ret.sp, ret.hp, newmem + newsize, hp);
  free(info->base);
  info->base = newmem;
  info->size = newsize;
  return ret;
}

void cxgr_putchar(cxgr_word c)
{
  putchar(c >> 1);
  fflush(stdout);
}

cxgr_word cxgr_getchar(void)
{
  int c = getchar();
  if(c == EOF)
    return CXGR_EOF;
  return (c << 1) + 1;
}

void cxgr_message(const char *msg, cxgr_runtime_info *info)
{
  fprintf(stderr, "%s\n", msg);
}

static int handle_status(cxgr_status s)
{
  switch(s)
  {
  case cxgr_success: 
    return 0;
  case cxgr_error_out_notchar:
    fprintf(stderr, "Out: not a character\n");
    return 1;
  case cxgr_error_succ_notchar:
    fprintf(stderr, "Succ: not a character\n");
    return 1;
  case cxgr_error_stack_oob:
    fprintf(stderr, "stack reference out of bounds\n");
    return 1;
  case cxgr_error_internal:
    fprintf(stderr, "aborting because of an internal error\n");
    return 2;
  }
  fprintf(stderr, "program exited with an unknown status\n");
  return 2;
}

static int call_code(cxgr_runtime_info *info)
{
  int r = setjmp(info->abort);
  if(!r)
  {
    cxgr_result res = cxgr_code(info->base + info->size, info->base, info->statics, info);
    update_stats_before_exit(&info->stats, info->base, info->base + info->size, res.sp, res.hp);
    return handle_status(res.status);
  }
  else
    return r;
}

static void init_stats(cxgr_stats *out, cxgr_word *hp)
{
  out->total_alloc = 0;
  out->total_copied = 0;
  out->gc_count = 0;
  out->max_heap_residency = 0;
  out->max_stack_size = 0;
  out->prev_hp = hp;
  out->prev_residency = 0;
}

static int init_info(cxgr_runtime_info *out, int n_static)
{
  int i;
  cxgr_word *mem = (cxgr_word *)malloc(g_initial_memsize * sizeof(cxgr_word));
  cxgr_word *ss;
  if(!mem)
    return 2;
  out->base = mem;
  out->size = g_initial_memsize;
  ss = (cxgr_word *)malloc(n_static * sizeof(cxgr_word));
  if(!ss)
  {
    free(mem);
    return 2;
  }
  for(i = 0; i < n_static; i++)
    ss[i] = 1;
  out->statics = ss;
  out->static_count = n_static;
  init_stats(&out->stats, out->base);
  return 0;
}

static void print_stats(const cxgr_stats *stats)
{
  fprintf(stderr, "GC stats: alloc = %u; copied = %u; gc-count = %u; max-heap = %u, max-stack = %u\n",
      stats->total_alloc, stats->total_copied, stats->gc_count, stats->max_heap_residency, stats->max_stack_size);
}

static void destroy_info(const cxgr_runtime_info *info)
{
  free(info->base);
  free(info->statics);
}

int cxgr_main(void)
{
  int r;
  cxgr_runtime_info info;
  init_info(&info, cxgr_static_count());
  r = call_code(&info);
  print_stats(&info.stats);
  destroy_info(&info);
  return r;
}

int main(int argc, char **argv)
{
  if(argc > 1)
    g_max_memsize = atoi(argv[1]);
  if(g_max_memsize == 0)
    g_max_memsize = 0x100000;
  return cxgr_main();
}