Interesting stuff. To summarize here to save people some clicks, these methods in DataStructures.jl/src/sorted_dict.jl (that link goes to master, link to the changes here) were removed for type piracy:
@inline Base.eltype(::Type{SortedDict{K,D,Ord}}) where {K,D,Ord <: Ordering} = Pair{K,D}
@inline Base.keytype(::Type{SortedDict{K,D,Ord}}) where {K,D,Ord <: Ordering} = K
@inline Base.valtype(::Type{SortedDict{K,D,Ord}}) where {K,D,Ord <: Ordering} = D
with what I presume to be these methods in julia/base/abstractdict.jl:
function eltype(::Type{<:AbstractDict{K,V}}) where {K,V} ...
keytype(::Type{<:AbstractDict{K}}) where {K} = K
valtype(::Type{<:AbstractDict{<:Any,V}}) where {V} = V
I omitted the body of eltype
there for brevity, but it’s basically an if-statement checking if K
and V
were provided (iterated unions may not) to see what parameters to specify for Pair
, and the branch would occur at compile-time. Those AbstractDict
methods would already work for SortedDict
in sorted_dict.jl due to subtyping:
mutable struct SortedDict{K, D, Ord <: Ordering} <: AbstractDict{K,D} ...
The comments from the pull request explaining the type piracy:
- The meaning of
eltype
is defined for AbstractDict already, which this declaring itself a subtype of, then pirating the definitions for it
- You could own some of
Type{<:YourObject}
, but you don’t own any of Type{<:AbstractDict}
, since that is already owned by the interface for AbstractDict.
- I think one issue is that all code that has previously inferred
eltype(::Type{<:AbstractDict{S,T}})
needs to recompile since this method could have returned something different.
- Correct. You are force it to inject an inference barrier here, so that the compiler can handle the piracy. It knows how to keep working, even though it will cost users performance after it is pushed off the fast path.
- A reason to consider that is that defining new
eltype
etc. methods may in principle invalidate other code; if you would have gotten the same answer without defining those methods, you’re far, far better off deleting them.
As for me, I don’t really understand this. I do see that the AbstractDict
methods are already enough (and better because eltype
also works on iterated unions) and that DataStructures.jl owned ::Type{SortedDict{K,D,Ord}}
, not ::Type{<:AbstractDict{K,V}}
. I don’t see how this is type piracy or how this would recompile anything:
eltype(SortedDict(...))
isn’t ever called between the definitions for SortedDict
type and the previous eltype
method, so the first such call would compile that method.
eltype(T)
for other AbstractDict
input types T
specialize the method for each T
because of the method’s shared type parameters, and as far as I know, none of those specializations would need to be invalidated because of the eltype(SortedDict(...))
call or method definition.
I do love a controversy though, let’s see if this evolves the common understanding of type piracy.