advance(i, most-negative) and prev(i, most-negative)
Casey Carter

Created on 2019-11-22.00:00:00 last changed 9 months ago


Date: 2019-12-07.13:45:41

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. ]

  1. Modify [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.

  2. Modify [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.

Date: 2019-12-07.00:00:00

[ 2019-12-07 Issue Prioritization ]

Priority to 3 after reflector discussion.

Date: 2019-11-22.00:00:00

ranges::advance ([range.iter.op.advance]) and std::advance ([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 ([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.

Date User Action Args
2019-12-07 13:45:41adminsetmessages: + msg10859
2019-11-23 18:16:35adminsetmessages: + msg10847
2019-11-22 00:00:00admincreate