How/when does 'circular reference' detection work?

Using Swift
,
1

I recently stumbled upon a compiler feature that I don’t quite understand. Consider the following example:

class A {
    var b: B
    init(b: B) { self.b = b }
}

class B {
    var a: A
    init(a: A) { self.a = a }
}

As written, it would seem that these types can’t actually be instantiated due to the cyclic dependence of their initializers (or can they?). If we add a client like this:

class C {
    lazy var a: A = A(b: self.b)
    lazy var b: B = B(a: self.a)
}

let c = C()
c.a // stack overflows

Then the code will compile and overflow the stack upon access to the lazy properties. However, with a slight modification that removes the explicit type annotations from the properties, we will get a compile-time error that identifies the cycle:

class C {
    lazy var a = A(b: self.b) // 🛑 Circular reference
    lazy var b = B(a: self.a)
}

I was slightly surprised that this detection exists, and am curious about when/how it is performed. My guess was that the second formulation is inadvertently leveraging something in the type checker, but it’s not really clear under what circumstances that can be relied upon, or if this functionality is even explicitly guaranteed, or just incidental. Any insights would be appreciated!

2 Likes
2

Without digging into this too much, I suspect what’s going on is that when you leave out the type annotations, answering the question “what is the type of a?” requires you to typecheck the initializing expression, which requires you to figure out the type of self.b, which requires you to typecheck the initializing expression, which requires you to know the type of self.a, resulting in a circular reference.

When you have a type annotation, you cut the cycle at the “figure out the type of self.b” by just looking at the annotation. If the annotation and initializer expression disagree, we will diagnose that at a later point anyway, so for the purpose of typechecking a we can assume the annotation is correct.

4 Likes
3

That's exactly right. To answer the original question,

I was slightly surprised that this detection exists, and am curious about when/how it is performed.

The "circular reference" diagnostics come from the request evaluator, which answers semantic questions about declarations in the AST. At the most fundamental level, something like this must exist because Swift allows forward-referencing identifiers, so you can write a pair of variables where inferring the type of one requires the type of the other, or two classes class A: B {}; class B: A {}, etc.

It's not attempting to detect run time infinite recursion, but rather "static" cycles that would otherwise send the type checker into an infinite loop.

We do have some diagnostic checks to detect the other kind of cycle, where something can type check but the code is still incorrect (like a struct that ultimately contains itself, or a function that calls itself along all control flow paths) but what you're seeing here is specifically related to the type checker.

4 Likes
4

Only if you cheat:

class A {
    var b: B
    init(b: B) { self.b = b }
}

class B {
    var a: A
    init(a: A) { self.a = a }
}

let a = A(b: unsafeBitCast(0, to: B.self))
let b = B(a: a)
a.b = b
print(a, ObjectIdentifier(a))               // App.A ObjectIdentifier(0x0000600000203620)
print(a.b, ObjectIdentifier(a.b))           // App.B ObjectIdentifier(0x0000600000203680)
print(a.b.a, ObjectIdentifier(a.b.a))       // App.A ObjectIdentifier(0x0000600000203620)
print(a.b.a.b, ObjectIdentifier(a.b.a.b))   // App.B ObjectIdentifier(0x0000600000203680)
1 Like
5

I’m surprised this line doesn’t lead to a crash. Shouldn’t it attempt to deallocate the invalid 0-initialized instance of B that was originally set as a.b?

1 Like
6

IIRC the standard retain/release functions are prepared to deal with possibly-nil input references. But regardless, the unsafeBitCast above is undefined behavior and shouldn’t be used as a ‘workaround’ for the circular dependency.

1 Like