From 99d91ccd31366e78c7ec0e94b5e3d473806721ed Mon Sep 17 00:00:00 2001 From: gingerBill Date: Mon, 17 Feb 2025 11:32:49 +0000 Subject: Work on making name mangling deterministic --- src/checker.cpp | 1 + 1 file changed, 1 insertion(+) (limited to 'src/checker.cpp') diff --git a/src/checker.cpp b/src/checker.cpp index bfcabe4fa..c74a72a14 100644 --- a/src/checker.cpp +++ b/src/checker.cpp @@ -3894,6 +3894,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" -- cgit v1.2.3 From 9b26bb2e6a1e32e17102550b481c6909549b87e5 Mon Sep 17 00:00:00 2001 From: gingerBill Date: Mon, 17 Feb 2025 13:10:38 +0000 Subject: Begin work on hash types --- src/checker.cpp | 44 +++++++++++++++++++++++++++++++++++++++++-- src/checker.hpp | 7 ++++++- src/llvm_backend.cpp | 7 ++++--- src/llvm_backend_general.cpp | 2 -- src/llvm_backend_type.cpp | 6 +++--- src/name_canonicalization.cpp | 25 +++++++++++++++++++----- src/ptr_set.cpp | 10 +++++----- src/types.cpp | 36 +++++++++++++++++++++++++++++++++-- 8 files changed, 114 insertions(+), 23 deletions(-) (limited to 'src/checker.cpp') diff --git a/src/checker.cpp b/src/checker.cpp index c74a72a14..054d6aeb0 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); @@ -2037,7 +2040,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); + Type_Info_Type 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); @@ -6725,6 +6729,42 @@ 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("check for type hash collisions"); + { + PtrSet found = {}; + ptr_set_init(&found, c->info.type_info_types.count); + defer (ptr_set_destroy(&found)); + for (auto const &tt : c->info.type_info_types) { + if (ptr_set_update(&found, cast(uintptr)tt.hash)) { + Type *other_type = nullptr; + for (auto const &other : c->info.type_info_types) { + if (&tt == &other) { + continue; + } + if (cast(uintptr)other.hash == cast(uintptr)tt.hash && + !are_types_identical(tt.type, other.type)) { + other_type = other.type; + break; + } + } + if (other_type != nullptr) { + String ts = type_to_canonical_string(temporary_allocator(), tt.type); + String os = type_to_canonical_string(temporary_allocator(), other_type); + if (ts != os) { + compiler_error("%s found type hash collision with %s (hash = %llu)\n" + "%s vs %s\n", + type_to_string(tt.type), type_to_string(other_type), cast(unsigned long long)tt.hash, + temp_canonical_string(tt.type), + temp_canonical_string(other_type) + ); + } + } + } + } + } + + + TIME_SECTION("sort init and fini procedures"); check_sort_init_and_fini_procedures(c); diff --git a/src/checker.hpp b/src/checker.hpp index 472ab8e50..c9a0c3302 100644 --- a/src/checker.hpp +++ b/src/checker.hpp @@ -409,6 +409,11 @@ struct Defineable { String pos_str; }; +struct Type_Info_Type { + Type *type; + u64 hash; // see: type_hash_canonical_type +}; + // CheckerInfo stores all the symbol information for a type-checked program struct CheckerInfo { Checker *checker; @@ -453,7 +458,7 @@ struct CheckerInfo { PtrMap gen_types; BlockingMutex type_info_mutex; // NOT recursive - Array type_info_types; + Array type_info_types; PtrMap type_info_map; BlockingMutex foreign_mutex; // NOT recursive diff --git a/src/llvm_backend.cpp b/src/llvm_backend.cpp index 0896ea8c7..8cb480dd4 100644 --- a/src/llvm_backend.cpp +++ b/src/llvm_backend.cpp @@ -24,7 +24,7 @@ #include "llvm_backend_stmt.cpp" #include "llvm_backend_proc.cpp" -String get_default_microarchitecture() { +gb_internal String get_default_microarchitecture() { String default_march = str_lit("generic"); if (build_context.metrics.arch == TargetArch_amd64) { // NOTE(bill): x86-64-v2 is more than enough for everyone @@ -47,7 +47,7 @@ String get_default_microarchitecture() { return default_march; } -String get_final_microarchitecture() { +gb_internal String get_final_microarchitecture() { BuildContext *bc = &build_context; String microarch = bc->microarch; @@ -3182,7 +3182,8 @@ gb_internal bool lb_generate_code(lbGenerator *gen) { isize count = 0; isize offsets_extra = 0; - for (Type *t : m->info->type_info_types) { + for (auto const &tt : m->info->type_info_types) { + Type *t = tt.type; isize index = lb_type_info_index(m->info, t, false); if (index < 0) { continue; diff --git a/src/llvm_backend_general.cpp b/src/llvm_backend_general.cpp index 7fdfa0bb2..b9ae3d254 100644 --- a/src/llvm_backend_general.cpp +++ b/src/llvm_backend_general.cpp @@ -1460,8 +1460,6 @@ gb_internal String lb_get_entity_name(lbModule *m, Entity *e) { w = write_canonical_entity_name(w, e); defer (gb_string_free(w)); - gb_printf_err("%s\n", w); - String name = copy_string(permanent_allocator(), make_string(cast(u8 const *)w, gb_string_length(w))); if (e->kind == Entity_TypeName) { diff --git a/src/llvm_backend_type.cpp b/src/llvm_backend_type.cpp index 6c12b37be..6f9f94fbd 100644 --- a/src/llvm_backend_type.cpp +++ b/src/llvm_backend_type.cpp @@ -12,7 +12,7 @@ gb_internal isize lb_type_info_index(CheckerInfo *info, Type *type, bool err_on_ gb_printf_err("NOT FOUND lb_type_info_index:\n\t%s\n\t@ index %td\n\tmax count: %u\nFound:\n", type_to_string(type), index, set->count); for (auto const &entry : *set) { isize type_info_index = entry.key; - gb_printf_err("\t%s\n", type_to_string(info->type_info_types[type_info_index])); + gb_printf_err("\t%s\n", type_to_string(info->type_info_types[type_info_index].type)); } GB_PANIC("NOT FOUND"); } @@ -280,7 +280,7 @@ gb_internal void lb_setup_type_info_data_giant_array(lbModule *m, i64 global_typ LLVMTypeRef *modified_types = lb_setup_modified_types_for_type_info(m, global_type_info_data_entity_count); defer (gb_free(heap_allocator(), modified_types)); for_array(type_info_type_index, info->type_info_types) { - Type *t = info->type_info_types[type_info_type_index]; + Type *t = info->type_info_types[type_info_type_index].type; if (t == nullptr || t == t_invalid) { continue; } @@ -343,7 +343,7 @@ gb_internal void lb_setup_type_info_data_giant_array(lbModule *m, i64 global_typ }; for_array(type_info_type_index, info->type_info_types) { - Type *t = info->type_info_types[type_info_type_index]; + Type *t = info->type_info_types[type_info_type_index].type; if (t == nullptr || t == t_invalid) { continue; } diff --git a/src/name_canonicalization.cpp b/src/name_canonicalization.cpp index 3910c573d..8edb5e968 100644 --- a/src/name_canonicalization.cpp +++ b/src/name_canonicalization.cpp @@ -7,7 +7,7 @@ * builtin names - just their normal name e.g. `i32` or `string` * nested - pkg.parent1.parent2.name * file private - pkg.[file_name].name - * Example: `foo.[bar.odin].Type` + * Example: `pkg.[file.odin].Type` * polymorphic procedure/type - pkg.foo::TYPE * naming convention for parameters * type @@ -15,7 +15,7 @@ * $$constant_parameter * Example: `foo.to_thing::proc(u64)->([]u8)` * nested decl in polymorphic procedure - pkg.foo::TYPE.name - * anonymous procedures - pkg.foo.$anon123 + * anonymous procedures - pkg.foo.$anon[file.odin:123] * 123 is the file offset in bytes @@ -38,7 +38,12 @@ #define CANONICAL_NONE_TYPE "<>" + gb_internal gbString write_type_to_canonical_string(gbString w, Type *type); +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); + gb_internal gbString write_canonical_params(gbString w, Type *params) { w = gb_string_appendc(w, "("); if (params) { @@ -81,7 +86,7 @@ gb_internal u64 type_hash_canonical_type(Type *type) { 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; + return hash ? hash : 1; } gb_internal String type_to_canonical_string(gbAllocator allocator, Type *type) { @@ -90,6 +95,11 @@ gb_internal String type_to_canonical_string(gbAllocator allocator, Type *type) { return make_string(cast(u8 const *)w, gb_string_length(w)); } +gb_internal gbString temp_canonical_string(Type *type) { + gbString w = gb_string_make(temporary_allocator(), ""); + return write_type_to_canonical_string(w, type); +} + gb_internal void print_scope_flags(Scope *s) { if (s->flags & ScopeFlag_Pkg) gb_printf_err("Pkg "); if (s->flags & ScopeFlag_Builtin) gb_printf_err("Builtin "); @@ -156,7 +166,8 @@ gb_internal gbString write_canonical_parent_prefix(gbString w, Entity *e, bool i } if (e->kind == Entity_Procedure && e->Procedure.is_anonymous) { - w = gb_string_appendc(w, gb_bprintf(CANONICAL_ANON_PREFIX "%d", e->token.pos.offset)); + String file_name = filename_without_directory(e->file->fullpath); + w = gb_string_appendc(w, gb_bprintf(CANONICAL_ANON_PREFIX "[%.*s:%d]", LIT(file_name), e->token.pos.offset)); } else { w = gb_string_append_length(w, e->token.string.text, e->token.string.len); } @@ -449,8 +460,12 @@ gb_internal gbString write_type_to_canonical_string(gbString w, Type *type) { } return w; + case Type_Tuple: + w = gb_string_appendc(w, "params"); + w = write_canonical_params(w, type); + return w; default: - GB_PANIC("unknown type kind %d", type->kind); + GB_PANIC("unknown type kind %d %.*s", type->kind, LIT(type_strings[type->kind])); break; } diff --git a/src/ptr_set.cpp b/src/ptr_set.cpp index ff4befc37..5097e2bb6 100644 --- a/src/ptr_set.cpp +++ b/src/ptr_set.cpp @@ -42,7 +42,7 @@ gb_internal void ptr_set_destroy(PtrSet *s) { template gb_internal isize ptr_set__find(PtrSet *s, T ptr) { - GB_ASSERT(ptr != nullptr); + GB_ASSERT(ptr != 0); if (s->count != 0) { #if 0 for (usize i = 0; i < s->capacity; i++) { @@ -58,7 +58,7 @@ gb_internal isize ptr_set__find(PtrSet *s, T ptr) { T key = s->keys[hash_index]; if (key == ptr) { return hash_index; - } else if (key == nullptr) { + } else if (key == 0) { return -1; } hash_index = (hash_index+1)&mask; @@ -122,7 +122,7 @@ gb_internal bool ptr_set_update(PtrSet *s, T ptr) { // returns true if it pre for (usize i = 0; i < s->capacity; i++) { T *key = &s->keys[hash_index]; GB_ASSERT(*key != ptr); - if (*key == (T)PtrSet::TOMBSTONE || *key == nullptr) { + if (*key == (T)PtrSet::TOMBSTONE || *key == 0) { *key = ptr; s->count++; return false; @@ -169,7 +169,7 @@ struct PtrSetIterator { return *this; } T key = set->keys[index]; - if (key != nullptr && key != (T)PtrSet::TOMBSTONE) { + if (key != 0 && key != (T)PtrSet::TOMBSTONE) { return *this; } } @@ -191,7 +191,7 @@ gb_internal PtrSetIterator begin(PtrSet &set) noexcept { usize index = 0; while (index < set.capacity) { T key = set.keys[index]; - if (key != nullptr && key != (T)PtrSet::TOMBSTONE) { + if (key != 0 && key != (T)PtrSet::TOMBSTONE) { break; } index++; diff --git a/src/types.cpp b/src/types.cpp index d6dea56ad..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; -- cgit v1.2.3 From b8f057951c47ccb07316fcd936dba9b71e052d1f Mon Sep 17 00:00:00 2001 From: gingerBill Date: Mon, 17 Feb 2025 13:46:17 +0000 Subject: Begin work on `TypeSet` --- src/checker.cpp | 21 ++-- src/checker.hpp | 21 +++- src/name_canonicalization.cpp | 221 ++++++++++++++++++++++++++++++++++++++++++ 3 files changed, 246 insertions(+), 17 deletions(-) (limited to 'src/checker.cpp') 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 gen_types; BlockingMutex type_info_mutex; // NOT recursive - Array type_info_types; + Array type_info_types; PtrMap type_info_map; + TypeSet type_info_set; BlockingMutex foreign_mutex; // NOT recursive StringMap 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) { -- cgit v1.2.3 From 4a29d9bb845050c483e537c7a0d6b2889af0f7bc Mon Sep 17 00:00:00 2001 From: gingerBill Date: Mon, 17 Feb 2025 16:29:42 +0000 Subject: Simplify type info table construction --- src/checker.cpp | 162 ++++++++++++++++++++++++++---------------- src/checker.hpp | 17 +++-- src/llvm_backend.cpp | 4 +- src/llvm_backend_type.cpp | 25 +++---- src/name_canonicalization.cpp | 23 ++++-- 5 files changed, 146 insertions(+), 85 deletions(-) (limited to 'src/checker.cpp') diff --git a/src/checker.cpp b/src/checker.cpp index 6ceb31489..1c7126e9a 100644 --- a/src/checker.cpp +++ b/src/checker.cpp @@ -828,9 +828,15 @@ 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); rw_mutex_unlock(&d->type_info_deps_mutex); @@ -1361,9 +1367,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->type_info_set); + 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); @@ -1396,9 +1405,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->type_info_set); + 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); @@ -1632,41 +1643,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; @@ -2018,8 +2024,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 @@ -2238,6 +2248,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 } @@ -2295,11 +2306,10 @@ gb_internal void add_min_dep_type_info(Checker *c, Type *t) { return; } - if (type_set_update(&c->info.type_info_set, t)) { - // return; + if (type_set_update(&c->info.min_dep_type_info_set, t)) { + return; } - // Add nested types if (t->kind == Type_Named) { // NOTE(bill): Just in case @@ -2697,7 +2707,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) { \ @@ -6720,39 +6729,70 @@ 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("check for type hash collisions"); + TIME_SECTION("initilize type info array"); { - PtrSet found = {}; - ptr_set_init(&found, c->info.type_info_types.count); - defer (ptr_set_destroy(&found)); - for (auto const &tt : c->info.type_info_types) { - if (ptr_set_update(&found, cast(uintptr)tt.hash)) { - Type *other_type = nullptr; - for (auto const &other : c->info.type_info_types) { - if (&tt == &other) { - continue; - } - if (cast(uintptr)other.hash == cast(uintptr)tt.hash && - !are_types_identical(tt.type, other.type)) { - other_type = other.type; - break; - } - } - if (other_type != nullptr) { - String ts = type_to_canonical_string(temporary_allocator(), tt.type); - String os = type_to_canonical_string(temporary_allocator(), other_type); - if (ts != os) { - compiler_error("%s found type hash collision with %s (hash = %llu)\n" - "%s vs %s\n", - type_to_string(tt.type), type_to_string(other_type), cast(unsigned long long)tt.hash, - temp_canonical_string(tt.type), - temp_canonical_string(other_type) - ); + 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) { + for (auto const &entry : c->info.minimum_dependency_type_info_index_map) { + if (entry.key == cast(uintptr)tt.hash) { + auto const &other = c->info.type_info_types[entry.value]; + if (!are_types_identical_unique_tuples(tt.type, other.type)) { + 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("check for type hash collisions"); + // { + // PtrSet found = {}; + // ptr_set_init(&found, c->info.type_info_types.count); + // defer (ptr_set_destroy(&found)); + // for (auto const &tt : c->info.type_info_types) { + // if (ptr_set_update(&found, cast(uintptr)tt.hash)) { + // Type *other_type = nullptr; + // for (auto const &other : c->info.type_info_types) { + // if (&tt == &other) { + // continue; + // } + // if (cast(uintptr)other.hash == cast(uintptr)tt.hash && + // !are_types_identical(tt.type, other.type)) { + // other_type = other.type; + // break; + // } + // } + // if (other_type != nullptr) { + // String ts = type_to_canonical_string(temporary_allocator(), tt.type); + // String os = type_to_canonical_string(temporary_allocator(), other_type); + // if (ts != os) { + // compiler_error("%s found type hash collision with %s (hash = %llu)\n" + // "%s vs %s\n", + // type_to_string(tt.type), type_to_string(other_type), cast(unsigned long long)tt.hash, + // temp_canonical_string(tt.type), + // temp_canonical_string(other_type) + // ); + // } + // } + // } + // } + // } diff --git a/src/checker.hpp b/src/checker.hpp index 725c1ccf5..52676d4ee 100644 --- a/src/checker.hpp +++ b/src/checker.hpp @@ -222,7 +222,7 @@ struct DeclInfo { PtrSet deps; RwMutex type_info_deps_mutex; - PtrSet type_info_deps; + PtrSet type_info_deps; // TODO(bill): Use TypeSet BlockingMutex type_and_value_mutex; @@ -444,8 +444,10 @@ struct CheckerInfo { Scope * init_scope; Entity * entry_point; PtrSet minimum_dependency_set; - PtrMap minimum_dependency_type_info_set; - + BlockingMutex minimum_dependency_type_info_mutex; + PtrMap minimum_dependency_type_info_index_map; + TypeSet min_dep_type_info_set; + Array type_info_types; // sorted after filled Array testing_procedures; @@ -473,10 +475,10 @@ struct CheckerInfo { BlockingMutex gen_types_mutex; PtrMap gen_types; - BlockingMutex type_info_mutex; // NOT recursive - Array type_info_types; - PtrMap type_info_map; - TypeSet type_info_set; + // BlockingMutex type_info_mutex; // NOT recursive + // Array type_info_types; + // PtrMap type_info_map; + // TypeSet type_info_set; BlockingMutex foreign_mutex; // NOT recursive StringMap foreigns; @@ -595,6 +597,7 @@ gb_internal DeclInfo * decl_info_of_entity (Entity * e); gb_internal AstFile * ast_file_of_filename (CheckerInfo *i, String filename); // IMPORTANT: Only to use once checking is done gb_internal isize type_info_index (CheckerInfo *i, Type *type, bool error_on_failure); +gb_internal isize type_info_index (CheckerInfo *info, TypeInfoPair pair, bool error_on_failure); // Will return nullptr if not found gb_internal Entity *entity_of_node(Ast *expr); diff --git a/src/llvm_backend.cpp b/src/llvm_backend.cpp index 8cb480dd4..908117501 100644 --- a/src/llvm_backend.cpp +++ b/src/llvm_backend.cpp @@ -3154,7 +3154,9 @@ gb_internal bool lb_generate_code(lbGenerator *gen) { lbModule *m = default_module; { // Add type info data - isize max_type_info_count = info->minimum_dependency_type_info_set.count+1; + GB_ASSERT_MSG(info->minimum_dependency_type_info_index_map.count == info->type_info_types.count, "%tu vs %tu", info->minimum_dependency_type_info_index_map.count, info->type_info_types.count); + + isize max_type_info_count = info->minimum_dependency_type_info_index_map.count+1; Type *t = alloc_type_array(t_type_info_ptr, max_type_info_count); // IMPORTANT NOTE(bill): As LLVM does not have a union type, an array of unions cannot be initialized diff --git a/src/llvm_backend_type.cpp b/src/llvm_backend_type.cpp index 6f9f94fbd..8e0f15f35 100644 --- a/src/llvm_backend_type.cpp +++ b/src/llvm_backend_type.cpp @@ -1,16 +1,12 @@ -gb_internal isize lb_type_info_index(CheckerInfo *info, Type *type, bool err_on_not_found=true) { - auto *set = &info->minimum_dependency_type_info_set; - isize index = type_info_index(info, type, err_on_not_found); + +gb_internal isize lb_type_info_index(CheckerInfo *info, TypeInfoPair pair, bool err_on_not_found=true) { + isize index = type_info_index(info, pair, err_on_not_found); if (index >= 0) { - auto *found = map_get(set, index+1); - if (found) { - GB_ASSERT(*found >= 0); - return *found + 1; - } + return index+1; } if (err_on_not_found) { - gb_printf_err("NOT FOUND lb_type_info_index:\n\t%s\n\t@ index %td\n\tmax count: %u\nFound:\n", type_to_string(type), index, set->count); - for (auto const &entry : *set) { + gb_printf_err("NOT FOUND lb_type_info_index:\n\t%s\n\t@ index %td\n\tmax count: %u\nFound:\n", type_to_string(pair.type), index, info->minimum_dependency_type_info_index_map.count); + for (auto const &entry : info->minimum_dependency_type_info_index_map) { isize type_info_index = entry.key; gb_printf_err("\t%s\n", type_to_string(info->type_info_types[type_info_index].type)); } @@ -19,6 +15,10 @@ gb_internal isize lb_type_info_index(CheckerInfo *info, Type *type, bool err_on_ return -1; } +gb_internal isize lb_type_info_index(CheckerInfo *info, Type *type, bool err_on_not_found=true) { + return lb_type_info_index(info, {type, type_hash_canonical_type(type)}, err_on_not_found); +} + gb_internal u64 lb_typeid_kind(lbModule *m, Type *type, u64 id=0) { GB_ASSERT(!build_context.no_rtti); @@ -280,12 +280,13 @@ gb_internal void lb_setup_type_info_data_giant_array(lbModule *m, i64 global_typ LLVMTypeRef *modified_types = lb_setup_modified_types_for_type_info(m, global_type_info_data_entity_count); defer (gb_free(heap_allocator(), modified_types)); for_array(type_info_type_index, info->type_info_types) { - Type *t = info->type_info_types[type_info_type_index].type; + auto const &tt = info->type_info_types[type_info_type_index]; + Type *t = tt.type; if (t == nullptr || t == t_invalid) { continue; } - isize entry_index = lb_type_info_index(info, t, false); + isize entry_index = lb_type_info_index(info, tt, false); if (entry_index <= 0) { continue; } diff --git a/src/name_canonicalization.cpp b/src/name_canonicalization.cpp index b83441b19..de35312da 100644 --- a/src/name_canonicalization.cpp +++ b/src/name_canonicalization.cpp @@ -48,6 +48,15 @@ gb_internal gbString temp_canonical_string(Type *type); struct TypeInfoPair; struct TypeSet; +gb_internal GB_COMPARE_PROC(type_info_pair_cmp) { + TypeInfoPair *x = cast(TypeInfoPair *)a; + TypeInfoPair *y = cast(TypeInfoPair *)b; + if (x->hash == y->hash) { + return 0; + } + return x->hash < y->hash ? -1 : +1; +} + static constexpr u64 TYPE_SET_TOMBSTONE = ~(u64)(0ull); gb_internal void type_set_init (TypeSet *s, isize capacity); @@ -136,7 +145,7 @@ gb_internal isize type_set__find(TypeSet *s, TypeInfoPair pair) { 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)) { + if (are_types_identical_unique_tuples(key, pair.type)) { return hash_index; } else if (key == 0) { return -1; @@ -154,7 +163,7 @@ gb_internal isize type_set__find(TypeSet *s, Type *ptr) { 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)) { + if (are_types_identical_unique_tuples(key, ptr)) { return hash_index; } else if (key == 0) { return -1; @@ -224,7 +233,7 @@ gb_internal bool type_set_update(TypeSet *s, TypeInfoPair pair) { // returns tru 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)); + GB_ASSERT(!are_types_identical_unique_tuples(key->type, pair.type)); if (key->hash == TYPE_SET_TOMBSTONE || key->hash == 0) { *key = pair; s->count++; @@ -274,6 +283,9 @@ gb_internal gbString write_canonical_params(gbString w, Type *params) { if (i > 0) { w = gb_string_appendc(w, CANONICAL_PARAM_SEPARATOR); } + w = gb_string_append_length(w, v->token.string.text, v->token.string.len); + w = gb_string_appendc(w, CANONICAL_TYPE_SEPARATOR); + if (v->kind == Entity_Variable) { if (v->flags&EntityFlag_CVarArg) { w = gb_string_appendc(w, CANONICAL_PARAM_C_VARARG); @@ -466,14 +478,17 @@ write_base_name: switch (e->kind) { case Entity_TypeName: { + Type *params = nullptr; Entity *parent = type_get_polymorphic_parent(e->type, ¶ms); - if (parent) { + if (parent && (parent->token.string == e->token.string)) { 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); } + gb_unused(parent); + } // Handle parapoly stuff here? return w; -- cgit v1.2.3 From d69eb57cfa7a781e68b61307093e08790f95f640 Mon Sep 17 00:00:00 2001 From: gingerBill Date: Tue, 18 Feb 2025 13:18:51 +0000 Subject: Fix typos --- src/checker.cpp | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) (limited to 'src/checker.cpp') diff --git a/src/checker.cpp b/src/checker.cpp index 1c7126e9a..41adf0296 100644 --- a/src/checker.cpp +++ b/src/checker.cpp @@ -6729,7 +6729,7 @@ 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("initilize type info array"); + 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); -- cgit v1.2.3 From 721bcf2249fe2f2f6dd462833fede983205d6c5a Mon Sep 17 00:00:00 2001 From: gingerBill Date: Tue, 18 Feb 2025 13:24:08 +0000 Subject: Minor code clean up --- src/checker.cpp | 62 ++++++++++++++------------------------------------------- 1 file changed, 15 insertions(+), 47 deletions(-) (limited to 'src/checker.cpp') diff --git a/src/checker.cpp b/src/checker.cpp index 41adf0296..32e5ca405 100644 --- a/src/checker.cpp +++ b/src/checker.cpp @@ -6741,60 +6741,28 @@ gb_internal void check_parsed_files(Checker *c) { 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) { - for (auto const &entry : c->info.minimum_dependency_type_info_index_map) { - if (entry.key == cast(uintptr)tt.hash) { - auto const &other = c->info.type_info_types[entry.value]; - if (!are_types_identical_unique_tuples(tt.type, other.type)) { - 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); - } - } + 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("check for type hash collisions"); - // { - // PtrSet found = {}; - // ptr_set_init(&found, c->info.type_info_types.count); - // defer (ptr_set_destroy(&found)); - // for (auto const &tt : c->info.type_info_types) { - // if (ptr_set_update(&found, cast(uintptr)tt.hash)) { - // Type *other_type = nullptr; - // for (auto const &other : c->info.type_info_types) { - // if (&tt == &other) { - // continue; - // } - // if (cast(uintptr)other.hash == cast(uintptr)tt.hash && - // !are_types_identical(tt.type, other.type)) { - // other_type = other.type; - // break; - // } - // } - // if (other_type != nullptr) { - // String ts = type_to_canonical_string(temporary_allocator(), tt.type); - // String os = type_to_canonical_string(temporary_allocator(), other_type); - // if (ts != os) { - // compiler_error("%s found type hash collision with %s (hash = %llu)\n" - // "%s vs %s\n", - // type_to_string(tt.type), type_to_string(other_type), cast(unsigned long long)tt.hash, - // temp_canonical_string(tt.type), - // temp_canonical_string(other_type) - // ); - // } - // } - // } - // } - // } - - TIME_SECTION("sort init and fini procedures"); check_sort_init_and_fini_procedures(c); -- cgit v1.2.3 From 19b59461b04f4b6b63fa24d70e9c9376b3dd3249 Mon Sep 17 00:00:00 2001 From: gingerBill Date: Tue, 18 Feb 2025 13:31:34 +0000 Subject: Use `TypeSet` for DeclInfo deps --- src/check_decl.cpp | 4 +-- src/checker.cpp | 10 +++--- src/checker.hpp | 80 ++++++++++++++++++++++++++++++------------- src/name_canonicalization.cpp | 37 ++++---------------- 4 files changed, 71 insertions(+), 60 deletions(-) (limited to 'src/checker.cpp') diff --git a/src/check_decl.cpp b/src/check_decl.cpp index d6f8e6fa7..5607ea725 100644 --- a/src/check_decl.cpp +++ b/src/check_decl.cpp @@ -1742,8 +1742,8 @@ gb_internal void add_deps_from_child_to_parent(DeclInfo *decl) { rw_mutex_shared_lock(&decl->type_info_deps_mutex); rw_mutex_lock(&decl->parent->type_info_deps_mutex); - for (Type *t : decl->type_info_deps) { - ptr_set_add(&decl->parent->type_info_deps, t); + for (auto const &tt : decl->type_info_deps) { + type_set_add(&decl->parent->type_info_deps, tt); } rw_mutex_unlock(&decl->parent->type_info_deps_mutex); diff --git a/src/checker.cpp b/src/checker.cpp index 32e5ca405..38da38b0c 100644 --- a/src/checker.cpp +++ b/src/checker.cpp @@ -173,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; @@ -838,7 +838,7 @@ gb_internal void add_type_info_dependency(CheckerInfo *info, DeclInfo *d, Type * } } 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); } @@ -2506,8 +2506,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) { @@ -6742,7 +6742,7 @@ gb_internal void check_parsed_files(Checker *c) { 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 + continue; } for (auto const &entry : c->info.minimum_dependency_type_info_index_map) { if (entry.key != cast(uintptr)tt.hash) { diff --git a/src/checker.hpp b/src/checker.hpp index 52676d4ee..b8878d745 100644 --- a/src/checker.hpp +++ b/src/checker.hpp @@ -167,6 +167,61 @@ typedef DECL_ATTRIBUTE_PROC(DeclAttributeProc); gb_internal void check_decl_attributes(CheckerContext *c, Array const &attributes, DeclAttributeProc *proc, AttributeContext *ac); +struct TypeInfoPair { + Type *type; + u64 hash; // see: type_hash_canonical_type +}; + +struct TypeSet { + TypeInfoPair *keys; + usize count; + usize capacity; +}; + +static constexpr u64 TYPE_SET_TOMBSTONE = ~(u64)(0ull); + +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 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 Type *type_set_add (TypeSet *s, TypeInfoPair pair); +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 TypeSetIterator begin(TypeSet &set) noexcept; +gb_internal TypeSetIterator end(TypeSet &set) noexcept; + enum ProcCheckedState : u8 { ProcCheckedState_Unchecked, @@ -221,8 +276,8 @@ struct DeclInfo { RwMutex deps_mutex; PtrSet deps; - RwMutex type_info_deps_mutex; - PtrSet type_info_deps; // TODO(bill): Use TypeSet + RwMutex type_info_deps_mutex; + TypeSet type_info_deps; BlockingMutex type_and_value_mutex; @@ -409,27 +464,6 @@ struct Defineable { String pos_str; }; -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; diff --git a/src/name_canonicalization.cpp b/src/name_canonicalization.cpp index de35312da..ef0e23f38 100644 --- a/src/name_canonicalization.cpp +++ b/src/name_canonicalization.cpp @@ -57,11 +57,10 @@ gb_internal GB_COMPARE_PROC(type_info_pair_cmp) { return x->hash < y->hash ? -1 : +1; } -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 Type *type_set_add (TypeSet *s, TypeInfoPair pair); 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); @@ -73,34 +72,6 @@ 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) { @@ -257,6 +228,12 @@ gb_internal Type *type_set_add(TypeSet *s, Type *ptr) { return ptr; } +gb_internal Type *type_set_add(TypeSet *s, TypeInfoPair pair) { + type_set_update(s, pair); + return pair.type; +} + + gb_internal void type_set_remove(TypeSet *s, Type *ptr) { isize index = type_set__find(s, ptr); -- cgit v1.2.3 From 0bac34eec891080e2d0b9b4fc9e7b429a42064a3 Mon Sep 17 00:00:00 2001 From: gingerBill Date: Wed, 19 Feb 2025 10:59:05 +0000 Subject: Number fields within procedures with a depth-first numbering system --- src/checker.cpp | 4 ++++ src/checker.hpp | 4 ++++ src/name_canonicalization.cpp | 5 ++++- 3 files changed, 12 insertions(+), 1 deletion(-) (limited to 'src/checker.cpp') diff --git a/src/checker.cpp b/src/checker.cpp index 38da38b0c..f1f1b2556 100644 --- a/src/checker.cpp +++ b/src/checker.cpp @@ -358,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; } diff --git a/src/checker.hpp b/src/checker.hpp index 8850d5c3f..c89a1bc9c 100644 --- a/src/checker.hpp +++ b/src/checker.hpp @@ -229,6 +229,8 @@ struct DeclInfo { Array labels; + i32 scope_index; + Array variadic_reuses; i64 variadic_reuse_max_bytes; i64 variadic_reuse_max_align; @@ -273,6 +275,8 @@ struct Scope { std::atomic next; std::atomic head_child; + i32 index; // within a procedure + RwMutex mutex; StringMap elements; PtrSet imported; diff --git a/src/name_canonicalization.cpp b/src/name_canonicalization.cpp index fd4e4b50f..b24bf9126 100644 --- a/src/name_canonicalization.cpp +++ b/src/name_canonicalization.cpp @@ -464,7 +464,10 @@ gb_internal void write_canonical_entity_name(TypeWriter *w, Entity *e) { if (s->decl_info != nullptr && s->decl_info->entity) { Entity *parent = s->decl_info->entity; write_canonical_parent_prefix(w, parent); - type_writer_append_fmt(w, CANONICAL_TYPE_SEPARATOR "[%d]", e->token.pos.offset); + if (e->scope->index > 0) { + type_writer_append_fmt(w, CANONICAL_TYPE_SEPARATOR "[%d]", e->scope->index); + } + // type_writer_append_fmt(w, CANONICAL_TYPE_SEPARATOR "[%d]", e->token.pos.offset); goto write_base_name; } else if ((s->flags & ScopeFlag_File) && s->file != nullptr) { -- cgit v1.2.3