Incorrect result of Equals involving NaN in structural type nested in generic structural type

[exercitusvir]

(Reposted from github.com/fsharp/fsharp)

I know that nan = nan and nanf = nanf both return false.

But nan.Equals(nan) and nanf.Equals(nanf) return true. These are intended results and this also applies when nan or nanf is contained in another structural type such as a union.

The .NET Guidelines also say that Equals, GetHashCode and CompareTo should be consistent. That is, two values that are equal should be equal as per Equals, should return the same hash and CompareTo should return 0.

F# types adhere to this except for the following case when a single/float32 or double/float that is NaN is a value of a structural type such as a union, which is nested in another structural type such as a union or record that has at least one type parameter.

Here is sample code that shows the inconsistent behavior:

    type UnionWithFloat = UnionWithFloat of float
    type GenericUnion<'value> = GenericUnion of 'value
    type NonGenericUnion = NonGenericUnion of UnionWithFloat

    let leftGenericUnion = GenericUnion (UnionWithFloat nan)
    let rightGenericUnion = GenericUnion (UnionWithFloat nan)

    let leftNonGenericUnion = NonGenericUnion (UnionWithFloat nan)
    let rightNonGenericUnion = NonGenericUnion (UnionWithFloat nan)

    let comparableLeftGenericUnion = leftGenericUnion :> System.IComparable<GenericUnion<UnionWithFloat>>
    let comparableLeftNonGenericUnion = leftNonGenericUnion :> System.IComparable<NonGenericUnion>

    let genericUnionsEqual = leftGenericUnion.Equals(rightGenericUnion) // false! 
    let nonGenericUnionsEqual = leftNonGenericUnion.Equals(rightNonGenericUnion) // true

    let genericUnionsHashCodesEqual = leftGenericUnion.GetHashCode() = rightGenericUnion.GetHashCode() // true
    let nonGenericUnionsHashCodesEqual = leftNonGenericUnion.GetHashCode() = rightNonGenericUnion.GetHashCode() //true

    let genericUnionsComparisonEqual = comparableLeftGenericUnion.CompareTo(rightGenericUnion) = 0 // true
    let nonGenericUnionsComparisonEqual = comparableLeftNonGenericUnion.CompareTo(rightNonGenericUnion) = 0 // true

The inconsistent result is the following line:

    let genericUnionsEqual = leftGenericUnion.Equals(rightGenericUnion) // false! 

All the other ways of comparison correctly return true.

Note that this also applies to single/float32 and records. And you only see the inconsistent results when the type is generic (GenericUnion here), which nests another type (UnionWithFloat here). I have not tested this for more types or constellations. This was tested with F# 3.1 if this makes a difference.

I would be nice if you could fix this as it had me scratching my head for some time until I could pin down when this happens. It would also be nice if you could verify that the results are consistent for all possible types in all constellations in F#, whether generic and/or nested.

[exercitusvir]

Update: Forgot to use System.Collections.StructuralComparisons.StructuralEqualityComparer on System.Collections.IStructuralEquatable.Equals, but now the previous problem resurfaced along with the hash not being useful.

I've also tested this for arrays by making the same values above the only element of an array and I have the same problem as before.

Here is code from above adapted to use arrays, System.Collections.IStructuralEquatable and System.Collections.IStructuralComparable:

    type UnionWithFloat = UnionWithFloat of float
    type GenericUnion<'value> = GenericUnion of 'value
    type NonGenericUnion = NonGenericUnion of UnionWithFloat

    let leftGenericUnion = [| GenericUnion (UnionWithFloat nan) |] 
    let rightGenericUnion = [| GenericUnion (UnionWithFloat nan) |]

    let leftNonGenericUnion = [| NonGenericUnion (UnionWithFloat nan) |]
    let rightNonGenericUnion = [| NonGenericUnion (UnionWithFloat nan) |]

    let comparableLeftGenericUnion = leftGenericUnion :> System.Collections.IStructuralComparable
    let comparableLeftNonGenericUnion = leftNonGenericUnion :> System.Collections.IStructuralComparable

    let equatableLeftGenericUnion = leftGenericUnion :> System.Collections.IStructuralEquatable
    let equatableRightGenericUnion = rightGenericUnion :> System.Collections.IStructuralEquatable

    let equatableLeftNonGenericUnion = leftNonGenericUnion :> System.Collections.IStructuralEquatable
    let equatableRightNonGenericUnion = rightNonGenericUnion :> System.Collections.IStructuralEquatable

    let equalityComparer = System.Collections.StructuralComparisons.StructuralEqualityComparer
    let genericUnionsEqual = equatableLeftGenericUnion.Equals(equatableRightGenericUnion, equalityComparer) // false!
    let nonGenericUnionsEqual = equatableLeftNonGenericUnion.Equals(equatableRightNonGenericUnion, equalityComparer) // false!

    let genericUnionsHashCodesEqual = equatableLeftGenericUnion.GetHashCode() = equatableRightGenericUnion.GetHashCode() // false!
    let nonGenericUnionsHashCodesEqual = equatableLeftNonGenericUnion.GetHashCode() = equatableRightNonGenericUnion.GetHashCode() // false!

    let structuralComparer = System.Collections.StructuralComparisons.StructuralComparer
    let genericUnionsComparisonEqual = comparableLeftGenericUnion.CompareTo(rightGenericUnion, structuralComparer) = 0 // true
    let nonGenericUnionsComparisonEqual = comparableLeftNonGenericUnion.CompareTo(rightNonGenericUnion, structuralComparer) = 0 // true

The unexpected results are the following lines:

    let genericUnionsEqual = equatableLeftGenericUnion.Equals(equatableRightGenericUnion, equalityComparer) // false!
    let nonGenericUnionsEqual = equatableLeftNonGenericUnion.Equals(equatableRightNonGenericUnion, equalityComparer) // false!

    let genericUnionsHashCodesEqual = equatableLeftGenericUnion.GetHashCode() = equatableRightGenericUnion.GetHashCode() // false!
    let nonGenericUnionsHashCodesEqual = equatableLeftNonGenericUnion.GetHashCode() = equatableRightNonGenericUnion.GetHashCode() // false!

In addition to the previous problem, I find it confusing that arrays implement System.Collections.IStructuralEquatable, which has an explicit GetHashCode, but it seems to be based on the references (as opposed to the elements).

So GetHashCode can no longer be used as a workaround and neither System.Collections.IStructuralEquatable.Equals works in this particular case of nan in in a structural type nested in another structural type (it does not even have to be generic this time). The only method that remains to workaround this is System.Collections.IStructuralEquatable.CompareTo passing in a default comparer.

[latkin]

Yes, looks like some inconsistencies in generic comparison with NaN. FWIW this is not a 4.0 regression, it has been like this for a few releases.

@manofstick does any of this change with your comparison optimizations? You found some other inconsistencies, is this related?

type F     = F of float

type A<'t> = X of 't
type B     = X of F

let x = A.X(F(nan))
let y = B.X(F(nan))

// why inconsistent?
x.Equals(x) // false
y.Equals(y) // true

[manofstick]

@latkin

I faithfully duplicate this existing code :-)

Do you want it fixed? Or better to do that later, as easier to regression test when replicating same bugs...

[manofstick]

@latkin

Not in my scope actually.

It's in the F type, the IStructuralEquatable.Equals implementation is incorrect.

So need to fix the optimizer I'm guessing... (or, not that I have traversed through the code beyond my little neck of the woods, but I guess there must be some non-optimized tree that gets created first, and that is probably just choosing the wrong equality function which is later optimized to the PER equals.)

...and actually I think this is actually the same issues as #527

i.e. you shouldn't be optimizing IStructualEquality.Equals at all, because there is an IEqualityComparer argument which should be honoured.

[exercitusvir]

527 is related, but not the same issue. #527 occurs with a non-generic type, but this issue occurs with a generic type. The second example involving arrays has inconsistent results with both generic and non-generic types. And both examples of this issue involve NaN.

[psfinaki]

To add a few more links here:

• another nice summary from @manofstick
• places in Optimizer where @dsyme acknowledges this problem: one, two
• it was attacked and AFAIU even fixed and benchmarked here here

Actually I think is a serious and unfortunate bug. It should be fixed. I guess it will count as a breaking change.

It wasn't fixed earlier primarily because it was being tried to be "squashed" together with other changes which eventually didn't get in - also we probably didn't yet have some mechanisms like feature flags and langpreviews to get this in gradually.

But things have changed, it just should be addressed in a separate and focused manner. Not jumping on this right now, just saying it would be nice to plan and get this done.

@vzarytovskii what do you think will be the process around this? I mean RFCs, lang suggestions and so on.