CODEWITHSUNDEEP
c++stlc++20std-ranges
ProgrammierPatrick
ProgrammierPatrick

Reputation: 123

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

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?

Upvotes: 9

Views: 536

Answers (2)

Gaurish Gangwar
Gaurish Gangwar

Reputation: 444

Although this is very old question, but I came across this annoying bug/(or maybe feature) today, and this is how I solved it without much change to the original code.

#include <ranges>
#include <iostream>
#include <array>
#include <string>
#include <span>   /////// <------ added this

using namespace std;

template<ranges::range T>
void printCombinations(T values_) {  // <--- Changed values to values_
    auto values = std::span(values_);  // <--- defined values here
    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;
}

By creating span, we make the typename of the variable simply span instead of deeply nested typenames as shown in the accepted answer.

You can check it here on goldbolt that it works exactly as expected.

UPDATE: You can replace the use of std::span with std::ranges::subrange and it will cover even more cases. For example, std::span does not work with std::ranges::views::reverse.

Upvotes: 1

Barry
Barry

Reputation: 303057

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.

Upvotes: 8

Related Questions