Regression in inference with recursive methods

[pablosanjose]

(Ref: https://discourse.julialang.org/t/regression-in-v0-7-due-to-weird-inference-failure-for-function-with-lisp-y-recursion/9342)

For some reason the following code drives inference a bit crazy

struct A{E, L}
end

struct B{E, L}
end

struct C{E, L}
end

foo(::Type{T}, t, ts...) where {T} = foo(foo(T, t), ts...)
foo(::Type{A{E, L}}, ::B{E2,L2}) where {E,E2,L,L2} = A{E2,L}
foo(::Type{A{E, L}}, ::C{E2,L2}) where {E,E2,L,L2} = A{E2,L2}

If we call foo specifically in the following way, inference fails, and execution is slow (this can also be seen as a non-leaf inferred type of foo using @code_warntype)

julia> b, c = B{Float64,2}(), C{Float64,2}();
julia> @btime foo(A{Float64,0}, $b, $c, $b, $b)
  258.510 ns (2 allocations: 32 bytes)
A{Float64,2}

The failure depends on the number and combination of cs and bs.
However, if we slightly change the last method definition to

foo(::Type{A{E, L}}, ::C{E2,L2}) where {E,E2,L,L2} = A{E2,L}

inference recovers, and everything is elided

julia> @btime foo(A{Float64,0}, $b, $c, $b, $b)
  0.023 ns (0 allocations: 0 bytes)
A{Float64,0}

The problem occurs in current master, but did not happen approximately one month ago (I didn't manage to find the precise commit, I'll keep trying [EDIT: I've gone back 4 months, and the problem was already there]). It also doesn't happen in v0.6.1. [EDIT: Neither in v0.6.2]

julia> versioninfo()
Julia Version 0.7.0-DEV.4390
Commit 79c7bdd9ec (2018-02-26 07:59 UTC)
Platform Info:
  OS: macOS (x86_64-apple-darwin17.4.0)
  CPU: Intel(R) Core(TM) i7-5775R CPU @ 3.30GHz
  WORD_SIZE: 64
  LIBM: libopenlibm
  LLVM: libLLVM-3.9.1 (ORCJIT, broadwell)
Environment:

[pablosanjose]

I bisected the problem to commit fcfe875
This is rather old, part of PR #21933 (CC @vtjnash)
Perhaps related to TUPLE_COMPLEXITY_LIMIT_DEPTH = 3? [I really have no clue!]

[vtjnash]

foo(foo...) is not generally terminating, so it is not inferred (unless #21933 can detect some other reason that it is terminating). This is per design, to permit inter-proceedural constant-propagation.

[pablosanjose]

Many thanks for the clarification Jameson, it makes sense. Just in case there is still some room for improvement here, I posted more info in the original discourse thread showing that the simple change ts... -> ts::Vararg{<:Any,N} in the example (and arbitrary extensions AFAICT) makes a huge difference. It doesn't make things type-stable, but performance is restored, to the point it doesn't matter any more. Is it possible there is a low-hanging optimization for Vararg lowering here, perhaps?