Merge branch 'odin-lang:master' into core-image-tga

1 files changed, 220 insertions, 16 deletions

diff --git a/src/name_canonicalization.cpp b/src/name_canonicalization.cpp
index 6a4538e26..f1dccb182 100644
--- a/src/name_canonicalization.cpp
+++ b/src/name_canonicalization.cpp
@@ -57,10 +57,13 @@ gb_internal isize type_set__find(TypeSet *s, TypeInfoPair pair) {
 		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_unique_tuples(key, pair.type)) {
+			auto *e = &s->keys[hash_index];
+			u64 hash  = e->hash;
+			Type *key = e->type;
+			if (hash == pair.hash &&
+			    are_types_identical_unique_tuples(key, pair.type)) {
 				return hash_index;
-			} else if (key == 0) {
+			} else if (key == nullptr) {
 				return -1;
 			}
 			hash_index = (hash_index+1)&mask;
@@ -164,6 +167,48 @@ gb_internal bool type_set_update(TypeSet *s, Type *ptr) { // returns true if it
 	return type_set_update(s, pair);
 }
 
+gb_internal bool type_set_update_with_mutex(TypeSet *s, TypeInfoPair pair, RWSpinLock *m) { // returns true if it previously existsed
+	rwlock_acquire_upgrade(m);
+	if (type_set_exists(s, pair)) {
+		rwlock_release_upgrade(m);
+		return true;
+	}
+
+	rwlock_release_upgrade_and_acquire_write(m);
+	defer (rwlock_release_write(m));
+
+	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_unique_tuples(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_with_mutex(TypeSet *s, Type *ptr, RWSpinLock *m) { // returns true if it previously existsed
+	TypeInfoPair pair = {ptr, type_hash_canonical_type(ptr)};
+	return type_set_update_with_mutex(s, pair, m);
+}
+
 
 gb_internal Type *type_set_add(TypeSet *s, Type *ptr) {
 	type_set_update(s, ptr);
@@ -197,9 +242,146 @@ gb_internal gb_inline void type_set_clear(TypeSet *s) {
 typedef TYPE_WRITER_PROC(TypeWriterProc);
 
 
+enum { SIP_BLOCK_SIZE = 8 };
+
+struct SipHashContext {
+	u64   v0, v1, v2, v3;      // State values
+	u64   k0, k1;              // Split key
+	isize c_rounds;            // Number of message rounds
+	isize d_rounds;            // Number of finalization rounds
+	u8    buf[SIP_BLOCK_SIZE]; // Provided data
+	isize last_block;          // offset from last block
+	isize total_length;
+	bool  is_initialized;
+};
+
+struct TypeidHashContext {
+	SipHashContext sip;
+};
+
+
+void typeid_hash_context_init(TypeidHashContext *hash_ctx) {
+	SipHashContext *sip = &hash_ctx->sip;
+	sip->c_rounds = 2;
+	sip->d_rounds = 4;
+
+	// some random numbers to act as the seed
+	sip->k0 = 0xa6592ea25e04ac3cull;
+	sip->k1 = 0xba3cba04ed28a9aeull;
+
+	//
+	sip->v0 = 0x736f6d6570736575 ^ sip->k0;
+	sip->v1 = 0x646f72616e646f6d ^ sip->k1;
+	sip->v2 = 0x6c7967656e657261 ^ sip->k0;
+	sip->v3 = 0x7465646279746573 ^ sip->k1;
+
+	sip->last_block = 0;
+	sip->total_length = 0;
+
+	sip->is_initialized = true;
+}
+
+u64 rotate_left64(u64 x, u64 k) {
+	static u64 const n = 64;
+	u64 s = k & (n-1);
+	return (x<<s) | (x>>(n-2));
+}
+
+void sip_compress(SipHashContext *sip) {
+	sip->v0 += sip->v1;
+	sip->v1 =  rotate_left64(sip->v1, 13);
+	sip->v1 ^= sip->v0;
+	sip->v0 =  rotate_left64(sip->v0, 32);
+	sip->v2 += sip->v3;
+	sip->v3 =  rotate_left64(sip->v3, 16);
+	sip->v3 ^= sip->v2;
+	sip->v0 += sip->v3;
+	sip->v3 =  rotate_left64(sip->v3, 21);
+	sip->v3 ^= sip->v0;
+	sip->v2 += sip->v1;
+	sip->v1 =  rotate_left64(sip->v1, 17);
+	sip->v1 ^= sip->v2;
+	sip->v2 =  rotate_left64(sip->v2, 32);
+}
+
+void sip_block(SipHashContext *sip, void const *ptr, isize len) {
+	u8 const *data = cast(u8 const *)ptr;
+	while (len >= SIP_BLOCK_SIZE) {
+		u64 m = 0;
+		gb_memcopy(&m, data, 8);
+
+		sip->v3 ^= m;
+
+		for (isize i = 0; i < sip->c_rounds; i++) {
+			sip_compress(sip);
+		}
+
+		sip->v0 ^= m;
+
+		data += SIP_BLOCK_SIZE;
+		len -= SIP_BLOCK_SIZE;
+	}
+}
+
+void typeid_hash_context_update(TypeidHashContext *ctx, void const *ptr, isize len) {
+	GB_ASSERT(ctx->sip.is_initialized);
+	SipHashContext *sip = &ctx->sip;
+
+	u8 const *data = cast(u8 const *)ptr;
+	sip->total_length += len;
+	if (sip->last_block > 0) {
+		isize n = gb_min(SIP_BLOCK_SIZE - sip->last_block, len);
+		gb_memcopy(sip->buf + sip->last_block, data, n);
+		sip->last_block += n;
+		if (sip->last_block == SIP_BLOCK_SIZE) {
+			sip_block(sip, sip->buf, SIP_BLOCK_SIZE);
+			sip->last_block = 0;
+		}
+		data += n;
+		len -= n;
+	}
+
+	if (len >= SIP_BLOCK_SIZE) {
+		isize n = len & ~(SIP_BLOCK_SIZE-1);
+		sip_block(sip, data, n);
+		data += n;
+		len -= n;
+	}
+	if (len > 0) {
+		isize n = gb_min(SIP_BLOCK_SIZE, len);
+		gb_memcopy(sip->buf, data, n);
+		sip->last_block = n;
+	}
+}
+
+u64 typeid_hash_context_fini(TypeidHashContext *ctx) {
+	GB_ASSERT(ctx->sip.is_initialized);
+	SipHashContext *sip = &ctx->sip;
+
+	u8 tmp[SIP_BLOCK_SIZE] = {};
+	gb_memcopy(tmp, sip->buf, gb_min(sip->last_block, SIP_BLOCK_SIZE));
+	tmp[7] = u8(sip->total_length & 0xff);
+	sip_block(sip, tmp, SIP_BLOCK_SIZE);
+
+	sip->v2 ^= 0xff;
+
+	for (isize i = 0; i < sip->d_rounds; i++) {
+		sip_compress(sip);
+	}
+
+	u64 res = sip->v0 ^ sip->v1 ^ sip->v2 ^ sip->v3;
+
+	*sip = {};
+
+	return res ? res : 1;
+}
+
+
+
 struct TypeWriter {
-	TypeWriterProc *proc;
-	void *user_data;
+	TypeWriterProc *  proc;
+	void *            user_data;
+	TypeidHashContext hash_ctx;
 };
 
 bool type_writer_append(TypeWriter *w, void const *ptr, isize len) {
@@ -244,13 +426,14 @@ void type_writer_destroy_string(TypeWriter *w) {
 
 
 TYPE_WRITER_PROC(type_writer_hasher_writer_proc) {
-	u64 *seed = cast(u64 *)w->user_data;
-	*seed = fnv64a(ptr, len, *seed);
+	TypeidHashContext *ctx = cast(TypeidHashContext *)w->user_data;
+	typeid_hash_context_update(ctx, ptr, len);
 	return true;
 }
 
-void type_writer_make_hasher(TypeWriter *w, u64 *hash) {
-	w->user_data = hash;
+void type_writer_make_hasher(TypeWriter *w, TypeidHashContext *ctx) {
+	typeid_hash_context_init(ctx);
+	w->user_data = ctx;
 	w->proc = type_writer_hasher_writer_proc;
 }
 
@@ -328,12 +511,19 @@ gb_internal u64 type_hash_canonical_type(Type *type) {
 	if (type == nullptr) {
 		return 0;
 	}
-	u64 hash = fnv64a(nullptr, 0);
+	u64 prev_hash = type->canonical_hash.load(std::memory_order_relaxed);
+	if (prev_hash != 0) {
+		return prev_hash;
+	}
+
 	TypeWriter w = {};
-	type_writer_make_hasher(&w, &hash);
+	type_writer_make_hasher(&w, &w.hash_ctx);
 	write_type_to_canonical_string(&w, type);
+	u64 hash = typeid_hash_context_fini(&w.hash_ctx);
+
+	type->canonical_hash.store(hash, std::memory_order_relaxed);
 
-	return hash ? hash : 1;
+	return hash;
 }
 
 gb_internal String type_to_canonical_string(gbAllocator allocator, Type *type) {
@@ -364,7 +554,7 @@ gb_internal gbString string_canonical_entity_name(gbAllocator allocator, Entity
 
 gb_internal void write_canonical_parent_prefix(TypeWriter *w, Entity *e) {
 	GB_ASSERT(e != nullptr);
-	if (e->kind == Entity_Procedure || e->kind == Entity_TypeName) {
+	if (e->kind == Entity_Procedure || e->kind == Entity_TypeName || e->kind == Entity_Variable) {
 		if (e->kind == Entity_Procedure && (e->Procedure.is_export || e->Procedure.is_foreign)) {
 			// no prefix
 			return;
@@ -474,6 +664,11 @@ gb_internal void write_canonical_entity_name(TypeWriter *w, Entity *e) {
 		} else if (s->flags & (ScopeFlag_Builtin)) {
 			goto write_base_name;
 		}
+
+		if (e->kind == Entity_TypeName) {
+			goto write_base_name;
+		}
+
 		gb_printf_err("%s WEIRD ENTITY TYPE %s %u %p\n", token_pos_to_string(e->token.pos), type_to_string(e->type), s->flags, s->decl_info);
 
 		auto const print_scope_flags = [](Scope *s) {
@@ -490,7 +685,7 @@ gb_internal void write_canonical_entity_name(TypeWriter *w, Entity *e) {
 		};
 
 		print_scope_flags(s);
-		GB_PANIC("weird entity %.*s", LIT(e->token.string));
+		GB_PANIC("weird entity %.*s (%.*s)", LIT(e->token.string), LIT(entity_strings[e->kind]));
 	}
 	if (e->pkg != nullptr) {
 		type_writer_append(w, e->pkg->name.text, e->pkg->name.len);
@@ -691,8 +886,9 @@ gb_internal void write_type_to_canonical_string(TypeWriter *w, Type *type) {
 			write_canonical_params(w, type->Struct.polymorphic_params);
 		}
 
-		if (type->Struct.is_packed)    type_writer_appendc(w, "#packed");
-		if (type->Struct.is_raw_union) type_writer_appendc(w, "#raw_union");
+		if (type->Struct.is_packed)      type_writer_appendc(w, "#packed");
+		if (type->Struct.is_raw_union)   type_writer_appendc(w, "#raw_union");
+		if (type->Struct.is_all_or_none) type_writer_appendc(w, "#all_or_none");
 		if (type->Struct.custom_min_field_align != 0) type_writer_append_fmt(w, "#min_field_align(%lld)", cast(long long)type->Struct.custom_min_field_align);
 		if (type->Struct.custom_max_field_align != 0) type_writer_append_fmt(w, "#max_field_align(%lld)", cast(long long)type->Struct.custom_max_field_align);
 		if (type->Struct.custom_align != 0)           type_writer_append_fmt(w, "#align(%lld)",           cast(long long)type->Struct.custom_align);
@@ -703,6 +899,14 @@ gb_internal void write_type_to_canonical_string(TypeWriter *w, Type *type) {
 			if (i > 0) {
 				type_writer_appendc(w, CANONICAL_FIELD_SEPARATOR);
 			}
+
+			if (f->flags & EntityFlags_IsSubtype) {
+				type_writer_appendc(w, "#subtype ");
+			}
+
+			if (f->flags & EntityFlag_Using) {
+				type_writer_appendc(w, "using ");
+			}
 			type_writer_append(w, f->token.string.text, f->token.string.len);
 			type_writer_appendc(w, CANONICAL_TYPE_SEPARATOR);
 			write_type_to_canonical_string(w, f->type);