Inference regression on 1.7-RC2 and master (relative to 1.6.3)

[Sacha0]

@NHDaly (🙏) and I reduced the following out of a regression on Julia 1.7-RC2. Happily, on Julia 1.6.3:

               _
   _       _ _(_)_     |  Documentation: https://docs.julialang.org
  (_)     | (_) (_)    |
   _ _   _| |_  __ _   |  Type "?" for help, "]?" for Pkg help.
  | | | | | | |/ _` |  |
  | | |_| | | | (_| |  |  Version 1.6.3 (2021-09-23)
 _/ |\__'_|_|_|\__'_|  |
|__/                   |

julia> begin
           cat_storage_type(::Type{T}) where T = T
           cat_storage_type(::Type{T}) where {T<:Tuple} = Tuple{_cat_storage_type_tuple(T)...}

           _cat_storage_type_tuple(::Type{Tuple{}}) = ()
           function _cat_storage_type_tuple(::Type{T}) where {T<:Tuple}
               return (
                   cat_storage_type(fieldtype(T, 1)),
                   _cat_storage_type_tuple(Base.tuple_type_tail(T))...,
               )
           end
       end
_cat_storage_type_tuple (generic function with 2 methods)

julia> @code_warntype cat_storage_type(Tuple{NTuple{3, UInt8}})
Variables
  #self#::Core.Const(cat_storage_type)
  #unused#::Core.Const(Tuple{Tuple{UInt8, UInt8, UInt8}})

Body::Type{Tuple{Tuple{UInt8, UInt8, UInt8}}}
1 ─ %1 = Core.tuple(Main.Tuple)::Core.Const((Tuple,))
│   %2 = Main._cat_storage_type_tuple($(Expr(:static_parameter, 1)))::Core.Const((Tuple{UInt8, UInt8, UInt8},))
│   %3 = Core._apply_iterate(Base.iterate, Core.apply_type, %1, %2)::Core.Const(Tuple{Tuple{UInt8, UInt8, UInt8}})
└──      return %3

While on 1.7-RC2:

               _
   _       _ _(_)_     |  Documentation: https://docs.julialang.org
  (_)     | (_) (_)    |
   _ _   _| |_  __ _   |  Type "?" for help, "]?" for Pkg help.
  | | | | | | |/ _` |  |
  | | |_| | | | (_| |  |  Version 1.7.0-rc2 (2021-10-20)
 _/ |\__'_|_|_|\__'_|  |
|__/                   |

julia> begin
           cat_storage_type(::Type{T}) where T = T
           cat_storage_type(::Type{T}) where {T<:Tuple} = Tuple{_cat_storage_type_tuple(T)...}

           _cat_storage_type_tuple(::Type{Tuple{}}) = ()
           function _cat_storage_type_tuple(::Type{T}) where {T<:Tuple}
               return (
                   cat_storage_type(fieldtype(T, 1)),
                   _cat_storage_type_tuple(Base.tuple_type_tail(T))...,
               )
           end
       end
_cat_storage_type_tuple (generic function with 2 methods)

julia> @code_warntype cat_storage_type(Tuple{NTuple{3, UInt8}})
MethodInstance for cat_storage_type(::Type{Tuple{Tuple{UInt8, UInt8, UInt8}}})
  from cat_storage_type(::Type{T}) where T<:Tuple in Main at REPL[1]:3
Static Parameters
  T = Tuple{Tuple{UInt8, UInt8, UInt8}}
Arguments
  #self#::Core.Const(cat_storage_type)
  _::Core.Const(Tuple{Tuple{UInt8, UInt8, UInt8}})
Body::Type{<:Tuple}
1 ─ %1 = Core.tuple(Main.Tuple)::Core.Const((Tuple,))
│   %2 = Main._cat_storage_type_tuple($(Expr(:static_parameter, 1)))::Tuple{Type}
│   %3 = Core._apply_iterate(Base.iterate, Core.apply_type, %1, %2)::Type{<:Tuple}
└──      return %3

And on several day old master:

               _
   _       _ _(_)_     |  Documentation: https://docs.julialang.org
  (_)     | (_) (_)    |
   _ _   _| |_  __ _   |  Type "?" for help, "]?" for Pkg help.
  | | | | | | |/ _` |  |
  | | |_| | | | (_| |  |  Version 1.8.0-DEV.702 (2021-10-10)
 _/ |\__'_|_|_|\__'_|  |  master/82257229c9 (fork: 1 commits, 18 days)
|__/                   |

julia> begin
           cat_storage_type(::Type{T}) where T = T
           cat_storage_type(::Type{T}) where {T<:Tuple} = Tuple{_cat_storage_type_tuple(T)...}

           _cat_storage_type_tuple(::Type{Tuple{}}) = ()
           function _cat_storage_type_tuple(::Type{T}) where {T<:Tuple}
               return (
                   cat_storage_type(fieldtype(T, 1)),
                   _cat_storage_type_tuple(Base.tuple_type_tail(T))...,
               )
           end
       end
_cat_storage_type_tuple (generic function with 2 methods)

julia> @code_warntype cat_storage_type(Tuple{NTuple{3, UInt8}})
MethodInstance for cat_storage_type(::Type{Tuple{Tuple{UInt8, UInt8, UInt8}}})
  from cat_storage_type(::Type{T}) where T<:Tuple in Main at REPL[1]:3
Static Parameters
  T = Tuple{Tuple{UInt8, UInt8, UInt8}}
Arguments
  #self#::Core.Const(cat_storage_type)
  _::Core.Const(Tuple{Tuple{UInt8, UInt8, UInt8}})
Body::Type{<:Tuple}
1 ─ %1 = Core.tuple(Main.Tuple)::Core.Const((Tuple,))
│   %2 = Main._cat_storage_type_tuple($(Expr(:static_parameter, 1)))::Tuple{Type}
│   %3 = Core._apply_iterate(Base.iterate, Core.apply_type, %1, %2)::Type{<:Tuple}
└──      return %3

[Sacha0]

Tested on fresh master (c054dbc) just now, persists.

[Sacha0]

It might be worth noting that this (though naughty) works:

               _
   _       _ _(_)_     |  Documentation: https://docs.julialang.org
  (_)     | (_) (_)    |
   _ _   _| |_  __ _   |  Type "?" for help, "]?" for Pkg help.
  | | | | | | |/ _` |  |
  | | |_| | | | (_| |  |  Version 1.7.0-rc2 (2021-10-20)
 _/ |\__'_|_|_|\__'_|  |
|__/                   |

julia> begin
           cat_storage_type(::Type{T}) where T = T
           cat_storage_type(::Type{T}) where {T<:Tuple} = Tuple{_cat_storage_type_tuple(T)...}

           _cat_storage_type_tuple(::Type{Tuple{}}) = ()
           function _cat_storage_type_tuple(::Type{T}) where {T<:Tuple}
               Base.@_pure_meta
               return (
                   cat_storage_type(fieldtype(T, 1)),
                   _cat_storage_type_tuple(Base.tuple_type_tail(T))...,
               )
           end
       end
_cat_storage_type_tuple (generic function with 2 methods)

julia> @code_warntype cat_storage_type(Tuple{NTuple{3, UInt8}})
MethodInstance for cat_storage_type(::Type{Tuple{Tuple{UInt8, UInt8, UInt8}}})
  from cat_storage_type(::Type{T}) where T<:Tuple in Main at REPL[1]:3
Static Parameters
  T = Tuple{Tuple{UInt8, UInt8, UInt8}}
Arguments
  #self#::Core.Const(cat_storage_type)
  _::Core.Const(Tuple{Tuple{UInt8, UInt8, UInt8}})
Body::Type{Tuple{Tuple{UInt8, UInt8, UInt8}}}
1 ─ %1 = Core.tuple(Main.Tuple)::Core.Const((Tuple,))
│   %2 = Main._cat_storage_type_tuple($(Expr(:static_parameter, 1)))::Core.Const((Tuple{UInt8, UInt8, UInt8},))
│   %3 = Core._apply_iterate(Base.iterate, Core.apply_type, %1, %2)::Core.Const(Tuple{Tuple{UInt8, UInt8, UInt8}})
└──      return %3

[vtjnash]

It is perhaps worth noting that the internal tuple_type_tail function was deprecated and is not supported anymore (in favor of ntuple and fieldtype typically)

[KristofferC]

A bisect might be useful here.

[Sacha0]

It is perhaps worth noting that the internal tuple_type_tail function was deprecated and is not supported anymore (in favor of ntuple and fieldtype typically)

Thanks for letting me know! I was aware of tuple_type_head's deprecation to fieldtype(T, 1), but not of tuple_type_tail's deprecation. On master tuple_type_tail seems to still live in tuple.jl without a deprecation warning; perhaps we should move it to deprecated.jl etc? :)

[NHDaly]

For the deprecation, do you mean we should replace it with something like this?:

julia> T = NTuple{8, Int8}; Tuple(fieldtype(T,i) for i in 2:fieldcount(T))
(Int8, Int8, Int8, Int8, Int8, Int8, Int8)

Or if that's not what you mean, can you expand on what we should replace it with? Thanks

EDIT: oh, whoops, also this isn't even computing the same thing, so ignore this.

[vtjnash]

Usually now we try to avoid forming the tuple of types, by using ntuple(...) on the values, or another existing call such as convert

[Sacha0]

A bisect might be useful here.

Kicked one off 🍿, will report back.

[Sacha0]

Bisect points to

commit c2ec70cd1842b53f45ac72ea74c94f008adbc7b3
Author: Jameson Nash <vtjnash@gmail.com>
Date:   Thu Apr 8 23:10:57 2021 -0400

    inference: limit single-level nested `Type` signature (#40379)

    Previously `type_more_complex` returns `false` for `Type{Type{...}}`
    compared against `Type{...}`. Per comment there, this should return `true`,
    but the code was ordered incorrect (it was also missing support for
    Vararg, after the recent changes).

    Fixes #40336

    Co-authored-by: Shuhei Kadowaki <aviatesk@gmail.com>

[ChenNingCong]

Cross ref: #42835 and my comment on 42835 issue at discourse

It seems this is also caused by type_more_complex function and Type. And if you change inference order, type inference succeeds. I test following code in Julia 1.8-DEV (in a fresh session), where type inference of cat_storage_type(Tuple{NTuple{3, UInt8}}) also fails.

@code_warntype cat_storage_type(Tuple{NTuple{1, UInt8}}) 
@code_warntype cat_storage_type(Tuple{NTuple{2, UInt8}})
@code_warntype cat_storage_type(Tuple{NTuple{3, UInt8}})

Then we get:

MethodInstance for cat_storage_type(::Type{Tuple{Tuple{UInt8, UInt8, UInt8}}})
  from cat_storage_type(::Type{T}) where T<:Tuple in Main at /home/chenningcong/Documents/Code/juliaCode/TypeInferenceDebugger/src/debugger.jl:244
Static Parameters
  T = Tuple{Tuple{UInt8, UInt8, UInt8}}
Arguments
  #self#::Const(cat_storage_type)
  _::Const(Tuple{Tuple{UInt8, UInt8, UInt8}})
Body::Type{Tuple{Tuple{UInt8, UInt8, UInt8}}}
1 ─ %1 = Core.tuple(Main.Tuple)::Const((Tuple,))
│   %2 = Main._cat_storage_type_tuple($(Expr(:static_parameter, 1)))::Const((Tuple{UInt8, UInt8, UInt8},))
│   %3 = Core._apply_iterate(Base.iterate, Core.apply_type, %1, %2)::Const(Tuple{Tuple{UInt8, UInt8, UInt8}})
└──      return %3

With this strategy you can infer arbitrarily large tuple, the following code infers @code_warntype cat_storage_type(Tuple{NTuple{10, UInt8}}):

for i in 1:10
  @code_warntype cat_storage_type(Tuple{NTuple{i, UInt8}})
end

But if you skip over some number (>=3) then inference fails:

for i in 1:5
  @code_warntype cat_storage_type(Tuple{NTuple{i, UInt8}})
end
@code_warntype cat_storage_type(Tuple{NTuple{7, UInt8}})

Contrasted to In Julia 1.6.1, the inference of arbitrarily large tuple succeeds in any order of evaluation.

I guess the patch that @Sacha0 quotes strengthens recursion detection and causes Julia stops to make progress with N=3, even type inference actually won't get into infinite loop. So maybe fixing type_more_complex can also fix #42835

[NHDaly]

I don't exactly see how the case that @Sacha0 posted in the OP on this issue should be affected by the change that #40379 (pointed to by bisect) was meant to make.

It seems that #40379 was trying to fix #40336, where inference itself could get stuck in a loop because it wasn't detecting that Type{Type{T}} was more complex than Type{T}.

But the code in @Sacha0's original post doesn't seem to ever introduce Type{...} wrappers, so I guess it shouldn't be affected?

Do you think that PR accidentally now catches other patterns as being an increase in complexity that it didn't mean to?