2687. {inclusive,exclusive}_scan misspecified

Section: 29.8.7 [exclusive.scan], 29.8.8 [inclusive.scan], 29.8.9 [transform.exclusive.scan], 29.8.10 [transform.inclusive.scan] Status: C++17 Submitter: Tim Song Opened: 2016-03-21 Last modified: 2017-07-30

Priority: 1

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 29.8.8 [inclusive.scan]/2 says of inclusive_scan:

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

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 29.8.7 [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 29.8.8 [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 29.8.9 [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 29.8.10 [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.