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