Julia 1.0/1.1 can't handle deep nested structs

[felipenoris]

I'm migrating code from v0.6 to v1.0/v1.1 , and I found this issue that breaks Julia.

abstract type AbstractNode end                                                                                                                                                                                     
                                                                                                                                                                                                                   
struct Node{N1<:AbstractNode, N2<:AbstractNode} <: AbstractNode                                                                                                                                                    
    a::N1                                                                                                                                                                                                          
    b::N2                                                                                                                                                                                                          
end                                                                                                                                                                                                                
                                                                                                                                                                                                                   
struct Leaf <: AbstractNode                                                                                                                                                                                        
end                                                                                                                                                                                                                
                                                                                                                                                                                                                   
function gen_nodes(qty::Integer) :: AbstractNode                                                                                                                                                                   
    @assert qty > 0                                                                                                                                                                                                
    result = Leaf()                                                                                                                                                                                                
                                                                                                                                                                                                                   
    for i in 1:qty                                                                                                                                                                                                 
        result = Node(result, Leaf())                                                                                                                                                                              
    end                                                                                                                                                                                                            
                                                                                                                                                                                                                   
    return result                                                                                                                                                                                                  
end

Running on Julia v1.0 or v1.1, it runs ok for 10 nested elements, but it never finishes if I try to nest about 50 elements. In the example below, I had to use CTRL+C to cancel.

julia> include("issue.jl")                                                                                                                                                                                         
gen_nodes (generic function with 1 method)                                                                                                                                                                                                                                                                                                                                                                                            

julia> gen_nodes(10)                                                                                                                                                                                               
Node{Node{Node{Node{Node{Node{Node{Node{Node{Node{Leaf,Leaf},Leaf},Leaf},Leaf},Leaf},Leaf},Leaf},Leaf},Leaf},Leaf}(Node{Node{Node{Node{Node{Node{Node{Node{Node{Leaf,Leaf},Leaf},Leaf},Leaf},Leaf},Leaf},Leaf},Leaf},Leaf}(Node{Node{Node{Node{Node{Node{Node{Node{Leaf,Leaf},Leaf},Leaf},Leaf},Leaf},Leaf},Leaf},Leaf}(Node{Node{Node{Node{Node{Node{Node{Leaf,Leaf},Leaf},Leaf},Leaf},Leaf},Leaf},Leaf}(Node{Node{Node{Node{Node{Node{Leaf,Leaf},Leaf},Leaf},Leaf},Leaf},Leaf}(Node{Node{Node{Node{Node{Leaf,Leaf},Leaf},Leaf},Leaf},Leaf}(Node{Node{Node{Node{Leaf,Leaf},Leaf},Leaf},Leaf}(Node{Node{Node{Leaf,Leaf},Leaf},Leaf}(Node{Node{Leaf,Leaf},Leaf}(Node{Leaf,Leaf}(Leaf(), Leaf()), Leaf()), Leaf()), Leaf()), Leaf()), Leaf()), Leaf()), Leaf()), Leaf()), Leaf())                                                                                                                                                                                                                                                                                                                

julia> gen_nodes(50)                                                                                                                                                                                               ^C^C^C^C^C^C^C^C^CWARNING: Force throwing a SIGINT                                                                                                                                                                 
Internal error: encountered unexpected error in runtime:                                                                                                                                                           InterruptException()                                                                                                                                                                                               is_derived_type at ./compiler/typelimits.jl:32                                                                                                                                                                     is_derived_type at ./compiler/typelimits.jl:57                                                                                                                                                                     
is_derived_type at ./compiler/typelimits.jl:68                                                                                                                                                                     
is_derived_type at ./compiler/typelimits.jl:57 
is_derived_type at ./compiler/typelimits.jl:57                                                                                                                                                                     
...
is_derived_type_from_any at ./compiler/typelimits.jl:77                                                                                                                                                            
type_more_complex at ./compiler/typelimits.jl:199                                                                                                                                                                  limit_type_size at ./compiler/typelimits.jl:20                                                                                                                                                                     jfptr_limit_type_size_5660.clone_1 at /home/felipenoris/local/julia-1.1.0/lib/julia/sys.so (unknown line)                                                                                                          jl_apply_generic at /buildworker/worker/package_linux64/build/src/gf.c:2219                                                                                                                                        
abstract_call_method at ./compiler/abstractinterpretation.jl:300                                                                                                                                                   
abstract_call_gf_by_type at ./compiler/abstractinterpretation.jl:85

The same code runs without issues on Julia v0.6, even if I increase to 1000 nested elements.

julia> include("issue.jl")
gen_nodes (generic function with 1 method)

julia> gen_nodes(50)
Node{Node{Node{Node{Node{Node{Node{Node{Node{Node{Node{Node{Node{Node{Node{Node{Node{Node{Node{Node{Node{Node{Node{Node{Node{Node{Node{Node{Node{Node{Node{Node{Node{Node{Node{Node{Node{Node{Node{Node{Node{Node{Node{Node{Node{Node{Node{Node{Node{Node{Leaf,Leaf},Leaf},Leaf},Leaf},Leaf},Leaf},Leaf},Leaf},Leaf},Leaf},Leaf},Leaf},Leaf},Leaf},Leaf},Leaf},Leaf},Leaf},Leaf},Leaf},Leaf},Leaf},Leaf},Leaf},Leaf},Leaf},Leaf},Leaf},Leaf},Leaf},Leaf},Leaf},Leaf},Leaf},Leaf},Leaf},Leaf},Leaf},Leaf},Leaf},Leaf},Leaf},Leaf},Leaf},Leaf},Leaf},Leaf},Leaf},Leaf},Leaf}(Node{Node{Node{Node{Node{Node{Node{Node{Node{Node{Node{Node{Node{Node{Node{Node{Node{Node{Node{Node{Node{Node{Node{Node{Node{Node{Node{Node{Node{Node{Node{Node{Node{Node{Node{Node{Node{Node{Node{Node{Node{Node{Node{Node{Node{Node{Node{Node{Node{Leaf,Leaf},Leaf},Leaf},Leaf},Leaf},Leaf},Leaf},Leaf},Leaf},Leaf},Leaf},Leaf},Leaf},Leaf},Leaf},Leaf},Leaf},Leaf},Leaf},Leaf},Leaf},Leaf},Leaf},Leaf},Leaf},Leaf},Leaf},Leaf},Leaf},Leaf},Leaf},Leaf},Leaf},Leaf},Leaf},Leaf},Leaf},Leaf},Leaf},Leaf},Leaf},Leaf},Leaf},Leaf},Leaf},Leaf},Leaf},Leaf},Leaf}(Node{Node{Node{Node{Node{Node{Node{Node{Node{Node{Node{Node{Node{Node{Node{Node{Node{Node{Node{Node{Node{Node{Node{Node{Node{Node{Node{Node{Node{Node{Node{Node{Node{Node{Node{Node{Node{Node{Node{Node{Node{Node{Node{Node{Node{Node{Node{Node{Leaf,Leaf},Leaf},Leaf},Leaf},Leaf},Leaf},Leaf},Leaf},Leaf},Leaf},Leaf},Leaf},Leaf},Leaf},Leaf},Leaf},Leaf},Leaf},Leaf},Leaf},Leaf},Leaf},Leaf},Leaf},Leaf},Leaf},Leaf},Leaf},Leaf},Leaf},Leaf},Leaf},Leaf},Leaf},Leaf},Leaf},Leaf},Leaf},Leaf},Leaf},Leaf},Leaf},Leaf},Leaf},Leaf},Leaf},Leaf},Leaf}(Node{Node{Node{Node{Node{Node{Node{Node{Node{Node{Node{Node{Node{Node{Node{Node{Node{Node{Node{Node{Node{Node{Node{Node{Node{Node{Node{Node{Node{Node{Node{Node{Node{Node{Node{Node{Node{Node{Node{Node{Node{Node{Node{Node{Node{Node{Node{Leaf,Leaf},Leaf},Leaf},Leaf},Leaf},Leaf},Leaf},Leaf},Leaf},Leaf},Leaf},Leaf},Leaf},Leaf},Leaf},Leaf},Leaf},Leaf},Leaf},Leaf},Leaf},Leaf},Leaf},Leaf},Leaf},Leaf},Leaf},Leaf},Leaf},Leaf},Leaf},Leaf},Leaf},Leaf},Leaf},Leaf},Leaf},Leaf},Leaf},Leaf},Leaf},Leaf},Leaf},Leaf},Leaf},Leaf},Leaf}
...

I would say that this is a major issue for any code that deals with trees or similar data structures.

[felipenoris]

I did a few more tests, and it looks like Julia is able to construct the value, but it can't print it.
If I define

Base.show(io::IO, n::AbstractNode) = print(io, "a node")

it succeeds:

julia> c = gen_nodes(1000)
a node

julia> c.a
a node

But my original issue arised from a type that had customized show method. So it looks like that the problem is not in the default show method, but something more general.

[JeffBezanson]

Possibly related to #31572?

[felipenoris]

Yes. I'm having other side effects beyond printing, related to structs with many type parameters. I'm trying to isolate the problem, but it looks like related to #31572.

[felipenoris]

This example exposes the problem regarding other side effects beyond printing:

abstract type AbstractNode end

struct Node{N1<:AbstractNode, N2<:AbstractNode} <: AbstractNode
    a::N1
    b::N2
end

struct Leaf <: AbstractNode
end

function gen_nodes(qty::Integer) :: AbstractNode
    @assert qty > 0
    result = Leaf()

    for i in 1:qty
        result = Node(result, Leaf())
    end

    return result
end

count_leafs(l::Leaf) = 1
count_leafs(n::Node) = count_leafs(n.a) + count_leafs(n.b)

# this function call triggers the problem and does not return
count_leafs(gen_nodes(50))

[felipenoris]

This is great! 8a6271b fixes both the printing and also this new example I came up with.