Compile-time sizes for range adaptors

by Jonathan

This blog post was first published at think-cell's developer blog. Subscribe there to stay up-to-date!

In my previous blog post, we’ve discussed the static constexpr std::integral_constant idiom to specify the size of a range at compile-time. Unlike the standard, our (think-cell’s) ranges library at think-cell already supports compile-time sizes natively, so I was eager to try the idiom there and see how it works out in practice.

namespace tc
{
    template <typename Rng>
    constexpr auto size(Rng&& rng); // runtime-size of a range, like std::ranges::size

    template <typename Rng> requires tc::has_constexpr_size<Rng>
    constexpr auto constexpr_size = …; // compile-time size of a range given its type
}

We have two ways to query the size: One size function that returns an integer like std::ranges::size, and one constexpr_size variable template that determines the compile-time size given the type of the range. In the latter case, we can directly apply the idiom by making constexpr_size a variable template of std::integral_constant type. That way the user has full flexibility in the interface:

template <typename Rng>
void foo(Rng&& rng)
{
    std::size_t runtime_size = tc::size(rng);
    constexpr std::size_t compile_time_size = tc::constexpr_size<Rng>();
    constexpr std::integral_constant compile_time_size_constant = tc::constexpr_size<Rng>;
}

That leaves the implementation of tc::constexpr_size. The status quo was using trait specializations. Note that providing an implementation for tc::constexpr_size automatically supports tc::size as well.

template <typename Rng>
struct constexpr_size_impl; // no definition

template <typename Rng>
constexpr auto constexpr_size = constexpr_size_impl<std::remove_cvref_t<Rng>>{};

// Real implementation delegates all tuple-like types to std::tuple_size, omitted here.
template <typename T, std::size_t N>
struct constexpr_size_impl<std::array<T, N>> : std::integral_constant<std::size_t, N> {};

// more specializations

Can we use static constexpr std::integral_constant in the implementation?

I wanted to change it to somehow leverage the static constexpr std::integral_constant idiom instead. That is, the implementation of tc::constexpr_size checks for the well-formedness of Rng::size as the default implementation. We then only need trait specializations to provide implementations for types we can’t control like std::array. While it worked great for range factories where the size is always known, like std::array, tc::empty_range, or tc::all_values<Enum>, it does not work for range adaptors.

Consider tc::transform_adaptor (our std::ranges::transform_view), which returns a range whose elements are the underlying range elements transformed by applying a function. Crucially, it does not change the size of the range: If the underlying range rng has N elements, tc::transform(rng, fn) also has N elements. Thus we want to forward the size properties of rng transparently:

A naive attempt using static constexpr std::integral_constant for tc::constexpr_size can look like this:

template <typename Rng, typename Fn>
struct transform_adaptor
{
    // for tc::constexpr_size and tc::size
    static constexpr std::integral_constant size = tc::constexpr_size<Rng>; // somehow constrained

    // for tc::size
    constexpr std::size_t size() const
        requires tc::has_size<Rng> && (!tc::has_constexpr_size<Rng>)
    {
        return tc::size(base_rng());
    }
};

The issue here is the “somehow constrained” comment: static member variables, unlike functions, cannot be constrained, nor overloaded with member functions. So we’d have to conditionally inherit the constexpr size only if Rng has a constexpr size, which is ugly.

We also don’t have any benefit from using static constexpr std::integral_constant—users shouldn’t directly call rng.size(), they should use tc::size or tc::constexpr_size instead. So there is no upside to using static constexpr std::integral_constant in the implementation.

Conditionally returning std::integral_constant from .size()

So let’s just have a single size() function that returns either std::size_t or std::integral_constant, the “most constexpr” version of the range size. This approach continues to work for range factories, but now we can also write our adaptors:

template <typename Rng, typename Fn>
struct transform_adaptor
{
    // for tc::size and tc::constexpr_size
    constexpr auto size() const& requires tc::has_size<Rng>
    {
        if constexpr (tc::has_constexpr_size<Rng>)
          return tc::constexpr_size<Rng>;
        else
          return tc::size(base_rng());
    }
};

The corresponding specialization of tc::constexpr_size calls the function inside decltype to get the result:

// Rng has a size function that returns an integral_constant.
template <typename Rng> requires requires { decltype(std::declval<Rng&>().size())::value; }
struct constexpr_size_impl<Rng> : decltype(std::declval<Rng&>().size()) {};

The runtime version tc::size doesn’t need to be changed, as the range continues to have a .size() member function that returns the size, just possible encoded in the return type itself.

Avoiding code duplication

While the approach is nice, there is a bit of code duplication. This becomes especially apparent for more complex ranges like tc::concat_adaptor, whose size is the sum of all sub-range sizes:

template <typename ... Rng>
struct concat_adaptor
{
    constexpr auto size() const
        requires (tc::has_size<Rng> && ...)
    {
        if constexpr ((tc::has_constexpr_size<Rng> && ...))
            return std::integral_constant<std::size_t, (tc::constexpr_size<Rng>() + ...)>{};
        else
            return std::apply([](auto const& ... base_rng) {
              return (tc::size(base_rng) + ...);
            }, base_rng_tuple);
    }
};

We are computing the same value twice: once as a std::integral_constant, and once as std::size_t. We can unify it by splitting the size computation and the result wrapping using a helper function:

template <auto Fn, typename ... Rng>
constexpr auto compute_range_adaptor_size(Rng&&... rng)
{
    if constexpr ((tc::has_constexpr_size<Rng> && ...))
    {
        auto constexpr value = Fn(tc::constexpr_size<Rng>()...);
        return std::integral_constant<std::size_t, value>{};
    } else
    {
        auto const value = Fn(tc::size(std::forward<Rng>(rng))...);
        return value;
    }
}

template <typename ... Rng>
struct concat_adaptor
{
    constexpr auto size() const
        requires (tc::has_size<Rng> && ...)
    {
        return std::apply([](auto const& ... base_rng) {
            return tc::compute_range_adaptor_size<[](auto const ... n) {
                return (n + ...);
            }>(base_rng...);
        }, base_rng_tuple);
    }
};

The helper function compute_range_adaptor_size() takes all sub-ranges and computes the most constexpr version of their sizes. This is then passed to a lambda to compute the derived size, and returned in the most constexpr way. Note that the lambda has to be passed as a non-type template parameter, so we can use its result in a constexpr context.

concat_adaptor::size() then just needs to call compute_range_adaptor_size() with an appropriate lambda and the subranges, and it will automatically work.

Conclusion

The size of a range adaptor can be available at compile-time or runtime. We can forward that information easily by returning std::integral_constant whenever possible, the most constexpr version of the size.

The pattern can be applied to more situations. For example, I’ve recently added support to tc::filter predicates that return std::true_type or std::false_type. That way, we can filter e.g. a std::tuple by type with the same mechanism used to filter a runtime range by value.