Different type-widening for indirect vs. direct recursion

[martinholters]

This is good:

julia> f(x::Tuple{Any,Vararg}) = x[1] + f(x[2:end])
f (generic function with 1 method)

julia> f(x::Tuple{}) = 0
f (generic function with 2 methods)

julia> only(Base.return_types(f, Tuple{Tuple{Int,Int,Int,Int,Int,Int,Int}}))
Int64

However, when introducing a level of indirection, inference widens more aggressively when detecting the recursion and fails:

julia> g(x::Tuple{Any,Vararg}) = x[1] + _g(x[2:end])
g (generic function with 1 method)

julia> g(x::Tuple{}) = 0
g (generic function with 2 methods)

julia> _g(x) = g(x)
_g (generic function with 1 method)

julia> only(Base.return_types(g, Tuple{Tuple{Int,Int,Int,Int,Int,Int,Int}}))
Any

This is particularly unfortunate as this kind of indirection is implicitly introduced when adding kwargs:

julia> h(x::Tuple{Any,Vararg}; kwargs...) = x[1] + h(x[2:end]; kwargs...)
h (generic function with 1 method)

julia> h(x::Tuple{}; kwargs...) = 0
h (generic function with 2 methods)

julia> only(Base.return_types(h, Tuple{Tuple{Int,Int,Int,Int,Int,Int,Int}}))
Any

A manifestation of this effect is #45715.

We deliberately distinguish the cases of direct vs. indirect recursion:

julia/base/compiler/abstractinterpretation.jl

Lines 538 to 546 in cda99c8

	if method === sv.linfo.def
	# Under direct self-recursion, permit much greater use of reducers.
	# here we assume that complexity(specTypes) :>= complexity(sig)
	comparison = sv.linfo.specTypes
	l_comparison = length((unwrap_unionall(comparison)::DataType).parameters)
	spec_len = max(spec_len, l_comparison)
	else
	comparison = method.sig
	end

I'd argue that we shouldn't do this and instead, treat both cases equal. As a first trial balloon, I did

--- a/base/compiler/abstractinterpretation.jl
+++ b/base/compiler/abstractinterpretation.jl
@@ -542,7 +542,7 @@ function abstract_call_method(interp::AbstractInterpreter, method::Method, @nosp
             l_comparison = length((unwrap_unionall(comparison)::DataType).parameters)
             spec_len = max(spec_len, l_comparison)
         else
-            comparison = method.sig
+            comparison = topmost.linfo.specTypes
         end
 
         if isdefined(method, :recursion_relation)

That indeed lets above cases all be inferred as Int (and also fixes #45715). However, one @inferred test in the broadcast tests then fails. Although I didn't really know what I was doing there, I was not expecting this to worsen inference results, but maybe it's now triggering some other edge case? Anyway, feedback from @vtjnash on why these two cases are treated differently and whether it's a good idea to try to unify them would be welcome.

[schlichtanders]

Two of my packages also run into this issue. There are mainly of functional nature, where recursion is a typical tool.
It would be great if double recursion could be as good as single recursion

[schlichtanders]

Just tried to define recursion_relation here, and indeed it works 🙂
(first time I see that this workaround actually works - thank you for the convincing simple example)

Here the g exampleusing singlewhich` calls to grasp the method definitions

julia> g(x::Tuple{Any,Vararg}) = x[1] + _g(x[2:end])
g (generic function with 1 method)

julia> g(x::Tuple{}) = 0
g (generic function with 2 methods)

julia> _g(x) = g(x)
_g (generic function with 1 method)

julia> which(g, Tuple{Tuple{Any, Vararg}}).recursion_relation = (@nospecialize(_...)) -> true
#1 (generic function with 1 method)

julia> which(_g, Tuple{Any}).recursion_relation = (@nospecialize(_...)) -> true
#3 (generic function with 1 method)

julia> only(Base.return_types(g, Tuple{Tuple{Int,Int,Int,Int,Int,Int,Int}}))
Int64

Here the h example with kwfunction using methods to loop through all method definitions

julia> h(x::Tuple{Any,Vararg}; kwargs...) = x[1] + h(x[2:end]; kwargs...)
h (generic function with 1 method)

julia> h(x::Tuple{}; kwargs...) = 0
h (generic function with 2 methods)

julia> for m in methods(h)
           m.recursion_relation = (@nospecialize(_...)) -> true
       end

julia> for kwm in methods(Core.kwfunc(h))
           kwm.recursion_relation = (@nospecialize(_...)) -> true
       end
       
julia> only(Base.return_types(h, Tuple{Tuple{Int,Int,Int,Int,Int,Int,Int}}))
Int64

[vtjnash]

Manually mutating the fields of an internal object such as Method is undefined behavior, and should not be done too casually

[StefanKarpinski]

By "not done too casually" what is really meant is, it might work today, but it not guaranteed to continue working in the future, so do at the risk of having to add some ugly version checks to support a future version of Julia. Which is not the end of the world, but fair warning seems appropriate.

[vtjnash]

And also it might blow up the compiler in really weird unexpected and basically inexplicable ways, since you are deleting one of the initial assumptions that is required to show that compilation will eventually converge to a fixed point solution.

[StefanKarpinski]

Ok, that's substantially worse and probably not recommended even on a version of Julia that it happens to work on in some situations.

[schlichtanders]

a real pity... one of my packages relies heavily on recursion, where it is very natural to write with indirect recursion.

Are there any plans to improve type-inference for such indirect recursion for upcoming Julia version? Like in one year it is roughly planned to have this in julia? (I know, I could try fixing it myself, but it is already quite tough to find time for maintaining and improving my own Julia packages)

[vtjnash]

we may fix it, but the timeline of getting someone to implement and test it is unclear