What Is Existentialmetatype in Swift

What does existential type mean in Swift?

An example of an existential type is given in the evolution proposal itself:

protocol Shape {
  func draw(to: Surface)
}

An example of using protocol Shape as an existential type would look like

func collides(with: any Shape) -> Bool

as opposed to using a generic argument Other:

func collides<Other: Shape>(with: Other) -> Bool

Important to note here that the Shape protocol is not an existential type by itself, only using it in "protocols-as-types" context as above "creates" an existential type from it. See this post from the member of Swift Core Team:

Also, protocols currently do double-duty as the spelling for existential types, but this relationship has been a common source of confusion.

Also, citing the Swift Generics Evolution article (I recommend reading the whole thing, which explains this in more details):

The best way to distinguish a protocol type from an existential type is to look at the context. Ask yourself: when I see a reference to a protocol name like Shape, is it appearing at a type level, or at a value level? Revisiting some earlier examples, we see:
func addShape<T: Shape>() -> T
// Here, Shape appears at the type level, and so is referencing the protocol type

var shape: any Shape = Rectangle()
// Here, Shape appears at the value level, and so creates an existential type

Deeper dive

Why is it called an "existential"? I never saw an unambiguous confirmation of this, but I assume that the feature is inspired by languages with more advanced type systems, e.g. consider Haskell's existential types:

class Buffer -- declaration of type class `Buffer` follows here

data Worker x y = forall b. Buffer b => Worker {
  buffer :: b, 
  input :: x, 
  output :: y
}

which is roughly equivalent to this Swift snippet (if we assume that Swift's protocols more or less represent Haskell's type classes):

protocol Buffer {}

struct Worker<X, Y> {
  let buffer: any Buffer
  let input: X
  let output: Y
}

Note that the Haskell example used forall quantifier here. You could read this as "for all types that conform to the Buffer type class ("protocol" in Swift) values of type Worker would have exactly the same types as long as their X and Y type parameters are the same". Thus, given

extension String: Buffer {}
extension Data: Buffer {}

values Worker(buffer: "", input: 5, output: "five") and Worker(buffer: Data(), input: 5, output: "five") would have exactly the same types.

This is a powerful feature, which allows things such as heterogenous collections, and can be used in a lot more places where you need to "erase" an original type of a value and "hide" it under an existential type. Like all powerful features it can be abused and can make code less type-safe and/or less performant, so should be used with care.

If you want even a deeper dive, check out Protocols with Associated Types (PATs), which currently can't be used as existentials for various reasons. There are also a few Generalized Existentials proposals being pitched more or less regularly, but nothing concrete as of Swift 5.3. In fact, the original Opaque Result Types proposal linked by the OP can solve some of the problems caused by use of PATs and significantly alleviates lack of generalized existentials in Swift.

What is an existential type?

When someone defines a universal type ∀X they're saying: You can plug in whatever type you want, I don't need to know anything about the type to do my job, I'll only refer to it opaquely as X.

When someone defines an existential type ∃X they're saying: I'll use whatever type I want here; you won't know anything about the type, so you can only refer to it opaquely as X.

Universal types let you write things like:

void copy<T>(List<T> source, List<T> dest) {
   ...
}

The copy function has no idea what T will actually be, but it doesn't need to know.

Existential types would let you write things like:

interface VirtualMachine<B> {
   B compile(String source);
   void run(B bytecode);
}

// Now, if you had a list of VMs you wanted to run on the same input:
void runAllCompilers(List<∃B:VirtualMachine<B>> vms, String source) {
   for (∃B:VirtualMachine<B> vm : vms) {
      B bytecode = vm.compile(source);
      vm.run(bytecode);
   }
}

Each virtual machine implementation in the list can have a different bytecode type. The runAllCompilers function has no idea what the bytecode type is, but it doesn't need to; all it does is relay the bytecode from VirtualMachine.compile to VirtualMachine.run.

Java type wildcards (ex: List<?>) are a very limited form of existential types.

Update: Forgot to mention that you can sort of simulate existential types with universal types. First, wrap your universal type to hide the type parameter. Second, invert control (this effectively swaps the "you" and "I" part in the definitions above, which is the primary difference between existentials and universals).

// A wrapper that hides the type parameter 'B'
interface VMWrapper {
   void unwrap(VMHandler handler);
}

// A callback (control inversion)
interface VMHandler {
   <B> void handle(VirtualMachine<B> vm);
}

Now, we can have the VMWrapper call our own VMHandler which has a universally-typed handle function. The net effect is the same, our code has to treat B as opaque.

void runWithAll(List<VMWrapper> vms, final String input)
{
   for (VMWrapper vm : vms) {
      vm.unwrap(new VMHandler() {
         public <B> void handle(VirtualMachine<B> vm) {
            B bytecode = vm.compile(input);
            vm.run(bytecode);
         }
      });
   }
}

An example VM implementation:

class MyVM implements VirtualMachine<byte[]>, VMWrapper {
   public byte[] compile(String input) {
      return null; // TODO: somehow compile the input
   }
   public void run(byte[] bytecode) {
      // TODO: Somehow evaluate 'bytecode'
   }
   public void unwrap(VMHandler handler) {
      handler.handle(this);
   }
}

Relation between Existential Container and struct instance which conform protocol

Preface: I don't know how much background knowledge you have, so I might over-explain to make sure my answer is clear.

Also, I'm doing this to the best of my ability, off by memory. I might mix up some details, but hopefully this answer could at least point you towards further reading.

See also:

https://stackoverflow.com/a/41490551/3141234
https://github.com/apple/swift/blob/main/docs/SIL.rst#id201

In Swift, protocols can be used "as a type", or as a generic constraint. The latter case looks like so:

protocol SomeProtocol {}
struct SomeConformerSmall: SomeProtocol {
    // No ivars
}
struct SomeConformerBig: SomeProtocol {
    let a, b, c, d, e, f, g: Int // Lots of ivars
}

func fooUsingGenerics<T: SomeProtocol>(_: T) {}

let smallObject = SomeConformerSmall()
let bigObject = SomeConformerBig()

fooUsingGenerics(smallObject)
fooUsingGenerics(bigObject)

The protocol is used as a constraint for type-checking at compile time, but nothing particularly special happens at runtime (for the most part). Most of the time, the compiler will produced monomorphized variants of the foo function, as if you had defined fooUsingGenerics(_: SomeConformerSmall) or fooUsingGenerics(_: SomeConformerBig) to begin with.

When a protocol is "used like a type", it would look like this:

func fooUsingProtcolExistential(_: SomeProtocol) {}

fooUsingGenerics(smallObject)
fooUsingGenerics(bigObject)

As you see, this function can be called using both smallObject and bigObject. The problem is that these two objects have different sizes. This is a problem: how will the compiler know how much stack space is necessary to allocate for the arguments of this function, if the arguments can be different sizes? It must do something to help fooUsingProtcolExistential accommodate that.

Existential containers are the solution. When you pass a value where a protocol type is expected, the Swift compiler will generate code that automagically boxes that value into an "existential container" for you. As currently defined, an existential container is 4 words in size:

The first word is a pointer to the Protocol Witness Table (more on this later)
The next three words are inline storage for the value.

When the value being stored is less than 3 words in size (e.g. SomeConformerSmall), the value is packed directly inline into that 3 word buffer. If the value is more than 3 words in size (e.g. SomeConformerSmall), a ARC-managed box is allocated on the heap, and the value is copied into there. A pointer to this box is then copied into the first word of the existential container (the last 2 words are unused, IIRC).

This introduces a new issue: suppose that fooUsingProtcolExistential wanted to forward along its parameter to another function. How should it pass the EC? fooUsingProtcolExistential doesn't know whether the EC contains a value-inline (in which case, passing the EC just entails copying its 4 words of memory), or heap-allocated (in which case, passing the EC also requires an ARC retain on that heap-allocated buffer).

To remedy this, the Protocol Witness Table contains a pointer to a Value Witness Table (VWT). Each VWT defines the a standard set of function pointers, that define how the EC can be allocated, copied, deleted, etc. Whenever a protocol existential needs to be manipulated in someway, the VWT defines exactly how to do so.

So now we have a constant-size container (which solves our heterogeneously-sized parameter passing problem), and a way to move the container around. What can we actually do with it?

Well at a minimum, values of this protocol type must at least define the required members (initializers, properties (stored or computed), functions and subscripts) that the protocol defines.

But each conforming type might implement these members in a different way. E.g. some struct might satisfy a method requirement by defining the method directly, but another class might satisfy it by inheriting the method from a superclass. Some might implement a property as a stored property, others as a computed property, etc.

Handling these incompatibilities is the primary purpose of the Protocol Witness Table. There's one of these tables per protocol conformance (e.g. one for SomeConformerSmall and one for SomeConformerBig). They contain a set of function pointers with point to the implementations of the protocols' requirements. While the pointed-to functions might be in different places, the PWT's layout is consistent for the protocol is conforms to. As a result, fooUsingProtcolExistential is able to look at the PWT of an EC, and use it to find the implementation of a protocol method, and call it.

So in short:

An EC contains a PWT and a value (inline or indirect)
A PWT points to a VWT

Swift Generalized Existentials

Are there any proposals or discussions currently present on introducing Generalized Existentials into Swift, what are the plans? If no, how can I participate and affect this?

It is a commonly requested feature, and there was already preliminary design effort on swift-evolution. But at this moment, the core team and the community are focusing on ABI stability affecting features, or what Lattner defines as "Swift 4 Phase 1".

You would definitely hear more about it when Phase 2 commences. Given its popularity, it is expected to be part of Swift 4.

If Swift was designed that way (with Associated Types, but without Generalized Existentials), maybe it implies some architectural shift. What am I expected to replace delegation pattern with?

You can use type-erased wrappers as a transitive solution. In general, it exploits the dynamic dispatch and the inheritance of classes to erase the type.

protocol Fancy {
    associatedtype Value
    var value: Value
}

struct FancyMatter<Value> {
    let value: Value
}

class AnyFancyBoxBase<P: FancyProtocol>: AnyFancyBox<P.Value> {
    let base: P
    override var value: P.Value { return base.value }
    init(_ base: P) { self.base = base }
}

class AnyFancyBox<Value> {
    var value: Value { fatalError() }
}

var box: AnyFancyBox<Int> = AnyFancyBoxBase(FancyMatter(1))

You may take a look at how the Standard Library implements type-erased wrappers.

Why does type(of:) return Metatype, rather than T.Type?

tl;dr: The behavior of type(of:) depends on whether T is existential or concrete, and the type system can't effectively reflect the actual return type syntactically, so it's handled directly in the type checking system. Metatype is specifically not bound in code to be the same as T so that the effective behavior can be specialized. Metatype and T are not necessarily related.

type(of:) is special in that its behavior differs depending on the type passed into it. Specifically, it has special behavior for existential types by being able to reach through the existential box to get the underlying type of the value passed in. For example:

func myType<T>(of value: T) -> T.Type {
    return T.self
}

protocol Foo {}
struct X: Foo {}

let x = X()
print(type(of: x), "vs.", myType(of: x)) // => X vs. X

let f: Foo = X()
print(type(of: f), "vs.", myType(of: f)) // => X vs. Foo

When given an existential type like Foo, a return type of T.Type could only return the metatype of the existential itself (i.e. Foo.self), as opposed to the metatype of the value inside of the existential container (X.self). So instead of returning T.Type, type(of:) returns an unrelated type Metadata which is bound to the correct type in the type checker itself. This is the edge case you were looking for:

My guess is that there is some edge case where type(of:) will return a completely unrelated type to T, but I have no idea what that is.

If you look in lib/Sema/TypeChecker.h, you can see some special semantics declarations for several stdlib function types:

/// Special-case type checking semantics for certain declarations.
enum class DeclTypeCheckingSemantics {
  /// A normal declaration.
  Normal,

  /// The type(of:) declaration, which performs a "dynamic type" operation,
  /// with different behavior for existential and non-existential arguments.
  TypeOf,

  /// The withoutActuallyEscaping(_:do:) declaration, which makes a nonescaping
  /// closure temporarily escapable.
  WithoutActuallyEscaping,

  /// The _openExistential(_:do:) declaration, which extracts the value inside
  /// an existential and passes it as a value of its own dynamic type.
  OpenExistential,
};

The key one here is TypeOf, which is indeed returned for functions with the @_semantics("typechecker.type(of:)") attribute you noted. (You can see how that attribute is checked in TypeChecker::getDeclTypeCheckingSemantics)

If you go looking for usages of TypeOf, there are two key locations in type-checking:

getTypeOfReferenceWithSpecialTypeCheckingSemantics which injects the type constraint in the type checker constraint system. type(of:) is handled here as an overload, because Metadata isn't actually bound; the constraint solver here applies an effective type checking constraint which constrains Metadata to be the actual type of value. The key here is that type(of:) is written in this way so that it would be an overload, and handled here.
ExprRewriter::finishApply which performs the actual expression rewriting in the AST to replace the return type with the effective actual type of the value

From (1):

// Proceed with a "DynamicType" operation. This produces an existential
// metatype from existentials, or a concrete metatype from non-
// existentials (as seen from the current abstraction level), which can't
// be expressed in the type system currently.

Pulling back some history — this was implemented back in commit 1889fde2284916e2c368c9c7cc87906adae9155b. The commit message from Joe is illuminating:

Resolve type(of:) by overload resolution rather than parse hackery.
type(of:) has behavior whose type isn't directly representable in Swift's type system, since it produces both concrete and existential metatypes. In Swift 3 we put in a parser hack to turn type(of: <expr>) into a DynamicTypeExpr, but this effectively made type(of:) a reserved name. It's a bit more principled to put Swift.type(of:) on the same level as other declarations, even with its special-case type system behavior, and we can do this by special-casing the type system we produce during overload resolution if Swift.type(of:) shows up in an overload set. This also lays groundwork for handling other declarations we want to ostensibly behave like normal declarations but with otherwise inexpressible types, viz. withoutActuallyEscaping from SE-0110.

Since then, as we can see from WithoutActuallyEscaping and OpenExistential, other special functions have been rewritten to take advantage of this.

Swift 5.7 - Make existential 'any' protocol conform to Hashable

Assuming we want to find a way of how to list [any Animal] but not "why this shit happens" :) (see corresponding WWDC22 session to find answer on second one)

Tested with Xcode 14b3 / iOS 16

demo

Let's jump into this hole...

There are two places of reported error in original code:

List(anAnimalList, 
                   id: \.self,     // << 1st place
            selection: $anAnimal   // << 2nd place
) { animal in
    Text("Animal")
}

1st place - because Animal is not identifiable and self relates to instance of concrete type, so we should not use \.self (because compiler will not be able to infer concrete type), but identify directly by \.id

So here is a possible fix for the first issue:

protocol Animal: Hashable, Identifiable {
    var id: UUID { get }
    var name: String { get }
}

struct Cow: Animal {
    let id = UUID()
    let name: String
}

struct Chicken: Animal {
    let id = UUID()
    let name: String
}

    var body: some View {
        VStack {
            List(anAnimalList, id: \.id) { animal in   // << no error !!
                Text("Animal: \(animal.name)")
            }
        }
    }

2nd place - now about selection; the story is the same, swift should know "concrete type of selection" or could be able "infer it from code", both are impossible at compile type, so instead trying to break the wall with a head, let's find a door...

A possible solution is to use for selection something known and concrete in the context... we've just added it above - the 'id'

So here a fix for second part

@State private var anAnimalID: UUID? // << here !!

var body: some View {
    VStack {
        List(anAnimalList, id: \.id, selection: $anAnimalID) { animal in
            Text("Animal: \(animal.name)")
        }
        if let animal = anAnimalList.first { $0.id == anAnimalID } {
            Text("Animal is \(animal.name)")
        }
    }
}

Test code on GitHub

Issue with Swift 5.7 existentials

The problem here is that body needs to be some specific type, so ProviderView needs to be some specific type (since body relies on that type). It can't change at runtime. So ProviderView can't be generic over its Provider if that's going to change at runtime.

That means that ProviderView.provider needs to be any Provider, not generic:

struct ProviderView: View {
    let provider: any Provider

    var body: some View {
        Text(String(describing: type(of: provider.get())))
    }
}

So that part is expected.

The problem you'll run into is that the current runtime can't quite handle this yet, and you'll get an error later:

// Runtime support for parameterized protocol types is only available in iOS 99.0.0 or newer
ProviderView(provider: s.stringProvider)

I do expect this to improve in later betas, though I encourage you to open a Feedback to track it.