Infinite ranges

[ericniebler]

The TS is inconsistent wrt infinite ranges. It requires the end to be reachable in a finite number of increments, but it uses unreachable as a sentinel. It also has ye olde problem of difference type overflow for truly infinite ranges. Clean this up for the IS.

[ericniebler]

Think about what happens when a pointer is used along with unreachable to form a range. That isn't technically a valid range because incrementing the iterator will eventually advance past the end of the range. Nevertheless, it can be a useful technique; e.g., when migrating away from the use of a (now deprecated) three-legged algorithm, without incurring the perf hit of an extra pointer comparison in the loop. So long as the pointer never gets advanced past the end of its range, that usage should be permitted.

[CaseyCarter]

Some pertinent if overspecific info I'm leaving here for later:

As specified, SizedSentinel is not satisfiable by values of iterators in a cycle of size greater than 1. Consider a hypothetical view alternating_view such that when r is alternating_view(x, y), *next(begin(r), n) is x if n is even, and y otherwise. This view has two distinct iterator values: one that denotes x, and one that denotes y. The range as a DAG looks like:

           <-
begin -> x    y
           ->

Note the cycle of length two in the iterator values. Let:

auto r = alternating_view(0, 1);
using I = decltype(begin(r));
I i0 = begin(r);
I i1 = next(i0, 1);

Since next(i0, 1) == i1 && next(i1, 1) == i0, we have distance(i0, i1) == 1 && distance(i1, i0) == 1. If we wanted to satisfy SizedSentinel<I, I>, what should i1 - i0 be? Recall the specification of SizedSentinel is (https://timsong-cpp.github.io/cppwp/ranges-ts/iterators.sizedsentinel):

template <class S, class I>
concept bool SizedSentinel = Sentinel<S, I> &&
  !disable_sized_sentinel<remove_cv_t<S>, remove_cv_t<I>> &&
  requires(const I& i, const S& s) {
    { s - i } -> Same<difference_type_t<I>>&&;
    { i - s } -> Same<difference_type_t<I>>&&;
  };

2 Let i be an iterator of type I, and s a sentinel of type S such that [i,s) denotes a range. Let N be the smallest number of applications of ++i necessary to make bool(i == s) be true. SizedSentinel<S, I> is satisfied only if: (2.1) — If N is representable by difference_type_t<I>, then s - i is well-defined and equals N. (2.2) — If −N is representable by difference_type_t<I>, then i - s is well-defined and equals −N.

Consider the range [i0, i1). Since 1 is the smallest number of applications of ++i0 necessary to make bool(i0 == i1) true, we have that i1 - i0 == 1 (presumably 1 is representable by difference_type_t<I>). By 2.2 above, we also have that i0 - i1 == -1 (ditto representable). But then consider the range [i1, i0). Again, one application of ++i1 suffices to make bool(i1 == i0) be true, so both i0 - i1 == 1 and i1 - i0 == -1 must hold. Neither i1 - i0 nor i0 - i1 can simultaneously equal both 1 and -1, so we cannot possibly satisfy SizedSentinel<I, I>.

Note that this argument doesn't apply for cycles of size 1, such as range-v3's view::repeat, since 0 == -0.

EDIT: This may be evidence of a class of iterators "between" Bidirectional and RandomAccess for which advance can be O(1), but distance cannot. Or it may be evidence that negative differences simply don't make sense for cyclic ranges.

[ericniebler]

This may be evidence of a class of iterators "between" Bidirectional and RandomAccess

I see it as evidence that cyclic iterators are fundamentally broken.