microscript: add maps

9 files changed, 367 insertions, 40 deletions

diff --git a/uscript/map.c b/uscript/map.c
new file mode 100644
index 0000000..01f2462
--- /dev/null
+++ b/uscript/map.c
@@ -0,0 +1,143 @@
+#include "map.h"
+
+#include <assert.h>
+#include <string.h>
+
+#define MAP_MAX (0.75)
+
+static
+uint32_t hash_val(struct us_val v)
+{
+        switch (v.type) {
+        case VAL_NUM: {
+                double n = get_num(v);
+                return *(uint32_t*)&n;
+        }
+        case VAL_BOOL: return get_bool(v) ? 1 : 0;
+        case VAL_ZILCH: return 2;
+        case VAL_STR: // TODO: string should use a different hash function
+        case VAL_ARR:
+        case VAL_MAP:
+        case VAL_PROTO:
+        case VAL_FUNC:
+        case VAL_CFUNC:
+        case VAL_UPVAL:
+                return (uint32_t)(uint64_t)get_obj(v);
+        }
+        return 0;
+}
+
+static
+struct us_map_kv *find_entry(struct us_map_kv *map, int cap, struct us_val k)
+{
+        if (k.type == VAL_ZILCH) {
+                us_err("use of zilch as a map key");
+        }
+
+        uint32_t hash = hash_val(k);
+
+        uint32_t i = hash % cap;
+        struct us_map_kv *ts = NULL;
+
+        while (true) {
+                struct us_map_kv *item = &map[i];
+                if (item->key.type == VAL_ZILCH) {
+                        if (item->val.type == VAL_ZILCH) {
+                                return ts ? ts : item;
+                        } else if (ts == NULL) {
+                                ts = item;
+                        }
+                } else if (vals_eql(item->key, k)) {
+                        return item;
+                }
+
+                i = (i + 1) % cap;
+        }
+}
+
+static
+void grow_map(struct us_map *map, int new_cap)
+{
+        struct us_map_kv *new = mem_alloc(sizeof(struct us_map_kv) * new_cap);
+        for (int i = 0; i < new_cap; i++) {
+                new[i].key = create_zilch();
+                new[i].val = create_zilch();
+        }
+
+        map->len = 0;
+        for (int i = 0; i < map->cap; i++) {
+                struct us_map_kv *item = &map->e[i];
+                if (item->key.type == VAL_ZILCH)
+                        continue;
+
+                struct us_map_kv *dst = find_entry(new, new_cap, item->key);
+                dst->key = item->key;
+                dst->val = item->val;
+                map->len++;
+        }
+
+        mem_free(map->e);
+
+        map->e = new;
+        map->cap = new_cap;
+}
+
+void map_set_value(struct us_map *map, struct us_val k, struct us_val v)
+{
+        // hijack the __locked key for faster lookup
+        if (k.type == VAL_STR) {
+                struct us_str *sk = get_str(k);
+                if (
+                        sk->len == 11 &&
+                        memcmp(sk->chars, "__keylocked", sk->len) == 0
+                ) {
+                        map->locked = v;
+                        return;
+                }
+        }
+
+        if (map->len + 1 > map->cap * MAP_MAX) {
+                int cap = map->cap < 8 ? 8 : map->cap * 2;
+                grow_map(map, cap);
+        }
+
+        struct us_map_kv *kv = find_entry(map->e, map->cap, k);
+        if (kv->key.type == VAL_ZILCH) {
+                if (val_as_bool(map->locked))
+                        us_err("attempt to modify keylocked map");
+                map->len++;
+        }
+
+        kv->key = k;
+        kv->val = v;
+}
+
+bool map_get_value(struct us_map *map, struct us_val k, struct us_val *v)
+{
+        if (map->len == 0)
+                goto fail;
+
+        if (k.type == VAL_STR) {
+                struct us_str *sk = get_str(k);
+                if (
+                        sk->len == 8 &&
+                        memcmp(sk->chars, "__keylocked", sk->len) == 0
+                ) {
+                        if (v)
+                                *v = map->locked;
+                        return true;
+                }
+        }
+
+        struct us_map_kv *kv = find_entry(map->e, map->cap, k);
+        if (kv->key.type == VAL_ZILCH)
+                goto fail;
+
+        if (v)
+                *v = kv->val;
+        return true;
+fail:
+        if (v)
+                *v = create_zilch();
+        return false;
+}
diff --git a/uscript/map.h b/uscript/map.h
new file mode 100644
index 0000000..83ff09e
--- /dev/null
+++ b/uscript/map.h
@@ -0,0 +1,11 @@
+#ifndef __USCRIPT_MAP_H__
+#define __USCRIPT_MAP_H__
+
+#include "common.h"
+#include "val.h"
+
+void map_set_value(struct us_map *map, struct us_val k, struct us_val v);
+// returns false if it could not find the key
+bool map_get_value(struct us_map *map, struct us_val k, struct us_val *v);
+
+#endif // __USCRIPT_MAP_H__
diff --git a/uscript/parser.c b/uscript/parser.c
index f90e6d0..2bb1afa 100644
--- a/uscript/parser.c
+++ b/uscript/parser.c
@@ -401,6 +401,58 @@ void parse_arr(struct parser *p)
 }
 
 static
+void parse_map_literal_entry(struct parser *p)
+{
+
+        if (consume(p, '[')) {
+                expr(p);
+                expect(p, ']', "unterminated key");
+        } else {
+                expect(
+                        p,
+                        TOKEN_IDENT,
+                        "expected property name"
+                );
+                parser_add_const(
+                        p,
+                        wrap_str(copy_str(p->prev.start, p->prev.len))
+                );
+        }
+
+        expect(p, '=', "expected '='");
+
+        expr(p);
+}
+
+static
+void parse_map(struct parser *p)
+{
+        int map_len = 0;
+
+        if (p->cur.kind != '}') {
+                do {
+                        if (p->cur.kind == '}')
+                                break;
+                        if (map_len > UINT8_MAX) {
+                                show_error(
+                                        p,
+                                        p->prev,
+                                        "too many elements in map literal "
+                                        "(%d/%d)",
+                                        map_len, UINT8_MAX
+                                );
+                        }
+                        parse_map_literal_entry(p);
+                        map_len++;
+                } while (consume(p, ','));
+        }
+        expect(p, '}', "unterminated map literal");
+
+        parser_add_byte(p, BC_MAP);
+        parser_add_byte(p, map_len);
+}
+
+static
 void parser_add_var_access(struct parser *p, u8 acc, int var)
 {
         parser_add_byte(p, acc);
@@ -547,13 +599,8 @@ void parse_call(struct parser *p)
 }
 
 static
-void parse_index(struct parser *p)
+void index_access(struct parser *p, bool can_assign)
 {
-        bool can_assign = p->can_assign;
-
-        expr(p);
-        expect(p, ']', "expected ']'");
-
 #define compound_op(op) \
         do { \
                 parser_add_byte(p, BC_PUSH_INDEX); \
@@ -582,17 +629,38 @@ void parse_index(struct parser *p)
 }
 
 static
+void parse_index(struct parser *p)
+{
+        bool can_assign = p->can_assign;
+        expr(p);
+        expect(p, ']', "expected ']'");
+
+        index_access(p, can_assign);
+}
+
+static
+void parse_dot(struct parser *p)
+{
+        bool can_assign = p->can_assign;
+        expect(p, TOKEN_IDENT, "expected property name");
+        parser_add_const(p, wrap_str(copy_str(p->prev.start, p->prev.len)));
+
+        index_access(p, can_assign);
+}
+#undef compound_op
+
+static
 struct expr expressions[] = {
         ['(']             = {parse_grouping, parse_call, PREC_CALL},
         [')']             = {NULL, NULL, PREC_NONE},
-        ['{']             = {NULL, NULL, PREC_NONE},
+        ['{']             = {parse_map, NULL, PREC_NONE},
         ['}']             = {NULL, NULL, PREC_NONE},
         ['[']             = {parse_arr, parse_index, PREC_CALL},
         [']']             = {NULL, NULL, PREC_NONE},
         [',']             = {NULL, NULL, PREC_NONE},
         [';']             = {NULL, NULL, PREC_NONE},
         [':']             = {NULL, NULL, PREC_NONE},
-        ['.']             = {NULL, NULL, PREC_NONE},
+        ['.']             = {NULL, parse_dot, PREC_CALL},
         ['+']             = {NULL, parse_binary, PREC_TERM},
         ['-']             = {parse_unary, parse_binary, PREC_TERM},
         ['*']             = {NULL, parse_binary, PREC_FACTOR},
@@ -745,7 +813,7 @@ void fun_stat(struct parser *p, bool is_global)
         } else {
                 while (p->cur.kind != TOKEN_END && p->cur.kind != TOKEN_EOF)
                         stat(p);
-                expect(p, TOKEN_END, "unterminated function");
+        expect(p, TOKEN_END, "unterminated function");
         }
 
         end_function(p);
diff --git a/uscript/us_debug.c b/uscript/us_debug.c
index 8898211..15465ce 100644
--- a/uscript/us_debug.c
+++ b/uscript/us_debug.c
@@ -44,6 +44,7 @@ int print_instruction(struct us_proto *proto, int idx)
         }
         case BC_SMALL_INT:
         case BC_ARR:
+        case BC_MAP:
         case BC_GET_UPVAL:
         case BC_SET_UPVAL:
         case BC_GET_LOCAL:
diff --git a/uscript/uscript.c b/uscript/uscript.c
index 008bcbe..6afdb25 100644
--- a/uscript/uscript.c
+++ b/uscript/uscript.c
@@ -4,9 +4,10 @@
 
 #include "dyn_arr.h"
 #include "lex.h"
+#include "map.h"
+#include "parser.h"
 #include "val.h"
 #include "vm.h"
-#include "parser.h"
 
 void core_print(int argc)
 {
@@ -116,6 +117,17 @@ void arr_iter(int argc)
         vm_push(wrap_cfunc(cfunc));
 }
 
+void map_has(int argc)
+{
+        (void)argc;
+        if (vm_get(0).type != VAL_MAP)
+                us_err("map:has expected a map");
+
+        struct us_map *map = get_map(vm_get(0));
+        bool has = map_get_value(map, vm_get(1), NULL);
+        vm_push(create_bool(has));
+}
+
 void us_init(void)
 {
         init_vm();
@@ -126,6 +138,8 @@ void us_init(void)
 
         us_set_cfunc("arr:iter", arr_iter, 1);
         us_set_cfunc("arr:add", arr_add, 2);
+
+        us_set_cfunc("map:has", map_has, 2);
 }
 
 void us_deinit(void)
@@ -159,3 +173,4 @@ void us_set_cfunc(const char *c_name, us_cfunc_sig c, int argc)
         int global = declare_global(name);
         set_global(global, wrap_cfunc(create_cfunc(name, c, argc)));
 }
+
diff --git a/uscript/val.c b/uscript/val.c
index 76f1376..9df040a 100644
--- a/uscript/val.c
+++ b/uscript/val.c
@@ -9,6 +9,7 @@
 #define STR_NUM_FMT "%g"
 #define STR_FUNC_FMT "<func '%s': %p>"
 #define STR_ARR_FMT "<arr: %p>"
+#define STR_MAP_FMT "<map: %p>"
 
 static
 void init_obj(struct us_val val, struct us_obj *obj)
@@ -46,6 +47,17 @@ struct us_arr *create_arr(void)
         return arr;
 }
 
+struct us_map *create_map(void)
+{
+        struct us_map *map = mem_alloc(sizeof(struct us_map));
+        map->e = NULL;
+        map->locked = create_bool(false);
+        map->len = 0;
+        map->cap = 0;
+        init_obj(wrap_map(map), &map->header);
+        return map;
+}
+
 struct us_proto *create_proto(struct us_str *name)
 {
         struct us_proto *proto = mem_alloc(sizeof(struct us_proto));
@@ -100,10 +112,16 @@ void free_val(struct us_val v)
         }
         case VAL_ARR: { 
                 struct us_arr *arr = get_arr(v);
-                da_free(arr->e);
+                mem_free(arr->e);
                 mem_free(arr);
                 break;
         }
+        case VAL_MAP: { 
+                struct us_map *map = get_map(v);
+                mem_free(map->e);
+                mem_free(map);
+                break;
+        }
         case VAL_PROTO: {
                 struct us_proto *proto = get_proto(v);
                 da_free(proto->bytecode);
@@ -156,6 +174,7 @@ bool vals_eql(struct us_val a, struct us_val b)
                         memcmp(a_str->chars, b_str->chars, a_str->len) == 0;
         }
         case VAL_ARR:
+        case VAL_MAP:
         case VAL_FUNC:
         case VAL_CFUNC:
         case VAL_UPVAL:
@@ -214,6 +233,15 @@ char *val_to_str(struct us_val v, int *len_out)
                         *len_out = len;
                 return str;
         }
+        case VAL_MAP: {
+                const struct us_map *map = get_map(v);
+                int len = snprintf(NULL, 0, STR_MAP_FMT, (void*)map);
+                char *str = mem_alloc(sizeof(char) * (len + 1));
+                snprintf(str, len + 1, STR_MAP_FMT, (void*)map);
+                if (len_out)
+                        *len_out = len;
+                return str;
+        }
         case VAL_PROTO: {
                 const struct us_proto *proto = get_proto(v);
                 int len = snprintf(
@@ -266,3 +294,12 @@ char *val_to_str(struct us_val v, int *len_out)
         return NULL;
 }
 
+bool val_as_bool(struct us_val v)
+{
+        if (v.type == VAL_ZILCH)
+                return false;
+        if (v.type == VAL_BOOL)
+                return get_bool(v);
+        return true;
+}
+
diff --git a/uscript/val.h b/uscript/val.h
index 5deb64c..3c579af 100644
--- a/uscript/val.h
+++ b/uscript/val.h
@@ -9,6 +9,7 @@
 #define create_zilch() ((struct us_val){.type=VAL_ZILCH, .dat={.number=0}})
 #define wrap_str(o)    ((struct us_val){.type=VAL_STR,   .dat={.str=(o)}})
 #define wrap_arr(o)    ((struct us_val){.type=VAL_ARR,   .dat={.arr=(o)}})
+#define wrap_map(o)    ((struct us_val){.type=VAL_MAP,   .dat={.map=(o)}})
 #define wrap_proto(o)  ((struct us_val){.type=VAL_PROTO, .dat={.proto=(o)}})
 #define wrap_func(o)   ((struct us_val){.type=VAL_FUNC,  .dat={.func=(o)}})
 #define wrap_cfunc(o)  ((struct us_val){.type=VAL_CFUNC, .dat={.cfunc=(o)}})
@@ -19,6 +20,7 @@
 #define get_obj(v)   (v.dat.obj)
 #define get_str(v)   (v.dat.str)
 #define get_arr(v)   (v.dat.arr)
+#define get_map(v)   (v.dat.map)
 #define get_proto(v) (v.dat.proto)
 #define get_func(v)  (v.dat.func)
 #define get_cfunc(v) (v.dat.cfunc)
@@ -40,6 +42,7 @@ enum val_type {
         // detected by doing a comparison with VAL_STR. See val_is_obj().
         VAL_STR,
         VAL_ARR,
+        VAL_MAP,
         VAL_PROTO,
         VAL_FUNC,
         VAL_CFUNC,
@@ -54,6 +57,7 @@ struct us_val {
                 struct us_obj *obj;
                 struct us_str *str;
                 struct us_arr *arr;
+                struct us_map *map;
                 struct us_proto *proto;
                 struct us_func *func;
                 struct us_cfunc *cfunc;
@@ -78,6 +82,19 @@ struct us_arr {
         struct us_val *e; // dyn_arr
 };
 
+struct us_map_kv {
+        struct us_val key;
+        struct us_val val;
+};
+
+struct us_map {
+        struct us_obj header;
+        struct us_map_kv *e;
+        struct us_val locked;
+        int len;
+        int cap;
+};
+
 struct us_proto {
         struct us_obj header;
         const struct us_str *name;
@@ -115,6 +132,7 @@ struct us_upval {
 struct us_str *take_str(char *chars, int len);
 struct us_str *copy_str(const char *chars, int len);
 struct us_arr *create_arr(void);
+struct us_map *create_map(void);
 struct us_proto *create_proto(struct us_str *name);
 struct us_func *create_func(struct us_proto *proto);
 struct us_cfunc *create_cfunc(struct us_str *name, us_cfunc_sig func, int argc);
@@ -127,5 +145,6 @@ void proto_add_const(struct us_proto *func, struct us_val v);
 bool vals_eql(struct us_val a, struct us_val b);
 
 char *val_to_str(struct us_val v, int *len_out);
+bool val_as_bool(struct us_val v);
 
 #endif // __USCRIPT_VAL_H__
diff --git a/uscript/vm.c b/uscript/vm.c
index c381112..97f4958 100644
--- a/uscript/vm.c
+++ b/uscript/vm.c
@@ -5,6 +5,7 @@
 #include <string.h>
 
 #include "dyn_arr.h"
+#include "map.h"
 #include "us_debug.h"
 #include "uscript.h"
 
@@ -57,16 +58,6 @@ void us_err(const char *msg, ...)
 }
 
 static
-bool as_bool(struct us_val v)
-{
-        if (v.type == VAL_ZILCH)
-                return false;
-        if (v.type == VAL_BOOL)
-                return get_bool(v);
-        return true;
-}
-
-static
 struct us_str *concat(struct us_val a, struct us_val b)
 {
         int a_len;
@@ -99,6 +90,38 @@ void close_upvals(struct us_val *to)
 }
 
 static
+void set_index(struct us_val idx_val, struct us_val idxee_val, struct us_val to)
+{
+        switch (idxee_val.type) {
+        case VAL_ARR: {
+                if (idx_val.type != VAL_NUM)
+                        us_err("arrays must be indexed by numbers");
+                int idx = (int)get_num(idx_val);
+                struct us_arr *arr = get_arr(idxee_val);
+                if (idx < 0)
+                        idx += da_len(arr->e);
+                if (idx < 0 || idx >= da_len(arr->e)) {
+                        us_err(
+                                "index out of range (%d/%d)",
+                                idx,
+                                da_len(arr->e) - 1
+                        );
+                }
+                arr->e[idx] = to;
+                break;
+        }
+        case VAL_MAP: {
+                struct us_map *map = get_map(idxee_val);
+                map_set_value(map, idx_val, to);
+                break;
+        }
+        default:
+                us_err("cannot index that value");
+                break;
+        }
+}
+
+static
 void index_val(struct us_val idx_val, struct us_val idxee_val)
 {
         switch (idxee_val.type) {
@@ -119,6 +142,17 @@ void index_val(struct us_val idx_val, struct us_val idxee_val)
                 vm_push(arr->e[idx]);
                 break;
         }
+        case VAL_MAP: {
+                struct us_map *map = get_map(idxee_val);
+                struct us_val out;
+                bool has = map_get_value(map, idx_val, &out);
+                if (!has) {
+                        char *val = val_to_str(idx_val, NULL);
+                        us_err("map does not have key '%s'", val);
+                }
+                vm_push(out);
+                break;
+        }
         case VAL_STR: {
                 if (idx_val.type != VAL_NUM)
                         us_err("strings must be indexed by numbers");
@@ -265,6 +299,19 @@ void us_exec(struct us_func *func)
                         vm_push(wrap_arr(arr));
                         break;
                 }
+                case BC_MAP: {
+                        struct us_map *map = create_map();
+                        u8 map_len = read_byte();
+                        int offset = (int)map_len * 2;
+                        for (u8 i = 0; i < map_len; i++) {
+                                struct us_val k = *(vm.stacktop - offset + i*2);
+                                struct us_val v = *(vm.stacktop - offset + i*2+1);
+                                map_set_value(map, k, v);
+                        }
+                        vm.stacktop -= map_len * 2;
+                        vm_push(wrap_map(map));
+                        break;
+                }
                 case BC_GET_LOCAL:
                         vm_push(vm.cf->stackbot[read_byte()]);
                         break;
@@ -298,23 +345,8 @@ void us_exec(struct us_func *func)
                 case BC_SET_INDEX: {
                         struct us_val set_val = vm_pop();
                         struct us_val idx_val = vm_pop();
-                        struct us_val arr_val = vm_pop();
-                        if (idx_val.type != VAL_NUM)
-                                us_err("index type must be number");
-                        if (arr_val.type != VAL_ARR)
-                                us_err("only arrays can be indexed");
-                        int idx = (int)get_num(idx_val);
-                        struct us_arr *arr = get_arr(arr_val);
-                        if (idx < 0)
-                                idx += da_len(arr->e);
-                        if (idx < 0 || idx >= da_len(arr->e)) {
-                                us_err(
-                                        "index out of range (%d/%d)",
-                                        idx,
-                                        da_len(arr->e) - 1
-                                );
-                        }
-                        arr->e[idx] = set_val;
+                        struct us_val idxee_val = vm_pop();
+                        set_index(idx_val, idxee_val, set_val);
                         vm_push(set_val);
                         break;
                 }
@@ -403,7 +435,7 @@ void us_exec(struct us_func *func)
                         break;
                 }
                 case BC_NOT: {
-                        bool negated = !as_bool(vm_pop());
+                        bool negated = !val_as_bool(vm_pop());
                         vm_push(create_bool(negated));
                         break;
                 }
@@ -432,7 +464,7 @@ void us_exec(struct us_func *func)
                 }
                 case BC_FALSEY_JMP: {
                         u16 jmp = read_short();
-                        if (as_bool(vm_peek(0)))
+                        if (val_as_bool(vm_peek(0)))
                                 break;
                         i += jmp;
                         break;
diff --git a/uscript/xbytecode.h b/uscript/xbytecode.h
index 1a7f359..5eef6db 100644
--- a/uscript/xbytecode.h
+++ b/uscript/xbytecode.h
@@ -5,6 +5,7 @@ BC(FALSE)
 BC(TRUE)
 BC(ZILCH)
 BC(ARR)
+BC(MAP)
 BC(GET_LOCAL)
 BC(SET_LOCAL)
 BC(GET_GLOBAL)