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