Unclear ambiguity when one argument is more specific in one method and another argument in the other

[Seelengrab]

MWE:

julia> struct Foo{N} <: IO end

julia> Base.write(::Foo{N}, b::Base.BitInteger) where N = write(stdout, b)

julia> write(Foo{0x0}(), 0x00)
1

julia> write(Foo{0x0}(), 0x0000)
ERROR: MethodError: write(::Foo{0x00}, ::UInt16) is ambiguous.

Candidates:
  write(s::IO, x::Union{Float16, Float32, Float64, Int128, Int16, Int32, Int64, UInt128, UInt16, UInt32, UInt64})
    @ Base io.jl:685
  write(::Foo{N}, b::Union{Int128, Int16, Int32, Int64, Int8, UInt128, UInt16, UInt32, UInt64, UInt8}) where N
    @ Main REPL[2]:1

Possible fix, define
  write(::Foo{N}, ::Union{Int128, Int16, Int32, Int64, UInt128, UInt16, UInt32, UInt64}) where N

Stacktrace:
 [1] top-level scope
   @ REPL[4]:1

I think this should not be ambigious, since Foo{0x0} is concrete and more specific than IO, while the intersection of the two Unions with the passed in type is the same, so the second argument cannot serve as a tie breaker/cause for ambiguity either way.

Version:

julia> versioninfo()
Julia Version 1.9.0-DEV.1622
Commit e8342863db* (2022-10-20 10:44 UTC)
Platform Info:
  OS: Linux (x86_64-pc-linux-gnu)
  CPU: 4 × Intel(R) Core(TM) i7-6600U CPU @ 2.60GHz
  WORD_SIZE: 64
  LIBM: libopenlibm
  LLVM: libLLVM-14.0.6 (ORCJIT, skylake)
  Threads: 4 on 4 virtual cores
Environment:
  JULIA_NUM_THREADS = 4

[Moelf]

one of the union has Int8 and UInt8 the other doesn't, so the two unions are either <: nor :>.

but yeah I would expect Union is equivalent to splitting into n methods so I wouldn't expect an ambiguity error here .

[Seelengrab]

one of the union has Int8 and UInt8 the other doesn't, so the two unions are either <: nor :>.

Not sure how that's relevant - the ambiguity error is thrown when passing in UInt16, which both unions have. I'm arguing that this shouldn't be cause for ambiguity, since the other arguments are still more specific (IO vs Foo{N}).

[Moelf]

Not sure how that's relevant

Because it IS relevant?

julia> struct Foo{N} <: IO end

julia> Base.write(::Foo{N}, b::Union{Float16, Float32, Float64, Int128, Int16, Int32, Int64, UInt128, UInt16, UInt32, UInt64}) where N = write(stdout, b)

julia> write(Foo{0x0}(), 0x0000)
2

#btw
julia> Base.write(::Foo{N}, b::Union{Int8, UInt8}) where N = write(stdout, b)

julia> write(Foo{0x0}(), 0x00)
ERROR: MethodError: write(::Foo{0x00}, ::UInt8) is ambiguous. Candidates:
  write(s::IO, x::UInt8) in Base at io.jl:278
  write(::Foo{N}, b::Union{Int8, UInt8}) where N in Main at REPL[6]:1
Possible fix, define
  write(::Foo{N}, ::UInt8) where N

[Seelengrab]

What I'm saying is that I don't see how the <: or :> relationship between the unions should matter at all for dispatch. If anything, at most their typeintersect should be relevant to see whether they are ambiguous with respect to that one argument, which, yeah, they are:

julia> un
Union{Float16, Float32, Float64, Int128, Int16, Int32, Int64, UInt128, UInt16, UInt32, UInt64}

julia> typeintersect(Base.BitInteger, un)
Union{Int128, Int16, Int32, Int64, UInt128, UInt16, UInt32, UInt64}

julia> typeintersect(un, UInt16)
UInt16

julia> typeintersect(Base.BitInteger, UInt16)
UInt16

Both contain UInt16, so clearly they are ambiguous with respect to that. However, since we pass in Tuple{Foo{0x0}, UInt16}, the fact that we have Foo{0x0} passed in and there's a method taking Foo{N} <: IO, the method taking in Foo should be more specific purely from the fact that Foo is more specific than IO, with the other arguments being resolved:

julia> Base.morespecific(Foo, IO)
true

julia> Base.morespecific(Tuple{Foo, UInt16}, Tuple{IO, UInt16})
true

I guess this indicates a problem with method selection in dispatch? I would have thought that Union arguments are checked first for eliminating potential method matches instead of plain typeintersect of the argument types and the method signatures:

julia> args = Tuple{Foo{0x0}, UInt16}
Tuple{Foo{0x00}, UInt16}

julia> io_sig = Tuple{IO, un}
Tuple{IO, Union{Float16, Float32, Float64, Int128, Int16, Int32, Int64, UInt128, UInt16, UInt32, UInt64}}

julia> foo_sig = Tuple{Foo, Base.BitInteger}
Tuple{Foo, Union{Int128, Int16, Int32, Int64, Int8, UInt128, UInt16, UInt32, UInt64, UInt8}}

julia> typeintersect(io_sig, args)
Tuple{Foo{0x00}, UInt16}

julia> typeintersect(foo_sig, args)
Tuple{Foo{0x00}, UInt16}

but maybe that's not the case and is done deliberately this way. The typeintersect is correct, mind you - intersecting io_sig with args should give the same type as intersecting foo_sig with args. However, that does not mean that io_sig is more specific than or necessarily ambiguous with foo_sig, I don't think.

[Moelf]

What I'm saying is that I don't see how the <: or :> relationship between the unions should matter at all for dispatch

not saying it should, but it does, and since we don't have a formal spec, the only spec is the implementation.

[Seelengrab]

Yeah, and I'm saying we should change the implementation to make this clearly unambiguous case truly not ambiguous :)

[sgaure]

So ... the suggestion is that if there's ambiguity as now, i.e. the typeintersect of the candidates' type signatures is not equal to any of them, one should check if one of the signatures has more concrete types than the others and choose that one?

[Seelengrab]

one should check if one of the signatures has more concrete types than the others and choose that one?

No, not necessarily. The signature containing Foo may also be abstract, the important part is just that we have Foo <: IO. In particular, since Foo is already a UnionAll, it's not a concrete type anyway.

So for two methods bar(::Foo, ::T) and bar(::IO, S) where neither S <: T nor S >: T but typeintersect(T, S) != Union{}, when calling with some arg1 isa Foo and typeof(arg2) <: T && typeof(arg2) <: S both hold, we should call the bar method that explicitly has Foo, instead of throwing an ambiguity error. This should generalize, I think (or may occur rarer with 3-arg methods, 4-arg methods etc, since more objects are available to break ambiguity ties).

[vtjnash]

I suspect morespecific is struggling to prove that all elements of both Unions are equivalent-or-disjoint, so it is giving up and declaring ambiguity. It would like to try to sort the method such that it has the same precedence as if each element of the Union was declared as a separate method. But comparing Unions then is tricky, since it has to decide if all elements of one are strictly ordered (<=) with the elements of the other one. (c.f. the start of my JuliaCon 2022 talk)

This seems likely a fixable case.

[Seelengrab]

For morespecific in isolation, I agree! But in dispatch, we don't just have the two signatures in isolation, we have the actual argument types that can serve as a tie breaker.

The way I picture dispatch to work (and this may be totally wrong) is that the function to-be-called determines the method table to use. Then, a filtering process starts - if at the end of that filtering process we have more than one method left over, we have an ambiguity. If no methods are left over, we have a MethodError. If exactly one method is left over, we found our match and call it.

I think the current steps for that filtering are (roughly)

1. Filter out based on arities (trivial cases to reject)
2. Filter out based on subtyping/morespecific/typeintersect returning a non-Union{} type when comparing the methods' signature to the callers' signature
3. Hopefully we have a singular match.

And what I think it should be

1. Filter out based on arities
2. Filter out based on subtyping/morespecific/typeintersect of the method signature with the caller signature (so only methods are kept where each declared argument type is a supertype of the passed-in argument type)
3. Are we done (empty/only one left)? -> return it - this should ensure this stays fast for existing code that's unambiguous here
4. Otherwise, if we're still ambiguous:
   a. "remove" unions from the potential signatures by typeintersecting them with the corresponding argument type from the caller (this will be non-Union{}, since we removed the methods where that can happen earlier). This ensures that all Union-based ambiguities are resolved, since they are (at worst) all the same as the true argument type now - crucially without resolving supertype relationships for UnionAlls and abstract types yet.
   b. Now sort the methods, where concretely typed signatures are better than UnionAll, which are better than abstract type. Matches with more concrete types are also better than matches with more UnionAlls, which are in turn better than matches with more abstract types. Ties within each tier don't really matter, as long as the topmost/"best" match is not tied with another entry. If it is, we have a true ambiguity that needs to be resolved manually (think of having f(::Any, Int) and f(::String, ::Any) and calling f(::String, Int) and the likes).

It might be possible to have a pre-filtering step where you just count the number of concrete, UnionAll and abstract type arguments for each signature (should be cacheable at definition time) and sort by that tuple (depends on whether we want (3 concrete, 5 UnionAll, 2 abstract) to be better than (3 concrete, 2 UnionAll, 5 abstract) or not). The caveat of course is that I have no idea how it's actually implemented and it might very well be that this is not performant in the slightest 😅

[LilithHafner]

See also #47325 which would resolve this ambiguity in favor of the ::Foo{N} method.

[Seelengrab]

Yes, partially - I think this issue can be fixed without impacting the more general case presented there (what I still call a "true ambiguity" here).

[Seelengrab]

This has regressed now - on master, the first write too is now ambiguous:

julia> versioninfo()
Julia Version 1.10.0-DEV.103
Commit d3e4daba80 (2022-12-14 19:36 UTC)
Platform Info:
  OS: Linux (x86_64-pc-linux-gnu)
  CPU: 24 × AMD Ryzen 9 7900X 12-Core Processor
  WORD_SIZE: 64
  LIBM: libopenlibm
  LLVM: libLLVM-14.0.6 (ORCJIT, znver3)
  Threads: 24 on 24 virtual cores
Environment:
  JULIA_NUM_THREADS = 24

julia> struct Foo{N} <: IO end

julia> Base.write(::Foo{N}, b::Base.BitInteger) where N = write(stdout, b)

julia> write(Foo{0x0}(), 0x00)
ERROR: MethodError: write(::Foo{0x00}, ::UInt8) is ambiguous.

Candidates:
  write(s::IO, x::UInt8)
    @ Base io.jl:291
  write(::Foo{N}, b::Union{Int128, Int16, Int32, Int64, Int8, UInt128, UInt16, UInt32, UInt64, UInt8}) where N
    @ Main REPL[3]:1

Possible fix, define
  write(::Foo{N}, ::UInt8) where N

Stacktrace:
 [1] top-level scope
   @ REPL[4]:1

julia> write(Foo{0x0}(), 0x0000)
ERROR: MethodError: write(::Foo{0x00}, ::UInt16) is ambiguous.

Candidates:
  write(s::IO, x::Union{Float16, Float32, Float64, Int128, Int16, Int32, Int64, UInt128, UInt16, UInt32, UInt64})
    @ Base io.jl:688
  write(::Foo{N}, b::Union{Int128, Int16, Int32, Int64, Int8, UInt128, UInt16, UInt32, UInt64, UInt8}) where N
    @ Main REPL[3]:1

Possible fix, define
  write(::Foo{N}, ::Union{Int128, Int16, Int32, Int64, UInt128, UInt16, UInt32, UInt64}) where N

Stacktrace:
 [1] top-level scope
   @ REPL[5]:1

As far as I can tell, no new methods have been added, so it's unclear where this regressed..

[vtjnash]

Looks like a bugfix. You should not be able to define two methods simultaneously for Uint8

[Seelengrab]

Not sure what you mean - I don't think I've done that? The two errors are from distinct calls, they're just the MWE from the initial post. I tried bisecting, without much success though..

[vtjnash]

Sorry, yeah, I meant the royal you, since Base defined one of the methods and the OP defined the other

[Seelengrab]

But I am the OP, and only Base is defining the fallback for UInt8 😅 I'm not defining a method for (IO, UInt8) either way, it's a more specific type :)