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.MethodType;
 30 import java.lang.reflect.Modifier;
 31 import java.util.Arrays;
 32 import java.util.Comparator;
 33 import java.util.Objects;
 34 import java.util.stream.Stream;
 35 import jdk.internal.access.JavaLangInvokeAccess;
 36 import jdk.internal.access.SharedSecrets;
 37 import jdk.internal.value.PrimitiveClass;
 38 import sun.invoke.util.Wrapper;
 39 import sun.security.action.GetIntegerAction;
 40 import sun.security.action.GetPropertyAction;
 41 
 42 import static java.lang.invoke.MethodHandles.constant;
 43 import static java.lang.invoke.MethodHandles.countedLoop;
 44 import static java.lang.invoke.MethodHandles.dropArguments;
 45 import static java.lang.invoke.MethodHandles.filterArguments;
 46 import static java.lang.invoke.MethodHandles.filterReturnValue;
 47 import static java.lang.invoke.MethodHandles.guardWithTest;
 48 import static java.lang.invoke.MethodHandles.permuteArguments;
 49 import static java.lang.invoke.MethodType.methodType;
 50 import static java.lang.runtime.ObjectMethods.primitiveEquals;
 51 
 52 /**
 53  * Implementation for Object::equals and Object::hashCode for primitive classes.
 54  *
 55  * PrimitiveObjectMethods::isSubstitutable and primitiveObjectHashCode are
 56  * private entry points called by VM.
 57  */
 58 final class PrimitiveObjectMethods {
 59     private PrimitiveObjectMethods() {}
 60     private static final boolean VERBOSE =
 61         GetPropertyAction.privilegedGetProperty("value.bsm.debug") != null;
 62     private static final JavaLangInvokeAccess JLIA = SharedSecrets.getJavaLangInvokeAccess();
 63 
 64     static class MethodHandleBuilder {
 65         static MethodHandle[] getters(Class<?> type) {
 66             return getters(type, null);
 67         }
 68 
 69         static MethodHandle[] getters(Class<?> type, Comparator<MethodHandle> comparator) {
 70             // filter static fields
 71             Stream<MethodHandle> s = Arrays.stream(type.getDeclaredFields())
 72                 .filter(f -> !Modifier.isStatic(f.getModifiers()))
 73                 .map(f -> {
 74                     try {
 75                         return JLIA.unreflectField(f, false);
 76                     } catch (IllegalAccessException e) {
 77                         throw newLinkageError(e);
 78                     }
 79                 });
 80             if (comparator != null) {
 81                 s = s.sorted(comparator);
 82             }
 83             return s.toArray(MethodHandle[]::new);
 84         }
 85 
 86         static MethodHandle hashCodeForType(Class<?> type) {
 87             if (type.isPrimitive()) {
 88                 int index = Wrapper.forPrimitiveType(type).ordinal();
 89                 return HASHCODE[index];
 90             } else {
 91                 return HASHCODE[Wrapper.OBJECT.ordinal()].asType(methodType(int.class, type));
 92             }
 93         }
 94 
 95         static MethodHandle primitiveEquals(Class<?> primitiveType) {
 96             return primitiveEquals.get(primitiveType);
 97         }
 98 
 99         /*
100          * Produces a MethodHandle that returns boolean if two instances
101          * of the given reference type are substitutable.
102          *
103          * Two values of reference type are substitutable i== iff
104          * 1. if o1 and o2 are both reference objects then o1 r== o2; or
105          * 2. if o1 and o2 are both values then o1 v== o2
106          *
107          * At invocation time, it needs a dynamic check on the objects and
108          * do the substitutability test if they are of a primitive type.
109          */
110         static MethodHandle referenceTypeEquals(Class<?> type) {
111             return OBJECT_EQUALS.asType(methodType(boolean.class, type, type));
112         }
113 
114         static Class<?> fieldType(MethodHandle getter) {
115             Class<?> ftype = getter.type().returnType();
116             return ftype;
117         }
118 
119         /*
120          * Produces a MethodHandle that returns boolean if two value instances
121          * of the given primitive class are substitutable.
122          */
123         static MethodHandle primitiveTypeEquals(Class<?> type) {
124             assert PrimitiveClass.isPrimitiveValueType(type) ||
125                     (type.isValue() && !PrimitiveClass.isPrimitiveClass(type));
126             MethodType mt = methodType(boolean.class, type, type);
127             MethodHandle[] getters = getters(type, TYPE_SORTER);
128             MethodHandle instanceTrue = dropArguments(TRUE, 0, type, Object.class).asType(mt);
129             MethodHandle instanceFalse = dropArguments(FALSE, 0, type, Object.class).asType(mt);
130             MethodHandle accumulator = dropArguments(TRUE, 0, type, type);
131             for (MethodHandle getter : getters) {
132                 Class<?> ftype = fieldType(getter);
133                 MethodHandle eq = substitutableInvoker(ftype).asType(methodType(boolean.class, ftype, ftype));
134                 MethodHandle thisFieldEqual = filterArguments(eq, 0, getter, getter);
135                 accumulator = guardWithTest(thisFieldEqual, accumulator, instanceFalse);
136             }
137             // if both arguments are null, return true;
138             // otherwise return accumulator;
139             return guardWithTest(IS_NULL.asType(mt),
140                                  instanceTrue,
141                                  guardWithTest(IS_SAME_VALUE_CLASS.asType(mt),
142                                                accumulator,
143                                                instanceFalse));
144         }
145 
146         static MethodHandle primitiveTypeHashCode(Class<?> type) {
147             assert PrimitiveClass.isPrimitiveValueType(type) ||
148                     (type.isValue() && !PrimitiveClass.isPrimitiveClass(type));
149             MethodHandle target = dropArguments(constant(int.class, SALT), 0, type);
150             MethodHandle cls = dropArguments(constant(Class.class, type),0, type);
151             MethodHandle classHashCode = filterReturnValue(cls, hashCodeForType(Class.class));
152             MethodHandle combiner = filterArguments(HASH_COMBINER, 0, target, classHashCode);
153             // int v = SALT * 31 + type.hashCode();
154             MethodHandle init = permuteArguments(combiner, target.type(), 0, 0);
155             MethodHandle[] getters = MethodHandleBuilder.getters(type);
156             MethodHandle iterations = dropArguments(constant(int.class, getters.length), 0, type);
157             MethodHandle[] hashers = new MethodHandle[getters.length];
158             for (int i=0; i < getters.length; i++) {
159                 MethodHandle getter = getters[i];
160                 Class<?> ftype = fieldType(getter);
161 
162                 // For primitive type or reference type, this calls Objects::hashCode.
163                 // If the instance is of primitive type and the hashCode method is not
164                 // overridden, VM will call primitiveObjectHashCode to compute the
165                 // hash code.
166                 MethodHandle hasher = hashCodeForType(ftype);
167                 hashers[i] = filterReturnValue(getter, hasher);
168             }
169 
170             // for (int i=0; i < getters.length; i++) {
171             //   v = computeHash(v, i, a);
172             // }
173             MethodHandle body = COMPUTE_HASH.bindTo(hashers)
174                     .asType(methodType(int.class, int.class, int.class, type));
175             return countedLoop(iterations, init, body);
176         }
177 
178         // ------ utility methods ------
179         private static boolean eq(Object a, Object b)   {
180             if (a == null && b == null) return true;
181             if (a == null || b == null) return false;
182             if (a.getClass() != b.getClass()) return false;
183             return a.getClass().isValue() ? valueEq(a, b) : (a == b);
184         }
185 
186         /*
187          * Returns true if two values are substitutable.
188          */
189         private static boolean valueEq(Object a, Object b) {
190             assert a != null && b != null && isSameValueClass(a, b);
191             try {
192                 Class<?> type = a.getClass();
193                 if (PrimitiveClass.isPrimitiveClass(type)) {
194                     type = PrimitiveClass.asValueType(type);
195                 }
196                 return (boolean) substitutableInvoker(type).invoke(type.cast(a), type.cast(b));
197             } catch (Error|RuntimeException e) {
198                 throw e;
199             } catch (Throwable e) {
200                 throw new InternalError(e);
201             }
202         }
203 
204         private static boolean isNull(Object a, Object b) {
205             // avoid acmp that will call isSubstitutable
206             if (a != null) return false;
207             if (b != null) return false;
208             return true;
209         }
210 
211         /*
212          * Returns true if the given objects are of the same primitive class.
213          *
214          * Two objects are of the same primitive class iff:
215          * 1. a != null and b != null
216          * 2. the declaring class of a and b is the same primitive class
217          */
218         private static boolean isSameValueClass(Object a, Object b) {
219             if (a == null || b == null) return false;
220 
221             return a.getClass().isValue() && a.getClass() == b.getClass();
222         }
223 
224         private static int hashCombiner(int accumulator, int value) {
225             return accumulator * 31 + value;
226         }
227 
228         private static int computeHashCode(MethodHandle[] hashers, int v, int i, Object o) {
229             try {
230                 int hc = (int)hashers[i].invoke(o);
231                 return hashCombiner(v, hc);
232             } catch (Error|RuntimeException e) {
233                 throw e;
234             } catch (Throwable e) {
235                 throw new InternalError(e);
236             }
237         }
238 
239         private static final MethodHandle FALSE = constant(boolean.class, false);
240         private static final MethodHandle TRUE = constant(boolean.class, true);
241         private static final MethodHandle OBJECT_EQUALS = findStatic("eq", methodType(boolean.class, Object.class, Object.class));
242         private static final MethodHandle IS_SAME_VALUE_CLASS =
243             findStatic("isSameValueClass", methodType(boolean.class, Object.class, Object.class));
244         private static final MethodHandle IS_NULL =
245             findStatic("isNull", methodType(boolean.class, Object.class, Object.class));
246         private static final MethodHandle HASH_COMBINER =
247             findStatic("hashCombiner", methodType(int.class, int.class, int.class));
248         private static final MethodHandle COMPUTE_HASH =
249             findStatic("computeHashCode", methodType(int.class, MethodHandle[].class, int.class, int.class, Object.class));
250         private static final MethodHandle[] HASHCODE = initHashCode();
251 
252         private static MethodHandle[] initHashCode() {
253             MethodHandle[] mhs = new MethodHandle[Wrapper.COUNT];
254             for (Wrapper wrapper : Wrapper.values()) {
255                 if (wrapper == Wrapper.VOID) continue;
256                 Class<?> cls = wrapper == Wrapper.OBJECT ? Objects.class : wrapper.wrapperType();
257                 mhs[wrapper.ordinal()] = findStatic(cls, "hashCode",
258                                                     methodType(int.class, wrapper.primitiveType()));
259             }
260             return mhs;
261         }
262 
263         private static MethodHandle findStatic(String name, MethodType methodType) {
264             return findStatic(MethodHandleBuilder.class, name, methodType);
265         }
266         private static MethodHandle findStatic(Class<?> cls, String name, MethodType methodType) {
267             try {
268                 return JLIA.findStatic(cls, name, methodType);
269             } catch (IllegalAccessException e) {
270                 throw newLinkageError(e);
271             }
272         }
273 
274         /**
275          * A "salt" value used for this internal hashcode implementation that
276          * needs to vary sufficiently from one run to the next so that
277          * the default hashcode for value types will vary between JVM runs.
278          */
279         static final int SALT;
280         static {
281             long nt = System.nanoTime();
282             int value = (int)((nt >>> 32) ^ nt);
283             SALT = GetIntegerAction.privilegedGetProperty("value.bsm.salt", value);
284         }
285     }
286 
287     private static LinkageError newLinkageError(Throwable e) {
288         return (LinkageError) new LinkageError().initCause(e);
289     }
290 
291     /**
292      * Returns {@code true} if the arguments are <em>substitutable</em> to each
293      * other and {@code false} otherwise.
294      * <em>Substitutability</em> means that they cannot be distinguished from
295      * each other in any data-dependent way, meaning that it is safe to substitute
296      * one for the other.
297      *
298      * <ul>
299      * <li>If {@code a} and {@code b} are both {@code null}, this method returns
300      *     {@code true}.
301      * <li>If {@code a} and {@code b} are both value instances of the same class
302      *     {@code V}, this method returns {@code true} if, for all fields {@code f}
303      *      declared in {@code V}, {@code a.f} and {@code b.f} are substitutable.
304      * <li>If {@code a} and {@code b} are both primitives of the same type,
305      *     this method returns {@code a == b} with the following exception:
306      *     <ul>
307      *     <li> If {@code a} and {@code b} both represent {@code NaN},
308      *          this method returns {@code true}, even though {@code NaN == NaN}
309      *          has the value {@code false}.
310      *     <li> If {@code a} is floating point positive zero while {@code b} is
311      *          floating point negative zero, or vice versa, this method
312      *          returns {@code false}, even though {@code +0.0 == -0.0} has
313      *          the value {@code true}.
314      *     </ul>
315      * <li>If {@code a} and {@code b} are both instances of the same reference type,
316      *     this method returns {@code a == b}.
317      * <li>Otherwise this method returns {@code false}.
318      * </ul>
319      *
320      * <p>For example,
321      * <pre>{@code interface Number { ... }
322      * // ordinary reference class
323      * class IntNumber implements Number { ... }
324      * // value class
325      * value class IntValue implements Number {
326      *     int i;
327      *     :
328      *     public static IntValue of(int i) {...}     // IntValue::of creates a new value instance
329      * }
330      * // value class with an Object field
331      * value class RefValue {
332      *     Object o;
333      *     :
334      * }
335      *
336      * var val1 = IntValue.of(10);
337      * var val2 = IntValue.of(10);                    // val1 and val2 have the same value
338      * var ref1 = new IntNumber(10);                  // ref1 and ref2 are two reference instances
339      * var ref2 = new IntNumber(10);
340      * assertTrue(isSubstitutable(val1, val2));       // val1 and val2 are both value instances of IntValue
341      * assertFalse(isSubstitutable(ref1, ref2));      // ref1 and ref2 are two reference instances that are not substitutable
342      * assertTrue(isSubstitutable(ref1, ref1));       // a reference instance is substitutable with itself
343      *
344      * var rval1 = RefValue.of(List.of("list"));      // rval1.o and rval2.o both contain a list of one-single element "list"
345      * var rval2 = RefValue.of(List.of("list");
346      * var rval3 = RefValue.of(rval1.o);
347      *
348      * assertFalse(isSubstitutable(rval1, rval2));    // rval1.o and rval2.o are two different List instances and hence not substitutable
349      * assertTrue(isSubstitutable(rval1, rval3 ));    // rval1.o and rval3.o are the same reference instance
350      * }</pre>
351      *
352      * @param a an object
353      * @param b an object to be compared with {@code a} for substitutability
354      * @return {@code true} if the arguments are substitutable to each other;
355      *         {@code false} otherwise.
356      * @param <T> type
357      * @see Float#equals(Object)
358      * @see Double#equals(Object)
359      */
360     private static <T> boolean isSubstitutable(T a, Object b) {
361         if (VERBOSE) {
362             System.out.println("substitutable " + a + " vs " + b);
363         }
364 
365         // Called directly from the VM.
366         //
367         // DO NOT use "==" or "!=" on args "a" and "b", with this code or any of
368         // its callees. Could be inside of if_acmp<eq|ne> bytecode implementation.
369 
370         if (a == null && b == null) return true;
371         if (a == null || b == null) return false;
372         if (a.getClass() != b.getClass()) return false;
373 
374         try {
375             Class<?> type = a.getClass();
376             if (PrimitiveClass.isPrimitiveClass(type)) {
377                 type = PrimitiveClass.asValueType(type);
378             }
379             return (boolean) substitutableInvoker(type).invoke(a, b);
380         } catch (Error|RuntimeException e) {
381             if (VERBOSE) e.printStackTrace();
382             throw e;
383         } catch (Throwable e) {
384             if (VERBOSE) e.printStackTrace();
385             throw new InternalError(e);
386         }
387     }
388 
389     /**
390      * Produces a method handle which tests if two arguments are
391      * {@linkplain #isSubstitutable(Object, Object) substitutable}.
392      *
393      * <ul>
394      * <li>If {@code T} is a non-floating point primitive type, this method
395      *     returns a method handle testing the two arguments are the same value,
396      *     i.e. {@code a == b}.
397      * <li>If {@code T} is {@code float} or {@code double}, this method
398      *     returns a method handle representing {@link Float#equals(Object)} or
399      *     {@link Double#equals(Object)} respectively.
400      * <li>If {@code T} is a reference type that is not {@code Object} and not an
401      *     interface, this method returns a method handle testing
402      *     the two arguments are the same reference, i.e. {@code a == b}.
403      * <li>If {@code T} is a value type, this method returns
404      *     a method handle that returns {@code true} if
405      *     for all fields {@code f} declared in {@code T}, where {@code U} is
406      *     the type of {@code f}, if {@code a.f} and {@code b.f} are substitutable
407      *     with respect to {@code U}.
408      * <li>If {@code T} is an interface or {@code Object}, and
409      *     {@code a} and {@code b} are of the same value class {@code V},
410      *     this method returns a method handle that returns {@code true} if
411      *     {@code a} and {@code b} are substitutable with respect to {@code V}.
412      * </ul>
413      *
414      * @param type class type
415      * @param <T> type
416      * @return a method handle for substitutability test
417      */
418     private static <T> MethodHandle substitutableInvoker(Class<T> type) {
419         if (type.isPrimitive())
420             return MethodHandleBuilder.primitiveEquals(type);
421 
422         if (PrimitiveClass.isPrimitiveValueType(type) ||
423                 (type.isValue() && !PrimitiveClass.isPrimitiveClass(type))) {
424             return SUBST_TEST_METHOD_HANDLES.get(type);
425         }
426         return MethodHandleBuilder.referenceTypeEquals(type);
427     }
428 
429     // store the method handle for value types in ClassValue
430     private static ClassValue<MethodHandle> SUBST_TEST_METHOD_HANDLES = new ClassValue<>() {
431         @Override protected MethodHandle computeValue(Class<?> type) {
432             return MethodHandleBuilder.primitiveTypeEquals(type);
433         }
434     };
435 
436     /**
437      * Invoke the bootstrap methods hashCode for the given primitive class object.
438      * @param o the instance to hash.
439      * @return the hash code of the given primitive class object.
440      */
441     private static int primitiveObjectHashCode(Object o) {
442         Class<?> c = o.getClass();
443         try {
444             // Note: javac disallows user to call super.hashCode if user implemented
445             // risk for recursion for experts crafting byte-code
446             if (!c.isValue())
447                 throw new InternalError("must be value or primitive class: " + c.getName());
448             Class<?> type = PrimitiveClass.isPrimitiveClass(c) ? PrimitiveClass.asValueType(c) : c;
449             return (int) HASHCODE_METHOD_HANDLES.get(type).invoke(o);
450         } catch (Error|RuntimeException e) {
451             throw e;
452         } catch (Throwable e) {
453             if (VERBOSE) e.printStackTrace();
454             throw new InternalError(e);
455         }
456     }
457 
458     private static ClassValue<MethodHandle> HASHCODE_METHOD_HANDLES = new ClassValue<>() {
459         @Override protected MethodHandle computeValue(Class<?> type) {
460             return MethodHandleBuilder.primitiveTypeHashCode(type);
461         }
462     };
463 
464     private static final Comparator<MethodHandle> TYPE_SORTER = (mh1, mh2) -> {
465         // sort the getters with the return type
466         Class<?> t1 = mh1.type().returnType();
467         Class<?> t2 = mh2.type().returnType();
468         if (t1.isPrimitive()) {
469             if (!t2.isPrimitive()) {
470                 return 1;
471             }
472         } else {
473             if (t2.isPrimitive()) {
474                 return -1;
475             }
476         }
477         return -1;
478     };
479 }