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