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 };