datatype cache normalization bugs

[vtjnash]

These types should print the same (since the type parameters are type-equal), if the datatype cache (and new hash computation) is working correctly:

julia> Val{Tuple{Any}}
Val{Tuple{Any}}

julia> Val{Tuple{T} where T}
Val{Tuple{T} where T}

julia> Val{Tuple{Float64,Int64,Int64}}
Val{Tuple{Float64,Int64,Int64}}

julia> Val{Tuple{Float64,Vararg{T,2}} where T<:Int64}
Val{Tuple{Float64,Vararg{T,2}} where T<:Int64}

julia> Val{Tuple{Float64,T,T} where T<:Int64}
Val{Tuple{Float64,Vararg{T,2}} where T<:Int64}

This is actually an improvement from before the new hash computation code (the last one was previously also creating a unique type). Found these by some quick fuzzing, so I'm pleased to see there weren't more!

[vtjnash]

The fuzzing code was simply this diff, and then seeing which subtype tests failed:

diff --git a/src/subtype.c b/src/subtype.c
index 3b8cfce277..8f20db6e3c 100644
--- a/src/subtype.c
+++ b/src/subtype.c
@@ -235,6 +235,8 @@ static int obviously_unequal(jl_value_t *a, jl_value_t *b)
         if (jl_is_datatype(b)) {
             jl_datatype_t *ad = (jl_datatype_t*)a;
             jl_datatype_t *bd = (jl_datatype_t*)b;
+            if (ad->hash != bd->hash)
+                return 1;
             if (ad->name != bd->name)
                 return 1;
             int istuple = (ad->name == jl_tuple_typename);
@@ -1360,6 +1362,7 @@ static int is_definite_length_tuple_type(jl_value_t *x)
 static int forall_exists_equal(jl_value_t *x, jl_value_t *y, jl_stenv_t *e)
 {
     if (obviously_egal(x, y)) return 1;
+    //if (obviously_unequal(x, y)) return 0;
 
     if ((is_indefinite_length_tuple_type(x) && is_definite_length_tuple_type(y)) ||
         (is_definite_length_tuple_type(x) && is_indefinite_length_tuple_type(y)))

[vtjnash]

Another similar one:

julia> Val{Union{Nothing, T} where T} == Val{Any}
false

julia> Val{Union{Nothing, T} where T} <: Val{Any}
true

julia> Val{Union{Nothing, T} where T} >: Val{Any}
true

[martinholters]

I have a branch where I do a bit of normalization when a UnionAll is used as a type parameter. I get e.g.

julia> Val{Tuple{T} where T}
Val{Tuple{Any}}

That does have some subtle issues though. E.g.

julia> eltype(Vector{Tuple{T} where T}){Int}
Tuple{Int64} # master
ERROR: TypeError: in Type{...} expression, expected UnionAll, got Type{Tuple{Any}} # branch

Or this test:

julia/test/subtype.jl

Lines 1362 to 1363 in d31962c

	g24521(::T, ::T) where {T} = T
	@test_throws MethodError g24521(Tuple{Any}, Tuple{T} where T)

The second parameter is normalized at some point on my branch, so the method matches and returns DataType.

So I think we really need careful analysis as to where we may exchange type-equal types for one another and where we mustn't, unless we accept some breakage from normalizing more aggressively.

[martinholters]

Duplicate of #31696, not sure which one we should keep open.

[vtjnash]

The second parameter is normalized at some point on my branch

The Type{} object should be special, and not do this normalization that other types (particularly concrete ones) need to do

[martinholters]

Right, excepting Type is what I had settled on. Excepting abstract types in general might be another option. Anyway, discussion on this is probably better had at #36211 which is based on said branch, if we considering following that route.