Wrong Specialized Generic Function Gets Called in Swift 3 from an Indirect Call

Wrong specialized generic function gets called in Swift 3 from an indirect call

This is indeed correct behaviour as overload resolution takes place at compile time (it would be a pretty expensive operation to take place at runtime). Therefore from within test(value:), the only thing the compiler knows about value is that it's of some type that conforms to DispatchType – thus the only overload it can dispatch to is func doBar<D : DispatchType>(value: D).

Things would be different if generic functions were always specialised by the compiler, because then a specialised implementation of test(value:) would know the concrete type of value and thus be able to pick the appropriate overload. However, specialisation of generic functions is currently only an optimisation (as without inlining, it can add significant bloat to your code), so this doesn't change the observed behaviour.

One solution in order to allow for polymorphism is to leverage the protocol witness table (see this great WWDC talk on them) by adding doBar() as a protocol requirement, and implementing the specialised implementations of it in the respective classes that conform to the protocol, with the general implementation being a part of the protocol extension.

This will allow for the dynamic dispatch of doBar(), thus allowing it to be called from test(value:) and having the correct implementation called.

protocol DispatchType {
func doBar()
}

extension DispatchType {
func doBar() {
print("general function called")
}
}

class DispatchType1: DispatchType {
func doBar() {
print("DispatchType1 called")
}
}

class DispatchType2: DispatchType {
func doBar() {
print("DispatchType2 called")
}
}

func test<D : DispatchType>(value: D) {
value.doBar()
}

let d1 = DispatchType1()
let d2 = DispatchType2()

test(value: d1) // "DispatchType1 called"
test(value: d2) // "DispatchType2 called"

Unexpected Behavior in Swift Overloaded Function with Generic Parameters or T or Array of T

The compiler is getting confused by the use of the wrapped optional comming out of ary.first which will definitely go to the first function signature. But even fixing that will still leave some ambiguity on the processing of simpler cases such as [[1,2][3,4]].

Another way to approach this would be to handle all the types internally rather than leaving it up to the compiler:

func flatten<U>( _ ary:[Any] ) -> [ U ]
{
func makeFlat(_ flat:[U], _ elem:Any) -> [U]
{
if let item = elem as? U { return flat + [item] }
if let ary = elem as? [U] { return flat + ary }
if let subAry = elem as? [Any] { return flat + flatten(subAry) }
return flat
}
return ary.reduce([U](),makeFlat)
}

Differences generic protocol type parameter vs direct protocol type

The key confusion is that Swift has two concepts that are spelled the same, and so are often ambiguous. One of the is struct T: A {}, which means "T conforms to the protocol A," and the other is var a: A, which means "the type of variable a is the existential of A."

Conforming to a protocol does not change a type. T is still T. It just happens to conform to some rules.

An "existential" is a compiler-generated box the wraps up a protocol. It's necessary because types that conform to a protocol could be different sizes and different memory layouts. The existential is a box that gives anything that conforms to protocol a consistent layout in memory. Existentials and protocols are related, but not the same thing.

Because an existential is a run-time box that might hold any type, there is some indirection involved, and that can introduce a performance impact and prevents certain optimizations.

Another common confusion is understanding what a type parameter means. In a function definition:

func f<T>(param: T) { ... }

This defines a family of functions f<T>() which are created at compile time based on what you pass as the type parameter. For example, when you call this function this way:

f(param: 1)

a new function is created at compile time called f<Int>(). That is a completely different function than f<String>(), or f<[Double]>(). Each one is its own function, and in principle is a complete copy of all the code in f(). (In practice, the optimizer is pretty smart and may eliminate some of that copying. And there are some other subtleties related to things that cross module boundaries. But this is a pretty decent way to think about what is going on.)

Since specialized versions of generic functions are created for each type that is passed, they can in theory be more optimized, since each version of the function will handle exactly one type. The trade-off is that they can add code-bloat. Do not assume "generics are faster than protocols." There are reasons that generics may be faster than protocols, but you have to actually look at the code generation and profile to know in any particular case.

So, walking through your examples:

func direct(a: A) {
// Doesn't work
let _ = A.init(someInt: 1)
}

A protocol (A) is just a set of rules that types must conform to. You can't construct "some unknown thing that conforms to those rules." How many bytes of memory would be allocated? What implementations would it provide to the rules?

func indirect<T: A>(a: T) {
// Works
let _ = T.init(someInt: 1)
}

In order to call this function, you must pass a type parameter, T, and that type must conform to A. When you call it with a specific type, the compiler will create a new copy of indirect that is specifically designed to work with the T you pass. Since we know that T has a proper init, we know the compiler will be able to write this code when it comes time to do so. But indirect is just a pattern for writing functions. It's not a function itself; not until you give it a T to work with.

let a: A = B(someInt: 0)

// Works
direct(a: a)

a is an existential wrapper around B. direct() expects an existential wrapper, so you can pass it.

// Doesn't work
indirect(a: a)

a is an existential wrapper around B. Existential wrappers do not conform to protocols. They require things that conform to protocols in order to create them (that's why they're called "existentials;" the fact that you created one proves that such a value actually exists). But they don't, themselves, conform to protocols. If they did, then you could do things like what you've tried to do in direct() and say "make a new instance of an existential wrapper without knowing exactly what's inside it." And there's no way to do that. Existential wrappers don't have their own method implementations.

There are cases where an existential could conform to its own protocol. As long as there are no init or static requirements, there actually isn't a problem in principle. But Swift can't currently handle that. Because it can't work for init/static, Swift currently forbids it in all cases.

Protocol function with generic type

Status of the features needed to make this work:

  • Recursive protocol constraints (SE-0157) Implemented (Swift 4.1)
  • Arbitrary requirements in protocols (SE-0142) Implemented (Swift 4)
  • Generic Type Aliases (SE-0048) Implemented (Swift 3)

Looks like this is currently not possible without introducing boxed types (the "type erasure" technique), and is something looked at for a future version of Swift, as described by the Recursive protocol constraints and Arbitrary requirements in protocols sections of the Complete Generics Manifesto (since generic protocols are not going to be supported).

When Swift supports these two features, the following should become valid:

protocol Parser {
associatedtype Result
associatedtype SubParser: Parser where SubParser.Result == Result

func parse() -> ParserOutcome<Result, SubParser>
}

enum ParserOutcome<Result, SubParser: Parser where SubParser.Result == Result> {
case result(Result)
case parser(P)
}

With generic typealiases, the subparser type could also be extracted as:

typealias SubParser<Result> = Parser where SubParser.Result == Result

Extending Collection with a recursive property/method that depends on the element type

I don't believe that it's currently possible to write a recursive extension like this, where the base case is determined by the conformance of a static type.

Although note that Collection does have a count property requirement, it's just of type IndexDistance (an associated type), rather than Int. Therefore if this were possible, you could express it as:

extension Collection {
var flatCount: IndexDistance {
return count
}
}

extension Collection where Iterator.Element: Collection {
var flatCount: IndexDistance {
// compiler error: unable to infer closure type in the current context
// (if you expand it out, it will tell you that it's because
// $1.flatCount is ambiguous)
return self.reduce(0) { $0 + $1.flatCount }
}
}

However, this yields a compiler error (although why it doesn't for when flatCount is an Int, I have no idea – they should both either consistently compile or not compile). The problem is that Swift wants to statically dispatch $1.flatCount – therefore meaning that it can only pick one of the extensions to call (and in this case, the compiler thinks both are equally valid).

The only way static dispatch could work here is if the implementations were specialised for each concrete type of Collection that they're called on. In that case, the ambiguity would be resolved as the compiler would know the concrete type inside the implementation, and thus know whether Iterator.Element.Iterator.Element : Collection, and dispatch accordingly.

However, currently specialisation is only an optimisation (due to the fact that it has the potential to drastically bloat code size without the use of inlining to counteract this additional cost) – therefore it's not possible to guarantee that static dispatch would work for all cases.

Even if $1.flatCount was able to be dynamically dispatched, through for example a protocol witness table (see this great WWDC talk on them), overload resolution based on the type constraints of the extensions would need to take place at runtime (in order to determine which extension to call). However, Swift doesn't resolve overloads at runtime (it would be expensive). Instead, the overload itself is resolved at compile time, and dynamic dispatch then allows the implementation of that overload to be polymorphic with respect to the value that it's called on (i.e it can dispatch to a the value's own implementation of that overload).


Unfortunately, I think probably the closest you'll be able to get is to write an extension for Array and use conditional type-casting in order to iterate through nested arrays:

extension Array {
var flatCount: Int {

var iterator = makeIterator()

if let first = iterator.next() as? [Any] {
// must be an array of arrays – otherwise $1 as! [Any] will crash.
// feel free to add error handling or adding support for heterogeneous arrays
// by doing an O(n) walk.
return iterator.reduce(first.flatCount) { $0 + ($1 as! [Any]).flatCount }
} else {
return count
}
}
}

let arr = [[[[2, 3, 4]], [3, 4, 5, 6]], [57, 89]]

print(arr.flatCount) // 9

Although note that as @MartinR points out in the comments below, the conversion as(?/!) [Any] will create a new array in most cases (due to the difference in how Swift stores concrete typed and abstract typed values – see this Q&A), making the above implementation not particularly efficient.

One potential solution to this is to use a 'dummy protocol' in order to declare the flatCount property:

// dummy protocol to prevent conversions of arrays with concrete-typed elements to [Any].
protocol _Array {
var flatCount: Int { get }
}

extension Array : _Array {
var flatCount: Int {

var iterator = makeIterator()

if let first = iterator.next() as? _Array {
// same comment as above, can crash for heterogeneous arrays.
return iterator.reduce(first.flatCount) { $0 + ($1 as! _Array).flatCount }
} else {
return count
}
}
}

This avoids the O(n) conversion from an array of concrete-typed elements to abstract-typed elements (instead, only a single box is created for a given array).

If we do a rough quick benchmark of the two implementations (in a Release build on a MacBook Pro) with the array:

let arr = Array(repeating: Array(repeating: Array(repeating: 1, count: 100), count: 100), count: 1000)

For 10 repeated calls to flatCount, the first extension gives a time of 31.7 seconds. The same benchmark applied to the second implementation yields 0.93 seconds.

How to pass protocol with associated type (generic protocol) as parameter in Swift?

If you use typealias in a protocol to make it generic-like, then you cannot use it as a variable type until the associated type is resolved. As you have probably experienced, using a protocol with associated type to define a variable (or function parameter) results in a compilation error:

Protocol 'MyProtocol' can only be used as a generic constraint because it has Self os associated type requirements

That means you cannot use it as a concrete type.

So the only 2 ways I am aware of to use a protocol with associated type as a concrete type are:

  • indirectly, by creating a class that implements it. Probably not what you have planned to do
  • making explicit the associated type like you did in your func

See also related answer https://stackoverflow.com/a/26271483/148357



Related Topics



Leave a reply



Submit