#include "syntax.h"
#include "bitset.h"
#include "builtins.h"
#include "error.h"
#include "lexer.h"
#include "scope.h"
#include "util.h"
#include "intern.h"
#include "value.h"
#include <string.h>
#include <ctype.h>
#include <stdlib.h>
#include <stdbool.h>
#include <stdio.h>

static bool _expect(lexer_t *lexer, token_type expected, error_tag on_failure) {
  token_t tok = lexer_lex(lexer);
  if (tok.type != expected) {
    error_report(error(on_failure,lexer_source(lexer),tok.pos,tok.len));
    return false;
  } else {
    return true;
  }
}

static expr_t *_alloc_expr(void) {
  expr_t *ptr = malloc(sizeof(struct expr));
  if (ptr == NULL) {
    die("Out of memory: cannot allocate expr struct");
  }
  return ptr;
}

static char *_parse_string_literal(const char *input) {
  if (!input || *input != '"') {
    die("Provided string is not a string literal");
  }
  const char *p = input + 1; // skip opening quote
  size_t capacity = 16;
  size_t length = 0;
  char *result = malloc(capacity);
  if (result == NULL) {
    die("Out of memory: Cannot allocate space for string literal");
  }

  while (*p != '\0' && *p != '"') {
    char c = *p++;
    if (c == '\\') {
      if (!*p) break; // unterminated escape
      char esc = *p++;
      switch (esc) {
        case 'n': c = '\n'; break;
        case 't': c = '\t'; break;
        case 'r': c = '\r'; break;
        case '\\': c = '\\'; break;
        case '"': c = '"'; break;
        case '\'': c = '\''; break;
        default: c = esc; break;
      }
    }
    if (length + 1 >= capacity) {
      capacity *= 2;
      char *tmp = realloc(result, capacity);
      if (tmp == NULL) {
        die("Out of memory: Cannot enlarge space for string literal");
      }
      result = tmp;
    }
    result[length++] = c;
  }
  if (*p != '"') {
    die("The impossible happened");
  }

  result[length] = '\0'; // null-terminate
  return result;
}

static expr_t *_parse_expr(lexer_t *lexer, intern_table_t *table);


static expr_t *_parse_atom(lexer_t *lexer, intern_table_t *table) { 
  token_t tok = lexer_peek(lexer); 
  switch (tok.type) {
    case TOKEN_LPAREN: {
      lexer_lex(lexer); 
      
      expr_t *first_expr = _parse_expr(lexer, table);
      token_t next_tok = lexer_peek(lexer); 
      
      if (first_expr == NULL) {
        if (next_tok.type == TOKEN_RPAREN) {
            error_report(error(ERROR_EXPECTED_EXPRESSION, lexer_source(lexer), next_tok.pos, 1));
            
            lexer_lex(lexer); // Consume ')'
            return NULL;
        }
        return NULL; 
      }

      if (next_tok.type != TOKEN_COMMA) {
        // Single element parenthesized expression
        if (!_expect(lexer, TOKEN_RPAREN, ERROR_EXPECTED_RPAREN)) {
          syntax_expr_free(first_expr);
          return NULL;
        }
        return first_expr;
      }

      // Multi-element tuple
      lexer_lex(lexer); // consume the first ','

      size_t cap = 4;
      size_t nargs = 1; 
      expr_t **args = malloc(cap * sizeof(expr_t*));
      if (args == NULL)
        die("Out of memory: can't allocate args array for tuple");

      args[0] = first_expr; 

      while (1) {
        token_t next_arg_tok = lexer_peek(lexer);
        expr_t *arg = _parse_expr(lexer, table);
        
        if (arg == NULL) {
          error_report(error(ERROR_EXPECTED_EXPRESSION, lexer_source(lexer), next_arg_tok.pos, 1));
          
          for (size_t i = 0; i < nargs; i++) {
            syntax_expr_free(args[i]);
          }
          free(args);
          return NULL;
        }

        if (nargs == cap) {
          cap *= 2;
          expr_t **temp_args = realloc(args, cap * sizeof(expr_t*));
          if (temp_args == NULL)
            die("Out of memory: can't enlarge args array for tuple");
          args = temp_args;
        }

        args[nargs++] = arg;
        
        token_t post_arg_tok = lexer_peek(lexer); 
        if (post_arg_tok.type != TOKEN_COMMA) {
          break; 
        }
        lexer_lex(lexer); // consume ','
      }
      
      if (!_expect(lexer, TOKEN_RPAREN, ERROR_EXPECTED_RPAREN)) {
        for (size_t i = 0; i < nargs; i++) {
          syntax_expr_free(args[i]);
        }
        free(args);
        return NULL;
      }

      if (nargs < cap) {
        expr_t **temp_args = realloc(args, nargs * sizeof(expr_t*));
        if (temp_args == NULL) {
            die("Out of memory: can't resize args array for tuple");
        }
        args = temp_args;
      }

      expr_t *tuple = _alloc_expr();
      tuple->pos = tok.pos; 
      tuple->source = lexer_source(lexer);
      tuple->tag = EXPR_TUPLE;
      tuple->as.tuple.elements = args;
      tuple->as.tuple.nelements = nargs;
      return tuple;
    }
    case TOKEN_LBRACE: {
      lexer_lex(lexer); 
      
      expr_t *first_expr = _parse_expr(lexer, table);
      token_t next_tok = lexer_peek(lexer); 
      
      if (first_expr == NULL) {
        if (next_tok.type == TOKEN_RBRACE) {
            error_report(error(ERROR_EXPECTED_EXPRESSION, lexer_source(lexer), next_tok.pos, 1));
            
            lexer_lex(lexer); // Consume ')'
            return NULL;
        }
        return NULL; 
      }
    
      if (next_tok.type != TOKEN_COMMA) {
        // Single element parenthesized expression
        if (!_expect(lexer, TOKEN_RBRACE, ERROR_EXPECTED_RBRACE)) {
          syntax_expr_free(first_expr);
          return NULL;
        }
        return first_expr;
      }
    
      // Multi-element tuple
      lexer_lex(lexer); // consume the first ','
    
      size_t cap = 4;
      size_t nargs = 1; 
      expr_t **args = malloc(cap * sizeof(expr_t*));
      if (args == NULL)
        die("Out of memory: can't allocate args array for function group");
    
      args[0] = first_expr; 
    
      while (1) {
        token_t next_arg_tok = lexer_peek(lexer);
        expr_t *arg = _parse_expr(lexer, table);
        
        if (arg == NULL) {
          error_report(error(ERROR_EXPECTED_EXPRESSION, lexer_source(lexer), next_arg_tok.pos, 1));
          
          for (size_t i = 0; i < nargs; i++) {
            syntax_expr_free(args[i]);
          }
          free(args);
          return NULL;
        }
    
        if (nargs == cap) {
          cap *= 2;
          expr_t **temp_args = realloc(args, cap * sizeof(expr_t*));
          if (temp_args == NULL)
            die("Out of memory: can't enlarge args array for function group");
          args = temp_args;
        }
    
        args[nargs++] = arg;
        
        token_t post_arg_tok = lexer_peek(lexer); 
        if (post_arg_tok.type != TOKEN_COMMA) {
          break; 
        }
        lexer_lex(lexer); // consume ','
      }
      
      if (!_expect(lexer, TOKEN_RBRACE, ERROR_EXPECTED_RBRACE)) {
        for (size_t i = 0; i < nargs; i++) {
          syntax_expr_free(args[i]);
        }
        free(args);
        return NULL;
      }
    
      if (nargs < cap) {
        expr_t **temp_args = realloc(args, nargs * sizeof(expr_t*));
        if (temp_args == NULL) {
            die("Out of memory: can't resize args array for function group");
        }
        args = temp_args;
      }
    
      expr_t *tuple = _alloc_expr();
      tuple->pos = tok.pos; 
      tuple->source = lexer_source(lexer);
      tuple->tag = EXPR_GROUP;
      tuple->as.tuple.elements = args;
      tuple->as.tuple.nelements = nargs;
      return tuple;
    }
    case TOKEN_IDENT: {
      lexer_lex(lexer);
      intern_t name = intern_prefix(table,tok.start,tok.len);
      expr_t *it = _alloc_expr();
      it->pos = tok.pos;
      it->source = lexer_source(lexer);
      it->tag = EXPR_PAT_IDENT;
      it->as.ident = name;
      return it;       
    }
    case TOKEN_FLOAT_LIT: {
      lexer_lex(lexer);
      double value = strtod(tok.start, NULL);
      expr_t *lit = _alloc_expr();
      lit->pos = tok.pos;
      lit->source = lexer_source(lexer);
      lit->tag = EXPR_FLOAT_LIT;
      lit->as.float_lit = value;
      return lit;
    }
    case TOKEN_INT_LIT: {
      lexer_lex(lexer);
      long value = strtol(tok.start, NULL, 10);
      expr_t *lit = _alloc_expr();
      lit->pos = tok.pos;
      lit->source = lexer_source(lexer);
      lit->tag = EXPR_INT_LIT;
      lit->as.int_lit = value;
      return lit;
    }
    case TOKEN_CONSTRUCTOR: {
      lexer_lex(lexer);
      intern_t name = intern_prefix(table,tok.start,tok.len);
      expr_t *it = _alloc_expr();
      it->pos = tok.pos;
      it->source = lexer_source(lexer);
      it->tag = EXPR_CONSTRUCTOR;
      it->as.ident = name;
      return it;       
    }
    case TOKEN_STRING_LIT: {
      lexer_lex(lexer);
      char* contents = _parse_string_literal(tok.start);
      expr_t *lit = _alloc_expr();
      lit->pos = tok.pos;
      lit->source = lexer_source(lexer);
      lit->tag = EXPR_STRING_LIT;
      lit->as.string_lit = contents;
      return lit;
    }
    default: return NULL;
  }
}

static expr_t *_parse_call_expr(lexer_t *lexer, intern_table_t *table) {
  expr_t *lhs = _parse_atom(lexer, table);
  if (lhs == NULL) return NULL;

  // Loop to handle chained calls like f(a)(b)
  // If we see '(', we treat 'lhs' as the callee, parse arguments,
  // update 'lhs' to the new call node, and repeat.
  while (lexer_peek(lexer).type == TOKEN_LPAREN) {
    lexer_lex(lexer); // consume '('

    size_t cap = 4;
    size_t nargs = 0;
    expr_t **args = malloc(cap * sizeof(expr_t*));
    if (args == NULL) die("Out of memory: can't allocate args array");
    
    while (1) {
      pos_t arg_start_pos = lexer_cur_pos(lexer);
      // Use _parse_expr here to allow complex args like f(a + b)
      expr_t *arg = _parse_expr(lexer, table);
      
      if (arg == NULL) {
        error_report(error(ERROR_EXPECTED_EXPRESSION, lexer_source(lexer), arg_start_pos, 1));
        
        // Cleanup
        for (size_t i = 0; i < nargs; i++) {
          syntax_expr_free(args[i]);
        }
        free(args);
        syntax_expr_free(lhs);
        return NULL;
      }

      if (nargs == cap) {
        cap *= 2;
        args = realloc(args, cap * sizeof(expr_t*));
        if (args == NULL)
          die("Out of memory: can't enlarge args array");
      }

      args[nargs++] = arg;

      // If we see a comma, consume it and continue to next arg
      if (lexer_peek(lexer).type == TOKEN_COMMA) {
        lexer_lex(lexer);
        continue;
      }

      // If no comma, we expect the closing parenthesis
      break;
    }

    if (!_expect(lexer, TOKEN_RPAREN, ERROR_EXPECTED_RPAREN)) {
      // Cleanup
      for (size_t i = 0; i < nargs; i++) {
        syntax_expr_free(args[i]);
      }
      free(args);
      syntax_expr_free(lhs);
      return NULL;
    }
    // _expect consumes ')' on success

    // shrink array to exact size
    args = realloc(args, nargs * sizeof(expr_t*));
    if (args == NULL)
      die("Out of memory: can't resize args array");

    // build n-ary call node
    expr_t *call = _alloc_expr();
    call->pos = lhs->pos;
    call->source = lexer_source(lexer);
    call->tag = EXPR_CALL;
    call->as.call.callee = lhs;
    call->as.call.arguments = args;
    call->as.call.nargs = nargs;

    // The result of this call becomes the LHS for the next potential call in the chain
    lhs = call;
  }

  return lhs;
}

static expr_t *_parse_arith_plus(lexer_t *lexer, intern_table_t *table) {
  expr_t *lhs = _parse_call_expr(lexer, table);
  while (1) {
    token_t tok = lexer_peek(lexer);
    intern_t name = (tok.type == TOKEN_PLUS) ? intern(table, "+")
                  : (tok.type == TOKEN_MINUS) ? intern(table,"-")
                  : NULL;
    if (name == NULL) {
      return lhs;
    }
    lexer_lex(lexer);
    expr_t *rhs = _parse_call_expr(lexer, table);
    expr_t *it = _alloc_expr();
    it->pos = tok.pos;
    it->source = lexer_source(lexer);
    it->tag = EXPR_CALL;
    it->as.call.arguments = malloc(sizeof(expr_t*) * 2);
    if (it->as.call.arguments == NULL)
      die("Out of memory: cannot allocate args array");
    it->as.call.arguments[0] = lhs;
    it->as.call.arguments[1] = rhs;    
    it->as.call.nargs = 2;
    it->as.call.callee = _alloc_expr();
    it->as.call.callee->tag = EXPR_PAT_IDENT;
    it->as.call.callee->pos = tok.pos;
    it->as.call.callee->source = lexer_source(lexer);    
    it->as.call.callee->as.ident = name;
    lhs = it;
  }
}


static expr_t *_parse_arith(lexer_t *lexer, intern_table_t *table) {
  expr_t *lhs = _parse_arith_plus(lexer, table);
  while (1) {
    token_t tok = lexer_peek(lexer);
    intern_t name = (tok.type == TOKEN_MULT) ? intern(table, "*")
                  : (tok.type == TOKEN_DIV)  ? intern(table,"/")
                  : (tok.type == TOKEN_MOD)  ? intern(table,"mod")
                  : (tok.type == TOKEN_IDIV) ? intern(table,"div")
                  : NULL;
    if (name == NULL) {
      return lhs;
    }
    lexer_lex(lexer);
    expr_t *rhs = _parse_arith_plus(lexer, table);
    expr_t *it = _alloc_expr();
    it->tag = EXPR_CALL;
    it->pos = tok.pos;
    it->source = lexer_source(lexer);
    it->as.call.arguments = malloc(sizeof(expr_t*) * 2);
    if (it->as.call.arguments == NULL)
      die("Out of memory: cannot allocate args array");
    it->as.call.arguments[0] = lhs;
    it->as.call.arguments[1] = rhs;
    it->as.call.nargs = 2;    
    it->as.call.callee = _alloc_expr();
    it->as.call.callee->tag = EXPR_PAT_IDENT;
    it->as.call.callee->pos = tok.pos;
    it->as.call.callee->source = lexer_source(lexer);
    it->as.call.callee->as.ident = name;
    lhs = it;
  }
}


static expr_t *_parse_binop_comp(lexer_t *lexer, intern_table_t *table) {
  expr_t *lhs = _parse_arith(lexer, table);
  token_t tok = lexer_peek(lexer);
  intern_t name = (tok.type == TOKEN_EQ) ? intern(table, "=")
                : (tok.type == TOKEN_NOTEQ) ? intern(table,"/=")
                : (tok.type == TOKEN_GREATER) ? intern(table,">")
                : (tok.type == TOKEN_LESS) ? intern(table,"<")
                : (tok.type == TOKEN_LESSEQ) ? intern(table,"<=")
                : (tok.type == TOKEN_GREATEREQ) ? intern(table,">=")
                : NULL;
  if (name != NULL) {
    lexer_lex(lexer);
    expr_t *rhs = _parse_arith(lexer, table);
    expr_t *it = _alloc_expr();
    it->tag = EXPR_CALL;
    it->source = lexer_source(lexer);
    it->pos = tok.pos;
    it->as.call.arguments = malloc(sizeof(expr_t*) * 2);
    if (it->as.call.arguments == NULL)
      die("Out of memory: cannot allocate args array");
    it->as.call.arguments[0] = lhs;
    it->as.call.arguments[1] = rhs;
    it->as.call.nargs = 2;
    it->as.call.callee = _alloc_expr();
    it->as.call.callee->pos = tok.pos;
    it->as.call.callee->source = lexer_source(lexer);
    it->as.call.callee->tag = EXPR_PAT_IDENT;
    it->as.call.callee->as.ident = name;
    return it;
  }
  return lhs;
}

static expr_t *_parse_binop_and(lexer_t *lexer, intern_table_t *table) {
  expr_t *lhs = _parse_binop_comp(lexer, table);
  token_t tok = lexer_peek(lexer);  
  if (tok.type == TOKEN_AND) {
    lexer_lex(lexer);
    expr_t *rhs = _parse_binop_and(lexer, table);
    expr_t *it = _alloc_expr();
    it->source = lexer_source(lexer);
    it->pos = tok.pos;
    it->tag = EXPR_SEQ;
    it->as.seq.first = lhs;
    it->as.seq.then = rhs;    
    return it;
  }
  return lhs;
}
static expr_t *_parse_binop_or(lexer_t *lexer, intern_table_t *table) {
  expr_t *lhs = _parse_binop_and(lexer, table);
  token_t tok = lexer_peek(lexer);  
  if (tok.type == TOKEN_OR) {
    lexer_lex(lexer);
    expr_t *rhs = _parse_binop_or(lexer, table);
    expr_t *it = _alloc_expr();
    it->tag = EXPR_ALT;
    it->source = lexer_source(lexer);
    it->pos = tok.pos;
    it->as.alt.try = lhs;
    it->as.alt.orelse = rhs;    
    return it;
  }
  return lhs;
}
/*
static expr_t *_parse_binop_or(lexer_t *lexer, intern_table_t *table) {
  expr_t *lhs = _parse_binop_and(lexer, table);
  token_t tok = lexer_peek(lexer);
  intern_t or_name = intern(table, "or");  
  if (tok.type == TOKEN_OR) {
    lexer_lex(lexer);
    expr_t *rhs = _parse_binop_or(lexer, table);
    expr_t *it = _alloc_expr();
    it->tag = EXPR_CALL;
    it->as.call.arguments = malloc(sizeof(expr_t*) * 2);
    if (it->as.call.arguments == NULL)
      die("Out of memory: cannot allocate args array");
    it->as.call.arguments[0] = lhs;
    it->as.call.arguments[1] = rhs;
    it->as.call.callee = _alloc_expr();
    it->as.call.callee->tag = EXPR_PAT_IDENT;
    it->as.call.callee->as.ident = or_name;
    return it;
  }
  return lhs;
}
*/
static expr_t *_parse_sequence_expr(lexer_t *lexer, intern_table_t *table) {
  token_t tok = lexer_peek(lexer);
  if (tok.type == TOKEN_IF) {
    lexer_lex(lexer);
    expr_t *lhs = _parse_call_expr(lexer, table);
    if (lhs == NULL) {
      error_report(error(ERROR_EXPECTED_EXPRESSION, lexer_source(lexer), tok.pos, 1));
    }
    pos_t pos = lexer_cur_pos(lexer);
    expr_t *rhs = _parse_sequence_expr(lexer, table);    
    if (rhs == NULL) {
      syntax_expr_free(lhs);      
      error_report(error(ERROR_EXPECTED_EXPRESSION, lexer_source(lexer), pos, 1));
    }
    
    expr_t *sequence = _alloc_expr();
    sequence->tag = EXPR_SEQ;
    sequence->pos = lhs->pos; 
    sequence->source = lhs->source;
    sequence->as.seq.first = lhs; 
    sequence->as.seq.then = rhs; 
    return sequence;
  }
  expr_t *lhs = _parse_binop_or(lexer, table);
  if (lhs == NULL) return NULL;

  token_type next_token = lexer_peek(lexer).type;
    
  if (next_token == TOKEN_ASSIGN) { 
    expr_t *pattern = lhs;
    lhs = NULL; // Ownership transferred to 'pattern' variable
    lexer_lex(lexer); // consume :=
    pos_t value_pos = lexer_cur_pos(lexer);
    
    expr_t *value_expr = _parse_expr(lexer, table);
    if (value_expr == NULL) {
      error_report(error(ERROR_EXPECTED_EXPRESSION, lexer_source(lexer), value_pos, 1));
      syntax_expr_free(pattern);
      return NULL;
    }

    if (!_expect(lexer, TOKEN_SEMI, ERROR_EXPECTED_SEMI)) {
      syntax_expr_free(value_expr);
      syntax_expr_free(pattern);
      return NULL;
    }

    pos_t body_pos = lexer_cur_pos(lexer);
    expr_t *body_expr = _parse_sequence_expr(lexer, table);
    if (body_expr == NULL) {
      error_report(error(ERROR_EXPECTED_EXPRESSION, lexer_source(lexer), body_pos, 1));
      syntax_expr_free(value_expr);
      // Cleanup: Free the pattern node
      syntax_expr_free(pattern);
      return NULL;
    }

    expr_t *let_binding = _alloc_expr();
    let_binding->tag = EXPR_LET_BINDING;
    let_binding->pos = pattern->pos; 
    let_binding->source = pattern->source;
    let_binding->as.let_binding.pattern.expr = pattern; 
    let_binding->as.let_binding.pattern.bound_vars = (size_t)-1;
    let_binding->as.let_binding.expr = value_expr; 
    let_binding->as.let_binding.in = body_expr; 

    return let_binding;
  } 
    
    
  return lhs;
}

static expr_t *_parse_alt_expr(lexer_t *lexer, intern_table_t *table) {
  expr_t *lhs = _parse_sequence_expr(lexer, table);
  if (lhs == NULL) return NULL;

  if (lexer_peek(lexer).type == TOKEN_PIPE) { 
    lexer_lex(lexer); 

    pos_t rhs_pos = lexer_cur_pos(lexer);
    expr_t *rhs = _parse_alt_expr(lexer, table); 
    if (rhs == NULL) {
      error_report(error(ERROR_EXPECTED_EXPRESSION, lexer_source(lexer), rhs_pos, 1));
      syntax_expr_free(lhs);
      return NULL;
    }

    expr_t *disjunction = _alloc_expr();
    disjunction->tag = EXPR_ALT;
    disjunction->pos = lhs->pos;
    disjunction->source = lhs->source;
    disjunction->as.alt.try = lhs;
    disjunction->as.alt.orelse = rhs;
        
    return disjunction;
  }

  return lhs;
}

static expr_t *_parse_expr(lexer_t *lexer, intern_table_t *table) {
  expr_t *lhs = NULL;
  expr_t **params = NULL;
  size_t nparams = 0;
  
  lhs = _parse_alt_expr(lexer, table);
  if (lhs == NULL) return NULL;
  
  token_type next_token = lexer_peek(lexer).type;
  
  if (next_token == TOKEN_COLON) {
    lexer_lex(lexer); 
    if (lexer_peek(lexer).type == TOKEN_PIPE) {
      
      lexer_lex(lexer);
    }
    pos_t body_pos = lexer_cur_pos(lexer);
    
    if (lhs->tag == EXPR_TUPLE) { 
      nparams = lhs->as.tuple.nelements;
      params = lhs->as.tuple.elements;
      
      lhs->as.tuple.elements = NULL;
      lhs->as.tuple.nelements = 0; 

      syntax_expr_free(lhs);
      lhs = NULL; 

    } else {
      nparams = 1;
      params = malloc(sizeof(expr_t*));
      if (params == NULL) die("Out of memory: cannot allocate params");
      params[0] = lhs;
      lhs = NULL; 
    }

    expr_t *body = _parse_expr(lexer, table);
    if (body == NULL) {
      error_report(error(ERROR_EXPECTED_EXPRESSION, lexer_source(lexer), body_pos, 1));
      if (params != NULL) {
        for(size_t i=0; i<nparams; i++) syntax_expr_free(params[i]);
        free(params);
      }
      return NULL;
    }

    expr_t *lambda = _alloc_expr();
    lambda->tag = EXPR_LAMBDA;
    lambda->pos = params[0]->pos; 
    lambda->source = params[0]->source;
    lambda->as.lambda_raw.patterns = params;
    lambda->as.lambda_raw.npatterns = nparams;
    lambda->as.lambda_raw.body = body;
    return lambda;
  }
  
  return lhs;
}



static size_t _scope_check_pattern(expr_t *it, scope_t *scope) {
  switch (it->tag) {
    case EXPR_ALT:
    case EXPR_LAMBDA:
    case EXPR_LAMBDA_COMPILED:
    case EXPR_GROUP:
    case EXPR_SEQ:
    case EXPR_BUILTIN:
    case EXPR_LET_BINDING:
      error_report(error(ERROR_INVALID_PATTERN, it->source,it->pos,1));
      return (size_t)-1;
    case EXPR_VAR:
      die("Impossible happened: Found a var node when scope-checking.");
    case EXPR_TUPLE: {
      size_t i1 = 0;
      for (int i = 0; i < it->as.tuple.nelements; i++) {
        size_t i2 = _scope_check_pattern(it->as.tuple.elements[i],scope);  
        if (i2 == (size_t)-1) return i2;
        i1 += i2;
      }
      return i1;
    }
    case EXPR_CALL: {
      if (it->as.call.callee->tag != EXPR_CALL 
        && it->as.call.callee->tag != EXPR_CONSTRUCTOR) {
        error_report(error(ERROR_INVALID_PATTERN, it->source,it->pos,1));
        return (size_t)-1;
      }
      size_t i1 = _scope_check_pattern(it->as.call.callee, scope);
      if (i1 == (size_t)-1) return i1;
      for (int i = 0; i < it->as.call.nargs; i++) {
        size_t i2 = _scope_check_pattern(it->as.call.arguments[i],scope);  
        if (i2 == (size_t)-1) return i2;
        i1 += i2;
      }
      return i1;
    }
    case EXPR_STRING_LIT:
    case EXPR_INT_LIT:
    case EXPR_FLOAT_LIT:
    case EXPR_CONSTRUCTOR:
      return 0;
    case EXPR_PAT_IDENT: {
      scope_push(scope,it->as.ident);
      return 1;
    }
  }
}
static inline size_t max(size_t a, size_t b) {
    return (a > b) ? a : b;
}
static size_t _max_let_depth(expr_t *it) {
  switch (it->tag) {
    case EXPR_ALT:
    case EXPR_SEQ:
      return max(_max_let_depth(it->as.alt.try),_max_let_depth(it->as.alt.orelse));
    case EXPR_CALL: {
      size_t ret = _max_let_depth(it->as.call.callee);
      for (int i = 0; i < it->as.call.nargs;i++) {
        ret = max(ret,_max_let_depth(it->as.call.arguments[i]));
      }
      return ret;
    }
    case EXPR_LET_BINDING: {
      size_t expr = _max_let_depth(it->as.let_binding.expr);
      return max(expr,_max_let_depth(it->as.let_binding.in) + it->as.let_binding.pattern.bound_vars);
    }
    case EXPR_TUPLE: 
    case EXPR_GROUP: {
      size_t ret = 0;
      for (int i = 0; i < it->as.tuple.nelements;i++) {
        ret = max(ret,_max_let_depth(it->as.tuple.elements[i]));
      }
      return ret;
    }
    case EXPR_LAMBDA:
    case EXPR_LAMBDA_COMPILED:
    case EXPR_BUILTIN:
    case EXPR_INT_LIT:
    case EXPR_FLOAT_LIT:
    case EXPR_PAT_IDENT:
    case EXPR_STRING_LIT:
    case EXPR_VAR:
    case EXPR_CONSTRUCTOR:
      return 0;  
  }
}

size_t syntax_expr_required_locals(expr_t *it) {
  return _max_let_depth(it);
}

static char* INTERNAL_NAMES[]
  = {"0", "1", "2", "3", "4", "5", "6", "7", "8", "9", "10", "11", "12", 
     "13", "14", "15", "16", "17", "18", "19", "20", "21", "22", "23"};

static bool _scope_check_expr(expr_t *it, scope_t *scope, builtins_t *builtins, bitset_t *used) {
  
  //printf("SCOPE CHECK:");
  //scope_debug_dump(scope);
  //syntax_dump_expr(it);
  //printf("\n");
  switch (it->tag) {
    case EXPR_ALT:
    case EXPR_SEQ:
      return _scope_check_expr(it->as.alt.try, scope, builtins, used)
          && _scope_check_expr(it->as.alt.orelse, scope, builtins, used);
    case EXPR_LAMBDA: {
      size_t idx = 0;
      expr_t *body = it->as.lambda_raw.body;   
      size_t num_args = it->as.lambda_raw.npatterns;   
      for (int i = 0; i < it->as.lambda_raw.npatterns; i++) {
        if (it->as.lambda_raw.patterns[i]->tag == EXPR_PAT_IDENT) {
          scope_push(scope, it->as.lambda_raw.patterns[i]->as.ident);
        } else {
          expr_t *ident_expr = _alloc_expr();
          ident_expr->tag = EXPR_PAT_IDENT;
          ident_expr->pos = it->as.lambda_raw.patterns[i]->pos;
          ident_expr->source = it->as.lambda_raw.patterns[i]->source;
          ident_expr->as.ident = INTERNAL_NAMES[idx++];
          scope_push(scope, ident_expr->as.ident);
          expr_t *let_binding = _alloc_expr();          
          let_binding->tag = EXPR_LET_BINDING;
          let_binding->pos = it->as.lambda_raw.patterns[i]->pos; 
          let_binding->source = it->as.lambda_raw.patterns[i]->source;
          let_binding->as.let_binding.pattern.expr = it->as.lambda_raw.patterns[i]; 
          let_binding->as.let_binding.pattern.bound_vars = (size_t)-1;
          let_binding->as.let_binding.expr = ident_expr; 
          let_binding->as.let_binding.in = body; 
          body = let_binding;
        }
      }
      it->tag = EXPR_LAMBDA_COMPILED;
      it->as.lambda.body = body;
      it->as.lambda.args = num_args;
      
      bitset_t *lambda_mask = bitset_alloc();
      bool ret = _scope_check_expr(it->as.lambda.body,scope, builtins, lambda_mask);
      bitset_shift_down(lambda_mask,num_args);
      it->as.lambda.mask = lambda_mask;
      bitset_union(used, lambda_mask);
      it->as.lambda.num_lets = _max_let_depth(it->as.lambda.body);
      scope_pop(scope,num_args);
      return ret;
    }
    case EXPR_LET_BINDING: {
      if (!_scope_check_expr(it->as.let_binding.expr,scope,builtins, used))
        return false;
      size_t amount = _scope_check_pattern(it->as.let_binding.pattern.expr,scope);
      if (amount == (size_t)-1)
        return false;
      it->as.let_binding.pattern.bound_vars = amount;
      bitset_shift_up(used, amount);
      bool ret = _scope_check_expr(it->as.let_binding.in,scope,builtins, used);
      bitset_shift_down(used, amount);
      scope_pop(scope,amount);
      return ret;
    } 
    case EXPR_CALL:
      if (_scope_check_expr(it->as.call.callee, scope,builtins, used)) {
        for (int i = 0; i < it->as.call.nargs; i++) {
          if (!_scope_check_expr(it->as.call.arguments[i], scope,builtins,  used))
            return false;
        }
        return true;
      } else return false;
    case EXPR_STRING_LIT:
    case EXPR_INT_LIT:
    case EXPR_FLOAT_LIT:
    case EXPR_CONSTRUCTOR:
      return true;
    case EXPR_TUPLE:
      // TODO
    case EXPR_GROUP:
      for (int i = 0; i < it->as.group.nclauses; i++) {
        if (!_scope_check_expr(it->as.group.clauses[i], scope,builtins,  used))
          return false;
      }
      return true;
      
    case EXPR_LAMBDA_COMPILED:
    case EXPR_VAR:
    case EXPR_BUILTIN:
      die("Impossible happened: Found a compiled node when scope-checking.");
    case EXPR_PAT_IDENT: {
      de_bruijn_t idx = scope_lookup(scope, it->as.ident);
      if (idx == (de_bruijn_t)-1) {
        builtin_func_t *ptr = builtins_lookup(builtins, it->as.ident);
        if (ptr != NULL) {
          it->tag = EXPR_BUILTIN;
          it->as.builtin = ptr;
          return true;
        } else {
          //printf("FOO: %s\n", it->as.ident);
          error_report(error(ERROR_UNKNOWN_VARIABLE, it->source, it->pos, strlen(it->as.ident)));
          return false;
        }
      }
      it->tag = EXPR_VAR;
      it->as.var = idx;
      bitset_set(used,idx);
      return true;
    }
  }
}

expr_t *syntax_parse_expr(lexer_t *lexer, builtins_t *builtins, intern_table_t *table) {
  expr_t *it = _parse_expr(lexer, table);
  if (it == NULL) return NULL;
  bitset_t *used = bitset_alloc();
  scope_t *scope = scope_alloc();
  syntax_dump_expr(it);
  _scope_check_expr(it, scope, builtins, used);
  return it;
}
void syntax_expr_free(expr_t *it) {
  switch (it->tag) {
    case EXPR_ALT:
    case EXPR_SEQ:
      syntax_expr_free(it->as.alt.try);
      syntax_expr_free(it->as.alt.orelse);
      break;
    case EXPR_LAMBDA:
      for (int i = 0; i < it->as.lambda_raw.npatterns;i++) {
        syntax_expr_free(it->as.lambda_raw.patterns[i]);  
      }
      free(it->as.lambda_raw.patterns);
      syntax_expr_free(it->as.lambda_raw.body);
      break;
    case EXPR_LAMBDA_COMPILED:
      syntax_expr_free(it->as.lambda.body);
      if (it->as.lambda.mask != NULL) bitset_free(it->as.lambda.mask);
      break;
    
    case EXPR_LET_BINDING:
      syntax_expr_free(it->as.let_binding.expr);
      syntax_expr_free(it->as.let_binding.in);
      syntax_expr_free(it->as.let_binding.pattern.expr);
      break;
    
    case EXPR_TUPLE:
      for (int i = 0; i < it->as.tuple.nelements;i++) {
        syntax_expr_free(it->as.tuple.elements[i]);
      }
      free(it->as.tuple.elements);
      break;
    case EXPR_GROUP:
      for (int i = 0; i < it->as.group.nclauses;i++) {
        syntax_expr_free(it->as.group.clauses[i]);
      }
      free(it->as.group.clauses);
      break;
    case EXPR_CALL:
      syntax_expr_free(it->as.call.callee);
      for (int i = 0; i < it->as.call.nargs;i++) {
        syntax_expr_free(it->as.call.arguments[i]);
      }
      free(it->as.call.arguments);
      break;
    case EXPR_STRING_LIT:
      free(it->as.string_lit);
      break;
    default: break;
  }
  free(it);
}


void syntax_dump_expr(expr_t *it) {  
  switch (it->tag) {
    case EXPR_ALT:
      printf("alt(");
      goto bits;
    case EXPR_SEQ:
      printf("seq(");
      bits:
      syntax_dump_expr(it->as.alt.try);
      printf(",");
      syntax_dump_expr(it->as.alt.orelse);
      printf(")");
      break;
    case EXPR_LAMBDA:
      printf("lambda(");
      for (int i = 0; i < it->as.lambda_raw.npatterns;i++) {
        syntax_dump_expr(it->as.lambda_raw.patterns[i]);
        printf(": ");
      }
      syntax_dump_expr(it->as.lambda_raw.body);
      printf(")");
      break;
    case EXPR_LET_BINDING:
      printf("let(");
      syntax_dump_expr(it->as.let_binding.pattern.expr);
      printf(":=");
      syntax_dump_expr(it->as.let_binding.expr);
      printf(";");
      syntax_dump_expr(it->as.let_binding.in);
      printf(")");
      break;
    case EXPR_CALL:
      syntax_dump_expr(it->as.call.callee);
      printf("(");
      for (int i = 0; i < it->as.call.nargs;i++) {        
        syntax_dump_expr(it->as.call.arguments[i]);
        printf(",");
      }
      printf(")");
      break;
    case EXPR_TUPLE:
      printf("(");
      for (int i = 0; i < it->as.tuple.nelements;i++) {        
        syntax_dump_expr(it->as.tuple.elements[i]);
        printf(",");
      }
      printf(")");
      break;
    case EXPR_BUILTIN:
      printf("<builtin%p>",it->as.builtin);
      break;
    case EXPR_LAMBDA_COMPILED:
      printf("lambda_c(%zu,",it->as.lambda.args);
      syntax_dump_expr(it->as.lambda.body);
      printf(")");
      break;
    case EXPR_GROUP:
      printf("{");
      for (int i = 0; i < it->as.group.nclauses;i++) {        
        syntax_dump_expr(it->as.group.clauses[i]);
        printf(",");
      }
      printf("}");
      break;
    case EXPR_STRING_LIT:
      printf("\"%s\"",it->as.string_lit);
      break;
    case EXPR_INT_LIT:
      printf("%ld", it->as.int_lit);
      break;
    case EXPR_FLOAT_LIT:
      printf("%f", it->as.float_lit);
      break;
    case EXPR_PAT_IDENT:
      printf("%s", it->as.ident);
      break;
    case EXPR_VAR:
      printf("\\%zu", it->as.var);
      break;
    case EXPR_CONSTRUCTOR:
      printf("<%s>", it->as.constructor);
      break;
    default: break;
  }
}