Lifting the "Self or associated type" constraint on existentials


(Adrian Zubarev) #21

I love this. Thank you and Joe for sharing this, I coudln‘t come up with this

Just for my understanding, do you mean by ‚higher ranked types‘ ‚higher kinded typed‘?


(Karim Nassar) #22

Does this mean:

protocol Foo: Hashable { 
   ...
}

func something(with foo: Foo) { // <- This is OK ?
   return Set<Foo>([foo]) // but this will fail because the Hashable/Equatable members won't be accessible on the Foo existential?
}

(Joe Groff) #23

That's correct. By itself, this wouldn't address the issue of existentials not being Equatable/Hashable.


(Xiaodi Wu) #24

Hmm, lifting this constraint will be fantastic, but I think it would need to be done in conjunction with the implementation of a solid slate of diagnostics to educate users.

For example, users who really mean to write func f<T : P>(_: T) are often steered away from func f(_: P) by the impossibility of using an existential P, but without that limitation I can foresee users writing themselves into various tricky situations much further down the line.


(Nate Cook) #25

So the idea here is that you could use any protocol as a type, and when working with an instance of a protocol you could access any member that doesn't include Self or another associated type in its declaration? That is, with the Collection protocol we all know and love, you could write something like:

func hasAtLeastTwoElements(_ c: Collection) -> Bool {
    if c.isEmpty { return false }
    return c.count >= 2
}

But using methods like contains(where:), or subscripts, or for-in loops would still be disallowed, since they use the Element, Index, and Iterator associated types. Likewise, I could create a custom Equatable-inheriting protocol for a group of custom data types so that I could store them all in a single array, but I wouldn't be able to use == with the array's members or use Equatable-constrained array methods.

It feels a bit like this will make it harder to diagnose and help people fix problems in the right place, since they'll get an error message inside a function they're writing that they'll need to fix in the function's signature. Are there benefits of relaxing this constraint that would apply before we get all the way to generalized existentials?


(Joe Groff) #26

The benefits I see are:

  • It defines away some otherwise straightforward library evolution questions with protocols. Removing this constraint means that adding defaulted method or associated requirements to a protocol is always OK, since it can't interfere with existing uses of the protocol.
  • Even if it doesn't define away the need for manual type-erased containers, it allows for them to be written in a way that's easier for the compiler to optimize, and ABI-compatible with future generalized existentials, by wrapping the unconstrained existential type instead of boxing a value in a subclass or closure.
  • Some protocols may have associated types or contravariant requirements, but still have a useful subset of functionality that doesn't rely on those requirements.
  • Although you can't access the requirements on the existential directly, it is possible through the convolution of writing protocol extension methods to open the value inside and have full access to the protocol interface inside the protocol extension, and thereby wrap needed functionality in an existential-friend way.

(Slava Pestov) #27

You will be able to call methods that return Self, because those are erased to the existential type. This works today:

protocol Cloneable {
  func clone() -> Self
}

func foo(_ c: Cloneable) -> Cloneable {
  return c.clone()
}

Similarly, we could allow you to call methods that return associated types and erase them to their upper bounds.


(Jon Hull) #28

I'm definitely +1000 for taking steps in this direction...

Could you give an example of what this would look like? I have a bunch of type-erased types, and it would be nice to know the correct method for doing it once this change is made.

Is this predictable enough that the compiler could create some sort of thunk for doing it? What are the design/implementation obstacles that keep us from having a clean syntax to open things?


(David Sweeris) #29

+ all the 1s


(Greg Titus) #30

I agree that we'll need good diagnostics, but I think that lifting this constraint will actually be a good thing to help more people to understand what's going on. You hit the existing "self or associated type" error earlier, but I see a lot of questions about what it means and why this limitation exists on various forums.

Having a decent error message at point of use of a protocol method that involves a contravariant Self or an associated type can explain much better what the actual problem is.

So big +1 to this proposal.


(Thomas Krajacic) #31

Will this change be possible within the Swift 5 timeframe?


(Damian Malarczyk) #32

Would it be difficult to support this without fully implementing Generalized Existentials? Having to write type erased boxes is a bit of a hassle.


(Joe Groff) #33

Well, this is all predictable enough that the language and compiler ought to do it for you, in the fullness of time. You can wrap a more specific type-erasing container around the unconstrained existential by doing something like this:

protocol Foo {
  associatedtype Bar

  func foo(_: Bar) -> Bar
}

private extension Foo {
  // Forward to the foo method in an existential-accessible
  // way, asserting that the _Bar generic argument matches the
  // actual Bar associated type of the dynamic value
  func _fooThunk<_Bar>(_ bar: _Bar) -> _Bar {
    assert(_Bar.self == Bar.self)
    let result = foo(unsafeBitCast(bar, to: Bar.self))
    return unsafeBitCast(result, to: _Bar.self)
  }
}

struct AnyFoo<Bar>: Foo {
  private var _value: Foo

  init<F: Foo>(_ value: F) where F.Bar == Bar {
    self._value = value
  }
  
  func foo(_ bar: Bar) -> Bar {
    return self._value._fooThunk(bar)
  }
}

The Bar == _Bar assertion and unsafeBitCasts should optimize away, and in the future when we support Foo<.Bar == T> as a first-class existential type, it should have a compatible ABI with the unconstrained Foo existential, as well as this struct wrapper, since one-field structs have the same ABI as their one field. Because of the need for unsafe type casts, though, this is probably code you'd want a code generator to produce for you instead of writing out by hand.

The "open existential" operation exists in SIL as a general-purpose operation; however, our optimizers and code generation are not necessarily set up to handle the operation in full generality outside of the fixed patterns we emit as part of method calls. There's also no surface-level language design for expressing a generalized open existential operations; @Douglas_Gregor had a strawman syntax sketched out in his generics manifesto, but I hope we can come up with something a little bit more polished in the end (though perfect is the eternal enemy of good.)

For the brave, there is in fact a general _openExistential primitive hidden in the standard library you can play with, though I don't recommend using it in your code, since it may break or miscompile, and like all underscored things in the standard library, is subject to change without notice.


(John McCall) #34

I support lifting this restriction, but note that there are implementation reasons why lifting it might not be trivial. I've noticed a fair amount of code at the SIL level that seems to assume that an opened archetype is always the primary archetype, and IIRC opened archetypes still don't carry a generic environment, which will prevent IRGen from being able to follow requirement paths from the root metadata+conformance for an opened type.


(Joe Groff) #35

IIRC opened existentials do refer back to the protocol(s) of the existential they were opened from, which should be enough to reconstruct a generic environment given the limited existentials we currently support.


(John McCall) #36

Well, but not if you lift the restriction on there being only one archetype in the environment, I think. Maybe it works because the nesting relationships are right.


(Karl) #38

So we wouldn't be able to replace AnyHashable with a Hashable existential, but it could basically be a thin wrapper around one, right? Something like...

struct AnyHashable: Hashable {
  let val: Hashable

  func hash(into: inout Hasher) { val.hash(into: &hasher) }
  static func ==(lhs: AnyHashable, rhs: AnyHashable) -> Bool { return lhs.val._isEqual(to: rhs.val) }
}

extension Hashable {
  func _isEqual(to other: Hashable) -> Bool {
    guard let other = other as? Self else { return false }
    return self == other
  }
}

(Joe Groff) #39

AnyHashable also has some additional logic to deal with bridging, so that bridged types equate and hash interchangeably.


(Mox) #40

The current error about ”self or associated type” restriction is huge roadblock for new users trying make code work. It’s obscure, feels arbitrary and is hard to understand even when you try to read it up. Even if you would fail later (since generalized existentials are not there), at least with diagnostics you’d have better chance to understand the limitations, since it’s more specific problem. And there could be more exact workaround for that specific issue. So overall I think this is the step to right direction.


(Marc Palmer) #41

Yes please! I think I might cry for joy. I gather its not the whole story re: PAT usability issues but it sounds good to me.

I’m a pretty seasoned dev and I constantly hit limitations around PATs that i struggle to reason about so my default assumption is always that its best to avoid them. I have specific desires to extend protocols with PATs with derived protocol types that also use those PATs and have other generic functions able to match the base protocol type but then use “is” to check for a more specific subtype. I think this will solve this?