Test if a type conforms to a non-existential protocol

Hi everyone, I've encountered a problem when trying to optimize a generic algorithm and was a bit stuck when I had to adapt an implementation detail to whether my generic type conformed to more restrictive protocol or not. In python, a simple if isinstance(self, class) would solve the issue, but I didn't find any equivalent in swift.

The problem

Playing around with generic algorithms (in this case quickselect), I had to gather the last accessible index of a Collection. It is easy and cheap if the collection conforms to BidirectionalCollection by using

let lastIndex = index(before: endIndex)

(inside an extension on Collection). It is also easy in the general case (though O(n)) by doing something like

let lastIndex = indices.max()!

The problem is that I did not find a way to implement this so that it's O(n) in the general case (fair enough), but falls back to something that is O(1) when the collection happens to be bidirectional (which is often the case in practice). You can always use

let lastIndex = return index(endIndex, offsetBy: -1)

and the compiler is happy, but it crashes at runtime if you use it on a collection that is not bidirectional with:

Fatal error: Only BidirectionalCollections can be advanced by a negative amount

Defining different extensions for Collection and BidirectionalCollection such as:

extension BidirectionalCollection {
  public func lastIndex() -> Index {
    print("BidirectionalCollection implementation")
    return index(endIndex, offsetBy: -1)
  }
}

extension Collection {
  public func lastIndex() -> Index {
    print("Collection implementation")
    return indices.max()!
  }
}

may seem like it works, but as soon as you use that in a context more generic, it fails:

extension Collection {
   func findLastIndex() -> Index { return lastIndex() }
} 

will never use the BidirectionalCollection implementation. The only way to get this to work is if lastIndex was a protocol requirement, which would mean change the Collection protocol.

Pitch

Having some way to check at dispatch if the type on which we are writing an extension conforms to additional protocol would be very helpful to adjust the implementation to be the most efficient it can be. For instance, in this case, if we had a test like Self is BidirectionalCollection we could write something like:

var lastIndex: Index = startIndex
if Self is BidirectionalCollection {
  lastIndex = return index(endIndex, offsetBy: -1)
} else {
  lastIndex = indices.max()!
}

or even shorter

let lastIndex = (Self is BidirectionalCollection) ? index(endIndex, offsetBy: -1) : indices.max()!

or any other kind of syntax that would help know if Self conforms to BidirectionalCollection.

Please let me know if I missed anything and there is already something in the language to do this.

1 Like

In your example, I believe this works?

if self is BidirectionalCollection { … }

…or if you need methods of BidirectionalCollection:

if let self = self as? BidirectionalCollection { … }

Swift’s is expects a value on the lhs and a type on the rhs, so you need self and and not Self.


If you do need to turn the type of self into a value that you can use in expressions (e.g. on the lhs of is), the syntax is the curious but logical Self.self. And if for some reason you all have is the type and not the value, you can apply is to the metatype; this, while unnecessarily complicated, also works:

if Self.self is BidirectionalCollection.Type { … }
1 Like

The two tests fail with

error: protocol 'BidirectionalCollection' can only be used as a generic constraint because it has Self or associated type requirements

Same for the conversion with as.

1 Like

Ah, so the problem isn’t that the language doesn’t have the type membership test you’re looking for, but rather that it doesn’t work on protocols with associated types. It does seem like is should work here! That seems like a good proposal.

(It makes sense that as? wouldn’t work, because the language still can’t use one of these associated type protocols as the type of a variable.)

There's a slight problem that we also need a way to specify BidirectionalCollection.Element, .Index, .Indices, .SubSequence or any combination thereof to be useful.

Yes, that’s why BidirectionalCollection can’t be used as a variable type: we first need existential types that can wrap up all those unspecified associated types into a “best knowledge possible” interface that, for example, returns Any from a subscript if Element is unknown.

But none of that should be a problem for the is operation. Sylvain’s problem is they're just trying to use BidirectionalCollection as a tag protocol — a type relationship that indicates implementation behavior without exposing any additional API. No peering into associated types necessary for that.

2 Likes

I know this doesn't answer your question of casting to a protocol with associated type constraints, but have you tried using the following?

let lastIndex = collection.indices.last

I believe this would still allow collections to provide more efficient implementations through their Indices. I'm unsure if this is O(1) for bidirectional collections out-of-the-box, but for Array<T> it certainly is.

I don't see it, this example works only because self is already a collection of some sort, and that Index is for Collection is the same as Bidirectional collection. It wouldn't work if we go from Sequence to BidirectionalCollection because we don't know if Index matches (Self as BidirectionalCollection).Index.

In order to do what you want, we’d need somethihg like dynamic dispatch for protocol extension methods (Dynamically-dispatched protocol extension members).

There are iffy workarounds, like creating a closure-based type eraser with overloads for initialisation, but then you’d still need to construct it with a concrete type (it wouldn’t work in generic code).

There simply is no way today to conditionally downcast to a refined protocol if that protocol contains associated types.

There is no way to cast, but if you’re willing to write a bunch of boilerplate there is a way to conditionally “open” an existential in a way that brings conformance back into the type system for the duration of a callback. Here’s an example https://gist.github.com/anandabits/d9494d14fef221983ff4f1cafa318d47. This is super clunky and we should improve the language in this area, but it is possible as a workaround today.

3 Likes

It's also not supported by the language. I encouraged Sylvain to post this as an evolution pitch because the simple is test for non-existential protocols makes complete sense as a language extension and is almost impossible to mis-specify, even if we do want fancier existential-opening capabilities some day.

7 Likes

I believe we should rethink what we can do with values implementing protocols with associated types in general. Especially when we know that a value conforms to such a protocol, but not what these associated types are. @sgugger gave a great example above.

Another issue that I often run into is the following:

protocol P { // Protocol with Self or associated type requirement
    func foo(_ x: Self) {}
    func bar() {}
}
let array: [P] // protocol 'P' can only be used as generic constraint because it has Self or associated type requirements

Note that P might also inherit the Self or associatedtype requirements, e.g. if it refines Equatable.

Admittedly, such an array of P might not be what one might initially expect (we can't do things like array[0].foo(array[1]) or compare elements if P refines Equatable because the elements might be different concrete types), but we could still safely use all other methods, like array[0].bar()!

Today's workaround is splitting the protocols in two parts:

protocol P {
    func bar() {}
}
protocol Q: P {
    func foo(_ x: Self) {}
}
let array: [P]

That works, but isn't nice. Plus we can't use this workaround when we don't own the protocol hierarchy, such as in the example with BidirectionalCollection.

I guess we could also use Any*-style type erasers?

Either way, I think being able to use such protocols as standalone types and not only as generic constraints would open up lots of possibilities. Would it be possible to allow the definition of let array: [P] above and have array[0] be of type some P? What do you guys think?

Yeah, I'm all in favor of improving the language. I was just trying to make a point of fact that there is a workaround people can use if they really need to.

That's a somewhat controversial question that's been covered many times elsewhere in these forums (look for “generalized existentials”), and a whole other can of worms than what Sylvain is proposing.

It's O(1) for bidirectional collections, but doesn't compile for plain Collection, which is the problem.

Ah, I didn't realize last is only added to the collection hierarchy as a requirement on BidirectionalCollection. Thanks for pointing that out, @dabrahams.

My impression is that this should work as expected for is, but that would still not give that much as you might often want to know that it conforms to a PAT and has specific associatedtypes.
One way that I think would be pretty natural (once the language evolves in that part) is to have if let self = self as? some BidirectionalCollection<.Element = Int> { ..., which allows you to use the result in many more ways

Yes — and the obvious syntax now (is SomeProtocolWithAssociatedTypes) would almost certainly remain compatible with that bigger better existential world of the future.

It seems a sensible and straightforward proposal, and I would support it.

1 Like

You can also make lastIndex a requirement of a new protocol, and provide default implementations:

protocol LastIndex: Collection {
  public func lastIndex() -> Index
}

extension LastIndex where Self: BidirectionalCollection {
  public func lastIndex() -> Index {
    print("BidirectionalCollection implementation")
    return index(endIndex, offsetBy: -1)
  }
}

extension LastIndex where Self: Collection {
  public func lastIndex() -> Index {
    print("Collection implementation")
    return indices.max()!
  }
}

It would be nice if we had a mechanism for extending protocols with additional dispatched requirements. I think that would be a more robust approach than using dynamic casting or existentials; finding a protocol conformance dynamically has performance and semantic issues that are hard to avoid.

2 Likes

Heh, there are at least two problems with this approach. The first is that you need to explicitly make every Collection conform to LastIndex. The second is that if your generic collection conditionally conforms to BidirectionalCollection, you'll get the O(N) implementation unconditionally from a generic context.

It would be nice if we had a mechanism for extending protocols with additional dispatched requirements.

+1; we had a pitch on these forums for such a feature recently but I can't find it.

Terms of Service

Privacy Policy

Cookie Policy