Begin work on `TypeSet`

3 files changed, 246 insertions, 17 deletions

diff --git a/src/checker.cpp b/src/checker.cpp
index 054d6aeb0..6ceb31489 100644
--- a/src/checker.cpp
+++ b/src/checker.cpp
@@ -1363,6 +1363,7 @@ gb_internal void init_checker_info(CheckerInfo *i) {
 	map_init(&i->gen_types);
 	array_init(&i->type_info_types, a);
 	map_init(&i->type_info_map);
+	type_set_init(&i->type_info_set);
 	string_map_init(&i->files);
 	string_map_init(&i->packages);
 	array_init(&i->variable_init_order, a);
@@ -1397,6 +1398,7 @@ gb_internal void destroy_checker_info(CheckerInfo *i) {
 	map_destroy(&i->gen_types);
 	array_free(&i->type_info_types);
 	map_destroy(&i->type_info_map);
+	type_set_destroy(&i->type_info_set);
 	string_map_destroy(&i->files);
 	string_map_destroy(&i->packages);
 	array_free(&i->variable_init_order);
@@ -2040,7 +2042,7 @@ gb_internal void add_type_info_type_internal(CheckerContext *c, Type *t) {
 			// Unique entry
 			// NOTE(bill): map entries grow linearly and in order
 			ti_index = c->info->type_info_types.count;
-			Type_Info_Type tt = {t, type_hash_canonical_type(t)};
+			TypeInfoPair tt = {t, type_hash_canonical_type(t)};
 			array_add(&c->info->type_info_types, tt);
 		}
 		map_set(&c->checker->info.type_info_map, t, ti_index);
@@ -2293,22 +2295,11 @@ gb_internal void add_min_dep_type_info(Checker *c, Type *t) {
 		return;
 	}
 
-	auto *set = &c->info.minimum_dependency_type_info_set;
-
-	isize ti_index = type_info_index(&c->info, t, false);
-	if (ti_index < 0) {
-		add_type_info_type(&c->builtin_ctx, t); // Missing the type information
-		ti_index = type_info_index(&c->info, t, false);
-	}
-	GB_ASSERT(ti_index >= 0);
-	// IMPORTANT NOTE(bill): this must be copied as `map_set` takes a const ref
-	// and effectively assigns the `+1` of the value
-	isize const count = set->count;
-	if (map_set_if_not_previously_exists(set, ti_index+1, count)) {
-		// Type already exists;
-		return;
+	if (type_set_update(&c->info.type_info_set, t)) {
+		// return;
 	}
 
+
 	// Add nested types
 	if (t->kind == Type_Named) {
 		// NOTE(bill): Just in case
diff --git a/src/checker.hpp b/src/checker.hpp
index c9a0c3302..725c1ccf5 100644
--- a/src/checker.hpp
+++ b/src/checker.hpp
@@ -409,11 +409,27 @@ struct Defineable {
 	String pos_str;
 };
 
-struct Type_Info_Type {
+struct TypeInfoPair {
 	Type *type;
 	u64   hash; // see: type_hash_canonical_type
 };
 
+struct TypeSet {
+	TypeInfoPair *keys;
+	usize count;
+	usize capacity;
+};
+
+gb_internal void  type_set_init   (TypeSet *s, isize capacity = 16);
+gb_internal void  type_set_destroy(TypeSet *s);
+gb_internal Type *type_set_add    (TypeSet *s, Type *ptr);
+gb_internal bool  type_set_update (TypeSet *s, Type *ptr); // returns true if it previously existed
+gb_internal bool  type_set_update (TypeSet *s, TypeInfoPair pair); // returns true if it previously existed
+gb_internal bool  type_set_exists (TypeSet *s, Type *ptr);
+gb_internal void  type_set_remove (TypeSet *s, Type *ptr);
+gb_internal void  type_set_clear  (TypeSet *s);
+gb_internal TypeInfoPair *type_set_retrieve(TypeSet *s, Type *ptr);
+
 // CheckerInfo stores all the symbol information for a type-checked program
 struct CheckerInfo {
 	Checker *checker;
@@ -458,8 +474,9 @@ struct CheckerInfo {
 	PtrMap<Type *, GenTypesData *> gen_types;
 
 	BlockingMutex type_info_mutex; // NOT recursive
-	Array<Type_Info_Type> type_info_types;
+	Array<TypeInfoPair> type_info_types;
 	PtrMap<Type *, isize> type_info_map;
+	TypeSet type_info_set;
 
 	BlockingMutex foreign_mutex; // NOT recursive
 	StringMap<Entity *> foreigns;
diff --git a/src/name_canonicalization.cpp b/src/name_canonicalization.cpp
index 8edb5e968..b83441b19 100644
--- a/src/name_canonicalization.cpp
+++ b/src/name_canonicalization.cpp
@@ -44,6 +44,227 @@ gb_internal u64      type_hash_canonical_type(Type *type);
 gb_internal String   type_to_canonical_string(gbAllocator allocator, Type *type);
 gb_internal gbString temp_canonical_string(Type *type);
 
+
+struct TypeInfoPair;
+struct TypeSet;
+
+static constexpr u64 TYPE_SET_TOMBSTONE = ~(u64)(0ull);
+
+gb_internal void  type_set_init   (TypeSet *s, isize capacity);
+gb_internal void  type_set_destroy(TypeSet *s);
+gb_internal Type *type_set_add    (TypeSet *s, Type *ptr);
+gb_internal bool  type_set_update (TypeSet *s, Type *ptr); // returns true if it previously existed
+gb_internal bool  type_set_update (TypeSet *s, TypeInfoPair pair); // returns true if it previously existed
+gb_internal bool  type_set_exists (TypeSet *s, Type *ptr);
+gb_internal void  type_set_remove (TypeSet *s, Type *ptr);
+gb_internal void  type_set_clear  (TypeSet *s);
+gb_internal TypeInfoPair *type_set_retrieve(TypeSet *s, Type *ptr);
+
+gb_internal gbAllocator type_set_allocator(void) {
+	return heap_allocator();
+}
+
+struct TypeSetIterator {
+	TypeSet *set;
+	usize index;
+
+	TypeSetIterator &operator++() noexcept {
+		for (;;) {
+			++index;
+			if (set->capacity == index) {
+				return *this;
+			}
+			TypeInfoPair key = set->keys[index];
+			if (key.hash != 0 && key.hash != TYPE_SET_TOMBSTONE) {
+				return *this;
+			}
+		}
+	}
+
+	bool operator==(TypeSetIterator const &other) const noexcept {
+		return this->set == other.set && this->index == other.index;
+	}
+
+
+	operator TypeInfoPair *() const {
+		return &set->keys[index];
+	}
+};
+
+
+gb_internal TypeSetIterator begin(TypeSet &set) noexcept {
+	usize index = 0;
+	while (index < set.capacity) {
+		TypeInfoPair key = set.keys[index];
+		if (key.hash != 0 && key.hash != TYPE_SET_TOMBSTONE) {
+			break;
+		}
+		index++;
+	}
+	return TypeSetIterator{&set, index};
+}
+gb_internal TypeSetIterator end(TypeSet &set) noexcept {
+	return TypeSetIterator{&set, set.capacity};
+}
+
+
+gb_internal void type_set_init(TypeSet *s, isize capacity) {
+	GB_ASSERT(s->keys == nullptr);
+	if (capacity != 0) {
+		capacity = next_pow2_isize(gb_max(16, capacity));
+		s->keys = gb_alloc_array(type_set_allocator(), TypeInfoPair, capacity);
+		// This memory will be zeroed, no need to explicitly zero it
+	}
+	s->count = 0;
+	s->capacity = capacity;
+}
+
+gb_internal void type_set_destroy(TypeSet *s) {
+	gb_free(type_set_allocator(), s->keys);
+	s->keys = nullptr;
+	s->count = 0;
+	s->capacity = 0;
+}
+
+
+gb_internal isize type_set__find(TypeSet *s, TypeInfoPair pair) {
+	GB_ASSERT(pair.type != nullptr);
+	GB_ASSERT(pair.hash != 0);
+	if (s->count != 0) {
+		usize hash = pair.hash;
+		usize mask = s->capacity-1;
+		usize hash_index = cast(usize)hash & mask;
+		for (usize i = 0; i < s->capacity; i++) {
+			Type *key = s->keys[hash_index].type;
+			if (are_types_identical(key, pair.type)) {
+				return hash_index;
+			} else if (key == 0) {
+				return -1;
+			}
+			hash_index = (hash_index+1)&mask;
+		}
+	}
+	return -1;
+}
+gb_internal isize type_set__find(TypeSet *s, Type *ptr) {
+	GB_ASSERT(ptr != 0);
+	if (s->count != 0) {
+		usize hash = cast(usize)type_hash_canonical_type(ptr);
+		usize mask = s->capacity-1;
+		usize hash_index = cast(usize)hash & mask;
+		for (usize i = 0; i < s->capacity; i++) {
+			Type *key = s->keys[hash_index].type;
+			if (are_types_identical(key, ptr)) {
+				return hash_index;
+			} else if (key == 0) {
+				return -1;
+			}
+			hash_index = (hash_index+1)&mask;
+		}
+	}
+	return -1;
+}
+
+gb_internal bool type_set__full(TypeSet *s) {
+	return 0.75f * s->capacity <= s->count;
+}
+
+gb_internal gb_inline void type_set_grow(TypeSet *old_set) {
+	if (old_set->capacity == 0) {
+		type_set_init(old_set);
+		return;
+	}
+
+	TypeSet new_set = {};
+	type_set_init(&new_set, gb_max(old_set->capacity<<1, 16));
+
+	for (TypeInfoPair const &set : *old_set) {
+		bool was_new = type_set_update(&new_set, set);
+		GB_ASSERT(!was_new);
+	}
+	GB_ASSERT(old_set->count == new_set.count);
+
+	type_set_destroy(old_set);
+
+	*old_set = new_set;
+}
+
+
+gb_internal gb_inline bool type_set_exists(TypeSet *s, Type *ptr) {
+	return type_set__find(s, ptr) >= 0;
+}
+gb_internal gb_inline bool type_set_exists(TypeSet *s, TypeInfoPair pair) {
+	return type_set__find(s, pair) >= 0;
+}
+gb_internal gb_inline TypeInfoPair *type_set_retrieve(TypeSet *s, Type *type) {
+	isize index = type_set__find(s, type);
+	if (index >= 0) {
+		return &s->keys[index];
+	}
+	return nullptr;
+}
+
+
+gb_internal bool type_set_update(TypeSet *s, TypeInfoPair pair) { // returns true if it previously existsed
+	if (type_set_exists(s, pair)) {
+		return true;
+	}
+
+	if (s->keys == nullptr) {
+		type_set_init(s);
+	} else if (type_set__full(s)) {
+		type_set_grow(s);
+	}
+	GB_ASSERT(s->count < s->capacity);
+	GB_ASSERT(s->capacity >= 0);
+
+	usize mask = s->capacity-1;
+	usize hash = cast(usize)pair.hash;
+	usize hash_index = (cast(usize)hash) & mask;
+	GB_ASSERT(hash_index < s->capacity);
+	for (usize i = 0; i < s->capacity; i++) {
+		TypeInfoPair *key = &s->keys[hash_index];
+		GB_ASSERT(!are_types_identical(key->type, pair.type));
+		if (key->hash == TYPE_SET_TOMBSTONE || key->hash == 0) {
+			*key = pair;
+			s->count++;
+			return false;
+		}
+		hash_index = (hash_index+1)&mask;
+	}
+
+	GB_PANIC("ptr set out of memory");
+	return false;
+}
+
+gb_internal bool type_set_update(TypeSet *s, Type *ptr) { // returns true if it previously existsed
+	TypeInfoPair pair = {ptr, type_hash_canonical_type(ptr)};
+	return type_set_update(s, pair);
+}
+
+
+gb_internal Type *type_set_add(TypeSet *s, Type *ptr) {
+	type_set_update(s, ptr);
+	return ptr;
+}
+
+
+gb_internal void type_set_remove(TypeSet *s, Type *ptr) {
+	isize index = type_set__find(s, ptr);
+	if (index >= 0) {
+		GB_ASSERT(s->count > 0);
+		s->keys[index].type = nullptr;
+		s->keys[index].hash = TYPE_SET_TOMBSTONE;
+		s->count--;
+	}
+}
+
+gb_internal gb_inline void type_set_clear(TypeSet *s) {
+	s->count = 0;
+	gb_zero_size(s->keys, s->capacity*gb_size_of(*s->keys));
+}
+
+
 gb_internal gbString write_canonical_params(gbString w, Type *params) {
 	w = gb_string_appendc(w, "(");
 	if (params) {