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