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