Reference cycles with value types?

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()
  }
}

Nonstriated

I don't think this has anything to do with the ARC; structs and classes are not conceptually different in that regard. – Hetman

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.

Vergievergil

what's does closure + 8 & 8 signify in this context? – Beauchamp

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)
}

Spile

Can you elaborate a little on why this is not possible (a struct having a property of the same type as self)? – Vladikavkaz

@AlfieHanssen Read jtbandes' answer, it explains completely. – Spile

Either I'm missing something or jtbandes answer doesn't provide the info I'm looking for. I understand what a retain cycle is. What I'm a little confused about is: if a struct (a value type) can have a property of type int (a value type), and it can have a property of type anotherStruct (a value type), why can it not have a property of type self (a value type)? Does that make sense? – Vladikavkaz

@AlfieHanssen Here's one way to think about it. Remember these are value types: assignment makes a copy. Now imagine a struct struct Dog { var puppy : Dog? }. Now consider this code: let d = Dog(); d.puppy = d. Clearly that's incoherent: it's the Barber paradox. Thus Swift just puts its foot down and forbids the whole situation. — Now, in reality, there's more to it than that; it has to do with how value types are actually held in memory. But at least that gives you a motivation. – Spile

That's a great example, it's clear that because copy() is involved the situation quickly becomes untenable (infinite object graph instead of retain cycle?). Thanks for taking the time to explain this! – Vladikavkaz

@AlfieHanssen Find a slightly more elaborate take in my answer. I don't think retain cycles resp. the ARC are relevant here at all. – Hetman

@Hetman FWIW I agree; you'll notice I said nothing about retain cycles at all. There is no reference counting involved. – Spile

@Spile I know; my comment was directed at Alfie for a reason. ;) I agree with him that you don't give reasons, though. – Hetman

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.

Hetman

Might want to watch Session 416 of the WWDC 2016 videos. – Spile

@Spile Because I might find it interesting or because I wrote something wrong? The first few minutes are interesting and definitely fit the question but don't tell me anything new. Should I watch on, and why? – Hetman

You said you had to "guess about the inner workings of the Swift compiler". The reason for watching is that there is a lot of detail about how structs are actually stored. You can read it over at asciiwwdc rather than actually watching. – Spile

@Spile Thanks for the reference, I'll have a look when I find the time! – Hetman

Answer 4

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

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

Toggery

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

Jansson

So you can capture Self in a reference Cycle with itself! What If I have a struct that has a delegate and I want to assign itself as this delegate per default 😁 I think I cannot declare struct protocol properties weak, right? So how to get around this cycle? – Seth

I checked this in Swift 3 and you will get the compiler error Closure cannot implicitly capture a mutating self parameter. So the compiler prevents this kind of retain cycle! – Seth

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.

Showker