[SR-1011] Fix Swift's min and max

[jepers]

Previous ID	SR-1011
Radar	rdar://18371906
Original Reporter	@jepers
Type	Bug

Additional Detail from JIRA

Votes	0
Component/s	Standard Library
Labels	Bug, AffectsABI
Assignee	None
Priority	Medium

md5: 02e1f5c939fcf783306752ae56fbe5c9

is duplicated by:

• SR-1256 minElement and maxElement returns incorrect value when the first value in an array is Double.NaN

relates to:

• SR-1990 Sort has incorrect result on small collections with NaN values

Issue Description:

In Swift, max and min of some number and nan will either give the number or nan depending on the order of the arguments.

I'd expect Swift's min and max to follow IEEE-754, so all of the following should print 1.0, same as Darwin's fmin and fmax does:

import Darwin
print(min(1.0, Double.NaN)) // 1.0
print(min(Double.NaN, 1.0)) // nan
print(max(1.0, Double.NaN)) // 1.0
print(max(Double.NaN, 1.0)) // nan

print(fmin(1.0, Double.NaN)) // 1.0
print(fmin(Double.NaN, 1.0)) // 1.0
print(fmax(1.0, Double.NaN)) // 1.0
print(fmax(Double.NaN, 1.0)) // 1.0

[jepers]

Ah, in Swift 3 (Xcode 8 beta (8S128d)):
Double.minimum(1.0, .nan) // 1.0
Double.minimum(.nan, 1.0) // 1.0

Swift.min and Swift.max are still returning different result depending on the order of args though, so I guess they should be fixed or removed.

[jepers]

@stephentyrone

[swift-ci]

Comment by Anton Vlasov (JIRA)

Current Swift.max implementation is pretty straightforward:

// line 54-57 at Algorithm.swift
public func max<T : Comparable>(_ x: T, _ y: T) -> T {
  // In case `x == y`, we pick `y`. See min(_:_:).
  return y >= x ? y : x
}

It use Comparable protocol to compare objects. For Double.nan implementation of the protocol will always return false (nan). So, Swift.max will always return first argument when one of arguments is nan.

I think the issue can be solved if implementation of Comparable protocol will take into consideration of nan value and don't always return false. But it will be against current documentation.

[swift-ci]

Comment by Sunny (JIRA)

After reviewing the code and test suite, I think this bug is already fixed. However, it is clearly still broken in Swift 4 and I'm not sure when the fix was made.

stdlib/public/core/FloatingPoint.swift.gyb

  public static func minimum(_ x: Self, _ y: Self) -> Self {
    if x.isSignalingNaN || y.isSignalingNaN {
      //  Produce a quiet NaN matching platform arithmetic behavior.
      return x + y
    }
    if x <= y || y.isNaN { return x }
    return y
  }
 

This code already does NaN checking and will return the non-NaN value as the IEEE 754 specifies. Same goes for the maximum implementation.

and test/stdlib/FloatingPoint.swift.gyb

      else if lhs.isNaN && !rhs.isNaN {
        expectEqual(min.bitPattern, rhs.bitPattern)
        expectEqual(max.bitPattern, rhs.bitPattern)
        expectEqual(minMag.bitPattern, rhs.bitPattern)
        expectEqual(maxMag.bitPattern, rhs.bitPattern)
      }
      else if rhs.isNaN && !lhs.isNaN {
        expectEqual(min.bitPattern, lhs.bitPattern)
        expectEqual(max.bitPattern, lhs.bitPattern)
        expectEqual(minMag.bitPattern, lhs.bitPattern)
        expectEqual(maxMag.bitPattern, lhs.bitPattern)
      } 

I ran these test and they all passed.

[swift-ci]

Comment by Sunny (JIRA)

Actually, after reading flap (JIRA User)'s comment, I think that although FloatingPoint implements maximum and minimum properly, Comparable does not call into these implementation in its minimum and maximum methods. Instead, Comparable uses <= and >= methods which will cause this bug. I will continue looking into this today. I think that Comparable should actually call maximum/minimum inside its implementation of those methods rather than using >/<=

[jepers]

Just to summarize the current state (Xcode 9.1 (9B55)):

import Darwin

// These are of course OK:
print(fmin(1.0, Double.nan)) // 1.0
print(fmin(Double.nan, 1.0)) // 1.0
print(fmax(1.0, Double.nan)) // 1.0
print(fmax(Double.nan, 1.0)) // 1.0

// And these are also OK (since Jun 2016, see my first comment above):
print(Double.minimum(1.0, .nan)) // 1.0
print(Double.minimum(.nan, 1.0)) // 1.0
print(Double.maximum(1.0, .nan)) // 1.0
print(Double.maximum(.nan, 1.0)) // 1.0

// But these are not:
print(min(1.0, Double.nan)) // 1.0
print(min(Double.nan, 1.0)) // nan
print(max(1.0, Double.nan)) // 1.0
print(max(Double.nan, 1.0)) // nan

[swift-ci]

Comment by Sunny (JIRA)

I am unassigning this issue from me. I believe the solution should be to remove Swift.min and Swift.max because they are global implementations of methods that need type-specific implementations. Conforming to Comparable is not sufficient enough to allow for generalizing the min/max methods because the usage of <= and > comparators is not the correct way to implement min/max for all Comparable types.

Having added to this discussion, I don't think I can make the decision to remove these methods, and I will defer to someone else.

[swift-ci]

Comment by Dylan A. Lukes (JIRA)

The documentation specifies that Comparable is intended to define a strict total order (with exception made for exceptional cases like NaN). Therefore, it should always be possible to define max/min in for a Comparable type if it does not have exceptional cases. If it does, it would need to be able to provide its own implementation.

It seems like the cleanest solution would be to simply add max and min as static protocol methods on Comparable. Instead of:

public func max<T : Comparable>(x: T, y: T, rest: T...) -> T
public func min<T : Comparable>(x: T, y: T, rest: T...) -> T

One would have:

protocol Comparable {
    // rest of definition ...
    
    public static func max(x: Self, y: Self, rest: Self...) -> Self
    public static func min(x: Self, y: Self, rest: Self...) -> Self
}

extension Comparable {
    // rest of extension ... 

    @_inlineable
    public static func max(x: Self, y: Self, rest: Self...) -> Self {
        // default implementation
    }

    @_inlineable
    public static func min(x: Self, y: Self, rest: Self...) -> Self {
        // default implementation
    }
}

It's also worth noting that the agenda/minutes for IEEE745-2018/2028 suggest that min-max operator may either be removed or respecified in the future, in order to address concerns such as the associativity, commutativity, and handling of signed zeroes by the min-max operators. Refer to:

• May 2017 Agenda

  • http://754r.ucbtest.org/minutes/2017-05-19-agenda.txt

  • See heading "===== minNum/maxNum associativity" for what the replacement operations might look like.

• "The Removal/Demotion of MinNum and MaxNum Operations from IEEE 754TM-2018"

  • http://754r.ucbtest.org/background/minNum_maxNum_Removal_Demotion_v3.pdf

• Changes in 754-2018 (Draft) from ANSI/IEEE Std 754-2008

  • http://754r.ucbtest.org/changes.html

  • "9.6 new {min,max}imum{,Number,Magnitude,MagnitudeNumber} operations are recommended; NaN handling is changed from 754-2008 5.3.1."