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