proposal: spec: disallow NaN keys in maps

[bcmills]

Motivation

Go currently supports NaN keys in maps through some clever tricks.

The current spec is ambiguous on this behavior. It says:

[I]f the map contains an entry with key x, a[x] is the map value with key x and the type of a[x] is the value […]

but "with key x" could plausibly mean "with key represented by x". (In practice, today it means "with key equal to x".)

That leads to surprising and subtle bugs (such as #14427) and adds complexity even in correct code (#20138 (comment)).

For example, the following two functions appear to be equivalent, but the latter version silently copies zeroes instead of the intended values for NaN keys:

func copy(m map[float64]int) map[float64]int {
  c := make(map[float64]int, len(m))
  for k, v := range m {
    c[k] = v
  }
}

func copy(m map[float64]int) map[float64]int {
  c := make(map[float64]int, len(m))
  for k := range m {
    c[k] = m[k]
  }
}

---

Proposal

We already reject incomparable values as map keys:

If the key type is an interface type, these comparison operators must be defined for the dynamic key values; failure will cause a run-time panic.

I propose that we should apply that standard to NaNs as well. Specifically, I propose that we add the following sentence to https://golang.org/ref/spec#Index_expressions:
Assigning to an element of a map with a key that is not equal to itself causes a run-time panic.

This proposal is along the lines of #19624, in that it produces panics for arithmetic operations which are otherwise likely to result in silent corruption in typical user code.

---

Workarounds

Users can easily avoid the proposed panics by calling math.IsNaN(k) checking whether the key is equal to itself before inserting a map entry.

Users who expect NaNs with the same representation to map to the same element can transform the keys using math.Float64bits or math.Float32bits:

  if k == 0 { // -0.0 or +0.0
    m[math.Float64bits(0)] = v
  } else {
    m[math.Float64bits(k)] = v
  }

Users who really do intend to store all of the entries for NaN keys separately can explicitly pair the map with a slice:

  type nanElem struct {
    k float64
    v V
  }
  var (
    m map[float64]V
    nans []nanElem
  )
  if k != k {
    nans = append(nans, nanElem{k, v})
  } else {
    m[k] = v
  }

[randall77]

FWIW, there's a fair amount of code in the hashmap implementation that deals with the possibility of k!=k for keys k (search for reflexivekey in runtime/hashmap.go). It would be nice to strip that out.
That said, I don't think it is a big performance impediment. In the common case it's just a load/compare/predictable branch in a few places.

[dsnet]

The strange behavior with maps only because == is not symmetric when applied on NaNs.
An alternative proposal would be to define == to be symmetric for NaNs only for maps. Technically there are multiple types of NaNs (signaling and quiet NaNs and a variety of valid bit sequences that represent NaNs). I similarly argue that they should all be equal to each other for maps in the same way that -0.0 == +0.0.

[bcmills]

@randall77 It may be that this proposal would simplify the hashmap implementation, but I would prefer to focus on the correctness and complexity implications for user code.

[bcmills]

@dsnet As @rsc notes in the blog post, allowing m[k1] and m[k2] to be same element when k1 != k2 would also be surprising. It is straightforward to equate NaNs in user code if desired using the math.FloatNbits approach outlined above, and I would argue that the explicit code makes the change in equality less surprising.

m := map[uint64]V
…
switch {
case math.IsNan(k):
  m[math.Float64bits(math.NaN())] = v
case k == 0:  // +0.0 or -0.0
  m[math.Float64bits(0)] = v
default:
  m[math.Float64bits(k)] = v
}

[randall77]

@bcmills : I agree, just wanted to let people know what the effects on the implementation would be (tl;dr a small net positive).

[cznic]

We already reject incomparable values as map keys:

If the key type is an interface type, these comparison operators must be defined for the dynamic key values; failure will cause a run-time panic.

All and every value of type {float32,float64} is comparable (guaranteed by the specs). The result of the comparison is irrelevant here.

Map keys must be comparable is a simple, non-complicated rule. I object to making it not only more complex, but suprisingly non-orthogonal.

[rsc]

Users can easily avoid the proposed panics by calling math.IsNaN(k) before inserting a map entry for k.

Not true. NaNs can be inside arrays or structs.

All our current restrictions are type-based, not value-based. Even the interface panic restriction is about the type inside the interface, not the value. I'd really like to avoid introducing and explaining new value-based restrictions.

[bcmills]

Users can easily avoid the proposed panics by calling math.IsNaN(k) before inserting a map entry for k.

Not true. NaNs can be inside arrays or structs.

Good point. But it's still easy to check, especially given the "not equal to itself" phrasing I've proposed:

if k != k {
  … // Can't be a map key. Do something else with it.
} else {
  m[k] = v
}

[bcmills]

The main issue I want to address is the surprising inability to access elements by key in an irreflexively-keyed map. If you don't want to introduce value-based restrictions, perhaps we could at least change map entries from "with key equal to x" to "with key represented by x"?

[rsc]

It's certainly an idea worth evaluating when we get to language changes again (hence the Go2 label). Like all the Go2-labelled things, I'm not going to try to evaluate them now.