Protocols and covariance - How to enable LSP in swift?

I want to keep some graph traversal algorithms as generic as possible and define a protocol for this purpose:

protocol Path {
    var distance : Int { get}
    var end : Node { get }
    init (start:Node) 
    func extend (move:Edge) -> Path? 
}

Most graph traversal algorithms can easily be implemented with this protocol: starting with a source node and incrementally traversing new edges to build longer paths until reaching a target.

I want then to use the protocol in a generic Search<PathType:Path>. Unfortunately, I cannot use the protocol in a way that benefits from the Liskov Substitution Principle. For example, if I have BasicPath:Path, the return type of this subtype (a stronger postcondition) in extend() is not considered conforming to the protocol:

struct SimplePath : Path {
    ...
    func extend (move:Move) -> SimplePath? {  // OUCH: does not conform to Path 
           ...
    }
}

I have tried several alternatives, to make my generic Search<PathType:Path> work:

• If I use func extend (move:Move) -> Path?, the struct would conform to the protocol, but the generic Search algorithm cannot take advantage of the fact that the returned path and the original path share the same type.

• If I use in the protocol an associated type associatedtype PathType2 : Path and return this type from extend(), it ends the same. Nothing allows me to link the associated type to the original type.

Is there an idiom to properly implement covariance with protocols, without making Path a base class ?

If you always want the extend method to return the type it is declared in you can use Self in the protocol as the return type.

protocol Path {
   //…
   func extend(move:Edge) -> Self? 
}