1. Revision History
r1: Improving many parts, following feedback from Inbal Levi and from Reddit users
r0: initial revision
2. Intro
Project Euler is a project with many mathematical-related questions that are intended to encourage the reader to write a small program to compute the result. In this case, one of the problems there, no. 37 [EULER], helped reveal a pitfall coming from the definition ofstd :: counted_iterator
.
3. Problem description
3.1. Range with the exact number of items
Look at this example code [CE-FILTER]:
#include <ranges>#include <iostream>namespace rv = std :: views ; int main () { for ( auto i : rv :: iota ( 0 ) | rv :: filter ([]( auto i ) { return i < 11 ; }) | rv :: take ( 11 )) std :: cout << i << '\n' ; }
Compiler explorer gets a timeout when trying to run this simple example, instead
of printing the numbers from 0 to 10. Running the same code locally, it runs for
very long time. Tracking the roots of the issue, the problem is that
uses
when the range isn’t
and
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
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
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
on it means the program
never ends even while it got 11 elements already.
It means
isn’t usable on ranges that have the exact count of items (and
so is
when wrapping around an iterator for such a range).
3.2. input_iterator
case
Even more common problem is when using input ranges, e.g. basic_istream_view
.
In these cases, advancing the internal iterator when reaching the count means
eating an additional input that can’t be retrieved again later, or hanging
forever if no additional input exists and the stream isn’t closed. For example [CE-ISTREAM]:
#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.
Seems like this was discussed in [range-v3-issue57], and there was no decision what is the right solution.
4. Current behavior is what the standard mandates
Under 23.5.6.5 [counted.iter.nav], the standard defines the behavior of
for
as:
Effects: Equivalent to:
It means that even when
becomes 0, the internal iterator is
incremented, thus consuming an additional item from the range, and causing the
effects mentioned above for input iterator case or when
on the internal
iterator is costly (or never returns).
5. Desired behavior
As long as
is valid (not equal to
), it
must never try to access more than
items (when
is the given count). If
the range doesn’t have
items, the behavior is kept as is, i.e. it isn’t
defined (
might hang forever or access things that shouldn’t be
accessed etc.).
6. Naive design of the solution
Basically, what is required to implement the desired behavior is changing the
behavior of
operators around 0 length so it doesn’t increment
the internal iterator when reaching 0 length.
7. Designs that were considered (and rejected)
7.1. Don’t increment the underlying iterator until really required
We could change
internal behavior to increment the underlying
iterator only on first dereference. This can’t work as copying
of non-forward iterator (that wasn’t dereferenced yet for the
current item) and then dereferencing one of them resulted with invalidation of
the other one. Even if we are willing to make
non-copyable,
making the dereference operator non-const only or making the internal iterator
brings with it various other usability and correctness issues.
7.2. Fix counted_iterator
behavior around 0
Instead of introducing new type,
, which is almost like
but with some changes, we tried to apply similar changes to
itself. This has been proven to be impossible, even if the
changes can be done in ABI compatible way. For example, there is no sane way to
fix the c-tor that takes iterator and count, when the count is 0. Here are the
details:
allows constructing with
as argument for length. If we
change
operators to behave similarly to what we propose for
, this constructor puts the iterator in an inconsistent
internal state, as the underlying iterator is expected to be "one step back".
Please note that
and
are the only operations involving the state
of the internal iterator and still legal for
constructed with
.
The options we considered and rejected are:
Option 1: Require that if
,
must be decrementable, and actually
decrement it in the c-tor. Please note that this obviously works only for
. Other kind of iterators can be left as UB, or just
advice against calling
on the resulted
(which
doesn’t sound correct, blocking a basic operation like
).
This option assumes the only reason to create such an
is to
decrement it later, so we always expect the given iterator to be decrementable.
Obviously, we can’t really assume it. The next operation could be to test for
the value of
before doing anything else and do nothing in the
case.
Option 2: Require that if
,
must be "the one before" the actual
iterator (leaving it to the user to decide how to handle, and if neither
nor
are ever called on it, it doesn’t matter what the user does). This
option changes behavior of existing code so it’s isn’t relevant either.
Option 3: Mark this case internally (e.g. with
or a boolean flag)
and handle specially when decrementing (
"jumps" to
after
decrementing the internal iterator). Please note that both the counter/flag and
the internal iterator must be mutable (to be changed on first access to
). Also, if -1 is used, instead of a separated flag, comparison
operators have to consider this case too. Using a flag, OTOH, will probably push
for separated specialization of the whole class, so for random-access iterators
this member will not exist. This still doesn’t solve the problem of invalidation
of one copy when
is called on the other one. It also breaks ABI.
Another problem is that keeping the current behavior of
requires
to be non-const (obviously undesired for read-only method) or to start
returning by-value, preventing the usage of
on move-only
iterators [LWG3391].
Our conclusion is that
can’t be fixed to handle all cases.
8. P2578 and this paper
We propose a fix constructed from 2 parts:
-
Block the obviously wrong usages from
(most usages with input iterators)counted_iterator -
Create new tools that behave better in these cases
To make it easier to discuss and adopt each part by itself, if needed, we
separated them to 2 papers. [P2578] introduces
concept and blocks usage of
with input (non-forward)
iterators that aren’t
. This paper is about the
second part of the solution and builds on the concept introduced with P2578.
9. Design of the proposed solution
9.1. The main changes
We propose adding a new iterator type,
. This type
behaves similarly to
, with changes to its operator definition
around 0 length so it doesn’t increment the internal iterator when reaching 0
length, and as a result doesn’t decrement it when getting back from 0 to 1
length. This requires changing
behavior too.
Additionally, this requires adding
and
that
uses the new iterator instead of
.
9.2. Why lazy_take
instead of fixing take
?
We could have change
to use
when constructed with
input (non lazy) range. Besides ABI considerations, we find it wrong if
used to return one type (
) and now will start returning a
different one,
, as this is source-breaking change.
Additionally, as demonstrated above, there are cases where the user wants using
on forward iterators too, but this is something that
only the user know and we can’t automatically detect and decide on behalf of
them. We can’t change all cases of
to use
, due to
the differences in behavior both for lazy input iterators and forward iterators
(that are not random access), as described below.
We aren’t happy with the additional burden on teachability, but we believe in
most cases users can just use
and it does The Right Thing. The only
point where users must be aware of it is when they use
method, which we
expect to be quite advance usage in general.
9.3. random_access_iterator
case kept as-is
To reduce the amount of changes required, we keep the current behavior for
case, so we don’t have to touch the additional
operators defined only for this category. The rational behind it is that for
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 an issue similar to the one
might have.
9.4. Discussing base ()
changes
To keep
as
member, its behavior is
defined such when
it returns the "one before" iterator. If we
want it to return the actual end, it means we must advance the underlying
iterator first. This doesn’t allow
to be
, invalidates other
copies of the iterator and (depending on the way it’s defined) might even make
calling
twice UB. This is why we propose the behavior just described.
As mentioned, for
we do increment the underlying
iterator when
becomes 0 to simplify the definition of other operators
(e.g.
). To keep
functionality consistent for all
s, we return the
of the underlying iterator in
this case. As a result,
returns by value. As
mentioned in [LWG3391], this prevents using it with move-only iterators.
Please note that it’s OK to call
on the underlying iterator, as
can’t be created with
, so we are sure
there is a prev.
To rectify this, tools built on
(e.g.
) must
access the underlying iterator directly, instead of using
. Users who
need to access
, can choose between using
with their move-only
iterators (if the behavior is right, i.e. they know there is an additional
avaialble element at the end, they are willing to throw away the rest of the
range anyway and the iterator is lazy) or creating another iterator from the
same source they gave to
(as the internal state has changed to point
to the last item used by
). Please note that creating such an
iterator in the middle is impossible (it would invalidate the underlying
iterator of
), but as only the current element is available in such
ranges, it’s available already from what
returns in the current
iteration.
9.5. Constructor with count
Following the discussion above about the c-tor that takes count, we disallow
creating
with
. To make it easier to use it with
pipelines, we might want to explicitly allow it, but disallow any operation on
such an iterator that access the underlying iterator or comparing to another
iterator (effectively allowing only
and comparing to sentinel).
10. Proposed Wording
Duplicate "Counted iterators" section (25.5.6 [iterators.counted]), renaming it to "Lazy counted iterators" (adding 25.5.x [iterators.lazy.counted]), with the following differences (the wording here is done against the suggested changes in P2578R0):
Every occurence of
becomes
Every stable reference is prefixed with "lazy."
Under 25.5.x.1 [lazy.counted.iterator]:
Under 25.5.x.2 [lazy.counted.iter.const]:
Preconditions:
.
Under 25.5.x.3 [lazy.counted.iter.access]:
Effects: Equivalent to:
constexpr I base () const & ;
requires random_ access_ iterator < I > ;
Effects: Equivalent to:
return length ? current : std :: ranges :: prev ( current );
Returns:
.
constexpr I base () && ;
requires random_ access_ iterator < I > ;
Returns:
length ? std :: move ( current ) : std :: ranges :: prev ( current )
.
Under 23.5.6.5 [counted.iter.nav]:
constexpr lazy_counted_iterator & operator ++ ();
Preconditions:
length > 0
.Effects: Equivalent to:
if ( length > 1 ) ++ current ;
-- length ;
return * this ;
Preconditions:
.
Effects: Equivalent to:
Preconditions:
.
Effects: Equivalent to:
Effects: Equivalent to:
constexpr lazy_counted_iterator & operator -- ()
requires bidirectional_ iterator < I > ;
Effects: Equivalent to:
if ( length ) -- current ;
++ length ;
return * this ;
Effects: Equivalent to:
11. TODO
Missing wording for
and
and adding more
descriptions to
(e.g. behavior of
).
12. Note about optimization
It’s interesting to note that with any level of optimization enabled (including- Og
!), gcc is able to "fix the issue" [CE-OPT] for the filter+take case (but
not for input_iterator
, of course). It’s maybe even more interesting to see
the mentioned optimization is not an optimizer bug, and when the filter will
never return another number, it doesn’t change the behavior [CE-OPT2].
13. Acknowledgements
Many thanks to the Israeli NB members for their feedback and support, in particular Inbal Levi, Dvir Yitzchaki and Dan Raviv. Thanks r/cpp Reddit users for their feedback on P2406R0.