1/* 2 * Copyright (C) 2007 The Android Open Source Project 3 * 4 * Licensed under the Apache License, Version 2.0 (the "License"); 5 * you may not use this file except in compliance with the License. 6 * You may obtain a copy of the License at 7 * 8 * http://www.apache.org/licenses/LICENSE-2.0 9 * 10 * Unless required by applicable law or agreed to in writing, software 11 * distributed under the License is distributed on an "AS IS" BASIS, 12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 13 * See the License for the specific language governing permissions and 14 * limitations under the License. 15 */ 16 17package com.android.dx.rop.type; 18 19import com.android.dx.command.dexer.Main; 20import java.util.concurrent.ConcurrentHashMap; 21import java.util.concurrent.ConcurrentMap; 22 23/** 24 * Representation of a method descriptor. Instances of this class are 25 * generally interned and may be usefully compared with each other 26 * using {@code ==}. 27 */ 28public final class Prototype implements Comparable<Prototype> { 29 /** 30 * Intern table for instances. 31 * 32 * <p>The initial capacity is based on a medium-size project. 33 */ 34 private static final ConcurrentMap<String, Prototype> internTable = 35 new ConcurrentHashMap<>(10_000, 0.75f, Main.CONCURRENCY_LEVEL); 36 37 /** {@code non-null;} method descriptor */ 38 private final String descriptor; 39 40 /** {@code non-null;} return type */ 41 private final Type returnType; 42 43 /** {@code non-null;} list of parameter types */ 44 private final StdTypeList parameterTypes; 45 46 /** {@code null-ok;} list of parameter frame types, if calculated */ 47 private StdTypeList parameterFrameTypes; 48 49 /** 50 * Returns the unique instance corresponding to the 51 * given method descriptor. See vmspec-2 sec4.3.3 for details on the 52 * field descriptor syntax. 53 * 54 * @param descriptor {@code non-null;} the descriptor 55 * @return {@code non-null;} the corresponding instance 56 * @throws IllegalArgumentException thrown if the descriptor has 57 * invalid syntax 58 */ 59 public static Prototype intern(String descriptor) { 60 if (descriptor == null) { 61 throw new NullPointerException("descriptor == null"); 62 } 63 64 Prototype result = internTable.get(descriptor); 65 if (result != null) { 66 return result; 67 } 68 69 result = fromDescriptor(descriptor); 70 return putIntern(result); 71 } 72 73 /** 74 * Returns a prototype for a method descriptor. 75 * 76 * The {@code Prototype} returned will be the interned value if present, 77 * or a new instance otherwise. If a new instance is created, it is not 78 * placed in the intern table. 79 * 80 * @param descriptor {@code non-null;} the descriptor 81 * @return {@code non-null;} the corresponding instance 82 * @throws IllegalArgumentException thrown if the descriptor has 83 * invalid syntax 84 */ 85 public static Prototype fromDescriptor(String descriptor) { 86 Prototype result = internTable.get(descriptor); 87 if (result != null) { 88 return result; 89 } 90 91 Type[] params = makeParameterArray(descriptor); 92 int paramCount = 0; 93 int at = 1; 94 95 for (;;) { 96 int startAt = at; 97 char c = descriptor.charAt(at); 98 if (c == ')') { 99 at++; 100 break; 101 } 102 103 // Skip array markers. 104 while (c == '[') { 105 at++; 106 c = descriptor.charAt(at); 107 } 108 109 if (c == 'L') { 110 // It looks like the start of a class name; find the end. 111 int endAt = descriptor.indexOf(';', at); 112 if (endAt == -1) { 113 throw new IllegalArgumentException("bad descriptor"); 114 } 115 at = endAt + 1; 116 } else { 117 at++; 118 } 119 120 params[paramCount] = 121 Type.intern(descriptor.substring(startAt, at)); 122 paramCount++; 123 } 124 125 Type returnType = Type.internReturnType(descriptor.substring(at)); 126 StdTypeList parameterTypes = new StdTypeList(paramCount); 127 128 for (int i = 0; i < paramCount; i++) { 129 parameterTypes.set(i, params[i]); 130 } 131 132 return new Prototype(descriptor, returnType, parameterTypes); 133 } 134 135 public static void clearInternTable() { 136 internTable.clear(); 137 } 138 139 /** 140 * Helper for {@link #intern} which returns an empty array to 141 * populate with parsed parameter types, and which also ensures 142 * that there is a '(' at the start of the descriptor and a 143 * single ')' somewhere before the end. 144 * 145 * @param descriptor {@code non-null;} the descriptor string 146 * @return {@code non-null;} array large enough to hold all parsed parameter 147 * types, but which is likely actually larger than needed 148 */ 149 private static Type[] makeParameterArray(String descriptor) { 150 int length = descriptor.length(); 151 152 if (descriptor.charAt(0) != '(') { 153 throw new IllegalArgumentException("bad descriptor"); 154 } 155 156 /* 157 * This is a cheesy way to establish an upper bound on the 158 * number of parameters: Just count capital letters. 159 */ 160 int closeAt = 0; 161 int maxParams = 0; 162 for (int i = 1; i < length; i++) { 163 char c = descriptor.charAt(i); 164 if (c == ')') { 165 closeAt = i; 166 break; 167 } 168 if ((c >= 'A') && (c <= 'Z')) { 169 maxParams++; 170 } 171 } 172 173 if ((closeAt == 0) || (closeAt == (length - 1))) { 174 throw new IllegalArgumentException("bad descriptor"); 175 } 176 177 if (descriptor.indexOf(')', closeAt + 1) != -1) { 178 throw new IllegalArgumentException("bad descriptor"); 179 } 180 181 return new Type[maxParams]; 182 } 183 184 /** 185 * Interns an instance, adding to the descriptor as necessary based 186 * on the given definer, name, and flags. For example, an init 187 * method has an uninitialized object of type {@code definer} 188 * as its first argument. 189 * 190 * @param descriptor {@code non-null;} the descriptor string 191 * @param definer {@code non-null;} class the method is defined on 192 * @param isStatic whether this is a static method 193 * @param isInit whether this is an init method 194 * @return {@code non-null;} the interned instance 195 */ 196 public static Prototype intern(String descriptor, Type definer, 197 boolean isStatic, boolean isInit) { 198 Prototype base = intern(descriptor); 199 200 if (isStatic) { 201 return base; 202 } 203 204 if (isInit) { 205 definer = definer.asUninitialized(Integer.MAX_VALUE); 206 } 207 208 return base.withFirstParameter(definer); 209 } 210 211 /** 212 * Interns an instance which consists of the given number of 213 * {@code int}s along with the given return type 214 * 215 * @param returnType {@code non-null;} the return type 216 * @param count {@code > 0;} the number of elements in the prototype 217 * @return {@code non-null;} the interned instance 218 */ 219 public static Prototype internInts(Type returnType, int count) { 220 // Make the descriptor... 221 222 StringBuffer sb = new StringBuffer(100); 223 224 sb.append('('); 225 226 for (int i = 0; i < count; i++) { 227 sb.append('I'); 228 } 229 230 sb.append(')'); 231 sb.append(returnType.getDescriptor()); 232 233 // ...and intern it. 234 return intern(sb.toString()); 235 } 236 237 /** 238 * Constructs an instance. This is a private constructor; use one 239 * of the public static methods to get instances. 240 * 241 * @param descriptor {@code non-null;} the descriptor string 242 */ 243 private Prototype(String descriptor, Type returnType, 244 StdTypeList parameterTypes) { 245 if (descriptor == null) { 246 throw new NullPointerException("descriptor == null"); 247 } 248 249 if (returnType == null) { 250 throw new NullPointerException("returnType == null"); 251 } 252 253 if (parameterTypes == null) { 254 throw new NullPointerException("parameterTypes == null"); 255 } 256 257 this.descriptor = descriptor; 258 this.returnType = returnType; 259 this.parameterTypes = parameterTypes; 260 this.parameterFrameTypes = null; 261 } 262 263 /** {@inheritDoc} */ 264 @Override 265 public boolean equals(Object other) { 266 if (this == other) { 267 /* 268 * Since externally-visible instances are interned, this 269 * check helps weed out some easy cases. 270 */ 271 return true; 272 } 273 274 if (!(other instanceof Prototype)) { 275 return false; 276 } 277 278 return descriptor.equals(((Prototype) other).descriptor); 279 } 280 281 /** {@inheritDoc} */ 282 @Override 283 public int hashCode() { 284 return descriptor.hashCode(); 285 } 286 287 /** {@inheritDoc} */ 288 @Override 289 public int compareTo(Prototype other) { 290 if (this == other) { 291 return 0; 292 } 293 294 /* 295 * The return type is the major order, and then args in order, 296 * and then the shorter list comes first (similar to string 297 * sorting). 298 */ 299 300 int result = returnType.compareTo(other.returnType); 301 302 if (result != 0) { 303 return result; 304 } 305 306 int thisSize = parameterTypes.size(); 307 int otherSize = other.parameterTypes.size(); 308 int size = Math.min(thisSize, otherSize); 309 310 for (int i = 0; i < size; i++) { 311 Type thisType = parameterTypes.get(i); 312 Type otherType = other.parameterTypes.get(i); 313 314 result = thisType.compareTo(otherType); 315 316 if (result != 0) { 317 return result; 318 } 319 } 320 321 if (thisSize < otherSize) { 322 return -1; 323 } else if (thisSize > otherSize) { 324 return 1; 325 } else { 326 return 0; 327 } 328 } 329 330 /** {@inheritDoc} */ 331 @Override 332 public String toString() { 333 return descriptor; 334 } 335 336 /** 337 * Gets the descriptor string. 338 * 339 * @return {@code non-null;} the descriptor 340 */ 341 public String getDescriptor() { 342 return descriptor; 343 } 344 345 /** 346 * Gets the return type. 347 * 348 * @return {@code non-null;} the return type 349 */ 350 public Type getReturnType() { 351 return returnType; 352 } 353 354 /** 355 * Gets the list of parameter types. 356 * 357 * @return {@code non-null;} the list of parameter types 358 */ 359 public StdTypeList getParameterTypes() { 360 return parameterTypes; 361 } 362 363 /** 364 * Gets the list of frame types corresponding to the list of parameter 365 * types. The difference between the two lists (if any) is that all 366 * "intlike" types (see {@link Type#isIntlike}) are replaced by 367 * {@link Type#INT}. 368 * 369 * @return {@code non-null;} the list of parameter frame types 370 */ 371 public StdTypeList getParameterFrameTypes() { 372 if (parameterFrameTypes == null) { 373 int sz = parameterTypes.size(); 374 StdTypeList list = new StdTypeList(sz); 375 boolean any = false; 376 for (int i = 0; i < sz; i++) { 377 Type one = parameterTypes.get(i); 378 if (one.isIntlike()) { 379 any = true; 380 one = Type.INT; 381 } 382 list.set(i, one); 383 } 384 parameterFrameTypes = any ? list : parameterTypes; 385 } 386 387 return parameterFrameTypes; 388 } 389 390 /** 391 * Returns a new interned instance, which is the same as this instance, 392 * except that it has an additional parameter prepended to the original's 393 * argument list. 394 * 395 * @param param {@code non-null;} the new first parameter 396 * @return {@code non-null;} an appropriately-constructed instance 397 */ 398 public Prototype withFirstParameter(Type param) { 399 String newDesc = "(" + param.getDescriptor() + descriptor.substring(1); 400 StdTypeList newParams = parameterTypes.withFirst(param); 401 402 newParams.setImmutable(); 403 404 Prototype result = 405 new Prototype(newDesc, returnType, newParams); 406 407 return putIntern(result); 408 } 409 410 /** 411 * Puts the given instance in the intern table if it's not already 412 * there. If a conflicting value is already in the table, then leave it. 413 * Return the interned value. 414 * 415 * @param desc {@code non-null;} instance to make interned 416 * @return {@code non-null;} the actual interned object 417 */ 418 private static Prototype putIntern(Prototype desc) { 419 Prototype result = internTable.putIfAbsent(desc.getDescriptor(), desc); 420 return result != null ? result : desc; 421 } 422} 423