Merger.java revision de75089fb7216d19e9c22cce4dc62a49513477d3 
1/*
2 * Copyright (C) 2007 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
17package com.android.dx.cf.code;
18
19import com.android.dx.rop.type.Type;
20import com.android.dx.rop.type.TypeBearer;
21import com.android.dx.util.Hex;
22
23/**
24 * Utility methods to merge various frame information.
25 */
26public final class Merger {
27    /**
28     * This class is uninstantiable.
29     */
30    private Merger() {
31        // This space intentionally left blank.
32    }
33
34    /**
35     * Merges two locals arrays. If the merged result is the same as the first
36     * argument, then return the first argument (not a copy).
37     *
38     * @param locals1 {@code non-null;} a locals array
39     * @param locals2 {@code non-null;} another locals array
40     * @return {@code non-null;} the result of merging the two locals arrays
41     */
42    public static OneLocalsArray mergeLocals(OneLocalsArray locals1,
43                                          OneLocalsArray locals2) {
44        if (locals1 == locals2) {
45            // Easy out.
46            return locals1;
47        }
48
49        int sz = locals1.getMaxLocals();
50        OneLocalsArray result = null;
51
52        if (locals2.getMaxLocals() != sz) {
53            throw new SimException("mismatched maxLocals values");
54        }
55
56        for (int i = 0; i < sz; i++) {
57            TypeBearer tb1 = locals1.getOrNull(i);
58            TypeBearer tb2 = locals2.getOrNull(i);
59            TypeBearer resultType = mergeType(tb1, tb2);
60            if (resultType != tb1) {
61                /*
62                 * We only need to do anything when the result differs
63                 * from what is in the first array, since that's what the
64                 * result gets initialized to.
65                 */
66                if (result == null) {
67                    result = locals1.copy();
68                }
69
70                if (resultType == null) {
71                    result.invalidate(i);
72                } else {
73                    result.set(i, resultType);
74                }
75            }
76        }
77
78        if (result == null) {
79            return locals1;
80        }
81
82        result.setImmutable();
83        return result;
84    }
85
86    /**
87     * Merges two stacks. If the merged result is the same as the first
88     * argument, then return the first argument (not a copy).
89     *
90     * @param stack1 {@code non-null;} a stack
91     * @param stack2 {@code non-null;} another stack
92     * @return {@code non-null;} the result of merging the two stacks
93     */
94    public static ExecutionStack mergeStack(ExecutionStack stack1,
95                                            ExecutionStack stack2) {
96        if (stack1 == stack2) {
97            // Easy out.
98            return stack1;
99        }
100
101        int sz = stack1.size();
102        ExecutionStack result = null;
103
104        if (stack2.size() != sz) {
105            throw new SimException("mismatched stack depths");
106        }
107
108        for (int i = 0; i < sz; i++) {
109            TypeBearer tb1 = stack1.peek(i);
110            TypeBearer tb2 = stack2.peek(i);
111            TypeBearer resultType = mergeType(tb1, tb2);
112            if (resultType != tb1) {
113                /*
114                 * We only need to do anything when the result differs
115                 * from what is in the first stack, since that's what the
116                 * result gets initialized to.
117                 */
118                if (result == null) {
119                    result = stack1.copy();
120                }
121
122                try {
123                    if (resultType == null) {
124                        throw new SimException("incompatible: " + tb1 + ", " +
125                                               tb2);
126                    } else {
127                        result.change(i, resultType);
128                    }
129                } catch (SimException ex) {
130                    ex.addContext("...while merging stack[" + Hex.u2(i) + "]");
131                    throw ex;
132                }
133            }
134        }
135
136        if (result == null) {
137            return stack1;
138        }
139
140        result.setImmutable();
141        return result;
142    }
143
144    /**
145     * Merges two frame types.
146     *
147     * @param ft1 {@code non-null;} a frame type
148     * @param ft2 {@code non-null;} another frame type
149     * @return {@code non-null;} the result of merging the two types
150     */
151    public static TypeBearer mergeType(TypeBearer ft1, TypeBearer ft2) {
152        if ((ft1 == null) || ft1.equals(ft2)) {
153            return ft1;
154        } else if (ft2 == null) {
155            return null;
156        } else {
157            Type type1 = ft1.getType();
158            Type type2 = ft2.getType();
159
160            if (type1 == type2) {
161                return type1;
162            } else if (type1.isReference() && type2.isReference()) {
163                if (type1 == Type.KNOWN_NULL) {
164                    /*
165                     * A known-null merges with any other reference type to
166                     * be that reference type.
167                     */
168                    return type2;
169                } else if (type2 == Type.KNOWN_NULL) {
170                    /*
171                     * The same as above, but this time it's type2 that's
172                     * the known-null.
173                     */
174                    return type1;
175                } else if (type1.isArray() && type2.isArray()) {
176                    TypeBearer componentUnion =
177                        mergeType(type1.getComponentType(),
178                                type2.getComponentType());
179                    if (componentUnion == null) {
180                        /*
181                         * At least one of the types is a primitive type,
182                         * so the merged result is just Object.
183                         */
184                        return Type.OBJECT;
185                    }
186                    return ((Type) componentUnion).getArrayType();
187                } else {
188                    /*
189                     * All other unequal reference types get merged to be
190                     * Object in this phase. This is fine here, but it
191                     * won't be the right thing to do in the verifier.
192                     */
193                    return Type.OBJECT;
194                }
195            } else if (type1.isIntlike() && type2.isIntlike()) {
196                /*
197                 * Merging two non-identical int-like types results in
198                 * the type int.
199                 */
200                return Type.INT;
201            } else {
202                return null;
203            }
204        }
205    }
206
207    /**
208     * Returns whether the given supertype is possibly assignable from
209     * the given subtype. This takes into account primitiveness,
210     * int-likeness, known-nullness, and array dimensions, but does
211     * not assume anything about class hierarchy other than that the
212     * type {@code Object} is the supertype of all reference
213     * types and all arrays are assignable to
214     * {@code Serializable} and {@code Cloneable}.
215     *
216     * @param supertypeBearer {@code non-null;} the supertype
217     * @param subtypeBearer {@code non-null;} the subtype
218     */
219    public static boolean isPossiblyAssignableFrom(TypeBearer supertypeBearer,
220            TypeBearer subtypeBearer) {
221        Type supertype = supertypeBearer.getType();
222        Type subtype = subtypeBearer.getType();
223
224        if (supertype.equals(subtype)) {
225            // Easy out.
226            return true;
227        }
228
229        int superBt = supertype.getBasicType();
230        int subBt = subtype.getBasicType();
231
232        // Treat return types as Object for the purposes of this method.
233
234        if (superBt == Type.BT_ADDR) {
235            supertype = Type.OBJECT;
236            superBt = Type.BT_OBJECT;
237        }
238
239        if (subBt == Type.BT_ADDR) {
240            subtype = Type.OBJECT;
241            subBt = Type.BT_OBJECT;
242        }
243
244        if ((superBt != Type.BT_OBJECT) || (subBt != Type.BT_OBJECT)) {
245            /*
246             * No two distinct primitive types are assignable in this sense,
247             * unless they are both int-like.
248             */
249            return supertype.isIntlike() && subtype.isIntlike();
250        }
251
252        // At this point, we know both types are reference types.
253
254        if (supertype == Type.KNOWN_NULL) {
255            /*
256             * A known-null supertype is only assignable from another
257             * known-null (handled in the easy out at the top of the
258             * method).
259             */
260            return false;
261        } else if (subtype == Type.KNOWN_NULL) {
262            /*
263             * A known-null subtype is in fact assignable to any
264             * reference type.
265             */
266            return true;
267        } else if (supertype == Type.OBJECT) {
268            /*
269             * Object is assignable from any reference type.
270             */
271            return true;
272        } else if (supertype.isArray()) {
273            // The supertype is an array type.
274            if (! subtype.isArray()) {
275                // The subtype isn't an array, and so can't be assignable.
276                return false;
277            }
278
279            /*
280             * Strip off as many matched component types from both
281             * types as possible, and check the assignability of the
282             * results.
283             */
284            do {
285                supertype = supertype.getComponentType();
286                subtype = subtype.getComponentType();
287            } while (supertype.isArray() && subtype.isArray());
288
289            return isPossiblyAssignableFrom(supertype, subtype);
290        } else if (subtype.isArray()) {
291            /*
292             * Other than Object (handled above), array types are
293             * assignable only to Serializable and Cloneable.
294             */
295            return (supertype == Type.SERIALIZABLE) ||
296                (supertype == Type.CLONEABLE);
297        } else {
298            /*
299             * All other unequal reference types are considered at
300             * least possibly assignable.
301             */
302            return true;
303        }
304    }
305}
306