Merge pull request #4855 from odin-lang/bill/canonical-type-hashing

Deterministic Canonical Naming for Link Names and Types

1 files changed, 91 insertions, 47 deletions

diff --git a/src/checker.cpp b/src/checker.cpp
index bfcabe4fa..f1f1b2556 100644
--- a/src/checker.cpp
+++ b/src/checker.cpp
@@ -3,7 +3,10 @@
 #include "entity.cpp"
 #include "types.cpp"
 
-String get_final_microarchitecture();
+
+gb_internal u64 type_hash_canonical_type(Type *type);
+
+gb_internal String get_final_microarchitecture();
 
 gb_internal void check_expr(CheckerContext *c, Operand *operand, Ast *expression);
 gb_internal void check_expr_or_type(CheckerContext *c, Operand *operand, Ast *expression, Type *type_hint=nullptr);
@@ -170,7 +173,7 @@ gb_internal void init_decl_info(DeclInfo *d, Scope *scope, DeclInfo *parent) {
 	d->parent = parent;
 	d->scope  = scope;
 	ptr_set_init(&d->deps, 0);
-	ptr_set_init(&d->type_info_deps, 0);
+	type_set_init(&d->type_info_deps, 0);
 	d->labels.allocator = heap_allocator();
 	d->variadic_reuses.allocator = heap_allocator();
 	d->variadic_reuse_max_bytes = 0;
@@ -355,6 +358,10 @@ gb_internal void check_open_scope(CheckerContext *c, Ast *node) {
 		scope->flags |= ScopeFlag_Type;
 		break;
 	}
+	if (c->decl && c->decl->proc_lit) {
+		// Number the scopes within a procedure body depth-first
+		scope->index = c->decl->scope_index++;
+	}
 	c->scope = scope;
 	c->state_flags |= StateFlag_bounds_check;
 }
@@ -825,11 +832,17 @@ gb_internal void add_dependency(CheckerInfo *info, DeclInfo *d, Entity *e) {
 	rw_mutex_unlock(&d->deps_mutex);
 }
 gb_internal void add_type_info_dependency(CheckerInfo *info, DeclInfo *d, Type *type) {
-	if (d == nullptr) {
+	if (d == nullptr || type == nullptr) {
 		return;
 	}
+	if (type->kind == Type_Named) {
+		Entity *e = type->Named.type_name;
+		if (e->TypeName.is_type_alias) {
+			type = type->Named.base;
+		}
+	}
 	rw_mutex_lock(&d->type_info_deps_mutex);
-	ptr_set_add(&d->type_info_deps, type);
+	type_set_add(&d->type_info_deps, type);
 	rw_mutex_unlock(&d->type_info_deps_mutex);
 }
 
@@ -1358,8 +1371,12 @@ gb_internal void init_checker_info(CheckerInfo *i) {
 	string_map_init(&i->foreigns);
 	// map_init(&i->gen_procs);
 	map_init(&i->gen_types);
+
 	array_init(&i->type_info_types, a);
-	map_init(&i->type_info_map);
+	type_set_init(&i->min_dep_type_info_set);
+	map_init(&i->minimum_dependency_type_info_index_map);
+
+	// map_init(&i->type_info_map);
 	string_map_init(&i->files);
 	string_map_init(&i->packages);
 	array_init(&i->variable_init_order, a);
@@ -1392,8 +1409,11 @@ gb_internal void destroy_checker_info(CheckerInfo *i) {
 	string_map_destroy(&i->foreigns);
 	// map_destroy(&i->gen_procs);
 	map_destroy(&i->gen_types);
+
 	array_free(&i->type_info_types);
-	map_destroy(&i->type_info_map);
+	type_set_destroy(&i->min_dep_type_info_set);
+	map_destroy(&i->minimum_dependency_type_info_index_map);
+
 	string_map_destroy(&i->files);
 	string_map_destroy(&i->packages);
 	array_free(&i->variable_init_order);
@@ -1627,41 +1647,36 @@ gb_internal void check_remove_expr_info(CheckerContext *c, Ast *e) {
 	}
 }
 
-
-gb_internal isize type_info_index(CheckerInfo *info, Type *type, bool error_on_failure) {
-	type = default_type(type);
-	if (type == t_llvm_bool) {
-		type = t_bool;
-	}
-
-	mutex_lock(&info->type_info_mutex);
+gb_internal isize type_info_index(CheckerInfo *info, TypeInfoPair pair, bool error_on_failure) {
+	mutex_lock(&info->minimum_dependency_type_info_mutex);
 
 	isize entry_index = -1;
-	isize *found_entry_index = map_get(&info->type_info_map, type);
+	uintptr hash = cast(uintptr)pair.hash;
+	isize *found_entry_index = map_get(&info->minimum_dependency_type_info_index_map, hash);
 	if (found_entry_index) {
 		entry_index = *found_entry_index;
 	}
-	if (entry_index < 0) {
-		// NOTE(bill): Do manual linear search
-		for (auto const &e : info->type_info_map) {
-			if (are_types_identical_unique_tuples(e.key, type)) {
-				entry_index = e.value;
-				// NOTE(bill): Add it to the search map
-				map_set(&info->type_info_map, type, entry_index);
-				break;
-			}
-		}
-	}
-
-	mutex_unlock(&info->type_info_mutex);
+	mutex_unlock(&info->minimum_dependency_type_info_mutex);
 
 	if (error_on_failure && entry_index < 0) {
-		compiler_error("Type_Info for '%s' could not be found", type_to_string(type));
+		compiler_error("Type_Info for '%s' could not be found", type_to_string(pair.type));
 	}
 	return entry_index;
 }
 
 
+gb_internal isize type_info_index(CheckerInfo *info, Type *type, bool error_on_failure) {
+	type = default_type(type);
+	if (type == t_llvm_bool) {
+		type = t_bool;
+	}
+
+	u64 hash = type_hash_canonical_type(type);
+	return type_info_index(info, {type, hash}, error_on_failure);
+}
+
+
+
 gb_internal void add_untyped(CheckerContext *c, Ast *expr, AddressingMode mode, Type *type, ExactValue const &value) {
 	if (expr == nullptr) {
 		return;
@@ -2013,8 +2028,12 @@ gb_internal void add_type_info_type_internal(CheckerContext *c, Type *t) {
 	}
 
 	add_type_info_dependency(c->info, c->decl, t);
-
+#if 0
 	MUTEX_GUARD_BLOCK(&c->info->type_info_mutex) {
+		if (type_set_update(&c->info->type_info_set, t)) {
+			// return;
+		}
+
 		auto found = map_get(&c->info->type_info_map, t);
 		if (found != nullptr) {
 			// Types have already been added
@@ -2037,7 +2056,8 @@ 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;
-			array_add(&c->info->type_info_types, 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);
 
@@ -2232,6 +2252,7 @@ gb_internal void add_type_info_type_internal(CheckerContext *c, Type *t) {
 		GB_PANIC("Unhandled type: %*.s %d", LIT(type_strings[bt->kind]), bt->kind);
 		break;
 	}
+#endif
 }
 
 
@@ -2289,19 +2310,7 @@ 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;
+	if (type_set_update(&c->info.min_dep_type_info_set, t)) {
 		return;
 	}
 
@@ -2501,8 +2510,8 @@ gb_internal void add_dependency_to_set(Checker *c, Entity *entity) {
 	if (decl == nullptr) {
 		return;
 	}
-	for (Type *t : decl->type_info_deps) {
-		add_min_dep_type_info(c, t);
+	for (TypeInfoPair const tt : decl->type_info_deps) {
+		add_min_dep_type_info(c, tt.type);
 	}
 
 	for (Entity *e : decl->deps) {
@@ -2702,7 +2711,6 @@ gb_internal void generate_minimum_dependency_set(Checker *c, Entity *start) {
 	isize min_dep_set_cap = next_pow2_isize(entity_count*4); // empirically determined factor
 
 	ptr_set_init(&c->info.minimum_dependency_set, min_dep_set_cap);
-	map_init(&c->info.minimum_dependency_type_info_set);
 
 #define FORCE_ADD_RUNTIME_ENTITIES(condition, ...) do {                                              \
 	if (condition) {                                                                             \
@@ -3894,6 +3902,7 @@ gb_internal DECL_ATTRIBUTE_PROC(type_decl_attribute) {
 #include "check_expr.cpp"
 #include "check_builtin.cpp"
 #include "check_type.cpp"
+#include "name_canonicalization.cpp"
 #include "check_decl.cpp"
 #include "check_stmt.cpp"
 
@@ -6724,6 +6733,41 @@ gb_internal void check_parsed_files(Checker *c) {
 		add_type_and_value(&c->builtin_ctx, u.expr, u.info->mode, u.info->type, u.info->value);
 	}
 
+	TIME_SECTION("initialize and check for collisions in type info array");
+	{
+		for (auto const &tt : c->info.min_dep_type_info_set) {
+			array_add(&c->info.type_info_types, tt);
+		}
+		array_sort(c->info.type_info_types, type_info_pair_cmp);
+
+		map_reserve(&c->info.minimum_dependency_type_info_index_map, c->info.type_info_types.count);
+
+		for_array(i, c->info.type_info_types) {
+			auto const &tt = c->info.type_info_types[i];
+			bool exists = map_set_if_not_previously_exists(&c->info.minimum_dependency_type_info_index_map, cast(uintptr)tt.hash, i);
+			if (!exists) {
+				continue;
+			}
+			for (auto const &entry : c->info.minimum_dependency_type_info_index_map) {
+				if (entry.key != cast(uintptr)tt.hash) {
+					continue;
+				}
+				auto const &other = c->info.type_info_types[entry.value];
+				if (are_types_identical_unique_tuples(tt.type, other.type)) {
+					continue;
+				}
+				gbString t = temp_canonical_string(tt.type);
+				gbString o = temp_canonical_string(other.type);
+				GB_PANIC("%s (%s) %llu vs %s (%s) %llu",
+				         type_to_string(tt.type, false),    t, cast(unsigned long long)tt.hash,
+				         type_to_string(other.type, false), o, cast(unsigned long long)other.hash);
+			}
+		}
+
+		GB_ASSERT(c->info.minimum_dependency_type_info_index_map.count <= c->info.type_info_types.count);
+	}
+
+
 	TIME_SECTION("sort init and fini procedures");
 	check_sort_init_and_fini_procedures(c);