Clang & GCC misdeducing template parameters

Question

I am not good at C++, so this is probably a novice error. I am trying to make a heterogeneous linked list type where the type of each node and those of the rest of the list are known in each node.

Here is an SSSCE:

#include <utility>

template<typename T, typename... Rest>
struct hnode {
    T data;
    hnode<Rest...>* next;
};

template<typename T>
struct hnode<T> {
    T data;
    std::nullptr_t next;
};

template<typename T, typename... Rest>
hnode<T> hcons(T&& val, std::nullptr_t) {
    return { std::forward<T>(val), nullptr };
}

template<typename T, typename... Rest>
hnode<T, Rest...> hcons(T&& val, hnode<Rest...>& next) {
    return { std::forward<T>(val), &next };
}

int main() {
    hnode<int> three = hcons(1, nullptr);
    auto two = hcons("hi", three);
}

However, GCC gives me this error for that code:

test.cc: In function ‘int main()’:
test.cc:28:29: error: no matching function for call to ‘hcons(const char [3], hnode<int>&)’
 auto two = hcons("hi", three);
                             ^
test.cc:28:29: note: candidates are:
test.cc:17:10: note: template<class T, class ... Rest> hnode<T> hcons(T&&, std::nullptr_t)
 hnode<T> hcons(T&& val, std::nullptr_t) {
          ^
test.cc:17:10: note:   template argument deduction/substitution failed:
test.cc:28:29: note:   cannot convert ‘three’ (type ‘hnode<int>’) to type ‘std::nullptr_t’
 auto two = hcons("hi", three);
                             ^
test.cc:22:19: note: hnode<T, Rest ...> hcons(T&&, hnode<Rest ...>&) [with T = const char (&)[3]; Rest = {int, Rest}]
 hnode<T, Rest...> hcons(T&& val, hnode<Rest...>& next) {
                   ^
test.cc:22:19: note:   no known conversion for argument 2 from ‘hnode<int>’ to ‘hnode<int, Rest>&’

Clang is slightly more concise but still not helpful enough for me to fix it:

test.cc:28:12: error: no matching function for call to 'hcons'
auto two = hcons("hi", three);
           ^~~~~
test.cc:17:10: note: candidate function [with T = char const (&)[3], Rest = <>] not viable: no known conversion from 'hnode<int>' to 'std::nullptr_t' (aka 'nullptr_t') for 2nd argument
hnode<T> hcons(T&& val, std::nullptr_t) {
         ^
test.cc:22:19: note: candidate template ignored: substitution failure [with T = char const (&)[3], Rest = <>]: too few template arguments for class template 'hnode'
hnode<T, Rest...> hcons(T&& val, hnode<Rest...>& next) {
                  ^              ~~~~~
1 error generated.

It seems weird because it's deducing Rest to be <> when it should clearly be <int>, and it says that it's <int> on the line above with no known conversion from 'hnode<int>' to 'std::nullptr_t'. What error did I make?

Answer 1

While galop1n's answer is a valid work-around, it doesn't address the real problem in your code.

Although I'm not a C++ language lawyer or anything, I've read somewhere on SO that template matching is a rather strict process. To reflect on your original code: in your hcons function, you are asking the compiler to match next (which is ought to be of type hnode<typename...>) to hnode<typename, typename...>. As you can imagine this isn't really an exact match. It also doesn't match your 1 argument specialization, namely hnode<typename>.

To make your code compile, you only need to change 1 thing, and that is to provide an empty declaration of hnode as accepting a variable number of template arguments, and specialize it for both the 1 parameter version, and the multiple parameter version:

#include <utility>

// empty declaration with variable number of arguments
template<typename...>
struct hnode;

// specialization for 1 template argument
template<typename T>
struct hnode<T> {
    T data;
    std::nullptr_t next;
};

// specialization for multiple template arguments
template<typename T, typename... Rest>
struct hnode<T, Rest...> {
    T data;
    hnode<Rest...>* next;
};

template<typename T>
hnode<T> hcons(T&& val, std::nullptr_t) {
    return { std::forward<T>(val), nullptr };
}

template<typename T, typename... Rest>
hnode<T, Rest...> hcons(T&& val, hnode<Rest...>& next) {
    return { std::forward<T>(val), &next };
}

int main() {
    hnode<int> three = hcons(1, nullptr);
    auto two = hcons("hi", three);
}

Now your hcons function can match hnode<typename...> exactly, and will instantiate the corresponding specialization. POC on ideone

Visual Studio's compiler is known to be a little lax when it comes to template-related stuff, so that might be the reason why it accepts your original code.

As can be found in this related question, it turns out to be a bug in GCC and Clang, so VS is the one that is correctly accepting your code.

Also as a side note: by removing the std::nullptr_t member in your 1 argument specialization of hnode, you can save a little bit of memory.

Answer 2

Not sure why but as hnode has at least one template parameter, this works :

#include <utility>

template<typename T, typename... Rest>
struct hnode {
    T data;
    hnode<Rest...>* next;
};

template<typename T>
struct hnode<T> {
    T data;
    std::nullptr_t next;
};

template<typename T>
hnode<T> hcons(T&& val, std::nullptr_t) {
    return { std::forward<T>(val), nullptr };
}

template<typename T, typename S, typename... Rest>
    hnode<T, S, Rest...> hcons(T&& val, hnode<S, Rest...>& next) {
    return { std::forward<T>(val), &next };
}

int main() {
    hnode<int> three = hcons(1, nullptr);
    auto two = hcons("hi", three);
    auto one = hcons(5.14f, two);
}

On your version, once it fails to find a best match, it is normal the compiler list all the candidate. The real question still remains, why clang is wrong on the template parameter pack deduction…

Visual studio 2013 succeed on both version ( with and without S ), still it fails on the forward of a const char(*)[3] i replace with a int for the test…

Clang or Visual, who is right, i do not know, but it may be a good idea to fill a bug report here.