Issue 2687: {inclusive,exclusive}

This page is a snapshot from the LWG issues list, see the Library Active Issues List for more information and the meaning of C++17 status.

2687. `{inclusive,exclusive}_scan` misspecified

Section: 26.10.8 [exclusive.scan], 26.10.9 [inclusive.scan], 26.10.10 [transform.exclusive.scan], 26.10.11 [transform.inclusive.scan] Status: C++17 Submitter: Tim Song Opened: 2016-03-21 Last modified: 2017-07-30

Priority: 1

View all other issues in [exclusive.scan].

View all issues with C++17 status.

Discussion:

When P0024R2 changed the description of {inclusive,exclusive}_scan (and the transform_ version), it seems to have introduced an off-by-one error. Consider what N4582 26.10.9 [inclusive.scan]/2 says of inclusive_scan:

Effects: Assigns through each iterator i in [result, result + (last - first)) the value of

GENERALIZED_NONCOMMUTATIVE_SUM(binary_op, init, *j, ...) for every j in [first, first + (i - result)) if init is provided, or

GENERALIZED_NONCOMMUTATIVE_SUM(binary_op, *j, ...) for every j in [first, first + (i - result)) otherwise.

When i == result, i - result = 0, so the range [first, first + (i - result)) is [first, first) — which is empty. Thus according to the specification, we should assign GENERALIZED_NONCOMMUTATIVE_SUM(binary_op, init) if init is provided, or GENERALIZED_NONCOMMUTATIVE_SUM(binary_op) otherwise, which doesn't seem "inclusive" — and isn't even defined in the second case.

The parallelism TS's version uses GENERALIZED_NONCOMMUTATIVE_SUM(binary_op, *first, ..., *(first + (i - result))) — which is a closed range, not a half-open one.

Similar issues affect exclusive_scan, transform_inclusive_scan, and transform_exclusive_scan.

[2016-06 Oulu]

Voted to Ready 11-0 Tuesday evening in Oulu

Proposed resolution:

This wording is relative to N4582.

Edit 26.10.8 [exclusive.scan]/2 as indicated:

[Drafting note: when i is result, [first, first + (i - result)) is an empty range, so the value to be assigned reduces to GENERALIZED_NONCOMMUTATIVE_SUM(binary_op, init), which is init, so there's no need to special case this.]
```
template<class InputIterator, class OutputIterator, class T, class BinaryOperation>
  OutputIterator exclusive_scan(InputIterator first, InputIterator last,
                                OutputIterator result,
                                T init, BinaryOperation binary_op);
```
-2- Effects: Assigns through each iterator i in [result, result + (last - first)) the value of GENERALIZED_NONCOMMUTATIVE_SUM(binary_op, init, *j, ...) for every j in [first, first + (i - result)).
- ~~init, if i is result, otherwise~~
- ~~GENERALIZED_NONCOMMUTATIVE_SUM(binary_op, init, *j, ...) for every j in [first, first + (i - result) - 1).~~

Edit 26.10.9 [inclusive.scan]/2 as indicated:

template<class InputIterator, class OutputIterator, class BinaryOperation>
  OutputIterator inclusive_scan(InputIterator first, InputIterator last,
                                OutputIterator result,
                                BinaryOperation binary_op);
template<class InputIterator, class OutputIterator, class BinaryOperation>
  OutputIterator inclusive_scan(InputIterator first, InputIterator last,
                                OutputIterator result,
                                BinaryOperation binary_op, T init);
-2- Effects: Assigns through each iterator i in [result, result + (last - first)) the value of

GENERALIZED_NONCOMMUTATIVE_SUM(binary_op, init, *j, ...) for every j in [first, first + (i - result + 1)) if init is provided, or

GENERALIZED_NONCOMMUTATIVE_SUM(binary_op, *j, ...) for every j in [first, first + (i - result + 1)) otherwise.

Edit 26.10.10 [transform.exclusive.scan]/1 as indicated:

template<class InputIterator, class OutputIterator,
         class UnaryOperation,
         class T, class BinaryOperation>
  OutputIterator transform_exclusive_scan(InputIterator first, InputIterator last,
                                          OutputIterator result,
                                          UnaryOperation unary_op,
                                          T init, BinaryOperation binary_op);
-1- Effects: Assigns through each iterator i in [result, result + (last - first)) the value of GENERALIZED_NONCOMMUTATIVE_SUM(binary_op, init, unary_op(*j), ...) for every j in [first, first + (i - result)).

~~init, if i is result, otherwise~~

~~GENERALIZED_NONCOMMUTATIVE_SUM(binary_op, init, unary_op(*j), ...) for every j in [first, first + (i - result) - 1).~~

Edit 26.10.11 [transform.inclusive.scan]/1 as indicated:

template<class InputIterator, class OutputIterator,
         class UnaryOperation,
         class BinaryOperation>
  OutputIterator transform_inclusive_scan(InputIterator first, InputIterator last,
                                          OutputIterator result,
                                          UnaryOperation unary_op,
                                          BinaryOperation binary_op);
template<class InputIterator, class OutputIterator,
         class UnaryOperation,
         class BinaryOperation, class T>
  OutputIterator transform_inclusive_scan(InputIterator first, InputIterator last,
                                          OutputIterator result,
                                          UnaryOperation unary_op,
                                          BinaryOperation binary_op, T init);

-1- Effects: Assigns through each iterator i in [result, result + (last - first)) the value of

GENERALIZED_NONCOMMUTATIVE_SUM(binary_op, init, unary_op(*j), ...) for every j in [first, first + (i - result + 1)) if init is provided, or

GENERALIZED_NONCOMMUTATIVE_SUM(binary_op, unary_op(*j), ...) for every j in [first, first + (i - result + 1)) otherwise.

2687. {inclusive,exclusive}_scan misspecified

2687. `{inclusive,exclusive}_scan` misspecified