RegisterType.java revision a555aa0c0177f26fdd99b1a8b31d80ba104dbe6e 
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
32package org.jf.dexlib2.analysis;
33
34
35import org.jf.util.ExceptionWithContext;
36
37import javax.annotation.Nonnull;
38import javax.annotation.Nullable;
39import java.io.IOException;
40import java.io.Writer;
41
42public class RegisterType {
43    public final byte category;
44    @Nullable public final String type;
45
46    private RegisterType(byte category, @Nullable String 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
55    public String toString() {
56        return "(" + CATEGORY_NAMES[category] + (type==null?"":("," + type)) + ")";
57    }
58
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);
65        }
66        writer.write(')');
67    }
68
69    @Override
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        return (type != null ? type.equals(that.type) : that.type == null);
80    }
81
82    @Override
83    public int hashCode() {
84        int result = category;
85        result = 31 * result + (type != null ? type.hashCode() : 0);
86        return result;
87    }
88
89    //the Unknown category denotes a register type that hasn't been determined yet
90    public static final byte UNKNOWN = 0;
91    public static final byte UNINIT = 1;
92    public static final byte NULL = 2;
93    public static final byte ONE = 3;
94    public static final byte BOOLEAN = 4;
95    public static final byte BYTE = 5;
96    public static final byte POS_BYTE = 6;
97    public static final byte SHORT = 7;
98    public static final byte POS_SHORT = 8;
99    public static final byte CHAR = 9;
100    public static final byte INTEGER = 10;
101    public static final byte FLOAT = 11;
102    public static final byte LONG_LO = 12;
103    public static final byte LONG_HI = 13;
104    public static final byte DOUBLE_LO = 14;
105    public static final byte DOUBLE_HI = 15;
106    //the UninitRef category is used after a new-instance operation, and before the corresponding <init> is called
107    public static final byte UNINIT_REF = 16;
108    //the UninitThis category is used the "this" register inside an <init> method, before the superclass' <init>
109    //method is called
110    public static final byte UNINIT_THIS = 17;
111    public static final byte REFERENCE = 18;
112    //This is used when there are multiple incoming execution paths that have incompatible register types. For
113    //example if the register's type is an Integer on one incoming code path, but is a Reference type on another
114    //incomming code path. There is no register type that can hold either an Integer or a Reference.
115    public static final byte CONFLICTED = 19;
116
117    public static final String[] CATEGORY_NAMES = new String[] {
118            "Unknown",
119            "Uninit",
120            "Null",
121            "One",
122            "Boolean",
123            "Byte",
124            "PosByte",
125            "Short",
126            "PosShort",
127            "Char",
128            "Integer",
129            "Float",
130            "LongLo",
131            "LongHi",
132            "DoubleLo",
133            "DoubleHi",
134            "UninitRef",
135            "UninitThis",
136            "Reference",
137            "Conflicted"
138    };
139
140    //this table is used when merging register types. For example, if a particular register can be either a BYTE
141    //or a Char, then the "merged" type of that register would be Integer, because it is the "smallest" type can
142    //could hold either type of value.
143    protected static byte[][] mergeTable  =
144    {
145            /*              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*/
146            /*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},
147            /*UNINIT*/     {UNINIT,      UNINIT,     CONFLICTED, CONFLICTED, CONFLICTED, CONFLICTED, CONFLICTED, CONFLICTED, CONFLICTED, CONFLICTED, CONFLICTED, CONFLICTED, CONFLICTED, CONFLICTED, CONFLICTED, CONFLICTED, CONFLICTED, CONFLICTED, CONFLICTED, CONFLICTED},
148            /*NULL*/       {NULL,        CONFLICTED, NULL,       BOOLEAN,    BOOLEAN,    BYTE,       POS_BYTE,   SHORT,      POS_SHORT,  CHAR,       INTEGER,    FLOAT,      CONFLICTED, CONFLICTED, CONFLICTED, CONFLICTED, CONFLICTED, CONFLICTED, REFERENCE,  CONFLICTED},
149            /*ONE*/        {ONE,         CONFLICTED, BOOLEAN,    ONE,        BOOLEAN,    BYTE,       POS_BYTE,   SHORT,      POS_SHORT,  CHAR,       INTEGER,    FLOAT,      CONFLICTED, CONFLICTED, CONFLICTED, CONFLICTED, CONFLICTED, CONFLICTED, CONFLICTED, CONFLICTED},
150            /*BOOLEAN*/    {BOOLEAN,     CONFLICTED, BOOLEAN,    BOOLEAN,    BOOLEAN,    BYTE,       POS_BYTE,   SHORT,      POS_SHORT,  CHAR,       INTEGER,    FLOAT,      CONFLICTED, CONFLICTED, CONFLICTED, CONFLICTED, CONFLICTED, CONFLICTED, CONFLICTED, CONFLICTED},
151            /*BYTE*/       {BYTE,        CONFLICTED, BYTE,       BYTE,       BYTE,       BYTE,       BYTE,       SHORT,      SHORT,      INTEGER,    INTEGER,    FLOAT,      CONFLICTED, CONFLICTED, CONFLICTED, CONFLICTED, CONFLICTED, CONFLICTED, CONFLICTED, CONFLICTED},
152            /*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},
153            /*SHORT*/      {SHORT,       CONFLICTED, SHORT,      SHORT,      SHORT,      SHORT,      SHORT,      SHORT,      SHORT,      INTEGER,    INTEGER,    FLOAT,      CONFLICTED, CONFLICTED, CONFLICTED, CONFLICTED, CONFLICTED, CONFLICTED, CONFLICTED, CONFLICTED},
154            /*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},
155            /*CHAR*/       {CHAR,        CONFLICTED, CHAR,       CHAR,       CHAR,       INTEGER,    CHAR,       INTEGER,    CHAR,       CHAR,       INTEGER,    FLOAT,      CONFLICTED, CONFLICTED, CONFLICTED, CONFLICTED, CONFLICTED, CONFLICTED, CONFLICTED, CONFLICTED},
156            /*INTEGER*/    {INTEGER,     CONFLICTED, INTEGER,    INTEGER,    INTEGER,    INTEGER,    INTEGER,    INTEGER,    INTEGER,    INTEGER,    INTEGER,    INTEGER,    CONFLICTED, CONFLICTED, CONFLICTED, CONFLICTED, CONFLICTED, CONFLICTED, CONFLICTED, CONFLICTED},
157            /*FLOAT*/      {FLOAT,       CONFLICTED, FLOAT,      FLOAT,      FLOAT,      FLOAT,      FLOAT,      FLOAT,      FLOAT,      FLOAT,      INTEGER,    FLOAT,      CONFLICTED, CONFLICTED, CONFLICTED, CONFLICTED, CONFLICTED, CONFLICTED, CONFLICTED, CONFLICTED},
158            /*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},
159            /*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},
160            /*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},
161            /*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},
162            /*UNINIT_REF*/ {UNINIT_REF,  CONFLICTED, CONFLICTED, CONFLICTED, CONFLICTED, CONFLICTED, CONFLICTED, CONFLICTED, CONFLICTED, CONFLICTED, CONFLICTED, CONFLICTED, CONFLICTED, CONFLICTED, CONFLICTED, CONFLICTED, CONFLICTED, CONFLICTED, CONFLICTED, CONFLICTED},
163            /*UNINIT_THIS*/{UNINIT_THIS, CONFLICTED, CONFLICTED, CONFLICTED, CONFLICTED, CONFLICTED, CONFLICTED, CONFLICTED, CONFLICTED, CONFLICTED, CONFLICTED, CONFLICTED, CONFLICTED, CONFLICTED, CONFLICTED, CONFLICTED, CONFLICTED, UNINIT_THIS,CONFLICTED, CONFLICTED},
164            /*REFERENCE*/  {REFERENCE,   CONFLICTED, REFERENCE,  CONFLICTED, CONFLICTED, CONFLICTED, CONFLICTED, CONFLICTED, CONFLICTED, CONFLICTED, CONFLICTED, CONFLICTED, CONFLICTED, CONFLICTED, CONFLICTED, CONFLICTED, CONFLICTED, CONFLICTED, REFERENCE,  CONFLICTED},
165            /*CONFLICTED*/ {CONFLICTED,  CONFLICTED, CONFLICTED, CONFLICTED, CONFLICTED, CONFLICTED, CONFLICTED, CONFLICTED, CONFLICTED, CONFLICTED, CONFLICTED, CONFLICTED, CONFLICTED, CONFLICTED, CONFLICTED, CONFLICTED, CONFLICTED, CONFLICTED, CONFLICTED, CONFLICTED}
166    };
167
168
169    public static final RegisterType UNKNOWN_TYPE = new RegisterType(UNKNOWN, null);
170    public static final RegisterType UNINIT_TYPE = new RegisterType(UNINIT, null);
171    public static final RegisterType NULL_TYPE = new RegisterType(NULL, null);
172    public static final RegisterType ONE_TYPE = new RegisterType(ONE, null);
173    public static final RegisterType BOOLEAN_TYPE = new RegisterType(BOOLEAN, null);
174    public static final RegisterType BYTE_TYPE = new RegisterType(BYTE, null);
175    public static final RegisterType POS_BYTE_TYPE = new RegisterType(POS_BYTE, null);
176    public static final RegisterType SHORT_TYPE = new RegisterType(SHORT, null);
177    public static final RegisterType POS_SHORT_TYPE = new RegisterType(POS_SHORT, null);
178    public static final RegisterType CHAR_TYPE = new RegisterType(CHAR, null);
179    public static final RegisterType INTEGER_TYPE = new RegisterType(INTEGER, null);
180    public static final RegisterType FLOAT_TYPE = new RegisterType(FLOAT, null);
181    public static final RegisterType LONG_LO_TYPE = new RegisterType(LONG_LO, null);
182    public static final RegisterType LONG_HI_TYPE = new RegisterType(LONG_HI, null);
183    public static final RegisterType DOUBLE_LO_TYPE = new RegisterType(DOUBLE_LO, null);
184    public static final RegisterType DOUBLE_HI_TYPE = new RegisterType(DOUBLE_HI, null);
185    public static final RegisterType CONFLICTED_TYPE = new RegisterType(CONFLICTED, null);
186
187    @Nonnull
188    public static RegisterType getRegisterTypeForType(@Nonnull String type) {
189        switch (type.charAt(0)) {
190            case 'Z':
191                return getRegisterType(BOOLEAN, null);
192            case 'B':
193                return getRegisterType(BYTE, null);
194            case 'S':
195                return getRegisterType(SHORT, null);
196            case 'C':
197                return getRegisterType(CHAR, null);
198            case 'I':
199                return getRegisterType(INTEGER, null);
200            case 'F':
201                return getRegisterType(FLOAT, null);
202            case 'J':
203                return getRegisterType(LONG_LO, null);
204            case 'D':
205                return getRegisterType(DOUBLE_LO, null);
206            case 'L':
207            case 'U':
208            case '[':
209                return getRegisterType(REFERENCE, type);
210            default:
211                throw new RuntimeException("Invalid type: " + type);
212        }
213    }
214
215    @Nonnull
216    public static RegisterType getWideRegisterTypeForType(@Nonnull String type, boolean firstRegister) {
217        switch (type.charAt(0)) {
218            case 'J':
219                if (firstRegister) {
220                    return getRegisterType(LONG_LO, null);
221                } else {
222                    return getRegisterType(LONG_HI, null);
223                }
224            case 'D':
225                if (firstRegister) {
226                    return getRegisterType(DOUBLE_LO, null);
227                } else {
228                    return getRegisterType(DOUBLE_HI, null);
229                }
230            default:
231                throw new ExceptionWithContext("Cannot use this method for narrow register type: %s", type);
232        }
233    }
234
235    public static RegisterType getRegisterTypeForLiteral(long literalValue) {
236        if (literalValue < -32768) {
237            return getRegisterType(INTEGER, null);
238        }
239        if (literalValue < -128) {
240            return getRegisterType(SHORT, null);
241        }
242        if (literalValue < 0) {
243            return getRegisterType(BYTE, null);
244        }
245        if (literalValue == 0) {
246            return getRegisterType(NULL, null);
247        }
248        if (literalValue == 1) {
249            return getRegisterType(ONE, null);
250        }
251        if (literalValue < 128) {
252            return getRegisterType(POS_BYTE, null);
253        }
254        if (literalValue < 32768) {
255            return getRegisterType(POS_SHORT, null);
256        }
257        if (literalValue < 65536) {
258            return getRegisterType(CHAR, null);
259        }
260        return getRegisterType(INTEGER, null);
261    }
262
263    public RegisterType merge(RegisterType other) {
264        if (other == null || other == this) {
265            return this;
266        }
267
268        byte mergedCategory = mergeTable[this.category][other.category];
269
270        String mergedType = null;
271        if (mergedCategory == REFERENCE) {
272            // TODO: uncomment
273            // TODO: make sure to handle unresolved types in getCommonSuperclass (using U prefix?)
274            //mergedType = ClassPath.getCommonSuperclass(this.type, other.type);
275        } else if (mergedCategory == UNINIT_REF || mergedCategory == UNINIT_THIS) {
276            if (this.category == UNKNOWN) {
277                return other;
278            }
279            assert other.category == UNKNOWN;
280            return this;
281        }
282
283        if (mergedType != null) {
284            if (mergedType.equals(this.type)) {
285                return this;
286            }
287            if (mergedType.equals(other.type)) {
288                return other;
289            }
290        }
291        return RegisterType.getRegisterType(mergedCategory, mergedType);
292    }
293
294    public static RegisterType getRegisterType(byte category, String classType) {
295        switch (category) {
296            case UNKNOWN:
297                return UNKNOWN_TYPE;
298            case UNINIT:
299                return UNINIT_TYPE;
300            case NULL:
301                return NULL_TYPE;
302            case ONE:
303                return ONE_TYPE;
304            case BOOLEAN:
305                return BOOLEAN_TYPE;
306            case BYTE:
307                return BYTE_TYPE;
308            case POS_BYTE:
309                return POS_BYTE_TYPE;
310            case SHORT:
311                return SHORT_TYPE;
312            case POS_SHORT:
313                return POS_BYTE_TYPE;
314            case CHAR:
315                return CHAR_TYPE;
316            case INTEGER:
317                return INTEGER_TYPE;
318            case FLOAT:
319                return FLOAT_TYPE;
320            case LONG_LO:
321                return LONG_LO_TYPE;
322            case LONG_HI:
323                return LONG_HI_TYPE;
324            case DOUBLE_LO:
325                return DOUBLE_LO_TYPE;
326            case DOUBLE_HI:
327                return DOUBLE_HI_TYPE;
328            case CONFLICTED:
329                return CONFLICTED_TYPE;
330        }
331
332        return new RegisterType(category, classType);
333    }
334}
335