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

Deterministic Canonical Naming for Link Names and Types

1 files changed, 34 insertions, 256 deletions

diff --git a/src/types.cpp b/src/types.cpp
index c88878b9c..15e1bcf45 100644
--- a/src/types.cpp
+++ b/src/types.cpp
@@ -2774,7 +2774,37 @@ gb_internal bool are_types_identical_internal(Type *x, Type *y, bool check_tuple
 
 
 	case Type_Enum:
-		return x == y; // NOTE(bill): All enums are unique
+		if (x == y) {
+			return true;
+		}
+		if (x->Enum.fields.count != y->Enum.fields.count) {
+			return false;
+		}
+		if (!are_types_identical(x->Enum.base_type, y->Enum.base_type)) {
+			return false;
+		}
+		if (x->Enum.min_value_index != y->Enum.min_value_index) {
+			return false;
+		}
+		if (x->Enum.max_value_index != y->Enum.max_value_index) {
+			return false;
+		}
+
+		for (isize i = 0; i < x->Enum.fields.count; i++) {
+			Entity *a = x->Enum.fields[i];
+			Entity *b = y->Enum.fields[i];
+			if (a->token.string != b->token.string) {
+				return false;
+			}
+			GB_ASSERT(a->kind == b->kind);
+			GB_ASSERT(a->kind == Entity_Constant);
+			bool same = compare_exact_values(Token_CmpEq, a->Constant.value, b->Constant.value);
+			if (!same) {
+				return false;
+			}
+		}
+
+		return true;
 
 	case Type_Union:
 		if (x->Union.variants.count == y->Union.variants.count &&
@@ -2832,7 +2862,9 @@ gb_internal bool are_types_identical_internal(Type *x, Type *y, bool check_tuple
 					return false;
 				}
 			}
-			return are_types_identical(x->Struct.polymorphic_params, y->Struct.polymorphic_params);
+			// TODO(bill): Which is the correct logic here?
+			// return are_types_identical(x->Struct.polymorphic_params, y->Struct.polymorphic_params);
+			return true;
 		}
 		break;
 
@@ -4872,257 +4904,3 @@ gb_internal gbString type_to_string(Type *type, bool shorthand) {
 gb_internal gbString type_to_string_shorthand(Type *type) {
 	return type_to_string(type, true);
 }
-
-gb_internal gbString write_type_to_canonical_string(gbString w, Type *type);
-gb_internal gbString write_canonical_params(gbString w, Type *params) {
-	w = gb_string_appendc(w, "(");
-	if (params) {
-		GB_ASSERT(params->kind == Type_Tuple);
-		for_array(i, params->Tuple.variables) {
-			Entity *v = params->Tuple.variables[i];
-			if (i > 0) {
-				w = gb_string_appendc(w, ",");
-			}
-			if (v->kind == Entity_Variable) {
-				if (v->flags&EntityFlag_CVarArg) {
-					w = gb_string_appendc(w, "#c_vararg");
-				}
-				if (v->flags&EntityFlag_Ellipsis) {
-					Type *slice = base_type(v->type);
-					w = gb_string_appendc(w, "..");
-					GB_ASSERT(v->type->kind == Type_Slice);
-					w = write_type_to_canonical_string(w, slice->Slice.elem);
-				} else {
-					w = write_type_to_canonical_string(w, v->type);
-				}
-			} else if (v->kind == Entity_TypeName) {
-				w = gb_string_appendc(w, "$");
-				w = write_type_to_canonical_string(w, v->type);
-			} else if (v->kind == Entity_Constant) {
-				w = gb_string_appendc(w, "$$");
-				w = write_exact_value_to_string(w, v->Constant.value);
-			} else {
-				GB_PANIC("TODO(bill): handle non type/const parapoly parameter values");
-			}
-		}
-	}
-	return gb_string_appendc(w, ")");
-}
-
-gb_internal u64 type_hash_canonical_type(Type *type) {
-	if (type == nullptr) {
-		return 0;
-	}
-	TEMPORARY_ALLOCATOR_GUARD();
-	gbString w = write_type_to_canonical_string(gb_string_make(temporary_allocator(), ""), type);
-	u64 hash = fnv64a(w, gb_string_length(w));
-	return hash;
-}
-
-// NOTE(bill): This exists so that we deterministically hash a type by serializing it to a canonical string
-gb_internal gbString write_type_to_canonical_string(gbString w, Type *type) {
-	if (type == nullptr) {
-		return gb_string_appendc(w, "<>"); // none/void type
-	}
-
-	type = default_type(type);
-	GB_ASSERT(!is_type_untyped(type));
-
-	switch (type->kind) {
-	case Type_Basic:
-		return gb_string_append_length(w, type->Basic.name.text, type->Basic.name.len);
-	case Type_Pointer:
-		w = gb_string_append_rune(w, '^');
-		return write_type_to_canonical_string(w, type->Pointer.elem);
-	case Type_MultiPointer:
-		w = gb_string_appendc(w, "[^]");
-		return write_type_to_canonical_string(w, type->Pointer.elem);
-	case Type_SoaPointer:
-		w = gb_string_appendc(w, "#soa^");
-		return write_type_to_canonical_string(w, type->Pointer.elem);
-	case Type_EnumeratedArray:
-		if (type->EnumeratedArray.is_sparse) {
-			w = gb_string_appendc(w, "#sparse");
-		}
-		w = gb_string_append_rune(w, '[');
-		w = write_type_to_canonical_string(w, type->EnumeratedArray.index);
-		w = gb_string_append_rune(w, ']');
-		return write_type_to_canonical_string(w, type->EnumeratedArray.elem);
-	case Type_Array:
-		w = gb_string_appendc(w, gb_bprintf("[%lld]", cast(long long)type->Array.count));
-		return write_type_to_canonical_string(w, type->Array.elem);
-	case Type_Slice:
-		w = gb_string_appendc(w, "[]");
-		return write_type_to_canonical_string(w, type->Array.elem);
-	case Type_DynamicArray:
-		w = gb_string_appendc(w, "[dynamic]");
-		return write_type_to_canonical_string(w, type->DynamicArray.elem);
-	case Type_SimdVector:
-		w = gb_string_appendc(w, gb_bprintf("#simd[%lld]", cast(long long)type->SimdVector.count));
-		return write_type_to_canonical_string(w, type->SimdVector.elem);
-	case Type_Matrix:
-		if (type->Matrix.is_row_major) {
-			w = gb_string_appendc(w, "#row_major ");
-		}
-		w = gb_string_appendc(w, gb_bprintf("matrix[%lld, %lld]", cast(long long)type->Matrix.row_count, cast(long long)type->Matrix.column_count));
-		return write_type_to_canonical_string(w, type->Matrix.elem);
-	case Type_Map:
-		w = gb_string_appendc(w, "map[");
-		w = write_type_to_canonical_string(w, type->Map.key);
-		w = gb_string_appendc(w, "]");
-		return write_type_to_canonical_string(w, type->Map.value);
-
-	case Type_Enum:
-		w = gb_string_appendc(w, "enum");
-		if (type->Enum.base_type != nullptr) {
-			w = gb_string_append_rune(w, ' ');
-			w = write_type_to_canonical_string(w, type->Enum.base_type);
-			w = gb_string_append_rune(w, ' ');
-		}
-		w = gb_string_append_rune(w, '{');
-		for_array(i, type->Enum.fields) {
-			Entity *f = type->Enum.fields[i];
-			GB_ASSERT(f->kind == Entity_Constant);
-			if (i > 0) {
-				w = gb_string_appendc(w, ",");
-			}
-			w = gb_string_append_length(w, f->token.string.text, f->token.string.len);
-			w = gb_string_appendc(w, "=");
-			w = write_exact_value_to_string(w, f->Constant.value);
-		}
-		return gb_string_append_rune(w, '}');
-	case Type_BitSet:
-		w = gb_string_appendc(w, "bit_set[");
-		if (type->BitSet.elem == nullptr) {
-			w = write_type_to_canonical_string(w, type->BitSet.elem);
-		} else if (is_type_enum(type->BitSet.elem)) {
-			w = write_type_to_canonical_string(w, type->BitSet.elem);
-		} else {
-			w = gb_string_append_fmt(w, "%lld", type->BitSet.lower);
-			w = gb_string_append_fmt(w, "..=");
-			w = gb_string_append_fmt(w, "%lld", type->BitSet.upper);
-		}
-		if (type->BitSet.underlying != nullptr) {
-			w = gb_string_appendc(w, ";");
-			w = write_type_to_canonical_string(w, type->BitSet.underlying);
-		}
-		return gb_string_appendc(w, "]");
-
-	case Type_Union:
-		w = gb_string_appendc(w, "union");
-
-		switch (type->Union.kind) {
-		case UnionType_no_nil:     w = gb_string_appendc(w, "#no_nil");     break;
-		case UnionType_shared_nil: w = gb_string_appendc(w, "#shared_nil"); break;
-		}
-		if (type->Union.custom_align != 0) {
-			w = gb_string_append_fmt(w, "#align(%lld)", cast(long long)type->Union.custom_align);
-		}
-		w = gb_string_appendc(w, "{");
-		for_array(i, type->Union.variants) {
-			Type *t = type->Union.variants[i];
-			if (i > 0) w = gb_string_appendc(w, ", ");
-			w = write_type_to_canonical_string(w, t);
-		}
-		return gb_string_appendc(w, "}");
-	case Type_Struct:
-		if (type->Struct.soa_kind != StructSoa_None) {
-			switch (type->Struct.soa_kind) {
-			case StructSoa_Fixed:   w = gb_string_append_fmt(w, "#soa[%lld]", cast(long long)type->Struct.soa_count); break;
-			case StructSoa_Slice:   w = gb_string_appendc(w,    "#soa[]");                                    break;
-			case StructSoa_Dynamic: w = gb_string_appendc(w,    "#soa[dynamic]");                             break;
-			default: GB_PANIC("Unknown StructSoaKind"); break;
-			}
-			return write_type_to_canonical_string(w, type->Struct.soa_elem);
-		}
-
-		w = gb_string_appendc(w, "struct");
-		if (type->Struct.is_packed)    w = gb_string_appendc(w, "#packed");
-		if (type->Struct.is_raw_union) w = gb_string_appendc(w, "#raw_union");
-		if (type->Struct.is_no_copy)   w = gb_string_appendc(w, "#no_copy");
-		if (type->Struct.custom_min_field_align != 0) w = gb_string_append_fmt(w, "#min_field_align(%lld)", cast(long long)type->Struct.custom_min_field_align);
-		if (type->Struct.custom_max_field_align != 0) w = gb_string_append_fmt(w, "#max_field_align(%lld)", cast(long long)type->Struct.custom_max_field_align);
-		if (type->Struct.custom_align != 0)           w = gb_string_append_fmt(w, "#align(%lld)",           cast(long long)type->Struct.custom_align);
-		w = gb_string_appendc(w, "{");
-		for_array(i, type->Struct.fields) {
-			Entity *f = type->Struct.fields[i];
-			GB_ASSERT(f->kind == Entity_Variable);
-			if (i > 0) {
-				w = gb_string_appendc(w, ",");
-			}
-			w = gb_string_append_length       (w, f->token.string.text, f->token.string.len);
-			w = gb_string_appendc             (w, ":");
-			w = write_type_to_canonical_string(w, f->type);
-			String tag = type->Struct.tags[i];
-			if (tag.len != 0) {
-				String s = quote_to_ascii(heap_allocator(), tag);
-				w = gb_string_append_length(w, s.text, s.len);
-				gb_free(heap_allocator(), s.text);
-			}
-		}
-		return gb_string_appendc(w, "}");
-
-	case Type_BitField:
-		w = gb_string_appendc(w, "bit_field");
-		w = write_type_to_canonical_string(w, type->BitField.backing_type);
-		w = gb_string_appendc(w, " {");
-		for (isize i = 0; i < type->BitField.fields.count; i++) {
-			Entity *f = type->BitField.fields[i];
-			if (i > 0) {
-				w = gb_string_appendc(w, ",");
-			}
-			w = gb_string_append_length(w, f->token.string.text, f->token.string.len);
-			w = gb_string_appendc(w, ":");
-			w = write_type_to_canonical_string(w, f->type);
-			w = gb_string_appendc(w, "|");
-			w = gb_string_appendc(w, gb_bprintf("%u", type->BitField.bit_sizes[i]));
-		}
-		return gb_string_appendc(w, " }");
-
-	case Type_Proc:
-		w = gb_string_appendc(w, "proc");
-		if (default_calling_convention() != type->Proc.calling_convention) {
-			w = gb_string_appendc(w, "\"");
-			w = gb_string_appendc(w, proc_calling_convention_strings[type->Proc.calling_convention]);
-			w = gb_string_appendc(w, "\"");
-		}
-
-		w = write_canonical_params(w, type->Proc.params);
-		if (type->Proc.result_count > 0) {
-			w = gb_string_appendc(w, "->");
-			w = write_canonical_params(w, type->Proc.results);
-		}
-		return w;
-
-	case Type_Generic:
-		GB_PANIC("Type_Generic should never be hit");
-		return w;
-
-	case Type_Named:
-		if (type->Named.type_name != nullptr) {
-			Entity *e = type->Named.type_name;
-			if (e->pkg != nullptr) {
-				w = gb_string_append_length(w, e->pkg->name.text, e->pkg->name.len);
-				w = gb_string_appendc(w, ".");
-			}
-			Type *params = nullptr;
-			Entity *parent = type_get_polymorphic_parent(type, &params);
-			if (parent) {
-				w = gb_string_append_length(w, parent->token.string.text, parent->token.string.len);
-				w = write_canonical_params(w, params);
-			} else {
-				w = gb_string_append_length(w, e->token.string.text, e->token.string.len);
-			}
-		} else {
-			w = gb_string_append_length(w, type->Named.name.text, type->Named.name.len);
-		}
-		// Handle parapoly stuff here?
-		return w;
-
-	default:
-		GB_PANIC("unknown type kind %d", type->kind);
-		break;
-	}
-
-	return w;
-}
\ No newline at end of file