PartialStruct tmerge fails to converge

[vtjnash]

Original text:

I just opened a PR to Measurements.jl and found that CI is hanging on Julia nightly: https://github.com/JuliaPhysics/Measurements.jl/runs/4649844099?check_suite_focus=true. I just recompiled latest master of Julia and found that simple things like

julia> using Measurements

julia> (1 ± 2) + (3 ± 4)
^C^C^C^C^C^CWARNING: Force throwing a SIGINT
Internal error: encountered unexpected error in runtime:
InterruptException()
jl_is_tuple_type at /Users/mose/repo/julia/src/./julia.h:1287 [inlined]
jl_tuple1_isa at /Users/mose/repo/julia/src/subtype.c:2006
jl_typemap_entry_assoc_exact at /Users/mose/repo/julia/src/typemap.c:976
jl_typemap_assoc_exact at /Users/mose/repo/julia/src/./julia_internal.h:1300 [inlined]
jl_lookup_generic_ at /Users/mose/repo/julia/src/gf.c:2426 [inlined]
ijl_apply_generic at /Users/mose/repo/julia/src/gf.c:2482
is_lattice_equal at ./compiler/typelattice.jl:263
is_lattice_equal at ./compiler/typelattice.jl:265
is_lattice_equal at ./compiler/typelattice.jl:265
is_lattice_equal at ./compiler/typelattice.jl:265
is_lattice_equal at ./compiler/typelattice.jl:265
is_lattice_equal at ./compiler/typelattice.jl:265
is_lattice_equal at ./compiler/typelattice.jl:265
is_lattice_equal at ./compiler/typelattice.jl:265
is_lattice_equal at ./compiler/typelattice.jl:265
is_lattice_equal at ./compiler/typelattice.jl:265
is_lattice_equal at ./compiler/typelattice.jl:265
is_lattice_equal at ./compiler/typelattice.jl:265
is_lattice_equal at ./compiler/typelattice.jl:265
is_lattice_equal at ./compiler/typelattice.jl:265
is_lattice_equal at ./compiler/typelattice.jl:265
is_lattice_equal at ./compiler/typelattice.jl:265
is_lattice_equal at ./compiler/typelattice.jl:265
is_lattice_equal at ./compiler/typelattice.jl:265
is_lattice_equal at ./compiler/typelattice.jl:265
is_lattice_equal at ./compiler/typelattice.jl:265
is_lattice_equal at ./compiler/typelattice.jl:265
is_lattice_equal at ./compiler/typelattice.jl:265
is_lattice_equal at ./compiler/typelattice.jl:265
is_lattice_equal at ./compiler/typelattice.jl:265
is_argtype_match at ./compiler/inferenceresult.jl:7 [inlined]
cache_lookup at ./compiler/inferenceresult.jl:213
abstract_call_method_with_const_args at ./compiler/abstractinterpretation.jl:598
abstract_call_gf_by_type at ./compiler/abstractinterpretation.jl:126
abstract_call_known at ./compiler/abstractinterpretation.jl:1487
abstract_call at ./compiler/abstractinterpretation.jl:1543
abstract_call at ./compiler/abstractinterpretation.jl:1525
abstract_eval_statement at ./compiler/abstractinterpretation.jl:1664
typeinf_local at ./compiler/abstractinterpretation.jl:2053
typeinf_nocycle at ./compiler/abstractinterpretation.jl:2149
_typeinf at ./compiler/typeinfer.jl:226
typeinf at ./compiler/typeinfer.jl:209
abstract_call_method_with_const_args at ./compiler/abstractinterpretation.jl:622
abstract_call_gf_by_type at ./compiler/abstractinterpretation.jl:126
abstract_call_known at ./compiler/abstractinterpretation.jl:1487
abstract_call at ./compiler/abstractinterpretation.jl:1543
abstract_call at ./compiler/abstractinterpretation.jl:1525
abstract_eval_statement at ./compiler/abstractinterpretation.jl:1664
typeinf_local at ./compiler/abstractinterpretation.jl:2053
typeinf_nocycle at ./compiler/abstractinterpretation.jl:2149
_typeinf at ./compiler/typeinfer.jl:226
typeinf at ./compiler/typeinfer.jl:209
abstract_call_method_with_const_args at ./compiler/abstractinterpretation.jl:622
abstract_call_gf_by_type at ./compiler/abstractinterpretation.jl:126
abstract_call_known at ./compiler/abstractinterpretation.jl:1487
abstract_call at ./compiler/abstractinterpretation.jl:1543
abstract_call at ./compiler/abstractinterpretation.jl:1525
abstract_eval_statement at ./compiler/abstractinterpretation.jl:1664
typeinf_local at ./compiler/abstractinterpretation.jl:2053
typeinf_nocycle at ./compiler/abstractinterpretation.jl:2149
_typeinf at ./compiler/typeinfer.jl:226
typeinf at ./compiler/typeinfer.jl:209
abstract_call_method_with_const_args at ./compiler/abstractinterpretation.jl:622
abstract_call_gf_by_type at ./compiler/abstractinterpretation.jl:126
abstract_call_known at ./compiler/abstractinterpretation.jl:1487
abstract_call at ./compiler/abstractinterpretation.jl:1543
abstract_call at ./compiler/abstractinterpretation.jl:1525
abstract_eval_statement at ./compiler/abstractinterpretation.jl:1664
typeinf_local at ./compiler/abstractinterpretation.jl:2053
typeinf_nocycle at ./compiler/abstractinterpretation.jl:2149
_typeinf at ./compiler/typeinfer.jl:226
typeinf at ./compiler/typeinfer.jl:209
typeinf_edge at ./compiler/typeinfer.jl:826 [inlined]
abstract_call_method at ./compiler/abstractinterpretation.jl:570
abstract_call_gf_by_type at ./compiler/abstractinterpretation.jl:117
abstract_call_known at ./compiler/abstractinterpretation.jl:1487
abstract_call at ./compiler/abstractinterpretation.jl:1543
abstract_call at ./compiler/abstractinterpretation.jl:1525
abstract_eval_statement at ./compiler/abstractinterpretation.jl:1664
typeinf_local at ./compiler/abstractinterpretation.jl:2053
typeinf_nocycle at ./compiler/abstractinterpretation.jl:2149
_typeinf at ./compiler/typeinfer.jl:226
typeinf at ./compiler/typeinfer.jl:209
typeinf_ext at ./compiler/typeinfer.jl:907
typeinf_ext_toplevel at ./compiler/typeinfer.jl:940
typeinf_ext_toplevel at ./compiler/typeinfer.jl:936
jfptr_typeinf_ext_toplevel_10110 at /Users/mose/repo/julia/usr/lib/julia/sys.dylib (unknown line)
_jl_invoke at /Users/mose/repo/julia/src/gf.c:0 [inlined]
ijl_apply_generic at /Users/mose/repo/julia/src/gf.c:2486
jl_apply at /Users/mose/repo/julia/src/./julia.h:1789 [inlined]
jl_type_infer at /Users/mose/repo/julia/src/gf.c:295
jl_generate_fptr_impl at /Users/mose/repo/julia/src/jitlayers.cpp:301
jl_compile_method_internal at /Users/mose/repo/julia/src/gf.c:2020
_jl_invoke at /Users/mose/repo/julia/src/gf.c:2296 [inlined]
ijl_apply_generic at /Users/mose/repo/julia/src/gf.c:2486
jl_apply at /Users/mose/repo/julia/src/./julia.h:1789 [inlined]
do_call at /Users/mose/repo/julia/src/interpreter.c:126
eval_body at /Users/mose/repo/julia/src/interpreter.c:0
jl_interpret_toplevel_thunk at /Users/mose/repo/julia/src/interpreter.c:744
jl_toplevel_eval_flex at /Users/mose/repo/julia/src/toplevel.c:888
jl_toplevel_eval_flex at /Users/mose/repo/julia/src/toplevel.c:832
ijl_toplevel_eval at /Users/mose/repo/julia/src/toplevel.c:897 [inlined]
ijl_toplevel_eval_in at /Users/mose/repo/julia/src/toplevel.c:947
eval at ./boot.jl:368 [inlined]
eval_user_input at /Users/mose/repo/julia/usr/share/julia/stdlib/v1.8/REPL/src/REPL.jl:151
repl_backend_loop at /Users/mose/repo/julia/usr/share/julia/stdlib/v1.8/REPL/src/REPL.jl:245
start_repl_backend at /Users/mose/repo/julia/usr/share/julia/stdlib/v1.8/REPL/src/REPL.jl:230
#run_repl#47 at /Users/mose/repo/julia/usr/share/julia/stdlib/v1.8/REPL/src/REPL.jl:367
run_repl at /Users/mose/repo/julia/usr/share/julia/stdlib/v1.8/REPL/src/REPL.jl:354
jfptr_run_repl_55691 at /Users/mose/repo/julia/usr/lib/julia/sys.dylib (unknown line)
_jl_invoke at /Users/mose/repo/julia/src/gf.c:0 [inlined]
ijl_apply_generic at /Users/mose/repo/julia/src/gf.c:2486
#934 at ./client.jl:403
jfptr_YY.934_34804 at /Users/mose/repo/julia/usr/lib/julia/sys.dylib (unknown line)
_jl_invoke at /Users/mose/repo/julia/src/gf.c:0 [inlined]
ijl_apply_generic at /Users/mose/repo/julia/src/gf.c:2486
jl_apply at /Users/mose/repo/julia/src/./julia.h:1789 [inlined]
jl_f__call_latest at /Users/mose/repo/julia/src/builtins.c:757
#invokelatest#2 at ./essentials.jl:731 [inlined]
invokelatest at ./essentials.jl:729 [inlined]
run_main_repl at ./client.jl:388
exec_options at ./client.jl:318
_start at ./client.jl:506
jfptr__start_46562 at /Users/mose/repo/julia/usr/lib/julia/sys.dylib (unknown line)
_jl_invoke at /Users/mose/repo/julia/src/gf.c:0 [inlined]
ijl_apply_generic at /Users/mose/repo/julia/src/gf.c:2486
jl_apply at /Users/mose/repo/julia/src/./julia.h:1789 [inlined]
true_main at /Users/mose/repo/julia/src/jlapi.c:562
jl_repl_entrypoint at /Users/mose/repo/julia/src/jlapi.c:706
4.0 ± 4.5

hang

Originally posted by @giordano in #43561 (comment)

Initial analysis and MWE:

The problem here is that this tmerge may fail to converge for recursive structs (e.g. if mayinlinealloc is false):

julia> init = Base.ImmutableDict{Any,Any}()

julia> a = Core.Const(init)
Core.Const(Base.ImmutableDict{Any, Any}())

julia> b = Core.PartialStruct(typeof(init), Any[
         Core.Const(init),
         Any,
         Any])
Core.PartialStruct(Base.ImmutableDict{Any, Any}, Any[Core.Const(Base.ImmutableDict{Any, Any}()), Any, Any])

julia> c = Core.Compiler.tmerge(a, b) # == b
Core.PartialStruct(Base.ImmutableDict{Any, Any}, Any[Core.Const(Base.ImmutableDict{Any, Any}()), Any, Any])

julia> Core.Compiler.is_lattice_equal(b, c)
true

julia> ⊑(a, c)
false

Then in a while loop, we keep wrapping it such that we never converge this lattice:

julia> let init = Base.ImmutableDict{Any,Any}()
       global function f()
         g = init
         while true
             g = Base.ImmutableDict(g, 1=>2)
         end
       end
       end

julia> @code_typed optimize=false f() # this goes on forever

[Keno]

Sigh ... this issue just caused me half my Sunday in a slightly different presentation ... let's get it fixed!

[Keno]

I see #43812 is merged now, which is probably good since it fixed the immediate issue, but from discussion with @vtjnash this morning, we're not convinced, it's the correct solution, so re-opening this to track hopefully coming up with something better (cc @martinholters @aviatesk).

Notes from our discussion this morning:

Point 1: A complicating issue here is that currently we have !⊑(a, b), i.e. we don't consider Union{} in a PartialStruct field to be a refinement of Const (or anything) else. @vtjnash is convinced this is wrong. I think it is a valid choice, but I agree that it is less consistent with the way we do things elsewhere. The relevant change here would be changing https://github.com/JuliaLang/julia/blob/master/base/compiler/typelattice.jl#L203 to continue.

Point 2: Because of (1), prior to #43812, tmerge as violating its spec. It should always produce a valid upper bound over the inference lattice, but currently it did not.

Point 3: #43784 fixed this specific case, but it is not generally sufficient as the same issue can happen with PartialStructs that don't have Union{} fieldtypes. For regular types we limit the complexity growth. We need to do something similar here.

Point 4: Because of Point 1 and Point 3, if we were to fix the thing identified in Point 1, the fix from #43812 would become ineffective, since tmerge would always return the larger of the two types.

[vtjnash]

For point 3, I propose we could use here a simplified tmerge concept, where they are either equal, or we aggressively widen them (to the narrower of their shared wrapper type, or the declared fieldtype):

function tmerge_fast(fielda, fieldb, reftype)
    is_lattice_equal(fielda, fieldb) && return fielda
    tn = _typename(widentype(fielda))
    if tn isa Const && tn === _typename(widentype(fieldb))
        return typeintersect(reftype, (tn.val::TypeName).wrapper)
    end
    return reftype
end

......
    fieldx = tmerge_fast(fielda, fieldb, fieldtype(ty, n))
......

This is not monotonic (since we completely ignore the possibility of them being subtypes), but neither is tmerge, and nor do we expect–or require–it to be. (This is simply among the reasons why the return_type function is known not to be :invariant in the general case.)