julia
julia copied to clipboard
type-intersection env may fail merging of multiple value matches
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)
It seems fixed on the master branch.
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.
The bug is present in versions 1.1 to 1.6. It works correctly on 1.0 and master.
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.
It appears to be fixed by 3635f0473dea7c7254d611e3eaa939e0f6dd9484.
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
.
Should be fixed on https://github.com/JuliaLang/julia/pull/41554. Thanks for the bisect @anaveragehuman
Unfortunately, the fix for this issue caused another problem so it cannot be backported to 1.6.
Cc: @tkf since you a authored the bisected fix.
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.)
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).
Right, that's a fair point. It's good to be cautious.
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)}
master is fine, but the type intersection issue still seems to be present on 1.6.6.
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
The root cause should come from intersect_var
, it has a branch that fixing the TypeVar's ub/lb
eagerly.
https://github.com/JuliaLang/julia/blob/e1fa6a51e4142fbf25019b1c95ebc3b5b7f4e8a1/src/subtype.c#L2296-L2297
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)