1// Copyright (C) 2011 The Android Open Source Project
2// All rights reserved.
3//
4// Redistribution and use in source and binary forms, with or without
5// modification, are permitted provided that the following conditions
6// are met:
7// 1. Redistributions of source code must retain the above copyright
8//    notice, this list of conditions and the following disclaimer.
9// 2. Redistributions in binary form must reproduce the above copyright
10//    notice, this list of conditions and the following disclaimer in the
11//    documentation and/or other materials provided with the distribution.
12// 3. Neither the name of the project nor the names of its contributors
13//    may be used to endorse or promote products derived from this software
14//    without specific prior written permission.
15//
16// THIS SOFTWARE IS PROVIDED BY THE PROJECT AND CONTRIBUTORS ``AS IS'' AND
17// ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
18// IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
19// ARE DISCLAIMED.  IN NO EVENT SHALL THE PROJECT OR CONTRIBUTORS BE LIABLE
20// FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
21// DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
22// OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
23// HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
24// LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
25// OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
26// SUCH DAMAGE.
27//
28// dynamic_cast.cc: RTTI support.
29//
30// References:
31// Itanium C++ ABI at http://www.codesourcery.com/public/cxx-abi/abi.html
32// IHI0041A C++ Application Binary Interface for the ARM architecture.
33//
34
35#include "cxxabi_defines.h"
36
37#include <cstddef>
38#include <cassert>
39
40namespace
41{
42  // Adjust a pointer by an offset.
43
44  const void*
45  adjust_pointer(const void* p, std::ptrdiff_t off)
46  {
47    // FIXME: should we align pointer after adjustment?
48    const char *cp = reinterpret_cast<const char*>(p) + off;
49    return reinterpret_cast<const void*>(cp);
50  }
51
52  // Return the vtable pointer of a polymorphic object pointed by p.
53
54  inline const void*
55  get_vtable(const void* p)
56  {
57    return *reinterpret_cast<void*const*>(p);
58  }
59
60  // Return a pointer to a __class_type_info in a vtable.
61
62  inline const abi::__class_type_info*
63  get_class_type_info(const void* vtable)
64  {
65    const void* type_info_ptr = adjust_pointer(vtable, -sizeof(void*));
66    return *reinterpret_cast<abi::__class_type_info*const*>(type_info_ptr);
67  }
68
69  // Return offset to object in a vtable.
70
71  inline std::ptrdiff_t
72  get_offset_to_top(const void* vtable)
73  {
74    const void* type_info_ptr_address = adjust_pointer(vtable, -sizeof(void*));
75    const void* offset_to_top_address =
76      adjust_pointer(type_info_ptr_address, -sizeof(std::ptrdiff_t));
77    return *reinterpret_cast<const std::ptrdiff_t*>(offset_to_top_address);
78  }
79
80  // Return the virtual pointer to the most derived object of referred by a
81  // pointer p.
82
83  const void*
84  get_most_derived_object(const void* p)
85  {
86    const void* vtable = get_vtable(p);
87    std::ptrdiff_t offset_to_top = get_offset_to_top(vtable);
88    return adjust_pointer(p, offset_to_top);
89  }
90
91  // We assume that -1 cannot be a valid pointer to object.
92  const void * const ambiguous_object =
93    reinterpret_cast<const void*>(-1);
94
95  // Return a pointer to the subobject described by base_info.
96
97  const void*
98  get_subobject(const void* object,
99                const void* vtable,
100                const abi::__base_class_type_info* base_info)
101  {
102    long offset = base_info->offset();
103    if (base_info->is_virtual())
104      {
105        const std::ptrdiff_t* virtual_base_offset_address =
106          static_cast<const std::ptrdiff_t*> (adjust_pointer(vtable, offset));
107        offset = *virtual_base_offset_address;
108      }
109    return adjust_pointer(object, offset);
110  }
111
112  // Helper of __dyanmic_cast to walk the type tree of an object.
113
114  const void *
115  walk_object(const void *object,
116              const abi::__class_type_info *type,
117              const void *match_object,
118              const abi::__class_type_info *match_type)
119  {
120    if (*type == *match_type)
121      return (match_object == NULL || object == match_object) ? object : NULL;
122
123    switch(type->code())
124      {
125      case abi::__class_type_info::CLASS_TYPE_INFO_CODE:
126        // This isn't not the class you're looking for.
127        return NULL;
128
129      case abi::__class_type_info::SI_CLASS_TYPE_INFO_CODE:
130        // derived type has a single public base at offset 0.
131        {
132          const abi::__si_class_type_info* ti =
133            static_cast<const abi::__si_class_type_info*>(type);
134          return walk_object(object, ti->__base_type, match_object,
135                             match_type);
136        }
137
138      case abi::__class_type_info::VMI_CLASS_TYPE_INFO_CODE:
139        {
140          const void* vtable = get_vtable(object);
141          const abi::__vmi_class_type_info* ti =
142            static_cast<const abi::__vmi_class_type_info*>(type);
143
144          // Look at all direct bases.
145          const void* result = NULL;
146          for (unsigned i = 0; i < ti->__base_count; ++i)
147            {
148              if (!ti->__base_info[i].is_public())
149                continue;
150
151              const void *subobject =
152                get_subobject(object, vtable, &ti->__base_info[i]);
153              const void* walk_subobject_result =
154                walk_object(subobject, ti->__base_info[i].__base_type,
155                            match_object, match_type);
156
157              if (walk_subobject_result == ambiguous_object)
158                return ambiguous_object;
159              else if (walk_subobject_result != NULL)
160                {
161                  if (result == NULL)
162                    {
163                      result = walk_subobject_result;
164                    }
165                  else if (result != walk_subobject_result)
166                    return ambiguous_object;
167                }
168            }
169          return result;
170        }
171
172      default:
173        assert(0);
174      }
175    return NULL;
176  }
177
178  // Bookkeeping structure for derived-to-base cast in the general case.
179  struct cast_context
180  {
181  public:
182    const void* object;
183    const abi::__class_type_info *src_type;
184    const abi::__class_type_info *dst_type;
185    std::ptrdiff_t src2dst_offset;
186
187    const void* dst_object;
188    const void* result;
189
190    cast_context(const void* obj, const abi::__class_type_info *src,
191                 const abi::__class_type_info *dst, std::ptrdiff_t offset)
192      : object(obj), src_type(src), dst_type(dst), src2dst_offset(offset),
193        dst_object(NULL), result(NULL)
194    { }
195  };
196
197  // based-to-derive cast in the general case.
198
199  void
200  base_to_derived_cast(const void *object,
201                       const abi::__class_type_info *type,
202                       cast_context* context)
203  {
204    const void* saved_dst_object = context->dst_object;
205    bool is_dst_type = *type == *context->dst_type;
206    if (is_dst_type)
207      context->dst_object = object;
208
209    if (object == context->object
210        && context->dst_object != NULL
211        && *type == *context->src_type)
212      {
213        if (context->result == NULL)
214          context->result = context->dst_object;
215        else if (context->result != context->dst_object)
216          context->result = ambiguous_object;
217        context->dst_object = saved_dst_object;
218        return;
219      }
220
221    switch(type->code())
222      {
223      case abi::__class_type_info::CLASS_TYPE_INFO_CODE:
224        // This isn't not the class you're looking for.
225        break;
226
227      case abi::__class_type_info::SI_CLASS_TYPE_INFO_CODE:
228        // derived type has a single public base at offset 0.
229        {
230          const abi::__si_class_type_info* ti =
231            static_cast<const abi::__si_class_type_info*>(type);
232          base_to_derived_cast(object, ti->__base_type, context);
233          break;
234        }
235
236      case abi::__class_type_info::VMI_CLASS_TYPE_INFO_CODE:
237        {
238          const void* vtable = get_vtable(object);
239          const abi::__vmi_class_type_info* ti =
240            static_cast<const abi::__vmi_class_type_info*>(type);
241
242          // Look at all direct bases.
243          for (unsigned i = 0; i < ti->__base_count; ++i)
244            {
245              if (!ti->__base_info[i].is_public())
246                continue;
247
248              const void *subobject =
249                get_subobject(object, vtable, &ti->__base_info[i]);
250              base_to_derived_cast(subobject, ti->__base_info[i].__base_type,
251                                   context);
252
253              // FIXME: Use flags in base_info to optimize search.
254              if (context->result == ambiguous_object)
255                break;
256            }
257          break;
258        }
259
260      default:
261        assert(0);
262      }
263     context->dst_object = saved_dst_object;
264  }
265} // namespace
266
267namespace __cxxabiv1
268{
269#define DYNAMIC_CAST_NO_HINT -1
270#define DYNAMIC_CAST_NOT_PUBLIC_BASE -2
271#define DYNAMIC_CAST_MULTIPLE_PUBLIC_NONVIRTUAL_BASE -3
272
273  /* v: source address to be adjusted; nonnull, and since the
274   *    source object is polymorphic, *(void**)v is a virtual pointer.
275   * src: static type of the source object.
276   * dst: destination type (the "T" in "dynamic_cast<T>(v)").
277   * src2dst_offset: a static hint about the location of the
278   *    source subobject with respect to the complete object;
279   *    special negative values are:
280   *       -1: no hint
281   *       -2: src is not a public base of dst
282   *       -3: src is a multiple public base type but never a
283   *           virtual base type
284   *    otherwise, the src type is a unique public nonvirtual
285   *    base type of dst at offset src2dst_offset from the
286   *    origin of dst.
287   */
288  extern "C" void*
289  __dynamic_cast (const void *v,
290                  const abi::__class_type_info *src,
291                  const abi::__class_type_info *dst,
292                  std::ptrdiff_t src2dst_offset)
293  {
294    const void* most_derived_object = get_most_derived_object(v);
295    const void* vtable = get_vtable(most_derived_object);
296    const abi::__class_type_info* most_derived_class_type_info =
297      get_class_type_info(vtable);
298
299    // If T is not a public base type of the most derived class referred
300    // by v, the cast always fails.
301    void* t_object =
302      const_cast<void*>(walk_object(most_derived_object,
303                                    most_derived_class_type_info, NULL, dst));
304    if (t_object == NULL)
305      return NULL;
306
307    // C++ ABI 2.9.7 The dynamic_cast Algorithm:
308    //
309    // If, in the most derived object pointed (referred) to by v, v points
310    // (refers) to a public base class subobject of a T object [note: this can
311    // be checked at compile time], and if only one object of type T is derived
312    // from the subobject pointed (referred) to by v, the result is a pointer
313    // (an lvalue referring) to that T object.
314
315    // We knew that src is not a public base, so base-to-derived cast
316    // is not possible.  This works even if there are multiple subobjects
317    // of type T in the most derived object.
318    if (src2dst_offset != DYNAMIC_CAST_NOT_PUBLIC_BASE)
319      {
320        // If it is known that v points to a public base class subobject
321        // of a T object, simply adjust the pointer by the offset.
322        if (t_object != ambiguous_object && src2dst_offset >= 0)
323          return const_cast<void*>(adjust_pointer(v, -src2dst_offset));
324
325        // If there is only one T type subobject, we only need to look at
326        // there.  Otherwise, look for the subobject referred by v in the
327        // most derived object.
328        cast_context context(v, src, dst, src2dst_offset);
329        if (t_object != ambiguous_object)
330          base_to_derived_cast(t_object, dst, &context);
331        else
332          base_to_derived_cast(most_derived_object,
333                               most_derived_class_type_info, &context);
334
335        if (context.result != NULL && context.result != ambiguous_object)
336          return const_cast<void*>(context.result);
337      }
338
339    // C++ ABI 2.9.7 The dynamic_cast Algorithm:
340    //
341    // Otherwise, if v points (refers) to a public base class subobject of the
342    // most derived object, and the type of the most derived object has an
343    // unambiguous public base class of type T, the result is a pointer (an
344    // lvalue referring) to the T subobject of the most derived object.
345    // Otherwise, the run-time check fails.
346
347    // Check to see if T is a unambiguous public base class.
348    if (t_object == ambiguous_object)
349      return NULL;
350
351    // See if v refers to a public base class subobject.
352    const void* v_object =
353      walk_object(most_derived_object, most_derived_class_type_info, v, src);
354    return v_object == v ? t_object : NULL;
355  }
356} // namespace __cxxabiv1
357