//
// sym is a string type that is interned and can be efficiently compared
// for equality by pointer value. It's used for identifiers.
//
#include "common/defs.h"
#include "common/hash.h"
#include "common/test.h"
#include "parse/ast.h"
#include "sym.h"

#define RBKEY Sym
#define RBUSERDATA Memory
#include "common/rbtree.c.h"

// -----------------------------------------------------------------------------------------
// generated by gen_constants at the end of this file.
// Define to run the generator during program initialization:
// #define W_SYM_RUN_GENERATOR


//-- BEGIN gen_constants() at src/sym.c:349

const Sym sym_as = &"\0\0\0\0\0\0\0\x8D\x20\x25\x5E\x02\x00\x02\x00\x0A""as"[16];
const Sym sym_break = &"\0\0\0\0\0\0\0\x78\x81\x64\xC9\x05\x00\x05\x00\x12""break"[16];
const Sym sym_case = &"\0\0\0\0\0\0\0\xB1\x38\x25\x9B\x04\x00\x04\x00\x1A""case"[16];
const Sym sym_continue = &"\0\0\0\0\0\0\0\x44\x7E\x72\xB1\x08\x00\x08\x00\x22""continue"[16];
const Sym sym_default = &"\0\0\0\0\0\0\0\xDE\x5B\x3B\x93\x07\x00\x07\x00\x2A""default"[16];
const Sym sym_defer = &"\0\0\0\0\0\0\0\x3B\xFB\x01\x1A\x05\x00\x05\x00\x32""defer"[16];
const Sym sym_else = &"\0\0\0\0\0\0\0\xF0\x5B\xBF\xBD\x04\x00\x04\x00\x3A""else"[16];
const Sym sym_enum = &"\0\0\0\0\0\0\0\x00\xB0\x6C\x81\x04\x00\x04\x00\x42""enum"[16];
const Sym sym_for = &"\0\0\0\0\0\0\0\x90\x83\xF3\xAC\x03\x00\x03\x00\x4A""for"[16];
const Sym sym_fun = &"\0\0\0\0\0\0\0\x5E\x78\xDB\xA8\x03\x00\x03\x00\x52""fun"[16];
const Sym sym_if = &"\0\0\0\0\0\0\0\x06\x6E\x38\x39\x02\x00\x02\x00\x5A""if"[16];
const Sym sym_import = &"\0\0\0\0\0\0\0\xD4\x90\x2A\x11\x06\x00\x06\x00\x62""import"[16];
const Sym sym_in = &"\0\0\0\0\0\0\0\x9E\x7A\x38\x41\x02\x00\x02\x00\x6A""in"[16];
const Sym sym_interface = &"\0\0\0\0\0\0\0\x30\x51\xEA\x84\x09\x00\x09\x00\x72""interface"[16];
const Sym sym_is = &"\0\0\0\0\0\0\0\x15\x8F\x38\x4E\x02\x00\x02\x00\x7A""is"[16];
const Sym sym_mutable = &"\0\0\0\0\0\0\0\xA9\x33\x03\x3B\x07\x00\x07\x00\x82""mutable"[16];
const Sym sym_nil = &"\0\0\0\0\0\0\0\xEC\xF8\xA3\x0D\x03\x00\x03\x00\x8A""nil"[16];
const Sym sym_return = &"\0\0\0\0\0\0\0\xBF\x37\xEE\x85\x06\x00\x06\x00\x92""return"[16];
const Sym sym_select = &"\0\0\0\0\0\0\0\x2D\x66\xC2\x11\x06\x00\x06\x00\x9A""select"[16];
const Sym sym_struct = &"\0\0\0\0\0\0\0\x20\xBE\xC2\x92\x06\x00\x06\x00\xA2""struct"[16];
const Sym sym_switch = &"\0\0\0\0\0\0\0\x71\x5F\xE0\x93\x06\x00\x06\x00\xAA""switch"[16];
const Sym sym_symbol = &"\0\0\0\0\0\0\0\xD1\x51\xFB\xF3\x06\x00\x06\x00\xB2""symbol"[16];
const Sym sym_type = &"\0\0\0\0\0\0\0\x4D\xF1\x27\x51\x04\x00\x04\x00\xBA""type"[16];
const Sym sym_while = &"\0\0\0\0\0\0\0\xCE\x28\xC6\x0D\x05\x00\x05\x00\xC2""while"[16];
const Sym sym_bool = &"\0\0\0\0\0\0\0\x3D\x95\x94\xC8\x04\x00\x04\x00\x02""bool"[16];
const Sym sym_int8 = &"\0\0\0\0\0\0\0\x92\xFA\x91\x64\x04\x00\x04\x00\x02""int8"[16];
const Sym sym_uint8 = &"\0\0\0\0\0\0\0\xDB\xF2\x9D\x19\x05\x00\x05\x00\x02""uint8"[16];
const Sym sym_int16 = &"\0\0\0\0\0\0\0\xD1\x72\xE3\x07\x05\x00\x05\x00\x02""int16"[16];
const Sym sym_uint16 = &"\0\0\0\0\0\0\0\xF2\xBE\x8E\xAE\x06\x00\x06\x00\x02""uint16"[16];
const Sym sym_int32 = &"\0\0\0\0\0\0\0\xBF\xE2\xDE\xFB\x05\x00\x05\x00\x02""int32"[16];
const Sym sym_uint32 = &"\0\0\0\0\0\0\0\xEC\x0B\x94\x32\x06\x00\x06\x00\x02""uint32"[16];
const Sym sym_int64 = &"\0\0\0\0\0\0\0\x64\x23\xD2\x03\x05\x00\x05\x00\x02""int64"[16];
const Sym sym_uint64 = &"\0\0\0\0\0\0\0\x13\x08\xA0\xAE\x06\x00\x06\x00\x02""uint64"[16];
const Sym sym_float32 = &"\0\0\0\0\0\0\0\x10\x74\x9F\xE8\x07\x00\x07\x00\x02""float32"[16];
const Sym sym_float64 = &"\0\0\0\0\0\0\0\x47\x0E\x98\x7C\x07\x00\x07\x00\x02""float64"[16];
const Sym sym_int = &"\0\0\0\0\0\0\0\x5E\x7E\xE9\x95\x03\x00\x03\x00\x02""int"[16];
const Sym sym_uint = &"\0\0\0\0\0\0\0\xA1\x36\x98\xCB\x04\x00\x04\x00\x02""uint"[16];
const Sym sym_str = &"\0\0\0\0\0\0\0\x90\xD1\x4B\xC2\x03\x00\x03\x00\x02""str"[16];
const Sym sym__ = &"\0\0\0\0\0\0\0\x6E\x19\x0C\xDA\x01\x00\x01\x00\x02""_"[16];
const Sym sym_true = &"\0\0\0\0\0\0\0\xE5\x11\xB2\x4D\x04\x00\x04\x00\x02""true"[16];
const Sym sym_false = &"\0\0\0\0\0\0\0\x58\x99\x06\x0B\x05\x00\x05\x00\x02""false"[16];
const Sym sym_b = &"\0\0\0\0\0\0\0\xE5\x2D\x0C\xE7\x01\x00\x01\x00\x02""b"[16];
const Sym sym_1 = &"\0\0\0\0\0\0\0\x1C\xA7\x0C\x34\x01\x00\x01\x00\x02""1"[16];
const Sym sym_2 = &"\0\0\0\0\0\0\0\xD5\xAB\x0C\x37\x01\x00\x01\x00\x02""2"[16];
const Sym sym_3 = &"\0\0\0\0\0\0\0\x42\xAA\x0C\x36\x01\x00\x01\x00\x02""3"[16];
const Sym sym_4 = &"\0\0\0\0\0\0\0\x63\xA2\x0C\x31\x01\x00\x01\x00\x02""4"[16];
const Sym sym_5 = &"\0\0\0\0\0\0\0\xD0\xA0\x0C\x30\x01\x00\x01\x00\x02""5"[16];
const Sym sym_6 = &"\0\0\0\0\0\0\0\x89\xA5\x0C\x33\x01\x00\x01\x00\x02""6"[16];
const Sym sym_7 = &"\0\0\0\0\0\0\0\xF6\xA3\x0C\x32\x01\x00\x01\x00\x02""7"[16];
const Sym sym_8 = &"\0\0\0\0\0\0\0\x47\xB5\x0C\x3D\x01\x00\x01\x00\x02""8"[16];
const Sym sym_f = &"\0\0\0\0\0\0\0\x99\x27\x0C\xE3\x01\x00\x01\x00\x02""f"[16];
const Sym sym_F = &"\0\0\0\0\0\0\0\x39\xF5\x0B\xC3\x01\x00\x01\x00\x02""F"[16];
const Sym sym_i = &"\0\0\0\0\0\0\0\xC4\x35\x0C\xEC\x01\x00\x01\x00\x02""i"[16];
const Sym sym_u = &"\0\0\0\0\0\0\0\x10\x3C\x0C\xF0\x01\x00\x01\x00\x02""u"[16];
const Sym sym_s = &"\0\0\0\0\0\0\0\x82\x45\x0C\xF6\x01\x00\x01\x00\x02""s"[16];

static const Node _Type_bool = {NBasicType,{0,0,0},NULL,{.t={sym_b,.basic={TypeCode_bool,sym_bool}}}};
Node* Type_bool = (Node*)&_Type_bool;
static const Node _Type_int8 = {NBasicType,{0,0,0},NULL,{.t={sym_1,.basic={TypeCode_int8,sym_int8}}}};
Node* Type_int8 = (Node*)&_Type_int8;
static const Node _Type_uint8 = {NBasicType,{0,0,0},NULL,{.t={sym_2,.basic={TypeCode_uint8,sym_uint8}}}};
Node* Type_uint8 = (Node*)&_Type_uint8;
static const Node _Type_int16 = {NBasicType,{0,0,0},NULL,{.t={sym_3,.basic={TypeCode_int16,sym_int16}}}};
Node* Type_int16 = (Node*)&_Type_int16;
static const Node _Type_uint16 = {NBasicType,{0,0,0},NULL,{.t={sym_4,.basic={TypeCode_uint16,sym_uint16}}}};
Node* Type_uint16 = (Node*)&_Type_uint16;
static const Node _Type_int32 = {NBasicType,{0,0,0},NULL,{.t={sym_5,.basic={TypeCode_int32,sym_int32}}}};
Node* Type_int32 = (Node*)&_Type_int32;
static const Node _Type_uint32 = {NBasicType,{0,0,0},NULL,{.t={sym_6,.basic={TypeCode_uint32,sym_uint32}}}};
Node* Type_uint32 = (Node*)&_Type_uint32;
static const Node _Type_int64 = {NBasicType,{0,0,0},NULL,{.t={sym_7,.basic={TypeCode_int64,sym_int64}}}};
Node* Type_int64 = (Node*)&_Type_int64;
static const Node _Type_uint64 = {NBasicType,{0,0,0},NULL,{.t={sym_8,.basic={TypeCode_uint64,sym_uint64}}}};
Node* Type_uint64 = (Node*)&_Type_uint64;
static const Node _Type_float32 = {NBasicType,{0,0,0},NULL,{.t={sym_f,.basic={TypeCode_float32,sym_float32}}}};
Node* Type_float32 = (Node*)&_Type_float32;
static const Node _Type_float64 = {NBasicType,{0,0,0},NULL,{.t={sym_F,.basic={TypeCode_float64,sym_float64}}}};
Node* Type_float64 = (Node*)&_Type_float64;
static const Node _Type_int = {NBasicType,{0,0,0},NULL,{.t={sym_i,.basic={TypeCode_int,sym_int}}}};
Node* Type_int = (Node*)&_Type_int;
static const Node _Type_uint = {NBasicType,{0,0,0},NULL,{.t={sym_u,.basic={TypeCode_uint,sym_uint}}}};
Node* Type_uint = (Node*)&_Type_uint;
static const Node _Type_str = {NBasicType,{0,0,0},NULL,{.t={sym_s,.basic={TypeCode_str,sym_str}}}};
Node* Type_str = (Node*)&_Type_str;

static const Node _Const_true = {NBoolLit,{0,0,0},(Node*)&_Type_bool,{.val={CType_bool,.i=1}}};
Node* Const_true = (Node*)&_Const_true;
static const Node _Const_false = {NBoolLit,{0,0,0},(Node*)&_Type_bool,{.val={CType_bool,.i=0}}};
Node* Const_false = (Node*)&_Const_false;

static RBNode n_int64 = { sym_int64, true, null, null };
static RBNode n_false = { sym_false, true, null, null };
static RBNode n_int16 = { sym_int16, false, &n_int64, &n_false };
static RBNode n_while = { sym_while, false, null, null };
static RBNode n_nil = { sym_nil, false, &n_int16, &n_while };
static RBNode n_select = { sym_select, true, null, null };
static RBNode n_uint8 = { sym_uint8, false, &n_select, null };
static RBNode n_uint32 = { sym_uint32, true, null, null };
static RBNode n_mutable = { sym_mutable, true, null, null };
static RBNode n_if = { sym_if, false, &n_uint32, &n_mutable };
static RBNode n_defer = { sym_defer, false, &n_uint8, &n_if };
static RBNode n_import = { sym_import, true, &n_nil, &n_defer };
static RBNode n_true = { sym_true, true, null, null };
static RBNode n_type = { sym_type, true, null, null };
static RBNode n_is = { sym_is, false, &n_true, &n_type };
static RBNode n_int8 = { sym_int8, true, null, null };
static RBNode n_enum = { sym_enum, true, null, null };
static RBNode n_float64 = { sym_float64, false, &n_int8, &n_enum };
static RBNode n_as = { sym_as, false, &n_is, &n_float64 };
static RBNode n_in = { sym_in, false, &n_import, &n_as };
static RBNode n_return = { sym_return, false, null, null };
static RBNode n_default = { sym_default, true, null, null };
static RBNode n_int = { sym_int, true, null, null };
static RBNode n_switch = { sym_switch, false, &n_default, &n_int };
static RBNode n_struct = { sym_struct, false, &n_return, &n_switch };
static RBNode n_fun = { sym_fun, false, null, null };
static RBNode n_uint16 = { sym_uint16, true, null, null };
static RBNode n_continue = { sym_continue, true, null, null };
static RBNode n_uint64 = { sym_uint64, false, &n_uint16, &n_continue };
static RBNode n_for = { sym_for, false, &n_fun, &n_uint64 };
static RBNode n_case = { sym_case, true, &n_struct, &n_for };
static RBNode n_str = { sym_str, true, null, null };
static RBNode n_bool = { sym_bool, false, &n_str, null };
static RBNode n_uint = { sym_uint, true, null, null };
static RBNode n_float32 = { sym_float32, true, null, null };
static RBNode n__ = { sym__, false, &n_uint, &n_float32 };
static RBNode n_break = { sym_break, true, &n_bool, &n__ };
static RBNode n_int32 = { sym_int32, false, null, null };
static RBNode n_symbol = { sym_symbol, false, &n_break, &n_int32 };
static RBNode n_else = { sym_else, false, &n_case, &n_symbol };
static RBNode n_interface = { sym_interface, false, &n_in, &n_else };

static RBNode* symRoot = &n_interface;
#ifndef NDEBUG
static const char* const debugSymCheck =
  "as#101 break#102 case#103 continue#104 default#105 defer#106 else#107 "
  "enum#108 for#109 fun#10a if#10b import#10c in#10d interface#10e "
  "is#10f mutable#110 nil#111 return#112 select#113 struct#114 switch#115 "
  "symbol#116 type#117 while#118 bool int8 uint8 int16 uint16 int32 uint32 "
  "int64 uint64 float32 float64 int uint str true:bool=1 false:bool=0 _ ";
#endif

//-- END gen_constants() at src/sym.c:536



// nil is special and implemented without macros since its sym is defined by TOKEN_KEYWORDS
static const Node _Type_nil = {NBasicType,{0,0,0},NULL,{.t={"0",.basic={TypeCode_nil,sym_nil}}}};
Node* Type_nil = (Node*)&_Type_nil;

static const Node _Const_nil = {NNil,{0,0,0},(Node*)&_Type_nil,{.val={CType_nil,.i=0}}};
Node* Const_nil = (Node*)&_Const_nil;

// ideal
const Sym sym_ideal = &"\0\0\0\0\0\0\0\x64\x23\xD2\x03\x05\x00\x05\x00\x02""ideal"[16];
static const Node _Type_ideal = {NBasicType,{0,0,0},NULL,{
  .t={"\0",.basic={TypeCode_ideal,sym_ideal}}
}};
Node* Type_ideal = (Node*)&_Type_ideal;


// -----------------------------------------------------------------------------------------


// // dumpSymTree functionn
// #if DEBUG
// static Str dumpSymTreeFmtKey(Str s, Sym k) {
//   s = sdscatrepr(s, k, sdslen(k));
//   return sdscatprintf(s, " (flags %02X, hash %u)", SYM_HDR(k)->sh.flags, SYM_HDR(k)->hash);
// }
// static void dumpSymTree() {
//   auto s = RBRepr(symRoot, sdsempty(), 0, &dumpSymTreeFmtKey);
//   s[sdslen(s)] = '\n'; // replace NUL with ln
//   fwrite(s, sdslen(s)+1, 1, stderr);
//   sdsfree(s);
// }
// #endif


static Sym newsym(u32 hash, const u8* ptr, size_t len, u8 flags) {
  assert(len <= 0xFFFF);
  auto hp = (SymHeader*)memalloc(NULL, sizeof(SymHeader) + len + 1);
  hp->hash = hash;
  hp->sh.len = len;
  hp->sh.alloc = len;
  hp->sh.flags = flags;
  auto s = ((u8*)hp) + sizeof(SymHeader); // pointer to data
  memcpy(s, ptr, len);
  s[len] = 0;
  return (Sym)s;
}


// RB functions
inline static RBNode* RBAllocNode(Memory mem) {
  return (RBNode*)memalloc(mem, sizeof(RBNode));
}

// syms are never removed from the interning tree
inline static void RBFreeNode(RBNode* node, Memory mem) {
  assert(!"sym deallocated");
}


inline static int RBCmp(Sym a, Sym b, Memory mem) {
  if (symhash(a) < symhash(b)) {
    return -1;
  }
  if (symhash(a) > symhash(b)) {
    return 1;
  }
  int cmp = (int)symlen(a) - (int)symlen(b);
  if (cmp == 0) {
    // hash is identical and length is identical; compare bytes.
    cmp = memcmp(a, b, symlen(a));
  }
  return cmp;
}


inline static Sym symFind(u32 hash, const u8* aptr, u16 alen) {
  RBNode* node = symRoot;
  while (node) {
    // IMPORTANT: The comparison here MUST match the comparison used for other
    // operations on the tree. I.e. it must match RBCmp.
    // int cmp = RBCmp(key, (RBKEY)node->key);

    Sym b = (RBKEY)node->key;
    if (hash < symhash(b)) {
      node = node->left;
    } else if (hash > symhash(b)) {
      node = node->right;
    } else {
      int cmp = (int)alen - (int)symlen(b);
      if (cmp == 0) {
        cmp = memcmp(aptr, b, alen);
        if (cmp == 0) {
          return b;
        }
      }
      node = cmp < 0 ? node->left : node->right;
    }
  }
  return NULL;
}


Sym symget(const u8* data, size_t _len, u32 hash) {
  assert(_len <= 0xFFFF);
  u16 len = (u16)_len;
  auto s = symFind(hash, data, len);
  if (s == NULL) {
    // intern miss
    // auto key = newsym(hash, data, len, SDS_TYPE_16);
    // bool rbhas = RBHas(symRoot, key);
    s = newsym(hash, data, len, SDS_TYPE_16);
    symRoot = RBInsert(symRoot, s, NULL);
  }
  return s;
}


Sym symgeth(const u8* data, size_t len) {
  return symget(data, len, hashFNV1a(data, len));
}


Node* const _TypeCodeToTypeNodeMap[TypeCode_CONCRETE_END] = {
  (Node*)&_Type_bool, // TypeCode_bool
  (Node*)&_Type_int8, // TypeCode_int8
  (Node*)&_Type_uint8, // TypeCode_uint8
  (Node*)&_Type_int16, // TypeCode_int16
  (Node*)&_Type_uint16, // TypeCode_uint16
  (Node*)&_Type_int32, // TypeCode_int32
  (Node*)&_Type_uint32, // TypeCode_uint32
  (Node*)&_Type_int64, // TypeCode_int64
  (Node*)&_Type_uint64, // TypeCode_uint64
  (Node*)&_Type_float32, // TypeCode_float32
  (Node*)&_Type_float64, // TypeCode_float64
  (Node*)&_Type_int, // TypeCode_int
  (Node*)&_Type_uint, // TypeCode_uint
  (Node*)&_Type_nil, // TypeCode_NUM_END
  (Node*)&_Type_str, // TypeCode_str
  (Node*)&_Type_nil, // TypeCode_nil
};


// ---------------------------------------------------------------------------------------
// sym constant data generator

#if defined(W_SYM_RUN_GENERATOR)

inline static Str fmt_nodes(const RBNode* n, Str s) {
  // descent first
  if (n->left) {
    s = fmt_nodes(n->left, s);
  }
  if (n->right) {
    s = fmt_nodes(n->right, s);
  }

  s = sdscat(s, "static RBNode n_");
  s = sdscatsds(s, n->key);
  s = sdscat(s, " = { ");

  // { key, isred, left, right }

  s = sdscatfmt(s, "sym_%S, ", n->key);
  // s = sdscat(s, "null, ");

  s = sdscat(s, n->isred ? "true, " : "false, ");
  if (n->left) {
    s = sdscatfmt(s, "&n_%S, ", n->left->key);
  } else {
    s = sdscat(s, "null, ");
  }
  if (n->right) {
    s = sdscatfmt(s, "&n_%S ", n->right->key);
  } else {
    s = sdscat(s, "null ");
  }
  s = sdscat(s, "};\n");
  return s;
}

static constsds fmtkey(Sym k) { return k; } // Sym is a type of Str :-)

__attribute__((constructor)) static void gen_constants() {
  printf("//-- BEGIN gen_constants() at %s:%d\n\n", __FILE__, __LINE__);

  #define SYM_DEF(str, tok)                                             \
    Sym sym_##str = newsym(hashFNV1a((const u8*)(#str), strlen(#str)),  \
      (const u8*)(#str), (u32)strlen(#str), SDS_TYPE_16);
  TOKEN_KEYWORDS(SYM_DEF)
  #undef SYM_DEF

  #define SYM_DEF(name)                                                   \
    Sym sym_##name = newsym(hashFNV1a((const u8*)(#name), strlen(#name)), \
      (const u8*)(#name), (u32)strlen(#name), SDS_TYPE_16);
  #define SYM_DEF_CONST(name, _t, _v)                                     \
    Sym sym_##name = newsym(hashFNV1a((const u8*)(#name), strlen(#name)), \
      (const u8*)(#name), (u32)strlen(#name), SDS_TYPE_16);
  TYPE_SYMS(SYM_DEF)
  PREDEFINED_CONSTANTS(SYM_DEF_CONST)
  PREDEFINED_IDENTS(SYM_DEF)
  #undef SYM_DEF
  #undef SYM_DEF_CONST

  u8 buf1[1];
  #define SYM_DEF(name)                                                       \
    buf1[0] = TypeCodeEncoding[TypeCode_##name];                              \
    Sym sym_typeid_##name = newsym(hashFNV1a(buf1, 1), buf1, 1, SDS_TYPE_16);
  TYPE_SYMS(SYM_DEF)
  #undef SYM_DEF


  // TOKEN_KEYWORDS => sym_
  // TYPE_SYMS => sym_
  // PREDEFINED_IDENTS => sym_
  #define SYM_DEF(str, name, flags)  {                                  \
    auto hdr = SYM_HDR(sym_##name);                                     \
    auto hash = (u8*)&hdr->hash;                                        \
    auto len = (u8*)&hdr->sh.len;                                       \
    printf(                                                             \
      "const Sym sym_" #name " = &\""                                   \
      /* padding = align2(sizeof(SymHeader), 8) - sizeof(SymHeader) */  \
      "\\0\\0\\0\\0\\0\\0\\0"                                           \
      "\\x%02X\\x%02X\\x%02X\\x%02X" /* SymHeader.hash */               \
      "\\x%02X\\x%02X"               /* sdshdr16.len */                 \
      "\\x%02X\\x%02X"               /* sdshdr16.alloc */               \
      "\\x%02X"                      /* sdshdr16.flags = SDS_TYPE_16 */ \
      "\"\"" str                     /* "" is here to terminate \x03 */ \
      "\"[%d];\n",                                                      \
      hash[0], hash[1], hash[2], hash[3],                               \
      len[0],  len[1],                                                  \
      len[0],  len[1],                                                  \
      SDS_TYPE_16 | ((flags) << SDS_TYPE_BITS),                         \
      16 /* align2(sizeof(SymHeader), 8) */                             \
    );                                                                  \
  }
  #define SYM_DEF_KW(str, tok) SYM_DEF(#str, str, (tok - TKeywordsStart))
  #define SYM_DEF_NAME(name)   SYM_DEF(#name, name, 0)
  TOKEN_KEYWORDS(SYM_DEF_KW)
  TYPE_SYMS(SYM_DEF_NAME)
  PREDEFINED_IDENTS(SYM_DEF_NAME)
  #undef SYM_DEF_KW
  #undef SYM_DEF_NAME
  #undef SYM_DEF


  // PREDEFINED_CONSTANTS => sym_
  #define SYM_DEF(name, _type, _val)  {                                 \
    auto hdr = SYM_HDR(sym_##name);                                     \
    auto hash = (u8*)&hdr->hash;                                        \
    auto len = (u8*)&hdr->sh.len;                                       \
    printf(                                                             \
      "const Sym sym_" #name " = &\""                                   \
      "\\0\\0\\0\\0\\0\\0\\0"                                           \
      "\\x%02X\\x%02X\\x%02X\\x%02X" /* SymHeader.hash */               \
      "\\x%02X\\x%02X"               /* sdshdr16.len */                 \
      "\\x%02X\\x%02X"               /* sdshdr16.alloc */               \
      "\\x%02X"                      /* sdshdr16.flags = SDS_TYPE_16 */ \
      "\"\"" #name                   /* "" is here to terminate \x03 */ \
      "\"[%d];\n",                                                      \
      hash[0], hash[1], hash[2], hash[3],                               \
      len[0],  len[1],                                                  \
      len[0],  len[1],                                                  \
      SDS_TYPE_16 | (0 << SDS_TYPE_BITS),                               \
      16 /* align2(sizeof(SymHeader), 8) */                             \
    );                                                                  \
  }
  PREDEFINED_CONSTANTS(SYM_DEF)
  #undef SYM_DEF


  // TYPE_SYMS.TypeCode => sym_typeid_
  #define SYM_DEF(name)  {                                              \
    auto hdr = SYM_HDR(sym_typeid_##name);                              \
    auto hash = (u8*)&hdr->hash;                                        \
    auto len = (u8*)&hdr->sh.len;                                       \
    printf(                                                             \
      "const Sym sym_%c = &\""                                          \
      "\\0\\0\\0\\0\\0\\0\\0"                                           \
      "\\x%02X\\x%02X\\x%02X\\x%02X" /* SymHeader.hash */               \
      "\\x%02X\\x%02X"               /* sdshdr16.len */                 \
      "\\x%02X\\x%02X"               /* sdshdr16.alloc */               \
      "\\x%02X"                      /* sdshdr16.flags = SDS_TYPE_16 */ \
      "\"\"%c"                       /* "" is here to terminate \x03 */ \
      "\"[%d];\n",                                                      \
      TypeCodeEncoding[TypeCode_##name],                                \
      hash[0], hash[1], hash[2], hash[3],                               \
      len[0],  len[1],                                                  \
      len[0],  len[1],                                                  \
      SDS_TYPE_16 | (0 << SDS_TYPE_BITS),                               \
      TypeCodeEncoding[TypeCode_##name], 16 /* align2(sizeof(SymHeader), 8) */  \
    );                                                                  \
  }
  TYPE_SYMS(SYM_DEF)
  #undef SYM_DEF


  // TODO: precompute t.id Sym
  // const Node* type_NAME
  printf(
    "\n"
    //"static const Node _badnode = {NBad,{0,0,0},NULL,{0}};\n"
  );
  #define SYM_DEF(name)                                                         \
    printf(                                                                     \
      "static const Node _Type_%s = "                                           \
      "{NBasicType,{0,0,0},NULL,{.t={sym_%c,.basic={TypeCode_%s,sym_%s}}}};\n"  \
      "Node* Type_%s = (Node*)&_Type_%s;\n",                                    \
      #name, TypeCodeEncoding[TypeCode_##name], #name, #name, #name, #name      \
    );
  TYPE_SYMS(SYM_DEF)
  #undef SYM_DEF


  // PREDEFINED_CONSTANTS
  printf("\n");
  #define SYM_DEF(name, type, value)                                             \
    printf(                                                                      \
      "static const Node _Const_%s = {%s,{0,0,0},(Node*)&_Type_%s,{.val=%s}};\n" \
      "Node* Const_%s = (Node*)&_Const_%s;\n",                                   \
      #name,                                                                     \
      #type == "bool" ? "NBoolLit" : "NIntLit",                                  \
      #type,                                                                     \
      /*NVal*/ "{CType_" #type ",.i=" #value "}",                                \
      #name, #name                                                               \
    );
  PREDEFINED_CONSTANTS(SYM_DEF)
  #undef SYM_DEF


  RBNode* root = NULL;
  #define KW(str, tok) root = RBInsert(root, sym_##str, NULL);
  TOKEN_KEYWORDS(KW)
  #undef KW
  #define KW(name) root = RBInsert(root, sym_##name, NULL);
  #define CONST(name, _type, _val) root = RBInsert(root, sym_##name, NULL);
  TYPE_SYMS(KW)
  PREDEFINED_CONSTANTS(CONST)
  PREDEFINED_IDENTS(KW)
  #undef CONST
  #undef KW

  printf("\n%s\n", fmt_nodes(root, sdsempty()));

  printf("static RBNode* symRoot = &n_%s;\n", root->key);

  // generate a sort of checksum used in debug mode to make sure the generator is updated
  // when keywords change. See the function debug_check() below as well.
  int col = 0;
  printf("#ifndef NDEBUG\nstatic const char* const debugSymCheck =\n  \"");
  #define KW(str, tok)             \
    printf("%s#%03x ", #str, tok); \
    col += strlen(#str) + 6;       \
    if (col > 70) { col = 0; printf("\"\n  \""); }
  #define CONST(name, type, val)               \
    printf("%s:%s=%s ", #name, #type, #val);   \
    col += strlen(#name #type #val) + 3;      \
    if (col > 70) { col = 0; printf("\"\n  \""); }
  #define NAME(name)               \
    printf("%s ", #name);          \
    col += strlen(#name) + 1;      \
    if (col > 70) { col = 0; printf("\"\n  \""); }
  TOKEN_KEYWORDS(KW)
  TYPE_SYMS(NAME)
  PREDEFINED_CONSTANTS(CONST)
  PREDEFINED_IDENTS(NAME)
  #undef KW
  #undef CONST
  #undef NAME
  printf("\";\n#endif\n");

  printf("\n//-- END gen_constants() at %s:%d\n\n", __FILE__, __LINE__);
  exit(1);
}

#endif /* defined(W_SYM_RUN_GENERATOR) */


// -----------------------------------------------------------------------------------------------


#if !defined(NDEBUG) && !defined(W_SYM_RUN_GENERATOR)
__attribute__((constructor)) static void debug_check() {
  auto s = sdsempty();

  #define KW(str, tok)           s = sdscatprintf(s, "%s#%03x ", #str, tok);
  #define CONST(name, type, val) s = sdscatprintf(s, "%s:%s=%s ", #name, #type, #val);
  #define NAME(name)             s = sdscatlen(s, #name " ", strlen(#name " "));
  TOKEN_KEYWORDS(KW)
  TYPE_SYMS(NAME)
  PREDEFINED_CONSTANTS(CONST)
  PREDEFINED_IDENTS(NAME)
  #undef KW
  #undef CONST
  #undef NAME

  if (strcmp(debugSymCheck, s) != 0) {
    printf("Keywords changed.\n");
    printf("Define W_SYM_RUN_GENERATOR in %s to run code generator.\n", __FILE__);
    printf("\ndebugSymCheck:\n%s\n\ndetected:\n%s\n", debugSymCheck, s);
    exit(1);
  }
}
#endif


// -----------------------------------------------------------------------------------------------

// SymMap implementation
#define HASHMAP_NAME     SymMap
#define HASHMAP_KEY      Sym
#define HASHMAP_KEY_HASH symhash
#define HASHMAP_VALUE    void*
#include "common/hashmap.c.h"
#undef HASHMAP_NAME
#undef HASHMAP_KEY
#undef HASHMAP_KEY_HASH
#undef HASHMAP_VALUE

#if DEBUG
static void testMapIterator(Sym key, void* value, bool* stop, void* userdata) {
  // dlog("\"%s\" => %zu", key, (size_t)value);
  size_t* n = (size_t*)userdata;
  (*n)++;
}
#endif

W_UNIT_TEST(SymMap, {;
  auto m = SymMapNew(64, NULL);

  assert(m->len == 0);

  #define SYM(cstr) symgeth((const u8*)(cstr), strlen(cstr))
  const void* oldval;

  oldval = SymMapSet(m, SYM("hello"), (void*)1);
  // dlog("SymMapSet(hello) => %zu", (size_t)oldval);
  assert(m->len == 1);

  oldval = SymMapSet(m, SYM("hello"), (void*)2);
  // dlog("SymMapSet(hello) => %zu", (size_t)oldval);
  assert(m->len == 1);

  assert(SymMapDel(m, SYM("hello")) == (void*)2);
  assert(m->len == 0);

  size_t n = 100;
  SymMapSet(m, SYM("break"),       (void*)n++); assert(m->len == n - 100);
  SymMapSet(m, SYM("case"),        (void*)n++); assert(m->len == n - 100);
  SymMapSet(m, SYM("const"),       (void*)n++); assert(m->len == n - 100);
  SymMapSet(m, SYM("continue"),    (void*)n++); assert(m->len == n - 100);
  SymMapSet(m, SYM("default"),     (void*)n++); assert(m->len == n - 100);
  SymMapSet(m, SYM("defer"),       (void*)n++); assert(m->len == n - 100);
  SymMapSet(m, SYM("else"),        (void*)n++); assert(m->len == n - 100);
  SymMapSet(m, SYM("enum"),        (void*)n++); assert(m->len == n - 100);
  SymMapSet(m, SYM("fallthrough"), (void*)n++); assert(m->len == n - 100);
  SymMapSet(m, SYM("for"),         (void*)n++); assert(m->len == n - 100);
  SymMapSet(m, SYM("fun"),         (void*)n++); assert(m->len == n - 100);
  SymMapSet(m, SYM("go"),          (void*)n++); assert(m->len == n - 100);
  SymMapSet(m, SYM("if"),          (void*)n++); assert(m->len == n - 100);
  SymMapSet(m, SYM("import"),      (void*)n++); assert(m->len == n - 100);
  SymMapSet(m, SYM("in"),          (void*)n++); assert(m->len == n - 100);
  SymMapSet(m, SYM("interface"),   (void*)n++); assert(m->len == n - 100);
  SymMapSet(m, SYM("is"),          (void*)n++); assert(m->len == n - 100);
  SymMapSet(m, SYM("return"),      (void*)n++); assert(m->len == n - 100);
  SymMapSet(m, SYM("select"),      (void*)n++); assert(m->len == n - 100);
  SymMapSet(m, SYM("struct"),      (void*)n++); assert(m->len == n - 100);
  SymMapSet(m, SYM("switch"),      (void*)n++); assert(m->len == n - 100);
  SymMapSet(m, SYM("symbol"),      (void*)n++); assert(m->len == n - 100);
  SymMapSet(m, SYM("type"),        (void*)n++); assert(m->len == n - 100);
  SymMapSet(m, SYM("var"),         (void*)n++); assert(m->len == n - 100);
  SymMapSet(m, SYM("while"),       (void*)n++); assert(m->len == n - 100);
  SymMapSet(m, SYM("_"),           (void*)n++); assert(m->len == n - 100);
  SymMapSet(m, SYM("int"),         (void*)n++); assert(m->len == n - 100);

  n = 0;
  SymMapIter(m, testMapIterator, &n);
  assert(n == 27);

  n = 100;
  assert(SymMapGet(m, SYM("break"))       == (void*)n++);
  assert(SymMapGet(m, SYM("case"))        == (void*)n++);
  assert(SymMapGet(m, SYM("const"))       == (void*)n++);
  assert(SymMapGet(m, SYM("continue"))    == (void*)n++);
  assert(SymMapGet(m, SYM("default"))     == (void*)n++);
  assert(SymMapGet(m, SYM("defer"))       == (void*)n++);
  assert(SymMapGet(m, SYM("else"))        == (void*)n++);
  assert(SymMapGet(m, SYM("enum"))        == (void*)n++);
  assert(SymMapGet(m, SYM("fallthrough")) == (void*)n++);
  assert(SymMapGet(m, SYM("for"))         == (void*)n++);
  assert(SymMapGet(m, SYM("fun"))         == (void*)n++);
  assert(SymMapGet(m, SYM("go"))          == (void*)n++);
  assert(SymMapGet(m, SYM("if"))          == (void*)n++);
  assert(SymMapGet(m, SYM("import"))      == (void*)n++);
  assert(SymMapGet(m, SYM("in"))          == (void*)n++);
  assert(SymMapGet(m, SYM("interface"))   == (void*)n++);
  assert(SymMapGet(m, SYM("is"))          == (void*)n++);
  assert(SymMapGet(m, SYM("return"))      == (void*)n++);
  assert(SymMapGet(m, SYM("select"))      == (void*)n++);
  assert(SymMapGet(m, SYM("struct"))      == (void*)n++);
  assert(SymMapGet(m, SYM("switch"))      == (void*)n++);
  assert(SymMapGet(m, SYM("symbol"))      == (void*)n++);
  assert(SymMapGet(m, SYM("type"))        == (void*)n++);
  assert(SymMapGet(m, SYM("var"))         == (void*)n++);
  assert(SymMapGet(m, SYM("while"))       == (void*)n++);
  assert(SymMapGet(m, SYM("_"))           == (void*)n++);
  assert(SymMapGet(m, SYM("int"))         == (void*)n++);

  n = 200;
  SymMapSet(m, SYM("xbreak"),       (void*)n++);
  SymMapSet(m, SYM("xcase"),        (void*)n++);
  SymMapSet(m, SYM("xconst"),       (void*)n++);
  SymMapSet(m, SYM("xcontinue"),    (void*)n++);
  SymMapSet(m, SYM("xdefault"),     (void*)n++);
  SymMapSet(m, SYM("xdefer"),       (void*)n++);
  SymMapSet(m, SYM("xelse"),        (void*)n++);
  SymMapSet(m, SYM("xenum"),        (void*)n++);
  SymMapSet(m, SYM("xfallthrough"), (void*)n++);
  SymMapSet(m, SYM("xfor"),         (void*)n++);
  SymMapSet(m, SYM("xfun"),         (void*)n++);
  SymMapSet(m, SYM("xgo"),          (void*)n++);
  SymMapSet(m, SYM("xif"),          (void*)n++);
  SymMapSet(m, SYM("ximport"),      (void*)n++);
  SymMapSet(m, SYM("xin"),          (void*)n++);
  SymMapSet(m, SYM("xinterface"),   (void*)n++);
  SymMapSet(m, SYM("xis"),          (void*)n++);
  SymMapSet(m, SYM("xreturn"),      (void*)n++);
  SymMapSet(m, SYM("xselect"),      (void*)n++);
  SymMapSet(m, SYM("xstruct"),      (void*)n++);
  SymMapSet(m, SYM("xswitch"),      (void*)n++);
  SymMapSet(m, SYM("xsymbol"),      (void*)n++);
  SymMapSet(m, SYM("xtype"),        (void*)n++);
  SymMapSet(m, SYM("xvar"),         (void*)n++);
  SymMapSet(m, SYM("xwhile"),       (void*)n++);
  SymMapSet(m, SYM("x_"),           (void*)n++);
  SymMapSet(m, SYM("xint"),         (void*)n++);

  n = 200;
  assert(SymMapGet(m, SYM("xbreak"))       == (void*)n++);
  assert(SymMapGet(m, SYM("xcase"))        == (void*)n++);
  assert(SymMapGet(m, SYM("xconst"))       == (void*)n++);
  assert(SymMapGet(m, SYM("xcontinue"))    == (void*)n++);
  assert(SymMapGet(m, SYM("xdefault"))     == (void*)n++);
  assert(SymMapGet(m, SYM("xdefer"))       == (void*)n++);
  assert(SymMapGet(m, SYM("xelse"))        == (void*)n++);
  assert(SymMapGet(m, SYM("xenum"))        == (void*)n++);
  assert(SymMapGet(m, SYM("xfallthrough")) == (void*)n++);
  assert(SymMapGet(m, SYM("xfor"))         == (void*)n++);
  assert(SymMapGet(m, SYM("xfun"))         == (void*)n++);
  assert(SymMapGet(m, SYM("xgo"))          == (void*)n++);
  assert(SymMapGet(m, SYM("xif"))          == (void*)n++);
  assert(SymMapGet(m, SYM("ximport"))      == (void*)n++);
  assert(SymMapGet(m, SYM("xin"))          == (void*)n++);
  assert(SymMapGet(m, SYM("xinterface"))   == (void*)n++);
  assert(SymMapGet(m, SYM("xis"))          == (void*)n++);
  assert(SymMapGet(m, SYM("xreturn"))      == (void*)n++);
  assert(SymMapGet(m, SYM("xselect"))      == (void*)n++);
  assert(SymMapGet(m, SYM("xstruct"))      == (void*)n++);
  assert(SymMapGet(m, SYM("xswitch"))      == (void*)n++);
  assert(SymMapGet(m, SYM("xsymbol"))      == (void*)n++);
  assert(SymMapGet(m, SYM("xtype"))        == (void*)n++);
  assert(SymMapGet(m, SYM("xvar"))         == (void*)n++);
  assert(SymMapGet(m, SYM("xwhile"))       == (void*)n++);
  assert(SymMapGet(m, SYM("x_"))           == (void*)n++);
  assert(SymMapGet(m, SYM("xint"))         == (void*)n++);

  // del
  assert(SymMapSet(m, SYM("hello"), (void*)2) == NULL);
  assert(SymMapGet(m, SYM("hello")) == (void*)2);
  assert(SymMapDel(m, SYM("hello")) == (void*)2);
  assert(SymMapGet(m, SYM("hello")) == NULL);
  assert(SymMapSet(m, SYM("hello"), (void*)2) == NULL);
  assert(SymMapGet(m, SYM("hello")) == (void*)2);

  n = 100;
  assert(SymMapDel(m, SYM("break"))       == (void*)n++);
  assert(SymMapDel(m, SYM("case"))        == (void*)n++);
  assert(SymMapDel(m, SYM("const"))       == (void*)n++);
  assert(SymMapDel(m, SYM("continue"))    == (void*)n++);
  assert(SymMapDel(m, SYM("default"))     == (void*)n++);
  assert(SymMapDel(m, SYM("defer"))       == (void*)n++);
  assert(SymMapDel(m, SYM("else"))        == (void*)n++);
  assert(SymMapDel(m, SYM("enum"))        == (void*)n++);
  assert(SymMapDel(m, SYM("fallthrough")) == (void*)n++);
  assert(SymMapDel(m, SYM("for"))         == (void*)n++);
  assert(SymMapDel(m, SYM("fun"))         == (void*)n++);
  assert(SymMapDel(m, SYM("go"))          == (void*)n++);
  assert(SymMapDel(m, SYM("if"))          == (void*)n++);
  assert(SymMapDel(m, SYM("import"))      == (void*)n++);
  assert(SymMapDel(m, SYM("in"))          == (void*)n++);
  assert(SymMapDel(m, SYM("interface"))   == (void*)n++);
  assert(SymMapDel(m, SYM("is"))          == (void*)n++);
  assert(SymMapDel(m, SYM("return"))      == (void*)n++);
  assert(SymMapDel(m, SYM("select"))      == (void*)n++);
  assert(SymMapDel(m, SYM("struct"))      == (void*)n++);
  assert(SymMapDel(m, SYM("switch"))      == (void*)n++);
  assert(SymMapDel(m, SYM("symbol"))      == (void*)n++);
  assert(SymMapDel(m, SYM("type"))        == (void*)n++);
  assert(SymMapDel(m, SYM("var"))         == (void*)n++);
  assert(SymMapDel(m, SYM("while"))       == (void*)n++);
  assert(SymMapDel(m, SYM("_"))           == (void*)n++);
  assert(SymMapDel(m, SYM("int"))         == (void*)n++);

  assert(SymMapGet(m, SYM("break"))       == 0);
  assert(SymMapGet(m, SYM("case"))        == 0);
  assert(SymMapGet(m, SYM("const"))       == 0);
  assert(SymMapGet(m, SYM("continue"))    == 0);
  assert(SymMapGet(m, SYM("default"))     == 0);
  assert(SymMapGet(m, SYM("defer"))       == 0);
  assert(SymMapGet(m, SYM("else"))        == 0);
  assert(SymMapGet(m, SYM("enum"))        == 0);
  assert(SymMapGet(m, SYM("fallthrough")) == 0);
  assert(SymMapGet(m, SYM("for"))         == 0);
  assert(SymMapGet(m, SYM("fun"))         == 0);
  assert(SymMapGet(m, SYM("go"))          == 0);
  assert(SymMapGet(m, SYM("if"))          == 0);
  assert(SymMapGet(m, SYM("import"))      == 0);
  assert(SymMapGet(m, SYM("in"))          == 0);
  assert(SymMapGet(m, SYM("interface"))   == 0);
  assert(SymMapGet(m, SYM("is"))          == 0);
  assert(SymMapGet(m, SYM("return"))      == 0);
  assert(SymMapGet(m, SYM("select"))      == 0);
  assert(SymMapGet(m, SYM("struct"))      == 0);
  assert(SymMapGet(m, SYM("switch"))      == 0);
  assert(SymMapGet(m, SYM("symbol"))      == 0);
  assert(SymMapGet(m, SYM("type"))        == 0);
  assert(SymMapGet(m, SYM("var"))         == 0);
  assert(SymMapGet(m, SYM("while"))       == 0);
  assert(SymMapGet(m, SYM("_"))           == 0);
  assert(SymMapGet(m, SYM("int"))         == 0);

  SymMapFree(m);
}) // W_UNIT_TEST


// -----------------------------------------------------------------------------------------------

