From 2ebc6746c33024ba8b7147734a360d8411ad1388 Mon Sep 17 00:00:00 2001
From: =?utf8?q?J=C3=A9r=C3=A9mie=20Astor?= <fennecdjay@gmail.com>
Date: Fri, 29 Oct 2021 14:23:28 +0200
Subject: [PATCH] :art: Introduce Dict

---
 ast                      |   2 +-
 fmt                      |   2 +-
 include/emit.h           |   2 +
 include/env/type.h       |   1 +
 include/import.h         |   6 +
 include/instr.h          |   3 +
 include/lang_private.h   |   1 +
 src/clean.c              |   4 +-
 src/emit/emit.c          |  65 +++-
 src/import/import_fdef.c |  11 +-
 src/lib/dict.c           | 669 +++++++++++++++++++++++++++++++++++++++
 src/lib/engine.c         |   2 +
 src/lib/object_op.c      |  31 +-
 src/lib/tmpl_info.c      |   8 +-
 src/parse/check.c        |  63 ++--
 src/parse/scan1.c        |   4 +-
 src/parse/scan2.c        |   4 +-
 src/parse/template.c     |  22 +-
 util                     |   2 +-
 19 files changed, 826 insertions(+), 76 deletions(-)
 create mode 100644 src/lib/dict.c

diff --git a/ast b/ast
index e46922eb..728975ef 160000
--- a/ast
+++ b/ast
@@ -1 +1 @@
-Subproject commit e46922eb0cc11d718e4d50431ac45fbe1f5d386b
+Subproject commit 728975efaa3de381bf11b4b800787b3ebad593a7
diff --git a/fmt b/fmt
index 03d98cb9..35dae816 160000
--- a/fmt
+++ b/fmt
@@ -1 +1 @@
-Subproject commit 03d98cb98e0f51492f1b0e569debc01ddabd2167
+Subproject commit 35dae816a65843488b03d4dce27b1dfa8ddc09ea
diff --git a/include/emit.h b/include/emit.h
index 35656e4d..4e55dce8 100644
--- a/include/emit.h
+++ b/include/emit.h
@@ -107,4 +107,6 @@ ANN static inline m_uint emit_code_size(const Emitter emit) {
 
 ANN void emit_push_scope(const Emitter emit);
 ANN void emit_pop_scope(const Emitter emit);
+
+ANN m_bool ensure_emit(const Emitter, const Type);
 #endif
diff --git a/include/env/type.h b/include/env/type.h
index 7d383e44..6da3ef18 100644
--- a/include/env/type.h
+++ b/include/env/type.h
@@ -140,6 +140,7 @@ typedef enum {
   et_auto,
   et_none,
   et_curry,
+  et_dict,
   MAX_TYPE
 } type_enum;
 #endif
diff --git a/include/import.h b/include/import.h
index 2de834d9..699edd7e 100644
--- a/include/import.h
+++ b/include/import.h
@@ -89,4 +89,10 @@ static inline M_Object new_object_str(const Gwion gwion, const m_str str) {
   DECL_OO(const Type, t, = str2type(gwion, str, loc));
   return new_object(gwion->mp, t);
 }
+
+static inline Type dict_type(const Gwion gwion, const Type key, const Type val, const loc_t pos) {
+   char c[1024];
+   sprintf(c, "Dict:[%s,%s]", key->name, val->name);
+   return str2type(gwion, c, pos);
+}
 #endif
diff --git a/include/instr.h b/include/instr.h
index 141e1e57..e6192120 100644
--- a/include/instr.h
+++ b/include/instr.h
@@ -82,4 +82,7 @@ INSTR(SetCtor);
 INSTR(PutArgsInMem);
 #endif
 #include "opcode.h"
+
+INSTR(dict_ctor_alt);
+INSTR(dict_lit_ctor);
 #endif
diff --git a/include/lang_private.h b/include/lang_private.h
index eb61ce14..734ba68e 100644
--- a/include/lang_private.h
+++ b/include/lang_private.h
@@ -16,4 +16,5 @@ ANN m_bool import_values(const Gwi gwi);
 ANN m_bool import_union(const Gwi gwi);
 ANN m_bool import_ref(const Gwi gwi);
 ANN m_bool import_deep_equal(const Gwi gwi);
+ANN m_bool import_dict(const Gwi gwi);
 #endif
diff --git a/src/clean.c b/src/clean.c
index f3d965b6..a990904d 100644
--- a/src/clean.c
+++ b/src/clean.c
@@ -41,7 +41,7 @@ ANN static void clean_type_decl(Clean *a, Type_Decl *b) {
 }
 
 ANN static void clean_prim(Clean *a, Exp_Primary *b) {
-  if (b->prim_type == ae_prim_hack || b->prim_type == ae_prim_interp)
+  if (b->prim_type == ae_prim_hack || b->prim_type == ae_prim_dict || b->prim_type == ae_prim_interp)
     clean_exp(a, b->d.exp);
   else if (b->prim_type == ae_prim_array)
     clean_array_sub(a, b->d.array);
@@ -271,7 +271,7 @@ ANN static void clean_func_base(Clean *a, Func_Base *b) {
 ANN static void clean_func_def(Clean *a, Func_Def b) {
   clean_func_base(a, b->base);
   ++a->scope;
-  if (b->d.code &&
+  if (!b->builtin && b->d.code &&
       !(b->base->func && safe_vflag(b->base->func->value_ref, vflag_builtin)))
     clean_stmt(a, b->d.code);
   else
diff --git a/src/emit/emit.c b/src/emit/emit.c
index daf2c423..594bdc63 100644
--- a/src/emit/emit.c
+++ b/src/emit/emit.c
@@ -123,7 +123,7 @@ regxxx(pushi, PushImm) regxxx(seti, SetImm);
 ANN static m_bool      emit_class_def(const Emitter, const Class_Def);
 ANN /*static */ m_bool emit_cdef(const Emitter, const Type);
 
-ANN static inline m_bool ensure_emit(const Emitter emit, const Type t) {
+ANN /*static inline*/ m_bool ensure_emit(const Emitter emit, const Type t) {
   if (tflag(t, tflag_emit) || !(tflag(t, tflag_cdef) || tflag(t, tflag_udef)))
     return GW_OK; // clean callers
   struct EnvSet es = {.env   = emit->env,
@@ -172,8 +172,8 @@ ANN static void struct_pop(const Emitter emit, const Type type,
   for (m_uint i = 0; i < vector_size(&type->info->tuple->types); ++i) {
     const Type t = (Type)vector_at(&type->info->tuple->types, i);
     if (isa(t, emit->gwion->type[et_object]) > 0) {
-      const Instr instr = emit_add_instr(emit, ObjectRelease);
-      instr->m_val      = offset + vector_at(&type->info->tuple->offset, i);
+       const Instr instr = emit_add_instr(emit, ObjectRelease);
+       instr->m_val      = offset + vector_at(&type->info->tuple->offset, i);
     } else if (tflag(t, tflag_struct))
       struct_pop(emit, t, offset + vector_at(&type->info->tuple->offset, i));
   }
@@ -663,6 +663,53 @@ ANN static m_bool emit_prim_range(const Emitter emit, Range **data) {
   return GW_OK;
 }
 
+static inline m_uint int2pow2(const m_uint x) {
+	return x == 1 ? 2 : 1<<(64-__builtin_clzl(x));
+}
+
+ANN static m_bool emit_prim_dict(const Emitter emit, Exp *data) {
+  Exp e = *data;
+  const Type  key = e->type;
+  const Type  val = e->next->type;
+  const Type t = dict_type(emit->gwion, key, val, e->pos);
+  const Instr init = emit_add_instr(emit, dict_ctor_alt);
+  struct Exp_ func = { .exp_type = ae_exp_primary, .d = { .prim = { .prim_type = ae_prim_id, .d = { .var = insert_symbol("hash") }} }};
+  m_uint count = 0;
+  CHECK_BB(traverse_exp(emit->env, &func));
+  do {
+    const Exp next = e->next;
+    const Exp nnext = next->next;
+    next->next = NULL;
+    e->next = NULL;
+    CHECK_BB(emit_exp(emit, e));
+    e->next = nnext;
+    CHECK_BB(emit_exp(emit, next));
+    next->next = nnext;
+    if(key->size == SZ_INT) {
+      const Instr instr = emit_add_instr(emit, Reg2Reg);
+      instr->m_val2 = -SZ_INT - val->size;
+      regpush(emit, SZ_INT);
+    } else {
+      const Instr instr = emit_add_instr(emit, Reg2RegOther);
+      instr->m_val  = -key->size;
+      instr->m_val2 = key->size;
+      regpush(emit, key->size);
+    }
+    e->next = next;
+    CHECK_BB(emit_exp(emit, &func));
+    CHECK_BB(emit_exp_call1(emit, func.type->info->func, true));
+    count++;
+  } while((e = e->next->next));
+  init->m_val = int2pow2(count);
+  init->m_val2 = (m_uint)t;
+  const m_uint sz = (key->size + val->size + SZ_INT) * count;
+  regpop(emit, sz);
+  const Instr ctor = emit_add_instr(emit, dict_lit_ctor);
+  ctor->m_val = sz;
+  ctor->m_val2 = count;
+  return GW_OK;
+}
+
 ANN m_bool emit_array_access(const Emitter                 emit,
                              struct ArrayAccessInfo *const info) {
   if (tflag(info->array.type, tflag_typedef)) {
@@ -1812,7 +1859,7 @@ ANN static m_bool emit_exp_unary(const Emitter emit, const Exp_Unary *unary) {
 ANN static m_bool emit_implicit_cast(const Emitter       emit,
                                      const restrict Exp  from,
                                      const restrict Type to) {
-  const struct Implicit imp = {from, to, from->pos};
+  const struct Implicit imp = { .e=from, .t=to, .pos=from->pos};
   // no pos
   struct Op_Import opi = {.op   = insert_symbol("@implicit"),
                           .lhs  = from->type,
@@ -2701,7 +2748,10 @@ ANN static VM_Code emit_func_def_code(const Emitter emit, const Func func) {
 ANN static m_bool emit_func_def_body(const Emitter emit, const Func_Def fdef) {
   if (fdef->base->args) emit_func_def_args(emit, fdef->base->args);
   if (fbflag(fdef->base, fbflag_variadic)) stack_alloc(emit);
-  if (fdef->d.code) CHECK_BB(scoped_stmt(emit, fdef->d.code, 1));
+  if (fdef->d.code) {
+    if(!fdef->builtin) CHECK_BB(scoped_stmt(emit, fdef->d.code, 1));
+    else fdef->base->func->code = (VM_Code)vector_at(&fdef->base->func->value_ref->from->owner_class->nspc->vtable, fdef->base->func->vt_index);
+  }
   return GW_OK;
 }
 
@@ -2784,6 +2834,11 @@ ANN m_bool _emit_func_def(const Emitter emit, const Func_Def f) {
   if (func->code || tmpl_base(fdef->base->tmpl) || fflag(func, fflag_emit))
     return GW_OK;
   set_fflag(func, fflag_emit);
+  if(fdef->builtin)  {
+    fdef->base->func->code = new_vmcode(emit->gwion->mp, NULL, NULL, func->name, fdef->stack_depth, true, false);
+    fdef->base->func->code->native_func = (m_uint)fdef->d.dl_func_ptr;
+    return GW_OK;
+  }
   if ((vflag(func->value_ref, vflag_builtin) &&
       safe_tflag(emit->env->class_def, tflag_tmpl)) || (fdef->base->tmpl && !strcmp(s_name(f->base->xid), "new"))) {
     const Func base =
diff --git a/src/import/import_fdef.c b/src/import/import_fdef.c
index 4dbcc173..234fc378 100644
--- a/src/import/import_fdef.c
+++ b/src/import/import_fdef.c
@@ -82,8 +82,15 @@ ANN static m_bool error_fdef(const Gwi gwi, const Func_Def fdef) {
 
 ANN m_int gwi_func_valid(const Gwi gwi, ImportCK *ck) {
   const Func_Def fdef = import_fdef(gwi, ck);
-  if (safe_tflag(gwi->gwion->env->class_def, tflag_tmpl))
-    return section_fdef(gwi, fdef);
+  fdef->builtin = true;
+  if (safe_tflag(gwi->gwion->env->class_def, tflag_tmpl)) {
+    if(!gwi->gwion->env->class_def->nspc->vtable.ptr)
+      vector_init(&gwi->gwion->env->class_def->nspc->vtable);
+    section_fdef(gwi, fdef);
+    fdef->d.dl_func_ptr = ck->addr;
+//  builtin_func(gwi->gwion->mp, fdef->base->func, ck->addr);
+    return GW_OK;
+  }
   if (traverse_func_def(gwi->gwion->env, fdef) < 0)
     return error_fdef(gwi, fdef);
   builtin_func(gwi->gwion->mp, fdef->base->func, ck->addr);
diff --git a/src/lib/dict.c b/src/lib/dict.c
new file mode 100644
index 00000000..6a08440a
--- /dev/null
+++ b/src/lib/dict.c
@@ -0,0 +1,669 @@
+#include <stdlib.h>
+#include <string.h>
+#include "gwion_util.h"
+#include "gwion_ast.h"
+#include "gwion_env.h"
+#include "vm.h"
+#include "gwion.h"
+#include "instr.h"
+#include "object.h"
+#include "operator.h"
+#include "import.h"
+#include "emit.h"
+#include "traverse.h"
+#include "parse.h"
+#include "gwi.h"
+#include "tmpl_info.h"
+#include "array.h"
+
+#define HMAP_MIN_CAP 32
+#define HMAP_MAX_LOAD 0.75
+
+typedef struct HState {
+  bool set;
+  bool deleted;
+} HState;
+
+typedef struct HMap {
+  m_bit  *state;
+  m_bit  *data;
+  m_uint  key_size;
+  m_uint  val_size;
+  m_uint  capacity;
+  m_uint  count;
+} HMap;
+
+enum HMapKind {
+  HKIND_NONE,
+  HKIND_OBJ,
+  HKIND_STRUCT
+};
+
+struct HMapInfo;
+typedef void (clear_fn)(const HMap*, const VM_Shred, const struct HMapInfo*, const m_uint);
+
+typedef struct HMapInfo {
+  Type key;
+  Type val;
+  m_uint sz;
+  enum HMapKind keyk;
+  enum HMapKind valk;
+} HMapInfo;
+
+// TODO: arch sensible hash
+static SFUN(mfun_int_h) {
+  m_int x = *(m_uint*)MEM(0);
+  x = (x ^ (x >> 30)) * UINT64_C(0xbf58476d1ce4e5b9);
+  x = (x ^ (x >> 27)) * UINT64_C(0x94d049bb133111eb);
+  x = x ^ (x >> 31);
+  *(m_int*) RETURN = x;
+}
+
+static SFUN(mfun_float_h) {
+  char c[1024];
+  snprintf(c, 1024, "%f",  *(m_float*)MEM(0));
+  *(m_uint*)RETURN = hash(c);
+}
+
+static SFUN(mfun_string_h) {
+  *(m_int*)RETURN = hash(STRING(MEM(0)));
+}
+
+ANN static void clear_oo(const HMap *a, const VM_Shred shred, const HMapInfo *info NUSED, const m_uint idx) {
+  release(*(M_Object*)(a->data + idx * SZ_INT*2), shred);
+  release(*(M_Object*)((a->data + idx * SZ_INT*2) + SZ_INT), shred);
+}
+
+ANN static void clear_ss(const HMap *a, const VM_Shred shred, const HMapInfo *info, const m_uint idx) {
+  struct_release(shred, info->key, a->data + idx * info->sz);
+  struct_release(shred, info->val, a->data + idx * info->sz + info->key->size);
+}
+
+ANN static void clear_os(const HMap *a, const VM_Shred shred, const HMapInfo *info, const m_uint idx) {
+  release(*(M_Object*)(a->data + idx * info->sz), shred);
+  struct_release(shred, info->val, a->data + idx * info->sz + SZ_INT);
+}
+
+ANN static void clear_so(const HMap *a, const VM_Shred shred, const HMapInfo *info, const m_uint idx) {
+  struct_release(shred, info->key, a->data + idx * info->sz);
+  release(*(M_Object*)(a->data + idx * info->sz + info->key->size), shred);
+}
+
+ANN static void clear_on(const HMap *a, const VM_Shred shred, const HMapInfo *info, const m_uint idx) {
+  release(*(M_Object*)(a->data + idx * info->sz), shred);
+}
+
+ANN static void clear_sn(const HMap *a, const VM_Shred shred, const HMapInfo *info, const m_uint idx) {
+  struct_release(shred, info->key, a->data + idx * info->sz);
+}
+
+ANN static void clear_no(const HMap *a, const VM_Shred shred, const HMapInfo *info, const m_uint idx) {
+  release(*(M_Object*)(a->data + idx * info->sz + info->key->size), shred);
+}
+
+
+ANN static void clear_ns(const HMap *a, const VM_Shred shred, const HMapInfo *info, const m_uint idx) {
+  struct_release(shred, info->val, a->data + idx * info->sz + info->key->size);
+}
+
+static clear_fn *const n_clear[3]  = { NULL,     clear_no, clear_ns };
+static clear_fn* o_clear[3]  = { clear_on, clear_oo, clear_os };
+static clear_fn* s_clear[3]  = { clear_sn, clear_so, clear_ss };
+static clear_fn*const* clear[3] = { n_clear, o_clear, s_clear };
+
+ANN static void hmapinfo_init(HMapInfo *const info, const Type types[], const Type key, const Type val) {
+  info->key = key;
+  info->val = val;
+  info->sz = key->size + val->size;
+  info->keyk = isa(key, types[et_compound]) > 0 + tflag(key, tflag_struct);
+  info->valk = isa(val, types[et_compound]) > 0 + tflag(val, tflag_struct);
+}
+
+static DTOR(dict_clear_dtor) {
+  const HMapInfo *hinfo = (HMapInfo*)o->type_ref->nspc->class_data;
+  clear_fn *fn = clear[hinfo->keyk][hinfo->valk];
+  HMap *a = &*(struct HMap*)o->data;
+  for(m_uint i = a->capacity; --i;) {
+    const HState state = *(HState*)(a->state + (i-1) * sizeof(HState));
+    if(!state.set || state.deleted) continue;
+    fn(a, shred, hinfo, i-1);
+  }
+}
+
+INSTR(dict_ctor_alt) {
+  const Type t = (Type)instr->m_val2;
+  const M_Object o = new_object(shred->info->mp, t);
+  const HMapInfo *hinfo = (HMapInfo*)t->nspc->class_data;
+  HMap *a = &*(struct HMap*)o->data;
+  a->key_size = hinfo->key->size;
+  a->val_size = hinfo->val->size;
+  a->data  = (m_bit*)mp_calloc2(shred->info->mp, hinfo->sz * instr->m_val);
+  a->state = (m_bit*)mp_calloc2(shred->info->mp, sizeof(HState) * instr->m_val);
+  a->capacity = instr->m_val;
+  shred->reg += SZ_INT;
+  *(M_Object*)REG(-SZ_INT) = o;
+}
+
+INSTR(dict_lit_ctor) {
+  const M_Object o = *(M_Object*)REG(-SZ_INT);
+  const HMapInfo *hinfo = (HMapInfo*)o->type_ref->nspc->class_data;
+  HMap *hmap = &*(struct HMap*)o->data;
+  for(m_uint i = 0; i < instr->m_val; i += hinfo->sz + SZ_INT) {
+    m_uint hash = *(m_uint*)REG(i + hinfo->sz) % hmap->capacity;
+    while(true) {
+      HState *const state = (HState*)(hmap->state + hash * sizeof(HState));
+      if(!state->set) {
+        m_bit *const data = hmap->data + hinfo->sz * hash;
+        memcpy(data, REG(i), hinfo->sz);
+        state->set = true;
+        break;
+      }
+      if(++hash >= hmap->capacity)
+        hash = 0;
+    }
+  }
+  hmap->count = instr->m_val2;
+}
+
+static CTOR(dict_ctor) {
+  const HMapInfo *hinfo = (HMapInfo*)o->type_ref->nspc->class_data;
+  HMap *a = &*(struct HMap*)o->data;
+  a->key_size = hinfo->key->size;
+  a->val_size = hinfo->val->size;
+  a->data  = (m_bit*)mp_calloc2(shred->info->mp, hinfo->sz * HMAP_MIN_CAP);
+  a->state = (m_bit*)mp_calloc2(shred->info->mp, sizeof(HState) * HMAP_MIN_CAP);
+  a->capacity = HMAP_MIN_CAP;
+  a->count    = 0;
+}
+
+static DTOR(dict_dtor) {
+  HMap *a = &*(struct HMap*)o->data;
+  const HMapInfo *hinfo = (HMapInfo*)o->type_ref->nspc->class_data;
+  mp_free2(shred->info->mp, hinfo->sz * a->capacity, a->data);
+  mp_free2(shred->info->mp, sizeof(HState) * a->capacity, a->state);
+}
+
+// bound the hash
+// could be put in next func
+static INSTR(hmap_iter_set_ini) {
+  const M_Object o = *(M_Object*)(shred->reg - SZ_INT*2 - instr->m_val);
+  const HMap *hmap = (HMap*)o->data;
+  const size_t h =  *(m_uint*)REG(-SZ_INT - instr->m_val);
+  if(h >= hmap->capacity)
+    *(m_uint*)REG(-SZ_INT - instr->m_val) = h % hmap->capacity;
+}
+
+static INSTR(hmpa_set_inc) {
+  (*(m_uint*)REG(-SZ_INT - instr->m_val))++;
+}
+
+static INSTR(hmap_iter_set) {
+  const M_Object o = *(M_Object*)(shred->reg - SZ_INT*2 - instr->m_val);
+  HMap *const hmap = (HMap*)o->data;
+  const HMapInfo *hinfo = (HMapInfo*)o->type_ref->nspc->class_data;
+  const size_t bucket =  *(m_uint*)REG(-SZ_INT - instr->m_val);
+  HState *const state = (HState*)(hmap->state + sizeof(HState) * bucket);
+  m_bit *const data = hmap->data + hinfo->sz * bucket;
+  if (!state->set || state->deleted) {
+
+    if(hinfo->keyk) {
+      if(hinfo->keyk == HKIND_OBJ)
+        (*(M_Object*)REG(-instr->m_val))->ref++;
+      else
+        struct_addref(shred->info->vm->gwion, hinfo->key, REG(-instr->m_val));
+    }
+
+    state->set     = true;
+    state->deleted = false;
+    memcpy(data, REG(-instr->m_val), instr->m_val);
+    POP_REG(shred, instr->m_val);
+    *(m_bit**)REG(-SZ_INT*2) = data + hmap->key_size;
+    *(m_uint*)REG(-SZ_INT) = 1;
+    hmap->count++;
+  } else {
+    memcpy(REG(0), data, hmap->key_size);
+    shred->reg += SZ_INT + hmap->key_size;
+    *(m_uint**)REG(-SZ_INT) = 0;
+  }
+}
+
+static INSTR(hmap_iter_inc) {
+  (*(m_uint*)(shred->reg - SZ_INT))++;
+}
+
+static INSTR(hmap_iter) {
+  const M_Object o = *(M_Object*)(shred->reg - SZ_INT*3);
+  const HMap *hmap = (HMap*)o->data;
+  const HMapInfo *hinfo = (HMapInfo*)o->type_ref->nspc->class_data;
+  size_t bucket =  *(m_uint*)(shred->reg - SZ_INT) % hmap->capacity;
+  const HState *state = (HState*)(hmap->state + sizeof(HState) * bucket);
+  if (state->set) {
+    const m_bit *data = hmap->data + hinfo->sz * bucket;
+    m_int *const tombstone = (m_int*)(shred->reg - SZ_INT*2);
+    if (state->deleted && *tombstone == -1) {
+      *tombstone = bucket++;
+    }
+    *(m_uint*)(shred->reg - SZ_INT) = bucket;
+    memcpy(REG(0), data, hmap->key_size);
+    shred->reg += hmap->key_size;
+    return;
+  }
+  handle(shred, "InvalidMapAccess");
+}
+
+static inline size_t grow(size_t c) { return c * 2; }
+
+static INSTR(hmap_grow) {
+  const M_Object o = *(M_Object*)(shred->reg - SZ_INT);
+  const HMap *hmap = (HMap*)o->data;
+  *(m_uint*)REG(0) = (hmap->count + 1) > (hmap->capacity * HMAP_MAX_LOAD);
+  PUSH_REG(shred, SZ_INT);
+}
+
+static INSTR(hmap_grow_init) {
+  const M_Object o = *(M_Object*)(shred->reg - SZ_INT);
+  HMap *const hmap = (HMap*)o->data;
+  const HMapInfo *hinfo = (HMapInfo*)o->type_ref->nspc->class_data;
+  *(m_bit**)REG(0) = hmap->data;
+  *(m_bit**)REG(SZ_INT) = hmap->state;
+  *(m_uint*)REG(SZ_INT*2) = hmap->capacity;
+  hmap->capacity *= 2;
+  hmap->count = 0;
+  hmap->state = mp_calloc2(shred->info->mp, hmap->capacity * sizeof(HState));
+  hmap->data = mp_calloc2(shred->info->mp, hmap->capacity * hinfo->sz);
+
+  PUSH_REG(shred, SZ_INT*3);
+}
+
+static INSTR(hmap_grow_dec) {
+  const M_Object o = *(M_Object*)(shred->reg - SZ_INT*4);
+  const HMap *hmap = (HMap*)o->data;
+  const HMapInfo *hinfo = (HMapInfo*)o->type_ref->nspc->class_data;
+  const m_bit *old_data = *(m_bit**)REG(-SZ_INT*3);
+  const m_bit *old_state = *(m_bit**)REG(-SZ_INT*2);
+  while((*(m_uint*)REG(-SZ_INT))--) {
+    const HState *state = (HState *)(old_state + (*(m_uint*)REG(-SZ_INT)) * sizeof(HState));
+    if(!state->set || state->deleted)continue;
+    m_bit *const data   = (m_bit*)(old_data + (*(m_uint*)REG(-SZ_INT)) * hinfo->sz);
+    memcpy(shred->reg + SZ_INT, data, hmap->key_size);
+    PUSH_REG(shred, SZ_INT + hmap->key_size);
+    *(m_uint*)shred->reg = 0;
+    PUSH_REG(shred, SZ_INT);
+    return;
+  }
+  POP_REG(shred, SZ_INT*2);
+  *(m_uint*)(shred->reg -SZ_INT) = 1;
+}
+
+static INSTR(hmap_wtf) {
+  const M_Object o = *(M_Object*)(shred->reg - SZ_INT*6);
+  HMap *const hmap = (HMap*)o->data;
+  const HMapInfo *hinfo = (HMapInfo*)o->type_ref->nspc->class_data;
+  const m_bit *old_data = *(m_bit**)REG(-SZ_INT*5);
+  const m_bit *old_state = *(m_bit**)REG(-SZ_INT*4);
+  const m_uint h = *(m_uint*)REG(-SZ_INT);
+  const m_uint idx = *(m_uint*)REG(-SZ_INT*3);
+  m_uint bucket = h % hmap->capacity;
+  while(true) {
+    HState *const state = (HState *)(hmap->state + bucket * sizeof(HState));
+    if(!state->set) {
+      const HState *prev_state = (HState *)(old_state + idx * sizeof(HState));
+      memcpy(state, prev_state, sizeof(HState));
+      m_bit *const data = hmap->data + bucket * hinfo->sz;
+      const m_bit *prev_data = old_data + idx * hinfo->sz;
+      memcpy(data, prev_data, hinfo->sz);
+      hmap->count++;
+      break;
+    }
+    if(++bucket > hmap->capacity)
+      bucket = 0;
+  }
+  if(!idx)
+    POP_REG(shred, SZ_INT*4 - instr->m_val)
+  else
+    POP_REG(shred, SZ_INT)
+  *(m_uint*)REG(-SZ_INT) = !idx;
+}
+
+static INSTR(hmap_addr) {
+  const M_Object o = *(M_Object*)(shred->reg - SZ_INT*2 - instr->m_val);
+  const HMap *hmap = (HMap*)o->data;
+  const HMapInfo *hinfo = (HMapInfo*)o->type_ref->nspc->class_data;
+  POP_REG(shred, SZ_INT + instr->m_val);
+  const m_uint bucket = *(m_uint*)REG(0);
+  *(HState *)(hmap->state + bucket * sizeof(HState)) = (HState) { true, false };
+  *(m_bit**)REG(-SZ_INT) = hmap->data + hinfo->sz * bucket + hinfo->key->size;
+}
+
+static INSTR(hmap_val) {
+  const M_Object o = *(M_Object*)(shred->reg - SZ_INT*2);
+  const HMap *hmap = (HMap*)o->data;
+  const HMapInfo *hinfo = (HMapInfo*)o->type_ref->nspc->class_data;
+  const m_uint bucket = *(m_uint*)REG(0);
+  const m_bit *new_data = hmap->data + hinfo->sz * bucket;
+
+  const m_int tombstone = *(m_int*)(shred->reg - SZ_INT);
+  if (tombstone != -1) {
+    m_bit  *const old_data = hmap->data + (hmap->key_size + hmap->val_size) * tombstone;
+    HState *const old_state = (HState*)(hmap->state + sizeof(HState) * tombstone);
+    HState *const new_state = (HState*)(hmap->state + sizeof(HState) * bucket);
+    memcpy(old_state, new_state, sizeof(HState));
+    memcpy(old_data, new_data, hinfo->sz);
+    new_state->deleted = true;
+  }
+
+  shred->reg -= SZ_INT*2 - hmap->val_size;
+  memcpy(REG(-hmap->val_size), new_data + hmap->key_size, hmap->val_size);
+}
+
+static INSTR(hmap_remove_clear) {
+  const M_Object o = *(M_Object*)(shred->reg - SZ_INT*2);
+  const HMap *hmap = (HMap*)o->data;
+  const HMapInfo *hinfo = (HMapInfo*)o->type_ref->nspc->class_data;
+  const m_uint bucket = *(m_uint*)REG(0);
+  clear_fn *fn = (clear_fn*)instr->m_val;
+  fn(hmap, shred, hinfo, bucket);
+}
+
+static INSTR(hmap_remove) {
+  const M_Object o = *(M_Object*)(shred->reg - SZ_INT*2);
+  const HMap *hmap = (HMap*)o->data;
+  const HMapInfo *hinfo = (HMapInfo*)o->type_ref->nspc->class_data;
+  const m_uint bucket = *(m_uint*)REG(0);
+  m_bit *data = hmap->data + hinfo->sz * bucket;
+  HState *const state = (HState *)(hmap->state + bucket * sizeof(HState));
+  state->deleted = true;
+  shred->reg -= SZ_INT*3 - hmap->val_size;
+  memcpy(REG(-hmap->val_size), data + hmap->key_size, hmap->val_size);
+}
+
+static OP_CHECK(opck_dict_remove_toop) {
+  const Exp       e    = (Exp)data;
+  const Exp_Call *call = &e->d.exp_call;
+  const Exp       func  = call->func;
+  const Exp       args  = call->args;
+  e->exp_type         = ae_exp_binary;
+  CHECK_OO(check_exp(env, e->d.exp_binary.rhs = cpy_exp(env->gwion->mp, func->d.exp_dot.base)));
+  CHECK_OO(check_exp(env, e->d.exp_binary.lhs = args));
+  e->d.exp_binary.op = insert_symbol("~~");
+  free_exp(env->gwion->mp, func);
+  const Type t = e->d.exp_binary.rhs->type;
+  HMapInfo *const hinfo = (HMapInfo*)t->nspc->class_data;
+  if(isa(args->type, hinfo->key) < 0 || args->next)
+    ERR_N(e->pos, "dict.remove must be called with one Key argument");
+  return e->type = hinfo->val;
+}
+
+static OP_EMIT(_opem_dict_access) {
+  struct ArrayAccessInfo *const info = (struct ArrayAccessInfo *const)data;
+  Array_Sub array = &info->array;
+  const Env env = emit->env;
+  const Type key = *(Type*)array->type->nspc->class_data;
+
+  struct Exp_ func = { .exp_type = ae_exp_primary, .d = { .prim = { .prim_type = ae_prim_id, .d = { .var = insert_symbol("hash") }} }};
+
+  struct Exp_ call = {
+   .exp_type = ae_exp_call,
+   .d = {
+     .exp_call = {
+       .func = &func,
+       .args = array->exp // beware next
+     }
+   }
+};
+struct Exp_ lhs = { .exp_type = ae_exp_primary, .type = key, .d = { .prim = { .prim_type = ae_prim_id } }};
+struct Exp_ rhs = { .exp_type = ae_exp_primary, .type = key, .d = { .prim = { .prim_type = ae_prim_id } }};
+struct Exp_ bin = { .exp_type = ae_exp_binary, .d = { .exp_binary = { .lhs = &lhs, .rhs = &rhs, .op = insert_symbol("?=") } }};
+struct Op_Import opi = {
+  .lhs = key,
+  .rhs = key,
+//  .op  = insert_symbol("=="),
+  .op  = bin.d.exp_binary.op,
+  .data = (m_uint)&bin
+};
+
+
+CHECK_BB(traverse_exp(env, &call));
+if(info->is_var) {
+
+  const Instr instr = emit_add_instr(emit, hmap_grow);
+  instr->m_val = key->size;
+  const Instr nogrow = emit_add_instr(emit, BranchEqInt);
+  emit_add_instr(emit, hmap_grow_init);
+  const m_uint grow_pc = emit_code_size(emit);
+  emit_add_instr(emit, hmap_grow_dec);
+  const Instr endgrow = emit_add_instr(emit, BranchNeqInt);
+  emit_exp(emit, call.d.exp_call.func);
+  emit_exp_call1(emit, call.d.exp_call.func->type->info->func, true);
+  emit_add_instr(emit, hmap_wtf);
+  const Instr regrow = emit_add_instr(emit, BranchEqInt);
+  regrow->m_val = grow_pc;
+  nogrow->m_val = emit_code_size(emit);
+  endgrow->m_val = emit_code_size(emit);
+  CHECK_BB(emit_exp(emit, &call));
+  CHECK_BB(emit_exp(emit, array->exp));
+  const m_uint top_pc = emit_code_size(emit);
+  const Instr idx = emit_add_instr(emit, hmap_iter_set_ini);
+  idx->m_val = key->size;
+
+
+  const Instr iter = emit_add_instr(emit, hmap_iter_set);
+  iter->m_val = key->size;
+  const Instr fast = emit_add_instr(emit, BranchNeqInt);
+  CHECK_BB(emit_exp(emit, array->exp));
+  op_emit(emit, &opi);
+
+  const Instr ok = emit_add_instr(emit, BranchNeqInt);
+  const Instr inc = emit_add_instr(emit, hmpa_set_inc);
+  inc->m_val = key->size;
+  const Instr not_ok = emit_add_instr(emit, Goto);
+  not_ok->m_val = top_pc;
+  ok->m_val = emit_code_size(emit);
+
+//  if(isa(val, emit->gwion->type[et_compound]) > 0) exit(3);
+  const Instr iseq = emit_add_instr(emit, hmap_addr);
+  iseq->m_val = key->size;
+  fast->m_val = emit_code_size(emit);
+  return GW_OK;
+}
+  const Instr room_for_tombstone = emit_add_instr(emit, RegPushImm);
+  room_for_tombstone->m_val = -1;
+  CHECK_BB(emit_exp(emit, &call));
+  const m_uint pc = emit_code_size(emit);
+  const Instr iter = emit_add_instr(emit, hmap_iter);
+  iter->m_val = key->size + SZ_INT;
+  CHECK_BB(emit_exp(emit, array->exp));
+  op_emit(emit, &opi);
+  const Instr ok = emit_add_instr(emit, BranchNeqInt);
+  emit_add_instr(emit, hmap_iter_inc);
+  const Instr top = emit_add_instr(emit, Goto);
+  top->m_val = pc;
+  ok->m_val = emit_code_size(emit);
+  const Instr _pop = emit_add_instr(emit, RegMove);
+  _pop->m_val = -SZ_INT;// - key->size;
+  const Instr pushval = emit_add_instr(emit, hmap_val);
+  pushval->m_val2 = key->size;
+  return GW_OK;
+}
+
+static OP_EMIT(opem_dict_remove) {
+  Exp_Binary *bin = (Exp_Binary*)data;
+  const Env env = emit->env;
+  struct Exp_ func = { .exp_type = ae_exp_primary, .d = { .prim = { .prim_type = ae_prim_id, .d = { .var = insert_symbol("hash") }} }};
+
+  struct Exp_ call = {
+    .exp_type = ae_exp_call,
+    .d = {
+      .exp_call = {
+        .func = &func,
+        .args = bin->lhs // beware next
+      }
+    }
+  };
+  const Type t = bin->rhs->type;
+  HMapInfo *const hinfo = (HMapInfo*)t->nspc->class_data;
+
+  struct Exp_ lhs = { .exp_type = ae_exp_primary, .type = hinfo->key, .d = { .prim = { .prim_type = ae_prim_id } }};
+  struct Exp_ rhs = { .exp_type = ae_exp_primary, .type = hinfo->key, .d = { .prim = { .prim_type = ae_prim_id } }};
+  struct Exp_ _bin = { .exp_type = ae_exp_binary, .d = { .exp_binary = { .lhs = &lhs, .rhs = &rhs, .op = insert_symbol("?=") } }};
+  struct Op_Import opi = {
+    .lhs = hinfo->key,
+    .rhs = hinfo->key,
+    .op  = _bin.d.exp_binary.op,
+    .data = (m_uint)&_bin
+  };
+
+  CHECK_BB(traverse_exp(env, &call));
+//
+  const Instr room_for_tombstone = emit_add_instr(emit, RegPushImm);
+  room_for_tombstone->m_val = -1;
+
+  CHECK_BB(emit_exp(emit, &call));
+  const m_uint pc = emit_code_size(emit);
+  const Instr iter = emit_add_instr(emit, hmap_iter);
+  iter->m_val = hinfo->key->size;
+  CHECK_BB(emit_exp(emit, bin->lhs));
+  op_emit(emit, &opi);
+  const Instr ok = emit_add_instr(emit, BranchNeqInt);
+  emit_add_instr(emit, hmap_iter_inc);
+  const Instr top = emit_add_instr(emit, Goto);
+  top->m_val = pc;
+  ok->m_val = emit_code_size(emit);
+  const Instr _pop = emit_add_instr(emit, RegMove);
+  _pop->m_val = -SZ_INT;// - key->size;
+//
+  if(hinfo->keyk || hinfo->valk) {
+    clear_fn *const fn = clear[hinfo->keyk][hinfo->valk];
+    const Instr clear = emit_add_instr(emit, hmap_remove_clear);
+    clear->m_val = (m_uint)fn;
+  }
+
+  const Instr pushval = emit_add_instr(emit, hmap_remove);
+  pushval->m_val2 = hinfo->key->size;
+  return GW_OK;
+
+//  exit(3);
+}
+
+ANN static m_bool emit_next_access(const Emitter emit, struct ArrayAccessInfo *const info) {
+  const struct Array_Sub_ array = info->array;
+  HMapInfo *const hinfo = (HMapInfo*)info->array.type->nspc->class_data;
+  info->array = (struct Array_Sub_){
+    .exp   = array.exp->next,
+    .type  = hinfo->val,
+    .depth = array.depth - 1
+  };
+  return emit_array_access(emit, info);
+}
+
+static OP_EMIT(opem_dict_access) {
+  struct ArrayAccessInfo *const info = (struct ArrayAccessInfo *const)data;
+  const Array_Sub array = &info->array;
+  const Exp enext = array->exp->next;
+  array->exp->next = NULL;
+  _opem_dict_access(emit, data);
+  array->exp->next = enext;
+  return !enext ? GW_OK : emit_next_access(emit, info);
+}
+
+static OP_CHECK(opck_dict_access) {
+  const Array_Sub array = (Array_Sub)data;
+  HMapInfo *const hinfo = (HMapInfo*)array->type->nspc->class_data;
+  if(!array->exp->next) return hinfo->val;
+  struct Array_Sub_ next = { array->exp->next, hinfo->val,
+                            array->depth - 1};
+  return check_array_access(env, &next) ?: env->gwion->type[et_error];
+}
+
+static OP_CHECK(opck_dict_scan) {
+  struct TemplateScan *ts   = (struct TemplateScan *)data;
+  struct tmpl_info     info = {
+      .base = ts->t, .td = ts->td, .list = ts->t->info->cdef->base.tmpl->list};
+  const Type  exists = tmpl_exists(env, &info);
+  if (exists) return exists != env->gwion->type[et_error] ? exists : NULL;
+  CHECK_ON(ts->td->types);
+  DECL_ON(const Type, key, = known_type(env, ts->td->types->td));
+  CHECK_ON(ts->td->types->next);
+  DECL_ON(const Type, val, = known_type(env, ts->td->types->next->td));
+  if(tflag(key, tflag_ref) || tflag(val, tflag_ref))
+    ERR_N(ts->td->pos, "can't use Ref:[] in dicts");
+  const Class_Def cdef  = cpy_class_def(env->gwion->mp, env->gwion->type[et_dict]->info->cdef);
+  cdef->base.ext        = type2td(env->gwion, env->gwion->type[et_dict], (loc_t) {});
+  cdef->base.xid        = info.name;
+  cdef->base.tmpl->base = 1; // could store depth here?
+  cdef->base.tmpl->call = cpy_type_list(env->gwion->mp, info.td->types);
+
+  (void)scan0_class_def(env, cdef);
+  const Type   t   = cdef->base.type;
+  t->nspc->class_data_size = sizeof(struct HMapInfo);
+  const m_bool ret = traverse_cdef(env, t);
+  HMapInfo *const hinfo = (HMapInfo*)t->nspc->class_data;
+  hmapinfo_init(hinfo, env->gwion->type, key, val);
+  if(hinfo->keyk + hinfo->valk) {
+    t->nspc->dtor = new_vmcode(env->gwion->mp, NULL, NULL, "@dtor", SZ_INT, true, false);
+    t->nspc->dtor->native_func = (m_uint)dict_clear_dtor;
+    set_tflag(t, tflag_dtor);
+  }
+  struct Op_Func opfunc = { .ck = opck_dict_access, .em = opem_dict_access };
+  struct Op_Import opi = { .lhs = key, .rhs = t, .ret = val, .op = insert_symbol("@array"), .func = &opfunc };
+  add_op(env->gwion, &opi);
+  opi.op = insert_symbol("~~");
+  opfunc.em = opem_dict_remove;
+  add_op(env->gwion, &opi);
+
+  {
+  const Func             f      = (Func)vector_front(&t->nspc->vtable);
+  const struct Op_Func   opfunc = {.ck = opck_dict_remove_toop};
+  const struct Op_Import opi    = {
+      .rhs  = f->value_ref->type,
+      .func = &opfunc,
+      .data = (uintptr_t)f,
+      .op   = insert_symbol("@func_check")};
+  CHECK_BN(add_op(env->gwion, &opi));
+
+  }
+
+  return ret > 0 ? t : NULL;
+//  return t;
+}
+
+GWION_IMPORT(dict) {
+//  gwidoc(gwi, "Ref: take a reference from a variable.");
+//  gwinote(gwi, "used just as the variable it reference.");
+//  gwinote(gwi, "can only be used as argument.");
+//  gwinote(gwi, "and cannot be returned.");
+
+
+  DECL_OB(const Type, t_dict, = gwi_class_ini(gwi, "Dict:[Key,Val]", "Object"));
+  gwi_class_xtor(gwi, dict_ctor, dict_dtor);
+  t_dict->nspc->offset += sizeof(struct HMap);
+  gwi->gwion->type[et_dict] = t_dict;
+
+  GWI_BB(gwi_func_ini(gwi, "bool",   "remove"));
+  GWI_BB(gwi_func_arg(gwi, "Key",    "key"));
+  GWI_BB(gwi_func_end(gwi, (f_xfun)1, ae_flag_none));
+
+  GWI_BB(gwi_class_end(gwi))
+
+  GWI_BB(gwi_oper_ini(gwi, "Dict", NULL, NULL))
+  GWI_BB(gwi_oper_add(gwi, opck_dict_scan))
+  GWI_BB(gwi_oper_end(gwi, "@scan", NULL))
+
+  GWI_BB(gwi_func_ini(gwi, "int",    "hash"));
+  GWI_BB(gwi_func_arg(gwi, "int",    "key"));
+  GWI_BB(gwi_func_end(gwi, mfun_int_h, ae_flag_none));
+
+  GWI_BB(gwi_func_ini(gwi, "int",    "hash"));
+  GWI_BB(gwi_func_arg(gwi, "Object",    "key"));
+  GWI_BB(gwi_func_end(gwi, mfun_int_h, ae_flag_none));
+
+  GWI_BB(gwi_func_ini(gwi, "int",    "hash"));
+  GWI_BB(gwi_func_arg(gwi, "float",    "key"));
+  GWI_BB(gwi_func_end(gwi, mfun_float_h, ae_flag_none));
+
+  GWI_BB(gwi_func_ini(gwi, "int",    "hash"));
+  GWI_BB(gwi_func_arg(gwi, "string",    "key"));
+  GWI_BB(gwi_func_end(gwi, mfun_string_h, ae_flag_none));
+
+  return GW_OK;
+}
diff --git a/src/lib/engine.c b/src/lib/engine.c
index 9ee335c7..bd8d8c2e 100644
--- a/src/lib/engine.c
+++ b/src/lib/engine.c
@@ -231,6 +231,8 @@ ANN static m_bool import_core_libs(const Gwi gwi) {
 
   GWI_BB(import_deep_equal(gwi));
 
+  GWI_BB(import_dict(gwi));
+
 gwi_enum_ini(gwi, "@hidden_enum");
 gwi_enum_add(gwi, "@hidden_enum", 0);
 gwi_enum_end(gwi);
diff --git a/src/lib/object_op.c b/src/lib/object_op.c
index 721f94a8..13997249 100644
--- a/src/lib/object_op.c
+++ b/src/lib/object_op.c
@@ -79,18 +79,9 @@ static OP_CHECK(opck_object_cast) {
 ANN /*static*/ Type scan_class(const Env env, const Type t,
                                const Type_Decl *td);
 
-static Type opck_object_scan(const Env env, const struct TemplateScan *ts) {
-  if (ts->td->types)
-    return scan_class(env, ts->t, ts->td) ?: env->gwion->type[et_error];
-  Type_Decl *td = (Type_Decl *)ts->td;
-  ERR_N(td->pos, _("you must provide template types for type '%s'"),
-        ts->t->name);
-}
-
 static OP_CHECK(opck_struct_scan) {
   struct TemplateScan *ts = (struct TemplateScan *)data;
-  CHECK_OO(ts->td);
-  return opck_object_scan(env, ts);
+  return scan_class(env, ts->t, ts->td) ?: env->gwion->type[et_error];
 }
 
 ANN static void emit_dot_static_data(const Emitter emit, const Value v,
@@ -199,6 +190,11 @@ OP_CHECK(opck_object_dot) {
           _("keyword 'this' must be associated with object instance..."));
   const Value value = get_value(env, member, the_base);
   if (!value) {
+    if(!tflag(the_base, tflag_check) && env->class_def != the_base) {
+      set_tflag(the_base, tflag_cdef);
+      CHECK_BN(ensure_traverse(env, the_base));
+      return check_exp(env, exp_self(member));
+    }
     const Value v = nspc_lookup_value1(env->curr, member->xid);
     if (v && member->is_call) {
       if (is_func(env->gwion, v->type) && (!v->from->owner_class || isa(the_base, v->from->owner_class) > 0))
@@ -252,6 +248,9 @@ OP_EMIT(opem_object_dot) {
 //  const Type     t_base = actual_type(emit->gwion, member->base->type);
   const Type     t_base = member_type(emit->gwion, member->base->type);
   const Value    value  = find_value(t_base, member->xid);
+  if(!tflag(t_base, tflag_emit) /*&& emit->env->class_def != t_base*/) {
+      ensure_emit(emit, t_base);
+  }
   if (is_class(emit->gwion, value->type)) {
     const Instr instr = emit_add_instr(emit, RegPushImm);
     instr->m_val      = (m_uint)value->type;
@@ -335,6 +334,15 @@ ANN static Type _scan_class(const Env env, struct tmpl_info *info) {
 }
 
 ANN Type tmpl_exists(const Env env, struct tmpl_info *const info);
+
+ANN bool tmpl_global(const Env env, Type_List call) {
+  do {
+    if(!type_global(env, known_type(env, call->td)))
+      return false;
+  } while((call = call->next));
+  return true;
+}
+
 ANN Type scan_class(const Env env, const Type t, const Type_Decl *td) {
   struct tmpl_info info = {
       .base = t, .td = td, .list = t->info->cdef->base.tmpl->list};
@@ -347,7 +355,10 @@ ANN Type scan_class(const Env env, const Type t, const Type_Decl *td) {
                       .flag  = tflag_scan0};
   const Type    owner = t->info->value->from->owner_class;
   CHECK_BO(envset_pushv(&es, t->info->value));
+  const bool local = !owner && !tmpl_global(env, td->types) && from_global_nspc(env, env->curr);
+  if(local)env_push(env, NULL, env->context->nspc);
   const Type ret = _scan_class(env, &info);
+  if(local)env_pop(env, es.scope);
   if (es.run) envset_pop(&es, owner);
   return ret;
 }
diff --git a/src/lib/tmpl_info.c b/src/lib/tmpl_info.c
index a1d17d14..0b88412f 100644
--- a/src/lib/tmpl_info.c
+++ b/src/lib/tmpl_info.c
@@ -79,15 +79,13 @@ ANN static m_bool template_match(Specialized_List base, Type_List call) {
 ANN static Type _tmpl_exists(const Env env, const Symbol name) {
   if (env->class_def && name == insert_symbol(env->class_def->name))
     return env->class_def;
-  return nspc_lookup_type1(env->curr, name);
+  return nspc_lookup_type1(env->curr, name) ?: env->context ?  nspc_lookup_type1(env->context->nspc, name) : NULL;
 }
 
 ANN Type tmpl_exists(const Env env, struct tmpl_info *const info) {
   if (template_match(info->list, info->td->types) < 0) // invalid template
     ERR_N(info->td->pos, _("invalid template types number"));
-  if (!info->name) {
-    DECL_ON(const Symbol, name, = info->name = template_id(env, info));
-    return _tmpl_exists(env, name);
-  }
+  if (!info->name)
+    info->name = template_id(env, info);
   return _tmpl_exists(env, info->name);
 }
diff --git a/src/parse/check.c b/src/parse/check.c
index 9a7429b8..0fb7affb 100644
--- a/src/parse/check.c
+++ b/src/parse/check.c
@@ -126,7 +126,7 @@ ANN static m_bool check_decl(const Env env, const Exp_Decl *decl) {
   return GW_OK;
 }
 
-ANN static inline m_bool ensure_check(const Env env, const Type t) {
+ANN /*static inline*/ m_bool ensure_check(const Env env, const Type t) {
   if (tflag(t, tflag_check) || !(tflag(t, tflag_cdef) || tflag(t, tflag_udef)))
     return GW_OK;
   struct EnvSet es = {.env   = env,
@@ -178,7 +178,7 @@ ANN Type check_exp_decl(const Env env, const Exp_Decl *decl) {
   return ret > 0 ? decl->list->self->value->type : NULL;
 }
 
-ANN static m_bool prim_array_inner(const Env env, Type type, const Exp e,
+ANN static m_bool check_collection(const Env env, Type type, const Exp e,
                                    const loc_t loc) {
   const Type common = find_common_anc(e->type, type);
   if (common) return GW_OK;
@@ -192,7 +192,6 @@ ANN static m_bool prim_array_inner(const Env env, Type type, const Exp e,
   char sec[16 + strlen(e->type->name)];
   sprintf(sec, "got `{+/}%s{0}`", e->type->name);
   gwerr_secondary(sec, env->name, e->pos);
-
   return GW_ERROR;
 }
 
@@ -201,7 +200,7 @@ ANN static inline Type prim_array_match(const Env env, Exp e) {
   bool        err  = false;
   const loc_t loc  = e->pos;
   do
-    if (prim_array_inner(env, type, e, loc) < 0) err = true;
+    if (check_collection(env, type, e, loc) < 0) err = true;
   while ((e = e->next));
   if (!err) return array_type(env, array_base_simple(type), type->array_depth + 1);
   env_set_error(env);
@@ -242,6 +241,24 @@ ANN static Type check_prim_range(const Env env, Range **data) {
   return op_check(env, &opi);
 }
 
+ANN static Type check_prim_dict(const Env env, Exp *data) {
+  const Exp base = *data;
+  CHECK_OO(check_exp(env, base));
+  const Type  key = base->type;
+  const Type  val = base->next->type;
+  bool        err = false;
+  const loc_t loc = base->pos;
+  Exp e = base;
+  env_weight(env, 1);
+  do {
+    if (check_collection(env, key, e, loc) < 0) err = true;
+    e = e->next;
+    if (check_collection(env, val, e, loc) < 0) err = true;
+  } while ((e = e->next));
+  if (!err) return dict_type(env->gwion, key, val, base->pos);
+  env_set_error(env); return NULL;
+}
+
 ANN m_bool not_from_owner_class(const Env env, const Type t, const Value v,
                                 const loc_t pos) {
   if (!v->from->owner_class || isa(t, v->from->owner_class) < 0) {
@@ -393,42 +410,7 @@ ANN static Type check_prim_hack(const Env env, const Exp *data) {
   env_weight(env, 1);
   return env->gwion->type[et_gack];
 }
-/*
-ANN static Type check_prim_map(const Env env, const Exp *data) {
-  CHECK_OO(check_exp(env, *data));
-  if(env->func) // really?
-    unset_fflag(env->func, fflag_pure);
-  bool err = false;
-  Exp key = *data;
-  Exp val = key->next;
-  const Type type_key = key->type;
-  const Type type_val = val->type;
-  const loc_t loc_key = (*data)->pos;
-  const loc_t loc_val = (*data)->next->pos;
-  do {
-    val = key->next;
-    if(prim_array_inner(env, type_key, key, loc_key) < 0)
-      err = true;
-    if(prim_array_inner(env, type_val, val, loc_val) < 0)
-      err = true;
-  } while((key = val->next));
-  if(!err) {
-    Type_Decl *td_key = type2td(env->gwion, type_key, loc_key);
-    Type_Decl *td_val = type2td(env->gwion, type_val, loc_val);
-    struct Type_List_ tl_val = { .td=td_val };
-    struct Type_List_ tl_key = { .td=td_key, .next=&tl_val };
-    Type_Decl td = { .xid=insert_symbol("Map"), .types=&tl_key };
-    const Type t = known_type(env, &td);
-    free_type_decl(env->gwion->mp, td_key);
-    free_type_decl(env->gwion->mp, td_val);
-    ensure_traverse(env, t);
-    prim_exp(data)->type = t;
-    return t;
-  }
-  env_set_error(env);
-  return NULL;
-}
-*/
+
 #define describe_prim_xxx(name, type)                                          \
   ANN static Type check_prim_##name(const Env env               NUSED,         \
                                     const union prim_data *data NUSED) {       \
@@ -1599,6 +1581,7 @@ ANN static m_bool check_func_def_override(const Env env, const Func_Def fdef,
 
 ANN m_bool check_fdef(const Env env, const Func_Def fdef) {
   if (fdef->base->args) CHECK_BB(check_func_args(env, fdef->base->args));
+  if(fdef->builtin) return GW_OK;
   if (fdef->d.code) {
     env->scope->depth--;
     CHECK_BB(check_stmt_code(env, &fdef->d.code->d.stmt_code));
diff --git a/src/parse/scan1.c b/src/parse/scan1.c
index 4637ede9..e1724fd8 100644
--- a/src/parse/scan1.c
+++ b/src/parse/scan1.c
@@ -211,7 +211,7 @@ ANN static m_bool scan1_range(const Env env, Range *range) {
 }
 
 ANN static inline m_bool scan1_prim(const Env env, const Exp_Primary *prim) {
-  if (prim->prim_type == ae_prim_hack || prim->prim_type == ae_prim_interp)
+  if (prim->prim_type == ae_prim_hack || prim->prim_type == ae_prim_dict || prim->prim_type == ae_prim_interp)
     return scan1_exp(env, prim->d.exp);
   if (prim->prim_type == ae_prim_array && prim->d.array->exp)
     return scan1_exp(env, prim->d.array->exp);
@@ -637,7 +637,7 @@ ANN m_bool scan1_fbody(const Env env, const Func_Def fdef) {
     CHECK_BB(scan1_fdef_args(env, fdef->base->args));
     CHECK_BB(scan1_args(env, fdef->base->args));
   }
-  if (fdef->d.code && fdef->d.code->d.stmt_code.stmt_list)
+  if (!fdef->builtin && fdef->d.code && fdef->d.code->d.stmt_code.stmt_list)
     CHECK_BB(scan1_stmt_list(env, fdef->d.code->d.stmt_code.stmt_list));
   return GW_OK;
 }
diff --git a/src/parse/scan2.c b/src/parse/scan2.c
index 344526ea..357e4168 100644
--- a/src/parse/scan2.c
+++ b/src/parse/scan2.c
@@ -101,7 +101,7 @@ ANN static m_bool scan2_range(const Env env, Range *range) {
 }
 
 ANN static inline m_bool scan2_prim(const Env env, const Exp_Primary *prim) {
-  if (prim->prim_type == ae_prim_hack || prim->prim_type == ae_prim_interp)
+  if (prim->prim_type == ae_prim_hack || prim->prim_type == ae_prim_dict || prim->prim_type == ae_prim_interp)
     CHECK_BB(scan2_exp(env, prim->d.exp));
   /*  else if(prim->prim_type == ae_prim_id) {
       const Value v = prim_value(env, prim->d.var);
@@ -497,7 +497,7 @@ m_bool scan2_fdef_std(const Env env, const Func_Def f, const Value overload) {
   else
     f->base->func = base;
   if (f->base->args) CHECK_BB(scan2_args(f));
-  if (f->d.code) CHECK_BB(scan2_func_def_code(env, f));
+  if (!f->builtin && f->d.code) CHECK_BB(scan2_func_def_code(env, f));
   if (!base) {
     if (fbflag(f->base, fbflag_op)) CHECK_BB(scan2_func_def_op(env, f));
     set_vflag(f->base->func->value_ref, vflag_valid);
diff --git a/src/parse/template.c b/src/parse/template.c
index 80e76556..0a72a547 100644
--- a/src/parse/template.c
+++ b/src/parse/template.c
@@ -27,12 +27,16 @@ ANN static m_bool _push_types(const Env env, const Nspc nspc,
 }
 
 ANN static m_bool push_types(const Env env, const Nspc nspc, const Tmpl *tmpl) {
-  if (nspc->parent) env->curr = env->curr->parent;
   const Type t = env->class_def;
-  if (t) env->class_def = t->info->value->from->owner_class;
+  if (t) {
+    env->class_def = t->info->value->from->owner_class;
+    env->curr = t->info->value->from->owner;
+  }
   const m_bool ret = _push_types(env, nspc, tmpl);
-  if (nspc->parent) env->curr = nspc;
-  env->class_def = t;
+  if (t) {
+    env->class_def = t;
+    env->curr = t->nspc;
+  }
   return ret;
 }
 
@@ -110,6 +114,15 @@ static ANN Type maybe_func(const Env env, const Type t, const Type_Decl *td) {
 ANN Type _scan_type(const Env env, const Type t, Type_Decl *td) {
   if (tflag(t, tflag_tmpl) && !is_func(env->gwion, t)) {
     if (tflag(t, tflag_ntmpl) && !td->types) return t;
+    if(!td->types) {
+      const Type new_type = nspc_lookup_type1(env->curr, td->xid);
+      Type_Decl *new_td = type2td(env->gwion, new_type, td->pos);
+      if(!new_td->types)
+        ERR_N(td->pos, _("you must provide template types for type '%s' !!!"), t->name);
+      const Type ret = _scan_type(env, t, new_td);
+      free_type_decl(env->gwion->mp, new_td);
+      return ret;
+    }
     struct TemplateScan ts = {.t = t, .td = td};
     Type_List           tl = td->types;
     Specialized_List    sl = t->info->cdef->base.tmpl
@@ -150,7 +163,6 @@ ANN Type scan_type(const Env env, const Type t, Type_Decl *td) {
                         .flag  = tflag_none};
     envset_push(&es, owner, owner->nspc);
     (void)env_push(env, owner, owner->nspc); // TODO: is this needed?
-    //    const Type ret = scan_type(env, t, td->next);
     const Type ret = known_type(env, td->next);
     env_pop(env, es.scope);
     if (es.run) envset_pop(&es, owner);
diff --git a/util b/util
index 5cfa1c9d..7643ceba 160000
--- a/util
+++ b/util
@@ -1 +1 @@
-Subproject commit 5cfa1c9d8a1cd714d8b7b25de30d5522be9e6e11
+Subproject commit 7643ceba751766ae5cd42da19667e1377a2b89d0
-- 
2.43.0