1 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
2 // -*- mode: C++ -*-
3 //
4 // Copyright 2022-2024 Google LLC
5 //
6 // Licensed under the Apache License v2.0 with LLVM Exceptions (the
7 // "License"); you may not use this file except in compliance with the
8 // License. You may obtain a copy of the License at
9 //
10 // https://llvm.org/LICENSE.txt
11 //
12 // Unless required by applicable law or agreed to in writing, software
13 // distributed under the License is distributed on an "AS IS" BASIS,
14 // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
15 // See the License for the specific language governing permissions and
16 // limitations under the License.
17 //
18 // Author: Siddharth Nayyar
19
20 #include "stable_hash.h"
21
22 #include <algorithm>
23 #include <cstdint>
24 #include <sstream>
25 #include <string>
26 #include <utility>
27 #include <vector>
28
29 #include "graph.h"
30 #include "hashing.h"
31
32 namespace stg {
33
34 namespace {
35
36 // This combines 2 hash values while decaying (by shifting right) the second
37 // value. This prevents the most significant bits of the first hash from being
38 // affected by the decayed hash. Hash combination is done using a simple XOR
39 // operation to preserve the separation of higher and lower bits. Note that XOR
40 // is not a very effective method of mixing hash values if the values are
41 // generated with a weak hashing algorithm.
42 template <uint8_t decay>
DecayHashCombine(HashValue a,HashValue b)43 constexpr HashValue DecayHashCombine(HashValue a, HashValue b) {
44 static_assert(decay > 0 && decay < 32, "decay must lie inside (0, 32)");
45 return HashValue(a.value ^ (b.value >> decay));
46 }
47
48 // Decaying hashes are combined in reverse since the each successive hashable
49 // should be decayed 1 more time than the previous hashable and the last
50 // hashable should receieve the most decay.
51 template <uint8_t decay, typename Type, typename Hash>
DecayHashCombineInReverse(const std::vector<Type> & hashables,Hash & hash)52 HashValue DecayHashCombineInReverse(const std::vector<Type>& hashables,
53 Hash& hash) {
54 HashValue result(0);
55 for (auto it = hashables.crbegin(); it != hashables.crend(); ++it) {
56 result = DecayHashCombine<decay>(hash(*it), result);
57 }
58 return result;
59 }
60
61 } // namespace
62
operator ()(Id id)63 HashValue StableHash::operator()(Id id) {
64 auto [it, inserted] = cache_.emplace(id, 0);
65 if (inserted) {
66 it->second = graph_.Apply<HashValue>(*this, id);
67 }
68 return it->second;
69 }
70
operator ()(const Special & x)71 HashValue StableHash::operator()(const Special& x) {
72 switch (x.kind) {
73 case Special::Kind::VOID:
74 return hash_("void");
75 case Special::Kind::VARIADIC:
76 return hash_("variadic");
77 case Special::Kind::NULLPTR:
78 return hash_("nullptr");
79 }
80 }
81
operator ()(const PointerReference & x)82 HashValue StableHash::operator()(const PointerReference& x) {
83 return DecayHashCombine<2>(hash_('r', static_cast<uint32_t>(x.kind)),
84 (*this)(x.pointee_type_id));
85 }
86
operator ()(const PointerToMember & x)87 HashValue StableHash::operator()(const PointerToMember& x) {
88 return DecayHashCombine<16>(hash_('n', (*this)(x.containing_type_id)),
89 (*this)(x.pointee_type_id));
90 }
91
operator ()(const Typedef & x)92 HashValue StableHash::operator()(const Typedef& x) {
93 return hash_('t', x.name);
94 }
95
operator ()(const Qualified & x)96 HashValue StableHash::operator()(const Qualified& x) {
97 return DecayHashCombine<2>(hash_('q', static_cast<uint32_t>(x.qualifier)),
98 (*this)(x.qualified_type_id));
99 }
100
operator ()(const Primitive & x)101 HashValue StableHash::operator()(const Primitive& x) {
102 return hash_('p', x.name);
103 }
104
operator ()(const Array & x)105 HashValue StableHash::operator()(const Array& x) {
106 return DecayHashCombine<2>(hash_('a', x.number_of_elements),
107 (*this)(x.element_type_id));
108 }
109
operator ()(const BaseClass & x)110 HashValue StableHash::operator()(const BaseClass& x) {
111 return DecayHashCombine<2>(hash_('b', static_cast<uint32_t>(x.inheritance)),
112 (*this)(x.type_id));
113 }
114
operator ()(const Method & x)115 HashValue StableHash::operator()(const Method& x) {
116 return hash_(x.mangled_name);
117 }
118
operator ()(const Member & x)119 HashValue StableHash::operator()(const Member& x) {
120 HashValue hash = hash_('m', x.name, x.bitsize);
121 hash = DecayHashCombine<20>(hash, hash_(x.offset));
122 if (x.name.empty()) {
123 return DecayHashCombine<2>(hash, (*this)(x.type_id));
124 } else {
125 return DecayHashCombine<8>(hash, (*this)(x.type_id));
126 }
127 }
128
operator ()(const VariantMember & x)129 HashValue StableHash::operator()(const VariantMember& x) {
130 HashValue hash = hash_('v', x.name);
131 hash = DecayHashCombine<8>(hash, (*this)(x.type_id));
132 return x.discriminant_value
133 ? DecayHashCombine<20>(hash, hash_(*x.discriminant_value))
134 : hash;
135 }
136
operator ()(const StructUnion & x)137 HashValue StableHash::operator()(const StructUnion& x) {
138 HashValue hash = hash_('S', static_cast<uint32_t>(x.kind), x.name,
139 static_cast<bool>(x.definition));
140 if (!x.name.empty() || !x.definition) {
141 return hash;
142 }
143
144 auto h1 = DecayHashCombineInReverse<8>(x.definition->methods, *this);
145 auto h2 = DecayHashCombineInReverse<8>(x.definition->members, *this);
146 return DecayHashCombine<2>(hash, HashValue(h1.value ^ h2.value));
147 }
148
operator ()(const Enumeration & x)149 HashValue StableHash::operator()(const Enumeration& x) {
150 HashValue hash = hash_('e', x.name, static_cast<bool>(x.definition));
151 if (!x.name.empty() || !x.definition) {
152 return hash;
153 }
154
155 auto hash_enum = [this](const std::pair<std::string, int64_t>& e) {
156 return hash_(e.first, e.second);
157 };
158 return DecayHashCombine<2>(
159 hash, DecayHashCombineInReverse<8>(x.definition->enumerators, hash_enum));
160 }
161
operator ()(const Variant & x)162 HashValue StableHash::operator()(const Variant& x) {
163 HashValue hash = hash_('V', x.name, x.bytesize);
164 if (x.discriminant.has_value()) {
165 hash = DecayHashCombine<12>(hash, (*this)(x.discriminant.value()));
166 }
167 return DecayHashCombine<2>(hash,
168 DecayHashCombineInReverse<8>(x.members, *this));
169 }
170
operator ()(const Function & x)171 HashValue StableHash::operator()(const Function& x) {
172 return DecayHashCombine<2>(hash_('f', (*this)(x.return_type_id)),
173 DecayHashCombineInReverse<4>(x.parameters, *this));
174 }
175
operator ()(const ElfSymbol & x)176 HashValue StableHash::operator()(const ElfSymbol& x) {
177 HashValue hash = hash_('s', x.symbol_name);
178 if (x.version_info) {
179 hash = DecayHashCombine<16>(
180 hash, hash_(x.version_info->name, x.version_info->is_default));
181 }
182 return hash;
183 }
184
operator ()(const Interface &)185 HashValue StableHash::operator()(const Interface&) {
186 return hash_("interface");
187 }
188
189 } // namespace stg
190