hare

[hare] The Hare programming language
git clone https://git.torresjrjr.com/hare.git
Log | Files | Refs | README | LICENSE

hash.ha (4119B)


      1 // License: MPL-2.0
      2 // (c) 2021 Drew DeVault <sir@cmpwn.com>
      3 // (c) 2021 Eyal Sawady <ecs@d2evs.net>
      4 use endian;
      5 use hash::fnv;
      6 use hash;
      7 use strings;
      8 use fmt;
      9 
     10 // Keep ordered with respect to bootstrap harec:include/types.h
     11 type storage = enum u8 {
     12 	BOOL, CHAR, F32, F64, I16, I32, I64, I8, INT, NULL, RUNE, SIZE, STRING,
     13 	U16, U32, U64, U8, UINT, UINTPTR, VOID, ALIAS, ARRAY, ENUM, FUNCTION,
     14 	POINTER, SLICE, STRUCT, TAGGED, TUPLE, UNION,
     15 };
     16 
     17 fn builtin_storage(b: builtin) u8 = {
     18 	switch (b) {
     19 	case builtin::BOOL =>
     20 		return storage::BOOL;
     21 	case builtin::CHAR =>
     22 		return storage::CHAR;
     23 	case builtin::F32 =>
     24 		return storage::F32;
     25 	case builtin::F64 =>
     26 		return storage::F64;
     27 	case builtin::I16 =>
     28 		return storage::I16;
     29 	case builtin::I32 =>
     30 		return storage::I32;
     31 	case builtin::I64 =>
     32 		return storage::I64;
     33 	case builtin::I8 =>
     34 		return storage::I8;
     35 	case builtin::INT =>
     36 		return storage::INT;
     37 	case builtin::NULL =>
     38 		return storage::NULL;
     39 	case builtin::RUNE =>
     40 		return storage::RUNE;
     41 	case builtin::SIZE =>
     42 		return storage::SIZE;
     43 	case builtin::STR =>
     44 		return storage::STRING;
     45 	case builtin::U16 =>
     46 		return storage::U16;
     47 	case builtin::U32 =>
     48 		return storage::U32;
     49 	case builtin::U64 =>
     50 		return storage::U64;
     51 	case builtin::U8 =>
     52 		return storage::U8;
     53 	case builtin::UINT =>
     54 		return storage::UINT;
     55 	case builtin::UINTPTR =>
     56 		return storage::UINTPTR;
     57 	case builtin::VOID =>
     58 		return storage::VOID;
     59 	};
     60 };
     61 
     62 fn type_storage(t: *_type) u8 = {
     63 	match (t.repr) {
     64 	case alias =>
     65 		return storage::ALIAS;
     66 	case array =>
     67 		return storage::ARRAY;
     68 	case let b: builtin =>
     69 		return builtin_storage(b);
     70 	case _enum =>
     71 		return storage::ENUM;
     72 	case func =>
     73 		return storage::FUNCTION;
     74 	case pointer =>
     75 		return storage::POINTER;
     76 	case slice =>
     77 		return storage::SLICE;
     78 	case let st: _struct =>
     79 		if (st.kind == struct_union::STRUCT) {
     80 			return storage::STRUCT;
     81 		} else {
     82 			return storage::UNION;
     83 		};
     84 	case tuple =>
     85 		return storage::TUPLE;
     86 	case tagged =>
     87 		return storage::TAGGED;
     88 	};
     89 };
     90 
     91 fn write8(h: *hash::hash, u: u8) void = {
     92 	let buf = &u: *[*]u8;
     93 	hash::write(h, buf[..1]);
     94 };
     95 
     96 fn write32(h: *hash::hash, u: u32) void = {
     97 	static let buf: [size(u32)]u8 = [0...];
     98 	endian::leputu32(buf, u);
     99 	hash::write(h, buf);
    100 };
    101 
    102 fn write64(h: *hash::hash, u: u64) void = {
    103 	static let buf: [size(u64)]u8 = [0...];
    104 	endian::leputu64(buf, u);
    105 	hash::write(h, buf);
    106 };
    107 
    108 // Returns the hash of a type. These hashes are deterministic and universally
    109 // unique: different computers will generate the same hash for the same type.
    110 export fn hash(t: *_type) u32 = {
    111 	// Note that this function should produce the same hashes as harec; see
    112 	// bootstrap harec:src/types.c:type_hash
    113 	let id = fnv::fnv32a();
    114 	write8(&id, type_storage(t));
    115 	write8(&id, t.flags);
    116 
    117 	match (t.repr) {
    118 	case let a: alias =>
    119 		for (let i = len(a.id); i > 0; i -= 1) {
    120 			hash::write(&id, strings::toutf8(a.id[i - 1]));
    121 			write8(&id, 0);
    122 		};
    123 	case let a: array =>
    124 		write32(&id, hash(a.member));
    125 		static assert(size(u64) == size(size)); // TODO
    126 		write64(&id, a.length);
    127 	case builtin => void;
    128 	case let e: _enum =>
    129 		write8(&id, builtin_storage(e.storage));
    130 		for (let i = 0z; i < len(e.values); i += 1) {
    131 			hash::write(&id, strings::toutf8(e.values[i].0));
    132 			write64(&id, e.values[i].1);
    133 		};
    134 	case let f: func =>
    135 		write32(&id, hash(f.result));
    136 		write8(&id, f.variadism: u8);
    137 		write8(&id, f.flags: u8);
    138 		for (let i = 0z; i < len(f.params); i += 1) {
    139 			write32(&id, hash(f.params[i]));
    140 		};
    141 	case let p: pointer =>
    142 		write8(&id, p.flags);
    143 		write32(&id, hash(p.referent));
    144 	case let s: slice =>
    145 		write32(&id, hash(s));
    146 	case let st: _struct =>
    147 		for (let i = 0z; i < len(st.fields); i += 1) {
    148 			const field = st.fields[i];
    149 			hash::write(&id, strings::toutf8(field.name));
    150 			write32(&id, hash(field._type));
    151 			static assert(size(u64) == size(size)); // TODO
    152 			write64(&id, field.offs);
    153 		};
    154 	case let tu: tuple =>
    155 		for (let i = 0z; i < len(tu); i += 1) {
    156 			write32(&id, hash(tu[i]._type));
    157 		};
    158 	case let ta: tagged =>
    159 		for (let i = 0z; i < len(ta); i += 1) {
    160 			write32(&id, hash(ta[i]));
    161 		};
    162 	};
    163 
    164 	return fnv::sum32(&id);
    165 };