Make default table removal behavior deterministic, but have caches

explicitly use random eviction.

4 files changed, 32 insertions, 57 deletions

diff --git a/builtins/table.c b/builtins/table.c
index 9f6b1f13..f9623342 100644
--- a/builtins/table.c
+++ b/builtins/table.c
@@ -297,12 +297,9 @@ public void Table$remove(table_t *t, const void *key, const TypeInfo *type)
     // TODO: this work doesn't need to be done if the key is already missing
     maybe_copy_on_write(t, type);
 
-    // If unspecified, pop a random key:
-    if (!key) {
-        hdebug("Popping random key\n");
-        uint32_t index = arc4random_uniform(t->entries.length);
-        key = GET_ENTRY(*t, index);
-    }
+    // If unspecified, pop the last key:
+    if (!key)
+        key = GET_ENTRY(*t, t->entries.length-1);
 
     // Steps: look up the bucket for the removed key
     // If missing, then return immediately
@@ -396,6 +393,13 @@ public void Table$clear(table_t *t)
     memset(t, 0, sizeof(table_t));
 }
 
+public table_t Table$sorted(table_t t, const TypeInfo *type)
+{
+    closure_t cmp = (closure_t){.fn=generic_compare, .userdata=(void*)type->TableInfo.key};
+    array_t entries = Array$sorted(t.entries, cmp, entry_size(type));
+    return Table$from_entries(entries, type);
+}
+
 public bool Table$equal(const table_t *x, const table_t *y, const TypeInfo *type)
 {
     assert(type->tag == TableInfo);
@@ -408,26 +412,7 @@ public bool Table$equal(const table_t *x, const table_t *y, const TypeInfo *type
     if ((x->fallback != NULL) != (y->fallback != NULL))
         return false;
 
-    const TypeInfo *value_type = type->TableInfo.value;
-    for (int64_t i = 0, length = Table$length(*x); i < length; i++) {
-        void *x_key = GET_ENTRY(*x, i);
-        void *x_value = x_key + value_offset(type);
-        void *y_value = Table$get_raw(*y, x_key, type);
-        if (!y_value)
-            return false;
-        if (!generic_equal(x_value, y_value, value_type))
-            return false;
-    }
-
-    if (x->default_value && y->default_value
-        && !generic_equal(x->default_value, y->default_value, value_type))
-        return false;
-
-    if (x->fallback && y->fallback
-        && !Table$equal(x->fallback, y->fallback, type))
-        return false;
-    
-    return true;
+    return (Table$compare(x, y, type) == 0);
 }
 
 public int32_t Table$compare(const table_t *x, const table_t *y, const TypeInfo *type)
@@ -439,12 +424,9 @@ public int32_t Table$compare(const table_t *x, const table_t *y, const TypeInfo
     else if (x->entries.length != y->entries.length)
         return (x->entries.length > y->entries.length) - (x->entries.length < y->entries.length);
 
-    closure_t cmp = (closure_t){.fn=generic_compare, .userdata=(void*)table.key};
-    array_t x_entries = Array$sorted(x->entries, cmp, entry_size(type));
-    array_t y_entries = Array$sorted(y->entries, cmp, entry_size(type));
-    for (int64_t i = 0; i < x_entries.length; i++) {
-        void *x_key = x_entries.data + x_entries.stride * i;
-        void *y_key = y_entries.data + y_entries.stride * i;
+    for (int64_t i = 0; i < x->entries.length; i++) {
+        void *x_key = x->entries.data + x->entries.stride * i;
+        void *y_key = y->entries.data + y->entries.stride * i;
         int32_t diff = generic_compare(x_key, y_key, table.key);
         if (diff != 0) return diff;
         void *x_value = x_key + value_offset(type);
@@ -473,30 +455,14 @@ public uint32_t Table$hash(const table_t *t, const TypeInfo *type)
 {
     assert(type->tag == TableInfo);
     // Table hashes are computed as:
-    // hash(#t, xor(hash(k) for k in t.keys), xor(hash(v) for v in t.values), hash(t.fallback), hash(t.default))
+    // hash(hash(t.keys), hash(t.values), hash(t.fallback), hash(t.default))
     // Where fallback and default hash to zero if absent
     auto table = type->TableInfo;
-    int64_t val_off = value_offset(type);
-
-    uint32_t key_hashes = 0, value_hashes = 0, fallback_hash = 0, default_hash = 0;
-    for (int64_t i = 0, length = Table$length(*t); i < length; i++) {
-        void *entry = GET_ENTRY(*t, i);
-        key_hashes ^= generic_hash(entry, table.key);
-        value_hashes ^= generic_hash(entry + val_off, table.value);
-    }
-
-    if (t->fallback)
-        fallback_hash = Table$hash(t->fallback, type);
-
-    if (t->default_value)
-        default_hash = generic_hash(t->default_value, table.value);
-
-    struct { int64_t len; uint32_t k, v, f, d; } components = {
-        Table$length(*t),
-        key_hashes,
-        value_hashes,
-        fallback_hash,
-        default_hash,
+    uint32_t components[] = {
+        Array$hash(&t->entries, $ArrayInfo(table.key)),
+        Array$hash(&t->entries + value_offset(type), $ArrayInfo(table.value)),
+        t->fallback ? Table$hash(t->fallback, type) : 0,
+        t->default_value ? generic_hash(t->default_value, table.value) : 0,
     };
     uint32_t hash;
     halfsiphash(&components, sizeof(components), TOMO_HASH_KEY, (uint8_t*)&hash, sizeof(hash));
diff --git a/builtins/table.h b/builtins/table.h
index a33b5775..82e12286 100644
--- a/builtins/table.h
+++ b/builtins/table.h
@@ -39,6 +39,7 @@ void Table$set(table_t *t, const void *key, const void *value, const TypeInfo *t
 #define Table$reserve_value(t, key_expr, type) ({ __typeof(key_expr) k = key_expr; Table$reserve(t, &k, NULL, type); })
 void Table$remove(table_t *t, const void *key, const TypeInfo *type);
 void Table$clear(table_t *t);
+table_t Table$sorted(table_t t, const TypeInfo *type);
 void Table$mark_copy_on_write(table_t *t);
 int32_t Table$compare(const table_t *x, const table_t *y, const TypeInfo *type);
 bool Table$equal(const table_t *x, const table_t *y, const TypeInfo *type);
diff --git a/compile.c b/compile.c
index 3b6b50f9..3891f66e 100644
--- a/compile.c
+++ b/compile.c
@@ -621,7 +621,10 @@ CORD compile_statement(env_t *env, ast_t *ast)
             body = CORD_asprintf("{\n%r\n}", body);
         env->code->funcs = CORD_all(env->code->funcs, code, " ", body, "\n");
 
-        if (fndef->cache && fndef->cache->tag == Int && Match(fndef->cache, Int)->i > 0) {
+        if (fndef->cache && fndef->cache->tag == Int) {
+            int64_t cache_size = Match(fndef->cache, Int)->i;
+            if (cache_size <= 0)
+                code_err(fndef->cache, "Cache sizes must be greater than 0");
             const char *arg_type_name = heap_strf("%s$args", Match(fndef->name, Var)->name);
             ast_t *args_def = FakeAST(StructDef, .name=arg_type_name, .fields=fndef->args);
             prebind_statement(env, args_def);
@@ -635,9 +638,9 @@ CORD compile_statement(env_t *env, ast_t *ast)
                 all_args = CORD_all(all_args, "$", arg->name, arg->next ? ", " : CORD_EMPTY);
 
             CORD pop_code = CORD_EMPTY;
-            if (fndef->cache->tag == Int && Match(fndef->cache, Int)->i < INT64_MAX) {
+            if (fndef->cache->tag == Int && cache_size < INT64_MAX) {
                 pop_code = CORD_all("if (Table$length(cache) > ", compile(body_scope, fndef->cache),
-                                    ") Table$remove(&cache, NULL, table_type);\n");
+                                    ") Table$remove(&cache, cache.entries.data + cache.entries.stride*Int$random(0, cache.entries.length-1), table_type);\n");
             }
 
             CORD arg_typedef = compile_struct_typedef(env, args_def);
@@ -1961,6 +1964,10 @@ CORD compile(env_t *env, ast_t *ast)
                 CORD self = compile_to_pointer_depth(env, call->self, 1, false);
                 (void)compile_arguments(env, ast, NULL, call->args);
                 return CORD_all("Table$clear(", self, ")");
+            } else if (streq(call->name, "sorted")) {
+                CORD self = compile_to_pointer_depth(env, call->self, 0, false);
+                (void)compile_arguments(env, ast, NULL, call->args);
+                return CORD_all("Table$sorted(", self, ", ", compile_type_info(env, self_value_t), ")");
             } else code_err(ast, "There is no '%s' method for tables", call->name);
         }
         default: {
diff --git a/typecheck.c b/typecheck.c
index a790f73d..9e94ea2f 100644
--- a/typecheck.c
+++ b/typecheck.c
@@ -685,6 +685,7 @@ type_t *get_type(env_t *env, ast_t *ast)
             else if (streq(call->name, "set")) return Type(VoidType);
             else if (streq(call->name, "remove")) return Type(VoidType);
             else if (streq(call->name, "clear")) return Type(VoidType);
+            else if (streq(call->name, "sorted")) return self_value_t;
             else code_err(ast, "There is no '%s' method for tables", call->name);
         }
         default: {