1 /*
2  * Copyright 2013, Google Inc.
3  * All rights reserved.
4  *
5  * Redistribution and use in source and binary forms, with or without
6  * modification, are permitted provided that the following conditions are
7  * met:
8  *
9  *     * Redistributions of source code must retain the above copyright
10  * notice, this list of conditions and the following disclaimer.
11  *     * Redistributions in binary form must reproduce the above
12  * copyright notice, this list of conditions and the following disclaimer
13  * in the documentation and/or other materials provided with the
14  * distribution.
15  *     * Neither the name of Google Inc. nor the names of its
16  * contributors may be used to endorse or promote products derived from
17  * this software without specific prior written permission.
18  *
19  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
20  * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
21  * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
22  * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
23  * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
24  * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
25  * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
26  * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
27  * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
28  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
29  * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
30  */
31 
32 package org.jf.dexlib2.analysis;
33 
34 
35 import org.jf.util.ExceptionWithContext;
36 
37 import javax.annotation.Nonnull;
38 import javax.annotation.Nullable;
39 import java.io.IOException;
40 import java.io.Writer;
41 
42 public class RegisterType {
43     public final byte category;
44     @Nullable public final TypeProto type;
45 
RegisterType(byte category, @Nullable TypeProto type)46     private RegisterType(byte category, @Nullable TypeProto type) {
47         assert ((category == REFERENCE || category == UNINIT_REF || category == UNINIT_THIS) && type != null) ||
48                ((category != REFERENCE && category != UNINIT_REF && category != UNINIT_THIS) && type == null);
49 
50         this.category = category;
51         this.type = type;
52     }
53 
54     @Override
toString()55     public String toString() {
56         return "(" + CATEGORY_NAMES[category] + (type==null?"":("," + type)) + ")";
57     }
58 
writeTo(Writer writer)59     public void writeTo(Writer writer) throws IOException {
60         writer.write('(');
61         writer.write(CATEGORY_NAMES[category]);
62         if (type != null) {
63             writer.write(',');
64             writer.write(type.getType());
65         }
66         writer.write(')');
67     }
68 
69     @Override
equals(Object o)70     public boolean equals(Object o) {
71         if (this == o) return true;
72         if (o == null || getClass() != o.getClass()) return false;
73 
74         RegisterType that = (RegisterType) o;
75 
76         if (category != that.category) {
77             return false;
78         }
79 
80         // These require strict reference equality. Every instance represents a unique
81         // reference that can't be merged with a different one, even if they have the same type.
82         if (category == UNINIT_REF || category == UNINIT_THIS) {
83             return false;
84         }
85         return (type != null ? type.equals(that.type) : that.type == null);
86     }
87 
88     @Override
hashCode()89     public int hashCode() {
90         int result = category;
91         result = 31 * result + (type != null ? type.hashCode() : 0);
92         return result;
93     }
94 
95     // The Unknown category denotes a register type that hasn't been determined yet
96     public static final byte UNKNOWN = 0;
97     // The Uninit category is for registers that haven't been set yet. e.g. the non-parameter registers in a method
98     // start out as unint
99     public static final byte UNINIT = 1;
100     public static final byte NULL = 2;
101     public static final byte ONE = 3;
102     public static final byte BOOLEAN = 4;
103     public static final byte BYTE = 5;
104     public static final byte POS_BYTE = 6;
105     public static final byte SHORT = 7;
106     public static final byte POS_SHORT = 8;
107     public static final byte CHAR = 9;
108     public static final byte INTEGER = 10;
109     public static final byte FLOAT = 11;
110     public static final byte LONG_LO = 12;
111     public static final byte LONG_HI = 13;
112     public static final byte DOUBLE_LO = 14;
113     public static final byte DOUBLE_HI = 15;
114     // The UninitRef category is used after a new-instance operation, and before the corresponding <init> is called
115     public static final byte UNINIT_REF = 16;
116     // The UninitThis category is used the "this" register inside an <init> method, before the superclass' <init>
117     // method is called
118     public static final byte UNINIT_THIS = 17;
119     public static final byte REFERENCE = 18;
120     // This is used when there are multiple incoming execution paths that have incompatible register types. For
121     // example if the register's type is an Integer on one incoming code path, but is a Reference type on another
122     // incomming code path. There is no register type that can hold either an Integer or a Reference.
123     public static final byte CONFLICTED = 19;
124 
125     public static final String[] CATEGORY_NAMES = new String[] {
126             "Unknown",
127             "Uninit",
128             "Null",
129             "One",
130             "Boolean",
131             "Byte",
132             "PosByte",
133             "Short",
134             "PosShort",
135             "Char",
136             "Integer",
137             "Float",
138             "LongLo",
139             "LongHi",
140             "DoubleLo",
141             "DoubleHi",
142             "UninitRef",
143             "UninitThis",
144             "Reference",
145             "Conflicted"
146     };
147 
148     //this table is used when merging register types. For example, if a particular register can be either a BYTE
149     //or a Char, then the "merged" type of that register would be Integer, because it is the "smallest" type can
150     //could hold either type of value.
151     protected static byte[][] mergeTable  =
152     {
153             /*              UNKNOWN      UNINIT      NULL        ONE,        BOOLEAN     BYTE        POS_BYTE    SHORT       POS_SHORT   CHAR        INTEGER,    FLOAT,      LONG_LO     LONG_HI     DOUBLE_LO   DOUBLE_HI   UNINIT_REF  UNINIT_THIS REFERENCE   CONFLICTED*/
154             /*UNKNOWN*/    {UNKNOWN,     UNINIT,     NULL,       ONE,        BOOLEAN,    BYTE,       POS_BYTE,   SHORT,      POS_SHORT,  CHAR,       INTEGER,    FLOAT,      LONG_LO,    LONG_HI,    DOUBLE_LO,  DOUBLE_HI,  UNINIT_REF, UNINIT_THIS,REFERENCE,  CONFLICTED},
155             /*UNINIT*/     {UNINIT,      UNINIT,     CONFLICTED, CONFLICTED, CONFLICTED, CONFLICTED, CONFLICTED, CONFLICTED, CONFLICTED, CONFLICTED, CONFLICTED, CONFLICTED, CONFLICTED, CONFLICTED, CONFLICTED, CONFLICTED, CONFLICTED, CONFLICTED, CONFLICTED, CONFLICTED},
156             /*NULL*/       {NULL,        CONFLICTED, NULL,       BOOLEAN,    BOOLEAN,    BYTE,       POS_BYTE,   SHORT,      POS_SHORT,  CHAR,       INTEGER,    FLOAT,      CONFLICTED, CONFLICTED, CONFLICTED, CONFLICTED, CONFLICTED, CONFLICTED, REFERENCE,  CONFLICTED},
157             /*ONE*/        {ONE,         CONFLICTED, BOOLEAN,    ONE,        BOOLEAN,    BYTE,       POS_BYTE,   SHORT,      POS_SHORT,  CHAR,       INTEGER,    FLOAT,      CONFLICTED, CONFLICTED, CONFLICTED, CONFLICTED, CONFLICTED, CONFLICTED, CONFLICTED, CONFLICTED},
158             /*BOOLEAN*/    {BOOLEAN,     CONFLICTED, BOOLEAN,    BOOLEAN,    BOOLEAN,    BYTE,       POS_BYTE,   SHORT,      POS_SHORT,  CHAR,       INTEGER,    FLOAT,      CONFLICTED, CONFLICTED, CONFLICTED, CONFLICTED, CONFLICTED, CONFLICTED, CONFLICTED, CONFLICTED},
159             /*BYTE*/       {BYTE,        CONFLICTED, BYTE,       BYTE,       BYTE,       BYTE,       BYTE,       SHORT,      SHORT,      INTEGER,    INTEGER,    FLOAT,      CONFLICTED, CONFLICTED, CONFLICTED, CONFLICTED, CONFLICTED, CONFLICTED, CONFLICTED, CONFLICTED},
160             /*POS_BYTE*/   {POS_BYTE,    CONFLICTED, POS_BYTE,   POS_BYTE,   POS_BYTE,   BYTE,       POS_BYTE,   SHORT,      POS_SHORT,  CHAR,       INTEGER,    FLOAT,      CONFLICTED, CONFLICTED, CONFLICTED, CONFLICTED, CONFLICTED, CONFLICTED, CONFLICTED, CONFLICTED},
161             /*SHORT*/      {SHORT,       CONFLICTED, SHORT,      SHORT,      SHORT,      SHORT,      SHORT,      SHORT,      SHORT,      INTEGER,    INTEGER,    FLOAT,      CONFLICTED, CONFLICTED, CONFLICTED, CONFLICTED, CONFLICTED, CONFLICTED, CONFLICTED, CONFLICTED},
162             /*POS_SHORT*/  {POS_SHORT,   CONFLICTED, POS_SHORT,  POS_SHORT,  POS_SHORT,  SHORT,      POS_SHORT,  SHORT,      POS_SHORT,  CHAR,       INTEGER,    FLOAT,      CONFLICTED, CONFLICTED, CONFLICTED, CONFLICTED, CONFLICTED, CONFLICTED, CONFLICTED, CONFLICTED},
163             /*CHAR*/       {CHAR,        CONFLICTED, CHAR,       CHAR,       CHAR,       INTEGER,    CHAR,       INTEGER,    CHAR,       CHAR,       INTEGER,    FLOAT,      CONFLICTED, CONFLICTED, CONFLICTED, CONFLICTED, CONFLICTED, CONFLICTED, CONFLICTED, CONFLICTED},
164             /*INTEGER*/    {INTEGER,     CONFLICTED, INTEGER,    INTEGER,    INTEGER,    INTEGER,    INTEGER,    INTEGER,    INTEGER,    INTEGER,    INTEGER,    INTEGER,    CONFLICTED, CONFLICTED, CONFLICTED, CONFLICTED, CONFLICTED, CONFLICTED, CONFLICTED, CONFLICTED},
165             /*FLOAT*/      {FLOAT,       CONFLICTED, FLOAT,      FLOAT,      FLOAT,      FLOAT,      FLOAT,      FLOAT,      FLOAT,      FLOAT,      INTEGER,    FLOAT,      CONFLICTED, CONFLICTED, CONFLICTED, CONFLICTED, CONFLICTED, CONFLICTED, CONFLICTED, CONFLICTED},
166             /*LONG_LO*/    {LONG_LO,     CONFLICTED, CONFLICTED, CONFLICTED, CONFLICTED, CONFLICTED, CONFLICTED, CONFLICTED, CONFLICTED, CONFLICTED, CONFLICTED, CONFLICTED, LONG_LO,    CONFLICTED, LONG_LO,    CONFLICTED, CONFLICTED, CONFLICTED, CONFLICTED, CONFLICTED},
167             /*LONG_HI*/    {LONG_HI,     CONFLICTED, CONFLICTED, CONFLICTED, CONFLICTED, CONFLICTED, CONFLICTED, CONFLICTED, CONFLICTED, CONFLICTED, CONFLICTED, CONFLICTED, CONFLICTED, LONG_HI,    CONFLICTED, LONG_HI,    CONFLICTED, CONFLICTED, CONFLICTED, CONFLICTED},
168             /*DOUBLE_LO*/  {DOUBLE_LO,   CONFLICTED, CONFLICTED, CONFLICTED, CONFLICTED, CONFLICTED, CONFLICTED, CONFLICTED, CONFLICTED, CONFLICTED, CONFLICTED, CONFLICTED, LONG_LO,    CONFLICTED, DOUBLE_LO,  CONFLICTED, CONFLICTED, CONFLICTED, CONFLICTED, CONFLICTED},
169             /*DOUBLE_HI*/  {DOUBLE_HI,   CONFLICTED, CONFLICTED, CONFLICTED, CONFLICTED, CONFLICTED, CONFLICTED, CONFLICTED, CONFLICTED, CONFLICTED, CONFLICTED, CONFLICTED, CONFLICTED, LONG_HI,    CONFLICTED, DOUBLE_HI,  CONFLICTED, CONFLICTED, CONFLICTED, CONFLICTED},
170             /*UNINIT_REF*/ {UNINIT_REF,  CONFLICTED, CONFLICTED, CONFLICTED, CONFLICTED, CONFLICTED, CONFLICTED, CONFLICTED, CONFLICTED, CONFLICTED, CONFLICTED, CONFLICTED, CONFLICTED, CONFLICTED, CONFLICTED, CONFLICTED, CONFLICTED, CONFLICTED, CONFLICTED, CONFLICTED},
171             /*UNINIT_THIS*/{UNINIT_THIS, CONFLICTED, CONFLICTED, CONFLICTED, CONFLICTED, CONFLICTED, CONFLICTED, CONFLICTED, CONFLICTED, CONFLICTED, CONFLICTED, CONFLICTED, CONFLICTED, CONFLICTED, CONFLICTED, CONFLICTED, CONFLICTED, UNINIT_THIS,CONFLICTED, CONFLICTED},
172             /*REFERENCE*/  {REFERENCE,   CONFLICTED, REFERENCE,  CONFLICTED, CONFLICTED, CONFLICTED, CONFLICTED, CONFLICTED, CONFLICTED, CONFLICTED, CONFLICTED, CONFLICTED, CONFLICTED, CONFLICTED, CONFLICTED, CONFLICTED, CONFLICTED, CONFLICTED, REFERENCE,  CONFLICTED},
173             /*CONFLICTED*/ {CONFLICTED,  CONFLICTED, CONFLICTED, CONFLICTED, CONFLICTED, CONFLICTED, CONFLICTED, CONFLICTED, CONFLICTED, CONFLICTED, CONFLICTED, CONFLICTED, CONFLICTED, CONFLICTED, CONFLICTED, CONFLICTED, CONFLICTED, CONFLICTED, CONFLICTED, CONFLICTED}
174     };
175 
176 
177     public static final RegisterType UNKNOWN_TYPE = new RegisterType(UNKNOWN, null);
178     public static final RegisterType UNINIT_TYPE = new RegisterType(UNINIT, null);
179     public static final RegisterType NULL_TYPE = new RegisterType(NULL, null);
180     public static final RegisterType ONE_TYPE = new RegisterType(ONE, null);
181     public static final RegisterType BOOLEAN_TYPE = new RegisterType(BOOLEAN, null);
182     public static final RegisterType BYTE_TYPE = new RegisterType(BYTE, null);
183     public static final RegisterType POS_BYTE_TYPE = new RegisterType(POS_BYTE, null);
184     public static final RegisterType SHORT_TYPE = new RegisterType(SHORT, null);
185     public static final RegisterType POS_SHORT_TYPE = new RegisterType(POS_SHORT, null);
186     public static final RegisterType CHAR_TYPE = new RegisterType(CHAR, null);
187     public static final RegisterType INTEGER_TYPE = new RegisterType(INTEGER, null);
188     public static final RegisterType FLOAT_TYPE = new RegisterType(FLOAT, null);
189     public static final RegisterType LONG_LO_TYPE = new RegisterType(LONG_LO, null);
190     public static final RegisterType LONG_HI_TYPE = new RegisterType(LONG_HI, null);
191     public static final RegisterType DOUBLE_LO_TYPE = new RegisterType(DOUBLE_LO, null);
192     public static final RegisterType DOUBLE_HI_TYPE = new RegisterType(DOUBLE_HI, null);
193     public static final RegisterType CONFLICTED_TYPE = new RegisterType(CONFLICTED, null);
194 
195     @Nonnull
getWideRegisterType(@onnull CharSequence type, boolean firstRegister)196     public static RegisterType getWideRegisterType(@Nonnull CharSequence type, boolean firstRegister) {
197         switch (type.charAt(0)) {
198             case 'J':
199                 if (firstRegister) {
200                     return getRegisterType(LONG_LO, null);
201                 } else {
202                     return getRegisterType(LONG_HI, null);
203                 }
204             case 'D':
205                 if (firstRegister) {
206                     return getRegisterType(DOUBLE_LO, null);
207                 } else {
208                     return getRegisterType(DOUBLE_HI, null);
209                 }
210             default:
211                 throw new ExceptionWithContext("Cannot use this method for narrow register type: %s", type);
212         }
213     }
214 
215     @Nonnull
getRegisterType(@onnull ClassPath classPath, @Nonnull CharSequence type)216     public static RegisterType getRegisterType(@Nonnull ClassPath classPath, @Nonnull CharSequence type) {
217         switch (type.charAt(0)) {
218             case 'Z':
219                 return BOOLEAN_TYPE;
220             case 'B':
221                 return BYTE_TYPE;
222             case 'S':
223                 return SHORT_TYPE;
224             case 'C':
225                 return CHAR_TYPE;
226             case 'I':
227                 return INTEGER_TYPE;
228             case 'F':
229                 return FLOAT_TYPE;
230             case 'J':
231                 return LONG_LO_TYPE;
232             case 'D':
233                 return DOUBLE_LO_TYPE;
234             case 'L':
235             case '[':
236                 return getRegisterType(REFERENCE, classPath.getClass(type));
237             default:
238                 throw new AnalysisException("Invalid type: " + type);
239         }
240     }
241 
242     @Nonnull
getRegisterTypeForLiteral(int literalValue)243     public static RegisterType getRegisterTypeForLiteral(int literalValue) {
244         if (literalValue < -32768) {
245             return INTEGER_TYPE;
246         }
247         if (literalValue < -128) {
248             return SHORT_TYPE;
249         }
250         if (literalValue < 0) {
251             return BYTE_TYPE;
252         }
253         if (literalValue == 0) {
254             return NULL_TYPE;
255         }
256         if (literalValue == 1) {
257             return ONE_TYPE;
258         }
259         if (literalValue < 128) {
260             return POS_BYTE_TYPE;
261         }
262         if (literalValue < 32768) {
263             return POS_SHORT_TYPE;
264         }
265         if (literalValue < 65536) {
266             return CHAR_TYPE;
267         }
268         return INTEGER_TYPE;
269     }
270 
271     @Nonnull
merge(@onnull RegisterType other)272     public RegisterType merge(@Nonnull RegisterType other) {
273         if (other.equals(this)) {
274             return this;
275         }
276 
277         byte mergedCategory = mergeTable[this.category][other.category];
278 
279         TypeProto mergedType = null;
280         if (mergedCategory == REFERENCE) {
281             TypeProto type = this.type;
282             if (type != null) {
283                 if (other.type != null) {
284                     mergedType = type.getCommonSuperclass(other.type);
285                 } else {
286                     mergedType = type;
287                 }
288             } else {
289                 mergedType = other.type;
290             }
291         } else if (mergedCategory == UNINIT_REF || mergedCategory == UNINIT_THIS) {
292             if (this.category == UNKNOWN) {
293                 return other;
294             }
295             assert other.category == UNKNOWN;
296             return this;
297         }
298 
299         if (mergedType != null) {
300             if (mergedType.equals(this.type)) {
301                 return this;
302             }
303             if (mergedType.equals(other.type)) {
304                 return other;
305             }
306         }
307         return RegisterType.getRegisterType(mergedCategory, mergedType);
308     }
309 
310     @Nonnull
getRegisterType(byte category, @Nullable TypeProto typeProto)311     public static RegisterType getRegisterType(byte category, @Nullable TypeProto typeProto) {
312         switch (category) {
313             case UNKNOWN:
314                 return UNKNOWN_TYPE;
315             case UNINIT:
316                 return UNINIT_TYPE;
317             case NULL:
318                 return NULL_TYPE;
319             case ONE:
320                 return ONE_TYPE;
321             case BOOLEAN:
322                 return BOOLEAN_TYPE;
323             case BYTE:
324                 return BYTE_TYPE;
325             case POS_BYTE:
326                 return POS_BYTE_TYPE;
327             case SHORT:
328                 return SHORT_TYPE;
329             case POS_SHORT:
330                 return POS_SHORT_TYPE;
331             case CHAR:
332                 return CHAR_TYPE;
333             case INTEGER:
334                 return INTEGER_TYPE;
335             case FLOAT:
336                 return FLOAT_TYPE;
337             case LONG_LO:
338                 return LONG_LO_TYPE;
339             case LONG_HI:
340                 return LONG_HI_TYPE;
341             case DOUBLE_LO:
342                 return DOUBLE_LO_TYPE;
343             case DOUBLE_HI:
344                 return DOUBLE_HI_TYPE;
345             case CONFLICTED:
346                 return CONFLICTED_TYPE;
347         }
348 
349         return new RegisterType(category, typeProto);
350     }
351 }
352