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