Regression: simple loop in v1.9 hangs when iterating over elements of a linked list

[berndblasius]

Here is a conceived example of simple heterogeneous linked list:

struct List{T}
  head :: T
  tail :: List{T}
  List{T}() where T = new()    # emply list is incompletely defined
  List{T}(x::T,l::List{T}) where T = new(x,l)
end

const ElemType = Union{Int,List}
const NIL = List{ElemType}()
cons(x,y) = List{ElemType}(x,y) 

pop(q::List) = (q.head, q.tail)
iscons(q::List) = isdefined(q,:tail)

When running reverse2 function over a small list Julia hangs (the loop does not terminate)

function reverse2(q)
  println("start")
  q1 = NIL
  while iscons(q)
  #while q != NIL  # generates the same problem
    head, q = pop(q)
    q1 = cons(head,q1)
  end
  q1
end

reverse2(cons(1, NIL))

The function does not even print "start", so maybe it is stuck already during compilation (?)
The problem appears with Julia 1.9.0. This was not an issue for earlier Julia versions, e.g. 1.6 or 1.7 (did not check on 1.8).

Interstingly, the problem does not appear when the list is not passed to, but constructed inside, the function

function reverse1()
  println("start")  
  q = cons(1,NIL)  
  q1 = NIL
  while iscons(q)
    head, q = pop(q)
    q1 = cons(head,q1)
  end
  q1
end

reverse1()

[KristofferC]

Seems fixed on master.

julia> reverse2(cons(1, NIL))
start
List{ElemType}(1, List{ElemType}(#undef, #undef))

On 1.9, Ctrl+C gives

julia> reverse2(cons(1, NIL))
^C^C^C^C^CWARNING: Force throwing a SIGINT
Internal error: encountered unexpected error in runtime:
InterruptException()
isvarargtype at ./essentials.jl:377 [inlined]
⊑ at ./compiler/typelattice.jl:263
⊑ at ./compiler/typelattice.jl:273
⊑ at ./compiler/typelattice.jl:273
⊑ at ./compiler/typelattice.jl:273
⊑ at ./compiler/typelattice.jl:273
⊑ at ./compiler/typelattice.jl:273
⊑ at ./compiler/typelattice.jl:273
⊑ at ./compiler/typelattice.jl:273
^C⊑ at ./compiler/typelattice.jl:273
⊑ at ./compiler/typelattice.jl:273
⊑ at ./compiler/typelattice.jl:273
⊑ at ./compiler/typelattice.jl:273
⊑ at ./compiler/typelattice.jl:273
⊑ at ./compiler/typelattice.jl:273
⊑ at ./compiler/typelattice.jl:273
⊑ at ./compiler/typelattice.jl:273
⊑ at ./compiler/typelattice.jl:273
⊑ at ./compiler/typelattice.jl:273
^C⊑ at ./compiler/typelattice.jl:273
⊑ at ./compiler/typelattice.jl:273
⊑ at ./compiler/typelattice.jl:273
⊑ at ./compiler/typelattice.jl:273
⊑ at ./compiler/typelattice.jl:273
⊑ at ./compiler/typelattice.jl:273
⊑ at ./compiler/typelattice.jl:273
....

[gbaraldi]

Fix bisected to #49271. Not sure when it broke. During the bisect the sigint printing changed but it still hung.

[vtjnash]

Fascinating to get a test case for that PR finally, 1 month after writing it.

[gbaraldi]

Is that PR backportable to 1.9?