private_typeinfo.cpp revision facfc46ef3ecde55e675fa19d93d9a25b169c49f
1//===----------------------- private_typeinfo.cpp -------------------------===// 2// 3// The LLVM Compiler Infrastructure 4// 5// This file is dual licensed under the MIT and the University of Illinois Open 6// Source Licenses. See LICENSE.TXT for details. 7// 8//===----------------------------------------------------------------------===// 9 10#define __name __type_name 11 12#include "private_typeinfo.h" 13 14#include <iostream> 15 16namespace std 17{ 18 19#pragma GCC visibility push(default) 20 21type_info::~type_info() 22{ 23} 24 25#pragma GCC visibility pop 26 27} // std 28 29namespace __cxxabiv1 30{ 31 32#pragma GCC visibility push(hidden) 33 34// __shim_type_info 35 36__shim_type_info::~__shim_type_info() 37{ 38} 39 40// __fundamental_type_info 41 42// This miraculously (compiler magic) emits the type_info's for: 43// 1. all of the fundamental types 44// 2. pointers to all of the fundamental types 45// 3. pointers to all of the const fundamental types 46__fundamental_type_info::~__fundamental_type_info() 47{ 48} 49 50void 51__fundamental_type_info::display() const 52{ 53 std::cout << "__fundamental_type_info " << __type_name << '\n'; 54} 55 56// __array_type_info 57 58__array_type_info::~__array_type_info() 59{ 60} 61 62void 63__array_type_info::display() const 64{ 65 std::cout << "__array_type_info " << __type_name << '\n'; 66} 67 68// __function_type_info 69 70__function_type_info::~__function_type_info() 71{ 72} 73 74void 75__function_type_info::display() const 76{ 77 std::cout << "__function_type_info " << __type_name << '\n'; 78} 79 80// __enum_type_info 81 82__enum_type_info::~__enum_type_info() 83{ 84} 85 86void 87__enum_type_info::display() const 88{ 89 std::cout << "__enum_type_info " << __type_name << '\n'; 90} 91 92// __class_type_info 93 94__class_type_info::~__class_type_info() 95{ 96} 97 98void 99__class_type_info::display() const 100{ 101 std::cout << "__class_type_info " << __type_name << '\n'; 102} 103 104// __si_class_type_info 105 106__si_class_type_info::~__si_class_type_info() 107{ 108} 109 110void 111__si_class_type_info::display() const 112{ 113 std::cout << "__si_class_type_info " << __type_name << '\n'; 114 std::cout << "derived from "; 115 __base_type->display(); 116} 117 118// __vmi_class_type_info 119 120__vmi_class_type_info::~__vmi_class_type_info() 121{ 122} 123 124void 125__vmi_class_type_info::display() const 126{ 127 std::cout << "__vmi_class_type_info " << __type_name << '\n'; 128 if (__flags & __non_diamond_repeat_mask) 129 std::cout << "__non_diamond_repeat_mask\n"; 130 if (__flags & __diamond_shaped_mask) 131 std::cout << "__diamond_shaped_mask\n"; 132 std::cout << "derived from\n"; 133 for (const __base_class_type_info* p = __base_info; p < __base_info + __base_count; ++p) 134 p->display(); 135} 136 137void 138__base_class_type_info::display() const 139{ 140 if (__offset_flags & __public_mask) 141 std::cout << "public "; 142 __base_type->display(); 143} 144 145// __pbase_type_info 146 147__pbase_type_info::~__pbase_type_info() 148{ 149} 150 151// __pointer_type_info 152 153__pointer_type_info::~__pointer_type_info() 154{ 155} 156 157void 158__pointer_type_info::display() const 159{ 160 std::cout << "__pointer_type_info " << __type_name << '\n'; 161 if (__flags & __const_mask) 162 std::cout << "const "; 163 if (__flags & __volatile_mask) 164 std::cout << "volatile "; 165 if (__flags & __restrict_mask) 166 std::cout << "restrict "; 167 if (__flags & __incomplete_mask) 168 std::cout << "__incomplete_mask "; 169 if (__flags & __incomplete_class_mask) 170 std::cout << "__incomplete_class_mask "; 171 std::cout << "pointer to "; 172 __pointee->display(); 173} 174 175// __pointer_to_member_type_info 176 177__pointer_to_member_type_info::~__pointer_to_member_type_info() 178{ 179} 180 181void 182__pointer_to_member_type_info::display() const 183{ 184 std::cout << "__pointer_to_member_type_info " << __type_name << '\n'; 185 if (__flags & __const_mask) 186 std::cout << "const "; 187 if (__flags & __volatile_mask) 188 std::cout << "volatile "; 189 if (__flags & __restrict_mask) 190 std::cout << "restrict "; 191 if (__flags & __incomplete_mask) 192 std::cout << "__incomplete_mask "; 193 if (__flags & __incomplete_class_mask) 194 std::cout << "__incomplete_class_mask "; 195 std::cout << "member pointer to class "; 196 __context->display(); 197 std::cout << "and type "; 198 __pointee->display(); 199} 200 201#pragma GCC visibility pop 202#pragma GCC visibility push(default) 203 204// __dynamic_cast 205 206// static_ptr: pointer to an object of type static_type; nonnull, and since the 207// object is polymorphic, *(void**)static_ptr is a virtual table pointer. 208// static_ptr is &v in the expression dynamic_cast<T>(v). 209// static_type: static type of the object pointed to by static_ptr. 210// dst_type: destination type of the cast (the "T" in "dynamic_cast<T>(v)"). 211// src2dst_offset: a static hint about the location of the 212// source subobject with respect to the complete object; 213// special negative values are: 214// -1: no hint 215// -2: static_type is not a public base of dst_type 216// -3: static_type is a multiple public base type but never a 217// virtual base type 218// otherwise, the static_type type is a unique public nonvirtual 219// base type of dst_type at offset src2dst_offset from the 220// origin of dst_type. 221// 222// (dynamic_ptr, dynamic_type) are the run time type of the complete object 223// referred to by static_ptr and a pointer to it. These can be found from 224// static_ptr for polymorphic types. 225// static_type is guaranteed to be a polymorphic type. 226// 227// (dynamic_ptr, dynamic_type) is the root of a DAG that grows upward. Each 228// node of the tree represents a base class/object of its parent (or parents) below. 229// Each node is uniquely represented by a pointer to the object, and a pointer 230// to a type_info - its type. Different nodes may have the same pointer and 231// different nodes may have the same type. But only one node has a specific 232// (pointer-value, type) pair. In C++ two objects of the same type can not 233// share the same address. 234// 235// There are two flavors of nodes which have the type dst_type: 236// 1. Those that are derived from (below) (static_ptr, static_type). 237// 2. Those that are not derived from (below) (static_ptr, static_type). 238// 239// Invariants of the DAG: 240// 241// There is at least one path from the root (dynamic_ptr, dynamic_type) to 242// the node (static_ptr, static_type). This path may or may not be public. 243// There may be more than one such path (some public some not). Such a path may 244// or may not go through a node having type dst_type. 245// 246// No node of type T appears above a node of the same type. That means that 247// there is only one node with dynamic_type. And if dynamic_type == dst_type, 248// then there is only one dst_type in the DAG. 249// 250// No node of type dst_type appears above a node of type static_type. Such 251// DAG's are possible in C++, but the compiler computes those dynamic_casts at 252// compile time, and only calls __dynamic_cast when dst_type lies below 253// static_type in the DAG. 254// 255// dst_type != static_type: The compiler computes the dynamic_cast in this case too. 256// dynamic_type != static_type: The compiler computes the dynamic_cast in this case too. 257// 258// Returns: 259// 260// If there is exactly one dst_type of flavor 1, and 261// If there is a public path from that dst_type to (static_ptr, static_type), or 262// If there are 0 dst_types of flavor 2, and there is a public path from 263// (dynamic_ptr, dynamic_type) to (static_ptr, static_type) and a public 264// path from (dynamic_ptr, dynamic_type) to the one dst_type, then return 265// a pointer to that dst_type. 266// Else if there are 0 dst_types of flavor 1 and exactly 1 dst_type of flavor 2, and 267// if there is a public path from (dynamic_ptr, dynamic_type) to 268// (static_ptr, static_type) and a public path from (dynamic_ptr, dynamic_type) 269// to the one dst_type, then return a pointer to that one dst_type. 270// Else return nullptr. 271// 272// If dynamic_type == dst_type, then the above algorithm collapses to the 273// following cheaper algorithm: 274// 275// If there is a public path from (dynamic_ptr, dynamic_type) to 276// (static_ptr, static_type), then return dynamic_ptr. 277// Else return nullptr. 278extern "C" 279void* 280__dynamic_cast(const void* static_ptr, 281 const __class_type_info* static_type, 282 const __class_type_info* dst_type, 283 std::ptrdiff_t src2dst_offset) 284{ 285 // TODO: Take advantage of src2dst_offset 286 287 // Get (dynamic_ptr, dynamic_type) from static_ptr 288 void** vtable = *(void***)static_ptr; 289 ptrdiff_t offset_to_derived = reinterpret_cast<ptrdiff_t>(vtable[-2]); 290 const void* dynamic_ptr = static_cast<const char*>(static_ptr) + offset_to_derived; 291 const __class_type_info* dynamic_type = static_cast<const __class_type_info*>(vtable[-1]); 292 293 // Initialize answer to nullptr. This will be changed from the search 294 // results if a non-null answer is found. Regardless, this is what will 295 // be returned. 296 const void* dst_ptr = 0; 297 // Initialize info struct for this search. 298 __dynamic_cast_info info = {dst_type, static_ptr, static_type, src2dst_offset, 0}; 299 300 // Find out if we can use a giant short cut in the search 301 if (dynamic_type == dst_type) 302 { 303 // Using giant short cut. Add that information to info. 304 info.number_of_dst_type = 1; 305 // Do the search 306 dynamic_type->search_above_dst(&info, dynamic_ptr, dynamic_ptr, public_path); 307 // Query the search. 308 if (info.path_dst_ptr_to_static_ptr == public_path) 309 dst_ptr = dynamic_ptr; 310 } 311 else 312 { 313 // Not using giant short cut. Do the search 314 dynamic_type->search_below_dst(&info, dynamic_ptr, public_path); 315 // Query the search. 316 switch (info.number_to_static_ptr) 317 { 318 case 0: 319 if (info.number_to_dst_ptr == 1 && 320 info.path_dynamic_ptr_to_static_ptr == public_path && 321 info.path_dynamic_ptr_to_dst_ptr == public_path) 322 dst_ptr = info.dst_ptr_not_leading_to_static_ptr; 323 break; 324 case 1: 325 if (info.path_dst_ptr_to_static_ptr == public_path || 326 ( 327 info.number_to_dst_ptr == 0 && 328 info.path_dynamic_ptr_to_static_ptr == public_path && 329 info.path_dynamic_ptr_to_dst_ptr == public_path 330 ) 331 ) 332 dst_ptr = info.dst_ptr_leading_to_static_ptr; 333 break; 334 } 335 } 336 return const_cast<void*>(dst_ptr); 337} 338 339#pragma GCC visibility pop 340#pragma GCC visibility push(hidden) 341 342// Call this function when you hit a static_type which is a base (above) a dst_type. 343// Let caller know you hit a static_type. But only start recording details if 344// this is (static_ptr, static_type) -- the node we are casting from. 345// If this is (static_ptr, static_type) 346// Record the path (public or not) from the dst_type to here. There may be 347// multiple paths from the same dst_type to here, record the "most public" one. 348// Record the dst_ptr as pointing to (static_ptr, static_type). 349// If more than one (dst_ptr, dst_type) points to (static_ptr, static_type), 350// then mark this dyanmic_cast as ambiguous and stop the search. 351void 352__class_type_info::process_static_type_above_dst(__dynamic_cast_info* info, 353 const void* dst_ptr, 354 const void* current_ptr, 355 int path_below) const 356{ 357 // Record that we found a static_type 358 info->found_any_static_type = true; 359 if (current_ptr == info->static_ptr) 360 { 361 // Record that we found (static_ptr, static_type) 362 info->found_our_static_ptr = true; 363 if (info->dst_ptr_leading_to_static_ptr == 0) 364 { 365 // First time here 366 info->dst_ptr_leading_to_static_ptr = dst_ptr; 367 info->path_dst_ptr_to_static_ptr = path_below; 368 info->number_to_static_ptr = 1; 369 // If there is only one dst_type in the entire tree and the path from 370 // there to here is public then we are done! 371 if (info->number_of_dst_type == 1 && info->path_dst_ptr_to_static_ptr == public_path) 372 info->search_done = true; 373 } 374 else if (info->dst_ptr_leading_to_static_ptr == dst_ptr) 375 { 376 // We've been here before. Update path to "most public" 377 if (info->path_dst_ptr_to_static_ptr == not_public_path) 378 info->path_dst_ptr_to_static_ptr = path_below; 379 // If there is only one dst_type in the entire tree and the path from 380 // there to here is public then we are done! 381 if (info->number_of_dst_type == 1 && info->path_dst_ptr_to_static_ptr == public_path) 382 info->search_done = true; 383 } 384 else 385 { 386 // We've detected an ambiguous cast from (static_ptr, static_type) 387 // to a dst_type 388 info->number_to_static_ptr += 1; 389 info->search_done = true; 390 } 391 } 392} 393 394// Call this function when you hit a static_type which is not a base (above) a dst_type. 395// If this is (static_ptr, static_type) 396// Record the path (public or not) from (dynamic_ptr, dynamic_type) to here. There may be 397// multiple paths from (dynamic_ptr, dynamic_type) to here, record the "most public" one. 398void 399__class_type_info::process_static_type_below_dst(__dynamic_cast_info* info, 400 const void* current_ptr, 401 int path_below) const 402{ 403 if (current_ptr == info->static_ptr) 404 { 405 // Record the most public path from (dynamic_ptr, dynamic_type) to 406 // (static_ptr, static_type) 407 if (info->path_dynamic_ptr_to_static_ptr != public_path) 408 info->path_dynamic_ptr_to_static_ptr = path_below; 409 } 410} 411 412// Call this function when searching below a dst_type node. This function searches 413// for a path to (static_ptr, static_type) and for paths to one or more dst_type nodes. 414// If it finds a static_type node, there is no need to further search base classes 415// above. 416// If it finds a dst_type node it should search base classes using search_above_dst 417// to find out if this dst_type points to (static_ptr, static_type) or not. 418// Either way, the dst_type is recorded as one of two "flavors": one that does 419// or does not point to (static_ptr, static_type). 420// If this is neither a static_type nor a dst_type node, continue searching 421// base classes above. 422// All the hoopla surrounding the search code is doing nothing but looking for 423// excuses to stop the search prematurely (break out of the for-loop). That is, 424// the algorithm below is simply an optimization of this: 425// void 426// __vmi_class_type_info::search_below_dst(__dynamic_cast_info* info, 427// const void* current_ptr, 428// int path_below) const 429// { 430// typedef const __base_class_type_info* Iter; 431// if (this == info->static_type) 432// process_static_type_below_dst(info, current_ptr, path_below); 433// else if (this == info->dst_type) 434// { 435// // Record the most public access path that got us here 436// if (info->path_dynamic_ptr_to_dst_ptr != public_path) 437// info->path_dynamic_ptr_to_dst_ptr = path_below; 438// bool does_dst_type_point_to_our_static_type = false; 439// for (Iter p = __base_info, e= __base_info + __base_count; p < e; ++p) 440// { 441// p->search_above_dst(info, current_ptr, current_ptr, public_path); 442// if (info->found_our_static_ptr) 443// does_dst_type_point_to_our_static_type = true; 444// // break out early here if you can detect it doesn't matter if you do 445// } 446// if (!does_dst_type_point_to_our_static_type) 447// { 448// // We found a dst_type that doesn't point to (static_ptr, static_type) 449// // So record the address of this dst_ptr and increment the 450// // count of the number of such dst_types found in the tree. 451// info->dst_ptr_not_leading_to_static_ptr = current_ptr; 452// info->number_to_dst_ptr += 1; 453// } 454// } 455// else 456// { 457// // This is not a static_type and not a dst_type. 458// for (Iter p = __base_info, e = __base_info + __base_count; p < e; ++p) 459// { 460// p->search_below_dst(info, current_ptr, public_path); 461// // break out early here if you can detect it doesn't matter if you do 462// } 463// } 464// } 465void 466__vmi_class_type_info::search_below_dst(__dynamic_cast_info* info, 467 const void* current_ptr, 468 int path_below) const 469{ 470 typedef const __base_class_type_info* Iter; 471 if (this == info->static_type) 472 process_static_type_below_dst(info, current_ptr, path_below); 473 else if (this == info->dst_type) 474 { 475 // We've been here before if we've recorded current_ptr in one of these 476 // two places: 477 if (current_ptr == info->dst_ptr_leading_to_static_ptr || 478 current_ptr == info->dst_ptr_not_leading_to_static_ptr) 479 { 480 // We've seen this node before, and therefore have already searched 481 // its base classes above. 482 // Update path to here that is "most public". 483 if (path_below == public_path) 484 info->path_dynamic_ptr_to_dst_ptr = public_path; 485 } 486 else // We have haven't been here before 487 { 488 // Record the access path that got us here 489 // If there is more than one dst_type this path doesn't matter. 490 info->path_dynamic_ptr_to_dst_ptr = path_below; 491 // Only search above here if dst_type derives from static_type, or 492 // if it is unknown if dst_type derives from static_type. 493 if (info->is_dst_type_derived_from_static_type != no) 494 { 495 // Set up flags to record results from all base classes 496 bool is_dst_type_derived_from_static_type = false; 497 bool does_dst_type_point_to_our_static_type = false; 498 // We've found a dst_type with a potentially public path to here. 499 // We have to assume the path is public because it may become 500 // public later (if we get back to here with a public path). 501 // We can stop looking above if: 502 // 1. We've found a public path to (static_ptr, static_type). 503 // 2. We've found an ambiguous cast from (static_ptr, static_type) to a dst_type. 504 // This is detected at the (static_ptr, static_type). 505 // 3. We can prove that there is no public path to (static_ptr, static_type) 506 // above here. 507 const Iter e = __base_info + __base_count; 508 for (Iter p = __base_info; p < e; ++p) 509 { 510 // Zero out found flags 511 info->found_our_static_ptr = false; 512 info->found_any_static_type = false; 513 p->search_above_dst(info, current_ptr, current_ptr, public_path); 514 if (info->search_done) 515 break; 516 if (info->found_any_static_type) 517 { 518 is_dst_type_derived_from_static_type = true; 519 if (info->found_our_static_ptr) 520 { 521 does_dst_type_point_to_our_static_type = true; 522 // If we found what we're looking for, stop looking above. 523 if (info->path_dst_ptr_to_static_ptr == public_path) 524 break; 525 // We found a private path to (static_ptr, static_type) 526 // If there is no diamond then there is only one path 527 // to (static_ptr, static_type) and we just found it. 528 if (!(__flags & __diamond_shaped_mask)) 529 break; 530 } 531 else 532 { 533 // If we found a static_type that isn't the one we're looking 534 // for, and if there are no repeated types above here, 535 // then stop looking. 536 if (!(__flags & __non_diamond_repeat_mask)) 537 break; 538 } 539 } 540 } 541 if (!does_dst_type_point_to_our_static_type) 542 { 543 // We found a dst_type that doesn't point to (static_ptr, static_type) 544 // So record the address of this dst_ptr and increment the 545 // count of the number of such dst_types found in the tree. 546 info->dst_ptr_not_leading_to_static_ptr = current_ptr; 547 info->number_to_dst_ptr += 1; 548 // If there exists another dst with a private path to 549 // (static_ptr, static_type), then the cast from 550 // (dynamic_ptr, dynamic_type) to dst_type is now ambiguous, 551 // so stop search. 552 if (info->number_to_static_ptr == 1 && 553 info->path_dst_ptr_to_static_ptr == not_public_path) 554 info->search_done = true; 555 } 556 // If we found no static_type,s then dst_type doesn't derive 557 // from static_type, else it does. Record this result so that 558 // next time we hit a dst_type we will know not to search above 559 // it if it doesn't derive from static_type. 560 if (is_dst_type_derived_from_static_type) 561 info->is_dst_type_derived_from_static_type = yes; 562 else 563 info->is_dst_type_derived_from_static_type = no; 564 } 565 } 566 } 567 else 568 { 569 // This is not a static_type and not a dst_type. 570 const Iter e = __base_info + __base_count; 571 Iter p = __base_info; 572 p->search_below_dst(info, current_ptr, path_below); 573 if (++p < e) 574 { 575 if ((__flags & __diamond_shaped_mask) || info->number_to_static_ptr == 1) 576 { 577 // If there are multiple paths to a base above from here, or if 578 // a dst_type pointing to (static_ptr, static_type) has been found, 579 // then there is no way to break out of this loop early unless 580 // something below detects the search is done. 581 do 582 { 583 if (info->search_done) 584 break; 585 p->search_below_dst(info, current_ptr, path_below); 586 } while (++p < e); 587 } 588 else if (__flags & __non_diamond_repeat_mask) 589 { 590 // There are not multiple paths to any base class from here and a 591 // dst_type pointing to (static_ptr, static_type) has not yet been 592 // found. 593 do 594 { 595 if (info->search_done) 596 break; 597 // If we just found a dst_type with a public path to (static_ptr, static_type), 598 // then the only reason to continue the search is to make sure 599 // no other dst_type points to (static_ptr, static_type). 600 // If !diamond, then we don't need to search here. 601 if (info->number_to_static_ptr == 1 && 602 info->path_dst_ptr_to_static_ptr == public_path) 603 break; 604 p->search_below_dst(info, current_ptr, path_below); 605 } while (++p < e); 606 } 607 else 608 { 609 // There are no repeated types above this node. 610 // There are no nodes with multiple parents above this node. 611 // no dst_type has been found to (static_ptr, static_type) 612 do 613 { 614 if (info->search_done) 615 break; 616 // If we just found a dst_type with a public path to (static_ptr, static_type), 617 // then the only reason to continue the search is to make sure sure 618 // no other dst_type points to (static_ptr, static_type). 619 // If !diamond, then we don't need to search here. 620 // if we just found a dst_type with a private path to (static_ptr, static_type), 621 // then we're only looking for a public path to (static_ptr, static_type) 622 // and to check for other dst_types. 623 // If !diamond & !repeat, then there is not a pointer to (static_ptr, static_type) 624 // and not a dst_type under here. 625 if (info->number_to_static_ptr == 1) 626 break; 627 p->search_below_dst(info, current_ptr, path_below); 628 } while (++p < e); 629 } 630 } 631 } 632} 633 634// This is the same algorithm as __vmi_class_type_info::search_below_dst but 635// simplified to the case that there is only a single base class. 636void 637__si_class_type_info::search_below_dst(__dynamic_cast_info* info, 638 const void* current_ptr, 639 int path_below) const 640{ 641 if (this == info->static_type) 642 process_static_type_below_dst(info, current_ptr, path_below); 643 else if (this == info->dst_type) 644 { 645 // We've been here before if we've recorded current_ptr in one of these 646 // two places: 647 if (current_ptr == info->dst_ptr_leading_to_static_ptr || 648 current_ptr == info->dst_ptr_not_leading_to_static_ptr) 649 { 650 // We've seen this node before, and therefore have already searched 651 // its base classes above. 652 // Update path to here that is "most public". 653 if (path_below == public_path) 654 info->path_dynamic_ptr_to_dst_ptr = public_path; 655 } 656 else // We have haven't been here before 657 { 658 // Record the access path that got us here 659 // If there is more than one dst_type this path doesn't matter. 660 info->path_dynamic_ptr_to_dst_ptr = path_below; 661 // Only search above here if dst_type derives from static_type, or 662 // if it is unknown if dst_type derives from static_type. 663 if (info->is_dst_type_derived_from_static_type != no) 664 { 665 // Set up flags to record results from all base classes 666 bool is_dst_type_derived_from_static_type = false; 667 bool does_dst_type_point_to_our_static_type = false; 668 // Zero out found flags 669 info->found_our_static_ptr = false; 670 info->found_any_static_type = false; 671 __base_type->search_above_dst(info, current_ptr, current_ptr, public_path); 672 if (info->found_any_static_type) 673 { 674 is_dst_type_derived_from_static_type = true; 675 if (info->found_our_static_ptr) 676 does_dst_type_point_to_our_static_type = true; 677 } 678 if (!does_dst_type_point_to_our_static_type) 679 { 680 // We found a dst_type that doesn't point to (static_ptr, static_type) 681 // So record the address of this dst_ptr and increment the 682 // count of the number of such dst_types found in the tree. 683 info->dst_ptr_not_leading_to_static_ptr = current_ptr; 684 info->number_to_dst_ptr += 1; 685 // If there exists another dst with a private path to 686 // (static_ptr, static_type), then the cast from 687 // (dynamic_ptr, dynamic_type) to dst_type is now ambiguous. 688 if (info->number_to_static_ptr == 1 && 689 info->path_dst_ptr_to_static_ptr == not_public_path) 690 info->search_done = true; 691 } 692 // If we found no static_type,s then dst_type doesn't derive 693 // from static_type, else it does. Record this result so that 694 // next time we hit a dst_type we will know not to search above 695 // it if it doesn't derive from static_type. 696 if (is_dst_type_derived_from_static_type) 697 info->is_dst_type_derived_from_static_type = yes; 698 else 699 info->is_dst_type_derived_from_static_type = no; 700 } 701 } 702 } 703 else 704 { 705 // This is not a static_type and not a dst_type 706 __base_type->search_below_dst(info, current_ptr, path_below); 707 } 708} 709 710// This is the same algorithm as __vmi_class_type_info::search_below_dst but 711// simplified to the case that there is no base class. 712void 713__class_type_info::search_below_dst(__dynamic_cast_info* info, 714 const void* current_ptr, 715 int path_below) const 716{ 717 typedef const __base_class_type_info* Iter; 718 if (this == info->static_type) 719 process_static_type_below_dst(info, current_ptr, path_below); 720 else if (this == info->dst_type) 721 { 722 // We've been here before if we've recorded current_ptr in one of these 723 // two places: 724 if (current_ptr == info->dst_ptr_leading_to_static_ptr || 725 current_ptr == info->dst_ptr_not_leading_to_static_ptr) 726 { 727 // We've seen this node before, and therefore have already searched 728 // its base classes above. 729 // Update path to here that is "most public". 730 if (path_below == public_path) 731 info->path_dynamic_ptr_to_dst_ptr = public_path; 732 } 733 else // We have haven't been here before 734 { 735 // Record the access path that got us here 736 // If there is more than one dst_type this path doesn't matter. 737 info->path_dynamic_ptr_to_dst_ptr = path_below; 738 // We found a dst_type that doesn't point to (static_ptr, static_type) 739 // So record the address of this dst_ptr and increment the 740 // count of the number of such dst_types found in the tree. 741 info->dst_ptr_not_leading_to_static_ptr = current_ptr; 742 info->number_to_dst_ptr += 1; 743 // If there exists another dst with a private path to 744 // (static_ptr, static_type), then the cast from 745 // (dynamic_ptr, dynamic_type) to dst_type is now ambiguous. 746 if (info->number_to_static_ptr == 1 && 747 info->path_dst_ptr_to_static_ptr == not_public_path) 748 info->search_done = true; 749 // We found that dst_type does not derive from static_type 750 info->is_dst_type_derived_from_static_type = no; 751 } 752 } 753} 754 755// Call this function when searching above a dst_type node. This function searches 756// for a public path to (static_ptr, static_type). 757// This function is guaranteed not to find a node of type dst_type. 758// Theoretically this is a very simple function which just stops if it finds a 759// static_type node: All the hoopla surrounding the search code is doing 760// nothing but looking for excuses to stop the search prematurely (break out of 761// the for-loop). That is, the algorithm below is simply an optimization of this: 762// void 763// __vmi_class_type_info::search_above_dst(__dynamic_cast_info* info, 764// const void* dst_ptr, 765// const void* current_ptr, 766// int path_below) const 767// { 768// if (this == info->static_type) 769// process_static_type_above_dst(info, dst_ptr, current_ptr, path_below); 770// else 771// { 772// typedef const __base_class_type_info* Iter; 773// // This is not a static_type and not a dst_type 774// for (Iter p = __base_info, e = __base_info + __base_count; p < e; ++p) 775// { 776// p->search_above_dst(info, dst_ptr, current_ptr, public_path); 777// // break out early here if you can detect it doesn't matter if you do 778// } 779// } 780// } 781void 782__vmi_class_type_info::search_above_dst(__dynamic_cast_info* info, 783 const void* dst_ptr, 784 const void* current_ptr, 785 int path_below) const 786{ 787 if (this == info->static_type) 788 process_static_type_above_dst(info, dst_ptr, current_ptr, path_below); 789 else 790 { 791 typedef const __base_class_type_info* Iter; 792 // This is not a static_type and not a dst_type 793 // Save flags so they can be restored when returning to nodes below. 794 bool found_our_static_ptr = info->found_our_static_ptr; 795 bool found_any_static_type = info->found_any_static_type; 796 // We've found a dst_type below with a path to here. If the path 797 // to here is not public, there may be another path to here that 798 // is public. So we have to assume that the path to here is public. 799 // We can stop looking above if: 800 // 1. We've found a public path to (static_ptr, static_type). 801 // 2. We've found an ambiguous cast from (static_ptr, static_type) to a dst_type. 802 // This is detected at the (static_ptr, static_type). 803 // 3. We can prove that there is no public path to (static_ptr, static_type) 804 // above here. 805 const Iter e = __base_info + __base_count; 806 Iter p = __base_info; 807 // Zero out found flags 808 info->found_our_static_ptr = false; 809 info->found_any_static_type = false; 810 p->search_above_dst(info, dst_ptr, current_ptr, path_below); 811 if (++p < e) 812 { 813 do 814 { 815 if (info->search_done) 816 break; 817 if (info->found_our_static_ptr) 818 { 819 // If we found what we're looking for, stop looking above. 820 if (info->path_dst_ptr_to_static_ptr == public_path) 821 break; 822 // We found a private path to (static_ptr, static_type) 823 // If there is no diamond then there is only one path 824 // to (static_ptr, static_type) from here and we just found it. 825 if (!(__flags & __diamond_shaped_mask)) 826 break; 827 } 828 else if (info->found_any_static_type) 829 { 830 // If we found a static_type that isn't the one we're looking 831 // for, and if there are no repeated types above here, 832 // then stop looking. 833 if (!(__flags & __non_diamond_repeat_mask)) 834 break; 835 } 836 // Zero out found flags 837 info->found_our_static_ptr = false; 838 info->found_any_static_type = false; 839 p->search_above_dst(info, dst_ptr, current_ptr, path_below); 840 } while (++p < e); 841 } 842 // Restore flags 843 info->found_our_static_ptr = found_our_static_ptr; 844 info->found_any_static_type = found_any_static_type; 845 } 846} 847 848// This is the same algorithm as __vmi_class_type_info::search_above_dst but 849// simplified to the case that there is only a single base class. 850void 851__si_class_type_info::search_above_dst(__dynamic_cast_info* info, 852 const void* dst_ptr, 853 const void* current_ptr, 854 int path_below) const 855{ 856 if (this == info->static_type) 857 process_static_type_above_dst(info, dst_ptr, current_ptr, path_below); 858 else 859 __base_type->search_above_dst(info, dst_ptr, current_ptr, path_below); 860} 861 862// This is the same algorithm as __vmi_class_type_info::search_above_dst but 863// simplified to the case that there is no base class. 864void 865__class_type_info::search_above_dst(__dynamic_cast_info* info, 866 const void* dst_ptr, 867 const void* current_ptr, 868 int path_below) const 869{ 870 if (this == info->static_type) 871 process_static_type_above_dst(info, dst_ptr, current_ptr, path_below); 872} 873 874// The search functions for __base_class_type_info are simply convenience 875// functions for adjusting the current_ptr and path_below as the search is 876// passed up to the base class node. 877 878void 879__base_class_type_info::search_above_dst(__dynamic_cast_info* info, 880 const void* dst_ptr, 881 const void* current_ptr, 882 int path_below) const 883{ 884 ptrdiff_t offset_to_base = __offset_flags >> __offset_shift; 885 if (__offset_flags & __virtual_mask) 886 { 887 const char* vtable = *static_cast<const char*const*>(current_ptr); 888 offset_to_base = *reinterpret_cast<const ptrdiff_t*>(vtable + offset_to_base); 889 } 890 __base_type->search_above_dst(info, dst_ptr, 891 static_cast<const char*>(current_ptr) + offset_to_base, 892 (__offset_flags & __public_mask) ? 893 path_below : 894 not_public_path); 895} 896 897void 898__base_class_type_info::search_below_dst(__dynamic_cast_info* info, 899 const void* current_ptr, 900 int path_below) const 901{ 902 ptrdiff_t offset_to_base = __offset_flags >> __offset_shift; 903 if (__offset_flags & __virtual_mask) 904 { 905 const char* vtable = *static_cast<const char*const*>(current_ptr); 906 offset_to_base = *reinterpret_cast<const ptrdiff_t*>(vtable + offset_to_base); 907 } 908 __base_type->search_below_dst(info, 909 static_cast<const char*>(current_ptr) + offset_to_base, 910 (__offset_flags & __public_mask) ? 911 path_below : 912 not_public_path); 913} 914 915#pragma GCC visibility pop 916 917} // __cxxabiv1 918