Swift Codable struct recursively containing itself as property

Question

I have a rather large struct that conforms to Codable, and one of its properties needs to be of the same type as itself. A shortened sample of what I'm trying to do is shown below:

struct Message: Codable {
    let content: String
    // ...other values
    let reference: Message // <-- Error: Value type 'Message' cannot have a stored property that recursively contains it
}

Swift doesn't seem to allow a struct to recursively contain itself as one of its values. Is there any way to get this working besides creating a complete duplicate Message struct (which turns this into a chicken and egg problem where the duplicate struct cannot contain itself etc). Not creating a duplicate struct also allows me to reuse SwiftUI code that takes in and renders a Message struct.

Answer 1

A simple way is to just change the struct into a class:

class Message: Codable {
    let content: String
    // ...other values
    let reference: Message? // optional - the recursion has to end somewhere right?
}

But this could break other parts of your code, since structs and classes have vastly different semantics.

An alternative would be to make a reference type Box:

class Box<T: Codable>: Codable {
    let wrappedValue: T
    required init(from decoder: Decoder) throws {
        wrappedValue = try T(from: decoder)
    }
    
    func encode(to encoder: Encoder) throws {
        try wrappedValue.encode(to: encoder)
    }
}

Then,

struct Message: Codable {
    let content: String
    // ...other values
    
    let boxedReference: Box<Message>?
    
    // you can still refer to 'reference' as 'reference' in your swift code
    var reference: Message? { boxedReference?.wrappedValue }
    
    enum CodingKeys: String, CodingKey {
        case content, boxedReference = "reference"
    }
}

Answer 2

Sweeper's approach provides two good solutions, both of which involve injecting a class. But there are a several other things you might try, some that work and some that don't, and it's worth understanding the underlying issue. It's not just a quirk; it's an important part of how Swift works.

// FAIL (for abstract reasons)
var manager: Manager
var manager: CollectionOfOne<Manager>

// FAIL (for swift-specific reasons)
var manager: Manager? // when manager is a struct
var manager: Result<Manager, Error> // when manager is a struct

// PASS
var manager: Manager? // when Manager is a class
var manager: Result<Manager, Error> // when manager is a class
var manager: Box<Manager>   // our custom class Box
var manager: [Manager]
var manager: EmptyCollection<Manager>

The following example also passes:

protocol ManagerLike {
    var id: String { get set }
    var mail: String { get set }
    var manager: ManagerLike? { get set }
}

struct Manager: ManagerLike {
    var id: String
    var mail: String
    var manager: any ManagerLike?
}

The first two cases fail for abstract, logical reasons. It's impossible for any "eager" language (like Swift) to construct a type that must contain a value of its own type. That's infinitely recursive. And an eager language needs to construct the entire value before it can progress. Even in a lazy language, you'd need some kind of generator to construct this. This is true no matter whether Manager is a struct or a class (or an enum or anything else).

The next two issues are related to how Swift implements structs. A struct stores each of its fields in sequence in memory; there's no indirection. So the size of the struct is based on the size of its properties, and Swift must know its final size at compile time. (In Rust, you can explicitly mark types as Sized to express this explicitly, but in Swift, it's an implicit part of being a struct.)

Optional and Result are themselves just structs, so they inline their contents just like any other struct, and their final size is dependent on the size of their content. Since there is no way to know at compile time how deep this chain goes, there's no way to know how large this struct is.

Classes, on the other hand, store their data on the heap, and are implemented as a pointer to that storage. They are always exactly the same size, no matter what they contain. So a nested Manager? works. It is logically possible, since it can eventually terminate (unlike a nested Manager). And it is sizable because it is always the size of an object pointer. Result works the same way.

Box is just a specific case of a class, which is why it works.

But what about [Manager]? Certainly we don't know how many elements are in it, so how does Swift know how large it is? Because Array is always the same size. It generally stores its contents on the heap, and just stores a pointer internally. There are cases where it can inline its contents if they're small enough. But the key point is that Array itself is a fixed size. It just has a pointer to variable sized storage.

EmptyCollection works for the same reason. It's always the same size, empty.

The final example, using a protocol, is an example of an existential container, which is what the new any points out. An existential container is very similar to the Box type, except that it's made by the compiler and you can't access it directly through the language. It moves the contents to the heap (unless the contents are very small), and so is itself fixed-size.

This brings up one more example that seems to work, but doesn't:

protocol ManagerLike {
    var id: String { get set }
    var mail: String { get set }
    var manager: ManagerLike? { get set }
}

struct Manager<M: ManagerLike> {
    var id: String
    var mail: String
    var manager: M?
}

Now, rather than using an any Manager, it is replaced with a generic. This will compile. So you might think "I'll just pass Manager as the type of M and get my original goal!" And you'll find the rule is...self-enforcing:

let m = Manager<Manager<Manager<Manager<...

The type itself is now infinitely recursive. Oh well. Hard to sneak past algebra.

The key take away is that a struct must know its size, and that means everything within it must know its size, and that's impossible if any of its properties' sizes rely on the size of the struct type itself.