2

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?

Raphael
  • 9,779
  • 5
  • 63
  • 94
  • All explanations for the quoted error I found browsing [SO] where basically saying "we don't know the values for the associated types, so how can we cast?". By this explanation, I don't think the second sample should compile, hence my question. – Raphael Jan 17 '17 at 11:21

1 Answers1

5

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.

Community
  • 1
  • 1
Hamish
  • 78,605
  • 19
  • 187
  • 280
  • Thank you, again. Summarized, protocol types are handled differently when they appear in existential vs generic form. Correct? (Good references!) – Raphael Jan 17 '17 at 15:19
  • After reading item 4 in the answer you link, overload resolution also seems to one of the things tripping me up. The basic rule of thumb "choose the closest-fitting implementation" seems violated there (Swift prefers non-generic over generic functions). – Raphael Jan 17 '17 at 15:23
  • 1
    @Raphael Unspecialised generics and protocol types are basically handled in the same way (the only difference being that generics don't use explicit existential containers, as consider a generic function with multiple parameters of type a generic placeholder `T` – the pointers to the protocol witness and value witness tables only need to be passed in once, not for each parameter). When it comes to *specialised* generic functions, obviously they are handled quite differently, as the parameters can just be passed in by value – and the callee will know the static concrete type. – Hamish Jan 17 '17 at 15:26
  • 1
    @Raphael Regarding the overload resolution – it's because Swift favours an explicit type annotation over a generic one. I agree that it is a bit counter-intuitive (as it can lead to the compiler choosing an `Any` overload over a suitably constrained generic one) – but can easily be remedied in most cases by just avoiding protocol typed parameters and using generic ones instead (this also lets you benefit from specialisation). – Hamish Jan 17 '17 at 15:33
  • I don't understand why we should be able to use protocols with `associatedtype` or `Self` requirements as specific types. Would this not go against Swift needing to resolve function lookups at compile time? E.g., `let arr: [Protocol] = [obj1, obj2]; arr.forEach { print($0.f()) }` where `f` is a requirement of `P` returning `Self`. How can the compiler resolve which type's `f` will be called in the `forEach` (or more importantly, which type will be returned by `f`)? This kind of lookup can only happen at runtime. – BallpointBen Feb 21 '17 at 21:25
  • @BallpointBen "*How can the compiler resolve which type's `f` will be called in the `forEach`*" – the call to `f` is dynamically dispatched via the protocol witness table for each element that it is called on (this doesn't have anything to do with associated types or `Self` requirements, this is currently how Swift handles method calls on protocol-typed values). Swift doesn't (nor can it) always statically dispatch method calls. – Hamish Feb 21 '17 at 21:30
  • 1
    Whoosh. Way over my head. Guess I'll have to watch that WWDC video. – BallpointBen Feb 21 '17 at 21:31