Nested types don't recognize protocol conformance in recursive methods

pnowell · May 23, 2024, 5:42am

I'm not sure exactly how to describe this unexpected behavior with protocols and generics, so I'll give a distilled example:

My app works with a certain kind of element (conforming to a protocol that I'll refer to as Element) and containers/groupings of them (conforming to a Container protocol). Containers are elements themselves, and can be nested (ex: container within a container). My use case is unique, but the structure is common (like a basic Array or a SwiftUI stack view).

protocol Element {}

protocol Container: Element {
	associatedtype Child: Element
	var elements: [Child] { get }
}

// Some types that conform to those protocols

struct ExampleElement: Element {}

struct ExampleContainer<Child: Element>: Container {
	var elements: [Child]
}

I'll define a method for all containers, to do something with their elements. At the moment, these examples simply print whether or not the container's child elements are also containers themselves.

extension Container {
	
	func action() {
		print("Child is a simple Element.")
	}
	
	func action() where Child: Container {
		print("Child is a Container")
		elements.forEach { $0.action() }
	}
}

This works fine. And I can test it like so:

let nestedContainer = ExampleContainer(elements: [ ExampleElement() ])
let doubleNestedContainer = ExampleContainer(elements: [nestedContainer])

doubleNestedContainer.action()

// Prints:
// Child is a Container
// Child is a simple Element.

This is what I would expect. The doubleNestedContainer is recognized correctly as a container of containers, so the appropriate action() method is called. But it doesn't work if I define a triple nested container.

let tripleNestedContainer = ExampleContainer(elements: [doubleNestedContainer])
tripleNestedContainer.action()

// Prints:
// Child is a Container
// Child is a simple Element.

I would have expected this:

// Child is a Container
// Child is a Container
// Child is a simple Element.

It seems that the version of the action() method where Child: Container only runs for the top-most parent container. Swift doesn't seem to recognize that the child containers conform to the Container protocol. The only way to get my expected result is to define yet another method with a second where clause:

extension Container {

	func action() where Child: Container, Child.Child: Container {
		print("Child is a Container")
		elements.forEach { $0.action() }
	}

}

tripleNestedContainer.action()

// Prints:
// Child is a Container
// Child is a Container
// Child is a simple Element.

I expected that Swift would be able to recognize a type's conformance in this scenario. Similar to how an Array is Equatable if its element is Equatable, and that applies recursively to Arrays of Arrays. That demonstrates enough type "awareness" that I assumed my situation would work too. In fact it took me half a day to identify that this was the cause of a bug.

I'm wondering 1. Why is this the case? and 2. Is there some way to accomplish the kind of action() method I expect, that drills down through containers until it gets to the ultimate child element?

hisekaldma · May 23, 2024, 7:09am

When you define method overloads in an extension like this, you’re getting static dispatch, i.e. which method to call is chosen at compile time based on the type information available at that point. When you call tripleNestedContainer.action() it chooses the second overload, but inside the forEach all the compiler knows is that Child: Container, so it chooses the first overload.

What you need is dynamic dispatch, i.e. for the method to be chosen dynamically based on the type. To get that you need to make the action() method into a protocol requirement:

protocol Element {
    func action()
}

protocol Container: Element {
    associatedtype Child: Element
    var elements: [Child] { get }
}

struct ExampleElement: Element {
    func action() {
        print("Element is a simple Element.")
    }
}

struct ExampleContainer<Child: Element>: Container {
    var elements: [Child]
    func action() {
        print("Element is a Container")
        elements.forEach { $0.action() }
    }
}

sveinhal · May 23, 2024, 7:52am

I'll just add to what @hisekaldma said, by noting that you could also get dynamic dispatch by doing some runtime checks such as this:

extension Container {
    func action() {
        if let containers = elements as? [any Container] {
            print("Child is a Container")
            containers.forEach { $0.action() }
        } else {
            print("Child is a simple Element.")
        }
    }
}

That is, use a single action function that always gets called, and decide at runtime what is does, based on some condition.

Edit: I guess this isn't dynamic dispatch, but just runtime behavior of a function dispatched statically.

pnowell · May 23, 2024, 6:10pm

Thank you both for the quick and clear responses! I didn't know about static vs. dynamic dispatch, but I figured it was caused by something like that.

@hisekaldma thank you for demonstrating how to set things up for dynamic dispatch instead. The only issue is that I don't want Element to have an action() method—only Container—so I don't see a way around having 2 action() methods on the same ExampleContainer type, with one using a where clause. I tried that just now and I get the same issue. Based on your code sample, it also seems like dynamic dispatch might require that the method be defined on the type (ex: struct) rather than the protocol (in a protocol extension). I have several types that conform to Container and I'd rather not repeat the same method definition for all of them.

@sveinhal I briefly tried such an if statement the other day, but wasn't sure if it was reliable or recommended. It seemed like a less Swifty way (with casting and any instead of strong types, and only done at runtime) but now I think it's by far the DRYest and clearest solution.
Update: I ended up not using this approach because I need my method to return values (see my flatten() use case below) and this would force it to return [any Element] rather than [some Element]. I’d rather the compiler know that all elements are of the same concrete type. But this approach could work for other use cases!

hisekaldma · May 23, 2024, 6:48pm

I don’t know anything about your exact use case, but in general it’s perfectly fine to have a method that does nothing for some types. Personally, I would prefer that to casting since it expresses more about the actual requirements on the types in the type system. But YMMV of course!

It actually doesn’t have to be defined for each type! A protocol requirement can have a default implementation, which looks confusingly similar to what you had originally:

protocol Element {
    func action()
}

protocol Container: Element {
    associatedtype Child: Element
    var elements: [Child] { get }
}

extension Element {
    func action() {
        print("Element is a simple Element.")
    }
}

extension Container {
    func action() {
        print("Element is a Container")
        elements.forEach { $0.action() }
    }
}

struct ExampleElement: Element {
}

struct ExampleContainer<Child: Element>: Container {
    var elements: [Child]
}

With this setup, if types conform to Element or Container without providing their own implementation of the action() method, the one from the respective protocol extension is chosen instead. What’s different from what you had originally is that these extensions match the requirement in the protocol exactly. (It's a bit unfortunate that default implementations look so similar to simple extension methods, even though they are very much not the same thing.)

Slava_Pestov · May 23, 2024, 7:05pm

FWIW this issue is also being discussed in this thread and all the general advice there applies as well: Generic implementation doesn't work with concrete types - #6 by Slava_Pestov

pnowell · May 23, 2024, 8:43pm

Thanks @Slava_Pestov. I have to admit however that the other thread is a bit over my head. I’m not a computer scientist so there are many parts that I don’t understand. I’m sure there are great reasons for Swift to be less dynamic, but it makes it difficult to refactor my code because each time I abstract something into a method it loses its awareness of the type’s conformances. It might make the compiler more performant, but this is a frustrating and counterintuitive user experience as a Swift developer. There’s already a significant learning curve to protocols and generics. I’m a huge fan of Swift and everything you and other contributors do, and at the same time it feels like non expert Swift developers should be able expect more dynamic/aware behavior in such a common use case.

@hisekaldma I really appreciate the follow up demo and it does indeed work. But when trying to implement it in my project, I’m realizing I might have oversimplified my initial example slightly. What I’m trying to do is flatten all containers so I just have an array of elements. And I would ideally like the compiler to know that those “ultimate” child elements (non-containers) are all the same type: that it’s a [some Element] Array rather than an [any Element] Array.

So going back to the example code, instead of action() my method would be flatten() with a return type.

extension Container {

	func flatten() -> [some Element] {
		print("Returning child elements")
		return elements
	}
	
	func flatten() -> [some Element] where Child: Container {
		print("Returning child containers")
		return elements.flatMap { $0.flatten() }
	}

}

print( tripleNestedContainer.flatten() )

This code has the same/original issue, but I can’t figure out how to apply your suggestions to it because the methods return values. Is there any way to accomplish this?

florianpircher · May 23, 2024, 9:57pm

You need a chain that links the type of the non-container elements all the way up for each container layer. You can introduce an associated type, say Flat, on Element that describes the underling/flattened type of the element. For non-container elements, Flat will be the element itself. For containers, Flat is the Flat type of its child element type. In code:

protocol Element {
    associatedtype Flat = Self
    
    func flatten() -> [Flat]
}

extension Element {
    func flatten() -> [Flat] where Flat == Self {
        return [self]
    }
}

protocol Container: Element where Flat == Child.Flat {
    associatedtype Child: Element
    associatedtype Flat = Child.Flat
    
    var elements: [Child] { get }
}

extension Container {
    func flatten() -> [Flat] {
        return elements.flatMap { $0.flatten() }
    }
}

An example implementation of the above would be:

struct Number: Element, Equatable {
    let value: Int
}

struct Term: Container {
    let elements: [Number]
}

struct TermGroup: Container {
    let elements: [Term]
}

You would use it like so:

let termGroup = TermGroup(elements: [
    Term(elements: [
        Number(value: 1),
        Number(value: 2),
    ]),
    Term(elements: [
        Number(value: 3),
    ]),
])

let flatElements = termGroup.flatten()
assert(flatElements == [
    Number(value: 1),
    Number(value: 2),
    Number(value: 3),
])

Slava_Pestov · May 23, 2024, 10:03pm

I’m not a computer scientist either and I’d be happy to explain any unfamiliar jargon.

Perhaps the associated type of your protocol should abstract over the Element type of the leaves, and not the child of each node:

protocol Tree<Element> {
  associatedtype Element
  func flatten() -> [Element]
}

struct Leaf<Element>: Tree {
  var value: Element
  func flatten() -> [Element] { return [value] }
}

struct Interior<Node: Tree>: Tree {
  var nodes: [Node]
  func flatten() -> [Node.Element] {
    var result: [Node.Element] = []
    for node in nodes {
      result += node.flatten()
    }
    return result
  }
}

Alternatively, Interior doesn’t need to be generic over Node at all, if you add a new generic parameter Element and change the type of var nodes to [any Tree<Element>].

hisekaldma · May 24, 2024, 6:01am

You absolutely don’t need to know all the jargon to understand how it works! The important thing to remember is that that if the method you’re calling is not a protocol requirement or an overridable method in a class, the compiler will always pick exactly one method to call at compile time. Before you have a good intuition for what this means in practice, it can help a lot to avoid overloading – i.e. don’t name multiple methods the same thing unless they implement a protocol requirement or override a method in a superclass. Then you’ll always have to type out the exact method to call, and so you’ll always know exactly which method the compiler picks.

If we do that with your initial example, it becomes much clearer which method is called where:

extension Container {
	func actionContainer() {
		print("Child is a simple Element.")
	}
	
	func actionNestedContainer() where Child: Container {
		print("Child is a Container")
		elements.forEach { $0.actionContainer() }
	}
}

If you do this with some piece of code and your reaction is “but I want the compiler to pick the right method for me!”, it means you’ve taken a wrong turn somewhere, and you probably need to express it using a protocol requirement instead.

pnowell · May 24, 2024, 7:59pm

Thanks to all of your ideas and insights I figured out a great solution!

@florianpircher and @Slava_Pestov, I couldn’t use your exact code because in my use case I can’t have a separate type for containers of containers—I really need a container to be able to store either another container or some “ultimate” child elements. But you both inspired me to try implementing a protocol where containers know their “ultimate” child type (I think this was what you were referring to as “your protocol should abstract over the Element type of the leaves”).

For example, imagine a container of containers of integers. Each level of container now knows that the ultimate element is an integer. And they also know that they all have the same type of ultimate element. I implemented this by adding an additional UltimateChild associatedtype for all elements, then using where clauses to describe/enforce the relationships. Unlike my original code, the flatten() method is a protocol requirement (thanks @hisekaldma) and there’s no need for overloading methods with the same name. Any where clauses exist on the protocol and concrete type declaration—not on specific methods—and I think that makes a difference too, as more can be known about the types.

Slava, your code example also made me realize that for the purpose of this distilled code example, it’s simpler to use integers as elements rather than defining a ExampleElement struct, so I’ve done that here.

/// A domain-specific item/element, with certain shared characteristics.
/// If the element can store other elements, it should conform to the Container protocol.
/// Otherwise it should conform to the UltimateElement protocol.
protocol Element {
	associatedtype UltimateChild: UltimateElement
	func flatten() -> [UltimateChild]
}

/// An ultimate child element can be stored in a container but it is not itself a container.
protocol UltimateElement: Element where UltimateChild == Self {}

/// Provide a default implementation of the `flatten()` method for UltimateElement.
extension UltimateElement {
	/// An ultimate element is already flattened, so it simply returns itself in an array.
	func flatten() -> [UltimateChild] { [self] }
}

/// A container can store any kind of element—including other containers. 
/// It adopts the ultimate child type of its children.
/// At the heart/core of a container (or container of containers) must be an UltimateElement child.
protocol Container<Child>: Element where UltimateChild == Child.UltimateChild  {
	associatedtype Child: Element
	var elements: [Child] { get }
}

/// Provide a default implementation of the `flatten()` method for Container.
extension Container {
	
	/// Distill this container down to its ultimate child elements.
	func flatten() -> [UltimateChild] {
		elements.flatMap { $0.flatten() }
	}
	
}



/// A simple container type.
struct ExampleContainer<Child: Element, UltimateChild: UltimateElement>: Container where Child.UltimateChild == UltimateChild {
	var elements: [Child]
}


/// Allow Integers to be ultimate child elements for this code example.
extension Int: UltimateElement {}



let containerOfUltimateElements = ExampleContainer(elements: [ 1, 2, 3 ])
let nestedContainer = ExampleContainer(elements: [ containerOfUltimateElements, containerOfUltimateElements ])
let doubleNestedContainer = ExampleContainer(elements: [ nestedContainer, nestedContainer ])
let tripleNestedContainer = ExampleContainer(elements: [ doubleNestedContainer, doubleNestedContainer ])


print( tripleNestedContainer.flatten() )

// Prints:
// [1, 2, 3, 1, 2, 3, 1, 2, 3, 1, 2, 3, 1, 2, 3, 1, 2, 3, 1, 2, 3, 1, 2, 3]

Thank you all, again! Your detailed and quick responses have been very generous. I was able to implement this solution in my app and it seems to be working perfectly! Of course feel free to add any feedback or improvements you notice.