[pre-pitch] Noncopyable comparison, partial orders, and the spaceship operator

Using Swift
1

As the UTF8Span pitch brought it back up, I'd like to discuss allowing comparisons of non-copyable types, implementing the spaceship operator, as well as partially ordered comparisons.

All of these things are (relatively) easy to implement in user code, but there's a couple of wrinkles if we want to add them to the standard library.

Example implementation. 
@frozen public enum Ordering: Sendable {
  case ascending
  case equal
  case descending
}

public protocol PartiallyEquatable: ~Copyable {
  static func == (lhs: borrowing Self, rhs: borrowing Self) -> Bool
}

extension PartiallyEquatable where Self: ~Copyable {
  @_transparent
  public static func != (lhs: borrowing Self, rhs: borrowing Self) -> Bool {
    !(lhs == rhs)
  }
}

public protocol FullyEquatable: PartiallyEquatable, ~Copyable {}

infix operator <=> : ComparisonPrecedence

public protocol PartiallyOrdered: PartiallyEquatable, ~Copyable {
  borrowing func compare(to other: borrowing Self) -> Ordering?
}

extension PartiallyOrdered where Self: ~Copyable {
  @inlinable
  public static func < (lhs: borrowing Self, rhs: borrowing Self) -> Bool {
    lhs.compare(to: rhs) == .ascending
  }
  @inlinable
  public static func <= (lhs: borrowing Self, rhs: borrowing Self) -> Bool {
    lhs == rhs || lhs < rhs
  }
  @inlinable
  public static func > (lhs: borrowing Self, rhs: borrowing Self) -> Bool {
    lhs.compare(to: rhs) == .descending
  }
  @inlinable
  public static func >= (lhs: borrowing Self, rhs: borrowing Self) -> Bool {
    lhs == rhs || lhs > rhs
  }
}

public protocol Ordered: PartiallyOrdered, FullyEquatable, ~Copyable {
  static func <=> (lhs: borrowing Self, rhs: borrowing Self) -> Ordering
  static func < (lhs: borrowing Self, rhs: borrowing Self) -> Bool
}

extension Ordered where Self: ~Copyable {
  @inlinable
  public borrowing func compare(to other: borrowing Self) -> Ordering? {
    self <=> other
  }
}

extension PartiallyOrdered where Self: Comparable {
  @inlinable
  public borrowing func compare(to other: borrowing Self) -> Ordering? {
    if self < other {
      .ascending
    } else if self == other {
      .equal
    } else if self > other {
      .descending
    } else {
      nil
    }
  }
}

extension Ordered where Self: Comparable {
  @inlinable
  public static func < (lhs: borrowing Self, rhs: borrowing Self) -> Bool {
    @_transparent func lt<T: Comparable>(_ lhs: T, _ rhs: T) -> Bool {
      return lhs < rhs
    }
    return lt(copy lhs, copy rhs)
  }
  @inlinable
  public static func <=> (lhs: borrowing Self, rhs: borrowing Self) -> Ordering {
    if lhs < rhs {
      .ascending
    } else if lhs == rhs {
      .equal
    } else {
      .descending
    }
  }
}

extension Bool: FullyEquatable {}

extension Int: Ordered {}
extension Int8: Ordered {}
extension Int16: Ordered {}
extension Int32: Ordered {}
extension Int64: Ordered {}
extension Int128: Ordered {}

extension UInt: Ordered {}
extension UInt8: Ordered {}
extension UInt16: Ordered {}
extension UInt32: Ordered {}
extension UInt64: Ordered {}
extension UInt128: Ordered {}

extension Float16: PartiallyOrdered {}
extension Float32: PartiallyOrdered {}
extension Float64: PartiallyOrdered {}
extension Float80: PartiallyOrdered {}

The points of contention are:

  1. Do we want to support partially ordered comparisons? This would require either a (mostly) separate protocol hierarchy, or a change in semantics of Equatable and Comparison to represent partial orderings (because stable ABI means we can't retroactively add new protocols above them in the hierarchy).
  2. The answer to point 1 changes how we extend the comparison protocols to encompass non-copyable types. If the answer is yes, then we need at least two new protocols. One for either partial or full equatability, and two for three way comparisons (one if we repurpose the existing protocols for partial orders).

Three way comparisons themselves are easy peasy:

@frozen public enum Ordering: Sendable {
  case ascending
  case equal
  case descending
}

infix operator <=> : ComparisonPrecedence

And whichever protocol handles total orders gets a defaulted static func <=> (_ lhs: borrowing Self, _ rhs: borrowing Self) -> Ordering requirement, and (if we add them) the protocol for partial orders gets a func compare(to other: borrowing Self) -> Ordering? requirement.

The previous pitch wanted to just move Foundation's ComparisonResult into the standard library, but the case names are so ugly. There might be a benefit to making it an Int backed @ObjC enum, but that depends on whether that actually makes the discriminator equal the rawValue.

2 Likes
2

This was previously pitched and rejected years ago.

The rationale (which I won’t do justice to but you can find in these forums) was that experience with languages that do have such protocol hierarchies shows that, practically, generic constraints will end up always calling for one of these. I think it was the fully ordered one.

As protocol hierarchies are meant to support users writing useful generic algorithms and not as a name-them-all taxonomy, it was favored to create a simpler hierarchy.

More generally, while taking the time to address targeted pain points with the existing protocols that emerge from years of user experience as we generalize to incorporate noncopyable types is good, I’m wary of efforts to basically relitigate design decisions de novo. We are likely to introduce as many problems as we solve, and concern about code churn with every new language feature is already high.

Users should not have to relearn fundamental aspects of the language like equatability that have nothing to do with or are only tangentially related to noncopyable types just because the latter offered an opportunity for language designers to do something different.

I am personally a fan of the spaceship operator as well, but that too seems orthogonal to the question of retrofitting Equatable to noncopyable types. If a change is not necessary for the latter effort, I personally would strongly prefer to see it considered independently, and ideally I think even at least a language version later. Local maximization with respect to every protocol we touch does not necessarily lead to the best overall next release in terms of user experience.

1 Like