[Pitch] Associated Type Disambiguation

Evolution Pitches
,
1

Associated Type Disambiguation

Introduction

In 2016, @Noah_Blake pitched adding name-spacing to associated types. Back then, just as now, you can't use dot-syntax qualifiers to disambiguate same-named associated types:

protocol Foo {
    associatedtype Baz
}

protocol Bar {
    associatedtype Baz
}

struct Alice: Foo, Bar {
    typealias Foo.Baz = Int    // does not compile today: you can't use
    typealias Bar.Baz = String // dot-syntax to disambiguate here
}

For some of us, this may seem unexpected, since it's normal to disambiguate same-name collisions with dot-syntax like:

struct Foo {
    typealias Baz = Int
}

struct Bar {
    typealias Baz = String
}

struct Alice {
    let x: Foo.Baz
    let y: Bar.Baz
}

Obviously that's not the exact same situation, but the underlying issue is that when a type conforms to two protocols that each declare an associated type with the same name, Swift today forces a single witness to satisfy both. There is no way to say "this protocol's Output is A, but that protocol's Output is B," even though the two requirements are completely independent and are already stored separately at the ABI level (each conformance has its own witness table with its own slot).

This proposal lets a conforming type give distinct witnesses to same-named associated types from different protocols, using a protocol-qualified type alias, and lets call sites refer to a specific protocol's associated type unambiguously:

protocol Parser   { associatedtype Output }
protocol Renderer { associatedtype Output }

struct MarkdownEngine: Parser, Renderer {
    typealias Parser.Output   = MarkdownAST   // distinct …
    typealias Renderer.Output = HTML          // … witnesses
}

Motivation

Consider a markdown engine:

// From package "SyntaxKit":
public protocol Parser {
    associatedtype Output                       // the parse result
    func parse(_ text: String) throws -> Output
}

// From a completely unrelated package "RenderKit":
public protocol Renderer {
    associatedtype Output                       // the rendered artifact
    func render() -> Output
}

// In *your* app: a Markdown engine that is naturally both.
// But it doesn't compile...
struct MarkdownEngine: Parser, Renderer {
    typealias Parser.Output   = MarkdownAST     // parse(_:) -> MarkdownAST
    typealias Renderer.Output = HTML            // render()  -> HTML

    func parse(_ text: String) throws -> MarkdownAST { … }
    func render() -> HTML { … }
}

Parser.Output (an AST) and Renderer.Output (rendered HTML) are genuinely different concepts from unrelated packages that happen to choose the same name. The collision is pure coincidence, the two protocols have no relationship to one another, and you own neither package — so "just rename a requirement" is not an option. Note also that only the associated type collides: the value requirements parse(_:) and render() have distinct names and are witnessed normally.

Today this doesn't compile: you'd be forced to witness Output with a single type, breaking one conformance — or rename a requirement you don't control. With the feature, (MarkdownEngine as Parser).Output is MarkdownAST and (MarkdownEngine as Renderer).Output is HTML.

As @Douglas_Gregor noted on Swift GitHub issue SR-3329:

Unfortunately, I do think this is behaving as designed. To make this work without renaming the associated type Value, we'd need some other language feature to allow the associated type witness for Factory.Value to be equivalent to Dictionary<Key, Value>. This kind of disambiguation has been discussed on the Swift evolution list a few times, but no single proposal has gotten traction yet.

Hopefully we can get some traction, because the witnesses are already separate in the runtime: associated-type witnesses are stored per-conformance, so Parser's witness table has its own Output slot and Renderer's has its own. Allowing two different witnesses is therefore a source-level name-resolution problem, not a new runtime capability, and the implementation here does so without ABI impact or source breakage. (See PR link at top.)

This is explicitly not intended for protocols in a refinement relationship. When one protocol refines another and redeclares an associated type of the same name, that name resolves to a single witness via the existing override rules — and genuinely distinct concepts in such a hierarchy should keep distinct names. This proposal targets only coincidental collisions between independent protocols.

Proposed solution

Update the compiler to allow using dot-syntax to disambiguate typealiases to same-named associated types:

1. Protocol-qualified witness type aliases

Inside a conforming type, a type alias may name the protocol whose associated type it witnesses:

struct MarkdownEngine: Parser, Renderer {
    typealias Parser.Output   = MarkdownAST
    typealias Renderer.Output = HTML
}

These aliases do not conflict with each other (they share a base name by design), and each one binds only its protocol's requirement.

2. Disambiguated member type references

A member type reference can be qualified by the protocol it should be resolved through, written (X as P).Member:

func cache(engine: MarkdownEngine) {
    let ast:  (MarkdownEngine as Parser).Output   = …   // MarkdownAST
    let html: (MarkdownEngine as Renderer).Output = …   // HTML
}

Here, the base is a concrete type, so this works fine. For readability, (X as any P).Member is also accepted and avoids an existential-any warning on the protocol name.

However, a generic parameter constrained to more than one of the protocols collapses the associated types into one type, which the compiler warns about (see Limitations):

// This does NOT disambiguate — the compiler warns, and both are the same type:
func cache<T: Parser & Renderer>(_ engine: T) {
    let ast:  (T as any Parser).Output   = … // ⚠️ collapses to T.Output
    let html: (T as any Renderer).Output = … // ⚠️ same type as ast (which one is unspecified)
}

Note that the qualifier must name a protocol; any P is accepted, some P is not.

Fortunately, the intended solution for this is already provided by existing Swift. Simply give each protocol its own generic parameter, each constrained by a different one of the protocols:

// This works:
func cache<P: Parser, R: Renderer>(_ parser: P, _ renderer: R) {
    let ast:  P.Output = … // P's Parser.Output   (e.g. MarkdownAST)
    let html: R.Output = … // R's Renderer.Output (e.g. HTML)
}

cache(engine, engine)   // P = R = MarkdownEngine

Detailed design

  • Parsing. A type alias declaration accepts an optional protocol qualifier:
    typealias P.Name = T. The qualifying protocol may itself be written as a
    qualified name (e.g. Mod.P). The qualifier is stored on the TypeAliasDecl;
    the alias keeps its base name so that associated-type witness lookup can find
    it, but it is excluded from ordinary unqualified name lookup and from
    redeclaration checking. The alias may be declared either in the primary type
    declaration or in an extension; the same rules apply.

  • Witness resolution. When resolving the type witness for protocol P's
    associated type, a protocol-qualified alias naming P is used exclusively;
    qualified aliases naming other protocols are ignored for that requirement.

  • Member type grammar. (X as P).Member is a new type representation. For a
    concrete base it resolves to X's type witness for P's associated type.
    For an abstract type parameter it forms the dependent member type for P's
    associated type (but see Limitations).

  • Diagnostics. Referring to a member that the named protocol does not declare,
    or naming a non-protocol after as, is an error. See Limitations for the
    abstract-generic warning.

Source compatibility

Additive. The new typealias P.Name syntax is a parse error today, so no existing code uses it. Existing code that names T.Member under a single protocol is unaffected. The behavior is gated behind an experimental feature flag.

ABI compatibility

This proposal is additive and has no effect on ABI. Associated-type witnesses are already stored per-conformance, so distinct witnesses introduce no new mangling or runtime structures. Concrete disambiguation and the split-parameter idiom reuse existing mechanisms.

Limitations and future directions

Abstract disambiguation on a single type parameter

For a generic parameter T: Parser & Renderer, the type system canonicalizes T.Output to a single type: the requirement machine merges same-named associated types of one type parameter into one equivalence class (an emergent consequence of completing the rewrite rules [P].Name => [P:Name] against the conformance rules). As a result, (T as Parser).Output and (T as Renderer).Output denote the same type when written on one type parameter.

Keeping them distinct would require changing generic-signature canonicalization, which feeds name mangling and module serialization—i.e. an ABI-level change—and a prototype that simply dropped the merge violated the rewrite system's confluence invariant. This is left as future work.

Because this case is silent today, the compiler emits a warning when (T as P).Member is written on such a type parameter, recommending the split-parameter idiom:

warning: disambiguation of associated type 'Output' has no effect: 'T'
conforms to both 'Parser' and 'Renderer', whose 'Output' are merged into a
single type parameter; to keep them distinct, constrain each protocol with its
own generic parameter instead

Recommended pattern for generic code

To use both associated types from a single value in generic code, use the split-parameter pattern shown in Disambiguated member type references: give each protocol its own generic parameter and pass the value for both. The two associated types then live on two different type parameters and are never conflated. This requires no new language feature.

Implementation notes (experimental)

The implementation PR passes its new tests, with two known gaps:

  • The new syntax is currently parsed only by the C++ parser; the SwiftSyntax
    (ASTGen) parser does not yet understand it, so tests pass
    -disable-experimental-parser-round-trip.
  • The two witness aliases currently share a USR in symbol-graph output (the
    mangler ignores the qualifier); DocC/indexing would see a collision. Folding
    the qualifying protocol into the alias USR is a small follow-up.

Alternatives considered

  • Renaming one requirement—the status quo; pushes the awkward name onto
    every reader and writer forever, and is unavailable when you own neither
    protocol.
  • Spelling of the disambiguated reference. (X as P).Member reuses the
    familiar "view this through protocol P" reading of as. Alternatives such as
    T.P.Member, P.Member for T, or T[as: P].Member were considered;
    (X as P).Member was chosen because it parallels the existing as coercion,
    reads naturally for concrete and (where supported) abstract bases, and is
    straightforward to parse given the parenthesized base.
  • Full abstract (T as P).Member support—desirable but ABI-scale; see
    Limitations.
8 Likes
[Second review] SE-0516: `Iterable`
2

Again, as we discussed previously, this example can't motivate this feature because we absolutely do not intend for these two associated types to share the same name. Having distinct names for Iterator and IterableIterator is not a "workaround" for a missing language feature. For one, Sequence may eventually be re-parented on Iterable, so the Iterable.IterableIterator associated type would then also be Sequence.IterableIterator. These are simply two distinct associated types, which need two distinct names.

1 Like
3

You're right — I'll drop Sequence/Iterable as the motivating example. I conflated two different situations:

  1. Protocols in a (potential) refinement relationship, like Iterable and Sequence, where the iterators are genuinely distinct concepts. There, distinct names (Iterator vs IterableIterator) are the correct design, and — as you point out — if Sequence is later re-parented on Iterable, shared names would actively collapse two distinct concepts into one under the existing override rules. This feature is explicitly not for that case, and I'll add it as a non-goal.
  2. Independent protocols with no relationship that happen to pick the same associated-type name. That's the actual target: two libraries that each reasonably call something Element/Value/Iterator, and a third party conforms one type to both — frequently retroactively, owning neither protocol — so renaming a requirement isn't an option. Today the conflict silently forces a single witness for both; see the 9-year-old #45917, where Factory.Value collides with Dictionary.Value and the default implementation is used instead of the intended one. That's a correctness bug, not an ergonomic preference.

Will post the edited proposal shortly, thanks for the clarification.

4

A conformance like this would be unsound. There is a pretty fundamental assumption in the generics system that if a type parameter conforms to two protocols that both have an associated type with the same name (whether the protocols are related by inheritance or not), then those associated types must actually map to identical concrete types in the declarations of the conformances to the two protocols.

protocol P {
  associatedtype A
}

protocol Q {
  associatedtype A
}

func f<T: P & Q>(_: T) {
  … there is a single unique T.A here …
}
3 Likes
5

Yeah, that's the limitation I mentioned. It seems the conformance is unsound relative to the current behavior of the requirement machine. The types P.A and Q.A get merged into a single type deterministically. It picks one anchor by a fixed ordering (compareAssociatedTypes ) and silently discards the other witness. The merged static type keeps one witness while the discarded conformance's requirements still hand back the other at runtime, when you pass the dual-conforming type in as <T: P & Q>.

Ideally we could find a way in these cases where the same-named associated types are different, to detect the ambiguity, up-front, and emit an error—but from what I could tell, "detect and emit error instead of collapsing the types" cannot be layered on top of today's behavior. It seems to require replacing the merging behavior, which as you implied reaches pretty far down, and seemed like it would have ABI/source impact.

If that makes this pitch a non-starter that's fine, but I didn't know if there might be a creative solution to this, so I figured we could put this up for discussion and see.

In the current implementation, the merge happens in canonicalization, not name resolution. I verified this directly: I'd hoped that writing the types fully-qualified (T as P).A / (T as Q).A is the proposed syntax here for manual disambiguation in these situations. But I realized it's impossible due to the merge because they still collapse to the same T.A .

The ability to "force disambiguation with (T as P).A " only becomes meaningful once (T as P).A and (T as Q).A are actually distinct types. But that would only seem possible if the requirement machine didn't merge them. When I prototyped not adding the merge rule, the rewrite system aborted in RequirementMachine::verify—it lost confluence/unique normal forms, because those invariants are built around the merge. So making [P:A] and [Q:A] distinct soundly seems like a principled rework of how the rewrite system handles same-named associated symbols, not a suppression.

Hopefully something constructive might come from the discussion even if the pitched change is moot.

For example, I do feel the diagnostics could be improved, and maybe that's an alternate pitch/PR to work on. I noticed that when a type conforms to two protocols that independently declare a same-named associated type, the compiler silently merges them, and both failure modes are poor:

  • divergent witnesses → a baffling error that never names the cause, e.g. 'Bag.X' does not conform to 'XProtocol';
  • a single witness that satisfies both, a silent merge

Swift does give good diagnostics in protocol refinement—typealias overriding associated type 'Element' … is better expressed as a same-type constraint, and redeclaration of associated type … is better expressed as a 'where' clause. But the unrelated-protocol collision does not, which is the more surprising.

For example consider:

protocol Parser   { associatedtype Output; func parse()  -> Output }
protocol Renderer { associatedtype Output; func render() -> Output }

struct Engine: Parser, Renderer {
    func parse()  -> String { "ast"  }   // Parser.Output
    func render() -> String { "html" }   // Renderer.Output
}

Parser.Output and Renderer.Output — two associated types from two unrelated protocols — have been silently unified into one Engine.Output . Nothing in the build tells you this happened, or that you've permanently given up the ability to make them differ. Would you agree this should be a warning?

And if you try to make them differ and you get a misleading error:

struct Engine: Parser, Renderer {
    func parse()  -> String { "ast" }
    func render() -> Int    { 0 }        // wants a different Output
}

error: type 'Engine' does not conform to protocol 'Renderer'
note: protocol requires function 'render()' with type '() -> Engine.Output' (aka '() -> String');
add a stub for conformance
note: candidate has non-matching type '() -> Int'

If I follow the fixit, now it's happy and I have:

struct Engine: Parser, Renderer {
    func parse()  -> String { "ast" }
    func render() -> Int    { 0 }     
    func render() -> String { "0" } 
}

... which could be obviously misleading.

What do you think of an effort towards improving the diagnostics in these cases?

Thanks

1 Like
6

The right solution is to reject substitution maps with incompatible conformances at the call site, eg:

protocol P {
  associatedtype A
}

protocol Q {
  associatedtype A
}

struct G<T> {}

extension G: P where T: Hashable {
  typealias A = Bool
}

extension G: Q where T: Comparable {
  typealias A = Float
}

func f<T: P & Q>(_: T) {}

// all declarations up until here are good!

// but Int conforms to both Hashable and Comparable:

f(G<Int>())  // so an error must be diagnosed here

This is a known issue that I'd like to fix some day. However, it's a fairly involved fix that requires a good understanding of Part 4 in https://download.swift.org/docs/assets/generics.pdf, as well as the requirement minimization algorithm, which is not even documented yet.

1 Like
7

Although this is the current implementation, I'll remind you that this implicit merging behavior is itself unsound, and we will need to fix it at some point:

  • There is no way to guarantee that P.A and Q.A are bound to the same associated type if a type's conformances to P and Q come independently through different modules, and those two conformances come together in a third module that imports both conformances then spells P & Q
  • P or Q could gain a new associated type requirement through library evolution, with a retroactive default witness for A being applied to an existing type that doesn't match the existing A binding for the other protocol
2 Likes
8

My thinking too. One idea I had in terms of language syntax (not sure if it would help at all though) would be if the user has to specify which of the conformances should be collapsed to, rather than it being up to some hidden logic:

struct MarkdownEngine: Parser, Renderer {
    // Declare Parser.Output as the default for disambiguation
    default typealias Parser.Output  = MarkdownAST

    typealias Renderer.Output = HTML
}

func process<T: Parser & Renderer>(_ engine: T) {
   var output: T.Output? = nil // defaults to (T as Parser).Output
}

I'd hoped this could allow a happy path but so far did not find a way.

9

I'm not sure it's fixable without giving up something else, like recursive conformances, or restricting same-type requirements to be less general (Rust's approach here is the latter I think).

To resolve a type parameter like T.A.B.C that appears in a where clause, in today's semantic model, we cannot simply do a series of name lookups to resolve and check for ambiguity in T, then T.A, T.A.B, and T.A.B.C, because in general conformance requirements and same-type requirements can depend on each other. They go in a blender and get sorted out "at the same time". The end result is that we don't know that T.A might refer to two different associated type declarations until after their equivalence classes have been merged.

Here is an example of the inter-dependent requirement resolution behavior:

protocol P {
  associatedtype A: P
}

func f<T, U>(_: T, _: U) where T: P, T.A == U.A, U.A == U {}

Neither T: P, T.A == U.A nor T: P, U.A == U is valid in isolation, but together, they imply that T.A == U, and thus U: P, which is what makes U.A valid in the first place. But we could not have discovered that U.A "exists" without considering the same-type requirements that mention U.A.

The example looks contrived, but in fact if you spell it the other way (T.A == U, U.A == U) and print it in a module interface, we output the above, because it's more "canonical" according to the current rules.

This is the issue I mentioned here. The bad situation can be detected when you can see both conformances from the call site: [Pitch] Associated Type Disambiguation - #6 by Slava_Pestov

This might not be fixable.

1 Like
10

In that case let me share my findings from the spike on this, for what it might be worth (correct me if wrong):

  • No-merge seems like it would alter generic-signature canonicalization, ABI-sensitive.
  • Could require a source code fix for certain existing generic functions, requiring something like a where clause to keep compiling, e.g.:
// Existing function that might require a source fix after collapse
// behavior is removed:
func f<T: P & Q>(_: T) 
    where (T as Parser).Output == (Q as Parser).Output {
}
  • For a public/@inlinable/library-evolution API, that migration is an ABI break for that entry point. The question seems to become, might there be a way to enforce the old rules to maintain backwards compatibility in those cases?
  • For code that doesn't need a source change, it seemed to depend on whether bare T.A keeps the anchor's mangling. Today, every existing T.A under T: P & Q canonicalizes to the anchor associated type, and that's baked into existing mangled names (and .swiftmodules). If the no-merge design keeps bare T.A resolving to that same anchor (the "anchor-as-default" path), those manglings are preserved and unchanged source stays ABI-stable. If instead bare T.A becomes a hard error (forcing rewrites) or (as I described in a reply above) default typealias lets you pick a non-anchor default, then it seemed to me like the canonical type—and the mangling—would have to change. So it seems like unchanged code is "preserved iff the design pins bare T.A to today's anchor." (Unless there's a way to finesse it that was not obvious at the time I was looking.)
  • Or I could be completely wrong about all that, it's my first try to do something in the compiler arena.