Incorrect env computed for trivial UnionAll over Union

[vtjnash]

subtyping forgets to incorporate TypeVar-matched parameters from a Union into the env:

julia> (ti, env) = ccall(:jl_type_intersection_with_env, Any, (Any, Any), Union{S, AbstractMatrix{Int}} where S<:AbstractMatrix, AbstractMatrix); env
svec(Int64) # should be svec(T)

julia> T = ccall(:jl_new_structv, Any, (Any, Ptr{Cvoid}, UInt32), Union, [S, S], 2) where S<:AbstractMatrix;

julia> (ti, env) = ccall(:jl_type_intersection_with_env, Any, (Any, Any), T, AbstractMatrix); env
svec(#undef) # should be svec(T)

[N5N3]

The first example looks similar to #41096. Deserve to check if this comes from

julia/src/subtype.c

Lines 2155 to 2165 in 9fd4087

	if (param == 2 || (!jl_has_free_typevars(x) && !jl_has_free_typevars((jl_value_t*)u))) {
	jl_value_t *a=NULL, *b=NULL;
	JL_GC_PUSH2(&a, &b);
	jl_saved_unionstate_t oldRunions; push_unionstate(&oldRunions, &e->Runions);
	a = R ? intersect_all(x, u->a, e) : intersect_all(u->a, x, e);
	b = R ? intersect_all(x, u->b, e) : intersect_all(u->b, x, e);
	pop_unionstate(&e->Runions, &oldRunions);
	jl_value_t *i = simple_join(a,b);
	JL_GC_POP();
	return i;
	}

where the env change is not restored and merged correctly between 2 intersect_all.

[vtjnash]

I think u has_free_typevars here, so maybe similar, but not exactly?

[N5N3]

You are right.
Just notice that Union{S, AbstractMatrix{Int}} where S<:AbstractMatrix <: AbstractMatrix. So intersect_all would not be hitted anyway.

julia> env = Any[nothing];
julia> a = Union{S, Matrix{Float64}} where S<:AbstractMatrix;
julia> @ccall jl_subtype_env(a::Any, AbstractMatrix::Any, env::Ptr{Any}, 1::Cint)::Cint;
julia> env
1-element Vector{Any}:
 Float64

[vtjnash]

In this case, I think it sees that they are == as jl_value_t* pointers, and then fails to copy the env right then (we have code much later to fix up these cases just before returning)

[N5N3]

Exactly, we hit this branch

julia/src/subtype.c

Lines 563 to 566 in e6d9979

	static int subtype_left_var(jl_value_t *x, jl_value_t *y, jl_stenv_t *e, int param)
	{
	if (x == y)
	return 1;

where x === y === AbstractMatrix, thus subtype_unionall would not be called for S <: AbstractMatrix
Remove this fast-path for y <: Unionall should fix the examples above.

[vtjnash]

I guess that should still be fast, since it will stop when it reaches the inside of the UnionAll, and in the meantime will fill out the env (exactly as we want)?

[N5N3]

I tried to bench this extreme case with the above patch

@eval abstract type A{$((Symbol(:T,i) for i in 1:1000)...)} end
B = @eval A{$((:Int for i in 1:1000)...)}

@eval abstract type C{$((Symbol(:T,i) for i in 1:10)...)} end
D = @eval C{$((:Int for i in 1:10)...)}

julia> @btime typeintersect($(Union{S, D} where S<:C), $C)
  23.600 μs (212 allocations: 24.31 KiB) # 14.600 μs (117 allocations: 15.25 KiB) on master

julia> @btime typeintersect($Union{S, B} where S<:A, $A)
  1.737 s (505503 allocations: 92.04 MiB) # 25.128 ms (1003 allocations: 23.01 MiB) on master

But the regression should be rare. I think we can revist it if it does have a pratical usecase