"Recursive template instantiation exceeded maximum depth" for innocent-looking code.

[Quuxplusone]

Bugzilla Link	PR44650
Status	NEW
Importance	P normal
Reported by	Mikhail Kremniov (officesamurai@gmail.com)
Reported on	2020-01-24 04:19:20 -0800
Last modified on	2020-01-27 13:48:34 -0800
Version	9.0
Hardware	PC Linux
CC	blitzrakete@gmail.com, dblaikie@gmail.com, dgregor@apple.com, eric@efcs.ca, erik.pilkington@gmail.com, llvm-bugs@lists.llvm.org, mclow.lists@gmail.com, richard-llvm@metafoo.co.uk, zilla@kayari.org
Fixed by commit(s)
Attachments	test_alpine1.cpp (231 bytes, text/x-c++src) test_alpine2.cpp (230 bytes, text/x-c++src) test_anywhere.cpp (616 bytes, text/x-c++src) test_alpine1.cpp.i (562369 bytes, text/plain) test_alpine2.cpp.i (562368 bytes, text/plain) test_anywhere.cpp.i (63583 bytes, text/plain)
Blocks
Blocked by
See also

Created attachment 23050
The original test case

I've got this problem on Alpine Linux originally.
<<<
# cat /etc/os-release
NAME="Alpine Linux"
ID=alpine
VERSION_ID=3.11.2
PRETTY_NAME="Alpine Linux v3.11"
HOME_URL="https://alpinelinux.org/"
BUG_REPORT_URL="https://bugs.alpinelinux.org/"

# clang -v
Alpine clang version 9.0.0 (https://git.alpinelinux.org/aports
f7f0d2c2b8bcd6a5843401a9a702029556492689) (based on LLVM 9.0.0)
Target: x86_64-alpine-linux-musl
Thread model: posix
InstalledDir: /usr/bin
Found candidate GCC installation: /usr/bin/../lib/gcc/x86_64-alpine-linux-
musl/9.2.0
Found candidate GCC installation: /usr/lib/gcc/x86_64-alpine-linux-musl/9.2.0
Selected GCC installation: /usr/bin/../lib/gcc/x86_64-alpine-linux-musl/9.2.0
Candidate multilib: .;@m64
Selected multilib: .;@m64

# clang++ -c test_alpine1.cpp
In file included from test_alpine1.cpp:1:
In file included from /usr/bin/../lib/gcc/x86_64-alpine-linux-
musl/9.2.0/../../../../include/c++/9.2.0/functional:58:
/usr/bin/../lib/gcc/x86_64-alpine-linux-
musl/9.2.0/../../../../include/c++/9.2.0/bits/refwrap.h:303:46: fatal error:
recursive template instantiation exceeded maximum depth of 1024
      template<typename _Up, typename _Up2 = __remove_cvref_t<_Up>>
...
>>>

test_alpine1.cpp:
<<<
#include <functional>

using function = std::function<void()>;

struct S
{
    S(std::reference_wrapper<function>)
    {
    }

    void operator()() const
    {
    }
};

auto test()
{
    function f;
    return S(std::ref(f));
}
>>>

The interesting thing here is that if I remove S::operator(), the compilation
succeeds.

P.S. I've tried to minimize it further by replacing std::function with a
trivial struct and in the resulting code the operator() is no longer needed to
reproduce the error (see test_alpine2.cpp).

P.S.2 I've also tried to get rid of things specific to the stdlib used on
Alpine and got test_anywhere.cpp, which fails to compile with the same error on
other systems as well. Namely, I've tried it on LinuxMint 17.3 where I have
more versions of Clang installed and it fails virtually for all of them (4.x -
9.x).

P.S.3 GCC is able to compile all of the files.

[Quuxplusone]

Attached test_alpine1.cpp (231 bytes, text/x-c++src): The original test case

[Quuxplusone]

Attached test_alpine2.cpp (230 bytes, text/x-c++src): A slightly minimized test case

[Quuxplusone]

Attached test_anywhere.cpp (616 bytes, text/x-c++src): The minimal test case

[Quuxplusone]

Attached test_alpine1.cpp.i (562369 bytes, text/plain): Preprocessed source

[Quuxplusone]

Attached test_alpine2.cpp.i (562368 bytes, text/plain): Preprocessed source for test_alpine2.cpp

[Quuxplusone]

Attached test_anywhere.cpp.i (63583 bytes, text/plain): Preprocessed source for test_anywhere.cpp

[Quuxplusone]

The standard library under test is libstdc++. Re-binning back to Clang.

[Quuxplusone]

Please can you provide the complete compiler output, or at least enough to show the (presumably) repeating cycle in template instantiation?

I suspect this is to be a bug in libstdc++, due to some kind of dependency cycle in this particular overload resolution that libstdc++ is not guarding against. GCC happens to skip some steps in overload resolution that Clang does not skip (GCC's behavior is permitted by http://eel.is/c++draft/temp#inst-8.sentence-1 but certainly not required), so it may sometimes mask this kind of problem; the fact that GCC accepts does not necessarily imply a bug in either compiler.

[Quuxplusone]

Here is the output for the first file on Alpine
===========================================
# clang++ -c test_alpine1.cpp
In file included from test_alpine1.cpp:1:
In file included from /usr/bin/../lib/gcc/x86_64-alpine-linux-
musl/9.2.0/../../../../include/c++/9.2.0/functional:58:
/usr/bin/../lib/gcc/x86_64-alpine-linux-
musl/9.2.0/../../../../include/c++/9.2.0/bits/refwrap.h:303:46: fatal error:
recursive template instantiation exceeded maximum depth of 1024
      template<typename _Up, typename _Up2 = __remove_cvref_t<_Up>>
                                             ^
/usr/bin/../lib/gcc/x86_64-alpine-linux-
musl/9.2.0/../../../../include/c++/9.2.0/bits/refwrap.h:313:41: note: in
instantiation of default argument for '__not_same<S>' required here
      template<typename _Up, typename = __not_same<_Up>, typename
                                        ^~~~~~~~~~~~~~~
/usr/bin/../lib/gcc/x86_64-alpine-linux-
musl/9.2.0/../../../../include/c++/9.2.0/bits/refwrap.h:315:2: note: in
instantiation of default argument for 'reference_wrapper<S>' required here
        reference_wrapper(_Up&& __uref)
        ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
/usr/bin/../lib/gcc/x86_64-alpine-linux-
musl/9.2.0/../../../../include/c++/9.2.0/bits/refwrap.h:314:40: note: while
substituting deduced template arguments into function template
'reference_wrapper'
      [with _Up = S, $1 = (no value), $2 = (no value)]
                = decltype(reference_wrapper::_S_fun(std::declval<_Up>()))>
                                                     ^
/usr/bin/../lib/gcc/x86_64-alpine-linux-
musl/9.2.0/../../../../include/c++/9.2.0/bits/refwrap.h:315:2: note: in
instantiation of default argument for 'reference_wrapper<S, void>' required here
        reference_wrapper(_Up&& __uref)
        ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
/usr/bin/../lib/gcc/x86_64-alpine-linux-
musl/9.2.0/../../../../include/c++/9.2.0/bits/refwrap.h:314:40: note: while
substituting deduced template arguments into function template
'reference_wrapper'
      [with _Up = S, $1 = (no value), $2 = (no value)]
                = decltype(reference_wrapper::_S_fun(std::declval<_Up>()))>
                                                     ^
/usr/bin/../lib/gcc/x86_64-alpine-linux-
musl/9.2.0/../../../../include/c++/9.2.0/bits/refwrap.h:315:2: note: (skipping
1015 contexts in backtrace; use -ftemplate-backtrace-limit=0 to see all)
        reference_wrapper(_Up&& __uref)
        ^
/usr/bin/../lib/gcc/x86_64-alpine-linux-
musl/9.2.0/../../../../include/c++/9.2.0/bits/refwrap.h:314:40: note: while
substituting deduced template arguments into function template
'reference_wrapper'
      [with _Up = S, $1 = (no value), $2 = (no value)]
                = decltype(reference_wrapper::_S_fun(std::declval<_Up>()))>
                                                     ^
/usr/bin/../lib/gcc/x86_64-alpine-linux-
musl/9.2.0/../../../../include/c++/9.2.0/bits/refwrap.h:315:2: note: in
instantiation of default argument for 'reference_wrapper<S, void>' required here
        reference_wrapper(_Up&& __uref)
        ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
/usr/bin/../lib/gcc/x86_64-alpine-linux-
musl/9.2.0/../../../../include/c++/9.2.0/bits/refwrap.h:314:40: note: while
substituting deduced template arguments into function template
'reference_wrapper'
      [with _Up = S, $1 = (no value), $2 = (no value)]
                = decltype(reference_wrapper::_S_fun(std::declval<_Up>()))>
                                                     ^
/usr/bin/../lib/gcc/x86_64-alpine-linux-
musl/9.2.0/../../../../include/c++/9.2.0/bits/refwrap.h:315:2: note: in
instantiation of default argument for 'reference_wrapper<S, void>' required here
        reference_wrapper(_Up&& __uref)
        ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
test_alpine1.cpp:19:12: note: while substituting deduced template arguments
into function template 'reference_wrapper' [with _Up = S, $1 = (no value), $2 =
(no value)]
    return S(std::ref(f));
           ^
1 error generated.
===========================================

Here is test_anywhere.cpp
===========================================
# clang++ -c test_anywhere.cpp
test_anywhere.cpp:17:5: fatal error: recursive template instantiation exceeded
maximum depth of 1024
    using not_same = typename std::enable_if<!std::is_same<reference_wrapper, TT>::value>::type;
    ^~~~~
test_anywhere.cpp:19:38: note: in instantiation of template type alias
'not_same' requested here
    template <typename T, typename = not_same<T>, typename = decltype(xxx(std::declval<T>()))>
                                     ^
test_anywhere.cpp:20:5: note: in instantiation of default argument for
'reference_wrapper<S>' required here
    reference_wrapper(T&&);
    ^~~~~~~~~~~~~~~~~~~~~~
test_anywhere.cpp:19:75: note: while substituting deduced template arguments
into function template 'reference_wrapper' [with T = S, $1 = (no value), $2 =
(no value)]
    template <typename T, typename = not_same<T>, typename = decltype(xxx(std::declval<T>()))>
                                                                          ^
test_anywhere.cpp:20:5: note: in instantiation of default argument for
'reference_wrapper<S, void>' required here
    reference_wrapper(T&&);
    ^~~~~~~~~~~~~~~~~~~~~~
test_anywhere.cpp:19:75: note: while substituting deduced template arguments
into function template 'reference_wrapper' [with T = S, $1 = (no value), $2 =
(no value)]
    template <typename T, typename = not_same<T>, typename = decltype(xxx(std::declval<T>()))>
                                                                          ^
test_anywhere.cpp:20:5: note: (skipping 1015 contexts in backtrace; use -
ftemplate-backtrace-limit=0 to see all)
    reference_wrapper(T&&);
    ^
test_anywhere.cpp:19:75: note: while substituting deduced template arguments
into function template 'reference_wrapper' [with T = S, $1 = (no value), $2 =
(no value)]
    template <typename T, typename = not_same<T>, typename = decltype(xxx(std::declval<T>()))>
                                                                          ^
test_anywhere.cpp:20:5: note: in instantiation of default argument for
'reference_wrapper<S, void>' required here
    reference_wrapper(T&&);
    ^~~~~~~~~~~~~~~~~~~~~~
test_anywhere.cpp:19:75: note: while substituting deduced template arguments
into function template 'reference_wrapper' [with T = S, $1 = (no value), $2 =
(no value)]
    template <typename T, typename = not_same<T>, typename = decltype(xxx(std::declval<T>()))>
                                                                          ^
test_anywhere.cpp:20:5: note: in instantiation of default argument for
'reference_wrapper<S, void>' required here
    reference_wrapper(T&&);
    ^~~~~~~~~~~~~~~~~~~~~~
test_anywhere.cpp:33:12: note: while substituting deduced template arguments
into function template 'reference_wrapper' [with T = S, $1 = (no value), $2 =
(no value)]
    return S(reference_wrapper(f));
           ^
1 error generated.
===========================================

Please note that test_anywhere.cpp depends on <type_traits> only.

[Quuxplusone]

Thanks. Here's what's happening in test_anywhere.cpp:

1) On line 33, we try to construct a reference_wrapper from a reference_wrapper
xvalue. So we consider reference_wrapper constructors.

2) When considering the reference_wrapper constructor on line 19-20, we deduce
T = reference_wrapper.

3) We substitute the deduced T into the default template argument for the third
parameter, and form a call to xxx passing in an xvalue of type T =
reference_wrapper. So we consider the two xxx overloads, and select the
overload on line 12 with T = reference_wrapper.

4) In order to call the function(T) constructor with T = reference_wrapper, we
try to construct a reference_wrapper from a reference_wrapper xvalue. So we
consider reference_wrapper constructors.

5) Go to 2.

I believe Clang is behaving as the standard requires here. The GCC shortcut I
mentioned in comment#7 is that GCC will sometimes not perform template argument
deduction and substitution into the template argument list for some overload
candidates if it can see that a different candidate will always be better, and
this does appear to be one of the cases where that shortcut is taken. (I think
I've *finally* figured out exactly what GCC is doing here -- it's applying
[class.copy.ctor]p5 "A declaration of a constructor for a class X is ill-formed
if its first parameter is of type (optionally cv-qualified) X and either there
are no other parameters or else all other parameters have default arguments. A
member function template is never instantiated to produce such a constructor
signature." early -- before deduction and substitution rather than afterwards.)

Unless we can demonstrate that Clang is misinterpreting the code it was given,
I think there are two possibilities here:

1) The standard requires that copying a
std::reference_wrapper<std::function<void()>> works: this is a bug in
libstdc++, that is not observable when using GCC because GCC happens to
implement an optimization that works around the bug.

2) The standard does not require that copying a
std::reference_wrapper<std::function<void()>> works: the testcase is invalid.

I don't know which of these is the case. The specification for the "function(F
f)" constructor doesn't say anything about the case where F would be deduced as
the same function type -- it just says "Requires: F shall be
Cpp17CopyConstructible". (And it's unclear whether that "Requires" should be
interpreted as a Constraints or Precondition / Mandates, which would give a
clue as to how early an implementation is permitted to check it.)

[Quuxplusone]

Thanks for the detailed explanation. But now I fear that I might have
oversimplified the code in test_anywhere.cpp. E.g. the functions "xxx" (which
mimic std::reference_wrapper::_S_fun) should have been as follows:
===
static void xxx(function&);
static void xxx(function&&) = delete;
===
With the second xxx marked as deleted I get exactly the same error message as
before.
Shouldn't it be skipped in this case?

In any case, could you also look at test_alpine1.cpp or its preprocessed
variant test_alpine1.cpp.i which reproduce the original issue?