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