Revisiting 'T != Type' in where clause


#1

Hello,

This discussion sort of fizzled out when the topic was first introduced. Joe Groff had asked the following:

Do you have a concrete example where you need this? It'd be good to know whether the types are ambiguous due to type checker bugs, or whether there's a principle by which they could be naturally ordered.

There is an example of this ordering that I stumbled upon recently. Suppose I wish to extend `Array` with a `uniques()` function that returns an array containing the unique elements of `self`. For performance reasons, I would first write a method for arrays with Hashable elements, so that I could check for uniqueness in constant time per element.

extension Array where Element: Hashable {
  func uniques() -> [Element] {
    var seen: Set<Element> = []
    var uniq: [Element] = []
    
    for e in self {
      if !seen.contains(e) {
        seen.insert(e)
        uniq.append(e)
      }
    }
    
    return uniq
  }
}

However I would still like to have a `uniques()` method for arrays whose elements are merely Equatable, and I'm willing to take the performance cost of O(n) lookup per element.

extension Array where Element: Equatable {
  func uniques() -> [Element] {
    var uniq: [Element] = []
    
    for e in self {
      if !uniq.contains(e) {
        uniq.append(e)
      }
    }
    
    return uniq
  }
}

However, there is a problem, which is that elements that are Hashable are also Equatable, and so there is ambiguity when calling this method:

// error: ambiguous use of 'uniques()'
print([1,2,3,1,2,4,5,1,2,3,4,5].uniques())

If I could add `Element != Hashable` to the second extension, there would be no ambiguity.

FWIW replacing Array with Collection and Element with Iterator.Element fixes the error. The first extension (the one for Hashables) is called. I'm not sure why it is ambiguous in one case and not the other.


(Jaden Geller) #2

I would’ve expected overload resolution to pick the “more specific” one in this case without needing any additional constraints… :thinking:

···

On Mar 16, 2017, at 6:40 PM, Robert Bennett via swift-evolution <swift-evolution@swift.org> wrote:

Hello,

This discussion sort of fizzled out when the topic was first introduced. Joe Groff had asked the following:

Do you have a concrete example where you need this? It'd be good to know whether the types are ambiguous due to type checker bugs, or whether there's a principle by which they could be naturally ordered.

There is an example of this ordering that I stumbled upon recently. Suppose I wish to extend `Array` with a `uniques()` function that returns an array containing the unique elements of `self`. For performance reasons, I would first write a method for arrays with Hashable elements, so that I could check for uniqueness in constant time per element.

extension Array where Element: Hashable {
  func uniques() -> [Element] {
    var seen: Set<Element> = []
    var uniq: [Element] = []
    
    for e in self {
      if !seen.contains(e) {
        seen.insert(e)
        uniq.append(e)
      }
    }
    
    return uniq
  }
}

However I would still like to have a `uniques()` method for arrays whose elements are merely Equatable, and I'm willing to take the performance cost of O(n) lookup per element.

extension Array where Element: Equatable {
  func uniques() -> [Element] {
    var uniq: [Element] = []
    
    for e in self {
      if !uniq.contains(e) {
        uniq.append(e)
      }
    }
    
    return uniq
  }
}

However, there is a problem, which is that elements that are Hashable are also Equatable, and so there is ambiguity when calling this method:

// error: ambiguous use of 'uniques()'
print([1,2,3,1,2,4,5,1,2,3,4,5].uniques())

If I could add `Element != Hashable` to the second extension, there would be no ambiguity.

FWIW replacing Array with Collection and Element with Iterator.Element fixes the error. The first extension (the one for Hashables) is called. I'm not sure why it is ambiguous in one case and not the other.

_______________________________________________
swift-evolution mailing list
swift-evolution@swift.org
https://lists.swift.org/mailman/listinfo/swift-evolution


(Slava Pestov) #3

Overload resolution has a lot of heuristics, but it’s not magic. It simply doesn’t know how to handle this case.

I’d be in favor of consolidating and simplifying the overload resolution rules, with the goal of disambiguating common cases that are currently ambiguous. We might even be able to do that without breaking too much user code, since a lot of the rules there were put in place to handle specific situations that came up in the standard library.

However adding more heuristics to handle specific examples is a -1 from me. :slight_smile:

Slava

···

On Mar 16, 2017, at 7:38 PM, Jaden Geller via swift-evolution <swift-evolution@swift.org> wrote:

I would’ve expected overload resolution to pick the “more specific” one in this case without needing any additional constraints… :thinking:

On Mar 16, 2017, at 6:40 PM, Robert Bennett via swift-evolution <swift-evolution@swift.org> wrote:

Hello,

This discussion sort of fizzled out when the topic was first introduced. Joe Groff had asked the following:

Do you have a concrete example where you need this? It'd be good to know whether the types are ambiguous due to type checker bugs, or whether there's a principle by which they could be naturally ordered.

There is an example of this ordering that I stumbled upon recently. Suppose I wish to extend `Array` with a `uniques()` function that returns an array containing the unique elements of `self`. For performance reasons, I would first write a method for arrays with Hashable elements, so that I could check for uniqueness in constant time per element.

extension Array where Element: Hashable {
  func uniques() -> [Element] {
    var seen: Set<Element> = []
    var uniq: [Element] = []
    
    for e in self {
      if !seen.contains(e) {
        seen.insert(e)
        uniq.append(e)
      }
    }
    
    return uniq
  }
}

However I would still like to have a `uniques()` method for arrays whose elements are merely Equatable, and I'm willing to take the performance cost of O(n) lookup per element.

extension Array where Element: Equatable {
  func uniques() -> [Element] {
    var uniq: [Element] = []
    
    for e in self {
      if !uniq.contains(e) {
        uniq.append(e)
      }
    }
    
    return uniq
  }
}

However, there is a problem, which is that elements that are Hashable are also Equatable, and so there is ambiguity when calling this method:

// error: ambiguous use of 'uniques()'
print([1,2,3,1,2,4,5,1,2,3,4,5].uniques())

If I could add `Element != Hashable` to the second extension, there would be no ambiguity.

FWIW replacing Array with Collection and Element with Iterator.Element fixes the error. The first extension (the one for Hashables) is called. I'm not sure why it is ambiguous in one case and not the other.

_______________________________________________
swift-evolution mailing list
swift-evolution@swift.org
https://lists.swift.org/mailman/listinfo/swift-evolution

_______________________________________________
swift-evolution mailing list
swift-evolution@swift.org
https://lists.swift.org/mailman/listinfo/swift-evolution


(Jaden Geller) #4

Overload resolution has a lot of heuristics, but it’s not magic. It simply doesn’t know how to handle this case.

I’d be in favor of consolidating and simplifying the overload resolution rules, with the goal of disambiguating common cases that are currently ambiguous. We might even be able to do that without breaking too much user code, since a lot of the rules there were put in place to handle specific situations that came up in the standard library.

Do you think there’s a simplification of the rules that would also better handle most cases? I definitely found overload resolution to be confusing topic when I first learned Swift (and still today tbh).

···

On Mar 16, 2017, at 8:27 PM, Slava Pestov <spestov@apple.com> wrote:

However adding more heuristics to handle specific examples is a -1 from me. :slight_smile:

Slava

On Mar 16, 2017, at 7:38 PM, Jaden Geller via swift-evolution <swift-evolution@swift.org> wrote:

I would’ve expected overload resolution to pick the “more specific” one in this case without needing any additional constraints… :thinking:

On Mar 16, 2017, at 6:40 PM, Robert Bennett via swift-evolution <swift-evolution@swift.org> wrote:

Hello,

This discussion sort of fizzled out when the topic was first introduced. Joe Groff had asked the following:

Do you have a concrete example where you need this? It'd be good to know whether the types are ambiguous due to type checker bugs, or whether there's a principle by which they could be naturally ordered.

There is an example of this ordering that I stumbled upon recently. Suppose I wish to extend `Array` with a `uniques()` function that returns an array containing the unique elements of `self`. For performance reasons, I would first write a method for arrays with Hashable elements, so that I could check for uniqueness in constant time per element.

extension Array where Element: Hashable {
  func uniques() -> [Element] {
    var seen: Set<Element> = []
    var uniq: [Element] = []
    
    for e in self {
      if !seen.contains(e) {
        seen.insert(e)
        uniq.append(e)
      }
    }
    
    return uniq
  }
}

However I would still like to have a `uniques()` method for arrays whose elements are merely Equatable, and I'm willing to take the performance cost of O(n) lookup per element.

extension Array where Element: Equatable {
  func uniques() -> [Element] {
    var uniq: [Element] = []
    
    for e in self {
      if !uniq.contains(e) {
        uniq.append(e)
      }
    }
    
    return uniq
  }
}

However, there is a problem, which is that elements that are Hashable are also Equatable, and so there is ambiguity when calling this method:

// error: ambiguous use of 'uniques()'
print([1,2,3,1,2,4,5,1,2,3,4,5].uniques())

If I could add `Element != Hashable` to the second extension, there would be no ambiguity.

FWIW replacing Array with Collection and Element with Iterator.Element fixes the error. The first extension (the one for Hashables) is called. I'm not sure why it is ambiguous in one case and not the other.

_______________________________________________
swift-evolution mailing list
swift-evolution@swift.org
https://lists.swift.org/mailman/listinfo/swift-evolution

_______________________________________________
swift-evolution mailing list
swift-evolution@swift.org
https://lists.swift.org/mailman/listinfo/swift-evolution


(Slava Pestov) #5

Overload resolution has a lot of heuristics, but it’s not magic. It simply doesn’t know how to handle this case.

I’d be in favor of consolidating and simplifying the overload resolution rules, with the goal of disambiguating common cases that are currently ambiguous. We might even be able to do that without breaking too much user code, since a lot of the rules there were put in place to handle specific situations that came up in the standard library.

Do you think there’s a simplification of the rules that would also better handle most cases? I definitely found overload resolution to be confusing topic when I first learned Swift (and still today tbh).

I’m as confused as you are. We don’t even have a good writeup of the existing rules anywhere.

Slava

···

On Mar 16, 2017, at 8:36 PM, Jaden Geller <jaden.geller@gmail.com> wrote:

On Mar 16, 2017, at 8:27 PM, Slava Pestov <spestov@apple.com> wrote:

However adding more heuristics to handle specific examples is a -1 from me. :slight_smile:

Slava

On Mar 16, 2017, at 7:38 PM, Jaden Geller via swift-evolution <swift-evolution@swift.org> wrote:

I would’ve expected overload resolution to pick the “more specific” one in this case without needing any additional constraints… :thinking:

On Mar 16, 2017, at 6:40 PM, Robert Bennett via swift-evolution <swift-evolution@swift.org> wrote:

Hello,

This discussion sort of fizzled out when the topic was first introduced. Joe Groff had asked the following:

Do you have a concrete example where you need this? It'd be good to know whether the types are ambiguous due to type checker bugs, or whether there's a principle by which they could be naturally ordered.

There is an example of this ordering that I stumbled upon recently. Suppose I wish to extend `Array` with a `uniques()` function that returns an array containing the unique elements of `self`. For performance reasons, I would first write a method for arrays with Hashable elements, so that I could check for uniqueness in constant time per element.

extension Array where Element: Hashable {
  func uniques() -> [Element] {
    var seen: Set<Element> = []
    var uniq: [Element] = []
    
    for e in self {
      if !seen.contains(e) {
        seen.insert(e)
        uniq.append(e)
      }
    }
    
    return uniq
  }
}

However I would still like to have a `uniques()` method for arrays whose elements are merely Equatable, and I'm willing to take the performance cost of O(n) lookup per element.

extension Array where Element: Equatable {
  func uniques() -> [Element] {
    var uniq: [Element] = []
    
    for e in self {
      if !uniq.contains(e) {
        uniq.append(e)
      }
    }
    
    return uniq
  }
}

However, there is a problem, which is that elements that are Hashable are also Equatable, and so there is ambiguity when calling this method:

// error: ambiguous use of 'uniques()'
print([1,2,3,1,2,4,5,1,2,3,4,5].uniques())

If I could add `Element != Hashable` to the second extension, there would be no ambiguity.

FWIW replacing Array with Collection and Element with Iterator.Element fixes the error. The first extension (the one for Hashables) is called. I'm not sure why it is ambiguous in one case and not the other.

_______________________________________________
swift-evolution mailing list
swift-evolution@swift.org
https://lists.swift.org/mailman/listinfo/swift-evolution

_______________________________________________
swift-evolution mailing list
swift-evolution@swift.org
https://lists.swift.org/mailman/listinfo/swift-evolution


#6

Agreed, I'm fine with a way of achieving this without T != Type. I suppose I should have made the subject "Fix Swift's type checker in this particular case".

I still have trouble figuring out *how* it can correctly handle ambiguity in protocol extensions but be unable to in a "true" (constructible) type extension. Does this warrant a bug report of some kind?

···

On Mar 16, 2017, at 11:27 PM, Slava Pestov <spestov@apple.com> wrote:

Overload resolution has a lot of heuristics, but it’s not magic. It simply doesn’t know how to handle this case.

I’d be in favor of consolidating and simplifying the overload resolution rules, with the goal of disambiguating common cases that are currently ambiguous. We might even be able to do that without breaking too much user code, since a lot of the rules there were put in place to handle specific situations that came up in the standard library.

However adding more heuristics to handle specific examples is a -1 from me. :slight_smile:

Slava

On Mar 16, 2017, at 7:38 PM, Jaden Geller via swift-evolution <swift-evolution@swift.org> wrote:

I would’ve expected overload resolution to pick the “more specific” one in this case without needing any additional constraints… :thinking:

On Mar 16, 2017, at 6:40 PM, Robert Bennett via swift-evolution <swift-evolution@swift.org> wrote:

Hello,

This discussion sort of fizzled out when the topic was first introduced. Joe Groff had asked the following:

Do you have a concrete example where you need this? It'd be good to know whether the types are ambiguous due to type checker bugs, or whether there's a principle by which they could be naturally ordered.

There is an example of this ordering that I stumbled upon recently. Suppose I wish to extend `Array` with a `uniques()` function that returns an array containing the unique elements of `self`. For performance reasons, I would first write a method for arrays with Hashable elements, so that I could check for uniqueness in constant time per element.

extension Array where Element: Hashable {
  func uniques() -> [Element] {
    var seen: Set<Element> = []
    var uniq: [Element] = []
    
    for e in self {
      if !seen.contains(e) {
        seen.insert(e)
        uniq.append(e)
      }
    }
    
    return uniq
  }
}

However I would still like to have a `uniques()` method for arrays whose elements are merely Equatable, and I'm willing to take the performance cost of O(n) lookup per element.

extension Array where Element: Equatable {
  func uniques() -> [Element] {
    var uniq: [Element] = []
    
    for e in self {
      if !uniq.contains(e) {
        uniq.append(e)
      }
    }
    
    return uniq
  }
}

However, there is a problem, which is that elements that are Hashable are also Equatable, and so there is ambiguity when calling this method:

// error: ambiguous use of 'uniques()'
print([1,2,3,1,2,4,5,1,2,3,4,5].uniques())

If I could add `Element != Hashable` to the second extension, there would be no ambiguity.

FWIW replacing Array with Collection and Element with Iterator.Element fixes the error. The first extension (the one for Hashables) is called. I'm not sure why it is ambiguous in one case and not the other.

_______________________________________________
swift-evolution mailing list
swift-evolution@swift.org
https://lists.swift.org/mailman/listinfo/swift-evolution

_______________________________________________
swift-evolution mailing list
swift-evolution@swift.org
https://lists.swift.org/mailman/listinfo/swift-evolution


(Joe Groff) #7

There is a general guideline that more specific things should be favored over less specific ones, which I'm surprised isn't applying here. (I agree we should have real *rules* of course.)

-Joe

···

On Mar 16, 2017, at 8:27 PM, Slava Pestov via swift-evolution <swift-evolution@swift.org> wrote:

Overload resolution has a lot of heuristics, but it’s not magic. It simply doesn’t know how to handle this case.

I’d be in favor of consolidating and simplifying the overload resolution rules, with the goal of disambiguating common cases that are currently ambiguous. We might even be able to do that without breaking too much user code, since a lot of the rules there were put in place to handle specific situations that came up in the standard library.

However adding more heuristics to handle specific examples is a -1 from me. :slight_smile:


(Ben Cohen) #8

Overload resolution has a lot of heuristics, but it’s not magic. It simply doesn’t know how to handle this case.

I think this might this just be a bug in overload resolution that’s since been fixed... ToT compiler resolves this as I’d expect, picking the where Hashable version over the where Equatable one unambiguously.

···

On Mar 17, 2017, at 3:27 AM, Slava Pestov via swift-evolution <swift-evolution@swift.org> wrote:

I’d be in favor of consolidating and simplifying the overload resolution rules, with the goal of disambiguating common cases that are currently ambiguous. We might even be able to do that without breaking too much user code, since a lot of the rules there were put in place to handle specific situations that came up in the standard library.

However adding more heuristics to handle specific examples is a -1 from me. :slight_smile:

Slava

On Mar 16, 2017, at 7:38 PM, Jaden Geller via swift-evolution <swift-evolution@swift.org> wrote:

I would’ve expected overload resolution to pick the “more specific” one in this case without needing any additional constraints… :thinking:

On Mar 16, 2017, at 6:40 PM, Robert Bennett via swift-evolution <swift-evolution@swift.org> wrote:

Hello,

This discussion sort of fizzled out when the topic was first introduced. Joe Groff had asked the following:

Do you have a concrete example where you need this? It'd be good to know whether the types are ambiguous due to type checker bugs, or whether there's a principle by which they could be naturally ordered.

There is an example of this ordering that I stumbled upon recently. Suppose I wish to extend `Array` with a `uniques()` function that returns an array containing the unique elements of `self`. For performance reasons, I would first write a method for arrays with Hashable elements, so that I could check for uniqueness in constant time per element.

extension Array where Element: Hashable {
  func uniques() -> [Element] {
    var seen: Set<Element> = []
    var uniq: [Element] = []
    
    for e in self {
      if !seen.contains(e) {
        seen.insert(e)
        uniq.append(e)
      }
    }
    
    return uniq
  }
}

However I would still like to have a `uniques()` method for arrays whose elements are merely Equatable, and I'm willing to take the performance cost of O(n) lookup per element.

extension Array where Element: Equatable {
  func uniques() -> [Element] {
    var uniq: [Element] = []
    
    for e in self {
      if !uniq.contains(e) {
        uniq.append(e)
      }
    }
    
    return uniq
  }
}

However, there is a problem, which is that elements that are Hashable are also Equatable, and so there is ambiguity when calling this method:

// error: ambiguous use of 'uniques()'
print([1,2,3,1,2,4,5,1,2,3,4,5].uniques())

If I could add `Element != Hashable` to the second extension, there would be no ambiguity.

FWIW replacing Array with Collection and Element with Iterator.Element fixes the error. The first extension (the one for Hashables) is called. I'm not sure why it is ambiguous in one case and not the other.

_______________________________________________
swift-evolution mailing list
swift-evolution@swift.org
https://lists.swift.org/mailman/listinfo/swift-evolution

_______________________________________________
swift-evolution mailing list
swift-evolution@swift.org
https://lists.swift.org/mailman/listinfo/swift-evolution

_______________________________________________
swift-evolution mailing list
swift-evolution@swift.org
https://lists.swift.org/mailman/listinfo/swift-evolution


(Slava Pestov) #9

Agreed, I'm fine with a way of achieving this without T != Type. I suppose I should have made the subject "Fix Swift's type checker in this particular case".

I still have trouble figuring out *how* it can correctly handle ambiguity in protocol extensions but be unable to in a "true" (constructible) type extension. Does this warrant a bug report of some kind?

If you’re feeling adventurous, take a look at lib/Sema/CSRanking.cpp. It appears to have some special case logic for handling protocol extensions in particular.

Slava

···

On Mar 16, 2017, at 8:32 PM, Robert Bennett <rltbennett@icloud.com> wrote:

On Mar 16, 2017, at 11:27 PM, Slava Pestov <spestov@apple.com> wrote:

Overload resolution has a lot of heuristics, but it’s not magic. It simply doesn’t know how to handle this case.

I’d be in favor of consolidating and simplifying the overload resolution rules, with the goal of disambiguating common cases that are currently ambiguous. We might even be able to do that without breaking too much user code, since a lot of the rules there were put in place to handle specific situations that came up in the standard library.

However adding more heuristics to handle specific examples is a -1 from me. :slight_smile:

Slava

On Mar 16, 2017, at 7:38 PM, Jaden Geller via swift-evolution <swift-evolution@swift.org> wrote:

I would’ve expected overload resolution to pick the “more specific” one in this case without needing any additional constraints… :thinking:

On Mar 16, 2017, at 6:40 PM, Robert Bennett via swift-evolution <swift-evolution@swift.org> wrote:

Hello,

This discussion sort of fizzled out when the topic was first introduced. Joe Groff had asked the following:

Do you have a concrete example where you need this? It'd be good to know whether the types are ambiguous due to type checker bugs, or whether there's a principle by which they could be naturally ordered.

There is an example of this ordering that I stumbled upon recently. Suppose I wish to extend `Array` with a `uniques()` function that returns an array containing the unique elements of `self`. For performance reasons, I would first write a method for arrays with Hashable elements, so that I could check for uniqueness in constant time per element.

extension Array where Element: Hashable {
  func uniques() -> [Element] {
    var seen: Set<Element> = []
    var uniq: [Element] = []
    
    for e in self {
      if !seen.contains(e) {
        seen.insert(e)
        uniq.append(e)
      }
    }
    
    return uniq
  }
}

However I would still like to have a `uniques()` method for arrays whose elements are merely Equatable, and I'm willing to take the performance cost of O(n) lookup per element.

extension Array where Element: Equatable {
  func uniques() -> [Element] {
    var uniq: [Element] = []
    
    for e in self {
      if !uniq.contains(e) {
        uniq.append(e)
      }
    }
    
    return uniq
  }
}

However, there is a problem, which is that elements that are Hashable are also Equatable, and so there is ambiguity when calling this method:

// error: ambiguous use of 'uniques()'
print([1,2,3,1,2,4,5,1,2,3,4,5].uniques())

If I could add `Element != Hashable` to the second extension, there would be no ambiguity.

FWIW replacing Array with Collection and Element with Iterator.Element fixes the error. The first extension (the one for Hashables) is called. I'm not sure why it is ambiguous in one case and not the other.

_______________________________________________
swift-evolution mailing list
swift-evolution@swift.org
https://lists.swift.org/mailman/listinfo/swift-evolution

_______________________________________________
swift-evolution mailing list
swift-evolution@swift.org
https://lists.swift.org/mailman/listinfo/swift-evolution