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