Test if a type conforms to a non-existential protocol

Slava_Pestov · April 20, 2020, 7:21pm

The restriction with "is" not accepting protocols that have associated types is artificial. It could be lifted and it would work. However, as others have pointed out, this has limited utility because there is no way to operate on the value, or to cast its associated types.

Paul_Cantrell · April 20, 2020, 8:06pm

Sure, but it is a real solution to a real problem, here or in any case where the protocol in question is (or at least for the purpose of the code in question functions as) a marker interface / tag interface that indicates a contract that adds no API surface. In that situation, there's no need to peer into associated types; the obvious solution is a good one.

Given that the problem is real albeit narrow, given how hairy the current workaround (per @anandabits) is, and given that the solution is straightforward and non-breaking, it does seem like a sensible proposal.

Joe_Groff · April 20, 2020, 8:08pm

Keep in mind that is/as? Protocol is always an expensive dynamic check if the type is not statically known to conform to the protocol, because the compiler cannot know whether conformances are added to a type externally.

Ben_Cohen · April 21, 2020, 4:10am

This is one reason why I think that a good rule of thumb with these algorithms is, if you need to do this check, the first assumption should be you have taken a wrong turn.

In this case, it seems like you just need to check and go down the O(n) path. And if it's a one-off, that might be worth doing. But the OP states that this is in pursuit of implementing quickselect, the implementation of which will probably need random access to select the pivot.

In many cases, probably including quickselect, the idea you can have one algorithm service both forward-only and random-access collections just by having specific customization points for things like advancing an index is an illusion. In practice, if you know up front you're operating on a non-random-access (or non-bidirectional) collection, you'd be better off taking a completely different approach. If you push this requirement far enough up the chain, you end up at a concrete type and the user can make that decision for you, or you can make it via overloading at the top level (like reversed does – it returns an array for forward-only collections, but a lazy view for bidirectional ones).

This isn't a universal rule – there are some algorithms that could benefit from extra customization points. But if we had the benefit of a feature that let us add arbitrary customization points to a protocol, I expect you'd want to use them to be algorithm-specific rather than algorithm-building-block-specific (i.e. use mergesort instead of quicksort to implement sort on non-random-access collections).

Paul_Cantrell · April 21, 2020, 4:12am

I wonder if that's an argument for:

protocol Collection {
  var isBidirectional: Bool { get }  // on the protocol itself, so virtual dispatch
}
extension Collection {
  var isBidirectional: Bool { false }
}
extension BidirectionalCollection {
  var isBidirectional: Bool { true }  // would be nice if Swift supported `final` here
}

…?

Joe_Groff · April 21, 2020, 4:17pm

Paul_Cantrell:

I wonder if that's an argument for:

protocol Collection {
  var isBidirectional: Bool { get }  // on the protocol itself, so virtual dispatch
}
extension Collection {
  var isBidirectional: Bool { false }
}
extension BidirectionalCollection {
  var isBidirectional: Bool { true }  // would be nice if Swift supported `final` here
}

…?

Yeah, or maybe some other way of opting into keeping cheap "dynamic cast" information inside a protocol hierarchy. This sort of reminds me of the problem @dabrahams discussed in this thread, where in order to be able to specialize a protocol requirement in a conditional conformance without resorting to global dynamic searches for the conformances, we might need some way to explicitly mark optional conformance requirements.

Paul_Cantrell · April 21, 2020, 6:31pm

Yeah, this is a really sticky area of the language, one where my reasoning often fails. The root of it all, I think, is that Swift extensions can express two very different things:

properties of values themselves, but also
properties values acquire from local assumptions in the context where they’re used.

It’s confusing that extension means both of these things.

In Dave’s example in that second link, this dynamically dispatched code:

extension P {
    static var isEquatable: Bool { false }
}

…is something that the value itself knows — “I am not equatable” — whereas this statically dispatched code (which if I understand correctly is a shadow, not an override):

extension P where Self : Equatable {
    static var isEquatable: Bool { true }
}

…is tied to something the calling context knows — “if you think I implement the Equatable protocol, then I guess I’m equatable!” Dave’s example goes haywire because the local assumptions (the static types) that could expose this isEquatable implementation don’t travel around with the value itself.

This all makes sense in terms of the language specification and implementation, but it’s hard to reason intuitively about. It feels like the Liskov Substitution Principle’s bohemian cousin.

Back to the problem at hand: I don’t think you can get things to make sense again here without doing some kind of runtime test based on metadata that lives with the value itself. Whether that’s an expensive type metadata search with is or the vtable lookup I sketched, it has to be dynamic.

dabrahams · April 22, 2020, 2:46am

It's all very well to say that, and of course we would rather not do any ugly type-switching, but the language's current limitations on generic dispatching leaves us few options today. Rather than asking for the feature we'd really want, which is hard to implement and specify, we thought we should ask for the obvious, conservative, easy-to-implement language extension that makes sense.

No, it doesn't, as you can easily see by inspecting the pseudocode: immediately after selecting the pivot from a range of elements, the algorithm does an O(N) traversal of that same range to partition it. Therefore, if choosing a pivot devolves to O(N) traversal of that range in the non-random-access case, it doesn't change the algorithm's complexity at all.

(Also, choosing a pivot other than the first element isn't necessarily important if you're going on to implement introselect, because you handle the pathological cases with a fallback algorithm. But that's neither here nor there; I just added it because I like to talk about algorithms ;-}).

dabrahams · April 22, 2020, 3:35am

Incidentally, Matthew/@anandabits, I don't see any way to use _openExistential to solve the problem Sylvain posted about, do you? The challenge is to implement this property:

extension Collection {
  /// Returns `true` if `self` conforms to `BidirectionalCollection`.
  var isBidirectional: Bool { /* your code here */ }
}

Thanks,
Dave

Ben_Cohen · April 22, 2020, 3:48am

Ah you're right, my bad.

The challenge is to implement this property:

extension Collection {
 /// Returns `true` if `self` conforms to `BidirectionalCollection`.
 var isBidirectional: Bool { /* your code here */ }
}

It there's a strong case here to add this particular customization point, it's easily done via an evolution proposal. I'm pretty sure we have the ability to add customization points ABI-stably (though not back deploy them).

anandabits · April 22, 2020, 4:33am

You're right that _openExistential does not help. I discovered a (admittedly rather clunky) pattern that does support opening arbitrary constraints and therefore allows this property to be implemented. You can find my implementation of isBidrectional using this pattern here: isBidirectional.swift · GitHub.

If you're able to clean up the implementation at all please let me know! And if you're able to push language improvements that let me toss this pattern into the dustbin even better.

dabrahams · April 22, 2020, 5:27am

Wow, thanks! I'm going to have to spend some time studying this code… and I will accept your invitation to try to simplify it.

Absolutely, I'm not giving up on those.

dabrahams · April 22, 2020, 5:32am

Thanks for the invitation, but wouldn't it be a lot more useful to have a generalized is test than a one-off addition to the standard library? Either one is (I think) easily done via an evolution proposal, after all. Of course, if the language feature turns out to be unexpectedly hard to implement, I'll gratefully take you up on it.

dabrahams · April 22, 2020, 4:02pm

Please see my reply here, thanks.

Nevin · April 23, 2020, 1:22am

If we literally just want the Bool result for isBidirectional, that’s actually pretty easy. Here’s a quick demo for all 5 of the standard Collection subprotocols.

First some empty enums:

enum BidirectionalCollectionMarker<T> {}
enum LazyCollectionMarker<T> {}
enum MutableCollectionMarker<T> {}
enum RandomAccessCollectionMarker<T> {}
enum RangeReplaceableCollectionMarker<T> {}

Then some empty conformances:

protocol ConformanceMarker {}

extension BidirectionalCollectionMarker   : ConformanceMarker where T: BidirectionalCollection {}
extension LazyCollectionMarker            : ConformanceMarker where T: LazyCollectionProtocol {}
extension MutableCollectionMarker         : ConformanceMarker where T: MutableCollection {}
extension RandomAccessCollectionMarker    : ConformanceMarker where T: RandomAccessCollection {}
extension RangeReplaceableCollectionMarker: ConformanceMarker where T: RangeReplaceableCollection {}

And finally the Collection properties:

extension Collection {
  var isBidirectional   : Bool { BidirectionalCollectionMarker<Self>.self    is ConformanceMarker.Type }
  var isLazy            : Bool { LazyCollectionMarker<Self>.self             is ConformanceMarker.Type }
  var isMutable         : Bool { MutableCollectionMarker<Self>.self          is ConformanceMarker.Type }
  var isRandomAccess    : Bool { RandomAccessCollectionMarker<Self>.self     is ConformanceMarker.Type }
  var isRangeReplaceable: Bool { RangeReplaceableCollectionMarker<Self>.self is ConformanceMarker.Type }
}

For actual use, it probably makes sense to have static Collection.isX properties as well, in which case the instance properties could just call Self.isX.

In any event, here’s a helper for checking all the capabilities of a Collection instance:

CollectionCapabilities

struct CollectionCapabilities {
  var isBidirectional   : Bool
  var isLazy            : Bool
  var isMutable         : Bool
  var isRandomAccess    : Bool
  var isRangeReplaceable: Bool
}

extension Collection {
  var capabilities: CollectionCapabilities {
    CollectionCapabilities(
      isBidirectional   : isBidirectional,
      isLazy            : isLazy,
      isMutable         : isMutable,
      isRandomAccess    : isRandomAccess,
      isRangeReplaceable: isRangeReplaceable
    )
  }
}

• • •

Edit: Here’s a slight variation that adds a 2nd empty protocol in order to shorten the line length of the Collection properties, and make things read a little better:

Version 2

extension Collection {
  var isBidirectional   : Bool { BidirectionalCollectionMarker<Self>.conforms }
  var isLazy            : Bool { LazyCollectionMarker<Self>.conforms }
  var isMutable         : Bool { MutableCollectionMarker<Self>.conforms }
  var isRandomAccess    : Bool { RandomAccessCollectionMarker<Self>.conforms }
  var isRangeReplaceable: Bool { RangeReplaceableCollectionMarker<Self>.conforms }
}

protocol ConformanceMarker {}

extension ConformanceMarker {
  static var conforms: Bool { Self.self is Conforming.Type }
}

enum BidirectionalCollectionMarker<T>   : ConformanceMarker {}
enum LazyCollectionMarker<T>            : ConformanceMarker {}
enum MutableCollectionMarker<T>         : ConformanceMarker {}
enum RandomAccessCollectionMarker<T>    : ConformanceMarker {}
enum RangeReplaceableCollectionMarker<T>: ConformanceMarker {}

protocol Conforming {}

extension BidirectionalCollectionMarker   : Conforming where T: BidirectionalCollection {}
extension LazyCollectionMarker            : Conforming where T: LazyCollectionProtocol {}
extension MutableCollectionMarker         : Conforming where T: MutableCollection {}
extension RandomAccessCollectionMarker    : Conforming where T: RandomAccessCollection {}
extension RangeReplaceableCollectionMarker: Conforming where T: RangeReplaceableCollection {}

dabrahams · April 23, 2020, 5:04am

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.

anandabits · April 23, 2020, 1:04pm

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.

Nevin · April 24, 2020, 3:22am

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.

Nevin · April 25, 2020, 8:28am

@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.

dabrahams · April 25, 2020, 9:22am

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…