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.

Answer 1

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;
}

Answer 2

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.

Answer 3

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