Type inference failing with a stack overflow on 1.7-DEV

[palday]

MWE (sorry that it involves a heavyweight dependency)

using Pkg; Pkg.add("MixedModels")
using MixedModels
using MixedModels: dataset

cbpp = dataset(:cbpp)
form = @formula((incid/hsz) ~ 1 + period + (1|herd))
# fails
glmm = GeneralizedLinearMixedModel(form, cbpp,
                                   Binomial();
                                   wts=float(cbpp.hsz))
#fails
@code_warntype GeneralizedLinearMixedModel(form, cbpp,
                                           Binomial();
                                           wts=float(cbpp.hsz))

On 1.6, we get reasonable behavior:

      @code_warntype GeneralizedLinearMixedModel(form, cbpp,
                                                  Binomial();
                                                  wts=float(cbpp.hsz))
MethodInstance for (::Core.var"#Type##kw")(::NamedTuple{(:wts,), Tuple{Vector{Float64}}}, ::Type{GeneralizedLinearMixedModel}, ::StatsModels.FormulaTerm{StatsModels.FunctionTerm{typeof(/), var"#1#3", (:incid, :hsz)}, Tuple{StatsModels.ConstantTerm{Int64}, StatsModels.Term, StatsModels.FunctionTerm{typeof(|), var"#2#4", (:herd,)}}}, ::Arrow.Table, ::Binomial{Float64})
  from (var"#s35"::Core.var"#Type##kw")(::Any, ::Type{GeneralizedLinearMixedModel}, f::StatsModels.FormulaTerm, tbl, d::Distributions.Distribution) in MixedModels at /home/alex/.julia/dev/MixedModels/src/generalizedlinearmixedmodel.jl:325
Arguments
  #s35::Core.Const(Core.var"#Type##kw"())
  @_2::NamedTuple{(:wts,), Tuple{Vector{Float64}}}
  @_3::Type{GeneralizedLinearMixedModel}
  f::StatsModels.FormulaTerm{StatsModels.FunctionTerm{typeof(/), var"#1#3", (:incid, :hsz)}, Tuple{StatsModels.ConstantTerm{Int64}, StatsModels.Term, StatsModels.FunctionTerm{typeof(|), var"#2#4", (:herd,)}}}
  tbl::Arrow.Table
  d::Binomial{Float64}
Body::GeneralizedLinearMixedModel
1 ─ %1 = MixedModels.canonicallink(d)::Core.Const(LogitLink())
│   %2 = (#s35)(@_2, @_3, f, tbl, d, %1)::GeneralizedLinearMixedModel
└──      return %2

My environment

julia> versioninfo(verbose=true)
Julia Version 1.7.0-DEV.709
Commit 11016bfcb2 (2021-03-15 14:55 UTC)
Platform Info:
  OS: Linux (x86_64-linux-gnu)
      Linux Mint 20.1
  uname: Linux 5.8.0-44-generic #50~20.04.1-Ubuntu SMP Wed Feb 10 21:07:30 UTC 2021 x86_64 x86_64
  CPU: Intel(R) Xeon(R) E-2288G CPU @ 3.70GHz: 
                 speed         user         nice          sys         idle          irq
       #1-16  4781 MHz    3839559 s      18585 s    1265381 s  102100514 s          0 s
       
  Memory: 31.24289321899414 GB (654.33203125 MB free)
  Uptime: 676427.0 sec
  Load Avg:  2.0  1.49  1.24
  WORD_SIZE: 64
  LIBM: libopenlibm
  LLVM: libLLVM-11.0.1 (ORCJIT, skylake)
Environment:
  JULIA_NUM_THREADS = 8
  R_LD_LIBRARY_PATH = /usr/local/lib/julia/
  XDG_SESSION_PATH = /org/freedesktop/DisplayManager/Session0
  MANDATORY_PATH = /usr/share/gconf/cinnamon.mandatory.path
  HOMEBREW_PREFIX = /home/linuxbrew/.linuxbrew
  MANPATH = /home/linuxbrew/.linuxbrew/share/man:/home/linuxbrew/.linuxbrew/share/man::
  HOME = /home/user
  XDG_SEAT_PATH = /org/freedesktop/DisplayManager/Seat0
  INFOPATH = /home/linuxbrew/.linuxbrew/share/info:/home/linuxbrew/.linuxbrew/share/info:
  GEM_HOME = /home/user/gems
  TERM = screen-256color
  DEFAULTS_PATH = /usr/share/gconf/cinnamon.default.path
  HOMEBREW_CELLAR = /home/linuxbrew/.linuxbrew/Cellar
  HOMEBREW_REPOSITORY = /home/linuxbrew/.linuxbrew/Homebrew
  PATH = /home/user/gems/bin:/home/linuxbrew/.linuxbrew/bin:/home/linuxbrew/.linuxbrew/sbin:/home/user/.local/bin:/home/user/.bin:/home/user/gems/bin:/home/user/anaconda3/condabin:/home/linuxbrew/.linuxbrew/bin:/home/linuxbrew/.linuxbrew/sbin:/home/user/.local/bin:/home/user/.bin:/usr/local/sbin:/usr/local/bin:/usr/sbin:/usr/bin:/sbin:/bin:/usr/games:/usr/local/games:/snap/bin:/home/user/.golang/bin:/home/user/.golang/bin
  GOPATH = /home/user/.golang

cc @ararslan @dmbates

[palday]

git bisect brought me to this:

commit 1f21f2d6feacaa5bf3f7ea212c64e98bd66fd265                
Author: Shuhei Kadowaki <[email protected]>                                                          
Date:   Thu Mar 11 05:25:29 2021 +0900                         
                                                                                                                              
    inference: enable constant propagation for union-split signatures (#39305)                                                
                                                                                                                              
    The inference precision of certain functions really relies on constant
    propagation, but currently constant prop' won't happen when a call
    signature is union split and so sometimes inference ends up looser
    return type: e.g.                                                                                                         
    ```julia                                                   
    julia>                                                                                                                    
    Base.return_types((Union{Tuple{Int,Nothing},Tuple{Int,Missing}},)) do t
               a, b = t                                        
               a # I expected a::Int, but a::Union{Missing,Nothing,Int}
           end |

[ararslan]

cc @aviatesk

[aviatesk]

Thanks for your detailed issue report. I'll look into this during the weekend.

[JeffBezanson]

The stack overflow is in type intersection, so I doubt it's a bug in that PR specifically.

[vtjnash]

I tried to run this, and it seemed to work fine for me, both on master, and that commit. Are you able to run rr (./julia --bug-report=rr) on this?

(@v1.1) pkg> st MixedModels
      Status `~/.julia/environments/v1.1/Project.toml`
  [ff71e718] MixedModels v3.4.1

[palday]

Will do, but in the meantime this first started showing up on our CI for julia-nightly (called "Future" in our GHA). Here's one example that hasn't been garbage collected yet: https://github.com/JuliaStats/MixedModels.jl/runs/2090575505?check_suite_focus=true

[dmbates]

I was able to trigger a similar StackOverflowError in another part of our test suite. Here is a simpler example

bates@Aspire-A515-56:~$ julia-nightly -t 4 -O3 
               _
   _       _ _(_)_     |  Documentation: https://docs.julialang.org
  (_)     | (_) (_)    |
   _ _   _| |_  __ _   |  Type "?" for help, "]?" for Pkg help.
  | | | | | | |/ _` |  |
  | | |_| | | | (_| |  |  Version 1.7.0-DEV.762 (2021-03-28)
 _/ |\__'_|_|_|\__'_|  |  Commit 40267bb03d* (1 day old master)
|__/                   |

julia> using MixedModels

julia> using Random

julia> fm = fit(MixedModel, @formula(yield ~ 1+(1|batch)), MixedModels.dataset(:dyestuff))
Linear mixed model fit by maximum likelihood
 yield ~ 1 + (1 | batch)
   logLik   -2 logLik     AIC       AICc        BIC    
  -163.6635   327.3271   333.3271   334.2501   337.5307

Variance components:
            Column    Variance Std.Dev.
batch    (Intercept)  1388.3332 37.2603
Residual              2451.2501 49.5101
 Number of obs: 30; levels of grouping factors: 6

  Fixed-effects parameters:
────────────────────────────────────────────────
              Coef.  Std. Error      z  Pr(>|z|)
────────────────────────────────────────────────
(Intercept)  1527.5     17.6946  86.33    <1e-99
────────────────────────────────────────────────

julia> samp = parametricbootstrap(MersenneTwister(1234321), 100, fm)
Progress: 100%|███████████████████████████████████████████████████████████████████████████████████████████████████████████| Time: 0:00:00
MixedModelBootstrap{Float64}(NamedTuple{(:objective, :σ, :β, :se, :θ), Tuple{Float64, Float64, NamedTuple{(Symbol("(Intercept)"),), Tuple{Float64}}, StaticArrays.SVector{1, Float64}, StaticArrays.SVector{1, Float64}}}[(objective = 339.0218641595563, σ = 67.43149101553416, β = ((Intercept) = 1509.1284452530542,), se = [13.627395181453002], θ = [0.21224549103003246]), (objective = 322.6888354110108, σ = 47.98309598035959, β = ((Intercept) = 1538.0812178511553,), se = [13.626954777541815], θ = [0.5328401598023007]), (objective = 324.00164566948195, σ = 50.13459890828718, β = ((Intercept) = 1508.0209150702349,), se = [12.755981711483347], θ = [0.43407615020099666]), (objective = 331.8870128849374, σ = 53.223777443862694, β = ((Intercept) = 1538.4726943803653,), se = [19.374131591781268], θ = [0.7713828678125624]), (objective = 317.7713479160508, σ = 45.29750545442813, β = ((Intercept) = 1520.6230383631485,), se = [11.388982581198134], θ = [0.42342767795431846]), (objective = 315.18080940170603, σ = 36.75557710139419, β = ((Intercept) = 1536.9434757710696,), se = [21.170658823139625], θ = [1.3381150539334468]), (objective = 333.6410319678268, σ = 53.81608798609473, β = ((Intercept) = 1519.88344937394,), se = [21.45243483681328], θ = [0.8679925437799068]), (objective = 325.72878851041907, σ = 47.898905647654665, β = ((Intercept) = 1528.427793310579,), se = [17.679463684119536], θ = [0.7857523716564815]), (objective = 311.60088321882165, σ = 41.400032156386224, β = ((Intercept) = 1497.4612421601812,), se = [9.760291640326935], θ = [0.3653551275709431]), (objective = 335.2440119476761, σ = 64.61597465652851, β = ((Intercept) = 1532.6529758691388,), se = [11.797208964854264], θ = [0.0])  …  (objective = 317.98692372232665, σ = 41.177859263461485, β = ((Intercept) = 1549.776729352635,), se = [16.979658890560412], θ = [0.9056441710579907]), (objective = 320.5920235610596, σ = 46.03376032367043, β = ((Intercept) = 1535.4160352990684,), se = [13.507031707227771], θ = [0.562633913753437]), (objective = 327.5030394413276, σ = 49.6844529289097, β = ((Intercept) = 1490.4401431462202,), se = [17.705234551975064], θ = [0.7496181732833448]), (objective = 332.19522057939116, σ = 53.38139114288901, β = ((Intercept) = 1531.791782641363,), se = [19.64445032817108], θ = [0.7826571019153903]), (objective = 332.54952008583496, σ = 55.632059992722745, β = ((Intercept) = 1526.1590897018484,), se = [17.15226158388399], θ = [0.6085663691161599]), (objective = 330.8536495516082, σ = 56.79654888676652, β = ((Intercept) = 1537.316615520655,), se = [13.70750984338548], θ = [0.3866286835928947]), (objective = 330.6549684701264, σ = 55.860183567190575, β = ((Intercept) = 1538.5506211920106,), se = [14.409417157941524], θ = [0.4463685544767057]), (objective = 334.24348731922026, σ = 55.697200474699464, β = ((Intercept) = 1545.3919628575006,), se = [19.660529492687107], θ = [0.7400065650171074]), (objective = 331.86164307707213, σ = 54.92464025070719, β = ((Intercept) = 1524.5400892509165,), se = [17.047393063696628], θ = [0.6148223706907177]), (objective = 317.70278059776393, σ = 43.260307224334014, β = ((Intercept) = 1524.9258446326094,), se = [13.612633159826975], θ = [0.6277703378932419])], LinearAlgebra.LowerTriangular{Float64, Matrix{Float64}}[[0.7525806394967323]], [[1]], [0.0], (batch = ("(Intercept)",),))

julia> samp.fits
Internal error: encountered unexpected error in runtime:
StackOverflowError()
intersect at /home/bates/git/julia/src/subtype.c:2944
intersect at /home/bates/git/julia/src/subtype.c:3044
intersect at /home/bates/git/julia/src/subtype.c:3044
intersect at /home/bates/git/julia/src/subtype.c:3060
intersect_unionall_ at /home/bates/git/julia/src/subtype.c:2538
intersect_unionall at /home/bates/git/julia/src/subtype.c:2587
intersect at /home/bates/git/julia/src/subtype.c:3096
intersect_all at /home/bates/git/julia/src/subtype.c:3186
intersect_aside at /home/bates/git/julia/src/subtype.c:2092 [inlined]
intersect_aside at /home/bates/git/julia/src/subtype.c:2079 [inlined]
intersect_var at /home/bates/git/julia/src/subtype.c:2306
intersect at /home/bates/git/julia/src/subtype.c:3044
intersect at /home/bates/git/julia/src/subtype.c:3044
intersect at /home/bates/git/julia/src/subtype.c:3044
intersect at /home/bates/git/julia/src/subtype.c:3044
intersect at /home/bates/git/julia/src/subtype.c:3060
intersect_unionall_ at /home/bates/git/julia/src/subtype.c:2538
intersect_unionall at /home/bates/git/julia/src/subtype.c:2587
intersect at /home/bates/git/julia/src/subtype.c:3096
intersect_all at /home/bates/git/julia/src/subtype.c:3186
intersect_aside at /home/bates/git/julia/src/subtype.c:2092 [inlined]
intersect_aside at /home/bates/git/julia/src/subtype.c:2079 [inlined]
intersect_var at /home/bates/git/julia/src/subtype.c:2306
intersect at /home/bates/git/julia/src/subtype.c:3044
intersect at /home/bates/git/julia/src/subtype.c:3044
intersect at /home/bates/git/julia/src/subtype.c:3044
intersect at /home/bates/git/julia/src/subtype.c:3044
intersect at /home/bates/git/julia/src/subtype.c:3060
intersect_unionall_ at /home/bates/git/julia/src/subtype.c:2538
intersect_unionall at /home/bates/git/julia/src/subtype.c:2587
...

[chriscoey]

bump! this is causing #40350

[chriscoey]

if this can't be fixed, does anyone know how to avoid triggering it? it's a bit tough to even figure out where in my code it is coming from.
edit: I managed to "fix" it accidentally by changing a bunch of code but I can't narrow it down to a single change

[KristofferC]

I tried to run this, and it seemed to work fine for me, both on master, and that commit.

I could repro consistently with the example in #40048 (comment). Does that work for you @vtjnash?

[StefanKarpinski]

People on Slack are reporting hitting this in 1.7.0-beta3.

[KristofferC]

Should be fixed by #41091.

[JeffBezanson]

Reduced example:

julia> typeintersect(Tuple{Type{T}, Vararg{T}} where T,
                     Tuple{Type{U}, Union{Ref{S}, Ref{U}, Int}, Union{Ref{S}, S}} where S where U)
ERROR: StackOverflowError:

[JeffBezanson]

Ok that one fails for a slightly different reason. This one tracks the issue better:

typeintersect(Tuple{Ref{T}, Vararg{T}} where T,
              Tuple{Ref{U}, Union{Ref{S}, Ref{U}, Ref{W}}, Union{Ref{S}, W, V}} where V<:AbstractArray where W where S where U)