1 /*
   2  * Copyright (c) 2015, 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.
   8  *
   9  * This code is distributed in the hope that it will be useful, but WITHOUT
  10  * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
  11  * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
  12  * version 2 for more details (a copy is included in the LICENSE file that
  13  * accompanied this code).
  14  *
  15  * You should have received a copy of the GNU General Public License version
  16  * 2 along with this work; if not, write to the Free Software Foundation,
  17  * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
  18  *
  19  * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
  20  * or visit www.oracle.com if you need additional information or have any
  21  * questions.
  22  */
  23 
  24 /*
  25  * @test
  26  * @bug 8033148
  27  * @summary tests for array equals and compare
  28  * @run testng ArraysEqCmpTest
  29 */
  30 
  31 import org.testng.Assert;
  32 import org.testng.annotations.DataProvider;
  33 import org.testng.annotations.Test;
  34 
  35 import java.lang.invoke.MethodHandle;
  36 import java.lang.invoke.MethodHandles;
  37 import java.lang.invoke.MethodType;
  38 import java.lang.reflect.Array;
  39 import java.util.Arrays;
  40 import java.util.Comparator;
  41 import java.util.HashMap;
  42 import java.util.List;
  43 import java.util.Map;
  44 import java.util.Objects;
  45 import java.util.function.BiFunction;
  46 import java.util.function.LongFunction;
  47 import java.util.stream.IntStream;
  48 
  49 public class ArraysEqCmpTest {
  50 
  51     // Maximum width in bits
  52     static final int MAX_WIDTH = 512;
  53 
  54     static final Map<Class, Integer> typeToWidth;
  55 
  56     static {
  57         typeToWidth = new HashMap<>();
  58         typeToWidth.put(boolean.class, Byte.SIZE);
  59         typeToWidth.put(byte.class, Byte.SIZE);
  60         typeToWidth.put(short.class, Short.SIZE);
  61         typeToWidth.put(char.class, Character.SIZE);
  62         typeToWidth.put(int.class, Integer.SIZE);
  63         typeToWidth.put(long.class, Long.SIZE);
  64         typeToWidth.put(float.class, Float.SIZE);
  65         typeToWidth.put(double.class, Double.SIZE);
  66         typeToWidth.put(Object.class, Integer.SIZE); // @@@ 32 or 64?
  67     }
  68 
  69     static int arraySizeFor(Class<?> type) {
  70         type = type.isPrimitive() ? type : Object.class;
  71         return 4 * MAX_WIDTH / typeToWidth.get(type);
  72     }
  73 
  74     static abstract class ArrayType<T> {
  75         final Class<?> arrayType;
  76         final Class<?> componentType;
  77         final boolean unsigned;
  78 
  79         final MethodHandle cpy;
  80 
  81         final MethodHandle eq;
  82         final MethodHandle eqr;
  83         final MethodHandle cmp;
  84         final MethodHandle cmpr;
  85         final MethodHandle mm;
  86         final MethodHandle mmr;
  87 
  88         final MethodHandle getter;
  89 
  90         final MethodHandle toString;
  91 
  92         public ArrayType(Class<T> arrayType) {
  93             this(arrayType, false);
  94         }
  95 
  96         public ArrayType(Class<T> arrayType, boolean unsigned) {
  97             this.arrayType = arrayType;
  98             this.componentType = arrayType.getComponentType();
  99             this.unsigned = unsigned;
 100 
 101             try {
 102                 MethodHandles.Lookup l = MethodHandles.lookup();
 103 
 104                 getter = MethodHandles.arrayElementGetter(arrayType);
 105 
 106                 if (componentType.isPrimitive()) {
 107                     cpy = l.findStatic(Arrays.class, "copyOfRange",
 108                                        MethodType.methodType(arrayType, arrayType, int.class, int.class));
 109 
 110                     MethodType eqt = MethodType.methodType(
 111                             boolean.class, arrayType, arrayType);
 112                     MethodType eqrt = MethodType.methodType(
 113                             boolean.class, arrayType, int.class, int.class, arrayType, int.class, int.class);
 114 
 115                     eq = l.findStatic(Arrays.class, "equals", eqt);
 116                     eqr = l.findStatic(Arrays.class, "equals", eqrt);
 117 
 118                     String compareName = unsigned ? "compareUnsigned" : "compare";
 119                     cmp = l.findStatic(Arrays.class, compareName,
 120                                        eqt.changeReturnType(int.class));
 121                     cmpr = l.findStatic(Arrays.class, compareName,
 122                                         eqrt.changeReturnType(int.class));
 123 
 124                     mm = l.findStatic(Arrays.class, "mismatch",
 125                                        eqt.changeReturnType(int.class));
 126                     mmr = l.findStatic(Arrays.class, "mismatch",
 127                                        eqrt.changeReturnType(int.class));
 128 
 129                     toString = l.findStatic(Arrays.class, "toString",
 130                                             MethodType.methodType(String.class, arrayType));
 131                 }
 132                 else {
 133                     cpy = l.findStatic(Arrays.class, "copyOfRange",
 134                                        MethodType.methodType(Object[].class, Object[].class, int.class, int.class));
 135 
 136                     MethodType eqt = MethodType.methodType(
 137                             boolean.class, Object[].class, Object[].class);
 138                     MethodType eqrt = MethodType.methodType(
 139                             boolean.class, Object[].class, int.class, int.class, Object[].class, int.class, int.class);
 140 
 141                     eq = l.findStatic(Arrays.class, "equals", eqt);
 142                     eqr = l.findStatic(Arrays.class, "equals", eqrt);
 143 
 144                     MethodType cmpt = MethodType.methodType(
 145                             int.class, Comparable[].class, Comparable[].class);
 146                     MethodType cmprt = MethodType.methodType(
 147                             int.class, Comparable[].class, int.class, int.class, Comparable[].class, int.class, int.class);
 148 
 149                     cmp = l.findStatic(Arrays.class, "compare", cmpt);
 150                     cmpr = l.findStatic(Arrays.class, "compare", cmprt);
 151 
 152                     mm = l.findStatic(Arrays.class, "mismatch",
 153                                       eqt.changeReturnType(int.class));
 154                     mmr = l.findStatic(Arrays.class, "mismatch",
 155                                        eqrt.changeReturnType(int.class));
 156 
 157                     toString = l.findStatic(Arrays.class, "toString",
 158                                             MethodType.methodType(String.class, Object[].class));
 159                 }
 160 
 161             }
 162             catch (Exception e) {
 163                 throw new Error(e);
 164             }
 165         }
 166 
 167         @Override
 168         public String toString() {
 169             String s = arrayType.getCanonicalName();
 170             return unsigned ? "unsigned " + s : s;
 171         }
 172 
 173         Object construct(int length) {
 174             return Array.newInstance(componentType, length);
 175         }
 176 
 177         Object copyOf(Object a) {
 178             return copyOf(a, 0, Array.getLength(a));
 179         }
 180 
 181         Object copyOf(Object a, int from, int to) {
 182             try {
 183                 return (Object) cpy.invoke(a, from, to);
 184             }
 185             catch (RuntimeException | Error e) {
 186                 throw e;
 187             }
 188             catch (Throwable t) {
 189                 throw new Error(t);
 190             }
 191         }
 192 
 193         Object get(Object a, int i) {
 194             try {
 195                 return (Object) getter.invoke(a, i);
 196             }
 197             catch (RuntimeException | Error e) {
 198                 throw e;
 199             }
 200             catch (Throwable t) {
 201                 throw new Error(t);
 202             }
 203         }
 204 
 205         abstract void set(Object a, int i, Object v);
 206 
 207         boolean equals(Object a, Object b) {
 208             try {
 209                 return (boolean) eq.invoke(a, b);
 210             }
 211             catch (RuntimeException | Error e) {
 212                 throw e;
 213             }
 214             catch (Throwable t) {
 215                 throw new Error(t);
 216             }
 217         }
 218 
 219         boolean equals(Object a, int aFromIndex, int aToIndex,
 220                        Object b, int bFromIndex, int bToIndex) {
 221             try {
 222                 return (boolean) eqr.invoke(a, aFromIndex, aToIndex, b, bFromIndex, bToIndex);
 223             }
 224             catch (RuntimeException | Error e) {
 225                 throw e;
 226             }
 227             catch (Throwable t) {
 228                 throw new Error(t);
 229             }
 230         }
 231 
 232         int compare(Object a, Object b) {
 233             try {
 234                 return (int) cmp.invoke(a, b);
 235             }
 236             catch (RuntimeException | Error e) {
 237                 throw e;
 238             }
 239             catch (Throwable t) {
 240                 throw new Error(t);
 241             }
 242         }
 243 
 244         int compare(Object a, int aFromIndex, int aToIndex,
 245                     Object b, int bFromIndex, int bToIndex) {
 246             try {
 247                 return (int) cmpr.invoke(a, aFromIndex, aToIndex, b, bFromIndex, bToIndex);
 248             }
 249             catch (RuntimeException | Error e) {
 250                 throw e;
 251             }
 252             catch (Throwable t) {
 253                 throw new Error(t);
 254             }
 255         }
 256 
 257         int mismatch(Object a, Object b) {
 258             try {
 259                 return (int) mm.invoke(a, b);
 260             }
 261             catch (RuntimeException | Error e) {
 262                 throw e;
 263             }
 264             catch (Throwable t) {
 265                 throw new Error(t);
 266             }
 267         }
 268 
 269         int mismatch(Object a, int aFromIndex, int aToIndex,
 270                      Object b, int bFromIndex, int bToIndex) {
 271             try {
 272                 return (int) mmr.invoke(a, aFromIndex, aToIndex, b, bFromIndex, bToIndex);
 273             }
 274             catch (RuntimeException | Error e) {
 275                 throw e;
 276             }
 277             catch (Throwable t) {
 278                 throw new Error(t);
 279             }
 280         }
 281 
 282         String toString(Object a) {
 283             try {
 284                 return (String) toString.invoke(a);
 285             }
 286             catch (RuntimeException | Error e) {
 287                 throw e;
 288             }
 289             catch (Throwable t) {
 290                 throw new Error(t);
 291             }
 292         }
 293 
 294         static class BoxedIntegers extends ArrayType<Integer[]> {
 295             public BoxedIntegers() {
 296                 super(Integer[].class);
 297             }
 298 
 299             @Override
 300             void set(Object a, int i, Object v) {
 301                 // Ensure unique reference
 302                 ((Integer[]) a)[i] = v != null ? new Integer((Integer) v) : null;
 303             }
 304         }
 305 
 306         static class BoxedIntegersWithReverseComparator extends BoxedIntegers {
 307             final Comparator<Integer> c = (a, b) -> {
 308                 // Nulls sort after non-nulls
 309                 if (a == null || b == null)
 310                     return a == null ? b == null ? 0 : 1 : -1;
 311 
 312                 return Integer.compare(b, a);
 313             };
 314 
 315             final MethodHandle cmpc;
 316             final MethodHandle cmpcr;
 317             final MethodHandle mismatchc;
 318             final MethodHandle mismatchcr;
 319 
 320             public BoxedIntegersWithReverseComparator() {
 321                 try {
 322                     MethodHandles.Lookup l = MethodHandles.lookup();
 323 
 324                     MethodType cmpt = MethodType.methodType(
 325                             int.class, Object[].class, Object[].class, Comparator.class);
 326                     MethodType cmprt = MethodType.methodType(
 327                             int.class, Object[].class, int.class, int.class,
 328                             Object[].class, int.class, int.class, Comparator.class);
 329 
 330                     cmpc = l.findStatic(Arrays.class, "compare", cmpt);
 331                     cmpcr = l.findStatic(Arrays.class, "compare", cmprt);
 332                     mismatchc = l.findStatic(Arrays.class, "mismatch", cmpt);
 333                     mismatchcr = l.findStatic(Arrays.class, "mismatch", cmprt);
 334                 }
 335                 catch (Exception e) {
 336                     throw new Error(e);
 337                 }
 338             }
 339 
 340             @Override
 341             int compare(Object a, Object b) {
 342                 try {
 343                     return (int) cmpc.invoke(a, b, c);
 344                 }
 345                 catch (RuntimeException | Error e) {
 346                     throw e;
 347                 }
 348                 catch (Throwable t) {
 349                     throw new Error(t);
 350                 }
 351             }
 352 
 353             @Override
 354             int compare(Object a, int aFromIndex, int aToIndex,
 355                         Object b, int bFromIndex, int bToIndex) {
 356                 try {
 357                     return (int) cmpcr.invoke(a, aFromIndex, aToIndex, b, bFromIndex, bToIndex, c);
 358                 }
 359                 catch (RuntimeException | Error e) {
 360                     throw e;
 361                 }
 362                 catch (Throwable t) {
 363                     throw new Error(t);
 364                 }
 365             }
 366 
 367             @Override
 368             int mismatch(Object a, Object b) {
 369                 try {
 370                     return (int) mismatchc.invoke(a, b, c);
 371                 }
 372                 catch (RuntimeException | Error e) {
 373                     throw e;
 374                 }
 375                 catch (Throwable t) {
 376                     throw new Error(t);
 377                 }
 378             }
 379 
 380             @Override
 381             int mismatch(Object a, int aFromIndex, int aToIndex,
 382                          Object b, int bFromIndex, int bToIndex) {
 383                 try {
 384                     return (int) mismatchcr.invoke(a, aFromIndex, aToIndex, b, bFromIndex, bToIndex, c);
 385                 }
 386                 catch (RuntimeException | Error e) {
 387                     throw e;
 388                 }
 389                 catch (Throwable t) {
 390                     throw new Error(t);
 391                 }
 392             }
 393 
 394             @Override
 395             public String toString() {
 396                 return arrayType.getCanonicalName() + " with Comparator";
 397             }
 398         }
 399 
 400         static class Booleans extends ArrayType<boolean[]> {
 401             public Booleans() {
 402                 super(boolean[].class);
 403             }
 404 
 405             @Override
 406             void set(Object a, int i, Object v) {
 407                 boolean pv;
 408                 if (v instanceof Boolean) {
 409                     pv = (Boolean) v;
 410                 }
 411                 else if (v instanceof Integer) {
 412                     pv = ((Integer) v) >= 0;
 413                 }
 414                 else throw new IllegalStateException();
 415 
 416                 ((boolean[]) a)[i] = pv;
 417             }
 418         }
 419 
 420         static class Bytes extends ArrayType<byte[]> {
 421             public Bytes(boolean unsigned) {
 422                 super(byte[].class, unsigned);
 423             }
 424 
 425             @Override
 426             void set(Object a, int i, Object v) {
 427                 byte pv;
 428                 if (v instanceof Byte) {
 429                     pv = (Byte) v;
 430                 }
 431                 else if (v instanceof Integer) {
 432                     pv = ((Integer) v).byteValue();
 433                 }
 434                 else throw new IllegalStateException();
 435 
 436                 ((byte[]) a)[i] = pv;
 437             }
 438         }
 439 
 440         static class Characters extends ArrayType<char[]> {
 441             public Characters() {
 442                 super(char[].class);
 443             }
 444 
 445             @Override
 446             void set(Object a, int i, Object v) {
 447                 char pv;
 448                 if (v instanceof Character) {
 449                     pv = (Character) v;
 450                 }
 451                 else if (v instanceof Integer) {
 452                     pv = (char) ((Integer) v).intValue();
 453                 }
 454                 else throw new IllegalStateException();
 455 
 456                 ((char[]) a)[i] = pv;
 457             }
 458         }
 459 
 460         static class Shorts extends ArrayType<short[]> {
 461             public Shorts(boolean unsigned) {
 462                 super(short[].class, unsigned);
 463             }
 464 
 465             @Override
 466             void set(Object a, int i, Object v) {
 467                 short pv;
 468                 if (v instanceof Short) {
 469                     pv = (Short) v;
 470                 }
 471                 else if (v instanceof Integer) {
 472                     pv = ((Integer) v).shortValue();
 473                 }
 474                 else throw new IllegalStateException();
 475 
 476                 ((short[]) a)[i] = pv;
 477             }
 478         }
 479 
 480         static class Integers extends ArrayType<int[]> {
 481             public Integers(boolean unsigned) {
 482                 super(int[].class, unsigned);
 483             }
 484 
 485             @Override
 486             void set(Object a, int i, Object v) {
 487                 int pv;
 488                 if (v instanceof Integer) {
 489                     pv = ((Integer) v).shortValue();
 490                 }
 491                 else throw new IllegalStateException();
 492 
 493                 ((int[]) a)[i] = pv;
 494             }
 495         }
 496 
 497         static class Longs extends ArrayType<long[]> {
 498             public Longs(boolean unsigned) {
 499                 super(long[].class, unsigned);
 500             }
 501 
 502             @Override
 503             void set(Object a, int i, Object v) {
 504                 long pv;
 505                 if (v instanceof Long) {
 506                     pv = (Long) v;
 507                 }
 508                 else if (v instanceof Integer) {
 509                     pv = ((Integer) v).longValue();
 510                 }
 511                 else throw new IllegalStateException();
 512 
 513                 ((long[]) a)[i] = pv;
 514             }
 515         }
 516 
 517         static class Floats extends ArrayType<float[]> {
 518             public Floats() {
 519                 super(float[].class);
 520             }
 521 
 522             @Override
 523             void set(Object a, int i, Object v) {
 524                 float pv;
 525                 if (v instanceof Float) {
 526                     pv = (Float) v;
 527                 }
 528                 else if (v instanceof Integer) {
 529                     pv = ((Integer) v).floatValue();
 530                 }
 531                 else throw new IllegalStateException();
 532 
 533                 ((float[]) a)[i] = pv;
 534             }
 535         }
 536 
 537         static class Doubles extends ArrayType<double[]> {
 538             public Doubles() {
 539                 super(double[].class);
 540             }
 541 
 542             @Override
 543             void set(Object a, int i, Object v) {
 544                 double pv;
 545                 if (v instanceof Double) {
 546                     pv = (Double) v;
 547                 }
 548                 else if (v instanceof Integer) {
 549                     pv = ((Integer) v).doubleValue();
 550                 }
 551                 else throw new IllegalStateException();
 552 
 553                 ((double[]) a)[i] = pv;
 554             }
 555         }
 556     }
 557 
 558     static Object[][] arrayTypes;
 559 
 560     @DataProvider
 561     public static Object[][] arrayTypesProvider() {
 562         if (arrayTypes == null) {
 563             arrayTypes = new Object[][]{
 564                     new Object[]{new ArrayType.BoxedIntegers()},
 565                     new Object[]{new ArrayType.BoxedIntegersWithReverseComparator()},
 566                     new Object[]{new ArrayType.Booleans()},
 567                     new Object[]{new ArrayType.Bytes(false)},
 568                     new Object[]{new ArrayType.Bytes(true)},
 569                     new Object[]{new ArrayType.Characters()},
 570                     new Object[]{new ArrayType.Shorts(false)},
 571                     new Object[]{new ArrayType.Shorts(true)},
 572                     new Object[]{new ArrayType.Integers(false)},
 573                     new Object[]{new ArrayType.Integers(true)},
 574                     new Object[]{new ArrayType.Longs(false)},
 575                     new Object[]{new ArrayType.Longs(true)},
 576                     new Object[]{new ArrayType.Floats()},
 577                     new Object[]{new ArrayType.Doubles()},
 578             };
 579         }
 580         return arrayTypes;
 581     }
 582 
 583     static Object[][] floatArrayTypes;
 584 
 585     @DataProvider
 586     public static Object[][] floatArrayTypesProvider() {
 587         if (floatArrayTypes == null) {
 588             LongFunction<Object> bTof = rb -> Float.intBitsToFloat((int) rb);
 589             LongFunction<Object> bToD = Double::longBitsToDouble;
 590 
 591             floatArrayTypes = new Object[][]{
 592                     new Object[]{new ArrayType.Floats(), 0x7fc00000L, 0x7f800001L, bTof},
 593                     new Object[]{new ArrayType.Doubles(), 0x7ff8000000000000L, 0x7ff0000000000001L, bToD},
 594             };
 595         }
 596         return floatArrayTypes;
 597     }
 598 
 599     static Object[][] objectArrayTypes;
 600 
 601     @DataProvider
 602     public static Object[][] objectArrayTypesProvider() {
 603         if (objectArrayTypes == null) {
 604             LongFunction<Object> bTof = rb -> Float.intBitsToFloat((int) rb);
 605             LongFunction<Object> bToD = Double::longBitsToDouble;
 606 
 607             objectArrayTypes = new Object[][]{
 608                     new Object[]{new ArrayType.BoxedIntegers()},
 609                     new Object[]{new ArrayType.BoxedIntegersWithReverseComparator()},
 610             };
 611         }
 612         return objectArrayTypes;
 613     }
 614 
 615 
 616     static Object[][] signedUnsignedArrayTypes;
 617 
 618     @DataProvider
 619     public static Object[][] signedUnsignedArrayTypes() {
 620         if (signedUnsignedArrayTypes == null) {
 621             signedUnsignedArrayTypes = new Object[][]{
 622                     new Object[]{new ArrayType.Bytes(false), new ArrayType.Bytes(true)},
 623                     new Object[]{new ArrayType.Shorts(false), new ArrayType.Shorts(true)},
 624                     new Object[]{new ArrayType.Integers(false), new ArrayType.Integers(true)},
 625                     new Object[]{new ArrayType.Longs(false), new ArrayType.Longs(true)},
 626             };
 627         }
 628         return signedUnsignedArrayTypes;
 629     }
 630 
 631     // Equality and comparison tests
 632 
 633     @Test(dataProvider = "arrayTypesProvider")
 634     public void testArray(ArrayType<?> arrayType) {
 635         BiFunction<ArrayType<?>, Integer, Object> constructor = (at, s) -> {
 636             Object a = at.construct(s);
 637             for (int x = 0; x < s; x++) {
 638                 at.set(a, x, x % 8);
 639             }
 640             return a;
 641         };
 642 
 643         BiFunction<ArrayType<?>, Object, Object> cloner = (at, a) ->
 644                 constructor.apply(at, Array.getLength(a));
 645 
 646         testArrayType(arrayType, constructor, cloner);
 647     }
 648 
 649     @Test(dataProvider = "floatArrayTypesProvider")
 650     public void testPrimitiveFloatArray(
 651             ArrayType<?> arrayType,
 652             long canonicalNanRawBits, long nonCanonicalNanRawBits,
 653             LongFunction<Object> bitsToFloat) {
 654         Object canonicalNan = bitsToFloat.apply(canonicalNanRawBits);
 655         // If conversion is a signalling NaN it may be subject to conversion to a
 656         // quiet NaN on some processors, even if a copy is performed
 657         // The tests assume that if conversion occurs it does not convert to the
 658         // canonical NaN
 659         Object nonCanonicalNan = bitsToFloat.apply(nonCanonicalNanRawBits);
 660 
 661         BiFunction<ArrayType<?>, Integer, Object> canonicalNaNs = (at, s) -> {
 662             Object a = at.construct(s);
 663             for (int x = 0; x < s; x++) {
 664                 at.set(a, x, canonicalNan);
 665             }
 666             return a;
 667         };
 668 
 669         BiFunction<ArrayType<?>, Object, Object> nonCanonicalNaNs = (at, a) -> {
 670             int s = Array.getLength(a);
 671             Object ac = at.construct(s);
 672             for (int x = 0; x < s; x++) {
 673                 at.set(ac, x, nonCanonicalNan);
 674             }
 675             return ac;
 676         };
 677 
 678         BiFunction<ArrayType<?>, Object, Object> halfNonCanonicalNaNs = (at, a) -> {
 679             int s = Array.getLength(a);
 680             Object ac = at.construct(s);
 681             for (int x = 0; x < s / 2; x++) {
 682                 at.set(ac, x, nonCanonicalNan);
 683             }
 684             for (int x = s / 2; x < s; x++) {
 685                 at.set(ac, x, 1);
 686             }
 687             return ac;
 688         };
 689 
 690         testArrayType(arrayType, canonicalNaNs, nonCanonicalNaNs);
 691         testArrayType(arrayType, canonicalNaNs, halfNonCanonicalNaNs);
 692     }
 693 
 694     @Test(dataProvider = "objectArrayTypesProvider")
 695     public void testNullElementsInObjectArray(ArrayType<?> arrayType) {
 696         BiFunction<ArrayType<?>, Object, Object> cloner = ArrayType::copyOf;
 697 
 698         // All nulls
 699         testArrayType(arrayType,
 700                       (at, s) -> {
 701                           Object a = at.construct(s);
 702                           for (int x = 0; x < s; x++) {
 703                               at.set(a, x, null);
 704                           }
 705                           return a;
 706                       },
 707                       cloner);
 708 
 709 
 710         // Some nulls
 711         testArrayType(arrayType,
 712                       (at, s) -> {
 713                           Object a = at.construct(s);
 714                           for (int x = 0; x < s; x++) {
 715                               int v = x % 8;
 716                               at.set(a, x, v == 0 ? null : v);
 717                           }
 718                           return a;
 719                       },
 720                       cloner);
 721 
 722         Integer[] a = new Integer[]{null, 0};
 723         Integer[] b = new Integer[]{0, 0};
 724         Assert.assertTrue(Arrays.compare(a, b) < 0);
 725         Assert.assertTrue(Arrays.compare(b, a) > 0);
 726     }
 727 
 728     @Test(dataProvider = "objectArrayTypesProvider")
 729     public void testSameRefElementsInObjectArray(ArrayType<?> arrayType) {
 730         BiFunction<ArrayType<?>, Object, Object> cloner = ArrayType::copyOf;
 731 
 732         // One ref
 733         Integer one = 1;
 734         testArrayType(arrayType,
 735                       (at, s) -> {
 736                           Integer[] a = (Integer[]) at.construct(s);
 737                           for (int x = 0; x < s; x++) {
 738                               a[x] = one;
 739                           }
 740                           return a;
 741                       },
 742                       cloner);
 743 
 744         // All ref
 745         testArrayType(arrayType,
 746                       (at, s) -> {
 747                           Integer[] a = (Integer[]) at.construct(s);
 748                           for (int x = 0; x < s; x++) {
 749                               a[x] = Integer.valueOf(s);
 750                           }
 751                           return a;
 752                       },
 753                       cloner);
 754 
 755         // Some same ref
 756         testArrayType(arrayType,
 757                       (at, s) -> {
 758                           Integer[] a = (Integer[]) at.construct(s);
 759                           for (int x = 0; x < s; x++) {
 760                               int v = x % 8;
 761                               a[x] = v == 1 ? one : new Integer(v);
 762                           }
 763                           return a;
 764                       },
 765                       cloner);
 766     }
 767 
 768     @Test(dataProvider = "signedUnsignedArrayTypes")
 769     public void testSignedUnsignedArray(ArrayType<?> sat, ArrayType<?> uat) {
 770         BiFunction<ArrayType<?>, Integer, Object> constructor = (at, s) -> {
 771             Object a = at.construct(s);
 772             for (int x = 0; x < s; x++) {
 773                 at.set(a, x, 1);
 774             }
 775             return a;
 776         };
 777 
 778         int n = arraySizeFor(sat.componentType);
 779 
 780         for (int s : ranges(0, n)) {
 781             Object a = constructor.apply(sat, s);
 782 
 783             for (int aFrom : ranges(0, s)) {
 784                 for (int aTo : ranges(aFrom, s)) {
 785                     int aLength = aTo - aFrom;
 786 
 787                     if (aLength > 0) {
 788                         for (int i = aFrom; i < aTo; i++) {
 789                             Object ac = sat.copyOf(a);
 790                             // Create common prefix with a length of i - aFrom
 791                             sat.set(ac, i, -1);
 792 
 793                             int sc = sat.compare(ac, aFrom, aTo, a, aFrom, aTo);
 794                             int uc = uat.compare(ac, aFrom, aTo, a, aFrom, aTo);
 795 
 796                             Assert.assertTrue(sc < 0);
 797                             Assert.assertTrue(uc > 0);
 798                         }
 799                     }
 800                 }
 801             }
 802         }
 803     }
 804 
 805     void testArrayType(ArrayType<?> at,
 806                        BiFunction<ArrayType<?>, Integer, Object> constructor,
 807                        BiFunction<ArrayType<?>, Object, Object> cloner) {
 808         int n = arraySizeFor(at.componentType);
 809 
 810         for (int s : ranges(0, n)) {
 811             Object a = constructor.apply(at, s);
 812             Object b = cloner.apply(at, a);
 813 
 814             for (int aFrom : ranges(0, s)) {
 815                 for (int aTo : ranges(aFrom, s)) {
 816                     int aLength = aTo - aFrom;
 817 
 818                     for (int bFrom : ranges(0, s)) {
 819                         for (int bTo : ranges(bFrom, s)) {
 820                             int bLength = bTo - bFrom;
 821 
 822                             Object anr = at.copyOf(a, aFrom, aTo);
 823                             Object bnr = at.copyOf(b, bFrom, bTo);
 824 
 825                             boolean eq = isEqual(at, a, aFrom, aTo, b, bFrom, bTo);
 826                             Assert.assertEquals(at.equals(a, aFrom, aTo, b, bFrom, bTo), eq);
 827                             Assert.assertEquals(at.equals(b, bFrom, bTo, a, aFrom, aTo), eq);
 828                             Assert.assertEquals(at.equals(anr, bnr), eq);
 829                             Assert.assertEquals(at.equals(bnr, anr), eq);
 830                             if (eq) {
 831                                 Assert.assertEquals(at.compare(a, aFrom, aTo, b, bFrom, bTo), 0);
 832                                 Assert.assertEquals(at.compare(b, bFrom, bTo, a, aFrom, aTo), 0);
 833                                 Assert.assertEquals(at.compare(anr, bnr), 0);
 834                                 Assert.assertEquals(at.compare(bnr, anr), 0);
 835 
 836                                 Assert.assertEquals(at.mismatch(a, aFrom, aTo, b, bFrom, bTo), -1);
 837                                 Assert.assertEquals(at.mismatch(b, bFrom, bTo, a, aFrom, aTo), -1);
 838                                 Assert.assertEquals(at.mismatch(anr, bnr), -1);
 839                                 Assert.assertEquals(at.mismatch(bnr, anr), -1);
 840                             }
 841                             else {
 842                                 int aCb = at.compare(a, aFrom, aTo, b, bFrom, bTo);
 843                                 int bCa = at.compare(b, bFrom, bTo, a, aFrom, aTo);
 844                                 int v = Integer.signum(aCb) * Integer.signum(bCa);
 845                                 Assert.assertTrue(v == -1);
 846 
 847                                 int anrCbnr = at.compare(anr, bnr);
 848                                 int bnrCanr = at.compare(bnr, anr);
 849                                 Assert.assertEquals(anrCbnr, aCb);
 850                                 Assert.assertEquals(bnrCanr, bCa);
 851 
 852 
 853                                 int aMb = at.mismatch(a, aFrom, aTo, b, bFrom, bTo);
 854                                 int bMa = at.mismatch(b, bFrom, bTo, a, aFrom, aTo);
 855                                 int anrMbnr = at.mismatch(anr, bnr);
 856                                 int bnrManr = at.mismatch(bnr, anr);
 857 
 858                                 Assert.assertNotEquals(aMb, -1);
 859                                 Assert.assertEquals(aMb, bMa);
 860                                 Assert.assertNotEquals(anrMbnr, -1);
 861                                 Assert.assertEquals(anrMbnr, bnrManr);
 862                                 Assert.assertEquals(aMb, anrMbnr);
 863                                 Assert.assertEquals(bMa, bnrManr);
 864 
 865                                 // Common or proper prefix
 866                                 Assert.assertTrue(at.equals(a, aFrom, aFrom + aMb, b, bFrom, bFrom + aMb));
 867                                 if (aMb < Math.min(aLength, bLength)) {
 868                                     // Common prefix
 869                                     Assert.assertFalse(isEqual(at, a, aFrom + aMb, b, bFrom + aMb));
 870                                 }
 871                             }
 872                         }
 873                     }
 874 
 875                     if (aLength > 0) {
 876                         for (int i = aFrom; i < aTo; i++) {
 877                             Object ac = at.copyOf(a);
 878                             // Create common prefix with a length of i - aFrom
 879                             at.set(ac, i, -1);
 880 
 881                             Object acnr = at.copyOf(ac, aFrom, aTo);
 882                             Object anr = at.copyOf(a, aFrom, aTo);
 883 
 884                             Assert.assertFalse(at.equals(ac, aFrom, aTo, a, aFrom, aTo));
 885                             Assert.assertFalse(at.equals(acnr, anr));
 886 
 887                             int acCa = at.compare(ac, aFrom, aTo, a, aFrom, aTo);
 888                             int aCac = at.compare(a, aFrom, aTo, ac, aFrom, aTo);
 889                             int v = Integer.signum(acCa) * Integer.signum(aCac);
 890                             Assert.assertTrue(v == -1);
 891 
 892                             int acnrCanr = at.compare(acnr, anr);
 893                             int anrCacnr = at.compare(anr, acnr);
 894                             Assert.assertEquals(acnrCanr, acCa);
 895                             Assert.assertEquals(anrCacnr, aCac);
 896 
 897 
 898                             int acMa = at.mismatch(ac, aFrom, aTo, a, aFrom, aTo);
 899                             int aMac = at.mismatch(a, aFrom, aTo, ac, aFrom, aTo);
 900                             Assert.assertEquals(acMa, aMac);
 901                             Assert.assertEquals(acMa, i - aFrom);
 902 
 903                             int acnrManr = at.mismatch(acnr, anr);
 904                             int anrMacnr = at.mismatch(anr, acnr);
 905                             Assert.assertEquals(acnrManr, anrMacnr);
 906                             Assert.assertEquals(acnrManr, i - aFrom);
 907                         }
 908                     }
 909                 }
 910             }
 911         }
 912     }
 913 
 914     static boolean isEqual(ArrayType<?> at, Object a, int aFromIndex, int aToIndex,
 915                            Object b, int bFromIndex, int bToIndex) {
 916         int aLength = aToIndex - aFromIndex;
 917         int bLength = bToIndex - bFromIndex;
 918         if (aLength != bLength)
 919             return false;
 920 
 921         for (int i = 0; i < aLength; i++) {
 922             Object av = at.get(a, aFromIndex++);
 923             Object bv = at.get(b, bFromIndex++);
 924             if (!Objects.equals(av, bv)) return false;
 925         }
 926 
 927         return true;
 928     }
 929 
 930     static boolean isEqual(ArrayType<?> at, Object a, int aFrom, Object b, int bFrom) {
 931         Object av = at.get(a, aFrom);
 932         Object bv = at.get(b, bFrom);
 933 
 934         return Objects.equals(av, bv);
 935     }
 936 
 937     static int[] ranges(int from, int to) {
 938         int width = to - from;
 939         switch (width) {
 940             case 0:
 941                 return new int[]{};
 942             case 1:
 943                 return new int[]{from, to};
 944             case 2:
 945                 return new int[]{from, from + 1, to};
 946             case 3:
 947                 return new int[]{from, from + 1, from + 2, to};
 948             default:
 949                 return IntStream.of(from, from + 1, from + 2, to / 2 - 1, to / 2, to / 2 + 1, to - 2, to - 1, to)
 950                         .filter(i -> i >= from && i <= to)
 951                         .distinct().toArray();
 952         }
 953     }
 954 
 955 
 956     // Null array reference tests
 957 
 958     @Test(dataProvider = "arrayTypesProvider")
 959     public void testNullArrayRefs(ArrayType<?> arrayType) {
 960         Object n = null;
 961         Object a = arrayType.construct(0);
 962 
 963         Assert.assertTrue(arrayType.equals(n, n));
 964         Assert.assertFalse(arrayType.equals(n, a));
 965         Assert.assertFalse(arrayType.equals(a, n));
 966 
 967         Assert.assertEquals(arrayType.compare(n, n), 0);
 968         Assert.assertTrue(arrayType.compare(n, a) < 0);
 969         Assert.assertTrue(arrayType.compare(a, n) > 0);
 970     }
 971 
 972 
 973     // Exception throwing tests
 974 
 975     @Test(dataProvider = "arrayTypesProvider")
 976     public void testNPEs(ArrayType<?> arrayType) {
 977         Object[] values = new Object[]{null, arrayType.construct(0)};
 978 
 979         for (Object o1 : values) {
 980             for (Object o2 : values) {
 981                 if (o1 != null && o2 != null)
 982                     continue;
 983 
 984                 testNPE(() -> arrayType.equals(o1, 0, 0, o2, 0, 0));
 985                 testNPE(() -> arrayType.compare(o1, 0, 0, o2, 0, 0));
 986                 testNPE(() -> arrayType.mismatch(o1, o2));
 987                 testNPE(() -> arrayType.mismatch(o1, 0, 0, o2, 0, 0));
 988             }
 989         }
 990     }
 991 
 992     @Test
 993     public void testObjectNPEs() {
 994         String[][] values = new String[][]{null, new String[0]};
 995         Comparator<String> c = String::compareTo;
 996         Comparator[] cs = new Comparator[]{null, c};
 997 
 998         for (String[] o1 : values) {
 999             for (String[] o2 : values) {
1000                 for (Comparator o3 : cs) {
1001                     if (o1 != null && o2 != null && o3 != null)
1002                         continue;
1003 
1004                     if (o3 == null) {
1005                         testNPE(() -> Arrays.compare(o1, o2, o3));
1006                         testNPE(() -> Arrays.mismatch(o1, o2, o3));
1007                     }
1008 
1009                     testNPE(() -> Arrays.compare(o1, 0, 0, o2, 0, 0, o3));
1010                     testNPE(() -> Arrays.mismatch(o1, 0, 0, o2, 0, 0, o3));
1011                 }
1012             }
1013         }
1014     }
1015 
1016     @Test(dataProvider = "arrayTypesProvider")
1017     public void testIAEs(ArrayType<?> arrayType) {
1018         List<Integer> values = Arrays.asList(0, 1);
1019 
1020         for (int s : values) {
1021             Object a = arrayType.construct(s);
1022 
1023             for (int o1 : values) {
1024                 for (int o2 : values) {
1025                     if (o1 <= o2) continue;
1026 
1027                     testIAE(() -> arrayType.equals(a, o1, 0, a, o2, 0));
1028                     testIAE(() -> arrayType.compare(a, o1, 0, a, o2, 0));
1029                     testIAE(() -> arrayType.mismatch(a, o1, 0, a, o2, 0));
1030                 }
1031             }
1032         }
1033     }
1034 
1035     @Test(dataProvider = "arrayTypesProvider")
1036     public void testAIOBEs(ArrayType<?> arrayType) {
1037         List<Integer> froms = Arrays.asList(-1, 0);
1038 
1039         for (int s : Arrays.asList(0, 1)) {
1040             List<Integer> tos = Arrays.asList(s, s + 1);
1041             Object a = arrayType.construct(s);
1042 
1043             for (int aFrom : froms) {
1044                 for (int aTo : tos) {
1045                     for (int bFrom : froms) {
1046                         for (int bTo : tos) {
1047                             if (aFrom >= 0 && aTo <= s &&
1048                                 bFrom >= 0 && bTo <= s) continue;
1049 
1050                             testAIOBE(() -> arrayType.equals(a, aFrom, aTo, a, bFrom, bTo));
1051                             testAIOBE(() -> arrayType.compare(a, aFrom, aTo, a, bFrom, bTo));
1052                             testAIOBE(() -> arrayType.mismatch(a, aFrom, aTo, a, bFrom, bTo));
1053                         }
1054                     }
1055                 }
1056             }
1057         }
1058     }
1059 
1060     static void testNPE(Runnable r) {
1061         testThrowable(r, NullPointerException.class);
1062     }
1063 
1064     static void testIAE(Runnable r) {
1065         testThrowable(r, IllegalArgumentException.class);
1066     }
1067 
1068     static void testAIOBE(Runnable r) {
1069         testThrowable(r, ArrayIndexOutOfBoundsException.class);
1070     }
1071 
1072     static void testThrowable(Runnable r, Class<? extends Throwable> expected) {
1073         Throwable caught = null;
1074         try {
1075             r.run();
1076         }
1077         catch (Throwable t) {
1078             caught = t;
1079         }
1080         Assert.assertNotNull(caught);
1081         Assert.assertTrue(expected.isInstance(caught));
1082     }
1083 }