Creating Circular Referencing Structs

General Usage
,
1

This works

abstract type Abstract_B end

mutable struct A
    obj::Abstract_B
    function A() 
       x     = new()
       x.obj = B(x)        
    end
end

struct B<:Abstract_B
    obj::A
end

Can it be done without the abstract type ?
The below works. Repeating the definition of A2 before and after B2. The first A2 definition gives an error but the next one executes without error. It avoids the abstract type but is messy.

mutable struct A2
    obj::B2
    function A2() 
       x     = new()
       x.obj = B2(x)        
    end
end

struct B2
    obj::A2
end

mutable struct A2
    obj::B2
    function A2() 
       x     = new()
       x.obj = B2(x)        
    end
end
2 Likes
2

Julia doesn’t feature forward declarations, that is declarations prior to full definitions; you can kind of do it for functions by making 0 methods function foo end, but not much else, definitely not for structs. Julia also does not have a multi-pass AOT compiler that can leave placeholders and return to fill out definitions.

Your abstract type example is about as close as you can get to a forward declaration, though it strictly speaking isn’t one. The other thing you can do is parameterize your structs so the field type only needs to be specified at instantiation. You still can’t make them all immutable structs though because you run into the impossible first node issue.

julia> mutable struct A{T}
         next::T
         A{T}() where T = new{T}()
       end

julia> function A(next::T) where T
         a = A{T}()
         a.next = next
         a
       end
A

julia> struct B{T}  next::T  end # need not be mutable, but probably should be

julia> b = B( A{B}() ); b.next.next = b # connect 2 nodes; complete circle
B{A{B}}(A{B}(B{A{B}}(#= circular reference @-2 =#)))
3 Likes
3

Thanks Benny. Much appreciated

4

Oh, I should’ve realized and highlight that the parameter of the A node is an abstract B, so that doesn’t escape abstract types. It’s impossible for 2 parametric types because you can’t finish writing A{B{A{B{A{B......}}}}(). You can cheat your way to concrete field types by wrapping the abstract B in a Ref{B}, but that extra indirection doesn’t dereference type-stably either. I’m not sure if there is a proper way around this, mutables and abstract fields seem to be Julia’s closest analog to the pointers necessary for mutually recursive structs in C/C++; it’s worth the memory safety to omit them from languages, but it also sacrifices some flexibility. Pointers in particular aren’t necessary to pull this off; this really old issue covers the speculations around mutually recursive type definitions. One of the working hacks is to add a try-catch to the first definition in your type-stable 2nd example to suppress the error, effectively a wordy forward declaration. Personally I’d rather not write any forward declarations and have type-searching passes or “delay” determination of the struct layout in some other way, though I doubt that’s coming anytime soon.

1 Like