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.

1. 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).

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

3. 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).

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