Mysterious recursion in protocol extension

[ibex10]

I have experienced a mysterious recursion when porting some code from C++ to Swift.

The simplified version of the code is below.

protocol Expr {
}

protocol VectorExpr: Expr {
    var vectorSignature : String {get}
}

enum PrimaryExpr: Expr {
    case Z (Int)
    case vector (Vector)
}

class Vector: VectorExpr {
    var vectorSignature : String {
        "\(type (of:self))"
    }
}

class RowVector: Vector {
    override var vectorSignature : String {
        "\(type (of:self))"
    }
}

class ColumnVector: Vector {
    override var vectorSignature : String {
        "\(type (of:self))"
    }
}

extension Expr {
    var vectorSignature : String? {
        if let u = self as? VectorExpr { // Thread 1: EXC_BAD_ACCESS
            return u.vectorSignature     // Thread 1: EXC_BAD_ACCESS
        }
        
        if let u = self as? PrimaryExpr {
            return u.vectorSignature
        }
        return nil
    }

}

extension PrimaryExpr {
    var vectorSignature : String? {
        switch self {
            case .vector (let u):
                return u.vectorSignature
            default:
                return nil
        }
    }
}

func expr () -> Expr {
    return ColumnVector ()
}


@main
struct Test {
    static func main () {
        // Mysterious recursion ahead!
        #if true
            let u = RowVector () // Even here!
            let s = u.vectorSignature
        #elseif false
            let u = PrimaryExpr.vector (RowVector ())  // Here too!
            let s = u.vectorSignature
        #else
            let u = expr() // Here
            let s = u.vectorSignature
        #endif
    }
}

What is mysterious to me is the fact that always the vectorSignature in the extension of Expr gets triggered despite the fact vectorSignature on more specialised instances of Expr is invoked.

This feels wrong. What do you think?

Thank you.

[itaiferber]

There are two interesting interactions going on here which make the recursion somewhat expected (in a pedantic way, if you understand the interactions), both related to how the compiler behaves when you have two functions/fields with the same name, and one needs to be accessed:

1. Fields/functions added in extensions to protocols behave differently if those fields/functions are part of the original protocol declaration or not:

   • If they are, the implementation in the extension is a default implementation, and calling the implementation will dynamically dispatch at runtime to the effective underlying type which implements the protocol
   • If they aren't, the implementation in the extension is statically dispatched at compile-time exclusively, and the implementation in the protocol will get called as-is regardless of the underlying type implementing the protocol. Such functions/fields cannot be overridden in any way

   protocol P { /* no requirements */ }
   
   protocol Q: P {
       // One requirement:
       func f()
   }
   
   extension P {
       // Statically-dispatched because `f()` isn't part of the requirements
       // for `P` in the original declaration.
       //
       // This `f` is a totally separate function from `Q.f`.
       // Calls to this function will _never_ call to `Q.f`.
       //
       // This function also can't be overridden in any way.
       func f() { print("P.f") }
   }
   
   extension Q {
       // This is a default implementation for `Q.f` which is dynamically-
       // dispatched. If a type provides its own implementation of `f()`,
       // that will get called; if not, this implementation will.
       func f() { print("Q.f") }
   }
   
   struct S1: Q {}
   struct S2: Q {
       func f() { print("S2.f") }
   }
   
   (S1() as Q).f() // Dynamically-dispatched, defaults to `Q.f`
   (S1() as P).f() // Statically-dispatched, calls `P.f`
   
   (S2() as Q).f() // Dynamically-dispatched, calls to `S2.f` implementation
   (S2() as P).f() // Statically-dispatched, calls `P.f` 
   

   You have to be very careful with adding functions/fields to protocols in this way, because when two names shadow one another, the static type of a variable may determine which gets called

2. When multiple functions/fields shadow one another, and calls to each are equally possible, the one with the most specific and closest type to the one that you need will get called

In your specific case:

1. Expr has no protocol requirements at all, and VectorExpr adds one protocol requirement in vectorSignature
2. In an extension, Expr offers a vectorSignature of its own which is statically-dispatched and completely unrelated to VectorExpr.vectorSignature, except that the names shadow one another
3. The types of Expr.vectorSignature and VectorExpr.signature are different: String? vs. String

Thus, in

extension Expr {
    var vectorSignature : String? {
        if let u = self as? VectorExpr {
            return u.vectorSignature // <- here
        }

the compiler sees two possible calls in u.vectorSignature:

1. Because u is a VectorExpr, it's possible to dynamically-dispatch VectorExpr.vectorSignature to the implementation of the concrete type of u
2. Because u is also an Expr, it's possible to statically-dispatch to the implementation of Expr.vectorSignature

Both are equally possible, because the two accessors are completely unrelated to one another, even if they have the same name! The compiler then needs to pick between them; it can either:

1. Call VectorExpr.vectorSignature, and wrap its String result into String?, or
2. Call Expr.vectorSignature, and return its value directly

It goes with (2) because the type matches more closely. Hence, u.vectorSignature is actually statically dispatching back to Expr.vectorSignature, regardless of what u is. sad trombone noises...

Without changing anything about the rest of your code, the fix here is easy: if you explicitly designate the type you want from u.vectorSignature, you can disqualify Expr.vectorSignature from being a valid candidate to call:

if let u = self as? VectorExpr {
    // Explicit `String` type rules out `Expr` impl:
    let signature: String = u.vectorSignature
    return signature
}

This breaks you out of the infinite loop.

All of this being said, as a user of the language, yeah, this can be pretty surprising. The static-vs-dynamic dispatch of protocol members has been discussed at length here on the forums; it can be easy to get unexpectedly-bitten by the behavior. But, technically not a bug: the behavior is applied consistently everywhere.

---

As an aside, in Swift 5.8 at least, only the latter two cases you've posted appear to trigger this loop, because they go through PrimaryExpr, which is calling Expr directly. When you're using RowVector directly, it appears that the compiler prefers to call through to the protocol — but I don't know if this has changed in Swift 5.8, or if this has been the case for a while (and you may be on an older compiler), or if this may be a copy-and-paste error in your code.

[ibex10]

Thank you, @itaiferber.

(1) This solves the problem:

@itaiferber

if let u = self as? VectorExpr {
    // Explicit `String` type rules out `Expr` impl:
    let signature: String = u.vectorSignature
    return signature
}

This also does the job:

if let u = self as? VectorExpr {
    let signature = u.vectorSignature
    return signature
}

(2) In Swift 5.8, this does not cause recursion:

let u = RowVector () // recursion is gone!
let s = u.vectorSignature