<commit_before>// Copyright 2012 <NAME> <<EMAIL>>
// This program is free software licensed under the MIT license.

/*
 * Recursive descendent parser for C.
 */

#include <assert.h>
#include <ctype.h>
#include <limits.h>
#include <stdlib.h>
#include <string.h>
#include <strings.h>
#include "8cc.h"

// The largest alignment requirement on x86-64. When we are allocating memory
// for an array whose type is unknown, the array will be aligned to this
// boundary.
#define MAX_ALIGN 16

#define MAX(a, b) ((a) > (b) ? (a) : (b))
#define MIN(a, b) ((a) < (b) ? (a) : (b))

// The last source location we want to point to when we find an error in the
// soruce code.
SourceLoc *source_loc;

// Objects representing various scopes. Did you know C has so many different
// scopes? You can use the same name for global variable, local variable, struct
// tag, union tag, and goto label!
static Map *globalenv = &EMPTY_MAP;
static Map *localenv;
static Map *struct_defs = &EMPTY_MAP;
static Map *union_defs = &EMPTY_MAP;
static Map *labels;

static Vector *toplevels;
static Vector *localvars;
static Vector *gotos;
static Type *current_func_type;

// Objects representing basic types. All variables will be of one of these types
// or a derived type from one of them. Note that (typename){initializer} is C99
// feature to write a literal struct.
Type *type_void = &(Type){ KIND_VOID, 0, 0, false };
Type *type_bool = &(Type){ KIND_BOOL, 1, 1, true };
Type *type_char = &(Type){ KIND_CHAR, 1, 1, false };
Type *type_short = &(Type){ KIND_SHORT, 2, 2, false };
Type *type_int = &(Type){ KIND_INT, 4, 4, false };
Type *type_long = &(Type){ KIND_LONG, 8, 8, false };
Type *type_float = &(Type){ KIND_FLOAT, 4, 4, false };
Type *type_double = &(Type){ KIND_DOUBLE, 8, 8, false };
Type *type_ldouble = &(Type){ KIND_LDOUBLE, 8, 8, false };
static Type *type_uint = &(Type){ KIND_INT, 4, 4, true };
static Type *type_ulong = &(Type){ KIND_LONG, 8, 8, true };
static Type *type_llong = &(Type){ KIND_LLONG, 8, 8, false };
static Type *type_ullong = &(Type){ KIND_LLONG, 8, 8, true };

static Type* make_ptr_type(Type *ty);
static Type* make_array_type(Type *ty, int size);
static Node *read_compound_stmt(void);
static void read_decl_or_stmt(Vector *list);
static Node *conv(Node *node);
static Node *read_stmt(void);
static bool is_type_keyword(Token *tok);
static Node *read_unary_expr(void);
static Type *read_func_param(char **name, bool optional);
static void read_decl(Vector *toplevel, bool isglobal);
static Type *read_declarator(char **name, Type *basetype, Vector *params, int ctx);
static Type *read_decl_spec(int *sclass);
static Node *read_struct_field(Node *struc);
static void read_initializer_list(Vector *inits, Type *ty, int off, bool designated);
static Type *read_cast_type(void);
static Vector *read_decl_init(Type *ty);
static Node *read_boolean_expr(void);
static Node *read_expr_opt(void);
static Node *read_conditional_expr(void);
static Node *read_assignment_expr(void);
static Node *read_cast_expr(void);
static Node *read_comma_expr(void);

enum {
    S_TYPEDEF = 1,
    S_EXTERN,
    S_STATIC,
    S_AUTO,
    S_REGISTER,
};

enum {
    DECL_BODY = 1,
    DECL_PARAM,
    DECL_PARAM_TYPEONLY,
    DECL_CAST,
};

/*
 * Source location
 */

static void mark_location(void) {
    Token *tok = peek_token();
    if (!tok) {
        source_loc = NULL;
        return;
    }
    source_loc = malloc(sizeof(SourceLoc));
    source_loc->file = tok->file;
    source_loc->line = tok->line;
}

/*
 * Constructors
 */

char *make_label(void) {
    static int c = 0;
    return format(".L%d", c++);
}

static char *make_static_label(char *name) {
    static int c = 0;
    return format(".S%d.%s", c++, name);
}

static Map *env(void) {
    return localenv ? localenv : globalenv;
}

static Node *make_ast(Node *tmpl) {
    Node *r = malloc(sizeof(Node));
    *r = *tmpl;
    r->sourceLoc = source_loc;
    return r;
}

static Node *ast_uop(int kind, Type *ty, Node *operand) {
    return make_ast(&(Node){ kind, ty, .operand = operand });
}

static Node *ast_binop(Type *ty, int kind, Node *left, Node *right) {
    Node *r = make_ast(&(Node){ kind, ty });
    r->left = left;
    r->right = right;
    return r;
}

static Node *ast_inttype(Type *ty, long val) {
    return make_ast(&(Node){ AST_LITERAL, ty, .ival = val });
}

static Node *ast_floattype(Type *ty, double val) {
    return make_ast(&(Node){ AST_LITERAL, ty, .fval = val });
}

static Node *ast_lvar(Type *ty, char *name) {
    Node *r = make_ast(&(Node){ AST_LVAR, ty, .varname = name });
    if (localenv)
        map_put(localenv, name, r);
    if (localvars)
        vec_push(localvars, r);
    return r;
}

static Node *ast_gvar(Type *ty, char *name) {
    Node *r = make_ast(&(Node){ AST_GVAR, ty, .varname = name, .glabel = name });
    map_put(globalenv, name, r);
    return r;
}

static Node *ast_static_lvar(Type *ty, char *name) {
    Node *r = make_ast(&(Node){
        .kind = AST_GVAR,
        .ty = ty,
        .varname = name,
        .glabel = make_static_label(name) });
    assert(localenv);
    map_put(localenv, name, r);
    return r;
}

static Node *ast_typedef(Type *ty, char *name) {
    Node *r = make_ast(&(Node){ AST_TYPEDEF, ty, .typedefname = name });
    map_put(env(), name, r);
    return r;
}

static Node *ast_string(char *str) {
    return make_ast(&(Node){
        .kind = AST_STRING,
        .ty = make_array_type(type_char, strlen(str) + 1),
        .sval = str });
}

static Node *ast_funcall(Type *ftype, char *fname, Vector *args) {
    return make_ast(&(Node){
        .kind = AST_FUNCALL,
        .ty = ftype->rettype,
        .fname = fname,
        .args = args,
        .ftype = ftype });
}

static Node *ast_funcdesg(char *fname, Node *func) {
    return make_ast(&(Node){
        .kind = AST_FUNCDESG,
        .ty = type_void,
        .fname = fname,
        .fptr = func });
}

static Node *ast_funcptr_call(Node *fptr, Vector *args) {
    assert(fptr->ty->kind == KIND_PTR);
    assert(fptr->ty->ptr->kind == KIND_FUNC);
    return make_ast(&(Node){
        .kind = AST_FUNCPTR_CALL,
        .ty = fptr->ty->ptr->rettype,
        .fptr = fptr,
        .args = args });
}

static Node *ast_func(Type *ty, char *fname, Vector *params, Node *body, Vector *localvars) {
    return make_ast(&(Node){
        .kind = AST_FUNC,
        .ty = ty,
        .fname = fname,
        .params = params,
        .localvars = localvars,
        .body = body});
}

static Node *ast_decl(Node *var, Vector *init) {
    return make_ast(&(Node){ AST_DECL, .declvar = var, .declinit = init });
}

static Node *ast_init(Node *val, Type *totype, int off) {
    return make_ast(&(Node){ AST_INIT, .initval = val, .initoff = off, .totype = totype });
}

static Node *ast_conv(Type *totype, Node *val) {
    return make_ast(&(Node){ AST_CONV, totype, .operand = val });
}

static Node *ast_if(Node *cond, Node *then, Node *els) {
    return make_ast(&(Node){ AST_IF, .cond = cond, .then = then, .els = els });
}

static Node *ast_ternary(Type *ty, Node *cond, Node *then, Node *els) {
    return make_ast(&(Node){ AST_TERNARY, ty, .cond = cond, .then = then, .els = els });
}

static Node *ast_for(Node *init, Node *cond, Node *step, Node *body) {
    return make_ast(&(Node){
            AST_FOR, .forinit = init, .forcond = cond, .forstep = step, .forbody = body });
}

static Node *ast_while(Node *cond, Node *body) {
    return make_ast(&(Node){ AST_WHILE, .forcond = cond, .forbody = body });
}

static Node *ast_do(Node *cond, Node *body) {
    return make_ast(&(Node){ AST_DO, .forcond = cond, .forbody = body });
}

static Node *ast_switch(Node *expr, Node *body) {
    return make_ast(&(Node){ AST_SWITCH, .switchexpr = expr, .switchbody = body });
}

static Node *ast_case(int begin, int end) {
    return make_ast(&(Node){ AST_CASE, .casebeg = begin, .caseend = end });
}

static Node *ast_return(Node *retval) {
    return make_ast(&(Node){ AST_RETURN, .retval = retval });
}

static Node *ast_compound_stmt(Vector *stmts) {
    return make_ast(&(Node){ AST_COMPOUND_STMT, .stmts = stmts });
}

static Node *ast_struct_ref(Type *ty, Node *struc, char *name) {
    return make_ast(&(Node){ AST_STRUCT_REF, ty, .struc = struc, .field = name });
}

static Node *ast_goto(char *label) {
    return make_ast(&(Node){ AST_GOTO, .label = label });
}

static Node *ast_computed_goto(Node *expr) {
    return make_ast(&(Node){ AST_COMPUTED_GOTO, .operand = expr });
}

static Node *ast_label(char *label) {
    return make_ast(&(Node){ AST_LABEL, .label = label });
}

static Node *ast_va_start(Node *ap) {
    return make_ast(&(Node){ AST_VA_START, type_void, .ap = ap });
}

static Node *ast_va_arg(Type *ty, Node *ap) {
    return make_ast(&(Node){ AST_VA_ARG, ty, .ap = ap });
}

static Node *ast_label_addr(char *label) {
    return make_ast(&(Node){ OP_LABEL_ADDR, make_ptr_type(type_void), .label = label });
}

static Type *make_type(Type *tmpl) {
    Type *r = malloc(sizeof(Type));
    *r = *tmpl;
    return r;
}

static Type *copy_type(Type *ty) {
    Type *r = malloc(sizeof(Type));
    memcpy(r, ty, sizeof(Type));
    return r;
}

static Type *make_numtype(int kind, bool usig) {
    Type *r = malloc(sizeof(Type));
    r->kind = kind;
    r->usig = usig;
    if (kind == KIND_VOID)         r->size = r->align = 0;
    else if (kind == KIND_BOOL)    r->size = r->align = 1;
    else if (kind == KIND_CHAR)    r->size = r->align = 1;
    else if (kind == KIND_SHORT)   r->size = r->align = 2;
    else if (kind == KIND_INT)     r->size = r->align = 4;
    else if (kind == KIND_LONG)    r->size = r->align = 8;
    else if (kind == KIND_LLONG)   r->size = r->align = 8;
    else if (kind == KIND_FLOAT)   r->size = r->align = 4;
    else if (kind == KIND_DOUBLE)  r->size = r->align = 8;
    else if (kind == KIND_LDOUBLE) r->size = r->align = 8;
    else error("internal error");
    return r;
}

static Type* make_ptr_type(Type *ty) {
    return make_type(&(Type){ KIND_PTR, .ptr = ty, .size = 8, .align = 8 });
}

static Type* make_array_type(Type *ty, int len) {
    int size;
    if (len < 0)
        size = -1;
    else
        size = ty->size * len;
    return make_type(&(Type){
        KIND_ARRAY,
        .ptr = ty,
        .size = size,
        .len = len,
        .align = ty->align });
}

static Type* make_rectype(bool is_struct) {
    return make_type(&(Type){ KIND_STRUCT, .is_struct = is_struct });
}

static Type* make_func_type(Type *rettype, Vector *paramtypes, bool has_varargs, bool oldstyle) {
    return make_type(&(Type){
        KIND_FUNC,
        .rettype = rettype,
        .params = paramtypes,
        .hasva = has_varargs,
        .oldstyle = oldstyle });
}

static Type *make_stub_type(void) {
    return make_type(&(Type){ KIND_STUB });
}

/*
 * Predicates and kind checking routines
 */

bool is_inttype(Type *ty) {
    switch (ty->kind) {
    case KIND_BOOL: case KIND_CHAR: case KIND_SHORT: case KIND_INT:
    case KIND_LONG: case KIND_LLONG:
        return true;
    default:
        return false;
    }
}

bool is_flotype(Type *ty) {
    switch (ty->kind) {
    case KIND_FLOAT: case KIND_DOUBLE: case KIND_LDOUBLE:
        return true;
    default:
        return false;
    }
}

static bool is_arithtype(Type *ty) {
    return is_inttype(ty) || is_flotype(ty);
}

static bool is_string(Type *ty) {
    return ty->kind == KIND_ARRAY && ty->ptr->kind == KIND_CHAR;
}

static void ensure_lvalue(Node *node) {
    switch (node->kind) {
    case AST_LVAR: case AST_GVAR: case AST_DEREF: case AST_STRUCT_REF:
        return;
    default:
        error("lvalue expected, but got %s", a2s(node));
    }
}

static void ensure_inttype(Node *node) {
    if (!is_inttype(node->ty))
        error("integer kind expected, but got %s", a2s(node));
}

static void ensure_arithtype(Node *node) {
    if (!is_arithtype(node->ty))
        error("arithmetic kind expected, but got %s", a2s(node));
}

static void ensure_not_void(Type *ty) {
    if (ty->kind == KIND_VOID)
        error("void is not allowed");
}

static void expect(char id) {
    Token *tok = read_token();
    if (!is_keyword(tok, id))
        error("'%c' expected, but got %s", id, t2s(tok));
}

static Type *copy_incomplete_type(Type *ty) {
    if (!ty) return NULL;
    return (ty->len == -1) ? copy_type(ty) : ty;
}

static Type *get_typedef(char *name) {
    Node *node = map_get(env(), name);
    return (node && node->kind == AST_TYPEDEF) ? node->ty : NULL;
}

static bool is_type_keyword(Token *tok) {
    if (tok->kind == TIDENT)
        return get_typedef(tok->sval);
    if (tok->kind != TKEYWORD)
        return false;
    switch (tok->id) {
#define op(x, y)
#define keyword(id, _, istype) case id: return istype;
#include "keyword.h"
#undef keyword
#undef op
    default:
        return false;
    }
}

static bool next_token(int kind) {
    Token *tok = read_token();
    if (is_keyword(tok, kind))
        return true;
    unget_token(tok);
    return false;
}

void *make_pair(void *first, void *second) {
    Pair *r = malloc(sizeof(Pair));
    r->first = first;
    r->second = second;
    return r;
}

/*
 * Type conversion
 */

static Node *conv(Node *node) {
    if (!node)
        return NULL;
    // C11 6.3.2.1p4: A function designator is converted to a pointer to the function.
    if (node->kind == AST_FUNCDESG)
        return ast_uop(AST_ADDR, make_ptr_type(node->fptr->ty), node->fptr);
    // C11 6.3.2.1p3: An array of T is converted to a pointer to T.
    Type *ty = node->ty;
    if (ty->kind == KIND_ARRAY)
        return ast_uop(AST_CONV, make_ptr_type(ty->ptr), node);
    // C11 6.3.1.1p2: The integer promotions
    switch (ty->kind) {
    case KIND_SHORT: case KIND_CHAR: case KIND_BOOL:
        return ast_conv(type_int, node);
    case KIND_INT:
        if (ty->bitsize > 0)
            return ast_conv(type_int, node);
    }
    return node;
}

static bool same_arith_type(Type *t, Type *u) {
    return t->kind == u->kind && t->usig == u->usig;
}

// C11 6.3.1.8: Usual arithmetic conversions
static Type *usual_arith_conv(Type *t, Type *u) {
    assert(is_arithtype(t));
    assert(is_arithtype(u));
    if (t->kind < u->kind) {
        // Make t the larger type
        Type *tmp = t;
        t = u;
        u = tmp;
    }
    if (is_flotype(t))
        return t;
    assert(is_inttype(t) && t->size >= type_int->size);
    assert(is_inttype(u) && u->size >= type_int->size);
    if (t->size > u->size)
        return t;
    assert(t->size == u->size);
    if (t->usig == u->usig)
        return t;
    Type *r = copy_type(t);
    r->usig = true;
    return r;
}

static Node *binop(int op, Node *lhs, Node *rhs) {
    if (!is_arithtype(lhs->ty) || !is_arithtype(rhs->ty)) {
        Type *t = (lhs->ty->kind == KIND_ARRAY)
            ? make_ptr_type(lhs->ty->ptr) : lhs->ty;
        return ast_binop(t, op, lhs, rhs);
    }
    Type *r = usual_arith_conv(lhs->ty, rhs->ty);
    if (!same_arith_type(lhs->ty, r))
        lhs = ast_uop(AST_CONV, r, lhs);
    if (!same_arith_type(rhs->ty, r))
        rhs = ast_uop(AST_CONV, r, rhs);
    return ast_binop(r, op, lhs, rhs);
}

static bool is_same_struct(Type *a, Type *b) {
    if (a->kind != b->kind)
        return false;
    switch (a->kind) {
    case KIND_ARRAY:
        return a->len == b->len &&
            is_same_struct(a->ptr, b->ptr);
    case KIND_PTR:
        return is_same_struct(a->ptr, b->ptr);
    case KIND_STRUCT: {<commit_msg>Don't do array to pointer conversion in binop().<commit_after>// Copyright 2012 <NAME> <<EMAIL>>
// This program is free software licensed under the MIT license.

/*
 * Recursive descendent parser for C.
 */

#include <assert.h>
#include <ctype.h>
#include <limits.h>
#include <stdlib.h>
#include <string.h>
#include <strings.h>
#include "8cc.h"

// The largest alignment requirement on x86-64. When we are allocating memory
// for an array whose type is unknown, the array will be aligned to this
// boundary.
#define MAX_ALIGN 16

#define MAX(a, b) ((a) > (b) ? (a) : (b))
#define MIN(a, b) ((a) < (b) ? (a) : (b))

// The last source location we want to point to when we find an error in the
// soruce code.
SourceLoc *source_loc;

// Objects representing various scopes. Did you know C has so many different
// scopes? You can use the same name for global variable, local variable, struct
// tag, union tag, and goto label!
static Map *globalenv = &EMPTY_MAP;
static Map *localenv;
static Map *struct_defs = &EMPTY_MAP;
static Map *union_defs = &EMPTY_MAP;
static Map *labels;

static Vector *toplevels;
static Vector *localvars;
static Vector *gotos;
static Type *current_func_type;

// Objects representing basic types. All variables will be of one of these types
// or a derived type from one of them. Note that (typename){initializer} is C99
// feature to write a literal struct.
Type *type_void = &(Type){ KIND_VOID, 0, 0, false };
Type *type_bool = &(Type){ KIND_BOOL, 1, 1, true };
Type *type_char = &(Type){ KIND_CHAR, 1, 1, false };
Type *type_short = &(Type){ KIND_SHORT, 2, 2, false };
Type *type_int = &(Type){ KIND_INT, 4, 4, false };
Type *type_long = &(Type){ KIND_LONG, 8, 8, false };
Type *type_float = &(Type){ KIND_FLOAT, 4, 4, false };
Type *type_double = &(Type){ KIND_DOUBLE, 8, 8, false };
Type *type_ldouble = &(Type){ KIND_LDOUBLE, 8, 8, false };
static Type *type_uint = &(Type){ KIND_INT, 4, 4, true };
static Type *type_ulong = &(Type){ KIND_LONG, 8, 8, true };
static Type *type_llong = &(Type){ KIND_LLONG, 8, 8, false };
static Type *type_ullong = &(Type){ KIND_LLONG, 8, 8, true };

static Type* make_ptr_type(Type *ty);
static Type* make_array_type(Type *ty, int size);
static Node *read_compound_stmt(void);
static void read_decl_or_stmt(Vector *list);
static Node *conv(Node *node);
static Node *read_stmt(void);
static bool is_type_keyword(Token *tok);
static Node *read_unary_expr(void);
static Type *read_func_param(char **name, bool optional);
static void read_decl(Vector *toplevel, bool isglobal);
static Type *read_declarator(char **name, Type *basetype, Vector *params, int ctx);
static Type *read_decl_spec(int *sclass);
static Node *read_struct_field(Node *struc);
static void read_initializer_list(Vector *inits, Type *ty, int off, bool designated);
static Type *read_cast_type(void);
static Vector *read_decl_init(Type *ty);
static Node *read_boolean_expr(void);
static Node *read_expr_opt(void);
static Node *read_conditional_expr(void);
static Node *read_assignment_expr(void);
static Node *read_cast_expr(void);
static Node *read_comma_expr(void);

enum {
    S_TYPEDEF = 1,
    S_EXTERN,
    S_STATIC,
    S_AUTO,
    S_REGISTER,
};

enum {
    DECL_BODY = 1,
    DECL_PARAM,
    DECL_PARAM_TYPEONLY,
    DECL_CAST,
};

/*
 * Source location
 */

static void mark_location(void) {
    Token *tok = peek_token();
    if (!tok) {
        source_loc = NULL;
        return;
    }
    source_loc = malloc(sizeof(SourceLoc));
    source_loc->file = tok->file;
    source_loc->line = tok->line;
}

/*
 * Constructors
 */

char *make_label(void) {
    static int c = 0;
    return format(".L%d", c++);
}

static char *make_static_label(char *name) {
    static int c = 0;
    return format(".S%d.%s", c++, name);
}

static Map *env(void) {
    return localenv ? localenv : globalenv;
}

static Node *make_ast(Node *tmpl) {
    Node *r = malloc(sizeof(Node));
    *r = *tmpl;
    r->sourceLoc = source_loc;
    return r;
}

static Node *ast_uop(int kind, Type *ty, Node *operand) {
    return make_ast(&(Node){ kind, ty, .operand = operand });
}

static Node *ast_binop(Type *ty, int kind, Node *left, Node *right) {
    Node *r = make_ast(&(Node){ kind, ty });
    r->left = left;
    r->right = right;
    return r;
}

static Node *ast_inttype(Type *ty, long val) {
    return make_ast(&(Node){ AST_LITERAL, ty, .ival = val });
}

static Node *ast_floattype(Type *ty, double val) {
    return make_ast(&(Node){ AST_LITERAL, ty, .fval = val });
}

static Node *ast_lvar(Type *ty, char *name) {
    Node *r = make_ast(&(Node){ AST_LVAR, ty, .varname = name });
    if (localenv)
        map_put(localenv, name, r);
    if (localvars)
        vec_push(localvars, r);
    return r;
}

static Node *ast_gvar(Type *ty, char *name) {
    Node *r = make_ast(&(Node){ AST_GVAR, ty, .varname = name, .glabel = name });
    map_put(globalenv, name, r);
    return r;
}

static Node *ast_static_lvar(Type *ty, char *name) {
    Node *r = make_ast(&(Node){
        .kind = AST_GVAR,
        .ty = ty,
        .varname = name,
        .glabel = make_static_label(name) });
    assert(localenv);
    map_put(localenv, name, r);
    return r;
}

static Node *ast_typedef(Type *ty, char *name) {
    Node *r = make_ast(&(Node){ AST_TYPEDEF, ty, .typedefname = name });
    map_put(env(), name, r);
    return r;
}

static Node *ast_string(char *str) {
    return make_ast(&(Node){
        .kind = AST_STRING,
        .ty = make_array_type(type_char, strlen(str) + 1),
        .sval = str });
}

static Node *ast_funcall(Type *ftype, char *fname, Vector *args) {
    return make_ast(&(Node){
        .kind = AST_FUNCALL,
        .ty = ftype->rettype,
        .fname = fname,
        .args = args,
        .ftype = ftype });
}

static Node *ast_funcdesg(char *fname, Node *func) {
    return make_ast(&(Node){
        .kind = AST_FUNCDESG,
        .ty = type_void,
        .fname = fname,
        .fptr = func });
}

static Node *ast_funcptr_call(Node *fptr, Vector *args) {
    assert(fptr->ty->kind == KIND_PTR);
    assert(fptr->ty->ptr->kind == KIND_FUNC);
    return make_ast(&(Node){
        .kind = AST_FUNCPTR_CALL,
        .ty = fptr->ty->ptr->rettype,
        .fptr = fptr,
        .args = args });
}

static Node *ast_func(Type *ty, char *fname, Vector *params, Node *body, Vector *localvars) {
    return make_ast(&(Node){
        .kind = AST_FUNC,
        .ty = ty,
        .fname = fname,
        .params = params,
        .localvars = localvars,
        .body = body});
}

static Node *ast_decl(Node *var, Vector *init) {
    return make_ast(&(Node){ AST_DECL, .declvar = var, .declinit = init });
}

static Node *ast_init(Node *val, Type *totype, int off) {
    return make_ast(&(Node){ AST_INIT, .initval = val, .initoff = off, .totype = totype });
}

static Node *ast_conv(Type *totype, Node *val) {
    return make_ast(&(Node){ AST_CONV, totype, .operand = val });
}

static Node *ast_if(Node *cond, Node *then, Node *els) {
    return make_ast(&(Node){ AST_IF, .cond = cond, .then = then, .els = els });
}

static Node *ast_ternary(Type *ty, Node *cond, Node *then, Node *els) {
    return make_ast(&(Node){ AST_TERNARY, ty, .cond = cond, .then = then, .els = els });
}

static Node *ast_for(Node *init, Node *cond, Node *step, Node *body) {
    return make_ast(&(Node){
            AST_FOR, .forinit = init, .forcond = cond, .forstep = step, .forbody = body });
}

static Node *ast_while(Node *cond, Node *body) {
    return make_ast(&(Node){ AST_WHILE, .forcond = cond, .forbody = body });
}

static Node *ast_do(Node *cond, Node *body) {
    return make_ast(&(Node){ AST_DO, .forcond = cond, .forbody = body });
}

static Node *ast_switch(Node *expr, Node *body) {
    return make_ast(&(Node){ AST_SWITCH, .switchexpr = expr, .switchbody = body });
}

static Node *ast_case(int begin, int end) {
    return make_ast(&(Node){ AST_CASE, .casebeg = begin, .caseend = end });
}

static Node *ast_return(Node *retval) {
    return make_ast(&(Node){ AST_RETURN, .retval = retval });
}

static Node *ast_compound_stmt(Vector *stmts) {
    return make_ast(&(Node){ AST_COMPOUND_STMT, .stmts = stmts });
}

static Node *ast_struct_ref(Type *ty, Node *struc, char *name) {
    return make_ast(&(Node){ AST_STRUCT_REF, ty, .struc = struc, .field = name });
}

static Node *ast_goto(char *label) {
    return make_ast(&(Node){ AST_GOTO, .label = label });
}

static Node *ast_computed_goto(Node *expr) {
    return make_ast(&(Node){ AST_COMPUTED_GOTO, .operand = expr });
}

static Node *ast_label(char *label) {
    return make_ast(&(Node){ AST_LABEL, .label = label });
}

static Node *ast_va_start(Node *ap) {
    return make_ast(&(Node){ AST_VA_START, type_void, .ap = ap });
}

static Node *ast_va_arg(Type *ty, Node *ap) {
    return make_ast(&(Node){ AST_VA_ARG, ty, .ap = ap });
}

static Node *ast_label_addr(char *label) {
    return make_ast(&(Node){ OP_LABEL_ADDR, make_ptr_type(type_void), .label = label });
}

static Type *make_type(Type *tmpl) {
    Type *r = malloc(sizeof(Type));
    *r = *tmpl;
    return r;
}

static Type *copy_type(Type *ty) {
    Type *r = malloc(sizeof(Type));
    memcpy(r, ty, sizeof(Type));
    return r;
}

static Type *make_numtype(int kind, bool usig) {
    Type *r = malloc(sizeof(Type));
    r->kind = kind;
    r->usig = usig;
    if (kind == KIND_VOID)         r->size = r->align = 0;
    else if (kind == KIND_BOOL)    r->size = r->align = 1;
    else if (kind == KIND_CHAR)    r->size = r->align = 1;
    else if (kind == KIND_SHORT)   r->size = r->align = 2;
    else if (kind == KIND_INT)     r->size = r->align = 4;
    else if (kind == KIND_LONG)    r->size = r->align = 8;
    else if (kind == KIND_LLONG)   r->size = r->align = 8;
    else if (kind == KIND_FLOAT)   r->size = r->align = 4;
    else if (kind == KIND_DOUBLE)  r->size = r->align = 8;
    else if (kind == KIND_LDOUBLE) r->size = r->align = 8;
    else error("internal error");
    return r;
}

static Type* make_ptr_type(Type *ty) {
    return make_type(&(Type){ KIND_PTR, .ptr = ty, .size = 8, .align = 8 });
}

static Type* make_array_type(Type *ty, int len) {
    int size;
    if (len < 0)
        size = -1;
    else
        size = ty->size * len;
    return make_type(&(Type){
        KIND_ARRAY,
        .ptr = ty,
        .size = size,
        .len = len,
        .align = ty->align });
}

static Type* make_rectype(bool is_struct) {
    return make_type(&(Type){ KIND_STRUCT, .is_struct = is_struct });
}

static Type* make_func_type(Type *rettype, Vector *paramtypes, bool has_varargs, bool oldstyle) {
    return make_type(&(Type){
        KIND_FUNC,
        .rettype = rettype,
        .params = paramtypes,
        .hasva = has_varargs,
        .oldstyle = oldstyle });
}

static Type *make_stub_type(void) {
    return make_type(&(Type){ KIND_STUB });
}

/*
 * Predicates and kind checking routines
 */

bool is_inttype(Type *ty) {
    switch (ty->kind) {
    case KIND_BOOL: case KIND_CHAR: case KIND_SHORT: case KIND_INT:
    case KIND_LONG: case KIND_LLONG:
        return true;
    default:
        return false;
    }
}

bool is_flotype(Type *ty) {
    switch (ty->kind) {
    case KIND_FLOAT: case KIND_DOUBLE: case KIND_LDOUBLE:
        return true;
    default:
        return false;
    }
}

static bool is_arithtype(Type *ty) {
    return is_inttype(ty) || is_flotype(ty);
}

static bool is_string(Type *ty) {
    return ty->kind == KIND_ARRAY && ty->ptr->kind == KIND_CHAR;
}

static void ensure_lvalue(Node *node) {
    switch (node->kind) {
    case AST_LVAR: case AST_GVAR: case AST_DEREF: case AST_STRUCT_REF:
        return;
    default:
        error("lvalue expected, but got %s", a2s(node));
    }
}

static void ensure_inttype(Node *node) {
    if (!is_inttype(node->ty))
        error("integer kind expected, but got %s", a2s(node));
}

static void ensure_arithtype(Node *node) {
    if (!is_arithtype(node->ty))
        error("arithmetic kind expected, but got %s", a2s(node));
}

static void ensure_not_void(Type *ty) {
    if (ty->kind == KIND_VOID)
        error("void is not allowed");
}

static void expect(char id) {
    Token *tok = read_token();
    if (!is_keyword(tok, id))
        error("'%c' expected, but got %s", id, t2s(tok));
}

static Type *copy_incomplete_type(Type *ty) {
    if (!ty) return NULL;
    return (ty->len == -1) ? copy_type(ty) : ty;
}

static Type *get_typedef(char *name) {
    Node *node = map_get(env(), name);
    return (node && node->kind == AST_TYPEDEF) ? node->ty : NULL;
}

static bool is_type_keyword(Token *tok) {
    if (tok->kind == TIDENT)
        return get_typedef(tok->sval);
    if (tok->kind != TKEYWORD)
        return false;
    switch (tok->id) {
#define op(x, y)
#define keyword(id, _, istype) case id: return istype;
#include "keyword.h"
#undef keyword
#undef op
    default:
        return false;
    }
}

static bool next_token(int kind) {
    Token *tok = read_token();
    if (is_keyword(tok, kind))
        return true;
    unget_token(tok);
    return false;
}

void *make_pair(void *first, void *second) {
    Pair *r = malloc(sizeof(Pair));
    r->first = first;
    r->second = second;
    return r;
}

/*
 * Type conversion
 */

static Node *conv(Node *node) {
    if (!node)
        return NULL;
    // C11 6.3.2.1p4: A function designator is converted to a pointer to the function.
    if (node->kind == AST_FUNCDESG)
        return ast_uop(AST_ADDR, make_ptr_type(node->fptr->ty), node->fptr);
    // C11 6.3.2.1p3: An array of T is converted to a pointer to T.
    Type *ty = node->ty;
    if (ty->kind == KIND_ARRAY)
        return ast_uop(AST_CONV, make_ptr_type(ty->ptr), node);
    // C11 6.3.1.1p2: The integer promotions
    switch (ty->kind) {
    case KIND_SHORT: case KIND_CHAR: case KIND_BOOL:
        return ast_conv(type_int, node);
    case KIND_INT:
        if (ty->bitsize > 0)
            return ast_conv(type_int, node);
    }
    return node;
}

static bool same_arith_type(Type *t, Type *u) {
    return t->kind == u->kind && t->usig == u->usig;
}

// C11 6.3.1.8: Usual arithmetic conversions
static Type *usual_arith_conv(Type *t, Type *u) {
    assert(is_arithtype(t));
    assert(is_arithtype(u));
    if (t->kind < u->kind) {
        // Make t the larger type
        Type *tmp = t;
        t = u;
        u = tmp;
    }
    if (is_flotype(t))
        return t;
    assert(is_inttype(t) && t->size >= type_int->size);
    assert(is_inttype(u) && u->size >= type_int->size);
    if (t->size > u->size)
        return t;
    assert(t->size == u->size);
    if (t->usig == u->usig)
        return t;
    Type *r = copy_type(t);
    r->usig = true;
    return r;
}

static Node *binop(int op, Node *lhs, Node *rhs) {
    if (lhs->ty->kind == KIND_PTR)
        return ast_binop(lhs->ty, op, lhs, rhs);
    if (rhs->ty->kind == KIND_PTR)
        return ast_binop(rhs->ty, op, rhs, lhs);
    assert(is_arithtype(lhs->ty));
    assert(is_arithtype(rhs->ty));
    Type *r = usual_arith_conv(lhs->ty, rhs->ty);
    if (!same_arith_type(lhs->ty, r))
        lhs = ast_uop(AST_CONV, r, lhs);
    if (!same_arith_type(rhs->ty, r))
        rhs = ast_uop(AST_CONV, r, rhs);
    return ast_binop(r, op, lhs, rhs);
}

static bool is_same_struct(Type *a, Type *b) {
    if (a->kind != b->kind)
        return false;
    switch (a->kind) {
    case KIND_ARRAY:
        return a->len == b->len &&
            is_same_struct(a->ptr, b->ptr);
    case KIND_PTR:
        return is_same_struct(a->ptr, b->ptr);
    case KIND_STRUCT: {
{'fraction_non_alphanumeric': 0.1522181653688326, 'fraction_numerical': 0.005880642347087143, 'mean_word_length': 3.1294196130753837, 'pattern_counts': {'":': 0, '<': 27, '<?xml version=': 0, '>': 240, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 8, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '2569391', 'n_tokens_mistral': 11453, 'n_tokens_neox': 11291, 'n_words': 3155}