Implementing a tree protocol for non-final classes

Using Swift
1

Hi! :wave: I recently got stumped by a compiler limitation while trying to implement a seemingly-reasonable protocol, and I'm curious if anyone has some insight on how to properly approach the problem.

The idea was to describe a general tree structure like this:

protocol TreeNode: AnyObject {
    var parent: Self? { get }
    var children: [Self] { get }
}

This was motivated by code reuse for UI development on Apple platforms, so I'll be using that as a concrete example, but this isn't inherently specific to Apple platforms.

Apple's frameworks make heavy use of this kind of tree structure. Views, view controllers, and scene kit nodes are examples of common objects that could theoretically adopt this protocol. Then, generic algorithms like searching could be implemented once for all of these types rather than reimplementing them over and over. But it turns out that this protocol can't be adopted by a subclassable type. When you try to add a conformance to UIView for example, you get this error:

Protocol 'TreeNode' requirement 'parent' cannot be satisfied by a non-final class ('UIView') because it uses 'Self' in a non-parameter, non-result type position

Please correct me if I get anything wrong, but my understanding of this limitation is that it prevents a subclass from breaking the superclass's protocol conformance. If UIView conforms to the protocol, then Self resolves to UIView. A subclass of UIView (say, UILabel) would inherit this conformance, but it would be invalid to do so. If UILabel conforms to TreeNode, then Self must refer to UILabel and not UIView, but the protocol was already implemented in terms of UIView.

That makes sense, but on the other hand it also seems reasonable in this case to want to say that Self continues to refer to the original conforming type in the subclass. A UILabel's superview and subviews are UIViews, not UILabels, but it seems that there's no way to use a protocol to express that generically.

So I have two questions:

  • Are there other viable approaches to achieve a similar end result?
  • Has there been any discussion about changes that could make this approach viable in the future?
3 Likes
2

You can do

protocol TreeNode: AnyObject {
  associatedtype Parent: TreeNode where Parent.Child == Self
  associatedtype Child: TreeNode where Child.Parent == Self
  
  var parent: Parent? { get }
  var children: [Child] { get }
}
5 Likes
3

Another workaround seems to be

protocol TreeNode {
    associatedtype NodeType: TreeNode
    var parent: NodeType? { get }
    var children: [NodeType] { get }
}


extension UIView : TreeNode {
    var parent: UIView? {
        return superview
    }
    
    var children: [UIView] {
        return subviews
    }
}

Then constrain NodeType to self to taste.

1 Like
4

I thought of that as well. Though it seems we want child->parent to point back to self, so it's probably nicer to put them in protocol requirement itself.

1 Like
5

Those approaches make the conformance valid, but they make implementing the extensions impossible :disappointed:

extension TreeNode where Child: Equatable {
	public func contains(_ child: Child) -> Bool {
		if children.contains(child) {
			return true
		}
		
		// Doesn't work because Child.Child doesn't necessarily conform to Equatable
		if children.contains(where: { $0.contains(child) }) {
			return true
		}
		
		return false
	}
}

It seems like being able to constrain the parent, self and child to all be the same type (or subtypes) is necessary for this to work.

6

You can do

extension TreeNode where Child: Equatable, Child == Self {
    func contains(_ child: Child) -> Bool {
        if child == self {
            return true
        }

        return children.contains { $0.contains(child) }
    }
}

Or to forego equatability

extension TreeNode {
    func contains(_ child: AnyObject) -> Bool {
        if child === self {
            return true
        }

        return children.contains { $0.contains(child) }
    }
}

Or if you need homogeneity most of the time, this is the closest one I could do

protocol TreeNode: AnyObject {
    associatedtype Base: TreeNode where Base.Base == Base

    var parent: Base? { get }
    var children: [Base] { get }
}
2 Likes
7

Constraining Child == Self on the extension pushes out the original error to the call site:

Referencing instance method 'contains' on 'TreeNode' requires the types 'UILabel' and 'UIView' be equivalent

But the last option seems to be a suitable workaround! The main drawback is that any TreeNode extension that needs Self to be homogenous with Base needs to force-cast to make that happen. Which makes the implementations more complicated and means that if you don't fulfill the implicit requirement of Base == Self, you'll crash at runtime. But I can deal with that for my use case. Thanks for your help @Lantua and @griotspeak :pray:

It seems like this might be the best that can be done currently in Swift, but if anyone has any insight I'm curious if there are any potential language changes that would support this more properly.

8

You didn't post the call site that leads to error so I can only speculate, but likely you did this.

someUILabel.contains(someUIView)

in that case the compiler expect someUIView to be UILabel, but it actually is UIView. Instead you can do

(someUILabel as UIView).contains(someUIView)
9

That's right. I didn't think about using as, good to know that's an option although I prefer the other solution to keep the call site clean.

10

There's hardly anyway really since you want to keep TreeNode generic. We probably need generic protocol to make this cleaner.

// Not valid
protocol TreeNode<Base> {
  ...
}

or sacrifice generality of TreeNode

protocol ViewTreeNode: UIView {
  var parent: UIView? { get }
  var children: [UIView] { get }
}
11

I'm not very knowledgeable on the subject, but would it not be possible for Swift to support some variant of Self in a protocol that could mean "subtype of Self" rather than "exactly Self"?

12

What about "supertype of Self" since that's what cause this problem.

because to UILabel think Child is UILabel as per the condition Child == Self.
We could essentially add Child : Self or Self : Child, but the intricacy needs to be taught out. What if Self is a final class, or doesn't have super class?