Possible bug with dispatch on parametric abstract type

General Usage
1

Hi all,

I think I may have encountered a possible bug in Julia’s method dispatch. But I would like to post this here first in case anyone can spot something that I have missed. I was able to reproduce the problem in a simple MWE modeled after my actual use case:

abstract type ParamType end
struct ParamImpl <: ParamType end
struct Foo end
struct Bar end
abstract type TestType{T1<:ParamType,T2<:Union{Nothing,<:Foo},T3<:Union{Nothing,<:Bar}} end
Base.@kwdef struct TestTypeImpl{T1,T2,T3} <: TestType{T1,T2,T3}
    val1::T1 = ParamImpl()
    val2::T2 = Foo()
    val3::T3 = nothing
end
testfunc(::TestType{<:ParamImpl}, x) = x
testfunc(::TestType{<:ParamImpl,T2,<:Bar}, x) where {T2} = x*x

testfunc(TestTypeImpl(val3=Bar()), 2.0)
@which testfunc(TestTypeImpl(val3=Bar()), 2.0)
@assert typeof(TestTypeImpl(val3=Bar())) <: TestType{<:ParamImpl,T2,<:Bar} where {T2}

The call to testfunc then invokes the wrong method:

julia> testfunc(TestTypeImpl(val3=Bar()), 2.0)
2.0

The expected behavior here is that the second method of testfunc should be called, as the assertion proves that this is the correct and more specific dispatch. I haven’t been able to narrow down yet exactly what breaks this, but I’d like to get a second opinion before I spend more time on it.

Julia version info:

Julia Version 1.8.5
Commit 17cfb8e65ea (2023-01-08 06:45 UTC)
Platform Info:
  OS: Linux (x86_64-linux-gnu)
  CPU: 8 × Intel(R) Core(TM) i5-8265U CPU @ 1.60GHz
  WORD_SIZE: 64
  LIBM: libopenlibm
  LLVM: libLLVM-13.0.1 (ORCJIT, skylake)
  Threads: 1 on 8 virtual cores

It appears to happen on v1.9 as well.

Thanks!

2

So here’s a minimal example of what’s going on;

julia> struct A end

julia> struct B end

julia> struct C{T1<:A,T2<:B} end

julia> main(::C) = 1
main (generic function with 1 method)

julia> main(::C{T,<:B}) where {T} = 2
main (generic function with 2 methods)

julia> @assert main(C{A,B}()) == 2
ERROR: AssertionError: main(C{A, B}()) == 2

Expanding out the where {T} part and the inferred type parameters for the 1 method gives:

julia> struct A end

julia> struct B end

julia> struct C{T1<:A,T2<:B} end

julia> main(::C{<:A,<:B}) = 1
main (generic function with 1 method)

julia> main(::C{<:Any,<:B}) = 2
main (generic function with 2 methods)

julia> @assert main(C{A,B}()) == 2
ERROR: AssertionError: main(C{A, B}()) == 2

So this show’s what is going on. Method 2 really is less-specific than method 1, and so method 1 gets called.

To fix your method, you need to change

testfunc(::TestType{<:ParamImpl,T2,<:Bar}, x) where {T2} = x*x
# to
testfunc(::TestType{<:ParamImpl,T2,<:Bar}, x) where {T2<:Union{Nothing,<:Foo}} = x*x

julia> abstract type ParamType end

julia> struct ParamImpl <: ParamType end

julia> struct Foo end

julia> struct Bar end

julia> abstract type TestType{T1<:ParamType,T2<:Union{Nothing,<:Foo},T3<:Union{Nothing,<:Bar}} end

julia> Base.@kwdef struct TestTypeImpl{T1,T2,T3} <: TestType{T1,T2,T3}
           val1::T1 = ParamImpl()
           val2::T2 = Foo()
           val3::T3 = nothing
       end

julia> testfunc(::TestType{<:ParamImpl}, x) = x
testfunc (generic function with 1 method)

julia> testfunc(::TestType{<:ParamImpl,T2,<:Bar}, x) where {T2<:Union{Nothing,<:Foo}} = x*x
testfunc (generic function with 2 methods)

julia> testfunc(TestTypeImpl(val3=Bar()), 2.0)
4.0
6 Likes
3

Thanks!

This, however:

julia> main(::C{<:A,<:B}) = 1
main (generic function with 1 method)

julia> main(::C{<:Any,<:B}) = 2
main (generic function with 2 methods)

is very surprising to me. I always assumed that Julia always used the relevant upper bound on the parametric type. I don’t really understand why it does so in the first case but not in the second?

For the first method, ::C is a UnionAll type that implicitly expands to ::C{T1,T2} where {T1,T2}; so logically, per your explanation regarding the second method, this should also be then further expanded to ::C{T1,T2} where {T1<:Any,T2<:Any} but it’s not. Why is this?

4

I don’t think this is true. The definition of C restricts both parameters to be subtypes of A and B respectively, which is more specific than allowing subtypes of Any and B. E.g. this doesn’t work:

julia> C{Int, Float64}
ERROR: TypeError: in C, in T1, expected T1<:A, got Type{Int64}

And since A and B are concrete types, really only those types are allowed as parameters for C and a method that accepts some C{<:Any, <:B} won’t ever be called in such a situation, because no such objects will exist (exept C{A,B}).

1 Like
5

And since A and B are concrete types, really only those types are allowed as parameters for C and a method that accepts some C{<:Any, <:B} won’t ever be called in such a situation, because no such objects will exist (exept C{A,B}).

Yes, and that’s the point that I am trying to make. When expanding the method main(::C{T,<:B}) where {T}, it strikes me as erroneous behavior for Julia to use T<:Any as the upper bound for T because the type parameters of C are bounded such that this type cannot exist. I don’t see any reason why the type bound for T should not be automatically inferred from the type parameters of the struct… but maybe there is some internal technical reason why this isn’t possible?

6

This also looks odd to me:

struct S{T<:Number}
end

julia> S{AbstractString}
ERROR: TypeError: in S, in T, expected T<:Number, got Type{AbstractString}

julia> S{<:AbstractString}
S{<:AbstractString}
3 Likes
7

Ah, then I misunderstood your point. I thought you said that in main(::C) the C is treated as C{T1, T2} where {T1, T2}, but it is treated just as C{<:A,<:B} as it is defined.

I don’t know enough about the internals to say if or why it’s not possible to restrict method definitions for types unions that cannot have any instances, but it would feel weird to me if the type would automatically be restricted, e.g. if these two would always match the same signature:

main(::C{<:A,<:B})
main(::C{<:Any,<:B})

Defining the second would then overwrite the first, but semantically I read this as “do the first method if you have C{A,B} and the second if you have any other C{...,B}”.

I guess it would be nice if there could be at least a warning when one tries to define methods for empty type unions, like in the example from @sijo .

8

Yeah, it really looks odd. My personal interpretation is that with S{AbstractString} we are trying to talk about a type which has no instances (i.e. is useless?), whereas S{<:AbstractString} is a union of types which just happens to be empty (a little bit like Union{}, meaning, of course, that it also has no possible instances… but an empty type union is used at other places in Julia I believe).

As a (probably bad) analogy: I can create an array with no elements [x for x in 1:0], but I cannot create an object that is just “empty”.

9

Right, I mean that this is what it should expand to in order to be consistent with the behavior in the other case. I realize that this is not what actually happens. I am trying to understand the apparent inconsistency.

But I think the point is that Julia should not let you define the second one because it is not a valid type… or rather it has an invalid upper bound.

If you write A{T} and A has a bounded type parameter then T should also implicitly have this bound.

1 Like
10

It’s just replacing a parametric type’s where clause, in this case struct S{T<:Number} with where T<: AbstractString. Replacing where clauses is routine, obviously useful for specifying abstract subtypes, like Ref{T} where T<:Integer. But sometimes you don’t want to write types as strictly for easier editing, or you need nonspecific type bounds in the where clause:

# can edit the union and where clauses afterward
MyTypes = Union{Number, AbstractString}
struct S{T<:Number} end
struct R{T<:AbstractString} end

# and leave the methods as is
bar(a::S{T} where T<:MyTypes, b::R{U} where U<:MyTypes) = 1

# type bound for T is an unknown U, even though
# Vector's where is less constrained than S's
foo(a::Vector{T}, b::S{U}) where {U, T<:U} = 0

I assume this is the reason that where clauses aren’t checked against their original struct immediately.

I am leaning toward agreeing that Julia should check <:DataType bounds in where clauses because an error is thrown if you attempt to make any subtype of S{<:AbstractString}, but someone feel free to show me if this is unfeasible or if an impossible type can be useful.

2 Likes