Struct cannot have a stored property that references itself [duplicate]

Question

Reference cycles in Swift occur when properties of reference types have strong ownership of each other (or with closures).

Is there, however, a possibility of having reference cycles with value types only?

---

I tried this in playground without succes (Error: Recursive value type 'A' is not allowed).

struct A {
  var otherA: A? = nil
  init() {
    otherA = A()
  }
}

Answer 1

A reference cycle (or retain cycle) is so named because it indicates a cycle in the object graph:

Each arrow indicates one object retaining another (a strong reference). Unless the cycle is broken, the memory for these objects will never be freed.

When capturing and storing value types (structs and enums), there is no such thing as a reference. Values are copied, rather than referenced, although values can hold references to objects.

In other words, values can have outgoing arrows in the object graph, but no incoming arrows. That means they can't participate in a cycle.

Answer 2

As the compiler told you, what you're trying to do is illegal. Exactly because this is a value type, there's no coherent, efficient way to implement what you're describing. If a type needs to refer to itself (e.g., it has a property that is of the same type as itself), use a class, not a struct.

Alternatively, you can use an enum, but only in a special, limited way: an enum case's associated value can be an instance of that enum, provided the case (or the entire enum) is marked indirect:

enum Node {
    case None(Int)
    indirect case left(Int, Node)
    indirect case right(Int, Node)
    indirect case both(Int, Node, Node)
}

Answer 3

Disclaimer: I'm making an (hopefully educated) guess about the inner workings of the Swift compiler here, so apply grains of salt.

Aside from value semantics, ask yourself: Why do we have structs? What is the advantage?

One advantage is that we can (read: want to) store them on the stack (resp. in an object frame), i.e. just like primitive values in other languages. In particular, we don't want to allocate dedicated space on the heap to point to. That makes accessing struct values more efficient: we (read: the compiler) always knows where exactly in memory it finds the value, relative to the current frame or object pointer.

In order for that to work out for the compiler, it needs to know how much space to reserve for a given struct value when determining the structure of the stack or object frame. As long as struct values are trees of fixed size (disregarding outgoing references to objects; they point to the heap are not of interest for us), that is fine: the compiler can just add up all the sizes it finds.

If you had a recursive struct, this fails: you can implement lists or binary trees in this way. The compiler can not figure out statically how to store such values in memory, so we have to forbid them.

Nota bene: The same reasoning explains why structs are pass-by-value: we need them to physically be at their new context.

Answer 4

Quick and easy hack workaround: just embed it in an array.

struct A {
  var otherA: [A]? = nil
  init() {
    otherA = [A()]
  }
}

Answer 5

You normally cannot have a reference cycle with value types simply because Swift normally doesn't allow references to value types. Everything is copied.

However, if you're curious, you actually can induce a value-type reference cycle by capturing self in a closure.

The following is an example. Note that the MyObject class is present merely to illustrate the leak.

class MyObject {
    static var objCount = 0
    init() {
        MyObject.objCount += 1
        print("Alloc \(MyObject.objCount)")
    }

    deinit {
        print("Dealloc \(MyObject.objCount)")
        MyObject.objCount -= 1
    }
}

struct MyValueType {
    var closure: (() -> ())?
    var obj = MyObject()

    init(leakMe: Bool) {
        if leakMe {
            closure = { print("\(self)") }
        }
    }
}

func test(leakMe leakMe: Bool) {
    print("Creating value type.  Leak:\(leakMe)")
    let _ = MyValueType(leakMe: leakMe)
}

test(leakMe: true)
test(leakMe: false)

Output:

Creating value type.  Leak:true
Alloc 1
Creating value type.  Leak:false
Alloc 2
Dealloc 2

Answer 6

Is there, however, a possibility of having reference cycles with value types only?

Depends on what you mean with "value types only". If you mean completely no reference including hidden ones inside, then the answer is NO. To make a reference cycle, you need at least one reference.

But in Swift, Array, String or some other types are value types, which may contain references inside their instances. If your "value types" includes such types, the answer is YES.