java.util.NoSuchElementException: key not found: Constant(NaN)

[scabug]

The following code works at least until 2.8.0.r19433, but not now:

Welcome to Scala version 2.8.0.r19458-b20091109194122 (Java HotSpot(TM) 64-Bit Server VM, Java 1.6.0_15).

scala> final val a = Float.NaN
Exception in thread "main" java.util.NoSuchElementException: key not found: Constant(NaN)
	at scala.collection.MapLike$$class.default(MapLike.scala:191)
	at scala.collection.mutable.LinkedHashMap.default(LinkedHashMap.scala:33)
	at scala.collection.MapLike$$class.apply(MapLike.scala:106)
	at scala.collection.mutable.LinkedHashMap.apply(LinkedHashMap.scala:33)
	at scala.tools.nsc.symtab.classfile.Pickler$$Pickle.scala$$tools$$nsc$$symtab$$classfile$$Pickler$$Pickle$$$$writeRef(Pickler.scala:478)
	at scala.tools.nsc.symtab.classfile.Pickler$$Pickle.writeBody$$1(Pickler.scala:567)
	at scala.tools.nsc.symtab.classfile.Pickler$$Pickle.scala$$tools$$nsc$$symtab$$classfile$$Pickler$$Pickle$$$$writeEntry(Pickler.scala:972)
	at scala.tools.nsc.symtab.classfile.Pickler$$Pickle$$$$anonfun$$finish$$1.apply(Pickler.scala:1099)
	at scala.tools.nsc.symtab.classfile.Pickler$$Pickle$$$$anonfun$$finish$$1.apply(Pickler.scala:1094)
	at scala.collection.immutable.Range$$ByOne$$class.foreach(Range.scala:167)
	at scala.collection.immutable.Range$$$$anon$$2.foreach(Range.scala:149)
	at scala.tools.nsc.symtab.classfile.Pickler$$Pickle.finish(Pickler.scala:1094)
	at scala.tools.nsc.symtab.classfile.Pickler$$PicklePhase.pickle$$1(Pickler.scala:53)
	at scala.tools.nsc.symtab.classfile.Pickler$$PicklePhase$$$$anonfun$$pickle$$1$$1.apply(Pickler.scala:47)
	at scala.tools.nsc.symtab.classfile.Pickler$$PicklePhase$$$$anonfun$$pickle$$1$$1.apply(Pickler.scala:47)
	at scala.collection.LinearSeqLike$$class.foreach(LinearSeqLike.scala:85)
	at scala.collection.immutable.List.foreach(List.scala:29)
	at scala.tools.nsc.symtab.classfile.Pickler$$PicklePhase.pickle$$1(Pickler.scala:47)
	at scala.tools.nsc.symtab.classfile.Pickler$$PicklePhase.apply(Pickler.scala:57)
	at scala.tools.nsc.Global$$GlobalPhase.applyPhase(Global.scala:323)
	at scala.tools.nsc.Global$$GlobalPhase$$$$anonfun$$run$$1.apply(Global.scala:301)
	at scala.tools.nsc.Global$$GlobalPhase$$$$anonfun$$run$$1.apply(Global.scala:301)
	at scala.collection.Iterator$$class.foreach(Iterator.scala:541)
	at scala.collection.mutable.ListBuffer$$$$anon$$1.foreach(ListBuffer.scala:285)
	at scala.tools.nsc.Global$$GlobalPhase.run(Global.scala:301)
	at scala.tools.nsc.Global$$Run.compileSources(Global.scala:794)
	at scala.tools.nsc.Interpreter$$Request.compile(Interpreter.scala:718)
	at scala.tools.nsc.Interpreter.interpret(Interpreter.scala:432)
	at scala.tools.nsc.InterpreterLoop.interpretStartingWith(InterpreterLoop.scala:331)
	at scala.tools.nsc.InterpreterLoop.command(InterpreterLoop.scala:308)
	at scala.tools.nsc.InterpreterLoop.processLine$$1(InterpreterLoop.scala:205)
	at scala.tools.nsc.InterpreterLoop.repl(InterpreterLoop.scala:219)
	at scala.tools.nsc.InterpreterLoop.main(InterpreterLoop.scala:379)
	at scala.tools.nsc.MainGenericRunner$$.createLoop$$1(MainGenericRunner.scala:119)
	at scala.tools.nsc.MainGenericRunner$$.main(MainGenericRunner.scala:144)
	at scala.tools.nsc.MainGenericRunner.main(MainGenericRunner.scala)

I add "final" before a class's val field "a" to prevent overridden

[scabug]

Imported From: https://issues.scala-lang.org/browse/SI-2598?orig=1
Reporter: @dcaoyuan

[scabug]

@dcaoyuan said:
My project that works under 2.8.0.r19433 now also throws something likeness:

java.util.NoSuchElementException: key not found: MA2
     [java] 	at scala.collection.MapLike$$class.default(MapLike.scala:191)
     [java] 	at scala.collection.mutable.HashMap.default(HashMap.scala:21)
     [java] 	at scala.collection.MapLike$$class.apply(MapLike.scala:106)
     [java] 	at scala.collection.mutable.HashMap.apply(HashMap.scala:21)

It seems hash is broken?

[scabug]

@paulp said:
This was introduced with the new equals method in r19456 and it highlights an interesting corner case. Thanks for reporting it so quickly. A little known secret is that "final" also signals the compiler to do constant folding, which is why this only happens when you say final.

The corner case is that in java NaN != NaN in float primitives, but NaN == NaN among the boxed. Hopefully NaN is the only case where the boxed type has more generous equality than the primitive.

[scabug]

@paulp said:
Replying to [comment:1 dcaoyuan]:

It seems hash is broken?

Possibly. I'll review the implementation shortly, but at the moment there's some other breakage in trunk so I'll queue up over by the snack bar.

[scabug]

@dcaoyuan said:
The following example also shown that Float.NaN cannot be contained in for example, an ArrayBuffer for some hash code usage:

Welcome to Scala version 2.8.0.r19480-b20091110111040 (Java HotSpot(TM) 64-Bit Server VM, Java 1.6.0_15).
Type in expressions to have them evaluated.
Type :help for more information.

scala> val a = Array(1f)
a: Array[Float] = Array(1.0)

scala> val b = Array(Float.NaN)
b: Array[Float] = Array(NaN)

scala> val c = scala.collection.mutable.ArrayBuffer(1f)
c: scala.collection.mutable.ArrayBuffer[Float] = ArrayBuffer(1.0)

scala> val d = scala.collection.mutable.ArrayBuffer(Float.NaN)                         
d: scala.collection.mutable.ArrayBuffer[Float] = ArrayBuffer(NaN)

scala> val m = scala.collection.mutable.HashMap(a -> "a", b -> "b", c -> "c", d -> "d")
m: scala.collection.mutable.HashMap[ScalaObject,java.lang.String] = Map([F@62b92956 -> a, ArrayBuffer(1.0) -> c, [F@6a48ffbc -> b, ArrayBuffer(NaN) -> d)

scala> m(a)
res0: java.lang.String = a

scala> m(b)
res1: java.lang.String = b

scala> m(c)
res2: java.lang.String = d

scala> m(d)
java.util.NoSuchElementException: key not found: ArrayBuffer(NaN)
	at scala.collection.MapLike$$class.default(MapLike.scala:191)
	at scala.collection.mutable.HashMap.default(HashMap.scala:21)
	at scala.collection.MapLike$$class.apply(MapLike.scala:106)
	at scala.collection.mutable.HashMap.apply(HashMap.scala:21)
	at .<init>(<console>:10)
	at .<clinit>(<console>)
	at RequestResult$$.<init>(<console>:4)
	at RequestResult$$.<clinit>(<console>)
	at RequestResult$$result(<console>)
	at sun.reflect.NativeMethodAccessorImpl.invoke0(Native Method)
	at sun.reflect.NativeMethodAccessorImpl.invoke(NativeMethodAccessorImpl.java:39)
	at sun.reflect.DelegatingMethodAccessorImpl.invoke(DelegatingMethodAccessorImpl.java:25)
	at java.lang.reflect.Method.invoke(Method.java:597)
	at scala.tools.nsc.Interpreter$$Request$$$$anonfun$$loadAndRun$$1$$$$anonfun$$apply$$13.apply(Interpreter.scala:788)
	at scala.tools.nsc.Interpreter$$Request$$$$anonfun$$loadAndRun$$1$$$$anonfun$$apply$$13.apply(Interpreter.scala:788)
	at scala.util.control.Exception$$Catch.apply(Exception.scala:79)
	at scala.tools.nsc.Interpreter$$Request$$$$anonfun$$loadAndRun$$1.apply(Interpreter.scala:787)
	at scala.tools.nsc.Interpreter$$Request$$$$anonfun$$loadAndRun$$1.apply(Interpreter.scala:787)
	at scala.util.control.Exception$$Catch.apply(Exception.scala:79)
	at scala.tools.nsc.Interpreter$$Request.loadAndRun(Interpreter.scala:786)
	at scala.tools.nsc.Interpreter.interpret(Interpreter.scala:435)
	at scala.tools.nsc.Interpreter.interpret(Interpreter.scala:425)
	at scala.tools.nsc.InterpreterLoop.interpretStartingWith(InterpreterLoop.scala:331)
	at scala.tools.nsc.InterpreterLoop.command(InterpreterLoop.scala:308)
	at scala.tools.nsc.InterpreterLoop.processLine$$1(InterpreterLoop.scala:205)
	at scala.tools.nsc.InterpreterLoop.repl(InterpreterLoop.scala:223)
	at scala.tools.nsc.InterpreterLoop.main(InterpreterLoop.scala:379)
	at scala.tools.nsc.MainGenericRunner$$.createLoop$$1(MainGenericRunner.scala:119)
	at scala.tools.nsc.MainGenericRunner$$.main(MainGenericRunner.scala:144)
	at scala.tools.nsc.MainGenericRunner.main(MainGenericRunner.scala)

[scabug]

@dcaoyuan said:
It seems that collection/object which contains Float.NaN whenever will not be hash equality anymore?

[scabug]

@paulp said:
Replying to [comment:5 dcaoyuan]:

It seems that collection/object which contains Float.NaN whenever will not be hash equality anymore?

Fixing this is straightforward (I just did it locally) but it looks like a steep performance price to pay relative to the utility. I'll have to wait and see how martin wants to handle it.

[scabug]

@adriaanm said:
Martin, please re-assign with recommendation on how to fix.

In general, it's not a good idea to use floats as hash keys -- then again, how can the Pickler avoid that problem?

[scabug]

@odersky said:
Fixed in one of my last commits on 12nov2009. The problem was that NaN != NaN, so the equality test for constants needed a special case.

[scabug]

@paulp said:
Possibly depending on what you expect to work, I'm pretty sure this isn't fixed.

scala> val m = scala.collection.mutable.HashMap(Float.NaN -> "hi")
m: scala.collection.mutable.HashMap[Float,java.lang.String] = Map(NaN -> hi)

scala> m(Float.NaN)
java.util.NoSuchElementException: key not found: NaN
	at scala.collection.MapLike$$class.default(MapLike.scala:191)

I don't see how it's fixable at the location where you put the nan code, or how to avoid the check in the boxesruntime equals method. That's what I was referring to in comment #5.

[scabug]

@odersky said:
My fix related to the original problem of the compiler crashing. It stored an Constant(NaN) in a hashtable and then did not find it again because NaN != NaN.
I do not think we either should or can solve the original problem. NaN will always be different from NaN (and there are good reasons for it), so you need to do a special trick each time you store it in a table. That's just how things are. Reassigning to you Paul, but feel free to close as is.

[scabug]

@dcaoyuan said:
But

scala> val a= Float.NaN
a: Float = NaN

scala> val b = Float.NaN
b: Float = NaN

scala> a.equals(b)
res0: Boolean = true

scala> Float.NaN equals Float.NaN
res1: Boolean = true

And, at least, Float.NaN can be put in HashMap in Java.

Float.NaN/Double.NaN is used a lot in scientific computing, since it's the only number that keeps same value (NaN) upon any operations.

The problem I see is that when any class/object contains or deeply contains some fields which can be filled with Float.NaN, may suffer from it.

[scabug]

@odersky said:
After having thought more than is healthy about this, I really think there's nothing we can do. We should not go against IEEE and admit NaN == NaN. That would bring the whole of mathematics crashing down ;-). On the other hand, in the interest of fast equality we should mandate that == strictly contains eq. But now we are in a quandary. On the one hand

new java.lang.Float(NaN) != new java.lang.Float(NaN)

would be desirable to follow primitive float equality. On the other hand,

val x = new java.lang.Float(NaN)
x == x

must hold because x eq x. But note that

val x = Float.NaN
x == x

also must yield false. So it's a paradox which can't be resolved. The only consolation is that NaN is a paradox by itself. The only advice I can give is don't use it, or at least be extremely careful where you use it!

-- Martin