1 /*
2 * Copyright (c) 2018, 2022, 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.reflect.Modifier;
32 import java.util.ArrayDeque;
33 import java.util.ArrayList;
34 import java.util.Arrays;
35 import java.util.Comparator;
36 import java.util.Deque;
37 import java.util.HashMap;
38 import java.util.HashSet;
39 import java.util.List;
40 import java.util.Map;
41 import java.util.Objects;
42 import java.util.Set;
43 import java.util.concurrent.ConcurrentHashMap;
44 import java.util.concurrent.atomic.AtomicInteger;
45 import java.util.stream.Collectors;
46 import java.util.stream.Stream;
47 import jdk.internal.access.JavaLangInvokeAccess;
48 import jdk.internal.access.SharedSecrets;
49 import jdk.internal.value.PrimitiveClass;
50 import sun.invoke.util.Wrapper;
51 import sun.security.action.GetIntegerAction;
52 import sun.security.action.GetPropertyAction;
53
54 import static java.lang.invoke.MethodHandles.constant;
55 import static java.lang.invoke.MethodHandles.countedLoop;
56 import static java.lang.invoke.MethodHandles.dropArguments;
57 import static java.lang.invoke.MethodHandles.filterArguments;
58 import static java.lang.invoke.MethodHandles.filterReturnValue;
59 import static java.lang.invoke.MethodHandles.guardWithTest;
60 import static java.lang.invoke.MethodHandles.permuteArguments;
61 import static java.lang.invoke.MethodType.methodType;
62 import static java.lang.runtime.ObjectMethods.primitiveEquals;
63
64 /**
65 * Implementation for Object::equals and Object::hashCode for value objects.
66 *
67 * ValueObjectMethods::isSubstitutable and valueObjectHashCode are
68 * private entry points called by VM.
69 */
70 final class ValueObjectMethods {
71 private ValueObjectMethods() {}
72 private static final boolean VERBOSE =
73 GetPropertyAction.privilegedGetProperty("value.bsm.debug") != null;
74 private static final int THRESHOLD =
75 GetIntegerAction.privilegedGetProperty("jdk.value.recursion.threshold", Integer.MAX_VALUE);
76 private static final JavaLangInvokeAccess JLIA = SharedSecrets.getJavaLangInvokeAccess();
77
78 static class MethodHandleBuilder {
79 static Stream<MethodHandle> getterStream(Class<?> type, Comparator<MethodHandle> comparator) {
80 // filter static fields
81 Stream<MethodHandle> s = Arrays.stream(type.getDeclaredFields())
82 .filter(f -> !Modifier.isStatic(f.getModifiers()))
83 .map(f -> {
84 try {
85 return JLIA.unreflectField(f, false);
86 } catch (IllegalAccessException e) {
87 throw newLinkageError(e);
88 }
89 });
90 if (comparator != null) {
91 s = s.sorted(comparator);
92 }
93 return s;
94 }
95
96 static List<MethodHandle> getters(Class<?> type, Comparator<MethodHandle> comparator) {
97 return getterStream(type, comparator).toList();
98 }
99
100 static MethodHandle hashCodeForType(Class<?> type) {
101 if (type.isPrimitive()) {
102 int index = Wrapper.forPrimitiveType(type).ordinal();
103 return HASHCODE[index];
104 } else {
105 return HASHCODE[Wrapper.OBJECT.ordinal()].asType(methodType(int.class, type));
106 }
107 }
108
109 static MethodHandle builtinPrimitiveEquals(Class<?> type) {
110 return primitiveEquals.get(type);
111 }
112
113 /*
114 * Produces a MethodHandle that returns boolean if two instances
115 * of the given reference type are substitutable.
116 *
117 * Two values of reference type are substitutable i== iff
118 * 1. if o1 and o2 are both reference objects then o1 r== o2; or
119 * 2. if o1 and o2 are both values then o1 v== o2
120 *
121 * At invocation time, it needs a dynamic check on the objects and
122 * do the substitutability test if they are of a value class.
123 */
124 static MethodHandle referenceTypeEquals(Class<?> type) {
125 return OBJECT_EQUALS.asType(methodType(boolean.class, type, type));
126 }
127
128 static Class<?> fieldType(MethodHandle getter) {
129 Class<?> ftype = getter.type().returnType();
130 return ftype;
131 }
132
133 /**
134 * A base method for testing substitutability on a recursive data type,
135 * a value class with cyclic membership.
136 *
137 * This method will first invoke a method handle to test the substitutability
138 * of fields whose type is not recursively-typed. If true, then compares the
139 * value of the fields whose type is a recursive data type.
140 * For a field of its own type {@code f}, invoke the method handle for
141 * this base method on the field value of the given objects.
142 * For a field of other recursive data type, invoke {@link #isSubstitutable(Object, Object)}
143 * on the field value of the given objects.
144 *
145 * @param type a value class
146 * @param mh a MethodHandle that tests substitutability of all fields whose type
147 * is not recursively-typed. The method type is (V, V)boolean
148 * @param getters all getters for the fields whose type is a recursive data type
149 * @param recur MethodHandle that is capable of recursively calling itself
150 * to test if two objects of the given value class are substitutable.
151 * The method type is (Object, Object, AtomicInteger)boolean.
152 * @param o1 an object
153 * @param o2 an object to be compared for substitutability
154 * @param counter an AtomicInteger counter to keep track of the traversal count
155 * @return
156 * @param <V> a value class
157 */
158 private static <V> boolean substitutableBase(Class<V> type, MethodHandle mh, MethodHandle[] getters,
159 MethodHandle recur, Object o1, Object o2,
160 AtomicInteger counter) throws Throwable {
161 assert isValueClass(type) : type.getName() + " not a value class";
162
163 if (o1 == null && o2 == null) return true;
164 if (o1 == null || o2 == null) return false;
165
166 if (counter.getAndDecrement() == 0) {
167 throw new StackOverflowError("fail to evaluate == for value class " + type.getName());
168 }
169
170 // test if the substitutability of all fields whose type is not recursively-typed
171 var result = (boolean) mh.invoke(o1, o2);
172 if (result) {
173 assert o1.getClass() == type && o2.getClass() == type;
174
175 // test if the fields of a recursive data type are substitutable
176 for (MethodHandle getter : getters) {
177 Class<?> ftype = fieldType(getter);
178 var f1 = getter.invoke(o1);
179 var f2 = getter.invoke(o2);
180
181 boolean substitutable;
182 if (ftype == type) {
183 substitutable = (boolean)recur.invokeExact(f1, f2, counter);
184 } else {
185 MethodHandle recur2 = RECUR_SUBST_METHOD_HANDLES.get(ftype);
186 substitutable = (boolean)recur2.invokeExact(f1, f2, counter);
187 }
188 if (!substitutable) {
189 return false;
190 }
191 }
192 }
193 return result;
194 }
195
196
197 /**
198 * A base method for computing the hashcode for a recursive data type,
199 * a value class with cyclic membership.
200 *
201 * This method will first invoke a method handle to compute the hash code
202 * of the fields whose type is not recursively-typed. Then compute the
203 * hash code of the remaining fields whose type is a recursive data type.
204 * For a field of its own type {@code f}, invoke the method handle for
205 * this base method on the field value of the given object.
206 * For a field of other recursive data type, invoke {@link Object#hashCode()}
207 * on the field value of the given object.
208 *
209 * @param type a value class
210 * @param mh a MethodHandle that computes the hash code of all fields whose
211 * type is not recursively-typed. The method type is (V)int
212 * @param getters all getters for the fields whose type is a recursive data type
213 * @param recur MethodHandle that is capable of recursively calling itself
214 * to compute the hash code of a field of the same type.
215 * The method type is (Object, AtomicInteger)int.
216 * @param obj an object
217 * @param counter an AtomicInteger counter to keep track of the traversal count
218 * @return the hash code of a value object of the given type
219 * @param <V> a value class
220 */
221 private static <V> int hashCodeBase(Class<V> type, MethodHandle mh, MethodHandle[] getters,
222 MethodHandle recur, Object obj,
223 AtomicInteger counter) throws Throwable {
224 assert isValueClass(type) : type.getName() + " not a value class";
225
226 if (obj == null) return 0;
227
228 if (counter.getAndDecrement() == 0) {
229 throw new StackOverflowError("fail to evaluate hashCode of a value object: " + type.getName());
230 }
231
232 // compute the hash code of all fields whose type is not recursively-typed
233 var result = (int) mh.invoke(obj);
234 if (obj != null) {
235 assert obj.getClass() == type;
236
237 // test if the fields of a recursive data type are substitutable
238 for (MethodHandle getter : getters) {
239 Class<?> ftype = fieldType(getter);
240 var f = getter.invoke(obj);
241
242 int hc;
243 if (ftype == type) {
244 hc = (int)recur.invokeExact(f, counter);
245 } else {
246 MethodHandle recur2 = RECUR_HASHCODE_METHOD_HANDLES.get(ftype);
247 hc = (int)recur2.invokeExact(f, counter);
248 }
249 result = hashCombiner(result, hc);
250 }
251 }
252 return result;
253 }
254
255 /*
256 * Finds all value class memberships of the given type involved in cycles
257 */
258 private static Set<Class<?>> recursiveValueTypes(Class<?> type) {
259 if (!isValueClass(type)) {
260 return Set.of();
261 }
262
263 Deque<Class<?>> deque = new ArrayDeque<>();
264 Set<Class<?>> visited = new HashSet<>();
265 Set<Class<?>> recursiveTypes = new HashSet<>();
266 Map<Class<?>, List<Class<?>>> unvisitedEdges = new HashMap<>();
267
268 Class<?> c;
269 deque.add(type);
270 while ((c = deque.peek()) != null) {
271 if (visited.contains(c)) {
272 // remove the current node being visited
273 deque.pop();
274 if (deque.contains(c)) {
275 // include all types in the cycle
276 for (Class<?> n : deque) {
277 recursiveTypes.add(n);
278 if (n == c) {
279 break;
280 }
281 }
282 }
283
284 // continue the depth-first search from the parent of c
285 if ((c = deque.peek()) == null)
286 continue;
287 } else {
288 visited.add(c);
289 }
290
291 // depth-first search on the field types of type c that are value classes
292 List<Class<?>> nodes = unvisitedEdges.computeIfAbsent(c, (k) -> fieldTypes(k));
293 if (nodes.isEmpty()) {
294 // all field types are traversed
295 deque.pop();
296 } else {
297 Class<?> n = nodes.remove(0);
298 deque.push(n);
299 }
300 }
301
302 if (recursiveTypes.isEmpty())
303 return Set.of();
304
305 return Arrays.stream(type.getDeclaredFields())
306 .filter(f -> !Modifier.isStatic(f.getModifiers()))
307 .map(f -> f.getType())
308 .filter(recursiveTypes::contains)
309 .collect(Collectors.toSet());
310 }
311
312 private static List<Class<?>> fieldTypes(Class<?> type) {
313 List<Class<?>> result = new ArrayList<>();
314 Arrays.stream(type.getDeclaredFields())
315 .filter(f -> !Modifier.isStatic(f.getModifiers()))
316 .map(f -> f.getType())
317 .filter(ft -> isValueClass(ft) && !result.contains(ft))
318 .forEach(result::add);
319 return result;
320 }
321
322 private static final ClassValue<MethodHandle> RECUR_SUBST_METHOD_HANDLES = new ClassValue<>() {
323 /*
324 * Produces a MethodHandle that returns boolean if two value objects of
325 * a recursive data type are substitutable. This method is invoked by
326 * the substitutableBase method.
327 *
328 * The method type is (Object, Object, AtomicInteger)boolean.
329 */
330 @Override protected MethodHandle computeValue(Class<?> type) {
331 return recurValueTypeEquals(type, recursiveValueTypes(type));
332 }
333 };
334
335 /*
336 * Produces a MethodHandle that returns boolean if two value objects
337 * are substitutable. The method type is (V, V)boolean.
338 */
339 static MethodHandle valueTypeEquals(Class<?> type) {
340 // ensure the reference type of a primitive class not used in the method handle
341 assert isValueClass(type) || PrimitiveClass.isPrimitiveValueType(type);
342
343 Set<Class<?>> recursiveTypes = recursiveValueTypes(type);
344 if (recursiveTypes.isEmpty()) {
345 return valueTypeEquals(type, getters(type, TYPE_SORTER));
346 } else {
347 MethodHandle target = recurValueTypeEquals(type, recursiveTypes);
348 return MethodHandles.insertArguments(target, 2, new AtomicInteger(THRESHOLD))
349 .asType(methodType(boolean.class, type, type));
350 }
351 }
352
353 /*
354 * Produces a MethodHandle that returns boolean if the given fields
355 * of the two value objects are substitutable. The method type is (V, V)boolean
356 */
357 static MethodHandle valueTypeEquals(Class<?> type, List<MethodHandle> getters) {
358 // ensure the reference type of a primitive class not used in the method handle
359 assert isValueClass(type) || PrimitiveClass.isPrimitiveValueType(type);
360
361 MethodType mt = methodType(boolean.class, type, type);
362 MethodHandle instanceTrue = dropArguments(TRUE, 0, type, Object.class).asType(mt);
363 MethodHandle instanceFalse = dropArguments(FALSE, 0, type, Object.class).asType(mt);
364 MethodHandle accumulator = dropArguments(TRUE, 0, type, type);
365 for (MethodHandle getter : getters) {
366 Class<?> ftype = fieldType(getter);
367 MethodHandle eq = substitutableInvoker(ftype).asType(methodType(boolean.class, ftype, ftype));
368 MethodHandle thisFieldEqual = filterArguments(eq, 0, getter, getter);
369 accumulator = guardWithTest(thisFieldEqual, accumulator, instanceFalse);
370 }
371
372 // if both arguments are null, return true;
373 // otherwise return accumulator;
374 return guardWithTest(IS_NULL.asType(mt),
375 instanceTrue,
376 guardWithTest(IS_SAME_VALUE_CLASS.asType(mt),
377 accumulator,
378 instanceFalse));
379 }
380
381 /*
382 * Produces a MethodHandle that returns boolean if two value objects of
383 * a recursive data type are substitutable.
384 *
385 * The method type is (Object, Object, AtomicInteger)boolean.
386 */
387 static MethodHandle recurValueTypeEquals(Class<?> type, Set<Class<?>> recursiveTypes) {
388 Stream<MethodHandle> getterStream = getterStream(type, TYPE_SORTER);;
389 List<MethodHandle> nonRecurTypeGetters = new ArrayList<>();
390 List<MethodHandle> recurTypeGetters = new ArrayList<>();
391 getterStream.forEach(getter -> {
392 Class<?> ftype = fieldType(getter);
393 if (recursiveTypes.contains(ftype)) {
394 // skip the value class that is involved in a cyclic membership
395 recurTypeGetters.add(getter);
396 } else {
397 nonRecurTypeGetters.add(getter);
398 }
399 });
400
401 if (recurTypeGetters.isEmpty()) {
402 throw new InternalError("must be a recursive data type: " + type.getName());
403 }
404
405 MethodHandle target = valueTypeEquals(type, nonRecurTypeGetters);
406 // This value class contains cyclic membership
407 // Create a method handle that is capable of calling itself.
408 // - the substitutableBase method first calls the method handle that tests
409 // the substitutability of all fields that are not a recursive data type
410 // - for a field of its own type, call the recursive method
411 // - for a field of a recursive data type, call isSubstitutable
412 Object[] arguments = new Object[]{type, target, recurTypeGetters.toArray(MethodHandle[]::new)};
413 target = MethodHandles.insertArguments(RECUR_EQUALS, 0, arguments);
414 return recursive(target);
415 }
416
417 private static final ClassValue<MethodHandle> RECUR_HASHCODE_METHOD_HANDLES = new ClassValue<>() {
418 /*
419 * Produces a MethodHandle that returns the hashcode of a value object of
420 * a recursive data type. This method is invoked by the hashCodeBase method.
421 *
422 * The method type is (Object, AtomicInteger)int.
423 */
424 @Override protected MethodHandle computeValue(Class<?> type) {
425 return recurValueTypeHashCode(type, recursiveValueTypes(type));
426 }
427 };
428
429 /*
430 * Produces a MethodHandle that computes the hash code of a value object.
431 * The method type of the return MethodHandle is (V)int.
432 */
433 static MethodHandle valueTypeHashCode(Class<?> type) {
434 // ensure the reference type of a primitive class not used in the method handle
435 assert isValueClass(type) || PrimitiveClass.isPrimitiveValueType(type);
436
437 Set<Class<?>> recursiveTypes = recursiveValueTypes(type);
438 if (recursiveTypes.isEmpty()) {
439 return valueTypeHashCode(type, getterStream(type, null).toList());
440 } else {
441 MethodHandle target = recurValueTypeHashCode(type, recursiveTypes);
442 return MethodHandles.insertArguments(target, 1, new AtomicInteger(THRESHOLD))
443 .asType(methodType(int.class, type));
444 }
445 }
446
447 /*
448 * Produces a MethodHandle that returns the hash code computed from
449 * the given fields of a value object. The method type is (V)int.
450 */
451 static MethodHandle valueTypeHashCode(Class<?> type, List<MethodHandle> getters) {
452 // ensure the reference type of a primitive class not used in the method handle
453 assert isValueClass(type) || PrimitiveClass.isPrimitiveValueType(type);
454
455 MethodHandle target = dropArguments(constant(int.class, SALT), 0, type);
456 MethodHandle cls = dropArguments(constant(Class.class, type),0, type);
457 MethodHandle classHashCode = filterReturnValue(cls, hashCodeForType(Class.class));
458 MethodHandle combiner = filterArguments(HASH_COMBINER, 0, target, classHashCode);
459 // int v = SALT * 31 + type.hashCode();
460 MethodHandle init = permuteArguments(combiner, target.type(), 0, 0);
461 int length = getters.size();
462 MethodHandle iterations = dropArguments(constant(int.class, length), 0, type);
463 MethodHandle[] hashers = new MethodHandle[length];
464 for (int i=0; i < length; i++) {
465 MethodHandle getter = getters.get(i);
466 Class<?> ftype = fieldType(getter);
467
468 // For primitive types or reference types, this calls Objects::hashCode.
469 // For value objects and the hashCode method is not overridden,
470 // VM will call valueObjectHashCode to compute the hash code.
471 MethodHandle hasher = hashCodeForType(ftype);
472 hashers[i] = filterReturnValue(getter, hasher);
473 }
474
475 // for (int i=0; i < getters.length; i++) {
476 // v = computeHash(v, i, a);
477 // }
478 MethodHandle body = COMPUTE_HASH.bindTo(hashers)
479 .asType(methodType(int.class, int.class, int.class, type));
480 return countedLoop(iterations, init, body);
481 }
482
483 /*
484 * Produces a MethodHandle that returns the hashcode of a value object of
485 * a recursive data type. This method is invoked by the hashCodeBase method.
486 *
487 * The method type is (Object, AtomicInteger)int.
488 */
489 static MethodHandle recurValueTypeHashCode(Class<?> type, Set<Class<?>> recursiveTypes) {
490 Stream<MethodHandle> getterStream = getterStream(type, null);;
491 List<MethodHandle> nonRecurTypeGetters = new ArrayList<>();
492 List<MethodHandle> recurTypeGetters = new ArrayList<>();
493 getterStream.forEach(getter -> {
494 Class<?> ftype = fieldType(getter);
495 if (recursiveTypes.contains(ftype)) {
496 // skip the value class that is involved in a cyclic membership
497 recurTypeGetters.add(getter);
498 } else {
499 nonRecurTypeGetters.add(getter);
500 }
501 });
502
503 if (recurTypeGetters.isEmpty()) {
504 throw new InternalError("must be a recursive data type: " + type.getName());
505 }
506
507 MethodHandle target = valueTypeHashCode(type, nonRecurTypeGetters);
508 System.out.println(type.getName() + " valueHashCode " + nonRecurTypeGetters + " " + recurTypeGetters);
509
510 // This value class contains cyclic membership
511 // Create a method handle that is capable of calling itself.
512 // - the hashCodeBase method first calls the method handle that computes the hash code
513 // of all fields whose type is not recursively-typed
514 // - for a field of its own type, call the recursive method
515 // - for a field of a recursive data type, call valueObjectHashCode
516 Object[] arguments = new Object[]{type, target, recurTypeGetters.toArray(MethodHandle[]::new)};
517 target = MethodHandles.insertArguments(RECUR_HASHCODE, 0, arguments);
518 return recursive(target);
519 }
520
521 // ------ utility methods ------
522 private static boolean eq(Object a, Object b) {
523 if (a == null && b == null) return true;
524 if (a == null || b == null) return false;
525 if (a.getClass() != b.getClass()) return false;
526 return a.getClass().isValue() ? valueEquals(a, b) : (a == b);
527 }
528
529 /*
530 * Returns true if two value objects are substitutable.
531 */
532 private static boolean valueEquals(Object a, Object b) {
533 assert a != null && b != null && isSameValueClass(a, b);
534 try {
535 Class<?> type = a.getClass();
536 if (PrimitiveClass.isPrimitiveClass(type)) {
537 type = PrimitiveClass.asValueType(type);
538 }
539 return (boolean) substitutableInvoker(type).invoke(type.cast(a), type.cast(b));
540 } catch (Error|RuntimeException e) {
541 throw e;
542 } catch (Throwable e) {
543 throw new InternalError(e);
544 }
545 }
546
547 private static boolean isNull(Object a, Object b) {
548 // avoid acmp that will call isSubstitutable
549 if (a != null) return false;
550 if (b != null) return false;
551 return true;
552 }
553
554 /*
555 * Returns true if the given objects are of the same value class.
556 *
557 * Two objects are of the same value class iff:
558 * 1. a != null and b != null
559 * 2. the declaring class of a and b is the same value class
560 */
561 private static boolean isSameValueClass(Object a, Object b) {
562 if (a == null || b == null) return false;
563
564 return a.getClass().isValue() && a.getClass() == b.getClass();
565 }
566
567 private static int hashCombiner(int accumulator, int value) {
568 return accumulator * 31 + value;
569 }
570
571 private static int computeHashCode(MethodHandle[] hashers, int v, int i, Object o) {
572 try {
573 int hc = (int)hashers[i].invoke(o);
574 return hashCombiner(v, hc);
575 } catch (Error|RuntimeException e) {
576 throw e;
577 } catch (Throwable e) {
578 throw new InternalError(e);
579 }
580 }
581
582 private static final MethodHandle FALSE = constant(boolean.class, false);
583 private static final MethodHandle TRUE = constant(boolean.class, true);
584 private static final MethodHandle OBJECT_EQUALS =
585 findStatic("eq", methodType(boolean.class, Object.class, Object.class));
586 private static final MethodHandle IS_SAME_VALUE_CLASS =
587 findStatic("isSameValueClass", methodType(boolean.class, Object.class, Object.class));
588 private static final MethodHandle IS_NULL =
589 findStatic("isNull", methodType(boolean.class, Object.class, Object.class));
590 private static final MethodHandle HASH_COMBINER =
591 findStatic("hashCombiner", methodType(int.class, int.class, int.class));
592 private static final MethodHandle COMPUTE_HASH =
593 findStatic("computeHashCode", methodType(int.class, MethodHandle[].class, int.class, int.class, Object.class));
594 private static final MethodHandle[] HASHCODE = initHashCode();
595 private static final MethodHandle RECUR_EQUALS =
596 findStatic("substitutableBase",
597 methodType(boolean.class, Class.class, MethodHandle.class, MethodHandle[].class,
598 MethodHandle.class, Object.class, Object.class, AtomicInteger.class));
599 private static final MethodHandle RECUR_HASHCODE =
600 findStatic("hashCodeBase",
601 methodType(int.class, Class.class, MethodHandle.class, MethodHandle[].class,
602 MethodHandle.class, Object.class, AtomicInteger.class));
603
604 private static MethodHandle[] initHashCode() {
605 MethodHandle[] mhs = new MethodHandle[Wrapper.COUNT];
606 for (Wrapper wrapper : Wrapper.values()) {
607 if (wrapper == Wrapper.VOID) continue;
608 Class<?> cls = wrapper == Wrapper.OBJECT ? Objects.class : wrapper.wrapperType();
609 mhs[wrapper.ordinal()] = findStatic(cls, "hashCode",
610 methodType(int.class, wrapper.primitiveType()));
611 }
612 return mhs;
613 }
614
615 private static MethodHandle findStatic(String name, MethodType methodType) {
616 return findStatic(MethodHandleBuilder.class, name, methodType);
617 }
618 private static MethodHandle findStatic(Class<?> cls, String name, MethodType methodType) {
619 try {
620 return JLIA.findStatic(cls, name, methodType);
621 } catch (IllegalAccessException e) {
622 throw newLinkageError(e);
623 }
624 }
625
626 /**
627 * A "salt" value used for this internal hashcode implementation that
628 * needs to vary sufficiently from one run to the next so that
629 * the default hashcode for value classes will vary between JVM runs.
630 */
631 static final int SALT;
632 static {
633 long nt = System.nanoTime();
634 int value = (int)((nt >>> 32) ^ nt);
635 SALT = GetIntegerAction.privilegedGetProperty("value.bsm.salt", value);
636 }
637 }
638
639 private static LinkageError newLinkageError(Throwable e) {
640 return (LinkageError) new LinkageError().initCause(e);
641 }
642
643 /**
644 * Returns {@code true} if the arguments are <em>substitutable</em> to each
645 * other and {@code false} otherwise.
646 * <em>Substitutability</em> means that they cannot be distinguished from
647 * each other in any data-dependent way, meaning that it is safe to substitute
648 * one for the other.
649 *
650 * <ul>
651 * <li>If {@code a} and {@code b} are both {@code null}, this method returns
652 * {@code true}.
653 * <li>If {@code a} and {@code b} are both instances of the same value class
654 * {@code V}, this method returns {@code true} if, for all fields {@code f}
655 * declared in {@code V}, {@code a.f} and {@code b.f} are substitutable.
656 * <li>If {@code a} and {@code b} are both values of the same builtin primitive type,
657 * this method returns {@code a == b} with the following exception:
658 * <ul>
659 * <li> If {@code a} and {@code b} both represent {@code NaN},
660 * this method returns {@code true}, even though {@code NaN == NaN}
661 * has the value {@code false}.
662 * <li> If {@code a} is floating point positive zero while {@code b} is
663 * floating point negative zero, or vice versa, this method
664 * returns {@code false}, even though {@code +0.0 == -0.0} has
665 * the value {@code true}.
666 * </ul>
667 * <li>If {@code a} and {@code b} are both instances of the same reference type,
668 * this method returns {@code a == b}.
669 * <li>Otherwise this method returns {@code false}.
670 * </ul>
671 *
672 * <p>For example,
673 * <pre>{@code interface Number { ... }
674 * // ordinary reference class
675 * class IntNumber implements Number { ... }
676 * // value class
677 * value class IntValue implements Number {
678 * int i;
679 * :
680 * public static IntValue of(int i) {...} // IntValue::of creates a new value instance
681 * }
682 * // value class with an Object field
683 * value class RefValue {
684 * Object o;
685 * :
686 * }
687 *
688 * var val1 = IntValue.of(10);
689 * var val2 = IntValue.of(10); // val1 and val2 have the same value
690 * var ref1 = new IntNumber(10); // ref1 and ref2 are two reference instances
691 * var ref2 = new IntNumber(10);
692 * assertTrue(isSubstitutable(val1, val2)); // val1 and val2 are both value instances of IntValue
693 * assertFalse(isSubstitutable(ref1, ref2)); // ref1 and ref2 are two reference instances that are not substitutable
694 * assertTrue(isSubstitutable(ref1, ref1)); // a reference instance is substitutable with itself
695 *
696 * var rval1 = RefValue.of(List.of("list")); // rval1.o and rval2.o both contain a list of one-single element "list"
697 * var rval2 = RefValue.of(List.of("list");
698 * var rval3 = RefValue.of(rval1.o);
699 *
700 * assertFalse(isSubstitutable(rval1, rval2)); // rval1.o and rval2.o are two different List instances and hence not substitutable
701 * assertTrue(isSubstitutable(rval1, rval3 )); // rval1.o and rval3.o are the same reference instance
702 * }</pre>
703 *
704 * @param a an object
705 * @param b an object to be compared with {@code a} for substitutability
706 * @return {@code true} if the arguments are substitutable to each other;
707 * {@code false} otherwise.
708 * @param <T> type
709 * @see Float#equals(Object)
710 * @see Double#equals(Object)
711 */
712 private static <T> boolean isSubstitutable(T a, Object b) {
713 if (VERBOSE) {
714 System.out.println("substitutable " + a + " vs " + b);
715 }
716
717 // Called directly from the VM.
718 //
719 // DO NOT use "==" or "!=" on args "a" and "b", with this code or any of
720 // its callees. Could be inside of if_acmp<eq|ne> bytecode implementation.
721
722 if (a == null && b == null) return true;
723 if (a == null || b == null) return false;
724 if (a.getClass() != b.getClass()) return false;
725
726 try {
727 Class<?> type = a.getClass();
728 if (PrimitiveClass.isPrimitiveClass(type)) {
729 type = PrimitiveClass.asValueType(type);
730 }
731 return (boolean) substitutableInvoker(type).invoke(a, b);
732 } catch (Error|RuntimeException e) {
733 if (VERBOSE) e.printStackTrace();
734 throw e;
735 } catch (Throwable e) {
736 if (VERBOSE) e.printStackTrace();
737 throw new InternalError(e);
738 }
739 }
740
741 /**
742 * Produces a method handle which tests if two arguments are
743 * {@linkplain #isSubstitutable(Object, Object) substitutable}.
744 *
745 * <ul>
746 * <li>If {@code T} is a non-floating point primitive type, this method
747 * returns a method handle testing the two arguments are the same value,
748 * i.e. {@code a == b}.
749 * <li>If {@code T} is {@code float} or {@code double}, this method
750 * returns a method handle representing {@link Float#equals(Object)} or
751 * {@link Double#equals(Object)} respectively.
752 * <li>If {@code T} is a reference type that is not {@code Object} and not an
753 * interface, this method returns a method handle testing
754 * the two arguments are the same reference, i.e. {@code a == b}.
755 * <li>If {@code T} is a value class, this method returns
756 * a method handle that returns {@code true} if
757 * for all fields {@code f} declared in {@code T}, where {@code U} is
758 * the type of {@code f}, if {@code a.f} and {@code b.f} are substitutable
759 * with respect to {@code U}.
760 * <li>If {@code T} is an interface or {@code Object}, and
761 * {@code a} and {@code b} are of the same value class {@code V},
762 * this method returns a method handle that returns {@code true} if
763 * {@code a} and {@code b} are substitutable with respect to {@code V}.
764 * </ul>
765 *
766 * @param type class type
767 * @param <T> type
768 * @return a method handle for substitutability test
769 */
770 private static <T> MethodHandle substitutableInvoker(Class<T> type) {
771 if (type.isPrimitive())
772 return MethodHandleBuilder.builtinPrimitiveEquals(type);
773
774 if (isValueClass(type) || PrimitiveClass.isPrimitiveValueType(type)) {
775 return SUBST_TEST_METHOD_HANDLES.get(type);
776 }
777 return MethodHandleBuilder.referenceTypeEquals(type);
778 }
779
780 // store the method handle for value classes in ClassValue
781 private static final ClassValue<MethodHandle> SUBST_TEST_METHOD_HANDLES = new ClassValue<>() {
782 @Override protected MethodHandle computeValue(Class<?> type) {
783 return MethodHandleBuilder.valueTypeEquals(type);
784 }
785 };
786
787 /**
788 * Invoke the hashCode method for the given value object.
789 * @param o the instance to hash.
790 * @return the hash code of the given value object.
791 */
792 private static int valueObjectHashCode(Object o) {
793 Class<?> c = o.getClass();
794 try {
795 // Note: javac disallows user to call super.hashCode if user implemented
796 // risk for recursion for experts crafting byte-code
797 if (!c.isValue())
798 throw new InternalError("must be value or primitive class: " + c.getName());
799
800 Class<?> type = PrimitiveClass.isPrimitiveClass(c) ? PrimitiveClass.asValueType(c) : c;
801 return (int) HASHCODE_METHOD_HANDLES.get(type).invoke(o);
802 } catch (Error|RuntimeException e) {
803 throw e;
804 } catch (Throwable e) {
805 if (VERBOSE) e.printStackTrace();
806 throw new InternalError(e);
807 }
808 }
809
810 /**
811 * Returns true if the given type is a value class.
812 */
813 private static boolean isValueClass(Class<?> type) {
814 return type.isValue() && !PrimitiveClass.isPrimitiveClass(type);
815 }
816
817 private static final ClassValue<MethodHandle> HASHCODE_METHOD_HANDLES = new ClassValue<>() {
818 @Override protected MethodHandle computeValue(Class<?> type) {
819 return MethodHandleBuilder.valueTypeHashCode(type);
820 }
821 };
822
823 private static final Comparator<MethodHandle> TYPE_SORTER = (mh1, mh2) -> {
824 // sort the getters with the return type
825 Class<?> t1 = mh1.type().returnType();
826 Class<?> t2 = mh2.type().returnType();
827 if (t1 == t2) return 0;
828
829 if (t1.isPrimitive()) {
830 if (!t2.isPrimitive()) {
831 return 1;
832 }
833 } else {
834 if (t2.isPrimitive()) {
835 return -1;
836 }
837 }
838 return -1;
839 };
840
841
842 /**
843 * Constructs a method handle that is capable of recursively
844 * calling itself, whose behavior is determined by a non-recursive
845 * base method handle which gets both the original arguments and a
846 * reference to the recursive method handle.
847 * <p>
848 * Here is pseudocode for the resulting loop handle, plus a sketch
849 * of the behavior of the base function. The symbols {@code A},
850 * {@code a}, and {@code R} represent arguments and return value
851 * for both the recursive function and the base function.
852 *
853 * <blockquote><pre>{@code
854 * R recursive(A... a) {
855 * MethodHandle recur = &recursive;
856 * return base(recur, a...);
857 * }
858 * R base(MethodHandle recur, A... a) {
859 * ... if (no recursion) return f(a); ...
860 * var r2 = recur.invokeExact(a2...);
861 * var r3 = recur.invokeExact(a3...);
862 * ... do stuff with r2, r3, etc. ...
863 * }
864 * }</pre></blockquote>
865 * <p>
866 * To make several functions mutually recursive, additional base
867 * arguments can be passed to this combinator. For each base
868 * function, a recursive adapter is formed (like {@code recur}
869 * above). The sequence of recursive adapters is passed as
870 * initial arguments to each base function. Here is pseudocode
871 * that corresponds to three base functions:
872 * <blockquote><pre>{@code
873 * R recursive(A... a) {
874 * return base(&recursive, &recursive2, &recursive3, a...);
875 * }
876 * R2 recursive2(A2... a2) {
877 * return base2(&recursive, &recursive2, &recursive3, a2...);
878 * }
879 * R3 recursive3(A3... a3) {
880 * return base2(&recursive, &recursive2, &recursive3, a3...);
881 * }
882 * R base(MethodHandle recur, MethodHandle recur2,
883 * MethodHandle recur3, A... a) {
884 * ... if (no recursion) return f(a); ...
885 * var r2 = recur2.invokeExact(a2...);
886 * var r3 = recur3.invokeExact(a3...);
887 * ... do stuff with r2, r3, etc. ...
888 * }
889 * R2 base2(MethodHandle recur, MethodHandle recur2,
890 * MethodHandle recur3, A2... a2) { ... }
891 * R3 base3(MethodHandle recur, MethodHandle recur2,
892 * MethodHandle recur3, A3... a3) { ... }
893 * }</pre></blockquote>
894 *
895 * @apiNote Example:
896 * {@snippet lang="java" :
897 * // classic recursive implementation of the factorial function
898 * static int base(MethodHandle recur, int k) throws Throwable {
899 * if (k <= 1) return 1;
900 * return k * (int) recur.invokeExact(k - 1);
901 * }
902 * // assume MH_base is a handle to the above method
903 * MethodHandle recur = MethodHandles.recursive(MH_base);
904 * assertEquals(120, recur.invoke(5));
905 * }
906 * <p>
907 * A constructed recursive method handle is made varargs
908 * if its corresponding base method handle is varargs.
909 * @implSpec
910 * For a single base function, this produces a result equivalent to:
911 * <pre>{@code
912 * class Holder {
913 * final MethodHandle recur;
914 * static final MH_recur = ...; //field getter
915 * Holder(MethodHandle base) {
916 * recur = filterArguments(base, 0, MH_recur).bindTo(this);
917 * }
918 * }
919 * return new Holder(base).recur;
920 * }</pre>
921 * @param base the logic of the function to make recursive
922 * @param moreBases additional base functions to be made mutually recursive
923 * @throws NullPointerException if any argument is null
924 * @throws IllegalArgumentException if any base function does not accept
925 * the required leading arguments of type {@code MethodHandle}
926 *
927 * @return a method handle which invokes the (first) base function
928 * on the incoming arguments, with recursive versions of the
929 * base function (or functions) prepended as extra arguments
930 *
931 * @since Valhalla
932 */
933 static MethodHandle recursive(MethodHandle base, MethodHandle... moreBases) {
934 // freeze the varargs and check for nulls:
935 List<MethodHandle> bases2 = List.of(moreBases);
936 int baseCount = 1 + bases2.size();
937 recursiveChecks(base, baseCount);
938 for (var base2 : bases2) { recursiveChecks(base2, baseCount); }
939 class Holder {
940 final MethodHandle recur;
941 final List<MethodHandle> recurs2;
942 MethodHandle recurs2(int i) { return recurs2.get(i); }
943 Holder() {
944 // Feed the first baseCount parameters of each base
945 // with a fetch of each recur, so we can bind to this:
946 var fetchers = new MethodHandle[baseCount];
947 fetchers[0] = MH_recur;
948 for (int pos = 1; pos < fetchers.length; pos++) {
949 int i = pos-1; // index into recurs2
950 fetchers[pos] = MethodHandles.insertArguments(MH_recurs2, 1, i);
951 }
952 this.recur = makeRecur(base, fetchers);
953 if (baseCount == 1) {
954 this.recurs2 = List.of();
955 } else {
956 var recurs2 = new MethodHandle[baseCount-1];
957 for (int i = 0; i < recurs2.length; i++) {
958 recurs2[i] = makeRecur(bases2.get(i), fetchers);
959 }
960 this.recurs2 = List.of(recurs2);
961 }
962 }
963 MethodHandle makeRecur(MethodHandle base, MethodHandle[] fetchers) {
964 var adapt = filterArguments(base, 0, fetchers);
965 for (int pos = 0; pos < fetchers.length; pos++) {
966 adapt = adapt.bindTo(this);
967 }
968 return adapt.withVarargs(base.isVarargsCollector());
969 }
970 static final MethodHandle MH_recur, MH_recurs2;
971 static {
972 try {
973 MH_recur = MethodHandles.lookup()
974 .findGetter(Holder.class, "recur", MethodHandle.class);
975 MH_recurs2 = MethodHandles.lookup()
976 .findVirtual(Holder.class, "recurs2",
977 methodType(MethodHandle.class, int.class));
978 } catch (ReflectiveOperationException ex) {
979 throw new InternalError(ex);
980 }
981 }
982 }
983 return new Holder().recur;
984 }
985
986 private static void recursiveChecks(MethodHandle base, int baseCount) {
987 MethodType mt = base.type(); // implicit null check
988 boolean wrong = (mt.parameterCount() < baseCount);
989 for (int i = 0; i < baseCount && !wrong; i++) {
990 if (mt.parameterType(i) != MethodHandle.class) {
991 wrong = true;
992 }
993 }
994 if (!wrong) return;
995 throw new IllegalArgumentException("missing leading MethodHandle parameters: " + mt);
996 }
997
998 }