Gwion coverage report

Directory: src/
File: src/lib/dict.c
Date: 2023-01-30 18:32:28
Exec Total Coverage
Lines: 374 534 70.0%
Functions: 25 46 54.3%
Branches: 62 140 44.3%
Line Branch Exec Source
1 #include <stdlib.h>
2 #include <string.h>
3 #include "gwion_util.h"
4 #include "gwion_ast.h"
5 #include "gwion_env.h"
6 #include "vm.h"
7 #include "gwion.h"
8 #include "instr.h"
9 #include "object.h"
10 #include "operator.h"
11 #include "import.h"
12 #include "emit.h"
13 #include "traverse.h"
14 #include "parse.h"
15 #include "gwi.h"
16 #include "tmpl_info.h"
17 #include "array.h"
18 #include "looper.h"
19 #include "dict.h"
20
21 #define HMAP_MIN_CAP 32
22 #define HMAP_MAX_LOAD 0.75
23
24 typedef void (clear_fn)(const HMap*, const VM_Shred, const struct HMapInfo*, const m_uint);
25
26 // TODO: arch sensible hash
27 ✗ static SFUN(mfun_int_h) {
28 ✗ m_int x = *(m_uint*)MEM(0);
29 ✗ x = (x ^ (x >> 30)) * UINT64_C(0xbf58476d1ce4e5b9);
30 ✗ x = (x ^ (x >> 27)) * UINT64_C(0x94d049bb133111eb);
31 ✗ x = x ^ (x >> 31);
32 ✗ *(m_int*) RETURN = x;
33 }
34
35 1 static SFUN(mfun_float_h) {
36 char c[1024];
37 1 snprintf(c, 1024, "%f", *(m_float*)MEM(0));
38 1 *(m_uint*)RETURN = hash(c);
39 1 }
40
41 9 static SFUN(mfun_string_h) {
42 9 *(m_int*)RETURN = hash(STRING(*(M_Object*)MEM(0)));
43 9 }
44
45 ✗ ANN static void clear_oo(const HMap *a, const VM_Shred shred, const HMapInfo *info NUSED, const m_uint idx) {
46 ✗ release(*(M_Object*)(a->data + idx * SZ_INT*2), shred);
47 ✗ release(*(M_Object*)((a->data + idx * SZ_INT*2) + SZ_INT), shred);
48 }
49
50 ✗ ANN static void clear_ss(const HMap *a, const VM_Shred shred, const HMapInfo *info, const m_uint idx) {
51 ✗ struct_release(shred, info->key, a->data + idx * info->sz);
52 ✗ struct_release(shred, info->val, a->data + idx * info->sz + info->key->size);
53 }
54
55 ✗ ANN static void clear_os(const HMap *a, const VM_Shred shred, const HMapInfo *info, const m_uint idx) {
56 ✗ release(*(M_Object*)(a->data + idx * info->sz), shred);
57 ✗ struct_release(shred, info->val, a->data + idx * info->sz + SZ_INT);
58 }
59
60 ✗ ANN static void clear_so(const HMap *a, const VM_Shred shred, const HMapInfo *info, const m_uint idx) {
61 ✗ struct_release(shred, info->key, a->data + idx * info->sz);
62 ✗ release(*(M_Object*)(a->data + idx * info->sz + info->key->size), shred);
63 }
64
65 3 ANN static void clear_on(const HMap *a, const VM_Shred shred, const HMapInfo *info, const m_uint idx) {
66 3 release(*(M_Object*)(a->data + idx * info->sz), shred);
67 3 }
68
69 ✗ ANN static void clear_sn(const HMap *a, const VM_Shred shred, const HMapInfo *info, const m_uint idx) {
70 ✗ struct_release(shred, info->key, a->data + idx * info->sz);
71 }
72
73 ✗ ANN static void clear_no(const HMap *a, const VM_Shred shred, const HMapInfo *info, const m_uint idx) {
74 ✗ release(*(M_Object*)(a->data + idx * info->sz + info->key->size), shred);
75 }
76
77
78 ✗ ANN static void clear_ns(const HMap *a, const VM_Shred shred, const HMapInfo *info, const m_uint idx) {
79 ✗ struct_release(shred, info->val, a->data + idx * info->sz + info->key->size);
80 }
81
82 static clear_fn *const n_clear[3] = { NULL, clear_no, clear_ns };
83 static clear_fn* o_clear[3] = { clear_on, clear_oo, clear_os };
84 static clear_fn* s_clear[3] = { clear_sn, clear_so, clear_ss };
85 static clear_fn*const* clear[3] = { n_clear, o_clear, s_clear };
86
87 5 ANN static void hmapinfo_init(HMapInfo *const info, const Type key, const Type val) {
88 5 info->key = key;
89 5 info->val = val;
90 5 info->sz = key->size + val->size;
91 5 info->keyk = tflag(key, tflag_compound) + tflag(key, tflag_struct);
92 5 info->valk = tflag(val, tflag_compound) + tflag(val, tflag_struct);
93 5 }
94
95 1 static DTOR(dict_clear_dtor) {
96 1 const HMapInfo *hinfo = (HMapInfo*)o->type_ref->nspc->class_data;
97 1 clear_fn *fn = clear[hinfo->keyk][hinfo->valk];
98 1 HMap *a = &*(struct HMap*)o->data;
99
2/2
✓ Branch 0 taken 31 times.
✓ Branch 1 taken 1 times.
 32 for(m_uint i = a->capacity; --i;) {
100 31 const HState state = *(HState*)(a->state + (i-1) * sizeof(HState));
101
4/4
✓ Branch 0 taken 3 times.
✓ Branch 1 taken 28 times.
✓ Branch 2 taken 1 times.
✓ Branch 3 taken 2 times.
 31 if(!state.set || state.deleted) continue;
102 2 fn(a, shred, hinfo, i-1);
103 }
104 1 }
105
106 2 INSTR(dict_ctor_alt) {
107 2 const Type t = (Type)instr->m_val2;
108 2 const M_Object o = new_object(shred->info->mp, t);
109 2 const HMapInfo *hinfo = (HMapInfo*)t->nspc->class_data;
110 2 HMap *a = &*(struct HMap*)o->data;
111 2 a->data = (m_bit*)mp_calloc2(shred->info->mp, hinfo->sz * instr->m_val);
112 2 a->state = (m_bit*)mp_calloc2(shred->info->mp, sizeof(HState) * instr->m_val);
113 2 a->capacity = instr->m_val;
114 2 shred->reg += SZ_INT;
115 2 *(M_Object*)REG(-SZ_INT) = o;
116 2 }
117
118 2 INSTR(dict_lit_ctor) {
119 2 const M_Object o = *(M_Object*)REG(-SZ_INT);
120 2 const HMapInfo *hinfo = (HMapInfo*)o->type_ref->nspc->class_data;
121 2 HMap *hmap = &*(struct HMap*)o->data;
122
2/2
✓ Branch 0 taken 4 times.
✓ Branch 1 taken 2 times.
 6 for(m_uint i = 0; i < instr->m_val; i += hinfo->sz + SZ_INT) {
123 4 m_uint hash = *(m_uint*)REG(i + hinfo->sz) % hmap->capacity;
124 1 while(true) {
125 5 HState *const state = (HState*)(hmap->state + hash * sizeof(HState));
126
2/2
✓ Branch 0 taken 4 times.
✓ Branch 1 taken 1 times.
 5 if(!state->set) {
127 4 m_bit *const data = hmap->data + hinfo->sz * hash;
128 4 memcpy(data, REG(i), hinfo->sz);
129 4 state->set = true;
130 4 break;
131 }
132
1/2
✓ Branch 0 taken 1 times.
✗ Branch 1 not taken.
 1 if(++hash >= hmap->capacity)
133 1 hash = 0;
134 }
135 }
136 2 hmap->count = instr->m_val2;
137 2 }
138
139 1 static CTOR(dict_ctor) {
140 1 const HMapInfo *hinfo = (HMapInfo*)o->type_ref->nspc->class_data;
141 1 HMap *const a = &*(struct HMap*)o->data;
142 1 a->data = (m_bit*)mp_calloc2(shred->info->mp, hinfo->sz * HMAP_MIN_CAP);
143 1 a->state = (m_bit*)mp_calloc2(shred->info->mp, sizeof(HState) * HMAP_MIN_CAP);
144 1 a->capacity = HMAP_MIN_CAP;
145 1 a->count = 0;
146 1 }
147
148 1 static DTOR(dict_dtor) {
149 1 HMap *const a = &*(struct HMap*)o->data;
150 1 const HMapInfo *hinfo = (HMapInfo*)o->type_ref->nspc->class_data;
151 1 mp_free2(shred->info->mp, hinfo->sz * a->capacity, a->data);
152 1 mp_free2(shred->info->mp, sizeof(HState) * a->capacity, a->state);
153 1 }
154
155 // bound the hash
156 // could be put in next func
157 3 static INSTR(hmap_iter_set_ini) {
158 3 const M_Object o = *(M_Object*)(shred->reg - SZ_INT*2 - instr->m_val);
159 3 const HMap *hmap = (HMap*)o->data;
160 3 const size_t h = *(m_uint*)REG(-SZ_INT - instr->m_val);
161
1/2
✓ Branch 0 taken 3 times.
✗ Branch 1 not taken.
 3 if(h >= hmap->capacity)
162 3 *(m_uint*)REG(-SZ_INT - instr->m_val) = h % hmap->capacity;
163 3 }
164
165 ✗ static INSTR(hmpa_set_inc) {
166 ✗ (*(m_uint*)REG(-SZ_INT - instr->m_val))++;
167 }
168
169 3 static INSTR(hmap_iter_set) {
170 3 const M_Object o = *(M_Object*)(shred->reg - SZ_INT*2 - instr->m_val);
171 3 HMap *const hmap = (HMap*)o->data;
172 3 const HMapInfo *hinfo = (HMapInfo*)o->type_ref->nspc->class_data;
173 3 const size_t bucket = *(m_uint*)REG(-SZ_INT - instr->m_val);
174 3 HState *const state = (HState*)(hmap->state + sizeof(HState) * bucket);
175 3 m_bit *const data = hmap->data + hinfo->sz * bucket;
176
1/4
✗ Branch 0 not taken.
✓ Branch 1 taken 3 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
 3 if (!state->set || state->deleted) {
177
178
1/2
✓ Branch 0 taken 3 times.
✗ Branch 1 not taken.
 3 if(hinfo->keyk) {
179
1/2
✓ Branch 0 taken 3 times.
✗ Branch 1 not taken.
 3 if(hinfo->keyk == HKIND_OBJ)
180 3 (*(M_Object*)REG(-instr->m_val))->ref++;
181 else
182 ✗ struct_addref(shred->info->vm->gwion, hinfo->key, REG(-instr->m_val));
183 }
184
185 3 state->set = true;
186 3 state->deleted = false;
187 3 memcpy(data, REG(-instr->m_val), instr->m_val);
188 3 POP_REG(shred, instr->m_val);
189 3 *(m_bit**)REG(-SZ_INT*2) = data + hinfo->key->size;
190 3 *(m_uint*)REG(-SZ_INT) = 1;
191 3 hmap->count++;
192 } else {
193 ✗ memcpy(REG(0), data, hinfo->key->size);
194 ✗ shred->reg += SZ_INT + hinfo->key->size;
195 ✗ *(m_uint**)REG(-SZ_INT) = 0;
196 }
197 3 }
198
199 1 static INSTR(hmap_iter_inc) {
200 1 (*(m_uint*)(shred->reg - SZ_INT))++;
201 1 }
202
203 4 static INSTR(hmap_iter) {
204 4 const M_Object o = *(M_Object*)(shred->reg - SZ_INT*3);
205 4 const HMap *hmap = (HMap*)o->data;
206 4 const HMapInfo *hinfo = (HMapInfo*)o->type_ref->nspc->class_data;
207 4 size_t bucket = *(m_uint*)(shred->reg - SZ_INT) % hmap->capacity;
208 4 const HState *state = (HState*)(hmap->state + sizeof(HState) * bucket);
209
2/2
✓ Branch 0 taken 3 times.
✓ Branch 1 taken 1 times.
 4 if (state->set) {
210 3 m_int *const tombstone = (m_int*)(shred->reg - SZ_INT*2);
211
3/4
✓ Branch 0 taken 1 times.
✓ Branch 1 taken 2 times.
✓ Branch 2 taken 1 times.
✗ Branch 3 not taken.
 3 if (state->deleted && *tombstone == -1) {
212 1 *tombstone = bucket++;
213 }
214 3 const m_bit *data = hmap->data + hinfo->sz * bucket;
215 3 *(m_uint*)(shred->reg - SZ_INT) = bucket;
216 3 memcpy(REG(0), data, hinfo->key->size);
217 3 shred->reg += hinfo->key->size;
218 3 return;
219 }
220 1 handle(shred, "InvalidMapAccess");
221 }
222
223 3 static INSTR(hmap_grow) {
224 3 const M_Object o = *(M_Object*)(shred->reg - SZ_INT);
225 3 const HMap *hmap = (HMap*)o->data;
226 3 *(m_uint*)REG(0) = (hmap->count + 1) > (hmap->capacity * HMAP_MAX_LOAD);
227 3 PUSH_REG(shred, SZ_INT);
228 3 }
229
230 ✗ static INSTR(hmap_grow_init) {
231 ✗ const M_Object o = *(M_Object*)(shred->reg - SZ_INT);
232 ✗ HMap *const hmap = (HMap*)o->data;
233 ✗ const HMapInfo *hinfo = (HMapInfo*)o->type_ref->nspc->class_data;
234 ✗ *(m_bit**)REG(0) = hmap->data;
235 ✗ *(m_bit**)REG(SZ_INT) = hmap->state;
236 ✗ *(m_uint*)REG(SZ_INT*2) = hmap->capacity;
237 ✗ hmap->capacity *= 2;
238 ✗ hmap->count = 0;
239 ✗ hmap->state = mp_calloc2(shred->info->mp, hmap->capacity * sizeof(HState));
240 ✗ hmap->data = mp_calloc2(shred->info->mp, hmap->capacity * hinfo->sz);
241
242 ✗ PUSH_REG(shred, SZ_INT*3);
243 }
244
245 ✗ static INSTR(hmap_grow_dec) {
246 ✗ const M_Object o = *(M_Object*)(shred->reg - SZ_INT*4);
247 ✗ const HMapInfo *hinfo = (HMapInfo*)o->type_ref->nspc->class_data;
248 ✗ const m_bit *old_data = *(m_bit**)REG(-SZ_INT*3);
249 ✗ const m_bit *old_state = *(m_bit**)REG(-SZ_INT*2);
250 ✗ while((*(m_uint*)REG(-SZ_INT))--) {
251 ✗ const HState *state = (HState *)(old_state + (*(m_uint*)REG(-SZ_INT)) * sizeof(HState));
252 ✗ if(!state->set || state->deleted)continue;
253 ✗ m_bit *const data = (m_bit*)(old_data + (*(m_uint*)REG(-SZ_INT)) * hinfo->sz);
254 ✗ memcpy(shred->reg + SZ_INT, data, hinfo->key->size);
255 ✗ PUSH_REG(shred, SZ_INT + hinfo->key->size);
256 ✗ *(m_uint*)shred->reg = 0;
257 ✗ PUSH_REG(shred, SZ_INT);
258 ✗ return;
259 }
260 ✗ POP_REG(shred, SZ_INT*2);
261 ✗ *(m_uint*)(shred->reg -SZ_INT) = 1;
262 }
263
264 ✗ static INSTR(hmap_find) {
265 ✗ const M_Object o = *(M_Object*)(shred->reg - SZ_INT*6);
266 ✗ HMap *const hmap = (HMap*)o->data;
267 ✗ const HMapInfo *hinfo = (HMapInfo*)o->type_ref->nspc->class_data;
268 ✗ const m_bit *old_data = *(m_bit**)REG(-SZ_INT*5);
269 ✗ const m_bit *old_state = *(m_bit**)REG(-SZ_INT*4);
270 ✗ const m_uint h = *(m_uint*)REG(-SZ_INT);
271 ✗ const m_uint idx = *(m_uint*)REG(-SZ_INT*3);
272 ✗ m_uint bucket = h % hmap->capacity;
273 ✗ while(true) {
274 ✗ HState *const state = (HState *)(hmap->state + bucket * sizeof(HState));
275 ✗ if(!state->set) {
276 ✗ const HState *prev_state = (HState *)(old_state + idx * sizeof(HState));
277 ✗ memcpy(state, prev_state, sizeof(HState));
278 ✗ m_bit *const data = hmap->data + bucket * hinfo->sz;
279 ✗ const m_bit *prev_data = old_data + idx * hinfo->sz;
280 ✗ memcpy(data, prev_data, hinfo->sz);
281 ✗ hmap->count++;
282 ✗ break;
283 }
284 ✗ if(++bucket > hmap->capacity)
285 ✗ bucket = 0;
286 }
287 ✗ if(!idx)
288 ✗ POP_REG(shred, SZ_INT*4 - instr->m_val)
289 else
290 ✗ POP_REG(shred, SZ_INT)
291 ✗ *(m_uint*)REG(-SZ_INT) = !idx;
292 }
293
294 ✗ static INSTR(hmap_addr) {
295 ✗ const M_Object o = *(M_Object*)(shred->reg - SZ_INT*2 - instr->m_val);
296 ✗ const HMap *hmap = (HMap*)o->data;
297 ✗ const HMapInfo *hinfo = (HMapInfo*)o->type_ref->nspc->class_data;
298 ✗ POP_REG(shred, SZ_INT + instr->m_val);
299 ✗ const m_uint bucket = *(m_uint*)REG(0);
300 ✗ *(HState *)(hmap->state + bucket * sizeof(HState)) = (HState) { true, false };
301 ✗ *(m_bit**)REG(-SZ_INT) = hmap->data + hinfo->sz * bucket + hinfo->key->size;
302 }
303
304 1 static INSTR(hmap_val) {
305 1 const M_Object o = *(M_Object*)(shred->reg - SZ_INT*2);
306 1 const HMap *hmap = (HMap*)o->data;
307 1 const HMapInfo *hinfo = (HMapInfo*)o->type_ref->nspc->class_data;
308 1 const m_uint bucket = *(m_uint*)REG(0);
309 1 const m_bit *new_data = hmap->data + hinfo->sz * bucket;
310 1 const m_int tombstone = *(m_int*)(shred->reg - SZ_INT);
311
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 1 times.
 1 if (tombstone != -1) {
312 ✗ m_bit *const old_data = hmap->data + (hinfo->key->size + hinfo->val->size) * tombstone;
313 ✗ HState *const old_state = (HState*)(hmap->state + sizeof(HState) * tombstone);
314 ✗ HState *const new_state = (HState*)(hmap->state + sizeof(HState) * bucket);
315 ✗ memcpy(old_state, new_state, sizeof(HState));
316 ✗ memcpy(old_data, new_data, hinfo->sz);
317 ✗ new_state->deleted = true;
318 }
319
320 1 shred->reg -= SZ_INT*2 - hinfo->val->size;
321 1 memcpy(REG(-hinfo->val->size), new_data + hinfo->key->size, hinfo->val->size);
322 1 }
323
324 1 static INSTR(hmap_remove_clear) {
325 1 const M_Object o = *(M_Object*)(shred->reg - SZ_INT*2);
326 1 const HMap *hmap = (HMap*)o->data;
327 1 const HMapInfo *hinfo = (HMapInfo*)o->type_ref->nspc->class_data;
328 1 const m_uint bucket = *(m_uint*)REG(0);
329 1 clear_fn *fn = (clear_fn*)instr->m_val;
330 1 fn(hmap, shred, hinfo, bucket);
331 1 }
332
333 1 static INSTR(hmap_remove) {
334 1 const M_Object o = *(M_Object*)(shred->reg - SZ_INT*2);
335 1 HMap *const hmap = (HMap*)o->data;
336 1 const HMapInfo *hinfo = (HMapInfo*)o->type_ref->nspc->class_data;
337 1 const m_uint bucket = *(m_uint*)REG(0);
338 1 m_bit *data = hmap->data + hinfo->sz * bucket;
339 1 hmap->count--;
340 1 HState *const state = (HState *)(hmap->state + bucket * sizeof(HState));
341 1 state->deleted = true;
342 1 shred->reg -= SZ_INT*3 - hinfo->val->size;
343 1 memcpy(REG(-hinfo->val->size), data + hinfo->key->size, hinfo->val->size);
344 1 }
345
346 1 static OP_CHECK(opck_dict_remove_toop) {
347 1 const Exp e = (Exp)data;
348 1 const Exp_Call *call = &e->d.exp_call;
349 1 const Exp func = call->func;
350 1 const Exp args = call->args;
351 1 e->exp_type = ae_exp_binary;
352
1/2
✗ Branch 2 not taken.
✓ Branch 3 taken 1 times.
 1 CHECK_OO(check_exp(env, e->d.exp_binary.rhs = cpy_exp(env->gwion->mp, func->d.exp_dot.base)));
353
1/2
✗ Branch 1 not taken.
✓ Branch 2 taken 1 times.
 1 CHECK_OO(check_exp(env, e->d.exp_binary.lhs = args));
354 1 e->d.exp_binary.op = insert_symbol("~~");
355 1 free_exp(env->gwion->mp, func);
356 1 const Type t = e->d.exp_binary.rhs->type;
357 1 HMapInfo *const hinfo = (HMapInfo*)t->nspc->class_data;
358
2/4
✓ Branch 0 taken 1 times.
✗ Branch 1 not taken.
✗ Branch 2 not taken.
✓ Branch 3 taken 1 times.
 1 if(isa(args->type, hinfo->key) < 0 || args->next)
359 ✗ ERR_N(e->pos, "dict.remove must be called with one Key argument");
360 1 return e->type = env->gwion->type[et_void];
361 }
362
363 3 ANN static m_bool emit_dict_iter(const Emitter emit, const HMapInfo *hinfo,
364 const struct Op_Import *opi, const Exp call, const Exp exp) {
365 3 emit_pushimm(emit, -1); // room for tombstone
366
1/2
✗ Branch 1 not taken.
✓ Branch 2 taken 3 times.
 3 CHECK_BB(emit_exp(emit, call));
367 3 const m_uint pc = emit_code_size(emit);
368 3 const Instr iter = emit_add_instr(emit, hmap_iter);
369 3 iter->m_val = hinfo->key->size + SZ_INT;
370
1/2
✗ Branch 1 not taken.
✓ Branch 2 taken 3 times.
 3 CHECK_BB(emit_exp(emit, exp));
371 3 op_emit(emit, opi);
372 3 const Instr ok = emit_add_instr(emit, BranchNeqInt);
373 3 emit_add_instr(emit, hmap_iter_inc);
374 3 const Instr top = emit_add_instr(emit, Goto);
375 3 top->m_val = pc;
376 3 ok->m_val = emit_code_size(emit);
377 3 emit_regmove(emit, -SZ_INT);
378 3 return GW_OK;
379 }
380
381 5 static OP_EMIT(_opem_dict_access) {
382 5 struct ArrayAccessInfo *const info = (struct ArrayAccessInfo *const)data;
383 5 Array_Sub array = &info->array;
384 5 const Env env = emit->env;
385 5 const HMapInfo *hinfo = (HMapInfo*)array->type->nspc->class_data;
386 5 const Type key = *(Type*)array->type->nspc->class_data;
387
388 5 struct Exp_ func = { .exp_type = ae_exp_primary, .d = { .prim = { .prim_type = ae_prim_id, .d = { .var = insert_symbol("hash") }} }};
389
390 5 struct Exp_ call = {
391 .exp_type = ae_exp_call,
392 .d = {
393 .exp_call = {
394 .func = &func,
395 5 .args = array->exp // beware next
396 }
397 }
398 };
399 5 struct Exp_ lhs = { .exp_type = ae_exp_primary, .type = key, .d = { .prim = { .prim_type = ae_prim_id } }};
400 5 struct Exp_ rhs = { .exp_type = ae_exp_primary, .type = key, .d = { .prim = { .prim_type = ae_prim_id } }};
401 5 struct Exp_ bin = { .exp_type = ae_exp_binary, .d = { .exp_binary = { .lhs = &lhs, .rhs = &rhs, .op = insert_symbol("?=") } }};
402 5 struct Op_Import opi = {
403 .lhs = key,
404 .rhs = key,
405 5 .op = bin.d.exp_binary.op,
406 5 .data = (m_uint)&bin
407 };
408
409
410
1/2
✗ Branch 1 not taken.
✓ Branch 2 taken 5 times.
 5 CHECK_BB(traverse_exp(env, &call));
411
2/2
✓ Branch 0 taken 3 times.
✓ Branch 1 taken 2 times.
 5 if(info->is_var) {
412
413 3 const Instr instr = emit_add_instr(emit, hmap_grow);
414 3 instr->m_val = key->size;
415 3 const Instr nogrow = emit_add_instr(emit, BranchEqInt);
416 3 emit_add_instr(emit, hmap_grow_init);
417 3 const m_uint grow_pc = emit_code_size(emit);
418 3 emit_add_instr(emit, hmap_grow_dec);
419 3 const Instr endgrow = emit_add_instr(emit, BranchNeqInt);
420
1/2
✗ Branch 1 not taken.
✓ Branch 2 taken 3 times.
 3 CHECK_BB(emit_exp(emit, call.d.exp_call.func));
421
1/2
✗ Branch 1 not taken.
✓ Branch 2 taken 3 times.
 3 CHECK_BB(emit_exp_call1(emit, call.d.exp_call.func->type->info->func, true));
422 3 emit_add_instr(emit, hmap_find);
423 3 const Instr regrow = emit_add_instr(emit, BranchEqInt);
424 3 regrow->m_val = grow_pc;
425 3 nogrow->m_val = emit_code_size(emit);
426 3 endgrow->m_val = emit_code_size(emit);
427
1/2
✗ Branch 1 not taken.
✓ Branch 2 taken 3 times.
 3 CHECK_BB(emit_exp(emit, &call));
428
1/2
✗ Branch 1 not taken.
✓ Branch 2 taken 3 times.
 3 CHECK_BB(emit_exp(emit, array->exp));
429 3 const m_uint top_pc = emit_code_size(emit);
430 3 const Instr idx = emit_add_instr(emit, hmap_iter_set_ini);
431 3 idx->m_val = key->size;
432
433
434 3 const Instr iter = emit_add_instr(emit, hmap_iter_set);
435 3 iter->m_val = key->size;
436 3 const Instr fast = emit_add_instr(emit, BranchNeqInt);
437
1/2
✗ Branch 1 not taken.
✓ Branch 2 taken 3 times.
 3 CHECK_BB(emit_exp(emit, array->exp));
438 3 op_emit(emit, &opi);
439
440 3 const Instr ok = emit_add_instr(emit, BranchNeqInt);
441 3 const Instr inc = emit_add_instr(emit, hmpa_set_inc);
442 3 inc->m_val = key->size;
443 3 const Instr not_ok = emit_add_instr(emit, Goto);
444 3 not_ok->m_val = top_pc;
445 3 ok->m_val = emit_code_size(emit);
446
447 3 const Instr iseq = emit_add_instr(emit, hmap_addr);
448 3 iseq->m_val = key->size;
449 3 fast->m_val = emit_code_size(emit);
450 3 return GW_OK;
451 }
452
1/2
✗ Branch 1 not taken.
✓ Branch 2 taken 2 times.
 2 CHECK_BB(emit_dict_iter(emit, hinfo, &opi, &call, array->exp));
453 2 const Instr pushval = emit_add_instr(emit, hmap_val);
454 2 pushval->m_val2 = key->size;
455 2 return GW_OK;
456 }
457
458 1 static OP_EMIT(opem_dict_remove) {
459 1 Exp_Binary *bin = (Exp_Binary*)data;
460 1 const Env env = emit->env;
461 1 struct Exp_ func = { .exp_type = ae_exp_primary, .d = { .prim = { .prim_type = ae_prim_id, .d = { .var = insert_symbol("hash") }} }};
462
463 1 struct Exp_ call = {
464 .exp_type = ae_exp_call,
465 .d = {
466 .exp_call = {
467 .func = &func,
468 1 .args = bin->lhs // beware next
469 }
470 }
471 };
472 1 const Type t = bin->rhs->type;
473 1 HMapInfo *const hinfo = (HMapInfo*)t->nspc->class_data;
474
475 1 struct Exp_ lhs = { .exp_type = ae_exp_primary, .type = hinfo->key, .d = { .prim = { .prim_type = ae_prim_id } }};
476 1 struct Exp_ rhs = { .exp_type = ae_exp_primary, .type = hinfo->key, .d = { .prim = { .prim_type = ae_prim_id } }};
477 1 struct Exp_ _bin = { .exp_type = ae_exp_binary, .d = { .exp_binary = { .lhs = &lhs, .rhs = &rhs, .op = insert_symbol("?=") } }};
478 1 struct Op_Import opi = {
479 1 .lhs = hinfo->key,
480 1 .rhs = hinfo->key,
481 1 .op = _bin.d.exp_binary.op,
482 1 .data = (m_uint)&_bin
483 };
484
485
1/2
✗ Branch 1 not taken.
✓ Branch 2 taken 1 times.
 1 CHECK_BB(traverse_exp(env, &call));
486
1/2
✗ Branch 1 not taken.
✓ Branch 2 taken 1 times.
 1 CHECK_BB(emit_dict_iter(emit, hinfo, &opi, &call, bin->lhs));
487
1/4
✗ Branch 0 not taken.
✓ Branch 1 taken 1 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
 1 if(hinfo->keyk || hinfo->valk) {
488 1 clear_fn *const fn = clear[hinfo->keyk][hinfo->valk];
489 1 const Instr instr = emit_add_instr(emit, hmap_remove_clear);
490 1 instr->m_val = (m_uint)fn;
491 }
492
493 1 const Instr pushval = emit_add_instr(emit, hmap_remove);
494 1 pushval->m_val2 = hinfo->key->size;
495 1 return GW_OK;
496 }
497
498 ✗ ANN static m_bool emit_next_access(const Emitter emit, struct ArrayAccessInfo *const info) {
499 ✗ const struct Array_Sub_ array = info->array;
500 ✗ HMapInfo *const hinfo = (HMapInfo*)info->array.type->nspc->class_data;
501 ✗ info->array = (struct Array_Sub_){
502 ✗ .exp = array.exp->next,
503 ✗ .type = hinfo->val,
504 ✗ .depth = array.depth - 1
505 };
506 ✗ return emit_array_access(emit, info);
507 }
508
509 5 static OP_EMIT(opem_dict_access) {
510 5 struct ArrayAccessInfo *const info = (struct ArrayAccessInfo *const)data;
511 5 const Array_Sub array = &info->array;
512 5 const Exp enext = array->exp->next;
513 5 array->exp->next = NULL;
514 5 const m_bool ret = _opem_dict_access(emit, data);
515 5 array->exp->next = enext;
516
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 5 times.
 5 CHECK_BB(ret);
517
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 5 times.
 5 return !enext ? GW_OK : emit_next_access(emit, info);
518 }
519
520 7 static OP_CHECK(opck_dict_access) {
521 7 const Array_Sub array = (Array_Sub)data;
522 7 HMapInfo *const hinfo = (HMapInfo*)array->type->nspc->class_data;
523
524 7 struct Exp_ func = { .exp_type = ae_exp_primary, .d = { .prim = { .prim_type = ae_prim_id, .d = { .var = insert_symbol("hash") }} }};
525
526 7 struct Exp_ call = {
527 .exp_type = ae_exp_call,
528 .d = {
529 .exp_call = {
530 .func = &func,
531 7 .args = array->exp // beware next
532 }
533 }
534 };
535 7 struct Exp_ lhs = { .exp_type = ae_exp_primary, .type = hinfo->key, .d = { .prim = { .prim_type = ae_prim_id } }};
536 7 struct Exp_ rhs = { .exp_type = ae_exp_primary, .type = hinfo->key, .d = { .prim = { .prim_type = ae_prim_id } }};
537 7 struct Exp_ bin = { .exp_type = ae_exp_binary, .d = { .exp_binary = { .lhs = &lhs, .rhs = &rhs, .op = insert_symbol("?=") } }};
538 7 struct Op_Import opi = {
539 7 .lhs = hinfo->key,
540 7 .rhs = hinfo->key,
541 7 .op = bin.d.exp_binary.op,
542 7 .data = (m_uint)&bin
543 };
544
545
546
1/2
✗ Branch 1 not taken.
✓ Branch 2 taken 7 times.
 7 CHECK_BN(traverse_exp(env, &call));
547
1/2
✗ Branch 1 not taken.
✓ Branch 2 taken 7 times.
 7 CHECK_ON(op_check(env, &opi));
548
549
1/2
✓ Branch 0 taken 7 times.
✗ Branch 1 not taken.
 7 if(!array->exp->next) return hinfo->val;
550 ✗ struct Array_Sub_ next = { array->exp->next, hinfo->val,
551 ✗ array->depth - 1};
552 ✗ return check_array_access(env, &next) ?: env->gwion->type[et_error];
553 }
554
555 ✗ static INSTR(DictEach) {
556 ✗ const M_Object o = *(M_Object *)(shred->mem + instr->m_val2);
557 ✗ HMapInfo *const hinfo = (HMapInfo*)o->type_ref->nspc->class_data;
558 ✗ const HMap *hmap = (HMap*)o->data;
559 ✗ m_uint bucket = ++*(m_uint *)(shred->mem + instr->m_val2 + SZ_INT);
560 ✗ while(bucket < hmap->capacity) {
561 ✗ const HState *state = (HState *)(hmap->state + bucket * sizeof(HState));
562 ✗ if (state->set && !state->deleted)
563 ✗ break;
564 ✗ bucket++;
565 }
566 ✗ *(m_uint *)(shred->mem + instr->m_val2 + SZ_INT) = bucket;
567 ✗ memcpy(shred->mem + instr->m_val2 + SZ_INT*2, hmap->data + (bucket * hinfo->sz) + hinfo->key->size, hinfo->val->size);
568 ✗ *(m_uint*)shred->reg = (bucket == hmap->capacity);
569 ✗ PUSH_REG(shred, SZ_INT);
570 }
571
572 ✗ static INSTR(DictEachIdx) {
573 ✗ const M_Object o = *(M_Object *)(shred->mem + instr->m_val2);
574 ✗ HMapInfo *const hinfo = (HMapInfo*)o->type_ref->nspc->class_data;
575 ✗ const HMap *hmap = (HMap*)o->data;
576 ✗ DictEach(shred, instr);
577 ✗ const m_int bucket = *(m_uint *)(shred->mem + instr->m_val2 + SZ_INT);
578 ✗ memcpy(shred->mem + instr->m_val, hmap->data + (bucket * hinfo->sz), hinfo->key->size);
579 }
580
581 ✗ static OP_EMIT(opem_dict_each) {
582 ✗ Looper *loop = (Looper *)data;
583 ✗ HMapInfo *const hinfo = (HMapInfo*)loop->exp->type->nspc->class_data;
584 ✗ if(loop->idx && !loop->init) loop->idx->v->from->offset = emit_localn(emit, hinfo->key);
585 ✗ const Instr instr = emit_add_instr(emit, !loop->idx ? DictEach : DictEachIdx);
586 ✗ instr->m_val2 = loop->offset;
587 ✗ if(loop->idx) instr->m_val = loop->idx->v->from->offset;
588 ✗ if(loop->n)instr->m_val2 += SZ_INT;
589 ✗ const Instr go = emit_add_instr(emit, BranchNeqInt);
590 ✗ if(!loop->n) loop->instr = go;
591 ✗ else vector_add(&loop->unroll_v, (m_uint)go);
592 ✗ loop->init = true;
593 ✗ return GW_OK;
594 }
595
596 ✗ static INSTR(DictEachInit) {
597 ✗ const M_Object o = *(M_Object *)(shred->mem + instr->m_val + SZ_INT);
598 ✗ *(m_uint *)(shred->mem + instr->m_val) = ((HMap*)o->data)->capacity;
599 }
600
601 ✗ static OP_EMIT(opem_dict_each_init) {
602 ✗ const Looper *loop = (Looper *)data;
603 ✗ const Instr instr = emit_add_instr(emit, DictEachInit);
604 ✗ instr->m_val = loop->offset;
605 ✗ return GW_OK;
606 }
607
608 ✗ static OP_CHECK(opck_dict_each_key) {
609 ✗ const Exp exp = (const Exp)data;
610 ✗ HMapInfo *const hinfo = (HMapInfo*)exp->type->nspc->class_data;
611 ✗ return hinfo->key;
612 }
613
614 ✗ static OP_CHECK(opck_dict_each_val) {
615 ✗ const Exp exp = (const Exp)data;
616 ✗ HMapInfo *const hinfo = (HMapInfo*)exp->type->nspc->class_data;
617 ✗ return hinfo->val;
618 }
619
620 7 static OP_CHECK(opck_dict_scan) {
621 7 struct TemplateScan *ts = (struct TemplateScan *)data;
622
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 7 times.
 7 if(ts->t->info->cdef->base.tmpl->call) return ts->t;
623 7 struct tmpl_info info = {
624 7 .base = ts->t, .td = ts->td, .list = ts->t->info->cdef->base.tmpl->list};
625 7 const Type exists = tmpl_exists(env, &info);
626
3/4
✓ Branch 0 taken 2 times.
✓ Branch 1 taken 5 times.
✓ Branch 2 taken 2 times.
✗ Branch 3 not taken.
 7 if (exists) return exists != env->gwion->type[et_error] ? exists : NULL;
627
2/4
✓ Branch 0 taken 5 times.
✗ Branch 1 not taken.
✗ Branch 2 not taken.
✓ Branch 3 taken 5 times.
 5 if(!ts->td->types || ts->td->types->len != 2) return env->gwion->type[et_error];
628
1/2
✗ Branch 1 not taken.
✓ Branch 2 taken 5 times.
 5 DECL_ON(const Type, key, = known_type(env, *mp_vector_at(ts->td->types, Type_Decl*, 0)));
629
1/2
✗ Branch 1 not taken.
✓ Branch 2 taken 5 times.
 5 DECL_ON(const Type, val, = known_type(env, *mp_vector_at(ts->td->types, Type_Decl*, 1)));
630
2/4
✓ Branch 1 taken 5 times.
✗ Branch 2 not taken.
✗ Branch 4 not taken.
✓ Branch 5 taken 5 times.
 5 if(tflag(key, tflag_ref) || tflag(val, tflag_ref))
631 ✗ ERR_N(ts->td->pos, "can't use Ref:[] in dicts");
632 5 const Class_Def cdef = cpy_class_def(env->gwion->mp, env->gwion->type[et_dict]->info->cdef);
633 5 cdef->base.ext = type2td(env->gwion, env->gwion->type[et_dict], (loc_t) {});
634 5 cdef->base.xid = info.name;
635 5 cdef->base.tmpl->call = cpy_type_list(env->gwion->mp, info.td->types);
636
637 5 const bool is_global = tmpl_global(env, ts->td->types);
638
1/2
✓ Branch 0 taken 5 times.
✗ Branch 1 not taken.
 5 const m_uint scope = is_global ? env_push_global(env) : env->scope->depth;
639
1/2
✗ Branch 1 not taken.
✓ Branch 2 taken 5 times.
 5 CHECK_BN(scan0_class_def(env, cdef));
640 5 const Type t = cdef->base.type;
641 5 t->nspc->class_data_size = sizeof(struct HMapInfo);
642 5 const m_bool ret = traverse_cdef(env, t);
643 5 set_tflag(t, tflag_cdef);
644
1/2
✓ Branch 0 taken 5 times.
✗ Branch 1 not taken.
 5 if(is_global) {
645 5 env_pop(env, scope);
646 5 type_addref(t);
647 }
648 5 HMapInfo *const hinfo = (HMapInfo*)t->nspc->class_data;
649 5 hmapinfo_init(hinfo, key, val);
650
2/2
✓ Branch 0 taken 4 times.
✓ Branch 1 taken 1 times.
 5 if(hinfo->keyk + hinfo->valk) {
651 4 t->nspc->dtor = new_vmcode(env->gwion->mp, NULL, NULL, "@dtor", SZ_INT, true, false);
652 4 t->nspc->dtor->native_func = (m_uint)dict_clear_dtor;
653 4 set_tflag(t, tflag_dtor);
654 }
655 5 struct Op_Func opfunc = { .ck = opck_dict_access, .em = opem_dict_access };
656 5 struct Op_Import opi = { .lhs = key, .rhs = t, .ret = val, .op = insert_symbol("[]"), .func = &opfunc };
657 5 add_op(env->gwion, &opi);
658 5 opi.op = insert_symbol("~~");
659 5 opfunc.em = opem_dict_remove;
660 5 add_op(env->gwion, &opi);
661
662 {
663 5 const Func f = (Func)vector_at(&t->nspc->vtable, 1);
664 5 const struct Op_Func opfunc = {.ck = opck_dict_remove_toop};
665 5 const struct Op_Import opi = {
666 5 .rhs = f->value_ref->type,
667 .func = &opfunc,
668 5 .data = (uintptr_t)f,
669 5 .op = insert_symbol("@func_check")};
670
1/2
✗ Branch 1 not taken.
✓ Branch 2 taken 5 times.
 5 CHECK_BN(add_op(env->gwion, &opi));
671
672 }
673
1/2
✓ Branch 0 taken 5 times.
✗ Branch 1 not taken.
 5 return ret > 0 ? t : NULL;
674 }
675
676 638 GWION_IMPORT(dict) {
677
1/2
✗ Branch 1 not taken.
✓ Branch 2 taken 638 times.
 638 DECL_OB(const Type, t_dict, = gwi_class_ini(gwi, "Dict:[Key,Val]", "Object"));
678 638 gwi_class_xtor(gwi, dict_ctor, dict_dtor);
679 638 t_dict->nspc->offset += sizeof(struct HMap);
680 638 gwi->gwion->type[et_dict] = t_dict;
681 638 set_tflag(t_dict, tflag_infer);
682 638 GWI_BB(gwi_func_ini(gwi, "void", "remove"));
683 638 GWI_BB(gwi_func_arg(gwi, "Key", "key"));
684 638 GWI_BB(gwi_func_end(gwi, (f_xfun)1, ae_flag_none));
685
686 638 GWI_BB(gwi_class_end(gwi))
687
688 638 GWI_BB(gwi_oper_ini(gwi, "Dict", NULL, NULL))
689 638 GWI_BB(gwi_oper_add(gwi, opck_dict_scan))
690 638 GWI_BB(gwi_oper_end(gwi, "class", NULL))
691
692 638 GWI_BB(gwi_oper_ini(gwi, "Dict", NULL, "int"))
693 638 GWI_BB(gwi_oper_emi(gwi, opem_dict_each))
694 638 GWI_BB(gwi_oper_end(gwi, "@each", NULL))
695
696 638 GWI_BB(gwi_oper_ini(gwi, "Dict", NULL, "void"))
697 638 GWI_BB(gwi_oper_emi(gwi, opem_dict_each_init))
698 638 GWI_BB(gwi_oper_end(gwi, "@each_init", NULL))
699
700 638 GWI_BB(gwi_oper_ini(gwi, "Dict", NULL, NULL))
701 638 GWI_BB(gwi_oper_add(gwi, opck_dict_each_val))
702 638 GWI_BB(gwi_oper_end(gwi, "@each_val", NULL))
703
704 638 GWI_BB(gwi_oper_ini(gwi, "Dict", NULL, NULL))
705 638 GWI_BB(gwi_oper_add(gwi, opck_dict_each_key))
706 638 GWI_BB(gwi_oper_end(gwi, "@each_idx", NULL))
707
708 638 GWI_BB(gwi_func_ini(gwi, "int", "hash"));
709 638 GWI_BB(gwi_func_arg(gwi, "int", "key"));
710 638 GWI_BB(gwi_func_end(gwi, mfun_int_h, ae_flag_none));
711
712 638 GWI_BB(gwi_func_ini(gwi, "int", "hash"));
713 638 GWI_BB(gwi_func_arg(gwi, "Object", "key"));
714 638 GWI_BB(gwi_func_end(gwi, mfun_int_h, ae_flag_none));
715
716 638 GWI_BB(gwi_func_ini(gwi, "int", "hash"));
717 638 GWI_BB(gwi_func_arg(gwi, "float", "key"));
718 638 GWI_BB(gwi_func_end(gwi, mfun_float_h, ae_flag_none));
719
720 638 GWI_BB(gwi_func_ini(gwi, "int", "hash"));
721 638 GWI_BB(gwi_func_arg(gwi, "time", "key"));
722 638 GWI_BB(gwi_func_end(gwi, mfun_float_h, ae_flag_none));
723
724 638 GWI_BB(gwi_func_ini(gwi, "int", "hash"));
725 638 GWI_BB(gwi_func_arg(gwi, "dur", "key"));
726 638 GWI_BB(gwi_func_end(gwi, mfun_float_h, ae_flag_none));
727
728 638 GWI_BB(gwi_func_ini(gwi, "int", "hash"));
729 638 GWI_BB(gwi_func_arg(gwi, "string", "key"));
730 638 GWI_BB(gwi_func_end(gwi, mfun_string_h, ae_flag_none));
731
732 638 return GW_OK;
733 }
734