Template instantiation reaches depth of 900

Question

In the following code I..

• create test list using my custom list struct (which works as expected)
• push some test ints into it
• want to call a function that takes as parameters every list element (observe())

To achieve this I tried to recursively extract the function parameters (values of the list nodes) out of the list via the call_observe_with_list and call_observe_with_list_impl - helpers. However, this leads infinite template recursion:

In file included from /opt/compiler-explorer/gcc-8.4.0/include/c++/8.4.0/memory:81,
                 from <source>:1:
/opt/compiler-explorer/gcc-8.4.0/include/c++/8.4.0/bits/shared_ptr.h: In substitution of 'template<class _Yp, class> std::shared_ptr<list<int>::node>::shared_ptr(const std::shared_ptr<_Tp>&) [with _Yp = list<int>::node; <template-parameter-1-2> = <missing>]':
<source>:45:43:   recursively required from 'void call_observe_with_list_impl(const list<T>&, std::shared_ptr<typename list<T>::node>, const Ks& ...) [with T = int; Ks = {int}]'
<source>:45:43:   required from 'void call_observe_with_list_impl(const list<T>&, std::shared_ptr<typename list<T>::node>, const Ks& ...) [with T = int; Ks = {}]'
<source>:52:39:   required from 'void call_observe_with_list(const list<T>&) [with T = int; Ks = {}]'
<source>:65:37:   required from here
/opt/compiler-explorer/gcc-8.4.0/include/c++/8.4.0/bits/shared_ptr.h:245:9: fatal error: template instantiation depth exceeds maximum of 900 (use -ftemplate-depth= to increase the maximum)
         typename = _Constructible<const shared_ptr<_Yp>&>>

This is my code (try it yourself).

#include <memory>
#include <iostream>

template <typename T>
struct list
{
    struct node
    {
        T val_;
        std::shared_ptr<node> next_;
        node(T val, const std::shared_ptr<node>& next) : val_(val), next_(next) {}
    };

    std::shared_ptr<node> head_ = nullptr;

    void push(T val) {
        head_ = std::make_shared<node>(val, head_);
    }

    void erase(T val) {
        auto* pptr = &head_;
        for (auto node = head_; node; node = node->next_) {
            if (node->val_ == val) {
                *pptr = node->next_;
                return ;
            }
            pptr = &(node->next_);
        }
    }
};


template <typename... Ts>
void observe(Ts... Args)
{
    std::cout << "observe" << std::endl;
}

template <typename T, typename... Ks>
void call_observe_with_list_impl(const list<T>& some_list, std::shared_ptr<typename list<T>::node> curr_ptr, const Ks&... Args)
{
    if (curr_ptr == nullptr) {
        return observe(Args...);
    } else {
        return call_observe_with_list_impl(some_list, curr_ptr->next_, curr_ptr->val_, Args...);
    }
}

template <typename T>
void call_observe_with_list(const list<T>& some_list)
{
    return call_observe_with_list_impl(some_list, some_list.head_);
}

int main()
{
    list<int> some_list;

    some_list.push(1);
    some_list.push(2);
    some_list.push(10123);
    some_list.push(100);
    some_list.push(5);

    call_observe_with_list(some_list);
}

Why does this happen? The terminal condition (last node = nullptr) is always met so this shouldn't ever happen or what am I missing?

Answer 1

It is possible to decide the number of arguments from some fixed number of arguments (say between 1 and 10 arguments). What is not possible is to write a function which takes arbitrarily many arguments, which is what you've tried to do here. It is not even possible to write a single non-templated function taking 10 million arguments, for example - the runtime doesn't have functions which take arbitrarily many parameters.

You have to decide in advance what the maximum number of arguments you'll reasonable expect to call this method with; and what to do if you have more list elements than that.

The simplest solution is to ignore the call if there's too many arguments, but you could also throw an exception:

template <typename T, typename... Ks>
void call_observe_with_list_impl(const list<T>& some_list, std::shared_ptr<typename list<T>::node> curr_ptr, const Ks&... Args)
{
    if (curr_ptr == nullptr) {
        return observe(Args...);
    } else
    {
        // note the if "constexpr" here - when there's more than 10 args,
        // the `else' branch is not even instantiated
        if constexpr (sizeof...(Ks) >= 10)
        {
            throw std::exception();
        }
        else
        {
            return call_observe_with_list_impl(some_list, curr_ptr->next_, curr_ptr->val_, Args...);
        }
    }
}

You could also break the calls to observe into "chunks" of up to some fixed size:

        ...
        if constexpr (sizeof...(Ks) >= 10)
        {
            observe(Args...);
            call_observe_with_list_impl(some_list, curr_ptr->next_);
        }
        ...

Then for example the following program:

template <typename T, typename... Ts>
void comma_sep(T Arg0, Ts... Args)
{
    std::cout << Arg0;
    ((std::cout << ", " << Args), ...);
}

template <typename... Ts>
void observe(Ts... Args)
{
    std::cout << "observe(";
    comma_sep(Args...);
    std::cout << ")\n";
}

int main()
{
    list<int> some_list;

    for (int i = 0; i < 25; ++i)
    {
        some_list.push(i*i);
    }

    call_observe_with_list(some_list);
}

gives this output:

observe(225, 256, 289, 324, 361, 400, 441, 484, 529, 576)
observe(16, 25, 36, 49, 64, 81, 100, 121, 144, 169)
observe(0, 1, 4)