Regression in nightly: dispatch depends on order runtime calls, not signatures

[odow]

JuMP/MathOptInterface is failing tests on nightly because of this regression.

Here's the latest nightly:

(base) oscar@Oscars-MBP ~ % /Applications/Julia-1.10.app/Contents/Resources/julia/bin/julia
               _
   _       _ _(_)_     |  Documentation: https://docs.julialang.org
  (_)     | (_) (_)    |
   _ _   _| |_  __ _   |  Type "?" for help, "]?" for Pkg help.
  | | | | | | |/ _` |  |
  | | |_| | | | (_| |  |  Version 1.10.0-DEV.1151 (2023-04-29)
 _/ |\__'_|_|_|\__'_|  |  Commit b4d15302517 (1 day old master)
|__/                   |

julia> struct Foo{T} end

julia> f = Foo{Int}()
Foo{Int64}()

julia> foo(::Type, ::Any) = nothing
foo (generic function with 1 method)

julia> foo(::Type{T}, f::T) where {T} = f
foo (generic function with 2 methods)

julia> foo(Foo{Int}, f)
Foo{Int64}()

julia> foo(Foo, f)         # <-- calls foo(::Type{T}, ::T)
Foo{Int64}()

julia> foo(Foo{String}, f)

julia> foo(Foo, f)         # <-- calls foo(::Type, ::Any)

The second call to foo(Foo, f) returns nothing instead of the desired Foo{Int64}().

Compare to v1.6.7

(base) oscar@Oscars-MBP MathOptInterface % julia
               _
   _       _ _(_)_     |  Documentation: https://docs.julialang.org
  (_)     | (_) (_)    |
   _ _   _| |_  __ _   |  Type "?" for help, "]?" for Pkg help.
  | | | | | | |/ _` |  |
  | | |_| | | | (_| |  |  Version 1.6.7 (2022-07-19)
 _/ |\__'_|_|_|\__'_|  |  Official https://julialang.org/ release
|__/                   |

julia> struct Foo{T} end

julia> f = Foo{Int}()
Foo{Int64}()

julia> foo(::Type, ::Any) = nothing
foo (generic function with 1 method)

julia> foo(::Type{T}, f::T) where {T} = f
foo (generic function with 2 methods)

julia> foo(Foo{Int}, f)
Foo{Int64}()

julia> foo(Foo, f)         # <-- calls foo(::Type{T}, ::T)
Foo{Int64}()

julia> foo(Foo{String}, f)

julia> foo(Foo, f)         # <-- calls foo(::Type{T}, ::T)
Foo{Int64}()

x-ref: jump-dev/MathOptInterface.jl#2159

I haven't tried bisecting. But based on our CI logs: https://github.com/jump-dev/MathOptInterface.jl/commits/master

Known good commit:

Julia Version 1.10.0-DEV.1069
Commit dcdac1e895f (2023-04-20 05:36 UTC)

Known bad commit:

Julia Version 1.10.0-DEV.1109
Commit c70e0fa552d (2023-04-24 22:47 UTC)

Diff dcdac1e...c70e0fa

[odow]

Culprit is c237c0a #49393

d8fb5e7...c237c0a

(base) oscar@Oscars-MBP ~ % /Applications/Julia-1.10.app/Contents/Resources/julia/bin/julia
               _
   _       _ _(_)_     |  Documentation: https://docs.julialang.org
  (_)     | (_) (_)    |
   _ _   _| |_  __ _   |  Type "?" for help, "]?" for Pkg help.
  | | | | | | |/ _` |  |
  | | |_| | | | (_| |  |  Version 1.10.0-DEV.1077 (2023-04-20)
 _/ |\__'_|_|_|\__'_|  |  Commit d8fb5e7bd92 (10 days old master)
|__/                   |

julia> struct Foo{T} end

julia> f = Foo{Int}()
Foo{Int64}()

julia> foo(::Type, ::Any) = nothing
foo (generic function with 1 method)

julia> foo(::Type{T}, f::T) where {T} = f
foo (generic function with 2 methods)

julia> foo(Foo{Int}, f)
Foo{Int64}()

julia> foo(Foo, f)
Foo{Int64}()

julia> foo(Foo{String}, f)

julia> foo(Foo, f)
Foo{Int64}()

(base) oscar@Oscars-MBP ~ % /Applications/Julia-1.10.app/Contents/Resources/julia/bin/julia
               _
   _       _ _(_)_     |  Documentation: https://docs.julialang.org
  (_)     | (_) (_)    |
   _ _   _| |_  __ _   |  Type "?" for help, "]?" for Pkg help.
  | | | | | | |/ _` |  |
  | | |_| | | | (_| |  |  Version 1.10.0-DEV.1078 (2023-04-20)
 _/ |\__'_|_|_|\__'_|  |  Commit c237c0ad0aa (10 days old master)
|__/                   |

julia> struct Foo{T} end

julia> f = Foo{Int}()
Foo{Int64}()

julia> foo(::Type, ::Any) = nothing
foo (generic function with 1 method)

julia> foo(::Type{T}, f::T) where {T} = f
foo (generic function with 2 methods)

julia> foo(Foo{Int}, f)
Foo{Int64}()

julia> foo(Foo, f)
Foo{Int64}()

julia> foo(Foo{String}, f)

julia> foo(Foo, f)

[odow]

cc @vtjnash since you authored #49393.

We can work-around this in JuMP by introducing a new method foo(::Type{Foo}, ::Foo):

julia> struct Foo{T} end

julia> f = Foo{Int}()
Foo{Int64}()

julia> foo(::Type, ::Any) = nothing
foo (generic function with 4 methods)

julia> foo(::Type{T}, f::T) where {T} = f
foo (generic function with 4 methods)

julia> foo(::Type{Foo}, ::Foo) = "new method"
foo (generic function with 4 methods)

julia> foo(Foo{Int}, f)
Foo{Int64}()

julia> foo(Foo, f)
"new method"

julia> foo(Foo{String}, f)

julia> foo(Foo, f)
"new method"

[vtjnash]

Ah, you have found a type-intersection mistake. The T mistakenly has been getting assigned as <:Foo{Int64} instead of the correct bound, which is >:Foo{Int64}. (checking at least as far back as v1.0)

MWE

julia> A = Tuple{Type,Some{Int}};

julia> B = Tuple{Type{T}, T} where T;

julia> C = Tuple{Type{Some}, Some{Int}};

julia> C<:A, C<:B
(true, true)

julia> I = typeintersect(Tuple{Type, Some{Int}}, Tuple{Type{T}, T} where T)
Tuple{Type{T}, T} where T<: Some{Int64} # before PR
Tuple{Type{Some{Int64}}, Some{Int64}} # after PR

julia> C <: I
false

[vtjnash]

Note that the true optimal intersection of this is (in my guesstimate):

julia> I2 = Tuple{Type{S}, Some{Int}} where S>:Some{Int};

julia> I2<:A, I2<:B, C<:I2
(true, true, true)

Since there is an upper bound on the covariant use, but not on the invariant usage.

[odow]

This only impacted one method in all of JuMP and MathOptInterface, so I assume it's pretty rare in the wild.

And so arguably I could/should have used this method in JuMP:

foo(::Type{>:T}, f::T) where {T} = f

(base) oscar@Oscars-MBP ~ % /Applications/Julia-1.10.app/Contents/Resources/julia/bin/julia ; exit;
               _
   _       _ _(_)_     |  Documentation: https://docs.julialang.org
  (_)     | (_) (_)    |
   _ _   _| |_  __ _   |  Type "?" for help, "]?" for Pkg help.
  | | | | | | |/ _` |  |
  | | |_| | | | (_| |  |  Version 1.10.0-DEV.1151 (2023-04-29)
 _/ |\__'_|_|_|\__'_|  |  Commit b4d15302517 (1 day old master)
|__/                   |

julia> struct Foo{T} end

julia> f = Foo{Int}()
Foo{Int64}()

julia> foo(::Type, ::Any) = nothing
foo (generic function with 1 method)

julia> foo(::Type{>:T}, f::T) where {T} = f
foo (generic function with 2 methods)

julia> foo(Foo{Int}, f)
Foo{Int64}()

julia> foo(Foo, f)
Foo{Int64}()

julia> foo(Foo{String}, f)

julia> foo(Foo, f)
Foo{Int64}()

[vtjnash]

Yeah, that is the transform that intersection should make here.

Looking even closer at this, the general form of the result needs another TypeVar introduced to separate out each covariant use from the invariant uses (separate variables for each use preserves the diagonal rule, while accumulating the Union of these variables as the lower bound for T). So the intermediate intersection should look like this (later passes may simplify it):

julia> Tuple{Type{T}, S} where T>:S where S<:Some{Int}

I think this may simplify vb.constraintkind, if we can inject something similar to 508992c for this case, taking some inspiration from @N5N3's recent commit.

[vtjnash]

This only breaks twice as many tests as it fixes, many for simple reasons (lack of canonicalization afterwards), so I think this may be a step in the right direction:

diff --git a/src/subtype.c b/src/subtype.c
index 83b8a84133..e24e7efdd7 100644
--- a/src/subtype.c
+++ b/src/subtype.c
@@ -2651,7 +2651,22 @@ static jl_value_t *intersect_var(jl_tvar_t *b, jl_value_t *a, jl_stenv_t *e, int
             return ub;
         else if (jl_egal(bb->ub, bb->lb))
             return ub;
-        set_bound(&bb->ub, ub, b, e);
+        if (is_leaf_bound(ub)) {
+            set_bound(&bb->lb, ub, b, e);
+            return ub;
+        }
+        else {
+            jl_value_t *ntv = NULL;
+            JL_GC_PUSH2(&ntv, &ub);
+            if (bb->innervars == NULL)
+                bb->innervars = jl_alloc_array_1d(jl_array_any_type, 0);
+            ntv = (jl_value_t*)jl_new_typevar(b->name, bb->lb, ub);
+            jl_array_ptr_1d_push(bb->innervars, ntv);
+            jl_value_t *lb = simple_join(b->lb, ntv);
+            JL_GC_POP();
+            bb->lb = lb;
+            return ntv;
+        }
     }
     return (jl_value_t*)b;
 }