Julia: new subtyping issues

[vtjnash]

these are issues found with subtyping after https://github.com/JuliaLang/julia/pull/18457, and other related punchlist items.

• [x] ambiguity / lack of definition of type-intersection environment (issue #20847), also needs documentation
• [x] fix subtype in typetree (currently switched to @test_broken) #20407
• [x] fix sizeof(Task) #20407
• [x] test having TypeMap intersection visitor use (tparam ? jl_isa(t, ty) : jl_subtype(t, ty)) #20407
• [x] fix compile-all mode #20820
• [x] improvements to printing TypeVar bounds in show #20407
• [x] writing a new equivalent-type-replacement check
• [x] correct ambiguity detection test: typeintersect(ml->sig, types) <: ml->sig #20407
• [x] improve check_ambiguous_visitor #20407
• [ ] insert the right simpletype in the TypeMap so that ::Kind queries get cached correctly
• [x] consider noting in doc/src/manual/types.md that "Float does not exist as a typealias for Float64, since the size of the floating point number is problem dependent, not platform dependent" #20407
• [x] define >: function (issupertype) #20407
• [x] work through newly detected ambiguities list (c.f. https://github.com/JuliaLang/julia/pull/18457#discussion_r94530472 from Jan 4)
• [x] correct printing of where appearing in a Type in a method error
  julia> convert(Type{T} where T<:Int, 1)
  ERROR: MethodError: Cannot convert an object of type Int64 to an object of type Type{T} where T<:Int64
  This may have arisen from a call to the constructor Type{T} where T<:Int64(...),
  since type constructors fall back to convert methods.
• [x] remove deprecation of remaining v0.5 items (since a couple random ones got removed in this PR)
• [x] remove UNION_SPLIT_MISMATCH_ERROR from inference
• [x] fix precise_container_types (it calls unwrap, but not re-wrap)
• [x] consider more aggressive normalization of Tuple{Vararg}, or making Vararg not a type
• [x] fix WeakKeyDict constructor https://github.com/JuliaLang/julia/pull/18457#discussion_r96266027 (done in https://github.com/JuliaLang/julia/pull/20092)
• [ ] add list of keywords to Punctuation.md documentation
• [x] add test case for #19414 (#20548)
• [ ] add test case for #19413
• [ ] add test case for #19159
• [ ] add test case for #19041
• [ ] add test case for #18985
• [ ] add test case for #18892
• [x] add test case for #18348 (done in #20097)
• [ ] add test case for #17943
• [ ] add test case for #16922
• [x] add test case for #13165 (done in #20097)
• [ ] add test case for #12814
• [x] add test case for #12721 (done in #20097)
• [ ] add test case for #12596
• [x] add test case for #12580 (done in #20097)
• [ ] add test case for #11407 (#20627)
• [ ] add test case for #8915 (#20627)
• [ ] add test case for #8625 (#20627)
• [ ] add test case for #6721
• [ ] add test case for #2552 (#20627)
• [ ] add test case for https://github.com/JuliaLang/julia/issues/17003
• [ ] add test case for https://github.com/JuliaLang/julia/issues/18307
• [ ] fix test_broken case added in https://github.com/JuliaLang/julia/pull/18352

---

• [x] intersection failure

julia> A = Tuple{Type{Tuple{Vararg{E, N} where N}}} where E
Tuple{Type{Tuple{Vararg{E,N} where N}}} where E

julia> B = Tuple{Type{Tuple{Vararg{E, N}}}} where N where E
Tuple{Type{Tuple{Vararg{E,N}}}} where N where E

julia> typeintersect(B, A)
Assertion failed: ((jl_value_t*)btemp->var != btemp->ub), function finish_unionall, file /Users/jameson/julia/src/subtype.c, line 1159.

https://github.com/JuliaLang/julia/pull/18457#issuecomment-271757202

---

• [x] tuple length subtyping inside invariant parameter:

julia> (Ref{Tuple{Int, Vararg{Int, N}}} where N) <: (Ref{Tuple{Vararg{Int, N}}} where N)
false

---

• [x] another intersection failure:

typeintersect(Tuple{Int, Ref{Pair{K,V}}} where V where K,
              Tuple{Any, Ref{Pair{T,T}} where T })

This overflows the union state stack.

---

• [x] subtype environment sub-optimality preventing a dispatch match, and subtyping error

julia> A = Ref{Tuple{T}} where T;
julia> B = Ref{Tuple{VecElement{S}} where S};
julia> ccall(:jl_match_method, Any, (Any, Any), B, A)
svec(Ref{Tuple{VecElement{S}} where S}, svec(T <: (VecElement{S} where S)))

julia> A = Tuple{Ref{Tuple{T}}, Ref{T}} where T;
julia> B = Tuple{Ref{Tuple{VecElement{S}} where S}, Ref{VecElement{Int}}}
julia> B <: A
true # should be false

a possibly related case is:

julia> A = Ref{Tuple{T, T}} where T;
julia> B = Ref{Tuple{S, Any} where S};
julia> B <: A
true # should be false
# a similar case, but that isn't wrong:
julia> A = Pair{Tuple{T, T}, T} where T;
julia> B = Pair{Tuple{S, Any} where S, Any};
julia> B <: A
true # correct

---

• [ ] Specificity issue in ColorTypes:

julia> (g(::Type{TC}) where TC <: (TransparentColor{C, T, N} where T where N) where C) = C
g (generic function with 1 method)

julia> g(ColorTypes.TransparentColor{ColorTypes.RGB{Float32}, Float32, 4})
ColorTypes.RGB{Float32}

julia> (g(::Type{TC}) where TC <: TransparentColor) = 1
g (generic function with 2 methods)

julia> g(ColorTypes.TransparentColor{ColorTypes.RGB{Float32}, Float32, 4})
1

julia> methods(g)
# 2 methods for generic function "g":
g{TC<:ColorTypes.TransparentColor}(::Type{TC}) in Main at REPL[16]:1
g{C,TC<:(ColorTypes.TransparentColor{C,T,N} where T where N)}(::Type{TC}) in Main at REPL[14]:1

---

• [ ] broken leaftype normalization (relative to codegen / inference assumptions for performance optimization)
  Vector{T} where Int <: T <: Int should return Vector{Int}

  so that isleaftype(T) guarantees isa(T, DataType) and pointer-egal

• [x] related to that normalization failure, it doesn't notice that T <: Int describes a Union with exactly two elements:

julia> (Ref{T} where T <: Int) <: Union{Ref{Union{}}, Ref{Int}}
false

---

- [x] Possibly wrong TypeVar serialization with new typesystem https://github.com/JuliaLang/julia/issues/20324

• [x] error thrown when trying to fill in sparam bounds with a non-type:

julia> ccall(:jl_match_method, Any, (Any, Any), Tuple{0}, Tuple{T} where T)
ERROR: TypeError: TypeVar: in upper bound, expected Type, got Int64
Stacktrace:
 [1] anonymous at <missing>:0
 [2] eval(::Module, ::Any) at ./boot.jl:236
 [3] eval_user_input(::Any, ::Base.REPL.REPLBackend) at REPL.jl:66
 [4] macro expansion; at REPL.jl:97 [inlined]
 [5] (::Base.REPL.##1#2{Base.REPL.REPLBackend})() at event.jl:73

---

• [ ] inconsistent handling of tuple leaftype covariance normalization

julia> (Tuple{S, Int} where S <: Int) <: Tuple{T, T} where T <: Real
false

---

• [x] Specificity: Tuple{Type{Nullable{T}}, Void} where T should be more specific than Tuple{Type{Nullable{T}}, T} where T.

---

type-intersection fails to sufficiently consider that a typevar may match a non-type: issue https://github.com/JuliaLang/julia/issues/20869

[StefanKarpinski]

Is this a list of 0.6-blocking issues?

[vtjnash]

no, it's a summary of bugs that won't be fixed by #18457

[StefanKarpinski]

That doesn't really answer my question.

[JeffBezanson]

It's a list of things he found while reviewing #18457 that don't block merging it. These are generally minor bugs or follow-on work items that don't block 0.6.

[tkelman]

We really shouldn't leave the ambiguity test turned off for very long though. That's the most urgent of these to fix.

[vtjnash]

whoever added "add test cases for all closed issues", can you list the issues that still need test-cases so we can cross them off as we go?

@tkelman there's no ordering in the above list, just a task list to keep track of everything

[tkelman]

Jeff is the one closing them, I've been grepping the test folder for references to each of them but haven't found any hits. (except 18450 and 11840)

edit: any of these cases that are covered by existing tests, should at least cross-reference the relevant issue in a comment / testset description

[pabloferz]

I found that you can't do subtypes(Type) now, but

let T = TypeVar{:T}
    subtypes(Type{T})
end

works.

EDIT: NVM, I think that is covered by the first item on the list.

[thofma]

@pabloferz See also https://github.com/JuliaLang/julia/issues/20086 and https://github.com/JuliaLang/julia/pull/20084 (if you want subtypes to not be removed)

[TotalVerb]

Is the following expected?

julia> Array{NTuple{N, Int} where N} <: (Array{NTuple{N, T} where N}) where T
true

julia> Array{NTuple{N, Integer} where N} <: (Array{NTuple{N, T} where N}) where T
false

I would expect that, since the T is not in covariant position, it should be allowed to range over Integer.

[vtjnash]

Yes. On the left, each element of the tuple can be any subtype of Integer. On the right, each element of the tuple must be the same subtype of Any.

[TotalVerb]

What do you mean by each element of the tuple ranging over any subtype of Integer? The tuple should is in invariant position on both left and right.

[vtjnash]

note that we can coerce that "subtype environment sub-optimality preventing a dispatch match" further to convince it to give other (related) bad answers for other leaftypes:

julia> A = Tuple{Ref{Tuple{T}}, T} where T;
julia> B = Tuple{Ref{Tuple{VecElement{S}} where S}, VecElement{Int}};
julia> ccall(:jl_match_method, Any, (Any, Any), B, A)
svec(Tuple{Ref{Tuple{VecElement{S}} where S}, VecElement{Int64}},
svec(VecElement{Int64})) # expected `VecElement`

julia> A = Tuple{Ref{Tuple{T}}, T, T} where T;
julia> B = Tuple{Ref{Tuple{VecElement{S}} where S}, VecElement{Int}, VecElement{Float64}};
julia> ccall(:jl_match_method, Any, (Any, Any), B, A)
svec(Tuple{Ref{Tuple{VecElement{S}} where S}, VecElement{Int64}, VecElement{Float64}},
svec(Union{VecElement{Float64}, VecElement{Int64}})) # expected `VecElement`

julia> A = Pair{Ref{Tuple{T}}, T} where T;
julia> B = Pair{Ref{Tuple{VecElement} where S}, VecElement};
julia> ccall(:jl_match_method, Any, (Any, Any), B, A)
svec(Pair{Ref{Tuple{VecElement{S}} where S}, VecElement},
svec(Union{VecElement, VecElement{S}})) # expected `VecElement`

[vtjnash]

alright, I've finally managed to turn that incorrect environment into a subtyping error, and updated the top issue with the example

[mauro3]

show of parametrized types doesn't show the type parameters anymore:

julia> immutable B{T}
       a::T
       end

julia> B 
B # used to be B{T}

Is this intentional or a regression? If the former, what is the preferred way get this information? dump works but is a bit on the verbose side. Let me know if should I open an issue for this.

[TotalVerb]

@mauro3

julia> Array
Array

julia> Base.unwrap_unionall(Array)
Array{T,N}

[Keno]

I do agree though that the printing for general UnionAlls needs to be revised to show the type parameters.

[mauro3]

I had a look at the show method https://github.com/JuliaLang/julia/blob/06fa32c40ca838152cac38182690266eaa3af60c/base/show.jl#L185 and it looks like the parameter printing was explicitly disabled by @JeffBezanson.

[JeffBezanson]

the printing for general UnionAlls needs to be revised to show the type parameters.

Example? Type parameters are certainly shown in general.

I decided to show types like Array the way they are usually written in code. This becomes especially nice when printing method signatures, e.g. f(x::Array, y::Array) instead of f(x::Array{T,N} where N where T, y::Array{T,N} where N where T). I'm open to changes here. We could use this only for :compact printing, or use a show/display distinction as in the verbose printing of Chars.

[JeffBezanson]

(Ref{T} where T <: Int) <: Union{Ref{Union{}}, Ref{Int}}

I don't worry too much about this one. I don't think subtyping should be expected to enumerate possible values of unionall variables.

I agree we can and should normalize Vector{T} where Int <: T <: Int (though constantly checking variable bounds for type equality could prove expensive), but the same argument almost applies. isleaftype returns false for this type.

[vtjnash]

but the same argument almost applies

in the second case, it could be undesirable since it could make f(::Type{Ref{Int}}) harder to infer (we don't know that Type.parameters[1] is DataType, so we would need to remove the isConstType predicate from inference and replace it with false.).

the first case doesn't have that issue, so I agree that it's not as likely to be a problem.

[amitmurthy]

As this is a meta-issue tracking issues in the new type system, referencing https://github.com/JuliaLang/julia/issues/20324 here.

[andyferris]

I've been pointed here for a strange error in StaticArrays. The most alarming thing (to me) is that dispatch is not deterministic, in the sense that calling method "A", constructing some object "B", and then calling the method "A" again results in a different (and incorrect) dispatch; see https://github.com/JuliaArrays/StaticArrays.jl/issues/106#issuecomment-280229919.

If someone could let me know if this error appears related to the things here or is orthogonal, I would appreciate it.

[maleadt]

~Is this expected?~

julia> Tuple{Tuple{Int64},Int64} <: NTuple{N} where N
false

julia> Tuple{Int64,Tuple{Int64}} <: NTuple{N} where N
false

Didn't read the NEWS

The type NTuple{N} now refers to tuples where every element has the same type (since it is shorthand for NTuple{N,T} where T). To get the old behavior of matching any tuple, use NTuple{N,Any}

[tkelman]

NTuple's have to be homogenous now - if that's not mentioned clearly enough in news then we should clarify it

[felixrehren]

Added PR #20627 with tests for #2552, #8625, #8915, #11407 (off the bottom of the list)
I couldn't reproduce #6721, because when defining SubgraphObject it runs into an error UndefVarError: T not defined, so I wonder if this one is still relevant
Is the list currently up-to-date? I don't see anything ticked off by #20407

[felixrehren]

Added tests for #12814 #16922 #17943 #18892 #19159 #19413 #19041 #18985 to #20627

12596 seems to be nothing to do, as original problem is no longer replicatable (TypeVar no longer has boolean bound field, and second reported problem was determined to be working as intended)

If these are correct, this ticks off all the "add test case"s on the list so far

[JeffBezanson]

On the ColorTypes specificity issue: this is one of those cases where we need to automatically restrict the bounds of method typevars; in TransparentColor the C parameter is C<:Color, and in the other method definition it's C<:Any, so the current ordering is technically corrrect. Adding C<:Color should fix it.

[vtjnash]

Also added a request to document the type-system parameter matching, as this is a current source of bugs in the inference results (such as #20847) and subtyping errors (already listed above).

[martinholters]

I did some fuzzing where I verified that for types a, b, and x, such that x <: a && x <: b, all of the following hold:

• typeintersect(a, b) == typeintersect(b, a)
• x <: typeintersect(a, b)
• typeintersect(a, b) <: a
• typeintersect(a, b) <: b

Here are some problematic cases I hit:

julia> versioninfo()
Julia Version 0.6.0-pre.alpha.142
Commit 64409a0cae* (2017-03-14 04:20 UTC)
Platform Info:
  OS: Linux (x86_64-linux-gnu)
  CPU: Intel(R) Xeon(R) CPU E5-1620 v2 @ 3.70GHz
  WORD_SIZE: 64
  BLAS: libopenblas (USE64BITINT DYNAMIC_ARCH NO_AFFINITY Sandybridge)
  LAPACK: libopenblas64_
  LIBM: libopenlibm
  LLVM: libLLVM-3.9.1 (ORCJIT, ivybridge)

julia> let a = Tuple{Float64,T7} where T7,
           b = Tuple{S5,Tuple{S5}} where S5,
           x = Tuple{Float64,Tuple{Float64}}
           typeintersect(a, b) <: b
       end
false

julia> let a = Tuple{T1,T1} where T1,
           b = Tuple{Val{S2},S6} where S2 where S6,
           x = Tuple{Val{Float64},Val{Float64}}
           typeintersect(a, b) == typeintersect(b, a)
       end
false

julia> let a = Val{Tuple{T1,T1}} where T1,
           b = Val{Tuple{Val{S2},S6}} where S2 where S6,
           x = Val{Tuple{Val{Float64},Val{Float64}}}
           typeintersect(a, b) <: a
       end
false # true since #21295

julia> let a = Tuple{Float64,T3,T4} where T4 where T3,
           b = Tuple{S2,Tuple{S3},S3} where S2 where S3,
           x = Tuple{Float64,Tuple{1},1}
           typeintersect(a, b) == typeintersect(b, a)
       end
false

julia> let a = Tuple{T1,Tuple{T1}} where T1,
           b = Tuple{Float64,S3} where S3,
           x = Tuple{Float64,Tuple{Float64}}
           typeintersect(a, b) <: a
       end
false

julia> let a = Tuple{5,T4,T5} where T4 where T5,
           b = Tuple{S2,S3,Tuple{S3}} where S2 where S3,
           x = Tuple{5,Float64,Tuple{Float64}}
           typeintersect(a, b) == typeintersect(b, a)
       end
false

julia> let a = Tuple{T2,Tuple{T4,T2}} where T4 where T2,
           b = Tuple{Float64,Tuple{Tuple{S3},S3}} where S3,
           x = Tuple{Float64,Tuple{Tuple{Float64},Float64}}
           typeintersect(a, b) <: b
       end
false

julia> let a = Tuple{Tuple{T2,4},T6} where T2 where T6,
           b = Tuple{Tuple{S2,S3},Tuple{S2}} where S2 where S3,
           x = Tuple{Tuple{Int64,4},Tuple{Int64}}
           typeintersect(a, b) == typeintersect(b, a)
       end
false

julia> let a = Tuple{T3,Int64,Tuple{T3}} where T3,
           b = Tuple{S3,S3,S4} where S4 where S3,
           x = Tuple{Int64,Int64,Tuple{Int64}}
           typeintersect(a, b) <: a
       end
false

julia> let a = Tuple{T1,Val{T2},T2} where T2 where T1,
           b = Tuple{Float64,S1,S2} where S2 where S1,
           x = Tuple{Float64,Val{Int64},Int64}
           typeintersect(a, b) == typeintersect(b, a)
       end
false

julia> let a = Tuple{T1,Val{T2},T2} where T2 where T1,
           b = Tuple{Float64,S1,S2} where S2 where S1,
           x = Tuple{Float64,Val{Int64},Int64}
           typeintersect(a, b) <: a
       end
false

julia> let a = Tuple{Float64,T1} where T1,
           b = Tuple{S1,Tuple{S1}} where S1,
           x = Tuple{Float64,Tuple{Float64}}
           typeintersect(a, b) <: b
       end
false

julia> let a = Tuple{Val{T1},T2,T2} where T2 where T1,
           b = Tuple{Val{Tuple{S2}},S3,Float64} where S2 where S3,
           x = Tuple{Val{Tuple{4}},Float64,Float64}
           typeintersect(a, b) == typeintersect(b, a)
       end
false # true since #21295

julia> let a = Tuple{Val{T1},T2,T2} where T2 where T1,
           b = Tuple{Val{Tuple{S2}},S3,Float64} where S2 where S3,
           x = Tuple{Val{Tuple{4}},Float64,Float64}
           x <: typeintersect(a, b)
       end
false # true since #21295

julia> let a = Tuple{T1,T2,T2} where T1 where T2,
           b = Tuple{Val{S2},S2,Float64} where S2,
           x = Tuple{Val{Float64},Float64,Float64}
           x <: typeintersect(a, b)
       end
false

julia> let a = Val{Tuple{T1,Val{T2},Val{Int64},Tuple{Tuple{T3,5,Float64},T4,T2,T5}}} where T1 where T5 where T4 where T3 where T2,
           b = Val{Tuple{Tuple{S1,5,Float64},Val{S2},S3,Tuple{Tuple{Val{Float64},5,Float64},2,Float64,S4}}} where S2 where S3 where S1 where S4
           typeintersect(b, a)
       end
ERROR: StackOverflowError:
Stacktrace:
 [1] typeintersect(::Any, ::Any) at ./reflection.jl:305

(Unless I'm mistaken, these should all give true.)

Should I open a dedicated issue for tracking those?

[vtjnash]

I was going back through and reviewing the OP here. There's still many that don't have confirmed tests, but are fixed now (the corresponding issue is closed).

In the above comment, all of those return true now except two:

julia> let a = Tuple{T3,Int64,Tuple{T3}} where T3,
           b = Tuple{S3,S3,S4} where S4 where S3,
           x = Tuple{Int64,Int64,Tuple{Int64}}
           typeintersect(a, b) <: a
       end
false # subtype is wrong about (Tuple{S3,S3,S4} where S4<:Tuple{Int64} where S3<:Int64) -- possibly a normalization issue?

julia> let a = Tuple{T1,Val{T2},T2} where T2 where T1,
           b = Tuple{Float64,S1,S2} where S2 where S1,
           x = Tuple{Float64,Val{Int64},Int64}
           typeintersect(a, b) <: a
       end
false # suboptimal, but valid (type-intersection was over-approximated)