libstdc++-v3/libsupc++/tinfo.cc

   1 // Methods for type_info for -*- C++ -*- Run Time Type Identification.
   2 // Copyright (C) 1994, 1996, 1998, 1999, 2000 Free Software Foundation
   3
   4 // This file is part of GNU CC.
   5
   6 // GNU CC is free software; you can redistribute it and/or modify
   7 // it under the terms of the GNU General Public License as published by
   8 // the Free Software Foundation; either version 2, or (at your option)
   9 // any later version.
  10
  11 // GNU CC is distributed in the hope that it will be useful,
  12 // but WITHOUT ANY WARRANTY; without even the implied warranty of
  13 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  14 // GNU General Public License for more details.
  15
  16 // You should have received a copy of the GNU General Public License
  17 // along with GNU CC; see the file COPYING.  If not, write to
  18 // the Free Software Foundation, 59 Temple Place - Suite 330,
  19 // Boston, MA 02111-1307, USA.
  20
  21 // As a special exception, you may use this file as part of a free software
  22 // library without restriction.  Specifically, if other files instantiate
  23 // templates or use macros or inline functions from this file, or you compile
  24 // this file and link it with other files to produce an executable, this
  25 // file does not by itself cause the resulting executable to be covered by
  26 // the GNU General Public License.  This exception does not however
  27 // invalidate any other reasons why the executable file might be covered by
  28 // the GNU General Public License.
  29
  30 #pragma implementation "typeinfo"
  31
  32 #include <stddef.h>
  33 #include "tinfo.h"
  34 #include "new"                  // for placement new
  35
  36 // This file contains the minimal working set necessary to link with code
  37 // that uses virtual functions and -frtti but does not actually use RTTI
  38 // functionality.
  39
  40 std::type_info::
  41 ~type_info ()
  42 { }
  43
  44 #if !defined(__GXX_ABI_VERSION) || __GXX_ABI_VERSION < 100
  45 // original (old) abi
  46
  47 namespace
  48 {
  49 // ADDR is a pointer to an object.  Convert it to a pointer to a base,
  50 // using OFFSET.
  51 inline void*
  52 convert_to_base (void *addr, bool is_virtual, myint32 offset)
  53 {
  54   if (!addr)
  55     return NULL;
  56
  57   if (!is_virtual)
  58     return (char *) addr + offset;
  59
  60   // Under the old ABI, the offset gives us the address of a pointer
  61   // to the virtual base.
  62   return *((void **) ((char *) addr + offset));
  63 }
  64
  65 }
  66
  67 // We can't rely on common symbols being shared between shared objects.
  68 bool std::type_info::
  69 operator== (const std::type_info& arg) const
  70 {
  71   return (&arg == this) || (__builtin_strcmp (name (), arg.name ()) == 0);
  72 }
  73
  74 extern "C" void
  75 __rtti_class (void *addr, const char *name,
  76               const __class_type_info::base_info *bl, size_t bn)
  77 { new (addr) __class_type_info (name, bl, bn); }
  78
  79 extern "C" void
  80 __rtti_si (void *addr, const char *n, const std::type_info *ti)
  81 {
  82   new (addr) __si_type_info
  83     (n, static_cast <const __user_type_info &> (*ti));
  84 }
  85
  86 extern "C" void
  87 __rtti_user (void *addr, const char *name)
  88 { new (addr) __user_type_info (name); }
  89
  90 // Upcast for catch checking. OBJPTR points to the thrown object and might be
  91 // NULL. Return 0 on failure, non-zero on success. Set *ADJPTR to adjusted
  92 // object pointer.
  93 int __user_type_info::
  94 upcast (const type_info &target, void *objptr,
  95         void **adjptr) const
  96 {
  97   upcast_result result;
  98
  99   if (do_upcast (contained_public, target, objptr, result))
 100     return 0;
 101   *adjptr = result.target_obj;
 102   return contained_public_p (result.whole2target);
 103 }
 104
 105 // Down or cross cast for dynamic_cast. OBJPTR points to the most derrived
 106 // object, SUBPTR points to the static base object. Both must not be NULL.
 107 // TARGET specifies the desired target type, SUBTYPE specifies the static
 108 // type. Both must be defined. Returns adjusted object pointer on success,
 109 // NULL on failure. [expr.dynamic.cast]/8 says 'unambiguous public base'. This
 110 // itself is an ambiguous statement. We choose it to mean the base must be
 111 // separately unambiguous and public, rather than unambiguous considering only
 112 // public bases.
 113 void *__user_type_info::
 114 dyncast (int boff,
 115          const type_info &target, void *objptr,
 116          const type_info &subtype, void *subptr) const
 117 {
 118   dyncast_result result;
 119
 120   do_dyncast (boff, contained_public,
 121               target, objptr, subtype, subptr, result);
 122   if (!result.target_obj)
 123     return NULL;
 124   if (contained_public_p (result.target2sub))
 125     return result.target_obj;
 126   if (contained_public_p (sub_kind (result.whole2sub & result.whole2target)))
 127     // Found a valid cross cast
 128     return result.target_obj;
 129   if (contained_nonvirtual_p (result.whole2sub))
 130     // Found an invalid cross cast, which cannot also be a down cast
 131     return NULL;
 132   if (result.target2sub == unknown)
 133     result.target2sub = static_cast <const __user_type_info &> (target)
 134                         .find_public_subobj (boff, subtype,
 135                                              result.target_obj, subptr);
 136   if (contained_public_p (result.target2sub))
 137     // Found a valid down cast
 138     return result.target_obj;
 139   // Must be an invalid down cast, or the cross cast wasn't bettered
 140   return NULL;
 141 }
 142
 143 // Catch cast helper. ACCESS_PATH is the access from the complete thrown
 144 // object to this base. TARGET is the desired type we want to catch. OBJPTR
 145 // points to this base within the throw object, it might be NULL. Fill in
 146 // RESULT with what we find. Return true, should we determine catch must fail.
 147 bool __user_type_info::
 148 do_upcast (sub_kind access_path,
 149            const type_info &target, void *objptr,
 150            upcast_result &__restrict result) const
 151 {
 152   if (*this == target)
 153     {
 154       result.target_obj = objptr;
 155       result.base_type = nonvirtual_base_type;
 156       result.whole2target = access_path;
 157       return contained_nonpublic_p (access_path);
 158     }
 159   return false;
 160 }
 161
 162 // dynamic cast helper. ACCESS_PATH gives the access from the most derived
 163 // object to this base. TARGET indicates the desired type we want. OBJPTR
 164 // points to this base within the object. SUBTYPE indicates the static type
 165 // started from and SUBPTR points to that base within the most derived object.
 166 // Fill in RESULT with what we find. Return true if we have located an
 167 // ambiguous match.
 168 bool __user_type_info::
 169 do_dyncast (int, sub_kind access_path,
 170             const type_info &target, void *objptr,
 171             const type_info &subtype, void *subptr,
 172             dyncast_result &__restrict result) const
 173 {
 174   if (objptr == subptr && *this == subtype)
 175     {
 176       // The subobject we started from. Indicate how we are accessible from
 177       // the most derived object.
 178       result.whole2sub = access_path;
 179       return false;
 180     }
 181   if (*this == target)
 182     {
 183       result.target_obj = objptr;
 184       result.whole2target = access_path;
 185       result.target2sub = not_contained;
 186       return false;
 187     }
 188   return false;
 189 }
 190
 191 // find_public_subobj helper. Return contained_public if we are the desired
 192 // subtype. OBJPTR points to this base type, SUBPTR points to the desired base
 193 // object.
 194 __user_type_info::sub_kind __user_type_info::
 195 do_find_public_subobj (int, const type_info &, void *objptr, void *subptr) const
 196 {
 197   if (subptr == objptr)
 198     // Must be our type, as the pointers match.
 199     return contained_public;
 200   return not_contained;
 201 }
 202
 203 // catch helper for single public inheritance types. See
 204 // __user_type_info::do_upcast for semantics.
 205 bool __si_type_info::
 206 do_upcast (sub_kind access_path,
 207            const type_info &target, void *objptr,
 208            upcast_result &__restrict result) const
 209 {
 210   if (*this == target)
 211     {
 212       result.target_obj = objptr;
 213       result.base_type = nonvirtual_base_type;
 214       result.whole2target = access_path;
 215       return contained_nonpublic_p (access_path);
 216     }
 217   return base.do_upcast (access_path, target, objptr, result);
 218 }
 219
 220 // dynamic cast helper for single public inheritance types. See
 221 // __user_type_info::do_dyncast for semantics. BOFF indicates how SUBTYPE
 222 // types are inherited by TARGET types.
 223 bool __si_type_info::
 224 do_dyncast (int boff, sub_kind access_path,
 225             const type_info &target, void *objptr,
 226             const type_info &subtype, void *subptr,
 227             dyncast_result &__restrict result) const
 228 {
 229   if (objptr == subptr && *this == subtype)
 230     {
 231       // The subobject we started from. Indicate how we are accessible from
 232       // the most derived object.
 233       result.whole2sub = access_path;
 234       return false;
 235     }
 236   if (*this == target)
 237     {
 238       result.target_obj = objptr;
 239       result.whole2target = access_path;
 240       if (boff >= 0)
 241         result.target2sub = ((char *)subptr - (char *)objptr) == boff
 242               ? contained_public : not_contained;
 243       else if (boff == -2)
 244         result.target2sub = not_contained;
 245       return false;
 246     }
 247   return base.do_dyncast (boff, access_path,
 248                           target, objptr, subtype, subptr, result);
 249 }
 250
 251 // find_public_subobj helper. See __user_type_info::do_find_public_subobj or
 252 // semantics. BOFF indicates how SUBTYPE types are inherited by the original
 253 // target object.
 254 __user_type_info::sub_kind __si_type_info::
 255 do_find_public_subobj (int boff, const type_info &subtype, void *objptr, void *subptr) const
 256 {
 257   if (subptr == objptr && subtype == *this)
 258     return contained_public;
 259   return base.do_find_public_subobj (boff, subtype, objptr, subptr);
 260 }
 261
 262 // catch helper for multiple or non-public inheritance types. See
 263 // __user_type_info::do_upcast for semantics.
 264 bool __class_type_info::
 265 do_upcast (sub_kind access_path,
 266            const type_info &target, void *objptr,
 267            upcast_result &__restrict result) const
 268 {
 269   if (*this == target)
 270     {
 271       result.target_obj = objptr;
 272       result.base_type = nonvirtual_base_type;
 273       result.whole2target = access_path;
 274       return contained_nonpublic_p (access_path);
 275     }
 276
 277   for (size_t i = n_bases; i--;)
 278     {
 279       upcast_result result2;
 280       void *p = objptr;
 281       sub_kind sub_access = access_path;
 282       p = convert_to_base (p,
 283                            base_list[i].is_virtual,
 284                            base_list[i].offset);
 285       if (base_list[i].is_virtual)
 286         sub_access = sub_kind (sub_access | contained_virtual_mask);
 287       if (base_list[i].access != PUBLIC)
 288         sub_access = sub_kind (sub_access & ~contained_public_mask);
 289       if (base_list[i].base->do_upcast (sub_access, target, p, result2)
 290           && !contained_virtual_p (result2.whole2target))
 291         return true; // must fail
 292       if (result2.base_type)
 293         {
 294           if (result2.base_type == nonvirtual_base_type
 295               && base_list[i].is_virtual)
 296             result2.base_type = base_list[i].base;
 297           if (!result.base_type)
 298             result = result2;
 299           else if (result.target_obj != result2.target_obj)
 300             {
 301               // Found an ambiguity.
 302               result.target_obj = NULL;
 303               result.whole2target = contained_ambig;
 304               return true;
 305             }
 306           else if (result.target_obj)
 307             {
 308               // Ok, found real object via a virtual path.
 309               result.whole2target
 310                   = sub_kind (result.whole2target | result2.whole2target);
 311             }
 312           else
 313             {
 314               // Dealing with a null pointer, need to check vbase
 315               // containing each of the two choices.
 316               if (result2.base_type == nonvirtual_base_type
 317                   || result.base_type == nonvirtual_base_type
 318                   || !(*result2.base_type == *result.base_type))
 319                 {
 320                   // Already ambiguous, not virtual or via different virtuals.
 321                   // Cannot match.
 322                   result.whole2target = contained_ambig;
 323                   return true;
 324                 }
 325               result.whole2target
 326                   = sub_kind (result.whole2target | result2.whole2target);
 327             }
 328         }
 329     }
 330   return false;
 331 }
 332
 333 // dynamic cast helper for non-public or multiple inheritance types. See
 334 // __user_type_info::do_dyncast for overall semantics.
 335 // This is a big hairy function. Although the run-time behaviour of
 336 // dynamic_cast is simple to describe, it gives rise to some non-obvious
 337 // behaviour. We also desire to determine as early as possible any definite
 338 // answer we can get. Because it is unknown what the run-time ratio of
 339 // succeeding to failing dynamic casts is, we do not know in which direction
 340 // to bias any optimizations. To that end we make no particular effort towards
 341 // early fail answers or early success answers. Instead we try to minimize
 342 // work by filling in things lazily (when we know we need the information),
 343 // and opportunisticly take early success or failure results.
 344 bool __class_type_info::
 345 do_dyncast (int boff, sub_kind access_path,
 346             const type_info &target, void *objptr,
 347             const type_info &subtype, void *subptr,
 348             dyncast_result &__restrict result) const
 349 {
 350   if (objptr == subptr && *this == subtype)
 351     {
 352       // The subobject we started from. Indicate how we are accessible from
 353       // the most derived object.
 354       result.whole2sub = access_path;
 355       return false;
 356     }
 357   if (*this == target)
 358     {
 359       result.target_obj = objptr;
 360       result.whole2target = access_path;
 361       if (boff >= 0)
 362         result.target2sub = ((char *)subptr - (char *)objptr) == boff
 363               ? contained_public : not_contained;
 364       else if (boff == -2)
 365         result.target2sub = not_contained;
 366       return false;
 367     }
 368   bool result_ambig = false;
 369   for (size_t i = n_bases; i--;)
 370     {
 371       dyncast_result result2;
 372       void *p;
 373       sub_kind sub_access = access_path;
 374       p = convert_to_base (objptr,
 375                            base_list[i].is_virtual,
 376                            base_list[i].offset);
 377       if (base_list[i].is_virtual)
 378         sub_access = sub_kind (sub_access | contained_virtual_mask);
 379       if (base_list[i].access != PUBLIC)
 380         sub_access = sub_kind (sub_access & ~contained_public_mask);
 381
 382       bool result2_ambig
 383           = base_list[i].base->do_dyncast (boff, sub_access,
 384                                            target, p, subtype, subptr, result2);
 385       result.whole2sub = sub_kind (result.whole2sub | result2.whole2sub);
 386       if (result2.target2sub == contained_public
 387           || result2.target2sub == contained_ambig)
 388         {
 389           result.target_obj = result2.target_obj;
 390           result.whole2target = result2.whole2target;
 391           result.target2sub = result2.target2sub;
 392           // Found a downcast which can't be bettered or an ambiguous downcast
 393           // which can't be disambiguated
 394           return result2_ambig;
 395         }
 396
 397       if (!result_ambig && !result.target_obj)
 398         {
 399           // Not found anything yet.
 400           result.target_obj = result2.target_obj;
 401           result.whole2target = result2.whole2target;
 402           result_ambig = result2_ambig;
 403         }
 404       else if (result.target_obj && result.target_obj == result2.target_obj)
 405         {
 406           // Found at same address, must be via virtual.  Pick the most
 407           // accessible path.
 408           result.whole2target =
 409               sub_kind (result.whole2target | result2.whole2target);
 410         }
 411       else if ((result.target_obj && result2.target_obj)
 412                || (result_ambig && result2.target_obj)
 413                || (result2_ambig && result.target_obj))
 414         {
 415           // Found two different TARGET bases, or a valid one and a set of
 416           // ambiguous ones, must disambiguate. See whether SUBOBJ is
 417           // contained publicly within one of the non-ambiguous choices.
 418           // If it is in only one, then that's the choice. If it is in
 419           // both, then we're ambiguous and fail. If it is in neither,
 420           // we're ambiguous, but don't yet fail as we might later find a
 421           // third base which does contain SUBPTR.
 422
 423           sub_kind new_sub_kind = result2.target2sub;
 424           sub_kind old_sub_kind = result.target2sub;
 425
 426           if (contained_nonvirtual_p (result.whole2sub))
 427             {
 428               // We already found SUBOBJ as a non-virtual base of most
 429               // derived. Therefore if it is in either choice, it can only be
 430               // in one of them, and we will already know.
 431               if (old_sub_kind == unknown)
 432                 old_sub_kind = not_contained;
 433               if (new_sub_kind == unknown)
 434                 new_sub_kind = not_contained;
 435             }
 436           else
 437             {
 438               const __user_type_info &t =
 439                   static_cast <const __user_type_info &> (target);
 440
 441               if (old_sub_kind >= not_contained)
 442                 ;// already calculated
 443               else if (contained_nonvirtual_p (new_sub_kind))
 444                 // Already found non-virtually inside the other choice,
 445                 // cannot be in this.
 446                 old_sub_kind = not_contained;
 447               else
 448                 old_sub_kind = t.find_public_subobj (boff, subtype,
 449                                                      result.target_obj, subptr);
 450
 451               if (new_sub_kind >= not_contained)
 452                 ;// already calculated
 453               else if (contained_nonvirtual_p (old_sub_kind))
 454                 // Already found non-virtually inside the other choice,
 455                 // cannot be in this.
 456                 new_sub_kind = not_contained;
 457               else
 458                 new_sub_kind = t.find_public_subobj (boff, subtype,
 459                                                      result2.target_obj, subptr);
 460             }
 461
 462           // Neither sub_kind can be contained_ambig -- we bail out early
 463           // when we find those.
 464           if (contained_p (sub_kind (new_sub_kind ^ old_sub_kind)))
 465             {
 466               // Only on one choice, not ambiguous.
 467               if (contained_p (new_sub_kind))
 468                 {
 469                   // Only in new.
 470                   result.target_obj = result2.target_obj;
 471                   result.whole2target = result2.whole2target;
 472                   result_ambig = false;
 473                   old_sub_kind = new_sub_kind;
 474                 }
 475               result.target2sub = old_sub_kind;
 476               if (result.target2sub == contained_public)
 477                 return false; // Can't be an ambiguating downcast for later discovery.
 478             }
 479           else if (contained_p (sub_kind (new_sub_kind & old_sub_kind)))
 480             {
 481               // In both.
 482               result.target_obj = NULL;
 483               result.target2sub = contained_ambig;
 484               return true;  // Fail.
 485             }
 486           else
 487             {
 488               // In neither publicly, ambiguous for the moment, but keep
 489               // looking. It is possible that it was private in one or
 490               // both and therefore we should fail, but that's just tough.
 491               result.target_obj = NULL;
 492               result.target2sub = not_contained;
 493               result_ambig = true;
 494             }
 495         }
 496
 497       if (result.whole2sub == contained_private)
 498         // We found SUBOBJ as a private non-virtual base, therefore all
 499         // cross casts will fail. We have already found a down cast, if
 500         // there is one.
 501         return result_ambig;
 502     }
 503
 504   return result_ambig;
 505 }
 506
 507 // find_public_subobj helper for non-public or multiple inheritance types. See
 508 // __user_type_info::do_find_public_subobj for semantics. We make use of BOFF
 509 // to prune the base class walk.
 510 __user_type_info::sub_kind __class_type_info::
 511 do_find_public_subobj (int boff, const type_info &subtype, void *objptr, void *subptr) const
 512 {
 513   if (objptr == subptr && subtype == *this)
 514     return contained_public;
 515
 516   for (size_t i = n_bases; i--;)
 517     {
 518       if (base_list[i].access != PUBLIC)
 519         continue; // Not public, can't be here.
 520       void *p;
 521
 522       if (base_list[i].is_virtual && boff == -3)
 523         // Not a virtual base, so can't be here.
 524         continue;
 525
 526       p = convert_to_base (objptr,
 527                            base_list[i].is_virtual,
 528                            base_list[i].offset);
 529
 530       sub_kind base_kind = base_list[i].base->do_find_public_subobj
 531                               (boff, subtype, p, subptr);
 532       if (contained_p (base_kind))
 533         {
 534           if (base_list[i].is_virtual)
 535             base_kind = sub_kind (base_kind | contained_virtual_mask);
 536           return base_kind;
 537         }
 538     }
 539
 540   return not_contained;
 541 }
 542 #else
 543 // new abi
 544
 545 namespace std {
 546
 547 // return true if this is a type_info for a pointer type
 548 bool type_info::
 549 __is_pointer_p () const
 550 {
 551   return false;
 552 }
 553
 554 // return true if this is a type_info for a function type
 555 bool type_info::
 556 __is_function_p () const
 557 {
 558   return false;
 559 }
 560
 561 // try and catch a thrown object.
 562 bool type_info::
 563 __do_catch (const type_info *thr_type, void **, unsigned) const
 564 {
 565   return *this == *thr_type;
 566 }
 567
 568 // upcast from this type to the target. __class_type_info will override
 569 bool type_info::
 570 __do_upcast (const abi::__class_type_info *, void **) const
 571 {
 572   return false;
 573 }
 574
 575 };
 576
 577 namespace {
 578
 579 using namespace std;
 580 using namespace abi;
 581
 582 // initial part of a vtable, this structure is used with offsetof, so we don't
 583 // have to keep alignments consistent manually.
 584 struct vtable_prefix {
 585   ptrdiff_t whole_object;           // offset to most derived object
 586   const __class_type_info *whole_type;  // pointer to most derived type_info
 587   const void *origin;               // what a class's vptr points to
 588 };
 589
 590 template <typename T>
 591 inline const T *
 592 adjust_pointer (const void *base, ptrdiff_t offset)
 593 {
 594   return reinterpret_cast <const T *>
 595     (reinterpret_cast <const char *> (base) + offset);
 596 }
 597
 598 // ADDR is a pointer to an object.  Convert it to a pointer to a base,
 599 // using OFFSET. IS_VIRTUAL is true, if we are getting a virtual base.
 600 inline void const *
 601 convert_to_base (void const *addr, bool is_virtual, ptrdiff_t offset)
 602 {
 603   if (is_virtual)
 604     {
 605       const void *vtable = *static_cast <const void *const *> (addr);
 606
 607       offset = *adjust_pointer<ptrdiff_t> (vtable, offset);
 608     }
 609
 610   return adjust_pointer<void> (addr, offset);
 611 }
 612
 613 // some predicate functions for __class_type_info::__sub_kind
 614 inline bool contained_p (__class_type_info::__sub_kind access_path)
 615 {
 616   return access_path >= __class_type_info::__contained_mask;
 617 }
 618 inline bool public_p (__class_type_info::__sub_kind access_path)
 619 {
 620   return access_path & __class_type_info::__contained_public_mask;
 621 }
 622 inline bool virtual_p (__class_type_info::__sub_kind access_path)
 623 {
 624   return (access_path & __class_type_info::__contained_virtual_mask);
 625 }
 626 inline bool contained_public_p (__class_type_info::__sub_kind access_path)
 627 {
 628   return ((access_path & __class_type_info::__contained_public)
 629           == __class_type_info::__contained_public);
 630 }
 631 inline bool contained_nonpublic_p (__class_type_info::__sub_kind access_path)
 632 {
 633   return ((access_path & __class_type_info::__contained_public)
 634           == __class_type_info::__contained_mask);
 635 }
 636 inline bool contained_nonvirtual_p (__class_type_info::__sub_kind access_path)
 637 {
 638   return ((access_path & (__class_type_info::__contained_mask
 639                           | __class_type_info::__contained_virtual_mask))
 640           == __class_type_info::__contained_mask);
 641 }
 642
 643 static const __class_type_info *const nonvirtual_base_type =
 644     static_cast <const __class_type_info *> (0) + 1;
 645
 646 }; // namespace
 647
 648 namespace __cxxabiv1
 649 {
 650
 651 __class_type_info::
 652 ~__class_type_info ()
 653 {}
 654
 655 __si_class_type_info::
 656 ~__si_class_type_info ()
 657 {}
 658
 659 __vmi_class_type_info::
 660 ~__vmi_class_type_info ()
 661 {}
 662
 663 // __upcast_result is used to hold information during traversal of a class
 664 // heirarchy when catch matching.
 665 struct __class_type_info::__upcast_result
 666 {
 667   const void *dst_ptr;        // pointer to caught object
 668   __sub_kind part2dst;        // path from current base to target
 669   int src_details;            // hints about the source type heirarchy
 670   const __class_type_info *base_type; // where we found the target,
 671                               // if in vbase the __class_type_info of vbase
 672                               // if a non-virtual base then 1
 673                               // else NULL
 674   public:
 675   __upcast_result (int d)
 676     :dst_ptr (NULL), part2dst (__unknown), src_details (d), base_type (NULL)
 677     {}
 678 };
 679
 680 // __dyncast_result is used to hold information during traversal of a class
 681 // heirarchy when dynamic casting.
 682 struct __class_type_info::__dyncast_result
 683 {
 684   const void *dst_ptr;        // pointer to target object or NULL
 685   __sub_kind whole2dst;       // path from most derived object to target
 686   __sub_kind whole2src;       // path from most derived object to sub object
 687   __sub_kind dst2src;         // path from target to sub object
 688   int whole_details;          // details of the whole class heirarchy
 689
 690   public:
 691   __dyncast_result (int details_ = __vmi_class_type_info::__flags_unknown_mask)
 692     :dst_ptr (NULL), whole2dst (__unknown),
 693      whole2src (__unknown), dst2src (__unknown),
 694      whole_details (details_)
 695     {}
 696 };
 697
 698 bool __class_type_info::
 699 __do_catch (const type_info *thr_type,
 700             void **thr_obj,
 701             unsigned outer) const
 702 {
 703   if (*this == *thr_type)
 704     return true;
 705   if (outer >= 4)
 706     // Neither `A' nor `A *'.
 707     return false;
 708   return thr_type->__do_upcast (this, thr_obj);
 709 }
 710
 711 bool __class_type_info::
 712 __do_upcast (const __class_type_info *dst_type,
 713              void **obj_ptr) const
 714 {
 715   __upcast_result result (__vmi_class_type_info::__flags_unknown_mask);
 716
 717   __do_upcast (dst_type, *obj_ptr, result);
 718   if (!contained_public_p (result.part2dst))
 719     return false;
 720   *obj_ptr = const_cast <void *> (result.dst_ptr);
 721   return true;
 722 }
 723
 724 inline __class_type_info::__sub_kind __class_type_info::
 725 __find_public_src (ptrdiff_t src2dst,
 726                    const void *obj_ptr,
 727                    const __class_type_info *src_type,
 728                    const void *src_ptr) const
 729 {
 730   if (src2dst >= 0)
 731     return adjust_pointer <void> (obj_ptr, src2dst) == src_ptr
 732             ? __contained_public : __not_contained;
 733   if (src2dst == -2)
 734     return __not_contained;
 735   return __do_find_public_src (src2dst, obj_ptr, src_type, src_ptr);
 736 }
 737
 738 __class_type_info::__sub_kind __class_type_info::
 739 __do_find_public_src (ptrdiff_t,
 740                       const void *obj_ptr,
 741                       const __class_type_info *,
 742                       const void *src_ptr) const
 743 {
 744   if (src_ptr == obj_ptr)
 745     // Must be our type, as the pointers match.
 746     return __contained_public;
 747   return __not_contained;
 748 }
 749
 750 __class_type_info::__sub_kind __si_class_type_info::
 751 __do_find_public_src (ptrdiff_t src2dst,
 752                       const void *obj_ptr,
 753                       const __class_type_info *src_type,
 754                       const void *src_ptr) const
 755 {
 756   if (src_ptr == obj_ptr && *this == *src_type)
 757     return __contained_public;
 758   return __base_type->__do_find_public_src (src2dst, obj_ptr, src_type, src_ptr);
 759 }
 760
 761 __class_type_info::__sub_kind __vmi_class_type_info::
 762 __do_find_public_src (ptrdiff_t src2dst,
 763                       const void *obj_ptr,
 764                       const __class_type_info *src_type,
 765                       const void *src_ptr) const
 766 {
 767   if (obj_ptr == src_ptr && *this == *src_type)
 768     return __contained_public;
 769
 770   for (size_t i = __base_count; i--;)
 771     {
 772       if (!__base_info[i].__is_public_p ())
 773         continue; // Not public, can't be here.
 774
 775       const void *base = obj_ptr;
 776       ptrdiff_t offset = __base_info[i].__offset ();
 777       bool is_virtual = __base_info[i].__is_virtual_p ();
 778
 779       if (is_virtual)
 780         {
 781           if (src2dst == -3)
 782             continue; // Not a virtual base, so can't be here.
 783         }
 784       base = convert_to_base (base, is_virtual, offset);
 785
 786       __sub_kind base_kind = __base_info[i].__base->__do_find_public_src
 787                               (src2dst, base, src_type, src_ptr);
 788       if (contained_p (base_kind))
 789         {
 790           if (is_virtual)
 791             base_kind = __sub_kind (base_kind | __contained_virtual_mask);
 792           return base_kind;
 793         }
 794     }
 795
 796   return __not_contained;
 797 }
 798
 799 bool __class_type_info::
 800 __do_dyncast (ptrdiff_t,
 801               __sub_kind access_path,
 802               const __class_type_info *dst_type,
 803               const void *obj_ptr,
 804               const __class_type_info *src_type,
 805               const void *src_ptr,
 806               __dyncast_result &__restrict result) const
 807 {
 808   if (obj_ptr == src_ptr && *this == *src_type)
 809     {
 810       // The src object we started from. Indicate how we are accessible from
 811       // the most derived object.
 812       result.whole2src = access_path;
 813       return false;
 814     }
 815   if (*this == *dst_type)
 816     {
 817       result.dst_ptr = obj_ptr;
 818       result.whole2dst = access_path;
 819       result.dst2src = __not_contained;
 820       return false;
 821     }
 822   return false;
 823 }
 824
 825 bool __si_class_type_info::
 826 __do_dyncast (ptrdiff_t src2dst,
 827               __sub_kind access_path,
 828               const __class_type_info *dst_type,
 829               const void *obj_ptr,
 830               const __class_type_info *src_type,
 831               const void *src_ptr,
 832               __dyncast_result &__restrict result) const
 833 {
 834   if (*this == *dst_type)
 835     {
 836       result.dst_ptr = obj_ptr;
 837       result.whole2dst = access_path;
 838       if (src2dst >= 0)
 839         result.dst2src = adjust_pointer <void> (obj_ptr, src2dst) == src_ptr
 840               ? __contained_public : __not_contained;
 841       else if (src2dst == -2)
 842         result.dst2src = __not_contained;
 843       return false;
 844     }
 845   if (obj_ptr == src_ptr && *this == *src_type)
 846     {
 847       // The src object we started from. Indicate how we are accessible from
 848       // the most derived object.
 849       result.whole2src = access_path;
 850       return false;
 851     }
 852   return __base_type->__do_dyncast (src2dst, access_path, dst_type, obj_ptr,
 853                              src_type, src_ptr, result);
 854 }
 855
 856 // This is a big hairy function. Although the run-time behaviour of
 857 // dynamic_cast is simple to describe, it gives rise to some non-obvious
 858 // behaviour. We also desire to determine as early as possible any definite
 859 // answer we can get. Because it is unknown what the run-time ratio of
 860 // succeeding to failing dynamic casts is, we do not know in which direction
 861 // to bias any optimizations. To that end we make no particular effort towards
 862 // early fail answers or early success answers. Instead we try to minimize
 863 // work by filling in things lazily (when we know we need the information),
 864 // and opportunisticly take early success or failure results.
 865 bool __vmi_class_type_info::
 866 __do_dyncast (ptrdiff_t src2dst,
 867               __sub_kind access_path,
 868               const __class_type_info *dst_type,
 869               const void *obj_ptr,
 870               const __class_type_info *src_type,
 871               const void *src_ptr,
 872               __dyncast_result &__restrict result) const
 873 {
 874   if (result.whole_details & __flags_unknown_mask)
 875     result.whole_details = __flags;
 876
 877   if (obj_ptr == src_ptr && *this == *src_type)
 878     {
 879       // The src object we started from. Indicate how we are accessible from
 880       // the most derived object.
 881       result.whole2src = access_path;
 882       return false;
 883     }
 884   if (*this == *dst_type)
 885     {
 886       result.dst_ptr = obj_ptr;
 887       result.whole2dst = access_path;
 888       if (src2dst >= 0)
 889         result.dst2src = adjust_pointer <void> (obj_ptr, src2dst) == src_ptr
 890               ? __contained_public : __not_contained;
 891       else if (src2dst == -2)
 892         result.dst2src = __not_contained;
 893       return false;
 894     }
 895
 896   bool result_ambig = false;
 897   for (size_t i = __base_count; i--;)
 898     {
 899       __dyncast_result result2 (result.whole_details);
 900       void const *base = obj_ptr;
 901       __sub_kind base_access = access_path;
 902       ptrdiff_t offset = __base_info[i].__offset ();
 903       bool is_virtual = __base_info[i].__is_virtual_p ();
 904
 905       if (is_virtual)
 906         base_access = __sub_kind (base_access | __contained_virtual_mask);
 907       base = convert_to_base (base, is_virtual, offset);
 908
 909       if (!__base_info[i].__is_public_p ())
 910         {
 911           if (src2dst == -2 &&
 912               !(result.whole_details
 913                 & (__non_diamond_repeat_mask | __diamond_shaped_mask)))
 914             // The hierarchy has no duplicate bases (which might ambiguate
 915             // things) and where we started is not a public base of what we
 916             // want (so it cannot be a downcast). There is nothing of interest
 917             // hiding in a non-public base.
 918             continue;
 919           base_access = __sub_kind (base_access & ~__contained_public_mask);
 920         }
 921
 922       bool result2_ambig
 923           = __base_info[i].__base->__do_dyncast (src2dst, base_access,
 924                                              dst_type, base,
 925                                              src_type, src_ptr, result2);
 926       result.whole2src = __sub_kind (result.whole2src | result2.whole2src);
 927       if (result2.dst2src == __contained_public
 928           || result2.dst2src == __contained_ambig)
 929         {
 930           result.dst_ptr = result2.dst_ptr;
 931           result.whole2dst = result2.whole2dst;
 932           result.dst2src = result2.dst2src;
 933           // Found a downcast which can't be bettered or an ambiguous downcast
 934           // which can't be disambiguated
 935           return result2_ambig;
 936         }
 937
 938       if (!result_ambig && !result.dst_ptr)
 939         {
 940           // Not found anything yet.
 941           result.dst_ptr = result2.dst_ptr;
 942           result.whole2dst = result2.whole2dst;
 943           result_ambig = result2_ambig;
 944           if (result.dst_ptr && result.whole2src != __unknown
 945               && !(__flags & __non_diamond_repeat_mask))
 946             // Found dst and src and we don't have repeated bases.
 947             return result_ambig;
 948         }
 949       else if (result.dst_ptr && result.dst_ptr == result2.dst_ptr)
 950         {
 951           // Found at same address, must be via virtual.  Pick the most
 952           // accessible path.
 953           result.whole2dst =
 954               __sub_kind (result.whole2dst | result2.whole2dst);
 955         }
 956       else if ((result.dst_ptr != 0 | result_ambig)
 957                && (result2.dst_ptr != 0 | result2_ambig))
 958         {
 959           // Found two different DST_TYPE bases, or a valid one and a set of
 960           // ambiguous ones, must disambiguate. See whether SRC_PTR is
 961           // contained publicly within one of the non-ambiguous choices. If it
 962           // is in only one, then that's the choice. If it is in both, then
 963           // we're ambiguous and fail. If it is in neither, we're ambiguous,
 964           // but don't yet fail as we might later find a third base which does
 965           // contain SRC_PTR.
 966
 967           __sub_kind new_sub_kind = result2.dst2src;
 968           __sub_kind old_sub_kind = result.dst2src;
 969
 970           if (contained_p (result.whole2src)
 971               && (!virtual_p (result.whole2src)
 972                   || !(result.whole_details & __diamond_shaped_mask)))
 973             {
 974               // We already found SRC_PTR as a base of most derived, and
 975               // either it was non-virtual, or the whole heirarchy is
 976               // not-diamond shaped. Therefore if it is in either choice, it
 977               // can only be in one of them, and we will already know.
 978               if (old_sub_kind == __unknown)
 979                 old_sub_kind = __not_contained;
 980               if (new_sub_kind == __unknown)
 981                 new_sub_kind = __not_contained;
 982             }
 983           else
 984             {
 985               if (old_sub_kind >= __not_contained)
 986                 ;// already calculated
 987               else if (contained_p (new_sub_kind)
 988                        && (!virtual_p (new_sub_kind)
 989                            || !(__flags & __diamond_shaped_mask)))
 990                 // Already found inside the other choice, and it was
 991                 // non-virtual or we are not diamond shaped.
 992                 old_sub_kind = __not_contained;
 993               else
 994                 old_sub_kind = dst_type->__find_public_src
 995                                 (src2dst, result.dst_ptr, src_type, src_ptr);
 996
 997               if (new_sub_kind >= __not_contained)
 998                 ;// already calculated
 999               else if (contained_p (old_sub_kind)
1000                        && (!virtual_p (old_sub_kind)
1001                            || !(__flags & __diamond_shaped_mask)))
1002                 // Already found inside the other choice, and it was
1003                 // non-virtual or we are not diamond shaped.
1004                 new_sub_kind = __not_contained;
1005               else
1006                 new_sub_kind = dst_type->__find_public_src
1007                                 (src2dst, result2.dst_ptr, src_type, src_ptr);
1008             }
1009
1010           // Neither sub_kind can be contained_ambig -- we bail out early
1011           // when we find those.
1012           if (contained_p (__sub_kind (new_sub_kind ^ old_sub_kind)))
1013             {
1014               // Only on one choice, not ambiguous.
1015               if (contained_p (new_sub_kind))
1016                 {
1017                   // Only in new.
1018                   result.dst_ptr = result2.dst_ptr;
1019                   result.whole2dst = result2.whole2dst;
1020                   result_ambig = false;
1021                   old_sub_kind = new_sub_kind;
1022                 }
1023               result.dst2src = old_sub_kind;
1024               if (public_p (result.dst2src))
1025                 return false; // Can't be an ambiguating downcast for later discovery.
1026               if (!virtual_p (result.dst2src))
1027                 return false; // Found non-virtually can't be bettered
1028             }
1029           else if (contained_p (__sub_kind (new_sub_kind & old_sub_kind)))
1030             {
1031               // In both.
1032               result.dst_ptr = NULL;
1033               result.dst2src = __contained_ambig;
1034               return true;  // Fail.
1035             }
1036           else
1037             {
1038               // In neither publicly, ambiguous for the moment, but keep
1039               // looking. It is possible that it was private in one or
1040               // both and therefore we should fail, but that's just tough.
1041               result.dst_ptr = NULL;
1042               result.dst2src = __not_contained;
1043               result_ambig = true;
1044             }
1045         }
1046
1047       if (result.whole2src == __contained_private)
1048         // We found SRC_PTR as a private non-virtual base, therefore all
1049         // cross casts will fail. We have already found a down cast, if
1050         // there is one.
1051         return result_ambig;
1052     }
1053
1054   return result_ambig;
1055 }
1056
1057 bool __class_type_info::
1058 __do_upcast (const __class_type_info *dst, const void *obj,
1059              __upcast_result &__restrict result) const
1060 {
1061   if (*this == *dst)
1062     {
1063       result.dst_ptr = obj;
1064       result.base_type = nonvirtual_base_type;
1065       result.part2dst = __contained_public;
1066       return true;
1067     }
1068   return false;
1069 }
1070
1071 bool __si_class_type_info::
1072 __do_upcast (const __class_type_info *dst, const void *obj_ptr,
1073              __upcast_result &__restrict result) const
1074 {
1075   if (__class_type_info::__do_upcast (dst, obj_ptr, result))
1076     return true;
1077
1078   return __base_type->__do_upcast (dst, obj_ptr, result);
1079 }
1080
1081 bool __vmi_class_type_info::
1082 __do_upcast (const __class_type_info *dst, const void *obj_ptr,
1083              __upcast_result &__restrict result) const
1084 {
1085   if (__class_type_info::__do_upcast (dst, obj_ptr, result))
1086     return true;
1087
1088   int src_details = result.src_details;
1089   if (src_details & __flags_unknown_mask)
1090     src_details = __flags;
1091
1092   for (size_t i = __base_count; i--;)
1093     {
1094       __upcast_result result2 (src_details);
1095       const void *base = obj_ptr;
1096       ptrdiff_t offset = __base_info[i].__offset ();
1097       bool is_virtual = __base_info[i].__is_virtual_p ();
1098       bool is_public = __base_info[i].__is_public_p ();
1099
1100       if (!is_public && !(src_details & __non_diamond_repeat_mask))
1101         // original cannot have an ambiguous base, so skip private bases
1102         continue;
1103
1104       if (base)
1105         base = convert_to_base (base, is_virtual, offset);
1106
1107       if (__base_info[i].__base->__do_upcast (dst, base, result2))
1108         {
1109           if (result2.base_type == nonvirtual_base_type && is_virtual)
1110             result2.base_type = __base_info[i].__base;
1111           if (contained_p (result2.part2dst) && !is_public)
1112             result2.part2dst = __sub_kind (result2.part2dst & ~__contained_public_mask);
1113
1114           if (!result.base_type)
1115             {
1116               result = result2;
1117               if (!contained_p (result.part2dst))
1118                 return true; // found ambiguously
1119
1120               if (result.part2dst & __contained_public_mask)
1121                 {
1122                   if (!(__flags & __non_diamond_repeat_mask))
1123                     return true;  // cannot have an ambiguous other base
1124                 }
1125               else
1126                 {
1127                   if (!virtual_p (result.part2dst))
1128                     return true; // cannot have another path
1129                   if (!(__flags & __diamond_shaped_mask))
1130                     return true; // cannot have a more accessible path
1131                 }
1132             }
1133           else if (result.dst_ptr != result2.dst_ptr)
1134             {
1135               // Found an ambiguity.
1136               result.dst_ptr = NULL;
1137               result.part2dst = __contained_ambig;
1138               return true;
1139             }
1140           else if (result.dst_ptr)
1141             {
1142               // Ok, found real object via a virtual path.
1143               result.part2dst
1144                   = __sub_kind (result.part2dst | result2.part2dst);
1145             }
1146           else
1147             {
1148               // Dealing with a null pointer, need to check vbase
1149               // containing each of the two choices.
1150               if (result2.base_type == nonvirtual_base_type
1151                   || result.base_type == nonvirtual_base_type
1152                   || !(*result2.base_type == *result.base_type))
1153                 {
1154                   // Already ambiguous, not virtual or via different virtuals.
1155                   // Cannot match.
1156                   result.part2dst = __contained_ambig;
1157                   return true;
1158                 }
1159               result.part2dst
1160                   = __sub_kind (result.part2dst | result2.part2dst);
1161             }
1162         }
1163     }
1164   return result.part2dst != __unknown;
1165 }
1166
1167 // this is the external interface to the dynamic cast machinery
1168 extern "C" void *
1169 __dynamic_cast (const void *src_ptr,    // object started from
1170                 const __class_type_info *src_type, // type of the starting object
1171                 const __class_type_info *dst_type, // desired target type
1172                 ptrdiff_t src2dst) // how src and dst are related
1173 {
1174   const void *vtable = *static_cast <const void *const *> (src_ptr);
1175   const vtable_prefix *prefix =
1176       adjust_pointer <vtable_prefix> (vtable,
1177                                       -offsetof (vtable_prefix, origin));
1178   const void *whole_ptr =
1179       adjust_pointer <void> (src_ptr, prefix->whole_object);
1180   const __class_type_info *whole_type = prefix->whole_type;
1181   __class_type_info::__dyncast_result result;
1182
1183   whole_type->__do_dyncast (src2dst, __class_type_info::__contained_public,
1184                             dst_type, whole_ptr, src_type, src_ptr, result);
1185   if (!result.dst_ptr)
1186     return NULL;
1187   if (contained_public_p (result.dst2src))
1188     // Src is known to be a public base of dst.
1189     return const_cast <void *> (result.dst_ptr);
1190   if (contained_public_p (__class_type_info::__sub_kind (result.whole2src & result.whole2dst)))
1191     // Both src and dst are known to be public bases of whole. Found a valid
1192     // cross cast.
1193     return const_cast <void *> (result.dst_ptr);
1194   if (contained_nonvirtual_p (result.whole2src))
1195     // Src is known to be a non-public nonvirtual base of whole, and not a
1196     // base of dst. Found an invalid cross cast, which cannot also be a down
1197     // cast
1198     return NULL;
1199   if (result.dst2src == __class_type_info::__unknown)
1200     result.dst2src = dst_type->__find_public_src (src2dst, result.dst_ptr,
1201                                                   src_type, src_ptr);
1202   if (contained_public_p (result.dst2src))
1203     // Found a valid down cast
1204     return const_cast <void *> (result.dst_ptr);
1205   // Must be an invalid down cast, or the cross cast wasn't bettered
1206   return NULL;
1207 }
1208
1209 }; // namespace __cxxabiv1
1210 #endif