StackOverflowError on Julia type-inference itself

[henriquebecker91]

Original Discouse discussion (only for history, no extra relevant info there).

The following was obtained using Julia 1.6.0-beta1, this version was chosen to be able to use the --bug-report=rr flag, but the problem also happens in 1.5.3 (other versions not tested). I used a clean .julia for this (i.e., moved the old folder somewhere else before the command below).

Reproduction:

$ git clone https://github.com/henriquebecker91/GuillotineModels.jl
$ cd GuillotineModels.jl/examples
$ git checkout 2c979b7f # commit that I am sure to have the problem
$ wget https://pastebin.com/raw/pUWn5BJP # toy instance of my problem, needed for the called function
$ julia-1.6.0-beta1 --project=@. 
julia> import Pkg
julia> Pkg.instantiate() # instantiate and get out to not pollute the logs
$ julia-1.6.0-beta1 --project=@. --bug-report=rr # first time it installs rr but fails, maybe do not play nice with --project=@. ?
$ julia-1.6.0-beta1 --project=@. --bug-report=rr # second time it works
julia> import Pkg
julia> Pkg.activate(".") # --project=@. really does not play nice with --bug-report=rr, I need to activate the Project manually
julia> using GuillotineModels, GLPK
julia> GuillotineModels.CommandLine.run(["G2CSP", "CPG_SSSCSP", "PPG2KP", "GLPK", "./pUWn5BJP", "--do-not-solve"])

The result is a very long error (but that mostly repeats itself starting with):

Internal error: encountered unexpected error in runtime:
StackOverflowError()
init_stenv at /buildworker/worker/package_linux64/build/src/subtype.c:1484 [inlined]
subtype_in_env_ at /buildworker/worker/package_linux64/build/src/subtype.c:1898
subtype_bounds_in_env at /buildworker/worker/package_linux64/build/src/subtype.c:1917 [inlined]
try_subtype_in_env at /buildworker/worker/package_linux64/build/src/subtype.c:2200 [inlined]
intersect_var at /buildworker/worker/package_linux64/build/src/subtype.c:2313
intersect at /buildworker/worker/package_linux64/build/src/subtype.c:3023
intersect_all at /buildworker/worker/package_linux64/build/src/subtype.c:3170
intersect_aside at /buildworker/worker/package_linux64/build/src/subtype.c:2147
intersect_var at /buildworker/worker/package_linux64/build/src/subtype.c:2316
intersect at /buildworker/worker/package_linux64/build/src/subtype.c:3023
intersect_all at /buildworker/worker/package_linux64/build/src/subtype.c:3170
intersect_aside at /buildworker/worker/package_linux64/build/src/subtype.c:2147
intersect_var at /buildworker/worker/package_linux64/build/src/subtype.c:2316
intersect at /buildworker/worker/package_linux64/build/src/subtype.c:3016
intersect_all at /buildworker/worker/package_linux64/build/src/subtype.c:3170
intersect_aside at /buildworker/worker/package_linux64/build/src/subtype.c:2147
var_lt at /buildworker/worker/package_linux64/build/src/subtype.c:589
subtype at /buildworker/worker/package_linux64/build/src/subtype.c:1256
subtype at /buildworker/worker/package_linux64/build/src/subtype.c:1254
subtype_tuple_tail at /buildworker/worker/package_linux64/build/src/subtype.c:1085
subtype_tuple at /buildworker/worker/package_linux64/build/src/subtype.c:1168 [inlined]
subtype at /buildworker/worker/package_linux64/build/src/subtype.c:1323
with_tvar at /buildworker/worker/package_linux64/build/src/subtype.c:745
subtype_unionall at /buildworker/worker/package_linux64/build/src/subtype.c:839 [inlined]
subtype at /buildworker/worker/package_linux64/build/src/subtype.c:1282
exists_subtype at /buildworker/worker/package_linux64/build/src/subtype.c:1426 [inlined]
forall_exists_subtype at /buildworker/worker/package_linux64/build/src/subtype.c:1454
subtype_in_env_ at /buildworker/worker/package_linux64/build/src/subtype.c:1907
subtype_bounds_in_env at /buildworker/worker/package_linux64/build/src/subtype.c:1917 [inlined]
try_subtype_in_env at /buildworker/worker/package_linux64/build/src/subtype.c:2200 [inlined]
intersect_var at /buildworker/worker/package_linux64/build/src/subtype.c:2313
intersect at /buildworker/worker/package_linux64/build/src/subtype.c:3019
intersect_all at /buildworker/worker/package_linux64/build/src/subtype.c:3170
intersect_aside at /buildworker/worker/package_linux64/build/src/subtype.c:2147
var_lt at /buildworker/worker/package_linux64/build/src/subtype.c:589
subtype at /buildworker/worker/package_linux64/build/src/subtype.c:1256
exists_subtype at /buildworker/worker/package_linux64/build/src/subtype.c:1426 [inlined]
forall_exists_subtype at /buildworker/worker/package_linux64/build/src/subtype.c:1454
subtype_in_env_ at /buildworker/worker/package_linux64/build/src/subtype.c:1907
subtype_bounds_in_env at /buildworker/worker/package_linux64/build/src/subtype.c:1917 [inlined]
try_subtype_in_env at /buildworker/worker/package_linux64/build/src/subtype.c:2200 [inlined]
intersect_var at /buildworker/worker/package_linux64/build/src/subtype.c:2313
intersect at /buildworker/worker/package_linux64/build/src/subtype.c:3019
intersect_all at /buildworker/worker/package_linux64/build/src/subtype.c:3170
intersect_aside at /buildworker/worker/package_linux64/build/src/subtype.c:2147
var_lt at /buildworker/worker/package_linux64/build/src/subtype.c:589
subtype at /buildworker/worker/package_linux64/build/src/subtype.c:1256
exists_subtype at /buildworker/worker/package_linux64/build/src/subtype.c:1426 [inlined]
forall_exists_subtype at /buildworker/worker/package_linux64/build/src/subtype.c:1454
...

It is interesting that after printing all the error message, the code continue executing, I have the output of some @shows of my code, and then inference fails again, this time ending with:

abstract_call_method at ./compiler/abstractinterpretation.jl:478
abstract_call_gf_by_type at ./compiler/abstractinterpretation.jl:141
abstract_call at ./compiler/abstractinterpretation.jl:1036
abstract_call at ./compiler/abstractinterpretation.jl:1022
abstract_eval_statement at ./compiler/abstractinterpretation.jl:1144
typeinf_local at ./compiler/abstractinterpretation.jl:1383
typeinf_nocycle at ./compiler/abstractinterpretation.jl:1454
_typeinf at ./compiler/typeinfer.jl:216
typeinf at ./compiler/typeinfer.jl:211
typeinf_edge at ./compiler/typeinfer.jl:745
abstract_call_method at ./compiler/abstractinterpretation.jl:478
abstract_call_gf_by_type at ./compiler/abstractinterpretation.jl:141
abstract_call_known at ./compiler/abstractinterpretation.jl:1015
abstract_call at ./compiler/abstractinterpretation.jl:1038
abstract_call at ./compiler/abstractinterpretation.jl:1022
abstract_eval_statement at ./compiler/abstractinterpretation.jl:1144
typeinf_local at ./compiler/abstractinterpretation.jl:1398
typeinf_nocycle at ./compiler/abstractinterpretation.jl:1454
_typeinf at ./compiler/typeinfer.jl:216
typeinf at ./compiler/typeinfer.jl:211
typeinf_ext at ./compiler/typeinfer.jl:835
typeinf_ext_toplevel at ./compiler/typeinfer.jl:868
typeinf_ext_toplevel at ./compiler/typeinfer.jl:864
jfptr_typeinf_ext_toplevel_10360.clone_1 at /opt/julia-1.6.0-beta1/lib/julia/sys.so (unknown line)
_jl_invoke at /buildworker/worker/package_linux64/build/src/gf.c:2224 [inlined]
jl_apply_generic at /buildworker/worker/package_linux64/build/src/gf.c:2406
jl_apply at /buildworker/worker/package_linux64/build/src/julia.h:1703 [inlined]
jl_type_infer at /buildworker/worker/package_linux64/build/src/gf.c:296
jl_generate_fptr at /buildworker/worker/package_linux64/build/src/jitlayers.cpp:340
jl_compile_method_internal at /buildworker/worker/package_linux64/build/src/gf.c:1957
jl_compile_method_internal at /buildworker/worker/package_linux64/build/src/gf.c:2223 [inlined]
_jl_invoke at /buildworker/worker/package_linux64/build/src/gf.c:2216 [inlined]
jl_apply_generic at /buildworker/worker/package_linux64/build/src/gf.c:2406
macro expansion at ./timing.jl:279 [inlined]
macro expansion at /home/henrique/AreaDeTrabalho/julia_bug_stackoverflow/GuillotineModels.jl/src/CommandLine.jl:874 [inlined]
#26 at /home/henrique/.julia/packages/TimerOutputs/ZmKD7/src/TimerOutput.jl:237
_jl_invoke at /buildworker/worker/package_linux64/build/src/gf.c:2224 [inlined]
jl_apply_generic at /buildworker/worker/package_linux64/build/src/gf.c:2406
timeit at /home/henrique/.julia/packages/TimerOutputs/ZmKD7/src/TimerOutput.jl:285
_jl_invoke at /buildworker/worker/package_linux64/build/src/gf.c:2224 [inlined]
jl_apply_generic at /buildworker/worker/package_linux64/build/src/gf.c:2406
#run#25 at /home/henrique/.julia/packages/TimerOutputs/ZmKD7/src/TimerOutput.jl:236
_jl_invoke at /buildworker/worker/package_linux64/build/src/gf.c:2224 [inlined]
jl_apply_generic at /buildworker/worker/package_linux64/build/src/gf.c:2406
run at /home/henrique/.julia/packages/TimerOutputs/ZmKD7/src/TimerOutput.jl:254
_jl_invoke at /buildworker/worker/package_linux64/build/src/gf.c:2224 [inlined]
jl_apply_generic at /buildworker/worker/package_linux64/build/src/gf.c:2406
jl_apply at /buildworker/worker/package_linux64/build/src/julia.h:1703 [inlined]
do_call at /buildworker/worker/package_linux64/build/src/interpreter.c:115
eval_value at /buildworker/worker/package_linux64/build/src/interpreter.c:204
eval_stmt_value at /buildworker/worker/package_linux64/build/src/interpreter.c:155 [inlined]
eval_body at /buildworker/worker/package_linux64/build/src/interpreter.c:561
jl_interpret_toplevel_thunk at /buildworker/worker/package_linux64/build/src/interpreter.c:669
top-level scope at REPL[8]:1
jl_toplevel_eval_flex at /buildworker/worker/package_linux64/build/src/toplevel.c:879
jl_toplevel_eval_flex at /buildworker/worker/package_linux64/build/src/toplevel.c:827
jl_toplevel_eval_in at /buildworker/worker/package_linux64/build/src/toplevel.c:931
eval at ./boot.jl:360
_jl_invoke at /buildworker/worker/package_linux64/build/src/gf.c:2224 [inlined]
jl_apply_generic at /buildworker/worker/package_linux64/build/src/gf.c:2406
eval_user_input at /buildworker/worker/package_linux64/build/usr/share/julia/stdlib/v1.6/REPL/src/REPL.jl:139
repl_backend_loop at /buildworker/worker/package_linux64/build/usr/share/julia/stdlib/v1.6/REPL/src/REPL.jl:200
start_repl_backend at /buildworker/worker/package_linux64/build/usr/share/julia/stdlib/v1.6/REPL/src/REPL.jl:185
#run_repl#42 at /buildworker/worker/package_linux64/build/usr/share/julia/stdlib/v1.6/REPL/src/REPL.jl:317
run_repl at /buildworker/worker/package_linux64/build/usr/share/julia/stdlib/v1.6/REPL/src/REPL.jl:305
_jl_invoke at /buildworker/worker/package_linux64/build/src/gf.c:2224 [inlined]
jl_apply_generic at /buildworker/worker/package_linux64/build/src/gf.c:2406
#875 at ./client.jl:387
jfptr_YY.875_36004.clone_1 at /opt/julia-1.6.0-beta1/lib/julia/sys.so (unknown line)
_jl_invoke at /buildworker/worker/package_linux64/build/src/gf.c:2224 [inlined]
jl_apply_generic at /buildworker/worker/package_linux64/build/src/gf.c:2406
jl_apply at /buildworker/worker/package_linux64/build/src/julia.h:1703 [inlined]
do_apply at /buildworker/worker/package_linux64/build/src/builtins.c:672
jl_f__apply_latest at /buildworker/worker/package_linux64/build/src/builtins.c:722
#invokelatest#2 at ./essentials.jl:707 [inlined]
invokelatest at ./essentials.jl:706 [inlined]
run_main_repl at ./client.jl:372
exec_options at ./client.jl:302
_start at ./client.jl:485
jfptr__start_40814.clone_1 at /opt/julia-1.6.0-beta1/lib/julia/sys.so (unknown line)
_jl_invoke at /buildworker/worker/package_linux64/build/src/gf.c:2224 [inlined]
jl_apply_generic at /buildworker/worker/package_linux64/build/src/gf.c:2406
jl_apply at /buildworker/worker/package_linux64/build/src/julia.h:1703 [inlined]
true_main at /buildworker/worker/package_linux64/build/src/jlapi.c:557
repl_entrypoint at /buildworker/worker/package_linux64/build/src/jlapi.c:699
main at /buildworker/worker/package_linux64/build/cli/loader_exe.c:51
__libc_start_main at /usr/lib/libc.so.6 (unknown line)
_start at /opt/julia-1.6.0-beta1/bin/julia (unknown line)
instfname = "./pUWn5BJP"
┌ Warning: Could not match the header pattern for format:
│ GuillotineModels.Data.CPG_SSSCSP{Int64, Int64, Int64}()
│ ; this is:
│ r"\*\*\*2D Rectangular Problem\*\*\*
│ \*\*\*Instances for the Single Stock Size Cutting Stock Problem \(SSSCSP\)\*\*\*
│ Input parameter file:[^\n]*
│ ^\*+$
│ .*
│ ^\*+$"ims
└ @ GuillotineModels.Data ~/AreaDeTrabalho/julia_bug_stackoverflow/GuillotineModels.jl/src/Data/cpg.jl:111
ERROR: Trying to parse GuillotineModels.Data.CPG_SSSCSP{Int64, Int64, Int64}() has resulted in the following error: Parser expects to find two lines only with asterisks; found 0 line(s) like this. As the data should be after the second of these lines, the parser did not start gathering data.
Stacktrace:
  [1] _find_header_end(format::GuillotineModels.Data.CPG_SSSCSP{Int64, Int64, Int64}, lines::Vector{SubString{String}})
    @ GuillotineModels.Data ~/AreaDeTrabalho/julia_bug_stackoverflow/GuillotineModels.jl/src/Data/cpg.jl:131

Another interesting thing is that this error at the end ERROR: Trying to parse GuillotineModels.Data.CPG_SSSCSP ... that comes from my code is incorrect. If you look at the pUWn5BJP file it has two lines of asterisks (and the code used to trigger this exception is correct, I will verify it further, but it is already tested code), so the inference error seem to not only pollute the output but also to trigger undefined behavior on the code that will be evaluated after it stack overflows.

The trace from --bug-report=rr was uploaded touploaded to https://s3.amazonaws.com/julialang-dumps/reports/2021-01-31T14-38-18-henriquebecker91.tar.zst, unfortunately I do not know how to read it.

I really need to have this code working (it is for my PhD that I am trying to finish in the next months), so I am open to make any extra tests necessary and even try to contribute to the solution (while it seems to be something kinda out of my area and abilities). I will probably try to isolate the problem more, or poke around to see if commenting a small part of the code can remove the inference StackOverflowError.

[henriquebecker91]

I have poked around a little more and found more information to share.

I was wrong about the undefined behaviour. The StackOverflowError in the inference does not affect the correctness of my code. The error from my code arose from the fact the wget ... bring a dos format file (with carriage return line endings) and I was not prepared for this. If left executing, the whole code runs perfectly, except by the gigantic error messages in the middle of the usual output and the fact it takes much more time (probably just because of the printing). I fixed the line-ending format and some small problems with GLPK (I often use Gurobi/CPLEX, I am using GLPK here just to make it easier to reproduce) and created a better commit for the issue reproduction. Now the third command in the post above can be replaced by:

$ git checkout c084795e

and I also recommend calling my code (last line in the command list of the original post) as

julia> GuillotineModels.CommandLine.run(["G2CSP", "CPG_SSSCSP", "PPG2KP", "GLPK", "./pUWn5BJP", "--PPG2KP-allow-rotation", "--generic-time-limit", "3600", "3600"]) # avoid some GLPK errors

Now more interesting discoveries:

1. Commenting line 333 of file src/PPG2KP/get_cut_pattern.jl (i.e., bmr.rad !== nothing && _cp_rai2opi!(patterns, bmr.rad :: RotationAwareData{D, S}) disappears with the problem. I had a hunch this was the cause because this is the last change I did to the code before the problem appeared.
2. If my code is run without the flag "--PPG2KP-allow-rotation" or if I add the flag "--do-not-solve", then either the enclosing function is never called or at least bmr.rad is nothing (and the part after the && does not run). Nevertheless, the bug still happens. However, if I change the line to replace the bmr.rad !== nothing with a literal false, then the bug does not happen. So, putting a false literal is enough for the type inference (or whatever is causing the problem) to completely ignore the call and don't trigger the stack overflow.
3. Unfortunately, calling _cp_rai2opi! directly does not trigger the problem. I have extracted value of the two arguments that are passed to it, and started a fresh session in which I created the values from scratch (with constructors and literals) and passed them directly to _cp_rai2opi!. No StackOverflowError happens.

I will keep poking around and see what more I discover. Any suggestions are welcome.

[henriquebecker91]

Ok, that was fast, I found one workaround that works for me. Maybe it will give some insight on the problem. I will stop pursuing this from now to focus on my PhD, but I am available to help if Julia developers want to try to find and fix this for good.

Basically, _cp_rai2opi! (the culprit) called in line 333 of src/PPG2KP/get_cut_pattern.jl was defined this way (line 268 of the same file):

function _cp_rai2opi!(
  patterns :: AbstractVector{CutPattern{D, S}},
  rad :: RotationAwareData{D, S}
) :: Nothing where {D, S}
  rai2opi = rad.sdi2opi[rad.rai2sdi]
  d = deepcopy(rad.original_demand)
  _inner_cp_rai2opi!(patterns, rai2opi, d)

  return nothing
end

as it can be seen it calls _inner_cp_rai2opi! (that is defined in line 242 of the same file)

function _inner_cp_rai2opi!(
  patterns :: AbstractVector{CutPattern{D, S}},
  rai2opi :: AbstractVector{Union{D, Tuple{D, D}}},
  remaining_original_demand :: AbstractVector{D}
) :: Nothing where {D, S}
    # the inner code does not seem relevant
end

If I change the remaining_original_demand :: AbstractVector{D} to remaining_original_demand :: Vector{D}, then the StackOverFlow error disappears. All the other parameters can be defined as AbstractVector, but if remaining_original_demand is defined as an AbstractVector the StackOverflowError happens. Other combinations like keeping remaining_original_demand as an AbstractVector and changing the other two parameters to Vectors instead have no effect (the error persists).

[henriquebecker91]

Just a complement. I have gone back to Julia 1.5.3 to work on my PhD and found it reacts a little different than version 1.6.0-beta1.

If I do what worked on 1.6.0-beta1, this is, I change remaining_original_demand from AbstractVector{D} to Vector{D}, then the code simply stalls. All my previous runs executed in less than a minute, with or without error, in this case I left the code alone for about 2~3 hours and it did not print anything (forgot to check the CPU usage but I think it was not high).

If I kept this change, and also change patterns of the _cp_rai2opi! signature (this is, the outer function) from AbstractVector to Vector, then I trigger the same StackOverflowProblem I reported in the original post when none of these changes were made.

Finally, if I make a third change, i.e., change rai2opi of the _inner_cp_rai2opi! signature from AbstractVector to Vector, then the code goes back to executing correctly (neither stalling nor throwing StackOverflowErrors).

[vtjnash]

The sets of Union and abstract types there are known cases that trigger inference (specifically type-intersection) to be slow or non-terminating. Closing as we have other reports of this with MWE already