[Bug libstdc++/109229] New: std::exclusive_scan narrows to initial value

[Bug libstdc++/109229] New: std::exclusive_scan narrows to initial value

[gnu-bugzilla at ribizel dot de]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=109229

            Bug ID: 109229
           Summary: std::exclusive_scan narrows to initial value
           Product: gcc
           Version: 13.0
            Status: UNCONFIRMED
          Severity: normal
          Priority: P3
         Component: libstdc++
          Assignee: unassigned at gcc dot gnu.org
          Reporter: gnu-bugzilla at ribizel dot de
  Target Milestone: ---

Take the following piece of code:
```
#include <vector>
#include <numeric>
#include <iostream>
#include <limits>
#include <cstdint>

int main() {
        std::vector<std::int64_t> vec{1LL << 32, 0};
        std::exclusive_scan(vec.begin(), vec.end(), vec.begin(), 0);
        std::cout << vec[0] << '\n';
        std::cout << vec[1] << '\n';
}
```
I would expect this to output 0 and 1LL<<32, but it outputs 0, 0, because T in
std::exclusive_scan is deduced as int, which is the computational type that
will be used in exclusive_scan. Not sure if this is a library or standard
defect, but I think this is pretty bug-prone otherwise. Other standard library
implementations have the same issue, see
https://github.com/NVIDIA/thrust/issues/1896 and
https://github.com/llvm/llvm-project/issues/61575.

[Bug libstdc++/109229] std::exclusive_scan narrows to initial value

[redi at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=109229

--- Comment #1 from Jonathan Wakely <redi at gcc dot gnu.org> ---
This is how all standard algorithms that take an initial value work.

[Bug libstdc++/109229] std::exclusive_scan narrows to initial value

[gnu-bugzilla at ribizel dot de]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=109229

--- Comment #2 from Tobias Ribizel <gnu-bugzilla at ribizel dot de> ---
I agree, but that doesn't make it less bug-prone IMO, with the narrowing
conversion happening deep inside the exclusive_scan implementation (-Wnarrowing
doesn't pick it up). Something similar like common_type<T,
invoke_result<binary_op, InputIt::value_type, T>> would be much safer.

[Bug libstdc++/109229] std::exclusive_scan narrows to initial value

[redi at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=109229

--- Comment #3 from Jonathan Wakely <redi at gcc dot gnu.org> ---
e.g. https://en.cppreference.com/w/cpp/algorithm/accumulate is clear that the
accumulator has the same type as the init parameter, and there's even a caveat
about it:
https://en.cppreference.com/w/cpp/algorithm/accumulate#Common_mistakes

[Bug libstdc++/109229] std::exclusive_scan narrows to initial value

[redi at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=109229

--- Comment #4 from Jonathan Wakely <redi at gcc dot gnu.org> ---
Maybe we could do this:

--- a/libstdc++-v3/include/std/numeric
+++ b/libstdc++-v3/include/std/numeric
@@ -483,12 +483,16 @@ namespace __detail
                   _OutputIterator __result, _Tp __init,
                   _BinaryOperation __binary_op)
     {
-      while (__first != __last)
+      if (__first != __last)
        {
-         auto __v = __init;
-         __init = __binary_op(__init, *__first);
-         ++__first;
-         *__result++ = std::move(__v);
+         auto __sum = __binary_op(__init, *__first);
+         *__result++ = std::move(__init);
+         while (++__first != __last)
+           {
+             auto __tmp = __sum;
+             __sum = __binary_op(__sum, *__first);
+             *__result++ = std::move(__tmp);
+           }
        }
       return __result;
     }

We'd need something similar for inclusive_scan, reduce etc.

But I don't think this is actually allowed by the standard. It clearly lists
the forms allowed when invoking the summation operator, and binary_op(sum,
*first) isn't one of them.

The reason for the requirement that the result of the summation operation can
be converted to T is precisely so that the summation can be done in that type.

[Bug libstdc++/109229] std::exclusive_scan narrows to initial value

[redi at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=109229

--- Comment #5 from Jonathan Wakely <redi at gcc dot gnu.org> ---
(In reply to Tobias Ribizel from comment #2)
> Something similar like common_type<T,
> invoke_result<binary_op, InputIt::value_type, T>> would be much safer.

No, there's no requirement that those types have a common type.

You can have two types which are valid inputs to the binary operator, but which
cannot be converted to each other.

[Bug libstdc++/109229] std::exclusive_scan narrows to initial value

[redi at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=109229

--- Comment #6 from Jonathan Wakely <redi at gcc dot gnu.org> ---
Ah yes, this issue is the subject of
https://www.open-std.org/jtc1/sc22/wg21/docs/papers/2018/p0571r2.html#intermediate_unordered
which is waiting for a new revision from the author.