<numeric>: non conformance of std::reduce()

[hikmatfarhat-ndu]

Describe the bug
in std::reduce(), binary_op(*first,*first) must be convertible to T. This isn't the case in the below code yet it compiles.

Command-line test case

C:\Temp>type repro.cpp
#include <iostream>

int main() {
  std::random_device e;
        std::uniform_int_distribution<> dist(1, 10);
        const int n = 10;
        std::vector<int> v(n);
        std::generate(v.begin(), v.end(), [&]() {return dist(e); });  
        const auto result = std::reduce(v.begin(), v.end(), std::make_pair(0, 0),
            [](std::pair<int,int> sum,int n) {
                n % 2 == 1?sum.first += n:sum.second += n;
                return sum;
            });
}

C:\Temp>cl /EHsc /W4 /WX .\repro.cpp
Microsoft (R) C/C++ Optimizing Compiler Version 19.26.28806 for x86
Copyright (C) Microsoft Corporation.  All rights reserved.

repro.cpp
Microsoft (R) Incremental Linker Version 14.26.28806.0
Copyright (C) Microsoft Corporation.  All rights reserved.

/out:repo.exe
repro.obj

Expected behavior
It shouldn't compile

STL version
Microsoft Visual Studio Community 2019 Version 16.6.1

Additional context
gcc and clang reject the above code

[CaseyCarter]

Per [reduce]/5 we are required to diagnose this program as ill-formed now since the requirement is a "Mandates" instead of the previous "Requires". I suspect there may be other similar cases in which a less-than-useful C++17 "Requires" became a C++20 "Mandates" which we will fail to diagnose due to the aforementioned lack of utility. That said, I don't think it would be a worthwhile investment of our time to audit every such change looking for them. Other maintainers, shout if you disagree.

We need to audit both serial and parallel implementations of reduce to determine how many of the four required expressions with required implicit conversions we actually use - I suspect it's one or two at most since convertibility requirements are usually defects in the Standard wording - and either add some static_asserts to enforce the Mandates or file an LWG issue for permission to do otherwise.

[timsong-cpp]

The convertibility requirements are bogus but most of the callability requirements are real, I think?

Rejecting this code (which is totally misusing reduce when it should use accumulate) seems like an improvement to me.

[CaseyCarter]

The convertibility requirements are bogus but most of the callability requirements are real, I think?

binary_op(init, init) requires binary_op to accept two lvalues of type T, a pattern which appears in no possible expansion of GENERALIZED_SUM(binary_op, init, *i, ...), so it's not useful for computing the return value. The other patterns are necessary (but insufficient) to compute the return value.

[statementreply]

The convertibility requirements are bogus but most of the callability requirements are real, I think?

binary_op(init, init) requires binary_op to accept two lvalues of type T, a pattern which appears in no possible expansion of GENERALIZED_SUM(binary_op, init, *i, ...), so it's not useful for computing the return value. The other patterns are necessary (but insufficient) to compute the return value.

I think that the requirements are sufficient (and in this case necessary) if all intermediate binary_op results are converted to T first. In other words, the requirements on init also apply to binary_op results, given them being of the same type.

Let T be the type of init, U be the type of *i, a + b be binary_op(a, b), arg... be at least one argument, ∑(arg...) be GENERALIZED_SUM(binary_op, arg...). With the following assumptions:

• ∑(*i) → U
• ∑(init) → T
• ∑(*i, *j...) → T
• ∑(init, *i...) → T

The following requirements are sufficient and necessary:

• ∑(*i, *j) = ∑(*i) + ∑(*j), requires U + U → T
• ∑(*i, *j, *k...) = ∑(*i) + ∑(*j, *k...), requires U + T → T
• ∑(*i, *j, *k...) = ∑(*j, *k...) + ∑(*i), requires T + U → T
• ∑(*i, *j, *k, *l...) = ∑(*i, *j...) + ∑(*k, *l...), requires T + T → T
• ∑(init, *i) = ∑(init) + ∑(*i), requires T + U → T
• ∑(init, *i) = ∑(*i) + ∑(init), requires U + T → T
• ∑(init, *i, *j...) = ∑(init) + ∑(*i, *j...), requires T + T → T
• ∑(init, *i, *j...) = ∑(*i, *j...) + ∑(init), requires T + T → T
• ∑(init, *i, *j...) = ∑(*i) + ∑(init, *j...), requires U + T → T
• ∑(init, *i, *j...) = ∑(init, *j...) + ∑(*i), requires T + U → T
• ∑(init, *i, *j, *k...) = ∑(init, *i...) + ∑(*j, *k...), requires T + T → T
• ∑(init, *i, *j, *k...) = ∑(*i, *j...) + ∑(init, *k...), requires T + T → T

[CaseyCarter]

The convertibility requirements are bogus but most of the callability requirements are real, I think?

binary_op(init, init) requires binary_op to accept two lvalues of type T, a pattern which appears in no possible expansion of GENERALIZED_SUM(binary_op, init, *i, ...), so it's not useful for computing the return value. The other patterns are necessary (but insufficient) to compute the return value.

I think that the requirements are sufficient (and in this case necessary) if all intermediate binary_op results are converted to T first. In other words, the requirements on init also apply to binary_op results, given them being of the same type.

The permissible expansions of GENERALIZED_SUM(binary_op, init, *i, ...) include no conversions to T other than the conversion implied by the fact that reduce's declared return type is T. So while there may be a calculation for which these requirements are useful, calculating the specified return value of reduce is not it.

[statementreply]

The convertibility requirements are bogus but most of the callability requirements are real, I think?

binary_op(init, init) requires binary_op to accept two lvalues of type T, a pattern which appears in no possible expansion of GENERALIZED_SUM(binary_op, init, *i, ...), so it's not useful for computing the return value. The other patterns are necessary (but insufficient) to compute the return value.

I think that the requirements are sufficient (and in this case necessary) if all intermediate binary_op results are converted to T first. In other words, the requirements on init also apply to binary_op results, given them being of the same type.

The permissible expansions of GENERALIZED_SUM(binary_op, init, *i, ...) include no conversions to T other than the conversion implied by the fact that reduce's declared return type is T. So while there may be a calculation for which these requirements are useful, calculating the specified return value of reduce is not it.

It isn't strictly necessary to convert binary_op(init, init) to T to evaluate GENERALIZED_SUM. However, it grants STL permission to spare intermediate results to Ts during (parallel) evaluation whenever desirable, without knowledge of the type of binary_op(...) (possibly non-determined at compile time).

Example (shouldn't compile)

#include <iostream>
#include <numeric>
#include <vector>

template <int N>
struct element_t {
    template <int M>
    friend auto operator+(element_t<N>, element_t<M>) {
        return element_t<N + M>{};
    }
};

using element = element_t<1>;

class accumulator {
public:
    accumulator() = default;

    int value() const { return value_; }

    template <int N>
    friend accumulator operator+(accumulator a, element_t<N>) {
        return accumulator{a.value() + N};
    }

    template <int N>
    friend accumulator operator+(element_t<N>, accumulator a) {
        return accumulator{N + a.value()};
    }

    friend accumulator operator+(accumulator a, accumulator b) = delete;

private:
    explicit accumulator(int val) : value_{val} {}

    int value_ = 0;
};

int main() {
    std::vector<element> x(100);
    std::cout << std::reduce(x.begin(), x.end(), accumulator{}).value() << "\n";
}

[CaseyCarter]

It isn't strictly necessary to convert binary_op(init, init) to T to evaluate GENERALIZED_SUM. However, it grants STL permission to spare intermediate results to Ts during (parallel) evaluation whenever desirable

Yes, the intent of the conversions to T is to allow intermediate results to be stored in a T. However GENERALIZED_SUM(binary_op, init, *i, ...) includes no conversions to T, and the semantics of the conversion to T are not specified, so we cannot prove that the value produced by any sequence of operations that includes conversions to T is equal to the value of some permissible expansion of GENERALIZED_SUM(binary_op, init, *i, ...). So while the STL has permission to store intermediate results, that permission is not useful in calculating the specified return value.

[frederick-vs-ja]

WG21-P0571R2 is supposed to resolve the issue of GENERALIZED_SUM, although the current revision is still less than ideal.
(Not yet rebased onto Mandates; only implicit conversion is mandatory, but explicit cast is specified in several places.)