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