I think this is getting close on __dynamic_cast. There's been quite a bit of code rearrangement, renaming, and better commenting. This exercise has exposed and fixed a few more bugs. I've also added several more tests (there's definitely a need for more tests here).

git-svn-id: https://llvm.org/svn/llvm-project/libcxxabi/trunk@148227 91177308-0d34-0410-b5e6-96231b3b80d8

1 files changed, 520 insertions, 537 deletions

diff --git a/src/private_typeinfo.cpp b/src/private_typeinfo.cpp
index 5400073..bac555e 100644
--- a/src/private_typeinfo.cpp
+++ b/src/private_typeinfo.cpp
@@ -9,11 +9,6 @@
 
 #include "private_typeinfo.h"
 
-#ifdef DEBUG
-// temporary headers
-#include <iostream>
-#endif
-
 namespace std
 {
 
@@ -60,646 +55,634 @@ __class_type_info::~__class_type_info()
 {
 }
 
-// __dynamic_cast notes:
-// Up or above refers to base classes and base objects.
-// Down or below refers to derived classes/objects.
-// There are two search algorithms, search1 and search2.
-// search1 is nothing but an optimization of search2 for a special case.
-// Take it away and things should still work correctly.
-// Both algorithms return 1 if the search should continue below the current node
-//    and 0 if the search should be aborted (because the answer is now known).
-
-// search1 is a search algorithm used by __dynamic_cast.
-// If a static_type is found
-//     If dynamic_ptr == static_ptr
-//         Record the path to get here.
-//         if the path to get here is public
-//             stop search
-//     Otherwise continue search only below this node
-// Else
-//     Continue search above and below this node.
-
-// search2 is a search algorithm used by __dynamic_cast.
-// if this is a dst_type
-//     if this node has already been classified then
-//        If the path to get here is public, overwrite existing path_dynamic_ptr_to_dst_ptr.
-//     else we haven't been to this (ptr, dst_type) before.
-//        Record the path to get here in path_dynamic_ptr_to_dst_ptr.
-//        For each base is (static_ptr, static_type) above this dst_type?
-//           Yes:
-//             Record it as dst_ptr_leading_to_static_ptr and increment the
-//                number of such recordings.
-//             If this is not the first of such recordings, then stop searching.
-//             Otherwise continue searching both above and below this node.
-//           No:
-//             record it as dst_ptr_not_leading_to_static_ptr and increment
-//                 the number of such recordings.
-//             Continue searching both above and below this node.
-// else if this is a static_type
-//     if this is *our* static_type
-//        if we found it above a dst_type, record the path from the dst_type
-//        else record the path from the dynamic_type being careful not to overwrite a
-//           previous public path in this latter case.
-//        Record that we found our static_type.
-//     Continue searching only below this node
-// else 
-//     Continue searching above and below this node.
-
-// __class_type_info::search1
-// There are no nodes to search above this node
-int
-__class_type_info::search1(__dynamic_cast_info* info, const void* dynamic_ptr,
-                           int path_below) const
+// __si_class_type_info
+
+__si_class_type_info::~__si_class_type_info()
 {
-    if (this == info->static_type)
-    {
-        if (dynamic_ptr == info->static_ptr)
-        {
-            if (info->path_dynamic_ptr_to_static_ptr != public_path)
-                info->path_dynamic_ptr_to_static_ptr = path_below;
-        }
-    }
-    return info->path_dynamic_ptr_to_static_ptr != public_path;
 }
 
-// __class_type_info::search2
-// There are no nodes to search above this node
-int
-__class_type_info::search2(__dynamic_cast_info* info, const void* dynamic_ptr,
-                           int path_below) const
+// __vmi_class_type_info
+
+__vmi_class_type_info::~__vmi_class_type_info()
 {
-#ifdef DEBUG
-std::cout << "__class_type_info::search2\n";
-#endif
-    if (this == info->static_type)
-    {
-        if (dynamic_ptr == info->static_ptr)
-        {
-            // It is possible to get here more than once.  Record the
-            //   "most public" path to here
-            if (info->above_dst_ptr)
-            {
-                if (info->path_dst_ptr_to_static_ptr != public_path)
-                    info->path_dst_ptr_to_static_ptr = path_below;
-                info->found_static_ptr = true;
-            }
-            else  // not above a dst_type
-            {
-                if (info->path_dynamic_ptr_to_static_ptr != public_path)
-                    info->path_dynamic_ptr_to_static_ptr = path_below;
-            }
-        }
-    }
-    else if (this == info->dst_type)
-    {
-        if (dynamic_ptr == info->dst_ptr_not_leading_to_static_ptr)
-        {
-            if (path_below == public_path)
-                info->path_dynamic_ptr_to_dst_ptr = public_path;
-        }
-        else
-        {
-            info->path_dynamic_ptr_to_dst_ptr = path_below;
-            info->dst_ptr_not_leading_to_static_ptr = dynamic_ptr;
-            info->number_to_dst_ptr += 1;
-            // If there exists another dst with a private path to
-            //    (static_ptr, static_type), then the cast from 
-            //     (dynamic_ptr, dynamic_type) to dst_type is now ambiguous.
-            if (info->number_to_static_ptr == 1 &&
-                info->path_dst_ptr_to_static_ptr == not_public_path)
-                return 0;
-        }
-    }
-    return 1;
 }
 
-#ifdef DEBUG
-void
-__class_type_info::display(const void* obj) const
+// __pbase_type_info
+
+__pbase_type_info::~__pbase_type_info()
 {
-    std::cout << "\n__class_type_info::this = " << obj << "  " << name() << '\n';
 }
-#endif
 
-// __si_class_type_info
+// __pointer_type_info
 
-__si_class_type_info::~__si_class_type_info()
+__pointer_type_info::~__pointer_type_info()
 {
 }
 
-// __si_class_type_info::search1
-// There is one node to search above this node.  The path to it is public
-//  and dynamic_ptr needs no adjustment in moving to that node.
-int
-__si_class_type_info::search1(__dynamic_cast_info* info, const void* dynamic_ptr,
-                              int path_below) const
+// __pointer_to_member_type_info
+
+__pointer_to_member_type_info::~__pointer_to_member_type_info()
 {
-    if (this == info->static_type)
+}
+
+// __dynamic_cast
+
+// static_ptr: source address to be adjusted; nonnull, and since the
+//   source object is polymorphic, *(void**)static_ptr is a virtual table pointer.
+// static_type: static type of the source object.
+// dst_type: destination type (the "T" in "dynamic_cast<T>(v)").
+// src2dst_offset: a static hint about the location of the
+//                 source subobject with respect to the complete object;
+//                 special negative values are:
+//                     -1: no hint
+//                     -2: static_type is not a public base of dst_type
+//                     -3: static_type is a multiple public base type but never a
+//                         virtual base type
+//                 otherwise, the static_type type is a unique public nonvirtual
+//                 base type of dst_type at offset src2dst_offset from the
+//                 origin of dst_type.
+//
+// (dynamic_ptr, dynamic_type) are the run time type of the complete object and
+// a pointer to it.  These can be found from static_ptr for polymorphic types.
+// static_type is guaranteed to be a polymorphic type.
+//
+// There are two classes of dst_types:
+//    1.  Those that lead to (static_ptr, static_type).
+//    2.  Those that do not lead to (static_ptr, static_type).
+// If there is exactly one dst_type of type 1, and
+//    If there is a public path from that dst_type to (static_ptr, static_type), or
+//    If there are 0 dst_types of type 2, and there is a public path from
+//        (dynamic_ptr, dynamic_type) to (static_ptr, static_type) and a public
+//        path from (dynamic_ptr, dynamic_type) to the one dst_type, then return
+//        a pointer to that dst_type.
+// Else if there are 0 dst_types of type 1 and exactly 1 dst_type of type 2, and
+//    if there is a public path (dynamic_ptr, dynamic_type) to
+//    (static_ptr, static_type) and a public path from (dynamic_ptr, dynamic_type)
+//    to the one dst_type, then return a pointer to that one dst_type.
+// Else return nullptr.
+//
+// If dynamic_type == dst_type, then the above algorithm collapses to the
+// following cheaper algorithm:
+//
+// If there is a public path from (dynamic_ptr, dynamic_type) to
+//    (static_ptr, static_type), then return dynamic_ptr.
+// Else return nullptr.
+extern "C"
+void*
+__dynamic_cast(const void* static_ptr,
+			   const __class_type_info* static_type,
+			   const __class_type_info* dst_type,
+			   std::ptrdiff_t src2dst_offset)
+{
+    // TODO:  Take advantage of src2dst_offset
+    void** vtable = *(void***)static_ptr;
+    ptrdiff_t offset_to_derived = (ptrdiff_t)vtable[-2];
+    const void* dynamic_ptr = (const char*)static_ptr + offset_to_derived;
+    const __class_type_info* dynamic_type = (const __class_type_info*)vtable[-1];
+    const void* dst_ptr = 0;
+    __dynamic_cast_info info = {dst_type, static_ptr, static_type, src2dst_offset, 0};
+    if (dynamic_type == dst_type)
     {
-        if (dynamic_ptr == info->static_ptr)
+        info.number_of_dst_type = 1;
+        dynamic_type->search_above_dst(&info, dynamic_ptr, dynamic_ptr, public_path);
+        if (info.path_dst_ptr_to_static_ptr == public_path)
+            dst_ptr = dynamic_ptr;
+    }
+    else
+    {
+        dynamic_type->search_below_dst(&info, dynamic_ptr, public_path);
+        switch (info.number_to_static_ptr)
         {
-            if (info->path_dynamic_ptr_to_static_ptr != public_path)
-                info->path_dynamic_ptr_to_static_ptr = path_below;
+        case 0:
+            if (info.number_to_dst_ptr == 1 &&
+                    info.path_dynamic_ptr_to_static_ptr == public_path &&
+                    info.path_dynamic_ptr_to_dst_ptr == public_path)
+                dst_ptr = info.dst_ptr_not_leading_to_static_ptr;
+            break;
+        case 1:
+            if (info.path_dst_ptr_to_static_ptr == public_path ||
+                   (
+                       info.number_to_dst_ptr == 0 &&
+                       info.path_dynamic_ptr_to_static_ptr == public_path &&
+                       info.path_dynamic_ptr_to_dst_ptr == public_path
+                   )
+               )
+                dst_ptr = info.dst_ptr_leading_to_static_ptr;
+            break;
         }
-        return info->path_dynamic_ptr_to_static_ptr != public_path;
     }
-    return __base_type->search1(info, dynamic_ptr, path_below);
+    return const_cast<void*>(dst_ptr);
 }
 
-// __si_class_type_info::search2
-// There is one node to search above this node.  The path to it is public
-//  and dynamic_ptr needs no adjustment in moving to that node.
-int
-__si_class_type_info::search2(__dynamic_cast_info* info, const void* dynamic_ptr,
-                              int path_below) const
+// Call this function when you hit a static_type which is a base (above) a dst_type.
+// Let caller know you hit a static_type.  But only start recording details if
+// this is (static_ptr, static_type) -- the node we are casting from.
+// If this is (static_ptr, static_type)
+//   Record the path (public or not) from the dst_type to here.  There may be
+//   multiple paths from the same dst_type to here, record the "most public" one.
+//   Record the dst_ptr as pointing to (static_ptr, static_type).
+//   If more than one (dst_ptr, dst_type) points to (static_ptr, static_type),
+//   then mark this dyanmic_cast as ambiguous and stop the search.
+void
+__class_type_info::process_static_type_above_dst(__dynamic_cast_info* info,
+                                                 const void* dst_ptr,
+                                                 const void* current_ptr,
+                                                 int path_below) const
 {
-#ifdef DEBUG
-std::cout << "__si_class_type_info::search2\n";
-#endif
-    if (this == info->static_type)
+    // Record that we found a static_type
+    info->found_any_static_type = true;
+    if (current_ptr == info->static_ptr)
     {
-        if (dynamic_ptr == info->static_ptr)
+        // Record that we found (static_ptr, static_type)
+        info->found_our_static_ptr = true;
+        if (info->dst_ptr_leading_to_static_ptr == 0)
         {
-            // It is possible to get here more than once.  Record the
-            //   "most public" path to here
-            if (info->above_dst_ptr)
-            {
-                if (info->path_dst_ptr_to_static_ptr != public_path)
-                    info->path_dst_ptr_to_static_ptr = path_below;
-                info->found_static_ptr = true;
-            }
-            else  // not above a dst_type
-            {
-                if (info->path_dynamic_ptr_to_static_ptr != public_path)
-                    info->path_dynamic_ptr_to_static_ptr = path_below;
-            }
+            // First time here
+            info->dst_ptr_leading_to_static_ptr = dst_ptr;
+            info->path_dst_ptr_to_static_ptr = path_below;
+            info->number_to_static_ptr = 1;
+            // If there is only one dst_type in the entire tree and the path from
+            //    there to here is public then we are done!
+            if (info->number_of_dst_type == 1 && info->path_dst_ptr_to_static_ptr == public_path)
+                info->search_done = true;
         }
-        return 1;
-    }
-    if (this == info->dst_type)
-    {
-        if (dynamic_ptr == info->dst_ptr_leading_to_static_ptr ||
-            dynamic_ptr == info->dst_ptr_not_leading_to_static_ptr)
+        else if (info->dst_ptr_leading_to_static_ptr == dst_ptr)
         {
-            if (path_below == public_path)
-                info->path_dynamic_ptr_to_dst_ptr = public_path;
+            // We've been here before.  Update path to "most public"
+            if (info->path_dst_ptr_to_static_ptr == not_public_path)
+                info->path_dst_ptr_to_static_ptr = path_below;
+            // If there is only one dst_type in the entire tree and the path from
+            //    there to here is public then we are done!
+            if (info->number_of_dst_type == 1 && info->path_dst_ptr_to_static_ptr == public_path)
+                info->search_done = true;
         }
         else
         {
-            info->path_dynamic_ptr_to_dst_ptr = path_below;
-            info->above_dst_ptr = true;
-            (void)__base_type->search2(info, dynamic_ptr, public_path);
-            info->above_dst_ptr = false;
-            if (info->found_static_ptr)
-            {
-                info->found_static_ptr = false;
-                info->dst_ptr_leading_to_static_ptr = dynamic_ptr;
-                info->number_to_static_ptr += 1;
-                // If more than one dst_type points to (static_ptr, static_type)
-                //   then the cast is ambiguous so abort search.
-                if (info->number_to_static_ptr != 1)
-                    return 0;
-                // If the path above to (static_ptr, static_type) isn't public
-                //    and if other dst_type's have been found, even if they
-                //    don't point to (static_ptr, static_type), then upcast
-                //    from (dynamic_ptr, dynamic_type) to dst_type is ambiguous.
-                if (info->path_dst_ptr_to_static_ptr == not_public_path &&
-                    info->number_to_dst_ptr != 0)
-                    return 0;
-            }
-            else
-            {
-                info->dst_ptr_not_leading_to_static_ptr = dynamic_ptr;
-                info->number_to_dst_ptr += 1;
-                // If there exists another dst with a private path to
-                //    (static_ptr, static_type), then the cast from 
-                //     (dynamic_ptr, dynamic_type) to dst_type is now ambiguous.
-                if (info->number_to_static_ptr == 1 &&
-                    info->path_dst_ptr_to_static_ptr == not_public_path)
-                    return 0;
-            }
+            // We've detected an ambiguous cast from (static_ptr, static_type)
+            //   to a dst_type
+            info->number_to_static_ptr += 1;
+            info->search_done = true;
         }
-        return 1;
     }
-    return __base_type->search2(info, dynamic_ptr, path_below);
 }
 
-#ifdef DEBUG
+// Call this function when you hit a static_type which is not a base (above) a dst_type.
+// Let caller know you hit a static_type (this may not be necessary).
+// But only start recording details if this is (static_ptr, static_type) -- the node we are casting from.
+// If this is (static_ptr, static_type)
+//   Record the path (public or not) from (dynamic_ptr, dynamic_type) to here.  There may be
+//   multiple paths from (dynamic_ptr, dynamic_type) to here, record the "most public" one.
 void
-__si_class_type_info::display(const void* obj) const
-{
-    std::cout << "\n__si_class_type_info::this = " << obj << "  " << name() << '\n';
-    __base_type->display(obj);
-}
-#endif
-
-// __vmi_class_type_info
-
-__vmi_class_type_info::~__vmi_class_type_info()
+__class_type_info::process_static_type_below_dst(__dynamic_cast_info* info,
+                                                 const void* current_ptr,
+                                                 int path_below) const
 {
+    // Record that we found a static_type
+    info->found_any_static_type = true;  // TODO: Consider removing, no one is currently listening
+    if (current_ptr == info->static_ptr)
+    {
+        // Record that we found (static_ptr, static_type)
+        info->found_our_static_ptr = true;  // TODO: Consider removing, no one is currently listening
+        // Record the most public path from (dynamic_ptr, dynamic_type) to
+        //                                  (static_ptr, static_type)
+        if (info->path_dynamic_ptr_to_static_ptr != public_path)
+            info->path_dynamic_ptr_to_static_ptr = path_below;
+    }
 }
 
-// __vmi_class_type_info::search1
-// There are one or more nodes to search above this node.  The path to it
-//  may be public or not and the dynamic_ptr may need to be adjusted.  Both
-//  of these details are handled by a pseudo-node in __base_class_type_info
-//  which has no type associated with it.
-int
-__vmi_class_type_info::search1(__dynamic_cast_info* info, const void* dynamic_ptr,
-                               int path_below) const
+// Call this function when searching below a dst_type node.  This function searches
+// for a path to (static_ptr, static_type) and for paths to one or more dst_type nodes.
+// If it finds a static_type node, there is no need to further search base classes
+// above.
+// If it finds a dst_type node it should search base classes using search_above_dst
+// to find out if this dst_type points to (static_ptr, static_type) or not.
+// Either way, the dst_type is recorded as one of two "classes":  one that does
+// or does not point to (static_ptr, static_type).
+// If this is neither a static_type nor a dst_type node, continue searching
+// base classes above.
+// All the hoopla surrounding the search code is doing nothing but looking for
+// excuses to stop the search prematurely (break out of the for-loop).
+void
+__vmi_class_type_info::search_below_dst(__dynamic_cast_info* info,
+                                        const void* current_ptr,
+                                        int path_below) const
 {
     typedef const __base_class_type_info* Iter;
     if (this == info->static_type)
+        process_static_type_below_dst(info, current_ptr, path_below);
+    else if (this == info->dst_type)
     {
-        if (dynamic_ptr == info->static_ptr)
+        // We've been here before if we've recorded current_ptr in one of these
+        //   two places:
+        if (current_ptr == info->dst_ptr_leading_to_static_ptr ||
+            current_ptr == info->dst_ptr_not_leading_to_static_ptr)
         {
-            if (info->path_dynamic_ptr_to_static_ptr != public_path)
-                info->path_dynamic_ptr_to_static_ptr = path_below;
+            // We've seen this node before, and therefore have already searched
+            // its base classes above.
+            //  Update path to here that is "most public".
+            if (path_below == public_path)
+                info->path_dynamic_ptr_to_dst_ptr = public_path;
+        }
+        else  // We have haven't been here before
+        {
+            // Record the access path that got us here
+            //   If there is more than one dst_type this path doesn't matter.
+            info->path_dynamic_ptr_to_dst_ptr = path_below;
+            // Only search above here if dst_type derives from static_type, or
+            //    if it is unknown if dst_type derives from static_type.
+            if (info->is_dst_type_derived_from_static_type != no)
+            {
+                // Set up flags to record results from all base classes
+                bool is_dst_type_derived_from_static_type = false;
+                bool does_dst_type_point_to_our_static_type = false;
+                // We've found a dst_type with a potentially public path to here.
+                // We have to assume the path is public because it may become
+                //   public later (if we get back to here with a public path).
+                // We can stop looking above if:
+                //    1.  We've found a public path to (static_ptr, static_type).
+                //    2.  We've found an ambiguous cast from (static_ptr, static_type) to a dst_type.
+                //        This is detected at the (static_ptr, static_type).
+                //    3.  We can prove that there is no public path to (static_ptr, static_type)
+                //        above here.
+                const Iter e = __base_info + __base_count;
+                for (Iter p = __base_info; p < e; ++p)
+                {
+                    // Zero out found flags
+                    info->found_our_static_ptr = false;
+                    info->found_any_static_type = false;
+                    p->search_above_dst(info, current_ptr, current_ptr, public_path);
+                   if (info->search_done)
+                        break;
+                    if (info->found_any_static_type)
+                    {
+                        is_dst_type_derived_from_static_type = true;
+                        if (info->found_our_static_ptr)
+                        {
+                            does_dst_type_point_to_our_static_type = true;
+                            // If we found what we're looking for, stop looking above.
+                            if (info->path_dst_ptr_to_static_ptr == public_path)
+                                break;
+                            // We found a private path to (static_ptr, static_type)
+                            //   If there is no diamond then there is only one path
+                            //   to (static_ptr, static_type) and we just found it.
+                            if (!(__flags & __diamond_shaped_mask))
+                                break;
+                        }
+                        else
+                        {
+                            // If we found a static_type that isn't the one we're looking
+                            //    for, and if there are no repeated types above here,
+                            //    then stop looking.
+                            if (!(__flags & __non_diamond_repeat_mask))
+                                break;
+                        }
+                    }
+                }
+                if (!does_dst_type_point_to_our_static_type)
+                {
+                    // We found a dst_type that doesn't point to (static_ptr, static_type)
+                    // So record the address of this dst_ptr and increment the
+                    // count of the number of such dst_types found in the tree.
+                    info->dst_ptr_not_leading_to_static_ptr = current_ptr;
+                    info->number_to_dst_ptr += 1;
+                    // If there exists another dst with a private path to
+                    //    (static_ptr, static_type), then the cast from 
+                    //     (dynamic_ptr, dynamic_type) to dst_type is now ambiguous,
+                    //      so stop search.
+                    if (info->number_to_static_ptr == 1 &&
+                            info->path_dst_ptr_to_static_ptr == not_public_path)
+                        info->search_done = true;
+                }
+                // If we found no static_type,s then dst_type doesn't derive
+                //   from static_type, else it does.  Record this result so that
+                //   next time we hit a dst_type we will know not to search above
+                //   it if it doesn't derive from static_type.
+                if (is_dst_type_derived_from_static_type)
+                    info->is_dst_type_derived_from_static_type = yes;
+                else
+                    info->is_dst_type_derived_from_static_type = no;
+            }
         }
-        return info->path_dynamic_ptr_to_static_ptr != public_path;
-    }
-    const Iter e = __base_info + __base_count;
-    for (Iter p = __base_info; p < e; ++p)
-    {
-        if (p->search1(info, dynamic_ptr, path_below) == 0)
-            return 0;
     }
-    return 1;
-}
-
-// __vmi_class_type_info::search2
-// There are one or more nodes to search above this node.  The path to it
-//  may be public or not and the dynamic_ptr may need to be adjusted.  Both
-//  of these details are handled by a pseudo-node in __base_class_type_info
-//  which has no type associated with it.
-int
-__vmi_class_type_info::search2(__dynamic_cast_info* info, const void* dynamic_ptr,
-                               int path_below) const
-{
-#ifdef DEBUG
-std::cout << "__vmi_class_type_info::search2\n";
-#endif
-    typedef const __base_class_type_info* Iter;
-    if (this == info->static_type)
+    else
     {
-        if (dynamic_ptr == info->static_ptr)
+        // This is not a static_type and not a dst_type.
+        const Iter e = __base_info + __base_count;
+        if ((__flags & __diamond_shaped_mask) || info->number_to_static_ptr == 1)
+        {
+            // If there are multiple paths to a base above from here, or if
+            //    a dst_type pointing to (static_ptr, static_type) has been found,
+            //    then there is no way to break out of this loop early unless
+            //    something below detects the search is done.
+            for (Iter p = __base_info; p < e; ++p)
+            {
+                p->search_below_dst(info, current_ptr, path_below);
+                if (info->search_done)
+                    break;
+            }
+        }
+        else if (__flags & __non_diamond_repeat_mask)
         {
-            // It is possible to get here more than once.  Record the
-            //   "most public" path to here
-            if (info->above_dst_ptr)
+            // There are not multiple paths to any base class from here and a
+            //   dst_type pointing to (static_ptr, static_type) has not yet been
+            //   found.
+            for (Iter p = __base_info; p < e; ++p)
             {
-                if (info->path_dst_ptr_to_static_ptr != public_path)
-                    info->path_dst_ptr_to_static_ptr = path_below;
-                info->found_static_ptr = true;
+                p->search_below_dst(info, current_ptr, path_below);
+                if (info->search_done)
+                    break;
+                // If we just found a dst_type with a public path to (static_ptr, static_type),
+                //    then the only reason to continue the search is to make sure
+                //    no other dst_type points to (static_ptr, static_type).
+                //    If !diamond, then we don't need to search here.
+                if (info->number_to_static_ptr == 1 &&
+                          info->path_dst_ptr_to_static_ptr == public_path)
+                    break;
             }
-            else  // not above a dst_type
+        }
+        else
+        {
+            // There are no repeated types above this node.
+            // There are no nodes with multiple parents above this node.
+            // no dst_type has been found to (static_ptr, static_type)
+            for (Iter p = __base_info; p < e; ++p)
             {
-                if (info->path_dynamic_ptr_to_static_ptr != public_path)
-                    info->path_dynamic_ptr_to_static_ptr = path_below;
+                p->search_below_dst(info, current_ptr, path_below);
+                if (info->search_done)
+                    break;
+                // If we just found a dst_type with a public path to (static_ptr, static_type),
+                //    then the only reason to continue the search is to make sure sure
+                //    no other dst_type points to (static_ptr, static_type).
+                //    If !diamond, then we don't need to search here.
+                // if we just found a dst_type with a private path to (static_ptr, static_type),
+                //    then we're only looking for a public path to (static_ptr, static_type)
+                //    and to check for other dst_types.
+                //    If !diamond & !repeat, then there is not a pointer to (static_ptr, static_type)
+                //    and not a dst_type under here.
+                if (info->number_to_static_ptr == 1)
+                    break;
             }
         }
-        return 1;
     }
-    if (this == info->dst_type)
+}
+
+// This is the same algorithm as __vmi_class_type_info::search_below_dst but
+//   simplified to the case that there is only a single base class.
+void
+__si_class_type_info::search_below_dst(__dynamic_cast_info* info,
+                                       const void* current_ptr,
+                                       int path_below) const
+{
+    if (this == info->static_type)
+        process_static_type_below_dst(info, current_ptr, path_below);
+    else if (this == info->dst_type)
     {
-        // If we've been here before
-        if (dynamic_ptr == info->dst_ptr_leading_to_static_ptr ||
-            dynamic_ptr == info->dst_ptr_not_leading_to_static_ptr)
+        // We've been here before if we've recorded current_ptr in one of these
+        //   two places:
+        if (current_ptr == info->dst_ptr_leading_to_static_ptr ||
+            current_ptr == info->dst_ptr_not_leading_to_static_ptr)
         {
-            // Then make a note if we can get here publicly
+            // We've seen this node before, and therefore have already searched
+            // its base classes above.
+            //  Update path to here that is "most public".
             if (path_below == public_path)
                 info->path_dynamic_ptr_to_dst_ptr = public_path;
         }
         else  // We have haven't been here before
         {
             // Record the access path that got us here
+            //   If there is more than one dst_type this path doesn't matter.
             info->path_dynamic_ptr_to_dst_ptr = path_below;
-            // Explore each base above
-            const Iter e = __base_info + __base_count;
-            for (Iter p = __base_info; p < e; ++p)
+            // Only search above here if dst_type derives from static_type, or
+            //    if it is unknown if dst_type derives from static_type.
+            if (info->is_dst_type_derived_from_static_type != no)
             {
-                // Let above nodes know that they are above a dst_type node
-                info->above_dst_ptr = true;
-                // Only a dst_type can abort the search, and one can't be
-                //   above here.  So it is safe to ignore return.
-                (void)p->search2(info, dynamic_ptr, public_path);
-                info->above_dst_ptr = false;
-                // If we found (static_ptr, static_type)
-                if (info->found_static_ptr)
+                // Set up flags to record results from all base classes
+                bool is_dst_type_derived_from_static_type = false;
+                bool does_dst_type_point_to_our_static_type = false;
+                // Zero out found flags
+                info->found_our_static_ptr = false;
+                info->found_any_static_type = false;
+                __base_type->search_above_dst(info, current_ptr, current_ptr, public_path);
+                if (info->found_any_static_type)
                 {
-                    info->found_static_ptr = false;
-                    if (info->dst_ptr_leading_to_static_ptr != dynamic_ptr)
-                    {
-                        info->dst_ptr_leading_to_static_ptr = dynamic_ptr;
-                        info->number_to_static_ptr += 1;
-                    }
-                    // If more than one dst_type points to (static_ptr, static_type)
-                    //   then the cast is ambiguous so abort search.
-                    if (info->number_to_static_ptr != 1)
-                        return 0;
-                    // If we've found a public path to (static_ptr, static_type)
-                    //   then we no longer need to search above this node
-                    if (info->path_dst_ptr_to_static_ptr == public_path)
-                        break;
+                    is_dst_type_derived_from_static_type = true;
+                    if (info->found_our_static_ptr)
+                        does_dst_type_point_to_our_static_type = true;
                 }
-                else
+                if (!does_dst_type_point_to_our_static_type)
                 {
-                    info->dst_ptr_not_leading_to_static_ptr = dynamic_ptr;
+                    // We found a dst_type that doesn't point to (static_ptr, static_type)
+                    // So record the address of this dst_ptr and increment the
+                    // count of the number of such dst_types found in the tree.
+                    info->dst_ptr_not_leading_to_static_ptr = current_ptr;
                     info->number_to_dst_ptr += 1;
                     // If there exists another dst with a private path to
                     //    (static_ptr, static_type), then the cast from 
                     //     (dynamic_ptr, dynamic_type) to dst_type is now ambiguous.
                     if (info->number_to_static_ptr == 1 &&
-                        info->path_dst_ptr_to_static_ptr == not_public_path)
-                        return 0;
+                            info->path_dst_ptr_to_static_ptr == not_public_path)
+                        info->search_done = true;
                 }
+                // If we found no static_type,s then dst_type doesn't derive
+                //   from static_type, else it does.  Record this result so that
+                //   next time we hit a dst_type we will know not to search above
+                //   it if it doesn't derive from static_type.
+                if (is_dst_type_derived_from_static_type)
+                    info->is_dst_type_derived_from_static_type = yes;
+                else
+                    info->is_dst_type_derived_from_static_type = no;
             }
-            // The path above to (static_ptr, static_type) isn't public
-            //    and multiple dst_type's have been found, even if they
-            //    don't point to (static_ptr, static_type), then upcast
-            //    from (dynamic_ptr, dynamic_type) to dst_type is ambiguous.
-            if (info->number_to_static_ptr == 1 &&
-                    info->path_dst_ptr_to_static_ptr == not_public_path &&
-                    info->number_to_dst_ptr != 0)
-                return 0;
         }
-        return 1;
     }
-    const Iter e = __base_info + __base_count;
-    // If you find a dst_type and __non_diamond_repeat_mask is not set, then
-    //    there is only one dst_type under here.
-    // If you find a static_type and __diamond_shaped_mask is not set, then
-    //    the static_type is the base of only one object.
-    if ((__flags & __diamond_shaped_mask) || info->number_to_static_ptr == 1)
+    else
     {
-        for (Iter p = __base_info; p < e; ++p)
-        {
-            if (p->search2(info, dynamic_ptr, path_below) == 0)
-                return 0;
-        }
+        // This is not a static_type and not a dst_type
+        __base_type->search_below_dst(info, current_ptr, path_below);
     }
-    else if (__flags & __non_diamond_repeat_mask)
+}
+
+// This is the same algorithm as __vmi_class_type_info::search_below_dst but
+//   simplified to the case that there is no base class.
+void
+__class_type_info::search_below_dst(__dynamic_cast_info* info,
+                                    const void* current_ptr,
+                                    int path_below) const
+{
+    typedef const __base_class_type_info* Iter;
+    if (this == info->static_type)
+        process_static_type_below_dst(info, current_ptr, path_below);
+    else if (this == info->dst_type)
     {
-        // There are no nodes with multiple parents above this node.
-        for (Iter p = __base_info; p < e; ++p)
+        // We've been here before if we've recorded current_ptr in one of these
+        //   two places:
+        if (current_ptr == info->dst_ptr_leading_to_static_ptr ||
+            current_ptr == info->dst_ptr_not_leading_to_static_ptr)
+        {
+            // We've seen this node before, and therefore have already searched
+            // its base classes above.
+            //  Update path to here that is "most public".
+            if (path_below == public_path)
+                info->path_dynamic_ptr_to_dst_ptr = public_path;
+        }
+        else  // We have haven't been here before
         {
-            if (p->search2(info, dynamic_ptr, path_below) == 0)
-                return 0;
-            // If we just found a dst_type with a public path to (static_ptr, static_type),
-            //    then the only reason to continue the search is to make sure
-            //    no other dst_type points to (static_ptr, static_type).
-            //    If !diamond, then we don't need to search here.
+            // Record the access path that got us here
+            //   If there is more than one dst_type this path doesn't matter.
+            info->path_dynamic_ptr_to_dst_ptr = path_below;
+            // We found a dst_type that doesn't point to (static_ptr, static_type)
+            // So record the address of this dst_ptr and increment the
+            // count of the number of such dst_types found in the tree.
+            info->dst_ptr_not_leading_to_static_ptr = current_ptr;
+            info->number_to_dst_ptr += 1;
+            // If there exists another dst with a private path to
+            //    (static_ptr, static_type), then the cast from 
+            //     (dynamic_ptr, dynamic_type) to dst_type is now ambiguous.
             if (info->number_to_static_ptr == 1 &&
-                      info->path_dst_ptr_to_static_ptr == public_path)
-                break;
+                    info->path_dst_ptr_to_static_ptr == not_public_path)
+                info->search_done = true;
+            // We found that dst_type does not derive from static_type
+            info->is_dst_type_derived_from_static_type = no;
         }
     }
+}
+
+// Call this function when searching above a dst_type node.  This function searches
+// for a public path to (static_ptr, static_type).
+// This function is guaranteed not to find a node of type dst_type.
+// Theoretically this is a very simple function which just stops if it finds a
+// static_type node, else keeps searching with:
+//
+//             const Iter e = __base_info + __base_count;
+//             for (Iter p = __base_info; p < e; ++p)
+//                 p->search_above_dst(info, dst_ptr, current_ptr, path_below);
+//
+// All the hoopla surrounding the search code is doing nothing but looking for
+// excuses to stop the search prematurely (break out of the for-loop).
+void
+__vmi_class_type_info::search_above_dst(__dynamic_cast_info* info,
+                                        const void* dst_ptr,
+                                        const void* current_ptr,
+                                        int path_below) const
+{
+    if (this == info->static_type)
+        process_static_type_above_dst(info, dst_ptr, current_ptr, path_below);
     else
     {
-        // There are no repeated types above this node.
-        // There are no nodes with multiple parents above this node.
-        // no dst_type has been found to (static_ptr, static_type) or
-        //   if it has been found, it has a public path.
+        typedef const __base_class_type_info* Iter;
+        // This is not a static_type and not a dst_type
+        // Save flags so they can be restored when returning to nodes below.
+        bool found_our_static_ptr = info->found_our_static_ptr;
+        bool found_any_static_type = info->found_any_static_type;
+        // We've found a dst_type below with a path to here.  If the path
+        //    to here is not public, there may be another path to here that
+        //    is public.  So we have to assume that the path to here is public.
+        //  We can stop looking above if:
+        //    1.  We've found a public path to (static_ptr, static_type).
+        //    2.  We've found an ambiguous cast from (static_ptr, static_type) to a dst_type.
+        //        This is detected at the (static_ptr, static_type).
+        //    3.  We can prove that there is no public path to (static_ptr, static_type)
+        //        above here.
+        const Iter e = __base_info + __base_count;
         for (Iter p = __base_info; p < e; ++p)
         {
-            if (p->search2(info, dynamic_ptr, path_below) == 0)
-                return 0;
-            // If we just found a dst_type with a public path to (static_ptr, static_type),
-            //    then the only reason to continue the search is to make sure sure
-            //    no other dst_type points to (static_ptr, static_type).
-            //    If !diamond, then we don't need to search here.
-            // if we just found a dst_type with a private path to (static_ptr, static_type),
-            //    then we're only looking for a public path to (static_ptr, static_type)
-            //    and to check for other dst_types.
-            //    If !diamond & !repeat, then there is not a pointer to (static_ptr, static_type)
-            //    and not a dst_type under here.
-            if (info->number_to_static_ptr == 1)
+            // Zero out found flags
+            info->found_our_static_ptr = false;
+            info->found_any_static_type = false;
+            p->search_above_dst(info, dst_ptr, current_ptr, path_below);
+            if (info->search_done)
                 break;
+            if (info->found_our_static_ptr)
+            {
+                // If we found what we're looking for, stop looking above.
+                if (info->path_dst_ptr_to_static_ptr == public_path)
+                    break;
+                // We found a private path to (static_ptr, static_type)
+                //   If there is no diamond then there is only one path
+                //   to (static_ptr, static_type) from here and we just found it.
+                if (!(__flags & __diamond_shaped_mask))
+                    break;
+            }
+            else if (info->found_any_static_type)
+            {
+                // If we found a static_type that isn't the one we're looking
+                //    for, and if there are no repeated types above here,
+                //    then stop looking.
+                if (!(__flags & __non_diamond_repeat_mask))
+                    break;
+            }
         }
+        // Restore flags
+        info->found_our_static_ptr = found_our_static_ptr;
+        info->found_any_static_type = found_any_static_type;
     }
-    return 1;
-}
-
-// __base_class_type_info::search1
-// This is a psuedo-node which does nothing but adjust the path access and
-//  dynamic_ptr prior to calling the base node above.
-//  The dynamic_ptr adjustment depends upon whether or not this node is marked
-//     virtual.
-//  If the path up is public, no change is made to the path (it may already be
-//     marked private from below).  If the path up is private, it is forced so.
-int
-__base_class_type_info::search1(__dynamic_cast_info* info, const void* dynamic_ptr,
-                                int path_below) const
-{
-    ptrdiff_t offset_to_base = __offset_flags >> __offset_shift;
-    if (__offset_flags & __virtual_mask)
-    {
-        char* vtable = *(char**)dynamic_ptr;
-        offset_to_base = *(ptrdiff_t*)(vtable + offset_to_base);
-    }
-    return __base_type->search1(info, (char*)dynamic_ptr + offset_to_base,
-                                (__offset_flags & __public_mask) ? path_below :
-                                                                   not_public_path);
 }
 
-// __base_class_type_info::search2
-// This is a psuedo-node which does nothing but adjust the path access and
-//  dynamic_ptr prior to calling the base node above.
-//  The dynamic_ptr adjustment depends upon whether or not this node is marked
-//     virtual.
-//  If the path up is public, no change is made to the path (it may already be
-//     marked private from below).  If the path up is private, it is forced so.
-int
-__base_class_type_info::search2(__dynamic_cast_info* info, const void* dynamic_ptr,
-                                int path_below) const
+// This is the same algorithm as __vmi_class_type_info::search_above_dst but
+//   simplified to the case that there is only a single base class.
+void
+__si_class_type_info::search_above_dst(__dynamic_cast_info* info,
+                                       const void* dst_ptr,
+                                       const void* current_ptr,
+                                       int path_below) const
 {
-#ifdef DEBUG
-std::cout << "__base_class_type_info::search2\n";
-#endif
-    ptrdiff_t offset_to_base = __offset_flags >> __offset_shift;
-    if (__offset_flags & __virtual_mask)
-    {
-        char* vtable = *(char**)dynamic_ptr;
-        offset_to_base = *(ptrdiff_t*)(vtable + offset_to_base);
-    }
-    return __base_type->search2(info, (char*)dynamic_ptr + offset_to_base,
-                                (__offset_flags & __public_mask) ? path_below :
-                                                                   not_public_path);
+    if (this == info->static_type)
+        process_static_type_above_dst(info, dst_ptr, current_ptr, path_below);
+    else
+        __base_type->search_above_dst(info, dst_ptr, current_ptr, path_below);
 }
 
-#ifdef DEBUG
-
+// This is the same algorithm as __vmi_class_type_info::search_above_dst but
+//   simplified to the case that there is no base class.
 void
-__vmi_class_type_info::display(const void* obj) const
+__class_type_info::search_above_dst(__dynamic_cast_info* info,
+                                    const void* dst_ptr,
+                                    const void* current_ptr,
+                                    int path_below) const
 {
-    std::cout << "\n__vmi_class_type_info::this = " << obj << "  " << name() << '\n';
-    if (__flags & __non_diamond_repeat_mask)
-        std::cout << "__non_diamond_repeat_mask\n";
-    if (__flags & __diamond_shaped_mask)
-        std::cout << "__diamond_shaped_mask\n";
-    std::cout << "__base_count = " << __base_count << '\n';
-    for (const __base_class_type_info* p = __base_info; p < __base_info + __base_count; ++p)
-        p->display(obj);
+    if (this == info->static_type)
+        process_static_type_above_dst(info, dst_ptr, current_ptr, path_below);
 }
 
+// The search functions for __base_class_type_info are simply convenience
+//   functions for adjusting the current_ptr and path_below as the search is
+//   passed up to the base class node.
+
 void
-__base_class_type_info::display(const void* obj) const
+__base_class_type_info::search_above_dst(__dynamic_cast_info* info,
+                                         const void* dst_ptr,
+                                         const void* current_ptr,
+                                         int path_below) const
 {
-    if (__offset_flags & __virtual_mask)
-        std::cout << "__virtual_mask\n";
-    if (__offset_flags & __public_mask)
-        std::cout << "__public_mask\n";
     ptrdiff_t offset_to_base = __offset_flags >> __offset_shift;
     if (__offset_flags & __virtual_mask)
     {
-        char* vtable = *(char**)obj;
+        char* vtable = *(char**)current_ptr;
         offset_to_base = *(ptrdiff_t*)(vtable + offset_to_base);
     }
-    __base_type->display((char*)obj + offset_to_base);
-}
-
-#endif
-
-// __pbase_type_info
-
-__pbase_type_info::~__pbase_type_info()
-{
-}
-
-// __pointer_type_info
-
-__pointer_type_info::~__pointer_type_info()
-{
-}
-
-// __pointer_to_member_type_info
-
-__pointer_to_member_type_info::~__pointer_to_member_type_info()
-{
+    __base_type->search_above_dst(info, dst_ptr,
+                                  (char*)current_ptr + offset_to_base,
+                                  (__offset_flags & __public_mask) ?
+                                      path_below :
+                                      not_public_path);
 }
 
-// __dynamic_cast
-
-// static_ptr: source address to be adjusted; nonnull, and since the
-//   source object is polymorphic, *(void**)static_ptr is a virtual table pointer.
-// static_type: static type of the source object.
-// dst_type: destination type (the "T" in "dynamic_cast<T>(v)").
-// src2dst_offset: a static hint about the location of the
-//                 source subobject with respect to the complete object;
-//                 special negative values are:
-//                     -1: no hint
-//                     -2: static_type is not a public base of dst_type
-//                     -3: static_type is a multiple public base type but never a
-//                         virtual base type
-//                 otherwise, the static_type type is a unique public nonvirtual
-//                 base type of dst_type at offset src2dst_offset from the
-//                 origin of dst_type.
-// Returns either one of:
-//    1.  dynamic_ptr adjusted from static_ptr given a public path from
-//        (static_ptr, static_type) to dst_type without ambiguity, or
-//    2.  dynamic_ptr adjusted from static_ptr given a public path from
-//        (static_ptr, static_type) to (dynamic_ptr, dynamic_type) and also
-//        a public path from (dynamic_ptr, dynamic_type) to dst_type without
-//        ambiguity, or
-//    3.  nullptr
-// Knowns:
-//     (dynamic_ptr, dynamic_type) can be extracted from static_ptr.
-//     dynamic_ptr is a pointer to the complete run time object.
-//     dynamic_type is the type of the complete run time object.
-//     The type hierarchy is a DAG rooted at (dynamic_ptr, dynamic_type) and
-//     traveling up.  Each node represents a distinct sub-object and is
-//     uniquely identified by a (const void*, const __class_type_info*) pair.
-//     __dynamic_cast is not called if dst_type == static_type, or if dst_type
-//     appears as a node above (static_ptr, static_type), or if static_ptr is
-//     nullptr.  In these cases the compiler already knows the answer.
-//     So if dst_type appears in the DAG, it appears at the root
-//     (dst_type == dynamic_type) or between the root and any static_types.
-//     No type can appear above a node of the same type in the DAG.  Thus
-//     there is only one node with type dynamic_type.
-//     A node can appear above more than one node, as well as below more than
-//     one node.
-//     If dst_type == dynamic_type then there is only one dst_type in the
-//        DAG and cases 1 and 2 collapse to the same degenerate case.  And
-//        this degenerate case is easier/faster to search:
-//        Returns dynamic_ptr if there exists a public path from
-//           (dynamic_ptr, dynamic_type) to (static_ptr, static_type),
-//           else returns nullptr.
-//        This check is purely an optimization and does not impact correctness.
-// Algorithm:
-//    Extract (dynamic_ptr, dynamic_type) from static_ptr.
-//    If dynamic_type == dst_type
-//       If there is a public path from (dynamic_ptr, dynamic_type) to
-//          (static_ptr, static_type), return dynamic_ptr else return nullptr.
-//    Else dynamic_type != dst_type
-//       If there is a single dst_type derived (below) (static_ptr, static_type)
-//           If the path from that unique dst_type to (static_ptr, static_type)
-//              is public, return a pointer to that dst_type else return nullptr.
-//           Else if there are no dst_type's which don't point to (static_ptr, static_type)
-//              and if there is a pubic path from (dynamic_ptr, dynamic_type) to
-//              (static_ptr, static_type) and a public path from (dynamic_ptr, dynamic_type)
-//              to the single dst_type, then return a pointer to that dst_type,
-//           Else return nullptr.
-//       Else if there are no dst_type derived (below) (static_ptr, static_type)
-//           And if there is a single dst_type base of (above)
-//               (dynamic_ptr, dynamic_type), and if that single dst_type has a
-//               public path to it.  And if there is a public path
-//               from (dynamic_ptr, dynamic_type) to (static_ptr, static_type)
-//               then return a pointer to that single dst_type, else return nullptr.
-//       Else return nullptr.
-extern "C"
-void*
-__dynamic_cast(const void* static_ptr,
-			   const __class_type_info* static_type,
-			   const __class_type_info* dst_type,
-			   std::ptrdiff_t src2dst_offset)
+void
+__base_class_type_info::search_below_dst(__dynamic_cast_info* info,
+                                         const void* current_ptr,
+                                         int path_below) const
 {
-#ifdef DEBUG
-std::cout << "static_ptr = " << static_ptr << '\n';
-std::cout << "static_type = " << static_type << '\n';
-std::cout << "dst_type = " << dst_type << '\n';
-std::cout << "src2dst_offset = " << src2dst_offset << '\n';
-#endif
-    void** vtable = *(void***)static_ptr;
-    ptrdiff_t offset_to_derived = (ptrdiff_t)vtable[-2];
-    const void* dynamic_ptr = (const char*)static_ptr + offset_to_derived;
-    const __class_type_info* dynamic_type = (const __class_type_info*)vtable[-1];
-#ifdef DEBUG
-std::cout << "dynamic_ptr = " << dynamic_ptr << '\n';
-std::cout << "dynamic_type = " << dynamic_type << '\n';
-dynamic_type->display(dynamic_ptr);
-#endif
-    const void* dst_ptr = 0;
-    __dynamic_cast_info info = {dst_type, static_ptr, static_type, src2dst_offset, 0};
-    if (dynamic_type == dst_type)
-    {
-        (void)dynamic_type->search1(&info, dynamic_ptr, public_path);
-        if (info.path_dynamic_ptr_to_static_ptr == public_path)
-            dst_ptr = dynamic_ptr;
-    }
-    else
+    ptrdiff_t offset_to_base = __offset_flags >> __offset_shift;
+    if (__offset_flags & __virtual_mask)
     {
-        (void)dynamic_type->search2(&info, dynamic_ptr, public_path);
-        switch (info.number_to_static_ptr)
-        {
-        case 0:
-            if (info.number_to_dst_ptr == 1 &&
-                    info.path_dynamic_ptr_to_static_ptr == public_path &&
-                    info.path_dynamic_ptr_to_dst_ptr == public_path)
-                dst_ptr = info.dst_ptr_not_leading_to_static_ptr;
-            break;
-        case 1:
-            if (info.path_dst_ptr_to_static_ptr == public_path ||
-                   (
-                       info.number_to_dst_ptr == 0 &&
-                       info.path_dynamic_ptr_to_static_ptr == public_path &&
-                       info.path_dynamic_ptr_to_dst_ptr == public_path
-                   )
-               )
-                dst_ptr = info.dst_ptr_leading_to_static_ptr;
-            break;
-        }
+        char* vtable = *(char**)current_ptr;
+        offset_to_base = *(ptrdiff_t*)(vtable + offset_to_base);
     }
-    return const_cast<void*>(dst_ptr);
+    __base_type->search_below_dst(info,
+                                  (char*)current_ptr + offset_to_base,
+                                  (__offset_flags & __public_mask) ?
+                                      path_below :
+                                      not_public_path);
 }
 
 }  // __cxxabiv1