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.unreflectGetter(f);
 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.isValueType();
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_PRIMITIVE_CLASS.asType(mt),
140                                                accumulator,
141                                                instanceFalse));
142         }
143 
144         static MethodHandle primitiveTypeHashCode(Class<?> type) {
145             assert type.isValueType();
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().isPrimitiveClass() ? 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 && isSamePrimitiveClass(a, b);
188             try {
189                 Class<?> type = a.getClass().asValueType();
190                 return (boolean) substitutableInvoker(type).invoke(type.cast(a), type.cast(b));
191             } catch (Error|RuntimeException e) {
192                 throw e;
193             } catch (Throwable e) {
194                 throw new InternalError(e);
195             }
196         }
197 
198         private static boolean isNull(Object a, Object b) {
199             // avoid acmp that will call isSubstitutable
200             if (a != null) return false;
201             if (b != null) return false;
202             return true;
203         }
204 
205         /*
206          * Returns true if the given objects are of the same primitive class.
207          *
208          * Two objects are of the same primitive class iff:
209          * 1. a != null and b != null
210          * 2. the declaring class of a and b is the same primitive class
211          */
212         private static boolean isSamePrimitiveClass(Object a, Object b) {
213             if (a == null || b == null) return false;
214 
215             return a.getClass().isPrimitiveClass() && a.getClass() == b.getClass();
216         }
217 
218         private static int hashCombiner(int accumulator, int value) {
219             return accumulator * 31 + value;
220         }
221 
222         private static int computeHashCode(MethodHandle[] hashers, int v, int i, Object o) {
223             try {
224                 int hc = (int)hashers[i].invoke(o);
225                 return hashCombiner(v, hc);
226             } catch (Error|RuntimeException e) {
227                 throw e;
228             } catch (Throwable e) {
229                 throw new InternalError(e);
230             }
231         }
232 
233         private static final MethodHandle FALSE = constant(boolean.class, false);
234         private static final MethodHandle TRUE = constant(boolean.class, true);
235         private static final MethodHandle OBJECT_EQUALS = findStatic("eq", methodType(boolean.class, Object.class, Object.class));
236         private static final MethodHandle IS_SAME_PRIMITIVE_CLASS =
237             findStatic("isSamePrimitiveClass", methodType(boolean.class, Object.class, Object.class));
238         private static final MethodHandle IS_NULL =
239             findStatic("isNull", methodType(boolean.class, Object.class, Object.class));
240         private static final MethodHandle HASH_COMBINER =
241             findStatic("hashCombiner", methodType(int.class, int.class, int.class));
242         private static final MethodHandle COMPUTE_HASH =
243             findStatic("computeHashCode", methodType(int.class, MethodHandle[].class, int.class, int.class, Object.class));
244         private static final MethodHandle[] HASHCODE = initHashCode();
245 
246         private static MethodHandle[] initHashCode() {
247             MethodHandle[] mhs = new MethodHandle[Wrapper.COUNT];
248             for (Wrapper wrapper : Wrapper.values()) {
249                 if (wrapper == Wrapper.VOID) continue;
250                 Class<?> cls = wrapper == Wrapper.OBJECT ? Objects.class : wrapper.wrapperType();
251                 mhs[wrapper.ordinal()] = findStatic(cls, "hashCode",
252                                                     methodType(int.class, wrapper.primitiveType()));
253             }
254             return mhs;
255         }
256 
257         private static MethodHandle findStatic(String name, MethodType methodType) {
258             return findStatic(MethodHandleBuilder.class, name, methodType);
259         }
260         private static MethodHandle findStatic(Class<?> cls, String name, MethodType methodType) {
261             try {
262                 return JLIA.findStatic(cls, name, methodType);
263             } catch (NoSuchMethodException|IllegalAccessException e) {
264                 throw newLinkageError(e);
265             }
266         }
267 
268         /**
269          * A "salt" value used for this internal hashcode implementation that
270          * needs to vary sufficiently from one run to the next so that
271          * the default hashcode for value types will vary between JVM runs.
272          */
273         static final int SALT;
274         static {
275             long nt = System.nanoTime();
276             int value = (int)((nt >>> 32) ^ nt);
277             SALT = GetIntegerAction.privilegedGetProperty("value.bsm.salt", value);
278         }
279     }
280 
281     private static LinkageError newLinkageError(Throwable e) {
282         return (LinkageError) new LinkageError().initCause(e);
283     }
284 
285     /**
286      * Returns {@code true} if the arguments are <em>substitutable</em> to each
287      * other and {@code false} otherwise.
288      * <em>Substitutability</em> means that they cannot be distinguished from
289      * each other in any data-dependent way, meaning that it is safe to substitute
290      * one for the other.
291      *
292      * <ul>
293      * <li>If {@code a} and {@code b} are both {@code null}, this method returns
294      *     {@code true}.
295      * <li>If {@code a} and {@code b} are both value instances of the same class
296      *     {@code V}, this method returns {@code true} if, for all fields {@code f}
297      *      declared in {@code V}, {@code a.f} and {@code b.f} are substitutable.
298      * <li>If {@code a} and {@code b} are both primitives of the same type,
299      *     this method returns {@code a == b} with the following exception:
300      *     <ul>
301      *     <li> If {@code a} and {@code b} both represent {@code NaN},
302      *          this method returns {@code true}, even though {@code NaN == NaN}
303      *          has the value {@code false}.
304      *     <li> If {@code a} is floating point positive zero while {@code b} is
305      *          floating point negative zero, or vice versa, this method
306      *          returns {@code false}, even though {@code +0.0 == -0.0} has
307      *          the value {@code true}.
308      *     </ul>
309      * <li>If {@code a} and {@code b} are both instances of the same reference type,
310      *     this method returns {@code a == b}.
311      * <li>Otherwise this method returns {@code false}.
312      * </ul>
313      *
314      * <p>For example,
315      * <pre>{@code interface Number { ... }
316      * // ordinary reference class
317      * class IntNumber implements Number { ... }
318      * // value class
319      * value class IntValue implements Number {
320      *     int i;
321      *     :
322      *     public static IntValue of(int i) {...}     // IntValue::of creates a new value instance
323      * }
324      * // value class with an Object field
325      * value class RefValue {
326      *     Object o;
327      *     :
328      * }
329      *
330      * var val1 = IntValue.of(10);
331      * var val2 = IntValue.of(10);                    // val1 and val2 have the same value
332      * var ref1 = new IntNumber(10);                  // ref1 and ref2 are two reference instances
333      * var ref2 = new IntNumber(10);
334      * assertTrue(isSubstitutable(val1, val2));       // val1 and val2 are both value instances of IntValue
335      * assertFalse(isSubstitutable(ref1, ref2));      // ref1 and ref2 are two reference instances that are not substitutable
336      * assertTrue(isSubstitutable(ref1, ref1));       // a reference instance is substitutable with itself
337      *
338      * var rval1 = RefValue.of(List.of("list"));      // rval1.o and rval2.o both contain a list of one-single element "list"
339      * var rval2 = RefValue.of(List.of("list");
340      * var rval3 = RefValue.of(rval1.o);
341      *
342      * assertFalse(isSubstitutable(rval1, rval2));    // rval1.o and rval2.o are two different List instances and hence not substitutable
343      * assertTrue(isSubstitutable(rval1, rval3 ));    // rval1.o and rval3.o are the same reference instance
344      * }</pre>
345      *
346      * @param a an object
347      * @param b an object to be compared with {@code a} for substitutability
348      * @return {@code true} if the arguments are substitutable to each other;
349      *         {@code false} otherwise.
350      * @param <T> type
351      * @see Float#equals(Object)
352      * @see Double#equals(Object)
353      */
354     private static <T> boolean isSubstitutable(T a, Object b) {
355         if (VERBOSE) {
356             System.out.println("substitutable " + a + " vs " + b);
357         }
358 
359         // Called directly from the VM.
360         //
361         // DO NOT use "==" or "!=" on args "a" and "b", with this code or any of
362         // its callees. Could be inside of if_acmp<eq|ne> bytecode implementation.
363 
364         if (a == null && b == null) return true;
365         if (a == null || b == null) return false;
366         if (a.getClass() != b.getClass()) return false;
367 
368         try {
369             Class<?> type = a.getClass();
370             if (type.isPrimitiveClass()) {
371                 type = type.asValueType();
372             }
373             return (boolean) substitutableInvoker(type).invoke(a, b);
374         } catch (Error|RuntimeException e) {
375             if (VERBOSE) e.printStackTrace();
376             throw e;
377         } catch (Throwable e) {
378             if (VERBOSE) e.printStackTrace();
379             throw new InternalError(e);
380         }
381     }
382 
383     /**
384      * Produces a method handle which tests if two arguments are
385      * {@linkplain #isSubstitutable(Object, Object) substitutable}.
386      *
387      * <ul>
388      * <li>If {@code T} is a non-floating point primitive type, this method
389      *     returns a method handle testing the two arguments are the same value,
390      *     i.e. {@code a == b}.
391      * <li>If {@code T} is {@code float} or {@code double}, this method
392      *     returns a method handle representing {@link Float#equals(Object)} or
393      *     {@link Double#equals(Object)} respectively.
394      * <li>If {@code T} is a reference type that is not {@code Object} and not an
395      *     interface, this method returns a method handle testing
396      *     the two arguments are the same reference, i.e. {@code a == b}.
397      * <li>If {@code T} is a value type, this method returns
398      *     a method handle that returns {@code true} if
399      *     for all fields {@code f} declared in {@code T}, where {@code U} is
400      *     the type of {@code f}, if {@code a.f} and {@code b.f} are substitutable
401      *     with respect to {@code U}.
402      * <li>If {@code T} is an interface or {@code Object}, and
403      *     {@code a} and {@code b} are of the same value class {@code V},
404      *     this method returns a method handle that returns {@code true} if
405      *     {@code a} and {@code b} are substitutable with respect to {@code V}.
406      * </ul>
407      *
408      * @param type class type
409      * @param <T> type
410      * @return a method handle for substitutability test
411      */
412     private static <T> MethodHandle substitutableInvoker(Class<T> type) {
413         if (type.isPrimitive())
414             return MethodHandleBuilder.primitiveEquals(type);
415 
416         if (type.isValueType())
417             return SUBST_TEST_METHOD_HANDLES.get(type);
418 
419         return MethodHandleBuilder.referenceTypeEquals(type);
420     }
421 
422     // store the method handle for value types in ClassValue
423     private static ClassValue<MethodHandle> SUBST_TEST_METHOD_HANDLES = new ClassValue<>() {
424         @Override protected MethodHandle computeValue(Class<?> type) {
425             return MethodHandleBuilder.primitiveTypeEquals(type.asValueType());
426         }
427     };
428 
429     /**
430      * Invoke the bootstrap methods hashCode for the given primitive class object.
431      * @param o the instance to hash.
432      * @return the hash code of the given primitive class object.
433      */
434     private static int primitiveObjectHashCode(Object o) {
435         try {
436             // Note: javac disallows user to call super.hashCode if user implemented
437             // risk for recursion for experts crafting byte-code
438             if (!o.getClass().isPrimitiveClass())
439                 throw new InternalError("must be primitive type: " + o.getClass().getName());
440             Class<?> type = o.getClass().asValueType();
441             return (int) HASHCODE_METHOD_HANDLES.get(type).invoke(o);
442         } catch (Error|RuntimeException e) {
443             throw e;
444         } catch (Throwable e) {
445             if (VERBOSE) e.printStackTrace();
446             throw new InternalError(e);
447         }
448     }
449 
450     private static ClassValue<MethodHandle> HASHCODE_METHOD_HANDLES = new ClassValue<>() {
451         @Override protected MethodHandle computeValue(Class<?> type) {
452             return MethodHandleBuilder.primitiveTypeHashCode(type.asValueType());
453         }
454     };
455 
456     private static final Comparator<MethodHandle> TYPE_SORTER = (mh1, mh2) -> {
457         // sort the getters with the return type
458         Class<?> t1 = mh1.type().returnType();
459         Class<?> t2 = mh2.type().returnType();
460         if (t1.isPrimitive()) {
461             if (!t2.isPrimitive()) {
462                 return 1;
463             }
464         } else {
465             if (t2.isPrimitive()) {
466                 return -1;
467             }
468         }
469         return -1;
470     };
471 }