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
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
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
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
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 ExceptionWithContext("Invalid type: " + type);
239        }
240    }
241
242    @Nonnull
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
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
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