1 /* 2 * Copyright (c) 2015, 2016, Oracle and/or its affiliates. All rights reserved. 3 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. 4 * 5 * This code is free software; you can redistribute it and/or modify it 6 * under the terms of the GNU General Public License version 2 only, as 7 * published by the Free Software Foundation. Oracle designates this 8 * particular file as subject to the "Classpath" exception as provided 9 * by Oracle in the LICENSE file that accompanied this code. 10 * 11 * This code is distributed in the hope that it will be useful, but WITHOUT 12 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or 13 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License 14 * version 2 for more details (a copy is included in the LICENSE file that 15 * accompanied this code). 16 * 17 * You should have received a copy of the GNU General Public License version 18 * 2 along with this work; if not, write to the Free Software Foundation, 19 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. 20 * 21 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA 22 * or visit www.oracle.com if you need additional information or have any 23 * questions. 24 */ 25 26 package java.lang.invoke; 27 28 import jdk.internal.org.objectweb.asm.ClassWriter; 29 import jdk.internal.org.objectweb.asm.Label; 30 import jdk.internal.org.objectweb.asm.MethodVisitor; 31 import jdk.internal.org.objectweb.asm.Opcodes; 32 import jdk.internal.vm.annotation.ForceInline; 33 import jdk.internal.misc.Unsafe; 34 35 import java.lang.invoke.MethodHandles.Lookup; 36 import java.util.*; 37 import java.util.concurrent.ConcurrentHashMap; 38 import java.util.concurrent.ConcurrentMap; 39 import java.util.function.Function; 40 import sun.security.action.GetPropertyAction; 41 42 import static jdk.internal.org.objectweb.asm.Opcodes.*; 43 44 /** 45 * <p>Methods to facilitate the creation of String concatenation methods, that 46 * can be used to efficiently concatenate a known number of arguments of known 47 * types, possibly after type adaptation and partial evaluation of arguments. 48 * These methods are typically used as <em>bootstrap methods</em> for {@code 49 * invokedynamic} call sites, to support the <em>string concatenation</em> 50 * feature of the Java Programming Language. 51 * 52 * <p>Indirect access to the behavior specified by the provided {@code 53 * MethodHandle} proceeds in order through two phases: 54 * 55 * <ol> 56 * <li><em>Linkage</em> occurs when the methods in this class are invoked. 57 * They take as arguments a method type describing the concatenated arguments 58 * count and types, and optionally the String <em>recipe</em>, plus the 59 * constants that participate in the String concatenation. The details on 60 * accepted recipe shapes are described further below. Linkage may involve 61 * dynamically loading a new class that implements the expected concatenation 62 * behavior. The {@code CallSite} holds the {@code MethodHandle} pointing to the 63 * exact concatenation method. The concatenation methods may be shared among 64 * different {@code CallSite}s, e.g. if linkage methods produce them as pure 65 * functions.</li> 66 * 67 * <li><em>Invocation</em> occurs when a generated concatenation method is 68 * invoked with the exact dynamic arguments. This may occur many times for a 69 * single concatenation method. The method referenced by the behavior {@code 70 * MethodHandle} is invoked with the static arguments and any additional dynamic 71 * arguments provided on invocation, as if by {@link MethodHandle#invoke(Object...)}.</li> 72 * </ol> 73 * 74 * <p> This class provides two forms of linkage methods: a simple version 75 * ({@link #makeConcat(java.lang.invoke.MethodHandles.Lookup, String, 76 * MethodType)}) using only the dynamic arguments, and an advanced version 77 * ({@link #makeConcatWithConstants(java.lang.invoke.MethodHandles.Lookup, 78 * String, MethodType, String, Object...)} using the advanced forms of capturing 79 * the constant arguments. The advanced strategy can produce marginally better 80 * invocation bytecode, at the expense of exploding the number of shapes of 81 * string concatenation methods present at runtime, because those shapes would 82 * include constant static arguments as well. 83 * 84 * @author Aleksey Shipilev 85 * @author Remi Forax 86 * @author Peter Levart 87 * 88 * @apiNote 89 * <p>There is a JVM limit (classfile structural constraint): no method 90 * can call with more than 255 slots. This limits the number of static and 91 * dynamic arguments one can pass to bootstrap method. Since there are potential 92 * concatenation strategies that use {@code MethodHandle} combinators, we need 93 * to reserve a few empty slots on the parameter lists to capture the 94 * temporal results. This is why bootstrap methods in this factory do not accept 95 * more than 200 argument slots. Users requiring more than 200 argument slots in 96 * concatenation are expected to split the large concatenation in smaller 97 * expressions. 98 * 99 * @since 9 100 */ 101 public final class StringConcatFactory { 102 103 /** 104 * Tag used to demarcate an ordinary argument. 105 */ 106 private static final char TAG_ARG = '\u0001'; 107 108 /** 109 * Tag used to demarcate a constant. 110 */ 111 private static final char TAG_CONST = '\u0002'; 112 113 /** 114 * Maximum number of argument slots in String Concat call. 115 * 116 * While the maximum number of argument slots that indy call can handle is 253, 117 * we do not use all those slots, to let the strategies with MethodHandle 118 * combinators to use some arguments. 119 */ 120 private static final int MAX_INDY_CONCAT_ARG_SLOTS = 200; 121 122 /** 123 * Concatenation strategy to use. See {@link Strategy} for possible options. 124 * This option is controllable with -Djava.lang.invoke.stringConcat JDK option. 125 */ 126 private static Strategy STRATEGY; 127 128 /** 129 * Default strategy to use for concatenation. 130 */ 131 private static final Strategy DEFAULT_STRATEGY = Strategy.MH_INLINE_SIZED_EXACT; 132 133 private enum Strategy { 134 /** 135 * Bytecode generator, calling into {@link java.lang.StringBuilder}. 136 */ 137 BC_SB, 138 139 /** 140 * Bytecode generator, calling into {@link java.lang.StringBuilder}; 141 * but trying to estimate the required storage. 142 */ 143 BC_SB_SIZED, 144 145 /** 146 * Bytecode generator, calling into {@link java.lang.StringBuilder}; 147 * but computing the required storage exactly. 148 */ 149 BC_SB_SIZED_EXACT, 150 151 /** 152 * MethodHandle-based generator, that in the end calls into {@link java.lang.StringBuilder}. 153 * This strategy also tries to estimate the required storage. 154 */ 155 MH_SB_SIZED, 156 157 /** 158 * MethodHandle-based generator, that in the end calls into {@link java.lang.StringBuilder}. 159 * This strategy also estimate the required storage exactly. 160 */ 161 MH_SB_SIZED_EXACT, 162 163 /** 164 * MethodHandle-based generator, that constructs its own byte[] array from 165 * the arguments. It computes the required storage exactly. 166 */ 167 MH_INLINE_SIZED_EXACT 168 } 169 170 /** 171 * Enables debugging: this may print debugging messages, perform additional (non-neutral for performance) 172 * checks, etc. 173 */ 174 private static final boolean DEBUG; 175 176 /** 177 * Enables caching of strategy stubs. This may improve the linkage time by reusing the generated 178 * code, at the expense of contaminating the profiles. 179 */ 180 private static final boolean CACHE_ENABLE; 181 182 private static final ConcurrentMap<Key, MethodHandle> CACHE; 183 184 /** 185 * Dump generated classes to disk, for debugging purposes. 186 */ 187 private static final ProxyClassesDumper DUMPER; 188 189 static { 190 // In case we need to double-back onto the StringConcatFactory during this 191 // static initialization, make sure we have the reasonable defaults to complete 192 // the static initialization properly. After that, actual users would use the 193 // the proper values we have read from the the properties. 194 STRATEGY = DEFAULT_STRATEGY; 195 // CACHE_ENABLE = false; // implied 196 // CACHE = null; // implied 197 // DEBUG = false; // implied 198 // DUMPER = null; // implied 199 200 Properties props = GetPropertyAction.privilegedGetProperties(); 201 final String strategy = 202 props.getProperty("java.lang.invoke.stringConcat"); 203 CACHE_ENABLE = Boolean.parseBoolean( 204 props.getProperty("java.lang.invoke.stringConcat.cache")); 205 DEBUG = Boolean.parseBoolean( 206 props.getProperty("java.lang.invoke.stringConcat.debug")); 207 final String dumpPath = 208 props.getProperty("java.lang.invoke.stringConcat.dumpClasses"); 209 210 STRATEGY = (strategy == null) ? DEFAULT_STRATEGY : Strategy.valueOf(strategy); 211 CACHE = CACHE_ENABLE ? new ConcurrentHashMap<>() : null; 212 DUMPER = (dumpPath == null) ? null : ProxyClassesDumper.getInstance(dumpPath); 213 } 214 215 /** 216 * Cache key is a composite of: 217 * - class name, that lets to disambiguate stubs, to avoid excess sharing 218 * - method type, describing the dynamic arguments for concatenation 219 * - concat recipe, describing the constants and concat shape 220 */ 221 private static final class Key { 222 final String className; 223 final MethodType mt; 224 final Recipe recipe; 225 226 public Key(String className, MethodType mt, Recipe recipe) { 227 this.className = className; 228 this.mt = mt; 229 this.recipe = recipe; 230 } 231 232 @Override 233 public boolean equals(Object o) { 234 if (this == o) return true; 235 if (o == null || getClass() != o.getClass()) return false; 236 237 Key key = (Key) o; 238 239 if (!className.equals(key.className)) return false; 240 if (!mt.equals(key.mt)) return false; 241 if (!recipe.equals(key.recipe)) return false; 242 return true; 243 } 244 245 @Override 246 public int hashCode() { 247 int result = className.hashCode(); 248 result = 31 * result + mt.hashCode(); 249 result = 31 * result + recipe.hashCode(); 250 return result; 251 } 252 } 253 254 /** 255 * Parses the recipe string, and produces the traversable collection of 256 * {@link java.lang.invoke.StringConcatFactory.RecipeElement}-s for generator 257 * strategies. Notably, this class parses out the constants from the recipe 258 * and from other static arguments. 259 */ 260 private static final class Recipe { 261 private final List<RecipeElement> elements; 262 263 public Recipe(String src, Object[] constants) { 264 List<RecipeElement> el = new ArrayList<>(); 265 266 int constC = 0; 267 int argC = 0; 268 269 StringBuilder acc = new StringBuilder(); 270 271 for (int i = 0; i < src.length(); i++) { 272 char c = src.charAt(i); 273 274 if (c == TAG_CONST || c == TAG_ARG) { 275 // Detected a special tag, flush all accumulated characters 276 // as a constant first: 277 if (acc.length() > 0) { 278 el.add(new RecipeElement(acc.toString())); 279 acc.setLength(0); 280 } 281 if (c == TAG_CONST) { 282 Object cnst = constants[constC++]; 283 el.add(new RecipeElement(cnst)); 284 } else if (c == TAG_ARG) { 285 el.add(new RecipeElement(argC++)); 286 } 287 } else { 288 // Not a special characters, this is a constant embedded into 289 // the recipe itself. 290 acc.append(c); 291 } 292 } 293 294 // Flush the remaining characters as constant: 295 if (acc.length() > 0) { 296 el.add(new RecipeElement(acc.toString())); 297 } 298 299 elements = el; 300 } 301 302 public List<RecipeElement> getElements() { 303 return elements; 304 } 305 306 @Override 307 public boolean equals(Object o) { 308 if (this == o) return true; 309 if (o == null || getClass() != o.getClass()) return false; 310 311 Recipe recipe = (Recipe) o; 312 return elements.equals(recipe.elements); 313 } 314 315 @Override 316 public int hashCode() { 317 return elements.hashCode(); 318 } 319 } 320 321 private static final class RecipeElement { 322 private final Object value; 323 private final int argPos; 324 325 public RecipeElement(Object cnst) { 326 this.value = Objects.requireNonNull(cnst); 327 this.argPos = -1; 328 } 329 330 public RecipeElement(int arg) { 331 this.value = null; 332 assert (arg >= 0); 333 this.argPos = arg; 334 } 335 336 public Object getValue() { 337 assert (isConst()); 338 return value; 339 } 340 341 public int getArgPos() { 342 assert (!isConst()); 343 return argPos; 344 } 345 346 public boolean isConst() { 347 return argPos == -1; 348 } 349 350 @Override 351 public boolean equals(Object o) { 352 if (this == o) return true; 353 if (o == null || getClass() != o.getClass()) return false; 354 355 RecipeElement that = (RecipeElement) o; 356 357 boolean isConst = isConst(); 358 if (isConst != that.isConst()) return false; 359 if (isConst && (!value.equals(that.value))) return false; 360 if (!isConst && (argPos != that.argPos)) return false; 361 return true; 362 } 363 364 @Override 365 public int hashCode() { 366 return argPos; 367 } 368 } 369 370 /** 371 * Facilitates the creation of optimized String concatenation methods, that 372 * can be used to efficiently concatenate a known number of arguments of 373 * known types, possibly after type adaptation and partial evaluation of 374 * arguments. Typically used as a <em>bootstrap method</em> for {@code 375 * invokedynamic} call sites, to support the <em>string concatenation</em> 376 * feature of the Java Programming Language. 377 * 378 * <p>When the target of the {@code CallSite} returned from this method is 379 * invoked, it returns the result of String concatenation, taking all 380 * function arguments passed to the linkage method as inputs for 381 * concatenation. The target signature is given by {@code concatType}. 382 * The arguments are concatenated as per requirements stated in JLS 15.18.1 383 * "String Concatenation Operator +". Notably, the inputs are converted as 384 * per JLS 5.1.11 "String Conversion", and combined from left to right. 385 * 386 * <p>Assume the linkage arguments are as follows: 387 * 388 * <ul> 389 * <li>{@code concatType}, describing the {@code CallSite} signature</li> 390 * </ul> 391 * 392 * <p>Then the following linkage invariants must hold: 393 * 394 * <ul> 395 * <li>The parameter count in {@code concatType} is less than or equal to 200</li> 396 * 397 * <li>The return type in {@code concatType} is assignable from {@link java.lang.String}</li> 398 * </ul> 399 * 400 * @param lookup Represents a lookup context with the accessibility 401 * privileges of the caller. When used with {@code 402 * invokedynamic}, this is stacked automatically by the VM. 403 * @param name The name of the method to implement. This name is 404 * arbitrary, and has no meaning for this linkage method. 405 * When used with {@code invokedynamic}, this is provided by 406 * the {@code NameAndType} of the {@code InvokeDynamic} 407 * structure and is stacked automatically by the VM. 408 * @param concatType The expected signature of the {@code CallSite}. The 409 * parameter types represent the types of concatenation 410 * arguments; the return type is always assignable from {@link 411 * java.lang.String}. When used with {@code invokedynamic}, 412 * this is provided by the {@code NameAndType} of the {@code 413 * InvokeDynamic} structure and is stacked automatically by 414 * the VM. 415 * @return a CallSite whose target can be used to perform String 416 * concatenation, with dynamic concatenation arguments described by the given 417 * {@code concatType}. 418 * @throws StringConcatException If any of the linkage invariants described 419 * here are violated. 420 * @throws NullPointerException If any of the incoming arguments is null. 421 * This will never happen when a bootstrap method 422 * is called with invokedynamic. 423 * 424 * @jls 5.1.11 String Conversion 425 * @jls 15.18.1 String Concatenation Operator + 426 */ 427 public static CallSite makeConcat(MethodHandles.Lookup lookup, 428 String name, 429 MethodType concatType) throws StringConcatException { 430 if (DEBUG) { 431 System.out.println("StringConcatFactory " + STRATEGY + " is here for " + concatType); 432 } 433 434 return doStringConcat(lookup, name, concatType, true, null); 435 } 436 437 /** 438 * Facilitates the creation of optimized String concatenation methods, that 439 * can be used to efficiently concatenate a known number of arguments of 440 * known types, possibly after type adaptation and partial evaluation of 441 * arguments. Typically used as a <em>bootstrap method</em> for {@code 442 * invokedynamic} call sites, to support the <em>string concatenation</em> 443 * feature of the Java Programming Language. 444 * 445 * <p>When the target of the {@code CallSite} returned from this method is 446 * invoked, it returns the result of String concatenation, taking all 447 * function arguments and constants passed to the linkage method as inputs for 448 * concatenation. The target signature is given by {@code concatType}, and 449 * does not include constants. The arguments are concatenated as per requirements 450 * stated in JLS 15.18.1 "String Concatenation Operator +". Notably, the inputs 451 * are converted as per JLS 5.1.11 "String Conversion", and combined from left 452 * to right. 453 * 454 * <p>The concatenation <em>recipe</em> is a String description for the way to 455 * construct a concatenated String from the arguments and constants. The 456 * recipe is processed from left to right, and each character represents an 457 * input to concatenation. Recipe characters mean: 458 * 459 * <ul> 460 * 461 * <li><em>\1 (Unicode point 0001)</em>: an ordinary argument. This 462 * input is passed through dynamic argument, and is provided during the 463 * concatenation method invocation. This input can be null.</li> 464 * 465 * <li><em>\2 (Unicode point 0002):</em> a constant. This input passed 466 * through static bootstrap argument. This constant can be any value 467 * representable in constant pool. If necessary, the factory would call 468 * {@code toString} to perform a one-time String conversion.</li> 469 * 470 * <li><em>Any other char value:</em> a single character constant.</li> 471 * </ul> 472 * 473 * <p>Assume the linkage arguments are as follows: 474 * 475 * <ul> 476 * <li>{@code concatType}, describing the {@code CallSite} signature</li> 477 * <li>{@code recipe}, describing the String recipe</li> 478 * <li>{@code constants}, the vararg array of constants</li> 479 * </ul> 480 * 481 * <p>Then the following linkage invariants must hold: 482 * 483 * <ul> 484 * <li>The parameter count in {@code concatType} is less than or equal to 485 * 200</li> 486 * 487 * <li>The parameter count in {@code concatType} equals to number of \1 tags 488 * in {@code recipe}</li> 489 * 490 * <li>The return type in {@code concatType} is assignable 491 * from {@link java.lang.String}, and matches the return type of the 492 * returned {@link MethodHandle}</li> 493 * 494 * <li>The number of elements in {@code constants} equals to number of \2 495 * tags in {@code recipe}</li> 496 * </ul> 497 * 498 * @param lookup Represents a lookup context with the accessibility 499 * privileges of the caller. When used with {@code 500 * invokedynamic}, this is stacked automatically by the 501 * VM. 502 * @param name The name of the method to implement. This name is 503 * arbitrary, and has no meaning for this linkage method. 504 * When used with {@code invokedynamic}, this is provided 505 * by the {@code NameAndType} of the {@code InvokeDynamic} 506 * structure and is stacked automatically by the VM. 507 * @param concatType The expected signature of the {@code CallSite}. The 508 * parameter types represent the types of dynamic concatenation 509 * arguments; the return type is always assignable from {@link 510 * java.lang.String}. When used with {@code 511 * invokedynamic}, this is provided by the {@code 512 * NameAndType} of the {@code InvokeDynamic} structure and 513 * is stacked automatically by the VM. 514 * @param recipe Concatenation recipe, described above. 515 * @param constants A vararg parameter representing the constants passed to 516 * the linkage method. 517 * @return a CallSite whose target can be used to perform String 518 * concatenation, with dynamic concatenation arguments described by the given 519 * {@code concatType}. 520 * @throws StringConcatException If any of the linkage invariants described 521 * here are violated. 522 * @throws NullPointerException If any of the incoming arguments is null, or 523 * any constant in {@code recipe} is null. 524 * This will never happen when a bootstrap method 525 * is called with invokedynamic. 526 * @apiNote Code generators have three distinct ways to process a constant 527 * string operand S in a string concatenation expression. First, S can be 528 * materialized as a reference (using ldc) and passed as an ordinary argument 529 * (recipe '\1'). Or, S can be stored in the constant pool and passed as a 530 * constant (recipe '\2') . Finally, if S contains neither of the recipe 531 * tag characters ('\1', '\2') then S can be interpolated into the recipe 532 * itself, causing its characters to be inserted into the result. 533 * 534 * @jls 5.1.11 String Conversion 535 * @jls 15.18.1 String Concatenation Operator + 536 */ 537 public static CallSite makeConcatWithConstants(MethodHandles.Lookup lookup, 538 String name, 539 MethodType concatType, 540 String recipe, 541 Object... constants) throws StringConcatException { 542 if (DEBUG) { 543 System.out.println("StringConcatFactory " + STRATEGY + " is here for " + concatType + ", {" + recipe + "}, " + Arrays.toString(constants)); 544 } 545 546 return doStringConcat(lookup, name, concatType, false, recipe, constants); 547 } 548 549 private static CallSite doStringConcat(MethodHandles.Lookup lookup, 550 String name, 551 MethodType concatType, 552 boolean generateRecipe, 553 String recipe, 554 Object... constants) throws StringConcatException { 555 Objects.requireNonNull(lookup, "Lookup is null"); 556 Objects.requireNonNull(name, "Name is null"); 557 Objects.requireNonNull(concatType, "Concat type is null"); 558 Objects.requireNonNull(constants, "Constants are null"); 559 560 for (Object o : constants) { 561 Objects.requireNonNull(o, "Cannot accept null constants"); 562 } 563 564 if ((lookup.lookupModes() & MethodHandles.Lookup.PRIVATE) == 0) { 565 throw new StringConcatException(String.format( 566 "Invalid caller: %s", 567 lookup.lookupClass().getName())); 568 } 569 570 int cCount = 0; 571 int oCount = 0; 572 if (generateRecipe) { 573 // Mock the recipe to reuse the concat generator code 574 char[] value = new char[concatType.parameterCount()]; 575 Arrays.fill(value, TAG_ARG); 576 recipe = new String(value); 577 oCount = concatType.parameterCount(); 578 } else { 579 Objects.requireNonNull(recipe, "Recipe is null"); 580 581 for (int i = 0; i < recipe.length(); i++) { 582 char c = recipe.charAt(i); 583 if (c == TAG_CONST) cCount++; 584 if (c == TAG_ARG) oCount++; 585 } 586 } 587 588 if (oCount != concatType.parameterCount()) { 589 throw new StringConcatException( 590 "Mismatched number of concat arguments: recipe wants " + 591 oCount + 592 " arguments, but signature provides " + 593 concatType.parameterCount()); 594 } 595 596 if (cCount != constants.length) { 597 throw new StringConcatException( 598 "Mismatched number of concat constants: recipe wants " + 599 cCount + 600 " constants, but only " + 601 constants.length + 602 " are passed"); 603 } 604 605 if (!concatType.returnType().isAssignableFrom(String.class)) { 606 throw new StringConcatException( 607 "The return type should be compatible with String, but it is " + 608 concatType.returnType()); 609 } 610 611 if (concatType.parameterCount() > MAX_INDY_CONCAT_ARG_SLOTS) { 612 throw new StringConcatException("Too many concat argument slots: " + 613 concatType.parameterCount() + 614 ", can only accept " + 615 MAX_INDY_CONCAT_ARG_SLOTS); 616 } 617 618 String className = getClassName(lookup.lookupClass()); 619 MethodType mt = adaptType(concatType); 620 Recipe rec = new Recipe(recipe, constants); 621 622 MethodHandle mh; 623 if (CACHE_ENABLE) { 624 Key key = new Key(className, mt, rec); 625 mh = CACHE.get(key); 626 if (mh == null) { 627 mh = generate(lookup, className, mt, rec); 628 CACHE.put(key, mh); 629 } 630 } else { 631 mh = generate(lookup, className, mt, rec); 632 } 633 return new ConstantCallSite(mh.asType(concatType)); 634 } 635 636 /** 637 * Adapt method type to an API we are going to use. 638 * 639 * This strips the concrete classes from the signatures, thus preventing 640 * class leakage when we cache the concatenation stubs. 641 * 642 * @param args actual argument types 643 * @return argument types the strategy is going to use 644 */ 645 private static MethodType adaptType(MethodType args) { 646 Class<?>[] ptypes = args.parameterArray(); 647 boolean changed = false; 648 for (int i = 0; i < ptypes.length; i++) { 649 Class<?> ptype = ptypes[i]; 650 if (!ptype.isPrimitive() && 651 ptype != String.class && 652 ptype != Object.class) { // truncate to Object 653 ptypes[i] = Object.class; 654 changed = true; 655 } 656 // else other primitives or String or Object (unchanged) 657 } 658 return changed 659 ? MethodType.methodType(args.returnType(), ptypes) 660 : args; 661 } 662 663 private static String getClassName(Class<?> hostClass) throws StringConcatException { 664 /* 665 When cache is enabled, we want to cache as much as we can. 666 667 However, there are two peculiarities: 668 669 a) The generated class should stay within the same package as the 670 host class, to allow Unsafe.defineAnonymousClass access controls 671 to work properly. JDK may choose to fail with IllegalAccessException 672 when accessing a VM anonymous class with non-privileged callers, 673 see JDK-8058575. 674 675 b) If we mark the stub with some prefix, say, derived from the package 676 name because of (a), we can technically use that stub in other packages. 677 But the call stack traces would be extremely puzzling to unsuspecting users 678 and profiling tools: whatever stub wins the race, would be linked in all 679 similar callsites. 680 681 Therefore, we set the class prefix to match the host class package, and use 682 the prefix as the cache key too. This only affects BC_* strategies, and only when 683 cache is enabled. 684 */ 685 686 switch (STRATEGY) { 687 case BC_SB: 688 case BC_SB_SIZED: 689 case BC_SB_SIZED_EXACT: { 690 if (CACHE_ENABLE) { 691 String pkgName = hostClass.getPackageName(); 692 return (pkgName != null && !pkgName.isEmpty() ? pkgName.replace('.', '/') + "/" : "") + "Stubs$$StringConcat"; 693 } else { 694 return hostClass.getName().replace('.', '/') + "$$StringConcat"; 695 } 696 } 697 case MH_SB_SIZED: 698 case MH_SB_SIZED_EXACT: 699 case MH_INLINE_SIZED_EXACT: 700 // MethodHandle strategies do not need a class name. 701 return ""; 702 default: 703 throw new StringConcatException("Concatenation strategy " + STRATEGY + " is not implemented"); 704 } 705 } 706 707 private static MethodHandle generate(Lookup lookup, String className, MethodType mt, Recipe recipe) throws StringConcatException { 708 try { 709 switch (STRATEGY) { 710 case BC_SB: 711 return BytecodeStringBuilderStrategy.generate(lookup, className, mt, recipe, Mode.DEFAULT); 712 case BC_SB_SIZED: 713 return BytecodeStringBuilderStrategy.generate(lookup, className, mt, recipe, Mode.SIZED); 714 case BC_SB_SIZED_EXACT: 715 return BytecodeStringBuilderStrategy.generate(lookup, className, mt, recipe, Mode.SIZED_EXACT); 716 case MH_SB_SIZED: 717 return MethodHandleStringBuilderStrategy.generate(mt, recipe, Mode.SIZED); 718 case MH_SB_SIZED_EXACT: 719 return MethodHandleStringBuilderStrategy.generate(mt, recipe, Mode.SIZED_EXACT); 720 case MH_INLINE_SIZED_EXACT: 721 return MethodHandleInlineCopyStrategy.generate(mt, recipe); 722 default: 723 throw new StringConcatException("Concatenation strategy " + STRATEGY + " is not implemented"); 724 } 725 } catch (Throwable t) { 726 throw new StringConcatException("Generator failed", t); 727 } 728 } 729 730 private enum Mode { 731 DEFAULT(false, false), 732 SIZED(true, false), 733 SIZED_EXACT(true, true); 734 735 private final boolean sized; 736 private final boolean exact; 737 738 Mode(boolean sized, boolean exact) { 739 this.sized = sized; 740 this.exact = exact; 741 } 742 743 boolean isSized() { 744 return sized; 745 } 746 747 boolean isExact() { 748 return exact; 749 } 750 } 751 752 /** 753 * Bytecode StringBuilder strategy. 754 * 755 * <p>This strategy operates in three modes, gated by {@link Mode}. 756 * 757 * <p><b>{@link Strategy#BC_SB}: "bytecode StringBuilder".</b> 758 * 759 * <p>This strategy spins up the bytecode that has the same StringBuilder 760 * chain javac would otherwise emit. This strategy uses only the public API, 761 * and comes as the baseline for the current JDK behavior. On other words, 762 * this strategy moves the javac generated bytecode to runtime. The 763 * generated bytecode is loaded via Unsafe.defineAnonymousClass, but with 764 * the caller class coming from the BSM -- in other words, the protection 765 * guarantees are inherited from the method where invokedynamic was 766 * originally called. This means, among other things, that the bytecode is 767 * verified for all non-JDK uses. 768 * 769 * <p><b>{@link Strategy#BC_SB_SIZED}: "bytecode StringBuilder, but 770 * sized".</b> 771 * 772 * <p>This strategy acts similarly to {@link Strategy#BC_SB}, but it also 773 * tries to guess the capacity required for StringBuilder to accept all 774 * arguments without resizing. This strategy only makes an educated guess: 775 * it only guesses the space required for known types (e.g. primitives and 776 * Strings), but does not otherwise convert arguments. Therefore, the 777 * capacity estimate may be wrong, and StringBuilder may have to 778 * transparently resize or trim when doing the actual concatenation. While 779 * this does not constitute a correctness issue (in the end, that what BC_SB 780 * has to do anyway), this does pose a potential performance problem. 781 * 782 * <p><b>{@link Strategy#BC_SB_SIZED_EXACT}: "bytecode StringBuilder, but 783 * sized exactly".</b> 784 * 785 * <p>This strategy improves on @link Strategy#BC_SB_SIZED}, by first 786 * converting all arguments to String in order to get the exact capacity 787 * StringBuilder should have. The conversion is done via the public 788 * String.valueOf and/or Object.toString methods, and does not touch any 789 * private String API. 790 */ 791 private static final class BytecodeStringBuilderStrategy { 792 static final Unsafe UNSAFE = Unsafe.getUnsafe(); 793 static final int CLASSFILE_VERSION = 52; 794 static final String METHOD_NAME = "concat"; 795 796 private BytecodeStringBuilderStrategy() { 797 // no instantiation 798 } 799 800 private static MethodHandle generate(Lookup lookup, String className, MethodType args, Recipe recipe, Mode mode) throws Exception { 801 ClassWriter cw = new ClassWriter(ClassWriter.COMPUTE_MAXS + ClassWriter.COMPUTE_FRAMES); 802 803 cw.visit(CLASSFILE_VERSION, 804 ACC_SUPER + ACC_PUBLIC + ACC_FINAL + ACC_SYNTHETIC, 805 className, // Unsafe.defineAnonymousClass would append an unique ID 806 null, 807 "java/lang/Object", 808 null 809 ); 810 811 MethodVisitor mv = cw.visitMethod( 812 ACC_PUBLIC + ACC_STATIC + ACC_FINAL, 813 METHOD_NAME, 814 args.toMethodDescriptorString(), 815 null, 816 null); 817 818 mv.visitAnnotation("Ljdk/internal/vm/annotation/ForceInline;", true); 819 mv.visitCode(); 820 821 Class<?>[] arr = args.parameterArray(); 822 boolean[] guaranteedNonNull = new boolean[arr.length]; 823 824 if (mode.isExact()) { 825 /* 826 In exact mode, we need to convert all arguments to their String representations, 827 as this allows to compute their String sizes exactly. We cannot use private 828 methods for primitives in here, therefore we need to convert those as well. 829 830 We also record what arguments are guaranteed to be non-null as the result 831 of the conversion. String.valueOf does the null checks for us. The only 832 corner case to take care of is String.valueOf(Object) returning null itself. 833 834 Also, if any conversion happened, then the slot indices in the incoming 835 arguments are not equal to the final local maps. The only case this may break 836 is when converting 2-slot long/double argument to 1-slot String. Therefore, 837 we get away with tracking modified offset, since no conversion can overwrite 838 the upcoming the argument. 839 */ 840 841 int off = 0; 842 int modOff = 0; 843 for (int c = 0; c < arr.length; c++) { 844 Class<?> cl = arr[c]; 845 if (cl == String.class) { 846 if (off != modOff) { 847 mv.visitIntInsn(getLoadOpcode(cl), off); 848 mv.visitIntInsn(ASTORE, modOff); 849 } 850 } else { 851 mv.visitIntInsn(getLoadOpcode(cl), off); 852 mv.visitMethodInsn( 853 INVOKESTATIC, 854 "java/lang/String", 855 "valueOf", 856 getStringValueOfDesc(cl), 857 false 858 ); 859 mv.visitIntInsn(ASTORE, modOff); 860 arr[c] = String.class; 861 guaranteedNonNull[c] = cl.isPrimitive(); 862 } 863 off += getParameterSize(cl); 864 modOff += getParameterSize(String.class); 865 } 866 } 867 868 if (mode.isSized()) { 869 /* 870 When operating in sized mode (this includes exact mode), it makes sense to make 871 StringBuilder append chains look familiar to OptimizeStringConcat. For that, we 872 need to do null-checks early, not make the append chain shape simpler. 873 */ 874 875 int off = 0; 876 for (RecipeElement el : recipe.getElements()) { 877 if (el.isConst()) { 878 // Guaranteed non-null, no null check required. 879 } else { 880 // Null-checks are needed only for String arguments, and when a previous stage 881 // did not do implicit null-checks. If a String is null, we eagerly replace it 882 // with "null" constant. Note, we omit Objects here, because we don't call 883 // .length() on them down below. 884 int ac = el.getArgPos(); 885 Class<?> cl = arr[ac]; 886 if (cl == String.class && !guaranteedNonNull[ac]) { 887 Label l0 = new Label(); 888 mv.visitIntInsn(ALOAD, off); 889 mv.visitJumpInsn(IFNONNULL, l0); 890 mv.visitLdcInsn("null"); 891 mv.visitIntInsn(ASTORE, off); 892 mv.visitLabel(l0); 893 } 894 off += getParameterSize(cl); 895 } 896 } 897 } 898 899 // Prepare StringBuilder instance 900 mv.visitTypeInsn(NEW, "java/lang/StringBuilder"); 901 mv.visitInsn(DUP); 902 903 if (mode.isSized()) { 904 /* 905 Sized mode requires us to walk through the arguments, and estimate the final length. 906 In exact mode, this will operate on Strings only. This code would accumulate the 907 final length on stack. 908 */ 909 int len = 0; 910 int off = 0; 911 912 mv.visitInsn(ICONST_0); 913 914 for (RecipeElement el : recipe.getElements()) { 915 if (el.isConst()) { 916 Object cnst = el.getValue(); 917 len += cnst.toString().length(); 918 } else { 919 /* 920 If an argument is String, then we can call .length() on it. Sized/Exact modes have 921 converted arguments for us. If an argument is primitive, we can provide a guess 922 for its String representation size. 923 */ 924 Class<?> cl = arr[el.getArgPos()]; 925 if (cl == String.class) { 926 mv.visitIntInsn(ALOAD, off); 927 mv.visitMethodInsn( 928 INVOKEVIRTUAL, 929 "java/lang/String", 930 "length", 931 "()I", 932 false 933 ); 934 mv.visitInsn(IADD); 935 } else if (cl.isPrimitive()) { 936 len += estimateSize(cl); 937 } 938 off += getParameterSize(cl); 939 } 940 } 941 942 // Constants have non-zero length, mix in 943 if (len > 0) { 944 iconst(mv, len); 945 mv.visitInsn(IADD); 946 } 947 948 mv.visitMethodInsn( 949 INVOKESPECIAL, 950 "java/lang/StringBuilder", 951 "<init>", 952 "(I)V", 953 false 954 ); 955 } else { 956 mv.visitMethodInsn( 957 INVOKESPECIAL, 958 "java/lang/StringBuilder", 959 "<init>", 960 "()V", 961 false 962 ); 963 } 964 965 // At this point, we have a blank StringBuilder on stack, fill it in with .append calls. 966 { 967 int off = 0; 968 for (RecipeElement el : recipe.getElements()) { 969 String desc; 970 if (el.isConst()) { 971 Object cnst = el.getValue(); 972 mv.visitLdcInsn(cnst); 973 desc = getSBAppendDesc(cnst.getClass()); 974 } else { 975 Class<?> cl = arr[el.getArgPos()]; 976 mv.visitVarInsn(getLoadOpcode(cl), off); 977 off += getParameterSize(cl); 978 desc = getSBAppendDesc(cl); 979 } 980 981 mv.visitMethodInsn( 982 INVOKEVIRTUAL, 983 "java/lang/StringBuilder", 984 "append", 985 desc, 986 false 987 ); 988 } 989 } 990 991 if (DEBUG && mode.isExact()) { 992 /* 993 Exactness checks compare the final StringBuilder.capacity() with a resulting 994 String.length(). If these values disagree, that means StringBuilder had to perform 995 storage trimming, which defeats the purpose of exact strategies. 996 */ 997 998 /* 999 The logic for this check is as follows: 1000 1001 Stack before: Op: 1002 (SB) dup, dup 1003 (SB, SB, SB) capacity() 1004 (int, SB, SB) swap 1005 (SB, int, SB) toString() 1006 (S, int, SB) length() 1007 (int, int, SB) if_icmpeq 1008 (SB) <end> 1009 1010 Note that it leaves the same StringBuilder on exit, like the one on enter. 1011 */ 1012 1013 mv.visitInsn(DUP); 1014 mv.visitInsn(DUP); 1015 1016 mv.visitMethodInsn( 1017 INVOKEVIRTUAL, 1018 "java/lang/StringBuilder", 1019 "capacity", 1020 "()I", 1021 false 1022 ); 1023 1024 mv.visitInsn(SWAP); 1025 1026 mv.visitMethodInsn( 1027 INVOKEVIRTUAL, 1028 "java/lang/StringBuilder", 1029 "toString", 1030 "()Ljava/lang/String;", 1031 false 1032 ); 1033 1034 mv.visitMethodInsn( 1035 INVOKEVIRTUAL, 1036 "java/lang/String", 1037 "length", 1038 "()I", 1039 false 1040 ); 1041 1042 Label l0 = new Label(); 1043 mv.visitJumpInsn(IF_ICMPEQ, l0); 1044 1045 mv.visitTypeInsn(NEW, "java/lang/AssertionError"); 1046 mv.visitInsn(DUP); 1047 mv.visitLdcInsn("Failed exactness check"); 1048 mv.visitMethodInsn(INVOKESPECIAL, 1049 "java/lang/AssertionError", 1050 "<init>", 1051 "(Ljava/lang/Object;)V", 1052 false); 1053 mv.visitInsn(ATHROW); 1054 1055 mv.visitLabel(l0); 1056 } 1057 1058 mv.visitMethodInsn( 1059 INVOKEVIRTUAL, 1060 "java/lang/StringBuilder", 1061 "toString", 1062 "()Ljava/lang/String;", 1063 false 1064 ); 1065 1066 mv.visitInsn(ARETURN); 1067 1068 mv.visitMaxs(-1, -1); 1069 mv.visitEnd(); 1070 cw.visitEnd(); 1071 1072 byte[] classBytes = cw.toByteArray(); 1073 try { 1074 Class<?> hostClass = lookup.lookupClass(); 1075 Class<?> innerClass = UNSAFE.defineAnonymousClass(hostClass, classBytes, null); 1076 UNSAFE.ensureClassInitialized(innerClass); 1077 dumpIfEnabled(innerClass.getName(), classBytes); 1078 return Lookup.IMPL_LOOKUP.findStatic(innerClass, METHOD_NAME, args); 1079 } catch (Throwable e) { 1080 dumpIfEnabled(className + "$$FAILED", classBytes); 1081 throw new StringConcatException("Error while spinning the class", e); 1082 } 1083 } 1084 1085 private static void dumpIfEnabled(String name, byte[] bytes) { 1086 if (DUMPER != null) { 1087 DUMPER.dumpClass(name, bytes); 1088 } 1089 } 1090 1091 private static String getSBAppendDesc(Class<?> cl) { 1092 if (cl.isPrimitive()) { 1093 if (cl == Integer.TYPE || cl == Byte.TYPE || cl == Short.TYPE) { 1094 return "(I)Ljava/lang/StringBuilder;"; 1095 } else if (cl == Boolean.TYPE) { 1096 return "(Z)Ljava/lang/StringBuilder;"; 1097 } else if (cl == Character.TYPE) { 1098 return "(C)Ljava/lang/StringBuilder;"; 1099 } else if (cl == Double.TYPE) { 1100 return "(D)Ljava/lang/StringBuilder;"; 1101 } else if (cl == Float.TYPE) { 1102 return "(F)Ljava/lang/StringBuilder;"; 1103 } else if (cl == Long.TYPE) { 1104 return "(J)Ljava/lang/StringBuilder;"; 1105 } else { 1106 throw new IllegalStateException("Unhandled primitive StringBuilder.append: " + cl); 1107 } 1108 } else if (cl == String.class) { 1109 return "(Ljava/lang/String;)Ljava/lang/StringBuilder;"; 1110 } else { 1111 return "(Ljava/lang/Object;)Ljava/lang/StringBuilder;"; 1112 } 1113 } 1114 1115 private static String getStringValueOfDesc(Class<?> cl) { 1116 if (cl.isPrimitive()) { 1117 if (cl == Integer.TYPE || cl == Byte.TYPE || cl == Short.TYPE) { 1118 return "(I)Ljava/lang/String;"; 1119 } else if (cl == Boolean.TYPE) { 1120 return "(Z)Ljava/lang/String;"; 1121 } else if (cl == Character.TYPE) { 1122 return "(C)Ljava/lang/String;"; 1123 } else if (cl == Double.TYPE) { 1124 return "(D)Ljava/lang/String;"; 1125 } else if (cl == Float.TYPE) { 1126 return "(F)Ljava/lang/String;"; 1127 } else if (cl == Long.TYPE) { 1128 return "(J)Ljava/lang/String;"; 1129 } else { 1130 throw new IllegalStateException("Unhandled String.valueOf: " + cl); 1131 } 1132 } else if (cl == String.class) { 1133 return "(Ljava/lang/String;)Ljava/lang/String;"; 1134 } else { 1135 return "(Ljava/lang/Object;)Ljava/lang/String;"; 1136 } 1137 } 1138 1139 /** 1140 * The following method is copied from 1141 * org.objectweb.asm.commons.InstructionAdapter. Part of ASM: a very small 1142 * and fast Java bytecode manipulation framework. 1143 * Copyright (c) 2000-2005 INRIA, France Telecom All rights reserved. 1144 */ 1145 private static void iconst(MethodVisitor mv, final int cst) { 1146 if (cst >= -1 && cst <= 5) { 1147 mv.visitInsn(Opcodes.ICONST_0 + cst); 1148 } else if (cst >= Byte.MIN_VALUE && cst <= Byte.MAX_VALUE) { 1149 mv.visitIntInsn(Opcodes.BIPUSH, cst); 1150 } else if (cst >= Short.MIN_VALUE && cst <= Short.MAX_VALUE) { 1151 mv.visitIntInsn(Opcodes.SIPUSH, cst); 1152 } else { 1153 mv.visitLdcInsn(cst); 1154 } 1155 } 1156 1157 private static int getLoadOpcode(Class<?> c) { 1158 if (c == Void.TYPE) { 1159 throw new InternalError("Unexpected void type of load opcode"); 1160 } 1161 return ILOAD + getOpcodeOffset(c); 1162 } 1163 1164 private static int getOpcodeOffset(Class<?> c) { 1165 if (c.isPrimitive()) { 1166 if (c == Long.TYPE) { 1167 return 1; 1168 } else if (c == Float.TYPE) { 1169 return 2; 1170 } else if (c == Double.TYPE) { 1171 return 3; 1172 } 1173 return 0; 1174 } else { 1175 return 4; 1176 } 1177 } 1178 1179 private static int getParameterSize(Class<?> c) { 1180 if (c == Void.TYPE) { 1181 return 0; 1182 } else if (c == Long.TYPE || c == Double.TYPE) { 1183 return 2; 1184 } 1185 return 1; 1186 } 1187 } 1188 1189 /** 1190 * MethodHandle StringBuilder strategy. 1191 * 1192 * <p>This strategy operates in two modes, gated by {@link Mode}. 1193 * 1194 * <p><b>{@link Strategy#MH_SB_SIZED}: "MethodHandles StringBuilder, 1195 * sized".</b> 1196 * 1197 * <p>This strategy avoids spinning up the bytecode by building the 1198 * computation on MethodHandle combinators. The computation is built with 1199 * public MethodHandle APIs, resolved from a public Lookup sequence, and 1200 * ends up calling the public StringBuilder API. Therefore, this strategy 1201 * does not use any private API at all, even the Unsafe.defineAnonymousClass, 1202 * since everything is handled under cover by java.lang.invoke APIs. 1203 * 1204 * <p><b>{@link Strategy#MH_SB_SIZED_EXACT}: "MethodHandles StringBuilder, 1205 * sized exactly".</b> 1206 * 1207 * <p>This strategy improves on @link Strategy#MH_SB_SIZED}, by first 1208 * converting all arguments to String in order to get the exact capacity 1209 * StringBuilder should have. The conversion is done via the public 1210 * String.valueOf and/or Object.toString methods, and does not touch any 1211 * private String API. 1212 */ 1213 private static final class MethodHandleStringBuilderStrategy { 1214 1215 private MethodHandleStringBuilderStrategy() { 1216 // no instantiation 1217 } 1218 1219 private static MethodHandle generate(MethodType mt, Recipe recipe, Mode mode) throws Exception { 1220 int pc = mt.parameterCount(); 1221 1222 Class<?>[] ptypes = mt.parameterArray(); 1223 MethodHandle[] filters = new MethodHandle[ptypes.length]; 1224 for (int i = 0; i < ptypes.length; i++) { 1225 MethodHandle filter; 1226 switch (mode) { 1227 case SIZED: 1228 // In sized mode, we convert all references and floats/doubles 1229 // to String: there is no specialization for different 1230 // classes in StringBuilder API, and it will convert to 1231 // String internally anyhow. 1232 filter = Stringifiers.forMost(ptypes[i]); 1233 break; 1234 case SIZED_EXACT: 1235 // In exact mode, we convert everything to String: 1236 // this helps to compute the storage exactly. 1237 filter = Stringifiers.forAny(ptypes[i]); 1238 break; 1239 default: 1240 throw new StringConcatException("Not supported"); 1241 } 1242 if (filter != null) { 1243 filters[i] = filter; 1244 ptypes[i] = filter.type().returnType(); 1245 } 1246 } 1247 1248 List<Class<?>> ptypesList = Arrays.asList(ptypes); 1249 MethodHandle[] lengthers = new MethodHandle[pc]; 1250 1251 // Figure out lengths: constants' lengths can be deduced on the spot. 1252 // All reference arguments were filtered to String in the combinators below, so we can 1253 // call the usual String.length(). Primitive values string sizes can be estimated. 1254 int initial = 0; 1255 for (RecipeElement el : recipe.getElements()) { 1256 if (el.isConst()) { 1257 Object cnst = el.getValue(); 1258 initial += cnst.toString().length(); 1259 } else { 1260 final int i = el.getArgPos(); 1261 Class<?> type = ptypesList.get(i); 1262 if (type.isPrimitive()) { 1263 MethodHandle est = MethodHandles.constant(int.class, estimateSize(type)); 1264 est = MethodHandles.dropArguments(est, 0, type); 1265 lengthers[i] = est; 1266 } else { 1267 lengthers[i] = STRING_LENGTH; 1268 } 1269 } 1270 } 1271 1272 // Create (StringBuilder, <args>) shape for appending: 1273 MethodHandle builder = MethodHandles.dropArguments(MethodHandles.identity(StringBuilder.class), 1, ptypesList); 1274 1275 // Compose append calls. This is done in reverse because the application order is 1276 // reverse as well. 1277 List<RecipeElement> elements = recipe.getElements(); 1278 for (int i = elements.size() - 1; i >= 0; i--) { 1279 RecipeElement el = elements.get(i); 1280 MethodHandle appender; 1281 if (el.isConst()) { 1282 Object constant = el.getValue(); 1283 MethodHandle mh = appender(adaptToStringBuilder(constant.getClass())); 1284 appender = MethodHandles.insertArguments(mh, 1, constant); 1285 } else { 1286 int ac = el.getArgPos(); 1287 appender = appender(ptypesList.get(ac)); 1288 1289 // Insert dummy arguments to match the prefix in the signature. 1290 // The actual appender argument will be the ac-ith argument. 1291 if (ac != 0) { 1292 appender = MethodHandles.dropArguments(appender, 1, ptypesList.subList(0, ac)); 1293 } 1294 } 1295 builder = MethodHandles.foldArguments(builder, appender); 1296 } 1297 1298 // Build the sub-tree that adds the sizes and produces a StringBuilder: 1299 1300 // a) Start with the reducer that accepts all arguments, plus one 1301 // slot for the initial value. Inject the initial value right away. 1302 // This produces (<ints>)int shape: 1303 MethodHandle sum = getReducerFor(pc + 1); 1304 MethodHandle adder = MethodHandles.insertArguments(sum, 0, initial); 1305 1306 // b) Apply lengthers to transform arguments to lengths, producing (<args>)int 1307 adder = MethodHandles.filterArguments(adder, 0, lengthers); 1308 1309 // c) Instantiate StringBuilder (<args>)int -> (<args>)StringBuilder 1310 MethodHandle newBuilder = MethodHandles.filterReturnValue(adder, NEW_STRING_BUILDER); 1311 1312 // d) Fold in StringBuilder constructor, this produces (<args>)StringBuilder 1313 MethodHandle mh = MethodHandles.foldArguments(builder, newBuilder); 1314 1315 // Convert non-primitive arguments to Strings 1316 mh = MethodHandles.filterArguments(mh, 0, filters); 1317 1318 // Convert (<args>)StringBuilder to (<args>)String 1319 if (DEBUG && mode.isExact()) { 1320 mh = MethodHandles.filterReturnValue(mh, BUILDER_TO_STRING_CHECKED); 1321 } else { 1322 mh = MethodHandles.filterReturnValue(mh, BUILDER_TO_STRING); 1323 } 1324 1325 return mh; 1326 } 1327 1328 private static MethodHandle getReducerFor(int cnt) { 1329 return SUMMERS.computeIfAbsent(cnt, SUMMER); 1330 } 1331 1332 private static MethodHandle appender(Class<?> appendType) { 1333 MethodHandle appender = lookupVirtual(MethodHandles.publicLookup(), StringBuilder.class, "append", 1334 StringBuilder.class, adaptToStringBuilder(appendType)); 1335 1336 // appenders should return void, this would not modify the target signature during folding 1337 MethodType nt = MethodType.methodType(void.class, StringBuilder.class, appendType); 1338 return appender.asType(nt); 1339 } 1340 1341 private static String toStringChecked(StringBuilder sb) { 1342 String s = sb.toString(); 1343 if (s.length() != sb.capacity()) { 1344 throw new AssertionError("Exactness check failed: result length = " + s.length() + ", buffer capacity = " + sb.capacity()); 1345 } 1346 return s; 1347 } 1348 1349 private static int sum(int v1, int v2) { 1350 return v1 + v2; 1351 } 1352 1353 private static int sum(int v1, int v2, int v3) { 1354 return v1 + v2 + v3; 1355 } 1356 1357 private static int sum(int v1, int v2, int v3, int v4) { 1358 return v1 + v2 + v3 + v4; 1359 } 1360 1361 private static int sum(int v1, int v2, int v3, int v4, int v5) { 1362 return v1 + v2 + v3 + v4 + v5; 1363 } 1364 1365 private static int sum(int v1, int v2, int v3, int v4, int v5, int v6) { 1366 return v1 + v2 + v3 + v4 + v5 + v6; 1367 } 1368 1369 private static int sum(int v1, int v2, int v3, int v4, int v5, int v6, int v7) { 1370 return v1 + v2 + v3 + v4 + v5 + v6 + v7; 1371 } 1372 1373 private static int sum(int v1, int v2, int v3, int v4, int v5, int v6, int v7, int v8) { 1374 return v1 + v2 + v3 + v4 + v5 + v6 + v7 + v8; 1375 } 1376 1377 private static int sum(int initial, int[] vs) { 1378 int sum = initial; 1379 for (int v : vs) { 1380 sum += v; 1381 } 1382 return sum; 1383 } 1384 1385 private static final ConcurrentMap<Integer, MethodHandle> SUMMERS; 1386 1387 // This one is deliberately non-lambdified to optimize startup time: 1388 private static final Function<Integer, MethodHandle> SUMMER = new Function<Integer, MethodHandle>() { 1389 @Override 1390 public MethodHandle apply(Integer cnt) { 1391 if (cnt == 1) { 1392 return MethodHandles.identity(int.class); 1393 } else if (cnt <= 8) { 1394 // Variable-arity collectors are not as efficient as small-count methods, 1395 // unroll some initial sizes. 1396 Class<?>[] cls = new Class<?>[cnt]; 1397 Arrays.fill(cls, int.class); 1398 return lookupStatic(Lookup.IMPL_LOOKUP, MethodHandleStringBuilderStrategy.class, "sum", int.class, cls); 1399 } else { 1400 return lookupStatic(Lookup.IMPL_LOOKUP, MethodHandleStringBuilderStrategy.class, "sum", int.class, int.class, int[].class) 1401 .asCollector(int[].class, cnt - 1); 1402 } 1403 } 1404 }; 1405 1406 private static final MethodHandle NEW_STRING_BUILDER, STRING_LENGTH, BUILDER_TO_STRING, BUILDER_TO_STRING_CHECKED; 1407 1408 static { 1409 SUMMERS = new ConcurrentHashMap<>(); 1410 Lookup publicLookup = MethodHandles.publicLookup(); 1411 NEW_STRING_BUILDER = lookupConstructor(publicLookup, StringBuilder.class, int.class); 1412 STRING_LENGTH = lookupVirtual(publicLookup, String.class, "length", int.class); 1413 BUILDER_TO_STRING = lookupVirtual(publicLookup, StringBuilder.class, "toString", String.class); 1414 if (DEBUG) { 1415 BUILDER_TO_STRING_CHECKED = lookupStatic(MethodHandles.Lookup.IMPL_LOOKUP, 1416 MethodHandleStringBuilderStrategy.class, "toStringChecked", String.class, StringBuilder.class); 1417 } else { 1418 BUILDER_TO_STRING_CHECKED = null; 1419 } 1420 } 1421 1422 } 1423 1424 1425 /** 1426 * <p><b>{@link Strategy#MH_INLINE_SIZED_EXACT}: "MethodHandles inline, 1427 * sized exactly".</b> 1428 * 1429 * <p>This strategy replicates what StringBuilders are doing: it builds the 1430 * byte[] array on its own and passes that byte[] array to String 1431 * constructor. This strategy requires access to some private APIs in JDK, 1432 * most notably, the read-only Integer/Long.stringSize methods that measure 1433 * the character length of the integers, and the private String constructor 1434 * that accepts byte[] arrays without copying. While this strategy assumes a 1435 * particular implementation details for String, this opens the door for 1436 * building a very optimal concatenation sequence. This is the only strategy 1437 * that requires porting if there are private JDK changes occur. 1438 */ 1439 private static final class MethodHandleInlineCopyStrategy { 1440 static final Unsafe UNSAFE = Unsafe.getUnsafe(); 1441 1442 private MethodHandleInlineCopyStrategy() { 1443 // no instantiation 1444 } 1445 1446 static MethodHandle generate(MethodType mt, Recipe recipe) throws Throwable { 1447 1448 // Create filters and obtain filtered parameter types. Filters would be used in the beginning 1449 // to convert the incoming arguments into the arguments we can process (e.g. Objects -> Strings). 1450 // The filtered argument type list is used all over in the combinators below. 1451 Class<?>[] ptypes = mt.parameterArray(); 1452 MethodHandle[] filters = null; 1453 for (int i = 0; i < ptypes.length; i++) { 1454 MethodHandle filter = Stringifiers.forMost(ptypes[i]); 1455 if (filter != null) { 1456 if (filters == null) { 1457 filters = new MethodHandle[ptypes.length]; 1458 } 1459 filters[i] = filter; 1460 ptypes[i] = filter.type().returnType(); 1461 } 1462 } 1463 List<Class<?>> ptypesList = Arrays.asList(ptypes); 1464 1465 // Start building the combinator tree. The tree "starts" with (<parameters>)String, and "finishes" 1466 // with the (int, byte[], byte)String in String helper. The combinators are assembled bottom-up, 1467 // which makes the code arguably hard to read. 1468 1469 // Drop all remaining parameter types, leave only helper arguments: 1470 MethodHandle mh; 1471 1472 mh = MethodHandles.dropArguments(NEW_STRING, 2, ptypes); 1473 mh = MethodHandles.dropArguments(mh, 0, int.class); 1474 1475 // Safety: check that remaining index is zero -- that would mean the storage is completely 1476 // overwritten, and no leakage of uninitialized data occurred. 1477 mh = MethodHandles.filterArgument(mh, 0, CHECK_INDEX); 1478 1479 // Mix in prependers. This happens when (int, byte[], byte) = (index, storage, coder) is already 1480 // known from the combinators below. We are assembling the string backwards, so "index" is the 1481 // *ending* index. 1482 for (RecipeElement el : recipe.getElements()) { 1483 MethodHandle prepender; 1484 if (el.isConst()) { 1485 Object cnst = el.getValue(); 1486 prepender = MethodHandles.insertArguments(prepender(cnst.getClass()), 3, cnst); 1487 } else { 1488 int pos = el.getArgPos(); 1489 prepender = selectArgument(prepender(ptypesList.get(pos)), 3, ptypesList, pos); 1490 } 1491 1492 // Remove "old" index from arguments 1493 mh = MethodHandles.dropArguments(mh, 1, int.class); 1494 1495 // Do the prepend, and put "new" index at index 0 1496 mh = MethodHandles.foldArguments(mh, prepender); 1497 } 1498 1499 // Prepare the argument list for prepending. The tree below would instantiate 1500 // the storage byte[] into argument 0, so we need to swap "storage" and "index". 1501 // The index at this point equals to "size", and resides at argument 1. 1502 { 1503 MethodType nmt = mh.type() 1504 .changeParameterType(0, byte[].class) 1505 .changeParameterType(1, int.class); 1506 mh = MethodHandles.permuteArguments(mh, nmt, swap10(nmt.parameterCount())); 1507 } 1508 1509 // Fold in byte[] instantiation at argument 0. 1510 MethodHandle combiner = MethodHandles.dropArguments(NEW_ARRAY, 2, ptypesList); 1511 mh = MethodHandles.foldArguments(mh, combiner); 1512 1513 // Start combining length and coder mixers. 1514 // 1515 // Length is easy: constant lengths can be computed on the spot, and all non-constant 1516 // shapes have been either converted to Strings, or explicit methods for getting the 1517 // string length out of primitives are provided. 1518 // 1519 // Coders are more interesting. Only Object, String and char arguments (and constants) 1520 // can have non-Latin1 encoding. It is easier to blindly convert constants to String, 1521 // and deduce the coder from there. Arguments would be either converted to Strings 1522 // during the initial filtering, or handled by primitive specializations in CODER_MIXERS. 1523 // 1524 // The method handle shape after all length and coder mixers is: 1525 // (int, byte, <args>)String = ("index", "coder", <args>) 1526 byte initialCoder = INITIAL_CODER; 1527 int initialLen = 0; // initial length, in characters 1528 for (RecipeElement el : recipe.getElements()) { 1529 if (el.isConst()) { 1530 Object constant = el.getValue(); 1531 String s = constant.toString(); 1532 initialCoder = (byte) coderMixer(String.class).invoke(initialCoder, s); 1533 initialLen += s.length(); 1534 } else { 1535 int ac = el.getArgPos(); 1536 1537 Class<?> argClass = ptypesList.get(ac); 1538 MethodHandle lm = selectArgument(lengthMixer(argClass), 1, ptypesList, ac); 1539 lm = MethodHandles.dropArguments(lm, 0, byte.class); // (*) 1540 lm = MethodHandles.dropArguments(lm, 2, byte.class); 1541 1542 MethodHandle cm = selectArgument(coderMixer(argClass), 1, ptypesList, ac); 1543 cm = MethodHandles.dropArguments(cm, 0, int.class); // (**) 1544 1545 // Read this bottom up: 1546 1547 // 4. Drop old index and coder, producing ("new-index", "new-coder", <args>) 1548 mh = MethodHandles.dropArguments(mh, 2, int.class, byte.class); 1549 1550 // 3. Compute "new-index", producing ("new-index", "new-coder", "old-index", "old-coder", <args>) 1551 // Length mixer ignores both "new-coder" and "old-coder" due to dropArguments above (*) 1552 mh = MethodHandles.foldArguments(mh, lm); 1553 1554 // 2. Compute "new-coder", producing ("new-coder", "old-index", "old-coder", <args>) 1555 // Coder mixer ignores the "old-index" arg due to dropArguments above (**) 1556 mh = MethodHandles.foldArguments(mh, cm); 1557 1558 // 1. The mh shape here is ("old-index", "old-coder", <args>) 1559 } 1560 } 1561 1562 // Insert initial lengths and coders here. 1563 // The method handle shape here is (<args>). 1564 mh = MethodHandles.insertArguments(mh, 0, initialLen, initialCoder); 1565 1566 // Apply filters, converting the arguments: 1567 if (filters != null) { 1568 mh = MethodHandles.filterArguments(mh, 0, filters); 1569 } 1570 1571 return mh; 1572 } 1573 1574 private static int[] swap10(int count) { 1575 int[] perm = new int[count]; 1576 perm[0] = 1; 1577 perm[1] = 0; 1578 for (int i = 2; i < count; i++) { 1579 perm[i] = i; 1580 } 1581 return perm; 1582 } 1583 1584 // Adapts: (...prefix..., parameter[pos])R -> (...prefix..., ...parameters...)R 1585 private static MethodHandle selectArgument(MethodHandle mh, int prefix, List<Class<?>> ptypes, int pos) { 1586 if (pos == 0) { 1587 return MethodHandles.dropArguments(mh, prefix + 1, ptypes.subList(1, ptypes.size())); 1588 } else if (pos == ptypes.size() - 1) { 1589 return MethodHandles.dropArguments(mh, prefix, ptypes.subList(0, ptypes.size() - 1)); 1590 } else { // 0 < pos < ptypes.size() - 1 1591 MethodHandle t = MethodHandles.dropArguments(mh, prefix, ptypes.subList(0, pos)); 1592 return MethodHandles.dropArguments(t, prefix + 1 + pos, ptypes.subList(pos + 1, ptypes.size())); 1593 } 1594 } 1595 1596 @ForceInline 1597 private static byte[] newArray(int length, byte coder) { 1598 return (byte[]) UNSAFE.allocateUninitializedArray(byte.class, length << coder); 1599 } 1600 1601 @ForceInline 1602 private static int checkIndex(int index) { 1603 if (index != 0) { 1604 throw new IllegalStateException("Storage is not completely initialized, " + index + " bytes left"); 1605 } 1606 return index; 1607 } 1608 1609 private static MethodHandle prepender(Class<?> cl) { 1610 return PREPENDERS.computeIfAbsent(cl, PREPEND); 1611 } 1612 1613 private static MethodHandle coderMixer(Class<?> cl) { 1614 return CODER_MIXERS.computeIfAbsent(cl, CODER_MIX); 1615 } 1616 1617 private static MethodHandle lengthMixer(Class<?> cl) { 1618 return LENGTH_MIXERS.computeIfAbsent(cl, LENGTH_MIX); 1619 } 1620 1621 // This one is deliberately non-lambdified to optimize startup time: 1622 private static final Function<Class<?>, MethodHandle> PREPEND = new Function<Class<?>, MethodHandle>() { 1623 @Override 1624 public MethodHandle apply(Class<?> c) { 1625 return lookupStatic(Lookup.IMPL_LOOKUP, STRING_HELPER, "prepend", int.class, int.class, byte[].class, byte.class, c); 1626 } 1627 }; 1628 1629 // This one is deliberately non-lambdified to optimize startup time: 1630 private static final Function<Class<?>, MethodHandle> CODER_MIX = new Function<Class<?>, MethodHandle>() { 1631 @Override 1632 public MethodHandle apply(Class<?> c) { 1633 return lookupStatic(Lookup.IMPL_LOOKUP, STRING_HELPER, "mixCoder", byte.class, byte.class, c); 1634 } 1635 }; 1636 1637 // This one is deliberately non-lambdified to optimize startup time: 1638 private static final Function<Class<?>, MethodHandle> LENGTH_MIX = new Function<Class<?>, MethodHandle>() { 1639 @Override 1640 public MethodHandle apply(Class<?> c) { 1641 return lookupStatic(Lookup.IMPL_LOOKUP, STRING_HELPER, "mixLen", int.class, int.class, c); 1642 } 1643 }; 1644 1645 private static final MethodHandle NEW_STRING; 1646 private static final MethodHandle CHECK_INDEX; 1647 private static final MethodHandle NEW_ARRAY; 1648 private static final ConcurrentMap<Class<?>, MethodHandle> PREPENDERS; 1649 private static final ConcurrentMap<Class<?>, MethodHandle> LENGTH_MIXERS; 1650 private static final ConcurrentMap<Class<?>, MethodHandle> CODER_MIXERS; 1651 private static final Class<?> STRING_HELPER; 1652 private static final byte INITIAL_CODER; 1653 1654 static { 1655 try { 1656 STRING_HELPER = Class.forName("java.lang.StringConcatHelper"); 1657 MethodHandle initCoder = lookupStatic(Lookup.IMPL_LOOKUP, STRING_HELPER, "initialCoder", byte.class); 1658 INITIAL_CODER = (byte) initCoder.invoke(); 1659 } catch (Throwable e) { 1660 throw new AssertionError(e); 1661 } 1662 1663 PREPENDERS = new ConcurrentHashMap<>(); 1664 LENGTH_MIXERS = new ConcurrentHashMap<>(); 1665 CODER_MIXERS = new ConcurrentHashMap<>(); 1666 1667 NEW_STRING = lookupStatic(Lookup.IMPL_LOOKUP, STRING_HELPER, "newString", String.class, byte[].class, byte.class); 1668 NEW_ARRAY = lookupStatic(Lookup.IMPL_LOOKUP, MethodHandleInlineCopyStrategy.class, "newArray", byte[].class, int.class, byte.class); 1669 CHECK_INDEX = lookupStatic(Lookup.IMPL_LOOKUP, MethodHandleInlineCopyStrategy.class, "checkIndex", int.class, int.class); 1670 } 1671 } 1672 1673 /** 1674 * Public gateways to public "stringify" methods. These methods have the form String apply(T obj), and normally 1675 * delegate to {@code String.valueOf}, depending on argument's type. 1676 */ 1677 private static final class Stringifiers { 1678 private Stringifiers() { 1679 // no instantiation 1680 } 1681 1682 private static class StringifierMost extends ClassValue<MethodHandle> { 1683 @Override 1684 protected MethodHandle computeValue(Class<?> cl) { 1685 if (cl == String.class) { 1686 return lookupStatic(MethodHandles.publicLookup(), String.class, "valueOf", String.class, Object.class); 1687 } else if (cl == float.class) { 1688 return lookupStatic(MethodHandles.publicLookup(), String.class, "valueOf", String.class, float.class); 1689 } else if (cl == double.class) { 1690 return lookupStatic(MethodHandles.publicLookup(), String.class, "valueOf", String.class, double.class); 1691 } else if (!cl.isPrimitive()) { 1692 MethodHandle mhObject = lookupStatic(MethodHandles.publicLookup(), String.class, "valueOf", String.class, Object.class); 1693 1694 // We need the additional conversion here, because String.valueOf(Object) may return null. 1695 // String conversion rules in Java state we need to produce "null" String in this case. 1696 // It can be easily done with applying valueOf the second time. 1697 return MethodHandles.filterReturnValue(mhObject, 1698 mhObject.asType(MethodType.methodType(String.class, String.class))); 1699 } 1700 1701 return null; 1702 } 1703 } 1704 1705 private static class StringifierAny extends ClassValue<MethodHandle> { 1706 @Override 1707 protected MethodHandle computeValue(Class<?> cl) { 1708 if (cl == byte.class || cl == short.class || cl == int.class) { 1709 return lookupStatic(MethodHandles.publicLookup(), String.class, "valueOf", String.class, int.class); 1710 } else if (cl == boolean.class) { 1711 return lookupStatic(MethodHandles.publicLookup(), String.class, "valueOf", String.class, boolean.class); 1712 } else if (cl == char.class) { 1713 return lookupStatic(MethodHandles.publicLookup(), String.class, "valueOf", String.class, char.class); 1714 } else if (cl == long.class) { 1715 return lookupStatic(MethodHandles.publicLookup(), String.class, "valueOf", String.class, long.class); 1716 } else { 1717 MethodHandle mh = STRINGIFIERS_MOST.get(cl); 1718 if (mh != null) { 1719 return mh; 1720 } else { 1721 throw new IllegalStateException("Unknown class: " + cl); 1722 } 1723 } 1724 } 1725 } 1726 1727 private static final ClassValue<MethodHandle> STRINGIFIERS_MOST = new StringifierMost(); 1728 private static final ClassValue<MethodHandle> STRINGIFIERS_ANY = new StringifierAny(); 1729 1730 /** 1731 * Returns a stringifier for references and floats/doubles only. 1732 * Always returns null for other primitives. 1733 * 1734 * @param t class to stringify 1735 * @return stringifier; null, if not available 1736 */ 1737 static MethodHandle forMost(Class<?> t) { 1738 return STRINGIFIERS_MOST.get(t); 1739 } 1740 1741 /** 1742 * Returns a stringifier for any type. Never returns null. 1743 * 1744 * @param t class to stringify 1745 * @return stringifier 1746 */ 1747 static MethodHandle forAny(Class<?> t) { 1748 return STRINGIFIERS_ANY.get(t); 1749 } 1750 } 1751 1752 /* ------------------------------- Common utilities ------------------------------------ */ 1753 1754 private static MethodHandle lookupStatic(Lookup lookup, Class<?> refc, String name, Class<?> rtype, Class<?>... ptypes) { 1755 try { 1756 return lookup.findStatic(refc, name, MethodType.methodType(rtype, ptypes)); 1757 } catch (NoSuchMethodException | IllegalAccessException e) { 1758 throw new AssertionError(e); 1759 } 1760 } 1761 1762 private static MethodHandle lookupVirtual(Lookup lookup, Class<?> refc, String name, Class<?> rtype, Class<?>... ptypes) { 1763 try { 1764 return lookup.findVirtual(refc, name, MethodType.methodType(rtype, ptypes)); 1765 } catch (NoSuchMethodException | IllegalAccessException e) { 1766 throw new AssertionError(e); 1767 } 1768 } 1769 1770 private static MethodHandle lookupConstructor(Lookup lookup, Class<?> refc, Class<?> ptypes) { 1771 try { 1772 return lookup.findConstructor(refc, MethodType.methodType(void.class, ptypes)); 1773 } catch (NoSuchMethodException | IllegalAccessException e) { 1774 throw new AssertionError(e); 1775 } 1776 } 1777 1778 private static int estimateSize(Class<?> cl) { 1779 if (cl == Integer.TYPE) { 1780 return 11; // "-2147483648" 1781 } else if (cl == Boolean.TYPE) { 1782 return 5; // "false" 1783 } else if (cl == Byte.TYPE) { 1784 return 4; // "-128" 1785 } else if (cl == Character.TYPE) { 1786 return 1; // duh 1787 } else if (cl == Short.TYPE) { 1788 return 6; // "-32768" 1789 } else if (cl == Double.TYPE) { 1790 return 26; // apparently, no larger than this, see FloatingDecimal.BinaryToASCIIBuffer.buffer 1791 } else if (cl == Float.TYPE) { 1792 return 26; // apparently, no larger than this, see FloatingDecimal.BinaryToASCIIBuffer.buffer 1793 } else if (cl == Long.TYPE) { 1794 return 20; // "-9223372036854775808" 1795 } else { 1796 throw new IllegalArgumentException("Cannot estimate the size for " + cl); 1797 } 1798 } 1799 1800 private static Class<?> adaptToStringBuilder(Class<?> c) { 1801 if (c.isPrimitive()) { 1802 if (c == Byte.TYPE || c == Short.TYPE) { 1803 return int.class; 1804 } 1805 } else { 1806 if (c != String.class) { 1807 return Object.class; 1808 } 1809 } 1810 return c; 1811 } 1812 1813 private StringConcatFactory() { 1814 // no instantiation 1815 } 1816 1817 }