qic/qic.c

#include <ctype.h>
#include <stdio.h>
#include <stdarg.h>
#include <stdlib.h>

size_t GID = 0;

typedef struct {
  void **data;

  size_t length;
} list_t;

list_t *list_new(void) {
  list_t *list = malloc(sizeof(list_t));
  list->data = NULL;
  list->length = 0;

  return list;
}

void list_push(list_t *l, void *v) {
  size_t i = l->length++;

  l->data = realloc(l->data, l->length * sizeof(void *));

  l->data[i] = v;
}

void *list_pop(list_t *l) {
  if (!l->length)
    return NULL;

  return l->data[--l->length];
}

void *list_index(list_t *l, ssize_t index) {
  if (!l->length)
    return NULL;

  if (index < 0)
    index += ((ssize_t)l->length);

  if (index < 0 || index >= l->length)
    return NULL;

  return l->data[index];
}

void list_set(list_t *l, ssize_t index, void *v) {
  if (!l->length)
    return;

  if (index < 0)
    index += ((ssize_t)l->length);

  if (index < 0 || index >= l->length)
    return;

  l->data[index] = v;
}

typedef struct {
  size_t *data;
  size_t length;
} stack_t;

stack_t *stack_new(void) {
  stack_t *stack = malloc(sizeof(list_t));
  stack->data = NULL;
  stack->length = 0;

  return stack;
}

void stack_push(stack_t *l, size_t v) {
  size_t i = l->length++;

  l->data = realloc(l->data, l->length * sizeof(size_t));
  l->data[i] = v;
}

size_t stack_pop(stack_t *l) {
  if (!l->length)
    return 0;

  return l->data[--l->length];
}

struct entry_t {
  char *key;
  void *value;
};

struct table_t {
  struct entry_t *entries;

  size_t used;
  size_t capacity;
};

typedef struct entry_t entry_t;
typedef struct table_t table_t;

table_t *table_new() {
  table_t *table = malloc(sizeof(table_t));
  table->used = 0;

  table->capacity = 32;
  table->entries = calloc(table->capacity, sizeof(entry_t));

  return table;
}

unsigned long ht_hash(const char* key) {
    unsigned long hash = 5381;
    int c;

    while ((c = *key++))
        hash = ((hash << 5) + hash) + c;

    return hash;
}

void *table_get(table_t *table, char *key) {
  if (!table->used)
    return NULL;

  unsigned long hash = ht_hash(key);
  size_t index = hash % table->capacity;

  size_t i = index;

  while (table->entries[i].key) {
    if (strcmp(table->entries[i].key, key) == 0)
      return table->entries[i].value;

    i++;

    if (i >= table->capacity)
      i = 0;

    if (i == index)
      break;
  }

  return NULL;
}

static void table_entry_set(entry_t *entries, char *key, void *value, size_t capacity, size_t *used) {
  unsigned long hash = ht_hash(key);
  size_t index = hash % capacity;

  size_t i = index;

  while (entries[i].key) {
    if (strcmp(entries[i].key, key) == 0) {
      entries[i].value = value;

      return;
    }

    i++;

    if (i >= capacity)
      i = 0;

    if (i == index)
      break;
  }

  if (used)
    (*used)++;

  entries[i].key = key;
  entries[i].value = value;
}

table_t *table_set(table_t *table, char *key, void *value) {
  if (table->used >= table->capacity) {
    size_t capacity = table->capacity + 32;
    entry_t *entries = calloc(capacity, sizeof(entry_t));

    for (size_t i = 0; i < table->capacity; i++) {
      entry_t entry = table->entries[i];

      if (entry.key)
        table_entry_set(entries, entry.key, entry.value, capacity, NULL);
    }

    table->entries = entries;
    table->capacity = capacity;
  }

  table_entry_set(table->entries, key, value, table->capacity, &table->used);

  return table;
}

#define table_iterate(table, code)                                             \
  {                                                                            \
    if (table->used) {                                                         \
      size_t i = 0;                                                            \
      while (i < (table)->capacity) {                                          \
        entry_t entry = (table)->entries[i];                             \
        if (entry.key) {                                                       \
          code;                                                                \
        }                                                                      \
        i++;                                                                   \
      }                                                                        \
    }                                                                          \
  }

typedef struct {
  char *str;

  size_t size;
} buffer_t;

buffer_t *buffer_new(void) {
  buffer_t *buf = malloc(sizeof(buffer_t));

  buf->str = NULL;
  buf->size = 0;

  return buf;
}

void buffer_append(buffer_t *buf, char c) {
  buf->size++;

  void *p = malloc(sizeof(char) * buf->size);
  if (buf->str)
    memcpy(p, buf->str, buf->size - 1);

  buf->str = p;

  buf->str[buf->size - 1] = c;
}

char *buffer_read(buffer_t *buf) {
  if (buf->size == 0 || buf->str[buf->size - 1])
    buffer_append(buf, 0);

  return buf->str;
}

void buffer_appends(buffer_t *buf, char *s) {
  for (size_t i = 0; i < strlen(s); i++)
    buffer_append(buf, s[i]);
}

void buffer_appendb(buffer_t *dst, buffer_t *src) {
  for (size_t i = 0; i < src->size; i++)
    buffer_append(dst, src->str[i]);
}

void buffer_fmt(buffer_t *buf, const char *fmt, ...) {
  va_list args;
  va_start(args, fmt);

  size_t size = vsnprintf(NULL, 0, fmt, args);
  char *str = malloc(sizeof(char) * (size + 1));

  vsnprintf(str, size + 1, fmt, args);

  va_end(args);

  buffer_appends(buf, str);
}

typedef struct {
  enum {
    T_EOF,

    T_NUMBER,
    T_STRING,
    T_NAME,

    T_VAR,
    T_IF,
    T_ELSE,
    T_ELIF,
    T_FOR,
    T_BREAK,
    T_CONTINUE,
    T_PASS,
    T_FUNC,
    T_USE,
    T_RETURN,
    T_DEFER,

    T_LPAR,
    T_RPAR,
    T_LSB,
    T_RSB,
    T_LCB,
    T_RCB,

    T_EQUALS,
    T_PLUSASSIGN,
    T_BARBAR,
    T_ANDAND,
    T_STARSTAR,
    T_PLUSPLUS,
    T_MINUSMINUS,

    T_PLUS,
    T_MINUS,
    T_QM,
    T_COLON,
    T_BAR,
    T_AND,
    T_RAISE,
    T_LT,
    T_LTLT,
    T_GT,
    T_GTGT,
    T_STAR,
    T_SLASH,
    T_COMMA,
    T_DOT,

    T_ASSIGN,
    T_SEMI
  } tag;

  char *text;

  size_t fi;
  size_t pos;
} token_t;

token_t *token(int tag, char *text) {
  token_t *tok = malloc(sizeof(token_t));
  tok->tag = tag;
  tok->text = text;

  return tok;
}

#define TK(tk) (token(T_##tk, NULL))
#define WS() while (source[*pos] == ' ' || source[*pos] == '\t' || source[*pos] == '\n' || source[*pos] == '\r') { (*pos)++; }

void consume_ignored(char *source, size_t *pos) {
  WS();

  while (source[*pos] == '#') {
    (*pos)++;

    for (;;) {
      if (!source[*pos])
        break;

      if (source[*pos] == '\n') {
        (*pos)++;

        break;
      }

      (*pos)++;
    }

    WS();
  }
}

list_t *FILES;

void traverse(char *source, size_t pos, size_t *line, size_t *col) {
  *line = 1;
  *col = 1;

  for (size_t i = 0; i < pos; i++) {
     if (source[i] == '\n') {
       (*line)++;
       (*col) = 1;
     } else (*col)++;
  }
}

void format_error(char *filename, char *source, size_t pos, char *fmt, ...) {
  size_t line, col;
  traverse(source, pos, &line, &col);

  va_list args;
  va_start(args, fmt);

  fprintf(stderr, "%s (%zu:%zu): ", filename, line, col);
  vfprintf(stderr, fmt, args);
  fputc('\n', stderr);

  va_end(args);
}

#define GETFNAME(fi) ((char *)((list_t *)list_index(FILES, fi))->data[0])
#define GETSRC(fi) ((char *)((list_t *)list_index(FILES, fi))->data[1])

#define LEX_ERROR(fmt, ...) { format_error(GETFNAME(-1), source, *pos, fmt, ##__VA_ARGS__); exit(1); }

token_t *next_token(char *source, size_t *pos) {
  if (!source[*pos])
    return token(T_EOF, NULL);

  if (source[*pos] == '"' || source[*pos] == '\'') {
    char term = source[(*pos)++];

    buffer_t *text = buffer_new();

    while (source[*pos] != term) {
      if (!source[*pos])
        LEX_ERROR("unterminated string literal");

      char c = source[(*pos)++];

      if (c == '\\') {
        char nc = source[(*pos)++];

        if (!nc)
          continue;

        switch (nc) {
          case 'n':
            buffer_appends(text, "\\n");
            break;

          case 't':
            buffer_appends(text, "\\t");
            break;

          case 'r':
            buffer_appends(text, "\\r");
            break;

          case 'b':
            buffer_appends(text, "\\b");
            break;

          case 'e':
            buffer_appends(text, "\\e");
            break;

          case 's':
            buffer_appends(text, " ");
            break;

          case '"':
            buffer_appends(text, "\\\"");
            break;

          case '\\':
            buffer_appends(text, "\\\\");
            break;

          default:
            buffer_append(text, nc);
            break;
        }

        continue;
      }

      if (c == '"' || c == '\\')
        buffer_append(text, '\\');

      buffer_append(text, c);
    }

    (*pos)++;

    return token(T_STRING, buffer_read(text));
  } else if (isdigit(source[*pos])) {
    buffer_t *number = buffer_new();
    int dot = 0;
    int sub = 0;

    do {
      buffer_append(number, source[(*pos)++]);

      if (!dot && source[*pos] == '.') {
        buffer_append(number, source[(*pos)++]);

        if (!isdigit(source[*pos]))
          LEX_ERROR("illegal number literal (missing part after floating point)");

        dot = 1;
      } else if (!sub && source[*pos] == '.') {
        (*pos)++;

        sub = 1;
      } else if (sub) sub = 0;
    } while (isdigit(source[*pos]));

    return token(T_NUMBER, buffer_read(number));
  } else if (isalpha(source[*pos]) || source[*pos] == '_') {
    buffer_t *text = buffer_new();

    do {
      buffer_append(text, source[(*pos)++]);
    } while (isalpha(source[*pos]) || source[*pos] == '_' || isdigit(source[*pos]));

    char *name = buffer_read(text);

    if (strcmp(name, "var") == 0)
      return TK(VAR);
    else if (strcmp(name, "if") == 0)
      return TK(IF);
    else if (strcmp(name, "else") == 0)
      return TK(ELSE);
    else if (strcmp(name, "elif") == 0)
      return TK(ELIF);
    else if (strcmp(name, "for") == 0)
      return TK(FOR);
    else if (strcmp(name, "break") == 0)
      return TK(BREAK);
    else if (strcmp(name, "continue") == 0)
      return TK(CONTINUE);
    else if (strcmp(name, "func") == 0)
      return TK(FUNC);
    else if (strcmp(name, "use") == 0)
      return TK(USE);
    else if (strcmp(name, "return") == 0)
      return TK(RETURN);
    else if (strcmp(name, "defer") == 0)
      return TK(DEFER);
    else if (strcmp(name, "pass") == 0)
      return TK(PASS);

    return token(T_NAME, name);
  } else if (strncmp(&source[*pos], "==", 2) == 0 && ++(*pos) && ++(*pos))
    return TK(EQUALS);
  else if (strncmp(&source[*pos], "+=", 2) == 0 && ++(*pos) && ++(*pos))
    return TK(PLUSASSIGN);
  else if (strncmp(&source[*pos], "||", 2) == 0 && ++(*pos) && ++(*pos))
    return TK(BARBAR);
  else if (strncmp(&source[*pos], "&&", 2) == 0 && ++(*pos) && ++(*pos))
    return TK(ANDAND);
  else if (strncmp(&source[*pos], "++", 2) == 0 && ++(*pos) && ++(*pos))
    return TK(PLUSPLUS);
  else if (strncmp(&source[*pos], "--", 2) == 0 && ++(*pos) && ++(*pos))
    return TK(MINUSMINUS);
  else if (source[*pos] == '(' && ++(*pos))
    return TK(LPAR);
  else if (source[*pos] == ')' && ++(*pos))
    return TK(RPAR);
  else if (source[*pos] == '[' && ++(*pos))
    return TK(LSB);
  else if (source[*pos] == ']' && ++(*pos))
    return TK(RSB);
  else if (source[*pos] == '{' && ++(*pos))
    return TK(LCB);
  else if (source[*pos] == '}' && ++(*pos))
    return TK(RCB);
  else if (source[*pos] == '+' && ++(*pos))
    return TK(PLUS);
  else if (source[*pos] == '-' && ++(*pos))
    return TK(MINUS);
  else if (source[*pos] == '*' && ++(*pos))
    return TK(STAR);
  else if (source[*pos] == '/' && ++(*pos))
    return TK(SLASH);
  else if (source[*pos] == '?' && ++(*pos))
    return TK(QM);
  else if (source[*pos] == ':' && ++(*pos))
    return TK(COLON);
  else if (source[*pos] == '=' && ++(*pos))
    return TK(ASSIGN);
  else if (source[*pos] == ';' && ++(*pos))
    return TK(SEMI);
  else if (source[*pos] == ',' && ++(*pos))
    return TK(COMMA);
  else if (source[*pos] == '.' && ++(*pos))
    return TK(DOT);

  LEX_ERROR("unexpected input")
}

list_t *tokenize(char *source) {
  size_t pos = 0;
  list_t *toks = list_new();

  do {
    consume_ignored(source, &pos);

    size_t tok_pos = pos;

    token_t *tok = next_token(source, &pos);
    tok->fi = FILES->length-1;
    tok->pos = tok_pos;

    if (tok->tag == T_EOF)
      break;

    list_push(toks, tok);
  } while (1);

  return toks;
}

struct _node_t {
  enum {
    N_PROGRAM,
    N_EXPRSTMT,

    N_BLOCK,

    N_NEGATE,

    N_LITERAL,
    N_LIST,
    N_TUPLE,
    N_NILTUPLE,
    N_TABLE,

    N_CALL,
    N_MEMBER,
    N_INDEX,

    N_ADD,
    N_SUB,
    N_MUL,
    N_DIV,

    N_ASSIGN,
    N_ASSIGN_ADD,

    N_EQUALS,

    N_INC,
    N_DEC,

    N_VAR,
    N_IF,
    N_FOR,
    N_BREAK,
    N_CONTINUE,
    N_FUNCDEF,
    N_RETURN,
    N_DEFER,
    N_PASS,

    N_IFEXPR,
    N_FUNCEXPR,

    N_LOGOR,
    N_LOGAND,
  } tag;

  struct _node_t *a;
  struct _node_t *b;
  struct _node_t *c;
  struct _node_t *d;

  list_t *l;

  table_t *h;
  table_t *h2;

  token_t *t;

  size_t fi;
  size_t pos;
};
typedef struct _node_t node_t;

node_t *node_pos(node_t *node, size_t fi, size_t pos) {
  node->fi = fi;
  node->pos = pos;

  return node;
}

node_t *nodet(int tag, token_t *t) {
  node_t *node = malloc(sizeof(node_t));

  node->tag = tag;
  node->t = t;

  return node;
}

#define NODET(n, a) (node_pos(nodet(N_##n, (a)), ((token_t *)tokens->data[(*pos)-1])->fi, ((token_t *)tokens->data[(*pos)-1])->pos))

node_t *nodel(int tag, list_t *l) {
  node_t *node = malloc(sizeof(node_t));

  node->tag = tag;
  node->l = l;

  return node;
}

#define NODEL(n, a) (node_pos(nodel(N_##n, (a)), ((token_t *)tokens->data[(*pos)-1])->fi, ((token_t *)tokens->data[(*pos)-1])->pos))

node_t *nodeh(int tag, table_t *h) {
  node_t *node = malloc(sizeof(node_t));

  node->tag = tag;
  node->h = h;

  return node;
}

#define NODEH(n, a) (node_pos(nodeh(N_##n, (a)), ((token_t *)tokens->data[(*pos)-1])->fi, ((token_t *)tokens->data[(*pos)-1])->pos))

node_t *node0(int tag) {
  node_t *node = malloc(sizeof(node_t));

  node->tag = tag;

  return node;
}

#define NODE0(n) (node_pos(node0(N_##n), ((token_t *)tokens->data[(*pos)-1])->fi, ((token_t *)tokens->data[(*pos)-1])->pos))

node_t *node1(int tag, node_t *a) {
  node_t *node = malloc(sizeof(node_t));

  node->tag = tag;
  node->a = a;

  return node;
}

#define NODE1(n, a) (node_pos(node1(N_##n, (a)), ((token_t *)tokens->data[(*pos)-1])->fi, ((token_t *)tokens->data[(*pos)-1])->pos))

node_t *node1l(int tag, node_t *a, list_t *l) {
  node_t *node = malloc(sizeof(node_t));

  node->tag = tag;
  node->a = a;
  node->l = l;

  return node;
}

#define NODE1l(n, a, l) (node_pos(node1l(N_##n, (a), (l)), ((token_t *)tokens->data[(*pos)-1])->fi, ((token_t *)tokens->data[(*pos)-1])->pos))

node_t *node1t(int tag, node_t *a, token_t *t) {
  node_t *node = malloc(sizeof(node_t));

  node->tag = tag;
  node->a = a;
  node->t = t;

  return node;
}

#define NODE1t(n, a, t) (node_pos(node1t(N_##n, (a), (t)), ((token_t *)tokens->data[(*pos)-1])->fi, ((token_t *)tokens->data[(*pos)-1])->pos))

node_t *node2(int tag, node_t *a, node_t *b) {
  node_t *node = malloc(sizeof(node_t));

  node->tag = tag;
  node->a = a;
  node->b = b;

  return node;
}

#define NODE2(n, a, b) (node_pos(node2(N_##n, (a), (b)), ((token_t *)tokens->data[(*pos)-1])->fi, ((token_t *)tokens->data[(*pos)-1])->pos))

node_t *node3(int tag, node_t *a, node_t *b, node_t *c) {
  node_t *node = malloc(sizeof(node_t));

  node->tag = tag;
  node->a = a;
  node->b = b;
  node->c = c;

  return node;
}

#define NODE3(n, a, b, c) (node_pos(node3(N_##n, (a), (b), (c)), ((token_t *)tokens->data[(*pos)-1])->fi, ((token_t *)tokens->data[(*pos)-1])->pos))

node_t *node4(int tag, node_t *a, node_t *b, node_t *c, node_t *d) {
  node_t *node = malloc(sizeof(node_t));

  node->tag = tag;
  node->a = a;
  node->b = b;
  node->c = c;
  node->d = d;

  return node;
}

#define NODE4(n, a, b, c, d) (node_pos(node4(N_##n, (a), (b), (c), (d)), ((token_t *)tokens->data[(*pos)-1])->fi, ((token_t *)tokens->data[(*pos)-1])->pos))

node_t *nodef(int tag, token_t *name, table_t *params, table_t *captured, node_t *body) {
  node_t *node = malloc(sizeof(node_t));

  node->tag = tag;
  node->t = name;
  node->h = params;
  node->h2 = captured;
  node->a = body;

  return node;
}

#define NODEF(n, a, b, c, d) (node_pos(nodef(N_##n, (a), (b), (c), (d)), ((token_t *)tokens->data[(*pos)-1])->fi, ((token_t *)tokens->data[(*pos)-1])->pos))

#define AT(tk) (*pos < tokens->length && ((token_t *)tokens->data[*pos])->tag == T_##tk)
#define MATCH(tk) (AT(tk) && ++(*pos))
#define PARSE_ERROR(fmt, ...) { format_error(GETFNAME(((token_t *)tokens->data[(*pos)>0?(*pos)-1:(*pos)])->fi), GETSRC(((token_t *)tokens->data[(*pos)>0?(*pos)-1:(*pos)])->fi), ((token_t *)tokens->data[(*pos)>0?(*pos)-1:(*pos)])->pos, fmt, ##__VA_ARGS__); exit(1); }
#define EXPECT(tk, s) { if (!MATCH(tk)) PARSE_ERROR("expected %s", (s)); }

node_t *parse_expr(list_t *tokens, size_t *pos);

list_t *parse_sequence(list_t *tokens, size_t *pos, int term) {
  list_t *seq = list_new();

  do {
    if (term != -1 && *pos < tokens->length && ((token_t *)tokens->data[*pos])->tag == term)
      break;

    list_push(seq, parse_expr(tokens, pos));
  } while (MATCH(COMMA));

  return seq;
}

node_t *parse_func(list_t *tokens, size_t *pos, int is_expr);

node_t *parse_primary(list_t *tokens, size_t *pos) {
  if (MATCH(FUNC))
    return parse_func(tokens, pos, 1);
  else if (MATCH(LPAR)) {
    if (MATCH(RPAR))
      return NODE0(NILTUPLE);

    node_t *a = parse_expr(tokens, pos);

    if (MATCH(COMMA)) {
      list_t *l = list_new();
      list_push(l, a);

      if (!AT(RPAR))
        do {
          node_t *n = parse_expr(tokens, pos);

          list_push(l, n);
        } while (MATCH(COMMA));

      a = NODEL(TUPLE, l);
    }

    EXPECT(RPAR, ")");

    return a;
  } else if (MATCH(LSB)) {
    list_t *a = parse_sequence(tokens, pos, T_RSB);

    EXPECT(RSB, "]");

    return NODEL(LIST, a);
  } else if (MATCH(LCB)) {
    table_t *table = table_new();

    do {
      if (AT(RCB))
        break;

      if (!AT(NAME) && !AT(STRING))
        PARSE_ERROR("expected identifier or string");

      char *key = ((token_t *)tokens->data[(*pos)++])->text;

      EXPECT(COLON, ":");

      node_t *val = parse_expr(tokens, pos);

      table_set(table, key, val);
    } while (MATCH(COMMA));

    EXPECT(RCB, "}");

    return NODEH(TABLE, table);
  } else if (MATCH(NUMBER) || MATCH(STRING) || MATCH(NAME))
    return NODET(LITERAL, tokens->data[(*pos)-1]);

  PARSE_ERROR("expected expression");

  return NULL;
}

size_t get_lineno(token_t *tok) {
  size_t line, col;
  traverse(GETSRC(tok->fi), tok->pos, &line, &col);

  return line;
}

#define CLIFF (get_lineno(((token_t *)tokens->data[(*pos)>0?(*pos)-1:(*pos)])) != get_lineno(((token_t *)tokens->data[(*pos)>=tokens->length?tokens->length-1:(*pos)])))

node_t *parse_call(list_t *tokens, size_t *pos) {
  node_t *a = parse_primary(tokens, pos);

  do {
    if (!CLIFF && MATCH(LPAR)) {
      list_t *b = NULL;

      if (!AT(RPAR))
        b = parse_sequence(tokens, pos, -1);

      EXPECT(RPAR, ")");

      a = NODE1l(CALL, a, b);

      continue;
    } else if (!CLIFF && MATCH(LSB)) {
      node_t *b = parse_expr(tokens, pos);

      EXPECT(RSB, "]");

      a = NODE2(INDEX, a, b);

      continue;
    } else if (!CLIFF && MATCH(DOT)) {
      if (!AT(NAME))
        PARSE_ERROR("expected identifier after .");

      a = NODE1t(MEMBER, a, tokens->data[(*pos)++]);

      continue;
    }

    break;
  } while (1);

  return a;
}

node_t *parse_postfix(list_t *tokens, size_t *pos) {
  node_t *a = parse_call(tokens, pos);

  if (CLIFF)
    return a;

  if (MATCH(PLUSPLUS))
    return NODE1(INC, a);
  else if (MATCH(MINUSMINUS))
    return NODE1(DEC, a);

  return a;
}

node_t *parse_unary(list_t *tokens, size_t *pos) {
  if (MATCH(MINUS)) {
    node_t *a = parse_unary(tokens, pos);

    return NODE1(NEGATE, a);
  }

  return parse_postfix(tokens, pos);
}

node_t *parse_pow(list_t *tokens, size_t *pos) {
  node_t *a = parse_unary(tokens, pos);

  return a;
}

node_t *parse_mul(list_t *tokens, size_t *pos) {
  node_t *a = parse_pow(tokens, pos);

  do {
    if (MATCH(STAR)) {
      node_t *b = parse_pow(tokens, pos);

      a = NODE2(MUL, a, b);

      continue;
    } else if (MATCH(SLASH)) {
      node_t *b = parse_pow(tokens, pos);

      a = NODE2(DIV, a, b);

      continue;
    }

    break;
  } while (1);

  return a;
}

node_t *parse_add(list_t *tokens, size_t *pos) {
  node_t *a = parse_mul(tokens, pos);

  do {
    if (MATCH(PLUS)) {
      node_t *b = parse_mul(tokens, pos);

      a = NODE2(ADD, a, b);

      continue;
    } else if (MATCH(MINUS)) {
      node_t *b = parse_mul(tokens, pos);

      a = NODE2(SUB, a, b);

      continue;
    }

    break;
  } while (1);

  return a;
}

node_t *parse_shift(list_t *tokens, size_t *pos) {
  node_t *a = parse_add(tokens, pos);

  return a;
}

node_t *parse_relation(list_t *tokens, size_t *pos) {
  node_t *a = parse_shift(tokens, pos);

  return a;
}

node_t *parse_equality(list_t *tokens, size_t *pos) {
  node_t *a = parse_relation(tokens, pos);

  do {
    if (MATCH(EQUALS)) {
      node_t *b = parse_relation(tokens, pos);

      a = NODE2(EQUALS, a, b);

      continue;
    }

    break;
  } while (1);

  return a;
}

node_t *parse_bitand(list_t *tokens, size_t *pos) {
  node_t *a = parse_equality(tokens, pos);

  return a;
}

node_t *parse_bitxor(list_t *tokens, size_t *pos) {
  node_t *a = parse_bitand(tokens, pos);

  return a;
}

node_t *parse_bitor(list_t *tokens, size_t *pos) {
  node_t *a = parse_bitxor(tokens, pos);

  return a;
}

node_t *parse_logand(list_t *tokens, size_t *pos) {
  node_t *a = parse_bitor(tokens, pos);

  if (MATCH(ANDAND)) {
    node_t *b = parse_logand(tokens, pos);

    return NODE2(LOGAND, a, b);
  }

  return a;
}

node_t *parse_logor(list_t *tokens, size_t *pos) {
  node_t *a = parse_logand(tokens, pos);

  if (MATCH(BARBAR)) {
    node_t *b = parse_logor(tokens, pos);

    return NODE2(LOGOR, a, b);
  }

  return a;
}

node_t *parse_assignment(list_t *tokens, size_t *pos);

node_t *parse_conditional(list_t *tokens, size_t *pos) {
  node_t *a = parse_logor(tokens, pos);

  if (MATCH(QM)) {
    node_t *b = parse_assignment(tokens, pos);

    EXPECT(COLON, ":");

    node_t *c = parse_assignment(tokens, pos);

    return NODE3(IFEXPR, a, b, c);
  }

  return a;
}

node_t *parse_assignment(list_t *tokens, size_t *pos) {
  node_t *a = parse_conditional(tokens, pos);

  if (MATCH(ASSIGN)) {
    node_t *b = parse_assignment(tokens, pos);

    return NODE2(ASSIGN, a, b);
  } else if (MATCH(PLUSASSIGN)) {
    node_t *b = parse_assignment(tokens, pos);

    return NODE2(ASSIGN_ADD, a, b);
  }

  return a;
}

node_t *parse_expr(list_t *tokens, size_t *pos) {
  return parse_assignment(tokens, pos);
}

node_t *parse_stmt(list_t *tokens, size_t *pos);

node_t *parse_block(list_t *tokens, size_t *pos) {
  EXPECT(LCB, "{");

  list_t *stmts = list_new();
  while (!AT(EOF) && !AT(RCB))
    list_push(stmts, parse_stmt(tokens, pos));

  EXPECT(RCB, "}");

  return NODEL(PROGRAM, stmts);
}

#define BLOCK() (MATCH(COLON)?parse_stmt(tokens, pos):parse_block(tokens, pos))

node_t *parse_if(list_t *tokens, size_t *pos) {
  node_t *a = parse_expr(tokens, pos);
  node_t *b = BLOCK();
  node_t *c = NULL;

  if (MATCH(ELSE))
    c = BLOCK();
  else if (MATCH(ELIF))
    c = parse_if(tokens, pos);

  return NODE3(IF, a, b, c);
}

node_t *parse_var(list_t *tokens, size_t *pos) {
  table_t *h = table_new();

  do {
    if(!AT(NAME))
      PARSE_ERROR("expected identifier");

    char *k = ((token_t *)tokens->data[(*pos)++])->text;
    node_t *v = NULL;

    if (MATCH(ASSIGN))
      v = parse_expr(tokens, pos);

    table_set(h, k, v);
  } while (MATCH(COMMA));

  return NODEH(VAR, h);
}

node_t *parse_func(list_t *tokens, size_t *pos, int is_expr) {
  token_t *name = NULL;

  if (!is_expr) {
    if(!AT(NAME))
      PARSE_ERROR("expected identifier");

    name = tokens->data[(*pos)++];
  }

  EXPECT(LPAR, "(");

  table_t *params = NULL;

  if (!AT(RPAR)) {
    int flag = 0;

    params = table_new();

    size_t argc = 0;

    do {
      if(!AT(NAME))
        PARSE_ERROR("expected identifier");

      char *l = ((token_t *)tokens->data[(*pos)++])->text;
      node_t *r = NULL;

      if (!flag && AT(ASSIGN))
        flag = 1;

      if (flag) {
        EXPECT(ASSIGN, "=");

        r = parse_expr(tokens, pos);
      }

      list_t *pair = list_new();

      size_t *argcp = malloc(sizeof(size_t));
      memcpy(argcp, &argc, sizeof(size_t));

      argc++;

      list_push(pair, argcp);
      list_push(pair, r);

      table_set(params, l, pair);
    } while (MATCH(COMMA));
  }

  EXPECT(RPAR, ")");

  table_t *captured = NULL;

  if (MATCH(USE)) {
    EXPECT(RPAR, "(");

    captured = table_new();

    do {
      if(!AT(NAME))
        PARSE_ERROR("expected identifier");

      token_t *name = tokens->data[(*pos)++];

      table_set(captured, name->text, NODET(LITERAL, name));
    } while (MATCH(COMMA));

    EXPECT(RPAR, ")");
  }

  node_t *body = BLOCK();

  if (is_expr)
    return NODEF(FUNCEXPR, NULL, params, captured, body);

  return NODEF(FUNCDEF, name, params, captured, body);
}

node_t *parse_stmt(list_t *tokens, size_t *pos) {
  if (MATCH(LCB)) {
    list_t *stmts = list_new();

    while (!AT(EOF) && !AT(RCB)) {
      node_t *n = parse_stmt(tokens, pos);

      MATCH(SEMI);

      list_push(stmts, n);
    }

    EXPECT(RCB, "}");

    return NODEL(BLOCK, stmts);
  } else if (MATCH(VAR))
    return parse_var(tokens, pos);
  else if (MATCH(IF))
    return parse_if(tokens, pos);
  else if (MATCH(FOR)) {
    node_t *a = NULL;
    node_t *b = NULL;
    node_t *c = NULL;

    if (!AT(LCB) && !AT(COLON)) {
      if (MATCH(VAR)) {
        a = parse_var(tokens, pos);
        EXPECT(SEMI, ";");
        b = parse_expr(tokens, pos);
        EXPECT(SEMI, ";");
        c = parse_expr(tokens, pos);
      } else a = parse_expr(tokens, pos);
    }

    node_t *d = BLOCK();

    return NODE4(FOR, a, b, c, d);
  } else if (MATCH(BREAK)) return NODE0(BREAK);
  else if (MATCH(CONTINUE)) return NODE0(CONTINUE);
  else if (MATCH(FUNC))
    return parse_func(tokens, pos, 0);
  else if (MATCH(RETURN)) {
    node_t *a = NULL;

    if (!AT(RCB) && !AT(EOF) && !CLIFF)
      a = parse_expr(tokens, pos);

    return NODE1(RETURN, a);
  } else if (MATCH(DEFER)) {
    node_t *a;

    if (AT(LCB) || AT(COLON))
      a = BLOCK();
    else a = parse_stmt(tokens, pos);

    return NODE1(DEFER, a);
  } else if (MATCH(PASS)) return NODE0(PASS);

  node_t *n = parse_expr(tokens, pos);

  return NODE1(EXPRSTMT, n);
}

node_t *parse_program(list_t *tokens, size_t *pos) {
  list_t *stmts = list_new();

  while (*pos < tokens->length) {
    node_t *n = parse_stmt(tokens, pos);

    MATCH(SEMI);

    list_push(stmts, n);
  }

  return NODEL(PROGRAM, stmts);
}

node_t *parse(char *source) {
  size_t pos = 0;

  return parse_program(tokenize(source), &pos);
}

#define NEWGID() size_t gid = GID++
 
#define EMIT(fmt, ...) buffer_fmt(buf, (fmt), ##__VA_ARGS__);
#define BINOP(s) { EMIT("qi_" s "(state, "); compile_node(gbuf, buf, ctx, lstk, node->a); EMIT(", "); compile_node(gbuf, buf, ctx, lstk, node->b); EMIT(")"); }
#define UNOP(s) { EMIT("qi_" s "(state, "); compile_node(gbuf, buf, ctx, lstk, node->a); EMIT(")"); }
#define ASSIGN(lhs, rhs) {\
  if ((lhs)->tag == N_LITERAL && (lhs)->t->tag == T_NAME) {\
    EMIT("qi_set(state, false, \"%s\", ", (lhs)->t->text);\
    rhs;\
    EMIT(")");\
  } else if ((lhs)->tag == N_INDEX) {\
    EMIT("qi_index_set(state, false, ");\
    compile_node(gbuf, buf, ctx, lstk, (lhs)->a);\
    EMIT(", ");\
    compile_node(gbuf, buf, ctx, lstk, (lhs)->b);\
    EMIT(", ");\
    rhs;\
    EMIT(")");\
  } else if ((lhs)->tag == N_MEMBER) {\
    EMIT("qi_index_set(state, false, ");\
    compile_node(gbuf, buf, ctx, lstk, (lhs)->a);\
    EMIT(", qi_make_string(state, \"%s\"), ", (lhs)->t->text);\
    rhs;\
    EMIT(")");\
  } else COMPILE_ERROR("illegal assignment left-hand side");\
}
#define COMPASSIGN(lhs, s, rhs) {\
  ASSIGN(node->a, {\
    EMIT("qi_%s(state, ", s);\
    compile_node(gbuf, buf, ctx, lstk, (lhs));\
    EMIT(", ");\
    rhs;\
    EMIT(")");\
  });\
}
#define COMPILE_ERROR(fmt, ...) { format_error(GETFNAME(node->fi), GETSRC(node->fi), node->pos, fmt, ##__VA_ARGS__); exit(1); }

void compile_node(buffer_t *gbuf, buffer_t *buf, list_t *ctx, stack_t *lstk, node_t *node);

void compile_list(buffer_t *gbuf, buffer_t *buf, list_t *ctx, stack_t *lstk, list_t *seq) {
  if (!seq || seq->length < 1) {
    EMIT("NULL");

    return;
  }

  buffer_t *tbuf = buffer_new();

  NEWGID();

  buffer_fmt(tbuf, "qi_list_t *__list%d(qi_state_t *state) {\n", gid);
  buffer_fmt(tbuf, "qi_list_t *list = qi_list_make();\n");

  for (size_t i = 0; i < seq->length; i++) {
    buffer_fmt(tbuf, "qi_list_push(list, ");

    compile_node(gbuf, tbuf, ctx, lstk, seq->data[i]);

    buffer_fmt(tbuf, ");\n");
  }

  buffer_fmt(tbuf, "return list;\n");
  buffer_fmt(tbuf, "}\n");

  buffer_appendb(gbuf, tbuf);

  EMIT("__list%d(state)", gid);
}

void compile_table(buffer_t *gbuf, buffer_t *buf, list_t *ctx, stack_t *lstk, table_t *table) {
  if (!table || table->used < 1) {
    EMIT("NULL");

    return;
  }

  buffer_t *tbuf = buffer_new();

  NEWGID();

  buffer_fmt(tbuf, "qi_table_t *__table%d(qi_state_t *state) {\n", gid);
  buffer_fmt(tbuf, "qi_table_t *table = qi_table_make();\n");

  table_iterate(table, {
    buffer_fmt(tbuf, "qi_table_set(table, \"%s\", ", entry.key);

    compile_node(gbuf, tbuf, ctx, lstk, entry.value);

    buffer_fmt(tbuf, ");\n");
  });

  buffer_fmt(tbuf, "return table;\n");
  buffer_fmt(tbuf, "}\n");

  buffer_appendb(gbuf, tbuf);

  EMIT("__table%d(state)", gid);
}

#define CTXPUSH(s) list_push(ctx, (s))
#define CTXPOP() list_pop(ctx)

int in_context(list_t *ctx, char *s) {
  if (!ctx->length)
    return 0;

  for (ssize_t i = ctx->length - 1; i >= 0; i--) {
    if (strcmp(ctx->data[i], "gap") == 0)
      break;
    else if (strcmp(ctx->data[i], s) == 0)
      return 1;
  }

  return 0;
}

#define INCTX(s) (in_context(ctx, (s)))

#define LPUSH(i) stack_push(lstk, (i))
#define LPOP() stack_pop(lstk)
#define LID (lstk->data[lstk->length-1])

void compile_func(buffer_t *gbuf, buffer_t *buf, list_t *ctx, stack_t *lstk, node_t *node) {
  NEWGID();

  buffer_t *tbuf = buffer_new();

  buffer_fmt(tbuf, "qi_value_t *__func%d(qi_state_t *state, qi_size_t pargc, qi_list_t *pargs) {\n", gid);

  CTXPUSH("gap");
  CTXPUSH("func");

  size_t optargc = 0;

  if (node->h) {
    table_iterate(node->h, {
      list_t *pair = entry.value;

      size_t argc = *(size_t *)pair->data[0];

      if (pair->data[1]) {
        optargc++;

        buffer_fmt(tbuf, "qi_set(state, false, false, \"%s\", pargc >= %d? qi_list_index(pargs, %d): ", entry.key, argc+1, argc);
        compile_node(gbuf, tbuf, ctx, lstk, pair->data[1]);
        buffer_fmt(tbuf, ");\n");
      } else
        buffer_fmt(tbuf, "qi_set(state, false, false, \"%s\", qi_list_index(pargs, %d));\n", entry.key, argc);

      argc++;
    });
  }

  compile_node(gbuf, tbuf, ctx, lstk, node->a);

  CTXPOP();
  CTXPOP();

  buffer_fmt(tbuf, "return state->nil;\n");
  buffer_fmt(tbuf, "}\n");

  buffer_appendb(gbuf, tbuf);

  tbuf = buffer_new();

  buffer_fmt(tbuf, "qi_make_function(state, \"%s\", %d, __func%d, ", node->t? node->t->text: "<anon>", !node->h? 0: (node->h->used - optargc), gid);
  compile_table(gbuf, tbuf, ctx, lstk, node->h2);
  buffer_fmt(tbuf, ")");

  if (node->tag == N_FUNCEXPR) {
    buffer_appendb(buf, tbuf);

    return;
  }

  EMIT("qi_set(state, false, false, \"%s\", ", node->t->text);
  buffer_appendb(buf, tbuf);
  EMIT(");");
}

void compile_block(buffer_t *gbuf, buffer_t *buf, list_t *ctx, stack_t *lstk, list_t *block) {
  for (size_t i = 0; i < block->length; i++) {
    node_t *n = block->data[i];

    if (n->tag == N_FUNCDEF) {
      compile_func(gbuf, buf, ctx, lstk, n);

      EMIT("\n");
    } else if (n->tag == N_VAR) {
      table_iterate(n->h, {
        EMIT("qi_decl(state, \"%s\", ", entry.key);
        
        if (entry.value)
          compile_node(gbuf, buf, ctx, lstk, entry.value);
        else EMIT("state->nil");

        EMIT(");\n");
      });
    }
  }

  for (size_t i = 0; i < block->length; i++) {
    compile_node(gbuf, buf, ctx, lstk, block->data[i]);

    EMIT("\n");
  }
}

void compile_node(buffer_t *gbuf, buffer_t *buf, list_t *ctx, stack_t *lstk, node_t *node) {
  switch (node->tag) {
    case N_PROGRAM:
      compile_block(gbuf, buf, ctx, lstk, node->l);
      break;

    case N_EXPRSTMT:
      EMIT("(void)(");
      compile_node(gbuf, buf, ctx, lstk, node->a);
      EMIT(");");
      break;

    case N_BLOCK:
      EMIT("qi_new_scope(state);\n");
      compile_block(gbuf, buf, ctx, lstk, node->l);
      EMIT("qi_old_scope(state);");
      break;

    case N_LITERAL:
      switch (node->t->tag) {
        case T_NUMBER:
          EMIT("qi_make_number(state, %s)", node->t->text);
          break;

        case T_STRING:
          if (!*(node->t->text)) {
            EMIT("state->empty_string");
          } else {
            EMIT("qi_make_string(state, \"%s\")", node->t->text);
          }
          break;

        case T_NAME:
          EMIT("qi_get(state, \"%s\")", node->t->text);
          break;

        default:
          COMPILE_ERROR("not yet implemented");
      }
      break;

    case N_LIST:
      EMIT("qi_make_list(state, ");
      compile_list(gbuf, buf, ctx, lstk, node->l);
      EMIT(")");
      break;

    case N_TUPLE:
      EMIT("qi_make_tuple(state, ");
      compile_list(gbuf, buf, ctx, lstk, node->l);
      EMIT(")");
      break;

    case N_NILTUPLE: EMIT("state->empty_tuple"); break;

    case N_TABLE:
      EMIT("qi_make_table(state, ");
      compile_table(gbuf, buf, ctx, lstk, node->h);
      EMIT(")");
      break;

    case N_CALL:
      EMIT("qi_call(state, ");
      compile_node(gbuf, buf, ctx, lstk, node->a);
      EMIT(", ");
      compile_list(gbuf, buf, ctx, lstk, node->l);
      EMIT(")");
      break;

    case N_MEMBER:
      EMIT("qi_index(state, ");
      compile_node(gbuf, buf, ctx, lstk, node->a);
      EMIT(", qi_make_string(state, \"%s\"))", node->t->text);
      break;

    case N_INDEX:
      EMIT("qi_index(state, ");
      compile_node(gbuf, buf, ctx, lstk, node->a);
      EMIT(", ");
      compile_node(gbuf, buf, ctx, lstk, node->b);
      EMIT(")");
      break;

    case N_ASSIGN: ASSIGN(node->a, compile_node(gbuf, buf, ctx, lstk, node->b)); break;

    case N_ASSIGN_ADD: COMPASSIGN(node->a, "add", compile_node(gbuf, buf, ctx, lstk, node->b)); break;

    case N_INC: 
      COMPASSIGN(node->a, "add", EMIT("state->one"));
      break;

    case N_DEC: 
      COMPASSIGN(node->a, "sub", EMIT("state->one"));
      break;

    case N_VAR: break;

    case N_IF:
      EMIT("if (_qi_truthy(state, ");
      compile_node(gbuf, buf, ctx, lstk, node->a);
      EMIT(") {\n");
      EMIT("qi_new_subscope(state);\n");
      compile_node(gbuf, buf, ctx, lstk, node->b);
      EMIT("qi_old_scope(state);\n");
      if (node->c) {
        EMIT("} else {\n");
        EMIT("qi_new_subscope(state);\n");
        compile_node(gbuf, buf, ctx, lstk, node->c);
        EMIT("qi_old_scope(state);\n");
      }
      EMIT("}");
      break;

    case N_FOR: {
      NEWGID();

      EMIT("qi_new_subscope(state);\n");

      if (!node->a) {
        EMIT("for (;;) {\n");
      } else if (node->a && !node->b) {
        EMIT("while (_qi_truthy(state, ");
        compile_node(gbuf, buf, ctx, lstk, node->a);
        EMIT(")) {\n");
      } else {
        compile_node(gbuf, buf, ctx, lstk, node->a);
        EMIT("while (_qi_truthy(state, ");
        compile_node(gbuf, buf, ctx, lstk, node->b);
        EMIT(")) {\n");
      }

      LPUSH(gid);
      CTXPUSH("for");
      compile_node(gbuf, buf, ctx, lstk, node->d);
      CTXPOP();
      LPOP();

      EMIT("__continue%d:;\n", gid);

      if (node->c)
        compile_node(gbuf, buf, ctx, lstk, node->c);

      EMIT("}\n");

      EMIT("__break%d:;\n", gid);

      EMIT("qi_old_scope(state);\n");
      } break;

    case N_BREAK:
      if (!INCTX("for"))
        COMPILE_ERROR("break outside of a loop");

      EMIT("goto __break%d;", LID);
      break;

    case N_CONTINUE:
      if (!INCTX("for"))
        COMPILE_ERROR("continue outside of a loop");

      EMIT("goto __continue%d;", LID);
      break;

    case N_DEFER: {
      NEWGID();

      buffer_t *tbuf = buffer_new();

      buffer_fmt(tbuf, "void __defer%d(qi_state_t *state) {\n", gid);

      CTXPUSH("gap");
      compile_node(gbuf, tbuf, ctx, lstk, node->a);
      CTXPOP();

      buffer_fmt(tbuf, "\n");
      buffer_fmt(tbuf, "}\n");

      buffer_appendb(gbuf, tbuf);

      EMIT("qi_add_defer(state, -1, __defer%d);", gid);
      } break;

    case N_RETURN:
      if (!INCTX("func"))
        COMPILE_ERROR("return outside of a function");

      EMIT("return ");

      if (node->a)
        compile_node(gbuf, buf, ctx, lstk, node->a);

      EMIT(";");
      break;

    case N_FUNCDEF: break;
    case N_PASS: break;

    case N_IFEXPR:
      EMIT("(_qi_truthy(state, ");
      compile_node(gbuf, buf, ctx, lstk, node->a);
      EMIT(")? ");
      compile_node(gbuf, buf, ctx, lstk, node->b);
      EMIT(": ");
      compile_node(gbuf, buf, ctx, lstk, node->c);
      EMIT(")");
      break;

    case N_FUNCEXPR:
      compile_func(gbuf, buf, ctx, lstk, node);
      break;

    case N_EQUALS:
      BINOP("equals");
      break;

    case N_ADD:
      BINOP("add");
      break;

    case N_SUB:
      BINOP("sub");
      break;

    case N_MUL:
      BINOP("mul");
      break;

    case N_DIV:
      BINOP("div");
      break;

    case N_NEGATE:
      UNOP("negate");
      break;

    default:
      COMPILE_ERROR("not yet implemented");
  }
}

char *compile(char *source) {
  node_t *n = parse(source);

  list_t *ctx = list_new();
  stack_t *lstk = stack_new();
  
  buffer_t *gbuf = buffer_new();

  buffer_appends(gbuf, "#include <qirt.h>\n");

  buffer_t *buf = buffer_new();

  compile_node(gbuf, buf, ctx, lstk, n);

  buffer_t *rbuf = buffer_new();

  buffer_appendb(rbuf, gbuf);

  buffer_appends(rbuf, "int main(int argc, char **argv) {\n");
  buffer_appends(rbuf, "qi_state_t *state;\n");
  buffer_appends(rbuf, "qi_state_init(&state);\n");
  buffer_appendb(rbuf, buf);
  buffer_appends(rbuf, "qi_old_scope(state);\n");
  buffer_appends(rbuf, "qi_finalize();\n");
  buffer_appends(rbuf, "return 0;\n");
  buffer_appends(rbuf, "}\n");
  
  return buffer_read(rbuf);
}

char *compile_file(char *filename, FILE *fd) {
  buffer_t *buf = buffer_new();

  for (;;) {
    char line[512];

    if (!fgets(line, sizeof(line), fd))
      break;

    buffer_appends(buf, line);
  }

  char *source = buffer_read(buf);

  list_t *pair = list_new();
  list_push(pair, filename);
  list_push(pair, source);

  list_push(FILES, pair);

  char *out = compile(source);

  list_pop(FILES);

  return out;
}

int main(int argc, char **argv) {
  FILES = list_new();

  char *out = compile_file("<stdin>", stdin);

  fwrite(out, sizeof(char), strlen(out), stdout);

  return 0;
}