swift - Why can we not cast to protocol types with associated types but achieve the same effect using generics?

Question

Consider this code:

extension Collection {
    func foo() -> Int {
        if self.first is Collection {
            return (self.first as! Collection).underestimatedCount // ERROR
        }
        else {
            return self.underestimatedCount
        }
    }
}

We get the dreaded and apparently widely puzzling:

protocol 'Collection' can only be used as a generic constraint because it has Self or associated type requirements.

However, this happily compiles:

func foo<C: Collection>(_ c: C) -> Int where C.Iterator.Element: Collection {
    if let first = c.first {
        return first.underestimatedCount // *
    } else {
        return c.underestimatedCount
    }
}

Why?!

In particular, the compiler does not know in * how the associated types of (the type of) first have been realized; it only gets the promise that they have been (because any object of type Collection has to realize them). This same guarantee is there in the first example! So why does the compiler complain about one but not the other?

My question is: at line *, what does the compiler know that it does not in line ERROR?

Answer 1

Protocol-typed values are represented using an 'existential container' (see this great WWDC talk on them; or on Youtube), which consists of a value-buffer of fixed size in order to store the value (if the value size exceeds this, it'll heap allocate), a pointer to the protocol witness table in order to lookup method implementations and a pointer to the value witness table in order to manage the lifetime of the value.

Unspecialised generics use pretty much the same format (I go into this in slightly more depth in this Q&A) – when they're called, pointers to the protocol and value witness tables are passed to the function, and the value itself is stored locally inside the function using a value-buffer, which will heap allocate for values larger than that buffer.

Therefore, because of the sheer similarity in how these are implemented, we can draw the conclusion that not being able to talk in terms of protocols with associated types or Self constraints outside of generics is just a current limitation of the language. There's no real technical reason why it's not possible, it just hasn't been implemented (yet).

Here's an excerpt from the Generics Manifesto on "Generalized existentials", which discusses how this could work in practice:

The restrictions on existential types came from an implementation limitation, but it is reasonable to allow a value of protocol type even when the protocol has Self constraints or associated types. For example, consider IteratorProtocol again and how it could be used as an existential:

protocol IteratorProtocol {
  associatedtype Element
  mutating func next() -> Element?
}

let it: IteratorProtocol = ...
it.next()   // if this is permitted, it could return an "Any?", i.e., the existential that wraps the actual element

Additionally, it is reasonable to want to constrain the associated types of an existential, e.g., "a Sequence whose element type is String" could be expressed by putting a where clause into protocol<...> or Any<...> (per "Renaming protocol<...> to Any<...>"):

let strings: Any<Sequence where .Iterator.Element == String> = ["a", "b", "c"]

The leading . indicates that we're talking about the dynamic type, i.e., the Self type that's conforming to the Sequence protocol. There's no reason why we cannot support arbitrary where clauses within the Any<...>.

And from being able to type a value as a protocol with an associated type, it's but a short step to allow for type-casting to that given type, and thus allow something like your first extension to compile.