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