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