Struct cannot have stored property that references itself but it can have an array of the same type [duplicate]

Question

In swift this fails

struct Node {
  var val: String
  var parent: Node
}

with error error: value type 'Node' cannot have a stored property that recursively contains it

but this works

struct Node {
  var val: String
  var parent: [Node]
}

What is the reasoning behind this behavior?

Answer 1

Basically, a struct cannot have a property that is of it's own type because a struct is a value type. That means that every time it's used it's a new copy - by value. The way the compiler works is that it needs to compute a set size in memory for a struct. A class, on the other hand, is more flexible in that sense. An array is a little more complicated - it's a struct wrapper around an object. The compiler can deal with an unknown array size in a struct, but it can't deal with custom object that might have infinite recursive values in it. Each node can have a node with another node, with another node, etc, etc... It would need to set infinite memory for the struct. For more detail see this excellent article: Bidirectional associations using value types in Swift

Answer 2

The reason for this compile error is memory allocation:-

Value types are fixed structures and they occupy a fixed space in memory, in registers and the stack, depending on its size. That space is pre-determined by the type and must be known at compile time.

So, the compiler needs to know how much space to reserve for a given struct value. But, how could that space be calculated if the value could contain another value of the same type, and that value could contain another one, and so on, and so on, and so on…(recursion)?

It is impossible to calculate the space needed, so the compiler simply says N0!

Answer 3

use this code:

class Box<T> {
   let boxed: T
   init(_ thingToBox: T) { boxed = thingToBox }
}

struct Node {
   let id: Int
   let parent: Box<Node>?
}

or wrap it in an array:

struct Node {
   let id: Int
   let parent: [Node]?
}