1 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 2 // -*- mode: C++ -*- 3 // 4 // Copyright 2020-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: Maria Teguiani 19 // Author: Giuliano Procida 20 // Author: Ignes Simeonova 21 22 #ifndef STG_COMPARISON_H_ 23 #define STG_COMPARISON_H_ 24 25 #include <cstddef> 26 #include <cstdint> 27 #include <functional> 28 #include <map> 29 #include <memory> 30 #include <optional> 31 #include <ostream> 32 #include <set> 33 #include <sstream> 34 #include <string> 35 #include <string_view> 36 #include <unordered_map> 37 #include <utility> 38 #include <vector> 39 40 #include "graph.h" 41 #include "runtime.h" 42 #include "scc.h" 43 44 namespace stg { 45 46 struct Ignore { 47 enum Value { 48 // noise reduction 49 SYMBOL_TYPE_PRESENCE, 50 TYPE_DECLARATION_STATUS, 51 PRIMITIVE_TYPE_ENCODING, 52 MEMBER_SIZE, 53 ENUM_UNDERLYING_TYPE, 54 QUALIFIER, 55 SYMBOL_CRC, 56 // ABI compatibility testing 57 INTERFACE_ADDITION, 58 TYPE_DEFINITION_ADDITION, 59 }; 60 61 using Bitset = uint16_t; 62 63 Ignore() = default; 64 template <typename... Values> IgnoreIgnore65 explicit Ignore(Values... values) { 66 for (auto value : {values...}) { 67 Set(value); 68 } 69 } 70 SetIgnore71 void Set(Value other) { 72 bitset = bitset | (1 << other); 73 } TestIgnore74 bool Test(Value other) const { 75 return bitset & (1 << other); 76 } 77 78 Bitset bitset = 0; 79 }; 80 81 std::optional<Ignore::Value> ParseIgnore(std::string_view ignore); 82 83 struct IgnoreUsage {}; 84 std::ostream& operator<<(std::ostream& os, IgnoreUsage); 85 86 using Comparison = std::pair<std::optional<Id>, std::optional<Id>>; 87 88 struct DiffDetail { DiffDetailDiffDetail89 DiffDetail(const std::string& text, const std::optional<Comparison>& edge) 90 : text_(text), edge_(edge) {} 91 std::string text_; 92 std::optional<Comparison> edge_; 93 }; 94 95 struct Diff { 96 // This diff node corresponds to an entity that is reportable, if it or any of 97 // its children (excluding reportable ones) has changed. 98 bool holds_changes = false; 99 // This diff node contains a local (non-recursive) change. 100 bool has_changes = false; 101 std::vector<DiffDetail> details; 102 AddDiff103 void Add(const std::string& text, 104 const std::optional<Comparison>& comparison) { 105 details.emplace_back(text, comparison); 106 } 107 }; 108 109 struct Result { 110 // Used when two nodes cannot be meaningfully compared. MarkIncomparableResult111 Result& MarkIncomparable() { 112 equals_ = false; 113 diff_.has_changes = true; 114 return *this; 115 } 116 117 // Used when a node attribute has changed. AddNodeDiffResult118 void AddNodeDiff(const std::string& text) { 119 equals_ = false; 120 diff_.has_changes = true; 121 diff_.Add(text, {}); 122 } 123 124 // Used when a node attribute may have changed. 125 template <typename T> MaybeAddNodeDiffResult126 void MaybeAddNodeDiff( 127 const std::string& text, const T& before, const T& after) { 128 if (before != after) { 129 std::ostringstream os; 130 os << text << " changed from " << before << " to " << after; 131 AddNodeDiff(os.str()); 132 } 133 } 134 135 // Used when a node attribute may have changed, lazy version. 136 template <typename T> MaybeAddNodeDiffResult137 void MaybeAddNodeDiff(const std::function<void(std::ostream&)>& text, 138 const T& before, const T& after) { 139 if (before != after) { 140 std::ostringstream os; 141 text(os); 142 os << " changed from " << before << " to " << after; 143 AddNodeDiff(os.str()); 144 } 145 } 146 147 // Used when node attributes are optional values. 148 template <typename T> MaybeAddNodeDiffResult149 void MaybeAddNodeDiff(const std::string& text, const std::optional<T>& before, 150 const std::optional<T>& after) { 151 if (before && after) { 152 MaybeAddNodeDiff(text, *before, *after); 153 } else if (before) { 154 std::ostringstream os; 155 os << text << ' ' << *before << " was removed"; 156 AddNodeDiff(os.str()); 157 } else if (after) { 158 std::ostringstream os; 159 os << text << ' ' << *after << " was added"; 160 AddNodeDiff(os.str()); 161 } 162 } 163 164 // Used when an edge has been removed or added. AddEdgeDiffResult165 void AddEdgeDiff(const std::string& text, const Comparison& comparison) { 166 equals_ = false; 167 diff_.Add(text, {comparison}); 168 } 169 170 // Used when an edge to a possible comparison is present. MaybeAddEdgeDiffResult171 void MaybeAddEdgeDiff(const std::string& text, 172 const std::pair<bool, std::optional<Comparison>>& p) { 173 equals_ &= p.first; 174 const auto& comparison = p.second; 175 if (comparison) { 176 diff_.Add(text, comparison); 177 } 178 } 179 180 // Used when an edge to a possible comparison is present, lazy version. MaybeAddEdgeDiffResult181 void MaybeAddEdgeDiff(const std::function<void(std::ostream&)>& text, 182 const std::pair<bool, std::optional<Comparison>>& p) { 183 equals_ &= p.first; 184 const auto& comparison = p.second; 185 if (comparison) { 186 std::ostringstream os; 187 text(os); 188 diff_.Add(os.str(), comparison); 189 } 190 } 191 192 bool equals_ = true; 193 Diff diff_; 194 }; 195 196 struct HashComparison { operatorHashComparison197 size_t operator()(const Comparison& comparison) const { 198 size_t seed = 0; 199 const std::hash<std::optional<Id>> h; 200 combine_hash(seed, h(comparison.first)); 201 combine_hash(seed, h(comparison.second)); 202 return seed; 203 } combine_hashHashComparison204 static void combine_hash(size_t& seed, size_t hash) { 205 seed ^= hash + 0x9e3779b97f4a7c15 + (seed << 12) + (seed >> 4); 206 } 207 }; 208 209 using Outcomes = std::unordered_map<Comparison, Diff, HashComparison>; 210 211 struct MatchingKey { MatchingKeyMatchingKey212 explicit MatchingKey(const Graph& graph) : graph(graph) {} 213 std::string operator()(Id id); 214 std::string operator()(const BaseClass&); 215 std::string operator()(const Method&); 216 std::string operator()(const Member&); 217 std::string operator()(const VariantMember&); 218 std::string operator()(const StructUnion&); 219 template <typename Node> 220 std::string operator()(const Node&); 221 const Graph& graph; 222 }; 223 224 std::pair<Id, std::vector<std::string>> ResolveTypedefs( 225 const Graph& graph, Id id); 226 227 struct ResolveTypedef { ResolveTypedefResolveTypedef228 ResolveTypedef(const Graph& graph, Id& id, std::vector<std::string>& names) 229 : graph(graph), id(id), names(names) {} 230 bool operator()(const Typedef&); 231 template <typename Node> 232 bool operator()(const Node&); 233 234 const Graph& graph; 235 Id& id; 236 std::vector<std::string>& names; 237 }; 238 239 using Qualifiers = std::set<Qualifier>; 240 241 // Separate qualifiers from underlying type. 242 // 243 // The caller must always be prepared to receive a different type as qualifiers 244 // are sometimes discarded. 245 std::pair<Id, Qualifiers> ResolveQualifiers(const Graph& graph, Id id); 246 247 struct ResolveQualifier { ResolveQualifierResolveQualifier248 ResolveQualifier(const Graph& graph, Id& id, Qualifiers& qualifiers) 249 : graph(graph), id(id), qualifiers(qualifiers) {} 250 bool operator()(const Qualified&); 251 bool operator()(const Array&); 252 bool operator()(const Function&); 253 template <typename Node> 254 bool operator()(const Node&); 255 256 const Graph& graph; 257 Id& id; 258 Qualifiers& qualifiers; 259 }; 260 261 struct Compare { CompareCompare262 Compare(Runtime& runtime, const Graph& graph, const Ignore& ignore) 263 : graph(graph), ignore(ignore), 264 queried(runtime, "compare.queried"), 265 already_compared(runtime, "compare.already_compared"), 266 being_compared(runtime, "compare.being_compared"), 267 really_compared(runtime, "compare.really_compared"), 268 equivalent(runtime, "compare.equivalent"), 269 inequivalent(runtime, "compare.inequivalent"), 270 scc_size(runtime, "compare.scc_size") {} 271 std::pair<bool, std::optional<Comparison>> operator()(Id id1, Id id2); 272 273 Comparison Removed(Id id); 274 Comparison Added(Id id); 275 void CompareDefined(bool defined1, bool defined2, Result& result); 276 277 Result Mismatch(); 278 Result operator()(const Special&, const Special&); 279 Result operator()(const PointerReference&, const PointerReference&); 280 Result operator()(const PointerToMember&, const PointerToMember&); 281 Result operator()(const Typedef&, const Typedef&); 282 Result operator()(const Qualified&, const Qualified&); 283 Result operator()(const Primitive&, const Primitive&); 284 Result operator()(const Array&, const Array&); 285 Result operator()(const BaseClass&, const BaseClass&); 286 Result operator()(const Method&, const Method&); 287 Result operator()(const Member&, const Member&); 288 Result operator()(const VariantMember&, const VariantMember&); 289 Result operator()(const StructUnion&, const StructUnion&); 290 Result operator()(const Enumeration&, const Enumeration&); 291 Result operator()(const Variant&, const Variant&); 292 Result operator()(const Function&, const Function&); 293 Result operator()(const ElfSymbol&, const ElfSymbol&); 294 Result operator()(const Interface&, const Interface&); 295 296 const Graph& graph; 297 const Ignore ignore; 298 std::unordered_map<Comparison, bool, HashComparison> known; 299 Outcomes outcomes; 300 Outcomes provisional; 301 SCC<Comparison, HashComparison> scc; 302 Counter queried; 303 Counter already_compared; 304 Counter being_compared; 305 Counter really_compared; 306 Counter equivalent; 307 Counter inequivalent; 308 Histogram scc_size; 309 }; 310 311 } // namespace stg 312 313 #endif // STG_COMPARISON_H_ 314