1/*
2 * Copyright (C) 2008 The Android Open Source Project
3 *
4 * Licensed under the Apache License, Version 2.0 (the "License");
5 * you may not use this file except in compliance with the License.
6 * You may obtain a copy of the License at
7 *
8 *      http://www.apache.org/licenses/LICENSE-2.0
9 *
10 * Unless required by applicable law or agreed to in writing, software
11 * distributed under the License is distributed on an "AS IS" BASIS,
12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13 * See the License for the specific language governing permissions and
14 * limitations under the License.
15 */
16/*
17 * instanceof, checkcast, etc.
18 */
19#include "Dalvik.h"
20
21#include <stdlib.h>
22
23/*
24 * I think modern C mandates that the results of a boolean expression are
25 * 0 or 1.  If not, or we suddenly turn into C++ and bool != int, use this.
26 */
27#define BOOL_TO_INT(x)  (x)
28//#define BOOL_TO_INT(x)  ((x) ? 1 : 0)
29
30/*
31 * Number of entries in instanceof cache.  MUST be a power of 2.
32 */
33#define INSTANCEOF_CACHE_SIZE   1024
34
35
36/*
37 * Allocate cache.
38 */
39bool dvmInstanceofStartup()
40{
41    gDvm.instanceofCache = dvmAllocAtomicCache(INSTANCEOF_CACHE_SIZE);
42    if (gDvm.instanceofCache == NULL)
43        return false;
44    return true;
45}
46
47/*
48 * Discard the cache.
49 */
50void dvmInstanceofShutdown()
51{
52    dvmFreeAtomicCache(gDvm.instanceofCache);
53}
54
55
56/*
57 * Determine whether "sub" is an instance of "clazz", where both of these
58 * are array classes.
59 *
60 * Consider an array class, e.g. Y[][], where Y is a subclass of X.
61 *   Y[][] instanceof Y[][]        --> true (identity)
62 *   Y[][] instanceof X[][]        --> true (element superclass)
63 *   Y[][] instanceof Y            --> false
64 *   Y[][] instanceof Y[]          --> false
65 *   Y[][] instanceof Object       --> true (everything is an object)
66 *   Y[][] instanceof Object[]     --> true
67 *   Y[][] instanceof Object[][]   --> true
68 *   Y[][] instanceof Object[][][] --> false (too many []s)
69 *   Y[][] instanceof Serializable     --> true (all arrays are Serializable)
70 *   Y[][] instanceof Serializable[]   --> true
71 *   Y[][] instanceof Serializable[][] --> false (unless Y is Serializable)
72 *
73 * Don't forget about primitive types.
74 *   int[] instanceof Object[]     --> false
75 *
76 * "subElemClass" is sub->elementClass.
77 *
78 * "subDim" is usually just sub->dim, but for some kinds of checks we want
79 * to pass in a non-array class and pretend that it's an array.
80 */
81static int isArrayInstanceOfArray(const ClassObject* subElemClass, int subDim,
82    const ClassObject* clazz)
83{
84    //assert(dvmIsArrayClass(sub));
85    assert(dvmIsArrayClass(clazz));
86
87    /* "If T is an array type TC[]... one of the following must be true:
88     *   TC and SC are the same primitive type.
89     *   TC and SC are reference types and type SC can be cast to TC [...]."
90     *
91     * We need the class objects for the array elements.  For speed we
92     * tucked them into the class object.
93     */
94    assert(subDim > 0 && clazz->arrayDim > 0);
95    if (subDim == clazz->arrayDim) {
96        /*
97         * See if "sub" is an instance of "clazz".  This handles the
98         * interfaces, java.lang.Object, superclassing, etc.
99         */
100        return dvmInstanceof(subElemClass, clazz->elementClass);
101    } else if (subDim > clazz->arrayDim) {
102        /*
103         * The thing we might be an instance of has fewer dimensions.  It
104         * must be an Object or array of Object, or a standard array
105         * interface or array of standard array interfaces (the standard
106         * interfaces being java/lang/Cloneable and java/io/Serializable).
107         */
108        if (dvmIsInterfaceClass(clazz->elementClass)) {
109            /*
110             * See if the class implements its base element.  We know the
111             * base element is an interface; if the array class implements
112             * it, we know it's a standard array interface.
113             */
114            return dvmImplements(clazz, clazz->elementClass);
115        } else {
116            /*
117             * See if this is an array of Object, Object[], etc.  We know
118             * that the superclass of an array is always Object, so we
119             * just compare the element type to that.
120             */
121            return (clazz->elementClass == clazz->super);
122        }
123    } else {
124        /*
125         * Too many []s.
126         */
127        return false;
128    }
129}
130
131/*
132 * Determine whether "sub" is a sub-class of "clazz", where "sub" is an
133 * array class.
134 *
135 * "clazz" could be an array class, interface, or simple class.
136 */
137static int isArrayInstanceOf(const ClassObject* sub, const ClassObject* clazz)
138{
139    assert(dvmIsArrayClass(sub));
140
141    /* "If T is an interface type, T must be one of the interfaces
142     * implemented by arrays."
143     *
144     * I'm not checking that here, because dvmInstanceof tests for
145     * interfaces first, and the generic dvmImplements stuff should
146     * work correctly.
147     */
148    assert(!dvmIsInterfaceClass(clazz));     /* make sure */
149
150    /* "If T is a class type, then T must be Object."
151     *
152     * The superclass of an array is always java.lang.Object, so just
153     * compare against that.
154     */
155    if (!dvmIsArrayClass(clazz))
156        return BOOL_TO_INT(clazz == sub->super);
157
158    /*
159     * If T is an array type TC[] ...
160     */
161    return isArrayInstanceOfArray(sub->elementClass, sub->arrayDim, clazz);
162}
163
164
165/*
166 * Returns 1 (true) if "clazz" is an implementation of "interface".
167 *
168 * "clazz" could be a class or an interface.
169 */
170int dvmImplements(const ClassObject* clazz, const ClassObject* interface)
171{
172    int i;
173
174    assert(dvmIsInterfaceClass(interface));
175
176    /*
177     * All interfaces implemented directly and by our superclass, and
178     * recursively all super-interfaces of those interfaces, are listed
179     * in "iftable", so we can just do a linear scan through that.
180     */
181    for (i = 0; i < clazz->iftableCount; i++) {
182        if (clazz->iftable[i].clazz == interface)
183            return 1;
184    }
185
186    return 0;
187}
188
189/*
190 * Determine whether or not we can put an object into an array, based on
191 * the class hierarchy.  The object might itself by an array, which means
192 * we have to pay attention to the array instanceof rules.
193 *
194 * Note that "objectClass" could be an array, but objectClass->elementClass
195 * is always a non-array type.
196 */
197bool dvmCanPutArrayElement(const ClassObject* objectClass,
198    const ClassObject* arrayClass)
199{
200    if (dvmIsArrayClass(objectClass)) {
201        /*
202         * We're stuffing an array into an array.  We want to see if the
203         * elements of "arrayClass" are compatible with "objectClass".
204         * We bump up the number of dimensions in "objectClass" so that we
205         * can compare the two directly.
206         */
207        return isArrayInstanceOfArray(objectClass->elementClass,
208                    objectClass->arrayDim + 1, arrayClass);
209    } else {
210        /*
211         * We're putting a non-array element into an array.  We need to
212         * test to see if the elements are compatible.  The easiest way
213         * to do that is to "arrayify" it and use the standard array
214         * compatibility check.
215         */
216        return isArrayInstanceOfArray(objectClass, 1, arrayClass);
217    }
218}
219
220
221/*
222 * Perform the instanceof calculation.
223 */
224static inline int isInstanceof(const ClassObject* instance,
225    const ClassObject* clazz)
226{
227    if (dvmIsInterfaceClass(clazz)) {
228        return dvmImplements(instance, clazz);
229    } else if (dvmIsArrayClass(instance)) {
230        return isArrayInstanceOf(instance, clazz);
231    } else {
232        return dvmIsSubClass(instance, clazz);
233    }
234}
235
236
237/*
238 * Do the instanceof calculation, pulling the result from the cache if
239 * possible.
240 */
241int dvmInstanceofNonTrivial(const ClassObject* instance,
242    const ClassObject* clazz)
243{
244#define ATOMIC_CACHE_CALC isInstanceof(instance, clazz)
245#define ATOMIC_CACHE_NULL_ALLOWED true
246    return ATOMIC_CACHE_LOOKUP(gDvm.instanceofCache,
247                INSTANCEOF_CACHE_SIZE, instance, clazz);
248#undef ATOMIC_CACHE_CALC
249}
250