src/third_party/libc++abi/trunk/src/private_typeinfo.cpp

   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