handle mutually-circular type declarations

[JeffBezanson]

Currently this doesn't work:

type Foo
    a::Bar
end

type Bar
    b::Foo
end

A nice way to handle it is to automatically insert forward declarations for all types defined in a file after lowering. That way as long as the types are in the same file it will Just Work™.

[StefanKarpinski]

We can also define it as wrong to declare mutually circular types beyond the span of a single file, which solves that problem. In the repl, should we do the same thing for every input expression? So that you can do this:

julia> begin
         type Foo
           a::Bar
         end
         type Bar
           b::Foo
         end
       end

It would be pretty janky to only be able to define certain types by loading a file.

[StefanKarpinski]

Aka mutually recursive type declarations.

[filmackay]

Is there a workaround for this - seems like a fairly fundamental gap at this point?

(other than Any-typing one of the references)

[StefanKarpinski]

The simplest workaround is to not declare a type on the circular field. Not awesome, but it works.

[filmackay]

Thanks. When using the above method you need to be careful to avoid runaways:

type A
       b
end

type B
       a::A
       function B()
         self = new()
         self.a = A(self)
         self
       end
end

b = B()

Since it then tries to display the value b it gets into an infinite loop:

B(A(B(A(B(A(B(A(B(A(B(A(B(A(B(A(B(A(B(A(B(A(B(A(B(A(B(A(B(A(B(A(B(A(B(A(B(A(B(A(B(A(B(A(B(A(B(A(B(A(B(A(B(A(B(A(B(A(B(A(B(A(B(A(B(A(B(A(B(A(B(A(B(A(B(A(B(A(B(A(B(A(B(A(B(A(B(A(B(A(B(A(B(A(B(A(B(A(B(A(B(A(B(A(B(A(B(A(B(A(B(A(B(A(B(A(B(A(B(A(B(A(B(A(B(A(B(A(B(A(B(A(B(A(B(
...

Presumably these circulars would need to be avoided somehow in the repr? Dangerous for REPL/IJulia playing.

Would have thought this 'reference to my parent' pattern would be fairly common - obviously not.

[quinnj]

Do we need to do some kind of cycle detection in the default show for new types? Once a cycle is detected, we could do a custom show_recursive. Having a function like this would then be handy for people implementing their own mutually recursive types.

[toivoh]

Cycle detection in show would definitely be nice to have. I did an attempt in #1139, but it did not reach completion. Still, I think that the discussion there is useful, even though I'm not sure whether my approach was right.

[toivoh]

Another trick to get mutually circular types is to make the first type parametrized, and then create a type alias for it that is parametrized on the second type afterwards. But it's not very beautiful either.

[amitmurthy]

Yet another attempt for show(::Any) to handle recursive types in #3831

[cuckookernel]

Guys. Isn't the original issue of mutually recursive type declarations not yet resolved? Seems kind of weird, it's been a long time... Are there plans to have this feature in a forthcoming release?

[StefanKarpinski]

It hasn't been a high priority. Nice to have, but not a show-stopper for anything.

[dhimmel]

It hasn't been a high priority. Nice to have, but not a show-stopper for anything.

I have to disagree that this is not a show-stopper. Some would say it's even a bone-breaker.
—Just one user's experience which will hopefully help prioritize development.

[StefanKarpinski]

Out of curiosity, what can't you do without this feature? Aside from the obvious – declare mutually dependent types.

[kmsquire]

@dhimmels, could you give a concrete example of where lack of this feature has broken a bone (or otherwise incapacitated a prospective Julia programmer)? ;-)

(Actual examples are usually more motivating than vague superlatives. Cheers!)

[dhimmel]

@StefanKarpinski, my usage is the obvious – mutually recursive type definitions.

@kmsquire, I am working on algorithms for graphs with multiple defined types of nodes and edges. Currently we've implemented the graph algorithms in python and machine learning in R but are considering julia for performance improvements and consolidating our code to a single language.

In the following example, I define types to represent nodes and edges. MetaNode and MetaEdge refer to the type of node or edge and are previously defined. The edges::Dict{MetaEdge, Set{Edge}} field for the Node type allows efficient lookup of edges of a specified kind (metaedge). Since this is an operation that is performed repeatedly, I desire the performance boost that type declaration provides.

type Node
    metanode::MetaNode
    edges::Dict{MetaEdge, Set{Edge}}
end

type Edge
    source::Node
    target::Node
    metaedge::MetaEdge
end

Thanks!

[JeffBezanson]

A workaround that might help is to access the fields via accessor functions:

edges(n::Node) = n.edges::Dict{MetaEdge,Set{Edge}}

This lets you write the type after both declarations. This function will almost certainly be fully inlined everywhere.

[dhimmel]

@JeffBezanson, @StefanKarpinski, Thanks for the elegant workaround. Julia is an entirely new way to program/think for me, and it sure is exciting.

[quinnj]

Just a note that with #3831 merged, we now handle show for circular reference types.

[crsl4]

Hi,
I am having similar issue. I am new to Julia and excited to use it.
I work on graphs and I would like for example:

type Node
index::Int32
edges::Array{Edge,1}
end

type Edge
index::Int32
nodes::Array{Node,1}
end

I've managed to declare both types with the suggestions you mention above without errors anymore, but I want instances of Node and Edge to be linked:
node1=Node(1,[])
node2=Node(2,[])
edge1=Edge(1,[node1,node2])
node1.edges=[edge1]
node2.edges=[edge1]

When I try, I get the "#= circular reference =#" message. Everything seems to work fine, so I wonder if it is ok to ignore such message, or if there is a better way to deal with this.
Thanks! I apologize if my code/notation is not the best, I am just beginning to learn Julia.

[tknopp]

@crsl4: Have you "Any"-typed one of the arrays?
The circular reference message is harmless and only appears at the REPL when you do not put ; at the end of the line.

[crsl4]

@tknopp thanks for your response! Yes, I "Any"-typed one of the arrays to be able to declare the types. I'll use ";" at the end of the lines. Thanks!

[bencherian]

I'm assuming that if you just don't type the mutually dependent yet to be declared type/immutable, then the data stored has an extra layer or indirection. I'm trying to make implement the Quad Edge data structure in Julia. I would like something like this

type DirEdge{DT}
    next::(QuadEdge{DT}, Uint8)
    data::DT
    function DirEdge(next::(QuadEdge{DT}, Uint8)) 
    newedge = new(next, data)
    newedge.next = next
    return newedge
    end

end

immutable QuadEdge{DT}
    record::Vector{DirEdge{DT}}
    function QuadEdge() # Implements MakeEdge
        qe = new(Array(DirEdge{DT},4))
        qe.record[1] = DirEdge{DT}((qe,1))
        qe.record[2] = DirEdge{DT}((qe,4))
        qe.record[3] = DirEdge{DT}((qe,3))
        qe.record[4] = DirEdge{DT}((qe,2))
        # Needs to be completed
    end
end

I could obviously have QuadEdge be a subtype of _QuadEdge and use the abstract supertype for next in DirEdge, but I believe that would result in DirEdge internally storing a pointer to the QuadEdge in next instead of the quad edge directly, which would hinder performance when traversing the subdivision.

Anyone have thoughts on how to avoid this penalty? Or are there clever ways of implementing a quad-edge in Julia that avoid the extra type but still nicely encapsulate the next pointer and stored data?

[JeffBezanson]

As it is, everything needs to be pointers anyway because of the circularity. Using an abstract type will not increase the amount of indirection.

If the Vector in QuadEdge always has 4 elements, it will be more efficient to use a tuple or declare 4 DirEdge fields inside QuadEdge.

[bencherian]

@JeffBezanson
I went through my logic again and realized you are right about the pointers. The abstract supertype solution will do for now. It still feels like the ugliest code I've had to write yet in Julia. (That's not really saying much yet though...we'll see what I think in a few months.)

Edit: Deleted some other stuff as off topic...

[ivarne]

Please ask for advice on the julia-users mailing list. This question is way off topic, and easy to answer for anyone who know how to overload getindex() and setndex!()

[JeffBezanson]

You can access object fields by index instead of name using e.g. obj.(2) or obj.(i).

[o314]

An attempt to recap the current situation as of 2021-01

# u know i'm bugged ain't u
mutable struct A
    name :: Symbol
    bs :: Vector{B}
end
mutable struct B
    a :: A
    val :: Int
end

Patch 1 w Abstract

abstract type AbstractB end
mutable struct A
    name :: Symbol
    bs :: Vector{<:AbstractB}
end
mutable struct B <: AbstractB
    a :: A
    val :: Int
end

A(name::Symbol, vals::Int...) = begin
    a = A(name, B[])
    a.bs = B[B(a, val) for val in vals]
    a
end

using Test
a = A(:foo, 1,2,3)
@test a.name == :foo
@test a.bs isa Vector{B}
@test all(a.bs) do b; b.a==a end
@test all([b.val for b in a.bs] .== 1:3)

Patch 2 w Parametrization

mutable struct A{BE}
    name :: Symbol
    bs :: Vector{BE}
end
mutable struct B
    a :: A
    val :: Int
end

A(name::Symbol, vals::Int...) = begin
    a = A{B}(name, B[])
    a.bs = B[B(a, val) for val in vals]
    a
end

using Test
a = A(:foo, 1,2,3)
@test a.name == :foo
@test a.bs isa Vector{B}
@test all(a.bs) do b; b.a==a end
@test all([b.val for b in a.bs] .== 1:3)

Afterwords

• parametrization is more open, but more and more typevar conducts to less and less useful api. It may lead to the need of macro to impl stuff like that IMO :

mutable struct A{V,B}
    name :: Symbol
    bs :: Vector{B{V}} # will not work without macro IMO
end
mutable struct B{V}
    a :: A
    val :: V
end

# ...

• abstract type is less powerful on the data side. but may be more convenient to attach a functional interface/protocol.

[mauro3]

There is this wild version, discovered on https://discourse.julialang.org/t/how-to-deal-with-recursive-type-dependencies-in-immutable-structs/53173 by @jeffreyesun:

julia> try 
           struct Foo
           a::Bar
           Foo() = new()
           Foo(a) = new(a)
       end
       catch
       end
       
    struct Bar
           b::Foo
           Bar() = new()
           Bar(b) = new(b)
    end

julia> struct Foo
           a::Bar
           Foo() = new()
           Foo(a) = new(a)
       end

julia> Foo(Bar(Foo()))
Foo(Bar(Foo(#undef)))

(Edit: don't actually use this! See #269 (comment))

[o314]

Very wild in deed, i may not try to postulate for a sla manager job where servers run such code here and there o:

Other points

• extending the undef initializer pattern outside the array world may be a good convention to give a hint that a circular ref is happening
• Mason mentions to use both abstract type and parametrization for performance reason https://discourse.julialang.org/t/how-to-deal-with-recursive-type-dependencies-in-immutable-structs/53173/6

EDIT

Here is a tiny variation i use to enforce correct initialization of the circular references

abstract type AbstractB end
mutable struct A
    name :: Symbol
    bs :: Vector{<:AbstractB}
    A(name, bs; unref=true) = begin
        unref && error()
        new(name, bs)
    end
end
mutable struct B <: AbstractB
    a :: A
    val :: Int
    B(a, val; unref=true) = begin
        unref && error()
        new(a, val)
    end
end

A(name::Symbol, vals::Int...) = begin
    a = A(name, B[]; unref=false)
    a.bs = B[B(a, val; unref=false) for val in vals]
    a
end

using Test
a = A(:foo, 1,2,3)
@test a.name == :foo
@test a.bs isa Vector{B}
@test all(a.bs) do b; b.a==a end
@test all([b.val for b in a.bs] .== 1:3)
@test_throws Exception A(:foo, B[]) # enforce circular ref correct initialization

[StefanKarpinski]

I've come to appreciate the incomplete type Foo{Bar} <: Baz; end option that @Keno already implemented over time. It not only works for mutually recursive types but could also allow things like the recursive JSONValue type:

incomplete type JSONValue end
const JSONValue = Union{String, Float64, Bool, Nothing, Dict{String, JSONValue}, Vector{<:JSONValue}}

Keno's implementation didn't allow that but it would be possible to implement it with the same mechanism.

[vtjnash]

That code is risky. The reason it almost works is that we've implemented some of the support for this feature. The reason we don't have it turned on though through syntax is that the layout computation implementation isn't compatible (yet), and it might get confused (segfault or return a pointer in place of a value, that sort of runtime corruption).

[jeffreyesun]

That code is risky. The reason it almost works is that we've implemented some of the support for this feature. The reason we don't have it turned on though through syntax is that the layout computation implementation isn't compatible (yet), and it might get confused (segfault or return a pointer in place of a value, that sort of runtime corruption).

Are you replying to my workaround, posted by @mauro3? I want it known that I have no idea what's going on behind the scenes with that code, and I certainly don't advocate it...

I actually ended up taking @mauro3's suggestion on the original discourse thread and going with an abstract supertype. The code wasn't performance critical at all; I probably could have just used untyped fields!

[mauro3]

@jeffreyesun: this was not meant to frame you. I just thought that it was a pretty awesome discovery. And with Jameson's comment it now makes how it can work.

(BTW it only works since Julia 1.5)

[jeffreyesun]

@mauro3 On the contrary, it was awesome to be referenced!

[StefanKarpinski]

One thing that's a bit odd about the incomplete type T end approach is that you define T as one thing and then later define it as something else, which doesn't quite sit right with me. It might be better if there was a delimited scope where it meant a different thing and after that it consistently means the full definition.

[rapus95]

One thing that's a bit odd about the incomplete type T end approach is that you define T as one thing and then later define it as something else, which doesn't quite sit right with me. It might be better if there was a delimited scope where it meant a different thing and after that it consistently means the full definition.

How about using another keyword like forward, declare, defer etc? I especially like the defer keyword since that might come in handy at some later point in some other place aswell. And it actually describes what it should do. Defer the definition to a later point. But already know that there will be one.
Either

defer type T end

or, in order to not to suggest having a complete definition might use defer as the block close expression:

type T defer
#because I guess the following wouldn't be possible?
defer type T

But to be honest I prefer the first of those options anyway.

[orkolorko]

I'm going through the same issue trying to wrap a C library in Julia. To make the library work structs that mirror the structs in the C header file have to be defined, but they are circularly defined with a forward declaration...

[krrutkow]

@orkolorko You should have a look at CBinding.jl. It effortlessly handles a lot of the complexities of interfacing C libraries, including circular definitions with a builtin workaround to this issue.

[orkolorko]

@krrutkow Thank you, I will give it a look!

[complyue]

I'm still diving into Julia, not deep enough yet. But how about deferring all resolution of :: type annotations until the enclosing module done with the first eval/exec pass?

[andyferris]

Yeah - it would be easier for users if the compiler looked ahead for new type names (in a pre-pass, perhaps even in lowering?) than to ask the user to explicitly do forward declaration (which we tend to avoid elsewhere).

until the enclosing module done

If it was easier to do this per included file rather than per module it would be sufficient (arguably it'd be preferable if users put their mutually-circular definitions closer to one another anyway, to help code readability)

[adkabo]

How about explicitly delimiting the boundaries with a block:

@recursive_types begin 

struct A
b::Union{B,Int}
end

struct B
a::Union{A,Int}
end

end

@recursive_types begin
const JSONValue = Union{String, Float64, Bool, Nothing, Dict{String, JSONValue}, Vector{<:JSONValue}}
end

[sairus7]

Technically, there is a way to enable mutually-circular types in REPL mode.
I don't know exactly how it works, but here it is:

julia> struct MyNode
           index::Int
           edges::Vector{MyEdge}
       end
ERROR: UndefVarError: MyEdge not defined
Stacktrace:
 [1] top-level scope
   @ REPL[1]:1

julia> dump(MyNode)
MyNode <: AnyERROR: cannot determine field types of incomplete type MyNode
Stacktrace:
 [1] datatype_fieldtypes
   @ .\reflection.jl:306 [inlined]
 [2] dump(io::IOContext{Base.TTY}, x::DataType, n::Int64, indent::String)
   @ Base .\show.jl:2662
 [3] dump(io::IOContext{Base.TTY}, x::Any; maxdepth::Int64)
   @ Base .\show.jl:2675
 [4] dump(arg::Type; maxdepth::Int64)
   @ Base .\show.jl:2710
 [5] dump(arg::Type)
   @ Base .\show.jl:2709
 [6] top-level scope
   @ REPL[2]:1

julia> struct MyEdge
           index::Int
           nodes::Vector{MyNode}
       end

julia> struct MyNode
           index::Int
           edges::Vector{MyEdge}
       end

julia> node1=MyNode(1,[])
MyNode(1, MyEdge[])

julia> node2=MyNode(2,[])
MyNode(2, MyEdge[])

julia> edge1=MyEdge(1,[node1,node2])
MyEdge(1, MyNode[MyNode(1, MyEdge[]), MyNode(2, MyEdge[])])

julia> push!(node1.edges, edge1)
1-element Vector{MyEdge}:
 MyEdge(1, MyNode[MyNode(1, MyEdge[#= circular reference @-4 =#]), MyNode(2, MyEdge[])])

julia> push!(node2.edges, edge1)
1-element Vector{MyEdge}:
 MyEdge(1, MyNode[MyNode(1, MyEdge[MyEdge(#= circular reference @-4 =#)]), MyNode(2, MyEdge[#= circular reference @-4 =#])])

[sairus7]

Soоо, seems like this is type-stable code with mutually-recursive types, but with a little bit duplication:

try
struct MyNode
    index::Int
    edges::Vector{MyEdge}
end
catch err
end

struct MyEdge
    index::Int
    nodes::Vector{MyNode}
end

struct MyNode
    index::Int
    edges::Vector{MyEdge}
end

node1=MyNode(1,[])
node2=MyNode(2,[])
edge1=MyEdge(1,[node1,node2])
push!(node1.edges, edge1)
push!(node2.edges, edge1)

Greedy and dirty :)

[complyue]

I can't help but wondering whether "incomplete type" is a feature (intentionally designed) or a bug (by-product of some other design)?

If it's a (or can be converted to a) feature, then only if the UndefVarError is postponed to premature usage, we seem to have a perfect solution thereof!

[o314]

At the syntaxical level, that could go like this

struct Foo
   x :: Qux
   y :: Int

with mutable Bar
  foov :: Vector{Foo}

with Baz
  z :: Foo
  u :: Bar
  v :: Baz

with Qux = Foo | Bar | Baz
with Quux = Bar | Baz
with Quuux = Baz | Foo
end

struct Bye # not recursively defined anymore
  a
  b
end

[vtjnash]

Interesting. That should have rejected the final attempt to set the type, since we already decided the type's memory layout, and now may access undefined memory instead when trying to load from it.

[jeffreyesun]

Soоо, seems like this is type-stable code with mutually-recursive types, but with a little bit duplication:

try
struct MyNode
    index::Int
    edges::Vector{MyEdge}
end
catch err
end

struct MyEdge
    index::Int
    nodes::Vector{MyNode}
end

struct MyNode
    index::Int
    edges::Vector{MyEdge}
end

node1=MyNode(1,[])
node2=MyNode(2,[])
edge1=MyEdge(1,[node1,node2])
push!(node1.edges, edge1)
push!(node2.edges, edge1)

Greedy and dirty :)

I should say that when I actually tried using this sort of approach, I was getting unexplained crashes. I don't recommend you do it like this.