src/dynamic_cast.cc - platform/abi/cpp - Git at Google

 // Copyright (C) 2011 The Android Open Source Project
 // All rights reserved.
 //
 // Redistribution and use in source and binary forms, with or without
 // modification, are permitted provided that the following conditions
 // are met:
 // 1. Redistributions of source code must retain the above copyright
 //    notice, this list of conditions and the following disclaimer.
 // 2. Redistributions in binary form must reproduce the above copyright
 //    notice, this list of conditions and the following disclaimer in the
 //    documentation and/or other materials provided with the distribution.
 // 3. Neither the name of the project nor the names of its contributors
 //    may be used to endorse or promote products derived from this software
 //    without specific prior written permission.
 //
 // THIS SOFTWARE IS PROVIDED BY THE PROJECT AND CONTRIBUTORS ``AS IS'' AND
 // ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
 // IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
 // ARE DISCLAIMED.  IN NO EVENT SHALL THE PROJECT OR CONTRIBUTORS BE LIABLE
 // FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
 // DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
 // OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
 // HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
 // LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
 // OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
 // SUCH DAMAGE.
 //
 // dynamic_cast.cc: RTTI support.
 //
 // References:
 // Itanium C++ ABI at http://www.codesourcery.com/public/cxx-abi/abi.html
 // IHI0041A C++ Application Binary Interface for the ARM architecture.
 //

 #include <cxxabi.h>

 #include <cstddef>
 #include <cassert>

 namespace
 {
   // Adjust a pointer by an offset.

   const void*
   adjust_pointer(const void* p, std::ptrdiff_t off)
   {
     // FIXME: should we align pointer after adjustment?
     const char *cp = reinterpret_cast<const char*>(p) + off;
     return reinterpret_cast<const void*>(cp);
   }

   // Return the vtable pointer of a polymorphic object pointed by p.

   inline const void*
   get_vtable(const void* p)
   {
     return *reinterpret_cast<void*const*>(p);
   }

   // Return a pointer to a __class_type_info in a vtable.

   inline const abi::__class_type_info*
   get_class_type_info(const void* vtable)
   {
     const void* type_info_ptr = adjust_pointer(vtable, -sizeof(void*));
     return *reinterpret_cast<abi::__class_type_info*const*>(type_info_ptr);
   }

   // Return offset to object in a vtable.

   inline std::ptrdiff_t
   get_offset_to_top(const void* vtable)
   {
     const void* type_info_ptr_address = adjust_pointer(vtable, -sizeof(void*));
     const void* offset_to_top_address =
       adjust_pointer(type_info_ptr_address, -sizeof(std::ptrdiff_t));
     return *reinterpret_cast<const std::ptrdiff_t*>(offset_to_top_address);
   }

   // Return the virtual pointer to the most derived object of referred by a
   // pointer p.

   const void*
   get_most_derived_object(const void* p)
   {
     const void* vtable = get_vtable(p);
     std::ptrdiff_t offset_to_top = get_offset_to_top(vtable);
     return adjust_pointer(p, offset_to_top);
   }

   // We assume that -1 cannot be a valid pointer to object.
   const void * const ambiguous_object =
     reinterpret_cast<const void*>(-1);

   // Return a pointer to the subobject described by base_info.

   const void*
   get_subobject(const void* object,
                 const void* vtable,
                 const abi::__base_class_type_info* base_info)
   {
     long offset = base_info->offset();
     if (base_info->is_virtual())
       {
         const std::ptrdiff_t* virtual_base_offset_address =
           static_cast<const std::ptrdiff_t*> (adjust_pointer(vtable, offset));
         offset = *virtual_base_offset_address;
       }
     return adjust_pointer(object, offset);
   }

   // Helper of __dyanmic_cast to walk the type tree of an object.

   const void *
   walk_object(const void *object,
               const abi::__class_type_info *type,
               const void *match_object,
               const abi::__class_type_info *match_type)
   {
     if (*type == *match_type)
       return (match_object == NULL || object == match_object) ? object : NULL;

     switch(type->code())
       {
       case abi::__class_type_info::CLASS_TYPE_INFO_CODE:
         // This isn't not the class you're looking for.
         return NULL;

       case abi::__class_type_info::SI_CLASS_TYPE_INFO_CODE:
         // derived type has a single public base at offset 0.
         {
           const abi::__si_class_type_info* ti =
             static_cast<const abi::__si_class_type_info*>(type);
           return walk_object(object, ti->__base_type, match_object,
                              match_type);
         }

       case abi::__class_type_info::VMI_CLASS_TYPE_INFO_CODE:
         {
           const void* vtable = get_vtable(object);
           const abi::__vmi_class_type_info* ti =
             static_cast<const abi::__vmi_class_type_info*>(type);

           // Look at all direct bases.
           const void* result = NULL;
           for (unsigned i = 0; i < ti->__base_count; ++i)
             {
               if (!ti->__base_info[i].is_public())
                 continue;

               const void *subobject =
                 get_subobject(object, vtable, &ti->__base_info[i]);
               const void* walk_subobject_result =
                 walk_object(subobject, ti->__base_info[i].__base_type,
                             match_object, match_type);

               if (walk_subobject_result == ambiguous_object)
                 return ambiguous_object;
               else if (walk_subobject_result != NULL)
                 {
                   if (result == NULL)
                     {
                       result = walk_subobject_result;
                     }
                   else if (result != walk_subobject_result)
                     return ambiguous_object;
                 }
             }
           return result;
         }

       default:
         assert(0);
       }
     return NULL;
   }

   // Bookkeeping structure for derived-to-base cast in the general case.
   struct cast_context
   {
   public:
     const void* object;
     const abi::__class_type_info *src_type;
     const abi::__class_type_info *dst_type;
     std::ptrdiff_t src2dst_offset;

     const void* dst_object;
     const void* result;

     cast_context(const void* obj, const abi::__class_type_info *src,
                  const abi::__class_type_info *dst, std::ptrdiff_t offset)
       : object(obj), src_type(src), dst_type(dst), src2dst_offset(offset),
         dst_object(NULL), result(NULL)
     { }
   };

   // based-to-derive cast in the general case.

   void
   base_to_derived_cast(const void *object,
                        const abi::__class_type_info *type,
                        cast_context* context)
   {
     const void* saved_dst_object = context->dst_object;
     bool is_dst_type = *type == *context->dst_type;
     if (is_dst_type)
       context->dst_object = object;

     if (object == context->object
         && context->dst_object != NULL
         && *type == *context->src_type)
       {
         if (context->result == NULL)
           context->result = context->dst_object;
         else if (context->result != context->dst_object)
           context->result = ambiguous_object;
         context->dst_object = saved_dst_object;
         return;
       }

     switch(type->code())
       {
       case abi::__class_type_info::CLASS_TYPE_INFO_CODE:
         // This isn't not the class you're looking for.
         break;

       case abi::__class_type_info::SI_CLASS_TYPE_INFO_CODE:
         // derived type has a single public base at offset 0.
         {
           const abi::__si_class_type_info* ti =
             static_cast<const abi::__si_class_type_info*>(type);
           base_to_derived_cast(object, ti->__base_type, context);
           break;
         }

       case abi::__class_type_info::VMI_CLASS_TYPE_INFO_CODE:
         {
           const void* vtable = get_vtable(object);
           const abi::__vmi_class_type_info* ti =
             static_cast<const abi::__vmi_class_type_info*>(type);

           // Look at all direct bases.
           for (unsigned i = 0; i < ti->__base_count; ++i)
             {
               if (!ti->__base_info[i].is_public())
                 continue;

               const void *subobject =
                 get_subobject(object, vtable, &ti->__base_info[i]);
               base_to_derived_cast(subobject, ti->__base_info[i].__base_type,
                                    context);

               // FIXME: Use flags in base_info to optimize search.
               if (context->result == ambiguous_object)
                 break;
             }
           break;
         }

       default:
         assert(0);
       }
      context->dst_object = saved_dst_object;
   }
 } // namespace

 namespace __cxxabiv1
 {
 #define DYNAMIC_CAST_NO_HINT -1
 #define DYNAMIC_CAST_NOT_PUBLIC_BASE -2
 #define DYNAMIC_CAST_MULTIPLE_PUBLIC_NONVIRTUAL_BASE -3

   /* v: source address to be adjusted; nonnull, and since the
    *    source object is polymorphic, *(void**)v is a virtual pointer.
    * src: static type of the source object.
    * dst: 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: src is not a public base of dst
    *       -3: src is a multiple public base type but never a
    *           virtual base type
    *    otherwise, the src type is a unique public nonvirtual
    *    base type of dst at offset src2dst_offset from the
    *    origin of dst.
    */
   extern "C" void*
   __dynamic_cast (const void *v,
                   const abi::__class_type_info *src,
                   const abi::__class_type_info *dst,
                   std::ptrdiff_t src2dst_offset)
   {
     const void* most_derived_object = get_most_derived_object(v);
     const void* vtable = get_vtable(most_derived_object);
     const abi::__class_type_info* most_derived_class_type_info =
       get_class_type_info(vtable);

     // If T is not a public base type of the most derived class referred
     // by v, the cast always fails.
     void* t_object =
       const_cast<void*>(walk_object(most_derived_object,
                                     most_derived_class_type_info, NULL, dst));
     if (t_object == NULL)
       return NULL;

     // C++ ABI 2.9.7 The dynamic_cast Algorithm:
     //
     // If, in the most derived object pointed (referred) to by v, v points
     // (refers) to a public base class subobject of a T object [note: this can
     // be checked at compile time], and if only one object of type T is derived
     // from the subobject pointed (referred) to by v, the result is a pointer
     // (an lvalue referring) to that T object.

     // We knew that src is not a public base, so base-to-derived cast
     // is not possible.  This works even if there are multiple subobjects
     // of type T in the most derived object.
     if (src2dst_offset != DYNAMIC_CAST_NOT_PUBLIC_BASE)
       {
         // If it is known that v points to a public base class subobject
         // of a T object, simply adjust the pointer by the offset.
         if (t_object != ambiguous_object && src2dst_offset >= 0)
           return const_cast<void*>(adjust_pointer(v, src2dst_offset));

         // If there is only one T type subobject, we only need to look at
         // there.  Otherwise, look for the subobject referred by v in the
         // most derived object.
         cast_context context(v, src, dst, src2dst_offset);
         if (t_object != ambiguous_object)
           base_to_derived_cast(t_object, dst, &context);
         else
           base_to_derived_cast(most_derived_object,
                                most_derived_class_type_info, &context);

         if (context.result != NULL && context.result != ambiguous_object)
           return const_cast<void*>(context.result);
       }

     // C++ ABI 2.9.7 The dynamic_cast Algorithm:
     //
     // Otherwise, if v points (refers) to a public base class subobject of the
     // most derived object, and the type of the most derived object has an
     // unambiguous public base class of type T, the result is a pointer (an
     // lvalue referring) to the T subobject of the most derived object.
     // Otherwise, the run-time check fails.

     // Check to see if T is a unambiguous public base class.
     if (t_object == ambiguous_object)
       return NULL;

     // See if v refers to a public base class subobject.
     const void* v_object =
       walk_object(most_derived_object, most_derived_class_type_info, v, src);
     return v_object == v ? t_object : NULL;
   }
 } // namespace __cxxabiv1
	// Copyright (C) 2011 The Android Open Source Project
	// All rights reserved.
	//
	// Redistribution and use in source and binary forms, with or without
	// modification, are permitted provided that the following conditions
	// are met:
	// 1. Redistributions of source code must retain the above copyright
	// notice, this list of conditions and the following disclaimer.
	// 2. Redistributions in binary form must reproduce the above copyright
	// notice, this list of conditions and the following disclaimer in the
	// documentation and/or other materials provided with the distribution.
	// 3. Neither the name of the project nor the names of its contributors
	// may be used to endorse or promote products derived from this software
	// without specific prior written permission.
	//
	// THIS SOFTWARE IS PROVIDED BY THE PROJECT AND CONTRIBUTORS ``AS IS'' AND
	// ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
	// IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
	// ARE DISCLAIMED. IN NO EVENT SHALL THE PROJECT OR CONTRIBUTORS BE LIABLE
	// FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
	// DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
	// OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
	// HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
	// LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
	// OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
	// SUCH DAMAGE.
	//
	// dynamic_cast.cc: RTTI support.
	//
	// References:
	// Itanium C++ ABI at http://www.codesourcery.com/public/cxx-abi/abi.html
	// IHI0041A C++ Application Binary Interface for the ARM architecture.
	//

	#include <cxxabi.h>

	#include <cstddef>
	#include <cassert>

	namespace
	{
	// Adjust a pointer by an offset.

	const void*
	adjust_pointer(const void* p, std::ptrdiff_t off)
	{
	// FIXME: should we align pointer after adjustment?
	const char cp = reinterpret_cast<const char>(p) + off;
	return reinterpret_cast<const void*>(cp);
	}

	// Return the vtable pointer of a polymorphic object pointed by p.

	inline const void*
	get_vtable(const void* p)
	{
	return reinterpret_cast<voidconst*>(p);
	}

	// Return a pointer to a __class_type_info in a vtable.

	inline const abi::__class_type_info*
	get_class_type_info(const void* vtable)
	{
	const void* type_info_ptr = adjust_pointer(vtable, -sizeof(void*));
	return reinterpret_cast<abi::__class_type_infoconst*>(type_info_ptr);
	}

	// Return offset to object in a vtable.

	inline std::ptrdiff_t
	get_offset_to_top(const void* vtable)
	{
	const void* type_info_ptr_address = adjust_pointer(vtable, -sizeof(void*));
	const void* offset_to_top_address =
	adjust_pointer(type_info_ptr_address, -sizeof(std::ptrdiff_t));
	return reinterpret_cast<const std::ptrdiff_t>(offset_to_top_address);
	}

	// Return the virtual pointer to the most derived object of referred by a
	// pointer p.

	const void*
	get_most_derived_object(const void* p)
	{
	const void* vtable = get_vtable(p);
	std::ptrdiff_t offset_to_top = get_offset_to_top(vtable);
	return adjust_pointer(p, offset_to_top);
	}

	// We assume that -1 cannot be a valid pointer to object.
	const void * const ambiguous_object =
	reinterpret_cast<const void*>(-1);

	// Return a pointer to the subobject described by base_info.

	const void*
	get_subobject(const void* object,
	const void* vtable,
	const abi::__base_class_type_info* base_info)
	{
	long offset = base_info->offset();
	if (base_info->is_virtual())
	{
	const std::ptrdiff_t* virtual_base_offset_address =
	static_cast<const std::ptrdiff_t*> (adjust_pointer(vtable, offset));
	offset = *virtual_base_offset_address;
	}
	return adjust_pointer(object, offset);
	}

	// Helper of __dyanmic_cast to walk the type tree of an object.

	const void *
	walk_object(const void *object,
	const abi::__class_type_info *type,
	const void *match_object,
	const abi::__class_type_info *match_type)
	{
	if (type == match_type)
	return (match_object == NULL \|\| object == match_object) ? object : NULL;

	switch(type->code())
	{
	case abi::__class_type_info::CLASS_TYPE_INFO_CODE:
	// This isn't not the class you're looking for.
	return NULL;

	case abi::__class_type_info::SI_CLASS_TYPE_INFO_CODE:
	// derived type has a single public base at offset 0.
	{
	const abi::__si_class_type_info* ti =
	static_cast<const abi::__si_class_type_info*>(type);
	return walk_object(object, ti->__base_type, match_object,
	match_type);
	}

	case abi::__class_type_info::VMI_CLASS_TYPE_INFO_CODE:
	{
	const void* vtable = get_vtable(object);
	const abi::__vmi_class_type_info* ti =
	static_cast<const abi::__vmi_class_type_info*>(type);

	// Look at all direct bases.
	const void* result = NULL;
	for (unsigned i = 0; i < ti->__base_count; ++i)
	{
	if (!ti->__base_info[i].is_public())
	continue;

	const void *subobject =
	get_subobject(object, vtable, &ti->__base_info[i]);
	const void* walk_subobject_result =
	walk_object(subobject, ti->__base_info[i].__base_type,
	match_object, match_type);

	if (walk_subobject_result == ambiguous_object)
	return ambiguous_object;
	else if (walk_subobject_result != NULL)
	{
	if (result == NULL)
	{
	result = walk_subobject_result;
	}
	else if (result != walk_subobject_result)
	return ambiguous_object;
	}
	}
	return result;
	}

	default:
	assert(0);
	}
	return NULL;
	}

	// Bookkeeping structure for derived-to-base cast in the general case.
	struct cast_context
	{
	public:
	const void* object;
	const abi::__class_type_info *src_type;
	const abi::__class_type_info *dst_type;
	std::ptrdiff_t src2dst_offset;

	const void* dst_object;
	const void* result;

	cast_context(const void* obj, const abi::__class_type_info *src,
	const abi::__class_type_info *dst, std::ptrdiff_t offset)
	: object(obj), src_type(src), dst_type(dst), src2dst_offset(offset),
	dst_object(NULL), result(NULL)
	{ }
	};

	// based-to-derive cast in the general case.

	void
	base_to_derived_cast(const void *object,
	const abi::__class_type_info *type,
	cast_context* context)
	{
	const void* saved_dst_object = context->dst_object;
	bool is_dst_type = type == context->dst_type;
	if (is_dst_type)
	context->dst_object = object;

	if (object == context->object
	&& context->dst_object != NULL
	&& type == context->src_type)
	{
	if (context->result == NULL)
	context->result = context->dst_object;
	else if (context->result != context->dst_object)
	context->result = ambiguous_object;
	context->dst_object = saved_dst_object;
	return;
	}

	switch(type->code())
	{
	case abi::__class_type_info::CLASS_TYPE_INFO_CODE:
	// This isn't not the class you're looking for.
	break;

	case abi::__class_type_info::SI_CLASS_TYPE_INFO_CODE:
	// derived type has a single public base at offset 0.
	{
	const abi::__si_class_type_info* ti =
	static_cast<const abi::__si_class_type_info*>(type);
	base_to_derived_cast(object, ti->__base_type, context);
	break;
	}

	case abi::__class_type_info::VMI_CLASS_TYPE_INFO_CODE:
	{
	const void* vtable = get_vtable(object);
	const abi::__vmi_class_type_info* ti =
	static_cast<const abi::__vmi_class_type_info*>(type);

	// Look at all direct bases.
	for (unsigned i = 0; i < ti->__base_count; ++i)
	{
	if (!ti->__base_info[i].is_public())
	continue;

	const void *subobject =
	get_subobject(object, vtable, &ti->__base_info[i]);
	base_to_derived_cast(subobject, ti->__base_info[i].__base_type,
	context);

	// FIXME: Use flags in base_info to optimize search.
	if (context->result == ambiguous_object)
	break;
	}
	break;
	}

	default:
	assert(0);
	}
	context->dst_object = saved_dst_object;
	}
	} // namespace

	namespace __cxxabiv1
	{
	#define DYNAMIC_CAST_NO_HINT -1
	#define DYNAMIC_CAST_NOT_PUBLIC_BASE -2
	#define DYNAMIC_CAST_MULTIPLE_PUBLIC_NONVIRTUAL_BASE -3

	/* v: source address to be adjusted; nonnull, and since the
	* source object is polymorphic, (void*)v is a virtual pointer.
	* src: static type of the source object.
	* dst: 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: src is not a public base of dst
	* -3: src is a multiple public base type but never a
	* virtual base type
	* otherwise, the src type is a unique public nonvirtual
	* base type of dst at offset src2dst_offset from the
	* origin of dst.
	*/
	extern "C" void*
	__dynamic_cast (const void *v,
	const abi::__class_type_info *src,
	const abi::__class_type_info *dst,
	std::ptrdiff_t src2dst_offset)
	{
	const void* most_derived_object = get_most_derived_object(v);
	const void* vtable = get_vtable(most_derived_object);
	const abi::__class_type_info* most_derived_class_type_info =
	get_class_type_info(vtable);

	// If T is not a public base type of the most derived class referred
	// by v, the cast always fails.
	void* t_object =
	const_cast<void*>(walk_object(most_derived_object,
	most_derived_class_type_info, NULL, dst));
	if (t_object == NULL)
	return NULL;

	// C++ ABI 2.9.7 The dynamic_cast Algorithm:
	//
	// If, in the most derived object pointed (referred) to by v, v points
	// (refers) to a public base class subobject of a T object [note: this can
	// be checked at compile time], and if only one object of type T is derived
	// from the subobject pointed (referred) to by v, the result is a pointer
	// (an lvalue referring) to that T object.

	// We knew that src is not a public base, so base-to-derived cast
	// is not possible. This works even if there are multiple subobjects
	// of type T in the most derived object.
	if (src2dst_offset != DYNAMIC_CAST_NOT_PUBLIC_BASE)
	{
	// If it is known that v points to a public base class subobject
	// of a T object, simply adjust the pointer by the offset.
	if (t_object != ambiguous_object && src2dst_offset >= 0)
	return const_cast<void*>(adjust_pointer(v, src2dst_offset));

	// If there is only one T type subobject, we only need to look at
	// there. Otherwise, look for the subobject referred by v in the
	// most derived object.
	cast_context context(v, src, dst, src2dst_offset);
	if (t_object != ambiguous_object)
	base_to_derived_cast(t_object, dst, &context);
	else
	base_to_derived_cast(most_derived_object,
	most_derived_class_type_info, &context);

	if (context.result != NULL && context.result != ambiguous_object)
	return const_cast<void*>(context.result);
	}

	// C++ ABI 2.9.7 The dynamic_cast Algorithm:
	//
	// Otherwise, if v points (refers) to a public base class subobject of the
	// most derived object, and the type of the most derived object has an
	// unambiguous public base class of type T, the result is a pointer (an
	// lvalue referring) to the T subobject of the most derived object.
	// Otherwise, the run-time check fails.

	// Check to see if T is a unambiguous public base class.
	if (t_object == ambiguous_object)
	return NULL;

	// See if v refers to a public base class subobject.
	const void* v_object =
	walk_object(most_derived_object, most_derived_class_type_info, v, src);
	return v_object == v ? t_object : NULL;
	}
	} // namespace __cxxabiv1