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: Giuliano Procida
19
20 #include "unification.h"
21
22 #include <cstddef>
23 #include <optional>
24 #include <utility>
25
26 #include "graph.h"
27
28 namespace stg {
29
30 namespace {
31
32 // Type Unification
33 //
34 // This is very similar to Equals. The differences are the recursion control,
35 // caching and handling of StructUnion and Enum nodes.
36 //
37 // During unification, keep track of which pairs of types need to be equal, but
38 // do not add them immediately to the unification substitutions. The caller can
39 // do that if the whole unification succeeds.
40 //
41 // A declaration and definition of the same named type can be unified. This is
42 // forward declaration resolution.
43 struct Unifier {
44 enum Winner { Neither, Right, Left }; // makes p ? Right : Neither a no-op
45
Unifierstg::__anon4e8ad42f0111::Unifier46 Unifier(const Graph& graph, Unification& unification)
47 : graph(graph), unification(unification) {}
48
operator ()stg::__anon4e8ad42f0111::Unifier49 bool operator()(Id id1, Id id2) {
50 Id fid1 = Find(id1);
51 Id fid2 = Find(id2);
52 if (fid1 == fid2) {
53 return true;
54 }
55
56 // Check if the comparison has an already known result.
57 //
58 // Opportunistic as seen is unaware of new mappings.
59 if (!seen.emplace(fid1, fid2).second) {
60 return true;
61 }
62
63 const auto winner = graph.Apply2<Winner>(*this, fid1, fid2);
64 if (winner == Neither) {
65 return false;
66 }
67
68 // These will occasionally get substituted due to a recursive call.
69 fid1 = Find(fid1);
70 fid2 = Find(fid2);
71 if (fid1 == fid2) {
72 return true;
73 }
74
75 if (winner == Left) {
76 std::swap(fid1, fid2);
77 }
78 mapping.insert({fid1, fid2});
79
80 return true;
81 }
82
operator ()stg::__anon4e8ad42f0111::Unifier83 bool operator()(const std::optional<Id>& opt1,
84 const std::optional<Id>& opt2) {
85 if (opt1.has_value() && opt2.has_value()) {
86 return (*this)(opt1.value(), opt2.value());
87 }
88 return opt1.has_value() == opt2.has_value();
89 }
90
operator ()stg::__anon4e8ad42f0111::Unifier91 bool operator()(const std::vector<Id>& ids1, const std::vector<Id>& ids2) {
92 bool result = ids1.size() == ids2.size();
93 for (size_t ix = 0; result && ix < ids1.size(); ++ix) {
94 result = (*this)(ids1[ix], ids2[ix]);
95 }
96 return result;
97 }
98
99 template <typename Key>
operator ()stg::__anon4e8ad42f0111::Unifier100 bool operator()(const std::map<Key, Id>& ids1,
101 const std::map<Key, Id>& ids2) {
102 bool result = ids1.size() == ids2.size();
103 auto it1 = ids1.begin();
104 auto it2 = ids2.begin();
105 const auto end1 = ids1.end();
106 const auto end2 = ids2.end();
107 while (result && it1 != end1 && it2 != end2) {
108 result = it1->first == it2->first
109 && (*this)(it1->second, it2->second);
110 ++it1;
111 ++it2;
112 }
113 return result && it1 == end1 && it2 == end2;
114 }
115
operator ()stg::__anon4e8ad42f0111::Unifier116 Winner operator()(const Special& x1, const Special& x2) {
117 return x1.kind == x2.kind
118 ? Right : Neither;
119 }
120
operator ()stg::__anon4e8ad42f0111::Unifier121 Winner operator()(const PointerReference& x1,
122 const PointerReference& x2) {
123 return x1.kind == x2.kind
124 && (*this)(x1.pointee_type_id, x2.pointee_type_id)
125 ? Right : Neither;
126 }
127
operator ()stg::__anon4e8ad42f0111::Unifier128 Winner operator()(const PointerToMember& x1, const PointerToMember& x2) {
129 return (*this)(x1.containing_type_id, x2.containing_type_id)
130 && (*this)(x1.pointee_type_id, x2.pointee_type_id)
131 ? Right : Neither;
132 }
133
operator ()stg::__anon4e8ad42f0111::Unifier134 Winner operator()(const Typedef& x1, const Typedef& x2) {
135 return x1.name == x2.name
136 && (*this)(x1.referred_type_id, x2.referred_type_id)
137 ? Right : Neither;
138 }
139
operator ()stg::__anon4e8ad42f0111::Unifier140 Winner operator()(const Qualified& x1, const Qualified& x2) {
141 return x1.qualifier == x2.qualifier
142 && (*this)(x1.qualified_type_id, x2.qualified_type_id)
143 ? Right : Neither;
144 }
145
operator ()stg::__anon4e8ad42f0111::Unifier146 Winner operator()(const Primitive& x1, const Primitive& x2) {
147 return x1.name == x2.name
148 && x1.encoding == x2.encoding
149 && x1.bytesize == x2.bytesize
150 ? Right : Neither;
151 }
152
operator ()stg::__anon4e8ad42f0111::Unifier153 Winner operator()(const Array& x1, const Array& x2) {
154 return x1.number_of_elements == x2.number_of_elements
155 && (*this)(x1.element_type_id, x2.element_type_id)
156 ? Right : Neither;
157 }
158
operator ()stg::__anon4e8ad42f0111::Unifier159 Winner operator()(const BaseClass& x1, const BaseClass& x2) {
160 return x1.offset == x2.offset
161 && x1.inheritance == x2.inheritance
162 && (*this)(x1.type_id, x2.type_id)
163 ? Right : Neither;
164 }
165
operator ()stg::__anon4e8ad42f0111::Unifier166 Winner operator()(const Method& x1, const Method& x2) {
167 return x1.mangled_name == x2.mangled_name
168 && x1.name == x2.name
169 && x1.vtable_offset == x2.vtable_offset
170 && (*this)(x1.type_id, x2.type_id)
171 ? Right : Neither;
172 }
173
operator ()stg::__anon4e8ad42f0111::Unifier174 Winner operator()(const Member& x1, const Member& x2) {
175 return x1.name == x2.name
176 && x1.offset == x2.offset
177 && x1.bitsize == x2.bitsize
178 && (*this)(x1.type_id, x2.type_id)
179 ? Right : Neither;
180 }
181
operator ()stg::__anon4e8ad42f0111::Unifier182 Winner operator()(const VariantMember& x1, const VariantMember& x2) {
183 return x1.name == x2.name
184 && x1.discriminant_value == x2.discriminant_value
185 && (*this)(x1.type_id, x2.type_id)
186 ? Right : Neither;
187 }
188
operator ()stg::__anon4e8ad42f0111::Unifier189 Winner operator()(const StructUnion& x1, const StructUnion& x2) {
190 const auto& definition1 = x1.definition;
191 const auto& definition2 = x2.definition;
192 bool result = x1.kind == x2.kind
193 && x1.name == x2.name;
194 // allow mismatches as forward declarations are always unifiable
195 if (result && definition1.has_value() && definition2.has_value()) {
196 result = definition1->bytesize == definition2->bytesize
197 && (*this)(definition1->base_classes, definition2->base_classes)
198 && (*this)(definition1->methods, definition2->methods)
199 && (*this)(definition1->members, definition2->members);
200 }
201 return result ? definition2.has_value() ? Right : Left : Neither;
202 }
203
operator ()stg::__anon4e8ad42f0111::Unifier204 Winner operator()(const Enumeration& x1, const Enumeration& x2) {
205 const auto& definition1 = x1.definition;
206 const auto& definition2 = x2.definition;
207 bool result = x1.name == x2.name;
208 // allow mismatches as forward declarations are always unifiable
209 if (result && definition1.has_value() && definition2.has_value()) {
210 result = (*this)(definition1->underlying_type_id,
211 definition2->underlying_type_id)
212 && definition1->enumerators == definition2->enumerators;
213 }
214 return result ? definition2.has_value() ? Right : Left : Neither;
215 }
216
operator ()stg::__anon4e8ad42f0111::Unifier217 Winner operator()(const Variant& x1, const Variant& x2) {
218 return x1.name == x2.name
219 && x1.bytesize == x2.bytesize
220 && (*this)(x1.discriminant, x2.discriminant)
221 && (*this)(x1.members, x2.members)
222 ? Right : Neither;
223 }
224
operator ()stg::__anon4e8ad42f0111::Unifier225 Winner operator()(const Function& x1, const Function& x2) {
226 return (*this)(x1.parameters, x2.parameters)
227 && (*this)(x1.return_type_id, x2.return_type_id)
228 ? Right : Neither;
229 }
230
operator ()stg::__anon4e8ad42f0111::Unifier231 Winner operator()(const ElfSymbol& x1, const ElfSymbol& x2) {
232 bool result = x1.symbol_name == x2.symbol_name
233 && x1.version_info == x2.version_info
234 && x1.is_defined == x2.is_defined
235 && x1.symbol_type == x2.symbol_type
236 && x1.binding == x2.binding
237 && x1.visibility == x2.visibility
238 && x1.crc == x2.crc
239 && x1.ns == x2.ns
240 && x1.full_name == x2.full_name
241 && x1.type_id.has_value() == x2.type_id.has_value();
242 if (result && x1.type_id.has_value()) {
243 result = (*this)(x1.type_id.value(), x2.type_id.value());
244 }
245 return result ? Right : Neither;
246 }
247
operator ()stg::__anon4e8ad42f0111::Unifier248 Winner operator()(const Interface& x1, const Interface& x2) {
249 return (*this)(x1.symbols, x2.symbols)
250 && (*this)(x1.types, x2.types)
251 ? Right : Neither;
252 }
253
Mismatchstg::__anon4e8ad42f0111::Unifier254 Winner Mismatch() {
255 return Neither;
256 }
257
Findstg::__anon4e8ad42f0111::Unifier258 Id Find(Id id) {
259 while (true) {
260 id = unification.Find(id);
261 auto it = mapping.find(id);
262 if (it != mapping.end()) {
263 id = it->second;
264 continue;
265 }
266 return id;
267 }
268 }
269
270 const Graph& graph;
271 Unification& unification;
272 std::unordered_set<Pair> seen;
273 std::unordered_map<Id, Id> mapping;
274 };
275
276 } // namespace
277
Unify(Id id1,Id id2)278 bool Unification::Unify(Id id1, Id id2) {
279 // TODO: Unifier only needs access to Unification::Find
280 Unifier unifier(graph_, *this);
281 if (unifier(id1, id2)) {
282 // commit
283 for (const auto& s : unifier.mapping) {
284 Union(s.first, s.second);
285 }
286 return true;
287 }
288 return false;
289 }
290
291 } // namespace stg
292