suboptimal typeintersections for degenerate TypeVars

[nsajko]

julia> examples = NTuple{2,UnionAll}[
         (Tuple{T, T} where T, Tuple{X, X, Vararg{Any}} where Int<:X<:Real),
         (Tuple{T, T} where T, Tuple{X, X, Vararg{X}} where Int<:X<:Real),
         (Tuple{T, T} where T<:Integer, Tuple{Vararg{X}} where X>:Int),
         (Tuple{T, T} where T<:Integer, Tuple{X, Vararg{X}} where X>:Int),
         (Tuple{T, T} where T<:Integer, Tuple{X, X, Vararg{Any}} where Int<:X<:Real),
         (Tuple{T, T} where T<:Integer, Tuple{X, X, Vararg{Real}} where X>:Int),
         (Tuple{T, T} where T<:Integer, Tuple{X, X, Vararg{X}} where X>:Int),
         (Tuple{Vararg{X}} where X, Tuple{Any, Vararg{X}} where X),
         (Tuple{X, X} where Int<:X<:Real, Tuple{T, T} where T<:Integer),
         (Tuple{X, X} where X, Tuple{Vararg{X}} where X>:Int),
         (Tuple{X, X} where X>:Int, Tuple{T, T} where T<:Integer),
         (Tuple{X, X} where X>:Int, Tuple{Vararg{X}} where X<:Real),
       ]
12-element Vector{Tuple{UnionAll, UnionAll}}:
 (Tuple{T, T} where T, Tuple{X, X, Vararg{Any}} where Int64<:X<:Real)
 (Tuple{T, T} where T, Tuple{X, X, Vararg{X}} where Int64<:X<:Real)
 (Tuple{T, T} where T<:Integer, Tuple{Vararg{X}} where X>:Int64)
 (Tuple{T, T} where T<:Integer, Tuple{X, Vararg{X}} where X>:Int64)
 (Tuple{T, T} where T<:Integer, Tuple{X, X, Vararg{Any}} where Int64<:X<:Real)
 (Tuple{T, T} where T<:Integer, Tuple{X, X, Vararg{Real}} where X>:Int64)
 (Tuple{T, T} where T<:Integer, Tuple{X, X, Vararg{X}} where X>:Int64)
 (Tuple{Vararg{X}} where X, Tuple{Any, Vararg{X}} where X)
 (Tuple{X, X} where Int64<:X<:Real, Tuple{T, T} where T<:Integer)
 (Tuple{X, X} where X, Tuple{Vararg{X}} where X>:Int64)
 (Tuple{X, X} where X>:Int64, Tuple{T, T} where T<:Integer)
 (Tuple{X, X} where X>:Int64, Tuple{Vararg{X}} where X<:Real)

julia> expected_property(S, T) = typeintersect(S, T) == typeintersect(T, S)
expected_property (generic function with 1 method)

julia> expected_property(ST) = expected_property(ST...)
expected_property (generic function with 2 methods)

julia> println(expected_property.(examples))
Bool[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]

julia> versioninfo()
Julia Version 1.11.0-DEV.1382
Commit 5cf10211fe9 (2024-01-26 02:37 UTC)
Build Info:
  Official https://julialang.org/ release
Platform Info:
  OS: Linux (x86_64-linux-gnu)
  CPU: 8 × AMD Ryzen 3 5300U with Radeon Graphics
  WORD_SIZE: 64
  LLVM: libLLVM-16.0.6 (ORCJIT, znver2)
Threads: 1 default, 0 interactive, 1 GC (on 8 virtual cores)

More examples:
intersection_commutativity_counterexamples.txt

[N5N3]

This is not a correctness bug.
As the doc says, typeintersect compute a type that contains the intersection of inputs.
We hope the result to be the smallest set but that's not true in many cases.
The algorithm is allowed to over-estimate when needed.

[nsajko]

Is it not possible to guarantee commutativity? It really seems like an essential property for an "intersection" operation.

Anyway, I stumbled upon this while trying to expand the "menagerie" of types used in the subtype test set, where commutativity of intersection is tested:

julia/test/subtype.jl

Lines 1089 to 1092 in 5d4d6ab

	S = menagerie[j]
	I = _type_intersect(T,S)
	I2 = _type_intersect(S,T)
	@test isequal_type(I, I2)

[N5N3]

Is it not possible to guarantee commutativity?

Commutativity doesn't quite make sense considering over-estimation.
At present the algorithm would widen the result to the 2nd input (usually the method signature) if it thinks the union complexity is too big.
But for simple input, we usually give the smallest result thus keeps commutativity.

[nsajko]

After taking a quick look at the JuliaHub symbol search, I don't think many are aware of the lack of commutativity of typeintersect.

The noncommutativity should be pointed out in the typeintersect doc string. In particular, people currently do this to check whether a type intersection subtypes some third type: typeintersect(A, B) <: C. But, given that typeintersect isn't commutative, that code should presumably be replaced with (typeintersect(A, B) <: C) || (typeintersect(B, A) <: C), and we could give that example in the doc string. What do you think? EDIT: opened a relevant Discourse thread: https://discourse.julialang.org/t/fr-provide-a-predicate-to-check-whether-a-type-intersection-subtypes-some-type/109303

[vtjnash]

(typeintersect(A, B) <: C) || (typeintersect(B, A) <: C)

This is also incorrect. What packages are trying to use this pattern?

[vtjnash]

We have a menagerie of other cases which may be similar and were noticed to be suboptimal (such that C<:A && C<:B does not hold), such as #36951

[nsajko]

What packages are trying to use this pattern?

No packages use that patter. I'm just saying it would be an improvement over the established typeintersect(A, B) <: C pattern.

[vtjnash]

What packages use that pattern? They possibly should not use it, although there are certain circumstances where it is correct (e.g. methods and isambiguous use that pattern quite heavily)

[nsajko]

Here are some cases where there's room for making typeintersect more accurate by computing both directional intersections, instead of just one, and then checking for subtyping between them:

julia> function test_property(a, b)
           ab = typeintersect(a, b)::Type
           ba = typeintersect(b, a)::Type
           (ab != ba && (ab <: ba || ba <: ab))::Bool
       end
test_property (generic function with 1 method)

julia> test_property(t) = test_property(t...)
test_property (generic function with 2 methods)

julia> examples = NTuple{2, Type}[
         (Tuple{T, T} where T<:Integer, Tuple{X, X} where Int<:X<:Real),
         (Tuple{T, T} where T<:Integer, Tuple{X, X} where X>:Int),
         (Tuple{X, X} where X<:Real, Tuple{X, X} where X>:Int),
         (Tuple{Vararg{X}} where X, Tuple{Any, Vararg{X}} where X),
         (Tuple{Vararg{X}} where X, Tuple{X, X, Vararg{Any}} where X),
       ];

julia> println(test_property.(examples))
Bool[1, 1, 1, 1, 1]

More: examples.jl.txt

[vtjnash]

Those seem to be just examples of equal types. In particular, when the types are equal, the type system has no opinion on which one is "better", and returns the first one.

julia> ==(Tuple{Any}, Tuple{X} where X)
true

julia> ==(Tuple, Tuple{Vararg{X}} where X>:Real)
true

[nsajko]

OK, I edited the previous message, leaving only the examples where the two type intersections aren't equal.

[nsajko]

What packages use that pattern?

Actually, when considering only packages with a significant dependent package count, I think only JSON.jl does that:

https://github.com/JuliaIO/JSON.jl/blob/46579b75938bf5cd2079907499cb8afd8eef7599/src/Parser.jl#L412-L415

[vtjnash]

Ah, that is very different if the third type C in the comparison is Union{}