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