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