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