Inference resulting in where T<:Int64

[Jutho]

While there are already several issues regarding inference regression on master, I decided to file this issue as it also exists in Julia 0.6.

I noticed a problem where inference introduces a type parameter which is bound to be a leaf type. Noticeably, while the problem exists on julia 0.6 and 0.7-DEV, it pops up sooner on master, probably because of the interplay with other inference regressions with respect to tuples (#23277, #22513).

I also posted this example in #22513 as I first assumed it was another instance of that issue:

tpermute(t::NTuple{N,T}, p::NTuple{N,Int}) where {T,N} = _tpermute((), t, p)
_tpermute(tdst::NTuple{N,T}, tsrc::NTuple{N,T}, p::NTuple{N,Int}) where {T,N} = tdst
_tpermute(tdst::NTuple{M,T}, tsrc::NTuple{N,T}, p::NTuple{N,Int}) where {T,M,N} = _tpermute((tdst...,tsrc[p[M+1]]), tsrc, p)

On master, one obtains for any N>=2

julia> N=2;Base.return_types(tpermute,Tuple{NTuple{N,Int},NTuple{N,Int}})
1-element Array{Any,1}:
 Tuple{Vararg{T,2}} where T<:Int64

which seems like it would infer correctly if not making the mistake of introducing a type parameter for a leaf type. On Julia 0.6, this is correctly inferred up to tuples of length N=15, after which one obtains:

julia> N=16;Base.return_types(tpermute,Tuple{NTuple{N,Int},NTuple{N,Int}})
1-element Array{Any,1}:
 Union{Tuple{T,T,T,T,T,T,T,T,T,T,T,T,T,T,Vararg{T,2}} where T<:Int64, Tuple{Vararg{T,16}} where T<:Int64}

which has the same issue with the type parameter, and the additional issue of not identifying the two types in the Union.

A slightly different implementation for the same function:

tpermute(t::NTuple{N,T}, p::NTuple{N,Int}) where {T,N} = _tpermute((), t, p)
_tpermute(tdst::NTuple{N,T}, tsrc::NTuple{N,T}, p::Tuple{}) where {T,N} = tdst
_tpermute(tdst, tsrc, p) = _tpermute((tdst..., tsrc[p[1]]), tsrc, Base.tail(p))

has the same behavior on master, and only fixes the Union problem on Julia 0.6.

My apologies if this is another instance of an existing issue. I don't know how inference works and did not find any similar issue.

[mauro3]

On 0.5.2 the first example works fine but the N=16 errors:

julia> N=16;Base.return_types(tpermute,Tuple{NTuple{N,Int},NTuple{N,Int}})               
WARNING: An error occurred during inference. Type inference is now partially disabled.   
ErrorException("type too large")                                                         
rec_backtrace at ~/julia/julia-0.5/src/stackwalk.c:84                          
... (long)

[vtjnash]

julia> N=2^18;Base.return_types(tpermute,Tuple{NTuple{N,Int},NTuple{N,Int}})
1-element Array{Any,1}:
 NTuple{262144,Int64}

(for the first example anyways—the second tends to infer up to 2^10, then starts to stack-overflow the compiler around 2^11)