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