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