#include <stdbool.h>
#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <sys/resource.h>
#include <sys/stat.h>

#define static_assert(c) _Static_assert(c, #c)

typedef uint32_t value;

static_assert(_Alignof(value) <= 4);

struct closure {
    void *native_code;
    uint16_t num_params;
    uint16_t env_size;
    value env_items[];
};

struct tuple {
    uint16_t num_items;
    uint16_t layout;
    value items[];
};

struct variant {
    uint16_t label;
    value item;
};

struct byte_vector {
    uint32_t num_bytes;
    char bytes[];
};

static_assert(_Alignof(struct closure) <= 8);
static_assert(_Alignof(struct tuple) <= 4);
static_assert(_Alignof(struct variant) <= 4);
static_assert(_Alignof(struct byte_vector) <= 4);

enum {
    TAG_HEAP_CLOSURE = 0x1,
    TAG_HEAP_TUPLE = 0x3,
    TAG_HEAP_VARIANT = 0x5,
    TAG_HEAP_BYTE_VECTOR = 0x7,
    TAG_IMMEDIATE_BOOLEAN = 0x0f,
    TAG_IMMEDIATE_TUPLE = 0x1f,
    TAG_IMMEDIATE_VARIANT = 0x2f,
};

enum {
    empty_tuple = TAG_IMMEDIATE_TUPLE,
};

enum {
    value_true = TAG_IMMEDIATE_BOOLEAN,
    value_false = (TAG_IMMEDIATE_BOOLEAN | 0x100),
};

enum {
    INTEGER_MIN = INT32_MIN / 2,
    INTEGER_MAX = INT32_MAX / 2,
};

static struct {
    uint32_t num_entries;
    const uint16_t *entries;
} record_layouts;

static FILE *file_table[FOPEN_MAX];

static void
err_print_line(const char *s)
{
    fprintf(stderr, "%s\n", s);
}

static _Noreturn void
halt(void)
{
    exit(1);
}

//  The Heap
//
//  The heap is a single contiguous memory region in which value
//  representation data is stored.
//
//  The heap grows monotonically. If its capacity is exceeded, then the
//  process exits with a nonzero exit status.
//
//  The size of the heap for a given program is fixed at compile time and
//  is at most pow(2, 30) bytes (1 GiB).
//
//  All objects allocated in the heap have 4-byte, 8-byte, or 16-byte
//  alignment. Each object allocated in the heap has an associated heap
//  identifier, established by heap_alloc. The heap_access function provides
//  the means for obtaining the native address of an object with a given heap
//  identifier.
//
//  Members:
//      bytes - The bytes member holds the native address of the memory
//          region, which must have 16-byte alignment. The memory region
//          starting at this address must contain at least (4 * heap.limit)
//          bytes.
//      limit - The limit member establishes the growth limit for the heap. It
//          must not exceed pow(2, 28). The capacity of the heap is
//          (4 * heap.limit) bytes. This limit is fixed at initialization
//          time.
//      top - The top member grows as allocations are made but never exceeds
//          the limit member. It is initially zero.

static struct {
    char *bytes;
    uint32_t limit;
    uint32_t top;
} heap;

//  heap_access
//
//  Parameters:
//      id - A heap object identifier produced by heap_alloc.

static void *
heap_access(uint32_t id)
{
    return heap.bytes + 4 * id;
}

//  heap_alloc
//
//  Parameters:
//      align - The address alignment constraint. It must be 1, 2, 4, 8, or 16.
//      size - The number of bytes required, which must be greater than zero.

static uint32_t
heap_alloc(size_t align, size_t size)
{
    uint32_t start = heap.top;
    if (align > 4) {
        uint32_t c = align / 4 - 1;
        start = (start + c) & ~c;
    }
    if (start > heap.limit || size > 4 * (heap.limit - start)) {
        err_print_line("Failed to allocate memory.");
        halt();
    }
    heap.top = start + ((uint32_t)size + 3) / 4;
    return start;
}

static value
value_make_box(unsigned int tag, uint32_t id)
{
    return (id << 4) | tag;
}

static void *
value_unbox(value x)
{
    return heap_access(x >> 4);
}

static bool
value_has_tag(value x, unsigned int mask, unsigned int tag)
{
    return (x & mask) == tag;
}

static struct closure *
closure_unbox(value closure)
{
    if (!value_has_tag(closure, 0xf, TAG_HEAP_CLOSURE)) {
        err_print_line("Value is not a function.");
        halt();
    }
    return value_unbox(closure);
}

static struct tuple *
tuple_unbox(value tuple)
{
    if (!value_has_tag(tuple, 0xf, TAG_HEAP_TUPLE)) {
        err_print_line("Value is not a tuple.");
        halt();
    }
    return value_unbox(tuple);
}

static struct variant *
variant_unbox(value variant)
{
    if (!value_has_tag(variant, 0xf, TAG_HEAP_VARIANT)) {
        err_print_line("Value is not a variant.");
        halt();
    }
    return value_unbox(variant);
}

static value
byte_vector_make(uint32_t num_bytes, const char *bytes)
{
    if (num_bytes > INTEGER_MAX) {
        err_print_line("Byte vector is too big.");
        halt();
    }
    size_t align = _Alignof(struct byte_vector);
    size_t size = sizeof(struct byte_vector) + num_bytes;
    uint32_t id = heap_alloc(align, size);
    struct byte_vector *byte_vector_rep = heap_access(id);
    byte_vector_rep->num_bytes = num_bytes;
    if (num_bytes > 0 && bytes != NULL)
        memmove(byte_vector_rep->bytes, bytes, num_bytes);
    return value_make_box(TAG_HEAP_BYTE_VECTOR, id);
}

static struct byte_vector *
byte_vector_unbox(value byte_vector)
{
    if (!value_has_tag(byte_vector, 0xf, TAG_HEAP_BYTE_VECTOR)) {
        err_print_line("Value is not a byte vector.");
        halt();
    }
    return value_unbox(byte_vector);
}

static char *
byte_vector_bytes(value byte_vector)
{
    struct byte_vector *byte_vector_rep = byte_vector_unbox(byte_vector);
    return byte_vector_rep->bytes;
}

static bool
byte_vector_is_string(struct byte_vector *byte_vector_rep)
{
    if (byte_vector_rep->num_bytes == 0)
        return false;
    if (byte_vector_rep->bytes[byte_vector_rep->num_bytes - 1] != 0)
        return false;
    return true;
}

static struct byte_vector *
string_unbox(value string)
{
    struct byte_vector *byte_vector_rep = byte_vector_unbox(string);
    if (!byte_vector_is_string(byte_vector_rep)) {
        err_print_line("Value is not a string.");
        halt();
    }
    return byte_vector_rep;
}

static char *
string_bytes(value string)
{
    struct byte_vector *byte_vector_rep = string_unbox(string);
    return byte_vector_rep->bytes;
}

static uint32_t
string_length(value string)
{
    struct byte_vector *byte_vector_rep = byte_vector_unbox(string);
    if (!byte_vector_is_string(byte_vector_rep)) {
        err_print_line("Value is not a string.");
        halt();
    }
    return byte_vector_rep->num_bytes - 1;
}

static int
simple_strcmp(const char *s1, const char *s2)
{
    for (;;) {
        char a = *s1;
        char b = *s2;
        if (a == 0) return (b == 0) ? 0 : -1;
        if (b == 0) return 1;
        if (a < b) return -1;
        if (a > b) return 1;
        s1++;
        s2++;
    }
}

static bool
value_is_number(value v)
{
    return (v & 1) == 0;
}

static value
integer_encode(int32_t n)
{
    if (n < INTEGER_MIN || INTEGER_MAX < n) {
        err_print_line("Number is out of range.");
        halt();
    }
    return n << 1;
}

static int32_t
integer_decode(value v)
{
    if (!value_is_number(v)) {
        err_print_line("Value is not a number.");
        halt();
    }
#ifdef __GNUC__
    int32_t n = v; // "implementation-defined" behaviour, according to C11.
    return n >> 1; // "implementation-defined" behaviour, according to C11.
#else
#error "Need validation of implementation-defined behaviour."
#endif
}

static value
boolean_encode(bool b)
{
    return b ? value_true : value_false;
}

static value
file_open(value name, const char *mode)
{
    FILE *stream = fopen(byte_vector_bytes(name), mode);
    if (stream == NULL) {
        err_print_line("Failed to open file.");
        halt();
    }
    int fd = fileno(stream);
    if (fd >= FOPEN_MAX) {
        err_print_line("Too many open files.");
        halt();
    }
    file_table[fd] = stream;
    return integer_encode(fd);
}

static FILE *
file_lookup(value fd_value, int *result_fd)
{
    int32_t fd = integer_decode(fd_value);
    if (fd < 0 || fd >= FOPEN_MAX) {
        err_print_line("File descriptor is out of range.");
        halt();
    }
    if (result_fd != NULL)
        *result_fd = fd;
    return file_table[fd];
}

static void
stack_init(uint32_t limit)
{
    static_assert(sizeof(rlim_t) == 8);
    struct rlimit rlim;
    int r = getrlimit(RLIMIT_STACK, &rlim);
    if (r != 0)
        goto fail;
    rlim.rlim_cur = limit;
    r = setrlimit(RLIMIT_STACK, &rlim);
    if (r != 0)
        goto fail;
    return;
fail:
    err_print_line("Failed to set the stack limit.");
    halt();
}

//  s36: init
//
//  heap_num_bytes must be at most pow(2, 30).
//  The alignment of heap_bytes must be at least 16.

void
s36(uint32_t heap_num_bytes, char *heap_bytes, uint32_t stack_limit,
        uint32_t record_layouts_num_entries,
        const uint16_t *record_layouts_entries)
{
    heap.limit = heap_num_bytes / 4;
    heap.top = 0;
    heap.bytes = heap_bytes;
    stack_init(stack_limit);
    record_layouts.num_entries = record_layouts_num_entries;
    record_layouts.entries = record_layouts_entries;
    file_table[0] = stdin;
    file_table[1] = stdout;
    file_table[2] = stderr;
}

//  s87: halt
//
//  Halt execution, returing 1 as the exit code of the process.

_Noreturn value
s87(void)
{
    exit(1);
}

//  s75: closure_make
//
//  Construct a fresh closure value.
//
//  Parameters:
//      native_code - A C function pointer to a function whose return type is
//          value and which takes one more than num_params arguments, all of
//          type value.
//      num_params - The number of parameters associated with the closure (not
//          the native function).
//      env_size - The number of values to be stored in the closure
//          environment.
//      env_items - If env_size is zero, then env_items may be NULL;
//          otherwise, env_items must be an array containing env_size values.
//          The values provided comprise the environment of the closure.

value
s75(void *native_code, uint16_t num_params, uint16_t env_size,
        const value *env_items)
{
    size_t align = _Alignof(struct closure);
    size_t size = sizeof(struct closure) + env_size * sizeof(value);
    uint32_t id = heap_alloc(align, size);
    struct closure *closure_rep = heap_access(id);
    closure_rep->native_code = native_code;
    closure_rep->num_params = num_params;
    closure_rep->env_size = env_size;
    if (env_size > 0)
        memmove(closure_rep->env_items, env_items, env_size * sizeof(value));
    return value_make_box(TAG_HEAP_CLOSURE, id);
}

//  s62: closure_env_items

const value *
s62(value closure)
{
    const struct closure *closure_rep = closure_unbox(closure);
    return closure_rep->env_items;
}

//  s35: closure_native_code

const void *
s35(value closure, uint16_t num_args)
{
    const struct closure *closure_rep = closure_unbox(closure);
    if (closure_rep->num_params != num_args) {
        err_print_line("Ill-formed function application.");
        halt();
    }
    return closure_rep->native_code;
}

//  s27: variant_make_nonempty
//
//  Construct a fresh variant value where the enclosed value is not {}.
//
//  Parameters:
//      label - The label!
//      item - The enclosed value.

value
s27(uint16_t label, value item)
{
    size_t align = _Alignof(struct variant);
    size_t size = sizeof(struct variant);
    uint32_t id = heap_alloc(align, size);
    struct variant *variant_rep = heap_access(id);
    variant_rep->label = label;
    variant_rep->item = item;
    return value_make_box(TAG_HEAP_VARIANT, id);
}

//  s09: variant_label
//
//  The label of a variant value.
//
//  Parameters:
//      variant - The variant!

uint16_t
s09(value variant)
{
    if (value_has_tag(variant, 0xff, TAG_IMMEDIATE_VARIANT))
        return variant >> 8;
    struct variant *variant_rep = variant_unbox(variant);
    return variant_rep->label;
}

//  s06: variant_item
//
//  The value embedded within a variant.
//
//  Parameters:
//      variant - The variant!

value
s06(value variant)
{
    if (value_has_tag(variant, 0xff, TAG_IMMEDIATE_VARIANT))
        return empty_tuple;
    struct variant *variant_rep = variant_unbox(variant);
    return variant_rep->item;
}

//  s30: tuple_make_with_layout

value
s30(uint16_t num_items, const value *items, uint16_t layout)
{
    size_t align = _Alignof(struct tuple);
    size_t size = sizeof(struct tuple) + num_items * sizeof(value);
    uint32_t id = heap_alloc(align, size);
    struct tuple *tuple_rep = heap_access(id);
    tuple_rep->num_items = num_items;
    tuple_rep->layout = layout;
    if (num_items > 0)
        memmove(tuple_rep->items, items, num_items * sizeof(value));
    return value_make_box(TAG_HEAP_TUPLE, id);
}

//  s78: tuple_make_with_no_layout

value
s78(uint16_t num_items, const value *items)
{
    return s30(num_items, items, UINT16_MAX);
}

//  s68: tuple_fetch_at_offset

value
s68(value tuple, uint16_t offset)
{
    if (tuple == empty_tuple)
        goto fail;
    struct tuple *tuple_rep = tuple_unbox(tuple);
    if (offset >= tuple_rep->num_items)
        goto fail;
    return tuple_rep->items[offset];
fail:
    err_print_line("Ill-formed tuple access.");
    halt();
}

//  s31: tuple_fetch_at_label

value
s31(value tuple, uint16_t label)
{
    if (tuple == empty_tuple)
        goto fail;
    const unsigned short *entries = record_layouts.entries;
    struct tuple *tuple_rep = tuple_unbox(tuple);
    unsigned int layout = tuple_rep->layout;
    if (layout == UINT16_MAX)
        goto fail;
    for (unsigned int i = layout; entries[i] != UINT16_MAX; i++) {
        if (entries[i] == label)
            return tuple_rep->items[i - layout];
    }
fail:
    err_print_line("Ill-formed record access.");
    halt();
}

//  s33: tuple_items

const value *
s33(value tuple, uint16_t num_items)
{
    if (tuple == empty_tuple) {
        err_print_line("Invalid use of empty tuple.");
        halt();
    }
    struct tuple *tuple_rep = tuple_unbox(tuple);
    if (tuple_rep->num_items != num_items) {
        err_print_line("Tuple mismatch.");
        halt();
    }
    return tuple_rep->items;
}

//  s57: string_make

value
s57(const char *s)
{
    size_t len = strlen(s);
    if (len > INTEGER_MAX) {
        err_print_line("String is too long.");
        halt();
    }
    return byte_vector_make(len + 1, s);
}

//  s89: stuck_cond

_Noreturn value
s89(void)
{
    err_print_line("Cond expression has no applicable clause.");
    halt();
}

//  s88: stuck_switch

_Noreturn value
s88(void)
{
    err_print_line("Switch expression has no applicable clause.");
    halt();
}

//  s53: stuck_match

_Noreturn value
s53(void)
{
    err_print_line("Match expression has no applicable clause.");
    halt();
}

//  s26: prim_die

value
s26(value string)
{
    err_print_line(string_bytes(string));
    halt();
}

//  s18: prim_print

value
s18(value string)
{
    printf("%s", string_bytes(string));
    return empty_tuple;
}

//  s79: prim_print_line

value
s79(value string)
{
    printf("%s\n", string_bytes(string));
    return empty_tuple;
}

//  s20: prim_file_create

value
s20(value name)
{
    return file_open(name, "w");
}

//  s23: prim_file_open

value
s23(value name)
{
    return file_open(name, "r");
}

//  s92: prim_file_close

value
s92(value fd_value)
{
    int32_t fd = integer_decode(fd_value);
    if (fd < 0 || fd >= FOPEN_MAX) {
        err_print_line("Invalid file descriptor.");
        halt();
    }
    if (fd <= 2) {
        err_print_line("Attempted to close stdin, stdout, or stderr.");
        halt();
    }
    FILE *stream = file_table[fd];
    if (stream != NULL) {
        fclose(stream);
        file_table[fd] = NULL;
    }
    return empty_tuple;
}

//  s28: prim_file_read_all

value
s28(value fd_value)
{
    int fd;
    FILE *stream = file_lookup(fd_value, &fd);
    if (stream == NULL) {
        err_print_line("File is not open.");
        halt();
    }
    struct stat statbuf;
    if (-1 == fstat(fd, &statbuf)) {
        err_print_line("Failed to determine file size.");
        halt();
    }
    off_t file_size = statbuf.st_size;
    if (file_size < 0 || file_size > UINT32_MAX - 1)
        goto fail;
    value string = byte_vector_make(file_size + 1, NULL);
    char *bytes = byte_vector_bytes(string);
    if (1 != fread(bytes, file_size, 1, stream))
        goto fail;
    bytes[file_size] = 0;
    return string;
fail:
    err_print_line("Failed to read file.");
    halt();
}

//  s97: prim_file_write

value
s97(value fd_value, value string)
{
    int fd;
    FILE *stream = file_lookup(fd_value, &fd);
    if (stream == NULL) {
        err_print_line("File is not open.");
        halt();
    }
    uint32_t length = string_length(string);
    if (length > 0) {
        size_t r = fwrite(byte_vector_bytes(string), length, 1, stream);
        if (r != 1) {
            err_print_line("Failed to write to file.");
            halt();
        }
    }
    return empty_tuple;
}

//  s12: prim_show_integer

value
s12(value integer)
{
    char text[16];
    size_t len =
        snprintf(text, sizeof(text), "%ld", (long)integer_decode(integer));
    if (len >= sizeof(text)) {
        err_print_line("Failed to show integer.");
        halt();
    }
    return byte_vector_make(len + 1, text);
}

//  s93: prim_multiply

value
s93(value a, value b)
{
    int32_t n;
    if (__builtin_mul_overflow(integer_decode(a), integer_decode(b), &n)) {
        err_print_line("Integer is out of range.");
        halt();
    }
    return integer_encode(n);
}

//  s19: prim_add

value
s19(value a, value b)
{
    int32_t n;
    if (__builtin_add_overflow(integer_decode(a), integer_decode(b), &n)) {
        err_print_line("Integer is out of range.");
        halt();
    }
    return integer_encode(n);
}

//  s47: prim_subtract

value
s47(value a, value b)
{
    int32_t n;
    if (__builtin_sub_overflow(integer_decode(a), integer_decode(b), &n)) {
        err_print_line("Integer is out of range.");
        halt();
    }
    return integer_encode(n);
}

//  s84: prim_negate

value
s84(value n)
{
    return integer_encode(-integer_decode(n));
}

//  s50: prim_equal

value
s50(value a, value b)
{
    return boolean_encode(integer_decode(a) == integer_decode(b));
}

//  s10: prim_less

value
s10(value a, value b)
{
    return boolean_encode(integer_decode(a) < integer_decode(b));
}

//  s63: prim_less_or_equal

value
s63(value a, value b)
{
    return boolean_encode(integer_decode(a) <= integer_decode(b));
}

//  s61: prim_greater

value
s61(value a, value b)
{
    return boolean_encode(integer_decode(a) > integer_decode(b));
}

//  s55: prim_greater_or_equal

value
s55(value a, value b)
{
    return boolean_encode(integer_decode(a) >= integer_decode(b));
}

//  s65: prim_string_length

value
s65(value string)
{
    return integer_encode(string_length(string));
}

//  s69: prim_string_fetch

value
s69(value string, value i_value)
{
    int32_t i = integer_decode(i_value);
    const struct byte_vector *byte_vector_rep = string_unbox(string);
    if (i < 0 || (uint32_t)i >= byte_vector_rep->num_bytes - 1) {
        err_print_line("Character index is out of range.");
        halt();
    }
    return integer_encode(byte_vector_rep->bytes[i]);
}

//  s37: prim_string_compare

value
s37(value s1, value s2)
{
    return integer_encode(simple_strcmp(string_bytes(s1), string_bytes(s2)));
}

//  s45: prim_string_equal

value
s45(value s1, value s2)
{
    int c = simple_strcmp(string_bytes(s1), string_bytes(s2));
    return boolean_encode(c == 0);
}

//  s25: prim_string_append

value
s25(value s1, value s2)
{
    uint32_t s1_length = string_length(s1);
    uint32_t s2_length = string_length(s2);
    uint32_t s3_length = s1_length + s2_length;
    value s3 = byte_vector_make(s3_length + 1, NULL);
    char *s3_bytes = byte_vector_bytes(s3);
    memmove(s3_bytes, string_bytes(s1), s1_length);
    memmove(s3_bytes + s1_length, string_bytes(s2), s2_length + 1);
    return s3;
}

//  s44: prim_string_clip

value
s44(value s1, value begin, value end)
{
    uint32_t s1_length = string_length(s1);
    int32_t b = integer_decode(begin);
    int32_t e = integer_decode(end);
    if (b < 0 || e < 0 || b > e || (uint32_t)e > s1_length) {
        err_print_line("String clip parameters are invalid.");
        halt();
    }
    uint32_t s2_length = e - b;
    value s2 = byte_vector_make(s2_length + 1, NULL);
    const char *s1_bytes = string_bytes(s1);
    char *s2_bytes = string_bytes(s2);
    memmove(s2_bytes, s1_bytes + b, s2_length);
    s2_bytes[s2_length] = 0;
    return s2;
}