[libc++] Allow transforming to a different type in transform_inclusive_scan

[philnik]

Summary

Fixes #60143

[Mordante]

libcxx/include/__numeric/transform_inclusive_scan.h

45

I'm not fond of auto here.

48

I'm not sure this approach is valid.
http://eel.is/c++draft/transform.inclusive.scan#3.1

If init is provided, T meets the Cpp17MoveConstructible (Table 32) requirements; otherwise, U meets the Cpp17MoveConstructible requirements.

If U (decltype(first)) is movable but T (decltype(__init)) isn't this code may violate the precondition. We even require __init to be copyable.

I wonder whether that's a bug in the Standard, since I'm unsure how to implement the init version with a non-copyable type. But at least here a copy feels wrong to me.

[huixie90]

libcxx/include/__numeric/transform_inclusive_scan.h

48

If T is provided, the spec mandates binary_­op(init, unary_­op(*first)) are convertible to T, and T meets the Cpp17MoveConstructible. so

__init = __b(__init, __u(*__first));

is valid expression (rhs expression convertible to T, and then a move construction)

if T is not provided, binary_­op(unary_­op(*first), unary_­op(*first)) is convertible to U, and U meets the Cpp17MoveConstructible. (note U is iterator_traits<Iter>::value_type here. So I think the spec only guarantees that

value_type val = ...;
decltype(auto) tmp = *first; // not quite, I think if we had range version, we need `iter_common_reference` for this to be valid.
val = __b(__u(tmp), __u(*++first));

The legacy algorithm's constraints are not very accurate in general in my opinion.

But I think @philnik 's change is an improvement in general. but yes I think we should std::move(__init) here

libcxx/include/__numeric/transform_inclusive_scan.h

 
 template <class _InputIterator, class _OutputIterator, class _BinaryOp, class _UnaryOp>
 _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_SINCE_CXX20
 _OutputIterator
 transform_inclusive_scan(_InputIterator __first, _InputIterator __last,
                                _OutputIterator __result, _BinaryOp __b, _UnaryOp __u)
 {
     if (__first != __last) {
-        typename iterator_traits<_InputIterator>::value_type __init = __u(*__first);
+        auto __init = __u(*__first);
         *__result++ = __init;
         if (++__first != __last)
             return _VSTD::transform_inclusive_scan(__first, __last, __result, __b, __u, __init);
     }
 
     return __result;
 }
 
 #endif // _LIBCPP_STD_VER > 14
 
 _LIBCPP_END_NAMESPACE_STD
 
 #endif // _LIBCPP___NUMERIC_TRANSFORM_INCLUSIVE_SCAN_H

libcxx/test/std/numerics/numeric.ops/transform.inclusive.scan/transform_inclusive_scan_bop_uop.pass.cpp

 
 struct add_one {
     template <typename T>
     constexpr T operator()(T x) const {
         return x + 1;
     }
 };
 
+class MyInt {
+  int i_;
+
+public:
+  constexpr MyInt() = default;
+  constexpr MyInt(int i) : i_(i) {}
+
+  constexpr int get() { return i_; }
+
+  constexpr friend bool operator==(MyInt lhs, MyInt rhs) { return lhs.get() == rhs.get(); }
+};
+
+struct transform_to_type {
+  template <class T>
+  constexpr MyInt operator()(T) const {
+    return {};
+  }
+};
+
 template <class Iter1, class BOp, class UOp, class T>
 TEST_CONSTEXPR_CXX20 void
 test(Iter1 first, Iter1 last, BOp bop, UOp uop, const T *rFirst, const T *rLast)
 {
     assert((rLast - rFirst) <= 5);  // or else increase the size of "out"
     T out[5];
 
     // Not in place
for (size_t i = 0; i < v.size(); ++i)
         assert(v[i] == triangle(i + 1) + i + 1);
     }
 
     {
     std::array<size_t, 0> v, res;
     std::transform_inclusive_scan(v.begin(), v.end(), res.begin(), std::plus<>(), add_one{});
     assert(res.empty());
     }
+
+  {
+    std::array a{1, 2, 3, 4};
+    std::array<MyInt, 4> b;
+    std::transform_inclusive_scan(
+        begin(a),
+        end(a),
+        begin(b),
+        [](MyInt lhs, MyInt rhs) { return MyInt{lhs.get() + rhs.get()}; },
+        [](int i) { return MyInt{i + 1}; });
+    assert((b == std::array<MyInt, 4>{2, 5, 9, 14}));
+  }
 }
 
 TEST_CONSTEXPR_CXX20 bool
 test()
 {
     basic_tests();
 
 //  All the iterator categories