Template deduction depends on another template deduction

Question

Since std::format isn't supported everywhere, and I didn't want another large dependency like fmt, I wanted to quickly roll my own to_string solution for a number of types. The following is the code.

#include <ranges>
#include <string>
#include <concepts>

template<typename Type>
constexpr std::string stringify(const Type &data) noexcept;

template<typename Type> requires std::integral<Type>
constexpr std::string stringify(const Type &data) noexcept {
    return std::to_string(data);
}

template<typename Type>
constexpr std::string stringify_inner(const Type &data) noexcept {
    return stringify(data);
}

template<typename Type> requires std::ranges::range<Type>
constexpr std::string stringify_inner(const Type &data) noexcept {
    return "[" + stringify(data) + "]";
}

template<typename Type> requires std::ranges::range<Type>
constexpr std::string stringify(const Type &data) noexcept {
    std::string string;
    for (auto &i : data) {
        string += stringify_inner(i);
        string += ", ";
    }

    string.pop_back();
    string.pop_back();
    return string;
}

Now, if I write the following code, I get some nice output.

int main() {
    std::vector<int> a = { 1, 2, 3, 4 };
    std::vector<std::vector<int>> b = {{ 1, 2 }, { 3, 4 }};
    std::cout << stringify(a) << std::endl;
    std::cout << stringify(b) << std::endl;
}

// >>> 1, 2, 3, 4
// >>> [1, 2], [3, 4]

Now, for some reason, if I remove the stringify<std::vector<int>> call, the compiler fails to deduce the correct function.

int main() {
    // std::vector<int> a = { 1, 2, 3, 4 };
    std::vector<std::vector<int>> b = {{ 1, 2 }, { 3, 4 }};
    // std::cout << stringify(a) << std::endl;
    std::cout << stringify(b) << std::endl;
}

// >>> undefined reference to `std::__cxx11::basic_string<char, std::char_traits<char>, 
// >>> std::allocator<char> > stringify<std::vector<int, std::allocator<int> > >(std::vector<int,
// >>> std::allocator<int> > const&)'

I think I understand what is happening here, but I don't know why exactly or how to fix it. It seems like the compiler needs the manual instantiation of stringify<std::vector<int>>, so that it can resolve stringify<std::vector<std::vector<int>>>.

I've never encountered this behavior before and have no idea how to continue. I'm compiling with C++20, using GCC on Windows. Thanks.

Forward declaring your last function before `stringify_inner` will likely fix the issue. `stringify_inner` only knows about the specialisation for integral types so assumes the unimplemented first declaration is the one it should use — Alan Birtles, Oct 23 '22 at 07:29
Clangd does give a warning for this: `inline function 'stringify>' is not defined [-Wundefined-inline]`. — Enlico, Oct 23 '22 at 07:30
@Enlico The warning is valid, however, it does not appear to affect the code. I'm actually not sure how to get rid of that warning other than removing `constexpr` but that's a problem for another time. — Jaan, Oct 23 '22 at 07:31
@AlanBirtles I'm not sure what you mean. I have already "forward declared" the base template function. If you mean `stringify>` specifically, I would think that would defeat the purpose using `std::ranges::range` to get any valid ranges. — Jaan, Oct 23 '22 at 07:33
@JeJo EDIT: I misread your answer. I understand why it might be easier to implement this using a single function, but I think as there are more corner cases to deal with such as containers of containers or tuples which require recursive unwrapping, a single function may be more difficult. — Jaan, Oct 23 '22 at 08:11

score 3 · Accepted Answer · answered Oct 23 '22 at 07:41

The order of declarations of your template overloads results in

template<typename Type> requires std::ranges::range<Type>
constexpr std::string stringify(const Type& data) noexcept;

being for the overload, when specializing

template<typename Type> requires std::ranges::range<Type>
constexpr std::string stringify_inner(const Type &data) noexcept {
    return "[" + stringify(data) + "]";
}

with Type = std::vector<int>, but this function isn't defined anywhere. You need to make sure to declare the function signature for ranges early enough for the compiler to use it:

template<typename Type>
constexpr std::string stringify(const Type& data) noexcept;

template<typename Type> requires std::integral<Type>
constexpr std::string stringify(const Type& data) noexcept {
    return std::to_string(data);
}

/////////////////////// Add this ////////////////////////////////////
template<typename Type> requires std::ranges::range<Type>
constexpr std::string stringify(const Type& data) noexcept;
/////////////////////////////////////////////////////////////////////

template<typename Type>
constexpr std::string stringify_inner(const Type& data) noexcept {
    return stringify(data);
}

template<typename Type> requires std::ranges::range<Type>
constexpr std::string stringify_inner(const Type& data) noexcept {
    return "[" + stringify(data) + "]";
}

template<typename Type> requires std::ranges::range<Type>
constexpr std::string stringify(const Type& data) noexcept {
    std::string string;
    for (auto& i : data) {
        string += stringify_inner(i);
        string += ", ";
    }

    string.pop_back();
    string.pop_back();
    return string;
}
template<typename Type> requires std::ranges::range<Type>
constexpr std::string stringify(const Type& data) noexcept;

template<typename Type>
constexpr std::string stringify_inner(const Type& data) noexcept {
    return stringify(data);
}

template<typename Type> requires std::ranges::range<Type>
constexpr std::string stringify_inner(const Type& data) noexcept {
    return "[" + stringify(data) + "]";
}

template<typename Type> requires std::ranges::range<Type>
constexpr std::string stringify(const Type& data) noexcept {
    std::string string;
    for (auto& i : data) {
        string += stringify_inner(i);
        string += ", ";
    }

    string.pop_back();
    string.pop_back();
    return string;
}

Ahhh I see. Thanks for the answer. I guess it's probably a guess idea to forward declare every unique `stringify ... requires` clause here. — Jaan, Oct 23 '22 at 07:44

Enlico · Answer 2 · 2022-10-23T08:06:57.560

The answer is typed in prose on cppreference

Specialization must be declared before the first use that would cause implicit instantiation

In your example, the specialization of stringify for ranges would be instatiated by the call to the first of stringify_inner's overload, but it is declared after it, instead of before.

As often happens, we could have got some insight by seeing what clang thinks about the code

Clangd does give a warning for this: `inline function 'stringify<std::vector<int>>' is not defined [-Wundefined-inline]`.
constexpr std::string stringify(const Type &data) noexcept;
                     ^
somesource.cpp:22:18: note: used here
   return "[" + stringify(data) + "]";
                ^
1 warning generated.

which would have at least been clearer than GCC's.

Related Q&A and related comment on another answer.

JeJo · Answer 3 · 2022-10-24T20:07:28.343

Other answers have mentioned the issue with overloading and function declaration issues.

(For future readers) I propose having the stringifying in a single (recursive) function, which take care the ranges, and the std::integral(or is_stringable) overload can be kept for integral types.

Something like as follows:

#include <type_traits>
#include <string>
#include <concepts>
#include <ranges>
using namespace std::string_literals;

template<typename Type> // concept for checking std::to_string-able types
concept is_stringable = requires (Type t) 
            { {std::to_string(t) }->std::same_as<std::string>; };

// "stringify" overload for is_stringable
constexpr std::string stringify(const is_stringable auto& data) {
    return std::to_string(data);
}

// "stringify" overload for ranges
constexpr std::string stringify(const std::ranges::range auto& data) {
    // value type of the ranges (Only Sequence ranges)
    using ValueType = std::remove_const_t<
        std::remove_reference_t<decltype(*data.cbegin())>
    >;

    if constexpr (is_stringable<ValueType>) {
        std::string string{};
        for (ValueType element : data)
            string += stringify(element) + ", "s;
        string.pop_back();
        string.pop_back();
        return "["s + string + "]"s;
    }
    // else if constexpr (<other types Ex. ValueType == std::tuple>) {}
    // .... more
    else {
        std::string string;
        for (const ValueType& innerRange : data)
            string += stringify(innerRange);
        return string;
    }
}

See live demo in godbolt.org

Template deduction depends on another template deduction

3 Answers3

Linked