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