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