Skip to content

Instantly share code, notes, and snippets.

@talybin

talybin/recursive_visitor.cpp

Last active June 9, 2024 23:42
Show Gist options
  • Save talybin/c985e747c07c3c841ab6c0b47ae87141 to your computer and use it in GitHub Desktop.
Save talybin/c985e747c07c3c841ab6c0b47ae87141 to your computer and use it in GitHub Desktop.
Download ZIP
Recursive visitor
Raw
recursive_visitor.cpp
#include <utility>
#include <cstddef>
#include <stdexcept>
#include <ctime>
struct test_t { };
namespace detail
{
template <size_t I>
using test_t_index = test_t;
template <class F, size_t... I>
decltype(auto) visit(F&& cb, std::index_sequence<I...>) {
return std::forward<F>(cb)(test_t_index<I>()...);
}
}
template <size_t MAX_SIZE = 5, size_t I = 0, class F>
decltype(detail::visit(std::declval<F>(), std::make_index_sequence<I>()))
visit(size_t cnt, F&& cb)
{
if constexpr (I < MAX_SIZE) {
if (cnt == I)
return detail::visit(std::forward<F>(cb), std::make_index_sequence<I>{});
return visit<MAX_SIZE, I + 1>(cnt, std::forward<F>(cb));
}
else
throw cnt;
}
int main()
{
try {
// 10 is larger than 5, still compiler
// able to see, that max allowed nr is 5
std::srand(std::time(nullptr));
size_t cnt = std::rand() % 10;
printf("try to create %lu arguments...\n", cnt);
// MAX_SIZE can be increased with visit<N>(cnt, ...)
auto ret = visit(cnt, [](auto... args) {
printf("got %lu args\n", sizeof...(args));
return 42;
});
printf("return value: %d\n", ret);
}
catch (size_t nr) {
printf("error: %lu argument do not fit in MAX_SIZE\n", nr);
}
}
@talybin
Copy link
Author

talybin commented Jun 9, 2024 •
edited
Loading

Output example:

try to create 4 arguments...
got 4 args
return value: 42

or when cnt >= MAX_SIZE

try to create 7 arguments...
error: 7 argument do not fit in MAX_SIZE

@talybin
Copy link
Author

talybin commented Jun 9, 2024 •
edited
Loading

When size is a unknown runtime value compiler has to create max number (5) of functions. But it able to throw away recursive calls and create a jump table (or switch) to each function with different number of arguments.
https://godbolt.org/z/TbffPzYoP

@talybin
Copy link
Author

talybin commented Jun 9, 2024

Works only with variadic number of arguments for visitor.

@talybin
Copy link
Author

talybin commented Jun 9, 2024

std::vector to args... version

namespace detail
{
    template <class T, class F, size_t... I>
    decltype(auto) visit(const std::vector<T>& v, F&& cb, std::index_sequence<I...>) {
        return std::forward<F>(cb)(v[I]...);
    }
}

template <size_t MAX_SIZE = 5, size_t I = 0, class T, class F>
decltype(detail::visit(std::vector<T>(), std::declval<F>(), std::make_index_sequence<I>()))
visit(const std::vector<T>& v, F&& cb)
{
    if constexpr (I < MAX_SIZE) {
        if (v.size() == I)
            return detail::visit(v, std::forward<F>(cb), std::make_index_sequence<I>{});
        return visit<MAX_SIZE, I + 1>(v, std::forward<F>(cb));
    }
    else
        throw v.size();
}

int main()
{
    try {
        // 10 is larger than 5, still compiler
        // able to see, that max allowed nr is 5
        std::srand(std::time(nullptr));
        std::vector<int> v(std::rand() % 10, 2042);

        printf("try to create %lu arguments...\n", v.size());

        // MAX_SIZE can be increased with visit<N>(cnt, ...)
        auto ret = visit(v, [](auto... args) {
            (printf("%d, ", args), ...);
            printf("nr args: %lu\n", sizeof...(args));
            return 42;
        });

        printf("return value: %d\n", ret);
    }
    catch (size_t nr) {
        printf("error: %lu argument do not fit in MAX_SIZE\n", nr);
    }
}

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment