type normalization: Union{Tuple{}, Tuple{Int64, Vararg{Int64, N}} where {N}} into Tuple{Vararg{Int64}}?

[nsajko]

PR #55123 introduced normalization of types like Union{Tuple{}, Tuple{Int64, Vararg{Int64}}} into Tuple{Vararg{Int64}}. The motivation was making subtyping more precise, helping inference, xref #54746.

This was great, however it seems incomplete: in the above Union, replacing Tuple{Int64, Vararg{Int64}} with the equal type Tuple{Int64, Vararg{Int64, N}} where {N} prevents this normalization from occuring, also resulting in some unexpected subtyping behavior:

julia> const A = Tuple{Int64, Vararg{Int64}}
Tuple{Int64, Vararg{Int64}}

julia> const B = Tuple{Int64, Vararg{Int64, N}} where {N}
Tuple{Int64, Vararg{Int64, N}} where N

julia> f(t) = Union{Tuple{}, t}
f (generic function with 1 method)

julia> A == B
true

julia> f(A) == f(B)
false

julia> A <: B
true

julia> f(A) <: f(B)
false

This results in bad inference in PR #56731 (buildkite CI link):

  Expression: Base.infer_return_type(sort, Tuple{Tuple{Vararg{Int}}}) == Tuple{Vararg{Int}}
   Evaluated: Union{Tuple{}, Tuple{Int64, Vararg{Int64, N}} where N} == Tuple{Vararg{Int64}}

I think one way of fixing it would be to normalize Tuple{Int64, Vararg{Int64, N}} where {N} into Tuple{Int64, Vararg{Int64}}. Does that sound doable? Keno explains this can't work.

[Keno]

The two are equal as types, but they're not equivalent under apply_type, so we can't normalize on construction. We could potentially normalize inside of Unions, which would still address the case you care about