Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Jump to bottom

infinite loop in C code when trying to add a method #54516

Closed
nsajko opened this issue May 18, 2024 · 7 comments · Fixed by #54545
Closed

infinite loop in C code when trying to add a method #54516

nsajko opened this issue May 18, 2024 · 7 comments · Fixed by #54545
Labels
bug Indicates an unexpected problem or unintended behavior regression Regression in behavior compared to a previous version types and dispatch Types, subtyping and method dispatch
Milestone
1.11

Comments

@nsajko
Copy link
Contributor

nsajko commented May 18, 2024

MWE:

struct Frac{T} end
Base.:+(a::Frac{<:T},b::Union{Number,T}) where {T} = nothing
Base.:+(b::Union{Number,T},a::Frac{<:T}) where {T} = nothing

FTR this makes it impossible to compile LaurentPolynomials.jl.

Version info:

Julia Version 1.12.0-DEV.555
Commit 6c17db1ba12 (2024-05-17 23:51 UTC)
Build Info:
  Official https://julialang.org/ release
Platform Info:
  OS: Linux (x86_64-linux-gnu)
  CPU: 8 × AMD Ryzen 3 5300U with Radeon Graphics
  WORD_SIZE: 64
  LLVM: libLLVM-17.0.6 (ORCJIT, znver2)
Threads: 1 default, 0 interactive, 1 GC (on 8 virtual cores)
@nsajko nsajko added bug Indicates an unexpected problem or unintended behavior regression Regression in behavior compared to a previous version types and dispatch Types, subtyping and method dispatch labels May 18, 2024
@nsajko
Copy link
Contributor Author

nsajko commented May 18, 2024

When trying to precompile LaurentPolynomials.jl:

julia> using LaurentPolynomials
Precompiling LaurentPolynomials...
^C Interrupted: Exiting precompilation...
Info [ Info: Waiting for another process (pid: 497792) to finish precompiling LaurentPolynomials [10b2801c-d482-41ed-a506-4a825c59e3da]. Pidfile: /home/nsajko/.julia/compiled/v1.12/LaurentPolynomials/9eoeD_u6Ef1.ji.pidfile
Given LaurentPolynomials was explicitly requested, output will be shown live 

[497799] signal 2: Interrupt
[ Info: Precompiling LaurentPolynomials [10b2801c-d482-41ed-a506-4a825c59e3da] 
in expression starting at /home/nsajko/.julia/packages/LaurentPolynomials/Vje2Z/src/LaurentPolynomials.jl:901
jl_has_bound_typevars at /cache/build/builder-amdci5-3/julialang/julia-master/src/jltypes.c:221
finish_unionall at /cache/build/builder-amdci5-3/julialang/julia-master/src/subtype.c:3015
intersect_unionall_ at /cache/build/builder-amdci5-3/julialang/julia-master/src/subtype.c:3194
intersect_unionall at /cache/build/builder-amdci5-3/julialang/julia-master/src/subtype.c:3265
intersect at /cache/build/builder-amdci5-3/julialang/julia-master/src/subtype.c:3865
intersect_all at /cache/build/builder-amdci5-3/julialang/julia-master/src/subtype.c:4126
jl_type_intersection_env_s at /cache/build/builder-amdci5-3/julialang/julia-master/src/subtype.c:4348
jl_typemap_intersection_node_visitor at /cache/build/builder-amdci5-3/julialang/julia-master/src/typemap.c:543
jl_typemap_intersection_visitor at /cache/build/builder-amdci5-3/julialang/julia-master/src/typemap.c:812
jl_typemap_intersection_memory_visitor at /cache/build/builder-amdci5-3/julialang/julia-master/src/typemap.c:500
jl_typemap_intersection_visitor at /cache/build/builder-amdci5-3/julialang/julia-master/src/typemap.c:802
get_intersect_matches at /cache/build/builder-amdci5-3/julialang/julia-master/src/gf.c:1567 [inlined]
jl_method_table_activate at /cache/build/builder-amdci5-3/julialang/julia-master/src/gf.c:2039
ijl_method_table_insert at /cache/build/builder-amdci5-3/julialang/julia-master/src/gf.c:2233
ijl_method_def at /cache/build/builder-amdci5-3/julialang/julia-master/src/method.c:1305
eval_methoddef at /cache/build/builder-amdci5-3/julialang/julia-master/src/interpreter.c:112
eval_body at /cache/build/builder-amdci5-3/julialang/julia-master/src/interpreter.c:619
jl_interpret_toplevel_thunk at /cache/build/builder-amdci5-3/julialang/julia-master/src/interpreter.c:865
jl_toplevel_eval_flex at /cache/build/builder-amdci5-3/julialang/julia-master/src/toplevel.c:969
jl_eval_module_expr at /cache/build/builder-amdci5-3/julialang/julia-master/src/toplevel.c:215 [inlined]
jl_toplevel_eval_flex at /cache/build/builder-amdci5-3/julialang/julia-master/src/toplevel.c:762
jl_toplevel_eval_flex at /cache/build/builder-amdci5-3/julialang/julia-master/src/toplevel.c:909
jl_toplevel_eval_flex at /cache/build/builder-amdci5-3/julialang/julia-master/src/toplevel.c:909
ijl_toplevel_eval at /cache/build/builder-amdci5-3/julialang/julia-master/src/toplevel.c:980
ijl_toplevel_eval_in at /cache/build/builder-amdci5-3/julialang/julia-master/src/toplevel.c:1022
eval at ./boot.jl:432 [inlined]
include_string at ./loading.jl:2591
_include at ./loading.jl:2651
include at ./Base.jl:559 [inlined]
include_package_for_output at ./loading.jl:2769
jfptr_include_package_for_output_68716.1 at /home/nsajko/tmp/jl/jl/julia-6c17db1ba1/lib/julia/sys.so (unknown line)
jl_apply at /cache/build/builder-amdci5-3/julialang/julia-master/src/julia.h:2189 [inlined]
do_call at /cache/build/builder-amdci5-3/julialang/julia-master/src/interpreter.c:127
eval_value at /cache/build/builder-amdci5-3/julialang/julia-master/src/interpreter.c:224
eval_stmt_value at /cache/build/builder-amdci5-3/julialang/julia-master/src/interpreter.c:175 [inlined]
eval_body at /cache/build/builder-amdci5-3/julialang/julia-master/src/interpreter.c:660
jl_interpret_toplevel_thunk at /cache/build/builder-amdci5-3/julialang/julia-master/src/interpreter.c:865
jl_toplevel_eval_flex at /cache/build/builder-amdci5-3/julialang/julia-master/src/toplevel.c:969
jl_toplevel_eval_flex at /cache/build/builder-amdci5-3/julialang/julia-master/src/toplevel.c:909
ijl_toplevel_eval at /cache/build/builder-amdci5-3/julialang/julia-master/src/toplevel.c:980
ijl_toplevel_eval_in at /cache/build/builder-amdci5-3/julialang/julia-master/src/toplevel.c:1022
eval at ./boot.jl:432 [inlined]
include_string at ./loading.jl:2591
include_string at ./loading.jl:2601 [inlined]
exec_options at ./client.jl:323
_start at ./client.jl:533
jfptr__start_70211.1 at /home/nsajko/tmp/jl/jl/julia-6c17db1ba1/lib/julia/sys.so (unknown line)
jl_apply at /cache/build/builder-amdci5-3/julialang/julia-master/src/julia.h:2189 [inlined]
true_main at /cache/build/builder-amdci5-3/julialang/julia-master/src/jlapi.c:900
jl_repl_entrypoint at /cache/build/builder-amdci5-3/julialang/julia-master/src/jlapi.c:1059
main at /cache/build/builder-amdci5-3/julialang/julia-master/cli/loader_exe.c:58
unknown function (ip: 0x7573c61cac87)
__libc_start_main at /usr/lib/libc.so.6 (unknown line)
unknown function (ip: 0x4010b8)
unknown function (ip: (nil))
Allocations: 1 (Pool: 1; Big: 0); GC: 0

@nsajko
Copy link
Contributor Author

nsajko commented May 18, 2024

Continuing from above, after second interrupt:

^C
[497804] signal 2: Interrupt
in expression starting at /home/nsajko/.julia/packages/LaurentPolynomials/Vje2Z/src/LaurentPolynomials.jl:901
jl_has_bound_typevars at /cache/build/builder-amdci5-3/julialang/julia-master/src/jltypes.c:271
ijl_has_typevar at /cache/build/builder-amdci5-3/julialang/julia-master/src/jltypes.c:276
finish_unionall at /cache/build/builder-amdci5-3/julialang/julia-master/src/subtype.c:3015
intersect_unionall_ at /cache/build/builder-amdci5-3/julialang/julia-master/src/subtype.c:3194
intersect_unionall at /cache/build/builder-amdci5-3/julialang/julia-master/src/subtype.c:3265
intersect at /cache/build/builder-amdci5-3/julialang/julia-master/src/subtype.c:3865
intersect_all at /cache/build/builder-amdci5-3/julialang/julia-master/src/subtype.c:4126
jl_type_intersection_env_s at /cache/build/builder-amdci5-3/julialang/julia-master/src/subtype.c:4348
jl_typemap_intersection_node_visitor at /cache/build/builder-amdci5-3/julialang/julia-master/src/typemap.c:543
jl_typemap_intersection_visitor at /cache/build/builder-amdci5-3/julialang/julia-master/src/typemap.c:812
jl_typemap_intersection_memory_visitor at /cache/build/builder-amdci5-3/julialang/julia-master/src/typemap.c:500
jl_typemap_intersection_visitor at /cache/build/builder-amdci5-3/julialang/julia-master/src/typemap.c:802
get_intersect_matches at /cache/build/builder-amdci5-3/julialang/julia-master/src/gf.c:1567 [inlined]
jl_method_table_activate at /cache/build/builder-amdci5-3/julialang/julia-master/src/gf.c:2039
ijl_method_table_insert at /cache/build/builder-amdci5-3/julialang/julia-master/src/gf.c:2233
ijl_method_def at /cache/build/builder-amdci5-3/julialang/julia-master/src/method.c:1305
eval_methoddef at /cache/build/builder-amdci5-3/julialang/julia-master/src/interpreter.c:112
eval_body at /cache/build/builder-amdci5-3/julialang/julia-master/src/interpreter.c:619
jl_interpret_toplevel_thunk at /cache/build/builder-amdci5-3/julialang/julia-master/src/interpreter.c:865
jl_toplevel_eval_flex at /cache/build/builder-amdci5-3/julialang/julia-master/src/toplevel.c:969
jl_eval_module_expr at /cache/build/builder-amdci5-3/julialang/julia-master/src/toplevel.c:215 [inlined]
jl_toplevel_eval_flex at /cache/build/builder-amdci5-3/julialang/julia-master/src/toplevel.c:762
jl_toplevel_eval_flex at /cache/build/builder-amdci5-3/julialang/julia-master/src/toplevel.c:909
jl_toplevel_eval_flex at /cache/build/builder-amdci5-3/julialang/julia-master/src/toplevel.c:909
ijl_toplevel_eval at /cache/build/builder-amdci5-3/julialang/julia-master/src/toplevel.c:980
ijl_toplevel_eval_in at /cache/build/builder-amdci5-3/julialang/julia-master/src/toplevel.c:1022
eval at ./boot.jl:432 [inlined]
include_string at ./loading.jl:2591
_include at ./loading.jl:2651
include at ./Base.jl:559 [inlined]
include_package_for_output at ./loading.jl:2769
jfptr_include_package_for_output_68716.1 at /home/nsajko/tmp/jl/jl/julia-6c17db1ba1/lib/julia/sys.so (unknown line)
jl_apply at /cache/build/builder-amdci5-3/julialang/julia-master/src/julia.h:2189 [inlined]
do_call at /cache/build/builder-amdci5-3/julialang/julia-master/src/interpreter.c:127
eval_value at /cache/build/builder-amdci5-3/julialang/julia-master/src/interpreter.c:224
eval_stmt_value at /cache/build/builder-amdci5-3/julialang/julia-master/src/interpreter.c:175 [inlined]
eval_body at /cache/build/builder-amdci5-3/julialang/julia-master/src/interpreter.c:660
jl_interpret_toplevel_thunk at /cache/build/builder-amdci5-3/julialang/julia-master/src/interpreter.c:865
jl_toplevel_eval_flex at /cache/build/builder-amdci5-3/julialang/julia-master/src/toplevel.c:969
jl_toplevel_eval_flex at /cache/build/builder-amdci5-3/julialang/julia-master/src/toplevel.c:909
ijl_toplevel_eval at /cache/build/builder-amdci5-3/julialang/julia-master/src/toplevel.c:980
ijl_toplevel_eval_in at /cache/build/builder-amdci5-3/julialang/julia-master/src/toplevel.c:1022
eval at ./boot.jl:432 [inlined]
include_string at ./loading.jl:2591
include_string at ./loading.jl:2601 [inlined]
exec_options at ./client.jl:323
_start at ./client.jl:533
jfptr__start_70211.1 at /home/nsajko/tmp/jl/jl/julia-6c17db1ba1/lib/julia/sys.so (unknown line)
jl_apply at /cache/build/builder-amdci5-3/julialang/julia-master/src/julia.h:2189 [inlined]
true_main at /cache/build/builder-amdci5-3/julialang/julia-master/src/jlapi.c:900
jl_repl_entrypoint at /cache/build/builder-amdci5-3/julialang/julia-master/src/jlapi.c:1059
main at /cache/build/builder-amdci5-3/julialang/julia-master/cli/loader_exe.c:58
unknown function (ip: 0x76ce340d6c87)
__libc_start_main at /usr/lib/libc.so.6 (unknown line)
unknown function (ip: 0x4010b8)
unknown function (ip: (nil))
Allocations: 1 (Pool: 1; Big: 0); GC: 0
ERROR: InterruptException:
Stacktrace:
  [1] try_yieldto(undo::typeof(Base.ensure_rescheduled))
    @ Base ./task.jl:1100
  [2] wait()
    @ Base ./task.jl:1164
  [3] wait(c::Base.GenericCondition{Base.Threads.SpinLock}; first::Bool)
    @ Base ./condition.jl:139
  [4] wait
    @ ./condition.jl:134 [inlined]
  [5] wait(x::Base.Process, syncd::Bool)
    @ Base ./process.jl:694
  [6] wait
    @ ./process.jl:687 [inlined]
  [7] success(x::Base.Process)
    @ Base ./process.jl:556
  [8] compilecache(pkg::Base.PkgId, path::String, internal_stderr::IO, internal_stdout::IO, keep_loaded_modules::Bool; flags::Cmd, cacheflags::Base.CacheFlags, reasons::Dict{String, Int64})
    @ Base ./loading.jl:2958
  [9] (::Base.var"#1102#1103"{Base.PkgId})()
    @ Base ./loading.jl:2437
 [10] mkpidlock(f::Base.var"#1102#1103"{Base.PkgId}, at::String, pid::Int32; kwopts::@Kwargs{stale_age::Int64, wait::Bool})
    @ FileWatching.Pidfile ~/tmp/jl/jl/julia-6c17db1ba1/share/julia/stdlib/v1.12/FileWatching/src/pidfile.jl:93
 [11] #mkpidlock#6
    @ ~/tmp/jl/jl/julia-6c17db1ba1/share/julia/stdlib/v1.12/FileWatching/src/pidfile.jl:88 [inlined]
 [12] trymkpidlock(::Function, ::Vararg{Any}; kwargs::@Kwargs{stale_age::Int64})
    @ FileWatching.Pidfile ~/tmp/jl/jl/julia-6c17db1ba1/share/julia/stdlib/v1.12/FileWatching/src/pidfile.jl:114
 [13] #invokelatest#2
    @ ./essentials.jl:1035 [inlined]
 [14] invokelatest
    @ ./essentials.jl:1030 [inlined]
 [15] maybe_cachefile_lock(f::Base.var"#1102#1103"{Base.PkgId}, pkg::Base.PkgId, srcpath::String; stale_age::Int64)
    @ Base ./loading.jl:3604
 [16] maybe_cachefile_lock
    @ ./loading.jl:3601 [inlined]
 [17] _require(pkg::Base.PkgId, env::String)
    @ Base ./loading.jl:2433
 [18] __require_prelocked(uuidkey::Base.PkgId, env::String)
    @ Base ./loading.jl:2266
 [19] #invoke_in_world#3
    @ ./essentials.jl:1067 [inlined]
 [20] invoke_in_world
    @ ./essentials.jl:1064 [inlined]
 [21] _require_prelocked(uuidkey::Base.PkgId, env::String)
    @ Base ./loading.jl:2257
 [22] macro expansion
    @ ./loading.jl:2197 [inlined]
 [23] macro expansion
    @ ./lock.jl:273 [inlined]
 [24] __require(into::Module, mod::Symbol)
    @ Base ./loading.jl:2154
 [25] #invoke_in_world#3
    @ ./essentials.jl:1067 [inlined]
 [26] invoke_in_world
    @ ./essentials.jl:1064 [inlined]
 [27] require(into::Module, mod::Symbol)
    @ Base ./loading.jl:2147

@nsajko
Copy link
Contributor Author

nsajko commented May 18, 2024 •
edited
Loading

Bisected to #53675, @N5N3. Indeed, this was caught back then by Nanosoldier's PkgEval of the PR, but wasn't noticed.

@nsajko nsajko mentioned this issue May 19, 2024
Closed
@N5N3
Copy link
Member

N5N3 commented May 19, 2024 •
edited
Loading

Em that loop might be infinite if innervals have circular bounds.
I haven't checked it locally, but this specific intersection has been broken since v1.10

julia> S = Tuple{Val{S1} where {S1<:T1}, Union{Int,T1}} where {T1}
Tuple{Val{S1} where S1<:T1, Union{Int64, T1}} where T1

julia> T = Tuple{Union{Int,T2}, Val{S2} where {S2<:T2}} where {T2}
Tuple{Union{Int64, T2}, Val{S2} where S2<:T2} where T2

julia> typeintersect(S, T) |> Base.has_free_typevars
true

julia> versioninfo()
Julia Version 1.10.3
Commit 0b4590a550 (2024-04-30 10:59 UTC)
Build Info:
  Official https://julialang.org/ release
Platform Info:
  OS: Windows (x86_64-w64-mingw32)
  CPU: 16 × 12th Gen Intel(R) Core(TM) i7-12650H
  WORD_SIZE: 64
  LIBM: libopenlibm
  LLVM: libLLVM-15.0.7 (ORCJIT, alderlake)
Threads: 1 default, 0 interactive, 1 GC (on 16 virtual cores)

@N5N3 N5N3 added this to the 1.11 milestone May 22, 2024
@N5N3
Copy link
Member

N5N3 commented May 22, 2024

Add the milestone as #53675 has been backported.

This was referenced May 22, 2024
Merged
Merged
vtjnash pushed a commit that referenced this issue May 28, 2024
@N5N3
typeintersect: fix incorrect innervar handling under circular env (#5…
92dfdca 
…4545)

The infinite loop encountered in #54516 has been traced back to a
circular bound during `finish_unionall`.
As we insert innervar more eagerly now, the direct `jl_has_typevar`
could not find all circularity.
To address this, `has_typevar_via_flatten_env` is added to perform
thorough check.
Although there is some code duplication with `reachable_var`, it could
be improved in future refactoring.

#54516 also highlighted another free var escaping regression since
v1.10. This regression is not solely
the result of incomplete checks, it is also caused by the missing final
substitution of `vb`'s bound, which has now been corrected.

At last, this PR adds an assertion of sorting complexity, which should
facilitate the detection of similar issues by PkgEval.
 
close #54516
KristofferC pushed a commit that referenced this issue May 29, 2024
@N5N3
typeintersect: fix incorrect innervar handling under circular env (#5…
84bde3f 
…4545)

The infinite loop encountered in #54516 has been traced back to a
circular bound during `finish_unionall`.
As we insert innervar more eagerly now, the direct `jl_has_typevar`
could not find all circularity.
To address this, `has_typevar_via_flatten_env` is added to perform
thorough check.
Although there is some code duplication with `reachable_var`, it could
be improved in future refactoring.

#54516 also highlighted another free var escaping regression since
v1.10. This regression is not solely
the result of incomplete checks, it is also caused by the missing final
substitution of `vb`'s bound, which has now been corrected.

At last, this PR adds an assertion of sorting complexity, which should
facilitate the detection of similar issues by PkgEval.

close #54516

(cherry picked from commit 92dfdca)
@jmichel7
Copy link

This problem seems to have been backported on 1.11 beta2. LaurentPolynomials did compile on beta1, and now has an infinite loop on beta2

@KristofferC
Copy link
Member

Yes, backporting #54545 will fix that.

DilumAluthge pushed a commit that referenced this issue Jun 3, 2024
@N5N3 @DilumAluthge
typeintersect: fix incorrect innervar handling under circular env (#5…
f3f525a 
…4545)

The infinite loop encountered in #54516 has been traced back to a
circular bound during `finish_unionall`.
As we insert innervar more eagerly now, the direct `jl_has_typevar`
could not find all circularity.
To address this, `has_typevar_via_flatten_env` is added to perform
thorough check.
Although there is some code duplication with `reachable_var`, it could
be improved in future refactoring.

#54516 also highlighted another free var escaping regression since
v1.10. This regression is not solely
the result of incomplete checks, it is also caused by the missing final
substitution of `vb`'s bound, which has now been corrected.

At last, this PR adds an assertion of sorting complexity, which should
facilitate the detection of similar issues by PkgEval.
 
close #54516
lazarusA pushed a commit to lazarusA/julia that referenced this issue Jul 12, 2024
@N5N3 @lazarusA
typeintersect: fix incorrect innervar handling under circular env (Ju…
ae6612c 
…liaLang#54545)

The infinite loop encountered in JuliaLang#54516 has been traced back to a
circular bound during `finish_unionall`.
As we insert innervar more eagerly now, the direct `jl_has_typevar`
could not find all circularity.
To address this, `has_typevar_via_flatten_env` is added to perform
thorough check.
Although there is some code duplication with `reachable_var`, it could
be improved in future refactoring.

JuliaLang#54516 also highlighted another free var escaping regression since
v1.10. This regression is not solely
the result of incomplete checks, it is also caused by the missing final
substitution of `vb`'s bound, which has now been corrected.

At last, this PR adds an assertion of sorting complexity, which should
facilitate the detection of similar issues by PkgEval.
 
close JuliaLang#54516
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Assignees
No one assigned
Labels
bug Indicates an unexpected problem or unintended behavior regression Regression in behavior compared to a previous version types and dispatch Types, subtyping and method dispatch
Projects
None yet
Milestone
1.11
Development

Successfully merging a pull request may close this issue.

typeintersect: fix incorrect innervar handling under circular env N5N3/julia
4 participants
@KristofferC @nsajko @N5N3 @jmichel7