A more principled rule for filtering and scoring potential witnesses for associated type inference


(Joe Groff) #1

In https://github.com/apple/swift/pull/7136 I tried to address some issues with associated type inference's consideration of witnesses. A property of associated type inference that sets it apart from other name lookup and overload resolution problems is that the associated types needing inference haven't been settled yet. Therefore, we can't filter inference candidates from extensions by the usual "isExtensionUsable" criteria, since an extension may become usable depending on what associated types we infer. This also means that, when we have multiple inference candidates, we can't rank them by the usual "is decl more specialized" criterion, since the generic constraints of two inference candidates may be formally non-overlapping due to mutually exclusive constraints on those associated types. To address both of these cases, I hand-rolled logic to consider only the "Self" constraints for usability and ranking; while this covers many common use cases, I'm not sure this is a principled general solution to the problem. As the generics system gets more expressive, there will be more subtle cases involving constrained conformances where this class of problem arises. Furthermore, if some associated types are explicitly bound by typealiases or nested types defined in the conforming type, then we would be able to confidently filter out potential witnesses based on constraints on those explicit associated type bindings. It seems to me like there's some general concept lurking here of "undecided generic constraints" that we want to filter from generic signatures while doing associated type inference—if a requirement may or may not be matched depending on what associated type we pick, we shouldn't filter witness candidates by it for associated type inference, and we shouldn't rank overload specificity by it either. Does that make sense?

-Joe


(Douglas Gregor) #2

Yeah, that makes sense. I think this will become a whole lot easier to do properly if we were to start modeling inferred type witnesses as (global) type variables, so they get recorded in the AST. Then, these cases where we have an “undecided generic constraint” become obvious because it’s simply a constraint on a type variable that can’t be resolved until we bind the type variable.

  - Doug

···

On Jan 30, 2017, at 11:34 AM, Joe Groff <jgroff@apple.com> wrote:

In https://github.com/apple/swift/pull/7136 I tried to address some issues with associated type inference's consideration of witnesses. A property of associated type inference that sets it apart from other name lookup and overload resolution problems is that the associated types needing inference haven't been settled yet. Therefore, we can't filter inference candidates from extensions by the usual "isExtensionUsable" criteria, since an extension may become usable depending on what associated types we infer. This also means that, when we have multiple inference candidates, we can't rank them by the usual "is decl more specialized" criterion, since the generic constraints of two inference candidates may be formally non-overlapping due to mutually exclusive constraints on those associated types. To address both of these cases, I hand-rolled logic to consider only the "Self" constraints for usability and ranking; while this covers many common use cases, I'm not sure this is a principled general solution to the problem. As the generics system gets more expressive, there will be more subtle cases involving constrained conformances where this class of problem arises. Furthermore, if some associated types are explicitly bound by typealiases or nested types defined in the conforming type, then we would be able to confidently filter out potential witnesses based on constraints on those explicit associated type bindings. It seems to me like there's some general concept lurking here of "undecided generic constraints" that we want to filter from generic signatures while doing associated type inference—if a requirement may or may not be matched depending on what associated type we pick, we shouldn't filter witness candidates by it for associated type inference, and we shouldn't rank overload specificity by it either. Does that make sense?