hash.ha (4223B)
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, NULL, OPAQUE, RUNE, 12 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::NULL => 39 return storage::NULL; 40 case builtin::OPAQUE => 41 return storage::OPAQUE; 42 case builtin::RUNE => 43 return storage::RUNE; 44 case builtin::SIZE => 45 return storage::SIZE; 46 case builtin::STR => 47 return storage::STRING; 48 case builtin::U16 => 49 return storage::U16; 50 case builtin::U32 => 51 return storage::U32; 52 case builtin::U64 => 53 return storage::U64; 54 case builtin::U8 => 55 return storage::U8; 56 case builtin::UINT => 57 return storage::UINT; 58 case builtin::UINTPTR => 59 return storage::UINTPTR; 60 case builtin::VALIST => 61 return storage::VALIST; 62 case builtin::VOID => 63 return storage::VOID; 64 case builtin::FCONST, builtin::ICONST, builtin::RCONST => 65 abort(); // unreachable 66 }; 67 }; 68 69 fn type_storage(t: *_type) u8 = { 70 match (t.repr) { 71 case alias => 72 return storage::ALIAS; 73 case array => 74 return storage::ARRAY; 75 case let b: builtin => 76 return builtin_storage(b); 77 case _enum => 78 return storage::ENUM; 79 case func => 80 return storage::FUNCTION; 81 case pointer => 82 return storage::POINTER; 83 case slice => 84 return storage::SLICE; 85 case let st: _struct => 86 if (st.kind == struct_union::STRUCT) { 87 return storage::STRUCT; 88 } else { 89 return storage::UNION; 90 }; 91 case tuple => 92 return storage::TUPLE; 93 case tagged => 94 return storage::TAGGED; 95 }; 96 }; 97 98 fn write8(h: *hash::hash, u: u8) void = { 99 let buf = &u: *[*]u8; 100 hash::write(h, buf[..1]); 101 }; 102 103 fn write32(h: *hash::hash, u: u32) void = { 104 static let buf: [size(u32)]u8 = [0...]; 105 endian::leputu32(buf, u); 106 hash::write(h, buf); 107 }; 108 109 fn write64(h: *hash::hash, u: u64) void = { 110 static let buf: [size(u64)]u8 = [0...]; 111 endian::leputu64(buf, u); 112 hash::write(h, buf); 113 }; 114 115 // Returns the hash of a type. These hashes are deterministic and universally 116 // unique: different computers will generate the same hash for the same type. 117 export fn hash(t: *_type) u32 = { 118 // Note that this function should produce the same hashes as harec; see 119 // bootstrap harec:src/types.c:type_hash 120 let id = fnv::fnv32a(); 121 write8(&id, type_storage(t)); 122 write8(&id, t.flags); 123 124 match (t.repr) { 125 case let a: alias => 126 for (let i = len(a.id); i > 0; i -= 1) { 127 hash::write(&id, strings::toutf8(a.id[i - 1])); 128 write8(&id, 0); 129 }; 130 case let a: array => 131 write32(&id, hash(a.member)); 132 writesize(&id, a.length); 133 case builtin => void; 134 case let e: _enum => 135 write8(&id, builtin_storage(e.storage)); 136 for (let i = 0z; i < len(e.values); i += 1) { 137 hash::write(&id, strings::toutf8(e.values[i].0)); 138 write64(&id, e.values[i].1); 139 }; 140 case let f: func => 141 write32(&id, hash(f.result)); 142 write8(&id, f.variadism: u8); 143 for (let i = 0z; i < len(f.params); i += 1) { 144 write32(&id, hash(f.params[i])); 145 }; 146 case let p: pointer => 147 write8(&id, p.flags); 148 write32(&id, hash(p.referent)); 149 case let s: slice => 150 write32(&id, hash(s)); 151 case let st: _struct => 152 for (let i = 0z; i < len(st.fields); i += 1) { 153 const field = st.fields[i]; 154 hash::write(&id, strings::toutf8(field.name)); 155 write32(&id, hash(field._type)); 156 writesize(&id, field.offs); 157 }; 158 case let tu: tuple => 159 for (let i = 0z; i < len(tu); i += 1) { 160 write32(&id, hash(tu[i]._type)); 161 }; 162 case let ta: tagged => 163 for (let i = 0z; i < len(ta); i += 1) { 164 write32(&id, hash(ta[i])); 165 }; 166 }; 167 168 return fnv::sum32(&id); 169 };