diff options
author | Howard Hinnant <hhinnant@apple.com> | 2012-01-16 00:13:46 +0000 |
---|---|---|
committer | Howard Hinnant <hhinnant@apple.com> | 2012-01-16 00:13:46 +0000 |
commit | 1309366d3676ca5a34bea0388ad2d2dd5701dc9b (patch) | |
tree | 12c8aea34663d0ace26edf595e3bc73a1c0ad661 /src | |
parent | 481fe05b27444f74f941678051e3a6b3ada25f39 (diff) |
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
Diffstat (limited to 'src')
-rw-r--r-- | src/private_typeinfo.cpp | 1057 | ||||
-rw-r--r-- | src/private_typeinfo.h | 47 |
2 files changed, 543 insertions, 561 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 diff --git a/src/private_typeinfo.h b/src/private_typeinfo.h index 9c3ad20..b7e952e 100644 --- a/src/private_typeinfo.h +++ b/src/private_typeinfo.h @@ -48,7 +48,9 @@ enum { unknown = 0, public_path, - not_public_path + not_public_path, + yes, + no }; class __class_type_info; @@ -80,11 +82,18 @@ struct __dynamic_cast_info int number_to_static_ptr; // Number of dst_types not below (static_ptr, static_type) int number_to_dst_ptr; - // true when the search is above a dst_type, else false - bool above_dst_ptr; + // + int is_dst_type_derived_from_static_type; + // Number of dst_type in tree. If 0, then that means unknown. + int number_of_dst_type; // communicates to a dst_type node that (static_ptr, static_type) was found // above it. - bool found_static_ptr; + bool found_our_static_ptr; + // communicates to a dst_type node that a static_type was found + // above it, but it wasn't (static_ptr, static_type) + bool found_any_static_type; + // Set whenever a search can be stopped + bool search_done; }; // Has no base class @@ -94,11 +103,10 @@ class __class_type_info public: virtual ~__class_type_info(); - virtual int search1(__dynamic_cast_info*, const void*, int) const; - virtual int search2(__dynamic_cast_info*, const void*, int) const; -#ifdef DEBUG - virtual void display(const void* obj) const; -#endif + void process_static_type_above_dst(__dynamic_cast_info*, const void*, const void*, int) const; + void process_static_type_below_dst(__dynamic_cast_info*, const void*, int) const; + virtual void search_above_dst(__dynamic_cast_info*, const void*, const void*, int) const; + virtual void search_below_dst(__dynamic_cast_info*, const void*, int) const; }; // Has one non-virtual public base class at offset zero @@ -110,11 +118,8 @@ public: virtual ~__si_class_type_info(); - virtual int search1(__dynamic_cast_info*, const void*, int) const; - virtual int search2(__dynamic_cast_info*, const void*, int) const; -#ifdef DEBUG - virtual void display(const void* obj) const; -#endif + virtual void search_above_dst(__dynamic_cast_info*, const void*, const void*, int) const; + virtual void search_below_dst(__dynamic_cast_info*, const void*, int) const; }; struct __base_class_type_info @@ -130,11 +135,8 @@ public: __offset_shift = 8 }; - int search1(__dynamic_cast_info*, const void*, int) const; - int search2(__dynamic_cast_info*, const void*, int) const; -#ifdef DEBUG - void display(const void* obj) const; -#endif + void search_above_dst(__dynamic_cast_info*, const void*, const void*, int) const; + void search_below_dst(__dynamic_cast_info*, const void*, int) const; }; // Has one or more base classes @@ -156,11 +158,8 @@ public: virtual ~__vmi_class_type_info(); - virtual int search1(__dynamic_cast_info*, const void*, int) const; - virtual int search2(__dynamic_cast_info*, const void*, int) const; -#ifdef DEBUG - virtual void display(const void* obj) const; -#endif + virtual void search_above_dst(__dynamic_cast_info*, const void*, const void*, int) const; + virtual void search_below_dst(__dynamic_cast_info*, const void*, int) const; }; class __pbase_type_info |