How to stop template recursion while using parameter deduction?

Question

This code task a const char[] and finds where is the last slash:

#include <array>
#define STATIC_ASSERT(...) static_assert(__VA_ARGS__, #__VA_ARGS__)

template< int PathIndex, int PathLength >
constexpr const int findlastslash(const char (&path)[PathLength])
{
    constexpr const int end = PathLength - PathIndex;
    return (PathIndex >= 0 && path[end] != '/' && path[end] != '\\') 
           ? findlastslash< PathIndex - 1, PathLength >( path ) : ( end + 1 );
}

template< int PathLength >
constexpr const int startfindlastslash(const char (&path)[PathLength]) {
    return findlastslash< PathLength >( path );
}

int main(int argc, char const *argv[])
{
    STATIC_ASSERT( startfindlastslash( "cppdebugger/test_debugger.cpp" ) == 11 );
}

But it does not work because the template recursion never stops:

$ g++ -o main.exe --std=c++14 test_debugger.cpp
test_debugger.cpp: In function ‘int main(int, const char**)’:
test_debugger.cpp:2:28: error: static assertion failed: startfindlastslash( "cppdebugger/test_debugger.cpp" ) == 17
 #define STATIC_ASSERT(...) static_assert(__VA_ARGS__, #__VA_ARGS__)
                            ^
test_debugger.cpp:18:5: note: in expansion of macro ‘STATIC_ASSERT’
     STATIC_ASSERT( startfindlastslash( "cppdebugger/test_debugger.cpp" ) == 17 );
     ^~~~~~~~~~~~~
test_debugger.cpp: In instantiation of ‘constexpr const int findlastslash(const char (&)[PathLength]) [with int PathIndex = -880; int PathLength = 30]’:
test_debugger.cpp:8:114:   recursively required from ‘constexpr const int findlastslash(const char (&)[PathLength]) [with int PathIndex = 19; int PathLength = 30]’
test_debugger.cpp:8:114:   required from here
test_debugger.cpp:8:114: fatal error: template instantiation depth exceeds maximum of 900 (use -ftemplate-depth= to increase the maximum)
     return (PathIndex >= 0 && path[end] != '/' && path[end] != '\\') ? findlastslash< PathIndex - 1, PathLength >( path ) : ( end + 1 );
                                                                        ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~
compilation terminated.

I know can do this easily using const char *, but I am interested in keeping using string "cppdebugger/test_debugger.cpp" (const char[]) as a array, i..e, without decaying into a const char * pointer.

Update

Correction. A template specialization is like this (with < 1, PathLength >:

template< int PathLength >
constexpr const int findlastslash< 1, PathLength >(const char (&path)[PathLength])
{
    constexpr const int end = PathLength;
    return ( path[end] != '/' && path[end] != '\\') ? 0 : 1;
}

Where the compiler correctly complains it:

$ g++ -o main.exe --std=c++14 test_debugger.cpp
test_debugger.cpp:18:82: error: non-class, non-variable partial specialization ‘findlastslash<1, PathLength>’ is not allowed
 constexpr const int findlastslash< 1, PathLength >(const char (&path)[PathLength])
                                                                                  ^
test_debugger.cpp: In function ‘int main(int, const char**)’:
test_debugger.cpp:2:28: error: static assertion failed: startfindlastslash( "cppdebugger/test_debugger.cpp" ) == 11
 #define STATIC_ASSERT(...) static_assert(__VA_ARGS__, #__VA_ARGS__)
                            ^
test_debugger.cpp:26:5: note: in expansion of macro ‘STATIC_ASSERT’
     STATIC_ASSERT( startfindlastslash( "cppdebugger/test_debugger.cpp" ) == 11 );
     ^~~~~~~~~~~~~
test_debugger.cpp: In instantiation of ‘constexpr const int findlastslash(const char (&)[PathLength]) [with int PathIndex = -880; int PathLength = 30]’:
test_debugger.cpp:9:56:   recursively required from ‘constexpr const int findlastslash(const char (&)[PathLength]) [with int PathIndex = 19; int PathLength = 30]’
test_debugger.cpp:9:56:   required from here
test_debugger.cpp:9:56: fatal error: template instantiation depth exceeds maximum of 900 (use -ftemplate-depth= to increase the maximum)
            ? findlastslash< PathIndex - 1, PathLength >( path ) : ( end + 1 );
              ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~
compilation terminated.

Related questions:

Even if (runtime) branch is not taken, the template is instantiated, you need `if constexpr` or specialization. — Jarod42, Dec 24 '19 at 19:47
What is the value of `PathIndex` when you instantiate the template as `return findlastslash< PathLength >( path );` ? What is `end` in this first instantiation? — Happy Green Kid Naps, Dec 24 '19 at 19:48
Re: "without decaying init a ... pointer" -- why? That makes what would be a one-liner incredibly complex. — Pete Becker, Dec 24 '19 at 20:05
@PeteBecker I am learning templates and this seems a good way to start learning build complex things. — Evandro Coan, Dec 24 '19 at 20:18
This question is too long IMHO, especially with the erased part. Just edit it into a final form. Also, `findlastslash` -> `find_last_slash`. Finally, std::filesystem has a path class which might already be doing what you need. — einpoklum, Dec 24 '19 at 23:12

score 1 · Accepted Answer · edited Dec 24 '19 at 22:27

If you are in C++14, you no longer require recursion for constexpr, you can use regular loop:

template<std::size_t PathLength>
constexpr const int findlastslash(const char (&path)[PathLength])
{
    for (std::size_t i = PathLength; i != 0; --i) {
        if (path[i - 1] == '/' || path[i - 1] == '\\') {
            return i;
        }
    }
    return 0;
}

In C++11, you might do:

template<std::size_t PathLength>
constexpr const int findlastslash(const char (&path)[PathLength], std::size_t i = PathLength)
{
    return (i == 0)
        ? 0
        : ((path[i - 1] == '/' || path[i - 1] == '\\')
            ? i
            : findlastslash(path, i - 1));
}

constexpr version in C++17 (to get rid of regular parameter i):

template<std::size_t PathLength, std::size_t I = PathLength>
constexpr const int findlastslash(const char (&path)[PathLength])
{
    if constexpr (I == 0) {
        return 0;
    } else {
        if (path[I - 1] == '/' || path[I - 1] == '\\') {
            return I;
        }
        return findlastslash<PathLength, I - 1>(path);
    }
}

Prior C++17, you have to use specialization or overload instead of if constexpr, but function cannot be partial specialized.

So struct specialization might be:

template <std::size_t I> struct findlastslash_impl
{
    template <std::size_t PathLength>
    constexpr const int findlastslash(const char (&path)[PathLength])
    {
        if (path[I - 1] == '/' || path[I - 1] == '\\') {
            return I;
        }
        return findlastslash_impl<I - 1>()(path);
    }
}
template<> struct findlastslash_impl<0>
{
    template<std::size_t PathLength>
    constexpr const int findlastslash(const char (&)[PathLength])
    {
        return 0;
    }
};

template<std::size_t PathLength>
constexpr const int findlastslash(const char (&path)[PathLength])
{
    return findlastslash_impl<PathLength>()(path);
}

or with overloads:

template <std::size_t PathLength>
constexpr const int findlastslash_impl(std::integral_constant<std::size_t, 0>,
                                       const char (&path)[PathLength])
{
    return 0;
}

template <std::size_t PathLength, std::size_t I>
constexpr const int findlastslash_impl(std::integral_constant<std::size_t, I>,
                                       const char (&path)[PathLength])
{
    if (path[I - 1] == '/' || path[I - 1] == '\\') {
        return I;
    }
    return findlastslash_impl(std::integral_constant<std::size_t, I - 1>(), path);
}

template<std::size_t PathLength>
constexpr const int findlastslash(const char (&path)[PathLength])
{
    return findlastslash_impl(std::integral_constant<std::size_t, PathLength>(), path);
}

Thanks for the examples! Now a new day has come and I can vote up again :) — Evandro Coan, Dec 25 '19 at 01:07

Marek R · Answer 2 · 2019-12-25T08:57:55.190

1

Note that this functionality is already available in C++17 in std::string_view.

See: std::basic_string_view::rfind

#include <string_view>

using namespace std::literals;

int main()
{
    static_assert("cppdebugger/test_debugger.cpp"sv.rfind('/') == 11);
    static_assert("cppdebugger/test_debugger.cpp"sv.find_last_of("\\/"sv) == 11);
}

Live demo

edited Dec 25 '19 at 08:57

answered Dec 24 '19 at 22:56

Marek R

32,568
6
55
140

Can you add an example? – Evandro Coan Dec 24 '19 at 22:58
@user here it is – Marek R Dec 25 '19 at 08:39

Evandro Coan · Answer 3 · 2019-12-24T23:11:15.370

I managed to fix it by using class partial template specialization. I did not use function partial template specialization because it is not allowed: Why I cannot partially specialize template free functions, only classes?

#define STATIC_ASSERT(...) static_assert(__VA_ARGS__, #__VA_ARGS__)

template<int PathIndex>
struct Findlastslash
{
    template< int PathLength >
    static constexpr int start(const char (&path)[PathLength])
    {
        constexpr const int end = PathLength - PathIndex;
        return (PathIndex >= 0 && path[end] != '/' && path[end] != '\\') 
              ? Findlastslash< PathIndex - 1 >::start( path ) : ( end );
    }
};

template<> 
struct Findlastslash< 1 >
{
    template< int PathLength >
    static constexpr int start(const char (&path)[PathLength]) {
        return 0;
    }
};

template< int PathLength >
constexpr const int startfindlastslash(const char (&path)[PathLength]) {
    return Findlastslash< PathLength >::start( path );
}

int main(int argc, char const *argv[])
{
    STATIC_ASSERT( startfindlastslash( "h/bye" ) == 1 );
}

This is the expanded template:

clang++ -Xclang -ast-print -fsyntax-only --std=c++14 test_debugger.cpp > main.exe

template <int PathIndex> 
struct Findlastslash 
{
    template <int PathLength> 
    static constexpr int start(const char (&path)[PathLength]) 
    {
        constexpr int end = PathLength - PathIndex;
        return (PathIndex >= 0 && path[end] != '/' && path[end] != '\\') 
                ? Findlastslash<PathIndex - 1>::start(path) : (end);
    }
};

template<> 
struct Findlastslash<6> 
{
    template <int PathLength> 
    static constexpr int start(const char (&path)[PathLength]);
    template<> static constexpr int start<6>(const char (&path)[6])
    {
        constexpr int end = 6 - 6;
        return (6 >= 0 && path[end] != '/' && path[end] != '\\') 
                ? Findlastslash<6 - 1>::start(path) : (end);
    };
};

template<> 
struct Findlastslash<5> 
{
    template <int PathLength> 
    static constexpr int start(const char (&path)[PathLength]);
    template<> static constexpr int start<6>(const char (&path)[6]) 
    {
        constexpr int end = 6 - 5;
        return (5 >= 0 && path[end] != '/' && path[end] != '\\') 
                ? Findlastslash<5 - 1>::start(path) : (end);
    };
};

template<> 
struct Findlastslash<4> 
{
    template <int PathLength> 
    static constexpr int start(const char (&path)[PathLength]);
    template<> static constexpr int start<6>(const char (&path)[6]) 
    {
        constexpr int end = 6 - 4;
        return (4 >= 0 && path[end] != '/' && path[end] != '\\') 
                ? Findlastslash<4 - 1>::start(path) : (end);
    };
};

template<> 
struct Findlastslash<3> 
{
    template <int PathLength> 
    static constexpr int start(const char (&path)[PathLength]);
    template<> static constexpr int start<6>(const char (&path)[6]) 
    {
        constexpr int end = 6 - 3;
        return (3 >= 0 && path[end] != '/' && path[end] != '\\') 
                ? Findlastslash<3 - 1>::start(path) : (end);
    };
};

template<> 
struct Findlastslash<2> 
{
    template <int PathLength> 
    static constexpr int start(const char (&path)[PathLength]);
    template<> static constexpr int start<6>(const char (&path)[6]) 
    {
        constexpr int end = 6 - 2;
        return (2 >= 0 && path[end] != '/' && path[end] != '\\') 
                ? Findlastslash<2 - 1>::start(path) : (end);
    };
};

template<> 
struct Findlastslash<1> 
{
    template <int PathLength> 
    static constexpr int start(const char (&path)[PathLength]) {
        return 0;
    }

    template<> 
    static constexpr int start<6>(const char (&path)[6]) {
        return 0;
    }
};

template <int PathLength> 
constexpr const int startfindlastslash(const char (&path)[PathLength]) {
    return Findlastslash<PathLength>::start(path);
}

template<> 
constexpr const int startfindlastslash<6>(const char (&path)[6]) {
    return Findlastslash<6>::start(path);
}

int main(int argc, const char *argv[]) {
    static_assert(startfindlastslash("h/bye")==1, "startfindlastslash( \"h/bye\" )==1");
}

How to stop template recursion while using parameter deduction?

Update

3 Answers3

Linked