Bug in Double.java

[Eric Blake]

There are some bugs with zero comparison in java.lang.Double.compare(double,
double) (and probably in Float as well, but I haven't checked that yet).

I also spotted some optimizations to add.  I made the equals, compare, and
isNaN work without needing to use doubleToLongBits(), since a native call
carries overhead.  I also updated hashCode to use a cache, to reduce the
number of native calls made by the same Double.  A further optimization
which I did not make might be to have Double.valueOf(double) reuse common
Doubles (-inf, inf, nan, +0, -0, 1, -1, 2, 0.5, 10, and maybe some others)
rather than construct new Doubles; much the way Boolean.valueOf(boolean)
works.  By the way, this patch will not work if you have a broken JIT that
assumes d!=d is always false - see JLS 15.21.1.

Someone will need to check my work with serialization issues, as I am not
very familiar with the process.  Basically, my added hashCode() caching will
break if a deserialization restores the transient hashCode field to 0
instead of -1.  I chose -1 for the non-cached value instead of 0, since new
Double(0).hashCode() == 0, but left the cache field transient so it will
interoperate with serial streams from other sources.  Maybe it's not worth
caching the result of hashCode() after all.

This patch is rather long, and I haven't signed paperwork, so you will have
to let me know what to do from here.  Below is a class I used to verify
correct operation.

// Requires 1.4 API to exist
class Foo {
  public static void main(String[] args) {
    double odd_nan = Double.longBitsToDouble(-1L);
    double canonical_nan = Double.NaN;
    double pos_zero = 0.0;
    double neg_zero = -0.0;
    if (! Double.isNaN(canonical_nan))
      System.out.println("failed Double.isNaN(NaN)");
    if (! Double.isNaN(odd_nan))
      System.out.println("failed Double.isNaN(NaN)");
    if (Double.compare(odd_nan, odd_nan) != 0)
      System.out.println("failed Double.compare(NaN, NaN)");
    if (Double.compare(canonical_nan, odd_nan) != 0)
      System.out.println("failed Double.compare(NaN, NaN)");
    if (Double.compare(canonical_nan, canonical_nan) != 0)
      System.out.println("failed Double.compare(NaN, NaN)");
    if (Double.compare(odd_nan, canonical_nan) != 0)
      System.out.println("failed Double.compare(NaN, NaN)");

    if (Double.compare(pos_zero, pos_zero) != 0)
      System.out.println("failed Double.compare(0d, 0d)");
    if (Double.compare(neg_zero, pos_zero) >= 0)
      System.out.println("failed Double.compare(-0d, 0d)");
    if (Double.compare(neg_zero, neg_zero) != 0)
      System.out.println("failed Double.compare(-0d, -0d)");
    if (Double.compare(pos_zero, neg_zero) <= 0)
      System.out.println("failed Double.compare(0d, -0d)");

    Double oddNaN = new Double(odd_nan);
    Double canonicalNaN = new Double(canonical_nan);
    Double posZero = new Double(pos_zero);
    Double negZero = new Double(neg_zero);
    if (! oddNaN.isNaN())
      System.out.println("failed new Double(NaN).isNaN()");
    if (! canonicalNaN.isNaN())
      System.out.println("failed new Double(NaN).isNaN()");

    if (! oddNaN.equals(canonicalNaN))
      System.out.println("failed new Double(NaN).equals(new Double(NaN))");
    if (! canonicalNaN.equals(canonicalNaN))
      System.out.println("failed new Double(NaN).equals(new Double(NaN))");
    if (! canonicalNaN.equals(oddNaN))
      System.out.println("failed new Double(NaN).equals(new Double(NaN))");
    if (! oddNaN.equals(oddNaN))
      System.out.println("failed new Double(NaN).equals(new Double(NaN))");

    if (! posZero.equals(posZero))
      System.out.println("failed new Double(0d).equals(new Double(0d))");
    if (posZero.equals(negZero))
      System.out.println("failed new Double(0d).equals(new Double(-0d))");
    if (! negZero.equals(negZero))
      System.out.println("failed new Double(-0d).equals(new Double(-0d))");
    if (negZero.equals(posZero))
      System.out.println("failed new Double(-0d).equals(new Double(0d))");

    if (Double.doubleToRawLongBits(canonicalNaN.doubleValue()) !=
0x7ff8000000000000L)
      System.out.println("failed Double.doubleToRawLongBits(NaN)");
    if (Double.doubleToRawLongBits(oddNaN.doubleValue()) != -1L)
      System.out.println("failed Double.doubleToRawLongBits(NaN)");
    if (Double.doubleToRawLongBits(posZero.doubleValue()) != 0L)
      System.out.println("failed Double.doubleToRawLongBits(0d)");
    if (Double.doubleToRawLongBits(negZero.doubleValue()) != Long.MIN_VALUE)
      System.out.println("failed Double.doubleToRawLongBits(-0d)");

    if (Double.doubleToLongBits(canonicalNaN.doubleValue()) !=
0x7ff8000000000000L)
      System.out.println("failed Double.doubleToLongBits(NaN)");
    if (Double.doubleToLongBits(oddNaN.doubleValue()) !=
0x7ff8000000000000L)
      System.out.println("failed Double.doubleToLongBits(NaN)");
    if (Double.doubleToLongBits(posZero.doubleValue()) != 0L)
      System.out.println("failed Double.doubleToLongBits(0d)");
    if (Double.doubleToLongBits(negZero.doubleValue()) != Long.MIN_VALUE)
      System.out.println("failed Double.doubleToLongBits(-0d)");

    if (canonicalNaN.hashCode() != 0x7ff80000)
      System.out.println("failed new Double(NaN).hashCode()");
    if (oddNaN.hashCode() != 0x7ff80000)
      System.out.println("failed new Double(NaN).hashCode()");
    if (posZero.hashCode() != 0)
      System.out.println("failed new Double(0d).hashCode()");
    if (negZero.hashCode() != Integer.MIN_VALUE)
      System.out.println("failed new Double(0d).hashCode()");
  }
}


--
Eric Blake, Elixent, Castlemead, Lwr Castle St., Bristol BS1 3AG, UK
address@hidden   tel:+44(0)117 917 5611


2001-07-16  Eric Blake  <address@hidden>

        * java/lang/Double.java (NaN): Improved docs.
        (doubleToLongBits double): idem.
        (doubleToRawLongBits double): idem.
        (longBitsToDouble long): idem.
        (value): Made final.
        (equals Object): Improve docs, optimize.
        (isNaN): idem.
        (compare): idem., plus fix bug with zero comparison.
        (hashCode): Add a cache, to reduce number of native calls.
        (readObject ObjectInputStream): Added for correct deserialization.
        (parseDouble String): Optimize.

Index: java/lang/Double.java
===================================================================
RCS file: /cvs/classpath/java/lang/Double.java,v
retrieving revision 1.17
diff -u -r1.17 Double.java
--- java/lang/Double.java       2001/07/09 23:24:12     1.17
+++ java/lang/Double.java       2001/07/16 13:50:38
@@ -27,6 +27,8 @@

 package java.lang;

+import java.io.IOException;
+import java.io.ObjectInputStream;
 import gnu.classpath.Configuration;

 /**
@@ -38,6 +40,7 @@
  *
  * @author Paul Fisher
  * @author Andrew Haley <address@hidden>
+ * @author Eric Blake <address@hidden>
  * @since JDK 1.0
  */
 public final class Double extends Number implements Comparable
@@ -66,7 +69,12 @@
   public static final double POSITIVE_INFINITY = 1.0d/0.0d;

   /**
-   * All IEEE 754 values of NaN have the same value in Java.
+   * All values of NaN (IEEE 754 not-a-number) generated by compilation
+   * or Java execution should have the bit pattern 0x7ff8000000000000L.
+   * This constant represents 0.0/0.0, the canonical NaN.
+   *
+   * @see #longBitsToDouble(long)
+   * @see #doubleToRawLongBits(double)
    */
   public static final double NaN = 0.0d/0.0d;

@@ -76,7 +84,31 @@
    */
   public static final Class TYPE =
VMClassLoader.getPrimitiveClass("double");

-  private double value;
+  /**
+   * The immutable value of this Double.
+   */
+  private final double value;
+
+  /**
+   * Since determining the hashCode involves a native call, we cache
+   * for performance.  The hash code is seldom -1, but if it is, we
+   * lose the benefit of a cache.
+   */
+  private transient int hashCode = -1;
+
+  /**
+   * Since the hashCode cache is transient (it is not specified to be
+   * serial), but must not default to 0 (or the cache is broken), we
+   * must fix it during deserialization.
+   *
+   * @param stream the deserialization stream
+   */
+  private void readObject(ObjectInputStream stream)
+    throws IOException, ClassNotFoundException
+  {
+    stream.defaultReadObject();
+    hashCode = -1;
+  }

   /**
    * Load native routines necessary for this class.
@@ -132,9 +164,29 @@

   /**
    * If the <code>Object</code> is not <code>null</code>, is an
-   * <code>instanceof</code> <code>Double</code>, and represents
-   * the same primitive <code>double</code> value return
-   * <code>true</code>.  Otherwise <code>false</code> is returned.
+   * <code>instanceof Double</code>, and represents the same bit pattern
+   * of a <code>double</code> value, return <code>true</code>.  Otherwise
+   * <code>false</code> is returned.
+   *
+   * Note that in most cases, for two instances of class Double,
+   * <code>d1</code> and <code>d2</code>, the value of
+   * <code>d1.equals(d2)</code> is true if and only if
+   * <pre>
+   *   d1.doubleValue() == d2.doubleValue()
+   * </pre>
+   * also has the value true. However, there are two exceptions:
+   *
+   * <ul>
+   *  <li>If <code>isNaN(d1)</code> and <code>isNaN(d2)</code> both
+   *   return true, then <code>equals</code> returns true, even though
+   *   <code>Double.NaN == Double.NaN</code> has the value false.  This
+   *   collapses all 2<super>53</super> values of NaN into one.</li>
+   *  <li>If <code>d1</code> represents +0.0 while <code>d2</code>
+   *   represents -0.0, or vice versa, then <code>equals</code> has the
+   *   value false, even though <code>+0.0 == -0.0</true> has the value
+   *   true.</li>
+   * </ul>
+   * This definition allows hash tables to operate properly.
    *
    * @param obj the object to compare to
    * @return whether the objects are semantically equal.
@@ -144,9 +196,12 @@
     if (!(obj instanceof Double))
       return false;

-    Double d = (Double) obj;
+    double d = ((Double) obj).value;

-    return doubleToLongBits (value) == doubleToLongBits (d.doubleValue ());
+    // common case first, then check NaN and 0
+    if (value == d)
+      return value == 0 ? 1/value == 1/d : true;
+    return isNaN(value) ? isNaN(d) : false;
   }

   /**
@@ -156,11 +211,18 @@
    * <br>
    * where v is defined by: <br>
    * <code>long v = Double.doubleToLongBits(this.longValue());</code><br>
+   *
+   * Since determining the hash involves a native call, we cache for
+   * performance.  In the rare event that the result is -1, we end
+   * up recalculating every time.
    */
   public int hashCode()
   {
+    if (hashCode != -1)
+      return hashCode;
+
     long v = doubleToLongBits(value);
-    return (int)(v ^ (v >>> 32));
+    return hashCode = (int) (v ^ (v >>> 32));
   }

   /**
@@ -169,7 +231,7 @@
    */
   public int intValue()
   {
-    return (int)value;
+    return (int) value;
   }

   /**
@@ -178,7 +240,7 @@
    */
   public long longValue()
   {
-    return (long)value;
+    return (long) value;
   }

   /**
@@ -187,7 +249,7 @@
    */
   public float floatValue()
   {
-    return (float)value;
+    return (float) value;
   }

   /**
@@ -248,15 +310,19 @@
   }

   /**
-   * Return <code>true</code> if the <code>double</code> has the same
-   * value as <code>NaN</code>, otherwise return <code>false</code>.
+   * Return <code>true</code> if the <code>double</code> represents NaN,
+   * otherwise return <code>false</code>.  While compiling or evaluating
+   * Java expressions will always produce a double with bits identical
+   * to those in address@hidden #NaN}, there are in fact 2<super>53</super>
+   * distinct NaN's that can be generated by address@hidden
#longBitsToDouble(long)}.
    *
    * @param d the <code>double</code> to compare
    * @return whether the argument is <code>NaN</code>.
    */
   public static boolean isNaN(double d)
   {
-    return (doubleToLongBits(d) == 0x7ff8000000000000L);
+    // JLS 15.21.1: NaN != NaN is the only true reflexive inequality
+    return d != d;
   }

   /**
@@ -332,14 +398,12 @@
       return isNaN(y) ? 0 : 1;
     if (isNaN (y))
       return -1;
-    if ((x == 0.0d) && (y == -0.0d))
-      return 1;
-    if ((x == -0.0d) && (y == 0.0d))
-      return -1;
-    if (x == y)
-      return 0;

-    return (x > y) ? 1 : -1;
+    // recall that 0.0 == -0.0, so we convert to infinities and try again
+    if (x == 0 && y == 0)
+      return compare(1/x, 1/y);
+
+    return (x == y) ? 0 : (x > y) ? 1 : -1;
   }

   /**
@@ -418,6 +482,12 @@
    * <code>Double.longBitsToDouble(long)</code> to obtain the
    * original <code>double</code> value.
    *
+   * This method collapses all 2<super>53</super> versions of NaN
+   * to the canonical value in address@hidden #NaN}.
+   *
+   * @see #doubleToRawLongBits(double)
+   * @see #longBitsToDouble(long)
+   *
    * @param value the <code>double</code> to convert
    * @return the bits of the <code>double</code>.
    */
@@ -431,6 +501,9 @@
    * <code>doubleToLongBits</code> in that it does not collapse
    * NaN values.
    *
+   * @see #doubleToLongBits(double)
+   * @see #longBitsToDouble(long)
+   *
    * @param value the <code>double</code> to convert
    * @return the bits of the <code>double</code>.
    */
@@ -440,6 +513,9 @@
    * Return the <code>double</code> represented by the long
    * bits specified.
    *
+   * @see #doubleToLongBits(double)
+   * @see #doubleToRawLongBits(double)
+   *
    * @param bits the long bits representing a <code>double</code>
    * @return the <code>double</code> represented by the bits.
    */
@@ -508,8 +584,7 @@
   public static double parseDouble (String s)
     throws NumberFormatException
   {
-    String t = s.trim();
-    return parseDouble0 (t);
+    return parseDouble0(s.trim());
   }

   private static native double parseDouble0 (String s)