type-intersection env may fail merging of multiple value matches

[waltergu]

When I was developing my own package, I came across a weird bug of Julia on the control flow using the if-else statement. The minimal reproducible example is as follows:

struct Modulate{M<:Union{Function, Val{true}, Val{false}}, id}
    modulate::M
    Modulate(id::Symbol, modulate::Function) = new{typeof(modulate), id}(modulate)
    Modulate(id::Symbol, modulate::Bool=true) = new{Val{modulate}, id}(modulate|>Val)
end
@inline ismodulatable(modulate::Modulate) = ismodulatable(typeof(modulate))
@inline ismodulatable(::Type{<:Modulate{Val{B}}}) where B = B
@inline ismodulatable(::Type{<:Modulate{<:Function}}) = true

mutable struct Term{I, M<:Modulate}
    modulate::M
    Term{I}(modulate::Modulate) where I = new{I, typeof(modulate)}(modulate)
end
@inline ismodulatable(term::Term) = ismodulatable(typeof(term))
@inline ismodulatable(::Type{<:Term{I, M} where I}) where M = ismodulatable(M)

function newexpand(gen, name::Symbol)
    flag = ismodulatable(getfield(gen, name))
    println(flag)
    if flag
        println("flow for true.")
    else
        println("flow for false.")
    end
end

t = Term{:t}(Modulate(:t, false))
μ = Term{:μ}(Modulate(:μ, false))
U = Term{:U}(Modulate(:U, false))

newexpand((t=t, μ=μ, U=U), :U)

In my computer, the output of the above script is

false
flow for true.

Apparently, something is wrong. However, if the last line of the above script is replaced with the following

newexpand((t=t, U=U), :U)

The result is correct as expected:

false
flow for false.

In fact, even for

newexpand((t=t, μ=t, U=U), :U)

The code also works fine:

false
flow for false.

My Julia version is

Julia Version 1.6.0
Commit f9720dc2eb (2021-03-24 12:55 UTC)
Platform Info:
  OS: Windows (x86_64-w64-mingw32)
  CPU: AMD Ryzen 7 4800HS with Radeon Graphics
  WORD_SIZE: 64
  LIBM: libopenlibm
  LLVM: libLLVM-11.0.1 (ORCJIT, znver2)

[rfourquet]

It seems fixed on the master branch.

[GiggleLiu]

Yes, I just checked this problem exists in julia-1.6, but is fixed in master.

(base) ➜  julia git:(master) ✗ ./julia
               _
   _       _ _(_)_     |  Documentation: https://docs.julialang.org
  (_)     | (_) (_)    |
   _ _   _| |_  __ _   |  Type "?" for help, "]?" for Pkg help.
  | | | | | | |/ _` |  |
  | | |_| | | | (_| |  |  Version 1.7.0-DEV.919 (2021-04-13)
 _/ |\__'_|_|_|\__'_|  |  tuple32/9300073eb4* (fork: 1 commits, 53 days)
|__/                   |

julia> ┌ Warning: Could not load Revise.
└ @ Main ~/.julia/config/startup.jl:7
julia> 

julia> struct Modulate{M<:Union{Function, Val{true}, Val{false}}, id}
           modulate::M
           Modulate(id::Symbol, modulate::Function) = new{typeof(modulate), id}(modulate)
           Modulate(id::Symbol, modulate::Bool=true) = new{Val{modulate}, id}(modulate|>Val)
       end

julia> @inline ismodulatable(modulate::Modulate) = ismodulatable(typeof(modulate))
ismodulatable (generic function with 1 method)

julia> @inline ismodulatable(::Type{<:Modulate{Val{B}}}) where B = B
ismodulatable (generic function with 2 methods)

julia> @inline ismodulatable(::Type{<:Modulate{<:Function}}) = true
ismodulatable (generic function with 3 methods)

julia> mutable struct Term{I, M<:Modulate}
           modulate::M
           Term{I}(modulate::Modulate) where I = new{I, typeof(modulate)}(modulate)
       end

julia> @inline ismodulatable(term::Term) = ismodulatable(typeof(term))
ismodulatable (generic function with 4 methods)

julia> @inline ismodulatable(::Type{<:Term{I, M} where I}) where M = ismodulatable(M)
ismodulatable (generic function with 5 methods)

julia> function newexpand(gen, name::Symbol)
           flag = ismodulatable(getfield(gen, name))
           println(flag)
           if flag
               println("flow for true.")
           else
               println("flow for false.")
           end
       end
newexpand (generic function with 1 method)

julia> t = Term{:t}(Modulate(:t, false))
Term{:t, Modulate{Val{false}, :t}}(Modulate{Val{false}, :t}(Val{false}()))

julia> μ = Term{:μ}(Modulate(:μ, false))
Term{:μ, Modulate{Val{false}, :μ}}(Modulate{Val{false}, :μ}(Val{false}()))

julia> U = Term{:U}(Modulate(:U, false))
Term{:U, Modulate{Val{false}, :U}}(Modulate{Val{false}, :U}(Val{false}()))

julia> newexpand((t=t, μ=μ, U=U), :U)
false
flow for false.

[sostock]

The bug is present in versions 1.1 to 1.6. It works correctly on 1.0 and master.

[KristofferC]

The next step here is for someone to identify the commit that fixed the issue (perhaps via a bisect) and then it can be backported to 1.6.

[anaveragehuman]

It appears to be fixed by 3635f04.

This one is a little tricky since git bisect assumes we're looking for the commit introducing breakage, so we need to flip the idea of good and bad. Define a good commit to be one where false only appears once in the output, then the first "bad" commit is the commit that fixes the issue.

make -j -C deps uninstall && make distclean -j && rm -fr usr/ && JULIA_PRECOMPILE=0 make -j && ./julia x.jl
[ 1 -eq $(./julia x.jl | grep false | wc -l) ]

Save the reproducer above as x.jl, this snippet as test.sh, and git bisect run ./test.sh.

[KristofferC]

Should be fixed on #41554. Thanks for the bisect @anaveragehuman

[KristofferC]

Unfortunately, the fix for this issue caused another problem so it cannot be backported to 1.6.

[vchuravy]

Cc: @tkf since you a authored the bisected fix.

[tkf]

I don't object for excluding #39980 due to #42007 per se, but #42007 is a performance problem and this is a correctness problem. So, if #39980 solves this issue, I think this gives us more motivation to actually backport this?

That said, I actually don't understand why #39980 would solve this. #39980 was just changing the precision of inference. I'm guessing it's more like #39980 hide the actual problem? (But, even if #39980 is just a workaround for this, I think the reasoning in my first paragraph still holds.)

[KristofferC]

but #42007 is a performance problem and this is a correctness problem. So, if #39980 solves this issue, I think this gives us more motivation to actually backport this?

For backports to patch-versions, it is not clear if fixing a corner case bug is worth a performance penalty in unrelated pieces of code. The fact that a surprising performance regression occurred also makes it a bit more scary to backport (perhaps there are more perf regressions etc).

[tkf]

Right, that's a fair point. It's good to be cautious.

[vtjnash]

Isolated this to the type-intersection environment being wrong:

julia> struct Modulate{t<:Union{Val{true}, Val{false}, Function}, id} end

julia> (ti, env) = ccall(:jl_type_intersection_with_env, Any, (Any, Any), Type{<:Modulate}, Type{<:Modulate{Val{B}}} where B)
svec(Type{var"#s3"} where var"#s3"<:(Modulate{Val{true}, id} where id), svec(true, var"#s3"<:(Modulate{Val{true}, id} where id)))

julia> Modulate.var
M<:Union{Val{true}, Val{false}, Function}

julia> @assert (env[1]::TypeVar).ub >: Union{typeof(true), typeof(false)}

[ViralBShah]

master is fine, but the type intersection issue still seems to be present on 1.6.6.

[LilithHafner]

I still get an assertion error on master

julia> versioninfo()
Julia Version 1.9.0-DEV.1053
Commit 9e22e567f29 (2022-07-26 14:21 UTC)
Platform Info:
  OS: macOS (x86_64-apple-darwin21.5.0)
  CPU: 4 × Intel(R) Core(TM) i5-8210Y CPU @ 1.60GHz
  WORD_SIZE: 64
  LIBM: libopenlibm
  LLVM: libLLVM-14.0.5 (ORCJIT, skylake)
  Threads: 1 on 2 virtual cores
Environment:
  LD_LIBRARY_PATH = /usr/local/lib

julia> struct Modulate{t<:Union{Val{true}, Val{false}, Function}, id} end

julia> (ti, env) = ccall(:jl_type_intersection_with_env, Any, (Any, Any), Type{<:Modulate}, Type{<:Modulate{Val{B}}} where B)
svec(Type{<:Modulate{Val{true}}}, svec(true, var"#s4"<:(Modulate{Val{true}})))

julia> Modulate.var
t<:Union{Val{true}, Val{false}, Function}

julia> @assert (env[1]::TypeVar).ub >: Union{typeof(true), typeof(false)}
ERROR: TypeError: in typeassert, expected TypeVar, got a value of type Bool
Stacktrace:
 [1] top-level scope
   @ REPL[5]:1

[N5N3]

The root cause should come from intersect_var, it has a branch that fixing the TypeVar's ub/lb eagerly.

julia/src/subtype.c

Lines 2296 to 2297 in e1fa6a5

	if (!jl_is_type(a) && !jl_is_typevar(a))
	return set_var_to_const(bb, a, NULL);

Once we hit to this branch during intersect_union, env records the first matched value and all rest unions would be ignored.

Theoritically, we should always perform restore_env during intersect_all no matter whether the current intersect returns a Union{}. (the output's ub should be maintained seperately)