Add Sets to the language

4 files changed, 135 insertions, 10 deletions

diff --git a/builtins/table.c b/builtins/table.c
index 16b06f6f..5329ec24 100644
--- a/builtins/table.c
+++ b/builtins/table.c
@@ -472,8 +472,12 @@ public CORD Table$as_text(const table_t *t, bool colorize, const TypeInfo *type)
     assert(type->tag == TableInfo);
     auto table = type->TableInfo;
 
-    if (!t)
-        return CORD_all("{", generic_as_text(NULL, false, table.key), ":", generic_as_text(NULL, false, table.value), "}");
+    if (!t) {
+        if (table.value != &$Void) 
+            return CORD_all("{", generic_as_text(NULL, false, table.key), ":", generic_as_text(NULL, false, table.value), "}");
+        else
+            return CORD_all("{", generic_as_text(NULL, false, table.key), "}");
+    }
 
     int64_t val_off = value_offset(type);
     CORD c = "{";
@@ -482,8 +486,8 @@ public CORD Table$as_text(const table_t *t, bool colorize, const TypeInfo *type)
             c = CORD_cat(c, ", ");
         void *entry = GET_ENTRY(*t, i);
         c = CORD_cat(c, generic_as_text(entry, colorize, table.key));
-        c = CORD_cat(c, ":");
-        c = CORD_cat(c, generic_as_text(entry + val_off, colorize, table.value));
+        if (table.value != &$Void) 
+            c = CORD_all(c, ":", generic_as_text(entry + val_off, colorize, table.value));
     }
 
     if (t->fallback) {
@@ -522,6 +526,103 @@ public table_t Table$from_entries(array_t entries, const TypeInfo *type)
     return t;
 }
 
+// Overlap is "set intersection" in formal terms
+public table_t Table$overlap(table_t a, table_t b, const TypeInfo *type)
+{
+    // Return a table such that t[k]==a[k] for all k such that a:has(k), b:has(k), and a[k]==b[k]
+    table_t result = {};
+    const size_t offset = value_offset(type);
+    for (int64_t i = 0; i < Table$length(a); i++) {
+        void *key = GET_ENTRY(a, i);
+        void *a_value = key + offset;
+        void *b_value = Table$get(b, key, type);
+        if (b_value && generic_equal(a_value, b_value, type->TableInfo.value))
+            Table$set(&result, key, a_value, type);
+    }
+
+    if (a.fallback) {
+        result.fallback = new(table_t);
+        *result.fallback = Table$overlap(*a.fallback, b, type);
+    }
+
+    if (a.default_value && b.default_value && generic_equal(a.default_value, b.default_value, type->TableInfo.value))
+        result.default_value = a.default_value;
+
+    return result;
+}
+
+// With is "set union" in formal terms
+public table_t Table$with(table_t a, table_t b, const TypeInfo *type)
+{
+    // return a table such that t[k]==b[k] for all k such that b:has(k), and t[k]==a[k] for all k such that a:has(k) and not b:has(k)
+    table_t result = {};
+    const size_t offset = value_offset(type);
+    for (int64_t i = 0; i < Table$length(a); i++) {
+        void *key = GET_ENTRY(a, i);
+        Table$set(&result, key, key + offset, type);
+    }
+    for (int64_t i = 0; i < Table$length(b); i++) {
+        void *key = GET_ENTRY(b, i);
+        Table$set(&result, key, key + offset, type);
+    }
+
+    if (a.fallback && b.fallback) {
+        result.fallback = new(table_t);
+        *result.fallback = Table$with(*a.fallback, *b.fallback, type);
+    } else {
+        result.fallback = a.fallback ? a.fallback : b.fallback;
+    }
+
+    // B's default value takes precedence over A's
+    result.default_value = b.default_value ? b.default_value : a.default_value;
+
+    return result;
+}
+
+// Without is "set difference" in formal terms
+public table_t Table$without(table_t a, table_t b, const TypeInfo *type)
+{
+    // Return a table such that t[k]==a[k] for all k such that not b:has(k) or b[k] != a[k]
+    table_t result = {};
+    const size_t offset = value_offset(type);
+    for (int64_t i = 0; i < Table$length(a); i++) {
+        void *key = GET_ENTRY(a, i);
+        void *a_value = key + offset;
+        void *b_value = Table$get(b, key, type);
+        if (!b_value || !generic_equal(a_value, b_value, type->TableInfo.value))
+            Table$set(&result, key, a_value, type);
+    }
+
+    if (a.fallback) {
+        result.fallback = new(table_t);
+        *result.fallback = Table$without(*a.fallback, b, type);
+    }
+
+    if (a.default_value) {
+        if (!b.default_value || !generic_equal(a.default_value, b.default_value, type->TableInfo.value))
+            result.default_value = a.default_value;
+    }
+
+    return result;
+}
+
+public bool Table$is_subset_of(table_t a, table_t b, bool strict, const TypeInfo *type)
+{
+    if (a.entries.length > b.entries.length || (strict && a.entries.length == b.entries.length))
+        return false;
+
+    for (int64_t i = 0; i < Table$length(a); i++) {
+        void *found = Table$get_raw(b, GET_ENTRY(a, i), type);
+        if (!found) return false;
+    }
+    return true;
+}
+
+public bool Table$is_superset_of(table_t a, table_t b, bool strict, const TypeInfo *type)
+{
+    return Table$is_subset_of(b, a, strict, type);
+}
+
 public void *Table$str_get(table_t t, const char *key)
 {
     void **ret = Table$get(t, &key, &StrToVoidStarTable);
diff --git a/builtins/table.h b/builtins/table.h
index 36f6d75e..3b1c7f98 100644
--- a/builtins/table.h
+++ b/builtins/table.h
@@ -21,15 +21,30 @@
     table.fallback = fb; \
     table.default_value = def; \
     table; })
-#define Table_get(table_expr, key_t, val_t, key_expr, info_expr, filename, start, end) ({ \
+#define Set(item_t, item_info, N, ...)  ({ \
+    item_t ents[N] = {__VA_ARGS__}; \
+    table_t set = Table$from_entries((array_t){ \
+                       .data=memcpy(GC_MALLOC(sizeof(ents)), ents, sizeof(ents)), \
+                       .length=sizeof(ents)/sizeof(ents[0]), \
+                       .stride=(void*)&ents[1] - (void*)&ents[0], \
+                       }, $SetInfo(item_info)); \
+    set; })
+
+table_t Table$from_entries(array_t entries, const TypeInfo *type);
+void *Table$get(table_t t, const void *key, const TypeInfo *type);
+#define Table$get_value_or_fail(table_expr, key_t, val_t, key_expr, info_expr, filename, start, end) ({ \
     const table_t t = table_expr; key_t k = key_expr; const TypeInfo* info = info_expr; \
     const val_t *v = Table$get(t, &k, info); \
     if (__builtin_expect(v == NULL, 0)) \
         fail_source(filename, start, end, "The key %r is not in this table\n", generic_as_text(&k, no, info->TableInfo.key)); \
     *v; })
-
-table_t Table$from_entries(array_t entries, const TypeInfo *type);
-void *Table$get(table_t t, const void *key, const TypeInfo *type);
+#define Table$get_value_or_default(table_expr, key_t, val_t, key_expr, default_val, info_expr) ({ \
+    const table_t t = table_expr; const key_t k = key_expr; \
+    const val_t *v = Table$get(t, &k, info_expr); \
+    v ? *v : default_val; })
+#define Table$has_value(table_expr, key_expr, info_expr) ({ \
+    const table_t t = table_expr; __typeof(key_expr) k = key_expr; \
+    (Table$get(t, &k, info_expr) != NULL); })
 void *Table$get_raw(table_t t, const void *key, const TypeInfo *type);
 void *Table$entry(table_t t, int64_t n);
 void *Table$reserve(table_t *t, const void *key, const void *value, const TypeInfo *type);
@@ -39,6 +54,13 @@ 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);
 #define Table$remove_value(t, key_expr, type) ({ __typeof(key_expr) k = key_expr; Table$remove(t, &k, type); })
+
+table_t Table$overlap(table_t a, table_t b, const TypeInfo *type);
+table_t Table$with(table_t a, table_t b, const TypeInfo *type);
+table_t Table$without(table_t a, table_t b, const TypeInfo *type);
+bool Table$is_subset_of(table_t a, table_t b, bool strict, const TypeInfo *type);
+bool Table$is_superset_of(table_t a, table_t b, bool strict, 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);
diff --git a/builtins/types.c b/builtins/types.c
index 355473e9..4fb2c523 100644
--- a/builtins/types.c
+++ b/builtins/types.c
@@ -29,8 +29,8 @@ public const TypeInfo $TypeInfo = {
     .TypeInfoInfo.type_str="TypeInfo",
 };
 
-public const TypeInfo $Void = {.size=0, .align=0};
-public const TypeInfo $Abort = {.size=0, .align=0};
+public const TypeInfo $Void = {.size=0, .align=0, .tag=EmptyStruct};
+public const TypeInfo $Abort = {.size=0, .align=0, .tag=EmptyStruct};
 
 public CORD Func$as_text(const void *fn, bool colorize, const TypeInfo *type)
 {
diff --git a/builtins/types.h b/builtins/types.h
index 864a55c2..4184e8fa 100644
--- a/builtins/types.h
+++ b/builtins/types.h
@@ -58,6 +58,8 @@ typedef struct TypeInfo {
                                                  .tag=PointerInfo, .PointerInfo={.sigil=sigil_expr, .pointed=pointed_info, .is_optional=opt}})
 #define $ArrayInfo(item_info) &((TypeInfo){.size=sizeof(array_t), .align=__alignof__(array_t), \
                                 .tag=ArrayInfo, .ArrayInfo.item=item_info})
+#define $SetInfo(item_info) &((TypeInfo){.size=sizeof(table_t), .align=__alignof__(table_t), \
+                              .tag=TableInfo, .TableInfo.key=item_info, .TableInfo.value=&$Void})
 #define $TableInfo(key_expr, value_expr) &((TypeInfo){.size=sizeof(table_t), .align=__alignof__(table_t), \
                                            .tag=TableInfo, .TableInfo.key=key_expr, .TableInfo.value=value_expr})
 #define $FunctionInfo(typestr) &((TypeInfo){.size=sizeof(void*), .align=__alignof__(void*), \