recursive application of C++20 range adaptor causes a compile time infinite loop

Question

The ranges library in C++20 supports the expression

auto view = r | std::views::drop(n);

to remove the first n elements of a range r with the range adaptor drop.

However if I recursively drop elements from a range, the compiler enters an infinite loop.

---

Minimal working example: (takes infinite time to compile in GCC 10)

#include <ranges>
#include <iostream>
#include <array>
#include <string>

using namespace std;

template<ranges::range T>
void printCombinations(T values) {
    if(values.empty())
        return;

    auto tail = values | views::drop(1);

    for(auto val : tail)
        cout << values.front() << " " << val << endl;

    printCombinations(tail);
}

int main() {
    auto range1 = array<int, 4> { 1, 2, 3, 4 };
    printCombinations(range1);
    cout << endl;

    string range2 = "abc";
    printCombinations(range2);
    cout << endl;
}

expected output:

1 2
1 3
1 4
2 3
2 4
3 4

a b
a c
b c

Why does this take infinite time to compile and how should I resolve the problem?

Answer 1

Let's take a look at the string case (just because that type is shorter) and manually examine the call stack.

printCombinations(range2) calls printCombinations<string>. The function recursively calls itself with tail. What's the type of tail? That's drop_view<ref_view<string>>. So we call printCombinations<drop_view<ref_view<string>>>. Straightforward so far.

Now, we again recursively call ourselves with tail. What's the type of tail now? Well, we just wrap. It's drop_view<drop_view<ref_view<string>>>. And then we recurse again with drop_view<drop_view<drop_view<ref_view<string>>>>. And then we recurse again with drop_view<drop_view<drop_view<drop_view<ref_view<string>>>>>. And so forth, infinitely, until the compiler explodes.

Can we fix this by maintaining the same algorithm? Actually, yes. P1739 was about reducing this kind of template instantiation bloat (although it didn't have an example as amusing as this one). And so drop_view has a few special cases for views that it recognizes and won't rewrap. The type of "hello"sv | views::drop(1) is still string_view, not drop_view<string_view>. So printCombinations(string_view(range2)) should only generate a single template instantiation.

But it looks like libstdc++ doesn't implement this feature yet. So you can either implement it manually (but only trafficking in, say, subrange) or abandon the recursive approach here.