Automatically resolve most method ambiguities

[LilithHafner]

Motivation

ChainRulesCore.jl defines

Base.:*(a::AbstractThunk, b) = unthunk(a) * b

MultivariatePolynomials.jl defines

Base.:*(α, r::RationalPoly) = (α * r.num) / r.den

How are we supposed to resolve *(::AbstractThunk, ::RationalPoly)?

Neither ChainRulesCore.jl nor MultivariatePolynomials.jl have any relation to each other or reason to be direct dependencies.

One option is weak dependencies, but this requires the package authors to be aware of each other and one of them to take action (add glue code) to ensure interoperability.

Proposal

Another option is to establish method precedence that is more opinionated than <:.

I porpose the folowing rule:

Look at components recursively and from left to right, resolving the ambiguity with the first unambiguous component.

This is not a breaking change, as it should not reverse the precedence of any currently unambiguous method pairs.

See also previous discussion on discourse

To clarify the interpretation, for parametric types, this means first compare the body and then the parameters First{Second, Third}. Subtypes are preferred over supertypes, values are preferred over types, and typevars are compared first based on their upper bound and only then based on the set of previous usages of that type var. Types are equvalent to typevars without any preivous usages. Tuple{Dict{T, U}, V} where T <: Integer is preffered over Tuple{Dict{T, T}, T} where T <: Integer which is preffered over Tuple{Dict{<:Integer, T}, T} where T <: Integer and Tuple{Dict{T, <:Integer}, T} where T <: Integer, but the final two are ambiguous. For unions, only prefer one union over another if every member of the first has a member in the second that it is either preffered over or is equal to. Types with more specified parameters are preffered over types with fewer if all the common parameters have no precedence.

To further clarify the intpretation, here is an implementation of the proposed semantics with a `prefer`:

macro compare(<, x, y)
    quote
        _x, _y = $(esc(x)), $(esc(y))
        $(<)(_x, _y) && return true
        $(<)(_y, _x) && return false
        nothing
    end
end
macro prefer(x, y, tvc)
    quote
        p = prefer($(esc(x)), $(esc(y)), $(esc(tvc)))
        p isa Bool && return p
        nothing
    end
end

function prefer(a::Int, b::Int, tvc)
    @compare (>) a b
    missing
end

const UUID_COUNTER = Ref(0)
uuid() = UUID_COUNTER[] += 1

function prefer(A::TypeVar, B::TypeVar, tvc)
    id = uuid()
    a, b = tvc[A], tvc[B] = push!(get(tvc, A, Set{Int}()), id), push!(get(tvc, B, Set{Int}()), id)
    @prefer A.ub B.ub tvc
    @compare (>) (a ⊆ b) (b ⊆ a)
    missing
end

function prefer(A::TypeVar, B::Type, tvc)
    a = tvc[A] = push!(get(tvc, A, Set{Int}()), uuid())
    @prefer A.ub B tvc
    length(a) > 1 && return true
    missing
end
prefer(A::Type, B::TypeVar, tvc) = !prefer(B, A, tvc)

function prefer(A::DataType, B::DataType, tvc)
    if A.name.wrapper != B.name.wrapper
        @compare (<:) A.name.wrapper B.name.wrapper
    else
        for (i, j) in zip(A.parameters, B.parameters)
            @prefer i j tvc
        end
    end
    missing
end

_body(A::UnionAll) = _body(A.body)
_body(A) = A
prefer(A::UnionAll, B::Type, tvc) = prefer(_body(A), B, tvc)
prefer(A::Type, B::UnionAll, tvc) = prefer(A, _body(B), tvc)
prefer(A::UnionAll, B::UnionAll, tvc) = prefer(_body(A), _body(B), tvc) # ha ha

# Values
prefer(A::Type, B, tvc) = false
prefer(A, B::Type, tvc) = true
prefer(A::TypeVar, B, tvc) = false
prefer(A, B::TypeVar, tvc) = true
prefer(A, B, tvc) = missing

expand(A::Union) = (expand(A.a)..., expand(A.b)...)
expand(A) = (A,)

function _prefer(a, b)
    all(a) do i
        any(b) do j
            i === j || prefer(i, j) === true
        end
    end
end
function prefer(A::Type, B::Type, tvc)
    a, b = expand(A), expand(B)
    @compare (>) _prefer(a, b) _prefer(b, a)
    missing
end

function prefer(A::Type{<:Tuple}, B::Type{<:Tuple}, tvc)
    A = A isa UnionAll ? _body(A) : A
    B = B isa UnionAll ? _body(B) : B
    for (a, b) in zip(A.parameters, B.parameters)
        @prefer a b tvc
    end
    @compare (>) length(A.parameters) length(B.parameters)
    missing
end

prefer(A, B) = prefer(A, B, Dict{TypeVar, Set{Int}}())

Emperical analysis

I loaded many popular packages (all but one of the 499 packages with at least as many downloads as Articfacts.jl, including all the standard libraries) and ran `Test.detect_ambiguities(mods...; recursive=true)` This yielded 7652 ambiguities. Of these, 7586 (99.1%) would be reolved by the proposed precedence rules in the `prefer` function above. A sample of 20 randomly chosen resolutions to check if they are good or not (currently they are ambiguous method errors) reveals my ignorance of obscure methods in the julia ecosystem. I attempted to code them as good or bad, and here are my notes; the methods listed first are prefferred over the methods listed second:

convert(::Type{AbstractArray{T, N}}, x::LArray{S, N, <:Any, Syms}) where {T, S, N, Syms} in LabelledArrays at /Users/x/.julia/packages/LabelledArrays/IYs8M/src/larray.jl:144
convert(::Type{T}, a::T) where T<:AbstractArray in Base at abstractarray.jl:16
Clear right answer.

*(A::Adjoint{<:Any, <:LayoutVector}, B::AbstractMatrix) in ArrayLayouts at /Users/x/.julia/packages/ArrayLayouts/nCtQC/src/mul.jl:151
*(u::Adjoint{T, <:AbstractVector} where T, v::Adjoint{<:Any, <:Transpose{T, <:AbstractVector} where T}) in LinearAlgebra at /Users/x/.julia/juliaup/julia-1.8.2+0.x64/share/julia/stdlib/v1.8/LinearAlgebra/src/adjtrans.jl:324
(2) I think this is the right choice, but not totally sure. It's kind of funny that the ambiguity is between a package and a method defined in a a stdlib explicitly intended to avoid ambiguity.

apply_recipe(plotattributes::AbstractDict{Symbol, Any}, x::AbstractVector, v::AbstractVector{OHLC}) in Plots at /Users/x/.julia/packages/RecipesBase/qpxEX/src/RecipesBase.jl:282
apply_recipe(plotattributes::AbstractDict{Symbol, Any}, f::Union{VecOrMat{F}, F}, x) where F<:Function in RecipesPipeline at /Users/x/.julia/packages/RecipesBase/qpxEX/src/RecipesBase.jl:282
These declarations are buried in a metaprogramming pipeline and I have no idea what they are.

frule(::RuleConfig, args...) in ChainRulesCore at /Users/x/.julia/packages/ChainRulesCore/Z4Jry/src/rules.jl:64
frule(::Any, ::typeof(sort), xs::AbstractVector; kw...) in ChainRules at /Users/x/.julia/packages/ChainRules/2ql0h/src/rulesets/Base/sort.jl:28
(4) Not sure, but I think this is the wrong choice answer, and I'm not sure if it is better or worse than an error.

*(A::Diagonal{<:Any, <:LayoutVector}, B::AbstractMatrix) in ArrayLayouts at /Users/x/.julia/packages/ArrayLayouts/nCtQC/src/ArrayLayouts.jl:206
*(A::Diagonal, B::Adjoint{<:Any, <:LinearAlgebra.AbstractRotation}) in LinearAlgebra at /Users/x/.julia/juliaup/julia-1.8.2+0.x64/share/julia/stdlib/v1.8/LinearAlgebra/src/givens.jl:407
Same as #2

ldiv!(A::QR{T, var"#s48", C} where {var"#s48"<:(SubArray{T, 2, BandedMatrix{T, C, R}, Tuple{I1, I2}} where {T, C, R, I1<:AbstractUnitRange, I2<:AbstractUnitRange}), C<:AbstractVector{T}}, B::AbstractVecOrMat{T}) where T in BandedMatrices at /Users/x/.julia/packages/BandedMatrices/swpf6/src/banded/bandedqr.jl:189
ldiv!(A::Factorization, x::UnitLowerTriangular{T, <:SubArray{T, 2, <:LayoutMatrix{T}}} where T) in ArrayLayouts at /Users/x/.julia/packages/ArrayLayouts/nCtQC/src/ldiv.jl:135
(6) Arbitrarily choosing one package over another

*(a::Adjoint{<:Any, <:Zeros{<:Any, 1}}, b::AbstractMatrix) in FillArrays at /Users/x/.julia/packages/FillArrays/Slipo/src/fillalgebra.jl:130
*(a::AbstractMatrix, b::Union{Adjoint{var"#s16", var"#s4"}, Transpose{var"#s16", var"#s4"}} where {var"#s16", var"#s4"<:(Zeros{<:Any, 1})}) in FillArrays at /Users/x/.julia/packages/FillArrays/Slipo/src/fillalgebra.jl:136
Perhaps this is an arbitrary choice when either would work?

(::ChainRulesCore.var"#frule##kw")(kws, ::typeof(frule), ::RuleConfig, args...) in ChainRulesCore at /Users/x/.julia/packages/ChainRulesCore/Z4Jry/src/rules.jl:77
(::ChainRulesCore.var"#frule##kw")(kwargs, frule::typeof(frule), ::Any, ::typeof(<=), var"373", var"374") in ChainRules
???

frule(::RuleConfig, args...) in ChainRulesCore at /Users/x/.julia/packages/ChainRulesCore/Z4Jry/src/rules.jl:64
frule(::Any, ::typeof(readuntil), var"1435"::IO, var"1436"::AbstractChar) in ChainRules at /Users/x/.julia/packages/ChainRules/2ql0h/src/rulesets/Base/nondiff.jl:361
(9) Same as #4

getindex(x::LArray, i...) in LabelledArrays at /Users/x/.julia/packages/LabelledArrays/IYs8M/src/larray.jl:75
getindex(A::AbstractArray, i::Int64, j::SymbolicUtils.Symbolic{<:Integer}) in Symbolics at /Users/x/.julia/packages/Symbolics/FGTCH/src/array-lib.jl:241
(10) Arbitrarily choosing one package over another, I suspect either choice will work.

ldiv!(S::LDLt{T, Symmetric{T, M}}, B::AbstractVecOrMat{T}) where {T, M<:(BandedMatrix{T})} in BandedMatrices at /Users/x/.julia/packages/BandedMatrices/swpf6/src/symbanded/ldlt.jl:47
ldiv!(A::Factorization, x::LowerTriangular{T, <:LayoutMatrix{T}} where T) in ArrayLayouts at /Users/x/.julia/packages/ArrayLayouts/nCtQC/src/ldiv.jl:135
Same as #6

rand(rng::Random.AbstractRNG, M::AbstractAlgebra.FPModule{T}, vals...) where T<:RingElement in AbstractAlgebra at /Users/x/.julia/packages/AbstractAlgebra/ZmWFo/src/Module.jl:302
rand(rng::Random.AbstractRNG, X, t::Type{<:BitArray}, dims::Tuple{Vararg{Int64, N}} where N) in RandomExtensions at /Users/x/.julia/packages/RandomExtensions/qAD6J/src/containers.jl:103
(12) I expect that this will replace an ambiguous method error with a more informative downstream error; and also never come up in practice

frule(::RuleConfig, args...) in ChainRulesCore at /Users/x/.julia/packages/ChainRulesCore/Z4Jry/src/rules.jl:64
frule(::Any, ::typeof(isprint), var"1142"::AbstractChar) in ChainRules at /Users/x/.julia/packages/ChainRules/2ql0h/src/rulesets/Base/nondiff.jl:261
Same as #4

frule(::RuleConfig, args...) in ChainRulesCore at /Users/x/.julia/packages/ChainRulesCore/Z4Jry/src/rules.jl:64
frule(::Any, ::typeof(fma), x::Number, y::Number, z::Number) in ChainRules at /Users/x/.julia/packages/ChainRules/2ql0h/src/rulesets/Base/base.jl:95
Duplicate of #9

*(a::AbstractThunk, b) in ChainRulesCore at /Users/x/.julia/packages/ChainRulesCore/Z4Jry/src/tangent_arithmetic.jl:125
*(α, r::RationalPoly) in MultivariatePolynomials at /Users/x/.julia/packages/MultivariatePolynomials/1bIGc/src/rational.jl:66
same as #10, but I'm optimistic this is the right choice

convert(::Type{PyAny}, x) in PyCall at /Users/x/.julia/packages/PyCall/ygXW2/src/conversions.jl:178
convert(::Type{T}, interval::Intervals.Interval{T}) where T in Intervals at /Users/x/.julia/packages/Intervals/wE73a/src/interval.jl:240
not sure what the right answer here is, convert(PyAny, ::Interval{PyAny}) is strange. I think this is a bit wrong but no worse than an error?

(::ChainRulesCore.var"#frule##kw")(kws, ::typeof(frule), ::RuleConfig, args...) in ChainRulesCore at /Users/x/.julia/packages/ChainRulesCore/Z4Jry/src/rules.jl:77
(::ChainRulesCore.var"#frule##kw")(kwargs, frule::typeof(frule), ::Any, ::typeof(diff), var"461"::AbstractArray{Bool}) in ChainRules
???

isapprox(p::AbstractPolynomialLike, α; kwargs...) in MultivariatePolynomials at /Users/x/.julia/packages/MultivariatePolynomials/1bIGc/src/operators.jl:210
isapprox(::Any, ::Missing; kwargs...) in Base at missing.jl:91
Wrong choice: changes ambiguity error to failed promotion error, the other choice would give a correct answer.

\(x::AbstractMatrix, A::UnitLowerTriangular{T, <:LayoutMatrix{T}} where T) in ArrayLayouts at /Users/x/.julia/packages/ArrayLayouts/nCtQC/src/ldiv.jl:143
\(F::Union{Adjoint{<:Any, <:Union{Cholesky{var"#s7269", var"#s7268"}, BunchKaufman{var"#s7269", var"#s7268"}, LQ{var"#s7269", var"#s7268", C} where C<:AbstractVector{var"#s7269"}, LU{var"#s7269", var"#s7268"}, QR{var"#s7269", var"#s7268", C} where C<:AbstractVector{var"#s7269"}, LinearAlgebra.QRCompactWY{var"#s7269", var"#s7268", C} where C<:AbstractMatrix{var"#s7269"}, QRPivoted{var"#s7269", var"#s7268", C} where C<:AbstractVector{var"#s7269"}, SVD{var"#s7269", var"#s885", var"#s7268", C} where {var"#s885"<:Real, C<:AbstractVector{var"#s885"}}} where {var"#s7269", var"#s7268"<:CuArray}}, Union{Cholesky{var"#s7273", var"#s7272"}, BunchKaufman{var"#s7273", var"#s7272"}, LQ{var"#s7273", var"#s7272", C} where C<:AbstractVector{var"#s7273"}, LU{var"#s7273", var"#s7272"}, QR{var"#s7273", var"#s7272", C} where C<:AbstractVector{var"#s7273"}, LinearAlgebra.QRCompactWY{var"#s7273", var"#s7272", C} where C<:AbstractMatrix{var"#s7273"}, QRPivoted{var"#s7273", var"#s7272", C} where C<:AbstractVector{var"#s7273"}, SVD{var"#s7273", var"#s885", var"#s7272", C} where {var"#s885"<:Real, C<:AbstractVector{var"#s885"}}} where {var"#s7273", var"#s7272"<:CuArray}}, B::AbstractVecOrMat) in CUDA.CUSOLVER at /Users/x/.julia/packages/CUDA/DfvRa/lib/cusolver/linalg.jl:40
Wow! Those are long types.

rand(rng::Random.AbstractRNG, S::MatAlgebra, v...) in AbstractAlgebra at /Users/x/.julia/packages/AbstractAlgebra/ZmWFo/src/MatrixAlgebra.jl:323
rand(rng::Random.AbstractRNG, X, t::Type{<:BitArray}, dims::Tuple{Vararg{Int64, N}} where N) in RandomExtensions at /Users/x/.julia/packages/RandomExtensions/qAD6J/src/containers.jl:103
Same as 12, I think.

[JeffBezanson]

I might be missing something but I think the example at the top is not ambiguous --- we should already resolve that in favor of SparseVector. Do you have an example? Of course your broader point stands.

[LilithHafner]

Thanks! Apparently, I don't understand the current method disambiguation procedures as well as I thought I did. I've replaced the example with one cherry-picked from the random sample.

[Seelengrab]

Related: #23740