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