Inference (?) hang on recursive methods

[timholy]

Here's what I suspect is a second example of the problem noted in #17137, but which can be easily replicated on master:

julia> I = (CartesianIndex{1}(2), 3, CartesianIndex{1}(3))
(CartesianIndex{1}((2,)),3,CartesianIndex{1}((3,)))

julia> _flatten(out) = out
_flatten (generic function with 1 method)

julia> _flatten(out, i, I...)        = _flatten((out..., i), I...)
_flatten (generic function with 2 methods)

julia> _flatten(out, i::CartesianIndex, I...) = _flatten((out..., i.I...), I...)
_flatten (generic function with 3 methods)

julia> _flatten((), I...)
^C^C^C^C^C^C^CWARNING: Force throwing a SIGINT
WARNING: An error occured during inference. Type inference is now partially disabled.
InterruptException()
unknown function (ip: 0x7f7341157bdf)
^C^C^C^C

All those Ctrl-Cs come from the fact that this call hangs, at least for minutes.

Interestingly, change i to i::Int in the second _flatten method, and it works fine.

Discovered in the course of trying to fix #17275.

[timholy]

Sadly, git bisect fingers ba2e389, which isn't relevant anymore (it's now 15). I'd also love to imagine that we don't rely on such limits for this case.

[vtjnash]

15 is still a very high number for the permitted branching factor, and is strongly dependent on one of our other unreliable heuristics actually kicking in fast enough.

[timholy]

But in this case there's only one branch that's relevant: if the 2nd argument isn't a CartesianIndex, there's only one relevant method.

[timholy]

I don't really understand the inference machinery well, but perhaps it's also worth pointing out that there are also only 3 indexes---naively, it doesn't seem that the tuple length limit is relevant.

[timholy]

As an experiment, I checked out julia-0.4 (before your inference rewrite), bumped MAX_TUPLETYPE_LEN up to 15, and tested this example. It also hangs. So it's not a recent problem, suggesting it may indeed be more fundamental than I was guessing.

[timholy]

Interestingly, this implementation:

_flatten() = ()
_flatten(i, I...)                 = (i, _flatten(I...)...)
_flatten(i::CartesianIndex, I...) = (i.I..., _flatten(I...)...)

has no problem on master. Cross-ref #17126.