Test if a type conforms to a non-existential protocol

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.