[Bug c++/103096] New: Compiling never ends (at least not in resonable time - less than 10 mins)

[Bug c++/103096] New: Compiling never ends (at least not in resonable time - less than 10 mins)

[pavel.celba at ricardo dot com]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=103096

            Bug ID: 103096
           Summary: Compiling never ends (at least not in resonable time -
                    less than 10 mins)
           Product: gcc
           Version: 10.2.0
            Status: UNCONFIRMED
          Severity: normal
          Priority: P3
         Component: c++
          Assignee: unassigned at gcc dot gnu.org
          Reporter: pavel.celba at ricardo dot com
  Target Milestone: ---

Code - file test.cpp:

#include <iostream>
#include <utility>


using namespace std;

template <typename T> int qHash(const T& a)
{
  return qHash(std::pair<T, T>(a, a));
}

int main()
{
  int a = 3;
  std::cout << qHash(a);
}

Run as normally:
gcc test.cpp

[Bug libstdc++/103096] Compiling never ends (at least not in resonable time - less than 10 mins)

[rguenth at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=103096

Richard Biener <rguenth at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
          Component|c++                         |libstdc++
           Keywords|                            |compile-time-hog

--- Comment #1 from Richard Biener <rguenth at gcc dot gnu.org> ---
same for clang++, so possibly a libstdc++ issue.  But then you are
instantiating std::pair<std::pair<int, int>, std::pair<int, int> >, etc.,
exponentially growing the size of the template...

Which means - don't do this?

[Bug libstdc++/103096] Compiling never ends (at least not in resonable time - less than 10 mins)

[pavel.celba at ricardo dot com]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=103096

--- Comment #2 from Pavel Celba <pavel.celba at ricardo dot com> ---
But shouldn't the compiler end in all cases with some error?
There should be a depth instantiation limit which is reached and compilation
ended.
No matter how non-sensible the input is. My input is quite sensible C++ code
bug thing any amateur can easily do.

[Bug c++/103096] Compiling never ends (at least not in resonable time - less than 10 mins)

[redi at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=103096

Jonathan Wakely <redi at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
          Component|libstdc++                   |c++
   Last reconfirmed|                            |2021-11-05
     Ever confirmed|0                           |1
             Status|UNCONFIRMED                 |NEW

--- Comment #3 from Jonathan Wakely <redi at gcc dot gnu.org> ---
(In reply to Richard Biener from comment #1)
> same for clang++, so possibly a libstdc++ issue.

No, the library isn't to blame here at all:


template<typename T, typename U>
struct pair
{
  pair(const T& t, const U& u) : first(t), second(u) { }

  T first;
  U second;
};

template <typename T> int qHash(const T& a)
{
  return qHash(pair<T, T>(a, a));
}

void f(int);

int main()
{
  int a = 3;
  f(qHash(a));
}


The compiler should indeed hit the template instantiation limit, but it takes
too long to do that. If you use -ftemplate-depth=10 it fails immediately.

The default value is 900 and the exponential growth here slows us down long
before we get there. Even -ftemplate-depth=100 takes forever.

[Bug c++/103096] Compiling never ends (at least not in resonable time - less than 10 mins)

[redi at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=103096

--- Comment #4 from Jonathan Wakely <redi at gcc dot gnu.org> ---
Maybe the compiler could notice that there is only one qHash function template,
and so realize that the instantiation recursion of qHash<X> instantiating
qHash<Y> instantiating qHash<Z> etc. will never terminate.

That check would be defeated by any indirection though:

template <typename T> int qHash2(const T& a);

template <typename T> int qHash(const T& a)
{
  return qHash2(pair<T, T>(a, a));
}

template <typename T> int qHash2(const T& a) { return qHash(a); }


The general case is the halting problem, which is why we just have the
-ftemplate-depth=n limit to stop it at some arbitrary point.

[Bug c++/103096] Compiling never ends (at least not in resonable time - less than 10 mins)

[redi at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=103096

--- Comment #5 from Jonathan Wakely <redi at gcc dot gnu.org> ---
(In reply to Jonathan Wakely from comment #4)
> Maybe the compiler could notice that there is only one qHash function
> template, and so realize that the instantiation recursion of qHash<X>
> instantiating qHash<Y> instantiating qHash<Z> etc. will never terminate.

It would also have to consider whether there are partial or explicit
specializations of the pair class template, because otherwise one of them could
define a friend that would be found by ADL and terminate the recursion. So
maybe too hard.

This case is fine:


template<typename T, typename U>
struct pair
{
  pair(const T& t, const U& u) : first(t), second(u) { }

  T first;
  U second;
};


template <typename T> int qHash(const T& a)
{
  return qHash(pair<T, T>(a, a));
}

template<typename T>
struct pair<pair<pair<T, T>, pair<T, T>>, pair<pair<T, T>, pair<T, T>>>
{
  template<typename... X>
  pair(X...) { }

  friend int qHash(pair) { return 0; }
};

void f(int);

int main()
{
  int a = 3;
  f(qHash(a));
}


The overload of qHash that terminates the recursion is only defined when the
partial specialization is instantiated.

[Bug c++/103096] Compiling never ends (at least not in resonable time - less than 10 mins)

[jakub at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=103096

--- Comment #6 from Jakub Jelinek <jakub at gcc dot gnu.org> ---
We'd need next to the instantiation depth limit something that would be
incremented for every nested instantiation and when this counter reaches some
limit, also fail like reaching the instantiation depth limit does.
E.g. with -ftemplate-depth=27 it takes on #c3 about 19s on my box to fail, so a
default limit for such counter of something like 2^23 to 2^27 might be ok (we'd
need to see what is actually reached on boost).  -ftemplate-depth=30 seems to
be already too slow.

[Bug c++/103096] Compiling never ends (at least not in resonable time - less than 10 mins)

[redi at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=103096

--- Comment #7 from Jonathan Wakely <redi at gcc dot gnu.org> ---
30 would be too low for "reasonable" code, like a std::variant or std::tuple of
31 types, if some algorithm is implemented as a recursive template.

[Bug c++/103096] Compiling never ends (at least not in resonable time - less than 10 mins)

[pinskia at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=103096

--- Comment #8 from Andrew Pinski <pinskia at gcc dot gnu.org> ---
No compiler I have tried does a decent job at figuring this testcase out
quickly (over 20s).

[Bug c++/103096] Compiling never ends (at least not in resonable time - less than 10 mins)

[redi at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=103096

--- Comment #9 from Jonathan Wakely <redi at gcc dot gnu.org> ---
(In reply to Jonathan Wakely from comment #5)
> (In reply to Jonathan Wakely from comment #4)
> > Maybe the compiler could notice that there is only one qHash function
> > template, and so realize that the instantiation recursion of qHash<X>
> > instantiating qHash<Y> instantiating qHash<Z> etc. will never terminate.
> 
> It would also have to consider whether there are partial or explicit
> specializations of the pair class template, because otherwise one of them
> could define a friend that would be found by ADL and terminate the
> recursion. So maybe too hard.

And if-constexpr means you can't just detect the recursion based on whether
name lookup finds more than one candidate:

template <typename T> int qHash(const T& a)
{
  if constexpr (delved too deep)
    return balrog;
  return qHash(pair<T, T>(a, a));
}

This one will terminate, even though it keeps calling itself.