Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

new subtyping issues #19998

Closed
32 of 53 tasks
vtjnash opened this issue Jan 12, 2017 · 31 comments
Closed
32 of 53 tasks

new subtyping issues #19998

vtjnash opened this issue Jan 12, 2017 · 31 comments
Labels
types and dispatch Types, subtyping and method dispatch

Comments

@vtjnash
Copy link
Member

vtjnash commented Jan 12, 2017

these are issues found with subtyping after #18457, and other related punchlist items.


  • 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.

#18457 (comment)


  • tuple length subtyping inside invariant parameter:
julia> (Ref{Tuple{Int, Vararg{Int, N}}} where N) <: (Ref{Tuple{Vararg{Int, N}}} where N)
false

  • 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.


  • 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

  • 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


  • 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

  • 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 #20869

@kshyatt kshyatt added the types and dispatch Types, subtyping and method dispatch label Jan 12, 2017
@StefanKarpinski
Copy link
Member

Is this a list of 0.6-blocking issues?

@vtjnash
Copy link
Member Author

vtjnash commented Jan 13, 2017

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

@StefanKarpinski
Copy link
Member

That doesn't really answer my question.

@JeffBezanson
Copy link
Member

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
Copy link
Contributor

tkelman commented Jan 16, 2017

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

@vtjnash
Copy link
Member Author

vtjnash commented Jan 16, 2017

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
Copy link
Contributor

tkelman commented Jan 16, 2017

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

mauro3 added a commit to mauro3/julia that referenced this issue Jan 17, 2017
mauro3 added a commit to mauro3/julia that referenced this issue Jan 17, 2017
mauro3 added a commit to mauro3/julia that referenced this issue Jan 17, 2017
mauro3 added a commit to mauro3/julia that referenced this issue Jan 18, 2017
Added tests for issues JuliaLang#12580, JuliaLang#18348, JuliaLang#13165, JuliaLang#11803, JuliaLang#12721

Enabled extra tests for JuliaLang#11840, however, that isssue is not resolved
yet but needs tests triggering it.
@pabloferz
Copy link
Contributor

pabloferz commented Jan 19, 2017

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
Copy link
Contributor

thofma commented Jan 19, 2017

@pabloferz See also #20086 and #20084 (if you want subtypes to not be removed)

@TotalVerb
Copy link
Contributor

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
Copy link
Member Author

vtjnash commented Jan 20, 2017

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
Copy link
Contributor

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.

mauro3 added a commit to mauro3/julia that referenced this issue Jan 20, 2017
Added tests for issues JuliaLang#12580, JuliaLang#18348, JuliaLang#13165, JuliaLang#12721

For JuliaLang#11803 it was decidided that no tests are needed.

Enabled extra tests for JuliaLang#11840, however, that isssue is not resolved
yet but needs new tests triggering it.
mauro3 added a commit to mauro3/julia that referenced this issue Jan 20, 2017
Added tests for issues JuliaLang#12580, JuliaLang#18348, JuliaLang#13165, JuliaLang#12721

For JuliaLang#11803 it was decidided that no tests are needed.

Enabled extra tests for JuliaLang#11840, however, that isssue is not resolved
yet but needs new tests triggering it.
@vtjnash vtjnash added this to the 0.6.0 milestone Jan 22, 2017
@vtjnash
Copy link
Member Author

vtjnash commented Jan 22, 2017

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
Copy link
Member Author

vtjnash commented Jan 22, 2017

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

@mauro3
Copy link
Contributor

mauro3 commented Jan 23, 2017

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
Copy link
Contributor

@mauro3

julia> Array
Array

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

@Keno
Copy link
Member

Keno commented Jan 24, 2017

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

@mauro3
Copy link
Contributor

mauro3 commented Jan 24, 2017

I had a look at the show method

function print_without_params(x::ANY)
and it looks like the parameter printing was explicitly disabled by @JeffBezanson.

@JeffBezanson
Copy link
Member

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
Copy link
Member

(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
Copy link
Member Author

vtjnash commented Jan 24, 2017

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
Copy link
Contributor

As this is a meta-issue tracking issues in the new type system, referencing #20324 here.

@andyferris
Copy link
Member

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 JuliaArrays/StaticArrays.jl#106 (comment).

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

@maleadt
Copy link
Member

maleadt commented Feb 16, 2017

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
Copy link
Contributor

tkelman commented Feb 16, 2017

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

@felixrehren
Copy link
Contributor

felixrehren commented Feb 16, 2017

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
Copy link
Contributor

felixrehren commented Feb 17, 2017

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
Copy link
Member

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
Copy link
Member Author

vtjnash commented Mar 7, 2017

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).

@vtjnash vtjnash mentioned this issue Mar 14, 2017
@martinholters
Copy link
Member

martinholters commented Mar 14, 2017

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
Copy link
Member Author

vtjnash commented Jul 8, 2019

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)

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
types and dispatch Types, subtyping and method dispatch
Projects
None yet
Development

No branches or pull requests