1 /*
2 * Copyright (c) 2018, 2025, 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.runtime;
27
28 import java.lang.invoke.MethodHandle;
29 import java.lang.invoke.MethodHandles;
30 import java.lang.invoke.MethodType;
31 import java.lang.invoke.VarHandle;
32 import java.util.ArrayDeque;
33 import java.util.ArrayList;
34 import java.util.Comparator;
35 import java.util.Deque;
36 import java.util.HashMap;
37 import java.util.HashSet;
38 import java.util.Iterator;
39 import java.util.LinkedHashMap;
40 import java.util.LinkedList;
41 import java.util.List;
42 import java.util.Map;
43 import java.util.Objects;
44 import java.util.Set;
45 import java.util.concurrent.ConcurrentHashMap;
46 import java.util.function.Function;
47 import java.util.function.Predicate;
48 import java.util.stream.Stream;
49
50 import jdk.internal.access.JavaLangInvokeAccess;
51 import jdk.internal.access.SharedSecrets;
52 import jdk.internal.value.LayoutIteration;
53 import sun.invoke.util.Wrapper;
54
55 import static java.lang.invoke.MethodHandles.constant;
56 import static java.lang.invoke.MethodHandles.dropArguments;
57 import static java.lang.invoke.MethodHandles.filterArguments;
58 import static java.lang.invoke.MethodHandles.foldArguments;
59 import static java.lang.invoke.MethodHandles.guardWithTest;
60 import static java.lang.invoke.MethodHandles.permuteArguments;
61 import static java.lang.invoke.MethodType.methodType;
62 import static java.lang.runtime.ObjectMethods.primitiveEquals;
63 import static java.util.stream.Collectors.joining;
64 import static java.util.stream.Collectors.toList;
65 import static java.util.stream.Collectors.toMap;
66
67 /**
68 * Implementation for Object::equals and Object::hashCode for value objects.
69 *
70 * ValueObjectMethods::isSubstitutable and valueObjectHashCode are
71 * private entry points called by VM.
72 */
73 final class ValueObjectMethods {
74 private ValueObjectMethods() {}
75 private static final boolean VERBOSE =
76 System.getProperty("value.bsm.debug") != null;
77 private static final int MAX_NODE_VISITS =
78 Integer.getInteger("jdk.value.recursion.threshold", Integer.MAX_VALUE);
79 private static final JavaLangInvokeAccess JLIA = SharedSecrets.getJavaLangInvokeAccess();
80
81 static class MethodHandleBuilder {
82 private static final HashMap<Class<?>, MethodHandle> primitiveSubstitutable = new HashMap<>();
83
84 static {
85 primitiveSubstitutable.putAll(primitiveEquals); // adopt all the primitive eq methods
86 primitiveSubstitutable.put(float.class,
87 findStatic("eqValue", methodType(boolean.class, float.class, float.class)));
88 primitiveSubstitutable.put(double.class,
89 findStatic("eqValue", methodType(boolean.class, double.class, double.class)));
90 }
91
92 static Stream<MethodHandle> getterStream(Class<?> type, Comparator<MethodHandle> comparator) {
93 // filter static fields
94 List<MethodHandle> mhs = LayoutIteration.ELEMENTS.get(type);
95 if (comparator != null) {
96 mhs = new ArrayList<>(mhs);
97 mhs.sort(comparator);
98 }
99 return mhs.stream();
100 }
101
102 static MethodHandle hashCodeForType(Class<?> type) {
103 if (type.isPrimitive()) {
104 int index = Wrapper.forPrimitiveType(type).ordinal();
105 return HASHCODE[index];
106 } else {
107 return HASHCODE[Wrapper.OBJECT.ordinal()].asType(methodType(int.class, type));
108 }
109 }
110
111 static MethodHandle builtinPrimitiveSubstitutable(Class<?> type) {
112 return primitiveSubstitutable.get(type);
113 }
114
115 /*
116 * Produces a MethodHandle that returns boolean if two instances
117 * of the given reference type are substitutable.
118 *
119 * Two values of reference type are substitutable i== iff
120 * 1. if o1 and o2 are both reference objects then o1 r== o2; or
121 * 2. if o1 and o2 are both values then o1 v== o2
122 *
123 * At invocation time, it needs a dynamic check on the objects and
124 * do the substitutability test if they are of a value class.
125 */
126 static MethodHandle referenceTypeEquals(Class<?> type) {
127 return OBJECT_EQUALS.asType(methodType(boolean.class, type, type));
128 }
129
130 static Class<?> fieldType(MethodHandle getter) {
131 Class<?> ftype = getter.type().returnType();
132 return ftype;
133 }
134
135 private static List<Class<?>> valueTypeFields(Class<?> type) {
136 return LayoutIteration.ELEMENTS.get(type).stream()
137 .<Class<?>>map(mh -> mh.type().returnType())
138 .filter(cl -> !cl.isPrimitive() && cl.isValue())
139 .distinct()
140 .toList();
141 }
142
143 /*
144 * Produces a MethodHandle that returns boolean if two value objects
145 * are substitutable. The method type is (V, V)boolean.
146 */
147 static MethodHandle valueTypeEquals(Class<?> type) {
148 var builder = METHOD_HANDLE_BUILDERS.get(type);
149 if (builder == null) {
150 builder = newBuilder(type);
151 }
152 return builder.equalsTarget();
153 }
154
155 /*
156 * Produces a MethodHandle that computes the hash code of a value object.
157 * The method type of the return MethodHandle is (V)int.
158 */
159 static MethodHandle valueTypeHashCode(Class<?> type) {
160 var builder = METHOD_HANDLE_BUILDERS.get(type);
161 if (builder == null) {
162 builder = newBuilder(type);
163 }
164 return builder.hashCodeTarget();
165 }
166
167 /*
168 * Produces a MethodHandle that returns boolean if the given non-recursively typed
169 * fields of the two value objects are substitutable. The method type is (V, V)boolean
170 */
171 static MethodHandle valueTypeEquals(Class<?> type, List<MethodHandle> getters) {
172 assert LayoutIteration.isFinalValueClass(type);
173
174 MethodType mt = methodType(boolean.class, type, type);
175 MethodHandle instanceTrue = dropArguments(TRUE, 0, type, Object.class).asType(mt);
176 MethodHandle instanceFalse = dropArguments(FALSE, 0, type, Object.class).asType(mt);
177 MethodHandle accumulator = dropArguments(TRUE, 0, type, type);
178 for (MethodHandle getter : getters) {
179 Class<?> ftype = fieldType(getter);
180 var eq = substitutableInvoker(ftype).asType(methodType(boolean.class, ftype, ftype));
181 var thisFieldEqual = filterArguments(eq, 0, getter, getter);
182 accumulator = guardWithTest(thisFieldEqual, accumulator, instanceFalse);
183 }
184
185 // if both arguments are null, return true;
186 // otherwise return accumulator;
187 return guardWithTest(IS_NULL.asType(mt),
188 instanceTrue,
189 guardWithTest(IS_SAME_VALUE_CLASS.asType(mt),
190 accumulator,
191 instanceFalse));
192 }
193
194 /*
195 * Produces a MethodHandle that returns the hash code computed from
196 * the given non-recursively-typed fields of a value object.
197 * The method type is (V)int.
198 */
199 static MethodHandle valueTypeHashCode(Class<?> type, List<MethodHandle> getters) {
200 assert LayoutIteration.isFinalValueClass(type);
201
202 MethodHandle target = dropArguments(constant(int.class, SALT), 0, type);
203 MethodHandle classHasher = dropArguments(hashCodeForType(Class.class).bindTo(type), 0, type);
204 MethodHandle hashCombiner = dropArguments(HASH_COMBINER, 2, type);
205 MethodHandle accumulator = foldArguments(foldArguments(hashCombiner, 1, classHasher), 0, target);
206 for (MethodHandle getter : getters) {
207 Class<?> ft = fieldType(getter);
208 // For primitive types or reference types, this calls Objects::hashCode.
209 // For value objects and the hashCode method is not overridden,
210 // VM will call valueObjectHashCode to compute the hash code.
211 var hasher = hashCodeForType(ft);
212 var hashThisField = filterArguments(hasher, 0, getter); // (R)I
213 var combineHashes = foldArguments(hashCombiner, 1, hashThisField);
214 accumulator = foldArguments(combineHashes, 0, accumulator);
215 }
216 return accumulator;
217 }
218
219 // ------ utility methods ------
220 private static boolean eq(Object a, Object b) {
221 if (a == null && b == null) return true;
222 if (a == null || b == null) return false;
223 if (a.getClass() != b.getClass()) return false;
224 return a.getClass().isValue() ? valueEquals(a, b) : (a == b);
225 }
226
227 /*
228 * Returns true if two value objects are substitutable.
229 */
230 private static boolean valueEquals(Object a, Object b) {
231 assert a != null && b != null && isSameValueClass(a, b);
232 try {
233 Class<?> type = a.getClass();
234 return (boolean) substitutableInvoker(type).invoke(type.cast(a), type.cast(b));
235 } catch (Error|RuntimeException e) {
236 throw e;
237 } catch (Throwable e) {
238 throw new InternalError(e);
239 }
240 }
241
242 private static boolean isNull(Object a, Object b) {
243 // avoid acmp that will call isSubstitutable
244 if (a != null) return false;
245 if (b != null) return false;
246 return true;
247 }
248
249 /*
250 * Returns true if the given objects are of the same value class.
251 *
252 * Two objects are of the same value class iff:
253 * 1. a != null and b != null
254 * 2. the declaring class of a and b is the same value class
255 */
256 private static boolean isSameValueClass(Object a, Object b) {
257 if (a == null || b == null) return false;
258
259 return a.getClass().isValue() && a.getClass() == b.getClass();
260 }
261
262 private static int hashCombiner(int accumulator, int value) {
263 return accumulator * 31 + value;
264 }
265
266 private static int[] newCounter(int[] counter) {
267 return new int[] { counter[0] };
268 }
269
270 private static boolean recurValueEq(MethodHandle target, Object o1, Object o2, int[] counter) {
271 assert counter[0] > 0;
272
273 if (o1 == null && o2 == null) return true;
274 if (o1 == null || o2 == null) return false;
275 if (o1.getClass() != o2.getClass()) return false;
276
277 if (--counter[0] == 0) {
278 throw new StackOverflowError("fail to evaluate == for value class " + o1.getClass().getName());
279 }
280
281 try {
282 return (boolean) target.invoke(o1, o2, counter);
283 } catch (Error|RuntimeException e) {
284 throw e;
285 } catch (Throwable e) {
286 throw new InternalError(e);
287 }
288 }
289
290 private static int recurValueHashCode(MethodHandle target, Object o, int[] counter) {
291 assert counter[0] > 0;
292
293 if (o == null) return 0;
294
295 if (--counter[0] == 0) {
296 throw new StackOverflowError("fail to evaluate hashCode for value class " + o.getClass().getName());
297 }
298
299 try {
300 return (int) target.invoke(o, counter);
301 } catch (Error|RuntimeException e) {
302 throw e;
303 } catch (Throwable e) {
304 throw new InternalError(e);
305 }
306 }
307
308 private static final MethodHandle FALSE = constant(boolean.class, false);
309 private static final MethodHandle TRUE = constant(boolean.class, true);
310 // Substitutability test for float
311 private static boolean eqValue(float a, float b) {
312 return Float.floatToRawIntBits(a) == Float.floatToRawIntBits(b);
313 }
314 // Substitutability test for double
315 private static boolean eqValue(double a, double b) {
316 return Double.doubleToRawLongBits(a) == Double.doubleToRawLongBits(b);
317 }
318 private static final MethodHandle OBJECT_EQUALS =
319 findStatic("eq", methodType(boolean.class, Object.class, Object.class));
320 private static final MethodHandle IS_SAME_VALUE_CLASS =
321 findStatic("isSameValueClass", methodType(boolean.class, Object.class, Object.class));
322 private static final MethodHandle IS_NULL =
323 findStatic("isNull", methodType(boolean.class, Object.class, Object.class));
324 private static final MethodHandle HASH_COMBINER =
325 findStatic("hashCombiner", methodType(int.class, int.class, int.class));
326 private static final MethodHandle[] HASHCODE = initHashCode();
327 private static final MethodHandle RECUR_VALUE_EQ =
328 findStatic("recurValueEq", methodType(boolean.class, MethodHandle.class, Object.class, Object.class, int[].class));
329 private static final MethodHandle RECUR_VALUE_HASHCODE =
330 findStatic("recurValueHashCode", methodType(int.class, MethodHandle.class, Object.class, int[].class));
331 private static final MethodHandle NEW_COUNTER =
332 findStatic("newCounter", methodType(int[].class, int[].class));
333
334 private static MethodHandle[] initHashCode() {
335 MethodHandle[] mhs = new MethodHandle[Wrapper.COUNT];
336 for (Wrapper wrapper : Wrapper.values()) {
337 if (wrapper == Wrapper.VOID) continue;
338 Class<?> cls = wrapper == Wrapper.OBJECT ? Objects.class : wrapper.wrapperType();
339 mhs[wrapper.ordinal()] = findStatic(cls, "hashCode",
340 methodType(int.class, wrapper.primitiveType()));
341 }
342 return mhs;
343 }
344
345 private static MethodHandle findStatic(String name, MethodType methodType) {
346 return findStatic(MethodHandleBuilder.class, name, methodType);
347 }
348 private static MethodHandle findStatic(Class<?> cls, String name, MethodType methodType) {
349 try {
350 return JLIA.findStatic(cls, name, methodType);
351 } catch (IllegalAccessException e) {
352 throw newLinkageError(e);
353 }
354 }
355
356 /**
357 * A "salt" value used for this internal hashcode implementation that
358 * needs to vary sufficiently from one run to the next so that
359 * the default hashcode for value classes will vary between JVM runs.
360 */
361 static final int SALT;
362 static {
363 long nt = System.nanoTime();
364 int value = (int)((nt >>> 32) ^ nt);
365 SALT = Integer.getInteger("value.bsm.salt", value);
366 }
367
368 static MethodHandleBuilder newBuilder(Class<?> type) {
369 assert LayoutIteration.isFinalValueClass(type);
370
371 Deque<Class<?>> deque = new ArrayDeque<>();
372 deque.add(type);
373 Map<Class<?>, MethodHandleBuilder> visited = new HashMap<>();
374 var builder = new MethodHandleBuilder(type, deque, visited);
375 visited.put(type, builder);
376 return builder;
377 }
378
379 enum Status {
380 NOT_START,
381 IN_PROGRESS,
382 TRAVERSAL_DONE,
383 READY
384 }
385
386 final Class<?> type;
387 final List<Class<?>> fieldValueTypes;
388 // a map of the type of a field T to a cycle of T -> ... -> V
389 // where V is this builder's value type
390 final Map<Class<?>, List<Class<?>>> cyclicMembers = new HashMap<>();
391 // recursively-typed fields declared in this builder's value type
392 final Set<Class<?>> recurFieldTypes = new HashSet<>();
393 final Deque<Class<?>> path;
394 final Map<Class<?>, MethodHandleBuilder> visited;;
395 volatile Status status = Status.NOT_START;
396 volatile MethodHandle equalsTarget;
397 volatile MethodHandle hashCodeTarget;
398
399 static final VarHandle STATUS_HANDLE;
400 static {
401 VarHandle vh = null;
402 try {
403 vh = MethodHandles.lookup().findVarHandle(MethodHandleBuilder.class, "status", Status.class);
404 } catch (ReflectiveOperationException e) {
405 throw new InternalError(e);
406 }
407 STATUS_HANDLE = vh;
408 }
409
410 /**
411 * Constructs a new MethodHandleBuilder for the given value type.
412 *
413 * @param type a value class
414 * @param path the graph traversal
415 * @param visited a map of a visited type to a builder
416 */
417 private MethodHandleBuilder(Class<?> type, Deque<Class<?>> path, Map<Class<?>, MethodHandleBuilder> visited) {
418 assert LayoutIteration.isFinalValueClass(type) : type;
419 this.type = type;
420 this.fieldValueTypes = valueTypeFields(type);
421 this.path = path;
422 this.visited = visited;
423 if (VERBOSE) {
424 System.out.println("New builder for " + type.getName() + " " + path);
425 }
426 }
427
428 /*
429 * Returns a method handle that implements equals method for this builder's value class.
430 */
431 MethodHandle equalsTarget() {
432 if (status != Status.READY)
433 throw new IllegalStateException(type.getName() + " not ready");
434
435 var mh = equalsTarget;
436 if (mh != null) return mh;
437
438 generateMethodHandle();
439 return equalsTarget;
440 }
441
442 /*
443 * Returns a method handle that implements hashCode method for this builder's value class.
444 */
445 MethodHandle hashCodeTarget() {
446 if (status != Status.READY)
447 throw new IllegalStateException(type.getName() + " not ready");
448
449 var mh = hashCodeTarget;
450 if (mh != null) return mh;
451
452 generateMethodHandle();
453 return hashCodeTarget;
454 }
455
456 /*
457 * Build the graph for this builder's value type. Detect all cycles.
458 * This builder after this method returns is in DONE_TRAVERSAL or READY status.
459 *
460 * A builder for type V will change to READY status when the entire graph for V
461 * is traversed (i.e. all builders in this graph are in DONE_TRAVERSAL or READY
462 * status).
463 */
464 MethodHandleBuilder build() {
465 if (status == Status.READY) return this;
466
467 if (!STATUS_HANDLE.compareAndSet(this, Status.NOT_START, Status.IN_PROGRESS)) {
468 throw new RuntimeException(type.getName() + " in progress");
469 }
470
471 // traverse the graph and find all cycles
472 detectCycles();
473
474 if (!STATUS_HANDLE.compareAndSet(this, Status.IN_PROGRESS, Status.TRAVERSAL_DONE)) {
475 throw new RuntimeException(type.getName() + " failed to set done traversal. " + status);
476 }
477
478 // Check if this node V is ready for building equals/hashCode method handles.
479 // V is ready if the types of all its fields are done traversal.
480 if (ready()) {
481 // Do a pass on all the cycles containing V. V is ready.
482 // If a node N in the cycle has completed the traversal (i.e. cycles are detected),
483 // call ready() on N to update its status if ready.
484 for (List<Class<?>> cycle : cyclicMembers.values()) {
485 cycle.stream().filter(c -> c != type)
486 .map(visited::get)
487 .filter(b -> b.status == Status.TRAVERSAL_DONE)
488 .forEach(MethodHandleBuilder::ready);
489 }
490 }
491 return this;
492 }
493
494 /*
495 * Traverses the graph and finds all cycles.
496 */
497 private void detectCycles() {
498 LinkedList<Class<?>> deque = new LinkedList<>();
499 deque.addAll(fieldValueTypes);
500 while (!deque.isEmpty()) {
501 Class<?> n = deque.pop();
502 // detect cyclic membership
503 if (path.contains(n)) {
504 List<Class<?>> cycle = new ArrayList<>();
505 Iterator<Class<?>> iter = path.iterator();
506 while (iter.hasNext()) {
507 Class<?> c = iter.next();
508 cycle.add(c);
509 if (c == n) break;
510 }
511 cyclicMembers.put(n, cycle);
512 path.pop();
513 continue;
514 }
515
516 try {
517 path.push(n);
518 if (!visited.containsKey(n)) {
519 // Duplicate the path and pass it to an unvisited node
520 Deque<Class<?>> newPath = new ArrayDeque<>();
521 newPath.addAll(path);
522 visited.computeIfAbsent(n, c -> new MethodHandleBuilder(n, newPath, visited));
523 }
524
525 var builder = visited.get(n);
526 switch (builder.status) {
527 case NOT_START -> builder.build();
528 case TRAVERSAL_DONE -> builder.ready();
529 }
530 } finally {
531 path.pop();
532 }
533 }
534
535 // propagate the cycles to the recursively-typed value classes
536 // For each cycle A -> B -> C -> A, the cycle is recorded in all
537 // the nodes (A, B, and C) in this cycle.
538 for (Map.Entry<Class<?>, List<Class<?>>> e : cyclicMembers.entrySet()) {
539 Class<?> c = e.getKey();
540 List<Class<?>> cycle = e.getValue();
541 var builder = visited.get(c);
542 for (Class<?> ft : cycle) {
543 if (ft != c && builder.fieldValueTypes.contains(ft)) {
544 var v = builder.cyclicMembers.put(ft, cycle);
545 assert v == null || cycle.equals(v) : "mismatched cycle: " + v + " vs " + cycle;
546 }
547 }
548 }
549 }
550
551 /*
552 * Tests if this builder is ready for generating equals and hashCode
553 * method handles for the value class.
554 *
555 * This builder is ready if and only if the type graph of all its fields
556 * are traversed and all cycles are detected.
557 *
558 * Before setting to READY, the recursively-typed fields are recorded
559 * that includes all types in the cycles and the field types which
560 * references recursive types
561 */
562 private boolean ready() {
563 if (status == Status.READY) return true;
564
565 boolean inProgress = fieldValueTypes.stream().map(visited::get)
566 .anyMatch(b -> b.status == Status.IN_PROGRESS);
567 if (inProgress)
568 return false;
569
570 // collect the recursively-typed value classes required by this method handle
571 // all types in the cycles and the field types which references recursive types
572 recurFieldTypes.addAll(cyclicMembers.keySet());
573 for (Class<?> c : fieldValueTypes) {
574 if (c == type) continue;
575
576 // if this field type references a recursive type
577 var b = visited.get(c);
578 if (b.cyclicMembers.size() > 0 || b.recurFieldTypes.size() > 0)
579 recurFieldTypes.add(c);
580 };
581
582 // Finished recording recursively-typed fields. Set to READY.
583 if (!STATUS_HANDLE.compareAndSet(this, Status.TRAVERSAL_DONE, Status.READY)) {
584 throw new RuntimeException(type.getName() + " failed to set READY. " + status);
585 }
586 return true;
587 }
588
589 void generateMethodHandle() {
590 if (status != Status.READY)
591 throw new IllegalStateException(type.getName() + " not ready");
592
593 // non-recursive value type
594 if (recurFieldTypes.isEmpty()) {
595 if (cyclicMembers.size() > 0)
596 throw new RuntimeException(type.getName() + " should not reach here");
597
598 this.equalsTarget = valueTypeEquals(type, getterStream(type, TYPE_SORTER).toList());
599 this.hashCodeTarget = valueTypeHashCode(type, getterStream(type, null).toList());
600 return;
601 }
602
603 if (VERBOSE) {
604 System.out.println(debugString());
605 }
606
607 // generate the base function for each recursive type
608 // boolean base1(MethodHandle entry, MethodHandle base1, MethodHandle base2,....., Object o1, Object o2, int[] counter)
609 // :
610 // boolean baseN(MethodHandle entry, MethodHandle base1, MethodHandle base2,....., Object o1, Object o2, int[] counter)
611 //
612 List<Class<?>> recursiveTypes = aggregateRecursiveTypes();
613 Map<Class<?>, MethodHandle> bases = new LinkedHashMap<>();
614 Map<Class<?>, MethodHandle> hashCodeBases = new LinkedHashMap<>();
615 for (Class<?> c : recursiveTypes) {
616 bases.put(c, visited.get(c).generateSubstBase(recursiveTypes));
617 hashCodeBases.put(c, visited.get(c).generateHashCodeBase(recursiveTypes));
618 }
619
620 var handles = bases.values().stream().toArray(MethodHandle[]::new);
621 var hashCodeHandles = hashCodeBases.values().stream().toArray(MethodHandle[]::new);
622
623 // The entry point for equals for this value type T looks like this:
624 //
625 // boolean entry(MethodHandle entry, MethodHandle base1, MethodHandle base2,....., Object o1, Object o2, int[] counter) {
626 // int[] newCounter = new int[] { counter[0] } ;
627 // return baseT(o1, o2, newCounter);
628 // }
629 this.equalsTarget = newValueEquals(recursiveTypes, handles);
630 this.hashCodeTarget = newValueHashCode(recursiveTypes, hashCodeHandles);
631
632 // Precompute the method handles for all recursive data types in the cycles
633 // They share the generated base method handles.
634 var cycles = cyclicMembers.values().stream().flatMap(List::stream)
635 .filter(c -> c != type)
636 .collect(toMap(Function.identity(), visited::get));
637 for (Class<?> n : cycles.keySet()) {
638 var builder = cycles.get(n);
639 if (builder.status != Status.READY) {
640 throw new InternalError(type.getName() + " is not ready: " + status);
641 }
642
643 var mh = builder.equalsTarget;
644 var mh2 = builder.hashCodeTarget;
645 if (mh != null && mh2 != null) {
646 continue;
647 }
648
649 // precompute the method handles for each recursive type in the cycle
650 if (mh == null) {
651 builder.equalsTarget = builder.newValueEquals(recursiveTypes, handles);
652 }
653 if (mh2 == null) {
654 builder.hashCodeTarget = builder.newValueHashCode(recursiveTypes, hashCodeHandles);
655 }
656 }
657
658 // cache the builders with precomputed method handles in the cache
659 synchronized (CACHED_METHOD_HANDLE_BUILDERS) {
660 for (Class<?> n : cycles.keySet()) {
661 try {
662 // the builder is added to the builder cache and propapate to
663 // the class value
664 CACHED_METHOD_HANDLE_BUILDERS.computeIfAbsent(n, cycles::get);
665 METHOD_HANDLE_BUILDERS.get(n);
666 } finally {
667 // Remove it from the builder cache once it's in class value
668 CACHED_METHOD_HANDLE_BUILDERS.remove(n);
669 }
670 }
671 }
672
673 // equals and hashCode are generated. Clear the path and visited builders.
674 clear();
675 }
676
677 private void clear() {
678 path.clear();
679 visited.clear();
680 }
681
682 /*
683 * Aggregates all recursive data types for this builder's value types.
684 * The result is used in generating a recursive method handle
685 * for this builder's value type.
686 *
687 * A graph of V:
688 * V -> P -> V
689 * -> N -> N (self-recursive)
690 * -> E -> F -> E
691 *
692 * V, P, N, E, F are the mutual recursive types for V. The recursive method handle
693 * for V is created with the base functions for V, P, N, E, F and it can mutually
694 * call the recursive method handle for these types. Specifically, MH_V calls
695 * MH_P which calls MH_V, MH_N which calls itself, and MH_E which calls MH_F.
696 */
697 private List<Class<?>> aggregateRecursiveTypes() {
698 boolean ready = true;
699 for (List<Class<?>> cycle : cyclicMembers.values()) {
700 // ensure all nodes in all cycles that are done traversal and ready for
701 // method handle generation
702 cycle.stream().filter(c -> c != type)
703 .map(visited::get)
704 .filter(b -> b.status == Status.TRAVERSAL_DONE)
705 .forEach(MethodHandleBuilder::ready);
706
707 // check the status
708 ready = ready && cycle.stream().filter(c -> c != type)
709 .map(visited::get)
710 .allMatch(b -> b.status == Status.READY);
711 }
712
713 if (!ready) {
714 throw new IllegalStateException(type.getName() + " " + status);
715 }
716
717 /*
718 * Traverse the graph for V to find all mutual recursive types for V.
719 *
720 * Node T is a mutual recursive type for V if any of the following:
721 * 1. T is a recursively-typed field in V
722 * 2. T is a type involved the cycles from V ... -> T ... -> V
723 * 3. T is a mutual recursive type for N where N is a mutual recursive type for V.
724 */
725 Deque<Class<?>> deque = new ArrayDeque<>();
726 List<Class<?>> recurTypes = new ArrayList<>();
727 recurTypes.add(type);
728 Stream.concat(recurFieldTypes.stream(),
729 cyclicMembers.values().stream().flatMap(List::stream))
730 .filter(Predicate.not(deque::contains)).forEach(deque::add);
731 while (!deque.isEmpty()) {
732 Class<?> c = deque.pop();
733 if (recurTypes.contains(c)) continue;
734
735 recurTypes.add(c);
736
737 var builder = visited.get(c);
738 Stream.concat(builder.recurFieldTypes.stream(),
739 builder.cyclicMembers.values().stream().flatMap(List::stream))
740 .filter(n -> !recurTypes.contains(n) && !deque.contains(n))
741 .forEach(deque::push);
742 }
743 return recurTypes;
744 }
745
746 /*
747 * Create a new method handle that implements equals(T, Object) for value class T
748 * for this builder using the given base method handles. The return method handle
749 * is capable of recursively calling itself for value class T whose entry point:
750 * boolean entry(MethodHandle entry, MethodHandle base1, MethodHandle base2, ..., Object o1, Object o2, int[] counter) {
751 * int[] newCounter = new int[] { counter[0] };
752 * return baseT(o1, o2, newCounter);
753 * }
754 *
755 * The counter is used to keep of node visits and throw StackOverflowError
756 * if the counter gets "unreasonably" large of a cyclic value graph
757 * (regardless of how many real stack frames were consumed.)
758 */
759 MethodHandle newValueEquals(List<Class<?>> recursiveTypes, MethodHandle[] bases) {
760 var entry = equalsEntry(recursiveTypes);
761 var mh = MethodHandles.insertArguments(recursive(entry, bases), 2, new int[] {MAX_NODE_VISITS});
762 return mh.asType(methodType(boolean.class, type, type));
763 }
764
765 /*
766 * Create a new method handle that implements hashCode(T) for value class T
767 * for this builder using the given base method handles. The return method handle
768 * is capable of recursively calling itself for value class T whose entry point:
769 * boolean entry(MethodHandle entry, MethodHandle base1, MethodHandle base2, ..., Object o, int[] counter) {
770 * int[] newCounter = new int[] { counter[0] };
771 * return baseT(o, newCounter);
772 * }
773 *
774 * The counter is used to keep of node visits and throw StackOverflowError
775 * if the counter gets "unreasonably" large of a cyclic value graph
776 * (regardless of how many real stack frames were consumed.)
777 */
778 MethodHandle newValueHashCode(List<Class<?>> recursiveTypes, MethodHandle[] bases) {
779 var entry = hashCodeEntry(recursiveTypes);
780 var mh = MethodHandles.insertArguments(recursive(entry, bases), 1, new int[] {MAX_NODE_VISITS});
781 return mh.asType(methodType(int.class, type));
782 }
783
784 /*
785 * Create a method handle where the first N+1 parameters are MethodHandle and
786 * N is the number of the recursive value types and followed with
787 * Object, Object and int[] parameters. The pseudo code looks like this:
788 *
789 * boolean eq(MethodHandle entry, MethodHandle base1, MethodHandle base2, ..., Object o1, Object o2, int[] counter) {
790 * if (o1 == null && o2 == null) return true;
791 * if (o1 == null || o2 == null) return false;
792 * if (o1.getClass() != o2. getClass()) return false;
793 *
794 * int[] newCounter = new int[] { counter[0]; }
795 * return (boolean) baseT.invoke(o1, o2, newCounter);
796 * }
797 */
798 MethodHandle equalsEntry(List<Class<?>> recursiveTypes) {
799 List<Class<?>> leadingMHParams = new ArrayList<>();
800 // the first MethodHandle parameter is this entry point
801 // followed with MethodHandle parameter for each mutual exclusive value class
802 int mhParamCount = recursiveTypes.size()+1;
803 for (int i=0; i < mhParamCount; i++) {
804 leadingMHParams.add(MethodHandle.class);
805 }
806
807 MethodType mt = methodType(boolean.class, Stream.concat(leadingMHParams.stream(), Stream.of(type, type, int[].class))
808 .collect(toList()));
809 var allParameters = mt.parameterList();
810 MethodHandle instanceTrue = dropArguments(TRUE, 0, allParameters).asType(mt);
811 MethodHandle instanceFalse = dropArguments(FALSE, 0, allParameters).asType(mt);
812 MethodHandle isNull = dropArguments(dropArguments(IS_NULL, 0, leadingMHParams), mhParamCount+2, int[].class).asType(mt);
813 MethodHandle isSameValueType = dropArguments(dropArguments(IS_SAME_VALUE_CLASS, 0, leadingMHParams), mhParamCount+2, int[].class).asType(mt);
814
815 int index = recursiveTypes.indexOf(type);
816 var mtype = methodType(boolean.class, Stream.concat(leadingMHParams.stream(), Stream.of(type, type, int[].class)).collect(toList()));
817 var recurEq = RECUR_VALUE_EQ.asType(methodType(boolean.class, MethodHandle.class, type, type, int[].class));
818 var eq = permuteArguments(recurEq, mtype, index+1, mhParamCount, mhParamCount+1, mhParamCount+2);
819 eq = filterArguments(eq, mhParamCount+2, NEW_COUNTER);
820
821 // if both arguments are null, return true;
822 // otherwise return the method handle corresponding to this type
823 return guardWithTest(isNull,
824 instanceTrue,
825 guardWithTest(isSameValueType, eq, instanceFalse));
826 }
827
828 /*
829 * A base method for substitutability test for a recursive data type,
830 * a value class with cyclic membership.
831 *
832 * The signature of this base method is:
833 * boolean base(MethodHandle entry, MethodHandle base1, MethodHandle base2, ..., V o1, V o2, int[] counter)
834 *
835 * where the first N+1 parameters are MethodHandle and N is the number of
836 * the recursive value types and followed with Object, Object and int[] parameters.
837 *
838 * This method first calls the method handle that tests the substitutability
839 * of all fields that are not recursively-typed, if any, and then test
840 * the substitutability of the fields that are of each recursive value type.
841 * The pseudo code looks like this:
842 *
843 * boolean base(MethodHandle entry, MethodHandle base1, MethodHandle base2, ..., V o1, V o2, int[] counter) {
844 * if (o1 == null && o2 == null) return true;
845 * if (o1 == null || o2 == null) return false;
846 * if (o1.getClass() != o2. getClass()) return false;
847 *
848 * for each non-recursively-typed field {
849 * if (field value of o1 != field value of o2) return false;
850 * }
851 *
852 * for each recursively-typed field of type T {
853 * if (--counter[0] == 0) throw new StackOverflowError();
854 * // baseT is the method handle corresponding to the recursive type T
855 * boolean rc = (boolean) baseT.invoke(o1, o2, counter);
856 * if (!rc) return false;
857 * }
858 * return true;
859 * }
860 */
861 MethodHandle generateSubstBase(List<Class<?>> recursiveTypes) {
862 List<MethodHandle> nonRecurGetters = new ArrayList<>();
863 Map<Class<?>, List<MethodHandle>> recurGetters = new LinkedHashMap<>();
864 getterStream(type, TYPE_SORTER).forEach(mh -> {
865 Class<?> ft = fieldType(mh);
866 if (!this.recurFieldTypes.contains(ft)) {
867 nonRecurGetters.add(mh);
868 } else {
869 assert recursiveTypes.contains(ft);
870 recurGetters.computeIfAbsent(ft, t -> new ArrayList<>()).add(mh);
871 }
872 });
873
874 // The first parameter is the method handle of the entry point
875 // followed with one MethodHandle for each recursive value type
876 List<Class<?>> leadingMHParams = new ArrayList<>();
877 int mhParamCount = recursiveTypes.size()+1;
878 for (int i=0; i < mhParamCount; i++) {
879 leadingMHParams.add(MethodHandle.class);
880 }
881
882 MethodType mt = methodType(boolean.class,
883 Stream.concat(leadingMHParams.stream(), Stream.of(type, type, int[].class)).collect(toList()));
884 var allParameters = mt.parameterList();
885
886 var instanceTrue = dropArguments(TRUE, 0, allParameters).asType(mt);
887 var instanceFalse = dropArguments(FALSE, 0, allParameters).asType(mt);
888 var accumulator = dropArguments(TRUE, 0, allParameters).asType(mt);
889 var isNull = dropArguments(dropArguments(IS_NULL, 0, leadingMHParams), mhParamCount+2, int[].class).asType(mt);
890 var isSameValueType = dropArguments(dropArguments(IS_SAME_VALUE_CLASS, 0, leadingMHParams), mhParamCount+2, int[].class).asType(mt);
891
892 // This value class contains cyclic membership.
893 // Create a method handle that first calls the method handle that tests
894 // the substitutability of all fields that are not recursively-typed, if any,
895 // and then test the substitutability of the fields that are of each recursive
896 // value type.
897 //
898 // Method handle for the substitutability test for recursive types is built
899 // before that for non-recursive types.
900 for (Map.Entry<Class<?>, List<MethodHandle>> e : recurGetters.entrySet()) {
901 Class<?> ft = e.getKey();
902 int index = recursiveTypes.indexOf(ft);
903 var mtype = methodType(boolean.class,
904 Stream.concat(leadingMHParams.stream(), Stream.of(ft, ft, int[].class)).collect(toList()));
905 var recurEq = RECUR_VALUE_EQ.asType(methodType(boolean.class, MethodHandle.class, ft, ft, int[].class));
906 var eq = permuteArguments(recurEq, mtype, index+1, mhParamCount, mhParamCount+1, mhParamCount+2);
907 for (MethodHandle getter : e.getValue()) {
908 assert ft == fieldType(getter);
909 var thisFieldEqual = filterArguments(eq, mhParamCount, getter, getter);
910 accumulator = guardWithTest(thisFieldEqual, accumulator, instanceFalse);
911 }
912 }
913
914 if (nonRecurGetters.isEmpty()) {
915 // if both arguments are null, return true;
916 // otherwise return accumulator;
917 return guardWithTest(isNull,
918 instanceTrue,
919 guardWithTest(isSameValueType, accumulator, instanceFalse));
920 } else {
921 // method handle for substitutability test of the non-recursive-typed fields
922 var mh = valueTypeEquals(type, nonRecurGetters);
923 mh = dropArguments(dropArguments(mh, 0, leadingMHParams), mhParamCount+2, int[].class).asType(mt);
924 return guardWithTest(mh, accumulator, instanceFalse);
925 }
926 }
927
928 /*
929 * Create a method handle where the first N+1 parameters are MethodHandle and
930 * N is the number of the recursive value types and followed with
931 * Object and int[] parameters. The pseudo code looks like this:
932 *
933 * int hashCode(MethodHandle entry, MethodHandle base1, MethodHandle base2, ..., Object o, int[] counter) {
934 * int[] newCounter = new int[] { counter[0]; }
935 * return (int) baseT.invoke(o, newCounter);
936 * }
937 */
938 MethodHandle hashCodeEntry(List<Class<?>> recursiveTypes) {
939 List<Class<?>> leadingMHParams = new ArrayList<>();
940 int mhParamCount = recursiveTypes.size()+1;
941 // the first MethodHandle parameter is this entry point
942 // followed with MethodHandle parameter for each mutual exclusive value class
943 for (int i=0; i < mhParamCount; i++) {
944 leadingMHParams.add(MethodHandle.class);
945 }
946
947 int index = recursiveTypes.indexOf(type);
948 var mtype = methodType(int.class, Stream.concat(leadingMHParams.stream(), Stream.of(type, int[].class)).collect(toList()));
949 var recurHashCode = RECUR_VALUE_HASHCODE.asType(methodType(int.class, MethodHandle.class, type, int[].class));
950 var mh = permuteArguments(recurHashCode, mtype, index+1, mhParamCount, mhParamCount+1);
951 return filterArguments(mh, mhParamCount+1, NEW_COUNTER);
952 }
953
954 /**
955 * A base method for computing the hashcode for a recursive data type,
956 * a value class with cyclic membership.
957 *
958 * The signature of this base method is:
959 * int base(MethodHandle entry, MethodHandle base1, MethodHandle base2, ..., V o, int[] counter)
960 *
961 * where the first N+1 parameters are MethodHandle and N is the number of
962 * the recursive value types and followed with Object and int[] parameters.
963 *
964 * This method will first invoke a method handle to compute the hash code
965 * of the not recursively-typed fields. Then compute the hash code of the
966 * remaining recursively-typed fields.
967 */
968 MethodHandle generateHashCodeBase(List<Class<?>> recursiveTypes) {
969 assert status == Status.READY;
970
971 List<MethodHandle> nonRecurGetters = new ArrayList<>();
972 Map<Class<?>, List<MethodHandle>> recurGetters = new LinkedHashMap<>();
973 getterStream(type, null).forEach(mh -> {
974 Class<?> ft = fieldType(mh);
975 if (!this.recurFieldTypes.contains(ft)) {
976 nonRecurGetters.add(mh);
977 } else {
978 assert recursiveTypes.contains(ft);
979 recurGetters.computeIfAbsent(ft, t -> new ArrayList<>()).add(mh);
980 }
981 });
982
983 int mhParamCount = recursiveTypes.size()+1;
984 List<Class<?>> leadingMHParams = new ArrayList<>();
985 for (int i=0; i < mhParamCount; i++) { // include entry point
986 leadingMHParams.add(MethodHandle.class);
987 }
988
989 MethodType mt = methodType(int.class,
990 Stream.concat(leadingMHParams.stream(), Stream.of(type, int[].class)).collect(toList()));
991 var allParameters = mt.parameterList();
992 var hashCombiner = dropArguments(HASH_COMBINER, 2, allParameters);
993 var salt = dropArguments(constant(int.class, SALT), 0, allParameters);
994 var classHasher = dropArguments(hashCodeForType(Class.class).bindTo(type), 0, allParameters);
995 var accumulator = foldArguments(foldArguments(hashCombiner, 1, classHasher), 0, salt);
996 for (MethodHandle getter : nonRecurGetters) {
997 Class<?> ft = fieldType(getter);
998 var hasher = dropArguments(hashCodeForType(ft), 0, leadingMHParams);
999 var hashThisField = filterArguments(hasher, mhParamCount, getter);
1000 var combineHashes = foldArguments(hashCombiner, 1, hashThisField);
1001 accumulator = foldArguments(combineHashes, 0, accumulator);
1002 }
1003
1004 for (Map.Entry<Class<?>, List<MethodHandle>> e : recurGetters.entrySet()) {
1005 Class<?> ft = e.getKey();
1006 int index = recursiveTypes.indexOf(ft);
1007 var mtype = methodType(int.class, Stream.concat(leadingMHParams.stream(), Stream.of(ft, int[].class)).collect(toList()));
1008 var recurHashCode = RECUR_VALUE_HASHCODE.asType(methodType(int.class, MethodHandle.class, ft, int[].class));
1009 var hasher = permuteArguments(recurHashCode, mtype, index + 1, mhParamCount, mhParamCount + 1);
1010 for (MethodHandle getter : e.getValue()) {
1011 assert ft == fieldType(getter);
1012 var hashThisField = filterArguments(hasher, mhParamCount, getter);
1013 var combineHashes = foldArguments(hashCombiner, 1, hashThisField);
1014 accumulator = foldArguments(combineHashes, 0, accumulator);
1015 }
1016 }
1017 return accumulator;
1018 }
1019
1020 private String debugString() {
1021 StringBuilder sb = new StringBuilder();
1022 sb.append(type.getName()).append(" ").append(status).append("\n");
1023 sb.append(fieldValueTypes.stream().filter(c -> !recurFieldTypes.contains(c))
1024 .map(Class::getName)
1025 .collect(joining(" ", " non-recursive types: ", "\n")));
1026 sb.append(recurFieldTypes.stream().map(Class::getName)
1027 .collect(joining(" ", " recursive types: ", "\n")));
1028 for (var n : cyclicMembers.keySet()) {
1029 List<Class<?>> cycle = cyclicMembers.get(n);
1030 sb.append(" cycle: ");
1031 int start = cycle.indexOf(n);
1032 for (int i=start; i < cycle.size(); i++ ) {
1033 sb.append(cycle.get(i).getName()).append(" -> ");
1034 }
1035 for (int i=0; i < start; i++) {
1036 sb.append(cycle.get(i).getName()).append(" -> ");
1037 }
1038 sb.append(n.getName()).append("\n");
1039 };
1040 return sb.toString();
1041 }
1042 }
1043
1044 private static LinkageError newLinkageError(Throwable e) {
1045 return (LinkageError) new LinkageError().initCause(e);
1046 }
1047
1048 /**
1049 * Returns {@code true} if the arguments are <em>substitutable</em> to each
1050 * other and {@code false} otherwise.
1051 * <em>Substitutability</em> means that they cannot be distinguished from
1052 * each other in any data-dependent way, meaning that it is safe to substitute
1053 * one for the other.
1054 *
1055 * <ul>
1056 * <li>If {@code a} and {@code b} are both {@code null}, this method returns
1057 * {@code true}.
1058 * <li>If {@code a} and {@code b} are both instances of the same value class
1059 * {@code V}, this method returns {@code true} if, for all fields {@code f}
1060 * declared in {@code V}, {@code a.f} and {@code b.f} are substitutable.
1061 * <li>If {@code a} and {@code b} are both values of the same builtin primitive type,
1062 * this method returns {@code a == b} with the following exception:
1063 * <ul>
1064 * <li> For primitive types {@code float} and {@code double} the
1065 * comparison uses the raw bits corresponding to {@link Float#floatToRawIntBits(float)}
1066 * and {@link Double#doubleToRawLongBits(double)} respectively.
1067 * </ul>
1068 * <li>If {@code a} and {@code b} are both instances of the same reference type,
1069 * this method returns {@code a == b}.
1070 * <li>Otherwise this method returns {@code false}.
1071 * </ul>
1072 *
1073 * <p>For example,
1074 * <pre>{@code interface Number { ... }
1075 * // ordinary reference class
1076 * class IntNumber implements Number { ... }
1077 * // value class
1078 * value class IntValue implements Number {
1079 * int i;
1080 * :
1081 * public static IntValue of(int i) {...} // IntValue::of creates a new value instance
1082 * }
1083 * // value class with an Object field
1084 * value class RefValue {
1085 * Object o;
1086 * :
1087 * }
1088 *
1089 * var val1 = IntValue.of(10);
1090 * var val2 = IntValue.of(10); // val1 and val2 have the same value
1091 * var ref1 = new IntNumber(10); // ref1 and ref2 are two reference instances
1092 * var ref2 = new IntNumber(10);
1093 * assertTrue(isSubstitutable(val1, val2)); // val1 and val2 are both value instances of IntValue
1094 * assertFalse(isSubstitutable(ref1, ref2)); // ref1 and ref2 are two reference instances that are not substitutable
1095 * assertTrue(isSubstitutable(ref1, ref1)); // a reference instance is substitutable with itself
1096 *
1097 * var rval1 = RefValue.of(List.of("list")); // rval1.o and rval2.o both contain a list of one-single element "list"
1098 * var rval2 = RefValue.of(List.of("list");
1099 * var rval3 = RefValue.of(rval1.o);
1100 *
1101 * assertFalse(isSubstitutable(rval1, rval2)); // rval1.o and rval2.o are two different List instances and hence not substitutable
1102 * assertTrue(isSubstitutable(rval1, rval3 )); // rval1.o and rval3.o are the same reference instance
1103 * }</pre>
1104 *
1105 * @param a an object
1106 * @param b an object to be compared with {@code a} for substitutability
1107 * @return {@code true} if the arguments are substitutable to each other;
1108 * {@code false} otherwise.
1109 * @param <T> type
1110 * @see Float#floatToRawIntBits(float)
1111 * @see Double#doubleToRawLongBits(double)
1112 */
1113 private static <T> boolean isSubstitutable(T a, Object b) {
1114 if (VERBOSE) {
1115 System.out.println("substitutable " + a.getClass() + ": " + a + " vs " + b);
1116 }
1117
1118 // Called directly from the VM.
1119 //
1120 // DO NOT use "==" or "!=" on args "a" and "b", with this code or any of
1121 // its callees. Could be inside of if_acmp<eq|ne> bytecode implementation.
1122
1123 if (a == null && b == null) return true;
1124 if (a == null || b == null) return false;
1125 if (a.getClass() != b.getClass()) return false;
1126
1127 try {
1128 Class<?> type = a.getClass();
1129 return (boolean) substitutableInvoker(type).invoke(a, b);
1130 } catch (Error|RuntimeException e) {
1131 if (VERBOSE) e.printStackTrace();
1132 throw e;
1133 } catch (Throwable e) {
1134 if (VERBOSE) e.printStackTrace();
1135 throw new InternalError(e);
1136 }
1137 }
1138
1139 /**
1140 * Produces a method handle which tests if two arguments are
1141 * {@linkplain #isSubstitutable(Object, Object) substitutable}.
1142 *
1143 * <ul>
1144 * <li>If {@code T} is a non-floating point primitive type, this method
1145 * returns a method handle testing the two arguments are the same value,
1146 * i.e. {@code a == b}.
1147 * <li>If {@code T} is {@code float} or {@code double}, this method
1148 * returns a method handle representing {@link Float#floatToRawIntBits(float)} or
1149 * {@link Double#doubleToRawLongBits(double)} respectively.
1150 * <li>If {@code T} is a reference type that is not {@code Object} and not an
1151 * interface, this method returns a method handle testing
1152 * the two arguments are the same reference, i.e. {@code a == b}.
1153 * <li>If {@code T} is a value class, this method returns
1154 * a method handle that returns {@code true} if
1155 * for all fields {@code f} declared in {@code T}, where {@code U} is
1156 * the type of {@code f}, if {@code a.f} and {@code b.f} are substitutable
1157 * with respect to {@code U}.
1158 * <li>If {@code T} is an interface or {@code Object}, and
1159 * {@code a} and {@code b} are of the same value class {@code V},
1160 * this method returns a method handle that returns {@code true} if
1161 * {@code a} and {@code b} are substitutable with respect to {@code V}.
1162 * </ul>
1163 *
1164 * @param type class type
1165 * @param <T> type
1166 * @return a method handle for substitutability test
1167 */
1168 private static <T> MethodHandle substitutableInvoker(Class<T> type) {
1169 if (type.isPrimitive()) {
1170 return MethodHandleBuilder.builtinPrimitiveSubstitutable(type);
1171 }
1172 if (type.isValue()) {
1173 return SUBST_TEST_METHOD_HANDLES.get(type);
1174 }
1175 return MethodHandleBuilder.referenceTypeEquals(type);
1176 }
1177
1178 private static final ClassValue<MethodHandleBuilder> METHOD_HANDLE_BUILDERS = new ClassValue<>() {
1179 @Override protected MethodHandleBuilder computeValue(Class<?> type) {
1180 var builder = CACHED_METHOD_HANDLE_BUILDERS.get(type);
1181 if (builder == null) {
1182 builder = MethodHandleBuilder.newBuilder(type).build();
1183 }
1184 return builder;
1185 }
1186 };
1187
1188 // This cache is only used to propagate the builders of mutual recursive types
1189 // A -> B -> C -> A as method handles for equals/hashCode for A, B, C are
1190 // all precomputed. This map should only be non-empty only during the short
1191 // window propagating to the method handle builder class value.
1192 private static Map<Class<?>, MethodHandleBuilder> CACHED_METHOD_HANDLE_BUILDERS = new ConcurrentHashMap<>();
1193
1194 // store the method handle for value classes in ClassValue
1195 private static final ClassValue<MethodHandle> SUBST_TEST_METHOD_HANDLES = new ClassValue<>() {
1196 @Override protected MethodHandle computeValue(Class<?> type) {
1197 return MethodHandleBuilder.valueTypeEquals(type);
1198 }
1199 };
1200
1201 /**
1202 * Invoke the hashCode method for the given value object.
1203 * @param o the instance to hash.
1204 * @return the hash code of the given value object.
1205 */
1206 private static int valueObjectHashCode(Object o) {
1207 Class<?> type = o.getClass();
1208 try {
1209 // Note: javac disallows user to call super.hashCode if user implemented
1210 // risk for recursion for experts crafting byte-code
1211 if (!type.isValue())
1212 throw new InternalError("must be value class: " + type.getName());
1213
1214 return (int) HASHCODE_METHOD_HANDLES.get(type).invoke(o);
1215 } catch (Error|RuntimeException e) {
1216 throw e;
1217 } catch (Throwable e) {
1218 if (VERBOSE) e.printStackTrace();
1219 throw new InternalError(e);
1220 }
1221 }
1222
1223 private static final ClassValue<MethodHandle> HASHCODE_METHOD_HANDLES = new ClassValue<>() {
1224 @Override protected MethodHandle computeValue(Class<?> type) {
1225 return MethodHandleBuilder.valueTypeHashCode(type);
1226 }
1227 };
1228
1229 private static final Comparator<MethodHandle> TYPE_SORTER = (mh1, mh2) -> {
1230 // sort the getters with the return type
1231 Class<?> t1 = mh1.type().returnType();
1232 Class<?> t2 = mh2.type().returnType();
1233 if (t1 == t2) return 0;
1234
1235 if (t1.isPrimitive()) {
1236 if (!t2.isPrimitive()) {
1237 return 1;
1238 }
1239 } else {
1240 if (t2.isPrimitive()) {
1241 return -1;
1242 }
1243 }
1244 return -1;
1245 };
1246
1247
1248 /**
1249 * Constructs a method handle that is capable of recursively
1250 * calling itself, whose behavior is determined by a non-recursive
1251 * base method handle which gets both the original arguments and a
1252 * reference to the recursive method handle.
1253 * <p>
1254 * Here is pseudocode for the resulting loop handle, plus a sketch
1255 * of the behavior of the base function. The symbols {@code A},
1256 * {@code a}, and {@code R} represent arguments and return value
1257 * for both the recursive function and the base function.
1258 *
1259 * <blockquote><pre>{@code
1260 * R recursive(A... a) {
1261 * MethodHandle recur = &recursive;
1262 * return base(recur, a...);
1263 * }
1264 * R base(MethodHandle recur, A... a) {
1265 * ... if (no recursion) return f(a); ...
1266 * var r2 = recur.invokeExact(a2...);
1267 * var r3 = recur.invokeExact(a3...);
1268 * ... do stuff with r2, r3, etc. ...
1269 * }
1270 * }</pre></blockquote>
1271 * <p>
1272 * To make several functions mutually recursive, additional base
1273 * arguments can be passed to this combinator. For each base
1274 * function, a recursive adapter is formed (like {@code recur}
1275 * above). The sequence of recursive adapters is passed as
1276 * initial arguments to each base function. Here is pseudocode
1277 * that corresponds to three base functions:
1278 * <blockquote><pre>{@code
1279 * R recursive(A... a) {
1280 * return base(&recursive, &recursive2, &recursive3, a...);
1281 * }
1282 * R2 recursive2(A2... a2) {
1283 * return base2(&recursive, &recursive2, &recursive3, a2...);
1284 * }
1285 * R3 recursive3(A3... a3) {
1286 * return base3(&recursive, &recursive2, &recursive3, a3...);
1287 * }
1288 * R base(MethodHandle recur, MethodHandle recur2,
1289 * MethodHandle recur3, A... a) {
1290 * ... if (no recursion) return f(a); ...
1291 * var r2 = recur2.invokeExact(a2...);
1292 * var r3 = recur3.invokeExact(a3...);
1293 * ... do stuff with r2, r3, etc. ...
1294 * }
1295 * R2 base2(MethodHandle recur, MethodHandle recur2,
1296 * MethodHandle recur3, A2... a2) { ... }
1297 * R3 base3(MethodHandle recur, MethodHandle recur2,
1298 * MethodHandle recur3, A3... a3) { ... }
1299 * }</pre></blockquote>
1300 *
1301 * @apiNote Example:
1302 * {@snippet lang="java" :
1303 * // classic recursive implementation of the factorial function
1304 * static int base(MethodHandle recur, int k) throws Throwable {
1305 * if (k <= 1) return 1;
1306 * return k * (int) recur.invokeExact(k - 1);
1307 * }
1308 * // assume MH_base is a handle to the above method
1309 * MethodHandle recur = MethodHandles.recursive(MH_base);
1310 * assertEquals(120, recur.invoke(5));
1311 * }
1312 * <p>
1313 * A constructed recursive method handle is made varargs
1314 * if its corresponding base method handle is varargs.
1315 * @implSpec
1316 * For a single base function, this produces a result equivalent to:
1317 * <pre>{@code
1318 * class Holder {
1319 * final MethodHandle recur;
1320 * static final MH_recur = ...; //field getter
1321 * Holder(MethodHandle base) {
1322 * recur = filterArguments(base, 0, MH_recur).bindTo(this);
1323 * }
1324 * }
1325 * return new Holder(base).recur;
1326 * }</pre>
1327 * @param base the logic of the function to make recursive
1328 * @param moreBases additional base functions to be made mutually recursive
1329 * @throws NullPointerException if any argument is null
1330 * @throws IllegalArgumentException if any base function does not accept
1331 * the required leading arguments of type {@code MethodHandle}
1332 *
1333 * @return a method handle which invokes the (first) base function
1334 * on the incoming arguments, with recursive versions of the
1335 * base function (or functions) prepended as extra arguments
1336 *
1337 * @since Valhalla
1338 */
1339 static MethodHandle recursive(MethodHandle base, MethodHandle... moreBases) {
1340 // freeze the varargs and check for nulls:
1341 List<MethodHandle> bases2 = List.of(moreBases);
1342 int baseCount = 1 + bases2.size();
1343 recursiveChecks(base, baseCount);
1344 for (var base2 : bases2) { recursiveChecks(base2, baseCount); }
1345 class Holder {
1346 final MethodHandle recur;
1347 final List<MethodHandle> recurs2;
1348 MethodHandle recurs2(int i) { return recurs2.get(i); }
1349 Holder() {
1350 // Feed the first baseCount parameters of each base
1351 // with a fetch of each recur, so we can bind to this:
1352 var fetchers = new MethodHandle[baseCount];
1353 fetchers[0] = MH_recur;
1354 for (int pos = 1; pos < fetchers.length; pos++) {
1355 int i = pos-1; // index into recurs2
1356 fetchers[pos] = MethodHandles.insertArguments(MH_recurs2, 1, i);
1357 }
1358 this.recur = makeRecur(base, fetchers);
1359 if (baseCount == 1) {
1360 this.recurs2 = List.of();
1361 } else {
1362 var recurs2 = new MethodHandle[baseCount-1];
1363 for (int i = 0; i < recurs2.length; i++) {
1364 recurs2[i] = makeRecur(bases2.get(i), fetchers);
1365 }
1366 this.recurs2 = List.of(recurs2);
1367 }
1368 }
1369 MethodHandle makeRecur(MethodHandle base, MethodHandle[] fetchers) {
1370 var adapt = filterArguments(base, 0, fetchers);
1371 for (int pos = 0; pos < fetchers.length; pos++) {
1372 adapt = adapt.bindTo(this);
1373 }
1374 return adapt.withVarargs(base.isVarargsCollector());
1375 }
1376 static final MethodHandle MH_recur, MH_recurs2;
1377 static {
1378 try {
1379 MH_recur = MethodHandles.lookup()
1380 .findGetter(Holder.class, "recur", MethodHandle.class);
1381 MH_recurs2 = MethodHandles.lookup()
1382 .findVirtual(Holder.class, "recurs2",
1383 methodType(MethodHandle.class, int.class));
1384 } catch (ReflectiveOperationException ex) {
1385 throw new InternalError(ex);
1386 }
1387 }
1388 }
1389 return new Holder().recur;
1390 }
1391
1392 private static void recursiveChecks(MethodHandle base, int baseCount) {
1393 MethodType mt = base.type(); // implicit null check
1394 boolean wrong = (mt.parameterCount() < baseCount);
1395 for (int i = 0; i < baseCount && !wrong; i++) {
1396 if (mt.parameterType(i) != MethodHandle.class) {
1397 wrong = true;
1398 }
1399 }
1400 if (!wrong) return;
1401 throw new IllegalArgumentException("missing leading MethodHandle parameters: " + mt);
1402 }
1403
1404 }