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_GRAPH_H_ 23 #define STG_GRAPH_H_ 24 25 #include <cstddef> 26 #include <cstdint> 27 #include <functional> 28 #include <map> 29 #include <optional> 30 #include <ostream> 31 #include <sstream> 32 #include <string> 33 #include <type_traits> 34 #include <utility> 35 #include <vector> 36 37 #include "error.h" 38 39 namespace stg { 40 41 // A wrapped (for type safety) array index. 42 struct Id { 43 // defined in graph.cc as maximum value for index type 44 static const Id kInvalid; IdId45 explicit Id(size_t ix) : ix_(ix) {} 46 // TODO: auto operator<=>(const Id&) const = default; 47 bool operator==(const Id& other) const { 48 return ix_ == other.ix_; 49 } 50 bool operator!=(const Id& other) const { 51 return ix_ != other.ix_; 52 } 53 size_t ix_; 54 }; 55 56 std::ostream& operator<<(std::ostream& os, Id id); 57 58 using Pair = std::pair<Id, Id>; 59 60 } // namespace stg 61 62 namespace std { 63 64 template <> 65 struct hash<stg::Id> { 66 size_t operator()(const stg::Id& id) const { 67 return hash<decltype(id.ix_)>()(id.ix_); 68 } 69 }; 70 71 template <> 72 struct hash<stg::Pair> { 73 size_t operator()(const stg::Pair& comparison) const { 74 const hash<stg::Id> h; 75 auto h1 = h(comparison.first); 76 auto h2 = h(comparison.second); 77 // assumes 64-bit size_t, would be better if std::hash_combine existed 78 return h1 ^ (h2 + 0x9e3779b97f4a7c15 + (h1 << 12) + (h1 >> 4)); 79 } 80 }; 81 82 } // namespace std 83 84 namespace stg { 85 86 struct Special { 87 enum class Kind { 88 VOID, 89 VARIADIC, 90 NULLPTR, 91 }; 92 explicit Special(Kind kind) 93 : kind(kind) {} 94 95 Kind kind; 96 }; 97 98 struct PointerReference { 99 enum class Kind { 100 POINTER, 101 LVALUE_REFERENCE, 102 RVALUE_REFERENCE, 103 }; 104 PointerReference(Kind kind, Id pointee_type_id) 105 : kind(kind), pointee_type_id(pointee_type_id) {} 106 107 Kind kind; 108 Id pointee_type_id; 109 }; 110 111 struct PointerToMember { 112 PointerToMember(Id containing_type_id, Id pointee_type_id) 113 : containing_type_id(containing_type_id), pointee_type_id(pointee_type_id) 114 {} 115 116 Id containing_type_id; 117 Id pointee_type_id; 118 }; 119 120 struct Typedef { 121 Typedef(const std::string& name, Id referred_type_id) 122 : name(name), referred_type_id(referred_type_id) {} 123 124 std::string name; 125 Id referred_type_id; 126 }; 127 128 enum class Qualifier { CONST, VOLATILE, RESTRICT, ATOMIC }; 129 130 std::ostream& operator<<(std::ostream& os, Qualifier qualifier); 131 132 struct Qualified { 133 Qualified(Qualifier qualifier, Id qualified_type_id) 134 : qualifier(qualifier), qualified_type_id(qualified_type_id) {} 135 136 Qualifier qualifier; 137 Id qualified_type_id; 138 }; 139 140 struct Primitive { 141 enum class Encoding { 142 BOOLEAN, 143 SIGNED_INTEGER, 144 UNSIGNED_INTEGER, 145 SIGNED_CHARACTER, 146 UNSIGNED_CHARACTER, 147 REAL_NUMBER, 148 COMPLEX_NUMBER, 149 UTF, 150 }; 151 Primitive(const std::string& name, std::optional<Encoding> encoding, 152 uint32_t bytesize) 153 : name(name), encoding(encoding), bytesize(bytesize) {} 154 155 std::string name; 156 std::optional<Encoding> encoding; 157 uint32_t bytesize; 158 }; 159 160 struct Array { 161 Array(uint64_t number_of_elements, Id element_type_id) 162 : number_of_elements(number_of_elements), 163 element_type_id(element_type_id) {} 164 165 uint64_t number_of_elements; 166 Id element_type_id; 167 }; 168 169 struct BaseClass { 170 enum class Inheritance { NON_VIRTUAL, VIRTUAL }; 171 BaseClass(Id type_id, uint64_t offset, Inheritance inheritance) 172 : type_id(type_id), offset(offset), inheritance(inheritance) {} 173 174 Id type_id; 175 uint64_t offset; 176 Inheritance inheritance; 177 }; 178 179 std::ostream& operator<<(std::ostream& os, BaseClass::Inheritance inheritance); 180 181 struct Method { 182 Method(const std::string& mangled_name, const std::string& name, 183 uint64_t vtable_offset, Id type_id) 184 : mangled_name(mangled_name), name(name), 185 vtable_offset(vtable_offset), type_id(type_id) {} 186 187 std::string mangled_name; 188 std::string name; 189 uint64_t vtable_offset; 190 Id type_id; 191 }; 192 193 struct Member { 194 Member(const std::string& name, Id type_id, uint64_t offset, uint64_t bitsize) 195 : name(name), type_id(type_id), offset(offset), bitsize(bitsize) {} 196 197 std::string name; 198 Id type_id; 199 uint64_t offset; 200 uint64_t bitsize; 201 }; 202 203 struct VariantMember { 204 VariantMember(const std::string& name, 205 std::optional<int64_t> discriminant_value, Id type_id) 206 : name(name), discriminant_value(discriminant_value), type_id(type_id) {} 207 208 std::string name; 209 std::optional<int64_t> discriminant_value; 210 Id type_id; 211 }; 212 213 struct StructUnion { 214 enum class Kind { STRUCT, UNION }; 215 struct Definition { 216 uint64_t bytesize; 217 std::vector<Id> base_classes; 218 std::vector<Id> methods; 219 std::vector<Id> members; 220 }; 221 StructUnion(Kind kind, const std::string& name) : kind(kind), name(name) {} 222 StructUnion(Kind kind, const std::string& name, uint64_t bytesize, 223 const std::vector<Id>& base_classes, 224 const std::vector<Id>& methods, const std::vector<Id>& members) 225 : kind(kind), name(name), 226 definition({bytesize, base_classes, methods, members}) {} 227 228 Kind kind; 229 std::string name; 230 std::optional<Definition> definition; 231 }; 232 233 std::ostream& operator<<(std::ostream& os, StructUnion::Kind kind); 234 std::string& operator+=(std::string& os, StructUnion::Kind kind); 235 236 struct Enumeration { 237 using Enumerators = std::vector<std::pair<std::string, int64_t>>; 238 struct Definition { 239 Id underlying_type_id; 240 Enumerators enumerators; 241 }; 242 explicit Enumeration(const std::string& name) : name(name) {} 243 Enumeration(const std::string& name, Id underlying_type_id, 244 const Enumerators& enumerators) 245 : name(name), definition({underlying_type_id, enumerators}) {} 246 247 std::string name; 248 std::optional<Definition> definition; 249 }; 250 251 struct Variant { 252 Variant(const std::string& name, uint64_t bytesize, 253 std::optional<Id> discriminant, const std::vector<Id>& members) 254 : name(name), 255 bytesize(bytesize), 256 discriminant(discriminant), 257 members(members) {} 258 259 std::string name; 260 uint64_t bytesize; 261 std::optional<Id> discriminant; 262 std::vector<Id> members; 263 }; 264 265 struct Function { 266 Function(Id return_type_id, const std::vector<Id>& parameters) 267 : return_type_id(return_type_id), parameters(parameters) {} 268 269 Id return_type_id; 270 std::vector<Id> parameters; 271 }; 272 273 struct ElfSymbol { 274 enum class SymbolType { OBJECT, FUNCTION, COMMON, TLS, GNU_IFUNC }; 275 enum class Binding { GLOBAL, LOCAL, WEAK, GNU_UNIQUE }; 276 enum class Visibility { DEFAULT, PROTECTED, HIDDEN, INTERNAL }; 277 struct VersionInfo { 278 // TODO: auto operator<=>(const VersionInfo&) const = default; 279 bool operator==(const VersionInfo& other) const { 280 return is_default == other.is_default && name == other.name; 281 } 282 bool is_default; 283 std::string name; 284 }; 285 struct CRC { 286 explicit CRC(uint32_t number) : number(number) {} 287 // TODO: auto operator<=>(const bool&) const = default; 288 bool operator==(const CRC& other) const { 289 return number == other.number; 290 } 291 bool operator!=(const CRC& other) const { 292 return number != other.number; 293 } 294 uint32_t number; 295 }; 296 ElfSymbol(const std::string& symbol_name, 297 std::optional<VersionInfo> version_info, 298 bool is_defined, 299 SymbolType symbol_type, 300 Binding binding, 301 Visibility visibility, 302 std::optional<CRC> crc, 303 std::optional<std::string> ns, 304 std::optional<Id> type_id, 305 const std::optional<std::string>& full_name) 306 : symbol_name(symbol_name), 307 version_info(version_info), 308 is_defined(is_defined), 309 symbol_type(symbol_type), 310 binding(binding), 311 visibility(visibility), 312 crc(crc), 313 ns(ns), 314 type_id(type_id), 315 full_name(full_name) {} 316 317 std::string symbol_name; 318 std::optional<VersionInfo> version_info; 319 bool is_defined; 320 SymbolType symbol_type; 321 Binding binding; 322 Visibility visibility; 323 std::optional<CRC> crc; 324 std::optional<std::string> ns; 325 std::optional<Id> type_id; 326 std::optional<std::string> full_name; 327 }; 328 329 std::ostream& operator<<(std::ostream& os, ElfSymbol::SymbolType); 330 std::ostream& operator<<(std::ostream& os, ElfSymbol::Binding); 331 std::ostream& operator<<(std::ostream& os, ElfSymbol::Visibility); 332 333 std::string VersionInfoToString(const ElfSymbol::VersionInfo& version_info); 334 std::string VersionedSymbolName(const ElfSymbol&); 335 336 std::ostream& operator<<(std::ostream& os, ElfSymbol::CRC crc); 337 338 struct Interface { 339 explicit Interface(const std::map<std::string, Id>& symbols) 340 : symbols(symbols) {} 341 Interface(const std::map<std::string, Id>& symbols, 342 const std::map<std::string, Id>& types) 343 : symbols(symbols), types(types) {} 344 345 std::map<std::string, Id> symbols; 346 std::map<std::string, Id> types; 347 }; 348 349 std::ostream& operator<<(std::ostream& os, Primitive::Encoding encoding); 350 351 // Concrete graph type. 352 class Graph { 353 public: 354 Id Limit() const { 355 return Id(indirection_.size()); 356 } 357 358 bool Is(Id id) const { 359 return indirection_[id.ix_].first != Which::ABSENT; 360 } 361 362 Id Allocate() { 363 const auto id = Limit(); 364 indirection_.emplace_back(Which::ABSENT, 0); 365 return id; 366 } 367 368 template <typename Node, typename... Args> 369 void Set(Id id, Args&&... args) { 370 auto& reference = indirection_[id.ix_]; 371 if (reference.first != Which::ABSENT) { 372 Die() << "node value already set: " << id; 373 } 374 if constexpr (std::is_same_v<Node, Special>) { 375 reference = {Which::SPECIAL, special_.size()}; 376 special_.emplace_back(std::forward<Args>(args)...); 377 } else if constexpr (std::is_same_v<Node, PointerReference>) { 378 reference = {Which::POINTER_REFERENCE, pointer_reference_.size()}; 379 pointer_reference_.emplace_back(std::forward<Args>(args)...); 380 } else if constexpr (std::is_same_v<Node, PointerToMember>) { 381 reference = {Which::POINTER_TO_MEMBER, pointer_to_member_.size()}; 382 pointer_to_member_.emplace_back(std::forward<Args>(args)...); 383 } else if constexpr (std::is_same_v<Node, Typedef>) { 384 reference = {Which::TYPEDEF, typedef_.size()}; 385 typedef_.emplace_back(std::forward<Args>(args)...); 386 } else if constexpr (std::is_same_v<Node, Qualified>) { 387 reference = {Which::QUALIFIED, qualified_.size()}; 388 qualified_.emplace_back(std::forward<Args>(args)...); 389 } else if constexpr (std::is_same_v<Node, Primitive>) { 390 reference = {Which::PRIMITIVE, primitive_.size()}; 391 primitive_.emplace_back(std::forward<Args>(args)...); 392 } else if constexpr (std::is_same_v<Node, Array>) { 393 reference = {Which::ARRAY, array_.size()}; 394 array_.emplace_back(std::forward<Args>(args)...); 395 } else if constexpr (std::is_same_v<Node, BaseClass>) { 396 reference = {Which::BASE_CLASS, base_class_.size()}; 397 base_class_.emplace_back(std::forward<Args>(args)...); 398 } else if constexpr (std::is_same_v<Node, Method>) { 399 reference = {Which::METHOD, method_.size()}; 400 method_.emplace_back(std::forward<Args>(args)...); 401 } else if constexpr (std::is_same_v<Node, Member>) { 402 reference = {Which::MEMBER, member_.size()}; 403 member_.emplace_back(std::forward<Args>(args)...); 404 } else if constexpr (std::is_same_v<Node, VariantMember>) { 405 reference = {Which::VARIANT_MEMBER, variant_member_.size()}; 406 variant_member_.emplace_back(std::forward<Args>(args)...); 407 } else if constexpr (std::is_same_v<Node, StructUnion>) { 408 reference = {Which::STRUCT_UNION, struct_union_.size()}; 409 struct_union_.emplace_back(std::forward<Args>(args)...); 410 } else if constexpr (std::is_same_v<Node, Enumeration>) { 411 reference = {Which::ENUMERATION, enumeration_.size()}; 412 enumeration_.emplace_back(std::forward<Args>(args)...); 413 } else if constexpr (std::is_same_v<Node, Variant>) { 414 reference = {Which::VARIANT, variant_.size()}; 415 variant_.emplace_back(std::forward<Args>(args)...); 416 } else if constexpr (std::is_same_v<Node, Function>) { 417 reference = {Which::FUNCTION, function_.size()}; 418 function_.emplace_back(std::forward<Args>(args)...); 419 } else if constexpr (std::is_same_v<Node, ElfSymbol>) { 420 reference = {Which::ELF_SYMBOL, elf_symbol_.size()}; 421 elf_symbol_.emplace_back(std::forward<Args>(args)...); 422 } else if constexpr (std::is_same_v<Node, Interface>) { 423 reference = {Which::INTERFACE, interface_.size()}; 424 interface_.emplace_back(std::forward<Args>(args)...); 425 } else { 426 // unfortunately we cannot static_assert(false, "missing case") 427 static_assert(std::is_same<Node, Node*>::value, "missing case"); 428 } 429 } 430 431 template <typename Node, typename... Args> 432 Id Add(Args&&... args) { 433 auto id = Allocate(); 434 Set<Node>(id, std::forward<Args>(args)...); 435 return id; 436 } 437 438 void Deallocate(Id) { 439 // don't actually do anything, not supported 440 } 441 442 void Unset(Id id) { 443 auto& reference = indirection_[id.ix_]; 444 if (reference.first == Which::ABSENT) { 445 Die() << "node value already unset: " << id; 446 } 447 reference = {Which::ABSENT, 0}; 448 } 449 450 void Remove(Id id) { 451 Unset(id); 452 Deallocate(id); 453 } 454 455 template <typename Result, typename FunctionObject, typename... Args> 456 Result Apply(FunctionObject& function, Id id, Args&&... args) const; 457 458 template <typename Result, typename FunctionObject, typename... Args> 459 Result Apply2(FunctionObject& function, Id id1, Id id2, Args&&... args) const; 460 461 template <typename Result, typename FunctionObject, typename... Args> 462 Result Apply(FunctionObject& function, Id id, Args&&... args); 463 464 template <typename Function> 465 void ForEach(Id start, Id limit, Function&& function) const { 466 for (size_t ix = start.ix_; ix < limit.ix_; ++ix) { 467 const Id id(ix); 468 if (Is(id)) { 469 function(id); 470 } 471 } 472 } 473 474 private: 475 enum class Which { 476 ABSENT, 477 SPECIAL, 478 POINTER_REFERENCE, 479 POINTER_TO_MEMBER, 480 TYPEDEF, 481 QUALIFIED, 482 PRIMITIVE, 483 ARRAY, 484 BASE_CLASS, 485 METHOD, 486 MEMBER, 487 VARIANT_MEMBER, 488 STRUCT_UNION, 489 ENUMERATION, 490 VARIANT, 491 FUNCTION, 492 ELF_SYMBOL, 493 INTERFACE, 494 }; 495 496 std::vector<std::pair<Which, size_t>> indirection_; 497 498 std::vector<Special> special_; 499 std::vector<PointerReference> pointer_reference_; 500 std::vector<PointerToMember> pointer_to_member_; 501 std::vector<Typedef> typedef_; 502 std::vector<Qualified> qualified_; 503 std::vector<Primitive> primitive_; 504 std::vector<Array> array_; 505 std::vector<BaseClass> base_class_; 506 std::vector<Method> method_; 507 std::vector<Member> member_; 508 std::vector<VariantMember> variant_member_; 509 std::vector<StructUnion> struct_union_; 510 std::vector<Enumeration> enumeration_; 511 std::vector<Variant> variant_; 512 std::vector<Function> function_; 513 std::vector<ElfSymbol> elf_symbol_; 514 std::vector<Interface> interface_; 515 }; 516 517 template <typename Result, typename FunctionObject, typename... Args> 518 Result Graph::Apply(FunctionObject& function, Id id, Args&&... args) const { 519 const auto& [which, ix] = indirection_[id.ix_]; 520 switch (which) { 521 case Which::ABSENT: 522 Die() << "undefined node: " << id; 523 case Which::SPECIAL: 524 return function(special_[ix], std::forward<Args>(args)...); 525 case Which::POINTER_REFERENCE: 526 return function(pointer_reference_[ix], std::forward<Args>(args)...); 527 case Which::POINTER_TO_MEMBER: 528 return function(pointer_to_member_[ix], std::forward<Args>(args)...); 529 case Which::TYPEDEF: 530 return function(typedef_[ix], std::forward<Args>(args)...); 531 case Which::QUALIFIED: 532 return function(qualified_[ix], std::forward<Args>(args)...); 533 case Which::PRIMITIVE: 534 return function(primitive_[ix], std::forward<Args>(args)...); 535 case Which::ARRAY: 536 return function(array_[ix], std::forward<Args>(args)...); 537 case Which::BASE_CLASS: 538 return function(base_class_[ix], std::forward<Args>(args)...); 539 case Which::METHOD: 540 return function(method_[ix], std::forward<Args>(args)...); 541 case Which::MEMBER: 542 return function(member_[ix], std::forward<Args>(args)...); 543 case Which::VARIANT_MEMBER: 544 return function(variant_member_[ix], std::forward<Args>(args)...); 545 case Which::STRUCT_UNION: 546 return function(struct_union_[ix], std::forward<Args>(args)...); 547 case Which::ENUMERATION: 548 return function(enumeration_[ix], std::forward<Args>(args)...); 549 case Which::VARIANT: 550 return function(variant_[ix], std::forward<Args>(args)...); 551 case Which::FUNCTION: 552 return function(function_[ix], std::forward<Args>(args)...); 553 case Which::ELF_SYMBOL: 554 return function(elf_symbol_[ix], std::forward<Args>(args)...); 555 case Which::INTERFACE: 556 return function(interface_[ix], std::forward<Args>(args)...); 557 } 558 } 559 560 template <typename Result, typename FunctionObject, typename... Args> 561 Result Graph::Apply2( 562 FunctionObject& function, Id id1, Id id2, Args&&... args) const { 563 const auto& [which1, ix1] = indirection_[id1.ix_]; 564 const auto& [which2, ix2] = indirection_[id2.ix_]; 565 if (which1 != which2) { 566 return function.Mismatch(std::forward<Args>(args)...); 567 } 568 switch (which1) { 569 case Which::ABSENT: 570 Die() << "undefined nodes: " << id1 << ", " << id2; 571 case Which::SPECIAL: 572 return function(special_[ix1], special_[ix2], 573 std::forward<Args>(args)...); 574 case Which::POINTER_REFERENCE: 575 return function(pointer_reference_[ix1], pointer_reference_[ix2], 576 std::forward<Args>(args)...); 577 case Which::POINTER_TO_MEMBER: 578 return function(pointer_to_member_[ix1], pointer_to_member_[ix2], 579 std::forward<Args>(args)...); 580 case Which::TYPEDEF: 581 return function(typedef_[ix1], typedef_[ix2], 582 std::forward<Args>(args)...); 583 case Which::QUALIFIED: 584 return function(qualified_[ix1], qualified_[ix2], 585 std::forward<Args>(args)...); 586 case Which::PRIMITIVE: 587 return function(primitive_[ix1], primitive_[ix2], 588 std::forward<Args>(args)...); 589 case Which::ARRAY: 590 return function(array_[ix1], array_[ix2], 591 std::forward<Args>(args)...); 592 case Which::BASE_CLASS: 593 return function(base_class_[ix1], base_class_[ix2], 594 std::forward<Args>(args)...); 595 case Which::METHOD: 596 return function(method_[ix1], method_[ix2], 597 std::forward<Args>(args)...); 598 case Which::MEMBER: 599 return function(member_[ix1], member_[ix2], 600 std::forward<Args>(args)...); 601 case Which::VARIANT_MEMBER: 602 return function(variant_member_[ix1], variant_member_[ix2], 603 std::forward<Args>(args)...); 604 case Which::STRUCT_UNION: 605 return function(struct_union_[ix1], struct_union_[ix2], 606 std::forward<Args>(args)...); 607 case Which::ENUMERATION: 608 return function(enumeration_[ix1], enumeration_[ix2], 609 std::forward<Args>(args)...); 610 case Which::VARIANT: 611 return function(variant_[ix1], variant_[ix2], 612 std::forward<Args>(args)...); 613 case Which::FUNCTION: 614 return function(function_[ix1], function_[ix2], 615 std::forward<Args>(args)...); 616 case Which::ELF_SYMBOL: 617 return function(elf_symbol_[ix1], elf_symbol_[ix2], 618 std::forward<Args>(args)...); 619 case Which::INTERFACE: 620 return function(interface_[ix1], interface_[ix2], 621 std::forward<Args>(args)...); 622 } 623 } 624 625 template <typename Result, typename FunctionObject, typename... Args> 626 struct ConstAdapter { 627 explicit ConstAdapter(FunctionObject& function) : function(function) {} 628 template <typename Node> 629 Result operator()(const Node& node, Args&&... args) { 630 return function(const_cast<Node&>(node), std::forward<Args>(args)...); 631 } 632 FunctionObject& function; 633 }; 634 635 template <typename Result, typename FunctionObject, typename... Args> 636 Result Graph::Apply(FunctionObject& function, Id id, Args&&... args) { 637 ConstAdapter<Result, FunctionObject, Args&&...> adapter(function); 638 return static_cast<const Graph&>(*this).Apply<Result>( 639 adapter, id, std::forward<Args>(args)...); 640 } 641 642 struct InterfaceKey { 643 explicit InterfaceKey(const Graph& graph) : graph(graph) {} 644 645 std::string operator()(Id id) const { 646 return graph.Apply<std::string>(*this, id); 647 } 648 649 std::string operator()(const stg::Typedef& x) const { 650 return x.name; 651 } 652 653 std::string operator()(const stg::StructUnion& x) const { 654 if (x.name.empty()) { 655 Die() << "anonymous struct/union interface type"; 656 } 657 std::ostringstream os; 658 os << x.kind << ' ' << x.name; 659 return os.str(); 660 } 661 662 std::string operator()(const stg::Enumeration& x) const { 663 if (x.name.empty()) { 664 Die() << "anonymous enum interface type"; 665 } 666 return "enum " + x.name; 667 } 668 669 std::string operator()(const stg::Variant& x) const { 670 if (x.name.empty()) { 671 Die() << "anonymous variant interface type"; 672 } 673 return "variant " + x.name; 674 } 675 676 std::string operator()(const stg::ElfSymbol& x) const { 677 return VersionedSymbolName(x); 678 } 679 680 template <typename Node> 681 std::string operator()(const Node&) const { 682 Die() << "unexpected interface type"; 683 } 684 685 const Graph& graph; 686 }; 687 688 // Roughly equivalent to std::set<Id> but with constant time operations and 689 // key set limited to allocated Ids. 690 class DenseIdSet { 691 public: 692 explicit DenseIdSet(Id start) : offset_(start.ix_) {} 693 void Reserve(Id limit) { 694 ids_.reserve(limit.ix_ - offset_); 695 } 696 bool Insert(Id id) { 697 const auto ix = id.ix_; 698 if (ix < offset_) { 699 Die() << "DenseIdSet: out of range access to " << id; 700 } 701 const auto offset_ix = ix - offset_; 702 if (offset_ix >= ids_.size()) { 703 ids_.resize(offset_ix + 1, false); 704 } 705 if (ids_[offset_ix]) { 706 return false; 707 } 708 ids_[offset_ix] = true; 709 return true; 710 } 711 712 private: 713 size_t offset_; 714 std::vector<bool> ids_; 715 }; 716 717 // Roughly equivalent to std::map<Id, Id>, defaulted to the identity mapping, 718 // but with constant time operations and key set limited to allocated Ids. 719 class DenseIdMapping { 720 public: 721 explicit DenseIdMapping(Id start) : offset_(start.ix_) {} 722 void Reserve(Id limit) { 723 ids_.reserve(limit.ix_ - offset_); 724 } 725 Id& operator[](Id id) { 726 const auto ix = id.ix_; 727 if (ix < offset_) { 728 Die() << "DenseIdMapping: out of range access to " << id; 729 } 730 Populate(ix + 1); 731 return ids_[ix - offset_]; 732 } 733 734 private: 735 void Populate(size_t size) { 736 for (size_t ix = offset_ + ids_.size(); ix < size; ++ix) { 737 ids_.emplace_back(ix); 738 } 739 } 740 741 size_t offset_; 742 std::vector<Id> ids_; 743 }; 744 745 } // namespace stg 746 747 #endif // STG_GRAPH_H_ 748