gf: sort order is not transitive over subtyping (JuliaLang#36603)

We initially assume the sort over is transitive over subtyping, because it usually is, and that lets us partition the sort space. But then we need to do one extra comparison step at the end before checking for ambiguities.
caleb-allen · Jul 10, 2020 · 901f1e2 · 901f1e2
1 parent 1f8ace6
commit 901f1e2
Show file tree

Hide file tree

Showing 3 changed files with 88 additions and 27 deletions.
diff --git a/src/gf.c b/src/gf.c
@@ -2561,8 +2561,13 @@ static int ml_matches_visitor(jl_typemap_entry_t *ml, struct typemap_intersectio
 // This is the collect form of calling jl_typemap_intersection_visitor
 // with optimizations to skip fully shadowed methods.
 //
-// Returns a match as an array of svec(argtypes, static_params, Method).
+// Returns a match as an array of svec(argtypes, static_params, Method, fully-covers).
+//
 // See below for the meaning of lim.
+//
+// fully-covers is a Bool indicating subtyping, though temporarily it may be
+// tri-values, with `nothing` indicating a match that is not a subtype, but
+// which is dominated by one which is (and thus should be excluded unless ambiguous)
 static jl_value_t *ml_matches(jl_methtable_t *mt, int offs,
                               jl_tupletype_t *type, int lim, int include_ambiguous,
                               int intersections, size_t world, int cache_result,
@@ -2670,6 +2675,9 @@ static jl_value_t *ml_matches(jl_methtable_t *mt, int offs,
         }
         if (all_subtypes || !include_ambiguous) {
             //   - then find a candidate for the best of these method results
+            //     (If we have a reason to compute this. There's no point in
+            //     finding the minmax now, if we still need to examine all
+            //     methods for ambiguities later.)
             for (i = 0; i < len; i++) {
                 jl_svec_t *matc = (jl_svec_t*)jl_array_ptr_ref(env.t, i);
                 if (jl_svecref(matc, 3) == jl_true) {
@@ -2701,6 +2709,22 @@ static jl_value_t *ml_matches(jl_methtable_t *mt, int offs,
                     }
                 }
             }
+            //   - it may even dominate some choices that are not subtypes!
+            //     move those into the subtype group, where we're filter them out shortly after
+            if (!all_subtypes && minmax) {
+                jl_method_t *minmaxm = (jl_method_t*)jl_svecref(minmax, 2);
+                all_subtypes = 1;
+                for (i = 0; i < len; i++) {
+                    jl_svec_t *matc = (jl_svec_t*)jl_array_ptr_ref(env.t, i);
+                    if (jl_svecref(matc, 3) != jl_true) {
+                        jl_method_t *m = (jl_method_t*)jl_svecref(matc, 2);
+                        if (jl_type_morespecific((jl_value_t*)minmaxm->sig, (jl_value_t*)m->sig))
+                            jl_svecset(matc, 3, jl_nothing); // put a sentinel value here for sorting
+                        else
+                            all_subtypes = 0;
+                    }
+                }
+            }
             //    - now we might have a fast-return here, if we see that
             //      we've already processed all of the possible outputs
             if (all_subtypes) {
@@ -2728,28 +2752,59 @@ static jl_value_t *ml_matches(jl_methtable_t *mt, int offs,
         for (i = 1; i < len; i++) {
             env.matc = (jl_svec_t*)jl_array_ptr_ref(env.t, i);
             jl_method_t *m = (jl_method_t*)jl_svecref(env.matc, 2);
-            if (minmax != NULL && jl_svecref(env.matc, 3) == jl_true) {
+            int subt = jl_svecref(env.matc, 3) != jl_false;
+            if (minmax != NULL && subt) {
                 continue; // already the biggest
             }
             for (j = 0; j < i; j++) {
                 jl_value_t *matc2 = jl_array_ptr_ref(env.t, i - j - 1);
                 jl_method_t *m2 = (jl_method_t*)jl_svecref(matc2, 2);
-                if (jl_svecref(matc2, 3) != jl_true && jl_svecref(env.matc, 3) == jl_true)
+                int subt2 = jl_svecref(matc2, 3) != jl_false;
+                if (!subt2 && subt)
                     break;
-                if (jl_svecref(matc2, 3) == jl_svecref(env.matc, 3))
-                    if (!jl_type_morespecific((jl_value_t*)m->sig, (jl_value_t*)m2->sig))
-                        break;
+                if (subt == subt2)
+                    if (subt || !jl_has_empty_intersection(m->sig, m2->sig))
+                        if (!jl_type_morespecific((jl_value_t*)m->sig, (jl_value_t*)m2->sig))
+                            break;
                 jl_array_ptr_set(env.t, i - j, matc2);
             }
             jl_array_ptr_set(env.t, i - j, env.matc);
         }
+        // final step to finish sort:
+        // we stopped early with just having all non-subtypes before all
+        // subtypes, but the case on the boundary might be wrongly placed:
+        // check for that now
+        if (!minmax) {
+            for (i = 0; i < len; i++) {
+                jl_svec_t *matc = (jl_svec_t*)jl_array_ptr_ref(env.t, i);
+                if (jl_svecref(matc, 3) == jl_true)
+                    break;
+            }
+            for (; i > 0; i--) {
+                env.matc = (jl_svec_t*)jl_array_ptr_ref(env.t, i - 1);
+                jl_method_t *m = (jl_method_t*)jl_svecref(env.matc, 2);
+                for (j = i; j < len; j++) {
+                    jl_svec_t *matc2 = (jl_svec_t*)jl_array_ptr_ref(env.t, j);
+                    jl_method_t *m2 = (jl_method_t*)jl_svecref(matc2, 2);
+                    if (jl_svecref(matc2, 3) != jl_true)
+                        break;
+                    if (!jl_type_morespecific((jl_value_t*)m2->sig, (jl_value_t*)m->sig))
+                        break;
+                    jl_array_ptr_set(env.t, j - 1, matc2);
+                }
+                if (j == i)
+                    break;
+                jl_svecset(env.matc, 3, jl_nothing); // leave behind a sentinel value here for clarity
+                jl_array_ptr_set(env.t, j - 1, env.matc);
+            }
+        }
         char *skip = (char*)alloca(len);
         memset(skip, 0, len);
         // since we had a minmax method, now may now be able to cleanup some of our sort result
         if (minmax_ambig && !include_ambiguous) {
             for (i = 0; i < len; i++) {
                 jl_svec_t *matc = (jl_svec_t*)jl_array_ptr_ref(env.t, i);
-                if (jl_svecref(matc, 3) == jl_true) {
+                if (jl_svecref(matc, 3) != jl_false) {
                     skip[i] = 1;
                 }
             }
@@ -2758,7 +2813,7 @@ static jl_value_t *ml_matches(jl_methtable_t *mt, int offs,
             assert(all_subtypes || !include_ambiguous);
             for (i = 0; i < len; i++) {
                 jl_svec_t *matc = (jl_svec_t*)jl_array_ptr_ref(env.t, i);
-                if (minmax != matc && jl_svecref(matc, 3) == jl_true) {
+                if (minmax != matc && jl_svecref(matc, 3) != jl_false) {
                     skip[i] = 1;
                 }
             }
@@ -2784,7 +2839,7 @@ static jl_value_t *ml_matches(jl_methtable_t *mt, int offs,
                 if (skip[j - 1]) {
                     // if there was a minmax method, we can just pretend these are all in the same group
                     // they're all together but unsorted in the list, since we'll drop them all later anyways
-                    assert(subt2);
+                    assert(jl_svecref(matc2, 3) != jl_false);
                     disjoint = 0;
                     ambig_groupid[i] = j - 1; // ambiguity covering range [i:j)
                 }
@@ -2927,8 +2982,12 @@ static jl_value_t *ml_matches(jl_methtable_t *mt, int offs,
         // cleanup array to remove skipped entries
         for (i = 0, j = 0; i < len; i++) {
             jl_value_t *matc = jl_array_ptr_ref(env.t, i);
-            if (!skip[i])
+            if (!skip[i]) {
                 jl_array_ptr_set(env.t, j++, matc);
+                // remove our sentinel entry markers
+                if (jl_svecref(matc, 3) == jl_nothing)
+                    jl_svecset(matc, 3, jl_false);
+            }
         }
         if (j != len)
             jl_array_del_end((jl_array_t*)env.t, len - j);

diff --git a/test/ambiguous.jl b/test/ambiguous.jl
@@ -16,21 +16,6 @@ using LinearAlgebra, SparseArrays
 # For curmod_*
 include("testenv.jl")
 
-getline(m::Core.TypeMapEntry) = getline(m.func::Method)
-getline(m::Method) = m.line - lineoffset
-
-#ambigs = Any[[], [3], [2, 5], [], [3]]
-#for m in methods(ambig)
-#    ln = getline(m)
-#    atarget = ambigs[ln]
-#    if isempty(atarget)
-#        @test m.ambig === nothing
-#    else
-#        aln = Int[getline(a::Core.TypeMapEntry) for a in m.ambig]
-#        @test sort(aln) == atarget
-#    end
-#end
-
 @test length(methods(ambig)) == 5
 @test length(Base.methods_including_ambiguous(ambig, Tuple)) == 5
 
@@ -330,4 +315,21 @@ end
     @test Base.has_bottom_parameter(Ref{<:Union{}})
 end
 
+# test a case where specificity is not transitive over subtyping
+f35983(::T, ::T) where {T} = 1
+f35983(::Type, ::Type) = 2
+@test f35983(10, 12) == 1
+@test f35983(Int32, Int32) == 2
+@test f35983(Int32, Int64) == 2
+@test f35983(Int32, Complex) == 2
+@test only(Base.methods_including_ambiguous(f35983, (Type, Type))).sig == Tuple{typeof(f35983), Type, Type}
+@test only(Base.methods(f35983, (Type, Type))).sig == Tuple{typeof(f35983), Type, Type}
+@test length(Base.methods_including_ambiguous(f35983, (Any, Any))) == 2
+@test first(Base.methods_including_ambiguous(f35983, (Any, Any))).sig == Tuple{typeof(f35983), Type, Type}
+@test length(Base.methods(f35983, (Any, Any))) == 2
+@test first(Base.methods(f35983, (Any, Any))).sig == Tuple{typeof(f35983), Type, Type}
+f35983(::Type{Int16}, ::Any) = 3
+@test length(Base.methods_including_ambiguous(f35983, (Type, Type))) == 3
+@test length(Base.methods(f35983, (Type, Type))) == 2
+
 nothing # don't return a module from the remote include
diff --git a/test/errorshow.jl b/test/errorshow.jl
@@ -86,7 +86,7 @@ method_c2(x::Int32, y::Int32, z::Int32) = true
 method_c2(x::T, y::T, z::T) where {T<:Real} = true
 
 Base.show_method_candidates(buf, Base.MethodError(method_c2,(1., 1., 2)))
-@test String(take!(buf)) ==  "\nClosest candidates are:\n  method_c2(::T, ::T, !Matched::T) where T<:Real$cfile$(c2line+5)\n  method_c2(!Matched::Int32, ::Float64, ::Any...)$cfile$(c2line+2)\n  method_c2(!Matched::Int32, ::Any...)$cfile$(c2line+1)\n  ..."
+@test String(take!(buf)) ==  "\nClosest candidates are:\n  method_c2(!Matched::Int32, ::Float64, ::Any...)$cfile$(c2line+2)\n  method_c2(::T, ::T, !Matched::T) where T<:Real$cfile$(c2line+5)\n  method_c2(!Matched::Int32, ::Any...)$cfile$(c2line+1)\n  ..."
 
 c3line = @__LINE__() + 1
 method_c3(x::Float64, y::Float64) = true
@@ -124,7 +124,7 @@ PR16155line2 = @__LINE__() + 1
 (::Type{T})(arg::Any) where {T<:PR16155} = "replace call-to-convert method from sysimg"
 
 Base.show_method_candidates(buf, MethodError(PR16155,(1.0, 2.0, Int64(3))))
-@test String(take!(buf)) == "\nClosest candidates are:\n  $(curmod_prefix)PR16155(::Any, ::Any)$cfile$PR16155line\n  $(curmod_prefix)PR16155(!Matched::Int64, ::Any)$cfile$PR16155line\n  (::Type{T})(::Any) where T<:$(curmod_prefix)PR16155$cfile$PR16155line2"
+@test String(take!(buf)) == "\nClosest candidates are:\n  $(curmod_prefix)PR16155(::Any, ::Any)$cfile$PR16155line\n  (::Type{T})(::Any) where T<:$(curmod_prefix)PR16155$cfile$PR16155line2\n  $(curmod_prefix)PR16155(!Matched::Int64, ::Any)$cfile$PR16155line"
 
 Base.show_method_candidates(buf, MethodError(PR16155,(Int64(3), 2.0, Int64(3))))
 @test String(take!(buf)) == "\nClosest candidates are:\n  $(curmod_prefix)PR16155(::Int64, ::Any)$cfile$PR16155line\n  $(curmod_prefix)PR16155(::Any, ::Any)$cfile$PR16155line\n  (::Type{T})(::Any) where T<:$(curmod_prefix)PR16155$cfile$PR16155line2"