What kind of black magic reconciles protocol with class inheritance

Hello everyone,

Some of you may recognize a similar protocol from another of my posts:

protocol Stack {
  associatedtype Element

  func push(element: Element) -> S
  func pop() -> (Self, Element?)
}

Say I want to adopt this protocol with a simple linked list implementation:

class List<Element>: Stack {
  var element: Element
  var next: List?

  // I really wish for SE-0018 to be implemented one day ...
  init(element: Element, next: List? = nil) {
    self.element = element
    self.next = next
  }

  func push(element: Element) -> List {
    return List(element: element, next: self)
  }

  func pop() -> (List, Element?) {
    return next == nil ? (self, nil) : (next!, element)
  }
}

This solution won't work, because List is not final. I guess the reason is that a subclass would not fulfill the self-requirement imposed by the protocol Stack for the methods push(element:) and pop(). One could use Self, as suggested by the compiler. While this can solve the problem for the push(element:) method (additionally requiring a way to reliably initializing a Self instance, e.g. by marking List's initializer required), it does not work for pop() because its return type is a tuple (by the way I think (Self, Element?) should work in theory, as tuples seems to be covariant).

By navigating a little on the forum, I found a solution by declaring an additional associated type in Stack with a same-type requirement on Self, and use it in the return types of push(element:) and pop():

protocol Stack {
  associatedtype Element
  associatedtype S where S == Self

  func push(element: Element) -> S
  func pop() -> (S, Element?)
}

// List's code is unchanged

class SortedList<Element>: List<Element> where Element: Comparable {

  override func push(element: Element) -> SortedList {
    // some completely irrelevant implementation ...
  }

}

This looks awfully hacky, but appears to work like a charm. SortedList.push(element:) is properly overridden and returns a SortedList, while List.pop() is inherited and returns a List, as expected (I know there would be far far better approaches to implement this that would not even have to rely on class inheritance, but my point isn't really about linked lists). Unfortunately, I don't understand why ...

I thought that protocol conformance was checked at every level of a class hierarchy. By this logic, it would make perfect sense that the first solution (using Self as a return type) does not work. But then this second approach shouldn't either, because SortedList inherits from a method List.pop() that does not fulfill the same-type requirement defined on Stack's associated type. Worse, S does not even represent the same type in SortedList's two methods, which leaves me wondering how type inference was able to solve it.

Could anyone enlighten me on the magic that leaves the type solver happy with this contrived example?

I think you've found a bug here. With the S == Self constraint, your conformance is still unsound for a non-final class; S needs to be able to be covariant for a class hierarchy just like Self does. What you ought to need to do is declare the return types of the conforming methods as covariant as well:

class List<Element>: Stack {
  func push(element: Element) -> Self { ... }

  func pop() -> (Self, Element?) { ... }
}

(though due to implementation constraints, I don't think we'll let you write the pop implementation today).

3 Likes

Thanks for your impressively fast answer. I'll open an issue about this.

Yeah, that's a bummer. But to be fair that's a quite contrived use case.

Relevant bug report: https://bugs.swift.org/browse/SR-10713

2 Likes
Terms of Service

Privacy Policy

Cookie Policy