Test if a type conforms to a non-existential protocol

Well, I never did understand what you were up to there, after reading about 10 lines I had an idea and solved it a bit more simply:

And now I see that Nevin posted another simple solution that uses basically the same technique.

2 Likes

The technique I posted was developed to be able to open value(s) and actually use the conformance (if it exists). I didn’t think about whether a simpler approach exists when only need to detect the conformance without actually using it. Good to know that there is one.

All right, I’ve wrapped my head around your protocol opening system @anandabits, that’s pretty clever!

When I first tried to build a protocol opener following your pattern, I thought I was doing something wrong because it kept crashing. However, it turns out I just discovered a rough edge.

Specifically, if you take your struct that conforms to the opener protocol, and constrain its generic type (the proxy) to have non-trivial conformances on the associated types of its associated type (and provide corresponding constraints on the top-level call site), then the program compiles but the receive method crashes at runtime. Even attempting to print(self) crashes!

In my case, I was writing a struct to open collections as BidirectionalCollection, and the algorithm I chose to implement for my testing was “Find the longest suffix that 2 collections share, and return a tuple of the indices of the first element in that suffix from each collection.”

So I made my top-level call site have the constraint T: Collection where T.Element: Equatable, I set up my openers to test for BidirectionalCollection conformance, and I made my struct constrain its proxy with where Proxy.Proxied: Collection, Proxy.Proxied.Element: Equatable.

The whole thing compiled, and traversed through the trampoline, and reached the receive method, then crashed.

I actually had changed all the names of protocols and types and functions to help myself better comprehend what they did, so I was worried I might have inadvertently made a mistake.

But eventually I discovered that if I removed the Equatable constraint, added an equalBy predicate to the struct, and made the top-level call site pass in (==) for it, then it ran without crashing and successfully executed the algorithm on BidirectionalCollections, while returning nil for other collections.

I could also make it dynamically check for BidirectionalCollection where Element: Equatable, but I was hoping to make use of an existing known conformance to Equatable while dynamically checking for the other. Unfortunately that crashed.

@dabrahams, if you’re interested in how Matt’s dynamic opener works, I’ve distilled it down to something hopefully easier to explain. I actually eliminated his “trampoline” type entirely, though I will explain at the end why it’s useful to include.

For this exercise, let’s say we want to take a Numeric value, and if it actually conforms to SignedNumeric then negate it. So we’re dynamically dispatching based on a conformance we don’t know statically.

• • •

Part 1: Two short protocols

To start off, here’s the primary protocol:

protocol AttemptIfSigned {
  associatedtype Wrapped
  associatedtype Result
  func action<T: SignedNumeric>(_ t: T.Type) -> Result where T == Wrapped
}

Wrapped is the type we start with and want to dynamically dispatch, and Result is the result type of whatever we do with it. In our example they will be the same types, but I’ve left them both for completeness.

The action function signature represents the bulk of the cleverness, so let’s break it down. In order to call that function, we need to pass in a type which both conforms to SignedNumeric, and also equals Wrapped.

That means within the body of the action function, we are guaranteed that Wrapped conforms to SignedNumeric, hence we can do things like negate values of type Wrapped. Now we just need to find a way to call it.

That brings us to our second protocol:

protocol KnownSignedNumeric {
  static func performAction<T: AttemptIfSigned>(_ t: T) -> T.Result
}

The trick is that we will only ever conform to this protocol conditionally, when Wrapped conforms to SignedNumeric, and we will only ever call performAction with T matching the action we’re using.

Here’s how we call it:

extension AttemptIfSigned {
  func attemptAction() -> Result? {
    (Self.self as? KnownSignedNumeric.Type)?.performAction(self)
  }
}

The attemptAction function is our main entry-point. It’s what we’ll actually call when we want to dynamically attempt an action. And all it does is check whether we are KnownSignedNumeric, and if so pass our action to performAction.

Note that performAction is generic specifically to avoid an associated type on KnownSignedNumeric, so that we can cast to that protocol inside attemptAction.

Part 2: A little prep work

That’s it for the high-level setup, now we need to write a conforming type to represent the action we want. We’ll call it NegateIfSigned, but before we get to the type itself, let’s see how it conforms to KnownSignedNumeric:

extension NegateIfSigned: KnownSignedNumeric where Wrapped: SignedNumeric {
  static func performAction<T: AttemptIfSigned>(_ t: T) -> T.Result {
    (t as! Self).action(Wrapped.self) as! T.Result
  }
}

The constraint on this extension is where we establish that Wrapped conforms to SignedNumeric, which allows us to call action by passing in Wrapped.

To do so, we need to convert back and forth between T and Self, but that will always succeed because performAction is only ever called by passing in self.

(Matt uses as? here, but I switched to as! because it’s a programmer error if the types don’t match. Note that there’s only one call-site, and the types do match.)

So we see what’s happening now. First attemptAction tries to cast our action type to KnownSignedNumeric, and if that succeeds then it calls performAction, which uses our holistic knowledge that T and Self are the same type, in order to call through to the action.

Got all that?

Great!

Now we’re almost ready to write the actual action type we want. Unfortunately, if we write it the obvious way as NegateIfSigned<Wrapped>, then when we implement our action function the compiler will raise an error at the same-type constraint T == Wrapped.

So we have to use a little indirection, which is where our third and most trivial protocol comes into play, along with its one empty conforming type:

protocol ProxyProtocol { associatedType Wrapped }

enum Proxy<Wrapped>: ProxyProtocol {}

We literally only use that to appease the compiler.

Part 3: The action itself

At last we are prepared to write our action type, and it’s pretty simple as generic types go:

struct NegateIfSigned<P: ProxyProtocol>: AttemptIfSigned {
  typealias Wrapped = P.Wrapped
  typealias Result = Wrapped
  
  var x: Wrapped
  
  init<T>(_ x: T) where P == Proxy<T> {
    self.x = x
  }
  
  func action<T: SignedNumeric>(_ t: T.Type) -> Result where T == Wrapped {
    return -x
  }
}

The action method is straightforward, it just implements the protocol requirement and does whatever calculations we want under the condition that Wrapped conforms to SignedNumeric.

The initializer is a little sneaky though. We could make it just take a parameter of type Wrapped, but then there’s no way to infer the type of P and we’d always have to specify it. We don’t want to have to write NegateIfSigned<Proxy<Foo>>(x), after all.

…of course, if the compiler would have let us use Wrapped directly as the generic type parameter, then we wouldn’t need Proxy at all, and type inference would work with a non-generic initializer. Oh well.

Part 4: Usage example

At this point we’re done, and it works. We can make a convenience method if we want:

extension Numeric {
  func negatedIfSigned() -> Self {
    NegateIfSigned(self).attemptAction() ?? self
  }
}

That lets us take any Numeric value, and if its type conforms to SignedNumeric we’ll get its negation:

(1 as Int).negatedIfSigned()     // -1
(1 as UInt).negatedIfSigned()    // 1
(1 as Float).negatedIfSigned()   // -1.0

In other words, we can dynamically dispatch to SignedNumeric.

• • •

The strategy is broadly applicable:

  • We could put anything we want inside action, within the constraints we put on T.
  • We could put whatever constraints we want on T.
  • We could make our top-level entry point do whatever we want if attemptAction() returns nil.

For example, if we constrain T to BidirectionalCollection instead of (or in addition to!) SignedNumeric, then we can write a double-ended algorithm in action. And we can make our entry point on Collection use a slower single-ended fallback algorithm if the attemptAction() call returns nil.

We can also compose actions. We could make one that dynamically dispatches to BidirectionalCollection, and another that dynamically dispatches to SignedNumeric, and we can make use of the latter within our action for the former.

And of course, we can make as many different action types as we want with the same constraints. As in, we can write as many dynamically-dispatched BidirectionalCollection algorithms as we wish.

• • •

Part 5: Trampolines

That last point brings us to the “trampoline“ that I removed.

In our SignedNumeric example, we checked the constraints by using a conditional conformance on our action type. But if we have many action types with the same constraints, do they all need their own conditional conformances?

Heck no!

We can make an empty helper type whose only purpose is to check a specific set of constraints:

enum SignedMarker<A: AttemptIfSigned> {}

extension SignedMarker: KnownSignedNumeric where A.Wrapped: SignedNumeric {
  static func performAction<T: AttemptIfSigned>(_ t: T) -> T.Result {
    (t as! A).action(A.Wrapped.self) as! T.Result
  }
}

This will let us remove the conditional extension on our action type, just by changing Self.self to SignedMarker<Self>.self in the attemptAction() method.

However, I like to go a small step further and put the constraint check on the marker type as well:

extension SignedMarker {
  static func attempt(_ a: A) -> A.Result? {
    (self as? KnownSignedNumeric.Type)?.performAction(a)
  }
}

That lets us simplify the implementation of attemptAction(), which after all “shouldn’t” need to know the details of how the conformance is checked:

extension AttemptIfSigned {
  func attemptAction() -> Result? {
    SignedMarker.attempt(self)
  }
}

Essentially, the trampoline (what I’ve called SignedMarker) makes it easier to implement action types, because they only need the main declaration now, not the conditional conformance.

• • •

So that’s the, uh, “quick” overview of how it works.

I will note that Matt’s implementation actually has one even higher level, where it starts from Any. That becomes important when the action being implemented takes multiple inputs of the same type but the call-site doesn’t have that information.

On the other hand, if your call-site will be generic and can thus guarantee the inputs are all of the same type T (whatever it may be), and you just need to check for certain constraints, then it isn’t necessary to start from Any.

8 Likes

Is that a compiler bug?

Thanks for your explanation, Nevin! I'm looking forward to digging into it, but I have another dissertation to read and respond to first…

2 Likes

I’m not sure, probably?

However, while playing around with things, I did find a bug where seemingly-valid Swift code crashes the compiler (specifically, both swift and SourceKitService unexpectedly quit). I haven’t reported it yet since I’m still on Xcode 11.3.1 / Swift 5.1.3 and not sure if it’s been fixed in newer versions.

As far as I can tell this is a minimal example, since if I try to reduce it further it stops crashing the compiler:

protocol P { associatedtype A }
enum E<A>: P {}

struct S<G: P> where G.A: Numeric {
  typealias N = G.A
  init<T>(_ n: N) where G == E<T> {}
}

// Uncomment to crash:
//func foo() { S(1) }

Edit: I just reported this compiler-crasher as SR-12670. I have not yet reported the runtime crash bug.

OK, so I went through the whole description, and it seemed… awful complicated. Then I wrote this to demonstrate some of the same capabilities more simply. Am I missing something that Matt's approach allows but mine doesn't?

[I'm disappointed to note that none of these techniques optimize well, even when all the information is available to the compiler statically.]

3 Likes

FWIW, this appears to have been "fixed" (meaning it no longer crashes; I haven't tried to decipher if it does the right thing or not) on master: Compiler Explorer

1 Like

Does your method allow one to write both lastIndexIfBidirectional and lastIndexOfNegativeIfBidirectionalWhereElementIsNumericAndComparable?

It seems to me that the conditional conformances on Dispatch would overlap.

Edit: Nevermind, I see now the conformances would be to separate protocols.

• • •

Also, and this isn’t a functionality difference, but for the UX of developers, Matt’s version allows actions to be written separately, whereas yours appears to require all actions for a given constraint to be placed in a single constrained extension on Dispatch.

That also means yours necessarily makes Dispatch visible to the programmer, they often must write at least one force-cast, and they could easily call apply with mismatched types.

Matt’s version allows, for any particular set of constraints, both the trampoline (SignedMarker) and the helper protocol (KnownSignedNumeric) to be private, meaning in particular the force-casts in performAction are only implemented once, privately, with identical copy-and-paste form for each set of constraints.

Then developers can write their own action types, and the only way to use them is by calling attemptAction which guarantees the same-type requirement cannot possibly be violated.

Thanks for your explanations, Nevin!

I don't think so; this works fine.

extension Dispatch : BidirectionalCollectionDispatch
    where Model: BidirectionalCollection
{
  func lastIndex<C: Collection>(_ x: C) -> C.Index? {
    apply(x) { $0.indices.last }
  }
}

extension Dispatch where Model : BidirectionalCollection {
  /// Returns the index before `i` in `x`.
  func index<C: Collection>(_ x: C, before i: C.Index) -> C.Index {
    apply(x) { $0.index(before: i as! Model.Index) }
  }
}

That also means yours necessarily makes Dispatch visible to the programmer

Which programmer? The one implementing new dispatched operations must see it, just like the one implementing NegateIfSigned needs to know about KnownSignedNumeric, AttemptIfSigned, and ProxyProtocol, but the end user of operations like negatedIfSigned surely doesn't need to see Dispatch.

they often must write at least one force-cast

I'm confused. The author of NegateIfSigned has to write two. And wouldn't one more such cast be needed in Matt's scheme when writing indexIfBIdirectional(before:), too?

and they could easily call apply with mismatched types.

Just as the author of NegateIfSigned could write the wrong casts?

Unless I'm missing something (and I may be), it seems to me that scheme exposes an enormous amount of complexity to, and demands a lot of code from, the author of a dispatched operation, and I don't currently see any benefits. Since in both cases the technique should be viewed as a hack making up for missing language features, I guess I'd opt for the simpler arrangement. But, to each his own I guess. Until we fix the optimizer to eliminate the dynamism when possible, I'll be reluctant to use any of them.

P.S. Looking forward to seeing that runtime bug show up at bugs.swift.org :wink:

Module `DynamicCollectionDispatch`
// Module `DynamicCollectionDispatch`

// MARK: Public

public protocol AttemptIfBidirectional {
  associatedtype Wrapped
  associatedtype Result
  func action<T: BidirectionalCollection>(_ t: T.Type) -> Result where T == Wrapped
}

extension AttemptIfBidirectional {
  public func attemptAction() -> Result? {
    BidirectionalMarker.attempt(self)
  }
}

public protocol ProxyProtocol { associatedType Wrapped }

public enum Proxy<Wrapped>: ProxyProtocol {}

// MARK: Private

private protocol KnownBidirectionalCollection {
  static func performAction<T: AttemptIfBidirectional>(_ t: T) -> T.Result
}

private enum BidirectionalMarker<A: AttemptIfBidirectional> {}

extension BidirectionalMarker {
  static func attempt(_ a: A) -> A.Result? {
    (self as? KnownBidirectionalCollection.Type)?.performAction(a)
  }
}

extension BidirectionalMarker: KnownBidirectionalCollection where A.Wrapped: BidirectionalCollection {
  static func performAction<T: AttemptIfBidirectional>(_ t: T) -> T.Result {
    (t as! A).action(A.Wrapped.self) as! T.Result
  }
}
// Module `MyCollectionAlgorithms`

import DynamicCollectionDispatch

// MARK: Private

private struct LastIfBidirectional<P: ProxyProtocol>: AttemptIfBidirectional
  where P.Wrapped: Collection
{
  typealias Wrapped = P.Wrapped
  typealias Result = Wrapped.Element?
  
  var x: Wrapped
  
  init<T>(_ x: T) where P == Proxy<T> {
    self.x = x
  }
  
  func action<T: BidirectionalCollection>(_ t: T.Type) -> Result where T == Wrapped {
    return x.last
  }
}

// MARK: Public

extension Collection {
  public var last: Element? {
    if let x = LastIfBidirectional(self).attemptAction() { return x }
    
    var i = startIndex
    if i == endIndex { return nil }
    
    while true {
      let j = i
      formIndex(after: &i)
      if i == endIndex { return self[j] }
    }
  }
}

The author of LastIfBidirectional writes zero casts, and cannot see either KnownBidirectionalCollection or BidirectionalMarker. They don’t even need to know how the dynamic dispatch was achieved, they just imported a library that enables it.

1 Like

Gotcha. Thanks for spelling it out for me!

1 Like

Here’s a way to make Matt’s method even more composable, with smaller modules and a clear separation of concerns:

Module `DynamicDispatch`
// Module `DynamicDispatch`

public protocol DynamicallyDispatched {
  associatedtype Input
  associatedtype Result
  func attemptAction() -> Result?
}

public protocol ProxyProtocol { associatedtype Wrapped }

public enum Proxy<Wrapped>: ProxyProtocol {}
Module `DynamicDispatchImplementation`
// Module `DynamicDispatchImplementation`

import DynamicDispatch

public protocol KnownConformance {
  static func performAction<T: DynamicallyDispatched>(_ t: T) -> T.Result
}

public protocol ConformanceMarker {
  associatedtype A: DynamicallyDispatched
}

extension ConformanceMarker {
  public static func attempt(_ a: A) -> A.Result? {
    (self as? KnownConformance.Type)?.performAction(a)
  }
}
Module `CollectionDispatch`
// Module `CollectionDispatch`

@_exported
import DynamicDispatch

@_implementationOnly
import DynamicDispatchImplementation

public protocol AttemptIfBidirectional: DynamicallyDispatched {
  override associatedtype Result    // To enable type inference
  func action<T: BidirectionalCollection>(_ t: T.Type) -> Result where T == Input
}

extension AttemptIfBidirectional {
  public func attemptAction() -> Result? {
    BidirectionalMarker.attempt(self)
  }
}

private enum BidirectionalMarker<A: AttemptIfBidirectional>: ConformanceMarker {}

extension BidirectionalMarker: KnownConformance where A.Input: BidirectionalCollection {
  static func performAction<T: DynamicallyDispatched>(_ t: T) -> T.Result {
    (t as! A).action(A.Input.self) as! T.Result
  }
}

// ...and similar for `RandomAccess`, etc.
Module `MyCollectionAlgorithms`
@_implementationOnly
import CollectionDispatch

private struct LastIndexIfBidirectional<P: ProxyProtocol>: AttemptIfBidirectional
  where P.Wrapped: Collection
{
  typealias Input = P.Wrapped
  typealias Result = Input.Index?
  
  var x: Input
  
  init<T>(_ x: T) where P == Proxy<T> {
    self.x = x
  }
  
  func action<T: BidirectionalCollection>(_ t: T.Type) -> Result where T == Input {
    return x.isEmpty ? nil : x.index(before: x.endIndex)
  }
}

extension Collection {
  public var lastIndex: Index? {
    if isEmpty { return nil }
    if let x = LastIndexIfBidirectional(self).attemptAction() { return x }
    
    var i = startIndex

    while true {
      let j = i
      formIndex(after: &i)
      if i == endIndex { return j }
    }
  }
}

// ...etc.
User code
import MyCollectionAlgorithms

func foo() {
  print([1.0, 2.0, 3.0].lastIndex)    // Optional(2)
  print([4: 5, 6: 7].lastIndex)       // Something ridiculously long
  print((8...9).lastIndex)            // Something moderately long
  print("".lastIndex)                 // nil
}

The first 2 modules are implemented once, with instructions on how to use them.

Then any number of modules like CollectionDispatch can be written, and they are quite simple. For each set of constraints, you essentially copy-and-paste the code, only changing the names and constraints. Importantly, the function with the force-casts gets pasted verbatim, with no changes at all, not even to its signature.

(I tried to lift the force-casting into one of the earlier modules, but couldn’t find a way.)

Next, any number of modules like MyCollectionAlgorithms can be written, importing as many modules like CollectionDispatch as they want. Their authors just need to implement an action type and give it a generic entry-point. They don’t need to know how the dynamic dispatch actually works.

And finally, user code can import modules with dynamically-dispatched algorithms, and call them like normal. From the perspective of these developers, those modules simply provide APIs like any other.

2 Likes

@dabrahams I created SR-12675 for the runtime crash.

• • •

Edit:

I also figured out how to lift the casting up into DynamicDispatchImplementation, so it only has to be written once and never seen again:

// Module `DynamicDispatchImplementation`

extension ConformanceMarker where Self: KnownConformance {
  public static func perform<T: DynamicallyDispatched>(_ action: (A)->(A.Input.Type)->A.Result, on t: T) -> T.Result {
    action(t as! A)(A.Input.self) as! T.Result
  }
}

With that in place, modules like CollectionDispatch can have the body of their performAction methods simply read perform(A.action, on: t). They don’t need to know about the casting at all.

2 Likes

Here's a bug I filed for the performance of this technique: [SR-12710] Static use of existentials not optimized · Issue #55155 · apple/swift · GitHub
@Nevin, I'd be grateful if you'd verify that it covers everything you think should be necessary.

Thanks,
Dave

1 Like

I'm finally getting a chance to catch up on this thread. Thanks for posting this! I'm switching to your technique in my code and wish I would have thought of it myself. :slight_smile:

I agree. Nevin hits on some of the reasons I was exploring this direction. I was never able get it as clean as necessary to make it usable. It was working for the two use cases where I needed it and I had to set it aside. Given the way it's actually been needed in practice (narrow cases in library code) I much prefer the simpler approach you came up with.

@Nevin I noticed @_implementationOnly in your code. I haven't run into that before. I can guess what it might do, but would like to understand it better. Can you explain or point me in the right direction to learn more?

Not @Nevin, but the relevant thread is here! :slight_smile:

1 Like

Thank you!

Great news, @Erik_Eckstein appears to have already fixed the performance bug: SILOptimizer: improvements for dead alloc_stack elimination by eeckstein · Pull Request #29907 · apple/swift · GitHub

…but it only fixes some cases, e.g. not the one in SR-12710, so please look at the generated code when using this approach if you care about performance.