Issue 3344: advance(i, most-negative) and prev(i, most-negative)

3344. `advance(i, most-negative)` and `prev(i, most-negative)`

Section: 24.4.3 [iterator.operations], 24.4.4.2 [range.iter.op.advance] Status: New Submitter: Casey Carter Opened: 2019-11-22 Last modified: 2019-12-07

Priority: 3

View other active issues in [iterator.operations].

View all other issues in [iterator.operations].

View all issues with New status.

Discussion:

ranges::advance (24.4.4.2 [range.iter.op.advance]) and std::advance (24.4.3 [iterator.operations]) can be called with a negative count n when the iterator argument i models bidirectional_iterator (respectively, meets the Cpp17BidirectionalIterator requirements). In this case, they are specified to "decrement i by -n". If n is the most-negative value of a signed integral type, the expression -n has undefined behavior. This UB is unfortunate given that typical implementations never actually form the expression -n. It's nonsensical to describe the effects of a function in terms of an expression with undefined behavior, so we should either define the behavior or exclude this case via precondition.

ranges::prev() and std::prev (24.4.3 [iterator.operations]) have a similar problem: prev(i, n) is equivalent to:

advance(i, -n); 
return i;

which has undefined behavior when n is numeric_limits<T>::min() where T is iter_difference_t<decltype(i)> (for ranges::prev) or some signed integral type (for std::prev). There is an implicit precondition here thanks to "Effects: Equivalent to" since the equivalent code has a precondition that n is not a most-negative value, so this wording is not defective. We could, however, define behavior for prev regardless of the value of n by duplicating the specification of advance and inverting the "direction" of the operations. We should consider doing so.

[2019-12-07 Issue Prioritization]

Priority to 3 after reflector discussion.

Proposed resolution:

This wording is relative to N4835.

[Drafting note: I've chosen to provide wording for the conservative "define behavior for advance and leave prev as status quo" middle ground.
The occurrences of "|" in the below are math-font vertical bars (indicating absolute value). I've changed both positive and negative cases for consistency of presentation. ]

Modify 24.4.3 [iterator.operations] as indicated:
```
template<class InputIterator, class Distance>
  constexpr void advance(InputIterator& i, Distance n);
```
-2- Expects: n is negative only for bidirectional iterators.
-3- Effects: Increments i by |n| if n is non-negative, and decrements i by -|n| otherwise.
Modify 24.4.4.2 [range.iter.op.advance] as indicated:
```
template<input_or_output_iterator I>
  constexpr void ranges::advance(I& i, iter_difference_t<I> n);
```
-1- Expects: If I does not model bidirectional_iterator, n is not negative.
-2- Effects:
1. (2.1) — If I models random_access_iterator, equivalent to i += n.
2. (2.2) — Otherwise, if n is non-negative, increments i by |n|.
3. (2.3) — Otherwise, decrements i by -|n|.
[…]
```
template<input_or_output_iterator I, sentinel_for<I> S>
  constexpr iter_difference_t<I> ranges::advance(I& i, iter_difference_t<I> n, S bound);
```
-5- Expects: […]
-6- Effects:
1. (6.1) — If S and I model sized_sentinel_for<S, I>:
  1. (6.1.1) — If |n| ≥ |bound - i|, equivalent to ranges::advance(i, bound).:
  2. (6.1.2) — Otherwise, equivalent to ranges::advance(i, n).
2. (6.2) — Otherwise,
  1. (6.2.1) — if n is non-negative, while bool(i != bound) is true, increments i but at most |n| times.:
  2. (6.2.2) — Otherwise, while bool(i != bound) is true, decrements i but at most -|n| times.

3344. advance(i, most-negative) and prev(i, most-negative)

3344. `advance(i, most-negative)` and `prev(i, most-negative)`