Inference regression on master in code that sorts arguments by type

[tkoolen]

Consider the following code (see https://discourse.julialang.org/t/function-with-unordered-parameter-list/7383/6?u=tkoolen for context and explanation):

abstract type ParticleType end
struct ChargedLepton <: ParticleType end
struct Hadron <: ParticleType end
struct AntiNeutrino <: ParticleType end

# functionality for finding the first argument of a specific type:
@inline first_type_match(::Type{T}, ts...) where {T} = first_type_match(T, (), ts...)
@inline first_type_match(::Type{T}, discards::Tuple, t1, ts...) where {T} = first_type_match(T, tuple(discards..., t1), ts...)
@inline first_type_match(::Type{T}, discards::Tuple, t1::T, ts...) where {T} = (t1, tuple(discards..., ts...))
@inline first_type_match(::Type{T}, discards::Tuple) where {T} = (nothing, discards)

# define type order
first_particle_type() = Hadron
next_particle_type(::Type{Hadron}) = ChargedLepton
next_particle_type(::Type{ChargedLepton}) = AntiNeutrino

# sorting `ParticleType` arguments by type using type order above
const ParticleTypeTuple = Tuple{Vararg{<:ParticleType,N} where N}
sort_particle_types(ts::ParticleType...) = _sort_particle_types(first_particle_type(), (), ts...)
@inline _sort_particle_types(::Type{<:ParticleType}, result::ParticleTypeTuple) = result
@inline function _sort_particle_types(::Type{T}, result::ParticleTypeTuple, ts::ParticleType...) where T<:ParticleType
    match, discards = first_type_match(T, ts...)
    _sort_particle_types(handle_match(T, result, match)..., discards...)
end

@inline handle_match(::Type{T}, result::ParticleTypeTuple, match::Void) where {T<:ParticleType} = (next_particle_type(T), result)
@inline handle_match(::Type{T}, result::ParticleTypeTuple, match::ParticleType) where {T<:ParticleType} = (first_particle_type(), tuple(result..., match))

@code_warntype sort_particle_types(ChargedLepton(), Hadron(), AntiNeutrino())

On 0.6.1, the code_warntype shows that the return type is inferred as

Tuple{Hadron,ChargedLepton,AntiNeutrino}

as I had hoped, but on one-day-old nightly (Julia Version 0.7.0-DEV.2692, Commit 710a3d8* (2017-11-29 07:44 UTC)), the return type is inferred as

Tuple{Vararg{ParticleType,N} where N}

It should also be noted that on 0.6.1, calling sort_particle_types from global scope results in a StackOverflowError in inference code (https://gist.github.com/tkoolen/8c3eb36aba92da194e84725c2eab18f6), whereas the function does return as expected on nightly.

[vtjnash]

(0.6 bug) fixed by #23912

[vtjnash]

Note: this looks like a variation on the common "tuple split" pattern used in base in a couple places (most notably perhaps, right now, being sparse broadcast "capturescalars"). I think there is likely a variant of this that will still be inferable, although it may require creative thinking to sort out.

[tkoolen]

OK, thanks. For reference, it looks like simply changing all of the @inlines to Base.@pures made everything inferable on nightly (up to 12 arguments).

[vtjnash]

Er, sure, yes, simply disabling correctness is one solution.

[tkoolen]

@vtjnash, could you explain why this usage of @pure is incorrect? I'm looking through #24817; which of the items in the list does this violate?