RegisterType.java revision 6eae34831fee1f116f3a453bdc5e143d68e05e03
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; 32import static org.jf.dexlib.Code.Analysis.ClassPath.ClassDef; 33 34import java.io.IOException; 35import java.io.Writer; 36import java.util.HashMap; 37 38public class RegisterType { 39 private final static HashMap<RegisterType, RegisterType> internedRegisterTypes = 40 new HashMap<RegisterType, RegisterType>(); 41 42 public final Category category; 43 public final ClassDef type; 44 45 private RegisterType(Category category, ClassDef type) { 46 assert ((category == Category.Reference || category == Category.UninitRef || category == Category.UninitThis) && 47 type != null) || 48 ((category != Category.Reference && category != Category.UninitRef && category != Category.UninitThis) && 49 type == null); 50 51 this.category = category; 52 this.type = type; 53 } 54 55 @Override 56 public String toString() { 57 return "(" + category.name() + (type==null?"":("," + type.getClassType())) + ")"; 58 } 59 60 public void writeTo(Writer writer) throws IOException { 61 writer.write('('); 62 writer.write(category.name()); 63 if (type != null) { 64 writer.write(','); 65 writer.write(type.getClassType()); 66 } 67 writer.write(')'); 68 } 69 70 @Override 71 public boolean equals(Object o) { 72 if (this == o) return true; 73 if (o == null || getClass() != o.getClass()) return false; 74 75 RegisterType that = (RegisterType) o; 76 77 if (category != that.category) return false; 78 if (type != null ? !type.equals(that.type) : that.type != null) return false; 79 80 return true; 81 } 82 83 @Override 84 public int hashCode() { 85 int result = category.hashCode(); 86 result = 31 * result + (type != null ? type.hashCode() : 0); 87 return result; 88 } 89 90 public static enum Category { 91 //the Unknown category denotes a register type that hasn't been determined yet 92 Unknown, 93 Uninit, 94 Null, 95 One, 96 Boolean, 97 Byte, 98 PosByte, 99 Short, 100 PosShort, 101 Char, 102 Integer, 103 Float, 104 LongLo, 105 LongHi, 106 DoubleLo, 107 DoubleHi, 108 //the UninitRef category is used after a new-instance operation, and before the corresponding <init> is called 109 UninitRef, 110 //the UninitThis category is used the "this" register inside an <init> method, before the superclass' <init> 111 //method is called 112 UninitThis, 113 Reference, 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 incomming 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 Conflicted; 118 119 //this table is used when merging register types. For example, if a particular register can be either a Byte 120 //or a Char, then the "merged" type of that register would be Integer, because it is the "smallest" type can 121 //could hold either type of value. 122 protected static Category[][] mergeTable = 123 { 124 /* Unknown Uninit Null One, Boolean Byte PosByte Short PosShort Char Integer, Float, LongLo LongHi DoubleLo DoubleHi UninitRef UninitThis Reference Conflicted*/ 125 /*Unknown*/ {Unknown, Uninit, Null, One, Boolean, Byte, PosByte, Short, PosShort, Char, Integer, Float, LongLo, LongHi, DoubleLo, DoubleHi, UninitRef, UninitThis, Reference, Conflicted}, 126 /*Uninit*/ {Uninit, Uninit, Conflicted, Conflicted, Conflicted, Conflicted, Conflicted, Conflicted, Conflicted, Conflicted, Conflicted, Conflicted, Conflicted, Conflicted, Conflicted, Conflicted, Conflicted, Conflicted, Conflicted, Conflicted}, 127 /*Null*/ {Null, Conflicted, Null, Boolean, Boolean, Byte, PosByte, Short, PosShort, Char, Integer, Float, Conflicted, Conflicted, Conflicted, Conflicted, Conflicted, Conflicted, Reference, Conflicted}, 128 /*One*/ {One, Conflicted, Boolean, One, Boolean, Byte, PosByte, Short, PosShort, Char, Integer, Float, Conflicted, Conflicted, Conflicted, Conflicted, Conflicted, Conflicted, Conflicted, Conflicted}, 129 /*Boolean*/ {Boolean, Conflicted, Boolean, Boolean, Boolean, Byte, PosByte, Short, PosShort, Char, Integer, Float, Conflicted, Conflicted, Conflicted, Conflicted, Conflicted, Conflicted, Conflicted, Conflicted}, 130 /*Byte*/ {Byte, Conflicted, Byte, Byte, Byte, Byte, Byte, Short, Short, Integer, Integer, Float, Conflicted, Conflicted, Conflicted, Conflicted, Conflicted, Conflicted, Conflicted, Conflicted}, 131 /*PosByte*/ {PosByte, Conflicted, PosByte, PosByte, PosByte, Byte, PosByte, Short, PosShort, Char, Integer, Float, Conflicted, Conflicted, Conflicted, Conflicted, Conflicted, Conflicted, Conflicted, Conflicted}, 132 /*Short*/ {Short, Conflicted, Short, Short, Short, Short, Short, Short, Short, Integer, Integer, Float, Conflicted, Conflicted, Conflicted, Conflicted, Conflicted, Conflicted, Conflicted, Conflicted}, 133 /*PosShort*/ {PosShort, Conflicted, PosShort, PosShort, PosShort, Short, PosShort, Short, PosShort, Char, Integer, Float, Conflicted, Conflicted, Conflicted, Conflicted, Conflicted, Conflicted, Conflicted, Conflicted}, 134 /*Char*/ {Char, Conflicted, Char, Char, Char, Integer, Char, Integer, Char, Char, Integer, Float, Conflicted, Conflicted, Conflicted, Conflicted, Conflicted, Conflicted, Conflicted, Conflicted}, 135 /*Integer*/ {Integer, Conflicted, Integer, Integer, Integer, Integer, Integer, Integer, Integer, Integer, Integer, Integer, Conflicted, Conflicted, Conflicted, Conflicted, Conflicted, Conflicted, Conflicted, Conflicted}, 136 /*Float*/ {Float, Conflicted, Float, Float, Float, Float, Float, Float, Float, Float, Integer, Float, Conflicted, Conflicted, Conflicted, Conflicted, Conflicted, Conflicted, Conflicted, Conflicted}, 137 /*LongLo*/ {LongLo, Conflicted, Conflicted, Conflicted, Conflicted, Conflicted, Conflicted, Conflicted, Conflicted, Conflicted, Conflicted, Conflicted, LongLo, Conflicted, LongLo, Conflicted, Conflicted, Conflicted, Conflicted, Conflicted}, 138 /*LongHi*/ {LongHi, Conflicted, Conflicted, Conflicted, Conflicted, Conflicted, Conflicted, Conflicted, Conflicted, Conflicted, Conflicted, Conflicted, Conflicted, LongHi, Conflicted, LongHi, Conflicted, Conflicted, Conflicted, Conflicted}, 139 /*DoubleLo*/ {DoubleLo, Conflicted, Conflicted, Conflicted, Conflicted, Conflicted, Conflicted, Conflicted, Conflicted, Conflicted, Conflicted, Conflicted, LongLo, Conflicted, DoubleLo, Conflicted, Conflicted, Conflicted, Conflicted, Conflicted}, 140 /*DoubleHi*/ {DoubleHi, Conflicted, Conflicted, Conflicted, Conflicted, Conflicted, Conflicted, Conflicted, Conflicted, Conflicted, Conflicted, Conflicted, Conflicted, LongHi, Conflicted, DoubleHi, Conflicted, Conflicted, Conflicted, Conflicted}, 141 /*UninitRef*/ {UninitRef, Conflicted, Conflicted, Conflicted, Conflicted, Conflicted, Conflicted, Conflicted, Conflicted, Conflicted, Conflicted, Conflicted, Conflicted, Conflicted, Conflicted, Conflicted, Conflicted, Conflicted, Conflicted, Conflicted}, 142 /*UninitThis*/ {UninitThis, Conflicted, Conflicted, Conflicted, Conflicted, Conflicted, Conflicted, Conflicted, Conflicted, Conflicted, Conflicted, Conflicted, Conflicted, Conflicted, Conflicted, Conflicted, Conflicted, UninitThis, Conflicted, Conflicted}, 143 /*Reference*/ {Reference, Conflicted, Reference, Conflicted, Conflicted, Conflicted, Conflicted, Conflicted, Conflicted, Conflicted, Conflicted, Conflicted, Conflicted, Conflicted, Conflicted, Conflicted, Conflicted, Conflicted, Reference, Conflicted}, 144 /*Conflicted*/ {Conflicted, Conflicted, Conflicted, Conflicted, Conflicted, Conflicted, Conflicted, Conflicted, Conflicted, Conflicted, Conflicted, Conflicted, Conflicted, Conflicted, Conflicted, Conflicted, Conflicted, Conflicted, Conflicted, Conflicted} 145 }; 146 147 //this table is used to denote whether a given value type can be assigned to a "slot" of a certain type. For 148 //example, to determine if you can assign a Boolean value to a particular array "slot", where the array is an 149 //array of Integers, you would look up assignmentTable[Boolean.ordinal()][Integer.ordinal()] 150 //Note that not all slot types in the table are expected to be used. For example, it doesn't make sense to 151 //check if a value can be assigned to an uninitialized reference slot - because there is no such thing. 152 protected static boolean[][] assigmentTable = 153 { 154 /* Unknown Uninit Null One, Boolean Byte PosByte Short PosShort Char Integer, Float, LongLo LongHi DoubleLo DoubleHi UninitRef UninitThis Reference Conflicted |slot type*/ 155 /*Unknown*/ {false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false}, 156 /*Uninit*/ {false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false}, 157 /*Null*/ {false, false, true, false, true, true, true, true, true, true, true, true, false, false, false, false, false, false, true, false}, 158 /*One*/ {false, false, false, true, true, true, true, true, true, true, true, true, false, false, false, false, false, false, false, false}, 159 /*Boolean*/ {false, false, false, false, true, true, true, true, true, true, true, true, false, false, false, false, false, false, false, false}, 160 /*Byte*/ {false, false, false, false, false, true, false, true, true, false, true, true, false, false, false, false, false, false, false, false}, 161 /*PosByte*/ {false, false, false, false, false, true, true, true, true, true, true, true, false, false, false, false, false, false, false, false}, 162 /*Short*/ {false, false, false, false, false, false, false, true, false, false, true, true, false, false, false, false, false, false, false, false}, 163 /*PosShort*/ {false, false, false, false, false, false, false, true, true, true, true, true, false, false, false, false, false, false, false, false}, 164 /*Char*/ {false, false, false, false, false, false, false, false, false, true, true, true, false, false, false, false, false, false, false, false}, 165 /*Integer*/ {false, false, false, false, false, false, false, false, false, false, true, true, false, false, false, false, false, false, false, false}, 166 /*Float*/ {false, false, false, false, false, false, false, false, false, false, true, true, false, false, false, false, false, false, false, false}, 167 /*LongLo*/ {false, false, false, false, false, false, false, false, false, false, false, false, true, false, true, false, false, false, false, false}, 168 /*LongHi*/ {false, false, false, false, false, false, false, false, false, false, false, false, false, true, false, true, false, false, false, false}, 169 /*DoubleLo*/ {false, false, false, false, false, false, false, false, false, false, false, false, true, false, true, false, false, false, false, false}, 170 /*DoubleHi*/ {false, false, false, false, false, false, false, false, false, false, false, false, false, true, false, true, false, false, false, false}, 171 /*UninitRef*/ {false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false}, 172 /*UninitThis*/ {false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false}, 173 /*Reference*/ {false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, true, false}, 174 /*Conflicted*/ {false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false} 175 /*----------*/ 176 /*value type*/ 177 }; 178 179 } 180 181 public static RegisterType getRegisterTypeForType(String type) { 182 switch (type.charAt(0)) { 183 case 'V': 184 throw new ValidationException("The V type can only be used as a method return type"); 185 case 'Z': 186 return getRegisterType(Category.Boolean, null); 187 case 'B': 188 return getRegisterType(Category.Byte, null); 189 case 'S': 190 return getRegisterType(Category.Short, null); 191 case 'C': 192 return getRegisterType(Category.Char, null); 193 case 'I': 194 return getRegisterType(Category.Integer, null); 195 case 'F': 196 return getRegisterType(Category.Float, null); 197 case 'J': 198 return getRegisterType(Category.LongLo, null); 199 case 'D': 200 return getRegisterType(Category.DoubleLo, null); 201 case 'L': 202 case '[': 203 return getRegisterType(Category.Reference, ClassPath.getClassDef(type)); 204 default: 205 throw new RuntimeException("Invalid type: " + type); 206 } 207 } 208 209 public static RegisterType getRegisterTypeForTypeIdItem(TypeIdItem typeIdItem) { 210 return getRegisterTypeForType(typeIdItem.getTypeDescriptor()); 211 } 212 213 public static RegisterType getWideRegisterTypeForTypeIdItem(TypeIdItem typeIdItem, boolean firstRegister) { 214 if (typeIdItem.getRegisterCount() == 1) { 215 throw new RuntimeException("Cannot use this method for non-wide register type: " + 216 typeIdItem.getTypeDescriptor()); 217 } 218 219 switch (typeIdItem.getTypeDescriptor().charAt(0)) { 220 case 'J': 221 if (firstRegister) { 222 return getRegisterType(Category.LongLo, null); 223 } else { 224 return getRegisterType(Category.LongHi, null); 225 } 226 case 'D': 227 if (firstRegister) { 228 return getRegisterType(Category.DoubleLo, null); 229 } else { 230 return getRegisterType(Category.DoubleHi, null); 231 } 232 default: 233 throw new RuntimeException("Invalid type: " + typeIdItem.getTypeDescriptor()); 234 } 235 } 236 237 public static RegisterType getRegisterTypeForLiteral(long literalValue) { 238 if (literalValue < -32768) { 239 return getRegisterType(Category.Integer, null); 240 } 241 if (literalValue < -128) { 242 return getRegisterType(Category.Short, null); 243 } 244 if (literalValue < 0) { 245 return getRegisterType(Category.Byte, null); 246 } 247 if (literalValue == 0) { 248 return getRegisterType(Category.Null, null); 249 } 250 if (literalValue == 1) { 251 return getRegisterType(Category.One, null); 252 } 253 if (literalValue < 128) { 254 return getRegisterType(Category.PosByte, null); 255 } 256 if (literalValue < 32768) { 257 return getRegisterType(Category.PosShort, null); 258 } 259 if (literalValue < 65536) { 260 return getRegisterType(Category.Char, null); 261 } 262 return getRegisterType(Category.Integer, null); 263 } 264 265 public RegisterType merge(RegisterType type) { 266 if (type == null || type == this) { 267 return this; 268 } 269 270 Category mergedCategory = Category.mergeTable[this.category.ordinal()][type.category.ordinal()]; 271 272 ClassDef mergedType = null; 273 if (mergedCategory == Category.Reference) { 274 mergedType = ClassPath.getCommonSuperclass(this.type, type.type); 275 } 276 if (mergedCategory == Category.UninitRef || mergedCategory == Category.UninitThis) { 277 if (this.category == Category.Unknown) { 278 return type; 279 } 280 assert type.category == Category.Unknown; 281 return this; 282 } 283 return RegisterType.getRegisterType(mergedCategory, mergedType); 284 } 285 286 public boolean canBeAssignedTo(RegisterType slotType) { 287 if (Category.assigmentTable[this.category.ordinal()][slotType.category.ordinal()]) { 288 if (this.category == Category.Reference && slotType.category == Category.Reference) { 289 if (!slotType.type.isInterface()) { 290 return this.type.extendsClass(slotType.type); 291 } 292 //for verification, we assume all objects implement all interfaces, so we don't verify the type if 293 //slotType is an interface 294 } 295 return true; 296 } 297 return false; 298 } 299 300 public static RegisterType getUnitializedReference(ClassDef classType) { 301 //We always create a new RegisterType instance for an uninit ref. Each unique uninit RegisterType instance 302 //is used to track a specific uninitialized reference, so that if multiple registers contain the same 303 //uninitialized reference, then they can all be upgraded to an initialized reference when the appropriate 304 //<init> is invoked 305 return new RegisterType(Category.UninitRef, classType); 306 } 307 308 public static RegisterType getRegisterType(Category category, ClassDef classType) { 309 RegisterType newRegisterType = new RegisterType(category, classType); 310 RegisterType internedRegisterType = internedRegisterTypes.get(newRegisterType); 311 if (internedRegisterType == null) { 312 internedRegisterTypes.put(newRegisterType, newRegisterType); 313 return newRegisterType; 314 } 315 return internedRegisterType; 316 } 317} 318