Recent improvements to associated type inference

Associated type inference is one of those features that is easy to describe but becomes maddeningly complex once you get into the details. The basic idea is this. We have a protocol with an associated type:

protocol P1 {
  associatedtype A
  func f(_: A)
}

Now if we declare a conforming type, we ought to be able to omit the typealias A = Int below, because the implementation of f() already completely determines A:

struct S1: P1 {  // ok!
  func f(_: Int) {}
}

In some cases, it is certainly better to state type aliases explicitly, even if associated type inference could infer them. On the other hand, many standard library protocols, like collections and numerics, rely on associated type inference for "progressive disclosure". For example, a basic Collection conformance doesn't need to state any type aliases at all; Element and Index can be inferred from the subscript, and Iterator, SubSequence and Indices all have reasonable defaults.

I wanted to highlight some fixes in this area. I've kept the below examples "abstract" so they may look silly to the uninitiated. But if you've hit any of these problems before (and many of you certainly did), you'll immediately see ;-)

Inferring associated types from same-type requirements in protocols

Suppose we add a default implementation of P1.f():

extension P1 {
  func f(_: A) {}
}

Now we might declare a protocol that inherits from P1 and completely fixes A:

protocol P2: P1 where A == Int {}

A conforming type now doesn't need to declare either f() or A at all:

struct S2: P2 {}  // ok!

The above worked in Swift 5.9. The new feature is is that this also applies to abstract same-type requirements. Here is a new protocol:

protocol P3 {
  associatedtype A
  associatedtype B

  func f(_: A)
  func g(_: B)
}

extension P3 {
  func f(_: A) {}
}

protocol P4: P3 where A == B {}

struct S4: P4 {  // error on 5.9; ok on main
  func g(_: Int) {}
}

In the conformance of S4 to P4 above, we must have A == B == Int. The compiler is now smart enough to realize this.

Both the original feature and the enhanced inference were contributed by @anthonylatsis. The latter was behind an experimental flag because it exposed some existing compiler bugs at the time. It is now enabled by default. Thanks Anthony!

Avoiding cycles when inferred associated types referenced from concrete context

Now look at this protocol:

protocol P5 {
  associatedtype A

  func f1(_: A)
  func f2(_: A)
  func f3(_: A)
}

We can declare a conforming type:

struct S5: P5 {  // ok
  func f1(_: Int) {}
  func f2(_: Int) {}
  func f3(_: A) {}
}

Notice how the A in the parameter type of f3 refers to the inferred associated type Int. The above worked in 5.9. Now let's add an innocent little bit of code that gets type checked before the struct declaration:

let _ = S5().f1(3)

struct S5: P5 {
  func f1(_: Int) {}
  func f2(_: Int) {}
  func f3(_: A) {}  // error diagnosed here on 5.9; ok on main
}

We used to get a reference to invalid associated type above, whereas moving the let statement so that it appears after the struct declaration would fix it. Now both declaration orders type check properly.

This limitation was the root cause of various bogus diagnostics and compiler crashes when moving a conformance to another file, or building with WMO vs non-WMO, etc.

Superclass-constrained associated types

Since the dawn of time, you've been able to constrain a generic parameter to a superclass that was itself generic, for example

class MyClass<T> {}

func f<A: MyClass<B>, B: Equatable>(_: A, _: B) {}

The same thing in a protocol superficially appeared to work:

protocol P6 {
  associatedtype A
  associatedtype B: MyClass<A>
  func f(_: B)
}

However, attempting to declare a conforming type would previously hit trouble, and in practice only a non-generic superclass would work in every case. This is now fixed, so we can write this:

struct S6<A>: P6 {  // error on 5.9; ok on main
  func f(_: MyClass<A>) {}
}
51 Likes

I love this - not just these specific fixes, but this exposition on them. I'd love to see more posts like this in future.

19 Likes

@Slava_Pestov Thanks for this. All the cases reported in the post, Associatedtype not inferred?, are addressed, except when the associatedtype is used as the return value of a method.

For the following example code, Xcode 15.3RC is still giving me the two error messages. Changing T in S to Int makes the error messages go away.

protocol P {
  associatedtype T
  func foo(x: T) -> T
}

struct S: P { // ERROR: Type 'S' does not conform to protocol 'P'
  func foo(x: Int) -> T { return x } // ERROR: Reference to invalid associated type 'T' of type 'S'
}
1 Like

Yeah, that's still not supported. The occurrence of T in the type of the witness removes it from consideration entirely. We don't try to separately resolve the non-circular parts.

Three cheers for Slava! Nice fixes.

Thank you for blowing the dust off these past efforts, Slava. I never expected a smooth transition to the new implementation — there had to be latent bugs in old code and some unintended behavioral quirks we have come to rely on in Swift code. But at some point I began to realize it would only fix a small class of problems, and this disheartened me on one hand. I was not feeling confident enough to go for the general problem either. So I ultimately left this on the shelf in a semi-complete state and have been getting distracted by the endless amount and variety of other fun work available on the project ever since. That said, conformances are of major interest to me, and I am just as firm about making them my primary focus in the future.

1 Like