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