1/* 2 * [The "BSD licence"] 3 * Copyright (c) 2010 Ben Gruver (JesusFreke) 4 * All rights reserved. 5 * 6 * Redistribution and use in source and binary forms, with or without 7 * modification, are permitted provided that the following conditions 8 * are met: 9 * 1. Redistributions of source code must retain the above copyright 10 * notice, this list of conditions and the following disclaimer. 11 * 2. Redistributions in binary form must reproduce the above copyright 12 * notice, this list of conditions and the following disclaimer in the 13 * documentation and/or other materials provided with the distribution. 14 * 3. The name of the author may not be used to endorse or promote products 15 * derived from this software without specific prior written permission. 16 * 17 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR 18 * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES 19 * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. 20 * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, 21 * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT 22 * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 23 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 24 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 25 * INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF 26 * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 27 */ 28 29package org.jf.dexlib.Code.Analysis; 30 31import org.jf.dexlib.TypeIdItem; 32 33import java.io.IOException; 34import java.io.Writer; 35import java.util.HashMap; 36 37import static org.jf.dexlib.Code.Analysis.ClassPath.ClassDef; 38 39public class RegisterType { 40 private final static HashMap<RegisterType, RegisterType> internedRegisterTypes = 41 new HashMap<RegisterType, RegisterType>(); 42 43 public final Category category; 44 public final ClassDef type; 45 46 private RegisterType(Category category, ClassDef type) { 47 assert ((category == Category.Reference || category == Category.UninitRef || category == Category.UninitThis) && 48 type != null) || 49 ((category != Category.Reference && category != Category.UninitRef && category != Category.UninitThis) && 50 type == null); 51 52 this.category = category; 53 this.type = type; 54 } 55 56 @Override 57 public String toString() { 58 return "(" + category.name() + (type==null?"":("," + type.getClassType())) + ")"; 59 } 60 61 public void writeTo(Writer writer) throws IOException { 62 writer.write('('); 63 writer.write(category.name()); 64 if (type != null) { 65 writer.write(','); 66 writer.write(type.getClassType()); 67 } 68 writer.write(')'); 69 } 70 71 @Override 72 public boolean equals(Object o) { 73 if (this == o) return true; 74 if (o == null || getClass() != o.getClass()) return false; 75 76 RegisterType that = (RegisterType) o; 77 78 if (category != that.category) return false; 79 if (type != null ? !type.equals(that.type) : that.type != null) return false; 80 81 return true; 82 } 83 84 @Override 85 public int hashCode() { 86 int result = category.hashCode(); 87 result = 31 * result + (type != null ? type.hashCode() : 0); 88 return result; 89 } 90 91 public static enum Category { 92 //the Unknown category denotes a register type that hasn't been determined yet 93 Unknown, 94 Uninit, 95 Null, 96 One, 97 Boolean, 98 Byte, 99 PosByte, 100 Short, 101 PosShort, 102 Char, 103 Integer, 104 Float, 105 LongLo, 106 LongHi, 107 DoubleLo, 108 DoubleHi, 109 //the UninitRef category is used after a new-instance operation, and before the corresponding <init> is called 110 UninitRef, 111 //the UninitThis category is used the "this" register inside an <init> method, before the superclass' <init> 112 //method is called 113 UninitThis, 114 Reference, 115 //This is used when there are multiple incoming execution paths that have incompatible register types. For 116 //example if the register's type is an Integer on one incomming code path, but is a Reference type on another 117 //incomming code path. There is no register type that can hold either an Integer or a Reference. 118 Conflicted; 119 120 //this table is used when merging register types. For example, if a particular register can be either a Byte 121 //or a Char, then the "merged" type of that register would be Integer, because it is the "smallest" type can 122 //could hold either type of value. 123 protected static Category[][] mergeTable = 124 { 125 /* Unknown Uninit Null One, Boolean Byte PosByte Short PosShort Char Integer, Float, LongLo LongHi DoubleLo DoubleHi UninitRef UninitThis Reference Conflicted*/ 126 /*Unknown*/ {Unknown, Uninit, Null, One, Boolean, Byte, PosByte, Short, PosShort, Char, Integer, Float, LongLo, LongHi, DoubleLo, DoubleHi, UninitRef, UninitThis, Reference, Conflicted}, 127 /*Uninit*/ {Uninit, Uninit, Conflicted, Conflicted, Conflicted, Conflicted, Conflicted, Conflicted, Conflicted, Conflicted, Conflicted, Conflicted, Conflicted, Conflicted, Conflicted, Conflicted, Conflicted, Conflicted, Conflicted, Conflicted}, 128 /*Null*/ {Null, Conflicted, Null, Boolean, Boolean, Byte, PosByte, Short, PosShort, Char, Integer, Float, Conflicted, Conflicted, Conflicted, Conflicted, Conflicted, Conflicted, Reference, Conflicted}, 129 /*One*/ {One, Conflicted, Boolean, One, Boolean, Byte, PosByte, Short, PosShort, Char, Integer, Float, Conflicted, Conflicted, Conflicted, Conflicted, Conflicted, Conflicted, Conflicted, Conflicted}, 130 /*Boolean*/ {Boolean, Conflicted, Boolean, Boolean, Boolean, Byte, PosByte, Short, PosShort, Char, Integer, Float, Conflicted, Conflicted, Conflicted, Conflicted, Conflicted, Conflicted, Conflicted, Conflicted}, 131 /*Byte*/ {Byte, Conflicted, Byte, Byte, Byte, Byte, Byte, Short, Short, Integer, Integer, Float, Conflicted, Conflicted, Conflicted, Conflicted, Conflicted, Conflicted, Conflicted, Conflicted}, 132 /*PosByte*/ {PosByte, Conflicted, PosByte, PosByte, PosByte, Byte, PosByte, Short, PosShort, Char, Integer, Float, Conflicted, Conflicted, Conflicted, Conflicted, Conflicted, Conflicted, Conflicted, Conflicted}, 133 /*Short*/ {Short, Conflicted, Short, Short, Short, Short, Short, Short, Short, Integer, Integer, Float, Conflicted, Conflicted, Conflicted, Conflicted, Conflicted, Conflicted, Conflicted, Conflicted}, 134 /*PosShort*/ {PosShort, Conflicted, PosShort, PosShort, PosShort, Short, PosShort, Short, PosShort, Char, Integer, Float, Conflicted, Conflicted, Conflicted, Conflicted, Conflicted, Conflicted, Conflicted, Conflicted}, 135 /*Char*/ {Char, Conflicted, Char, Char, Char, Integer, Char, Integer, Char, Char, Integer, Float, Conflicted, Conflicted, Conflicted, Conflicted, Conflicted, Conflicted, Conflicted, Conflicted}, 136 /*Integer*/ {Integer, Conflicted, Integer, Integer, Integer, Integer, Integer, Integer, Integer, Integer, Integer, Integer, Conflicted, Conflicted, Conflicted, Conflicted, Conflicted, Conflicted, Conflicted, Conflicted}, 137 /*Float*/ {Float, Conflicted, Float, Float, Float, Float, Float, Float, Float, Float, Integer, Float, Conflicted, Conflicted, Conflicted, Conflicted, Conflicted, Conflicted, Conflicted, Conflicted}, 138 /*LongLo*/ {LongLo, Conflicted, Conflicted, Conflicted, Conflicted, Conflicted, Conflicted, Conflicted, Conflicted, Conflicted, Conflicted, Conflicted, LongLo, Conflicted, LongLo, Conflicted, Conflicted, Conflicted, Conflicted, Conflicted}, 139 /*LongHi*/ {LongHi, Conflicted, Conflicted, Conflicted, Conflicted, Conflicted, Conflicted, Conflicted, Conflicted, Conflicted, Conflicted, Conflicted, Conflicted, LongHi, Conflicted, LongHi, Conflicted, Conflicted, Conflicted, Conflicted}, 140 /*DoubleLo*/ {DoubleLo, Conflicted, Conflicted, Conflicted, Conflicted, Conflicted, Conflicted, Conflicted, Conflicted, Conflicted, Conflicted, Conflicted, LongLo, Conflicted, DoubleLo, Conflicted, Conflicted, Conflicted, Conflicted, Conflicted}, 141 /*DoubleHi*/ {DoubleHi, Conflicted, Conflicted, Conflicted, Conflicted, Conflicted, Conflicted, Conflicted, Conflicted, Conflicted, Conflicted, Conflicted, Conflicted, LongHi, Conflicted, DoubleHi, Conflicted, Conflicted, Conflicted, Conflicted}, 142 /*UninitRef*/ {UninitRef, Conflicted, Conflicted, Conflicted, Conflicted, Conflicted, Conflicted, Conflicted, Conflicted, Conflicted, Conflicted, Conflicted, Conflicted, Conflicted, Conflicted, Conflicted, Conflicted, Conflicted, Conflicted, Conflicted}, 143 /*UninitThis*/ {UninitThis, Conflicted, Conflicted, Conflicted, Conflicted, Conflicted, Conflicted, Conflicted, Conflicted, Conflicted, Conflicted, Conflicted, Conflicted, Conflicted, Conflicted, Conflicted, Conflicted, UninitThis, Conflicted, Conflicted}, 144 /*Reference*/ {Reference, Conflicted, Reference, Conflicted, Conflicted, Conflicted, Conflicted, Conflicted, Conflicted, Conflicted, Conflicted, Conflicted, Conflicted, Conflicted, Conflicted, Conflicted, Conflicted, Conflicted, Reference, Conflicted}, 145 /*Conflicted*/ {Conflicted, Conflicted, Conflicted, Conflicted, Conflicted, Conflicted, Conflicted, Conflicted, Conflicted, Conflicted, Conflicted, Conflicted, Conflicted, Conflicted, Conflicted, Conflicted, Conflicted, Conflicted, Conflicted, Conflicted} 146 }; 147 148 //this table is used to denote whether a given value type can be assigned to a "slot" of a certain type. For 149 //example, to determine if you can assign a Boolean value to a particular array "slot", where the array is an 150 //array of Integers, you would look up assignmentTable[Boolean.ordinal()][Integer.ordinal()] 151 //Note that not all slot types in the table are expected to be used. For example, it doesn't make sense to 152 //check if a value can be assigned to an uninitialized reference slot - because there is no such thing. 153 protected static boolean[][] assigmentTable = 154 { 155 /* Unknown Uninit Null One, Boolean Byte PosByte Short PosShort Char Integer, Float, LongLo LongHi DoubleLo DoubleHi UninitRef UninitThis Reference Conflicted |slot type*/ 156 /*Unknown*/ {false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false}, 157 /*Uninit*/ {false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false}, 158 /*Null*/ {false, false, true, false, true, true, true, true, true, true, true, true, false, false, false, false, false, false, true, false}, 159 /*One*/ {false, false, false, true, true, true, true, true, true, true, true, true, false, false, false, false, false, false, false, false}, 160 /*Boolean*/ {false, false, false, false, true, true, true, true, true, true, true, true, false, false, false, false, false, false, false, false}, 161 /*Byte*/ {false, false, false, false, false, true, false, true, true, false, true, true, false, false, false, false, false, false, false, false}, 162 /*PosByte*/ {false, false, false, false, false, true, true, true, true, true, true, true, false, false, false, false, false, false, false, false}, 163 /*Short*/ {false, false, false, false, false, false, false, true, false, false, true, true, false, false, false, false, false, false, false, false}, 164 /*PosShort*/ {false, false, false, false, false, false, false, true, true, true, true, true, false, false, false, false, false, false, false, false}, 165 /*Char*/ {false, false, false, false, false, false, false, false, false, true, true, true, false, false, false, false, false, false, false, false}, 166 /*Integer*/ {false, false, false, false, false, false, false, false, false, false, true, true, false, false, false, false, false, false, false, false}, 167 /*Float*/ {false, false, false, false, false, false, false, false, false, false, true, true, false, false, false, false, false, false, false, false}, 168 /*LongLo*/ {false, false, false, false, false, false, false, false, false, false, false, false, true, false, true, false, false, false, false, false}, 169 /*LongHi*/ {false, false, false, false, false, false, false, false, false, false, false, false, false, true, false, true, false, false, false, false}, 170 /*DoubleLo*/ {false, false, false, false, false, false, false, false, false, false, false, false, true, false, true, false, false, false, false, false}, 171 /*DoubleHi*/ {false, false, false, false, false, false, false, false, false, false, false, false, false, true, false, true, false, false, false, false}, 172 /*UninitRef*/ {false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false}, 173 /*UninitThis*/ {false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false}, 174 /*Reference*/ {false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, true, false}, 175 /*Conflicted*/ {false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false} 176 /*----------*/ 177 /*value type*/ 178 }; 179 180 } 181 182 public static RegisterType getRegisterTypeForType(String type) { 183 switch (type.charAt(0)) { 184 case 'V': 185 throw new ValidationException("The V type can only be used as a method return type"); 186 case 'Z': 187 return getRegisterType(Category.Boolean, null); 188 case 'B': 189 return getRegisterType(Category.Byte, null); 190 case 'S': 191 return getRegisterType(Category.Short, null); 192 case 'C': 193 return getRegisterType(Category.Char, null); 194 case 'I': 195 return getRegisterType(Category.Integer, null); 196 case 'F': 197 return getRegisterType(Category.Float, null); 198 case 'J': 199 return getRegisterType(Category.LongLo, null); 200 case 'D': 201 return getRegisterType(Category.DoubleLo, null); 202 case 'L': 203 case '[': 204 return getRegisterType(Category.Reference, ClassPath.getClassDef(type)); 205 default: 206 throw new RuntimeException("Invalid type: " + type); 207 } 208 } 209 210 public static RegisterType getRegisterTypeForTypeIdItem(TypeIdItem typeIdItem) { 211 return getRegisterTypeForType(typeIdItem.getTypeDescriptor()); 212 } 213 214 public static RegisterType getWideRegisterTypeForTypeIdItem(TypeIdItem typeIdItem, boolean firstRegister) { 215 if (typeIdItem.getRegisterCount() == 1) { 216 throw new RuntimeException("Cannot use this method for non-wide register type: " + 217 typeIdItem.getTypeDescriptor()); 218 } 219 220 switch (typeIdItem.getTypeDescriptor().charAt(0)) { 221 case 'J': 222 if (firstRegister) { 223 return getRegisterType(Category.LongLo, null); 224 } else { 225 return getRegisterType(Category.LongHi, null); 226 } 227 case 'D': 228 if (firstRegister) { 229 return getRegisterType(Category.DoubleLo, null); 230 } else { 231 return getRegisterType(Category.DoubleHi, null); 232 } 233 default: 234 throw new RuntimeException("Invalid type: " + typeIdItem.getTypeDescriptor()); 235 } 236 } 237 238 public static RegisterType getRegisterTypeForLiteral(long literalValue) { 239 if (literalValue < -32768) { 240 return getRegisterType(Category.Integer, null); 241 } 242 if (literalValue < -128) { 243 return getRegisterType(Category.Short, null); 244 } 245 if (literalValue < 0) { 246 return getRegisterType(Category.Byte, null); 247 } 248 if (literalValue == 0) { 249 return getRegisterType(Category.Null, null); 250 } 251 if (literalValue == 1) { 252 return getRegisterType(Category.One, null); 253 } 254 if (literalValue < 128) { 255 return getRegisterType(Category.PosByte, null); 256 } 257 if (literalValue < 32768) { 258 return getRegisterType(Category.PosShort, null); 259 } 260 if (literalValue < 65536) { 261 return getRegisterType(Category.Char, null); 262 } 263 return getRegisterType(Category.Integer, null); 264 } 265 266 public RegisterType merge(RegisterType type) { 267 if (type == null || type == this) { 268 return this; 269 } 270 271 Category mergedCategory = Category.mergeTable[this.category.ordinal()][type.category.ordinal()]; 272 273 ClassDef mergedType = null; 274 if (mergedCategory == Category.Reference) { 275 if (this.type instanceof ClassPath.UnresolvedClassDef || 276 type.type instanceof ClassPath.UnresolvedClassDef) { 277 mergedType = ClassPath.getUnresolvedObjectClassDef(); 278 } else { 279 mergedType = ClassPath.getCommonSuperclass(this.type, type.type); 280 } 281 } else if (mergedCategory == Category.UninitRef || mergedCategory == Category.UninitThis) { 282 if (this.category == Category.Unknown) { 283 return type; 284 } 285 assert type.category == Category.Unknown; 286 return this; 287 } 288 return RegisterType.getRegisterType(mergedCategory, mergedType); 289 } 290 291 public boolean canBeAssignedTo(RegisterType slotType) { 292 if (Category.assigmentTable[this.category.ordinal()][slotType.category.ordinal()]) { 293 if (this.category == Category.Reference && slotType.category == Category.Reference) { 294 if (!slotType.type.isInterface()) { 295 return this.type.extendsClass(slotType.type); 296 } 297 //for verification, we assume all objects implement all interfaces, so we don't verify the type if 298 //slotType is an interface 299 } 300 return true; 301 } 302 return false; 303 } 304 305 public static RegisterType getUnitializedReference(ClassDef classType) { 306 //We always create a new RegisterType instance for an uninit ref. Each unique uninit RegisterType instance 307 //is used to track a specific uninitialized reference, so that if multiple registers contain the same 308 //uninitialized reference, then they can all be upgraded to an initialized reference when the appropriate 309 //<init> is invoked 310 return new RegisterType(Category.UninitRef, classType); 311 } 312 313 public static RegisterType getRegisterType(Category category, ClassDef classType) { 314 RegisterType newRegisterType = new RegisterType(category, classType); 315 RegisterType internedRegisterType = internedRegisterTypes.get(newRegisterType); 316 if (internedRegisterType == null) { 317 internedRegisterTypes.put(newRegisterType, newRegisterType); 318 return newRegisterType; 319 } 320 return internedRegisterType; 321 } 322} 323