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 
17 package com.android.dx.cf.code;
18 
19 import com.android.dx.rop.type.Type;
20 import com.android.dx.rop.type.TypeBearer;
21 import com.android.dx.util.Hex;
22 
23 /**
24  * Utility methods to merge various frame information.
25  */
26 public final class Merger {
27     /**
28      * This class is uninstantiable.
29      */
Merger()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      */
mergeLocals(OneLocalsArray locals1, OneLocalsArray locals2)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      */
mergeStack(ExecutionStack stack1, ExecutionStack stack2)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      */
mergeType(TypeBearer ft1, TypeBearer ft2)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      */
isPossiblyAssignableFrom(TypeBearer supertypeBearer, TypeBearer subtypeBearer)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