P2406R0
Fix `counted_iterator` interaction with input iterators

1. Revision History

r0: initial revision

2. Intro

3. Problem description

#include <ranges>
#include <iostream>
 
namespace rv = std::views;
 
int main() {
    for (auto i  : rv::iota(0)
            | rv::filter([](auto i) { return i < 10; })
            | rv::take(10))
        std::cout << i << '\n';
}

Compiler explorer gets a timeout when trying to run this simple example, instead of printing the numbers from 0 to 9. Running the same code locally, it runs for very long time. Tracking the roots of the issue, the problem is that take uses counted_iterator when the range isn’t random_access and counted_iterator increments the internal iterator even if the counter has reached the requested count. In this case, the filter never returns when trying to increment it once again (at least not until iota reaches the UB case of signed overflow).

The example above is just for illustration, but we can think about cases where it isn’t clear for the user how many items the filter is expected to return, so limiting the output count with take becomes dangerous and results in unexpected behavior.

The problem mentioned in the intro is one that actually describes a filter that return exactly 11 elements, so trying to use take(11) on it means the program never ends even while it got 11 elements already.

3.1. Counter argument

It still leaves the cases that there is a huge performance penalty on incrementing the iterator one additional time, but those are maybe considered less interesting.

3.2. The real problem

#include <ranges>
#include <iostream>
#include <sstream>
#include <cassert>
 
namespace rn = std::ranges;
namespace rv = rn::views;
 
int main()
{
    auto iss = std::istringstream("0 1 2");
    for (auto i : rn::istream_view<int>(iss)
                  | rv::take(1))
        std::cout << i << '\n';
    auto i = 0;
    iss >> i;
    std::cout << i << std::endl; // flush it in case the assert fails
    assert(i == 1); // FAILS, i == 2
}

It means that one can’t use ranges when parsing input, for example.

4. Design of suggested solution

4.1. The main changes

4.2. random_­access_­iterator case kept as-is

To reduce the amount of changes required, we keep the current behavior for random_­access_­iterator case, so we don’t have to touch the additional operators defined only for this category. The rational behind it is that for random_­access_­iterator case we can expect the view to either have all the items ready or able to compute all of them efficiently, so it doesn’t suffer from this issue.

4.3. Open question: Constructing with 0 length

We don’t have a good solution for the case that user constructs counted_iterator with 0 as argument for length. This puts it in an inconsistent internal state, as the next operations will be base() or --, and those expect the iterator to be one step back, with the changes suggested here.

Please note that base() and -- are the only operations involving the state of the internal iterator and still legal for counted_iterator constructed with n==0;

Option 1: Require that if n==0, i must be decrementable, and actually decrement it in the c-tor. (This option assumes the only reason to create such an counted_iteraor is to decrement it anyway.)

Option 2: Require that if n==0, i must be "the one before" the actual iterator (leaving it to the user to decide how to handle, and if neither -- nor base() are ever called on it, it doesn’t matter what the user does).

Option 3: Mark this case internally (e.g. with length=-1) and handle specially when decrementing (length "jumps" to 1 after decrementing the internal iterator). Please note that base() doesn’t need any special handling here.

5. Proposed Wording

Note: Wording doesn’t include any of the options suggested for the c-tor.

Under 23.5.6.3 [counted.iter.access]:

constexpr const I& base() const &;
requires random_­access_­iterator<I>;
Effects: Equivalent to: return current;

constexpr I base() &&;
requires random_­access_­iterator<I>;
Returns: std​::​move(current).

Under 23.5.6.5 [counted.iter.nav]:

constexpr counted_iterator& operator++();
requires random_­access_­iterator<I>;
Preconditions: length > 0.
Effects: Equivalent to:
++current;
--length;
return *this;

decltype(auto) operator++(int);
Preconditions: length > 0.
--length;
try { return current++; }
try { return length ? current++ : current; }
catch(...) { ++length; throw; }

constexpr counted_iterator operator++(int)
requires forward_­iterator<I>;
Effects: Equivalent to:
counted_iterator tmp = *this;
++*this;
return tmp;

constexpr counted_iterator& operator--()
requires random_­access_­iterator<I>;
Effects: Equivalent to:
--current;
++length;
return *this;

6. Effect on current state

In such a case, we suggest to consider requiring forward_or_output_iterator for counted_iterator, as it always does the wrong thing for input_iterator if it doesn’t reach the end of the input (while for forward_iterator and bidirectional_­iterator it’s mainly just a possible performance issue and rarely an infinite loop, as mentioned, and for output_iterator the incrementing is usually no-op).

At the very least, we have to warn users against using counted_iterator and its consumers with input_iterator.

7. Appendix